JPH0746777B2 - Code error correction circuit - Google Patents

Description

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a code error correction circuit for correcting a t-fold word error, and more particularly to a code error for correcting a random t-double word error at a high speed with a simple circuit configuration. It relates to a correction circuit.

[Prior art]

Conventionally, in order to improve data reliability in a file device such as a magnetic file, a Reed-Solomon code for correcting a single byte error, an adjacent error correction code, etc. are often used.

Further, when using a medium (optical disk or the like) having an error rate lower than that of the magnetic medium, or when it is desired to further improve the data reliability, the Reed-Solomon code having the ability to correct a random double-byte error is used. Has been.

If the redundancy is limited, the extended Reed-Solomon code is used to increase the number of information points. Or Is used.

However, one of the drawbacks of the above code is that the correction operation is not performed uniformly using the error locator polynomial due to the increase in the number of information points.

Now, as a check matrix on GF (2 ⁴ ), a code having the check matrix of the formula (1A) or the formula (1B) will be described as an example (m = 4).

In the conventional example, when generating syndromes S ₀ to S ₃ corresponding to the above formula, by determining the syndromes S ₀ to S _3, the correction operation was necessary to change as follows.

(I) S ₀ = S ₁ = S ₂ = S ₃ = 0 → no error (II) S ₀ ≠ 0, S _i = S ₂ = S ₃ = 0 → i = 15 single error e ₁₅ = S
₀ (III) S ₀ = 0, S ₁ ≠ 0, S ₂ ≠ 0, S ₃ ≠ 0 → S ₁ · S ₃ = ▲ S ² ₂ ▼ If i = 15, double error α ^j = S ₂ / S ₁ , e _j = ▲ S ² ₁ ▼ / S ₂ e ₁₅ = S ₀ + e _j (IV) S ₀ ≠ 0, S ₁ ≠ 0, S ₂ ≠ 0, S ₃ ≠ 0 → S ₀・If S ₂ = S ₁ · S ₂ , single error of i ≠ 15 α ⁱ = S ₁ / S ₀ , e _j = S ₀ S ₁ · S ₃ = ▲ S ² ₂ ▼, i = 15 Double error included α ⁱ = S ₂ / S ₁ , e _j = ▲ S ² ₁ ▼ / S ₂ , e ₁₅ = S ₀ + e _{j In} other cases σ (X) = (▲ S ² ₂ ▼ + S ₁ · S ₃ ) X ² + (S ₁ / S ₂ + S ₀ /
S ₃ ) X + ▲ S ² ₁ ▼ ＋ S ₀・ If the solution of S ₂ is found Double error is not correctable except for the above. FIG. 1 shows a block diagram of an error correction circuit based on the above correction principle. The syndrome determination unit 23 determines the syndrome generated by the illustrated syndrome generation unit 22, and the following processing is performed.

When it is determined to be (I): Block 0 is selected.

When it is determined to be (II): S ₀ is fetched by the block 1 and e ₁₅ = S ₀ is output at the i = 15th word.

When it is determined to be (III): S _{0 to} S ₃ by block 2
Is taken in, and e _j is output in the _jth word and e ₁₅ is output in the 15th word.

When it is determined to be (IV): S _{0 to} S ₃ are fetched by the block 3 and the operations shown in the above-mentioned are performed.

Therefore, in the conventional example, since the correction operation differs depending on the cases of (I) to (IV), the circuits shown in blocks 0 to 3 are separately required, and the correction operation cannot be uniformly executed. Therefore, there is a drawback that the circuit configuration increases.

〔Purpose〕

In view of the above points, an object of the present invention is to provide a code error correction circuit in which necessary circuit configurations are integrated to perform unified t-word error correction processing.

In order to achieve such an object, in the present invention, in a code error correction circuit capable of receiving an N-element extended Reed-Solomon code of code length N and correcting a t-fold error, a received word W _j (j =
0,1, ..., N-1) sequentially input from high to, alpha respectively stored contents 2t pieces of memory section ⁱ times (i = 0,1, ..., 2t -1.α
Is a primitive element of Galois field GF (2 ^m )) and is stored again to generate 2t syndromes.
The received word W _j (j = N−1) is input only to the storage unit for i = 0 and is not input to the other storage units, and the control unit for controlling and the syndrome generated by the generation unit. By the process of repeatedly multiplying each S _i (i = 0,1, ..., 2t−1) by α ⁱ N times, the syndrome S _i ^(k) = S
_i (α ⁱ ) ^k (k = 0, 1, ..., N−1) is sequentially calculated, and a sum S _i ^{(of the} syndromes S _i ^{(k) is} sequentially calculated by the first calculation means. ^k) + S _{i + 1} ^(k) (i = 0,1, ..., 2t
-2) in n + 1 row and i-n + 1 column (0≤n, i-n≤t-
1) the second computing means for sequentially computing the determinant Δ ^(k) of the t-th order square matrix, and the syndrome S _i ^(k) (i = 0,1 ⁾ sequentially obtained by the first computing means. , ..., 2t−
Third calculation means for calculating an error pattern e _Nk-1 when an error occurs in the received word W _Nk-1 using the value of 1), and the determinant Δ sequentially calculated by the second calculation means. Determination means for determining whether or not the value is 0 for each of ^(k) ,
When the determination means determines that the value of the determinant Δ ^(k) is 0, the calculated error correction pattern e _Nk-1
By having a correction means for correcting the received word W _{Nk-1 according} to the above, the received words other than the received word W _N-1 are corrected and output.

For example, a parity check matrix of a double word error correction code formed by using a primitive element α of a Galois field GF (2 ^m ) defined by an arbitrary integer m In the double word error correction circuit that encodes and decodes data according to the above, the encoded data is received and the syndrome S _i corresponding to the check matrix is received from the received data word.
A syndrome generation circuit for generating (i = 0 ... 3) and S ₀ S ₁ , S _i S ₂ which are exclusive ORs between the syndromes.
And a circuit for calculating S ₂ S ₃ and a determinant for S ₀ S ₁ , S ₁ S ₂ and S ₂ S ₃ which are the exclusive ORs. And a logic circuit for calculating Δ = 0 and detecting the position of the error word and the error pattern.

Hereinafter, the present invention will be described in detail with reference to the drawings.

〔Example〕

FIG. 2 is a block diagram showing an embodiment of the present invention. In this embodiment, the Galois field GF (2 ⁴ ) will be described as an example.

In FIG. 2, 1 to 3 are circuits for multiplying α, α ² and α ³ of elements of Galois field GF (2 ^m ), respectively, and GF (2 ⁴ )
In the case of, the α multiplication principle shown in FIG.
Α ² multiplication principle shown in FIG. 3B, α ³ shown in FIG. 3C
It can be achieved by the multiplication principle.

Each of 4 to 7 is a 4-bit register (syndrome register).

Reference numerals 8 to 15 are 4-bit exclusive OR circuits.

Here, the exclusive OR circuit 8 and the syndrome register 4 form a circuit for generating the syndrome S ₀ . Further, the exclusive OR circuit 9, the register 5, and the α multiplication circuit 1 constitute a circuit for generating the syndrome S ₁ . Similarly, the exclusive OR circuit 10, the register 6 and the α ² multiplication circuit 2 constitute a syndrome S ₂ generation circuit, and the exclusive OR circuit 11, the register 7 and the α ³ multiplication circuit 3 form the syndrome S ₃ To form a generation circuit of.

Let W be a codeword (each received word consists of 4 bits), and let W = [W ₀ , W ₁ , W ₂ ..., W ₁₅ ] E be an error, then E = [0, 0, ..., e _i ... e _j , 0,0] The received word can be expressed as = W + E by performing an exclusive OR operation.

Therefore, when generating syndromes S ₀ to S ₃ corresponding to the formula (1), by ^{S = H · T = H ·} E T, syndromes S ₀ to S _3, respectively, Must be generated.

To operate this embodiment, first switch 16 is closed, the received word is input to signal line a, and the shift clock is applied to signal line b. However, since the switch 17 is opened by the control signal from the signal line c in the 15th word, it is not input to the syndromes S ₁ , S ₂ , and S ₃ generation circuits, and at the end of input of the received word, the equation (2) The syndromes S _{0 to} S ₃ shown are generated.

Next, when the switch 16 is opened and the shift clock is continuously applied to the signal line b, the syndromes S _{0 to} S ₃ after shifting k times are represented by the following equations.

The exclusive ORs A ₀ , A ₁ , and A ₂ between the syndromes are taken by the exclusive OR circuits 12 to 14 and are expressed by the following equation.

Here, if L = A ₀ · A ₂ + ▲ A ² ₁ ▼ is defined, L = e _i · e _j (1 + α ^{i + k} ) (1 + α ^{j + k} ) (α
^{2 (i + k)} + α ^{2 (j + k)} ) However, when j = 15, α ^j = 0. Therefore, from L = e _i · e ₁₅ (1 + e _{i + k} ) e _{2 (i + k)} , k = − L only when i or k = -j (j ≠ 15)
= 0.

When k = -15, L ≠ 0, but since the 15th word is a parity word, it is not necessary to correct it in practice.

The pattern is calculated by the following equation.

e = S ₀ + ▲ A ² ₀ ▼ / (A ₀ + A ₁ ) because e = S ₀ + ▲ A ² ₀ ▼ / (A ₀ + A ₁ ) When k = −i, (1 + α ^{i + k} ) = 0, so e = (e _i + e _j ) + e _j = e _i If e _j = 0 in the case of a single error, Reference numeral 18 is a circuit for calculating L from A ₀ , A ₁ , and A ₂ described above, and RO
It can be configured by M.

Reference numeral 19 is a circuit for calculating e from S ₀ , A ₀ , A ₁ and can be constituted by a ROM.

Reference numeral 20 is a gate that outputs e when L is 0, and can be composed of a NAND circuit.

Reference numeral 21 is a buffer memory for storing received words.

When the input of the received word to the buffer memory 21 is completed, the syndromes S _{0 to} S ₃ are generated in the registers 4 to 7, after which the switch 16 is opened and the shift registers S ₀ to S ₃ are synchronized with the signal line b.
When S ₃ is circulated and data is output from the buffer memory 21, L = 0 at the i-th clock according to the above principle, and the error pattern e _i is output from the gate. Further, since _i is output from the buffer memory, the exclusive OR operation of both outputs is performed by the exclusive OR circuit 15,
The error is corrected. The same applies to j.

In the embodiment shown in FIG. 2, by opening / closing the switch 16, the syndrome generation unit and each syndrome are changed to S _i → S _i α ⁱ → S _i α ²ⁱ → ... → S _i (α _i ) ^k ( i = 0,1,2,3), but it is shared with
As shown in FIG. 4, the syndrome generation unit and the syndrome conversion unit can be separated.

As described above, by adopting the configuration shown in FIG. 4, it is not necessary to open the switch 16 and idle feed the received word after the syndrome is generated. Therefore, even when the code blocks are continuously transmitted, Processing becomes possible.

〔effect〕

As described above, according to the present invention, since it becomes possible to uniformly process a code that has not been conventionally subjected to a unified process, it is possible to reduce the hardware of the error correction circuit. A special effect can be obtained.

In particular, the present invention can be applied to a wide range of digital technical fields such as communication systems including space communication and digital image processing devices.

BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a diagram for explaining a conventional technique, FIG. 2 is a block diagram of an error correction circuit which is an embodiment of the present invention and is adapted to perform unified processing, and FIG. A) to (C) are conceptual diagrams for explaining the principle of multiplication, and FIG. 4 is a block diagram of an error correction circuit which is another embodiment of the present invention and performs unified processing in real time. 1 ... α multiplication circuit, 2 ... α ² multiplication circuit, 3 ... α ³ multiplication circuit, 4-7 ... m-bit register (syndrome register), 8-15 ... Exclusive OR circuit, 16, 17 ... Switch, 16, 19 ... ROM, 20 ... Gate circuit, 21 ... Buffer memory, 22 ... Syndrome generating section, 23 ... Syndrome determining section.

Claims (2)

[Claims] 1. A code error correction circuit capable of receiving an N-element extended Reed-Solomon code having a code length N and correcting a t-fold error, in a received word W _j (j = 0, 1, ..., N-1). ) Are sequentially input from the highest order, and stored in 2t storage units by α ⁱ times (i = 0,
1, ..., 2t-1. α is a primitive element of the Galois field GF (2 ^m ) and is stored again to generate 2t syndromes. For the received word W _j (j = N−1), i = Control means for controlling input to only the storage unit for 0 and not inputting to the other storage unit, and the syndrome S _i (i
= 0,1, ..., 2t−1) is repeatedly multiplied by α ⁱ N times, the syndrome S _i ^(k) = S _i (α ⁱ ) ^k (k =
0, 1 ..., N-1) sequentially calculating first calculating means, and the syndrome sequentially calculated by the first calculating means
S _i ^(k) sum between ^{_{S i (k) + S i}} + 1 (k) (i = 0,1, ..., 2t-2) (n + 1) row i-n + 1 column (0 ≦ n, i-n ≦ t −1) second arithmetic means for sequentially calculating the determinant Δ ^(k) of a t-th order square matrix, and the syndrome S _i ^(k) (i = 0, 0 ⁾ sequentially obtained by the first arithmetic means. 1, ..., 2t−1), the received word W
A third calculating means for calculating an error pattern e _nk-1 in the case of error _Nk-1 occurs, the determinant which are sequentially calculated by the second arithmetic means Δ
^For each of ^(k) , a discriminating means for discriminating whether the value is 0 or not, and the error pattern e _Nk calculated when the discriminant Δ ^(k) is discriminated as 0 by the discriminating means. A code error correction circuit characterized by having a correcting means for correcting the received word W _Nk-1 by _-1 , and correcting and outputting the received words other than the received word W _N-1 . 2. The generating means and the first computing means are independent circuit configurations, and while the first computing means computes the syndrome of the preceding code block, the generating means generates the syndrome of the subsequent code block. The code error correction circuit according to claim 1, wherein the code error correction circuit is capable of generation.