JPS6246893B2 - - Google Patents

Description

[Detailed description of the invention]

The present invention relates to an error correction method using an error correction code (a type of adjacent code) capable of correcting up to two-word errors in one block, and is particularly designed to enable high-speed error correction. First, the error correction code used in the present invention will be explained. When describing an error correction code, a vector representation or a cyclic group representation is used. First, consider an irreducible m-th degree polynomial F _(x) on GF(2). On the field GF(2) where only elements "0" and "1" exist, the irreducible polynomial F _(x) has no roots.
Therefore, consider a virtual root α that satisfies (F _(x) = 0). At this time, there are 2 ^m different elements 0, α, α ² , α ³ , etc. expressed as powers of α including zero elements.
...α ^m-1 constitutes an extended field GF(2 ^m ). GF
(2 ^m ) is a polynomial ring modulo the m-th order irreducible polynomial F _(x) over GF(2). The elements of GF(2 ^m ) are 1,
α={x}, α ² = {x ² }, ..., α ^m-1 = {x ^m-1 }
It can be expressed as a linear combination of . That is, a ₀ +a ₁ {x}+a ₂ {x ² }+...+a _n-1 {x ^m-1 } = a ₀ +a ₁ α+a ₂ α ² +......+a _n-1 α ^m-1 or ( a _n-1 , a _n-2 , ..., a ₂ , a ₁ , a ₀ ) Here, a ₀ , a ₁ , ..., a _n-1 ∈GF _(P) . As an example, considering GF(2 ⁸ ), (mod.F _(x)
= x ⁸ + x ⁴ + x ³ + x ² + 1), and all 8-bit data is a ₇ x ⁷ + a ₆ x ⁶ + a ₅ x ⁵ + a ₄ x ⁴ + a ₃ x ₃ + a ₂ x ² + a ₁ x + a ₀
Alternatively, it can be written as (a ₇ , a ₆ , a ₅ , a ₃ , a ₂ , a ₁ , a ₀ ), so for example, a ₇ is assigned to the MSB side and a ₀ to the LSB side. Since a _o belongs to GF(2), it is 0 or 1. Further, the following (m×m) matrix T is derived from the polynomial F _(x) . Another representation uses cyclic groups. This uses the fact that the 0 element is removed from GF(2 ^m ) and the remaining elements form a multiplicative group of order 2 ^m −1. Expressing the elements of GF (2 ^m ) using a cyclic group is 0, 1 (=α ^2m-1 ), α, α ² , α ³ , ... α ²
It becomes ^m-2 . Now, in one example of the present invention, when m bits are one word and n words constitute one block, k check words are generated based on the parity check matrix H below. Furthermore, the parity check matrix H can be similarly expressed by the matrix T. However, I is a (m×m) unit matrix. As mentioned above, the expression using the root α and the generation matrix T
Both expressions are essentially the same. Furthermore, taking the case of using four (k=4) check words as an example, the parity check matrix H is becomes. One block of received data is expressed as a column vector V
= (W _o-1 , W _o-2 , ..., W ₁ , W ₀ ) (where Wi = Wi
+eiei: error pattern), the four syndromes S ₀ , S ₁ , S ₂ , S ₃ that occur on the receiving side are becomes. This error correction code is capable of correcting up to 2 word errors within one error correction block, and is capable of correcting 3 word errors or 4 word errors when the error location is known. 4 check words in 1 block (p=
W ₃ , q=W ₂ , r=W ₁ , s=W ₀ ). This check word is obtained as follows. However, Σ is

It means [formula]. p+q+r+s=ΣWi=a α ³ p+α ² q+αr+s=Σα ⁱ Wi=b α ⁶ p+α ⁴ q+α ² r+s=Σα ²ⁱ Wi=c α ⁹ p+α ⁶ q+α ³ r+s=Σα ³ⁱ Wi=d Omit the calculation process and only the result If you show becomes. In this way, check words p, q,
The role of the encoder provided on the transmitting side is to form r and s. Next, a basic algorithm for error correction when data containing check words formed as described above is transmitted and received will be described. [1] When there is no error: S ₀ = S ₁ = S ₂ = S ₃ = 0 [2] When there is a 1-word error (error pattern is ei): S ₀ = ei S ₁ = α ⁱ ei S ₂ ＝α ²ⁱ ei S ₃
= α ³ⁱ ei Therefore, α ⁱ S ₀ = S ₁ α ⁱ S ₁ = S ₂ α ⁱ S ₂ = S ₃ , and when i is changed sequentially, a one-word error will occur depending on whether the above relationship holds. It can be determined whether Alternatively, S ₀ /S ₁ =S ₂ /S ₁ =S ₃ /S ₂ =α ⁱ , and the error location i can be found by comparing the pattern of α ⁱ with that previously stored in the ROM. At that time, syndrome S ₀ is the error pattern
It becomes ei itself. [3] In the case of 2-word error (ei, ej) S ₀ = ei + ej S ₁ = α ⁱ ei + α ^j ej S ₂ = α ²ⁱ ei + α ^2j ej S ₃ = α ³ⁱ ei + α ^3j ej Transforming the above equation, α ^j S ₀ +S ₁ = (α ⁱ + α ^j )ei α ^j S ₁ +S ₂ = α ⁱ + (α ⁱ + α ^j )ei α ^j S ₂ +S ₃ = α ²ⁱ (α ⁱ + α ^j )ei Therefore α ⁱ (α If ^j S ₀ + S ₁ )=α ^j S ₁ +S ₂ α ⁱ (α ^j S ₁ +S ₂ )=α ^j S ₂ +S ₃ holds, it is determined that there is a 2-word error, and the error locations i and j can be found. . That is, by changing the combination of i and j, it is examined whether the relationship in the above equation holds true. The error pattern at that time is ei=S ₀ +α ^−j S ₁ /1+α ^i−j ej=S ₀ +
α ⁻ⁱ S ₁ /1 + α ^j−i [4] In the case of 3-word error (ei, ej, ek) S ₀ = ei + ej + ek S ₁ = α ⁱ ei + α ^j ei + α ^k ek S ₂ = α ²ⁱ ei + α ^2j ej + α ^2k ek S ₃ = α ³ⁱ ei + α ^3j ej + α ^3k ek Transforming the above equation, α ^k S ₀ + S ₁ = (α ⁱ + α ^k ) ei + (α ^j + α ^k ) ej α ^k S ₁ + S ₂ = α ⁱ (α _i + α ^k ) ei + α ^j (α ^j + α ^k ) ej α ^k S ₂ + S ₃ = α _2i (α ⁱ + α ^k ) ei + α ^2j (α ^j + α ^k ) ej Therefore α ^j (α ^k S ₀ + S ₁ ) + (α ^k S ₁ + S ₂ ) = (α ⁱ + α ^j ) (α ⁱ + α ^k ) ei α ^j (α ^k S ₁ + S ₂ ) + (α ^k S ₂ + S ₃ ) = α ⁱ (α ⁱ + α ^j ) (α ⁱ + α ^k ) ei From the above formula, α ⁱ (α ^j (α ^k S ₀ + S ₁ ) + (α ^k S ₁ + S ₂ )) = α ^j (α ^k S ₁ + S ₂ ) + (α ^k S ₂ + S ₃ ) If this holds true, it can be determined that there is a 3-word error. However, the condition is that (S ₀ ≠0, S ₁ ≠0, S ₂ ≠0). Each error pattern at that time is ei=S ₀ + (α ^−j +α ^−k )S ₁ +α ^−j+k S
₂ /(1+α ^i-j )(1+α ^i-k ) ej=S ₀ +(α ^-k +α ^-i )S ₁ +α ^-k-i S
₂ /(1+α ^j−i )(1+α ^j−k ) ek=S ₀ +(α ⁻ⁱ +α ^−j )S ₁ +α ^−i−j S
₂ /(1+αk ^-i )(1+αk ^-j ). In reality, the configuration for correcting a 3-word error becomes complicated, and the time required for the correction operation also increases. Therefore, by using the pointer, i, j・
In combination with the case where the error location of k is known, it is practical to use the above equation for checking at that time and perform the error correction operation. [5] In case of 4-word error (ei, ej, ek, el): S ₀ = ei + ej + ek + el S ₁ = α ⁱ ei + α ^j ej + α ^k ek + α ^l el S ₂ = α ²ⁱ ei + α ^2j ej + α ^2k ek + α ^2l el S ₃ = α ³ⁱ ei+α ^3j ej+α ^3k ek+α ^3l el Transforming the above equation, ei=S ₀ + (α ^−j +α ^−k +α ^−l )S ₁ +(α ^−j−k +α ^−k−l +α ^−l−j )S ₂ +α ^−j−k−l
S ₃ /(1+α ^i-j )(1+α ^i-k )(1+α ^i-l ) ej=S ₀ +(α ^−k +α ^−l +α ⁻ⁱ )S ₁ +(α ^−k−l +α ^{−l− i} +α ^−i−k )S ₂ +α ^−k−l−i
S ₃ /(1+α ^j−i )(1+α ^j−k )(1+α ^j−l ) ek=S ₀ +(α ^−l +α ⁻ⁱ +α ^−j )S ₁ +(α ^−l−i +α ^{−i− j} +α ^−j−l )S ₂ +α ^−l−i−j
S ₃ /(1+α ^k−i )(1+α ^k−j )(1+α ^k−l ) el=S ₀ +(α ⁻ⁱ +α ^−j +α _−k )S ₁ +(α ^−i−j +α ^{−j− k} +α ^−k−i )S ₂ +α ^−i−j−k
S ₃ /(1+α ^l-i )(1+α ^l-j )(1+α ^l-k ) The error location (i,
j, k, l) is known, error correction can be performed by the above-mentioned calculation. The basic error correction algorithm described above uses syndromes S ₀ to _{S 3} to check for errors in the first step, check to see if there is a 1-word error in the second step, and check to see if there is a 2-word error in the third step. When trying to correct even a 2-word error, it takes a long time to complete all the steps, and this problem especially occurs when determining the error location of a 2-word error. arise. The present invention aims to solve these problems and propose an error correction method that can perform high-speed error correction operations. The present invention will be explained below. Syndromes S ₀ , S ₁ ,
The equations related to S ₂ and S ₃ are similar to the above, S ₀ = ei + ej S ₁ = α ⁱ ei + α ^j ej S ₂ = α ²ⁱ ei + α ^2j ej S ₃ = α ³ⁱ ei + α ^3j ej Transforming this formula, (α ⁱ S ₀ + S ₁ ) (α ⁱ S ₂ + S ₃ ) = (α ⁱ S ₁ + S ₂ ) ^2Further transformation is performed to find the error location polynomial below. (S ₀ S ₂ + S ₁ ² ) α ²ⁱ + (S ₁ S ₂ + S ₀ S ₃ ) α ⁱ + (S ₁ S ₃ + S ₂ ² )=0 Here, the coefficient of each equation is S ₀ S ₂ + S ₁ ² = A S ₁ S ₂ + S ₀ S ₃ = B S ₁ S ₃ + S ₂ ² = C. By using the coefficients A, B, and C in the above equation, the error location in the case of a two-word error can be determined. [1] When there is no error: A=B=C=0, S ₀ =0, S ₃ =0 [2] When there is a 1-word error: A=B=C=0, S ₀ ≠0, S ₃ ≠ When it is 0, it is determined that there is a 1 word error. (α ⁱ =
The error location i can be found from (S ₁ /S ₀ ), and (ei
= S ₀ ) for error correction. [3] In the case of a 2-word error: In the case of an error of 2 or more words, (A≠0,
B≠0, C≠0) holds, and the determination becomes extremely simple. Also, at this time Aα ²ⁱ +Bα ⁱ +C=0
(However, i=0 to (n-1)) holds true. Here, if we set (B/A=D, C/A=E), then D=α ⁱ +α ^j and E=α ⁱ ·α ^j and α ²ⁱ +Dα ⁱ +E=0. Here, if the difference between the two error locations is t, that is, (j=i+t), then it is transformed as D=α ⁱ (1+α ^t ) and E=α ^2i+t . Therefore, D ² /E=(1+α ^t ) ² /α ^t = α ^−t +α ^t . The values of α ^-t and α ^t for each of (t=1 to (n-1)) are written in advance in the ROM,
t is determined by detecting a match between (α ^−t +α ^t ) determined from the output of the ROM and the value of (D ² /E) calculated from the received word. If this matching relationship does not hold, there is an error of three or more words.
Therefore, by setting X=1+α ^t Y=1+α ^−t =D ² /E+X, α ⁱ =D/X, α ^j =D/Y, and error locations i and j can be found. The error patterns ei and ej are calculated as ei=(α ^j S ₀ +S ₁ )/D=S ₀ /Y+S ₁ /D ej=(α ⁱ S ₀ +S ₁ )/D=S ₀ /X+S ₁ /D, Error correction can be performed. The figure shows an example of an error correction device to which the present invention is applied, in which received data is supplied to an input terminal indicated by 1, and is supplied to a buffer memory 2 and a syndrome generation circuit 3. The buffer memory 2 delays received data by the time required for error detection and error pattern generation, and the output of the buffer memory 2 is supplied to an error correction circuit (mod. 2 adder) 4. The output of this error correction circuit 4 is taken out to an output terminal 5. The syndrome generation circuit 3 calculates (H・V ^T ), and syndromes S ₀ to _{S 3} are formed.
This syndrome is applied to the arithmetic circuit 6 of GF (2 ^m ). This arithmetic circuit 6 has coefficients A, B, C,
Operations that generate D and E and operations that generate error patterns are performed. Coefficients from the arithmetic circuit 6 are stored in a buffer register 7, and error patterns are stored in a buffer register 8. Error correction is performed by supplying the error pattern from the buffer register 8 to the error correction circuit 4.
In addition, error location decoder 9 and ROM
10 are provided, and by using the coefficients D and E from the buffer register 7 and the outputs α ^t and α ^-t from the ROM 10, the error location i and the new coefficients X and Y are set to the error location. yon decoder 9. These new coefficients X, Y, the coefficient D from the buffer register 7, and the syndrome are supplied to the arithmetic circuit 6 to form error patterns ei, ej, and these error patterns are stored in the buffer register 8. It will be done. Furthermore, the syndromes S ₀ and S ₃ from the syndrome generation circuit 3 and the coefficient A from the buffer register 7,
B and C are supplied to the error determination circuit 11, which determines whether there is an error, whether it is a one-word error, whether it is a two-word error, or whether there are more errors. This determination result is given to the controller 12. The controller 12 supplies clock pulses or control signals defined in a predetermined timing relationship to each circuit. As understood from the above explanation, according to the present invention, the values of α ^-t and α ^t (t=1 to (n-1)) are stored in the ROM, and the output of this ROM and the syndrome By comparing both with the coefficients formed by calculation, two-word errors and error locations can be detected, so that error detection and error correction can be performed at high speed. At the same time, the configuration of the arithmetic circuit and other hardware in the error correction device can be simplified.

[Brief explanation of the drawing]

The figure is a block diagram of an example of an error correction device to which the present invention is applied. 1 is an input terminal, 4 is an error correction circuit, 5 is an output terminal, 6 is an arithmetic circuit, and 10 is a ROM.

Claims (1)

[Claims] 1 m bits constitutes one word of data, n words constitute one block, and parity check matrix H is used. or (However, α is a root that satisfies (F _(x) = 0) when F ( _x) is an irreducible polynomial on GF(2).) Using From one block V ^T and the above parity check matrix H, By calculating k syndromes S ₀ to _{S k-1}
In the error correction method using this syndrome, from the above syndrome S ₀ to _{S k-1} , A ₁ = S ₀ S ₂ + S ₁ ² B ₁ = S ₁ S ₂ + S ₀ S ₃ C ₁ = S ₁ S ₃ +S ₂ ² A ₂ =S ₁ S ₃ +S ₂ ² B ₂ =S ₂ S ₃ +S ₁ S ₄ C ₂ =S ₂ S ₄ +S ₃ ² 〓 A _k-3 =S _k-4 S _k-2 +S _k-3 ² B _k-3 = S _k-3 S _k-2 + S _k-4 S _k-1 C _k-3 = S _k-3 S _k-1 + S _k-2 ^By the calculation of 2, the coefficient It is characterized by consisting of a first step of calculating A, B, and C, and a second step of performing error detection and error correction shown in (a), (b), and (c) below using the syndrome and coefficients. error correction method. (a) (S ₀ = S ₃ = S ₄ ... = S _k-1 = 0, A ₁ = A ₂ =...
…=A _k-3 =0, B ₁ =B ₂ =…=B _k-3 =0, C _k
-3 = 0), it is detected that there is no error word. (b) (S ₀ ≠0, S ₃ ≠0, S ₄ ≠0, ..., S _k-1 ≠
0) (A(k)=0, B(k)=0, (however, (k)=1~k-
₃ ), C _k-3 =0), it is determined that a one-word error has occurred, and the error is corrected by calculating the syndrome described above. (c) When (A(k)≠0, B(k)≠0, C _k-3 ≠0), (B ₁ /A ₁ =B ₂ /A ₂ =...=B _k-3 /A _k-
3 =D) ( _C1 / _A1 = _C2 / _A2 =...=Ck _-3 / _Ak-
3 = E), the error location equation of (α ²ⁱ +Dα ⁱ +E=0) is solved, the error location (i, j) is detected, and the two-word error is corrected.