JPS61258536A - Double error correction decoder - Google Patents

Abstract

PURPOSE:To reduce remarkably a decoding time by using the coefficient sigma2 of a polynomial to apply a simple pre-processing, halving values considered to be roots into n/2 ((n-1)/2 for an n of odd number) and executing an arithmetic with a half number. CONSTITUTION:A microprocessor 1 inputs a value (alphaLj)/sigma1 from the A side input of a selector 4 to a register 6 via a data bus 2 and inputs a value (alphaLi)/sigma1 from the A side input of a selector 5 to a register 7, outputs of the registers 6, 7 and '1' are ORed exclusively by an exclusively OR adder 10, and the output of the OR adder 10 is inputted to a zero detector 11 and it is discriminated whether or not it is zero. The output of the register 6 is multiplied by alphaby an alpha multiplier 8 and it is held to the register 6 via the B side input of the selector 4. The output of the register 7 is multiplied by 1/alpha by a 1/alpha multiplier 9 and it is held in the register 7 via the B side input. The process is executed repetitively for n/2 times ((n-1)/2 times for an odd number n). The error location is calculated by the repetitive number when zero is detected.

Description

[Detailed Description of the Invention] [Field of Industrial Application] The present invention relates to a decoder for Reed-Solomon codes (hereinafter referred to as R3 codes), and in particular to a decoder for easily and quickly calculating two-city error positions. This is what I decided to do.

[Conventional technology]

The R3 code decoding method will be described below according to the code flowchart l- in FIG. As an R3 code capable of correcting up to double errors, one using a parity check matrix H as described below is known.

...(11) Here, α is, for example, the root of the primitive polynomial of cF (28). Also, n is the code length.

To perform decoding, first, in step 30, an error syndrome S is calculated. This is the received data R with code n
It is determined by the combination of the transposed matrix RT and the parity check matrix l-linox I-[. In other words, V fZl is the transmission code vector V (Zl = V Q■v1z■V2 Z2■V3
Z3■・・・・・・■V n-+z n-1...(3
)R(7,1 as reception vector Rfzl-rOC+r1 z■r2Z2■r3Z3■・
...■r yl-IZn' ...(4), the error pattern added in a noisy communication channel is e (z) = r (Z)■V (Zl-eQ■ eI
Z■e2Z2 ■・・・・・・■en-IZ" ...It can be expressed as (5). From equation (2), 5K=rO■r1 'ct K■r2(αK)2■r3
(αK)3■... ■r n-1'(αK)n-' ...(6) Therefore, from equations (5) and (6), 5K-V (αK)■e ( αK) ・(7
It becomes 1. On the other hand, αO9α1. α2. Since α3 is the root of the sign polynomial V (Z), it becomes ■(αK)−〇. Therefore, 5H=e (αK)...
-(8)e (If zl is an error pattern with two errors, the syndrome will be as shown in equation (9).

Error correction is performed using this el, eJ+ α1. This is done based on solving equations for αj. yl.

When αj is found, exponents i and j are e (indicates the error position of zl, and when el and eJ are found, e (indicates the error value of zl. Therefore, from the syndrome component Sl, ei, ej, αi , αj will be explained.

The error locator polynomial is defined as follows.

σ(Z)-(Z■αj)(Z■αj) =aoZ2■σIZ■ty2 = (10) Here, Equation (9) 1 Equation (11) is called a power-phase symmetry equation, and the following Can lead to relationships.

Using equation (12), the error locator polynomial σ1. σ2 can be determined (step 31.
32). Here, the root (αi
, α3) can be obtained by some method, the error values ei and eJ can be obtained as follows (step 33).

As mentioned above, once the root of the error locator polynomial is found, the formula (1
3), the error position and error value are determined, and the decoding can be completed using equation (5) (step 34).

Here, the data (Chien) method devised to find the root of σfZl [Reference: R, T, Chien
;CyclicDacordingProceded
are for the Bose-Chaudhur
iHocquenghem Codes, IEIEE
Trans, on InformationThe
ory+ I↑-10, PP 357-368. Oc
T, 1964) will be explained.

In formula 00), σ1/σ2−η1. σO/σ2−η
If it is 2, then 1. 7 tz+ = 1■η1z■η2Z2 −
It can be transformed as (14).

Assuming that α/(0≦β≦n-1) is the error position, the following equation holds true.

σ(α71)=1■η1αl■η2α2p-0...(
15) From this equation, in the decoder, η1αl, η2α2! 1, and calculate the sum η1αp■η2α21 (16). If this sum becomes 1, αR becomes σ(7, 1
is the root of and indicates the error location. Therefore, the method of data is the value considered as the error position (α0.αl.

α2. ..., αn-1) into σ(21,
In this method, if σ(Zl=0) is satisfied, it is determined that the inserted value is an error position.

FIG. 3 shows hardware for calculating error positions using the data method. In the figure, 1 is a microphone coprocessor that performs data output, data processing, control, etc., 2 is a data bus for the microprocessor sensor, 3 is a control bus for the microprocessor sensor, 4.5 is a 2-manpower selector, and 6. 7 is a register, 8 is an α multiplier, 13 is an α2 multiplier, 1° is a three-man exclusive logic adder, and 11 is a zero detector.

To explain the operation in order, 1) Selector 4 is activated by a control signal from microprocessor 1.
, 5 to the A sub-input.

2) Input the above-mentioned η1 from the microprosensor via the data bus 2 to the register 6 from the A sub-input of the selector 4, and use the control signal from the microprosensor to input η1.
Hold 1 in register 6.

3) The microprocessor inputs the above-mentioned η2 via the data bus 2 into the register 7 from the A sub-input of the selector 5, and the control signal from the microprocessor sensor inputs η2.
2 is held in register 7.

4) Selector 4 with control signal from micropro sensor
, 5 to the B sub-input.

5> Output of register 6, output of register 7, and “
1'' is calculated by the exclusive logical adder 10.

6) The output of the exclusive logic adder 10 is input to the zero detector 11 to determine whether it is zero or not, and the result is notified to the microprocessor 1 via the control bus 3.

7) The output of the register 6 is multiplied by α by the α multiplier 8, and this is held in the register 6 via the B sub-input of the selector 4 by the control signal of the microprocessor 1. At the same time, the output of the register 7 is multiplied by α2 by the α2 multiplier 13, and held by the control signal of the microprocessor 1 through the B sub-input of the selector 5.

This process is 5→6-7-5-6→7→・・・・・・−
5-6, the code length is repeated n times. Inside the microprocessor I, the number of repetitions and the signal from the zero detector 11 at that time are monitored, and the number of repetitions when zero is detected is determined to be the error position.

[Problem that the invention seeks to solve]

Since a conventional decoder using Dane's method is configured as shown below, it is necessary to perform repeated calculations for the code length n times in order to calculate the error level M, which reduces the decoding time, etc. If there is not enough room, it is necessary to reduce the number of repeated operations, and simply trying to reduce the number of repeated operations has the problem of increasing the scale of the hardware. .

This invention was made to solve the above-mentioned problems.The scale of the hardware is exactly the same to calculate the error position, and the number of repeated operations is half the code length (if n is an even number). In case n/2゜In case of odd number (n-1)/2
The objective is to create a dual error correction decoder that can be implemented in (M).

[Means for solving problems]

In the double error correction decoder according to the present invention, when determining the root of an error locator polynomial, the value of the coefficient σ2 of the polynomial is subjected to simple preprocessing to reduce the value considered as the root of the polynomial by half. A processing operator stage and each value obtained by the calculation means are repeatedly multiplied, and each value is subjected to exclusive logical addition to detect whether or not the addition result is zero until it becomes zero. Error position detection means for determining the double error position based on the number of repetitions of .

[Effect]

In this invention, the number of possible roots of the error locator polynomial is reduced by almost half through preprocessing, so it can be performed with half as many iterative operations as before to find the error locator, and the decoding time is significantly reduced. Ru.

〔Example〕

Here, before explaining the present invention in detail, its principle will be explained.

Since the code length is n, the following relationship exists between i, j, and n.

0≦i≦n-1, 0≦j≦n-1 (17) FIG. 4 is a diagram showing all #He7j combinations of i and j based on this relationship. The intersection of 1 and j indicates the value of i→-j. The coefficient σ2 of the error locator polynomial can be considered from equation (11) as follows.

σ2-α1・αj-αi+3 ...(18
) In other words, i+j can be found from σ2. The meaning of the combination table of i and j in FIG. 4 is to clarify the range of existence of i and j by giving i+j. By the way, as explained before, α
1. Since αj are two different roots of the error locator polynomial (]0), the range i−j is i.

It is outside the range of j. Also, the combination of i and j is
There is no problem even if the value of i and the value of j are exchanged.

Therefore, the hatched portion of the triangle in FIG. 4 is the actual range of '+J' combinations.

For example, when i+j is 1, the combination (t, j) is (
1, 0), 1 set when i+j is 2 (2°0),
..., when j→-j is 5 (5, 0).

(4, 1) (3, 2> 3 sets, etc.), the combinations of '+ J are determined. Among these, the one with the most combinations is i+j, which is n-1. In this case, the number of combinations is as follows.

From these facts, given σ2, (i.

The number of combinations of j) can be narrowed down to the maximum value shown in equation (19).

Next, a method for selecting one set from these combinations will be described. The principle is the same as Dane's method explained earlier, and if all combinations of (t, j) are substituted and the following formula is satisfied, then (i, j) becomes the root.

σ1−αl■αj ...(11)
Transforming 'Equation (11)', αj αj 1−□+□ ...(20)σ 1
The same holds true even if the formula for σ 1 is satisfied. However, in the present invention, the maximum number of combinations that can be considered is equation (19), which is reduced by half compared to Dane's method.

This processing method will be explained using the preprocessing flow diagram shown in FIG. 5 and the principle diagram shown in FIG. 6.

Next, in step 35, the cases are determined depending on whether i+j is larger or smaller than n-1, and the values of Ll and Lj are determined. These Ll and J serve as initial values for the iterative calculation shown in FIG. For example, if j+j is smaller than n-1 and is 5, in step 37 Li =5. 1-3=0. Also, if j→=J is n, in step 36 Li
=n-1,,Lj-1. Once Li and Lj are determined, αLi and αL j conversion is performed, and further divided by σ1, αLi/σ1. Output αl·j/σ1.

In FIG. 6, 13.14 is a register, 15 is an α multiplier, 16 is a 1/α multiplier, 17 is an exclusive logic adder, 1
8 is a zero comparator. This circuit can be considered (i, j
) is a circuit that sequentially calculates equation (20). First, if it is not zero, αLi is 1/α
Multiply αL by α and calculate . If it is zero, the calculation ends; if it is not zero, the calculation continues. If the number of repetitions is Co, we find CO as follows. (23). The number of times of this repeated operation is the value shown by the highest expression (19). Once CO is determined, error positions i and j can be determined using the following equation.

Table 1 Table 1 shows i -1-j when i is plotted on the horizontal axis and j is plotted on the vertical axis.
indicates the value of Table 2 also shows the values of αl■αj when i is plotted on the horizontal axis and j is plotted on the vertical axis. Furthermore, Tables 3 and 4
, shows an X-αX conversion table and an αX-X conversion table necessary for calculation. Here, α is a primitive element of CF (2B), and X8■X4■X3■X2■1 is a generator polynomial, and from αo=1 to α, α2. α3.・・・・・・
It is an expression of

In Table 4, the zero element has the corresponding logarithmic expression (αX→X)
does not exist, so it is expressed as 255 for convenience.

Here, a read code capable of double error correction with code length n-16 is used.
Consider Solomon codes. If the error positions are the 3rd and 12th, the error position polynomial is as follows.

(Z+α3) (Z+α12) -Z2■ (α3■α12) Z■α3・α12-Z2■1
97Z■38 =Z2■σIZ■σ2 In an actual decoder, these σ1 and σ2 are given. Therefore, the error position is determined based on the principle of the present invention.

From σ2-38, 38-αi+l, therefore 1-1-j=1
5 If calculated according to the preprocessing flow shown in Figure 5, n-16
Therefore, Li = 15 and LJ = 0. Next, repeat calculations are performed according to FIG. 6 (see Table 2).

First α1- ■αI last ■1=145■1≠0 1st time α1 light-1■α record 4■1 = 247■1≠
0 2nd time α11-2■αt31"λ■1=151■
1≠0 1st=th α4q−3■α1313■1-1■1
It can be seen that when the number of -0 repetitions Go=3, equation (23) is not satisfied. From this, by substituting each numerical value into equation (24), i = 15-3 = 12 j = O+ 3 = 3, and the error position 3.12 can be found.

FIG. 1 shows a specific hardware embodiment of a decoder constructed based on the principle of the present invention. In the figure, the third
The same reference numerals as in the figure indicate the same or equivalent parts], and 9 is 1iU.
It is a multiplier.

The operation of this embodiment will be briefly described as follows: 1) A control signal from the microprocessor 1 sets the selectors 4 and 5 to the A side input.

2) Input the above-mentioned (αL 1 ) /σ1 from the microprocessor sensor 1 via the data bus 2 to the register 6 from the A side input of the selector 4, and use the control I roll signal from the microprocessor 1 to input (αLi) /σ1. Poll σ1 to register 6.

3) Input the above-mentioned (αLi)/σ1 from the microprocessor 1 to the register 7 from the A side input of the selector 5 via the data bus 2, and input (αL l )/σ1 to the register 7 using the control signal from the microprocessor 1. Hold on.

4) Selector 4 with control signal from microprocessor 1
, 5 to the B side input.

5> The output of register 6 and the output of register 7, and roughly “
1'' is determined by the exclusive logical adder 10.

6) The output of the abstract logic adder 10 is input to the zero detector 11 to determine whether it is zero or not, and the result is notified to the microprocessor 1 via the controller 3.

7) The output of the register 6 is multiplied by α by the α multiplier 8, and this is held in the register 6 via the Bff1l+ input of the selector 4 by the control signal of the microprocessor 1. At the same time, the output of register 7 is converted to 1i by 1iU multiplier 9.
This is multiplied by U and held in the register 7 via the B-side input of the selector 5 by the control signal of the microprocessor 1.

This process is 5→6→7-15→6→7→・・・・・・→
5-6 and the number of times shown in equation (19) are repeated.

Furthermore, the microprocessor 1 monitors the number of repetitions and the signal from the zero detector 11 at that time, and calculates the error position using equation (22) from the number of repetitions when zero is detected.

In this embodiment, when finding the root of the error locator polynomial, simple preprocessing is performed to reduce the number of possible roots by half, and the calculation is performed repeatedly. With this configuration, it is possible to significantly shorten the decoding time.

In addition, in the embodiment mentioned above, a case was explained in which data input/output was controlled using a microprocessor, but data input/output may also be controlled by dedicated hardware (similar to the above embodiment). It has the effect of

〔Effect of the invention〕

As described below, according to the present invention, when determining the double error location, instead of substituting all n values that can be considered as roots of the error location polynomial, the coefficient σ2 of the polynomial is used to easily calculate the double error location. After preprocessing, the possible root value is halved to n/21 (n: even number.

If n is an odd number, reduce to (n-1)/2(1iU),
Since it can be executed with half the number of repetitions compared to conventional methods, it has the effect of significantly shortening decoding time.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing a dual error correction decoder according to an embodiment of the present invention, FIG. 2 is a flowchart showing the procedure of a general) summer issue, and FIG. 3 is a block diagram showing a conventional decoder. , FIG. 4 is a diagram showing a combination of error positions for a detailed explanation of the present invention, FIG. 5 is a flowchart diagram showing a preprocessing part of the present invention, and FIG. 6 is a diagram for a detailed explanation of the present invention. FIG. 2 is a block configuration diagram. 1... Microprocessor, 2... Data bus, 3
...Control bus, 4.5...Selector, 6.
7...Register, 8...α multiplier, 9...1iU
Multiplier, 10... Exclusive logic adder, 11... Zero detector. Note that the same reference numerals in the figures indicate the same or equivalent parts.

Claims (1)

[Claims] (1) In a Reed-Solomon code decoder with a code length n that is capable of double error correction, it has an arithmetic function on a Galois field and has 2
The following error locator polynomial Z^2■σ_1Z■σ_2(
(2) is the exclusive OR), and calculates i+j from the coefficient σ_2 of , Lj=0 r_1=αLi/σ_1, r_2=αLj/σ_2] However, αi+j=σ_2, αi■αj=σ_1i, j: error position, α: preprocessing calculation means for performing the root operation of the primitive polynomial; Operation result r_
1, the first and second registers storing r_2, this first
a first multiplier that multiplies the value of the register by 1/α;
a second multiplier that multiplies the value of the register by α; an adder that calculates the exclusive OR of the contents of the first and second registers and the three values of the numerical value 1; and whether or not the addition result is zero. It has a zero detector that determines whether the 1. A double error correction decoder comprising: error position detection means for determining a double error position i=Li−Co j=Lj+Co from the number Co.