JPS6034137B2 - Reed-Solomon code decoding method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to an error correction decoding method using Reed-Solomon codes.

Reed-Solomon codes are one of the most powerful error correcting codes currently known for correcting random errors.

Regarding Reed-Solomon codes, North America. Holland Publishing Company (NORTH)
HOLLAND PUBLISHI
F.J. MACWILLl published in 1978 by NGCOMPANY
AM) N.J.A.S.
THE THEORY OF ER
ROR CORRECT INCDODES).

Since this code is a type of cyclic code, its encoding can be realized relatively easily using a well-known cyclic code encoder, but its decoding requires a general conventional method. This has the disadvantage that the device becomes very complex and the error detection ability of the code itself is not fully utilized.

The object of the present invention is to eliminate these drawbacks of the prior art.

The method of the present invention is based on code length N (where N' is a positive integer larger than M) generated from a generator polynomial formed by the product of M (where M is a positive integer) first-order polynomials. Receive a Solomon code, calculate M syndromes So, S, . . . , SM-, for the received code, and calculate the syndrome.
This method corrects the error when it detects that an error of only one symbol has occurred in the received code based on the syndrome, and outputs error detection information when an error of two or more symbols is detected. ,S,,...,SM-
・More M-1 syndrome ratios S.・S61, S2・
Stl,...,SM-.・Syndrome ratio information calculation means for calculating information corresponding to 2 in S; syndrome ratio information comparison means for determining whether all the information corresponding to the syndrome ratios are equal;
syndrome all-zero determination means for determining whether all of the syndromes o, S, , ..., SM, are "0"; Syndrome all-zero determining means for determining whether one "0" syndrome is included; responsive to the output of the syndrome ratio information comparing means; the output of the syndrome all-zero determining means; and the output of the syndrome zero detecting means. When it is decided whether or not to perform correction according to a predetermined algorithm, and when correction is performed, error correction is performed for the symbol at a position determined by the previous word-self sisodrome ratio in the block using the syndrome So as error correction information. and correction means.

Next, the present invention will be explained in detail with reference to the drawings.

FIG. 1 is a block diagram showing one embodiment of the present invention. This embodiment includes a syndrome calculation circuit 1, a syndrome ratio calculation circuit 2, a syndrome ratio comparison circuit 3, a syndrome all-zero determination circuit 4, and a syndrome all-zero detection circuit 5.
, a correction execution control logic circuit 6 and an error correction execution circuit 7. Now, before explaining the details of the operation of this embodiment according to this block diagram, the principle of operation will first be explained. In general, lead so.

In the Mon code, N symbols constitute one code block, and this one code block includes M test symbols and NM information transmission symbols. There are various types of symbols used here, but in this embodiment, it is assumed that they are 8-bit code vectors, which are generally widely used. In order to make the explanation more concrete, it is assumed that the number of symbols (code length) in one code block is N=32, and the number of test symbols in one code block M=4. Therefore, the number of information transmission data symbols in one code block is N-M=28. Now, each of the 32 symbols in one code block is expressed as Mr., B, . B2, &, B4
,...,B3,.

Any Bj is a 1-byte sign, so zo=25
It is expressed as one element out of six elements. Furthermore, it is assumed that 28 of these symbols B4 to & are symbols for information transmission data, and the remaining Bo to & are test symbols created based on these B4 to B3. Now, in the Reed-Solomon code, in the encoding process, the test symbol ~B3 is created so as to satisfy the following constraint relationship between the information transmission data symbols B4~B.

That is, in this '1} formula, in addition to the symbol Bj of each symbol, the symbol Q is used, and the operation of the sum connected by tens, the product between Qs (the curtain of Q), and the Jo and B
An operation of multiplying by i is used. This Q represents a specific symbol, and the above-mentioned sums and products also mean special operations different from general binary sums and products. This will be explained below. As described above, in this embodiment, both Bj and Q are code vectors made up of 8-bit "1" and "0" codes. Therefore, each represents one element in zo = 25 needles. Now, select any two elements A and B from among these 25 elements, and both the element A+B specified by the sum of these two elements and the element AB specified by the product of the two elements. Assuming that it is one of the 25 needles, each of them is defined as follows.

Ten 0: As shown in FIG. 2, elements A and B are represented in the form of code vectors, and the code vector resulting from exclusive OR of each digit (each dimension) is defined as A+B.

Because the sum operation is defined in this way, the sum of two same elements is always “0” (a sign vector whose components in each dimension are all “0”), and the difference operation is the inverse calculation of the sum. yields the surprising result that it is the same as the sum operation. product:
For example, if there are elements A and B as shown in Figure 3,
Let this be a polynomial representation of x A=10×20zu×5 B=x20も, and the product AB of this polynomial is AB ni(10×20×30×5)(ten×4) NiX2 (
Make +X4) ten x five ten and ten (X7 ten x seven) ten.

In this, terms of the same power of x are of the same digit (
dimension), so if we apply the above-mentioned exclusive OR rule and rearrange, the above equation becomes AB=da+×60×50×2.

Since this polynomial includes more than seven terms of x (that is, terms of ゞ), it is not possible to specify an 8-bit code vector corresponding to it as is. Therefore, when defining the product, an irreducible polynomial f(x) of degree 8 is used.
is determined in advance and defined as follows using this.

Assuming that this f(x) is f(x)=zu1, 10×30×11, the AB polynomial is divided using this f(x), and the resulting remainder is generated.

In this case, the remainder will necessarily be a polynomial of degree 7 or lower than x, and therefore an 8-bit code vector will exist corresponding to this. This is defined as product AB. In this case, the quotient obtained by dividing the AB polynomial by f(x) is x, and the remainder is , subtraction and addition are the same).

From this, AB=ゞ10×40×, and when this is expressed as a code vector, it becomes as shown in FIG. 32.

As described above, when the 8th order irreducible polynomial f(x) is specified, the sum and product are defined between each of the 25 elements, and the difference and quotient are also defined as their inverse calculations. ,
The four arithmetic operations are performed without contradiction within the 25-point element.

Now, by appropriately selecting the irreducible polynomial f(x), all 256 elements except "0" (an element in which all digit components are "0") among the elements of the 25 orbital solid , a certain former Q
It can be expressed in the form of a power of .

In other words, the elements generated by taking 1 as the identity element and then multiplying it by Q, Q, Q2, Q3...Q255
can be made to cycle through all the elements except for the above-mentioned "0" and return to the identity element 1 again at Q255. Actually, as the irreducible polynomial f(x), f(x) is 2, 10 and 3
If we use 10
55).

However, Q0=Q255=1. This Q is called a primitive element, and the polynomial f(x) having such properties is called a primitive polynomial. It is known that 8th-order primitive polynomials having such properties, including the above-mentioned ones, have a single point.
In this embodiment, it is assumed that operations between elements are defined by a specific one of these 16 primitive polynomials, and the primitive element Q defined by this is used. As a result, any element other than 0 is expressed as Qj (where j = 0, 1, 2, ..., 254),
Therefore, any element can be specified using only the index i. We will call this the original exponential representation. Using this exponential representation, the product of any two elements except “0” is
By taking the exponential expression of each element and adding both of them modulo 255, it is possible to easily calculate the exponential expression of the product of both. If one element contains "0", the element of the result may be set to "0". In addition, when creating a quotient, take the binary number in the original exponential representation that becomes the denominator, invert the "1" and "0" of each digit, and then 2555 as described above.
Just add it as a modulus. Of course, when calculating the sum of two elements, it can be easily performed using code vector representation.

In this way, each element can be specified as a power of Q, an exponential representation of Q, a code vector representation, or a polynomial representation.

Which of these expressions to use can be selected depending on the purpose of use. Now, the operation of the '1-expression has been defined in this way, but in reality, it is necessary to generate the test symbol ~B3 that satisfies the constraint condition of the {1} expression from any information transmission data symbol B4~&, is as follows. Now, as the generator polynomial g(X), g(X)=(×-1)(X-Q)(×-Q2)(X-Q
3) and define C(X) as a one-sided sign polynomial C(X).
2BIX310B3〆arc+...10B4×4 is defined.

The polynomial of the remainder obtained by dividing this C(X) by g(X) is R(×
), R(x) becomes a cubic or lower polynomial with respect to x, so R(X)=X30QX20b,
It can be expressed as X+bo.

When b3, Q, b, and bo determined in this way are used as test symbols B3, B2, B, and Bo, respectively, these become test symbols that satisfy the constraint condition of formula [1} for the following reason. There is. Now, convert C(X) to g(×)
The quotient divided by is written as Q(×), then C(X):g(X)Q
(X)+R(X), and from now on, C(X)+R(×
)=g(X)Q(X〉 is derived (also in this case R(×)
subtracting is the same as adding R(X)). Therefore, C(×) ten R(×) is divisible by g(×), &I
X31 ten B3 〆Yanagi ten... ten B4 x 40 B3 x 30 QX2
Ten B, X+B.

d(X-・)(X-Q)(X-Q2)(X-Q3)Q(
×) holds true.

1, Q, Q2 and Q3 on both sides of the above equation, respectively
By successively substituting , the relationship of equation '1' is derived. Furthermore, when the generator polynomial g(X) is given,
Execute the above division to obtain B from the symbols B4 to B3.
It is also easy to determine the configuration of a cyclic code encoder that generates symbols o to B3, but this is omitted here.

Now, the blocks Bo, B, B2, etc., which satisfy the constraint condition of the '1} formula created on the sending side as described above, are
・,B3, are received, and they are Bo,B,B2,...
・Assume that it is received as &.

It is assumed that an error occurs in only one symbol Bi among them. In other words, for a value other than j, B
k=Bk """{2' holds true, and for Bi Bj=Bj + Ej
"""[3'.

However, Ej is assumed to be an error occurring in the j-th symbol. Now, on the receiving side, the received symbols Bo, B, B2,
......, &. Using , perform the operation corresponding to the left side of each expression in the '1} expression, and calculate the results by S. S2S
Set it to 3.

That is, let it be.

If there is no error in reception, the left side of equation '4} is m
It is exactly the same as the left side of the equation, so So to S3 should all be "0". If there is an error in reception, the operation results corresponding to the left sides of equation '4' will generally take non-zero values So, S, , S2, and S3.
This is called a syndrome. The present embodiment uses the syndromes So to S3, and corrects the error by determining the error amount from the constraint calculation relationship of the '1} formula added between symbols in the -block on the transmitting side. Now, by substituting the relationship of formula (2) and formula (3) into formula (2) and using the relationship of m, the result is as follows.

By transforming this equation (2), the following four equations are derived.

Now, it is also possible to perform error correction using only So and S using the above equations [6' and (7}).

In other words, the error symbol position i can be found using S and So from equation (2), and the error correction information Ej can be obtained from equation (2) using So. (Exclusive OR is performed for each digit of the 8-bit symbol according to the above-mentioned rules.) However, in this embodiment, with a relatively simple circuit configuration, it is possible to perform error correction using not only the above-mentioned So and S, but also all the obtained syndrome information So to S3. This further improves the reliability of error correction. Next, details of the operation of this embodiment will be explained using FIG.

The code block of the received input signal is from the data input line 100, with each symbol being B3,,B3. ，・・・・
. . , B are supplied to the syndrome calculation circuit 1 in this order. At the same time, it is also supplied to the error correction execution circuit 7.
In circuit 1, the operation corresponding to formula 4 is executed, and sind. The rules So, S, , S2 and S3 are found. Among them, an example of an arithmetic circuit for calculating, for example, S is shown in the fourth section.
As shown in the figure. This consists of a one-stage shift register 10, a read-only memory (ROM) 11, and an exclusive OR circuit 12.
It consists of Shift register 0 and circuit 12 each process 8 bits in parallel. Also ROMII
has 256 memory addresses that can be addressed by the output (8 bits) of the shift register 10, and each memory address has a capacity to store 8 bits of data. ROM specified by the output of shift register 10
Data is read from the memory address of circuit 1.
2, an exclusive OR with the input data is taken, and this is read into one shift register. If you write QA' (however, QA' is the product of the code vector corresponding to this binary number A' and the primitive element Q) to the ROMII memory address specified by an arbitrary 8-bit binary number A', then ,
ROMI I operates as a Q multiplier. Thus,
First, the shift register 10 is reset, and the input data is inputted through the circuit 12 in the order of Ma, Byanagi, Bo, etc., as described above, and when Shame is input,
The contents of the shift register 10 are
,Q+&o)Q+un9)Q+...10B)Q+B.

NiQ's B's 10Q Mr.30.

Ten... ．． 、． ．． Ten QB ten B.

=S, and the desired syndrome S is obtained.

Change the contents of ROMII to Q2 and Q instead of Q above.
3, it is possible to obtain a circuit that calculates the syndromes S2 and S3 using similar circuits, and by feeding back the contents of the shift register 10 as is to the circuit 12 except for ROMII, it is possible to solve the syndrome So. A circuit for calculation is obtained. The syndromes So to S3 thus obtained are supplied to the syndrome ratio calculation circuit 2, the syndrome zero determination circuit 4, and the syndrome zero detection circuit 5, and So is
It is supplied to the correction execution circuit 7 via the correction execution control OR circuit 6 as Ej in the equation.

Now, in the syndrome ratio calculation circuit 2, the preconception 7}
By performing calculations on the expressions ``8'' and ``9}, the exponent expression j of Qj is obtained separately from each expression.

Now i obtained from equation '7}, equation {8) and equation '9}
are written as i' and i'', respectively. Fig. 5 shows an example of the syndrome ratio calculation circuit 2. The supplied syndrome S.
S61 = k that satisfies Qk (any So other than ``0''
can be expressed as Qg using Q, but using this g, (k+g
) which satisfies MOD255=0, that is, the inversion of each bit of g). ROM20 is 256
Each memory address has a capacity of 1 byte, but a memory address specified by an arbitrary binary number A'' stores the complement of b with the relationship A''=Qb. The above-mentioned conversion from So to k is executed by setting S, to k.Meanwhile, the supplied syndrome S, is converted by the read-only memory ROM22 into an exponential expression 1 that satisfies the relationship S,=QI.The ROM22 is ROM2
By storing b, which has the same capacity as 0 and has the relationship A'=Qb, in a memory address specified by an arbitrary 8-bit binary number A'', the conversion of S,→1 can be performed. In this way, S61 is converted into an exponential representation, k, and S, is also converted into an exponential representation, 1,
is supplied to the MOD255 adder 21 and the MOD255 addition is executed. - An index representation j' of S; 1 can be obtained.

S2, Stl and S3 corresponding to formula [8} and formula ■
- The index expressions i'' and j river of S summer 1 can be calculated in exactly the same way.For example, when calculating i'', S
An exponent representation of 1 is required, but this can be easily obtained by inverting each bit of the number representation 1 of S, obtained in the ROM 22, using the inverter 23. Thus, using the ROM 22, the inverter 23, the ROM 25 and the MOD 255 power calculator 24, an index of S2,S;1 is obtained, and the ROM 25, the inverter 26, the ROM 28 and the MO
Using the D255 force o calculator 27, the index expression i-kawa of S3·Ski1 is obtained. In this way, the static arithmetic circuit that does not use any clocks in circuit 2 quickly and reliably calculates the exponential expressions i', j'' for expressions '7}, [8}, and {9} from So to S3.
and jW can be obtained. The J′,i″ and j rivers corresponding to the exponential expressions of these syndrome ratios are
The signal is supplied from circuit 2 in the figure to syndrome ratio comparison circuit 3. At the same time, j' (which may be either i'' or i skin) is supplied to the correction execution control OR circuit 6. Next, the syndrome ratio comparison circuit 3 This is a circuit that detects whether the values of '' and i... all match.

This includes, for example, a first circuit that takes an exclusive OR for each digit of j' and i'', a second circuit that takes an exclusive OR for each digit of i'' and j, and 1st and 2nd
It can be easily constructed using a circuit that performs the logical OR NOT of all (16 bits) of each output bit of the circuit. As is clear from the above equations '7}, '8}, and {9),
If there is one error, the values of i corresponding to the error symbol position obtained as described above are ′, i″ and i...
all match. Therefore, in this case, the circuit 3 outputs a coincidence output 300, which is supplied to the correction execution control OR circuit 6. On the other hand, as described above, the syndromes So to S3 are supplied to the syndrome all-zero determination circuit 4.

This circuit 4 is composed of an OR circuit that takes all logic zeros of each bit of all digits of So to S3, and an inverter that inverts the output. When all syndromes are "0" ( In other words, only when there is no error, a "1" logic level is generated and supplied to the correction execution control OR circuit 6 via line 400. Furthermore, the syndromes So to S3 are supplied to the syndrome zero detection circuit 5 as described above.

This circuit 5 generates a logic level of "1" when even one "0" syndrome is included in So to S3, and supplies this to the correction execution control logic circuit 6. This circuit 5 also calculates the logical OR of the outputs of the four logical sum negation circuits and the four logical sum negation circuits that perform the logical sum negation of each digit (8 bits) of the respective syndromes So, S, , S2, and S3. It can be easily configured with one OR circuit. Now, the correction execution control logic circuit 6 uses the various input signals supplied as described above to control execution of error correction through the following logical operations.

First, when the output 400 of the circuit 4 is "1", that is,
If all of the syndromes So to S3 are "0", it is assumed that there is no error regardless of the other input signals, and no error correction is performed. Further, the error flag output 600 for supplying the lower circuit from the circuit 6 is set to "0" to indicate that there is no error in this code block. If the syndromes So to S3 are all "0", the following control should be performed according to the relationship in equation {5). It is clear.
Next, when the output 400 of the circuit 4 is "0", the following occurs.

In this case, there must be an error, but if there is one error, S
o to S3 are not all "0". Also [9 [8], t
9} All j values obtained from the formula should be equal. When these conditions are met, the error correction information S of the '6} formula
Control may be performed to perform error correction on the j-th symbol using o. That is, only when the input signal 500 of the syndrome zero detection circuit 5 is "0" and the output 300 of the syndrome ratio comparison circuit 3 is "1", the signal is placed at the symbol position specified by the supplied j'. , is controlled to perform error correction using the supplied So as error correction information. In addition, in this case, the error flag output 600
is set to "0" to indicate that there is no error in this code block as a result of correction. If the above relationship does not hold,
That is, at least the output 500 is “1” (“0” is included in any of the syndromes So to S3), or
Or, if the output 300 is “0” (the values of d, j″, and j do not match), then ■, '7}, ■, and {9)
It is clear from the relationship in the formula that the condition that the number of errors is one does not hold true.

Therefore, in this case, no correction is performed, and the error flag output 6 indicates that an error is included in this block.
Set 00 to “1”. A logic circuit that performs the above-described control can be easily realized using, for example, the circuit illustrated in FIG.

However, reference numerals 60, 61 and 62 in FIG. 6 represent AND circuits, reference numerals 63, 64 and 64 represent inverters, respectively, and reference numerals 101, 300,
Each input/output line 400, 600, 600 and 601 represents the same as the corresponding referenced input/output line in FIG. Now, the error correction information Ej (So) subjected to the above control is supplied by the circuit 6 as an output 601, and the error symbol position information i' is supplied as an output 602 to the error correction execution circuit 7.

This circuit 7 receives data from a data input 100.

It has a buffer for storing the symbols &,, B iso, etc. for the number of symbols in the next symbol position. For the symbol officer j at the position specified by the error symbol position specification information i' in the symbols stored in this way,
Error correction is performed by adding the supplied error correction information Ej (So) using exclusive OR. After error correction, each symbol is supplied as an output 700 to the lower circuit together with the air flag output 600. In the above embodiment, in order to make the explanation concrete, the code length N is 32, the number M of check symbols in one code block is 4, and the number of bits K of each symbol is 8. The case where a Reed-Solomon code is used has been described in detail, but the method of the present invention uses N, M
It is clear that the values of and K are not limited to these. Furthermore, circuit examples for the various circuits used are shown as examples for realizing the circuits, and the present invention is not limited to these. As described above, when the present invention is used, one block is made up of N symbols, and one error occurring in the Serido-Solomon code is corrected, two or more symbols are detected, and an error flag is issued. , it is possible to provide a highly reliable decoding method that effectively utilizes information on all syndromes of up to M test symbols and achieves the objective with a simple circuit configuration.

This makes it possible to improve reliability and economy.

[Brief explanation of the drawing]

Fig. 1 is a block diagram showing an embodiment of the present invention, Fig. 2 is a diagram for explaining the sum operation used in this embodiment, and Fig. 3 1 is a diagram for explaining the sign polynomial for the operation used in this embodiment. 2 is a diagram for explaining the product calculation used in this embodiment, FIG. 4 is a diagram showing an example of the internal circuit of the syndrome calculation circuit of this embodiment, and FIG. 5 is a diagram for explaining the product calculation used in this embodiment. A diagram showing a circuit example of the syndrome ratio comparison circuit of the example and FIG. 6 are diagrams showing an example of a logic circuit in the correction execution control OR circuit of this embodiment. In the figure, 1... syndrome calculation circuit, 2
... Syndrome ratio calculation circuit, 3 ... Syndrome ratio comparison circuit, 4 ... Synd. Syndrome zero detection circuit, 6... Correction execution control logic circuit, 7.
...Error correction execution circuit, 10...Shift register, 11, 20, 22, 25, 28...Read-only memory (ROM), 12...Exclusive OR circuit , 21, 24, 27... Adder modulo 255 (MOD255 adder), 23, 26, 63, 64, 6
5... Inverter, 60, 61, 62... AND circuit. Hair' Figure 2 Figure 4 Figure 3 Figure 3 Figure 6

Claims (1)

[Claims] 1 Receive a Reed-Solomon code of code length N (where N is a positive integer greater than M) generated from a generator polynomial formed by the product of M (where M is a positive integer) first-order polynomials and M syndromes S_0, S_1 for received codes
, ..., S_M_-_1 is calculated, and if it is detected that an error of only one symbol has occurred in the received code based on the syndrome, the error is corrected, and if an error of two or more symbols is detected, error detection information is generated. In the method of outputting the syndromes S_0, S_1, ..., S_M_-_1
Then M-1 syndrome ratio S_1・S^-^1_0
,S_2・S^-^1_1,...,S_M_-_1・S
A syndrome ratio information calculation means for calculating information corresponding to ^-^1_M_-_2, a syndrome ratio information comparison means for determining whether all the information corresponding to the syndrome ratios are equal, and a syndrome ratio information comparison means for calculating information corresponding to the syndromes S_0, S_1,...
..., S_M_-_1 are all "0" or not; and the syndromes S_0, S_1, ..., S_M_-_1 include at least one "0" syndrome. Syndrome zero detection means for determining whether or not the syndrome ratio information comparison means is corrected according to a predetermined algorithm in response to the output of the syndrome ratio information comparison means, the output of the syndrome all zero determination means, and the output of the syndrome zero detection means. and error correction means for performing error correction using the syndrome S_0 as error correction information for a symbol at a position determined by the syndrome ratio in the block when determining whether or not to perform correction. Lead to
Solomon code decoding method.