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
- Janos Falucskai: A novel test for unique decipherability of codes, 2011, pp. 535-537
- Cassaigne and Nicolas: On the decidability of semigroup freeness, arXiv:0808.3112v4, definitions and examples in section 1.1
- Hesela: unique finite decoding versus streaming delay, exact constructed examples
- Janos Falucskai: On equivalence of two tests for codes, 2008, section 1, pp. 249-250
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.