uniquely-decodable-code · shipping · also Uniquely decipherable code

Uniquely decodable code

A uniquely decodable code maps distinct finite sequences of source symbols to distinct concatenations of codewords.

Scope: The codebook and complete finite bitstring must be known. Prefix-free codes satisfy this property, but some nonprefix codes do too; the broader property does not promise immediate left-to-right decisions. [1] [2]

Delay: The nonprefix codewords 0, 01 and 11 are uniquely decodable. Yet 0 followed by repeated 11 and 01 followed by repeated 11 share arbitrarily long prefixes. A uniform streaming decision bound does not follow from finite-message uniqueness. [3]

Testing: Sardinas-Patterson checks possible unmatched suffixes until ambiguity is found or their finite reachability search closes. Enumerating only short messages is not a general proof: 0, 0010 and 1001 first collide at ten bits in the supplied example. [4] [3]

Recovery: Unique parsing does not establish the intended data, detect every changed bit, recover missing framing or prove object completeness. [3]

Relations

related
Prefix-free code

Citations

  1. Janos Falucskai: A novel test for unique decipherability of codes, 2011, pp. 535-537 (accessed 2026-11-18)
  2. Cassaigne and Nicolas: On the decidability of semigroup freeness, arXiv:0808.3112v4, definitions and examples in section 1.1 (accessed 2026-11-18)
  3. Hesela: unique finite decoding versus streaming delay, exact constructed examples (accessed 2026-11-18)
  4. Janos Falucskai: On equivalence of two tests for codes, 2008, section 1, pp. 249-250 (accessed 2026-11-18)
Sources & caveats
  • Primary-source synthesis with independent source review. Constructed examples are exact mathematical checks, not a native codec experiment, new theorem or measured error rate.
  • The bounded checker throws on invalid input or resource exhaustion; it never treats exhaustion as a uniqueness proof.

JSON: /data/terms/uniquely-decodable-code.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Uniquely decodable code. Hesela. 2026-11-18. https://hesela.dev/terms/uniquely-decodable-code/