JPH02214332A - error correction device - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to an error correction device, and particularly to increasing its processing speed.

[Conventional technology]

Conventionally, in a program control type error correction apparatus, the determination of program jump (transition of processing) and the accompanying change of the program counter are executed each time a certain determination result is obtained.

The conventional process will be explained using syndrome determination of a Reed-Solomon code as an example. The Reed-Solomotun code is a cyclic multidimensional professional code that has become widely known as it has been applied to various fields in recent years.

Now, regarding a Reed-Solomon code consisting of code length (n), information symbols (k), and check symbols (nk),
The decoding method will be explained. However, each symbol above is (m)
It is an element of the Galois field GF (2''), which is a finite field having 2 binary bits, or 21 elements.

In this case, (1) the generating polynomial g (x) of the multiple error correction Reed-Solomon code is expressed as (α) in the Galois field GF
The primitive light of (2″) is expressed as the following equation (1) or (2).

g(x) = (x+α) (X1α2) ・・・(X1α”) ・・・・・・・・・・・・
・・・・・・・・・ (1) g (X) = (X+α0)
(x+α)...(X+αm-1)...
・・・・・・・・・・・・・・・ (2) Also, if the transmitted codeword is represented by C(x), the received codeword is represented by R(x), and the error polynomial is E(x), then these The following relationship is established between them.

R(x) = C(x) + E(x) ・
・・・・・・・・・・・・・・・・・・ (3) In this case, the coefficients of the polynomial are included in the Galois field GF (2”), and the error polynomial E(x) is the error location and contains only the terms corresponding to the value (magnitude).

Therefore, if the error value at position Xi is Yj, then E(
x) =ΣY)x' ・・・・・・
. . . (4) In equation (4), Σ means the sum of errors over all positions.

Here, by syndrome S+=R(α1) [however, i=o, 1...2t −
1) As in (5) (if defined, above (3)
From the formula, S+=C(α') 1 E (α').

In this case, since C(x) is always divisible by g (x), C(α')=O, so S+=E(α'). Therefore, from the above formula (4), S+=E(α') =ΣY+(α')'−ΣYIX,'
・−・−(6) However, αI:
X, where xj represents the error location at αJ.

Here, the error location polynomial σ(x) is given by the number of errors as σ (X) = TI (x-X+) = X0+σ1
f-1+...+σ8 ・・・・・・・・・・・・・・・
(7) is defined as

Moreover, σ1 to σ6 in equation (7) are syndrome S.

There is a relationship between them as follows.

S++e+σHS ice l + ”+σe−I S
+++1σes+ −(8) In other words, the above-described Reed-Solomon code decoding procedure calculates syndrome Sl using equation (I) (5).

(n) (s) The coefficients σ, ~σ of the error location polynomial by the formula. Calculate.

(m) Root X of the error location polynomial by equation (7)
Find i.

(IV) The error value Yl is determined by equation (6), and the error polynomial is determined by equation (4).

(V) Error correction is performed using equation (3).

This results in the following steps (I) to (V).

Next, as a specific example of error correction using the above decoding procedure, a case will be described in which four check symbols are used for one block of data.

In other words, the generator polynomial g (X) in this case is g(x)
=(x+1) (x+α) (X+α2) (x+α3), and it is possible to correct up to double errors.

Now, considering the case where error correction is actually performed, the expected number of errors e is e = 0, e = l,
e = 2.

A case where e≧3 is possible. If e=o, the received codeword is correct, so no error correction processing is performed. Also, if e≧3, the correction capability is exceeded, so no error correction processing is performed other than setting an error flag. That is, error correction processing is actually performed when e=1 and when e=2.

As the error correction process, the above-mentioned decoding procedure (I) is used.

In response to (II), the following steps are roughly followed.

(a) Syndrome S. Calculate -83.

(b) Syndrome S. -83 tested, 5o=S.

If =S2=S3=O, it is determined that e=0 and the error correction process is ended. Furthermore, if only one value of syndromes 80 to S3 is 0, then ef-1, and if any two or more values are 0, e≧3, according to equation (6). It is clear from this.

(C) Expression (8) with e=1. Rewriting e=2,
In the case of e=1, it becomes. Moreover, in the case of e=2, it becomes.

Here, assuming that the actual decoder starts operation from the case where e=1, first, the solution σ1 that satisfies the simultaneous equations (9) is
must be sought. Then, if this solution does not exist, the decoder next uses the system of equations (
A solution σ1 that satisfies 10). We must find σ2. Note that if no solution is obtained here, it is assumed that e≧3.

The solution σ1 of equation (9) is obtained as, and the solution σ8 of equation (lO). σ2 is...
・・・・・・・・・・・・・・・It is obtained as (11).

Find the coefficient σ2 of the above error location polynomial (
11) When calculating the formula (S I S 3 + 32
” ) will be performed. Taking this operation as an example, the -numerical operation will be explained.

FIG. 3 is a timing chart showing a conventional general calculation operation, and the following description will be made with reference to this timing chart. CLK in FIG. 3 is a clock that determines the arithmetic processing timing in this example.

Syndrome S generated by a matrix calculation circuit. .

S,,S2. S3 is stored in the syndrome register. First, the syndrome S2 is outputted to the bus line at the l-th clock, and the original vector representation of the Galois field is converted to the exponential representation (VE conversion) through a conversion table, and the result is stored in the register l.

At the second clock, syndrome S2 is output to the bus line, similarly converted to VE, and held in register l. Here, the syndrome S2 previously held in register 1 is shifted to register 2.

At the third clock, the syndromes held in registers 1 and 2 are simultaneously sent to the multiplication/division circuit and multiplied (S2
'), computed and stored in the 'register'.

Next, at the fourth clock, syndrome S is output to the bus line, converted to vE, and held in register 1. At the 5th clock, °syndrome S3 is output to the bus line and V
E-converted and stored in register l. Shift Sl held in register l earlier to register 2. At the 6th clock, the syndromes held in registers 1 and 2 are sent to the multiplication/division circuit and multiplied (S, , S3), and this time they are converted from exponential expression to vector expression (EV conversion) 9 times through the conversion table. Hold in register l. 7
At the clock, S22, which was previously held in the calculation register, is output to the bus line and converted to EV through the conversion table.
Hold in register l. S held in register l
,.

S3 is shifted into register 2.

Finally, at the 8th clock, the syndromes held in registers 1 and 2 are sent to the adder circuit and added. In this way, output, conversion, and calculation are performed every l clocks, and the calculation of the formula s2''+s,·S3 is completed.

[Problems to be Solved by the Invention] However, when the calculation is performed in the above-described procedure, a single calculation and conversion is performed every l clock, which results in a long processing time for the calculation as a whole. Furthermore, the processing time for the calculations after the above calculation is similarly long (as a result, the processing time for the entire error correction apparatus becomes long, making it difficult to process received codes at a high bit rate).

For example, conventionally, when performing error correction on a received code at a high bit rate, a plurality of error correction circuits are provided in parallel to perform parallel processing, but this requires a large amount of hardware.

Against this background, it is an object of the present invention to increase the processing speed of an error correction device without increasing the amount of hardware.

[Means for solving problems]

With this objective in mind, the present invention provides an apparatus for correcting errors in received codes including error correction codes, which includes a plurality of bus lines to which a plurality of arithmetic data generated during error correction processing are respectively output. , means for generating new calculation data in accordance with the plurality of calculation data on the plurality of bus lines, and performing error correction processing in accordance with the new calculation data.

[For production]

By configuring as described above, multiple calculation data can be combined into one
In addition to outputting to the data bus in this step, one arithmetic operation can be performed in this step. Therefore, the calculation processing time can be significantly reduced compared to the conventional method.

〔Example〕

Examples of the present invention will be described below.

FIG. 1 is a diagram showing the configuration of an arithmetic unit forming a main part of an error correction device as an embodiment of the present invention. In this example, an arithmetic unit that performs an arithmetic operation using a four-word syndrome in order to perform double error correction is taken as an example.

In FIG. 1, l is a data memory, 2 is a memory controller, 3 is a determinant calculation circuit, and 3a.

3b, 3c, and 3d show syndrome S during the correction operation.

. S,,S2. This is a syndrome register for holding the value of S3. 4. 5. 7 is the VE conversion mentioned above.

RO with multiple function tables compatible with EV conversion, etc.
6 is a multiplication/division circuit, 8 is a temporary register for temporarily holding 1 byte data, 9 is a conversion table consisting of M, etc.
is an adder circuit, 10. Reference numeral 11 is an arithmetic register for holding the arithmetic results.

Next, as an example of the calculation operation of this calculation section, the timing chart in FIG. 2 shows the operation when performing the calculation for calculating the coefficient σ2 of the error location polynomial mentioned above, that is, the calculation of (SIS3+522)/(SO32+s, "). Explain using.

First, at the l-th clock, the syndrome S2 is simultaneously output from the register 3C to two bus lines (data bus A, data bus B), subjected to VE conversion in the conversion table 4.5, and sent to the multiplication/division circuit 6. do.

The calculation data S22 multiplied by the circuit 6 is again subjected to EV conversion in the conversion table 7, and is temporarily held in the temporary register 8.

At the second clock, syndromes S1 and S3 are simultaneously outputted from registers 3b and 3d to data buses A and B, respectively, subjected to VE conversion using conversion table 4.5, and then multiplied by multiplication/division circuit 6. Multiplied calculation data S1・S
3 is subjected to EV conversion in the conversion table 7 and sent to the adder circuit 9. At this time, the S that was held in the - hour register earlier
22 is sent to the adder circuit 9 and added to Sl and S3.

Then, the added calculation data (s 2”+s 1・S
S) is supplied to the arithmetic register IO and held there.

Next, at the third clock, syndrome S is output from registers 3a and 3c. and S2 at the same time as data bus A.

After being subjected to VE conversion in conversion tables 4 and 5, they are multiplied in a multiplication/division circuit 6. Multiplied calculation data S. -82 is EV converted in the conversion table 7 and temporarily held in the - hour register 8.

At the fourth clock, syndrome S1 is output from register 3b.
are simultaneously output to data buses A and B, subjected to VE conversion using conversion tables 4.5, and sent to multiplication/division circuit 6. The calculation data S, 2 multiplied by the circuit 6 is the conversion table 7
The signal is subjected to EV conversion and sent to the adder circuit 9. At the same time, data S0 and S2 held in temporary register 8
It is also sent to the adder circuit 9 and added to the above S and 2. The added calculation data (So-32+S, 2) is held in the calculation register 11.

Finally, at the 5th clock, operation register 10. ．． The data held in 11 (s 2”+s, ・S3) and (
So 'S2 +31'') are connected to data bus A, respectively.
B, undergoes VE conversion using conversion tables 4 and 5, and sends it to a multiplication/division circuit 6. Here, division is performed to obtain σ2 (S 2”+Sl ・S3) / (So 'S
2 +s, ”) is completed.

As is clear from the explanation up to this point, the speed of the following four arithmetic operations can be similarly increased in the above-mentioned arithmetic unit.

That is, by configuring as described above (by configuring the entire error correction process by simply providing multiple bus lines), high-speed processing can be achieved without increasing the amount of hardware, and video signals reproduced from magnetic recording media, etc. We have obtained a compact device that can perform error correction on received codes with many errors at a high bit rate.

In the above embodiment, two bus lines capable of outputting a plurality of arithmetic data are provided, but if three or more bus lines are provided, the arithmetic processing can be further speeded up. Also, a multiplication/division circuit depending on the arithmetic expression to be calculated.

It goes without saying that the arrangement of the adder circuit, the -time register, etc. can be changed as appropriate.

Furthermore, although the above embodiment has been explained using a Reed-Solomon code capable of correcting 2 errors as an example, the operation procedure and the arrangement of each of the unit operators described above may also be changed for an error correction device that performs error correction using other error correction codes. By doing so, the present invention can be similarly applied and similar effects can be obtained.

〔Effect of the invention〕

As explained above, according to the present invention, it is possible to obtain an error correction device that has small hardware scale and can perform error correction processing at high speed.

[Brief explanation of the drawing]

FIG. 1 is a diagram showing the configuration of an arithmetic unit forming a main part of an error correction device according to an embodiment of the present invention; FIG. 2 is a timing chart for explaining the arithmetic operation by the arithmetic unit in FIG. 1; The figure is a timing chart for explaining arithmetic operations in a conventional error correction device. In the figure, l is a data memory, 2 is a memory controller, and 3 is a data memory.
3a, 3b, 3c, 3d are syndrome memories, 4.5.7 are conversion tables, 6 is a multiplication/division circuit, 8 is a temporary register, 9 is an addition circuit, 10.
11 is an arithmetic register, and A and B are data buses, respectively.

Claims (3)

[Claims] (1) A device for correcting errors in a received code including an error correction code, which includes a plurality of bus lines to which a plurality of arithmetic data generated during error correction processing are respectively output, and a An error correction device comprising means for generating new calculation data according to a plurality of calculation data, and performing error correction processing according to the new calculation data. (2) Claim (1) characterized in that each of the plurality of calculation data is a syndrome, and the new calculation data is a coefficient of an error location polynomial.
Error correction device as described in section. (3) The error correction device according to claim (1), wherein the means for generating new calculation data comprises a plurality of calculation means that supply outputs to the plurality of bus lines.