Syndrome decoding

Laboratory work 4.3

NOISE IMMUNITY OF BLOCK ERROR-CONTROL CODES

Objectives

1.1 Study of decoding algorithms of (n, k) block error-control codes with the errors correction.

1.2 Experimental researches of noise immunity of (n, k) block error-control codes with the errors correction.

1.3 Experimental researches of coding gain (CG).

Main positions

Block codes

Bose-Chaudhuri-Hochuenghem (BCH) codes are class of systematic linear cyclic block codes correcting multiple errors, that is, two or more (d _min³ 5) [1].

Theoretically, BCH codes can correct any number of errors, but substantially increased the duration of code combinations, resulting in increased delays and complications data decoding algorithm.

Code distance d _min of block (n, k) code can be calculated by the formula [2]

d _min = 2 q _cor + 1, (1)

where q _cor is multiplicity of errors that are corrected by a code (n, k), q _cor can be calculated from the ratio [3]

k = n – m q _cor., (2)

where m is smallest integer that satisfies the condition 2 ^m ≥ n.

Syndrome decoding

For (n, k) block error-control codes today the syndromes decoding is basic for detection and correction of errors.

Syndromes method of errors correction is based on a simple rule: on the syndrome of code word the errors location is determined. Therefore under the syndrome of code word understand the result of decoder calculation on the set rules of number s = (s ₁, s ₂, …, s_r), r = n – k, which testifies to the errors detected and determines their placing (configuration) in code word. In binary codes a syndrome is written down in the binary number system, that its digits s ₁, s ₂, …, s_r take on a value 0 and 1.

A zero syndrome specifies on that the received code word is permitted, that the detected errors are not present. Nonzero syndrome is corresponding to some errors configurations. Thus syndrome is used for decoding with error detection.

At decoding with error correction decoded by syndrome code combination determined the location of errors.

If the multiplicity of errors in decoded code combination q does not exceed multiplicity of errors that are corrected q _cor, q ≤ q _cor, then syndrome uniquely identifies the location of errors in the code combination, and errors are corrected by inversion of symbol error.

If q > q _cor, then two situations are possible:

– the syndrome received by calculation corresponds to some configuration of errors which meets at q ≤ q _cor, in this situation the decoder "corrects" errors, but correction not true, and, most likely, the quantity of erroneous symbols in a code word grows;

– the syndrome received by calculation does not correspond to any of configurations of errors which can be at q ≤ q _cor, in this situation the decoder "refuses" decoding and passes such code word on an output with errors.

Thus, the syndromes decoding of binary codes is taken to the calculation of syndrome and search that or by other method errors configurations which errors are corrected on. Correction of an error in some binary symbol is reduced to its inversion and carried out by addition of an erroneous symbol with 1 on the module 2.The generalized block diagram of syndromes decoder is resulted in figure 1.

In the scheme of figure 1 “Syndrome analyzer” is the most complex device. In it on the calculated syndrome errors configuration, on which then the errors corrected with corrector, is set. As a syndrome can be calculated only after reception of all code word (block), for the errors correction in a code word needed to delay on n symbols, which is carried out n- digitshift register. After establishment of errors configuration an analyzer symbols of the decoding word are consistently "pushed" from a shift register, and from an analyzer symbols "1" act in those moments of time, when it is necessary to invert erroneous symbols.

Дата добавления: 2015-10-31