Prefix code

Prefix code or unprefixed code is a term from coding theory . As a prefix code is code refers to the Fano condition fulfilled: No code word of the code is prefix of another code word. In other words, no code word may represent the beginning of another code word. For example, a code with the code words {0, 10, 11} fulfills the prefix property, while the code with the code words {0, 01, 10} does not fulfill it, since "0" is the prefix of "01".

properties

With a prefix code, a message can be clearly broken down into its code words
Code words can be of different lengths
Each prefix code satisfies the force inequality

Examples

Objects A, B, C and D are represented with binary digits.

{\ displaystyle A \ rightarrow 0, B \ rightarrow 100, C \ rightarrow 101, D \ rightarrow 11}

An impermissible coding would be the following.

{\ displaystyle A \ rightarrow 10, B \ rightarrow 100, C \ rightarrow 101, D \ rightarrow 11}

The coding of A collides with that of B and C. Since, for example, CB is coded as 1011 0 0 and ADB as 1011 1 00, it becomes clear that, without the prefix property, the decoding of a code word will only take place a few digits later (or possibly even not possible.

Phone numbers

Each connection must be clearly identifiable by its telephone number. During the dialing process, it must not happen that another participant rings the bell in between. In Germany, for example, no other telephone number except the emergency number begins with 112. Likewise, no number begins with 0 in any local network, so that there is no collision with area codes (or special numbers such as 0800). Similar considerations apply to the international code .

Huffman code

Within the Huffman code , input symbols (for example the letters of a text) are coded with binary digit sequences of different lengths, the length of which depends on the frequency of the associated input symbol. In this way the memory consumption is optimized according to these frequencies. The Huffman code is a prefix code.

Fibonacci code

The Fibonacci code is a universal prefix code for the natural numbers.

Morse code

The Morse code is not inherently a prefix code because, for example, A (short-long) is a prefix of L (short-long-short-short). The message can only be clearly decoded by inserting pauses (in principle a third symbol next to short and long) between letters, e.g. B. short-long-break-short-short = AI, short-long-short-break-short = RE.

literature

Thomas H. Cormen, Charles E. Leiserson , Ronald L. Rivest : Introduction to Algorithms . 2nd Edition. MIT Press u. a., Cambridge MA [et al. a.] 2001, ISBN 0-262-03293-7 .
Ralph-Hardo Schulz: Coding Theory. An introduction . 2nd updated and expanded edition. Vieweg + Teubner Verlag, Wiesbaden 2003, ISBN 3-528-16419-0 .
Herbert Klimant, Rudi Piotraschke, Dagmar Schönfeld: Information and coding theory . 3rd revised and expanded edition. Vieweg + Teubner Verlag, Wiesbaden 2006, ISBN 3-8351-0042-4 ( textbook computer science ).