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.

✓ 3 results · all verified · 0 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 3 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Prefix Codes and Finite Lossless Coding — Examples

1 · Prerequisites

2 · Summary

These examples work an exact three-symbol Huffman tree, a uniquely decodable code that is not prefix-free, and one rational arithmetic-coded block. The code-tree and interval diagrams explain their conventions; the verification arguments use the displayed words, integer updates, and rational inequalities directly.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passOpen item page →

A uniquely decodable binary code that is not prefix-free

Facts & Assumptions

Given: The binary code on the two-symbol alphabet ${1, 2}$ defined by $C (1) = 0$ and $C (2) = 01$ .

[F1]

Finite binary source codes, extension, and expected length: The extension $C^{*}$ concatenates the codewords, and the code is uniquely decodable exactly when this extension is injective on all finite source words.

[F2]

Binary prefix codes and their code trees: A prefix code has no codeword that is a proper prefix of a different codeword.

[F3]

McMillan inequality for finite binary uniquely decodable codes: Every finite binary uniquely decodable code satisfies $\sum_{i} 2^{- ℓ_{i}} \leq 1$ .

Example

The word $0$ is itself assigned to symbol 1 and is also the first bit of the word $01$ assigned to symbol 2. Thus the code fails the prefix condition. The next verification shows that the two codewords still admit a unique parse.

Verification

1.1F2given

The codeword $C (1) = 0$ is a proper prefix of $C (2) = 01$ , so [F2] shows this code is not prefix-free.

1.2F1F2giveninduction

Every codeword begins with $0$ . If an encoded word begins with $01$ , its first codeword must be $01$ , since choosing $0$ would leave an unread suffix beginning with $1$ , and no codeword begins with $1$ . If the unread word begins with $00$ , or consists only of $0$ , its first codeword must be $0$ . Repeating this forced rule on the remaining suffix consumes one or two bits at each step and ends after finitely many steps; the empty word is produced only by the empty source word. Hence every encoded word has a unique source parse, and [F1] gives unique decodability.

2.1F3step 1.2algebra∎

The lengths are $1$ and $2$ , so the Kraft sum is $2^{- 1} + 2^{- 2} = 3 / 4 \leq 1$ , consistent with [F3]; this calculation is only a necessary-bound check, while unique decodability was proved in step 1.2.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passOpen item page →

Exact rational interval coding of the block AB

Facts & Assumptions

Given: Alphabet order $A, B, C$ , rational frequencies $(q_{A}, q_{B}, q_{C}) = (3, 2, 1)$ with $Q = 6$ , maximum and fixed frame length $N = n = 2$ , and input block $A B$ .

[F1]

Exact finite-register arithmetic coding for rational block sources: At symbol $x_{t}$ , the update is $L \leftarrow L + W c_{x_{t}} Q^{n - t}$ and $W \leftarrow W q_{x_{t}}$ ; the output uses the largest $u$ with $2^{u} W \leq Q^{n}$ , then $s = u + 2$ and $k = ⌊ 2^{s} (2 L + W) / (2 Q^{n}) ⌋$ .

[F2]

The rational finite-register arithmetic code is prefix-free and lossless: The finite decoder returns exactly the encoded block.

[F3]

Finite discrete sources and product blocks: The block law is the product of the one-symbol probabilities.

Example

With $p = (1 / 2, 1 / 3, 1 / 6)$ and a length-two frame, the interval for $A B$ should be $[1 / 4, 5 / 12)$ . The emitted codeword is $0101$ , whose dyadic cell is strictly inside that interval.

The diagram uses horizontal position for the real coordinate on $[0, 1)$ . The upper bar is the source interval for $A B$ ; the lower bar is the dyadic cell represented by $0101$ . It illustrates the exact rational comparisons below but is not used as proof.

Verification

1.1F1F3givenalgebra

For the first symbol $A$ , $c_{A} = 0$ , so the update from $(L, W) = (0, 1)$ gives $(0, 3)$ . For the second symbol $B$ , $c_{B} = q_{A} = 3$ and $Q^{n - 2} = 1$ , so $(L, W) = (0 + 3 \cdot 3, 3 \cdot 2) = (9, 6)$ . With $D = Q^{n} = 36$ , the source interval is $[9 / 36, 15 / 36) = [1 / 4, 5 / 12)$ ; its width $6 / 36 = 1 / 6$ equals $p_{A} p_{B}$ by [F3].

1.2F1givenalgebra

Since $2^{2} \cdot 6 = 24 \leq 36 < 48 = 2^{3} \cdot 6$ , the largest admissible $u$ is $2$ and the payload length is $s = 4$ . The midpoint is $(2 \cdot 9 + 6) / (2 \cdot 36) = 1 / 3$ , hence $k = ⌊ 16 / 3 ⌋ = 5$ and its four-bit representation is $0101$ . Also $B = 6$ because $2^{5} < 36 \leq 2^{6}$ , so the emitted four-bit word obeys the configured $B + 2$ limit.

2.1F2step 1.1step 1.2algebra∎

The dyadic cell of $0101$ is $[5 / 16, 6 / 16) = [5 / 16, 3 / 8)$ . Exact comparisons give $1 / 4 = 4 / 16 < 5 / 16$ and $3 / 8 = 9 / 24 < 10 / 24 = 5 / 12$ , so this cell is inside $[1 / 4, 5 / 12)$ . By [F2], the decoder returns $A B$ uniquely.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passOpen item page →

Huffman tree for a dyadic three-symbol source

Facts & Assumptions

Given: The source $p = (1 / 2, 1 / 4, 1 / 4)$ on symbols $1, 2, 3$ and the deterministic Huffman procedure.

[F1]

Deterministic binary Huffman coding: Equal weights are ordered by increasing serial number; the first selected node is the left child and the second is the right child.

[F2]

Finite binary source codes, extension, and expected length: $L_{p} (C) = \sum_{i} p_{i} ℓ_{i}$ .

[F3]

Base-two entropy of a finite source: $H_{2} (p) = - \sum_{i} p_{i} \log_{2} p_{i}$ .

[F4]

Huffman expected length is within one bit of entropy: If $m \geq 2$ , then $H_{2} (p) \leq L_{p} (C_{H}) < H_{2} (p) + 1$ .

[F5]

The deterministic Huffman code is prefix-optimal: The deterministic Huffman procedure returns a binary prefix code minimizing $L_{p} (C)$ among all binary prefix codes on the same alphabet.

[F6]

Information units and logarithm-base convention: $\log_{2} x = \ln x / \ln 2$ .

[F7]

Change of base and inversion of the positive-base real exponential: $\log_{2} (2^{u}) = u$ for every real $u$ .

Example

The weights of symbols 2 and 3 are tied for least, so the first merge combines them. The final tie is between symbol 1 and the merged node; the serial rule puts symbol 1 on the left. The code tree uses edge labels 0 on the left and 1 on the right; each leaf label is a source symbol, and reading its root path gives its codeword.

The diagram records the tree structure and edge convention; the verification below computes the codewords and lengths directly.

Verification

1.1F1givenconstruct

The first merge combines 2 and 3 into a node of weight $1 / 2$ . The active nodes are then $(1, 1 / 2)$ and the merged node of weight $1 / 2$ ; the serial tie-break puts 1 on the left and the merged node on the right. Thus $C_{H} (1) = 0$ , $C_{H} (2) = 10$ , and $C_{H} (3) = 11$ .

2.1F2F3F4F5F6F7step 1.1algebra∎

These lengths are $(1, 2, 2)$ , so [F2] gives $L_{p} (C_{H}) = \frac{1}{2} + \frac{1}{2} + \frac{1}{2} = \frac{3}{2}$ . By [F6] and [F7], $\log_{2} (1 / 2) = - 1$ and $\log_{2} (1 / 4) = - 2$ , so [F3] gives $H_{2} (p) = \frac{1}{2} + \frac{1}{2} + \frac{1}{2} = \frac{3}{2}$ as well, which satisfies the two-sided bound [F4]; [F5] confirms the optimal prefix-code conclusion.

Prefix Codes and Finite Lossless Coding — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

A uniquely decodable binary code that is not prefix-free

Facts & Assumptions

Example

Verification

Exact rational interval coding of the block AB

Facts & Assumptions

Example

Verification

Huffman tree for a dyadic three-symbol source

Facts & Assumptions

Example

Verification

Sources