US 5,537,426 AGrant
Operation Apparatus for Deriving Erasure Position .GAMMA.(x) and Forney Syndrome T(x) Polynomials of a Galois Field Employing a Single Multiplier
Issue Date:1996-07-16
•6 Claims
•8 Drawing Sheets
Abstract
Operation apparatus for deriving an error position polynomial .GAMMA.(x) and a Forney syndrome polynomial T(x) of a Galois field capable of reducing the required number of Galois field multipliers to one, irrespective of the maximum error correction capacity in a Galois field operation, thereby reducing the chip area and achieving a correct operation. The operation apparatus comprises a storing register for storing result values sequentially inputted therein, a multiplexor for receiving outputs from the storing register and selecting a necessary coefficient therefrom, a first register and a second register for storing a coefficient currently selected by the multiplexor and a coefficient previously selected by the multiplexor, respectively, a multiplier for multiplying a value corresponding to an input erasure position and the coefficient stored in the second register, and an adder for adding a value outputted from the multiplier to the coefficient stored in the first register and inputting the resultant value to the storing register.
Metadata
Assignee
- Goldstar Co., Ltd.
Inventor
- Dong H. Lee
Application Information
Application Number:US 0684341
Filing Date:1993-05-27
Priority Date:1992-05-29
Art Unit:236
Classifications
IPC:
G06F 1110
Field of Search:
37137.1;38.1;39.1;40.1
Patent Drawings (8 sheets)
Description
Background of the Invention
1. Field of the Invention
The present invention relates to error correction, and more particularly to an operation apparatus with multipliers for deriving an error position polynomial .GAMMA.(x) and a Forney syndrome polynomial .GAMMA.(x) of a Galois field.
2. Description of the Prior Art,
Generally, an erasure is known in terms of position, even though unknown in terms of size, as compared with an error whose position and size are unknown. Accordingly, when information indicative of an erasure of some symbol is applied to a decoder, he erasure corresponding to two times the same number of parity errors can be corrected.
Referring to FIG. 1, here is illustrated a general erasure position power operation apparatus. The operation apparatus comprises an AND gate 1 having one input for receiving information about erasure, namely, erasure positions of binary values. To the other input of the AND gate 1, register 2 and a multiplier 3 are connected. In the AND gate 1, the erasure position is AND-combined with a value obtained through the register 2 and the multiplier 4. To an output of the AND gate 1, a non-zero detector 4 is connected, which receives an output signal from the AND gate 1 and generates a control signal C.sub.1. The control signal C.sub.1 is applied to a 2t symbol latch 5 via a switch SW.sub.a. According to the control signal C.sub.1, the 2t symbol latch 5 outputs powers for the erasure positions, namely, values .alpha..sup.j1, .alpha..sup.j2, . . . corresponding to respective erasure positions. Here, the value .alpha..sup.j1 represents the value corresponding to the first erasure position and the value .alpha..sup.j2 represents the value corresponding to the second erasure position.
Since the erasure positions are already known, they can be expressed by the following polynomial: ##EQU1## wherein, e represents the number of erasures.
FIG, 2 is a block diagram of a conventional operation apparatus utilizing the polynomial for erasure positions.
As shown in FIG. 2, the operation apparatus comprises a non-zero detector 10 for receiving an erasure position value .alpha..sup.j(i) and detecting whether the received erasure position value is zero or not, and a multi-stage operation unit including a plurality of operation circuits 20.sub.0 to 20.sub.2t-1. The operation unit comprises a plurality of adders A.sub.0 to A.sub.2t-1 and a plurality of registers R.sub.0 to R.sub.2t-1 connected with the adders A.sub.0 to A.sub.2t-1 via a plurality of switches SW.sub.0 to SW.sub.2t-1, respectively. Each of the switches SW.sub.0 to SW.sub.2t-1 are controlled by an output signal from the non-zero detector 10, to be switched on or off. According to the switching operations of the switches SW.sub.0 to SW.sub.2t-1, the registers R.sub.0 to R.sub.2t-1 store temporally output values from the adders A.sub.0 to A.sub.2t-1, respectively. The operation unit also comprises a plurality of multipliers M.sub.0 to M.sub.2t-1 each for multiplying each value stored in each corresponding one of the registers R.sub.0 to R.sub.2t-1 and each corresponding erasure position value .alpha..sup.j(i) and sending the resultant value to each corresponding one of the adders A.sub.0 to A.sub.2t-1.
In the operation apparatus with the above-mentioned construction, the register R.sub.0 is initially loaded with the value of 1, while the remaining registers R.sub.1 to R.sub.2t-1 are initially loaded with the value of 0.
When a value .alpha..sup.j(1) corresponding to the first erasure position is received in the operation apparatus, it is applied to the non-zero detector 10 and respective multipliers M.sub.0 to M.sub.2t-1 of the operation circuits 20.sub.0 to 20.sub.2t-1.
The non-zero detector 10 detects whether the received erasure position value is zero or not and outputs a detect signal, so as to control respective switches SW.sub.0 to SW.sub.2t-1 of the operation circuits 20.sub.0 to 20.sub.2t-1 . The control of each switch is carried out such that the switch is switched to its closed state when the input value of non-zero detector 10 is not zero and to its opened state when the input value is zero.
This procedure will be described in detail.
Where the first register R.sub.0 has an initial value of 1 while the remaining registers R.sub.1 to R.sub.2t-1 have initial values of 0 at a state that the input value of non-zero detector 10 is not zero; the register R.sub.0 is loaded with the first erasure position value .alpha..sup.j(1), whereas the register R.sub.1 is loaded with the value of 1. In this case, the remaining registers R.sub.2 to R.sub.2t-1 are still maintained as being loaded with the value of 0.
As the above procedure is repeated, the register R.sub.0 is sequentially loaded with values in the order of 0.fwdarw.1.fwdarw..alpha..sup.j1 .fwdarw..alpha..sup.j1 .multidot..alpha..sup.j2 .fwdarw..alpha..sup.j1 .multidot..alpha..sup.j2 .multidot..alpha..sup.j3 .fwdarw..alpha.j1.multidot..alpha..sup.j2 .alpha..sup.j3. . . The register R.sub.1 is sequentially loaded with values in the order of 0.fwdarw.1.fwdarw..alpha..sup.j1 .fwdarw..alpha..sup.1 +.alpha..sup.j2 .fwdarw.(.alpha..sup.j1+ .alpha..sup.j2).alpha..sup.j3 .fwdarw..alpha.j1.multidot..alpha..sup.j2 . . . On the other hand, the register R.sub.2 is sequentially loaded with values in the order of 0.fwdarw.0.fwdarw.1.fwdarw..alpha..sup.j1 +.alpha..sup.j2 +.alpha..sup.j3 . . . .
The sequential value storing procedures executed in the registers are shown in FIG. 3.
FIG. 5 is a block diagram of a conventional operation apparatus for deriving a Forney syndrome.
As shown in FIG. 5, the operation apparatus comprises a non-zero detector 10a for receiving an erasure position value .alpha..sup.j(i) and detecting whether the received erasure position value is zero or not, and a multi-stage operation unit including a plurality of operation circuits 20a.sub.0 to 20a.sub.2t-1. The operation unit comprises a plurality of adders A.sub.0 to A.sub.2t-1 and a plurality of registers S.sub.0 to S.sub.2t-l connected with the adders A.sub.0 to A.sub.2t-1 via a plurality of first switches SW.sub.b, respectively. Each of the first switches SW.sub.b are controlled by an output signal from the non-zero detector 10a, to be switched on or off. According to the switching operations of the first switches SW.sub.b, the registers S.sub.0 to S.sub.2t-1 store temporally output values from the adders A.sub.0 to A.sub.2t-1, respectively. The operation unit also comprises a plurality of multipliers M.sub.0 to M.sub.2t-1 each for multiplying each value loaded in each corresponding one of the registers S.sub.0 to S.sub.2t-1 and each corresponding erasure position value .alpha..sup.j(i) and sending the resultant value to each corresponding one of the adders A.sub.0 to A.sub.2t-1. The operation apparatus also comprises an output unit 30 including a plurality of registers T.sub.0 to T.sub.2t-1 each connected to each corresponding one of the registers S.sub.0 to S.sub.2t-1 via a second switch SW.sub.c.
In the operation apparatus with the above-mentioned construction, the registers S.sub.0 to S.sub.2t-1 of the operation circuits 20.sub.a0 to 20a.sub.2t-1 are initially loaded with the values of S.sub.0, S.sub.1, . . . , and S.sub.2t-1 which are coefficients of the polynomial of the syndrome, respectively.
In similar manner to the case of FIG. 2, this operation apparatus receives sequentially values .alpha..sup.k(i) corresponding to erasure positions and controls the switches SW.sub.b via the non-zero detector 10a so that the values .alpha..sup.j(i) are applied to the multipliers M.sub.0 to M.sub.2t-1, respectively.
At the first clock, thereafter, the register S.sub.0 is loaded with the value of S.sub.0, whereas the register S.sub.1 is loaded with the value of S.sub.1 +S.sub.0 .multidot..alpha..sup.j(i). On the other hand, the register S.sub.2 is loaded with the value of S.sub.2 +S.sub.1 .multidot..alpha..sup.k(1). In such a manner, the register S.sub.j is loaded with the value of S.sub.j +S.sub.j .multidot..alpha..sup.j(i).
As the above procedure is repeated according to inputting of erasure position values .alpha..sup.j(i), the registers S.sub.0 to S.sub.2t-1 are loaded with coefficients of the polynomial.
At this time, the second switches SW.sub.c are switched to its closed state by the control signal C.sub.2, so that the coefficients loaded in the registers S.sub.0 to S.sub.2t-1 are transferred to the registers T.sub.0 to T.sub.2t-1 of the output unit 30, respectively.
FIG. 4 is a circuit diagram of Galois field (GF) multipliers M.sub.0 to M.sub.2t-1 used in both the operation apparatus of FIG. 3 and the operation apparatus of FIG. 5. Each adder is an GF(2.sup.4) adder for operating one byte comprised of four bits. The GF(2.sup.4) adder comprises an AND gate and an exclusive 0R gate.
First, a source polynomial P(X) having the degree of 4 is needed for expanding GF(2) up to GF(2.sup.4).
That is, assuming the source polynomial P(X)=X.sup.4 +X+1, elements of all fields are expressed by a cubic-nomials a.sub.3 X.sup.3 +a.sub.2 X.sup.2 +a.sub.1 X+a.sub.0 =a(X). In this case, a.sub.i represents elements of GF(2).
When the cubic-nomial is expressed for .tau. and .beta. indicative of input values of each AND gate, and .THETA. indicative of one input value of each exclusive OR gate, the following cubic-nomials are obtained:
.tau.(X)=.tau..sub.3 X.sup.3 +.tau..sub.2 X.sup.2 +.tau..sub.1 X+.tau..sub.0
.beta.(X)=.beta..sub.3 X.sup.3 +.beta..sub.2 X.sup.2 +.beta..sub.1 X+.beta..sub.0
.THETA.(X)=.THETA..sub.3 X.sup.3 +.THETA..sub.2 X.sup.2 +.THETA..sub.1 X+.THETA..sub.0
Also, .tau..multidot..beta. indicative of the output value of each AND gate is expressed by the following equation:
Assuming .tau..multidot..beta.=K.sub.3 X.sup.3 +K.sub.2 X.sup.2 +K.sub.1 X+K.sub.0 the output value .tau..multidot..beta.+.THETA. of each exclusive OR gate is expressed by the following cubic-nomial:
The operation of the first row is carried out as follows:
.tau..sup.(1) (X)=.tau.(X)
.THETA..sup.(1) (X)=.THETA.(X)+.beta..sub.0 .tau.(X)
The operation of the i-th row is carried out as follows:
.tau..sup.(i+1) (X)=X.tau..sup.(i) (X) mod P(X)
.THETA..sup.(i+1) (X)=.THETA..sup.(i) (X)+.beta..sub.i .tau..sup.(i+1) (X)
Each cell performs the following two functions:
wherein, .THETA..sub.j.sup.(i+1) represents the i-th row .multidot.j-th column.
For example, in the first cell of the second row, .tau..sub.3 and .beta..sub.1 are ANDed in the AND gate AD.sub.2.1 and then exclusively ORed in the exclusive OR gate XOR.sub.2.1, so as to be outputted as .THETA..sub.0.sup.(2). In the second cell, .tau..sub.3.sup.(0) and .tau..sub.0 are exclusively ORed in the exclusive OR gate XOR.sub.2.2, so as to be provided as one input of AND gate AD.sub.2.3.
The output from the exclusive OR gate XOR.sub.2.2 is ANDed with .beta..sub.1 in the AND gate AD.sub.2.3 and then exclusively ORed in the exclusive OR gate XOR.sub.2.3, so as to be outputted as .THETA..sub.1.sup.(1). In such a manner, the operation is repeated up to the final row.
As a result, the following results are obtained:
In the conventional circuit, however, the content of registers based on the polynomial for erasure positions includes the initial value of 1 only for the register R.sub.0 and the initial value of 0 for the remaining registers R.sub.1 to R.sub.2t-1.
For each input .alpha..sup.j(i) only one of such registers is used while the remaining registers are unnecessary. Accordingly, the multipliers for deriving values for the remaining registers are also unnecessary.
That is, for the operation of the polynomial for erasure positions, 2t GF multipliers and 2t adders are needed. In GF multipliers, the larger the symbol field, the more the number of exclusive OR gates.
As a result, where a Reed Solomon decoder is realized by using very large size integrated circuit chips, the area occupied by the multipliers is increased due to the increased number of exclusive OR gates. Furthermore, when symbol fields of codes are very large and the erasure correction capacity is large, the chip area becomes relatively large. The flow of signals is also vague, so that a correct operation can not be carried out.
Summary of the Invention
Therefore, an object of the invention is to provide an operation apparatus capable of reducing the number of Galois field multipliers to one, irrespective of the maximum error correction capacity in a Galois field operation, thereby reducing the chip area and achieving a correct operation,
In accordance with the present invention, this object can be accomplished by providing an operation apparatus comprising: a storing register for storing result values sequentially inputted therein; a multiplexor for receiving outputs from the storing register and selecting a necessary coefficient therefrom; a first register and a second register for storing a coefficient currently selected by the multiplexor and a coefficient previously selected by the multiplexor, respectively; a multiplier for multiplying a value corresponding to an input erasure position and the coefficient loaded in the second register; and an adder for adding a value outputted from the multiplier to the coefficient loaded in the first register and inputting the resultant value to the storing register.
The adder logically operates multiplication outputs (W.sub.0, W.sub.1, W.sub.2 and W.sub.3) for 4-bit input data (.tau..sub.0, .tau..sub.1, .tau..sub.2 and .tau..sub.3) and 4-bit input data (.beta..sub.0, .beta..sub.1 , .beta..sub.2 and .beta..sub.3 ), in the following order:
Upon receiving a power corresponding to one erasure position, the operation apparatus derives coefficients of a polynomial for the erasure position while increasing the degree of the erasure position polynomial one by one. The derived coefficients are loaded. Accordingly, it is possible to derive the erasure position polynomial by using one multiplier and one adder, irrespective of the error correction capacity. As a result, the chip area can be greatly reduced.
Brief Description of the Drawings
Other objects and aspects of the invention will become apparent from the following description of embodiments with reference to the accompanying drawings in which:
FIG. 1 is a block diagram of a general erasure position power operation apparatus;
FIG. 2 is a block diagram of a conventional operation apparatus utilizing a polynomial for erasure positions;
FIG. 3 is a table illustrating variations in register values in the operation apparatus of FIG. 2;
FIG. 4 is a circuit diagram of the multiplier of FIG. 2;
FIG. 5 is a block diagram of a conventional operation apparatus for deriving a Fourney syndrome;
FIG. 6 is a block diagram of an apparatus for operating a polynomial for erasure positions in accordance with a first embodiment of the present invention;
FIG. 7 is a circuit diagram of a multiplier in the operation apparatus of FIG. 6;
FIG. 8 is a circuit diagram of a circuit substituted for exclusive OR gates of FIG. 7;
FIG. 9 is a table illustrating variations in register values in the operation apparatus of FIG. 6; and
FIG. 10 is a block diagram of a Fourney syndrome operation apparatus according to a second embodiment of the present invention.
Detailed Description of the Preferred Embodiments
Referring to FIG. 6, there is illustrated an apparatus for operating a polynomial for erasure positions in accordance with a first embodiment of the present invention.
As shown in FIG. 6, the operation apparatus comprises a storing register 51 for storing results sequentially inputted therein and a multiplexor 52 for receiving outputs from the storing register 51 and selecting a necessary coefficient. To the multiplexor 52, a first register 53 and a second register 54 are connected, which receive the coefficient currently selected by the multiplexor 52 and the coefficient just previously selected by the multiplexor 52, respectively. The operation apparatus also comprises a multiplier 55 for multiplying a value corresponding to an input erasure position and the coefficient loaded in the second register 54, and an adder 56 for adding a value outputted from the multiplier 55 to the coefficient loaded in the first register 53.
FIG. 7 is a circuit diagram of the multiplier of FIG. 6. As shown in FIG. 6, the multiplier comprises a plurality of AND gates AD.sub.1.1, AD.sub.1.3, AD.sub.1.5, AD.sub.1.7, AD.sub.3.1, AD.sub.3.3, AD.sub.3.5, AD.sub.3.7, AD.sub.5.1, AD.sub.5.3, AD.sub.5.5, AD.sub.5.7, AD.sub.7.1, AD.sub.7.3, AD.sub.7.5 and AD.sub.7.7 each for AND-combining a selected one of 4-bit input data .tau..sub.0, .tau..sub.1, .tau..sub.2 and .tau..sub.3 and a selected one of 4-bit input data .beta..sub.0, .beta..sub.1, .beta..sub.2 and .beta..sub.3. A plurality of exclusive OR gates XOR.sub.4.4, XOR.sub.6.4, XOR.sub.6.6, XOR.sub.8.4, XOR.sub.8.6 and XOR.sub.8.8 are also provided for exclusively ORing outputs from the AND gates AD.sub.3.1 and AD.sub.3.7, outputs from the AND gates AD.sub.5.5 and AD.sub.5.7, outputs from the AND gates AD.sub.5.1 and AD.sub.5.7, outputs from the AND gates AD.sub.7.1 and AD.sub.7.3, outputs from the AND gates AD.sub.7.5 and AD.sub.7.7, and outputs from the AND gates AD.sub.7.1 and AD.sub.7.7, respectively. The multiplier also comprises an exclusive OR gate XOR.sub.9.2 for exclusively ORing outputs from the AND gates AD.sub.1.1, AD.sub.3.7, AD.sub.5.5 and AD.sub.7.3, an exclusive OR gate XOR.sub.9.4 for exclusively ORing an output from the AND gate AD.sub.1.3 and outputs from the exclusive OR gates XOR.sub.4.4, XOR.sub.6.4 and XOR.sub.8.4, an exclusive OR gate XOR.sub.9.6 for exclusively ORing outputs from the AND gates AD.sub.1.5 and AD.sub.3.3 and outputs from the exclusive 0R gates XOR.sub.6.6 and XOR.sub.8.6, and an exclusive OR gate XOR.sub.9.8 for exclusively ORing outputs from the AND gates AD.sub.1.7, AD.sub.3.5 and AD.sub.5.3 and an output from the exclusive OR gate XOR.sub.8.8.
In the AND gates AD.sub.i.j and the exclusive OR gates XOR.sub.i.j, i and j represent row and column, respectively. Data outputted from the exclusive OR gates XOR.sub.9.2, XOR.sub.9.4, XOR.sub.9.6 and XOR.sub.9.8 are values W.sub.0, W.sub.1, W.sub.2 and W.sub.3 obtained by multiplying input data .tau..sub.0, .tau..sub.1, .tau..sub.2 and .tau..sub.3 and input data .beta..sub.0, .beta..sub.1, .beta..sub.2 and .beta..sub.3, respectively.
In operating the erasure position polynomial, since the erasure is known in terms of position, even though unknown in terms of size, the erasure position polynomial can be derived by using the following equation: ##EQU2## wherein, e represents the number of erasures.
Accordingly, coefficients of the polynomial are sequentially outputted while increasing the degree of polynomial one by one in the order of .sub.1 (X) of the first degree, .sub.2 (X) of the second degree, . . . , and .sub.8 (X) of the e-th degree. Outputted coefficients of the polynomial (X) are loaded in the storing register 51 of FIG. 5.
The first and second registers 53 and 54 are initialized to 1 and 0 for every clock, respectively. The multiplexor 52 is also initialized to 0.
As 0 is outputted from the multiplexor 52, the first and second registers 53 and 54 receives 0 which is the current coefficient of the polynomial ( .sub.i (X)=0) and 1 which is the previous coefficient of the polynomial .sub.i-1 (X)=1). Accordingly, 1 is inputted at the storing register 51.
Next, as .alpha..sup.j1 corresponding to the first erasure position is inputted, .alpha..sup.j1 is applied to the storing register 51 (X)=.alpha..sup.j1).
At this time, the first register 53 adapted to store the current input value therein is loaded with (X)=1. On the other hand, the second register 54 adapted to store the previous input value therein is loaded with .sub.0 (X)=.alpha..sup.j1. Thus the operation for n=1 is completed.
Thereafter, an operation for n=2 is carried out.
That is, as .alpha..sup.j2 corresponding to the second erasure position is inputted, the multiplexor 52 selects .alpha..sup.j1. At this time, 1 is loaded in the storing register 51, since the first and second registers 53 and 54 have been set to 1 and 0, respectively.
Then, the first and second registers 53 and 54 are loaded with .sub.i (X)=.alpha..sup.j1 and .sub.i-1 (X)=1, respectively. The multiplier 55 then multiplies the value .sub.i-1 (X)=1 loaded in the second register 54 and the value .alpha..sup.j2 corresponding to the power value of the second erasure position received from the erasure position power value input and thus outputs the value .alpha..sup.j2. The output value .alpha..sup.j2 from the multiplier 55 is applied to the adder 56, so that it is added with the value .alpha..sup.j1 loaded in the first register 53.
Accordingly, the storing register 51 receives the output value .alpha..sup.j1 +.alpha..sup.J2 from the adder 56 and stores it therein.
At this time, the multiplexor 52 selects 0,
Since the values .sub.i (X) and .sub.i-1 (X) of the first and second registers 53 and 54 are 0 and 1 ( .sub.i (X)=0 and .sub.i-1 (X)=1), respectively, the value .alpha..sup.j1 .alpha..sup.J2 subsequently operated through the multiplier 55 and the adder 56 is applied to the storing register 51. Thus, the operation for n=2 is completed.
At this time, the content loaded in the storing register 51 includes .sub.0 (X)=.alpha..sup.j1 +.alpha..sup.j2, .sub.2 (X)=.alpha..sup.j1 .alpha..sup.j2, .sub.2 (X)=1, .sub.3 (X)=.alpha..sup.j1 and .sub.4 (X)=1.
As the operation is repeated up to n=e, in such a manner, coefficients of the erasure position polynomial are sequentially stored in the storing register 51.
Referring to FIG. 9, there is illustrated variations in values .sub.i and .sub.i-1 stored in the first and second registers 53 and 54 and in value (X) loaded in the storing register 51.
Now, a procedure that the value corresponding to the input erasure position and the value loaded in the second register 54 are multiplied in the multiplier 55 will be described, in conjunction with FIGS. 7 and 8.
The AND gates AD.sub.1.1, AD.sub.1.3, AD.sub.1.5 and AD.sub.1.7 for AND-combining 4-bit input data .tau..sub.0, .tau..sub.1, .tau..sub.2 and .tau..sub.3 and 4-bit input data .beta..sub.0, .beta..sub.1, .beta..sub.2 and .beta..sub.3 output values .tau..sub.0 .multidot..beta..sub.0, .tau..sub.1 .multidot..beta..sub.0, .tau..sub.2 .multidot..beta..sub.0 and .tau..sub.3 .multidot..beta..sub.0, respectively. The AND gates AD.sub.3.1, AD.sub.3.3, AD.sub.3.5 and AD.sub.3.7 output values .tau..sub.0 .multidot..beta..sub.1, .tau..sub.1 .multidot..beta..sub.1, .tau..sub.2 .multidot..beta..sub.1 and .tau..sub.3 .multidot..beta..sub.1, respectively. The exclusive OR gate XOR.sub.4.4 outputs a value ((.tau..sub.0 .multidot..beta..sub.1)+(.tau..sub.1 .multidot..beta..sub.1)X+(.tau..sub.2 .multidot..beta..sub.1)X.sup.2 +(.tau..sub.3 .multidot..beta..sub.1)X.sup.3)X.
On the other hand, the AND gates AD.sub.5.1, AD.sub.5.3, AD.sub.5.5 and AD.sub.5.7 output values .tau..sub.0 .multidot..beta..sub.2, .tau..sub.1 .multidot..beta..sub.2, .tau..sub.2.multidot..beta..sub.2 and .tau..sub.3 .multidot..beta..sub.2, respectively. The exclusive OR gates XOR.sub.6.4 and XOR.sub.6.6 output a value ((.tau..sub.0 .multidot..beta..sub.2)+(.tau..sub.1 .multidot..beta..sub.2)X+(.tau..sub.2 .multidot..beta..sub.2)X.sup.2 +(.tau..sub.3 .multidot..beta..sub.2)X.sup.3)X. The AND gates AD.sub.7.1, AD.sub.7.3, AD.sub.7.5 and AD.sub.7.7 output values .tau..sub.0 .multidot..beta..sub.3, .tau..sub.1 .multidot..beta..sub.3, .tau..sub.2 .multidot..beta..sub.3 and .tau..sub.3 .multidot..beta..sub.3 respectively.
The values outputted from the AND gates AD.sub.7.1, AD.sub.7.3, AD.sub.7.5 and AD.sub.7.7 are applied to the exclusive OR gates XOR.sub.8.4, XOR.sub.8.6 and XOR.sub.8.8 which, in turn, perform exclusive ORing operations and thus output a value ((.tau..sub.0 .multidot..beta..sub.3)+(.tau..sub.1 .multidot..beta..sub.3)X+(.tau..sub.2 .multidot..beta..sub.3)X.sup.2 +(.tau..sub.3 .multidot..beta..sub.3)X.sup.3)X.sup.2.
As mentioned above, the AND gates AD.sub.1.1, AD.sub.1.3, AD.sub.1.5, AD.sub.1.7, AD.sub.3.1, AD.sub.3.3, AD.sub.3.5, AD.sub.3.7, AD.sub.5.1, AD.sub.5.3, AD.sub.5.5, AD.sub.5.7, AD.sub.7.1, AD.sub.7.3, AD.sub.7.5 and AD.sub.7.7 are always fixed, irrespective of the source polynomial P(X). However, the exclusive OR gates XOR.sub.6.4, XOR.sub.6.6, XOR.sub.8.4, XOR.sub.8.6 and XOR.sub.8.8 are determined by the source polynomial P(X).
In a calculation with respect to an optional source polynomial P(X)=P.sub.3 X.sup.3 +P.sub.2 X.sup.2 +P.sub.1 X+P.sub.0, a circuit of FIG. 8 may be used.
The exclusive OR gate XOR.sub.9.2 receives outputs from the AND gates AD.sub.1.1, AD.sub.3.7, AD.sub.5.5 and AD.sub.7.3 and exclusively ORs them, to output a final value W.sub.0. The exclusive OR gate XOR.sub.9.4 receives an output from the AND gate AD.sub.1.3 and outputs from the exclusive OR gates XOR.sub.4.4, XOR.sub.6.4 and XOR.sub.8.4 and exclusively ORs them, to output a final value W.sub.1.
On the other hand, the exclusive OR gate XOR.sub.9.6 receives outputs from the AND gates AD.sub.1.5 and AD.sub.3.3 and outputs from the exclusive OR gates XOR.sub.6.6 and XOR.sub.8.6 and exclusively ORs them, to output a final value W.sub.2. The exclusive OR gate XOR.sub.9.8 receives outputs from the AND gates AD.sub.1.7, AD.sub.3.5 and AD.sub.5.3 and an output from the exclusive OR gate XOR.sub.8.8 and exclusively ORs them, to output a final value W.sub.3.
The calculation procedures are summarized by the following equation: ##EQU3##
The value W is applied to the adder 56 of FIG. 6 and added with the value stored in the first register 53.
That is, when the value (.tau..multidot..beta.)+.THETA. is required to be derived, which corresponds to a value obtained by adding the value .THETA. stored in the first register 53 to the value .tau..multidot..beta. inputted at the adder 56, input data .THETA..sub.0, .THETA..sub.1, .THETA..sub.2 and .THETA..sub.3 are applied to inputs of the exclusive OR gates XOR.sub.9.2, XOR.sub.9.4, XOR.sub.9.6 and XOR.sub.9.8, respectively.
For an operation in GF(2.sup.m) other than GF(2.sup.4), it can be achieved by an expansion design up to 2M+1 rows and 2M columns.
FIG. 10 is a block diagram of a Forney syndrome operation apparatus according to a second embodiment of the present invention.
As shown in FIG. 10, the operation apparatus comprises a storing register 61 for storing results sequentially inputted therein, a multiplexor 62 for receiving outputs from the storing register 61 and selecting a necessary coefficient, and a switch SW for selecting one of an output value of the multiplexor 62 and a syndrome S(X). To the multiplexor 62, a first register 63 and a second register 64 are connected via the switch SW. The registers 53 and 64 receive the coefficient currently selected by the multiplexor 52 and the coefficient just previously selected by the multiplexor 52, respectively. The operation apparatus also comprises a multiplier 65 for multiplying a power value .alpha..sup.jk corresponding to an input erasure position and the coefficient loaded in the second register 64, and an adder 66 for adding a value outputted from the multiplier 65 to the coefficient loaded in the first register 63 and outputting the resultant value to the storing register 61.
The Forney syndrome is expressed by the following equation: ##EQU4## wherein, e represents the number of erasures.
Accordingly, the syndrome S(X), can be calculated in the order of T.sub.1 (X).fwdarw.T.sub.2 (X) . . . .fwdarw.T.sub.e (X), in similar manner to the erasure position polynomial.
In this case, the i-th coefficient of T.sub.n (X) is expressed as follows:
The above procedure will be described in detail.
Initially, the switch SW is connected at its movable terminal c to its fixed terminal a so that S.sub.0 to S.sub.2t-1 of the syndrome S(X) are sequentially inputted.
When a calculation through the first and second registers and 64, the multiplier 65 and tile adder 66 is completed, the storing register 61 is loaded with S.sub.2t-1.alpha..sup.j1, S.sub.2t-1.alpha..sup.j1 +S.sub.2t-1, . . . , S.sub.1 .alpha..sup.j1 +S.sub.0 and S.sub.0.alpha..sup.j1 +S.sub.0, in this order,
Thereafter, the switch SW is switched such that the movable terminal c is connected to the fixed terminal b. At this time, the first and second registers 63 and 64 are set to 0. Then, the multiplexor 62 selects S.sub.0.alpha..sup.j1 +S.sub.1. Accordingly, the values T.sub.i and T.sub.i-1 stored in the first and second registers 63 and 64 become S.sub.0.alpha..sup.j1 +S.sub.1 and S.sub.0, respectively, so that the storing register 61 receives S.sub.0.alpha..sup.j2 +S.sub.0 .alpha..sup.j1 +S.sub.1 as its input The multiplexor 62 selects S.sub.1 .alpha..sup.j1 +S.sub.2.
After the operation is carried out up to S.sub.2t-1 .alpha..sup.j2, the calculation for n=2 is completed.
That is, the calculation is repeated 2t+1 times, for calculating T.sub.2 (X). For n=3, calculations of 2t+1 times are repeatedly carried out, so as to complete the calculation for T.sub.3 (X)
After the polynomial T(X) with the degree of 2t-1+e is calculated by repeating the above procedures, it is applied to the storing register 61.
The switch SW may be omitted. In this case, the syndrome S(X) is directly inputted at the storing register 6.
The storing registers 51 and 61 are capable of storing the maximum length, namely, 2t+e coefficients. Preferably, they are last-in first-out registers.
As apparent from the above description, the present invention makes it possible to derive an erasure position polynomial by using a single multiplier and a single adder, irrespective of an error correction capacity, upon sequentially deriving coefficients of the erasure position polynomial while increasing the degree of the erasure position polynomial one by one. Accordingly, an integration of the operation apparatus can be possible. Also, the present invention provides effects of simplifying the design of the adder and achieving a correct operation.
Although the preferred embodiments of the invention have been disclosed for illustrative purposes, those skilled in the art will appreciate that various modifications, additions and substitutions are possible, without departing from the scope and spirit of the invention as recited in the accompanying claims.
Claims
What is claimed is:
1. An operation apparatus for deriving an erasure position polynomial of a Galois field, comprising: a storing register means for storing result values sequentially inputted therein; a multiplexor means for receiving outputs from the storing register means and selecting a necessary coefficient therefrom; a first register means and a second register means for storing a coefficient currently selected by the multiplexor means and a coefficient previously selected by the multiplexor means, respectively; a single multiplier means for multiplying a value, corresponding to an input erasure position and the coefficient loaded in the second register means; and a single adder means for adding a value outputted from the multiplier means to the coefficient stored in the first register means and inputting the resultant value to the storing register means.
2. An operation apparatus for deriving an erasure position polynomial of a Galois field, comprising: a storing register for storing result values sequentially inputted therein; a multiplexor for receiving outputs from the storing register and selecting a necessary coefficient therefrom; a first register and a second register for storing a coefficient currently selected by the multiplexor and a coefficient previously selected by the multiplexor, respectively; a multiplier for multiplying a value corresponding to an input erasure position and the coefficient stored in the second register; and an adder for adding a value outputted from the multiplier to the coefficient stored in the first register and inputting the resultant value to the storing register: wherein the adder logically operates multiplication outputs (W.sub.0, W.sub.1, W.sub.2 and W.sub.3) for a 4-bit input data (.tau..sub.0, .tau..sub.1, .tau..sub.2 and .tau..sub.3) and 4-bit input data (.beta..sub.0, .beta..sub.1, .beta..sub.2 and .beta..sub.3), in the following order: .multidot..beta..sub.3)+(.tau..sub.3 .multidot..beta..sub.1)+(.tau..sub.2 .multidot..beta..sub.2) .multidot..beta..sub.1)+(.tau..sub.0 .multidot..beta..sub.1)+((.tau..sub.3 .multidot..beta..sub.2)+(.tau..sub.2 .multidot..beta..sub.2))+(.tau..sub.1 .multidot..beta..sub.3) .multidot..beta..sub.1)+((.tau..sub.3 .multidot..beta..sub.2)+(.tau..sub.0 .multidot..beta..sub.2))+((.tau..sub.2 .multidot..beta..sub.3)+(.tau..sub.3 .multidot..beta..sub.3)) .multidot..beta..sub.1)+(.tau..sub.1 .multidot..beta..sub.2)+((.tau..sub.0 .multidot..beta..sub.3)+(.tau..sub.3 .multidot..beta..sub.3)).
3. An operation apparatus for deriving an erasure position polynomial of a Galois field, comprising: a storing register for storing result values sequentially inputted therein; a multiplexor for receiving outputs from the storing register and selecting a necessary coefficient therefrom; a first register and a second register for storing a coefficient currently selected by the multiplexor and a coefficient previously selected by the multiplexor, respectively; a multiplier for multiplying a value corresponding to an input erasure position and the coefficient stored in the second register; where in the multiplier comprises: a plurality of AND gates (AD.sub.1.1, AD.sub.1.3, AD.sub.1.5, AD.sub.1.7, AD.sub.3.1, AD.sub.3.3, AD.sub.3.5, AD.sub.3.7, AD.sub.5.1, AD.sub.5.3, AD.sub.5.5, AD.sub.5.7, AD.sub.7.1, AD.sub.7.3, AD.sub.7.5 and AD.sub.7.7) each for AND-combining a selected one of 4-bit input data (.tau..sub.0, .tau..sub.1, .tau..sub.2 and .tau..sub.3) and a selected one of 4-bit input data (.beta..sub.0, .beta..sub.1, .beta..sub.2 .beta..sub.3); a plurality of exclusive OR gates (XOR.sub.4.4, XOR.sub.6.4, XOR.sub.6.6, XOR.sub.8.4, XOR.sub.8.6 and XOR.sub.8.8) for exclusively ORing outputs from the AND gates (AD.sub.3.1 and AD.sub.3.7), outputs from the AND gates (AD.sub.5.5 and AD.sub.5.7), outputs from the AND gates (AD.sub.5.1 and AD.sub.5.7), output from the AND gates (AD.sub.7.1 and AD.sub.7.3), and outputs from the AND gates (AD.sub.7.5 and AD.sub.7.7), and outputs from the AND gates (AD.sub.7.2 and AD.sub.7.7), respectively; an exclusive OR gate (XOR.sub.9.2) for exclusively ORing outputs from the AND gates (AD.sub.1.1, AD.sub.3.7, AD.sub.5.5 and AD.sub.7.3) and outputting a resultant value (W.sub.0); an exclusive OR gate (XOR.sub.9.4) for exclusively ORing an output from the AND gate (AD.sub.1.3) and outputs from the exclusive OR gates (XOR.sub.4.4, XOR.sub.6.4 and XOR.sub.8.4) and outputting a resultant value (W.sub.1); an exclusive OR gate (XOR.sub.9.6) for exclusively ORing outputs from the AND gates (AD.sub.1.5 and AD.sub.3.3) and outputs from the exclusive OR gates (XOR.sub.6.6 AND XOR.sub.8.6) and outputting a resultant value (W.sub.2); and an exclusive OR gate (XOR.sub.9.8) for exclusively ORing outputs from the AND gates (AD.sub.1.7, AD.sub.3.5 and AD.sub.5.3) and an output from the exclusive OR gate (XOR.sub.8.8) and outputting a resultant value (W.sub.3), and an adder for adding a value outputted from the multiplier to the coefficient stored in the first register and inputting the resultant value to the storing register.
4. An operation apparatus in accordance with claim 1, further comprising a switch mean for selecting the value outputted from the multiplexor means and a syndrome value and sending them to the first register.
5. An operation apparatus in accordance with claim 1, wherein the storing register means is a last-in first-out register.
6. An operation apparatus in accordance with claim 1, wherein the storing register means receives a syndrome value directly.