Prefix code

A prefix code is a type of code system distinguished by its possession of the prefix property, which requires that there is no whole code word in the system that is a prefix (initial segment) of any other code word in the system. It is trivially true for fixed-length codes, so only a point of consideration for variable-length codes.

For example, a code with code ab and also of 1 at the start of a code word would not know whether that was the complete code word 11; so the string 0.

The variable-length Huffman codes, telephone country codes, the country and publisher parts of ISBNs, the Secondary Synchronization Codes used in the UMTS W-CDMA 3G Wireless Standard, and the instruction sets (machine language) of most computer microarchitectures are prefix codes.

Prefix codes are not error-correcting codes. In practice, a message might first be compressed with a prefix code, and then encoded again with channel coding (including error correction) before transmission.

For every uniquely decodable code there is a prefix code that has the same code word lengths. Kraft's inequality characterizes the sets of code word lengths that are possible in a uniquely decodable code.

2k source symbols.

A fixed-length code is necessarily a prefix code. It is possible to turn any code into a fixed-length code by padding fixed symbols to the shorter prefixes in order to meet the length of the longest prefixes. Alternately, such padding codes may be employed to introduce redundancy that allows autocorrection and/or synchronisation. However, fixed length encodings are inefficient in situations where some words are much more likely to be transmitted than others.

Truncated binary encoding is a straightforward generalization of fixed-length codes to deal with cases where the number of symbols n is not a power of two. Source symbols are assigned codewords of length k is chosen so that p(Ai) for a prefix code Berstel, Jean; Perrin, Dominique (1985), Theory of Codes, Academic Press

↑ Pike, Rob (2003-04-03). "UTF-8 history".

↑ Elias, Peter (1975). "Universal codeword sets and representations of the integers". IEEE Trans. Inf. Theory. 21 (2): 194–203. doi:10.1109/tit.1975.1055349. ISSN 0018-9448. Zbl 0298.94011.

D.A. Huffman, "A method for the construction of minimum-redundancy codes", Proceedings of the I.R.E., Sept. 1952, pp. 1098–1102 (Huffman's original article)

Profile: David A. Huffman, Scientific American, Sept. 1991, pp. 54–58 (Background story)

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001.