Prefix-free code
A prefix-free code assigns distinct codewords so that none is a prefix of another, allowing immediate symbol decoding from a known boundary.
Decoding: With the same codebook and a known starting boundary, a decoder can recognize each symbol without reading the next symbol. Huffman coding constructs prefix-free codes. Prefix freedom alone does not guarantee resynchronization after a lost bit. [1] [2]
Lengths: Binary codeword lengths l must satisfy sum(2^-l) <= 1 for unique decoding. This condition guarantees that a prefix-free assignment with those lengths exists, not that any assignment works. A=0, B=01, C=10 has sum 1, yet 010 represents either AC or BA. [3] [4]
Scope: Prefix freedom is sufficient but not necessary for unique decoding. The codewords 1, 10 and 100 are uniquely decodable without being prefix-free. This broader property does not promise immediate left-to-right symbol decisions. [3]
Recovery: Parsing valid codewords does not verify the intended message or its completeness. Canonical reconstruction still needs symbol order and the format's assignment rules; code lengths alone do not supply those conventions. Prefix-free parsing for BWT construction is a different technique. [2] [4]
Relations
Citations
- David A. Huffman (1952): A Method for the Construction of Minimum-Redundancy Codes, pp. 1098-1099
- RFC 1951: prefix codes and canonical Huffman assignment, sections 3.2.1-3.2.2
- Brockway McMillan (1956): Two Inequalities Implied by Unique Decipherability, IRE Transactions on Information Theory 2(4), 115-116
- Hesela: equal codeword lengths can hide an ambiguous assignment
Sources & caveats
- McMillan's Discussion was checked in indexed original-paper text; direct retrieval of the university PDF mirror timed out. The theorem and its converse are distinguished from the constructed example.
- The codebook examples are exact teaching arithmetic, not a native codec experiment, error-rate estimate or general unique-decodability tester.