JPH0746776B2 - Error correction circuit - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to an error correction circuit adapted to correct a t-fold error by using a shortened Reed-Solomon code.

[Prior art]

Conventionally, in order to improve the data reliability of a filing device in a magnetic file or the like, a Reed-Solomon code or an adjacent error correction code that corrects a single-byte error is often used. In particular, when using a medium (optical disk or the like) having an error rate lower than that of a magnetic medium, or when it is desired to further improve data reliability, a Reed-Solomon code having a capability of correcting a random double byte error. Is used.

If a medium with a lower error rate such as a magneto-optical disk is used, or if the reliability of data is desired to be further improved, a Reed-Solomon code having the ability to correct a random triple byte error or more is used. Is desirable.

Generally, the Berlekamp-Massie method and the Peterson method are known as Reed-Solomon code decoding methods for correcting the t-fold error.

However, the Peterson method requires the following steps, which complicates the decoding process.

Step 1: From the syndrome, the determinant of degree M However, M = t, t−1, ..., 2,1 is calculated for each M,
Find the number of errors.

Step 2: An error locator polynomial is created according to the number of errors found in step 1, and its coefficient is found.

Step 3: Find M roots of the error locator polynomial. These roots represent the location of the error.

Step 4: Based on the obtained M error positions and the syndrome, each error pattern corresponding to each error position is obtained.

In order to avoid such a decoding process, as a method for directly decoding the error position and the error pattern without taking the above steps, "a decoding method of the extended Reed-Solomon code on GF (2 ^m )" (electronic IEICE Transactions '83 / 1 Vol.J
66-A, No. 1) or "digital signal error detection circuit" (JP-A-58-138140).

Since the method of directly decoding does not require the above steps, it is possible to provide a decoding circuit with a small circuit amount for double correction (see Japanese Patent Laid-Open No. 58-144952 shown in FIG. 2). (See schematic block diagram).

However, even for shortened Reed-Solomon codes,
It had the drawback of requiring the same number of clocks as when not shortened.

The reason will be described using the shortened code shown in the first figure. Here, the error pattern e _i is _added to the i-th word W _i of the double error correction shortened Reed-Solomon code, and the j-th word
A case where the error pattern e _j occurs in W _j will be described.

Primitive element α of Galois field GF (2 ^m ) defined by an arbitrary integer m
The syndrome obtained by multiplying the received code by the parity check matrix configured using And the syndromes S ₀ , S ₁ , S ₂ , and S ₃ are α ⁰ respectively.
It is generated by inputting the words W _N , ..., W _i in this order to a syndrome register having (= 1), α ¹ , α ² , and α ³ as feedback coefficients.

In the direct decoding method disclosed in Japanese Patent Laid-Open No. 58-144952, the syndrome register is further shifted after this.

The syndromes S ₀ , S ₁ , S ₂ , and S ₃ after the k-th shift are represented by the following equations.

The exclusive OR A ₀ , A ₁ , A ₂ between the syndromes is expressed by the following equation.

Here, if we define L = A ₀ · A ₁ + ▲ A ² ₁ ▼, L = e _i e _j (1 + α ^{i + k} ) (1 + α ^{i + k} ) (α
^{2 (i + k)} + α ^{2 (i + k)} ) (4), L = 0 only when k = M−i or k = M−j.

Therefore, in order to check whether or not an error has occurred in the first word from the value of L, it is necessary to shift the syndrome from i = 1 to k = M−1 times. This is the same as the number of shifts required when not shortened.
Since one clock is required for each shift, the same number of clocks as when not shortened is required. Therefore,
If the number of shifts can be reduced, the processing time can be shortened accordingly.

〔Purpose〕

In view of the above points, an object of the present invention is that when directly decoding a shortened Reed-Solomon code, the number of shift operations for the syndrome is smaller than that in the case where the shortened Reed-Solomon code is not shortened. To provide a circuit.

In order to achieve such an object, in the present invention, the code length N
In an error correction circuit that receives a 2 ^m-element shortened Reed-Solomon code (N <M = 2 ^m −1: m is a natural number) and corrects a t-fold error of the received word, the received word W _j (j = 1,2 , ..., N) is multiplied by α ^{i (M−N)} · α ^ij (α is a primitive element of Galois field GF (2 ^m )) to obtain a syndrome S _i (i = 0,1, ..., ^N) 2
t-1) and a process of repeatedly multiplying each of the syndromes S _i (i = 0,1, ..., 2t-1) generated by the generating device by α ⁱ N-1 times, Syndrome S _i ^(k) = S _i (α ⁱ ) ^k (k = 0 ..., N−1) is sequentially calculated, and the syndrome S _i ^{(k) is} sequentially calculated by the first calculation unit. Sum of two S _i ^(k) + S _{i + 1} ^(k)
(I = 0, 1, ..., 2t−2) in n + 1 rows and i−n + 1 columns (0 ≦
(n, i−n ≦ t−1) which is an element of a t-th order square matrix and which sequentially calculates the determinant Δ ^(k) , and the syndrome S _i ⁽ which is sequentially obtained by the first calculating means ^{). k)} (i
= 0,1, ..., 2t-1), the third calculation means for calculating the error pattern e _Nk when an error occurs in the received word W _Nk , and the second calculation means for sequentially calculating the error pattern e _Nk. For each of the determinants Δ ^(k) , a determination unit that determines whether or not the value is 0, and if the determination unit determines that the value of the determinant Δ ^(k) is 0, it is calculated. The error pattern
and having a correction means for correcting the received word W _Nk by e _Nk.

As a preferred embodiment of the present invention, a product of 2t (where t is a positive integer) first-order polynomial using a primitive element α of a Galois field GF (2 ^m ) defined by an arbitrary integer m. A shortened read of the code length N (where N is a positive integer larger than 2t and smaller than M = 2 ^m −1) generated from the obtained generator polynomial.
Syndrome computing means for receiving a Solomon code and individually outputting _2t syndromes S ₀ , S ₁ , ..., S _{2t-1 corresponding} to the received code, and α considering the shortening of the code.
^{i (M−N) is represented} by each syndrome S _i (i = 0, 1, ... 2t−
Multiplication means for multiplying 1) or multiplying the received signal in advance;
The syndromes S ₀ ′, S ₁ ′, ... Obtained from this multiplication means
For S 2 ′ _t−1 , S _i ′ → S _i ′ α ⁱ → S _i ′ α 2 ⁱ → ... → S _i ′ (α ⁱ ) ^k = S _i
^(k) However, means for sequentially exchanging i = 0,1, ..., 2t-1 k = 1,2, ..., N, and exclusive logic between syndromes for each conversion of the syndrome S _i ^(k) The sum S ₀ ^(k) S
Means for computing ₁ ^(k) , S ₁ ^(k) S ₂ ^(k) , ..., S _2t-2 ^(k) S _2t-1 ^(k) and the exclusive OR S ₀ ^(k) S ₁ ^(k) , S ₁
^(k) S ₂ ^(k) , ..., S _2t-2 ^(k) S _2t-1 ^(k) determinant Δ ₁ ^(k) = | S ₀ ^(k) , S ₁ ^(k) | Error correction is provided with a means for calculating Δi ^(k) = 0, a t-multiple error position detection circuit for simultaneously detecting the number of errors and the position of the error by detecting Δi ^(k) = 0, and a logic circuit for calculating an error pattern of the error position. It is also possible to configure a circuit.

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

〔Example〕

FIG. 3 is a block diagram of a shortened code real-time correction circuit to which the present invention is applied.

In this embodiment, a circuit configuration for correcting double error is shown.

In FIG. 3, 1 to 3 are elements α of Galois field GF (2 ^m ).
^(M−N) , α ^{2 (M−N)} , α ^{3 (M−N)} multiplication circuits, 4 to 6 are α, α ² and α ³ multiplication circuits, and ROM or exclusive OR It is configured by combining circuits.

Reference numerals 7 to 17 are m-bit exclusive OR circuits.

18 to 21 are m-bit registers (syndrome,
Register).

Further, the exclusive OR circuit 7 and the register 18 constitute a circuit for generating the syndrome S ₀ . Furthermore, the α ^(M−N) multiplication circuit 1, the exclusive OR circuit 8, the α multiplication circuit 4, and the register
19 and 19 form a circuit for generating the syndrome S ₁ .

α ^{2 (M−N)} multiplication circuit 2, exclusive OR circuit 9 and α ²
The multiplication circuit 5 and the register 20 constitute a circuit for generating the syndrome S ₂ .

α ^{3 (M−N)} multiplication circuit 3, exclusive OR circuit 10 and α ³
The multiplication circuit 6 and the register 21 constitute a circuit for generating the syndrome S ₃ .

W ₁ , W ₂ , ..., W _N (W _i (i = 1,2, ..., N) is composed of m bits) is the received code length N (where N is a shortened code length). , N <M = 2 ^m −1) codewords.

In order to operate this embodiment, first, the switch 28 is closed and the received words W ₁ , W ₂ , ..., W _N are sequentially input to the signal line a, and the signal line b.
Add a shift clock to. At this time,
The received word is preliminarily set to α ^(M−N) , α by the α ^(M−N) , α ^{2 (M−N)} , α ^{3 (M−N)} multiplication circuit.
^{2 (M−N)} , α ^{3 (M−N)} are multiplied.

Therefore, each syndrome is as follows.

Here, similarly to the conventional example, a case where an error pattern e _i occurs in the i-th word W _i and an error pattern e _j occurs in the j-th word W _j will be described as an example.

Therefore, each syndrome is as follows.

Next, when the switch 28 is opened and the shift clock is continuously applied to the signal line b, the syndromes S _{0 to} S ₃ after the k-th shift are expressed by the following equation.

When exclusive ORs A ₀ , A ₁ and A ₂ among the syndromes are taken by the exclusive OR circuits 11 to 13, they are expressed by the following equation.

Here, if L = A ₀ · A ₂ + ▲ A ² ₁ ▼ is defined, L = e _i · e _j (1 + α ^M−N · α ^{i + k} ) · (1 + α
^M−N · α ^{j + k} ) (α ^{2 (i + k)} +
From α ^{2 (j + k)} ) · α ^{2 (M−N)} (10), L = 0 only when k = N−i or k = N−j
Becomes

Here, since the code length is N, 1 ≦ i ≦ N, 1 ≦ j ≦ N Therefore, k <N, and the shift clock is suppressed to the shortened code length.

The pattern is also calculated by the following equation.

e = S ₀ + ▲ A ² ₀ ▼ (A ₀ + A ₁ ) ⁻¹ (11) Because, when k = N−i, A ₀ , A ₁ , and S ₀ are Therefore, Returning to FIG. 3 again, each component will be described.

22 and 23 are square circuits on the Galois field GF (2 ^m ), and α ⁱ
When is input, α ²ⁱ is output.

24 is a circuit for outputting a multiplication result α ^{i + j} of arbitrary elements α ⁱ and α ^j on the Galois field GF (2 ^m ), and when m ≦ 6, RO
Can be composed of M.

A circuit 25 outputs a division result α ^i−j of arbitrary elements α ⁱ and α ^j on the Galois field GF (2 ^m ). If m ≦ 6, it can be configured by a ROM.

Reference numeral 26 denotes a gate circuit, which uses a signal from the exclusive OR circuit 15 as a gate signal, opens the gate when the gate signal is "0", and outputs an output signal from the exclusive OR circuit 16, If the gate signal is not "0", the gate is closed and "0" is output.

27 is a buffer memory for storing N words of data.

The exclusive ORs A ₀ and A ₂ between the syndromes output from the above exclusive OR circuits 11 and 13 are input to the multiplication circuit 24,
A ₀ and A ₂ are output.

At this time, the exclusive OR A ₁ between the syndromes output from the exclusive OR circuit 12 is input to the squaring circuit 23, and ▲ A ²
₁ ▼ is output. By inputting the result to the exclusive OR circuit 15, L = A ₀ · A ₂ + ▲ A ² ₁ ▼ is calculated.

At the same time, the exclusive OR circuit 14 calculates A ₀ + A ₁ , and the square circuit 22 calculates ▲ A ² ₀ ▼. By inputting this result to the division circuit 25, ▲ A ² ₀ ▼ / (A
₀ + A ₁ ) is output.

Finally, the exclusive OR circuit 16 outputs e = S ₀ + ΔA ² ₀ ▼ / (A ₀ + A ₁ ).

When the switch 28 is closed and the received word W _N , ..., W ₁ is input from the signal line a, the memory buffer 27 receives W _N ,
…, Store W ₁ . Then, when the switch 28 is opened, the received word is output in synchronization with the shift clock b.

Therefore, when the switch 28 is closed and the (N-i) th shift is performed, the output from the exclusive OR circuit 15 is L =
0, and the output from the exclusive OR circuit 16 is e =
e _i . Therefore, since L = 0, the gate circuit 26 is opened, and the exclusive OR circuit 16 outputs the output e = e _i .
At this time, since W _i is output from the buffer, W _i + e _i = W _i is calculated in the exclusive OR circuit 17, and the error is corrected and output. The same applies to W _j .

Although the double error has been described above, the t error can be similarly expanded.

In the embodiment shown in FIG. 3, the syndrome generator and the respective syndromes are represented by S _i ′ → S _i ′ α ⁱ → S _i ′ α 2 ⁱ → ... → S _i ′ (α ⁱ ) ^k (i = 0, Although the part to be converted into 1,2,3) is shared by opening and closing the switch 28, as shown in FIG. 4, the syndrome generation part and the syndrome conversion part can be separated. With this configuration, it is not necessary to open the switch 28 and idle feed the received word after the syndrome is generated, and therefore, even when the code blocks are continuously transmitted, real-time processing is possible.

Further, when the α ^MN , α ^{2 (MN)} , and α ^{3 (MN)} multiplication circuits are constituted by ROM, as shown in FIG. 5, word position information is given to the signal line c. When the i-th word W _i is input to the ROM 33, W _i α ^M−N · α ⁱ is output, while for the ROM 34, W _i α ^{2 (M−N)} · α.
By outputting ²ⁱ to the ROM 35 and outputting W _i α ^{3 (M−N)} · α ³ⁱ , the equation (5) can be calculated.
With this configuration, the circuit can be further simplified.

If m ≦ 6, the arithmetic circuits for L and e can be simplified by using the ROMs 36, 37 and 38 (see FIG. 5).
Here, ROM 36 for the input of A _0, A _2, and outputs the A ₀ · A _2. ROM37 is A ₀ · A ₂ + A ₁ for A ₁ , A ₀ , A ₂ input
Is output. ROM38 is ▲ A ² ₀ ▼ ・ for input of A ₀ and A _1.
Outputs (A ₀ + A ₁ ) ^-1 .

Furthermore, as shown in FIG. 6, in the middle of the syndrome generation circuit and the syndrome conversion circuit, α ^(M−N) , α
It is also possible to insert a ^{2 (M−N)} , α ^{3 (M−N)} multiplication circuit. Such a configuration is equivalent to the following equation obtained by combining the equation (5) with α ^(M−N) , α ^{2 (M−N)} , and α ^{3 (M−N)} .

[Effect] As described above, according to the present invention, when the shortened Reed-Solomon code is directly decoded, the number of sequential operations performed on the syndrome can be reduced by the shortening of the code. High-speed error correction that requires a short time can be performed.

By implementing the present invention, not only can the hardware be downsized, but it can be applied to a wide range of digital technical fields such as all communication technologies including space communication and digital image processing technologies.

BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is an explanatory view of a shortened code, FIG. 2 is a block diagram of an error correction circuit disclosed in Japanese Patent Laid-Open No. 58-144952, and FIG. 3 applies the present invention. FIG. 4 is a block diagram showing an embodiment of a shortened code real-time correction circuit, FIG. 4 is a block diagram showing another embodiment of a shortened code real-time correction circuit that is configured by separating a syndrome generation unit and a syndrome conversion unit, and FIG. FIG. 6 is a block diagram showing another embodiment of the shortened code real-time correction circuit simplified by using ROM, and FIG. 6 shows the syndrome generation of α ^MN , α ^{2 (MN)} , and α ^{3 (MN)} multiplication circuits. FIG. 7 is a block diagram showing another embodiment of a shortened code real-time correction circuit that is configured by being inserted in the middle of the section and the syndrome conversion section. 1 ... α ^M-N multiplication circuit, 2 ... α ^{2 (M-N)} multiplication circuit,
3 ... α ^{3 (M−N)} multiplication circuit, 4 ... α multiplication circuit, 5 ... α
² multiplication circuit, 6 ... α ³ multiplication circuit, 7-17 ... Exclusive OR circuit, 18-21 ... m-bit register (syndrome register), 22, 23 ... Square circuit, 24 ... Multiplication circuit, 25 ... Split Arithmetic circuit, 26 ... gate circuit, 27 ... buffer memory, 28-32 ...
Switches, 33 to 38 ... ROM, 39 ... Error pattern decoding circuit, 4
0 ... Error position detection circuit.

Claims (1)

[Claims] 1. An error correction circuit for receiving a 2 ^m -element shortened Reed-Solomon code having a code length N (N <M = 2 ^m −1: m is a natural number) and correcting a t-fold error of a received word. Syndrome S _i by summing each word W _j (j = 1,2, ..., N) multiplied by α ^{i (M−N)} · α ^ij (α is a primitive element of Galois field GF (2 ^m )) (I = 0,1, ..., 2t
−1) is generated, and the syndrome S _i (i =
0,1, ..., 2t−1) is repeatedly multiplied by α ⁱ N−1 times, so that the syndrome S _i ^(k) = S _i (α ⁱ ) ^k (k
= 0 ..., N-1) sequentially, and the syndrome sequentially obtained by the first arithmetic 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
Third calculation means for calculating an error pattern e _Nk when an error occurs in _Nk , and the determinant Δ calculated sequentially by the second calculation 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. And an error correction circuit for correcting the received word W _Nk by the error correction circuit.