DefinitionDefinition: Literature-sourcedProof: Not applicablePipeline-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.

Fixed-length codes for a finite DMC

Definition

For a finite DMC $W$ , a length- $n$ code with $M$ messages is a pair of maps $e : [M] \to X^{n}$ and $d : Y^{n} \to [M]$ , where $n, M \geq 1$ and $[M] : = {1, \dots, M}$ . A message $m$ is encoded as $e (m)$ , passed through the block kernel $W^{n}$ of Finite discrete memoryless channels, and decoded as $d (Y^{n})$ . The encoder and decoder are deterministic; there is no feedback, and no input-cost constraint is imposed.

Depends on

Used by

Small expected average code error need not control maximal error Counterexample
Average and maximal error of a fixed-length code Definition
Average-cost fixed-length codes and operational DMC capacity Definition
Average-error and maximal-error DMC capacities Definition
Causal feedback codes for a finite cost-constrained DMC Definition
Expurgation converts small average error to small maximal error Lemma
Strictly feasible DMC input laws achieve every lower mutual-information rate Lemma
Finite-DMC dependence-testing achievability bound Theorem
Finite-DMC hypothesis-testing meta-converse Theorem
Gallager expurgated exponent lower bound Theorem
Gallager random-coding exponent lower bound Theorem
Lossy separation for finite IID sources and finite DMCs Theorem
Nondegenerate normal approximation for finite unconstrained DMCs Theorem
Operational capacity formula for a finite DMC Theorem
Random coding achieves every rate below finite DMC capacity Theorem
Reliable average-error DMC rates do not exceed capacity Theorem
Sphere-packing converse above the finite-divergence threshold Theorem
Strong converse for finite-alphabet DMCs Theorem

Dependency tree · two levels

4 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Yury Polyanskiy and Yihong Wu, Information Theory: From Coding to Learning, Chapter 19 §19.1 (standard reference, not scraped)
Robert Gallager, Principles of Digital Communication I, Chapter 8 §§8.7.2–8.7.3, MIT OpenCourseWare (standard reference, not scraped)