Efficient coding.

Under redundancy understand the use of a large number of characters than the minimum necessary. Language has a great redundancy. The question arises how to construct the rule G in such a way that the redundancy is minimal. Requirements for building non-redundant (effective) codes. The greater the likelihood of a message, the less should be its length. We obtain a mathematical relationship connecting the probability of occurrence and the length of the corresponding code combination.

Let the encoding map X = {x ₁ , x ₂ , ..., x _r } be B, and | m | power.

The coding mapping To each x _i sets in correspondence some code combination of length n _i from the alphabet B. Task: Estimate the minimum average length of the code combination of the code G. Knowing this value and comparing it with the average code word length of the real code, you can determine how real close to optimal. The probability P (x _i ) is known, and the entropy is H (x) =-= [i = 1, k] P (x _i ) * log ₂ P (x _i ), the average length n _cf = ∑ _{i = 1} ^r P _i * n _i . Maximum entropy, which can have a message from the characters of the alphabet: H _max = n _cf * log ₂ m, since H _max ≥H (x), then n _cf * log ₂ m ≥ -∑ _{i = 1} ^r P (x _i ) * log ₂ P (x _i ). Consider a special case in which redundancy = 0. (H (x) = H _max ), k _i is the redundancy factor.

k _i = (H _max - H (x)) / H _max ), k _i = (n _cf - n _min ). ∑ _{i = 1} ^r n _i * P (x _i ) * log ₂ m = –∑ [i = 1, r] P (x _i ) log ₂ P (x _i ), _{i = 1} ^r (P (x _i ) * (n _i log ₂ m + log ₂ P (x _i )) = 0, n _i log ₂ m + log ₂ P (x _i ) = 0, n _i = -log ₂ (P (x _i )) / log ₂ m (*). From (*) it follows that the length of the i-th code combination ~ (-log) of the probability of the i-th message. The left part is an integer, the right part is most often non-integer. The resulting condition for real. building an effective code cannot be used, since all equality is not fulfilled, but one can demand that n _i lie in a certain range of the obtained value, in which there is necessarily one whole.

- log ₂ P (x _i ) / log ₂ m ≤ n _i ≤ (- log ₂ P (x _i ) / log ₂ (m)) +1, multiply both parts by P (x _i ) .... - ∑ _{i = 1} ^r P (x _i ) log ₂ P (x _i ) / log ₂ m ≤ _{i = 1} ^r P (x _i ) n _i ≤ (-∑ _{i = 1} ^r P (x _i ) * log ₂ P (x _i ) / log ₂ m) + _{i = 1} ^r P (x _i ),

H (x) / log ₂ m≤n cf ≤ (H (x) / log ₂ m) +1 (**).

Using this inequality, one can numerically estimate the structure of the constructed code. To obtain efficient codes close to zero, there are several methods (Huffman code, Shannon-Fano code).