Syndrome decoding of cyclic codes

Let’s consider the decoders of cyclic codes. The construction of decoder for errors detection is shown in a fig. 1.3.

The decoder has: buffer register of k-bits; decoding register, the chart of which is similar to the chart of the encoder; logical charts OR, AND with the trigger, executing functions of the keys.

A decoder works as follows. The received informative sequence writes simultaneously in buffer and in decoding registers. On (k+1)-th clock cycle the electronic key &_k+1 is closed and in this case the information bits of the received code combination appear in a buffer register only. Check bits continue to enter decoding register.

On (n+1)-th clock cycle, after the reception of the last digit of code combination, the electronic key &_k+2 opens. If code combination is accepted without errors, then in the cells of decoding register only zeros will be written, and the signal "ERROR" will be absent. A presence even in one cell of decoding register of one testifies to the errors in the received information. In the output of the chart “OR” at this case a signal "ERROR" will appear, that can be used for deleting of the received code combination with errors accumulated in the buffer register.

If a decoder is used in the mode of the correction of errors, then it is necessary to specify the place of the error information bits. In the structure of the decoder instead of chart “OR” use the decipherer of the syndrome, producing in its output signal “1” during fixing in the cells of decoding register of remainder different from zero.

Figure 1.3 – Flow diagram of the cyclic (n, k) code decoder

For the position-fix of an error element received code combination of cyclic code use a remainder from dividing of this code combination by the generator polynomial Р(х). The got remainder R(x) is the syndrome of error. This procedure will be realized by comparison of remainder R(x) with the table of syndrome combinations formed by dividing of errors vectors e(x) by the generator polynomial Р(х).

As an example let’s consider the cyclic code decoder (15, 11) with the generator polynomial Р(х) = х⁴ + х + 1, correcting single errors. For this code a single error vector e(x) = х¹⁴ (100000000000000) is divided by the generator polynomial Р(х) = х⁴ + х + 1, forming the remainder S₁₄(x) = х³ + 1. If in the accepted combination of cyclic code the error is in 15^th position, i.e. bit х¹⁴, then a remainder from dividing of it by Р(х) will coincide with S₁₄(x).

Syndrome combinations for the errors vectors х¹³, х¹², х¹¹, х¹⁰, х⁹, х⁸, х⁷, х⁶, х⁵, х⁴, х³, х², х¹, х⁰ form similarly. For the chosen cyclic code with n = 9 have syndromes in table 1.2.

Comparing the remainder R(x) with syndrome combinations S_i(x), , get information about an error element in the accepted combination of the cyclic code.

Table 1.2 – The syndrome table for cyclic (15,11) code

So, the correction of errors is based on correspondence between the amount of syndromes values and the amount of the corrected errors. However at multiplicity of errors t > 1 this accordance breaks. As a rule, takes place additional input of error symbols, that is the serious defect of the syndrome decoder.

Date: 2015-02-16; view: 1507