Prefix code

Variable-length coding assigns bit strings of different lengths. If one is another’s beginning, its end may not be recognizable immediately. The prefix-free condition eliminates that uncertainty.

The codewords 0, 10 and 11 allow immediate symbol recognition: zero ends one codeword, while one requires a second bit. Using both 0 and 01 violates the condition. Failure to be prefix-free does not itself prove that a code lacks unique decodability by other means.

References: [1]

A binary prefix code can be drawn as a tree with zero and one edges and complete symbols at leaves. A symbol at another symbol’s ancestor would prefix that descendant, violating the condition.

Decoding follows bits from the root, emits a symbol at a leaf, and returns to the root. Huffman builds such a tree from frequencies, but prefix-freeness alone neither requires Huffman construction nor establishes optimal average length.

References: [2] [1]

The decoder must know the same codebook, whether predefined or supplied through tree or equivalent metadata. A bit string alone does not identify the symbols attached to unknown leaves.

Prefix-freeness separates adjacent codewords but does not frame the entire message. A format can transmit symbol count or an end marker and specify padding. The property also does not automatically correct damaged bits or provide integrity checking.

References: [2] [1]