§5, pp. 7–8 (composition decoder) — substituting the tree of a finite maximal prefix code Z for the letters of a decoder gives a Huffman decoder for (Y ∘ Z)* with Θ(n_Y n_Z) states
ProvedSyncPrefix.Huffman.composition_decoderLet be a complete automaton with states over an alphabet , let be a finite maximal prefix code over a finite nonempty alphabet , with tree of vertices, and let be a bijection. Let be the decoder obtained by hanging a copy of from every state of : the inner vertices are new states, and the leaf of the copy at is merged with . Then:
- the number of states of satisfies
so , which is for a fixed alphabet (for a binary , ); 2. is strongly connected if is, and is a Huffman decoder if is; 3. for every state of , a word over maps to itself in if and only if for a word over that maps to itself in .
By item 3, if recognizes with as initial and final state, then recognizes . Item 3 is the decoder over the alphabet of used in the proof of Corollary 8.
Differences from the source:
- generalization: "a Huffman decoder with Θ(n_Y n_Z) states" → the exact count |Σ_Z|·N + n_Y = n_Y n_Z; reason: it gives Θ(n_Y n_Z) for every fixed alphabet Σ_Z, in particular the binary one of the application.
- generalization: H_Y a Huffman decoder for a maximal prefix code Y → H_Y any complete automaton, with strong connectivity and the Huffman property each transferred, and item 3 for every state r; reason: specializes to the source's H_Y.
- reading: "a Huffman decoder recognizing the star of X = Y ∘ Z" → item 3 (returns to r in H_X are the images of returns to r in H_Y); reason: H_Y recognizes Y* with r as initial and final state.
- reading: Huffman decoder → strongly connected, with a state whose set of first-return words is finite; reason: the paper's setting for first-return codes (p. 3); the source's H_Y, a decoder recognizing Y*, is of this kind.
- encoding: the alphabet Σ_Z → a finite nonempty type; reason: alphabets are finite and nonempty, and over the empty alphabet ∅ is a degenerate maximal prefix code.
import Mathlib import Definitions.Def_SyncPrefix_Huffman_Constructions
namespace SyncPrefix.Huffman
/-- The composition decoder (pp. 7–8). Let `δY` be a complete automaton over `β` and `Z` a finite
maximal prefix code over a finite nonempty alphabet `α`, with a bijection `e : β → Z`. The decoder obtained
by hanging a copy of the tree `T_Z` from every state:
(a) has `n_Y (n_Z − 1) / |α|` states, where `n_Y` is the number of states of `δY` and `n_Z` the
number of vertices of `T_Z`;
(b) is strongly connected if `δY` is, and is a Huffman decoder if `δY` is;
(c) for every state `r`, the words returning `r` to itself in the decoder are exactly the
substitutions `β(y)` of the words `y` returning `r` to itself in `δY` (so it recognizes the star
of `X = Y ∘ Z` when `δY` recognizes `Y∗`). -/
theorem composition_decoder {σ α β : Type} [Fintype σ] [DecidableEq σ] [Fintype α] [Nonempty α]
[DecidableEq α] (δY : σ → β → σ) (Z : Finset (List α))
(hZ : IsMaximalPrefixCode (lang Z)) (e : β ≃ {z // z ∈ Z}) :
Fintype.card α * Fintype.card (DecoderState σ Z) + Fintype.card σ =
Fintype.card σ * (allPrefixes Z).card ∧
(StronglyConnected δY → StronglyConnected (composeDecoder δY Z e)) ∧
(IsHuffmanDecoder δY → IsHuffmanDecoder (composeDecoder δY Z e)) ∧
∀ (r : σ) (w : List α), run (composeDecoder δY Z e) (rootState Z r) w = rootState Z r ↔
∃ y : List β, run δY r y = r ∧ w = subst e y := by sorry
end SyncPrefix.Huffman
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.