Main principles. 2.1 One of methods of digital signal transmission by communication channel with errors quality increasing is error-control codes using

2.1 One of methods of digital signal transmission by communication channel with errors quality increasing is error-control codes using. Error-control codes allow to detect or to correct errors which appear in a communication channel. In this work binary block error-control codes study.

2.2 General principle of error-control codes construction easy enough. From the possible code words of length n number M = 2 ⁿ not all are used for the transmission, only M ₀ = 2 ^k (M ₀ < M). The used code words are named permitted. Other M – M ₀ code words is considered forbidden, they can not appear at the communication channel input, their appearance on the channel output indicates about errors. Thus, due to the forbidden code words presence the possibility of error detection appears. So, any error-control code is a code with redundancy (r = n – k redundant (checking) symbols in every code word transmits by communication channel).

2.3 For error-control codes description next parameters are used.

Hamming distance d_ij shows the order of difference between i -th and j -th code words. For any two binary code words distance equals the noncoincident symbols number in them.

Code distance d _min is the minimum Hamming distance for the given code. Enumerating all possible pair of the permitted code words and calculating distances d_ij for them, it is necessary to find minimal among them, d _min = min d_ij.

Code rate R shows the relative number of information symbols k in code words of length n and R is calculated as R = k / n.

Code control ability is determined by order of detected errors q _det, and order of corrected errors q_corr.

The order of detected errors q _det is number of errors in code word, which are assured detected at decoding, – it is determined as: q _det < d _min.

The order of corrected errors q_corr is the number of errors in code word, which are corrected at decoding, – it is determined: q_corr < d _min /2.

2.4 At the error-control coding use in the communication channel structure error-control code encoder and decoder is included, it is resulted on the figure 1.

Encoder and decoder destination consists in the following. Code word А _i, length k on the encoder input, encoder will transform it in error-control code word В _i, length n in accordance with the coding rule, and n > k. Code word, length n from a communication channel on the decoder input:

= В _i Å Е, (1)

where Е is error word. For example, В _i = 101000; let an error appear in the second and third symbols, then Е = 011000, and = 110000.

Depending on code control ability and purpose of its application the error-control code decoder can work in the detection mode or in the error correction mode. In the error detection mode a decoder analyses: is word permitted or forbidden? If word is permitted, a decoder in accordance with the decoding rule forms on the output information code word А _j, length k. If word is forbidden, a decoder does not decode it, on the decoder output no any code word, and a certain signal appears on the error signal output (figure 1) (for example, "1"). In the error correction mode a decoder instead of the forbidden code word decodes the permitted code word the nearest to it in accordance with the decoding rule and gives out information code word length k.

2.5 In transmission systems systematic codes the most distributed, code word of systematic code contain k information symbols (symbols on the encoder input) and r = n – k checking symbols formed by encoder from information code word. In the case of linear codes checking symbols are linear combinations of information code word.

Among systematic block codes wide distribution was got by cyclic codes, due to easy encoder and decoder construction. For cyclic codes description by polynomials is most useful - for example, the code word A _i =10111 corresponds topolynomial a_i (х) = х ⁴ + х ² + х + 1 (code word symbols are coefficients at the proper dummy variable x order of, thus to symbol 1, which is written down first, the most high order х in a polynomial corresponds).

Any cyclic code is set by not only the numbers of n and k but also generate polynomial g (x) order r. A cyclic (n, k) code names a code, all code words of which appear by the polynomials order of n - 1 and less, which are divided without remainder on generate polynomial. In table 1 generate polynomials are resulted for r = 3, 4 and 5.

Cyclic code (n, k) encoder operation method consists in the following. Lets a (x) is polynomial which corresponds to information code word on the encoder input. Polynomial a (x)× x^r corresponds to addition r zeros to information code word on the right. The polynomial a (x)× x^r on the generate polynomial g (x) dividing with the purpose of determination of remainder from the dividing r (x) is executed. Remainder from the dividing r (x) is the checking symbols. Polynomial, corresponding to code word on encoder output, it is determined:

b (x) = a (x)× x^r + r (x), (2)

the r zeros, is change by combination proper to the remainder from the dividing.

It is easy to show that the polynomial b (x) is divided without a remainder on the polynomial of g(x):

,

where p(x) is integer part from the division a (x)× x^r / g (x).

You should remember that addition of polynomials is executed as XOR operation of coefficients at the equal orders of х.

We will consider the example of code (10, 5) code word forming with the generate polynomial g (x) = x ⁵ + x ⁴ + x ² + 1 Lets А _i = 10110, then a_i (x) = x ⁴ + x ² + x, and a_i (x)× x ⁵ = x ⁹ + x ⁷ + x ⁶. We will execute the division with the purpose of remainder determination.

Acording to (2) b_i (x) = x ⁹ + x ⁷ + x ⁶ + x ³ + x ² + 1 or B _i = 1011001101.

In the cyclic code decoder the code word on decoder input division on generate polynomial is produced. Polynomials of the code word on encoder output b (x), code word on decoder input and errors e (x) connected by expression like (1): = b (x) Å e (x).The result of division on generate polynomial can be represented

,

From these expression follows that remainder s (x) depends only on the error polynomial and does not depend on the code word on encoder output (v (x) is integer part from the division e (x) on b (x)). Remainderfrom the division s (x) on g (x) is a syndrome. A nonzero remainderindicates that the accepted code word is forbidden (with errors). If a decoder works in the error correction mode, the error symbol number (or numbers of error symbols) is determined on the syndrome analysis base. For code (10, 5) with the generate polynomial g (x) = x ⁵ + x ⁴ + x ² + 1 we will make the syndromes table for all single errors, executing the divisions e (x) on g (x) and writing down remaindersfrom the division in table 2.

From table 2 follows that in the case of single errors (first order errors) all syndromes are different, therefore every syndrome simply specifies the error symbol number. Error correction by a decoder is executes by decipherer built according to table 2, and inverting element which executes the error symbol inversion.

The researched code (10, 5) has code distance d _min = 4 and allows to correct first order errors.