digplanet beta 1: Athena
Share digplanet:

Agriculture

Applied sciences

Arts

Belief

Chronology

Culture

Education

Environment

Geography

Health

History

Humanities

Language

Law

Life

Mathematics

Nature

People

Politics

Science

Society

Technology

A prefix code is a type of code system (typically a variable-length code) distinguished by its possession of the "prefix property"; which states that there is no valid code word in the system that is a prefix (start) of any other valid code word in the set. For example, a code with code words {9, 59, 55} has the prefix property; a code consisting of {9, 5, 59, 55} does not, because "5" is a prefix of both "59" and "55". A prefix code is an example of a uniquely decodable code: a receiver can identify each word without requiring a special marker between words.

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[1][2] but in most mathematical books and articles (e. g.[3][4]) it is used to mean self-synchronizing codes, a subclass of prefix codes.

Using prefix codes, a message can be transmitted as a sequence of concatenated code words, without any out-of-band markers to frame the words in the message. The recipient can decode the message unambiguously, by repeatedly finding and removing prefixes that form valid code words. This is not always possible with codes that lack the prefix property, for example {0, 1, 10, 11}: a receiver reading 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"; and the string "10" could be interpreted either as a single codeword or as the concatenation of the words "1" then "0".

The variable-length Huffman codes, country calling 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.

Kraft's inequality characterizes the sets of code word lengths that are possible in a uniquely decodable code.[5]

Techniques

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 codes in channel coding). For example, ISO 8859-15 letters are always 8 bits long. UTF-32/UCS-4 letters are always 32 bits long. ATM packets are always 424 bits long. A block code of fixed length k bits can encode up to $2^{k}$ source symbols.

Prefixes cannot exist in a fixed-length code without padding fixed codes to the shorter prefixes in order to meet the length of the longest prefixes (however such padding codes may be selected 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 (in which case some or all of the redundancy may be eliminated for data compression).

Truncated binary encoding is a straightforward generalization of block 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 $2^{k} < n < 2^{k+1}$.

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 a form of lossless data compression based on entropy encoding.

Some codes mark the end of a code word with a special "comma" symbol, different from normal data.[6] 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 prefix-free. However, modern communication systems send everything as sequences of "1" and "0" – adding a third symbol would be expensive, and using it only at the ends of words would be inefficient. 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.

Self-synchronizing codes are prefix codes that allow frame synchronization.

Related concepts

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 concantenation of such words is unique. A bifix code is a set of words which is both a prefix and a suffix code.[7]

Prefix codes in use today

Examples of prefix codes include:

Techniques

Commonly used techniques for constructing prefix codes include Huffman codes and the earlier Shannon-Fano codes, and universal codes such as:

Notes

1. ^
2. ^ ATIS Telecom Glossary 2007, retrieved December 4, 2010
3. ^ Berstel, Jean; Perrin, Dominique (1985), Theory of Codes, Academic Press
4. ^ Golomb, S. W.; Gordon, Basil; Welch, L. R. (1958), "Comma-Free Codes", Canadian Journal of Mathematics 10 (2): 202–209, doi:10.4153/CJM-1958-023-9
5. ^ Berstel et al (2010) p.75
6. ^ "Development of Trigger and Control Systems for CMS" by J. A. Jones: "Synchronisation" p. 70
7. ^ Berstel et al (2010) p.58
8. ^ Pike, Rob (2003-04-03). "UTF-8 history".

References

 12884 videos foundNext >
 (IC 2.5) Prefix codesDefinition of a prefix code (a.k.a. prefix-free code a.k.a. instantaneous code) for lossless compression. A playlist of these videos is available at: http://... (IC 4.13) Not every optimal prefix code is HuffmanEvery Huffman code is an optimal prefix code, but the converse is not true. This is illustrated with an example. A playlist of these videos is available at: ... (IC 2.6) Prefix codes - remarks and what's nextDefinition of a prefix code (a.k.a. prefix-free code a.k.a. instantaneous code) for lossless compression. A playlist of these videos is available at: http://... Information theory: Coding (2 of 2)An explanation of prefix-free codes, and another demonstration of Huffman coding. More on information theory and coding: http://tinyurl.com/cnuo9z http://tin... (IC 2.4) Decoding - prefix versus non-prefixExamples to illustrate the ease of decoding a prefix code versus a non-prefix code. A playlist of these videos is available at: http://www.youtube.com/playli... STLegacy Request: USS Federation VS USS Relianthttp://stlegacy.tk/ This requested video is about the Federation Class starship USS Federation, fighting against the Miranda Class starship USS Reliant. The ... Country Code list. Calling Code. International Call Prefix. COUNTRY CODE iPhone AppInternational Dialing. Country Calling Code. International Dialing Codes. Area Codes. How to call abroad. Country Codes. International Prefix. International ... (IC 4.7) Optimality of Huffman codes (part 2) - weak siblingsWe prove that Huffman codes are optimal. In part 2, we show that there exists an optimal prefix code with a pair of "weak siblings". A playlist of these videos is available at: http://www.youtube... Nokia Unlock Code Prefixhow to get the # P W + symbols on nokia phones to enter unlock code from www.fonefunshop.co.uk/unlock. Area Code And Prefix Databasehttp://www.CityStateZipAreaCodeDatabase.com - IMMEDIATE DOWNLOAD! Download your copy of the complete database of all United States City, State, Zip Code, Are...
 12884 videos foundNext >
 4 news items
 Flaunt your Gold BlackBerry P'9981 by Porsche Design Daily Bhaskar Fri, 24 May 2013 18:58:29 -0700 A total of 25 limited edition examples of the gold-plated, leather-bound P'9981 Gold smartphone will ever be produced with each carrying a solid gold plaque on its rear, engraved with its serial number and its all-important 2AA prefix code. This code ... New York Daily News Can't afford a Porsche? Limited edition Porsche BlackBerry to go on sale for ... New York Daily News Thu, 23 May 2013 06:40:33 -0700 Just 25 examples of the gold-plated, leather-bound P'9981 Gold smartphone will ever be created, and each one carries a solid gold plaque on its rear, engraved with its serial number and its all-important 2AA prefix code. This code forms part of the ... Research In Motion Ltd (BBRY) News: Innovative Platform Boost, Cost-Effective ... Insider Monkey (blog) Thu, 23 May 2013 06:44:21 -0700 ... solid gold plaque on its rear, engraved with its serial number and its all-important 2AA prefix code. This code forms part of the handset's PIN and informs other Research In Motion Ltd (NASDAQ:BBRY) users that they are communicating with a P'9981 ... Porsche outdoes Vertu with gold P'9981 smartphone GoMo News Thu, 23 May 2013 02:21:38 -0700 So this is the bit which we like … the P'9981 Gold smartphone features an exclusive BlackBerry PIN number – identified by the prefix code '2AA', which identifies to other BlackBerry customers. Wow. Naturally for a gold smartphone the case is finished ...
 Limit to books that you can completely read online Include partial books (book previews) .gsc-branding { display:block; }

Oops, we seem to be having trouble contacting Twitter