Prefix code: Difference between revisions

Revision as of 00:29, 7 May 2006

Latest revision as of 12:06, 12 May 2025

(200 intermediate revisions by more than 100 users not shown)

Line 1:

{{Short description|Type of code system}}

== Introduction ==

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 (communication)|code word]] in the system that is a [[prefix (computer science)|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 code|variable-length codes]].

For example, a code with code {9, 55} has the prefix property; a code consisting of {9, 5, 59, 55} does not, because "5" is a prefix of "59" and also of "55". A prefix code is a [[uniquely decodable code]]: given a complete and accurate sequence, a receiver can identify each word without requiring a special marker between words. However, there are uniquely decodable codes that are not prefix codes; for instance, the reverse of a prefix code is still uniquely decodable (it is a suffix code), but it is not necessarily a prefix code.

A '''prefix code''' is a [[code]] which meets the "prefix property", which is that no code word is a [[prefix (computer science)|prefix]] of any other code word in the set. A code which uses code words {0,10,11} meets the prefix property; a code whose set is {0,1,10,11} does not because "1" is a prefix of both "10" and "11".

Prefix codes are also known as '''prefix-free codes''', '''prefix condition codes''' and '''instantaneous codes'''. Although [[Huffman coding]] is just one of many algorithms for deriving prefix codes, prefix codes are also widely referred to as "Huffman codes", even when the code was not produced by a Huffman algorithm. The term '''comma-free code''' is sometimes also applied as a synonym for prefix-free codes<ref>US [[Federal Standard 1037C]]</ref><ref>{{citation|title=ATIS Telecom Glossary 2007|url=http://www.atis.org/glossary/definition.aspx?id=6416|access-date=December 4, 2010|archive-date=July 8, 2010|archive-url=https://web.archive.org/web/20100708083829/http://www.atis.org/glossary/definition.aspx?id=6416|url-status=dead}}</ref> but in most mathematical books and articles (e.g.<ref>{{citation|last1=Berstel|first1=Jean|last2=Perrin|first2=Dominique|title=Theory of Codes|publisher=Academic Press|year=1985}}</ref><ref>{{citation|doi=10.4153/CJM-1958-023-9|last1=Golomb|first1=S. W.|author1-link=Solomon W. Golomb|last2=Gordon|first2=Basil|author2-link=Basil Gordon|last3=Welch|first3=L. R.|title=Comma-Free Codes|journal=Canadian Journal of Mathematics|volume=10|issue=2|pages=202–209|year=1958|s2cid=124092269 |url=https://books.google.com/books?id=oRgtS14oa-sC&pg=PA202|doi-access=free}}</ref>) a comma-free code is used to mean a [[self-synchronizing code]], a subclass of prefix codes.

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.)

TheUsing prefix propertycodes, permitsa codemessage words tocan be transmitted andas properlya [[framingsequence (telecommunication)|framed]]of withoutconcatenated thecode needwords, ofwithout any [[Out-of-band data|out-of-band]] markers or (assumingalternatively) thatspecial themarkers receiverbetween canwords correctlyto identify[[framing (telecommunication)|frame]] the startwords ofin the transmissionmessage. andThe thatrecipient therecan aredecode nothe uncorrectedmessage errorsunambiguously, inby therepeatedly symbolfinding stream.)and removing sequences that form valid code words. This is not generally possible with codes that lack the prefix property, such as ourfor example of {0,&nbsp;1,&nbsp;10,&nbsp;11}: a receiver which readreading 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"; so the string "10" could be interpreted either as a single codeword or as the concatenation of the words "1" then "0".

Examples of prefix codes are theThe variable-length [[Huffman coding|Huffman codes]], [[country calling codes]], the country and publisher parts of [[ISBN]]s and, the Secondary Synchronization Codes used in the [[UMTS]] [[W-CDMA]] 3G Wireless Standard., '''prefixand codes'''the are[[instruction alsoset]]s a(machine formlanguage) of [[entropymost encoding]]computer usedmicroarchitectures inare [[losslessprefix data compression]]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 any [[Variable-length_code#Uniquely_decodable_codes|uniquely decodable]] code there is a prefix code that has the same code word lengths.<ref name=LTU2015>Le Boudec, Jean-Yves, Patrick Thiran, and Rüdiger Urbanke. Introduction aux sciences de l'information: entropie, compression, chiffrement et correction d'erreurs. PPUR Presses polytechniques, 2015.</ref> [[Kraft's inequality]] characterizes the sets of code word lengths that are possible in a [[Variable-length_code#Uniquely_decodable_codes|uniquely decodable]] code.<ref name=BRS75>Berstel et al (2010) p.75</ref>

== Primer to encoding ==

==Techniques==

A key problem with encoding is knowing where one symbols start and ends. In this section, we look at more and more sophisticated ways of doing this, which win prefix coding.

If every word in the code has the same length, the code is called a '''fixed-length code''', or a '''block code''' (though the term [[block code]] is also used for fixed-size [[error-correcting code]]s in [[channel coding]]). For example, [[ISO 8859-15]] letters are always 8 bits long. [[UTF-32/UCS-4]] letters are always 32 bits long. [[Asynchronous Transfer Mode|ATM cells]] are always 424 bits (53 bytes) long. A fixed-length code of fixed length ''k'' bits can encode up to <math>2^{k}</math> 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.

=== Using a "comma" ===

[[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'' and ''k''+1, where ''k'' is chosen so that ''2^k < n ≤ 2^k+1''.

The first and most obvious way to denote where one symbol starts and another ends is to use a special "comma" symbol. This is somewhat analogous to the period at the end of the sentence; it marks where one sentence ends and another begins. So the word "dada" could be transmitted

00101110,10000110,00101110,10000110,

where the "," represents the symbol which has to be different from "1" or "0".

[[Huffman coding]] is a more sophisticated technique for constructing variable-length prefix codes. The Huffman coding algorithm takes as input the frequencies that the code words should have, and constructs a prefix code that minimizes the weighted average of the code word lengths. (This is closely related to minimizing the entropy.) This is a form of [[lossless data compression]] based on [[entropy encoding]].

However, modern communication systems send everything as sequences of "1" or "0" -- adding a "third symbol" would be expensive.

In general, we call this third symbol a "[[comma]]").

Some codes mark the end of a code word with a special "comma" symbol (also called a [[Sentinel value]]), different from normal data.<ref>{{cite web |url=http://www.imperial.ac.uk/research/hep/group/theses/JJones.pdf |title=Development of Trigger and Control Systems for CMS |first1=J. |last1=A. Jones |page=70 |publisher=High Energy Physics, Blackett Laboratory, Imperial College, London |url-status=dead |archive-url= https://web.archive.org/web/20110613183447/http://www.imperial.ac.uk/research/hep/group/theses/JJones.pdf |archive-date= Jun 13, 2011 }}</ref> This is somewhat analogous to the spaces between words in a sentence; they mark where one word ends and another begins. If every code word ends in a comma, and the comma does not appear elsewhere in a code word, the code is automatically prefix-free. However, reserving an entire symbol only for use as a comma can be inefficient, especially for languages with a small number of symbols. [[Morse code]] is an everyday example of a variable-length code with a comma. The long pauses between letters, and the even longer pauses between words, help people recognize where one letter (or word) ends, and the next begins. Similarly, [[Fibonacci coding]] uses a "11" to mark the end of every code word.

=== Fixed-length comma-free codes ===

[[Self-synchronizing code]]s are prefix codes that allow [[frame synchronization]].

Fortunately, the "third symbol" turns out to be unnecessary. It's possible for a machine to receive the '''comma-free''' sequence

00101110100001100010111010000110

and correctly decode the word "dada".

==Related concepts==

The simplest method is to make every letter the same length. This is called a "[[fixed-length code]]".

A '''suffix code''' is a set of words none of which is a suffix of any other; equivalently, a set of words which are the reverse of a prefix code. As with a prefix code, the representation of a string as a concatenation of such words is unique. A '''bifix code''' is a set of words which is both a prefix and a suffix code.<ref name=BPR58>Berstel et al (2010) p.58</ref>

For example, [[ISO 8859-15]] letters are always 8 bits long. [UTF-32/UCS-4]] letters are always 32 bits long.

An '''optimal prefix code''' is a prefix code with minimal average length. That is, assume an alphabet of {{mvar|n}} symbols with probabilities <math>p(A_i)</math> for a prefix code {{mvar|C}}. If {{mvar|C'}} is another prefix code and <math>\lambda'_i</math> are the lengths of the codewords of {{mvar|C'}}, then <math>\sum_{i=1}^n { \lambda_i p(A_i) } \leq \sum_{i=1}^n { \lambda'_i p(A_i) } \!</math>.<ref>[http://www.cim.mcgill.ca/~langer/423/lecture2.pdf McGill COMP 423 Lecture notes]</ref>

[[Asynchronous Transfer Mode|ATM packets]] are always 424 bits long.

=== Variable-length codes with a comma ===

The problem with using encoding of the same size for each characters is that it's not very efficient. Letters

that occur frequently, like "e", have the same encoding length as letters you almost never see, like "z".

It is much more efficient if you use different length code words for different letters. That way, you can assign

the letter "e" a small code word like "01" and "z" a code like "01011010101".

One way to do this is to assign a code to each letter according to their probability of accurence in the message.

As an example, if we used a custom code:

0 a

1 d

01 space

then the phrase "add a dad" could be compressed to

0,1,1,01,0,01,1,0,1

Normally, this would take 72 bits to store because each character of the sentence encoded in ASCII takes eigh bits and there are nine words. With our code it takes the equivelent of 31 bits to store. This is because we have 19 characters and each character can take three possible values. We have achieved some shortening of the message due to the choice of encoding!

[[Morse code]] is an everyday example of a variable-length code with a comma. The long spaces between letters, and even longer spaces between words, help people recognize where one letter/word ends, and the next begins.

The problem with codes that use commas is that if we want to achieve further compression by removing the comma then the

message becomes ambiguous. Consider:

01101001101

Does a "0" followed by a "1" represent a space character, or 2 different letters ?

The ambiguity is caused because one complete code (in this case "0" for "a") is just the first part -- the prefix -- of another code which in this case, "01" for space. This brings us nicely to the next section.

=== Variable-length comma-free codes ===

It is possible to specially design a variable-length code such that there is never any ambiguity.

Such a specially designed code is called a "variable-length code" or a "prefix-free code".

The question quickly arises whether it is possible to design an optimal variable length code. I.e A code compresses a transmission into the fewest number of bits?

If one knows ahead of time all the letters that could possibly be used, and has a good estimate of the [[letter frequencies]] then it is indeed possible to construct such a code. They are called [[Huffman codes|Huffman code]]. It has been shown that all other codes, both variable-length and fixed-length, use at least as many bits than a Huffman code.

Usually the Huffman process generates a variable-length code but this isn't always the case. For example, when all the letters have the same frequency, such as in previously compressed or encrypted data, and the number of codewords is a power of 2, the Huffman process will generate a fixed-length code. Even in this case, the code will still be optimal.

== Non-codes ==

Some data compression algorithms can compress files even smaller than [[Huffman coding|Huffman compression]]. Generally this is because they don't use a code at all.

* They may represent "a" by one pattern of bits in one place in the compressed file, then use that same pattern of bits to represent a completely different letter later on, as in [[Adaptive Huffman coding|adaptive Huffman]] compression.

* They may use a pattern of bits to represent several letters, as in [[LZW]] compression -- changing any one of those bits may completely change that block of letters.

* Or they may avoid mapping particular bits to particular letters (the definition of a code) in other creative ways, as in [[range encoding]].

=== Existence of prefix codes / Kraft's inequality ===

If we have a fixed number of symbols <math>|X|</math>(the alphabet size), then for any given list of codeword lengths <math>(l_i)_{i=1...n}</math> a prefix code exists if and only if <math>\sum_{i=1}^{n}|X|^{-l_i}\le 1</math>. This is known as [[Kraft's inequality|''Kraft's inequality'']].

== error handling ==

Many communication systems are not completely error-free.

There are occasionally a single bit errors (toggling a bit, losing a bit, or gaining a bit).

With [[fixed-length code]]s, an error toggling a bit causes just that one code to be received in error,

but all other codes are received OK. However, with [[variable-length code]]s, losing or gaining a bit (a [[framing error]]) turns the rest of the message into gibberish.

(This is why most communication protocols periodically re-synchronize.

ASCII over RS-232 uses 20% of its bandwidth re-synchronizing after each character).

See

[[Synchronization]]

[[Link protocol]]

With [[Fibonacci code]]s and [[unary coding|unary code]]s, all single-bit errors cause one or two erroneous codes,

but all other codes are received OK. (These codes are "self-synchronizing").

With most other variable-length codes, any kind of single-bit error turns the rest of the message into gibberish.

== Prefix codes in use today ==

==Prefix codes in use today==

Examples of prefix codes include:

* variable-length [[Huffman coding|Huffman codes]]

* [[country calling codes]]

* [[Chen–Ho encoding]]

* the country and publisher parts of [[ISBN]]s

* the Secondary Synchronization Codes used in the [[UMTS]] [[W-CDMA]] 3G Wireless Standard

* [[VCR Plus|VCR Plus+ codes]]

* [[Unicode Transformation Format]], in particular the [[UTF-8]] system for encoding [[Unicode]] characters, which is both a prefix-free code and a [[self-synchronizing code]]<ref>{{cite web

* [[country calling codes]]

| url = http://www.cl.cam.ac.uk/~mgk25/ucs/utf-8-history.txt

* [[Universal code (data compression)|Universal code]]s such as

| title = UTF-8 history

** [[Elias delta coding]]

| first = Rob

** [[Elias gamma coding]]

| last = Pike

** [[Elias omega coding]]

| date = 2003-04-03

** [[Fibonacci coding]]

}}</ref>

** [[Golomb coding]]

** [[Unaryvariable-length codingquantity]]

* [[Shannon-Fano coding|Shannon-Fano codes]]

* [[Huffman coding|Huffman codes]]

== See also ==

===Techniques===

* [[binary symmetric channel]]

Commonly used techniques for constructing prefix codes include [[Huffman coding|Huffman codes]] and the earlier [[Shannon–Fano coding|Shannon–Fano codes]], and [[universal code (data compression)|universal code]]s such as:

* [[communications protocol]]

* [[characterElias encodingdelta coding]]

* [[Elias gamma coding]]

* [[Elias omega coding]]

* [[Fibonacci coding]]

* [[Levenshtein coding]]

* [[Unary coding]]

* [[Golomb Rice code]]

* [[Straddling checkerboard]] (simple cryptography technique which produces prefix codes)

* binary coding<ref>{{citation|doi=10.25209/2079-3316-2018-9-4-239-252|last1=Shevchuk|first1=Y. V.|author1-link=Yury V. Shevchuk|title=Vbinary: variable length integer coding revisited|journal=Program Systems: Theory and Applications|volume=9|issue=4|pages=239–252|year=2018|url=http://psta.psiras.ru//read/psta2018_4_239-252.pdf|doi-access=free}}</ref>

== References Notes==

{{Reflist}}

==References==

* P. Elias, Universal codeword sets and representations of integers, IEEE Trans. Inform. Theory 21 (2) (1975) 194-203.

* {{cite book | last1=Berstel | first1=Jean | last2=Perrin | first2=Dominique | last3=Reutenauer | first3=Christophe | title=Codes and automata | series=Encyclopedia of Mathematics and its Applications | volume=129 | ___location=Cambridge | publisher=[[Cambridge University Press]] | year=2010 | url=http://www-igm.univ-mlv.fr/~berstel/LivreCodes/Codes.html | isbn=978-0-521-88831-8 | zbl=1187.94001 }}

* {{cite journal | last=Elias | first=Peter | author-link=Peter Elias | title=Universal codeword sets and representations of the integers | journal=IEEE Trans. Inf. Theory | volume=21 | number=2 | year=1975 | pages=194–203 | issn=0018-9448 | zbl=0298.94011 | doi=10.1109/tit.1975.1055349}}

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

* [https://web.archive.org/web/20070220234037/http://www.huffmancoding.com/david/scientific.html Profile: David A. Huffman], [[Scientific American]], Sept. 1991, pp.&nbsp;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. {{ISBN|0-262-03293-7}}. Section 16.3, pp.&nbsp;385–392.

* {{FS1037C}}

==External links==

* [http://plus.maths.org/issue10/features/infotheory/index.html Codes, trees and the prefix property] by Kona Macphee

{{Compression methods}}

[[Category:Coding theory]]

[[Category:Prefixes|code]]

[[Category:Data compression]]

[[Category:Lossless compression algorithms]] <!-- do I really need both categories? -->

[[cs:Prefixov%C3%BD k%C3%B3d]]

[[pl:Kod prefiksowy]]