JPS6229821B2 - - Google Patents
Info
- Publication number
- JPS6229821B2 JPS6229821B2 JP57114282A JP11428282A JPS6229821B2 JP S6229821 B2 JPS6229821 B2 JP S6229821B2 JP 57114282 A JP57114282 A JP 57114282A JP 11428282 A JP11428282 A JP 11428282A JP S6229821 B2 JPS6229821 B2 JP S6229821B2
- Authority
- JP
- Japan
- Prior art keywords
- full adder
- circuit
- bit full
- bit
- carry
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
- G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
- G06F7/724—Finite field arithmetic
Landscapes
- Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- Computational Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computing Systems (AREA)
- Mathematical Physics (AREA)
- General Engineering & Computer Science (AREA)
- Detection And Correction Of Errors (AREA)
- Error Detection And Correction (AREA)
Description
本発明は、ガロア体GF（２n）におけるmod
（２n−１）演算回路、詳しくは、ガロア体GF
（２n）（但しｎは２以上の正の整数）で定義され
る元どおしの乗算を行なう場合、元の表現をαの
冪乗で表現し、その指数に対し、mod（２n−
１）加算を行なうガロア体GF（２n）における
mod（２n−１）演算回路に関する。
誤り訂正符号等の符号論理によく表われるガロ
ア体GF（２n）において、ガロア体GF（２n）を
構成する０を含す２n個の元の表現方法として、
ベクトル表現或いはαの冪乗で定義される巡回群
による表現がある。即ち、GF（２n）はｎ次の既
約多項式ｆ（Ｘ）を法とする多項式環であり、
GF（２n）の２n個の元は、α０（＝１），α，α
２，α３，……，αによる線形結合表現あるいは
ベクトル表現で書き現わすことができる。また、
GF（２n）を元の０元を除く残りの元を１を単位
元として、これに次々にαを乗ずることによつて
生ずる元α，α２，α３，……，αZn-Zは“０”
を除くすべての元を一巡して２Zn-１で再び単位
元に戻る巡回群を用いて表現すると、０，１，
α，α２，α３，……αZn-Zの２n個の元とな
る。
ところで、誤り訂正符号を復号し、誤り訂正を
実行する場合、GF2nの元どおしの積の演算がし
ばしば必要となる。その場合、GF（２n）の任意
の元をＡ，Ｂとすると、その積Ａ，Ｂはベクトル
表現どおしの積を実行するよりも前記αの冪乗の
表現の方がはるかに実行し易い。即ち、元Ａ，Ｂ
をそれぞれＡ＝αi，Ｂ＝αj（但し、ｉ，ｊは０
を含む２n−１以下の正の整数）とすると、元
Ａ，Ｂの積は次のようになる。
Ａ・Ｂ＝αi×αj
＝αj+j
ここにおいて、ｉ＋ｊは０を含む２n−１以下
の正の整数でmod（２n−１）加算となる。ま
た、商についても同様にＡ／Ｂを演算する場合は
次のようになる。
Ａ／Ｂ＝αi・α-j
＝αi・α(2n-１)-j
ここで、（２n−１）−ｊは０≦（２n−１）−ｊ≦
２n−１の正の整数であるから、積の場合と同様
にmod（２n−１）加算となる。
次にmod（２n−１）加算器について説明す
る。今説明を簡単にするために、ｎ＝２としGF
(2)を例にとつて説明する。
GF（22）のすべての元を前記αの冪乗で表現す
ると、０，１（１＝α０），α１，α２の４個で
表現される。そして、α３はα３＝α０＝１とな
つて単位元に戻る。従つて、α２×α２の乗算を
行なう場合、その演算結果をα４とせずにαとす
るようなmod3加算器を必要とする。
次に、上記mod3加算器の回路例を第１図に示
す。この回路例においては幕数を２進数で表現す
ることにし、A1，A2をそれぞれ任意の元Ａの２
進数で記述された幕数のエルエスビー（LSB），
エムエスビー（MSB）として表わし、B1，B2を
それぞれ任意の元Ｂの２進数で記述された幕数の
エルエスビー（LSB），エムエスビー（MSB）と
してあらわす。そして、この２ビツトの幕数
A1，A2とB1，B2とを第１図に示すmod3加算器の
第１の２ビツト全加算回路１０１に入力すると、
この第１の２ビツト全加算回路１０１は次の真理
値表に示すように２ビツトの全加算を行ない、そ
の和Σ１，Σ２を第２の２ビツト全加算回路１０
３に入力すると共に桁上げがあれば、この第１の
２ビツト全加算回路１０１の桁上げ出力よりライ
ン１０２を介して桁上げ信号C1を第２の２ビツ
ト全加算回路１０３の桁上げ入力に供給される。
The present invention is based on the mod in Galois field GF(2 n ).
(2 n −1) Arithmetic circuit, in detail, Galois field GF
(2 n ) (where n is a positive integer greater than or equal to 2), when performing multiplication between elements defined as −
1) In the Galois field GF(2 n ) that performs addition
This relates to a mod(2 n -1) arithmetic circuit. In the Galois field GF(2 n ), which often appears in code logic such as error correction codes, as a representation method for the 2 n elements including 0 that make up the Galois field GF(2 n ),
There is a vector representation or a representation using a cyclic group defined as a power of α. That is, GF(2 n ) is a polynomial ring modulo an n-th degree irreducible polynomial f(X),
The 2 n elements of GF (2 n ) are α 0 (=1), α, α
2 , α 3 , . . . , α can be expressed as a linear combination expression or a vector expression. Also,
Elements α, α 2 , α 3 , ..., α Zn-Z are generated by multiplying GF (2 n ) by α one after another, with the remaining elements excluding the 0 element set to 1 as the identity element. is “0”
If we express it using a cyclic group that goes through all the elements except
α, α 2 , α 3 , ... α There are 2 n elements of Zn-Z . By the way, when decoding an error correction code and performing error correction, it is often necessary to calculate the product of the elements of GF2 n . In that case, if the arbitrary elements of GF(2 n ) are A and B, the product A and B can be expressed much more easily by expressing the power of α than by multiplying the vector expressions. Easy to do. That is, elements A, B
A=α i and B=α j (however, i, j are 0
(a positive integer less than or equal to 2 n -1), the product of elements A and B is as follows. A.B=α i ×α j =α j+j where i+j is a positive integer equal to or less than 2 n −1 including 0, resulting in mod(2 n −1) addition. Similarly, when calculating A/B for the quotient, the following procedure is performed. A/B=α i・α -j = α i・α (2n- 1 )-j where (2 n -1)-j is 0≦(2 n -1)-j≦
Since it is a positive integer of 2 n -1, it is mod (2 n -1) addition as in the case of product. Next, the mod(2 n -1) adder will be explained. To simplify the explanation, let n=2 and GF
This will be explained using (2) as an example. When all the elements of GF(2 2 ) are expressed as powers of α, they are expressed as four elements: 0, 1 (1=α 0 ), α 1 , and α 2 . Then, α 3 becomes α 3 =α 0 =1 and returns to the identity element. Therefore, when performing a multiplication of α 2 ×α 2 , a mod3 adder is required that outputs the result of the operation as α instead of α 4 . Next, a circuit example of the mod3 adder described above is shown in FIG. In this circuit example, the act number is expressed in binary numbers, and A 1 and A 2 are respectively expressed as 2 of any element A.
Act number LSB (LSB) written in base numbers,
B 1 and B 2 are expressed as MSB (LSB) and MSB (MSB) of the number of acts written in binary numbers of arbitrary element B, respectively. And this 2-bit act number
When A 1 , A 2 and B 1 , B 2 are input to the first 2-bit full adder circuit 101 of the mod3 adder shown in FIG.
This first 2-bit full addition circuit 101 performs 2-bit full addition as shown in the following truth table, and the sums Σ 1 and Σ 2 are added to the second 2-bit full addition circuit 10.
3 and if there is a carry, the carry signal C1 is sent from the carry output of the first 2-bit full adder circuit 101 to the carry input of the second 2-bit full adder circuit 103 via the line 102. is supplied to
【表】【table】
【表】
このようにして演算されたA1，A2とB1，B2と
の和出力Σ１，Σ２（Σ１がエルエスビー
（LSB）でΣ２がエムエスビー（MSB））および
桁上げ出力C2は上記第２の２ビツト全加算回路
１０３に入力されるも、この場合上記和出力Σ
１，Σ２に加算される他方の２ビツトは“０”
（ゼロ）に設定しておく。したがつて、この場合
第２の２ビツト全加算回路１０３は次の真理値表
に示す加算を行ない、その和Σ1′，Σ2′を出力す
る。[Table] The sum outputs of A 1 , A 2 and B 1 , B 2 calculated in this way Σ 1 , Σ 2 (Σ 1 is LSB (LSB) and Σ 2 is MSB (MSB)) and The carry output C2 is input to the second 2-bit full adder circuit 103, but in this case the sum output Σ
1 , the other 2 bits added to Σ 2 are “0”
Set it to (zero). Therefore, in this case, the second 2-bit full adder circuit 103 performs the addition shown in the following truth table and outputs the sums Σ 1 ' and Σ 2 '.
【表】【table】
【表】
この表より
Σ２′＝Σ２○＋０○＋C１′
このようにして得られたmod3加算器は次表の
如くなる。[Table] From this table
Σ 2 ′=Σ 2 ○+0○+C 1 ′
The mod3 adder obtained in this way is shown in the following table.
【表】
上表において、かつこ内の数字は２進数表示を
意味する。
上記第１図に示した演算回路は、mod3＝mod
（22−１）加算の回路構成について説明したもの
であるが、これを拡張してmod（２n−１）加算
器（但し、ｎ≧２以上の正の整数）を構成するこ
とができる。
第２図は、このmod（２n−１）加算回路を示
すものであり、このmod（２n−１）加算回路は
第１図に示す回路をｎビツトまで拡張したもの
で、２つのｎビツトの２進数A1，A2，A3，……
ＡoとB1，B2，B3，……Ｂoの各対応する１ビツト
同志を加算するｎ個の第１の１ビツト全加算回路
１〜ｎと、これらの第１の１ビツト全加算回路１
〜ｎの和出力Σ１〜Σoのそれぞれと０（ゼロ）
入力との１ビツト加算を行うｎ個の第２の１ビツ
ト全加算回路１′〜n′と、上記第１の１ビツト全
加算回路２〜ｎの桁上げ出力C2〜Ｃoの１つを選
択して、上記第２の１ビツト全加算回路１′の桁
上げ入力に供給する桁上げ出力制御論理回路SW1
とより構成され、上記第１の１ビツト全加算回路
１〜ｎの各々の桁上げ出力C1〜Ｃo-１は次段の全
加算回路２〜ｎの桁上げ入力に供給され、第２の
１ビツト全加算回路１′〜ｎ−１′の各々の桁上げ
出力C1′〜Ｃo-１′は次段の全加算回路２〜n′の桁
上げ入力に供給されている。上記桁上げ出力制御
論理回路SW1は、この第２図に示すmod（２n−
１）加算回路で何ビツトまでの加算を行うかを決
定するものであつて、上記第１の１ビツト全加算
回路２〜ｎの桁上げ出力C2〜Ｃoに接続された接
点S1〜Ｓoと、この各接点S2〜Ｓo上を選択的に切
替わるワイパーＷとからなるロータリースイツチ
で構成され、このワイパーＷは上記第２の１ビツ
ト全加算回路１′の桁上げ入力に接続されてい
る。そして、このロータリースイツチのワイパー
Ｗを接点S2に接続した時には第１図に示した回路
と同じ２ビツトのmod（22−１）加算回路とな
り、接点S3に接続した時には３ビツトのmod（23
−１）加算回路になり、同様にして接点Ｓoに接
続した時にはｎビツトのmod（２n−１）加算回
路を構成するものである。この第２図に示す加算
回路は前述した第１図に示した加算回路と原理は
同じであり、ビツト数が増えただけであつて、そ
の動作は同じである。
以上説明したように、本発明によれば、ｎ個の
第１の１ビツト全加算回路１〜ｎの各和出力Σ１
〜Σoをそれぞれｎ個の第２の１ビツト全加算回
路の一方の入力に供給すると共に、この他方の入
力に０（ゼロ）入力を供給して、それぞれの１ビ
ツト加算を行い、かつ上記第１の１ビツト全加算
回路の桁上げ出力の１つを選択して、上記第２の
１ビツト全加算回路の最下位の全加算回路の桁上
げ入力に供給するという簡単な回路によつてガロ
ア体GF（２n）におけるmod（２n−１）演算回
路が構成され、更に上記ｎの数を拡大することに
よつて無限に拡張でき、GF（２n）の体のすべて
を演算することができる。[Table] In the above table, the numbers in brackets mean binary representation. The arithmetic circuit shown in Figure 1 above is mod3=mod
(2 2 -1) This describes the addition circuit configuration, but this can be extended to configure a mod (2 n -1) adder (where n is a positive integer greater than or equal to 2). . Figure 2 shows this mod (2 n -1) adder circuit. This mod (2 n -1) adder circuit is an extension of the circuit shown in Figure 1 to n bits. Bit binary numbers A 1 , A 2 , A 3 ,...
n first 1-bit full adder circuits 1 to n that add each corresponding 1 bit of A o and B 1 , B 2 , B 3 , . . . B o ; Addition circuit 1
The sum output of ~n Σ 1 Each of ~Σ o and 0 (zero)
n second 1-bit full adder circuits 1' to n' that perform 1-bit addition with the input, and one of the carry outputs C 2 to Co of the first 1-bit full adder circuits 2 to n. A carry output control logic circuit SW 1 selects and supplies it to the carry input of the second 1-bit full adder circuit 1 '.
The carry outputs C 1 to C o- 1 of each of the first 1-bit full adder circuits 1 to n are supplied to the carry inputs of the next stage full adder circuits 2 to n, and The carry outputs C 1 ' to C o -1' of the 1-bit full adder circuits 1' to n-1' are supplied to the carry inputs of the next-stage full adder circuits 2 to n'. The carry output control logic circuit SW 1 is mod (2 n −
1) The contacts S 1 - which are used to determine how many bits to add in the adder circuit and are connected to the carry outputs C 2 -C o of the first 1-bit full adder circuits 2 - n S o and a wiper W that selectively switches over the contacts S 2 to S o , and this wiper W is connected to the carry input of the second 1-bit full adder circuit 1'. It is connected. When the wiper W of this rotary switch is connected to the contact S2 , it becomes a 2-bit mod (2 2 -1) addition circuit, which is the same as the circuit shown in Figure 1, and when it is connected to the contact S3 , it becomes a 3-bit mod. (twenty three
-1) It becomes an adder circuit, and when connected to contact So in the same way, it constitutes an n-bit mod (2 n -1) adder circuit. The adder circuit shown in FIG. 2 has the same principle as the adder circuit shown in FIG. 1 described above, except that the number of bits is increased, and its operation is the same. As explained above, according to the present invention, each sum output Σ 1 of n first 1-bit full adder circuits 1 to n
~ Σo is supplied to one input of each of the n second 1-bit full adder circuits, and a 0 (zero) input is supplied to the other input to perform each 1-bit addition, and the above A simple circuit selects one of the carry outputs of the first 1-bit full adder and supplies it to the carry input of the lowest full adder of the second 1-bit full adder. A mod (2 n -1) calculation circuit in the Galois field GF (2 n ) is constructed, and can be expanded infinitely by further increasing the number of n mentioned above, and can calculate all of the field of GF (2 n ). be able to.
第１図は、本発明の一実施例を示すガロア体
GF（２n）におけるmod（２n−１）演算回路の
回路図、第２図は、本発明の他の実施例を示す
mod（２n−１）演算回路の回路図である。
１〜ｎ……第１の１ビツト全加算回路、１′〜
n′……第２の１ビツト全加算回路、SW1……桁上
げ出力制御論理回路。
FIG. 1 shows a Galois field showing an embodiment of the present invention.
FIG. 2, a circuit diagram of a mod(2 n −1) arithmetic circuit in GF(2 n ), shows another embodiment of the present invention.
FIG. 2 is a circuit diagram of a mod(2 n -1) arithmetic circuit. 1 to n...first 1-bit full adder circuit, 1' to
n'...Second 1-bit full adder circuit, SW1 ...Carry output control logic circuit.
Claims (1)
の整数）で定義される元どおしの乗算を行なうた
めに、元の表現をαの冪乗で表現し、その指数に
対しmod（２n−１）加算を行なうガロア体GF
（２n）におけるmod（２n−１）演算回路におい
て、 ｎ個の第１の１ビツト全加算回路１〜ｎであつ
て、この第１の１ビツト全加算回路１〜ｎ−１の
各桁上げ出力を次段の上記第１の１ビツト全加算
回路２〜ｎの桁上げ入力に供給するように並列に
接続されたｎ個の上記第１の１ビツト全加算回路
と、 このｎ個の第１の１ビツト全加算回路１〜ｎの
和出力Σ１〜Σoのそれぞれと０（ゼロ）入力と
の１ビツト加算を行うｎ個の第２の全加算回路
１′〜n′であつて、この第２の全加算回路１′〜ｎ
−１′の各桁上げ出力を次段の上記第２の１ビツ
ト全加算回路２′〜n′の桁上げ入力に供給するよ
うに並列に接続されたｎ個の上記第２の１ビツト
全加算回路と、 上記第１の１ビツト全加算回路の最後の段の桁
上げ出力を上記第２の１ビツト全加算回路１′の
桁上げ入力に供給する桁上げ出力制御論理回路
と、 を有することを特徴とするガロア体GF（２n）
におけるmod（２n−１）演算回路。[Claims] 1. In order to perform multiplication between elements defined by the Galois field GF(2 n ) (where n is a positive integer of 2 or more), the expression of the element is raised to a power of α. Galois field GF that represents and performs mod (2 n −1) addition to its exponents.
In the mod (2 n -1) arithmetic circuit in (2 n ), there are n first 1-bit full adder circuits 1 to n, and each of the first 1-bit full adder circuits 1 to n-1 n first 1-bit full adder circuits connected in parallel so as to supply the carry output to the carry inputs of the first 1-bit full adder circuits 2 to n in the next stage; n second full adder circuits 1' to n' which perform 1 bit addition of each of the sum outputs Σ 1 to Σ o of the first 1 bit full adder circuits 1 to n and the 0 (zero) input. This second full adder circuit 1' to n
The n second 1-bit full adders are connected in parallel so that each carry output of -1' is supplied to the carry input of the second 1-bit full adder circuits 2' to n' in the next stage. an adder circuit; and a carry output control logic circuit that supplies the carry output of the last stage of the first 1-bit full adder circuit to the carry input of the second 1-bit full adder circuit 1'. Galois field GF(2 n ) characterized by
mod(2 n -1) arithmetic circuit.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP57114282A JPS593644A (en) | 1982-06-30 | 1982-06-30 | Mod(2n-1) arithmetic circuit for galois field gf(2n) |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP57114282A JPS593644A (en) | 1982-06-30 | 1982-06-30 | Mod(2n-1) arithmetic circuit for galois field gf(2n) |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS593644A JPS593644A (en) | 1984-01-10 |
| JPS6229821B2 true JPS6229821B2 (en) | 1987-06-29 |
Family
ID=14633927
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP57114282A Granted JPS593644A (en) | 1982-06-30 | 1982-06-30 | Mod(2n-1) arithmetic circuit for galois field gf(2n) |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS593644A (en) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR20200111439A (en) * | 2019-03-19 | 2020-09-29 | 현대모비스 주식회사 | Apparatus and method for compensating stick-slip of motor driven power steering system |
| KR20210126862A (en) * | 2020-04-13 | 2021-10-21 | 현대자동차주식회사 | Control system and method for motor driven power steering system |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2581534B2 (en) * | 1984-08-27 | 1997-02-12 | 株式会社リコー | Arithmetic circuit |
-
1982
- 1982-06-30 JP JP57114282A patent/JPS593644A/en active Granted
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR20200111439A (en) * | 2019-03-19 | 2020-09-29 | 현대모비스 주식회사 | Apparatus and method for compensating stick-slip of motor driven power steering system |
| KR20210126862A (en) * | 2020-04-13 | 2021-10-21 | 현대자동차주식회사 | Control system and method for motor driven power steering system |
Also Published As
| Publication number | Publication date |
|---|---|
| JPS593644A (en) | 1984-01-10 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| KR900006666B1 (en) | Apparatus for multiplication in galois field | |
| CN102084335B (en) | Implementation of arbitrary galois field arithmetic on a programmable processor | |
| EP0620654B1 (en) | Circuit for performing the Euclidian algorithm in decoding of arithmetical codes | |
| EP0061345B1 (en) | Processing circuits for operating on digital data words which are elements of a galois field | |
| JP2000047833A (en) | System for encoding and decoder | |
| JPH09507110A (en) | Finite field inversion | |
| JPH10135848A (en) | Reed-Solomon encoding apparatus and method | |
| JP3000811B2 (en) | Cyclic coding and CRC device and processing method thereof | |
| JP2694792B2 (en) | Error position polynomial arithmetic circuit | |
| JPS6229821B2 (en) | ||
| TWI226758B (en) | Encoding method and apparatus for cross interleaved cyclic codes | |
| JPH06230991A (en) | Method and apparatus for computation of inverse number of arbitrary element in finite field | |
| JPH0220124A (en) | Method and apparatus of interleave type encoding | |
| JPS63107319A (en) | Polynomial division circuit on extended Galois field | |
| JPH0869372A (en) | Binary multiplier | |
| JPH0750595A (en) | Decoding device | |
| US6704901B1 (en) | Runtime programmable Reed-Solomon decoder | |
| JPH0326114A (en) | Multiplication remainder operator | |
| JP4042215B2 (en) | Arithmetic processing apparatus and method | |
| JPH08139612A (en) | Reed solomon error correction code decoding circuit | |
| KR970003979B1 (en) | Multiplexer | |
| JP2797570B2 (en) | Euclidean circuit | |
| JPH0834439B2 (en) | Galois field arithmetic unit | |
| JPH0778748B2 (en) | Galois field arithmetic unit | |
| JP3106767B2 (en) | Multiplication method and multiplication circuit |