KR100192790B1 - Device for calculating coefficient of error-evaluator polynominal in a rs decoder - Google Patents

Abstract

The invention leads to about the error evaluation coefficient calculation of the polynomial apparatus in Solomon decoder, Galois field multiplier for the output by multiplying the coefficients (σ _i) of the coefficients of the syndrome polynomial from the outside (S _i) and the error locator polynomial (10 )Wow; A galloise adder 20 for adding and outputting a value output from the galloise multiplier 10 and an intermediate value; A multiplexer (30) for selectively outputting a value output from the galloise adder (20) or a coefficient (σ _i ) of an error position polynomial input from the outside; And a shift register section 40 for shifting the value output from the multiplexer 30, inputting it to the galloche adder 20 as an intermediate value, and outputting as a coefficient Ω _i of an error evaluation polynomial. Therefore, since the coefficient estimator of the error evaluation polynomial is implemented without using a multiplexer and a demultiplexer, it is easy to implement as a very large integrated circuit (VLSI) because it is implemented by local routing.

Description

Coefficient calculation device of error evaluation polynomial in Reed Solomon decoder

1 is a circuit diagram of a coefficient calculating device of a conventional error evaluation polynomial.

2 is a timing diagram of a coefficient calculating device of a conventional error evaluation polynomial.

3 is a circuit diagram of a coefficient calculation device of an error evaluation polynomial according to the present invention.

4 is a timing diagram of an apparatus for calculating coefficients of an error evaluation polynomial according to the present invention.

* Explanation of symbols for main parts of the drawings

10: Galoache multiplier 20: Galoache adder

30: multiplexer 40: shift register section

40-1 to 40-8: raster

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a Reed Solomon decoder that error corrects and decodes digital data subjected to error correcting coding (ECC) by a Reed solomon encoder (RS encoder). An apparatus for calculating coefficients of error polynomials for calculating coefficients of an evaluation polynomial.

In general, Error Correction Coding (ECC) encodes digital data to detect and correct an error occurring when the digital data is transmitted through a communication channel or stored in a storage medium, and the data used to detect or correct an error may be added. This increases the reliability of the data.

The history of this error correction code (ECC) began in 1948 with Claude Shannon. Claude Shannon stated in 1948 that every communication channel had a unique transmission capacity called C (bps), and that an error correction code was used to construct a communication system that transmits data at a transmission rate R (bps) that does not exceed that capacity. Proved to be a channel and possible.

In other words, it is more economical to use an error correction code while using an existing channel that is somewhat poorer than implementing a very good channel.

However, Claude Shannon only proved that there was an error correction code and did not mention how to find the error correction code.

Accordingly, efforts to find an error correction code have been steadily progressed up to now, and the error correction code is largely divided into a block code and a nonblock code.

The block code divides the information sequence into blocks of k bits and then error corrects the code in block units. The non-block code encodes the entire information into the information sequence.

Representative examples of such block codes include BCH codes (Bose and Ray-Chaudhuri and Hocquenghem code) and Reed Solomon codes (RS code), and representative examples of non-block codes include convolutional codes. have.

The BCH code is operated on Galoache GF (2 ^m ) as a cyclic code.

A cyclic code refers to a linear code in which a cyclic shifted linear vector is a linear vector of the linear code, regardless of cyclic shift of any linear vector of the linear code.

Therefore, the BCH code can be coded using the feedback shift register when the code generation polynomial g (x) is determined as in the following first equation.

In this case, the BCH code has the ability to correct up to t errors if the code generation polynomial g (x) has two consecutive roots of t.

On the other hand, the Reed Solomon code is an optimal code of the BCH code and can correct t errors if the code generation polynomial is determined as in the first equation.

Thus, Reed Solomon codes are currently used not only widely in communication and computer storage systems, but also in secret communication systems as a way to combat jamming.

This Reed Solomon code is operated on Galoache GF (2 ^m ) like the BCH code.

That is, the Galoache GF (2 ^m ) is a number system having 2 ^m elements. When the hardware system is implemented in hardware, each element may be represented by m binary digits. Not only is it effective for the digital structure, but no overflow occurs.

Reed Solomon code having a code on Galoache GF (2 ^m ) as described above is a systematic code that does not mix information and parity, and a nonsystematic code that mixes information and parity. Are classified.

The systematic code is obtained by first moving the information to an upper byte so as not to mix information and parity, and then obtaining an error correcting code, which is obtained from the following equation.

In the second equation, c (x) is a codeword polynomial, i (x) is an information polynomial, and t (x) is a polynomial of error correction parity.

In other words, the information i (x) Shift to the higher byte by the difference Find the parity t (x) that satisfies.

And, The parity t (x) satisfying? Can be obtained from the following equation.

In the above Denotes the remainder of the codeword polynomial c (x) divided by the code generation polynomial g (x).

That is, to obtain the parity t (x) Is divided by the code generation polynomial g (x), which can be implemented by concatenating the shift registers according to the code generation polynomial g (x).

In the non-system code, as shown in Equation 4 below, information and parity are mixed as the information is multiplied by the code generation polynomial g (x).

In the first equation, c (x) is an n-1 order codeword polynomial, i (x) is an k-1 order information polynomial, and g (x) is an n-k order code generation polynomial.

The code generation polynomial g (x) is multiplied by the information polynomial i (x) to produce the codeword polynomial c (x). The code generation polynomial g (x) is multiplied by 2t consecutive roots as shown in Equation 5 below. If we set to have t errors, we can correct t errors.

Reed-Solomon decoding of Reed-Solomon-coded digital data as described above is largely divided into frequency-domain decoding and time-domain decoding, and the process of Reed-Solomon decoding in the time domain consists of four steps as follows.

1) syndrome calculation

The received data r (x) may be expressed as a sum of a codeword polynomial c (x) and an error polynomial e (x) generated during transmission, as shown in Equation 6 below.

Therefore, it is possible to know whether an error has occurred during transmission by substituting the root α ^o ˜ α ^2t-1 of the received data r (x) code generation polynomial g (x) in sequence as in the following seventh equation.

That is, when the received data r (x) becomes 0 by substituting the root of the code generating polynomial g (x) with α ¹ to the received data r (x), it means that no error occurred during transmission. Substituting the root α ¹ of the code generation polynomial into r (x), if the received data r (x) does not become 0, it means that an error occurred in the i-th position or the i-th order.

2) Finding error location polynomial

Compute the coefficients of the error location polynomials from the Berlekamp-Massey algorithm or the Euclid algorithm.

If the error position polynomial obtained by the above algorithm is sigma (x), a polynomial of less than or equal to t is obtained in the Reed Solomon code having an error correction capability of t as shown in Equation 8 below.

3) Error value calculation

Substituting α- ^t into the error position polynomial σ (X) finds the position of the error.

That is, when the error position polynomial σ (X) becomes 0 by substituting α ^-t into the error position polynomial σ (X), an error occurs at the i th position or the i th order.

The error evaluation polynomial? (X) can be obtained from the ninth expression below.

In the ninth formula, S (X) is a syndrome polynomial.

In this way, the error evaluation polynomial? (X) is obtained, and the error value e _i is calculated from the following Equation 10.

In the tenth equation, σ '(X) is a derivative of the error position polynomial σ (X).

4) Error correction

After the error value is obtained as described above, the original codeword polynomial c (x) is obtained using the following Equation 11.

At this time, if the same value is added to the properties of galloche becomes 0, e (x) + e (x) = 0.

Meanwhile, the error value calculation process of the third step is subdivided as follows.

(1) Error Evaluation The coefficient of the polynomial? (X) is calculated using the ninth equation below.

In the ninth expression, sigma (X) is an error position polynomial, and S (X) is a syndrome polynomial.

(2) evaluation procedure

The polynomial σ 'which differentiates α ^o , α ¹ , ..., α ^N-1 of GF ( ^2m ) from the error evaluation polynomial Ω (X), the error position polynomial σ (X), and the error position polynomial σ (X). Substitute each of (X) and find the value.

(3). The error value e _i is calculated using the following tenth equation.

In the Reed Solomon decoding method having the above process, the coefficient calculation device of the error evaluation polynomial in the conventional Reed Solomon decoder which implements the process of calculating the coefficient of the error evaluation polynomial in hardware, as shown in FIG. A galloise multiplier 1 for multiplying the coefficient S _i of the syndrome polynomial input from the outside by the coefficient σ _i of the error position polynomial; A galloise adder (3) which adds and outputs an intermediate value to a value output from the galloise multiplier (1); A first multiplexer 5 for selectively outputting a value output from the galloise adder 3 or a coefficient σ _i of an error position polynomial input from the outside according to a first selection signal sel1 input from the outside ; A demultiplexer (7) for demultiplexing and outputting a value output from the first multiplexer (5) according to a second selection signal (sel2) input from the outside; A latch unit (9) for latching and outputting values output through the demultiplexer (7); According to the third selection signal sel3 input from the outside, the value output through the latch unit 9 is input as the intermediate value to the galloach adder 3 and as the coefficient Ω _i of the error evaluation polynomial. It is comprised including the 2nd multiplexer 11 which outputs.

The latch unit 9 includes a plurality of registers 9-1 to 9-8 for latching and outputting a value input through the de-neutralizer 7 according to a symbol clock sym_clk.

2 is a timing diagram of the coefficient calculation device of the error evaluation polynomial according to FIG. 1, wherein the coefficient σ _i of the error position polynomial input from the outside is an error position polynomial during an initial 8 symbol clock (sym_clk) period. Is input in order from the 8th order coefficient of σ ₈ to the 1st order coefficient of the error position polynomial (σ ₁ ), while the 0th order coefficient of the error position polynomial having a value of 1 during the next 8 symbol clock (sym_clk) period ( σ ₀ ) is input, and the first order coefficient of the error position polynomial (σ ₁ ) is input during the next 7 symbol clock (sym_cly) period, and the second order coefficient of the error position polynomial ( σ ₂ ) is input, and the third order coefficient of the error position polynomial (σ ₃ ) is input during the next five symbol clock (sym_cly) period, and the fourth order coefficient of the error position polynomial ( σ ₄₎ is input, that is 3 the symbol clock while (sym_cly) period, and the fifth order coefficient (σ ₅₎ in the error locator polynomial type, the next two symbol clock (sym_cly) 6-th order coefficient (σ ₆₎ of the error locator polynomial during the period is input, and then During the one symbol clock period sym_cly, the seventh order coefficient σ ₇ of the error position polynomial is input.

The coefficient S _i of the syndrome polynomial input from the outside is the symbol clock sym_clk from the first coefficient S ₁ of the syndrome polynomial S ₈ to the eighth order S ₈ after the initial eight symbol clock sym_clk period has passed. ) Is input in synchronization with the first order coefficient (S ₁ ) of the syndrome polynomial (S ₁ ) to the seventh order (S ₇ ) in synchronization with the symbol clock (sym_clk), and then the first coefficient (S ₁ ) of the syndrome polynomial. ) Is inputted in synchronization with the symbol clock (sym_clk) from the sixth order (S ₆ ), and then synchronized with the symbol clock (sym_clk) from the first order (S ₁ ) to the fifth order (S ₅ ) of the syndrome polynomial. Input from the first coefficient (S ₁ ) of the syndrome polynomial to the fourth order (S ₄ ) in synchronization with the symbol clock (sym_clk), and then from the first coefficient (S ₁ ) of the syndrome polynomial Up to the coefficient S ₃ is input in synchronization with the symbol clock sym_clk, and then from the first coefficient S ₁ of the syndrome polynomial to the secondary system. Up to the number S ₂ is input in synchronization with the symbol clock sym_clk, and then the first order coefficient S ₁ of the syndrome polynomial is input in synchronization with the symbol clock sym_clk.

The first selection signal sel1 input to the first multiplexer 5 becomes 1 during the initial 8 symbol clock sys_clk period, and the coefficient σ of the error position polynomial input during the initial 8 symbol clock sym_clk. _{8 to} sigma ₁ ) are selected and output, and after the initial eight symbol clock (sym_clk) period has elapsed, the value output from the galloise adder 3 is selected and output.

The second selection signal sel2 input to the demultiplexer 7 includes the coefficients σ _{8 to} σ ₁ of the error position polynomial input during the initial eight-symbol clock sys_clk period. Each of the registers 9-8 to 9-1 is selected to be inputted, and the latched value is inputted by the galloche adder 3 during the eight symbol clock sym_clk after one symbol clock sym_clk has passed. Each register 9-1 to 9-8 of (9) is selected to be input, and during the next 7 symbol clock (sym_clk) period, the value input from the galloche adder 3 is inputted to the latch unit 9. Each register 9-2 to 9-8 is selected to be input, and during the next 6 symbol clock sym_clk period, the value input from the galloche adder 3 is inputted to each register 9 of the latch unit 9. -3 to 9-8, respectively, and during the next five symbol clock (sym_clk) periods, the galloise adder (3) The input value is selected to be input to each of the registers 9-4 to 9-8 of the latch section 9, and the value input from the galloche adder 3 is latched for the next four symbol clocks (sym_clk). The registers 9 are selected to be input to the registers 9-5 to 9-8 of the unit 9, and the latch unit 9 stores the value input from the galloche adder 3 during the next three symbol clock periods (sym_clk). Are selected to be input to the respective registers 9-6 to 9-8, and during the next two symbol clocks (sym_clk), the values inputted from the galloche adder 3 are inputted to the respective registers of the latch unit 9 ( 9-7 and 9-8, respectively, and during the next symbol clock (sym_clk) period, the value input from the galloese adder 3 is inputted to each register 9-8 of the latch unit 9; Choose to enter each one.

In this case, the coefficients σ _{8 to} σ ₁ of the error position polynomial inputted during the initial 8 symbol clock sym_clk period are selected to be input to the registers 9-8 to 9-1 of the latch unit 9, respectively. The reason for delaying the symbol clock sym_clk is to multiply the coefficient of the error position polynomial by the coefficient of the polynomial of the polynomial in the galloise multiplier (1), and to output the value of the galloise adder (1) by the galloise adder (1). The delay of one symbol clock sym_clk in consideration of the time to add the value output through the second multiplexer 11 and the second multiplexer 11.

The third select signal sel3 input to the multiplexer 11 is configured to register each of the registers 9 of the latch unit 9 during the eight symbol clock sym_clk period after the initial eight symbol clock sym_clk period has passed. Selects to output the values stored in -1 to 9-8 in order, and is stored in each of the registers 9-2 to 9-8 of the latch unit 9 during the next 7 symbol clock (sym_clk) period. Selects to output the values in order, and then outputs the values stored in the registers 9-3 to 9-8 of the latch unit 9 in order during the next 6 symbol clocks (sym_clk) period, During the next five symbol clock (sym_clk) periods, the respective stored values of the registers 9-4 to 9-8 of the latch unit 9 are sequentially output. In the next four symbol clock (sym_clk) periods, the values are stored. Lines for outputting the values stored in the registers 9-5 to 9-8 of the latch section 9 in order, respectively. Selects and outputs the values stored in the registers 9-6 to 9-8 of the latch unit 9 in order during the next three symbol clocks (sym_clk), and then the two symbol clocks (sym_clk). ), And outputs the values stored in the registers 9-7 and 9-8 of the latch unit 9 in order, and then, during the next one symbol clock (sym_clk) period, the latch unit 9 Select to output the value stored in each register (9-8).

In the coefficient estimation apparatus of the error evaluation polynomial in the conventional Reed Solomon decoder configured as described above, since the first selection signal sel1 input to the first multiplexer 6 is 1 during the initial eight-symbol clock (sym_clk) period. The coefficients σ _{8 to} σ ₁ of the error position polynomial input from the outside are input to the demultiplexer 7 through the first multiplexer 6, and the demultiplexer 7 receives the second selection signal sel2. ), The coefficients σ _{8 to} σ ₁ of the error position polynomial are sequentially input to the registers 9-8 to 9-1 of the latch unit 9.

That is, the registers 9-8 to 9-1 of the latch unit 9 are initialized to the coefficients σ _{8 to} σ ₁ of the error position polynomial.

On the other hand, during the 8-symbol (sym_clk) period after the initial 8-symbol clock (sym_clk) period, the galoche multiplier (1) has an error having each coefficient (S _{1 to} S ₈ ) and 1 value of the syndrome polynomial input from the outside. The 0th order coefficients (σ ₀ ) of the evaluation polynomial are respectively multiplied and output to the galloise adder (3).

In addition, the galloise adder 3 outputs the values S _{1 to} S ₈ output from the galloise multiplier 1 and the values output from the registers 9-1 to 9-8 of the latch unit 9 ( sigma _{1 to} sigma ₈ ) are added to output S ₁ + σ ₁ and S ₂ + σ ₂ .

Accordingly, the value output from the galloche adder 3 is input to the first multiplexer 5 as described above. In this case, since the first selection sel1 input to the first multiplexer 5 is 0, the value output from the galloche adder 3 is input to the demultiplexer 7 and the demultiplexer 7. Is sequentially inputted to the registers 9-1 to 9-8 of the latch unit 9 in accordance with the second selection signal sel2.

Thus, the value stored in each register (9-1~9-8) of the latch portion 9 becomes an _{S 1 + σ 1, ‥‥‥ S} 8 + σ 8.

During the next seven symbol clocks (sym_clk), the galloise multiplier 1 multiplies each coefficient (S _{1 to} S ₇ ) of the syndrome polynomial input from the outside by the first coefficient (σ ₁ ) of the error evaluation polynomial, respectively. Output to Aceh Adder (3).

That is, the value output from the galloise multiplier 1 is S ₁ sigma ₁ , ..... S ₇ sigma ₁ .

The galloche adder 3 includes the values S ₁ σ _{1 to} S ₇ σ ₁ and the registers 9-2 to 9-8 of the latch unit 9 outputted from the galloche multiplier 1. S ₂ + σ ₂ + S ₁ σ ₁ , ‥‥‥, S ₈ + σ ₈ + S ₇ σ ₁ in addition to the values (S ₂ + σ ₂ , ‥‥‥, S ₈ + σ ₈ ) Output as is.

That is, the third selection signal sel3 input to the second multiplexer 11 selects and outputs only the values stored in the seven registers 9-2 to 9-8 of the latch unit 9. Values input to the Aceh adder 3 are S ₂ + σ ₂ ,..., S ₈ + σ ₈ .

As described above, the values output from the galloche adder 3 are S ₂ + σ ₂ + S ₁ sigma ₁ , .................., S ₈ + σ ₈ + S ₇ sigma ₁ is again the first multiplexer 5. The demultiplexer 7 is multiplexed in accordance with the second selection signal sel2 and sequentially applied to the registers 9-2 to 9-8 of the latch unit 9 through the demultiplexer 7. To enter.

Therefore, the values stored in the registers 9-2 to 9-8 of the latch unit 9 are S ₂ + σ ₂ + S ₁ σ ₁ , .................., S ₈ + σ ₈ + S ₇ σ ₁ Will be.

When such a process is repeated, finally, the respective coefficient values σ _{1 to} σ ₈ of the error evaluation polynomial are sequentially stored in the registers 9-1 to 9-8 of the latch unit 9.

However, in the conventional Reed-Solomon decoder as described above, the coefficient calculation device of the error evaluation polynomial is a routing and demultiplexer between the registers 9-1 to 9-8 and the second multiplexer 11. Since routing between 7) and each register 9-1 to 9-8 is global routing, the routing itself takes up a large area and is realized as a very large integrated circuit (VLSI). There was a problem that was difficult to do.

Accordingly, the present invention is to solve the conventional problems as described above, in the Reed Solomon decoder implemented by local routing by implementing a coefficient calculation device of the error evaluation polynomial without using a multiplexer and a demultiplexer. It is an object of the present invention to provide a coefficient calculating device of an error evaluation polynomial.

In the Reed-Solomon decoder according to the present invention for achieving this object, the coefficient calculation device of the error evaluation polynomial includes: a Galloche multiplier for multiplying the coefficient of the syndrome polynomial and the number of the error position polynomial; A galloise adder for adding and outputting a value output from the galloise multiplier and an intermediate value; A multiplexer for selectively outputting a value output from the galloise adder or a coefficient of an error position polynomial input from the outside; And a shift register portion for shifting the value output from the multiplexer, inputting it to the Galois adder as an intermediate value, and outputting as a coefficient of an error evaluation polynomial.

Therefore, it is possible to implement a local routine by implementing the coefficient calculating device of the error evaluation polynomial without using the multiplexer and the demultiplexer.

Hereinafter, with reference to the accompanying drawings will be described an embodiment of the present invention;

In the Reed Solomon decoder, the coefficient of the error evaluation polynomial? (X) is calculated using the following ninth equation.

In the ninth expression, sigma (X) is an error position polynomial, and S (X) is a syndrome polynomial.

In the error evaluation polynomial Ω (X) of the ninth equation, the error evaluation polynomial Ω (X) when there is no erasure and the eighth order (t = 8) can be expressed as in the following twelfth equation.

At this time, Ω _{0, which} is the 0th order coefficient of the error evaluation polynomial Ω (X), is 1, so it is not necessary to calculate it, and only the remaining eight coefficients need to be obtained.

Therefore, the passage angle coefficient can be calculated | required through the process similar to following formula (13).

That is, the calculation time is fixed to 8 symbol clocks, and the coefficient of the syndrome polynomial is input to 0 for unnecessary symbol clocks.

The coefficient calculation device of the error evaluation polynomial according to the present invention, which implements the above-described calculation process in hardware, is implemented as shown in FIG.

The third turning coefficient of the error evaluation as a function circuit diagram of a calculation apparatus of the polynomial coefficient calculation unit of the error evaluation polynomial in accordance with the present invention, the coefficients of the syndrome polynomial from the outside (S _i) and the error locator polynomial in accordance with the present invention ( a galloise multiplier 10 for multiplying and outputting σ _i ); A galloise adder 20 for adding and outputting a value output from the galloise multiplier 10 and an intermediate value; A multiplexer (30) for selectively outputting a value output from the galloise adder (20) or a coefficient (σ _i ) of an error position polynomial input from the outside according to a selection signal (sel) input from the outside; And a shift register section 40 for shifting the value output from the multiplexer 30, inputting it to the galloche adder 20 as an intermediate value, and outputting as a coefficient Ω _i of an error evaluation polynomial. It is.

In the shift register unit 40, a plurality of registers 40-1 to 40-8 are connected in series to shift the value input through the multiplexer 30 according to a symbol clock sym-clk. To make it appear.

4 is a timing diagram of an error evaluation polynomial coefficient calculating device in the Reed Solomon decoder according to the present invention, wherein the coefficient σ _i of the error evaluation polynomial input from the outside is received during an initial 8 symbol clock (sym_clk) period. The first order coefficient of the error position polynomial (σ ₁ ) to the eighth order coefficient of the error position polynomial (σ ₈ ) are input in sequence in synchronization with the symbol clock (sym_clk), followed by the error position polynomial at intervals of eight symbols (sym_clk). the zeroth order coefficient is input in order to 8-th order coefficient of the error locator polynomial from _{(σ 0) (σ 8)} .

The coefficient S _i of the syndrome polynomial input from the outside is a symbol clock (S _i ) from the first coefficient S _{1 of the} syndrome polynomial to the eighth order S ₈ of the syndrome polynomial after the initial eight symbol clock period (sym_clk) has passed. in synchronization with the sym_clk) is input in turn the other hand, 0, in synchronization with the _{S 1, S 2, S 3} , S 4, S 5, S 6, S 7, the symbol clock (sym_clk) are inputted in sequence, then to 0, 0, S ₁ , S ₂ , S ₃ , S ₄ , S ₅ , S ₆ , are entered in sequence in synchronization with the symbol clock (sym_clk), followed by 0, 0, 0, S ₁ , S ₂ , S ₃ , S ₄ , S ₅ are input in sequence in synchronization with the symbol clock (sym_clk), followed by 0, 0, 0, 0, S ₁ , S ₂ , S ₃ , S ₄ is the symbol clock (sym_clk). ), And then 0, 0, 0, 0, 0, S ₁ , S ₂ , and S ₃ are input in sequence in synchronization with the symbol clock (sym_clk), followed by 0 and 0. , 0, 0, 0, 0, S ₁ , S ₂ are synchronized to the symbol clock (sym_clk) Next, 0, 0, 0, 0, 0, 0, 0, and S ₁ are sequentially input in synchronization with the symbol clock sym_clk.

The selection signal sel input to the multiplexer 30 becomes 1 during the initial 8 symbol clock sym_clk period, and the coefficients σ _{1 to} σ of the error position polynomial input during the initial 8 symbol clock sym_clk. ₈ ) is selected and input to the shift register unit 40, and after the initial 8 symbol clock (sym_clk) period has elapsed, the value becomes 0 and selects the value output from the galloche adder 20. Enter 40).

The operation and effects of the coefficient calculation device of the error evaluation polynomial of the Reed Solomon decoder according to the present invention configured as described above will be described in detail.

Since the selection signal sel input to the multiplexer 30 is 1 during the initial 8 symbol clock sym_clk period, the multiplexer 30 shifts the coefficients σ _{1 to} σ ₈ of the error position polynomial input from the outside. The register 40 is input to the register 40, and the shift register 40 is inputted to the galoche adder 20 by shifting the coefficients σ _{1 to} σ ₈ of the error position polynomial input through the multiplexer 30. do.

After the initial eight-symbol clock period (sym_clk) has passed, during the eight-symbol clock (sym_clk) period, the galoche multiplier 10 has an error having each coefficient (S _{1 to} S ₈ ) and one value of the syndrome polynomial input from the outside. The zero-order coefficients (σ ₀ ) of the evaluation polynomial are respectively multiplied and output to the galloise adder 20.

That is, the values output from the galloise multiplier 10 are S ₁ , S ₂ , S ₃ , S ₄ , S ₅ , S ₆ , S ₇ , and S ₈ .

In addition, the Galoache adder 20 includes a value S ₁ , S ₂ , S ₃ , S ₄ , S ₅ , S ₆ , S ₇ , and S ₈ outputted from the Galoache multiplier 10 and a shift register unit ( S ₁ + σ ₁ and S ₂ + σ ₂ ... Are then outputted by adding the values (σ _{1 to} σ ₈ ) shifted through 40).

As described above, the values S ₁ + σ ₁ and S ₂ + σ ₂ ... Output from the galloise adder 20 are input to the multiplexer 30. In this case, since the selection signal sel input to the multiplexer 30 is 0, a value output from the gallo-adder 20 is input to the shift register unit 40, and the shift register unit 40 The value output from the galloche adder 20 is input to the galloche adder 20 again.

Therefore, the value output through the shift register section 40 is S ₁ + σ ₁ ,..., S ₈ + σ ₈ .

During the next 8 symbol clock period (sym_clk), the Galloche multiplier 1 multiplies the externally input coefficients (0, S _{1 to} S ₇ ) of the syndrome polynomial by the first order coefficient (σ ₁ ) of the error evaluation polynomial, respectively. Output to the galloche adder (20).

That is, the value output from the galloise multiplier 10 is 0, S ₁ σ ₁ ,..., S ₇ σ ₁ .

In addition, the galloise adder 20 outputs the value (0, S ₁ σ ₁ , ..., S ₇ σ ₁ ) output from the galloise multiplier 10 and the value S ₁ output from the shift register 40. in addition to _{σ 1, ‥‥, S 8 σ} 8) and outputs the _{S 1 + σ 1, S 2} + σ 2 + S 1 σ 1, ‥‥, S 8 + σ 8 + S 7 σ 1 one after the other.

As described above, S ₁ + σ ₁ and S ₂ + σ ₂ + S ₁ σ ₁ , ‥‥, S ₈ + σ ₈ + S ₇ σ ₁ output from the galloche adder 20 are again multiplexed (30). Is input to the shift register section 40 through.

When the above process is repeated, the coefficient values σ _{1 to} σ ₈ of the error evaluation polynomial are finally output through the shift register 40.

As described above, according to the present invention, it is implemented by local routing by implementing a coefficient calculating device of an error evaluation polynomial without using a multiplexer and a demultiplexer, and is easily implemented in an ultra-large scale integrated circuit (VLSI). It is.

The present invention has been described by taking an example where there is no erasure and the error evaluation polynomial is 8th order (t = 8), but is not limited thereto.

Claims (5)

A galloise multiplier 10 for multiplying the coefficient S _i of the syndrome polynomial input from the outside by the coefficient σ _i of the error position polynomial; A galloise adder 20 for adding and outputting a value output from the galloise multiplier 10 and an intermediate value; A multiplexer (30) for selectively outputting a value output from the galloise adder (20) or a coefficient (σ _i ) of an error position polynomial input from the outside; The shift register unit 40 shifts the value output from the multiplexer 30 and inputs it to the Galoache adder 20 as an intermediate value, and outputs the coefficient Ω _i of the error evaluation polynomial. An apparatus for calculating coefficients of error evaluation polynomials in Reed Solomon decoders. 2. The shift register unit 40 of claim 1, wherein a plurality of registers 40-1 to 40-8 are connected in series, and the shift register unit 40 converts a value input through the multiplexer 30 into a symbol clock sym_clk. And a coefficient estimating apparatus of an error evaluation polynomial in the Reed Solomon decoder. 2. The coefficient σ _i of the error evaluation polynomial input from the outside is synchronized with the symbol clock sym_clk from the _first coefficient σ ₁ of the error position polynomial to the coefficient σ _k of the last order. And are input in order, and are sequentially inputted from the zeroth order coefficient (σ ₀ ) of the error position polynomial to the last order coefficient (σ _k ) with a k symbol clock (sym_clk) corresponding to the last order _k . Coefficient estimator of error evaluation polynomial in Reed Solomon decoder. The coefficient S _i of the syndrome polynomial input from the outside is sequentially input in synchronization with the symbol clock sym_clk from the _first coefficient S ₁ to the coefficient S _k of the last order. Next, 0, S ₁ , S ₂ , ‥‥‥, S _K-1 are input in order in synchronization with the symbol clock (sym_clk), and then 0, 0, S ₁ , ‥‥‥, S _K-2 Reed-Solomon, which is input in order in synchronization with the symbol clock sym_clk, and finally 0, 0, 0, ..., and S ₁ are input in order in synchronization with the symbol clock sym_clk. Coefficient calculation device of error evaluation polynomial in decoder. 2. The multiplexer (30) according to claim 1, wherein the multiplexer (30) is the error position while being sequentially input in synchronization with the symbol clock (sym_clk) from the _first coefficient (σ ₁ ) of the error position polynomial to the coefficient (σ _k ) of the last order. A polynomial coefficient σ _{1 to} sigma ₈ is selected and input to the shift register section 40. After this period, the value output from the galloche adder 20 is selected to select the shift register section ( And a coefficient estimating device of an error evaluation polynomial in the Reed Solomon decoder.