JPH0137049B2

JPH0137049B2 -

Info

Publication number: JPH0137049B2
Application number: JP59097975A
Authority: JP
Inventors: Junichi Kubo
Original assignee: Matsushita Electric Industrial Co Ltd
Current assignee: Panasonic Holdings Corp
Priority date: 1984-05-16
Filing date: 1984-05-16
Publication date: 1989-08-03
Also published as: JPS60241331A

Description

【発明の詳細な説明】産業上の利用分野本発明はデジタル通信やデジタル記録等の採用
される有限体GF（2ⁿ）上の誤り訂正符号の符号処
理に必要な乗算を行うのに用いることができる
MOD（2ⁿ−１）（ｎは２以上の整数）の加算回路
に関するものである。[Detailed Description of the Invention] Industrial Application Field The present invention can be used to perform multiplication necessary for code processing of an error correction code on a finite field GF(2 ⁿ ) used in digital communication, digital recording, etc. can do
The present invention relates to an adder circuit of MOD(2 ⁿ -1) (n is an integer of 2 or more).

従来例の構成とその問題点近年、デジタル通信やデジタル記録等で有限体
GF（2ⁿ）上の誤り訂正符号が広く用いられてお
り、その誤り訂正符号の訂正や検出などの符号処
理を行うにはGF（2ⁿ）上の乗算が必要である。Configuration of conventional examples and their problems In recent years, finite bodies have been used in digital communication, digital recording, etc.
Error correction codes on GF(2 ⁿ ) are widely used, and multiplication on GF(2 ⁿ ) is required to perform code processing such as correction and detection of the error correction codes.

GF（2ⁿ）上の乗算の１つの手法として、乗数、
被乗数をαⁱ、α^j（α：GF（2ⁿ）上の生成元、ｉ、ｊ
は０以上2ⁿ−１未満の整数）としたときに、まず
ｉ、ｊを求めて、ｋ≡ｉ＋ｊ（MOD（2ⁿ−１））に
より、乗算結果αⁱ×α^j＝α^kを求める方法がある。
その際、αⁱ、α^jからｉ、ｊを求めるには、αⁱのベ
クタ表現をアドレス入力とし、ｉをデータ出力と
するデーブルROMを用いれがよいし、ｋからα^k
を求めるには、ｋをアドレス入力とし、α^kのベク
タ表現をデータ出力とするようなテーブルROM
を用いればよい。従つて残る問題は、MOD（2ⁿ−
１）の加算回路をいかに構成するかということで
ある。 One method of multiplication on GF(2 ⁿ ) is to use the multiplier,
Let the multiplicands be α ⁱ , α ^j (α: generator on GF(2 ⁿ ), i, j
is an integer greater than or equal to 0 and less than 2 ⁿ -1), first find i and j, and then find the multiplication result α ⁱ ×α ^j = α ^k by k≡i+j (MOD (2 ⁿ -1)). There is a way.
In this case, to obtain i and j from α ⁱ and α ^j , it is best to use a table ROM that takes the vector representation of α ⁱ as the address input and i as the data output, ^and
To find , create a table ROM that takes k as address input and the vector representation of α ^k as data output.
You can use Therefore, the remaining problem is MOD(2 ⁿ −
The problem is how to configure the adder circuit in 1).

以下図面を参照しながら従来のMOD（2ⁿ−１）
の加算回路について説明する。第１図は従来の
MOD（2ⁿ−１）の加算回路のブロツク図であり、
１００はキヤリ入力端子のないｎビツトのバイナ
リ加算器（Ａとする）であり、２００はキヤリ入
力端子のあるｎビツトのバイナリ加算器（Ｂとす
る）である。Ａはキヤリ出力ＣはＢのキヤリ入力
に入力され、加算数Ｘ＝（x₀、x₁、…、x_o-1）（以
下、Ｖ＝（V₀、V₁、…、V_o-1）と書くと、数Ｖを
バイナリ表現したときの各けたを下けたから書い
たときに、V₀、V₁、…、V_o-1となるものとす
る。）と被加算数Ｙ＝（y₀、y₁、…、y_o-1）とがＡ
に入力され、Ａは加算出力がＢに加算数として入
力され、Ｂは被加算数としては（０、０、…、
０）（すなわちｎビツト分の０）が入力されてい
るように構成している。 Conventional MOD (2 ⁿ −1) with reference to the drawing below.
The adder circuit will be explained. Figure 1 shows the conventional
It is a block diagram of an adder circuit of MOD(2 ⁿ −1),
100 is an n-bit binary adder (referred to as A) without a carry input terminal, and 200 is an n-bit binary adder (referred to as B) with a carry input terminal. _The carry output of A is input to the carry input _of B, and _the _addition number X = (x ₀ _, ), then when the number V is expressed in binary and each digit is written down, it becomes V ₀ , V ₁ , ..., V _o-1 .) and the addend Y = ( y ₀ , y ₁ , ..., y _o-1 ) is A
The output of A is input as the addition number to B, and B is the augend (0, 0, ...,
0) (that is, n bits of 0) are input.

以上のように構成されたMOD（2ⁿ−１）の加算
回路についてその動作を以下に説明する。前記の
MOD（2ⁿ−１）の加算回路の出力Ｚ＝（z₀、z₁、
…、z_o-1）はその構成から考えて、Ｚ≡Ｘ＋Ｙ＋
Ｃ（MOD2ⁿ）（一般にＵ≡Ｖ＋Ｗ（MOD（Ｍ））と
書くとＶとＷとをMOD（Ｍ）で加算した結果が
Ｕになるということを意味する。）となる。 The operation of the MOD (2 ⁿ -1) adder circuit configured as described above will be described below. the above
The output of the adder circuit of MOD (2 ⁿ −1) Z = (z ₀ , z ₁ ,
..., z _o-1 ) is considered from its composition, Z≡X+Y+
C(MOD2 ⁿ ) (Generally written as U≡V+W(MOD(M)), it means that the result of adding V and W by MOD(M) is U.).

Ｓ≡Ｘ＋Ｙ（MOD（2ⁿ−１））とすると2ⁿ−１＞
Ｘ＋Ｙ≧０のときにはＣ＝０となるからＺ＝Ｓ＝
Ｘ＋Ｙとなり、Ｘ＋Ｙ≧2ⁿのときにはＣ＝１とな
るからＺ＝Ｓ＝（Ｘ＋Ｙ＋１）−2ⁿ＝Ｘ＋Ｙ−（2_o
−１）となる。従つてＸ＋Ｙ＝2ⁿ−１以外のとき
にはこの加算回路の出力Ｚが加算数、被加算数
Ｘ、ＹのMOD（2ⁿ−１）の加算結果となる。 If S≡X+Y(MOD(2 ⁿ −1)), then 2 ⁿ −1>
When X+Y≧0, C=0, so Z=S=
When X+Y≧2 ⁿ , C=1, so Z=S=(X+Y+1)−2 ⁿ =X+Y−(2 _o
-1). Therefore, when X+Y=2 ⁿ -1, the output Z of this adder circuit becomes the addition result of MOD(2 ⁿ -1) of the addends X and Y.

しかしながら、上記のような構成においては、
キヤリの伝搬が２つの加算器にまたがつているの
で演算速度が遅いという問題点を有していた。 However, in the above configuration,
Since the signal propagation spans two adders, there is a problem in that the calculation speed is slow.

発明の目的本発明の目的は、高速なMOD（2ⁿ−１）の加算
回路を提供することである。OBJECT OF THE INVENTION An object of the present invention is to provide a high-speed MOD(2 ⁿ -1) adder circuit.

発明の構成本発明のMOD（2ⁿ−１）の加算回路は、キヤリ
入力端子を有しないかまたはキヤリ入力が“０”
あるn_i（n_i：正の整数、ｉ＝０、１、２、…、ｋ−
１）ビツトの加算器AA_iと、キヤリ入力が“１”
であるn_iビツトの加算器AB_iと、セレクタS_iとに
より構成される単位回路をE_iとしたとき、E₀、
E₁、E₂、…、E_k-1により構成され、n₀＋n₁＋n₂＋
…n_k-1＝ｎ（ｎ：２以上の整数）であり、加算器
AA_iのキヤリ出力をA_i、加算器AB_iのキヤリ出力
をB_iとしたとき、プール代数上の演算 C_i＝A_i-1＋_k-2 〓^m=1 A_i-n-1 ・_n 〓^l=1 B_i-l＋_k-1 〓^l=0 B_l （ただし、Ｊを任意の整数としたとき、B_j＋ｋ
＝B_j、A_j＋ｋ＝A_jとする）が“０”のときにはS_iは加算器AA_iの演算結果を
出力し、C_iが“１”のときにはS_iは加算器AB_iの
演算結果を出力するように構成したものであり、
これにより高速にMOD（2ⁿ−１）の加算ができる
ものである。Structure of the Invention The MOD (2 ⁿ −1) adder circuit of the present invention does not have a carry input terminal or the carry input is “0”.
Some n _i (n _i : positive integer, i=0, 1, 2,..., k-
1) Bit adder AA _i and carry input are “1”
When a unit circuit consisting of an n _i- bit adder AB _i and a selector S _i is E _i , E ₀ ,
Consisting of E ₁ , E ₂ , ..., E _k-1 , n ₀ + n ₁ + n ₂ +
...n _k-1 = n (n: an integer greater than or equal to 2), and the adder
When the carry output of AA _i is A _i and the carry output of adder AB _i is B _i , the operation on the pool algebra is C _i = A _i-1 + _k-2 〓 ^m=1 A _in-1・_n 〓 ^l=1 B _il + _k-1 〓 ^l=0 B _l (However, when J is an arbitrary integer, B _j +k
= B _j , A _j +k = A _j ) is “0”, S _i outputs the operation result of adder AA _i , and when C _i is “1”, S _i outputs the operation result of adder AB _i It is configured to output the results,
This makes it possible to add MOD(2 ⁿ -1) at high speed.

実施例の説明以下本発明の一実施例について図面を参照しな
がら説明する。DESCRIPTION OF EMBODIMENTS An embodiment of the present invention will be described below with reference to the drawings.

第２図は本発明の一実施例におけるMOD（2ⁿ−
１）の加算回路のｎ＝８のときのブロツク図を示
すものである。第２図において、１，２，３，４
はキヤリ入力として“１”が入力されている２ビ
ツト加算器（それぞれ、AB₀、AB₁、AB₂、AB₃
とする）であり、５，６，７，８はキヤリ入力端
子のない２ビツト加算器（それぞれAA₀、AA₁、
AA₂、AA₃とする）であり、９，１０，１１，
１２はセレクタ（それぞれS₀、S₁、S₂、S₃とす
る）である。セレクタS₀は C₀＝A₃＋A₂・B₃＋A₁・B₂・B₃ ＋B₀・B₁・B₂・B₃ （ブール代数上の演算）が“１”のときにはAB₀の加算結果を選択して出
力し、C₀が“１”のときにはAA₀の加算結果を
選択して出力し、セレクタS₁は、 C₁＝A₀＋A₃・B₀＋A₂・B₃・B₀ ＋B₀・B₁・B₂・B₃ （ブール代数上の演算）が“１”のときにはAB₁の加算結果を選択して出
力し、C₁が“０”のときにはAA₁の加算結果を
選択して出力し、セレクタS₂は、 C₂＝A₁＋A₀・B₁＋A₃・B₀・B₁ ＋B₀・B₁・B₂・B₃ （ブール代数上の演算）が“１”のときにはAB₂の加算結果を選択して出
力し、C₂が“０”のときにはAA₂の加算結果を
選択して出力し、セレクタS₃は、 C₃＝A₂＋A₁・B₂＋A₀・B₁・B₂ ＋B₀・B₁・B₂・B₃ （ブール代数上の演算）が“１”のときにはAB₃の加算結果を選択して出
力し、C₃が“０”のときにはAA₃の加算結果を
選択して出力するように構成している。 FIG. 2 shows MOD (2 ⁿ −
1) shows a block diagram of the adder circuit when n=8. In Figure 2, 1, 2, 3, 4
are 2-bit adders (AB ₀ , AB ₁ , AB ₂ , AB ₃
5, 6, 7, and 8 are 2-bit adders without a carry input terminal (AA ₀ , AA ₁ , respectively).
AA ₂ and AA ₃ ), and 9, 10, 11,
12 is a selector (S ₀ , S ₁ , S ₂ , and S ₃ , respectively); Selector S ₀ adds AB 0 when C ₀ = A ₃ + A ₂ , B ₃ + A ₁ , B ₂ , B ₃ + B ₀ , B ₁ , B ₂ , B ₃ (operation on Boolean algebra) is “ ₁ ”. The result is selected and output, and when C ₀ is "1", the addition result of AA ₀ is selected and output, and the selector S ₁ is as follows: C ₁ = A ₀ + A ₃ · B ₀ + A ₂ · B ₃ · B When ₀ +B ₀ , B ₁ , B ₂ , B ₃ (Boolean algebraic operation) is “1”, the addition result of AB ₁ is selected and output, and when C ₁ is “0”, the addition result of AA ₁ is selected and output. _is selected _and _output _, _and _selector _S ₂ _selects _and _outputs _: When C 2 is "1", the addition result of AB ₂ is selected and output; when C ₂ is "0", the addition result of AA ₂ is selected and output; selector S ₃ is as follows: C ₃ = A ₂ + A ₁ · B ₂ +A ₀・B ₁・B ₂ +B ₀・B ₁・B ₂・B ₃ (Boolean algebraic operation) When is “1”, the addition result of AB ₃ is selected and output, and C ₃ is “0”. ”, the configuration is such that the addition result of AA ₃ is selected and output.

以上のように構成された本実施例のMOD（2ⁿ−
１）の加算器について以下その動作を説明する。
まず、加算数Ｘ＝（x₀、x₁、…、x₇）と被加算数
Ｙ＝（y₀、y₁、…、y₇）とのMOD225の加算結果
が、Ｚ＝（z₀、z₁、…、z₇）、０≦Ｚ≦255である
とし、（x₀、x₁）と（y₀、y₁）とをAA₀及びAB₀
で加算し、加算結果がそれぞれ（l₀、l₂）、（m₀、
m₁）となつたとし、（x₂、x₃）（y₂、y₃）とを
AA₁及びAB₁で加算し、加算結果がそれぞれ
（l₂、l₃）、、（m₂、m₃）となつたとし、（x₄、x₅）
と（y₄、y₅）とをAA₂及びAB₂で加算し、加算結
果がそれぞれ（l₄、l₅）、（m₄、m₅）となつたと
し、（x₆、x₇）、と（y₆、y₇）とをA₃及びAB₃で
加算し、加算結果がそれぞれ（l₆、l₇）、（m₆、
m₇）となつたとする。このとき、 C₀＝１のときには(z₀、z₁)＝(m₀、m₁)となり、 C₀＝０のときには(z₀、z₁)＝(l₀、l₁)となり、 C₁＝１のときには(z₂、z₃)＝(m₂、m₃)となり、 C₁＝０のときには(z₂、z₃)＝(l₂、l₃)となり、 C₂＝１のときには(z₄、z₅)＝(m₄、m₅)となり、 C₂＝０のときには(z₄、z₅)＝(l₄、l₅)となり、 C₃＝１のときには(z₆、z₇)＝(m₆、m₇)となり、 C₃＝０のときには(z₆、z₇)＝(l₆、l₇) となるので、上記のようにMOD（2ⁿ−１）の加算
回路を構成することにより、セレクタS₀、S₁、
S₂、S₃の出力は、（z₀、z₁、…、z₇）と等しくな
るものである。 The MOD of this embodiment configured as described above (2 ⁿ −
The operation of the adder 1) will be explained below.
First, the MOD225 addition result of the addend number X = (x ₀ , x ₁ , ..., x ₇ ) and the addend number Y = (y ₀ , y ₁ , ..., y ₇ ) is Z = (z ₀ , z ₁ , ..., z ₇ ), 0≦Z≦255, and (x ₀ , x ₁ ) and (y ₀ , y ₁ ) are AA ₀ and AB ₀
The addition results are (l ₀ , l ₂ ), (m ₀ ,
m ₁ ), and (x ₂ , x ₃ )(y ₂ , y ₃ )
Suppose that AA ₁ and AB ₁ are added, and the addition results are (l ₂ , l ₃ ), , (m ₂ , m ₃ ), respectively, and (x ₄ , x ₅ )
and (y ₄ , y ₅ ) are added using AA ₂ and AB ₂ , and the addition results are (l ₄ , l ₅ ) and (m ₄ , m ₅ ), respectively, and (x ₆ , x ₇ ) , and (y ₆ , y ₇ ) are added at A ₃ and AB ₃ , and the addition results are (l ₆ , l ₇ ), (m ₆ ,
m ₇ ). At this time, when C ₀ = 1, (z ₀ , z ₁ ) = (m ₀ , m ₁ ), and when C ₀ = 0, (z ₀ , z ₁ ) = (l ₀ , l ₁ ), and C When ₁ = 1, (z ₂ , z ₃ ) = (m ₂ , m ₃ ), and when C ₁ = 0, (z ₂ , z ₃ ) = (l ₂ , l ₃ ), and when C ₂ = 1, Sometimes (z ₄ , z ₅ ) = (m ₄ , m ₅ ), when C ₂ = 0, (z ₄ , z ₅ ) = (l ₄ , l ₅ ), and when C ₃ = 1, (z ₆ , z ₇ )=(m ₆ , m ₇ ), and when C ₃ = 0, (z ₆ , z ₇ )=(l ₆ , l ₇ ), so as above, MOD(2 ⁿ −1) By configuring an adder circuit, selectors S ₀ , S ₁ ,
The outputs of S ₂ and S ₃ are equal to (z ₀ , z ₁ , ..., z ₇ ).

以上のように本実施例によれば、使用するｋ個
の加算器間のキヤリ伝搬をなくしたことにより、
MOD（2ⁿ−１）の加算の演算時間を短縮してい
る。なお、上の実施例ではＦの加算器をキヤリ入
力端子が存在しないとしたが、Ｆはキヤリ入力端
子を持つていてもよく、ただそのときにはキヤリ
入力は“０”でなければならない。またこの
MOD（2ⁿ−１）の加算器の入力である加算数Ｘ
か、被加算数Ｙのとちらか一方の各ビツトをすべ
て反転することにより、MOD（2ⁿ−１）の減算回
路を構成することができる。 As described above, according to this embodiment, by eliminating the carry propagation between the k adders used,
The calculation time for addition of MOD(2 ⁿ -1) is shortened. In the above embodiment, the adder of F does not have a carry input terminal, but F may have a carry input terminal, but in that case, the carry input must be "0". Also this
Addition number X, which is the input of the adder of MOD (2 ⁿ −1)
By inverting all the bits of either the augend Y or the augend Y, a MOD(2 ⁿ -1) subtraction circuit can be constructed.

発明の効果以上の説明から明らかなように、本発明は使用
するｋ個のｎビツトのバイナリ加算器どうしのキ
ヤリ伝搬をなくしたことにより、演算速度が従来
のものよりもｋ倍近く向上するという優れた効果
が得られる。らに加算数か被加算数のどちらか一
方の各ビツトをすべて反転して、本発明の加算回
路に入力することにより、MOD（2ⁿ−１）の減算
回路が容易に構成できる。Effects of the Invention As is clear from the above explanation, the present invention improves the calculation speed by nearly k times compared to the conventional one by eliminating the carry propagation between the k n-bit binary adders used. Excellent effects can be obtained. Furthermore, by inverting all the bits of either the addend number or the addend number and inputting the inverted bits to the adder circuit of the present invention, a MOD(2 ⁿ -1) subtracter circuit can be easily constructed.

[Brief explanation of drawings]

第１図は従来のMOD（2ⁿ−１）の加算回路のブ
ロツク図、第２図は本発明の一実施例における
MOD（2ⁿ−１）の加算回路のブロツク図である。１，２，３，４……キヤリ入力端子のある２ビ
ツト加算器、５，６，７，８……キヤリ入力端子
のない２ビツト加算回路、９，１０，１１，１２
……セレクタ、１００……キヤリ入力端子のない
ｎビツトバイナリ加算器、２００……キヤリ入力
端子のあるｎビツトバイナリ加算器。 Figure 1 is a block diagram of a conventional MOD (2 ⁿ -1) adder circuit, and Figure 2 is an example of an embodiment of the present invention.
FIG. 2 is a block diagram of an adder circuit of MOD(2 ⁿ -1). 1, 2, 3, 4... 2-bit adder with a carry input terminal, 5, 6, 7, 8... 2-bit adder circuit without a carry input terminal, 9, 10, 11, 12
...Selector, 100...n-bit binary adder without a carry input terminal, 200...n-bit binary adder with a carry input terminal.

Claims

[Claims] 1 n _i (n _i : positive integer, i=0, 1,
2,...,k-1) When a unit circuit consisting of an adder AA _i of bits, an adder AB _i of n _i bits whose carry input is "1", and a selector S _i is E _i . , E ₀ , E ₁ , E ₂ , ..., E _k-1 ,
n ₀ +n ₁ +n ₂ +…+n _k-1 = n (n: integer greater than or equal to 2)
The input terminal of AA _i and the input terminal of AB _i are connected, and the carrier output of the adder AA _i is A _i ,
When the carry output of the adder AB _i is B _i , the operation on Boolean algebra C _i = A _i-1 + _k-2 〓 ^m=1 A _in-1・_n 〓 ^l=1 B _il + _{k- 1} 〓 ^l=0 B _l (However, when j is an arbitrary integer, B _j +k
= B _j , A _j +k = A _j ) is "0", S _i outputs the operation result of the adder AA _i , and when C _i is "1", S _i outputs the operation result of the adder AB _i addition of MOD(2 ⁿ −1), characterized in that the input terminal of the adder AA _i is used as the input terminal, and the output terminal of the selector S _i is used as the output terminal. circuit.