JPH0642632B2 - Arithmetic unit on Galois field - Google Patents

Description

Description: BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a digital signal error correction circuit, and more particularly to a Galois field arithmetic unit suitable for decoding Reed-Solomon codes.

[Background of the Invention]

In order to perform decoding of error correction codes such as Reed-Solomon codes, it is necessary to perform operations (multiplication, division and addition) on the Galois field. In particular, when the Reed-Solomon code with a large minimum distance is to be decoded, a high-order polynomial operation must be performed.

As a conventional arithmetic device on a Galois field, Japanese Patent Laid-Open No. 58-219
As described in No. 848, the multiplier is divided into two parts, the multiplicand is gate-controlled for each bit of the multiplier, and the output is sequentially added twice. It is known to do it once. Since this device does not require a large-capacity memory, the circuit scale can be reduced.

However, the control is complicated, and two steps are required for one multiplication. In addition, when a high-order polynomial operation is performed, since the power operation and the storage of the operation result are not taken into consideration, the RAM as a work buffer is frequently accessed and the number of operation steps increases. There is.

[Object of the Invention]

An object of the present invention is to provide an arithmetic unit on a Galois field that can execute a complex high-order polynomial operation with a small number of steps.

[Outline of Invention]

In the arithmetic unit of the present invention, multiplication or division and addition are simultaneously performed, and an auxiliary register is incorporated in a high-speed multiplication or division circuit to reduce the number of steps of exponentiation operation in a high-order polynomial, and further to the input unit of the addition circuit. By incorporating a selection circuit for the input from the data bus and the output of the multiplication / division circuit, the number of steps of the polynomial operation is reduced.

Example of Invention

An embodiment of the present invention will be described below with reference to FIG. In the figure, 1, 5 and 6 are registers for storing the input data from the data bus, 2 is a conversion ROM for obtaining the reciprocal from the output of the Y-register 1, and 7 is multiplication on the Galois field GF (2 ^m ). Multiplication circuit 4 which performs
-Output of register 1, output of reciprocal conversion ROM 2 and LX
An MPX circuit that selects any of the outputs of register 5. Further, 11 is an adder circuit for performing addition on the Galois field GF (2 ^m ), and 8 is data as an addend in the adder circuit.
An MPX circuit that selects either the input data from the bus or the output of the arithmetic unit, 10 a gate circuit that gate-controls the output of the MPX circuit 8, and 12 the data of the output of the adder circuit 11.
This is an Au buffer for outputting on the bus. Also, 13,1
Reference numerals 6, 17 and 18 denote Y-register 1, Z-register 9, X-register 6 and LX-register 5, YCP and Z, respectively.
CP, XCP, LXCP pulse input terminals, 14 and 15 are YS and ZS control signal input terminals of MPX circuits 4 and 8, respectively.
Reference numeral 19 is a ZC gate signal input terminal of the gate circuit 10.

First, regarding the arithmetic circuit on the Galois field GF (2 ^m ),
(2 ³ ) will be described as an example.

If one of the roots of the irreducible polynomial F (x) on GF (2) is α,
A set obtained by adding six elements represented by powers of α to the elements “0” and “1” of GF (2) {0, 1, α, α ² , α ³ , α ⁴ , α ⁵ , α ⁶ }. Constitutes GF (2 ³ ).

If F (x) = x ³ + x + 1, then α ³ = α + 1. And representation powers of GF (2 ³⁾ at this time shows a vector representation in Table 1.

Here, the multiplication on GF (2 ³ ) is X * Y, the division on GF (2 ³ ) is X / Y, the addition on GF (2 ³ ) is XY, and A = (a ₂ , a ₁ , If a ₀ ) = a ₂ x ² + a ₁ x + a ₀ B = (b ₂ , b ₁ , b ₀ ) = b ₂ x ² + b ₁ x + b ₀ , then AB = (a ₂ + b ₂ , a ₁ + b ₁ , a ₀ + b ₀ ) A * B = (a ₂ x ² + a ₁ x + a ₀ ) ・ (b ₂ x ² + b ₁ X + b ₀ ) mod (x ³ + x +1) = (a ₂ b ₂ + a ₂ b ₀ + a ₁ b ₁ + a ₀ b ₂ ) x ² + (a ₂ b ₂ + a ₂ b ₁ + a ₁ b ₂ + a ₁ b ₀ + a ₀ b ₁ ) x + (a ₂ b ₁ + a ₁ b ₂ + a ₀ b ₀ ). However ^{mod (x 3 + x + 1} ) indicates a multiplication modulo ^{(x 3 + x + 1)} . Normally, a digital signal is treated as a binary number (that is, a vector expression in Table 1), and therefore addition of mod2 (exclusive OR) may be performed for each bit.

FIG. 2 shows the adder circuit 11 when c = (c ₂ , c ₁ , c ₀ ) = AB. In the figure, 21
Is an A input terminal, 22 is a B input terminal, and 23 is a C output terminal. Clearly, subtraction on Galois field is the same as addition.

Regarding multiplication, if D = (d ₂ , d ₁ , d ₀ ) = A * B, And this operation is performed with 9 ANDs as shown in FIG.
Circuit and nine EOR circuits. In the figure, 31 is a D output terminal.

The addition circuit and the multiplication circuit can be similarly configured for other Galois fields such as GF (2 ⁸ ).

Next, division will be described.

The division E = A / B can be transformed as follows.

E = A * (1 / B) Therefore, if the reciprocal of B (1 / B) is obtained, division can be performed using the multiplication circuit of FIG. The Y-ROM 2 shown in FIG. 1 has a reciprocal 1 / Y from the output Y of the Y-register 1.
The division can be performed by selecting M by the MPX circuit 4.

The gate circuit 10 of FIG. 1 uses the output Z of the MPX circuit 8 as the addend Zb = (Zb ₂ , Zb ₁ , Zb ₀ ) in the adder circuit 11.
This is a gate for selecting whether a = (Za ₂ , Za ₁ , Za ₀ ) or 0, and is composed of an AND circuit as shown in FIG. In the figure, 41 is a Za input terminal from the MPX circuit 8, 42 is a Zb output terminal to the adder circuit 11, and 19 is a ZC gate signal input terminal.

Next, a specific operation of the arithmetic unit shown in FIG. 1 will be described by taking the following high-order polynomial arithmetic as an example.

The operation of R = S ⁴ T * S ³ 1 / U * S ² V * SW registers 1, 5, 6, 9, MPX circuits 4, 8 and gate circuit 10 is as shown in Table 2, but The explanation for each step is given in. Here, to latch data in each register, YCP pulse input terminal 13 (Y-register 1), ZCP pulse input terminal 16 (Z-register 9), XCP pulse input terminal 17 (X-register 6), L
A control pulse may be applied to the XCP pulse input terminal 18 (LX-register 5). Also, the MPX circuit 4 sends a 2-bit control signal to the YS control signal input terminal 14. No. (3 bits are selected, 2 bits are required), L, M, N are selected, and the MPX circuit 8 receives the ZS control signal input terminal 15
Q or P is selected by a control signal sent to. When the output of the gate circuit 10 takes Za, 1 is added to it, and when it takes 0, 0 is added to the ZC terminal 19.

The MPX circuit 8 is selected as Q and the data W is latched in the Z-register 9.

The data V is latched in the Y-register 1.

The data S is latched in the X-register 6 and the LX-register 5. After that, data is not latched in the LX-register 5 and the value of S is always held.

When the MPX circuit 4 is selected to be L and the gate signal input to the gate circuit 10 is set to 1, the output of the adder circuit 11 becomes X * YZ = S * VW = V * SW. At this time, by selecting the MPX circuit 8 to P, this operation result is latched in the Z-register 9. Also, by controlling the output of the Au buffer 12 to the data bus by the control signal of the terminal 20, the bus becomes free so that the data U can be latched in the Y-register 1 during this step. The reciprocal 1 / U is output from the Y-ROM 2.

When the MPX circuit 4 is selected as N and the gate signal input of the gate circuit 10 is set to 0, the output of the adder circuit 11 becomes And is output to the data bus and then latched in the X-register 6.

X = S ² . Also, the latch 3 receives Y by the pulse to the terminal 0.
-Latch the output 1 / U of ROM2.

When the MPX circuit 4 is selected as M and the gate signal input of the gate circuit 10 is set to 1, the output of the addition circuit 11 is: X * (1 / Y) Z = S ² * 1 / U (V * SW) = 1 / U * S ² V * SW. The MPX circuit 8 is selected as P, and this data is latched in the Z-register 9. At the same time, the data T is latched in the Y-register 1.

In the same way as the step, the output of the adder circuit 11 is And is latched in the X-register 6.

In the same way as the step, set X-YZ in the Z-register.
= S ³ * T (1 / U * S ² V * SW) = T * S ² 1 / U * S ² V * SW is latched.

When the MPX circuit 4 is selected as N and the gate input signal of the gate circuit 10 is set to 1, the output of the adder circuit 11 is: X * LXZ = S ³ * S (T * S ³ 1 / U * S ²
V * SW) = S ⁴ T * S ³ 1 / U * S ² V * SW, which is output on the data bus.

Stores the data S to the LX- register 5 as described above, by performing gated gate circuit 10 at the same time, S ^K
From S ^{K + 1} can be performed without newly inputting the data S or manipulating the Z-register 9. Further, since the MPX circuit 8 can latch the operation result in the Z-register 9 without passing through the data bus, the number of steps of the polynomial operation can be reduced.

By the way, in the above calculation, the MPX circuit 4 and the gate circuit 10 are controlled separately, but when the MPX circuit 4 selects N, the gate input signal of the gate circuit 10 is set to 0, so that the number of control signals is increased. Can be reduced.
A block diagram in this case is shown in FIG. This figure shows the ZC gate signal input terminal 19 of the gate circuit 10 in FIG.
1 bit Y of the YS control signal input terminal 14 of the MPX circuit 4
It is shared with S ₀ .

When the apparatus of FIG. 5 is used, as can be seen from Table 2, the same operation can be performed from step to step.
The operation after the step will be described as another embodiment.

'X * YZ to the Z register 9 in the same way as in step'
= S ³ * T (1 / U * S ² V * SW = T * S ³ 1 / U * S ² V * SW is latched, and at the same time, the data S is latched in the Y-register 1.

′ When the MPX circuit 4 is selected as L, the output of the adder circuit 11 is: X * YZ = S ³ * S) T * S ³ 1 / U * S ² V
* SW) = S ⁴ T * S ³ 1 / U * S ² V * SW, which is output on the data bus.

Thus, even if a part of the control input of the MPX circuit 4 is used as the control input of the gate circuit 10, the number of steps can be made the same depending on the method of calculation.

〔The invention's effect〕

According to the present invention, there is an effect of reducing the number of calculation steps of a high-order polynomial in a calculation device on a Galois field.

[Brief description of drawings]

FIG. 1 is a block diagram of an arithmetic unit according to the present invention, FIG. 2 is an addition circuit diagram, FIG. 3 is a multiplication circuit diagram, and FIG. 4 is a gate circuit diagram.
As another embodiment, FIG. 5 is an example of a block diagram of an arithmetic unit capable of reducing the number of control signals without changing the number of arithmetic steps. 1,3,5,6,9 …… Latch circuit 2 …… Conversion ROM, 4,8 …… MPX circuit 7 …… Multiplication circuit, 10 …… Gate circuit 11 …… Adding circuit, 12 …… Output buffer 13, 14,15,16,17,18 …… Control signal input terminal

Claims (1)

[Claims] 1. An arithmetic unit for performing an operation on a Galois field GF (2 ^m ), a data bus for inputting data from the outside, and a first memory instruction input terminal (13) for inputting a first memory instruction.
And a second memory command input terminal (18) for inputting a second memory command
And a third memory command input terminal (17) for inputting a third memory command
And a fourth memory command input terminal (16) for inputting a fourth memory command
A first memory circuit (1) for storing data on the data bus in accordance with a first memory instruction input from the first memory instruction input terminal; A second memory circuit (5) for storing the second memory command according to the second memory command input from the second memory command input terminal; and a third memory circuit for inputting the data on the data bus to the third memory command input terminal. A third memory circuit (6) for storing in accordance with the memory command of the first memory circuit, a conversion circuit (2) for outputting the reciprocal of the data stored in the first memory circuit, and an output of the first memory circuit, A first selection circuit (4) for selecting either the output of the second storage circuit or the output of the conversion circuit, and a Galois output of the first selection circuit and the output of the third storage circuit. a multiplier circuit for multiplying on the body ^{GF (2 m) (7)} , or the data on the data bus, out of the computing device A second selection circuit (8) for selecting any one of them, and a fourth selection circuit for storing the output of the second selection circuit according to a fourth storage instruction input from the fourth storage instruction input terminal. The output of the memory circuit (9) and the fourth memory circuit is output as it is or 0
And a Galois field G of the output of the multiplication circuit and the output of the gate circuit.
An arithmetic unit on a Galois field comprising an adder circuit (11) for performing addition on F (2 ^m ) and outputting the addition result as an output of the arithmetic unit.