JPH0137050B2

JPH0137050B2 -

Info

Publication number: JPH0137050B2
Application number: JP59097977A
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: JPS60241333A

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 error correction codes on a finite field GF(2 ⁿ ) employed 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ⁿ）上の乗算の１つの手法として、乗数、
被乗数をaⁱ、a^j（ａ：GF（2ⁿ）上の生成元、ｉ、ｊ
は０以上2ⁿ−１未満の整数）としたときに、まず
ｉ、ｊを求めて、ｋ≡ｉ＋ｊ（MOD（2ⁿ−１））、
０≦ｋ＜2ⁿ−１により、乗算結果aⁱ×a^j＝a^kを求
める方法がある。その際、aⁱ、a^jからｉ、ｊを求
めるには、aⁱのベクタ表現をアドレス入力とし、
ｉをデータ出力とするテーブルROMを用いれば
よいし、ｋからa^kを求めるには、ｋをアドレス入
力とし、a^kのベクタ表現をデータ出力とするよう
なテーブルROMを用いればよい。従つて残る問
題は、MOD（2ⁿ−１）の加算回路をいかに構成す
るかということである。 One method of multiplication on GF(2 ⁿ ) is to use the multiplier,
Let the multiplicands be a ⁱ , a ^j (a: 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 k≡i+j (MOD (2 ⁿ -1)),
There is a method of obtaining the multiplication result a ⁱ ×a ^j =a ^k using 0≦k<2 ⁿ −1. At that time, to obtain i and j from a ⁱ and a ^j , use the vector representation of a ⁱ as the address input,
A table ROM that takes i as the data output may be used, and to obtain a ^k from k, a table ROM that uses k as the address input and a vector representation of a ^k as the data output may be used. Therefore, the remaining problem is how to configure the MOD(2 ⁿ -1) adder circuit.

以下図面を参照しながら従来の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),
10 is an n-bit binary adder (referred to as A) without a carry input terminal, and 20 is an n-bit binary adder (referred to as B) with a carry input terminal. The carry output C of A is input to the carry input terminal of B, and the addition number X=x ₀ , x ₁ , ...,
x _o-1 ) (hereinafter, V = (v ₀ , v ₁ , ..., v _o-1 ), when the number V is expressed in binary, the name is lowered, so when written, v ₀ , v ₁ , ...V _o-1 ) and the addend Y = (y ₀ , y ₁ , ..., y _o-1 )
is input to A, the addition output of A is input to B as an addition number, and the addend of B is (0, 0,
..., 0) (that is, n bits of 0) are input.

以上のように構成されたMOD（2ⁿ−１）の加算
回路についてその動作を以下に説明する。前記の
MOD（2ⁿ−１）の加算回路の出力Ｚ＝（z₀、z₁、
……、z_o-1）はその構成から考えて、Ｚ≡Ｘ＋Ｙ
＋Ｃ（MOD2ⁿ）（一般にＵ≡Ｖ＋Ｗ（MOD（Ｍ））
と書くとＶとＷとをMOD（Ｍ）で加算した結果
がＵになるということを意味する。）となる。Ｓ
≡Ｘ＋Ｙ（MOD（2ⁿ−１）、０≦Ｓ＜2ⁿ−１とする
と、2ⁿ−１＞Ｘ＋Ｙ≧０のときにはＣ＝０となる
からＺ＝Ｓ＝Ｘ＋Ｙとなり、Ｘ＋Ｙ≧2ⁿのときに
はＣ＝１となるからＺ＝Ｓ＝（Ｘ＋Ｙ＋１）−2ⁿ＝
Ｘ＋Ｙ−（2ⁿ−１）となる。従つてＸ＋Ｙ＝2ⁿ−
１以外のときには、この加算回路の出力Ｚが加算
数、被加算数Ｘ、ＹのMOD（2ⁿ−１）の加算結果
となる。 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 U≡V+W(MOD(M))
Writing this means that the result of adding V and W using MOD(M) is U. ). S
If ≡X+Y(MOD(2 ⁿ -1), 0≦S<2 ⁿ -1, then C=0 when 2 ⁿ -1>X+Y≧0, so Z=S=X+Y, and X+Y≧2 ⁿ Sometimes C=1, so Z=S=(X+Y+1)−2 ⁿ =
It becomes X+Y-(2 ⁿ -1). Therefore, X+Y=2 ⁿ −
When the value is other than 1, the output Z of this adder circuit becomes the addition result of MOD(2 ⁿ -1) of the addition number, the augends 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ⁿ−１）の加算回路は、キヤリ
入力端子を有しないかまたは“０”をキヤリ入力
とするｎ（ｎ：正の整数）ビツトのバイナリ加算
器（第１の加算器）と、“１”をキヤリ入力とす
るｎビツトのバイナリ加算器（第２の加算器）
と、セレクタによつて構成され、前記セレクタに
より、第２の加算器のキヤリ出力が“０”のとき
には第１の加算器の加算結果を選択し、第２の加
算器のキヤリ出力が“１”のときには第２の加算
器の加算結果を選択するように構成したものであ
り、これにより高速にMOD（2ⁿ−１）の加算がで
きるものである。Structure of the Invention The MOD (2 ⁿ -1) adder circuit of the present invention is an n (n: positive integer) bit binary adder (first adder) and an n-bit binary adder with “1” as a carry input (second adder)
The selector selects the addition result of the first adder when the carry output of the second adder is "0", and selects the addition result of the first adder when the carry output of the second adder is "1". '', the addition result of the second adder is selected, thereby allowing the addition of 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ⁿ−
１）の加算回路のブロツク図を示すものである。
第２図において、１はキヤリ入力として“１”が
入力されているｎビツトのバイナリ加算器（Ｅと
する）、２はキヤリ入力端子のないｎビツトのバ
イナリ加算器（Ｆとする）、３はセレクタである。
ＥとＦの両方に加算数Ｘ＝（x₀、x₁、……、x_o-1）
と被加算数Ｙ＝（y₀、y₁、……、y_o-1）とを入力
し、それぞれの加算出力、Σ＝（Σ₀、Σ₁、……、
Σ_o-1）とΣ′＝（Σ₀、Σ₁、……、Σ′_o-1）を前記セ
レ
クタに入力し、セレクタの出力Ｚ＝（z₀、z₁、…
…z_o-1）は、Ｅのキヤリ出力ＣがＣ＝０のときに
は、Ｚ＝Σ′となり、Ｃ＝１のときには、Ｚ＝Σと
なるように構成している。 FIG. 2 shows MOD (2 ⁿ −
1) shows a block diagram of the adder circuit of FIG.
In Fig. 2, 1 is an n-bit binary adder (denoted as E) to which "1" is input as a carry input, 2 is an n-bit binary adder without a carry input terminal (denoted as F), and 3 is a selector.
The number of additions to both E and F is X = (x ₀ , x ₁ , ..., x _o-1 )
and addend Y = (y ₀ , y ₁ , ..., y _o-1 ) are input, and the respective addition outputs, Σ = (Σ ₀ , Σ ₁ , ...,
Σ _o-1 ) and Σ′ = (Σ ₀ , Σ ₁ , ..., Σ′ _o-1 ) are input to the selector, and the selector output Z = (z ₀ , z ₁ , ...
...z _o-1 ) is configured such that when the carry output C of E is C=0, Z=Σ', and when C=1, Z=Σ.

以上のように構成された本実施例のMOD（2ⁿ−
１）の加算回路についてその動作を説明する。Ｅ
はΣ≡Ｘ＋Ｙ＋１（MOD2ⁿ）を出力し、ＦはΣ′≡
Ｘ＋Ｙ（MOD2ⁿ）を出力するが、Ｓ≡Ｘ＋Ｙ
（MOD（2ⁿ−１））、０≦Ｓ≦2ⁿ−１とΣ、Σ′とを
比較すると、Ｘ＋Ｙ≧2ⁿ−１のときにはＳ＝Σと
なり、2ⁿ−１＞Ｘ＋Ｙ≧０のときには、Ｓ＝Σ′と
なる。しかるにＸ＋Ｙ≧2ⁿ−１のときにはＣ＝１
になり、2ⁿ−１＞Ｘ＋Ｙ≧０のときにはＣ＝０に
なるので、上記のように構成することにより、こ
のMOD（2ⁿ−１）の加算回路の出力Ｚは、Ｚ＝Ｓ
となる。 The MOD of this embodiment configured as described above (2 ⁿ −
The operation of the adder circuit 1) will be explained. E
outputs Σ≡X+Y+1 (MOD2 ⁿ ), and F outputs Σ′≡
Outputs X+Y (MOD2 ⁿ ), but S≡X+Y
(MOD(2 ⁿ -1)), 0≦S≦2 ⁿ -1 and comparing Σ and Σ', when X+Y≧2 ⁿ -1, S=Σ, and when 2 ⁿ -1>X+Y≧0, Sometimes S=Σ'. However, when X+Y≧2 ⁿ −1, C=1
When 2 ⁿ ^-1 >
becomes.

以上のように本実施例によれば、使用する２つ
の加算器間のキヤリ伝搬をなくしたことにより、
MOD（2ⁿ−１）の加算の演算時間を短縮してい
る。なお、上の実施例ではＦの加算器をキヤリ入
力端子が存在しないとしたが、Ｆはキヤリ入力端
子を持つていてもよく、ただそのときにはキヤリ
入力は“０”でなければならない。またこの
MOD（2ⁿ−１）の加算器の入力である加算数Ｘ
か、被加算数Ｙのどちらか一方の各ビツトをすべ
て反転することにより、MOD（2ⁿ−１）の減算回
路を構成することができる。 As described above, according to this embodiment, by eliminating the carry propagation between the two 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 has the advantage of improving the calculation speed by nearly twice as much as the conventional one by eliminating the carry propagation between the two n-bit binary adders used. You can get the same effect. Further, 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, 10, 20... n-bit binary adder, 3... selector.

Claims

[Claims]

1 An n (n: an integer of 2 or more) bit binary first adder that does not have a carry input terminal or has a carry input of “0” and an n-bit binary first adder that has a carry input of “1”. a second adder;
a selector, the selector selects the addition result of the first adder when the carry output of the second adder is "0", and selects the addition result of the first adder;
When the carry output of the adder is "1", the addition result of the second adder is connected, and the two input terminals of the first adder are used as two input terminals, and the selector is connected so that the addition result of the second adder is selected. A MOD (2 ⁿ −1) adder circuit characterized in that an output terminal is used as an output terminal.