NO851302L - SYSTEM FOR ERROR CORRECTION IN DIGITAL SIGNALS IN REED SOLO CODE - Google Patents

Abstract

Method for decoding data coded in Reed-Solomon code with correction of errors, wherein the code words are represented by bits forming a polynomial degree (n-1) comprised of m symbols of information and k control symbols with m+k = n-1, the control symbols being formed by words of 2<p> bits, said words forming the elements of a finite body of Gallois CG (2<p>) comprising the following steps: (i) dividing a packet of bits to be coded by a code generator polynomial of order k, and as a result the portion of the division provides the m information symbols and the remainder of the division be k control symbols; (ii) calculating the syndromes of the polynomial representative of a code word for certain roots of the code generator polynomial, those syndromes being eight and being related by a system of four linear equations of which the coefficients ( sigma 1 - sigma 4) are the locations of the errors in the code word; and resolving those localizing equations.

Description

SYSTEM FOR ERROR CORRECTION IN DIGITAL SIGNALS IN REED-SOLOMON CODE

The present invention relates to a method for coding and decoding digital data using an error correction code, as well as an encoder and a decoder for implementing said method. More precisely, the invention relates to a method for encoding and decoding using the Reed-Solomon code and the encoders and decoders that perform this method.

The Reed-Solomon code is described, for example, in the work "The Theory of Error-Correcting Codes" by F.J. Mac Williams and N.J.A. Sloane, North Holland Publishing Company, 1981, Chapter 10.

It will be recalled that a Reed-Solomon code in a finite Gallois field GF(q) is a Bose, Chaudhuri, Hocquenhem (BCH) code of length N = q - 1.

The CBH codes are codes where the generator polynomial per definition is as follows:

where 6 is the designated distance, with 6 - 2 = 2t + 1, where t represents the number of errors to be corrected.

The roots of G(x) are therefore the successive powers of a primitive element belonging to GF(2). This means that in a password:

yn_j_ has two possible values, 0 or 1, and

xn creates the position of Yn_ ±>

In a Reed-Solomon code, the characteristic of the field is no longer 2, but any whole prime number b which. results in a field GF(b^), Each vn_j_ no longer has two possible forms, but q =

bp forms. The coefficient y . is a code symbol.

nine

A definition of the polynomial thus results, where the coefficients are no longer just whole numbers 0 or 1 (base 2), but elements of GF(b<p>) which will be expressed by p binary elements.

If e.g. mn= 0, q = 2 3 and if the characteristic polynomial, which generates the elements of the field is equal to x 3 + x 2 +1, then each coefficient will be expressed in the form of a 3-bit word.

As for the binary case, the roots of the polynomial are defined as follows and for irig = 0 the code generator polynomial is:

The generator polynomial must " have a number of roots equal to twice the number t of errors to be corrected. In fact, the root has the highest power The roots of the generator polynomial are therefore

Since q is equal to 8, the length of the code words is given by N = 7 symbols. A code C(7, 4) contains four information symbols and three control symbols with three bits in each. The password can, for example, be written as:

where I(x) represents the information symbols and R(x) the control symbols which consist of the remainder when I(x) is divided by G(x).

An error is characterized by its value and position in a given code word. In the binary code case, it is enough to determine the position of the error, its value being obtained by supplementing the erroneous value in the calculated position. Correcting two errors using a binary code therefore involves solving a system of two equations with two unknowns. But in the case of a Reed-Solomon code, a code symbol is formed by a packet of p bits. In this case, two are mischaracterized by four parameters, respectively their two values and their two positions.

The invention in terms of both the coding method and the encoder and decoder for the Reed-Solomon code will now be described with reference to the attached drawings, where

fig. 1 in the form of a block kernel represents the encoder of the Reed-Solomon code embodying the invention,

fig. 2 represents the decoder of the Reed-Solomon code embodying the invention, and

fig. 3 represents the decoding algorithm.

1 - CODING

As indicated above, the symbols of the code are elements in the limited field of 2P elements. Each code symbol comprises p bits.

The code symbols are obtained by dividing the information message I(x) by the generator polynomial G(x).

The code consists of m information symbols and k control symbols.

The code is denoted by C(m + k, m). A well-known method for coding consists of pre-multiplying I(x) by x^, where k is the highest degree in the generator polynomial and dividing the thus obtained product by G(x), i.e.

where G(x) has the polynomial form previously indicated by k = m + 6 - 1. The described code is a code C(255, 247) with 2y d = 2 8, when I (x) = z 247 x 2 + ...Zq

The coefficients A, B, C, D, E, F, G and H are eight-bit words.

The polynomial division to be performed is:

The result of the division is:

The first part of the quotient is:

First partial remainder is:

Others easily by the quotient are:

Other partial remainders are:

When the first symbol appears at the system input, the preceding partial residues are zero. LaZ247be this first symbol. Circuit 2 stores z 247 temporarily, while circuit 3 gives the result of multiplying z 247 by each of the terms of the generator polynomial. The partial residues are stored in circuit 1 in a sequence that is characteristic of the system.

When the second symbol ' z- 2^ arrives at the input of the system, it is added modulo-2 to the preceding partial remainder of the highest degree. The result of this is stored in 2. Circuit 3 then performs the multiplications with the preceding partial remainders and the process continues, until the 247th symbol is introduced into the system.

Circuit 1 is a direct storage device for k words of p bits. Circuits 2 and 3 are storage units for p bits.

Circuit 4 is a modulo-2 adder for p bits.

As for circuit 5, this consists of an immutable table, which when addressed with (S^+ Rp^) 1 respectively gives the products of (S.^+ Rpi^ and each of the coefficients in G(x) ,

where S. is the information symbol of order i and R . like that

1 pi

partial remainder of order i which has the same degree as S^.

When all information symbols forming I(x) have been entered into the system, circuit 1 contains the 8 control symbols, arranged in a certain order. These symbols only need to be aligned behind x I(x) to complete the codeword's information.

2-DECODING

The method of decoding which is an embodiment of the invention comprises a single calculation system: - the error syndromes; - the coefficient of the mislocalizing polynomial; - the roots of the error-localizing polynomial; - the error diagrams corresponding to the calculated error position;

- the corrections.

CALCULATION REGARDING THE CORRECTION OF FOUR ERRORS

CALCULATION OF THE SYNDROMES

Since V(x) is a code word, if it is wrong it can be written as:

where E(x) is the error design that occurred during transmission.

In order to register the errors on reception, it is necessary either to check whether the received words are or are not divisible by the generator polynomial, or to check that each code word accepts the generator polynomial roots as roots. Use is made of the second solution for decoding as in the present invention.

A code word V(x) is written in polynomial form as follows, as previously shown:

If V(x) has a^ as a root, this is expressed by: If there is an error, the code word V(a^) is no longer received, but instead the code word

since V (a-*) = 0.

Sj is the failure syndrome of order j, the syndromes S_. must be calculated before it is possible to determine the position and value of the faults.

If an erroneous word is received, then there is a particular form of error E (x). , which can be defined with two parameters i' Y± (position and value).

CALCULATION OF THE COEFFICIENTS IN THE ERROR-LOCALIZING POLYNOMIAL USING THE SYNDROMES.

To correct t errors, the error-locating polynomial is written:

The coefficients o^,O2, .... o^_ are obtained by solving the following system:

Let A be the main determinant in the system; it is similar to:

By applying the rules for solving linear equations, the result is that o1= A]_ A, where

The coefficient of the error-localizing polynomial therefore has the following respective values:

CALCULATION OF THE ERROR-LOCALIZING POLYNOMIAL ROOTS

As equation (3) can only be solved if it is of the fourth degree in height, the system can correct up to four errors. The position of the four faults is therefore the solution of:

This equation can also be expressed in biquadratic form: with:

To locate errors, it is sufficient to determine the values of A, A<*>, u OYU<*> and then the roots of each of the quadratic equations. To solve the system (6), one will encounter two cases, depending on whether o1 is zero or not.

When o-^= 0, system (6) becomes :

This is a third degree equation in A and gives a root A-^. The quantities u and u' are solutions of a second degree equation; provided that: U and u' are the roots of

For o^= 0 by setting:

This results in a third degree equation for p, i.e.:

A root p^f. e.g., can be extracted from this equation, from which X and A<1> are solutions of a quadratic equation, i.e.

System (6) thus makes it possible to derive the values of u and u'.

SOLUTION OF A TERMINAL EQUATION LIKE (8) OR (11)

These two equations have the form:

This equation can be expressed in canonical form (with the y-coefficient equal to the number one) by putting: which gives

If p is even, two cases arise to find a cube root in the field GF(2<P>).

(1) If u = 0, equation (13) becomes:

Then: y-i 0<3Y2 are therefore solutions of

This equation can be expressed in canonical form as follows:

where Y = Y/ Y21 R = x/ y2= 1

(2) If u = 0, equation (14) must be solved, z., obtained by means of a table addressed by Q. The roots z^og are obtained by the use of a method identical with that just stated for u = 0 and R ^ 1.

Figure 3 depicts the decode algorithm.

The number of errors taken for correction is four, three or two.

Phase 101 represents the calculation of the syndromes which in the present case will amount to 8, S 7 to SQ. Phase 102 represents the calculation of (A) ^, (A) ^, (A)2f the first determinant in the case of 4, 3 and 2 errors, as well as the calculation of A^, where i varies from 1 to 4, i.e. A = A-^ ,<A>2, A^, A^.

If (A^) deviates from zero (phase 103), it is deduced that there are four errors, and this leads on to phase 104, where o^, , o^, o, defined by equations (4) are calculated.

If o, = 0 (phase 105), this leads to phase 106 for calculating the roots of the equation in p (equation (11)), then to phase 107 for calculating the roots A, A' in equation (12) and finally to phase 108 for calculation of u and y.' by the equations (6) .

Then follows the solution of equation 5 (phase 109), which gives X, X2, X^, X^ and the error address is derived from formula (17). Finally

in phase 110, Y1 and Y2 are calculated using formula (18).

If (phase 105) o-^= 0, phases 106-108 are replaced by phases 111-112, which correspond respectively to solving the equation in x 3 (equation (8)) and solving the equation in u 2 (equation (9).

The algorithm in fig. 3 further represents the decoding phase in case of correction of three and two errors. In these two cases, equation (3') becomes:

- in case of three errors

Equation (3") can be expressed in canonical form and one of the roots is obtained by Cardan's formula (phase (206)). The other two roots are obtained by solving the quadratic equation for X (phase 207).

In fig. 3 it is possible to see the equivalence between the phases which have the numbers 1, 2, 3, 4 for hundreds and the same number for ones and tens.

In all cases, apart from the value of the coefficients, the problem is reduced to the solution of a cubic equation or a quadratic equation in canonical form.

The effective position of the faults is determined as follows:

Provided by X^is of the form X^ = a-<11>(where a-<*1>is an elementGF(2<P>)), j^characterizes the error position, as

The determination of X^ then makes it possible to calculate the corresponding fault diagrams y.^:

- . — ... f Thus:

Reference is made to fig. 2. As the symbols arrive, the decoder calculates Sj as in equation (2) for a given value of j. This operation is performed as many times as G(x) has roots.

For a symbol of order ^, circuit 11 calculates:

This result is then temporarily stored in circuit 12.

The decoder calls up the sum of the (n-£) previous terms, which are stored in circuit 10, since circuit 11 is transparent. Circuit 13 performs the summation:

The calculation of this operation passes via storage unit 14 and circuit 15 which is transparent to be stored in circuit 10, until the arrival of the next symbol; the operation thus described is repeated until the last symbol has arrived. The various syndromes stored in circuit 10.

The decoder is made up of three storage units:

- circuit 10 which is a direct storage for u words of p bits, where u is a characteristic of the system,

- circuits 12 and 14 which are storage units for p bits.

A circuit 13, which during calculation of the syndromes acts as a modulo-2 adder.

A circuit 11 which is a table, where a reserved area multiplies the symbol arriving at its input by the roots of the generator polynomial in a sequence defined in advance by the system.

A circuit 15, which is a table, where a transparent area is utilized during this operation.

The operations required for calculating the different determinants are multiplication and modulo-2 addition.

The multiplication of two elements in the Galois field GF (a<p>) is replaced by modulo (2P<->1) addition of the base a logarithm of these two numbers, where a is a primitive element in the field GF (a<p>).

MULTIPLICATION CASE

The value of a syndrome stored in circuit 10 flows through circuit 11, which gives its logarithm. This result is stored in circuit 12. When using the same process, e.g. the logarithm of another syndrome calculated. At this point, the outputs from circuits 11 and 12 are fed to circuit 13, which in this particular case acts as a modulo (2P<->1) adder. The result of adding these two logarithms is stored in circuit 14. At this moment, circuit 15 outputs the antilogarithm of the result from circuit 14, a result which takes its place in a reserved area of circuit 10.

ADDITION CASE

In this case, circuits 11 and 15 are transparent and circuit 13 functions as a modulo-2 adder.

The coefficients o^, O2.

Example

Assume that:

is the characteristic polynomial that can be expressed in terms of

a code generator polynomial:

As shown, the generator polynomial must have a number of roots twice the number of errors to be corrected, and since there are eight roots in this case, four errors can be corrected. There are thus eight syndromes Sq to S^

and these syndromes are calculated by successively replacing a-'

2 3 4 5 6 7

with 1,a,a,a,a,a,a,a and by setting n-1 to 255.

It is assumed that the syndromes have the following values:

S0 a<3>

.S1 = ab

S2 = a7

a<9>

a 11

So"

S„ a15

8<*>a"

It is further assumed that there is an error in position a 2 and with the value a 3 , where a 2 and a 3 are elements in the Gallois field GF (28).

First determinant A which makes it possible to solve the unknowns o-^to o^ (4th order determinant for four errors) is written:

This determinant is zero. There are thus a maximum of three errors. The first determinant is then designed.

This is zero. There are thus a maximum of two errors. The first determinant is then designed.

This determinant is zero. There is thus only one error. The following is then designed:

and the determinant appears by: From equation 4, this results in Equation (3<1>) simplifies to

2

where X = o^= a

which confirms the assumption made as to the position of the fault.

The corrected error is the quantity Y-^ which is calculated using equation (2). It provides:

Claims (9)

1. Method for decoding data encoded in a Reed-Solomon code with error correction, where the code words are represented by symbols formed by bits and which form a polynomial of (n-1)th degree consisting of m information symbols and k control symbols with m + k = n-1, where the control symbols are words with 2P bits and said words form the elements of a limited Gallois field GF (2 <P> ), characterized in that it includes the following steps: - division of a bit packet to be coded with a code-generator polynomial of order k, so that the quotient of the division as a result gives the m information symbols and the remainder from the division gives the k control symbols; - calculation of the syndromes of the polynomial representing a code word for certain roots of the code-generator polynomial, which syndromes in height are eight in number and are in relation to two systems of four linear equations, whose coefficients are the error locations and error values in the code word ; - formation of the determinant A(4) and calculation of the value of said determinant which can be zero or non-zero; - if the A(4) value is zero, formation of the determinant A(3) of a three-equation system included in said four-equation system and calculation of the value of the determinant A(3), which may or may not be zero- zero; - if the A(3) value is zero, forming the determinant A(2) of a two-equation system included in said three-equation system and calculating the value of the determinant A(2) which can be zero or non-zero; - if (2) the value is zero, forming the determinant a(1) of a single equation included in said two-equation system and calculating the value of the determinant ^ (1) which may be zero or non-zero; where the number of errors is 4, 3, 2 or 1, depending on whether the determinants A(4), A(3), <A> (2) or ^(1) are zero; and where correction is formed for the error or errors at the locations formed by solving a system of equations that gives the values of the syndrome at the said locations. 2. System for Reed-Solomon coding which makes it possible to calculate the control symbols to be added to the information symbols, characterized in that said system comprises a table (5), three storage units (1, 2, 3) and a modulo-2 adder ( 4), which together make it possible to perform multiplications on one side and to add identical modulo 2 terms ("modulo 2 terms of identical") and store it in a unit (1), as can be recognized at each step of the division on the other hand, where said coding system makes it possible to calculate the control symbols of the Reed-Solomon code, where the symbols are in a limited field GF (2 <P> ), where p has any value. 3. System for calculating error syndromes in a Reed-Solomon code, which makes it possible to calculate k error syndromes, characterized in that said system comprises three storage units (10, 12, 14), one of which is a direct storage unit (10) for u words of p bits, where u is a characteristic of the system, and the other two (12 and 14) are storage units for p binary elements, a circuit (13) which during calculation of the syndromes acts as a modulo-2 adder, a circuit (11) which is a table, where a reserved area multiplies the symbol at the input thereof by the roots of the generator polynomial in an order defined in advance by the system, and a circuit (15), which is a table whose transparent area used during this operation. 4. System as stated in claim 2, which further makes it possible to calculate the t coefficients of p bits in the error-locating polynomial, characterized in that a circuit (16) successively tests the value of the determinants (A)^ , (A) 3, (A)2 ... (A)^ , until the point where it finds that (A)^ = 0, and at which point circuit (16), depending on the value of i, issues a message indicating the errors observed on the one hand and on the other hand prepare the system for calculating the coefficient o^ which corresponds to the number of errors to be corrected. 5. System as stated in claims 2 and 3, characterized in that the circuit (10) registers the type of operation to be performed in order to inform the circuit (13) about this, which, depending on the case, assumes a position of modulo 2 or module (2P ) adder, and where the circuits (11) and (15) are tables where certain areas respectively give Log (a <1> ) and Log — i(a1) , where a <1> is an element of GF (2 < P> ) and where the system further, by means of circuit (16), has a detector for blocked modes of operation, such as Log 3.(0), as the system allows the calculation o-^ to o^ to be carried out. 6. System as specified in claims 2, 3 and 4, characterized in that circuit (16) after successive tests makes it possible to determine the number of errors that occur and where the system calculates the positions in the case of four errors, based on a third-degree equation expressed in canonical form, and where the circuit (15) is furthermore such that it registers the case where the third degree equation has no solution in order to adapt the procedure for continuing the calculations. 7. System as stated in claims 2, 3, 4 and 5, characterized in that the circuit (15) is an unchanging table, certain areas of which form the roots of a third- and second-degree equation reduced to canonical form. 8. System as stated in claims 2-6, characterized in that the AND operation of the circuits (15) and (16) prevents the addition of several errors when more than four errors occur. 9. System as stated in claims 2-7, characterized in that the circuit (10), based on the information stored in it, makes it possible to correct the erroneous symbols in the positions determined by calculation.