Prefix code: Difference between revisions

Revision as of 19:51, 4 November 2005

Revision as of 20:34, 4 November 2005

Line 1:

{{cleanup-date|November 2005}}

A '''prefix code''', alsois knowna as[[code]] awhich meets the '''"prefix-free code'''property", '''comma-freewhich code'''is orthat '''instantaneousno code''', word is a [[codeprefix]] constructedof soany that dividing theother code word into two pieces cannot result in the firstset. being aA code word.which Foruses example,code the setwords {0100,011,010,10111} ismeets not athe prefix codeproperty; becausea thecode entrywhose '0'set is the prefix of the entries 010 and 011. Hence, when receiving in series, 0101101, how do you know if it means {0,1011,101 or 010,110,010,11} anddoes sonot on.because However, {01,101,110,0010}"1" is a prefix code,of becauseboth "10" noand entry"11". is the start of any other entry.

Prefix codes are also known as '''prefix-free codes''', '''comma-free codes''' or '''instantaneous codes'''; even though [[Huffman coding]] is only one algorithm for deriving prefix codes, prefix codes are also widely referred to as "Huffman codes" (even, confusingly, when the codes were not produced by a Huffman algorithm.)

This property permits the proper [[framing (telecommunication)|framing]] of transmitted code words when (a) external [[synchronization]] is provided to identify the start of the first code word in a [[sequence]] of code words and (b) no uncorrected errors occur in the symbol stream.

The prefix property permits code words to be transmitted and properly [[framing (telecommunication)|framed]] without the need of [[out-of-band]] markers (assuming that the receiver can correctly identify the start of the transmission and that there are no uncorrected errors in the symbol stream.) This is not possible with codes that lack the prefix property, such as our example of {0,1,10,11}: a receiver which read a "1" at the start of a code word would not know whether that was the complete code word "1" or merely the prefix of the code word "10" or "11".

Examples of prefix codes are the variable-length [[Huffman coding|Huffman codes]], [[country calling codes]], [[ISBN]]s and the Secondary Synchronization Codes used in the [[UMTS]] [[W-CDMA]] 3G Wireless Standard.