Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 4 results · all verified · 2 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 2 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Point-to-Point Source–Channel Separation

1 · Prerequisites

2 · Summary

This page proves asymptotic separation for finite IID sources sent through finite discrete memoryless channels. A code maps a source block to a channel input block and decodes the output block; the channel-use ratio has a fixed limit $n_{k} / k \to ρ \in (0, \infty)$ . The lossless threshold compares source entropy in nats with channel capacity in nats per use. The lossy threshold compares the finite information rate-distortion value in bits—converted to nats—with the same channel budget. Distortion is finite and bounded, and the rate-distortion budget is feasible and attained. The achievability arguments use maximal-error channel codes because a source-code index need not be uniform; the converses use information bounds and do not require channel-code constructions. The results concern asymptotic block criteria and make no finite-block, zero-delay, or universal matching claim.

\begin{tikzpicture}[>=stealth]
  \node (s) at (0,0) {$S^k$};
  \node[draw] (f) at (2,0) {$f_k$};
  \node (x) at (4,0) {$X^n$};
  \node[draw] (w) at (6,0) {$W^n$};
  \node (y) at (8,0) {$Y^n$};
  \node[draw] (g) at (10,0) {$g_k$};
  \node (shat) at (12,0) {$\widehat S^k$};
  \draw[->] (s.east) -- (f.west);
  \draw[->] (f.east) -- (x.west);
  \draw[->] (x.east) -- (w.west);
  \draw[->] (w.east) -- (y.west);
  \draw[->] (y.east) -- (g.west);
  \draw[->] (g.east) -- (shat.west);
\end{tikzpicture}

The boxes $f_{k}$ and $g_{k}$ are deterministic maps; $W^{n}$ is the stochastic product transition law of the DMC. This diagram records the code interface only; none of the proofs relies on it.

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Finite-alphabet point-to-point joint source-channel codes

Definition

Let $S, X, Y, \hat{S}$ be nonempty finite alphabets, let $P_{S}$ be a probability vector on $S$ , and let $W$ be a finite discrete memoryless channel from $X$ to $Y$ as in Finite discrete memoryless channels. For positive integers $k, n$ , a deterministic $(k, n)$ joint source-channel code is a pair of maps $f_{k} : S^{k} \to X^{n}, g_{k} : Y^{n} \to {\hat{S}}^{k} .$ The source block has law $P_{S}^{\otimes k}$ , the channel output conditional on input $x^{n}$ has law $W^{n} (\cdot ∣ x^{n})$ , and the reproduction is ${\hat{S}}^{k} = g_{k} (Y^{n})$ . The code has no feedback.

A code sequence at channel-use ratio $ρ$ consists of such codes with source lengths $k \to \infty$ , channel lengths $n_{k}$ , and $n_{k} / k \to ρ \in (0, \infty)$ . In the lossless case $\hat{S} = S$ , its block error is $\Pr [{\hat{S}}^{k} \neq S^{k}]$ . In the lossy case, for finite nonnegative single-letter distortion $d$ , its normalized block distortion is $d_{k}$ from Single-letter and block distortion; expected distortion and the positive-slack excess-distortion probabilities $\Pr [d_{k} > D + ε]$ for every $ε > 0$ are distinct criteria.

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

Finite-IID lossless source coding above entropy

Statement

Let $P_{S}$ be a probability vector on a finite nonempty alphabet $S$ , and define its entropy in nats by

$H (P_{S}) : = - \sum_{s : P_{S} (s) > 0} P_{S} (s) \ln P_{S} (s) .$

For every $R > H (P_{S})$ , there are deterministic fixed-length codes $f_{k} : S^{k} \to [M_{k}]$ , $g_{k} : [M_{k}] \to S^{k}$ for the IID source $P_{S}^{\otimes k}$ such that $\Pr [g_{k} (f_{k} (S^{k})) \neq S^{k}] \to 0$ and ${lim sup}_{k \to \infty} k^{- 1} \ln M_{k} < R$ .

Facts & Assumptions

Given: A finite nonempty alphabet $S$ , a probability vector $P_{S}$ , and a rate $R > H (P_{S})$ .

[A1]

The letters $S_{1}, S_{2}, \dots$ are IID with law $P_{S}$ ; $S^{k} = (S_{1}, \dots, S_{k})$ .

Proof

1.1A1givenchoosealgebra

Choose $δ$ with $0 < δ < R - H (P_{S})$ . On the support of $P_{S}$ , let $Z_{i} = - \ln P_{S} (S_{i})$ . This is a finite-valued IID sequence with mean $H (P_{S})$ and finite variance $σ^{2}$ . For ${\overline{Z}}_{k} = k^{- 1} \sum_{i = 1}^{k} Z_{i}$ , independence gives $E ({\overline{Z}}_{k} - H (P_{S}))^{2} = σ^{2} / k$ ; the pointwise bound $1_{{∣ {\overline{Z}}_{k} - H (P_{S}) ∣ \geq δ}} \leq ({\overline{Z}}_{k} - H (P_{S}))^{2} / δ^{2}$ therefore yields $\Pr [{\overline{Z}}_{k} > H (P_{S}) + δ] \leq σ^{2} / (k δ^{2}) \to 0$ .

2.1A1step 1.1algebra

Define $T_{k} : = {s^{k} : P_{S}^{\otimes k} (s^{k}) > 0, - k^{- 1} \ln P_{S}^{\otimes k} (s^{k}) \leq H (P_{S}) + δ}$ . By step 1.1, $P_{S}^{\otimes k} (T_{k}) \to 1$ . Every $s^{k} \in T_{k}$ has probability at least $e^{- k (H (P_{S}) + δ)}$ , so $∣ T_{k} ∣ e^{- k (H (P_{S}) + δ)} \leq \sum_{s^{k} \in T_{k}} P_{S}^{\otimes k} (s^{k}) \leq 1$ ; hence $∣ T_{k} ∣ \leq e^{k (H (P_{S}) + δ)}$ .

3.1A1step 2.1construct

Put $M_{k} = ⌈ e^{k (H (P_{S}) + δ)} ⌉$ and inject the finite set $T_{k}$ into $[M_{k}]$ . Encode each $s^{k} \in T_{k}$ by its assigned message and every other source word by message $1$ ; decode an assigned message to its unique word and unused messages to a fixed word of $S^{k}$ . This defines deterministic maps, and decoding is correct on $T_{k}$ , so the block-error probability is at most $P_{S}^{\otimes k} (T_{k}^{c}) \to 0$ .

4.1givenstep 3.1algebra∎

Since $⌈ e^{x} ⌉ \leq 2 e^{x}$ for $x \geq 0$ , $k^{- 1} \ln M_{k} \leq H (P_{S}) + δ + k^{- 1} \ln 2$ . Its limsup is at most $H (P_{S}) + δ < R$ , proving the rate claim.

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

Finite-IID rate-distortion mutual-information converse

Statement

Let $S_{1}, \dots, S_{k}$ be IID with law $P_{S}$ on a finite nonempty alphabet $S$ , let $\hat{S}$ be finite nonempty, and let $d : S \times \hat{S} \to [0, \infty)$ be finite-valued. For any joint law of $S^{k}$ and ${\hat{S}}^{k}$ , put $D_{k} : = E d_{k} (S^{k}, {\hat{S}}^{k})$ , using the normalized block distortion of Single-letter and block distortion. If $R (D)$ is the finite-alphabet information rate-distortion function in bits from Finite-alphabet information rate-distortion function, then

$\ln 2 R (D_{k}) \leq \frac{1}{k} I (S^{k}; {\hat{S}}^{k}),$

where mutual information on the right is in nats. The test channel induced by the joint law is feasible at distortion $D_{k}$ , so the rate-distortion minimum is attained there by Attainment of finite-alphabet rate-distortion minima.

Facts & Assumptions

Given: A finite IID source, finite reproduction alphabet, finite nonnegative distortion, and any joint distribution of $S^{k}, {\hat{S}}^{k}$ .

[A1]

$S_{1}, \dots, S_{k}$ are IID with common law $P_{S}$ ; hence each coordinate has law $P_{S}$ and is independent of its predecessors.

[F1]

Finite-alphabet information rate-distortion function and Attainment of finite-alphabet rate-distortion minima: $R (D)$ is the minimum finite mutual information in bits over test channels with source law $P_{S}$ and expected distortion at most $D$ ; every feasible minimum is attained.

[F2]

Single-letter and block distortion: $d_{k} (s^{k}, {\hat{s}}^{k}) = k^{- 1} \sum_{i = 1}^{k} d (s_{i}, {\hat{s}}_{i})$ .

[F3]

Finite mutual information and Finite entropy and mutual-information chain rules: finite mutual information has the chain rule, including $I (U; V, Z) = I (U; Z) + I (U; V ∣ Z)$ .

[F4]

Finite conditional mutual information identities and equality: finite conditional mutual information is nonnegative.

[F5]

Finite information quantities convert by the logarithm base: information in bits equals information in nats divided by $\ln 2$ .

Proof

1.1A1F1F2givenconstruct

Let $T$ be uniform on $[k]$ , independent of $(S^{k}, {\hat{S}}^{k})$ , and put $(S, \hat{S}) = (S_{T}, {\hat{S}}_{T})$ . By [A1], $S$ has law $P_{S}$ ; by [F2], $E d (S, \hat{S}) = k^{- 1} \sum_{i} E d (S_{i}, {\hat{S}}_{i}) = D_{k}$ . For each $s$ with $P_{S} (s) > 0$ , the conditional law of $\hat{S}$ given $S = s$ is a probability vector; choose any probability-vector row for zero-mass $s$ . This gives a finite test channel with source law $P_{S}$ and distortion $D_{k}$ , so it is feasible in [F1].

1.2A1F3F4givenalgebra

The chain rule [F3] gives $I (S^{k}; {\hat{S}}^{k}) = \sum_{i = 1}^{k} I (S_{i}; {\hat{S}}^{k} ∣ S^{i - 1})$ . Since $I (S_{i}; S^{i - 1}) = 0$ by [A1], the chain rule gives $I (S_{i}; {\hat{S}}^{k} ∣ S^{i - 1}) = I (S_{i}; {\hat{S}}^{k}, S^{i - 1})$ . Write $U_{i} = ({\hat{S}}^{k}, S^{i - 1})$ ; its coordinate ${\hat{S}}_{i}$ is a function of $U_{i}$ , so $I (S_{i}; U_{i}, {\hat{S}}_{i}) = I (S_{i}; U_{i})$ . Expanding the left side by [F3] and using [F4] yields $I (S_{i}; U_{i}) = I (S_{i}; {\hat{S}}_{i}) + I (S_{i}; U_{i} ∣ {\hat{S}}_{i}) \geq I (S_{i}; {\hat{S}}_{i})$ . Summing proves $\sum_{i} I (S_{i}; {\hat{S}}_{i}) \leq I (S^{k}; {\hat{S}}^{k})$ .

2.1F1F3F4F5step 1.1step 1.2algebra∎

By the chain rule, $I (S; \hat{S} ∣ T) = k^{- 1} \sum_{i} I (S_{i}; {\hat{S}}_{i})$ . Since $S$ and $T$ are independent, $I (S; \hat{S}, T) = I (S; \hat{S} ∣ T)$ ; also $I (S; \hat{S}, T) = I (S; \hat{S}) + I (S; T ∣ \hat{S}) \geq I (S; \hat{S})$ by [F3]–[F4]. Thus $I (S; \hat{S}) \leq k^{- 1} \sum_{i} I (S_{i}; {\hat{S}}_{i}) \leq k^{- 1} I (S^{k}; {\hat{S}}^{k})$ by step 1.2. The test channel in step 1.1 is feasible, so [F1] gives $R (D_{k}) \leq I_{2} (S; \hat{S})$ , where the subscript denotes bits. Multiply by $\ln 2$ and use [F5] to obtain the claimed nats inequality.

TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passOpen item page →

Lossless separation for finite IID sources and finite DMCs

Statement

Let $S_{1}, S_{2}, \dots$ be IID with probability vector $P_{S}$ on a finite nonempty alphabet $S$ , and let $W$ be a finite DMC with capacity $C (W)$ in nats per channel use. Write $H (P_{S}) : = - \sum_{s : P_{S} (s) > 0} P_{S} (s) \ln P_{S} (s)$ for source entropy in nats. Fix positive integers $n_{k}$ with $n_{k} / k \to ρ \in (0, \infty)$ . A deterministic $(k, n_{k})$ joint code is as in Finite-alphabet point-to-point joint source-channel codes. If $H (P_{S}) = 0$ , a zero-error code sequence exists for every such $W$ . If $H (P_{S}) < ρ C (W)$ , there are codes with block error tending to zero. Conversely, every code sequence with block error tending to zero satisfies $H (P_{S}) \leq ρ C (W)$ . Thus strict violation $H (P_{S}) > ρ C (W)$ rules out reliable transmission; the positive-entropy equality boundary is not asserted.

Facts & Assumptions

Given: A finite IID source, a finite DMC, positive blocklengths with $n_{k} / k \to ρ > 0$ , and deterministic joint codes.

[A1]

The source blocks have law $P_{S}^{\otimes k}$ , and $H (P_{S}) = - \sum_{s : P_{S} (s) > 0} P_{S} (s) \ln P_{S} (s)$ is measured in nats.

[F1]

Finite-alphabet point-to-point joint source-channel codes: an encoder maps $S^{k} \to X^{n_{k}}$ and a decoder maps $Y^{n_{k}} \to S^{k}$ in the lossless case.

[F2]

Single-letter information capacity of a finite DMC: $C (W)$ is the supremum of single-letter mutual information in nats per channel use.

[F3]

Average-error and maximal-error DMC capacities and Operational capacity formula for a finite DMC: the maximal-error capacity is the supremum of maximal-error achievable rates and equals $C (W)$ .

[F4]

Finite-IID lossless source coding above entropy: every source-code rate strictly above $H (P_{S})$ admits deterministic fixed-length source codes with block error tending to zero.

[F5]

The n-letter mutual information of a DMC is at most nC: for every input law on $X^{n}$ , $I (X^{n}; Y^{n}) \leq n C (W)$ .

[F6]

Finite-alphabet Fano inequality: for an estimate of a finite-alphabet random variable with error probability $p$ , $H (S^{k} ∣ {\hat{S}}^{k}) \leq \ln 2 + p \ln ∣ S ∣^{k}$ .

[F7]

Data processing for a finite Markov chain, with equality condition: along a finite Markov chain, mutual information cannot increase from the first variable to the last.

[F8]

Finite entropy and mutual-information chain rules: finite entropy and mutual information obey the chain rule, and IID coordinates have $H (S^{k}) = k H (P_{S})$ .

Proof

1.1A1F1givenchooseconstructalgebra

If $H (P_{S}) = 0$ , each nonzero term $- P_{S} (s) \ln P_{S} (s)$ is nonnegative, so exactly one source letter has probability one. Choose that letter $s_{0}$ and any channel input letter $x_{0}$ , encode every source block as $x_{0}^{n_{k}}$ , and decode every output to $s_{0}^{k}$ . This is a deterministic joint code with zero error.

1.2A1F4givenchoosealgebra

Now assume $0 < H (P_{S}) < ρ C (W)$ . Choose $η > 0$ with $H (P_{S}) + 2 η < ρ C (W)$ . By [F4], choose source codes with message counts $M_{k}$ , source block error tending to zero, and ${lim sup}_{k} k^{- 1} \ln M_{k} \leq H (P_{S}) + η$ . Then ${lim sup}_{k} n_{k}^{- 1} \ln M_{k} \leq (H (P_{S}) + η) / ρ < C (W)$ .

1.3A1F2F5F6F7F8givenalgebra

For any joint code, ${\hat{S}}^{k}$ is a function of $Y^{n_{k}}$ , so [F7] gives $I (S^{k}; {\hat{S}}^{k}) \leq I (S^{k}; Y^{n_{k}})$ . The encoder is deterministic and the DMC output law given $S^{k} = s^{k}$ is $W^{n_{k}} (\cdot ∣ f_{k} (s^{k}))$ ; averaging its finite conditional entropies by the value of $X^{n_{k}} = f_{k} (S^{k})$ gives $H (Y^{n_{k}} ∣ S^{k}) = H (Y^{n_{k}} ∣ X^{n_{k}})$ . By [F8], $I (S^{k}; Y^{n_{k}}) = I (X^{n_{k}}; Y^{n_{k}})$ , which is at most $n_{k} C (W)$ by [F2] and [F5]. If $p_{k} = \Pr [{\hat{S}}^{k} \neq S^{k}]$ , then [F6] and [F8] give $k H (P_{S}) \leq n_{k} C (W) + \ln 2 + p_{k} k \ln ∣ S ∣$ . Dividing by $k$ and taking $k \to \infty$ along a reliable code sequence proves $H (P_{S}) \leq ρ C (W)$ .

2.1F1F3step 1.2givenconstructalgebra

Choose a rate $R_{c}$ strictly between $(H (P_{S}) + η) / ρ$ and $C (W)$ . By [F3] and the supremum property, some maximal-error achievable rate $R^{'} > R_{c}$ exists, so its channel-code sequence has ${lim inf}_{n} n^{- 1} \ln L_{n} \geq R^{'}$ and maximal errors tending to zero. Since $n_{k} \to \infty$ , eventually $\ln L_{n_{k}} / n_{k} > R_{c} > \ln M_{k} / n_{k}$ . Restrict each such code to $M_{k}$ messages; mapping any discarded decoder output to a retained message preserves every retained message's former correct-decoding event, so maximal error does not increase.

3.1F1step 1.2step 2.1givenconstructalgebra

Compose the source encoder and decoder from step 1.2 with the restricted channel code from step 2.1. The source-code index can have any distribution, but its channel decoding error is at most the maximal error. The joint block-error event is contained in the union of the source-code error event and the channel message-error event, so its probability is at most the sum of those two probabilities and tends to zero.

4.1step 1.1step 1.2step 2.1step 3.1step 1.3algebra∎

Step 1.1 gives zero-error achievability when the source entropy is zero; steps 1.2, 2.1, and 3.1 give reliable achievability under the strict positive-entropy threshold; and step 1.3 gives the necessary condition. Thus the stated strict-threshold conclusions hold, with no claim at the positive-entropy equality boundary.

TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passOpen item page →

Lossy separation for finite IID sources and finite DMCs

Statement

Let $S_{1}, S_{2}, \dots$ be IID with probability vector $P_{S}$ on a finite nonempty alphabet $S$ . Let $\hat{S}$ be finite nonempty, let $d : S \times \hat{S} \to [0, d_{\max}]$ be finite-valued distortion, and let $D_{\min} : = \sum_{s} P_{S} (s) \min_{\hat{s}} d (s, \hat{s})$ . For $D \geq D_{\min}$ , let $R (D)$ be the finite-alphabet information rate-distortion function in bits from Finite-alphabet information rate-distortion function and put $r (D) : = (\ln 2) R (D)$ nats per source symbol. Let $W$ be a finite DMC with capacity $C (W)$ nats per channel use, and fix positive integers $n_{k}$ with $n_{k} / k \to ρ \in (0, \infty)$ . For either criterion separately—expected distortion ${lim sup}_{k} E d_{k} \leq D$ , or positive-slack excess distortion $\Pr [d_{k} > D + ε] \to 0$ for every $ε > 0$ —the following hold for deterministic joint codes as in Finite-alphabet point-to-point joint source-channel codes:

If $r (D) < ρ C (W)$ , codes achieving the criterion exist.
If $R (D) = 0$ , a one-message constant-reproduction code achieves both criteria for every channel.
Any code sequence achieving either criterion must satisfy $r (D) \leq ρ C (W)$ . Thus $r (D) > ρ C (W)$ is impossible; the positive-rate equality boundary is not asserted.

Facts & Assumptions

Given: A finite IID source, finite reproduction alphabet, bounded finite distortion, feasible budget $D$ , finite DMC, and $n_{k} / k \to ρ > 0$ .

[A1]

The source blocks have law $P_{S}^{\otimes k}$ ; distortion is the normalized additive block distortion $d_{k}$ of Single-letter and block distortion, with $0 \leq d_{k} \leq d_{\max}$ .

[F1]

Finite-alphabet information rate-distortion function and Attainment of finite-alphabet rate-distortion minima: $R (D)$ is the minimum test-channel mutual information in bits for a feasible distortion budget, and the minimum is attained.

[F2]

Fixed-length operational rate-distortion functions and Finite-alphabet memoryless rate-distortion coding theorem: for each of the expected and positive-slack excess criteria, source codes exist at rates arbitrarily close above $R (D)$ ; expected distortion has limsup at most $D$ , and every positive-slack excess probability tends to zero.

[F3]

Average-error and maximal-error DMC capacities, Fixed-length codes for a finite DMC, Average and maximal error of a fixed-length code, and Operational capacity formula for a finite DMC: maximal-error capacity is the supremum of maximal-error achievable rates and equals $C (W)$ ; per-message errors define maximal error.

[F4]

Finite-IID rate-distortion mutual-information converse: for any reconstruction of $S^{k}$ with expected distortion $D_{k}$ , $r (D_{k}) \leq k^{- 1} I (S^{k}; {\hat{S}}^{k})$ .

[F5]

Convexity, monotonicity, and continuity of finite rate-distortion: $R (D)$ is nonincreasing and right-continuous on the feasible distortion interval.

[F6]

The n-letter mutual information of a DMC is at most nC: $I (X^{n}; Y^{n}) \leq n C (W)$ for every DMC input law.

[F7]

Data processing for a finite Markov chain, with equality condition: if ${\hat{S}}^{k}$ is a function of $Y^{n}$ , then $I (S^{k}; {\hat{S}}^{k}) \leq I (S^{k}; Y^{n})$ .

[F8]

Finite mutual information and Finite KL divergence is nonnegative with equality exactly at equal laws: mutual information is the KL divergence from the joint law to the product law, and it is zero exactly when those laws agree.

[F9]

Finite information quantities convert by the logarithm base: bits equal nats divided by $\ln 2$ .

[F10]

Finite entropy and mutual-information chain rules: finite mutual information is $I (U; V) = H (V) - H (V ∣ U)$ .

Proof

1.1A1F1F8F9givenchooseconstructalgebra

Suppose $R (D) = 0$ . By [F1] choose a minimizing test channel; its mutual information is zero in bits and hence in nats by [F9]. By [F8], source and reproduction under that test channel are independent. If $q (\hat{s})$ is its reproduction marginal, then $\sum_{\hat{s}} q (\hat{s}) E d (S, \hat{s}) \leq D$ . This finite weighted average implies some ${\hat{s}}_{0}$ has $E d (S, {\hat{s}}_{0}) \leq D$ . Use one message, a fixed channel input word, and the constant reproduction ${\hat{s}}_{0}^{k}$ . Its expected distortion is at most $D$ . For each $ε > 0$ , the IID bounded variables $Z_{i} = d (S_{i}, {\hat{s}}_{0})$ have mean at most $D$ , finite variance, and variance of their average equal to $Var (Z_{1}) / k$ ; the pointwise bound $1_{{∣ \overline{Z} - E Z_{1} ∣ \geq ε}} \leq (\overline{Z} - E Z_{1})^{2} / ε^{2}$ gives $\Pr [k^{- 1} \sum_{i} Z_{i} > D + ε] \leq Var (Z_{1}) / (k ε^{2}) \to 0$ .

1.2A1F2F9givenchoosealgebra

Now assume $R (D) > 0$ and $r (D) < ρ C (W)$ . Choose $R_{c}$ with $r (D) / ρ < R_{c} < C (W)$ , then choose $η > 0$ so that $(\ln 2) (R (D) + η) / ρ < R_{c}$ . For either chosen source performance criterion, [F2] gives deterministic source codes with message counts $M_{k}$ , that criterion, and ${lim sup}_{k} k^{- 1} \log_{2} M_{k} \leq R (D) + η$ . Therefore ${lim sup}_{k} n_{k}^{- 1} \ln M_{k} \leq (\ln 2) (R (D) + η) / ρ < R_{c}$ .

1.3A1F4F6F7F10givenalgebra

For any joint code, [F7] gives $I (S^{k}; {\hat{S}}^{k}) \leq I (S^{k}; Y^{n_{k}})$ . Given $S^{k} = s^{k}$ , the DMC output has law $W^{n_{k}} (\cdot ∣ f_{k} (s^{k}))$ ; averaging conditional entropies over source words and grouping them by $X^{n_{k}} = f_{k} (S^{k})$ gives $H (Y^{n_{k}} ∣ S^{k}) = H (Y^{n_{k}} ∣ X^{n_{k}})$ . Therefore [F10] yields $I (S^{k}; Y^{n_{k}}) = I (X^{n_{k}}; Y^{n_{k}})$ , and [F6] bounds this by $n_{k} C (W)$ . The rate-distortion bound [F4] at the actual expected distortion $D_{k} = E d_{k}$ then gives $r (D_{k}) \leq (n_{k} / k) C (W)$ .

2.1F3step 1.2givenconstructalgebra

Since $R_{c} < C (W)$ , [F3] and the supremum definition of maximal-error capacity give a maximal-error achievable rate strictly greater than $R_{c}$ . Its channel code sequence has enough messages to include $M_{k}$ for all sufficiently large $n_{k}$ ; restrict to those messages, mapping discarded decoder outputs to a retained message. Correct-decoding regions for retained messages are preserved, so maximal error does not increase. The source-code index may be nonuniform, but its channel error is the weighted average of per-message errors and is bounded by the maximal error.

2.2A1F5step 1.3givenalgebra

If the expected-distortion criterion holds, then for every $ε > 0$ , eventually $D_{k} \leq D + ε$ . Monotonicity in [F5] and step 1.3 imply $r (D + ε) \leq (n_{k} / k) C (W)$ ; taking $k \to \infty$ , then $ε ↓ 0$ , and using right-continuity in [F5] yields $r (D) \leq ρ C (W)$ .

3.1A1F2step 2.1givenconstructalgebra

Compose the source and channel codes. On channel success the reproduction equals the source-code reproduction, while on channel error the normalized distortion is at most $d_{\max}$ . Hence expected distortion is at most the source-code expected distortion plus $d_{\max}$ times the maximal channel error, so its limsup is at most $D$ . For the excess criterion, for every $ε > 0$ , the event ${d_{k}^{j o i n t} > D + ε}$ is contained in the union of the source excess event ${d_{k}^{s o u r c e} > D + ε}$ and the channel error event. Both probabilities tend to zero.

3.2A1F5step 1.3step 2.2givenalgebra

If the positive-slack excess criterion holds, fix $ε > 0$ . Splitting expected distortion at $D + ε / 2$ , boundedness gives $D_{k} \leq D + ε / 2 + d_{\max} \Pr [d_{k} > D + ε / 2]$ , which is at most $D + ε$ for all sufficiently large $k$ . Step 2.2's monotonicity, information bound, and right-continuity argument therefore also gives $r (D) \leq ρ C (W)$ .

4.1step 1.1step 1.2step 2.1step 3.1step 2.2step 3.2algebra∎

The zero-rate construction in step 1.1, the strict-rate construction in steps 1.2, 2.1 and 3.1, and the two converse cases in steps 2.2 and 3.2 prove the stated conclusions; no positive-rate equality case is used.

5 · Examples, counterexamples and false statements

None yet.

Point-to-Point Source–Channel Separation

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Finite-alphabet point-to-point joint source-channel codes

Definition

Finite-IID lossless source coding above entropy

Statement

Facts & Assumptions

Proof

Finite-IID rate-distortion mutual-information converse

Statement

Facts & Assumptions

Proof

Lossless separation for finite IID sources and finite DMCs

Statement

Facts & Assumptions

Proof

Lossy separation for finite IID sources and finite DMCs

Statement

Facts & Assumptions

Proof

5 · Examples, counterexamples and false statements

Sources