Code

Code - a one-to-one mapping of a finite ordered set of characters belonging to a certain finite alphabet to another, not necessarily ordered, usually more extensive set of characters for encoding transmission , storage or transformation of information .

For example, a Morse code in which any letter / character is encoded by a sequence of dots and dashes. Another example is the encoding of letters, numbers, and symbols by sequences of logical zeros and ones in computers. A sequence of elementary encoded characters is usually called a code message or code message . Sometimes a sequence of encoded characters of known length is called a codeword , or code frame .

Content

Coding

The process of converting a message to a combination of characters in accordance with a code is called encoding ; the process of recovering a message from a combination of characters is called decoding .

Code Trees

For a clear description of the codes, code trees are used . If each level contains $m_{2}^{l}$ ${\ displaystyle m_ {2} ^ {l}}$ nodes, where l is the level number (the root of the tree is at level zero), it is called complete . Obviously, the value $m_{2}^{l_{max}}$ ${\ displaystyle m_ {2} ^ {l_ {max}}}$ , called the volume of the tree, characterizes the maximum number of code combinations that can be built using this tree.

In the theory of constructing translators, such a tree describes the set of all possible chains of conclusions from formal grammar .

Prefix Code

A prefix code is a code that does not have a single code word, which would be the prefix (beginning) of any other code word of the code. Any prefix code is separable (that is, any sequence of code words can always be uniquely divided into separate ones) ^[1] . Examples of prefix codes are Shannon , Shannon-Fano, and Huffman codes .

Examples

Uniform coding: codewords with length are used for an alphabet with m ₁ characters $n=up(log_{m_{2}}m_{1})$ ${\ displaystyle n = up (log_ {m_ {2}} m_ {1})}$ , where up is rounding to a larger integer. In this case, remain unused $log_{m_{2}}m_{1}-n$ ${\ displaystyle log_ {m_ {2}} m_ {1} -n}$ code words, and the rest are assigned the symbols of the primary alphabet. The Bodo code has a fixed length of 5 characters.

Prefix Codes: The Shannon-Fano Code is the first non-uniform coding algorithm. The Huffman code is a well-known method for constructing an optimal non-uniform code (ONC) using trees. Arithmetic coding is a generalization of the Huffman code.

Notes

↑ Gabidulin E. M. , Pilipchuk N. I. Lectures on Information Theory - MIPT , 2007. - P. 43–49. - 214 p. - ISBN 978-5-7417-0197-3
<a href=" https://wikidata.org/wiki/Track:Q4130888 "> </a> <a href=" https://wikidata.org/wiki/Track:Q27473237 "> </a> <a href = " https://wikidata.org/wiki/Track:Q27473383 "> </a>

Literature

Tsymbal V.P. Information Theory and Coding. - Kiev: Vyscha School, 1977. - 288 p.

[_ec8ef951a1229a77-1] Gabidulin E. M. , Pilipchuk N. I. Lectures on Information Theory - MIPT , 2007. - P. 43–49. - 214 p. - ISBN 978-5-7417-0197-3
<a href=" https://wikidata.org/wiki/Track:Q4130888 "> </a> <a href=" https://wikidata.org/wiki/Track:Q27473237 "> </a> <a href = " https://wikidata.org/wiki/Track:Q27473383 "> </a>