JPH03182122A - Division circuit for finite field - Google Patents

Abstract

PURPOSE:To make a circuit scale compact and to accelerate calculation speed by calculating the inverse element of a divisor out of a divident and the divisor expressed by a vector with (m) bits on a finite field GF (2<m>) by vector expression and multiplying the divident and the inverse element of the divisor while converting one of them to a matrix expression. CONSTITUTION:When a quotient x/y of two elements (x) and (y) on the finite field GF (2<m>) is calculated, at first, an inverse element y<-1> of the first element (y) is generated with the vector expression by an inverse element generating circuit 3 and afterwards, multiplier circuits 1 and 2 convert the second element (x) to the matrix expression and multiply this element (x) in the matrix expression and the inverse element y<-1> in the vector expression. Then, the quotient x/y is calculated in the vector expression. In comparison with a conventional circuit using a ROM as three conversion tables, the circuit scale of the inverse element generating circuit 3 becomes about 1/3 and the inverse element generating circuit 3 is used only once. Thus, the circuit scale of the multiplier circuit on the finite field GF (2<m>) is made compact and the calculation speed can be accelerated.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a finite field division circuit applied to, for example, an encoder or decoder of an error correction code.

[Summary of the invention]

The present invention is applicable to a finite field division circuit applied to, for example, an encoder or decoder of an error correction code.
2m) Find the inverse of the divisor of the dividend and divisor expressed as vectors using m bits above in vector expression, convert one of the dividend and the inverse of the divisor to matrix expression, and multiply. This allows the circuit scale to be reduced and the calculation speed to be increased.

[Conventional technology]

BACKGROUND ART When recording and reproducing digital video signals, digital audio signals, etc., adjacent codes, Lead-Don-Romon codes, and the like have been put into practical use as error correction codes. These error correction code encoders use parity data (redundant data)
The decoder generates a syndrome from the received signal including parity data, and performs error correction using this syndrome. These parity generation circuits, syndrome generation circuits, and error correction circuits use an arithmetic circuit for a finite field (Galois field) GF(p''') of order pH.The finite field GF(p''') is a calculation circuit of order m It is a field with p''' elements derived from the irreducible polynomial P (X), and in the error correction code, only the case where p=2 is important. That is, finite field GF
(2m).

The arithmetic circuit on the finite field GF (2m) includes an addition circuit (GF
(On 2m>, the subtraction circuit has the same structure), the multiplication circuit, and the division circuit, but the addition circuit among these can be easily realized using an exclusive OR gate.

However, the configurations of the multiplication circuit and the division circuit are complicated.

A conventional example of a division circuit is a ROM as a conversion table.
Circuits using this are known. If the irreducible polynomial of the finite field GF(2m) is set to 0 and the root is α, then the elements of this finite field other than O are expressed as powers of α. And α
When calculating the quotient (αl/α'') between 1 and αj, input α1 into the ROM to obtain the index i, and also
After obtaining the index j by inputting it into OM, the subtraction circuit calculates (i
−j), input this index (i−j) into the ROM, and output α″″j. On the other hand, regarding a multiplication circuit on a finite field G F (2m), Japanese Patent Application Laid-open No. 144834/1983 describes a method to reduce the circuit size and increase the calculation speed by using a matrix representation of the finite field. A multiplication circuit has been proposed.

[Problem to be solved by the invention]

However, with respect to the division circuit on the finite field G F (2m>), no effective method has been proposed other than the circuit using the above-mentioned conversion table, which has the disadvantages of large circuit scale and slow calculation speed.

Furthermore, in an actual error correction circuit, it is necessary to execute multiple divisions at the same time, and the divisor or dividend of each of these multiple divisions may be the same.
In such a case, simply arranging a plurality of the same M4 dividers in parallel has the disadvantage of further increasing the circuit scale.

In view of the above, an object of the present invention is to reduce the circuit scale of a division circuit on a finite field GF (2m) and increase the calculation speed.

The present invention further provides further miniaturization of the circuit scale when multiple divisions are simultaneously executed on the finite field GF (2m) and when the respective divisors or dividends in the multiple divisions are the same. purpose.

[Means to solve the problem]

The finite field division circuit according to claim 1, for example, as shown in FIG. The crystallographic circuit (3) generated in and the inverse element y-1 of its first element y
and a second element X expressed as a vector with m bits on the finite field GF (2m), respectively, with multiplication circuits (1) and (2) that convert one element into a matrix expression and multiply them, The quotient x/y obtained by dividing the second element X by the first element y is the quotient x/y of the finite field CF (
2') is obtained by the m-bit vector representation above.

In the invention according to claim 2, the multiplication circuits (1) and (2) are configured to convert the second element X into a matrix representation.

The invention as claimed in claim 3 provides a method for each of a group of elements a, c, e expressed as a vector with m bits on a finite field CF (2m〉) and one common element Quotient x/a
, x/c, x/e or a/x.

In the division circuit for obtaining c/x and e/x, a plurality of inverse element generation circuits or one inverse element generation circuit that generates the inverse elements of each of the elements a, c, and e of the group or the inverse element of their common element X in vector representation. (3A), (3B), (3C) and their common element X
directly or through its inverse generator circuit to represent the matrix T (
a representation conversion circuit (1) that converts into
/c, 1/e vector representation and its representation conversion circuit (1)
A plurality of multiplication circuits (2^), (2B), and (2C) are provided for multiplying the matrix representation T (X) outputted from.

[Effect]

According to the invention described in claim 1, when calculating the quotient x/y of two elements x and y on the finite field CF (2m), the inverse element generation circuit (3) first generates the inverse element of the first element y. After generating y −1 in vector representation, convert its second element
By multiplying by -1, the quotient x/y is obtained in vector representation. Note that it is also possible to convert the inverse element y-1 into a matrix representation and multiply the inverse element y-1 of this matrix representation by the element X of the vector representation. In addition, the inverse generator circuit (
3) is constructed with ROM etc. as a conversion table and has a relatively large circuit scale, but compared to the conventional circuit which uses ROM as three conversion tables, the inverse element generation circuit (3) is The circuit scale is reduced to about 1/3, and the overall circuit scale can be reduced.

Furthermore, since the inverse element generating circuit (3) is used only once, the overall calculation speed can be increased.

Furthermore, when the multiplication circuits (1) and (2) convert the second element X into a matrix representation, for example, as shown in FIG. The conversion of the expression of the second element

Further, according to the invention as claimed in claim 3, when a plurality of divisions having a common dividend or divisor are executed simultaneously on the finite field GF (2'''') as shown in FIG. Element X (when X is the dividend) or its inverse element x-' (x
is the divisor> from the vector representation to the matrix representation T
Expression conversion circuit (1) that converts to (X) or T(x-')
is commonly used. Therefore, the overall circuit scale can be made smaller than when multiple identical dividers are arranged in parallel.

〔Example〕

In the present invention, a finite field customer death matrix representation disclosed in Japanese Patent Application Laid-Open No. 60-144834 is used. Therefore, in order to facilitate understanding of an embodiment of the present invention, a matrix representation of the death matrix of the finite field GF(2m) will be explained.

As an example, a coefficient of 0 or 1 (=-1) g+9g2.
Define the following primitive irreducible polynomial POO using gs,
POO= 1+g+X +g2X"+g*X'+X+・
・”(1) Order 2 where this polynomial P(X) is a modulo polynomial
Consider a finite field G'F(2') of 4. First, POO=O
Let α be the root of , α is a primitive element of the finite field GF (2′), and a non-zero visitor death of this GF (2′) can be expressed as a power αi (+ is an integer) of α. This expression is called a “power expression.”

In this case, subtraction on P■-〇 and CF (2') is the same as addition, so α'= 1 g+α-g2α2-g3α3=
1 + g + α 10 g 2 α 2 + g, α 3 ... (
2A) α5=α・α4=α+gIα2+g2α3+g3
α4”gs+(1+g3g+)α+(g++g3g
2) α2+ (g2+ g3gz) α3
...(2B> etc. holds. Therefore, α'
(i = 4.5.6°...) is 1. α, α2. α
Since it can always be expressed as a linear combination of 3, if any element on GF(2') is a, the element a iiO or 1 (=-
Using the coefficient a of 1), ~a, a = ao+ a, α+a2α2+a3α3 ・
...It can be expressed as (3). Coefficient a o ” of equation (3)
A representation in which only "a!" are arranged vertically is called a "vector representation" of element a.If the vector representation of element a is a, then using the transposition symbol (...) t, it can be expressed as.G F Each element of (2') 0.α
1 (i=o, 1°.

...14) The vector representation of 0: (0000) α0=1 : (1000) α': (01
01) αI=(Ol 00) α”: (111
0) α': (0010) α11. (Q
1 1 1) α': (0001) α'': (
1111) α': (1100) α'': (1
011) α1: (1001) Customer death a other than O on GF(2') can be expressed by α1, and the original one-matrix representation of α1 (α1) is expressed as the following formula using the vector representation al of α1 Defined by

T (α') = [α1 αl+I αl+2 α'+
3] Specifically, the matrix representation T(αl) of α1 is as follows.

T(α') = [α1 α2 α3 α4] GF
Since any element on G F (2m), which is a film of (2'), can be expressed as an m-bit binary number in vector representation,
Vector representation is used in actual logic circuits. However, element a (=α′) and element b (=α”) on CF (2m〉)
(j is an integer) to obtain the multiplication result a-b, that is, α1α, the element α1. If αj are both vector representations, there is no easy way to obtain the vector representation of the multiplication result. However, by converting either α gourd or αj into a matrix representation, the vector representation of the multiplication result α1·α can be easily obtained.

That is, α1 is the coefficient a on the finite field G F (2')
.

Using ~a3, αj is also a coefficient. -b, is expressed as a vector as follows: 2N'= (ao a, a, a3)'
, -1, (6) α"" (bo b
+ b2 bs)' ...(7)
αj is 1 as follows. α, α2. It can be expressed as a linear combination of α3. Note that α1, that is, a is expressed by equation (3).

α'=bO+, blα+b2α2+b, α3...
(8) Therefore, the product of a and b, that is, the product of α1 and αj, is aIb=α1・α" = α'(bo+blα+b2α2+b3α3)=α'b
o+α101 b1+αI*2 b2+αj*3 b.

...(9) It is expressed as follows. From formula (5), α1~ in formula (9)
The vector representations of αl+3 are as follows.

α””(To. T o 1T O2T 0*) '
αi++=(T1゜ T1.T, T1.)tαl+2=
(72゜ T□ Tzz T23)'α”'= (T
ffOT31 Ts2 T33)' Therefore, equation (9
) and equation (5) to convert a-b into a vector representation, t = [α1 α1・1 αl+2 α′+3]
α4=T(αl)αj...
...(10) is obtained. Therefore, by converting a, that is, αj, into a matrix representation T(α'), the vector representation of a-b can be easily obtained by simply performing the usual multiplication of a matrix and a vector.

Hereinafter, an embodiment of a finite field division circuit according to the present invention will be described with reference to the drawings. In this example, finite field GF(2')
Divide the element X above by the element y on G F (2') and get the quotient z
The present invention is applied to a division circuit that calculates (=x/y). Also, the modulus polynomial 2 of the finite field in this example P 001-!
Coefficients g+, g2. gs is defined by the equation (1), and input data and output data are each expressed as a vector by a 4-bit binary number.

FIG. 1 shows a block diagram of the division circuit of this example.
In the figure, (1) is a representation conversion circuit from a vector representation to a matrix representation, and this representation conversion circuit (1) receives the dividend X expressed as a vector in 4 bits and the coefficients g, ~gs(g ), and each element TIJ (0≦1.j≦
3> is generated.

(2) is a multiplication unit that generates a vector by multiplying a matrix and a vector, and (3) is a ROM for inverse element generation as a conversion table that converts the divisor y in vector representation to the inverse element y −1 in vector representation. and supplies each element of the matrix T (x) to one input port of the multiplication unit (2), and the 4-bit coefficient (y-') of the inverse element y-1 expressed as a vector to the other input port. , (y-')2. (y-'
) supply a. The output port of this multiplication unit (2) outputs 4-bit coefficients 20 to z3 of a vector representation of the quotient z (=x/y).

FIG. 2 shows a specific circuit configuration of the example shown in FIG. 1. In the expression conversion circuit (1) of FIG.
1) to (13) and (17) to (19) are AND gates, and (8) to (10), respectively.

(14) to (16) and (20) to (22) are exclusive OR gates (hereinafter referred to as rEXORεXOR gates), respectively.
The AND gate is used as a multiplier of two coefficients, and the εXOR gate is used as a mad 2 adder of two coefficients. In this case, if the vector representation of the dividend X is (Xo

Coefficient x3 is commonly supplied to one input terminal of (6) and (7), and coefficients g++ gz, g are respectively supplied to the other input terminal.
s and εXOR gates (8), (9), (1
0) Coefficient XO+ xI+ X2 at one input terminal of
and εXOR gates (8), (9).

(5),
(6).

Supply the output data of (7).

Let α be the root of the modulus polynomial 2 P (X) = O, and let α1 be the power representation of the dividend X, then the matrix representation T (
X) is expressed by equation (5). In this example, the coefficient
o' = X i is each element TOO~T of matrix T (X)
Corresponding to os, coefficients X and εXOR gates (8) to (
10〉 output data is each element T't of matrix T (X)
o and elements Tll to T11.

In addition, the output data (element T
l 3 ) is commonly supplied, coefficients g, ~g, are supplied to the other input terminal, respectively, and εXOR gate (14) ~(
The coefficients Tlo-Tl2 are supplied to one input terminal of EXOR game (16), respectively, and the output data of EXOR game) (11) to (13) are supplied to the other input terminals of EXOR game) (14) to (16), respectively. .Element TI3 and εXOR gate (1
The output data of 4) to (16) correspond to elements T20 and T21-T2s of matrix T(a), respectively. Similarly, element T 23 and εXOR gate (20>~<22
> output data are elements T of matrix T (a), respectively. and T's+ to T35.

Matrix representation T (a) of multiplier a by representation conversion circuit (1)
The reason why 1h T t J is required will be explained with reference to Fig. 3.
) (5) to (7) εXOR gates (8) to (10) are shown as adders as multipliers. In this case, from equation (5), the matrix representation T (
x) is element<2', 12m'α1゛2. α1゛3
The vector representations of T (a) are arranged in four columns, and the coefficients of these vector representations become the elements of the matrix T (a) as they are.

First, the vector representation of element α1 is (Xo XI X2
X2)t, and the element α1 is 1. α, α2.
It can be expressed as a linear combination of α3.

a'=x, +x, a+x2a"+xsa'-"(
11) By multiplying both sides of this equation (11) by α, C
l"'= Xaα+ XlCl"+ X2(lr'+
X*α””・(12) is obtained. α is the modulus polynomial 2P(X
) = the root of O, so on G F (2'), the expression (2^
) holds, and by substituting this equation (2^) into equation (12), equation (12> can be transformed as follows.

CI” = X6 α+ X Iα2+x2α30X3
(1+g+α+g2(r”+g3(r3)=X3+(X
ll+X3g+)αten(X++X5g2)α2+ (X
2+ X3 g3)α. ...(13) From equation (13), the vector representation of element α1゛1 is (X,).

Xo+ Xsg++ x, +X3g2* X2+X3g
5)', and this vector representation is (Too T++
Tit Tit)'. In this case, in FIG. 3, the adder (8).

The output data of (9) and (10) are the coefficients Xo+Xs, respectively.
g(, X++ 'X 3 g 2. X a + X
Since s g 3 , the matrix T(3
) elements T, . ~T'+s is obtained.

Similarly, the vector representation of element αl″2 (matrix elements T2° to T23) is obtained from the vector representation of element α1゛1,
From the vector representation of element α′1, the vector representation of element α11 (
Matrix elements T30 to T3j) are determined. Note that, for example, X'+X+1 is used as the modulus P(X), but
In this case g+=1. Since gz=g3=0, the example in FIG. 3 is simplified to the example in FIG. 4.

Returning to FIG. 2, (2) indicates a multiplication unit, and each element TQO-'-733 of the matrix T(x) generated by the representation conversion circuit (1) is supplied to this multiplication unit (2). In this multiplication unit (2), (23> to (30),
(35) to (42) are AND gates, (31) to
(34), (43) to (50) respectively indicate εXOR gates, and elements T0° to TO3 of the matrix T (X) are supplied to one input terminal of the AND gates (23> to (26), respectively), and the other A coefficient (y-') of the vector representation of the input y''' of the divisor y is commonly supplied to the input terminal of , and (y-'
)o Too ~(3'-')o Too is generated.

Similarly, let the remaining coefficients of the vector representation of the introduction y −1 be (
y')+~(y-')t, and gate (2
7) to (30) gives (y-')+'r+. ~(y-'
)T13, and gate (35) ~ (38
) by (y-"L T211~(3'-'LT 2
s is generated, and by AND gates (39) to (42) (
y-')a'rs. ~<'/-'>5Tss is generated.

Also, EXOR game) (31), (43), (4
7) gives AND gates (23), (27), (3
5), add the output data of (39) with mod 2 to generate the coefficient Zo, and EXOR gate (32).

(44), (48) by Antogame) (24
), (28), (36).

Add the output data of (40) with mod 2 and add the coefficient 2
1, and the Snake XOR gate (33), (45)
, (49) l,: YoF) 7 Ndogate (2
5), (29), (37), and (41) are added with mod2 to produce a coefficient of 22, and EX
OR gate (34).

(46), (50) and gate (26)
, (30), (38).

The output data of <42> is added by ffIad 2 and the coefficient 2. generate. The vector representation of the quotient 2 of the dividend X and the divisor y is (Zo Z, z2 z3)'.

To explain the process of calculating the product of the matrix T (X) and the vector y-' (vector representation of the input y-1) by the multiplication unit (2) in FIG.
Vector y-1, vector 2 (vector representation of quotient 2)
There is the following relationship between each coefficient or element.

...(14) From this equation (14), each element zt of vector 2 (i =
.

~3) can be expressed as. According to equation (15), for example, the coefficient 20 is: Zo = Too(y-')o + T+a(y-')
l +T2o(y-')20T3゜(y-')s (16) However, zo obtained by the multiplication unit (2) in Fig. 2 satisfies the equation (16). Similarly, the coefficient 2. ~2. also satisfies equation (15).

As mentioned above, according to the division circuit of this example, the finite field G F (
2') The vector representation of the quotient 2 of the dividend X and the divisor y above is obtained by multiplying the matrix representation T (X) of the dividend Therefore, since only one ROM (inverse element generation ROM (3)) is required as a conversion table, the circuit size can be reduced and the calculation speed can be reduced compared to the conventional example using three ROMs as conversion tables. There is an advantage of being able to speed up the process.

In the above embodiment, the expression of the dividend X is converted from vector expression to matrix expression, but the inverse element generation ROM (3)
By disposing the representation conversion circuit (1) between It may also be done by multiplying the expression. Furthermore, the above embodiment can easily be applied to a general finite field G F (2m)(m
is an integer greater than or equal to 1).

Next, another embodiment of the present invention will be described with reference to FIG. In this example, the dividend is a common element X expressed as a 4-bit vector on the finite field GF(2'), and three elements a are each expressed as a 4-bit vector.

Three quotients b(=x/a), d(=X
/C), f (=X/e) in vector representation.

FIG. 5 shows the division circuit of this example, and in this 5rXJ, (2A) to (2C) are multiplication units each having the same configuration as the multiplication unit in the example of FIG. 1, and (3^) to (3C) are respectively This ROM for inverse element generation has the same configuration as the inverse element generation ROM (3) in the example in Figure 1, and the expression conversion circuit (
1) into a matrix representation T (X), and each element of this matrix representation T (X) is multiplied by a multiplication unit (2^〉~(2C
> to one input port of each. Also, the divisor a
.

Generation ROMs (3A), (3B) for c and e respectively,
Arrival of vector representation via (3C); a −1, C
-1, 6-1, and multiply these values by the respective multiplication units)
(2A), (2B).

(Supplies to the other human power port of 2C>. Multiplying unit)
Since (2A), (2B), and (2C) each operate in the same way as the multiplication unit (2) in the example in Figure 1, the quotients from these multiplication units (2^), (2B), and (2C), respectively, are , d, f are output as 4-bit vector representation coefficients.

According to the example in Figure 5, the expression conversion circuit [1] is commonly used for three multiplication units) (2A) to (2C), so when simply arranging three dividers in parallel. There is an advantage that the overall circuit scale can be made smaller than that of the conventional method.

Incidentally, by modifying the example in Fig. 5, the inverse element generation ROM (3A>~
(3C) and the multiplication units (2^> to (2C>) may each have an expression conversion circuit for converting vector expression to matrix expression. Also, in the example in FIG. 5, the dividend X is common. However, the present invention is also applicable to cases where the divisor is common in multiple division operations.

In this case, when the divisor is common, the divisor is used as the RO for inverse element generation.
The signal is supplied to one input port of each of the plurality of multiplication units via M and the representation conversion circuit.

As described above, the present invention is not limited to the above-described embodiments, and it goes without saying that various configurations may be adopted without departing from the gist of the present invention.

〔Effect of the invention〕

According to the present invention, there is an advantage that the circuit scale can be further reduced and the calculation speed can be increased. Furthermore, if the multiplication circuit is configured to convert the second element side into a matrix representation, the conversion of the second element representation and the generation of the first element are performed in parallel. Therefore, the calculation speed can be further increased.

Furthermore, if the representation conversion circuit is shared in the division circuit that calculates the quotient of a group of elements and one common element,
There is a practical advantage that the circuit scale can be further reduced.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing one embodiment of the present invention, and FIG. 2 is a block diagram showing an embodiment of the present invention. A circuit diagram showing the specific circuit configuration of example A, FIG. 3 is a circuit diagram showing the main part of the expression conversion circuit (1) in FIG. 2, and FIG. 4 is a circuit diagram showing a special case of example A. 5 are block diagrams showing other embodiments of the present invention. (1) is an expression conversion circuit, (2) and (2) to (2C) are multiplication units, respectively, and (3) and (3A) to (3C) are ROMs for reception generation, respectively. Figure 3

Claims (1)

[Claims] 1. An inverse element generation circuit that generates an inverse element of a first element expressed as a vector with m bits on a finite field GF(2^m) in a vector representation; Inverse element and finite field GF (2^m)
It has a multiplication circuit that converts one element into matrix representation and multiplies the second element expressed as a vector using m bits, and calculates the quotient of the second element divided by the first element. Finite field GF (
2^m) A finite field division circuit obtained by the m-bit vector representation above. 2. A finite field division circuit according to claim 1, wherein said multiplication circuit converts said second element into matrix representation. 3. In a division circuit that calculates the respective quotients of a group of elements expressed as m-bit vectors on the finite field GF(2^m) and one common element, the inverse element of each of the above group of elements or the above a plurality or one inverse element generation circuit that generates an inverse element of a common element in vector representation;
A representation conversion circuit that converts the common element into a matrix representation directly or via the inverse element generation circuit, and a vector representation of the group of elements or the inverse of each of the group of elements and output from the representation conversion circuit. A finite field division circuit provided with a plurality of multiplication circuits for multiplying matrix representations.