JP2722553B2 - Error correction decoder - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to an error correction decoder for decoding a Reed-Solomon code.

[Conventional technology]

Conventionally, there has been an apparatus of this type as shown in FIG.

This figure shows Hideo Yoshida, Toru Inoue, Atsuhiro Yamagishi, Toshihisa Nishijima,
Yoshiaki Oda, Minoru Ozaki, "A Study on Decoding Method of RS Code Using Galois Arithmetic Unit" (Refer to the 9th Information Theory and its Application Symposium Proceedings, Volume I, P.169) In the figure, (1) is a control circuit, (2) is a syndrome generation circuit that calculates and generates a syndrome from a received word, (3) is a Chien search circuit, and (3a) is an error locator polynomial. A polynomial evaluation circuit unit for performing an error search by performing a Chien search, and (3b) is an element α- ^(nk-1) (n is a code ^{) of} a Galois field corresponding to the error position k obtained by the polynomial evaluation circuit unit (3a) The length and α are Galois field element generation circuits for converting into primitive polynomials. (4) obtains an error position polynomial and an error value polynomial from the syndrome generated by the syndrome generation circuit, and generates a Galois field element and an error value corresponding to the error position obtained by the Galois field element generation circuit (3b). A Galois field element arithmetic circuit that calculates an error value from a polynomial and corrects the error, (6) a modem that demodulates a received word, (5) reads a received word from the modem (6), and reads out the syndrome generation circuit (2) And (8) a buffer memory which reads the error position obtained by the polynomial evaluation circuit (3a) and outputs it as an address of a Galois field element conversion ROM in order to convert the error position into a corresponding element on the Galois field. Is a microprogram ROM for storing signals of the control circuit (1), and (16) is a bus.

The control circuit (1) issues a command to another circuit by sending a control signal to the other circuit, and performs an interface with the other circuit.

Next, the operation will be described. First, a received word is stored in the buffer memory (5) from the modem (6). The received word is read from the buffer memory (5) by a signal from the control circuit (1), and the syndrome corresponding to the received word is calculated by the syndrome generation circuit (2). An error locator polynomial and an error numerical polynomial are obtained from the syndrome by a Galois field element arithmetic circuit (4). A polynomial evaluation circuit (3a) of the Chien search circuit (3) performs a Chien search from the error position polynomial to determine an error position. Then, the Galois field element generation circuit (3b) calculates the Galois field element α- ^(nk-1) corresponding to the error position k obtained by the polynomial evaluation circuit (3a) as shown in FIG. Convert. The Galois field element arithmetic circuit (4) calculates the error value again from the Galois field element α ^{− (nk−1)} and the error numerical polynomial, and corrects the error. The corrected code is read into the buffer memory (5) and output to a host (not shown) by a signal from the control circuit (1).

In the Galois field generation circuit (3b), the Galois field conversion RO
Converted by M. FIG. 5 shows an example of the contents of a Galois field conversion ROM disclosed in Japanese Patent Application Laid-Open No. 62-115928.

[Problems to be solved by the invention]

Since the conventional error correction decoder is configured as described above, when performing error correction processing on a variable length Reed-Solomon code, the Galois field corresponding to the error position in the variable length code has a code length. In order to convert to a sound on the Galois field and to perform error correction based on the element of the Galois field, separate Galois field conversion RO according to the code length
Since M or the like must be used, there is a problem that the device becomes large and decoding processing is excessively performed.

SUMMARY OF THE INVENTION The present invention has been made to solve the above problems, and has as its object to provide an error correction decoder that can be downsized and that can perform high-speed decoding.

[Means for solving the problem]

An error correction decoder according to the present invention includes: a syndrome generation circuit (2) for calculating a syndrome from a received word; a polynomial evaluation circuit (3a) for determining an error position based on an error position polynomial obtained from the syndrome; Storage means (5) for storing the value of (n-1) for the code length n of the received word; and an error position obtained by the polynomial evaluation circuit is subtracted from the output of the storage means. On the other hand, a subtraction circuit (7 ⁾ for converting into a corresponding Galois field element α ⁽⁻ⁱ⁾ , an error position polynomial and an error numerical polynomial are obtained from the syndrome of the syndrome generation circuit, and the element of the Galois field from the subtraction circuit is obtained. A Galois field element arithmetic circuit (4) for obtaining an error value from α ^(-i) and an error numerical value polynomial and performing error correction is provided.

[Action]

In the present invention, the error position and the element of the corresponding Galois field are matched by the subtraction circuit, so that the variable-length Reed-Solomon code can be converted into the element of the Galois corresponding to the error position. Error correction can be performed based on

〔Example〕

An embodiment of the present invention will be described below with reference to the drawings. In FIG. 1, (1) is a control circuit, (2) is a syndrome generation circuit, (3a) is a polynomial evaluation circuit, (4) is a Galois field element arithmetic circuit, (5) is a buffer memory, and (6) is a modem. , (8) is a microprogram ROM, and (16) is a bus, which are the same as those in the conventional device shown in FIG. (7) is a subtraction circuit, the details of which are shown in FIG. Second
In the figure, (9) is a value of “a possible value of code length−1”,
For example, when possible values of code length of _{n 1, n 2 ... n m} n 1 -1,
A register in which m values of n ₂ -1,..., n _m -1 are stored. (10) is received by a control signal (15) from the control circuit (1) according to an instruction of the microprogram ROM (8). The data of the register (9) corresponding to the code length of the word is, for example, n
Selector for selecting a ₁ -1, (11) a selector (109
From the data of the selected register (9), the signal line (1
4) A subtractor which subtracts the data k at the error position obtained by the Chien search circuit (3a) inputted from 4), calculates i = (n ₁ -1) -k, and outputs the result. This is a Galois field element conversion ROM that converts the output i into a corresponding Galois field element α ⁽⁻¹⁾ and outputs the result.

The operation of the device configured as described above will be described next.

First, a received word is input to the modem (6), demodulated, and stored in the buffer memory (5). The received word is read out from the buffer memory (5) by a signal from the control circuit (1), and a syndrome corresponding to the received word is calculated by the syndrome generation circuit (2), and the Galois field element operation circuit (4) is calculated from the syndrome. The error locator polynomial and the error numerical polynomial are obtained in (). A polynomial evaluation circuit (3a) performs a Chien search from the error position polynomial to find an error position k, which is input to a subtracter (11) of a subtraction circuit (7) via a signal line (14). On the other hand, in accordance with an instruction from the microprogram ROM (8), data (n-1) of code length n corresponding to the received word is stored in the register (9) by the signal (15) from the control circuit (1).
Is selected by the secretor (10) from the subtractor (11)
Is input to The subtracter (11) subtracts the data k at the error position from the data in the register (9), and i = (n-1)-
Calculate and output k. The output i of the subtracter (11) is converted into a corresponding Galois field element α ⁽⁻ⁱ⁾ by a Galois field element conversion ROM (12) and output. Then, the error value is calculated again from the Galois field element α ⁽⁻ⁱ⁾ and the error numerical polynomial in the Galois field element arithmetic circuit (4), and the error is corrected. The corrected code is read into the buffer memory (5) and output to a host (not shown) by a signal from the control circuit (1).

When the code length is n and the error position is k, the element of the corresponding Galois field is α- ^(nk−1) , but when the code length changes to m, the position of the address represented by the element of the Galois field becomes the As shown in FIGS. 3 (b) and (c), | m−n |

In the above embodiment, the decoding of the Reed-Solomon code having the code length previously stored in the register (9) has been described. However, as shown in FIG. 6, the selector (10) is removed from the subtractor and the resistor (9) is used instead of the resistor (9). Micro program
Similar effects can be obtained by using a register (13) that can be rewritten by a control signal (15) in accordance with an instruction from the ROM (8).

In the above embodiment, the variable length Reed-Solomon code has been described. However, it is needless to say that the present invention can be applied to a fixed length Reed-Solomon code.

〔The invention's effect〕

As described above, according to the present invention, when performing error correction processing on a variable-length n Reed-Solomon code, the value of (n-1) stored in the storage means and the error position obtained by the polynomial evaluation circuit ( K) and subtraction output (i =
n−1−K), the element α ⁽⁻ⁱ⁾ of the corresponding Galois field is found, and an error value is found from the found α ⁽⁻ⁱ⁾ and the numerical polynomial, and error correction is performed. The element of the Galois field corresponding to the long error position can be obtained instantaneously and easily.

Therefore, the amount of memory used for the error correction processing is reduced, the configuration can be made inexpensively and compactly, and the decoding time can be shortened.

[Brief description of the drawings]

FIG. 1 is a block diagram of an error correction decoder showing an embodiment of the present invention, FIG. 2 is a block diagram showing a subtraction circuit, and FIG. 3 is a diagram showing positions and positions of Reed-Solomon codes for explaining the principle of the present invention. FIG. 4 is a block diagram of a conventional error correction decoder, FIG. 5 is a diagram showing an example of the contents of a conventional Galois field conversion ROM, and FIG.
The figure shows a subtraction circuit of another embodiment. In the figure, (1) is a control circuit, (2) is a syndrome generation circuit, (3) is a Chien search circuit, (3a) is a polynomial evaluation circuit section, (3b) is a Galois field element generation circuit section, and (4) is Galois field element arithmetic circuit, (5) buffer memory, (6)
Is a modem, (7) is a subtraction circuit, (8) is a microprogram ROM, (9) is a register, (10) is a selector, (11)
Is a subtraction circuit, (12) is a Galois field conversion ROM, and (13) is a rewritable register. In the drawings, the same reference numerals represent the same or corresponding parts.

Claims (1)

(57) [Claims] An error correction decoder for correcting an error of a Reed-Solomon code defined on a Galois field, a syndrome generation circuit for calculating a syndrome from a received word (2).
And a polynomial evaluation circuit (3a) for obtaining an error position based on the error position polynomial obtained from the syndrome
And a storage means (5) for storing a value of (n-1) for the code length n of the received word, and subtracting the error position obtained by the polynomial evaluation circuit from the output of the storage means. i, a subtraction circuit (7 ⁾ for converting to a corresponding Galois field element α ⁽⁻ⁱ⁾ , an error locator polynomial and an error numerical polynomial are obtained from the syndrome of the syndrome generation circuit, and the Galois field from the subtraction circuit is obtained. An error correction decoder comprising: a Galois field element arithmetic circuit (4) for obtaining an error value from the element α ⁽⁻ⁱ⁾ and an error value polynomial and performing error correction.