3.18 Correction by Erasure

3.18 Correction by Erasure

In the examples of Figure 3.30, two redundant symbols P and Q have been used to locate and correct one error symbol. If the positions of errors are known by some separate mechanism (see product codes, section 3.19) the locator need not be calculated. The simultaneous equations may instead be solved for two correctors. In this case the number of symbols that can be corrected is equal to the number of redundant symbols. In Figure 3.31(a) two errors have taken place, and it is known that they are in symbols C and D. Since S is a simple parity check, it will reflect the modulo-2 sum of the two errors. Hence S 1 = E C E D.

image from book
Figure 3.31: If locations of errors are known, the syndromes are a known function of the two errors as shown in (a). It is, however, much simpler to set the incorrect symbols to zero, that is, to erase them as in (b). Then the syndromes are a function of the wanted symbols and correction is easier.

The two errors will have been multiplied by different powers in S 1 , such that:

S 1 = a 5 E C a 4 E D

These two equations can be solved, as shown in the figure, to find E C and E D, and the correct value of the symbols will be obtained by adding these correctors to the erroneous values. It is, however, easier to set the values of the symbols in error to zero. In this way the nature of the error is rendered irrelevant and it does not enter the calculation. This setting of symbols to zero gives rise to the term erasure. In this case,

S = C D

S 1 = a 5 C a 4 D

Erasing the symbols in error makes the errors equal to the correct symbol values and these are found more simply as shown in Figure 3.30 (b).

Practical systems will be designed to correct more symbols in error than in the simple examples given here. If it is proposed to correct by erasure an arbitrary number of symbols in error given by t , the codeword must be divisible by t different polynomials . Alternatively, if the errors must be located and corrected, 2 t polynomials will be needed. These will be of the form ( x + a n ) where n takes all values up to t or 2 t , where a is the primitive element.

Where four symbols are to be corrected by erasure, or two symbols are to be located and corrected, four redundant symbols are necessary, and the codeword polynomial must then be divisible by

( x + a ) ( x + a 1 ) ( x + a 2 ) ( x + a 3 )

Upon receipt of the message, four syndromes must be calculated, and the four correctors or the two error patterns and their positions are determined by solving four simultaneous equations. This generally requires an iterative procedure, and a number of algorithms have been developed for the purpose. 5 - 7 Modern FEC systems, such as ATM and DVB, use eight-bit RS codes and erasure extensively. The primitive polynomial commonly used with GF(256) is:

x 8 + x 4 + x 3 + x 2 + 1

The codeword will be 255 bytes long but will often be shortened by puncturing. The larger Galois fields require less redundancy, but the computational problem increases . LSI chips have been developed specifically for RS decoding in many high-volume formats.



Digital Interface Handbook
Digital Interface Handbook, Third Edition
ISBN: 0240519094
EAN: 2147483647
Year: 2004
Pages: 120

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net