prefix-free-code · shipping · also Prefix code, Instantaneous code

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

related
Uniquely decodable code, Huffman coding, Rice coding, Prefix-free parsing

Citations

  1. David A. Huffman (1952): A Method for the Construction of Minimum-Redundancy Codes, pp. 1098-1099 (accessed 2026-11-18)
  2. RFC 1951: prefix codes and canonical Huffman assignment, sections 3.2.1-3.2.2 (accessed 2026-11-18)
  3. Brockway McMillan (1956): Two Inequalities Implied by Unique Decipherability, IRE Transactions on Information Theory 2(4), 115-116 (accessed 2026-11-18)
  4. Hesela: equal codeword lengths can hide an ambiguous assignment (accessed 2026-11-18)
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.

JSON: /data/terms/prefix-free-code.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Prefix-free code. Hesela. 2026-11-18. https://hesela.dev/terms/prefix-free-code/