View source for Coding and decoding

The process of representing [[Information|information]] in a definite standard form and the inverse process of recovering the information in terms of such a representation of it. In the mathematical literature an encoding (coding) is a mapping of an arbitrary set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c0228901.png" /> into the set of finite sequences (words) over some alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c0228902.png" />, while the inverse mapping is called a decoding. Examples of an encoding are: the representation of the natural numbers in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c0228903.png" />-ary number systems, where each number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c0228904.png" /> is made to correspond to the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c0228905.png" /> over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c0228906.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c0228907.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c0228908.png" />; the conversion of English texts by means of a telegraphic code into sequences consisting of the transmission of pulses and pauses of various lengths; and the mapping applied in writing down the digits of a (Russian) postal index (see Fig.a and Fig.b). In this latter case, there corresponds to each decimal digit a word over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c0228909.png" /> of length 9 in which numbers referring to a line that is to be used are marked by the symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289010.png" />. (For example, the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289011.png" /> corresponds to the digit <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289012.png" />.)

<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/c022890a.gif" />

Figure: c022890a

<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/c022890b.gif" />

Figure: c022890b

The investigation of various properties of coding and decoding and the construction of encodings that are effective in some sense and possess specified properties constitute the subject matter of coding theory. Usually, a criterion for the effectiveness of an encoding is in some way or other tied up with the minimization of the length of the code words (images of the elements of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289013.png" />), and the specified properties of the coding relate to the guarantee of a given level of [[Noise immunity|noise immunity]], to be understood in some sense or other. In particular, noise immunity means the possibility of unique decoding in the absence of, or at a tolerable level of, distortion of the code words. Besides noise immunity, a number of additional requirements may be imposed on the code. For example, in the choice of an encoding for the digits of a postal code, an agreement with the ordinary way of writing digits is necessary. As additional requirements, restrictions are often applied relating to the allowed complexity of the scheme effecting the coding and decoding. The problems in coding theory were in the main created under the influence of the theory of information transmission as developed by C. Shannon [[#References|[1]]]. A source of new problems in coding theory is provided by the creation and perfection of automated systems of gathering, storage, transmission, and processing of information. The methods of solving problems in coding theory are mainly combinatorial, probability-theoretic and algebraic.

An arbitrary coding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289014.png" /> of a set (alphabet) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289015.png" /> by words over an alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289016.png" /> can be extended to the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289017.png" /> of all words over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289018.png" /> (messages) as follows:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289019.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289020.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289021.png" />. Such a mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289022.png" /> is called a letter-by-letter encoding of the messages. A more general class of encodings of messages is found by automated encoding realized by initial asynchronous automata (cf. [[Automaton|Automaton]]), which deliver at each instant of time some (possibly empty) word over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289023.png" />. The importance of this generalization consists in the fact that the automaton realizes, in different states, different encodings of the letters of the alphabet of the messages. A letter-by-letter encoding is an automaton encoding realized by a single-state automaton. One of the branches of coding theory is the study of the general properties of a coding and the construction of algorithms for recognizing these properties (see [[Coding, alphabetical|Coding, alphabetical]]). In particular, necessary and sufficient conditions have been found for automated and letter-by-letter encodings in order that 1) the decoding be single-valued; 2) there exists a decoding automaton, that is, an automaton effecting the decoding with a certain bounded delay; or 3) there exists a self-adjusting decoding automaton (making it possible to eliminate in a limited amount of time the effect of a mistake in the input sequence or in the functioning of the automaton itself).

The majority of problems in coding theory reduces to the study of finite or countable sets of words over an alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289024.png" />. Such sets are called codes. In particular, there corresponds to each single-valued encoding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289025.png" /> (and letter-by-letter encoding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289026.png" />) a code <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289027.png" />. One of the basic assertions in coding theory is that the condition of injectivity of a letter-by-letter encoding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289028.png" /> imposes the following restrictions on the lengths <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289029.png" /> of the code words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289030.png" />:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289031.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>

The converse statement also holds: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289032.png" /> is a set of natural numbers satisfying (1), then there exists a one-to-one letter-by-letter encoding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289033.png" /> such that the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289034.png" /> has length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289035.png" />. Furthermore, if the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289036.png" /> are increasingly ordered, then one can take for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289037.png" /> the first <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289038.png" /> symbols after the decimal point of the expansion of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289039.png" /> in an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289040.png" />-ary fraction (Shannon's method).

The most definitive results in coding theory relate to the construction of effective one-to-one encodings. The constructions described here are used in practice for the compression of information and access of information from the memory. The concept of effectiveness of an encoding depends on the choice of the cost criterion. In the definition of the cost <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289041.png" /> of a one-to-one letter-by-letter encoding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289042.png" /> it is assumed that there corresponds to each number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289043.png" /> a positive number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289044.png" /> and that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289045.png" />. The following versions of a definition of the cost <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289046.png" /> have been investigated:

1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289047.png" />,

2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289048.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289049.png" />,

3) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289050.png" />, where it is supposed that in the first two cases the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289051.png" /> are the probabilities with which some Bernoullian source generates the corresponding letters of the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289052.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289053.png" />), while in the third case, the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289054.png" /> are desirable lengths of code words. In the first definition, the cost is equal to the average length of a code word; in the second definition, as the parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289055.png" /> increases, the longer code words have a greater influence on the cost (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289056.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289057.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289058.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289059.png" />); in the third definition, the cost is equal to the maximum excess of the length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289060.png" /> of the code word over the desired length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289061.png" />. The problem of constructing a one-to-one letter-by-letter encoding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289062.png" /> minimizing the cost <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289063.png" /> is equivalent to that of minimizing the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289064.png" /> on the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289065.png" /> of natural numbers satisfying the condition (1). The solution of this problem is known for each of the above definitions of a cost.

Suppose that the minimum of the quantity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289066.png" /> on the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289067.png" /> of arbitrary (not necessarily natural) numbers satisfying condition (1) is equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289068.png" /> and is attained on the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289069.png" />. The non-negative quantity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289070.png" /> is called the redundancy, and the quantity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289071.png" /> is called the relative redundancy of the encoding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289072.png" />. The redundancy of a one-to-one encoding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289073.png" /> constructed by the method of Shannon for lengths <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289074.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289075.png" />, satisfies the inequality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289076.png" />. For the first, most usual, definition of the cost as the average number of code symbols necessary for one letter of the message generated by the source, the quantity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289077.png" /> is equal to the Shannon entropy

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289078.png" /></td> </tr></table>

of the source calculated in the base <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289079.png" />, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289080.png" />. The bound of the redundancy, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289081.png" />, can be improved by using so-called coding blocks of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289082.png" />, in which messages of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289083.png" /> (rather than separate letters) are encoded by the Shannon method. The redundancy of such an encoding does not exceed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289084.png" />. This same method is used for the effective encoding of related sources. In connection with the fact that the determination of the lengths <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289085.png" /> in coding by the Shannon method is based on a knowledge of the statistics of the source, methods have been developed, for certain classes of sources, for the construction of a universal encoding that guarantees a definite upper bound on the redundancy for any source in this class. In particular, a coding by blocks of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289086.png" /> has been constructed with a redundancy that is, for any Bernoullian source, asymptotically at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289087.png" /> (for fixed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289088.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289089.png" />), where this asymptotic limit cannot be improved upon.

Along with the problems of the effective compression of information, problems of the estimation of the redundancy of concrete types of information are also considered. For example, the relative redundancy of certain natural languages (in particular, English and Russian) has been estimated under the hypothesis that their texts are generated by Markov sources with a large number of states.

In the investigation of problems on the construction of effective noise-immune encodings, one usually considers encodings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289090.png" /> to which correspond codes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289091.png" /> belonging to the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289092.png" /> of words of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289093.png" /> over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289094.png" />. It is understood here that the letters of the alphabet of the messages <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289095.png" /> are equi-probable. The effectiveness of such an encoding is estimated by the redundancy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289096.png" /> or by the transmission rate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289097.png" />. In the definition of the noise-immunity of an encoding, the concept of an error is formalized and a model for the generation of errors is brought into consideration. An error of substitution type (or simply an error) is a transformation of words consisting of the substitution of a symbol in a word by another symbol in the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289098.png" />. For example, the production of a superfluous line in writing out the figure of a Russian postal index leads to the replacement in the coded word of the symbol 0 by the symbol 1, while the omission of a necessary line leads to the replacement of 1 by 0. The possibility of detecting and correcting errors is based on the fact that, for an encoding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c02289099.png" /> with non-zero redundancy, the decoding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890100.png" /> can be extended in arbitrary fashion onto the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890101.png" /> words in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890102.png" /> which are not code words. In particular, if the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890103.png" /> is partitioned into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890104.png" /> disjoint sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890105.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890106.png" /> and the decoding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890107.png" /> is extended so that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890108.png" />, then in decoding, all errors that translate a code word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890109.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890110.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890111.png" />, will be corrected. Similar possibilities arise also in the case of other types of error, such as the erasure of a symbol (substitution by a symbol of a different alphabet), the alteration of the numerical value of a code word by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890112.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890113.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890114.png" /> (an arithmetic error), the deletion or insertion of a symbol, etc.

In the theory of information transmission (see [[Information, transmission of|Information, transmission of]]), probabilistic models of error generation are considered; these are called channels. The simplest memoryless channel is defined by the probabilities <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890115.png" /> of substitution of a symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890116.png" /> by a symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890117.png" />. One defines for this channel the quantity (channel capacity)

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890118.png" /></td> </tr></table>

where the maximum is taken over all sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890119.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890120.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890121.png" />. The effectiveness of an encoding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890122.png" /> is characterized by the transmission rate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890123.png" />, while the noise-immunity is characterized by the mean probability of an error in the decoding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890124.png" /> (under the optimal partitioning of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890125.png" /> into subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890126.png" />). The main result in the theory of information transmission (Shannon's theorem) is that the channel capacity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890127.png" /> is the least upper bound of the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890128.png" /> such that for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890129.png" /> and for all sufficiently large <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890130.png" /> there exists an encoding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890131.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890132.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890133.png" />.

Another model for the generation of errors (see [[Error-correcting code|Error-correcting code]]; [[Code with correction of arithmetical errors|Code with correction of arithmetical errors]]; [[Code with correction of deletions and insertions|Code with correction of deletions and insertions]]) is characterized by the property that in each word of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890134.png" /> there occur not more than a prescribed number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890135.png" /> of errors. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890136.png" /> be the set of words obtainable from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890137.png" /> as a result of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890138.png" /> or fewer errors. If for the code

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890139.png" /></td> </tr></table>

the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890140.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890141.png" />, are pairwise disjoint, then in a decoding such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890142.png" />, all errors admitting of a model of the above type for the generation of errors will be corrected, and such a code is called a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890144.png" />-error-correcting code. For many types of errors (for example, substitutions, arithmetic errors, insertions and deletions) the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890145.png" /> equal to the minimal number of errors of given type taking the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890146.png" /> into the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890147.png" /> is a metric, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890148.png" /> is the metric ball of radius <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890149.png" />. Therefore the problem of constructing the most effective code (that is, the code with maximum number of words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890150.png" />) in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890151.png" /> with correction of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890152.png" /> errors is equivalent to that of the densest packing of the metric space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890153.png" /> by balls of radius <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890154.png" />. The code for the figures of a Russian postal index is not a one-error-correcting code, because <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890155.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890156.png" />, while all other distances between code words are at least 3.

The problem of studying the minimal redundancy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890157.png" /> of a code in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890158.png" /> for correction of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890159.png" /> errors of substitution type is divided into two basic cases. In the first case, when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890160.png" /> is fixed as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890161.png" />, the following asymptotic relation holds:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890162.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>

where the  "power"  bound is attained, based on a count of the number of words of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890163.png" /> in a ball of radius <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890164.png" />. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890165.png" /> the asymptotic behaviour of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890166.png" /> when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890167.png" /> except <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890168.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890169.png" />, and also when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890170.png" /> for many other types of errors (for example, arithmetic errors, deletions and insertions), is not known (1987). In the second case, when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890171.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890172.png" /> is some fixed number, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890173.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890174.png" />, the  "power"  bound

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890175.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890176.png" />, is substantially improved. It is conjectured that the upper bound

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890177.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>

obtained by the method of random sampling of codes, is asymptotically exact for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890178.png" />, that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890179.png" />. The proof or refutation of this conjecture is one of the central problems in coding theory.

The majority of the constructions of noise-immune codes are effective when the length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890180.png" /> of the code is sufficiently large. In this connection, questions relating to the complexity of systems that realize the coding and decoding (encoders and decoders) acquire special significance. Restrictions on the admissible type of decoder or on its complexity may lead to an increase in the redundancy necessary to guarantee a prescribed noise-immunity. For example, the minimal redundancy of a code in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890181.png" /> for which there is a decoder consisting of a shift register and a single majorizing element and correcting one error has order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890182.png" /> (compare with (2)). As mathematical models of an encoder and a decoder, diagrams of functional elements are usually considered, and by the complexity is meant the number of elements in the diagram. For the known classes of error-correcting codes, investigations have been carried out of the possible encoding and decoding algorithms and upper bounds for the complexity of the encoder and decoder have been obtained. Also, certain relationships have obtained among the transmission rate of the encoding, the noise-immunity of the encoding and the complexity of the decoder (see [[#References|[5]]]).

Yet another line of the investigation in coding theory is connected with the fact that many results (e.g. Shannon's theorem and the upper bound (3)) are not  "constructive" , but are theorems on the existence of infinite sequences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890183.png" /> of codes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890184.png" />. In this connection, efforts have been made to sharpen these results in order to prove them in a class of sequences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890185.png" /> of codes for which there is a Turing machine that recognizes the membership of an arbitrary word of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890186.png" /> in the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890187.png" /> in a time having slow order of growth with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890188.png" /> (e.g. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890189.png" />).

Certain new constructions and methods for obtaining bounds, which have been developed within coding theory, have led to a substantial advance in questions that on the face of it seem very remote from the traditional problems in coding theory. One should mention here the use of a maximal code for the correction of one error in an asymptotically-optimal method for realizing functions of the algebra of logic by contact schemes (cf. [[Contact scheme|Contact scheme]]); the fundamental improvement of the upper bound for the density of packing the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890190.png" />-dimensional Euclidean space with identical balls; and the use of inequality (1) in estimating the complexity of realizing a class of functions of the algebra of logic by formulas. The ideas and results of coding theory find further developments in the synthesis of self-correcting schemes and reliable schemes of unreliable elements.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  C. Shannon,   "A mathematical theory of communication"  ''Bell Systems Techn. J.'' , '''27'''  (1948)  pp. 379–423; 623–656</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  E. Berlekamp,   "Algebraic coding theory" , McGraw-Hill  (1968)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  E. Weldon jr.,   "Error-correcting codes" , M.I.T.  (1972)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top"> , ''Discrete mathematics and mathematical problems in cybernetics'' , '''1''' , Moscow  (1974)  pp. Sect. 5  (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  L.A. Bassalygo,   V.V. Zyablov,   M.S. Pinsker,   "Problems of complexity in the theory of correcting codes"  ''Problems of Information Transmission'' , '''13''' :  3  pp. 166–175  ''Problemy Peredachi Informatsii'' , '''13''' :  3  (1977)  pp. 5–17</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  V.M. Sidel'nikov,   "New bounds for densest packings of spheres in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c022/c022890/c022890191.png" />-dimensional Euclidean space"  ''Math. USSR-Sb.'' , '''24'''  (1974)  pp. 147–157  ''Mat. Sb.'' , '''95''' :  1  (1974)  pp. 148–158</TD></TR></table>



====Comments====
Two standard references on error-correcting codes and coding theory are [[#References|[a1]]], [[#References|[a2]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  F.J. MacWilliams,   N.J.A. Sloane,   "The theory of error-correcting codes" , '''I-II''' , North-Holland  (1977)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J.H. van Lint,   "Introduction to coding theory" , Springer  (1982)</TD></TR></table>