JPH0472923A - Error detecting and correcting device for reed solomon code - 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] [Industrial Application Field] The present invention is applied to a digital video tape recorder (DVTR).
), digital audio tape recorder (DAT)
) etc., when reproducing a digital signal consisting of a Reed-Solomon code (hereinafter referred to as an R8 code) to which a parity signal generated using a predetermined method is added to improve reliability, a predetermined method is used based on the added parity signal. The present invention relates to an error detection and correction apparatus that detects errors and corrects them to the original correct signal using the method described above, and particularly relates to a circuit configuration method of an arithmetic operation unit that calculates the coefficients of an error locator polynomial and the magnitude of each error.

[Conventional technology]

Conventionally, regarding error detection and correction of R8 codes, the Journal of the Institute of Electronics and Communication Engineers Vol. J64-A, No. 2 (February 1981)
Discussed on pages 137-144.

The error detection and correction consists of: (1) Syndrome calculation and error detection (2) Determination of the number of error symbols and calculation of the coefficients of the error locator polynomial (3) Derivation of the root of the error locator polynomial (4) Size of the error Calculation (5) is performed in the procedure of executing correction. Here, we will take as an example the decoding of the (15,11)R8 code, which is an R8 code in which 4 parity symbols generated by the generator polynomial %) are added to 11 symbols (8 bits per symbol) that are data. , the decoding operation will be explained. Note that all operations in the following explanation are performed on the finite field GF(2'').

(1) Syndrome calculation and error detection When a code word C = (c, 4. cm3.-, co) with a code length of 15 is recorded and reproduced, the reproduction sequence R = (rxsr rx
It is assumed that at...l ro) is reproduced.

Here, the error sequence included in the reproduced sequence R, that is, the difference between the reproduced sequence R and the code word C, is E= (ei,, e□3゜...
180), R is expressed as follows.

R(X)=C(X)1E (X) Here, since the generator polynomial G(X) is equation (1), the syndrome is.

S1=R(α1) =E(α') i=o, 1, 2.3...(2
) is defined. All of the syndromes that exist as many as the number of parity symbols become 0 (0 vector) when there is no error in the reproduced sequence R. From now on, the syndrome
If there is a sequence that is not the same, it can be detected that an error has occurred in the reproduced sequence R.

If there is a syndrome other than O and an error is detected, the following correction operations (2) to (5) are performed.

(2) Determination of the number of error symbols and error locator Although the (15, 11) R8 code with polynomial parity of 4 symbols can correct two or less errors, it is difficult to determine whether there are two or more errors. Can not.

Therefore, first, the two errors with the maximum correction ability are at position i.

Assuming that the magnitudes of Ei and EA occur in j, respectively, the following equation is obtained from equation (2).

S o = E l + E J
...(3) Sl-α"E++α'Ea
...(4) S2=α21E, +α2
4E, ...(5) S3=α3
'El+α3JEJ...(6
) The error location polynomial whose root is the error location is expressed as a quadratic equation, a (
X)=X2+a ”X+a'
-(7), since σ(X)=(X+α1)(X+α4), we have the relationship α8=α3+α α = α α. Therefore, from equations (3) to (6), α1
+α4. α1α4 is S. If it can be expressed by the relational expression -83, the coefficients of the error locator polynomial (7) can be obtained by calculating the syndrome.

From equations (4) and (5), α21. Eliminating the α2J term, S2+(α1+α')xs□=α1α' (E +
+ E a). Therefore, the following relationship exists: S2=αaS□10α”S o−(8).

Also, from equations (4) to (6), 53=aaS2+abS
There is a relationship of 1-(9). Formula (8),
When (9) is expressed in matrix representation, it becomes, so = 1. Therefore, Δ=S, ”+5oS2 −(10)α
3=(SiS2+5oS3)/Δ・−(1
1) αb=(Sz"5iS3)/Δ...
・(12). Here, the error is at position i, size E,
If it is one of the following, Δ=(α' E t)2+ E tα2” E t =
Since it becomes 0, Δ can be used as a determination formula for the number of error symbols. When Δ=0, there is one error, and the error locator polynomial, σ(X)=X+αa
...The constant term α1 in (13) is σ(
Since X)=O has α1 as a solution, Equation 1 (3), (
4), αa=α'=81/S.

can be easily determined.

(3) Derivation of the root of the error locator polynomial The main method for finding the root of the error locator polynomial is the ROM
There are two methods: a direct solution method using the method and a Chien search, but here we will explain the Chien search method, which substitutes all elements into the error locator polynomial and takes the element for which it becomes 0 as the root. Considering the case of
(α1)2+α0α1+α1σ(α14)=(α14)
This is a method of finding 2+αaα14+αb and using the element from which it becomes O as the root.

σ(α0) to σ(α14) are initial values of R2(0)
=1. , (0)=αa, K, (0)=αbσ(α'
) = , (0) 1 (0) + , (0) is given,
It can be determined by the following repeated calculations.

Kg(1) = α2 to 2(i −1)tKi(i) = α to 1(11).

xo(i) = xo(i - t) σ(α1) = KZ(1) + Kl(1) + KO(1) Since the Cheno search requires the number of steps equivalent to the code length, error detection and correction are Real-time processing is not possible. However, it is possible to process error detection and correction in real time by, for example, operating Cheno search in parallel.

(4) Calculating the size of the error Since one symbol of the R8 code on the finite field GF(2'') consists of 8 bits, in order to correct the error, not only the position of the error but also the size of the error is calculated. As is clear from equations (3) to (6), the magnitude of the error can be determined from the error position and syndrome.Equations (3) and (4) can be expressed in matrix form. If expressed using
(16) EJ=(α' s o + S 1 )/Δ
J − (17) Δl=ΔJ=α1+α
j...(18). In the case of one error, it is clear from equation (3) that E1=S.

(5) Execution of Correction Errors can be corrected by removing E+ and EΔ from the symbol at the lyj position of the reproduced sequence R obtained as described above.

[Problems to be Solved by the Invention] In (2) determining the number of error symbols and calculating the coefficients of the error locator polynomial in the prior art, equations (10) to (12) are used.
The coefficients αaαb of the second-order error locator polynomial expressed as number of steps).

(a) Calculation of common denominator Δ of αa α1 (2) (b)
Calculation of 1/Δ (using ROM that stores backlight in advance)
(1) (c) Calculation of the numerator of α8 (2) (d) Calculation of α8 (1) (e) Calculation of the numerator of α5 (2) (f) Calculation of αb (1) Therefore, to find the coefficient α8 α1 requires a total of 9 steps of calculation. Furthermore, as the number of errors increases to 3 and 4, the number of steps required to find the coefficients of the error locator polynomial increases exponentially to 44 steps and 221 steps, respectively. This is also the case in (4) error size calculation in the prior art, where there are two errors, three errors, and so on.
9, 33, and 124 steps are required for 4 and 4 steps, respectively. However, when detecting and correcting errors in R8 codes in real time, the calculation of the syndrome, the calculation of the error position and size, and the execution of correction are performed in a pipeline process, so the calculation of the error position and size is based on the code length. The number of steps must be within the range.

An object of the present invention is to provide an arithmetic circuit that reduces the number of steps required to calculate the coefficients of an error locator polynomial and the magnitude of an error, and an efficient method of configuring the circuit.

[Means to solve the problem]

The second purpose is to provide a memory for temporarily storing digital data consisting of a digital signal encoded with an R8 code and an error check code, and to perform operations on a predetermined finite field on the digital data stored in the memory. In an error detection and correction device having means for detecting errors in the digital data and correcting errors by applying
This is achieved by performing parallel operations using 1 or 2t multipliers and adders.

[Effect]

First, when the multipliers and adders of the R8 code error detection and correction device, which has the ability to correct up to 2 (=t) errors, are configured in parallel (3 (=t+1)), two errors are detected. Think about how to correct it when it happens.

The coefficients α3 and α5 of the second-order error locator polynomial expressed by equations (10) to (12) are obtained by the following procedure (the number of steps required is in parentheses).

(a) Parallel calculation of molecules of Δ, α8, and α5 (2
) (b) Calculation of 1/Δ (1) (c) Parallel calculation of α8 α5 (1) Therefore, the coefficient α8 α5 is calculated in a total of 4 steps, which is less than 1/2 of the number of steps by a single multiplier and adder. You can ask for it. Similarly, if the multipliers and adders of an error detection and correction device for an R8 code with up to three error correction capabilities are arranged in four parallel configurations, the coefficients of the third-order error locator polynomial can be found in 14 steps. . Furthermore, when the multipliers and adders of the R8 code error detection and correction device, which has up to four error correction capabilities, are arranged in five parallel configurations, the coefficients of the fourth-order error locator polynomial can be found in 62 steps, In either case, the number of steps can be significantly reduced compared to a single multiplier and adder.

Each coefficient of an error locator polynomial of order 5 or higher also has a common denominator, and in general, the coefficients of an error locator polynomial of order t have a common denominator with t multipliers and adders that calculate the numerators of t coefficients. By using one multiplier and adder for calculation, the calculation can be performed efficiently in terms of hardware scale.

Furthermore, when there are two errors, the number of steps required to calculate the magnitude of the error is 4 steps using the same procedure as for calculating the coefficients of the error locator polynomial, which can also be reduced to 1/2 or less. However, when there are three or more errors, the calculation of the magnitude of each error takes a different procedure from the procedure for calculating the coefficients of the error locator polynomial because the denominators of the calculation formulas are different. For example, if there are 4 errors, the error size is E
i y E J yEh, each denominator of Et is Δ1.
Δ3. Δ1. Assuming Δ, the calculation procedure using 5 (or 4) parallel multipliers and adders is as follows.

(a) Δ4. Δ4. Δ1. Calculation of Δ, (16) (b
) Calculation of 1/Δ1 (1) (C) Calculation of 1/Δ (1) (d) Calculation of 1/Δ (1) (e) Calculation of 1/Hatton (1) (f) Eat EJ , Ek, E brother's molecular calculation (]-
3) (g) Calculation of Ei, EJ, Ek, Ei (1) Therefore, the magnitude of each error E 1. , E a ,
Ek.

Ex is determined in a total of 34 steps. Here, above (
Since a) and (f) can be performed in parallel, the number of steps can be further reduced by configuring 8 (=2t) multipliers and adders in parallel, and the following procedure can reduce the number of steps from 34 to 21. It can be reduced to steps.

(,) Δ5. Δ6. Δ1. Calculation of Δ, El, E
Molecular calculation of J, E+ttEa (16) (b) Calculation of 1/Δ1 (1) (c) Calculation of 1/ΔJ (1) (d) Calculation of 1/Δ (1) (e) 1/80 Calculation (1) (f) Calculation for E, , EJ, Ek, E In the same way as (1), if there are 3 errors, 4 (or 3) parallel configuration will result in 13 steps, and 6 parallel configuration will result in 13 steps. The magnitude of each error can be determined in nine steps.

In this way, when there are three or more errors, the formula for calculating the size of each error has a different denominator, and the size of each error is calculated using 2t calculations, t for calculating the denominator and t for calculating the numerator. It can be efficiently calculated using a multiplier and an adder.

As the number of parallel multipliers and adders increases, the hardware scale increases, so whether to use a (t+1) parallel configuration or a 2t parallel configuration should be determined based on the balance between the number of steps and the hardware scale. .

〔Example〕

FIG. 1 shows a block diagram when the error detection and correction apparatus of the present invention is applied to decoding the (15.11) R8 code exemplified in the prior art section. R8 code decoding can be broadly divided into syndrome calculation and error detection;
Determining the number of error symbols and calculating the coefficients of the error locator polynomial,
This is performed through five steps: derivation of the root of the error locator polynomial, calculation of the magnitude of each error, and correction of input digital data. The program ROM 130 stores in advance control instructions for the circuit at each stage, and supplies control signals to each part of the circuit in accordance with the address generated by the program counter 131. The operation of this embodiment will be briefly explained below by dividing it into each correction stage using FIG.

(1) Syndrome calculation and error detection In FIG. 1, 101 is the information department D department. ~Do and parity part P3
This is a memory that temporarily stores the (15.11)R8 code consisting of ~Po. The digital data stored in the memo 101 is sequentially read out from Dlo and sent to the syndrome generation section 102. The syndrome generation unit 102 generates four syndromes S necessary for detecting and correcting errors in the (15,11)R8 code from the digital data PD read from the memory 101. -83 is generated. FIG. 2 is a detailed diagram of the syndrome generation unit 102 shown in FIG.
Register 202, SS2 Register 203, S83 register 204, addition circuits 205 to 208, α, U2 α3
It is composed of containers 209 to 211. Here, as an example, a procedure for determining syndrome S3 will be described.

(a) First, SSo register 201, SS register 2
02, S82 register 203, S83 register 20
4 are all cleared and the state becomes O.

(b) Hey D. is read out from the memory 101 in FIG.
It is input to the adder circuit 208. On the other hand, SS3 register 2
The content 0 of 04 is multiplied by U3 by the α3 unit 211, and this result is also supplied to the adder circuit 208 at the same time. here,
The input of the α3 device is 1 = (U7. tr6. u =, U4
．． U3. U2. U,, U,), the output is O= (
V7. V,,V5. V,,V3. V2. V engineering.

V, > then 0 = (U,, UsttJs, LJ4.U3.U2.
Ut, Uo)x(0,0,0,0,1,0,0,0) =(U7α7+U6α6+U5α5+U4α4+U3α
3+U2α2+U engineering α+Uo)×α=(U7α111 + u6α9+U, α9+U4α7
+U3α6+U2α5+U1α'+Uoα3).

The primitive polynomial of the finite field GF(28) is Xs+X'+X3
Since +X2+ 1 = 0, α8=α4+α3+α2+1 α9=α5+α4+α3+α α10=α6+α5+α4+α2. Therefore, 0=U, (α6+α5+α4+α2)+UG(α5+α
4+α+α)+U5(α4+α3+α2+1)+U,α
7+U, α+U2α'+U1α'+Uoa3 =U4α7+(U7+U3)α6+(U7+U,+U2
) α5 ten (U, ten U6 + US ten U1) α'+ (U6 + U
5+U,)α30(U7+U5)α2+U6α+U5 From v7=U4 v6=U3+U7 V,=U2+U,+U7 ■4−U□+U5+U6+U7 V3=U,+U5+U6 V2=U,+U7 V,=U.

The relationship V,=US is obtained. Therefore, as shown in Figure 3, α
The triple device can be composed of eight exclusive ORs 301 to 308. Further, the α unit 209, the α2 unit 210, and the power tree of α (referred to as a fixed coefficient multiplier) used hereinafter can all be configured using this method.

The adder circuit 208 performs an exclusive OR operation on the two inputs bit by bit (the same applies to 205 to 207), and newly sets the result in the S83 register 204. Expressed as a formula, it is as follows.

o×α3+D1o=D1o−)SS3 (c) The product of the contents of the SS3 register 204 and α3, read from the memory 101, is input to the adder circuit 208. The adder circuit 208 performs a bit-by-bit exclusive OR operation (hereinafter simply referred to as addition) as described above, and sets the result in the S83 register 204.

D1o×α3+D, →SS3 The same operation is repeated, and finally P from the memory 101. is read out, and finally the next value is set in the SS3 register 204.

(...((D10Xα3+D9)×α3+DI+)-
+P□)Xα3+P.

→S83 That is, DloX(α”)14+DgX(α3)13+-+P□
Xα3+P.

→SS3 This is the information section D1o-Do and the parity section P3-P.
Syndrome S3 of (15,11)R8 code consisting of ,
It is.

Other syndrome S. , S□t82 are similarly data D□ read from the memory 101 in the corresponding arithmetic circuits. ,..., is generated from Po,
SSo register 201 and SS□ register 2, respectively.
02, S82 The register 203 is loaded.

Syndrome S obtained in this way. ~S3 is
5So-8S3 registers 201-204 from FIG. 10 detector 103 and S. -83 is supplied to registers 104-107. 0 detector 103 is syndrome S. This circuit detects whether all -83 are O, that is, detects the presence or absence of errors in input data, and its detailed diagram is shown in FIG. Syndrome S exists in logical sums 401 to 404.

-S3 respective bit components are input, and if all bit components are LL O''', that is, the syndrome is 0, it outputs it O''. The respective outputs are input to the NOR gate 405, and the outputs are input to the NOR gate 405.

~ If all of S3 are O, the output N of the O detector 103
E becomes 111". Signal NE becomes program counter 1.
31, and if NE is "O", that is, there is an error in the input data, the program counter 131 starts counting, and the following correction operation is performed.

(2) Calculation of coefficients of error locator polynomial The calculation for calculating the coefficients of error locator polynomial is performed using the program RO.
Under the control of M130, the arithmetic operation section 108 has three parallel control circuits each including a multiplier, an adder, etc.

The arithmetic operation section 108, which is the gist of the present invention, is a section that performs the operations necessary to calculate the coefficients and error magnitude of the error locator polynomial described in the section of the prior art, and its block diagram is shown in FIG. is shown.

In FIG. 5, 501 is a multiplexer that selects a register, 502 to 504 are multipliers on the finite field G F (28), 505 to 507 are control circuits consisting of adders, logical sums, logical products, etc., and 508 is an input. RO that outputs the reverse destination of
M, 509-511 are registers. Here, the multiplication UXV on the finite field G F (28) is U= (U7.U
,,U5. U4. U3. U2. Ul.

Uo), V=(V7. V6. V5. V,, V3
．． V2. Vl.

Uo), then U X V = U X V oX a+UXV□×α
1 +UXV1Xα7 Therefore, the multipliers 502 to 50 in FIG.
4 can be constructed as shown in FIG. 601 to 608 are fixed coefficient multipliers, 64 609 are two-manual AND gates, 6
10 to 617 are parity generator circuits. As mentioned above, fixed coefficient multipliers are derived from exclusive OR gates,
Since the parity generator is composed of an exclusive OR gate, the multiplier 50 on the finite field GF (211)
2 to 504 can be configured by two manual AND gates and exclusive OR gates. Below, using FIG.
(12) and the calculation procedure of the % formula %(10) will be briefly explained.

(a) From the program ROM 130, a multiplier instruction is output to control circuits 505 to 507, a register selection signal is output to multiplexer 502, and multipliers 502 to 504
Then, S1×S1°51×S2, 52×S2t are calculated and stored in the AL/register 509 to C register 511, respectively.

S, 2 → A S1S2 → B 522 → C (b) Next, the program ROM 130 issues an instruction to “multiply” and “add 10”, and the multipliers 502 to 504 calculate 5IIX SKI SQX Ss-s, xS3, respectively. and adds it to the contents of the A register 509 to C register 511.

S12+5oS2 → A SiS2+5oS3 → B s2"+51s3 → C (Q) By the "backlight" instruction, the contents of the A register 509 are stored in the ROM 508, and all of the contents are stored in the multipliers 502 to 504.
0' is input. The control circuits 506 and 507 output the multiplication result (Oj), and the B register 510 and the C register 51
Add to 1. Further, the control circuit 505 outputs the output of the ROM 508, that is, the backlight of the contents of the A register 509,
Store in A register 509.

1 / (s x” + s o S 2) →
ASiS, +5oS3+O-+ B s2"+5oS3+O→C (d) Finally, by the "multiplier instruction, the multiplier 503 transfers the contents of the A register 509 and C register 511 to the multiplier 50.
4 multiplies the contents of the A register 509 and the B register 510 and stores them in the B register 510 and C register 511, respectively. Further, '1' and '1'' are input to the multiplier 502, and the multiplication result '1' is stored in the A register 509.

5182+5flS3 1 → A Through the above procedure, the coefficient αa of the first-order term of the second-order error locator polynomial is stored in the B register 510, and the coefficient α1 of the zero-order term is stored in the B register 510.
is stored in the C register 511, and the coefficient '1' of the quadratic term is stored in A
It is set in register 509. If there is one error, 0 is written to the A register 509, 1 is written to the B register 510, and C
Set α8 in register 511.

(3) Derivation of roots of error locator polynomial The coefficients of the error locator polynomial determined by the arithmetic operation unit 108, , , , , are sent to the Chien search unit 109 in FIG. FIG. 7 is a detailed diagram of the Chien search section 1.09. The Chien search unit includes registers 701 to 703 and a fixed coefficient multiplier 7.
04,705, addition circuit 706° logical sum 707. Down counter 708, and register 709. Fixed coefficient multiplier 710. Register ADR, 711, register ADR27
Consists of 12.

The coefficient of the error locator polynomial obtained in (2) is 2°K1.
Then, are latched from the A register 509 to the C register 511 to the registers 701 to 703 in FIG. At the same time, the program counter in Figure 1]-31 is held.
A, DR1 register 711 . that stores the location of the error. A.D.
R, register 712 is cleared and Chien search is started.

704 and 705 in FIG. 7 are α of the register 701, respectively.
2, the alpha device of register 702.

First, the signals stored in registers 701, 702, 703, ]-2α0. α5 is input to the addition circuit 706, 1 is input to the α2 unit 704, and the α unit is input to the α unit 705. The adder circuit 706 performs an exclusive OR operation on the inputs for each component. When this is X-α0 of the error locator polynomial% formula%, σ(α0)=(α0)2+αa(α0)+α1・=1+
It corresponds to α0+α1゛. Whether σ (α unit) is an O vector is detected by the logical sum 707 of each bit component of σ (α unit), and if it is a 0 vector, the output signal ER is (L Q II
, otherwise tL 1 ++.

■After the search is completed, the contents of the register 701 are the output α2 of the α2 unit 704, the contents of the register 702 are the output α8α of the α2 unit 705, and the output of the adder circuit 707 is σ(α unit )=α2+α8α+α5. Below, these processes are repeated to obtain the value obtained by substituting α to α14 into the error locator polynomial, and if it is O back 1 hell, the output ER of the logical sum 707 is tr
O”.

On the other hand, the register 709 and the α unit 710 are used to find the original position currently being searched, and the register 709 is set to '1' (=α0) at the start of the Chien search. The contents of the register 709 are changed to α, α2, . α3. ..., and if the value of the error locator polynomial at that time is O vector, the ADRl register 711 or ADR2 is controlled by the down counter 708.
The contents of the register 709 are stored in the register 712.

When the error locator polynomial is quadratic, the error locator P3 . (The order of α is Pl<P2) is stored,
In the case of the first order, the error position P is stored in the ADR register 11.

(4) Calculating the magnitude of each error Error position P found by Chen search.

P2 is set to S□ register 106 and S3 register 107 in FIG. Similar to the calculation for determining the coefficients of the error locator polynomial in (2), the calculation for determining the magnitude of the error is performed in parallel by the arithmetic operation section 08 in FIG. 1 under the control of the program ROM 130. A program RO in which the error magnitude calculation procedure described in the prior art section is stored in advance.
M130 is the multiplexer 501 and control circuit 5 in FIG.
05 to 507 are supplied with control signals. Each section operates according to its instructions and finally sets the magnitude of the error in A register 509 and B register 510. Here, A
The magnitude of the error set in the register 509 corresponds to the position of the error stored in the ADR1 register 711 in FIG. 7, and the B register 510 corresponds to the ADR2 register 712.

(5) Correction of input digital data FIG. 8 is a detailed diagram of the correction unit 110 in FIG. 1.

The correction section is RAM801. ROM802. Multiplexers 803, 804. Comparator 805. Latch 806.
Counters 807, 808. It is composed of an adder circuit 809, and the error position P□, P2 and the error size are 1. This circuit corrects the input data from 2 to 2 and outputs the corrected data ND. The RAM 801 inputs an address signal from a down counter 807 indicating the position of data, and outputs pre-written data PD before correction. Note that the down counter 807 is initially set to the code length. Multiplexers 803 and 804 each output the error position and error size of the error to be corrected next time, and counter 80
8 provides its control signals.

In the initial state, counter 808 is set to tt i I+, and multiplexers 803 and 804 output P2. K2 is being output. multiplexer 803
The output of is input as the address of ROM802, and the ROM
802 indicates the position of the error stored as a vector by α
Convert to the exponent part of .

At the start of correction, the RAM 801 receives an address signal from the counter 807 and outputs the stored data. The comparator 805 connects the output of the counter 807 and the ROM 80.
It is checked whether the two outputs match, that is, whether the data is erroneous, and a control signal is supplied to the adder circuit 809. The adder circuit 809 determines whether the data is an error based on the control signal, and if it is an error, the output of the multiplexer 804, that is, the exclusive OR of the error size and the data is corrected.

The output of the comparator is also supplied to the latch 806, and the output of the latch 806 is input to the counter 808 at the next clock.
input as the clock. The content of counter 808 is 2
The multiplexers 803 and 804 output 1 to Pl. Below, similar processing is performed and the RAM801
The correction is completed by outputting all data.

〔Effect of the invention〕

FIG. 9 shows the function of the number of parallel arithmetic operation sections and the number of operation steps for each number of errors in an error detection and correction device for an R8 code having a four-error correction capability. The coefficients in the figure are (2) coefficient calculation of error locator polynomial in the prior art, and the magnitude is (4) error magnitude calculation. As you can see from the figure, the number of calculation steps decreases as the number of parallels increases, but considering the hardware scale, the most efficient number of parallels is 5 (t + 1 when correction capacity t = 4). ), or 8(2t).

[Brief explanation of drawings]

FIG. 1 is a block diagram when the error detection and correction device of the present invention is applied to decoding the (15,11)R8 code of this embodiment, and FIG.
The figure shows the α3 multiplier 211 in FIG. 2, the O detector 103 in FIG. 1 in FIG. 4, the arithmetic operation unit 108 in FIG. 1 in FIG. Figure 1 Chen search section 109
, FIG. 8 is a block diagram that describes the correction unit 110 in FIG. Number of times required to calculate the size

Claims (1)

[Claims] 1. A memory for temporarily storing digital data consisting of a digital signal encoded by a Reed-Solomon code and an error check code, and performing an operation on a predetermined finite field on the digital data stored in the memory. In an error detection and correction apparatus having means for detecting errors in the digital data and correcting t errors,
The coefficients of the error locator polynomial and the magnitude of each error are expressed as (t+1
1. An error detection and correction device for a Reed-Solomon code, characterized in that operations are performed in parallel using ) or 2t multipliers and adders.