DefinitionDefinition: AI-adaptedProof: AI-generatedPipeline-generatedprecheck pendingjudge pass (gpt-6-luna)

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 lossless block codes and error probability

Definition

Consider a finite nonempty alphabet $A$ , a positive integer $n$ , a probability law $P_{n}$ on $A^{n}$ , and a rate $R \geq 0$ in bits per symbol. A rate- $R$ fixed-length block code consists of a nonempty message set $M \subseteq {0, 1}^{⌊ n R ⌋}$ , an encoder $e : A^{n} \to M$ , and a decoder $d : M \to A^{n}$ . Thus $∣ M ∣ \leq 2^{⌊ n R ⌋}$ and every message is a binary word of the same length.

The code is lossless when $d (e (x)) = x$ for every $x \in A^{n}$ ; equivalently, $e$ is injective and $d$ is its inverse on the image. For a code with block error, define its success set by $S = {x \in A^{n} : d (e (x)) = x}$ and its error probability by $P_{n} (S^{c})$ . The encoder restricted to $S$ is injective, so $∣ S ∣ \leq ∣ M ∣ \leq 2^{⌊ n R ⌋}$ .

Facts & Assumptions

Given: A finite nonempty alphabet $A$ , a positive integer $n$ , a probability law $P_{n}$ on $A^{n}$ , and a rate $R \geq 0$ .

[F1]

Finite-alphabet stationary source: the source alphabet is finite.

Proof

Given: The finite block domain, rate- $R$ message set, and encoder and decoder maps in the Definition.

1.1F1givenalgebra

If $d (e (x)) = x$ for every $x \in A^{n}$ , then $e$ is injective: $e (x) = e (y)$ implies $x = d (e (x)) = d (e (y)) = y$ . Conversely, if $e$ is injective, its inverse on the image is well-defined; a decoder is lossless exactly when it agrees with that inverse there, and its values off the image are irrelevant.

2.1givenstep 1.1algebra∎

If $x, y \in S$ and $e (x) = e (y)$ , then $x = d (e (x)) = d (e (y)) = y$ . Thus $e$ restricted to $S$ is injective, and the finite set $S$ has cardinality at most $∣ M ∣ \leq 2^{⌊ n R ⌋}$ . Its error probability is $P_{n} (S^{c})$ by definition.

Depends on

Finite-alphabet stationary source

Used by

Fixed-rate lossless coding for AMS ergodic sources Corollary
Fixed-rate source coding theorem for stationary ergodic sources Corollary
AEP criterion for fixed-rate lossless coding Lemma

Dependency tree · two levels

3 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

Robert M. Gray, Entropy and Information Theory, corrected edition (standard reference, not scraped)