JP2603243B2 - Error correction device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Industrial Application Field] In recent years, the application of error correction codes has become widespread as a measure for improving the reliability of various digital systems such as memory systems.

Among them, the Reed-Solomon code (hereinafter referred to as RS code) is a very important code for practical use that has the feature of being able to minimize redundancy among linear codes having the same code length and correction capability. , Magnetic disks, compact disks, etc.

The present invention belongs to the field of the above-described error correction technology, and particularly relates to a parallel computing device using a systolic array.

[Conventional technology]

There are various methods for encoding / decoding the RS code, and it is necessary to realize the following operations (1) to (7).

1) Generation of syndrome polynomial A syndrome polynomial S (x) = ΣS _i−1 * x ^j is generated from the received word sequence (r _n−1 , r _n−2 ,..., R ₁ , r ₀ ).

Where S _i-1 = Σr _n-1 * (α ^j ) ⁿ (1) 2) Generation of error locator polynomial and error numerical polynomial A ₀ = x ^2t , B ₀ = ^Smallest common polynomial of S (x) W = GCD (A ₀ , B ₀ ) (2) is obtained. On the way, a polynomial D satisfying the following equation represents an error locator polynomial σ (x), and W represents an error numerical polynomial ω (x).

degW <t, degD ≦ t C * A ₀ + D * B ₀ = W 3) Generation of error position and error value For polynomials σ (x), σ ′ (x), (x), ω (x), f (x ) = Σf _n-1 * x ⁿⁱ (3) is obtained for x = α ^{−n + i} (i = 1,..., N).

However, the calculation of f (x) is σ (x), σ ′ (x), ω
Three times are needed for (x).

4) Execution of error correction _r'ni = _rni + _eni (4) However, when σ (α- ^{n + i} ) ≠ 0, _eni = 0, σ (α- ^{n + i} )
When = 0, e _ni = ω (α− ^{n + i} ) / σ ′ (α− ^{n + i} ) For erasure error correction, in addition to the above 1) to 4), the following 5), 6 ) Is required.

5) Generation of vanishing position polynomial For s vanishing positions j1, j2,..., Js, Y ₁ = α ^ji (i = 1,
2, ..., and s), obtains the erasure position polynomial λ (x) = (1- Y 1 * x) * (1-Y 2 * x) * ... (1-Y 5 * x) (5).

6) Multiplication of erasure position polynomial and syndrome polynomial S (x) = S (x) * λ (x) (6) This S (x) is used as B ₀ in 2).

 The following operation is required for encoding.

7) Encoding Information sequence I (x) = (I _k−1 , I _k−2 ,..., I ₀ ) and generator polynomial g (x) = g _m * x ^m + g _m−1 * x ^m−1 + ... + from g ₀ to generate a Baritei P (x). (M = 2t) where P = (x) = I (x) * x ^m mod g (x) (7) In the RS coding / decoding process having a large correction capability in realizing the above-described operation. Instrumentation has been very difficult because the scale and control of the instrument is very complex and large.

However, recent advances in semiconductor technology have made it possible to make complex and large-scale devices VLSI. At this time, it is important to consider an algorithm that makes use of the features of VLSI.
The systolic algorithm is a VLSI-oriented algorithm proposed by Kung et al. Up to now, the configuration of IC cells by the systolic algorithm has been shown for some of the processes 1) to 7). However, they have been designed as independent cells for one function. Therefore, it is necessary to design a separate cell for each of the processes 1) to 7).

[Problems to be solved by the invention]

Japanese Patent Application No. 61-305898 filed earlier by the present applicant (hereinafter referred to as
In the prior application), the following processes 1) to 7) required for RS encoding / decoding are performed in the same processing unit (processing / processing).
Element, hereinafter referred to as PE).

In the architecture described in the prior application, when IC cells are converted into 1PE units, there is no need to design IC cells for each of the processes 1) to 7). In that respect, the architecture shown in the prior application can be said to be an architecture having versatility. However, in the architecture shown in the earlier application, the processing of 1) to 7) is the same PE
However, the connection and control of PE must be changed for each process. Even if an IC is formed in units of one PE and the connection is given externally, the connection is unique to the processing, so that one PE cannot perform another processing.

Therefore, the architecture shown in the earlier application was not a truly versatile architecture.

Therefore, when performing erasure error correction 5) and 6), PEs for processing 5) and 6) are required, and the erasure error correction cannot be processed by a normal RS code decoder.

Also, when the circuit size is reduced by increasing the number of register stages in the PE as in the prior application, the number m of register stages is limited to 2t (t is the correction capability), so there is a limit.

[Means and Actions for Solving the Problems] In the error correction device of the present invention, each processing circuit includes a plurality of single-stage registers and a plurality of multi-stage registers, an external input, and the plurality of single-stage registers. A selector for selecting and outputting a plurality of inputs from a register and inputs from the plurality of multi-stage registers; a first multiplier for multiplying a first output and a second output of the selector; A second multiplier for multiplying a third output and a fourth output; and an adder for adding results of the multiplication by the first and second multipliers, the result of the addition by the adder and the selector Are stored in the plurality of multi-stage registers, respectively.
The other part of the output of the selector is stored in each of the plurality of single-stage registers, and the outputs of the plurality of single-stage registers and the plurality of multi-stage registers are respectively input to the selector. An error correction device including a single-stage register and a plurality of processing circuits that output some outputs of the plurality of multi-stage registers to the outside,
A plurality of the processing circuits have the same circuit configuration and are connected in series with the same connection relationship, and by changing the input / output relationship of the selector, a different procedure required for decoding error correction is performed. Are executed, and two or more of the plurality of operations are executed by using the same processing circuit in a multiplex manner.

〔Example〕

FIG. 1 shows a basic PE according to the present invention. In FIG. 1, 1 is a multi-input multi-output selector (MUX), 2 and 3 are multipliers (on Galois fields), and 4 is (on Galois fields).
It is an adder. Primitive polynomial P over Galois field GF (2 ⁸ )
(X) = When considering a multiplier by ^{x 8 + x 4 + x 3} + x 2 +1, 2,3 is implemented as Fig. 13, the 4 EXOR circuit (8
). Registers 5 to 11 are operated by the clock CK.

FIG. 11 shows an extended PE in which register stages 12 to 14 are inserted for miniaturization of the circuit. When the number of register stages of 12 to 14 is m-1, the entire processing is decomposed into 1 / m, and the number of redundant PEs is also 1
/ m. It is connected as shown in FIG. Figure 1
FIGS. 3 to 9 show input / output diagrams and control of each PE in the case of a block.

1) First, α ^{j (j} = 1 to each PE, ..., a 2t) to set, α~α the alpha ^j to the A input of the # 1 of PE at a transfer rate of CK
Enter in the order of ^2t . Each PE is controlled to S1..5 = 02 (hereinafter, the value of the selector selection signal S1..5 is represented by HEX (hexadecimal)), and from the W output to the A input α ^j (j = 1,..., 2t) ) Is output with one clock delay. When the value of α ^j to be set arrives at each PE, α ^j and 1 are set in the registers 5, 11 by setting S1..5 = 03. After setting α ^j , return to S1..5 = 02.

Next, during the calculation, the received word r _ni is _updated for one cycle (the number of register stages is m
Mxck times), and control is also performed every cycle.
In r _ni (i = 1,..., n), when i = 1, S1..5 = 00
And an initial value Z ₀ = 0 is output from x, and Z _i = Z _i−1 · α ^j
+ R _ni = r _n-1 () is calculated. Normally, s1..5 = 01 until i = 2,..., n, and the operation is performed by feeding back the previous operation result Z _i-1 from the D input to the X output.

When i = n, a syndrome coefficient _Sj is generated in the register 8 of the PE #j. Its S to process the next codeword
_j-1 is transferred to the register 9 at the next clock i = 1. By sequentially setting each PE to S1..5 = 02, S _{j-1 of the} register 9 is output from the Z output, and the syndrome polynomial S from the last PE is output.
The coefficients of (x) are sequentially output. However, the received word r _nj is transferred by the register 10 and the register row 14 to the next PE with a one-cycle delay.

2) First, the PE of # 0 is set to S1..5 = 04 and A is input from A and B.
(Λ) and B (x) are input. When i = 1, the highest order coefficients β and α of the polynomials A (x) and B (x) are set in the registers 11 and 5, respectively (i = 1), and when i = 2,. S
Assuming 1..5 = 08, operation C (x) = α · A (x) + β · B
(X) is output from xy through the register 8 and the register sequence 13. At that time, the values of the registers 6 and 10 and the register rows 12 and 14 are fed back and output from the W and Z outputs, so that C (x) and A (x) and B (x) are aligned with the highest order.
Is input to the next PE.

Hereinafter, the PE of #i is controlled in an appropriate mode (nop, reduceA, reduceB) from the order of the previous A (x), B (x), C (x),
The above operation is repeated (the details of the algorithm are shown in the earlier application).

By repeating the above operation 2t + 2 times with feedback as a whole as shown in FIG. 10, A (x) and B (
The greatest common polynomial of (x) is obtained. However, 2t + 2
The second process is necessary only for the determination of degA <t or dagB <t, and is set to nop when dagA <t and nop 'when degB <t.

3) In 3), the register string 13 is omitted. i = 1, j = 1
The f _tj of A inputs and outputs to the x as S1..5 = 1C when, inputs to the register 6. At that time, the C input i is Z ₀ = 0, the α input is α ^{−n + i} (i = 1) from the B input, and Z ₁ = Z _{0 .α} ^{−n + i} + f _tj
Is calculated. j = 2 to t: S1..5 = 1D and Z _i-1
The operation is performed by feedback from the input.
Normally S1..5 = 1 when i = 2 ... n, j = 1, S when j = 2 ... t
The calculation of Z _i = Z _i-1 α ^{-n + i} + f _tj is performed by setting 1..5 = 1F, and when j = t, the value of f (α ^{-n + i} ) is output from the last PE. Is done.

4) Normally, S1..5 = 11, and r ′ _ni = r _ni +0 is calculated,
Output.

At the error position, by setting S1..5 = 10, r ′
_ni = r _ni + ω (α− ^{n + i} ) / σ ′ (α− ^{n + i} )
Perform error correction.

The detection of the error position is performed when σ (α− ^{n + i} ) = 0 (i = 1,..., N), thereby controlling S1.

Here, the register sequence is only delayed, and does not participate in the operation.

5) First, A of # 1 PE for setting Y _j (j = 1,... 2t)
Input Y _j in the order of Y ₁ to Y _2t . When i = 1, S1..5 =
By setting it to 14, Y _j from the A input (j = 1 ... 2t)
Is set in the register 5. For the C input or i, Z _j−1 is input and input to the register 9 through the Z output of the selector. The output of register 9 is Y (selector) at the next clock.
Is output to the _{Z i = Z i-1 ·} Y j · x + Z i-1 is calculated. The output is input to the register 8 and the register row 13 and input to the next PE one cycle later. However, the set values of the registers 5 and 11 are held for 2t clocks. By repeating the above operation eight times, the erasure position polynomial λ (t) is obtained. However, when PE is 8 or less, calculations and the like are performed by feedback as a whole as shown in FIG.

6) coefficients using the syndrome polynomial S (x) to the B input of the # 1 PE is inputted in the order of S _2t-f ~S _0, at the same time, from the E input lambda coefficient is lambda _2t to [lambda] ₀ of (x) Assume that they are input in order. From the C input, the input of Z _i-1 is input, but 0 is input in the PE of # 1 because Z ₀ = 0.

When i = 1, S1..5 = 12 is set, and the set values 1, 1 and S2t _-j are set in the registers 5, 11, respectively. After i = 2, by setting S1..5 = 13, it is held in the order of 1 and S2t _-j .

X always outputs the C input Z _i-1 . Y is 0, i when i = 1
= 2, the E input λ (x) is delayed by one clock in the register 9 to output a polynomial Z _i-1 .
It becomes λ (x) of the first order lower form.

As a result, Z _i = Z _i−1 · x + λ (x) · S _2t-j is sequentially calculated, and the calculation result λ (x) · S is obtained from the last PE.
(X) is output.

The above calculations are performed as many times as necessary by feedback as a whole as shown in FIG.

7) Information I (x) = (I _k−1 , I _k−2 ,..., I ₀ ) is represented by A (x),
Given the generator polynomial ^{g (x) = x m +} g m-1 · x m-1 + ... g 1 · x + g 0 B and (x). Parity P (x) is A (x) to B
Since the remainder is divided by (x), the operation is similar to the operation of reduceA in 2).

However, for simplicity, it is assumed that input and output are performed at the transfer rate of CK, and the required number of calculations is performed by feedback as shown in FIG.

[Other embodiments]

In this architecture, by using a register row as a RAM as shown in FIG. 12, an architecture that is not fixed not only in the circuit configuration but also in the processing speed can be obtained. In the case of the configuration shown in FIG.
When the degree PE is designed, the number m of register stages is fixed and the processing speed is determined.

Therefore, by arbitrarily using the RAM addresses 0 to m−1, a truly general-purpose operation PE on the Galois field is obtained.

FIG. 10 shows a system configuration using the PEs in FIGS. 11 and 12. A versatile computing unit can be configured simply by switching the control of PE by the control circuit.

〔The invention's effect〕

As described above, according to the present invention, a plurality of processing circuits have the same circuit configuration including multi-stage registers, and a plurality of processing circuits are connected in series in the same connection relationship. By executing a plurality of operations in different procedures necessary for decoding of error correction, and executing two or more of the plurality of operations using the same processing circuit in a multiplex manner. Therefore, the circuit scale of the device can be reduced.

In particular, when the code length n is much larger than the correction capability t, the same circuit is required to perform the erasure error correction, which is about 2t times in parallel with the syndrome generation processing, which is required about n code times, for example. The circuit size can be reduced without reducing the processing speed.

When a RAM is used as a multi-stage register, the number of register stages can be increased to improve the correction capability, and when the required correction capability is low, the number of register stages can be reduced to improve the processing speed.

[Brief description of the drawings]

FIG. 1 is an explanatory diagram of a basic PE of the present invention, FIG. 2 is a connection diagram of the PE of FIG. 11 of the present invention, FIG. 3 is an input / output diagram for syndrome generation by the PE of FIG. 11 of the present invention, FIG. Is an input / output diagram for GCD generation by the PE of FIG. 11 of the present invention, FIG. 5 is an input / output diagram for polynomial value generation by the PE of FIG. 11 of the present invention, and FIG. 6 is an error by the PE of FIG. 11 of the present invention. Input / output diagram for correction, FIG. 7 is an input / output diagram for erasure position polynomial generation by the PE of FIG. 11 of the present invention, FIG. 8 is an input / output diagram for multiplication by the PE of FIG. 11 of the present invention, and FIG. FIG. 11 is an input / output diagram for encoding by PE in FIG. 11 of the invention, FIG. 10 is a system configuration diagram, FIG. 11 is a diagram showing a register stage of the present invention, FIG. FIG. 13 is a diagram showing an example of a multiplier on a Galois field. 1 ... selector, 2,3 ... multiplier, 4 ... adder, 5-11 ... register, 12-14 ... register row, 15-17 ... RAM.

Continuation of the front page (56) References JP-A-63-233614 (JP, A) JP-A-63-157525 (JP, A) JP-A-63-157530 (JP, A) JP-A-63-164624 (JP) JP-A-63-164629 (JP, A) IEICE Technical Report 86 [301] IT86-102, P.A. 15-18 IEICE Technical Report 86 [301] IT86-103, p. 19-22

Claims (4)

(57) [Claims] A plurality of single-stage registers and a plurality of multi-stage registers; an external input; and a plurality of single-stage registers and a plurality of multi-stage registers. A selector for selecting and outputting an input; a first multiplier for multiplying a first output and a second output of the selector; a second multiplier for multiplying a third output and a fourth output of the selector
And an adder for adding the results of the multiplication by the first and second multipliers, and storing the result of the addition by the adder and a part of the output of the selector in the plurality of multi-stage registers, respectively. The other part of the output of the selector is stored in each of the plurality of single-stage registers, and the outputs of the plurality of single-stage registers and the plurality of multi-stage registers are respectively input to the selector. An error correction device comprising a plurality of single-stage registers and a plurality of processing circuits for outputting some outputs of the plurality of multi-stage registers to the outside, wherein each of the plurality of processing circuits has the same circuit configuration and the same A plurality of connections are connected in series with each other, and by changing the input / output relationship of the selector, a plurality of operations of different procedures necessary for decoding error correction are performed. And an error correction apparatus characterized by performing two or more operations of the operation of said plurality of using the same processing circuit multiplexed manner. 2. The error correction apparatus according to claim 1, wherein said plurality of operations in different procedures include erasure correction. 3. The error correction device according to claim 1, wherein said processing circuit having the same circuit configuration also performs an error correction code encoding process. 4. The error correction device according to claim 1, wherein a RAM is used as said multi-stage register.