JPH0584931B2 - - Google Patents
Info
- Publication number
- JPH0584931B2 JPH0584931B2 JP62102530A JP10253087A JPH0584931B2 JP H0584931 B2 JPH0584931 B2 JP H0584931B2 JP 62102530 A JP62102530 A JP 62102530A JP 10253087 A JP10253087 A JP 10253087A JP H0584931 B2 JPH0584931 B2 JP H0584931B2
- Authority
- JP
- Japan
- Prior art keywords
- stage
- output
- shift register
- exclusive
- input
- 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 - Lifetime
Links
Landscapes
- Detection And Correction Of Errors (AREA)
- Error Detection And Correction (AREA)
Description
〔産業上の利用分野〕
この発明は、符号化器及び復号器において必要
となる有限体の乗算回路に関するものである。 〔従来の技術〕 従来のこの種の有限体乗算回路としては、例え
ば、宮川、岩垂、今井“符号理論”、昭晃堂、
pp94〜pp.112（October，1973）に示された内容
により容易に導出できる第３図のような回路が構
成できる。第３図は、GF（24）の有限体の乗算回
路の例であり、１７は元をベクトル表現から指数
表現に変換するためのテーブルメモリ、１８は逆
に元を指数表現からベクトル表現に変換するため
のテーブルメモリ、１９は４ビツト２入力加算回
路、２０はモジユロ１５演算回路である。 次に従来技術の動作について説明する。まず
GF（24）を導くために原始多項式としてｆ(Z)＝Z4
＋Ｚ＋１を用い、ｆ(X)の原始元をαとすると、指
数表現とベクトル表現の元の対応は次のようにな
る。
となる有限体の乗算回路に関するものである。 〔従来の技術〕 従来のこの種の有限体乗算回路としては、例え
ば、宮川、岩垂、今井“符号理論”、昭晃堂、
pp94〜pp.112（October，1973）に示された内容
により容易に導出できる第３図のような回路が構
成できる。第３図は、GF（24）の有限体の乗算回
路の例であり、１７は元をベクトル表現から指数
表現に変換するためのテーブルメモリ、１８は逆
に元を指数表現からベクトル表現に変換するため
のテーブルメモリ、１９は４ビツト２入力加算回
路、２０はモジユロ１５演算回路である。 次に従来技術の動作について説明する。まず
GF（24）を導くために原始多項式としてｆ(Z)＝Z4
＋Ｚ＋１を用い、ｆ(X)の原始元をαとすると、指
数表現とベクトル表現の元の対応は次のようにな
る。
【表】
従来の有限体乗算回路は、以上のように構成さ
れているので、もともとベクトル表現で表された
２つの元の積を演算するのに一度指数表現にそれ
ぞれ変換し、更に演算後もとのベクトル表現に逆
変換する必要があり、回路を構成するハードウエ
ア量が多いという問題点があつた。 この発明は、上記のような問題点を解消するた
めになされたもので、有限体上の乗算をベクトル
表現のまま処理できるように構成し、回路を構成
するハードウエア量を大幅に少なくすることを目
的とする。 〔問題点を解決するための手段〕 この発明に係る有限体乗算回路は、発明者らの
“有限体上の演算に関する考案〔〕”、第９回情
報理論とその応用学会、pp.115〜pp.120
（October、29−31，1986）で証明されているよ
うに、GF（2m）を導くために原始多項式として、
ｆ(Z)＝Zm＋Zk＋１の８項多項式を用いて、最終
ｍ段目の出力と途中ｍ−ｋ段目の出力を排他的論
理和をとり１段目の入力とするようなｍ段シフト
レジスタを中心とするような簡単な回路を構成し
たものである。 〔作用〕 この発明における有限体乗算回路は、ｍ段シフ
トレジスタに入力パターンをプリセツトした後、
ｍ−１回のシフト動作を行うことにより、演算結
果が簡単に得られる。 〔発明の実施例〕 以下、この発明の一実施例を第１図について説
明する。ここでは、GF（2mのｍを４とした場合、
すなわち従来技術の説明で用いたGF（24）の有限
体の乗算回路を一例としてとりあげる。又、GF
（24）を導くための原始多項式も従来技術の説明
で用いたｆ(Z)＝Z4＋Ｚ＋１を用いる。 第１図において、２及び３はそれぞれ入力の元
〓及び〓、４は演算後の結果の元〓、５は４段シ
フトレジスタのプリセツト信号ｓ、６はシフトレ
ジスタのシフトクロツクｔ、７は２入力排他的論
理和ゲート、８は４入力排他的論理和ゲート、９
は２入力論理積ゲート、１０〜１３はプリセツト
入力付き１ビツト記憶素子で構成される４段シフ
トレジスタ、１４〜１６は１ビツト記憶素子で構
成される演算結果を一時的に保存するための３段
シフトレジスターである。 例えば入力の元〓としてα13に対応するベクト
ル表現（1101）と入力の元〓としてα9に対応する
ベクトル表現（1010）を考え、その２つの元の乗
算を一例にあげる。この例の回路動作を第２図に
タイムチヤートの形で示す。入力の元〓＝（a3，
a2，a1，a0）は、プリセツト信号ｓによつて、１
０にa1、１１にa2、１２にa3、１３にa0となるよ
うに右に１ビツト巡回シフトした形で４段シフト
レジスタに初期セツトされる。この４段シフトレ
ジスタでは最終４段目の出力と３段目の出力の排
他的論理和が１段目に入力されている。この４段
シフトレジスタにシフトクロツクｔを３クロツク
与えることにより、入力の元〓＝（b3，b2，b1，
b0）と、４段シフトレジスタ出力のビツト毎の論
理積がそれぞれのシフトロツク毎に出力され、４
入力排他的論理和ゲート８により演算され、シリ
アルなデータとして、c0，c3，c2，c1の順に出力
される。このシリアルデータは１４〜１６の３段
シフトレジスタに導びかれ、左に１ビツト巡回シ
フトする形のパラレルなデータとして、元〓と元
〓の乗算結果の元〓＝（c3，c2，c1，c0）すなわ
ち、α7に対応するベクトル表現（1011）を出力す
る。 なお、上記実施例では、GF（24）を導くための
原始多項式として、ｆ(Z)＝Z4＋Ｚ＋１を用いた
が、原始多項式としてｆ(Z)＝Z4＋Z3＋１の３項多
項式を選ぶこともでき、この場合の実施例は第４
図のように実現できる。この第４図の例におい
て、入力の元〓としてα13（ベクトル表現では
（0110）に対応）〓としてα9（ベクトル表現では
（0101）に対応）を選ぶとこれら２つの元の乗算
結果〓は前述と同様の動作によつて容易にα7（ベ
クトル表現では（0111）に対応）として得られ
る。又、一般にGF（2m）を導くために原始多項式
として、ｆ(Z)＝Zm＋Zk＋１の３項多項式を用い
ると、第５図のように実現される。すなわち、最
終ｍ段目の出力と途中ｍ−ｋ段目の出力の排他的
論理和をとり、１段目の入力とするようなｍ段シ
フトレジスタを中心とする回路構成において、入
力の元〓の（ak-1，ak-2，…a0，am-1，am-2，
…，ak）の巡回シフトのパターンをｍ段シフト
レジスタにプリセツトしm-1回のシフト動作を行
うことにより、入力の元〓と〓の乗算結果〓を〓
と同様の巡回シフトの順序（ck-1，ck-2，…，
c0，cm-1，cm-2，…ck）にてｍ入力の排他的論
理和ゲートの出力として得ることができる。 このように、この発明では数個のシフトレジス
タと数個のAND回路、排他的論理和回路で実現
でき、従来のようなベクトル・指数変換用テーブ
ルメモリやその逆変換メモリ、モジユロ１５演算
回路のような複雑な回路を必要としない。 したがつて、回路構成が簡単になり、ハードウ
エアが少くてすむので、回路がコンパクトで、信
頼性も向上し、また、消費電力も少なくなる。 それ故、今後より発展して行くコンピユータや
情報伝送関連の符号化器復号器等に利用され、そ
の有用性を発揮することができる。 〔発明の効果〕 以上のように、この発明によれば、回路を構成
するハードウエア量を従来のものに比べ、大幅に
減少させたので、回路がコンパクトに実現できる
効果がある。
れているので、もともとベクトル表現で表された
２つの元の積を演算するのに一度指数表現にそれ
ぞれ変換し、更に演算後もとのベクトル表現に逆
変換する必要があり、回路を構成するハードウエ
ア量が多いという問題点があつた。 この発明は、上記のような問題点を解消するた
めになされたもので、有限体上の乗算をベクトル
表現のまま処理できるように構成し、回路を構成
するハードウエア量を大幅に少なくすることを目
的とする。 〔問題点を解決するための手段〕 この発明に係る有限体乗算回路は、発明者らの
“有限体上の演算に関する考案〔〕”、第９回情
報理論とその応用学会、pp.115〜pp.120
（October、29−31，1986）で証明されているよ
うに、GF（2m）を導くために原始多項式として、
ｆ(Z)＝Zm＋Zk＋１の８項多項式を用いて、最終
ｍ段目の出力と途中ｍ−ｋ段目の出力を排他的論
理和をとり１段目の入力とするようなｍ段シフト
レジスタを中心とするような簡単な回路を構成し
たものである。 〔作用〕 この発明における有限体乗算回路は、ｍ段シフ
トレジスタに入力パターンをプリセツトした後、
ｍ−１回のシフト動作を行うことにより、演算結
果が簡単に得られる。 〔発明の実施例〕 以下、この発明の一実施例を第１図について説
明する。ここでは、GF（2mのｍを４とした場合、
すなわち従来技術の説明で用いたGF（24）の有限
体の乗算回路を一例としてとりあげる。又、GF
（24）を導くための原始多項式も従来技術の説明
で用いたｆ(Z)＝Z4＋Ｚ＋１を用いる。 第１図において、２及び３はそれぞれ入力の元
〓及び〓、４は演算後の結果の元〓、５は４段シ
フトレジスタのプリセツト信号ｓ、６はシフトレ
ジスタのシフトクロツクｔ、７は２入力排他的論
理和ゲート、８は４入力排他的論理和ゲート、９
は２入力論理積ゲート、１０〜１３はプリセツト
入力付き１ビツト記憶素子で構成される４段シフ
トレジスタ、１４〜１６は１ビツト記憶素子で構
成される演算結果を一時的に保存するための３段
シフトレジスターである。 例えば入力の元〓としてα13に対応するベクト
ル表現（1101）と入力の元〓としてα9に対応する
ベクトル表現（1010）を考え、その２つの元の乗
算を一例にあげる。この例の回路動作を第２図に
タイムチヤートの形で示す。入力の元〓＝（a3，
a2，a1，a0）は、プリセツト信号ｓによつて、１
０にa1、１１にa2、１２にa3、１３にa0となるよ
うに右に１ビツト巡回シフトした形で４段シフト
レジスタに初期セツトされる。この４段シフトレ
ジスタでは最終４段目の出力と３段目の出力の排
他的論理和が１段目に入力されている。この４段
シフトレジスタにシフトクロツクｔを３クロツク
与えることにより、入力の元〓＝（b3，b2，b1，
b0）と、４段シフトレジスタ出力のビツト毎の論
理積がそれぞれのシフトロツク毎に出力され、４
入力排他的論理和ゲート８により演算され、シリ
アルなデータとして、c0，c3，c2，c1の順に出力
される。このシリアルデータは１４〜１６の３段
シフトレジスタに導びかれ、左に１ビツト巡回シ
フトする形のパラレルなデータとして、元〓と元
〓の乗算結果の元〓＝（c3，c2，c1，c0）すなわ
ち、α7に対応するベクトル表現（1011）を出力す
る。 なお、上記実施例では、GF（24）を導くための
原始多項式として、ｆ(Z)＝Z4＋Ｚ＋１を用いた
が、原始多項式としてｆ(Z)＝Z4＋Z3＋１の３項多
項式を選ぶこともでき、この場合の実施例は第４
図のように実現できる。この第４図の例におい
て、入力の元〓としてα13（ベクトル表現では
（0110）に対応）〓としてα9（ベクトル表現では
（0101）に対応）を選ぶとこれら２つの元の乗算
結果〓は前述と同様の動作によつて容易にα7（ベ
クトル表現では（0111）に対応）として得られ
る。又、一般にGF（2m）を導くために原始多項式
として、ｆ(Z)＝Zm＋Zk＋１の３項多項式を用い
ると、第５図のように実現される。すなわち、最
終ｍ段目の出力と途中ｍ−ｋ段目の出力の排他的
論理和をとり、１段目の入力とするようなｍ段シ
フトレジスタを中心とする回路構成において、入
力の元〓の（ak-1，ak-2，…a0，am-1，am-2，
…，ak）の巡回シフトのパターンをｍ段シフト
レジスタにプリセツトしm-1回のシフト動作を行
うことにより、入力の元〓と〓の乗算結果〓を〓
と同様の巡回シフトの順序（ck-1，ck-2，…，
c0，cm-1，cm-2，…ck）にてｍ入力の排他的論
理和ゲートの出力として得ることができる。 このように、この発明では数個のシフトレジス
タと数個のAND回路、排他的論理和回路で実現
でき、従来のようなベクトル・指数変換用テーブ
ルメモリやその逆変換メモリ、モジユロ１５演算
回路のような複雑な回路を必要としない。 したがつて、回路構成が簡単になり、ハードウ
エアが少くてすむので、回路がコンパクトで、信
頼性も向上し、また、消費電力も少なくなる。 それ故、今後より発展して行くコンピユータや
情報伝送関連の符号化器復号器等に利用され、そ
の有用性を発揮することができる。 〔発明の効果〕 以上のように、この発明によれば、回路を構成
するハードウエア量を従来のものに比べ、大幅に
減少させたので、回路がコンパクトに実現できる
効果がある。
第１図はこの発明の一実施例によるGF（24）乗
算回路、第２図はこの発明の動作を示すタイムチ
ヤート、第３図は従来のGF（24）乗算回路、第４
図及び第５図はこの発明の他の実施例による乗算
回路である。 図において、１はGF（24）乗算回路、２は入力
の元ａ、３は入力の元ｂ、４は演算結果の元ｃ、
５はプリセツト信号ｓ、６はシフトクロツクｔ、
７は２入力排他的論理和ゲート、８は４入力排他
的論理和ゲート、９は２入力論理積ゲート、１０
〜１３，F1〜Fmはプリセツト入力付き１ビツト
記憶素子、１４〜１６，Ｇ１〜Gm−１は１ビツ
ト記憶素子、１７はベクトル・指数変換用テーブ
ルメモリ、１８は１７の逆変換用テーブルメモ
リ、１９は４ビツト２入力加算回路、２０はモジ
ユロ15演算回路、２１，２２は加算回路入力デー
タ、２３は加算結果出力データ、２４はモジユロ
15結果出力データである。なお、図中、同一符号
は同一、又は相当部分を示す。
算回路、第２図はこの発明の動作を示すタイムチ
ヤート、第３図は従来のGF（24）乗算回路、第４
図及び第５図はこの発明の他の実施例による乗算
回路である。 図において、１はGF（24）乗算回路、２は入力
の元ａ、３は入力の元ｂ、４は演算結果の元ｃ、
５はプリセツト信号ｓ、６はシフトクロツクｔ、
７は２入力排他的論理和ゲート、８は４入力排他
的論理和ゲート、９は２入力論理積ゲート、１０
〜１３，F1〜Fmはプリセツト入力付き１ビツト
記憶素子、１４〜１６，Ｇ１〜Gm−１は１ビツ
ト記憶素子、１７はベクトル・指数変換用テーブ
ルメモリ、１８は１７の逆変換用テーブルメモ
リ、１９は４ビツト２入力加算回路、２０はモジ
ユロ15演算回路、２１，２２は加算回路入力デー
タ、２３は加算結果出力データ、２４はモジユロ
15結果出力データである。なお、図中、同一符号
は同一、又は相当部分を示す。
Claims (1)
- 【特許請求の範囲】 １ ガロア体GF（2m）の任意の二つの元〔〓
（am−1，am-2，…a1，a0），〓（bm−1，bm-2，
…b1，b0）〕の乗算において、GF（2m）を導くた
めに原始多項式としてｆ(Z)＝Zm＋Zk＋１の３項
多項式を用いた場合であつて、 最終ｍ段目の出力と途中ｍ−ｋ段目の出力との
排他的論理和をとり、１段目の入力とするｍ段シ
フトレジスタ。 上記ｍ段シフトレジスタの各段の出力（Fm，
Fm-1，…F1）と元〓（b0，b1，…bn-1）との２
入力論理積をとるｍ個の論理積ゲート、 この論理積ゲートのｍ個の出力の排他的論理和
を求める排他的論理和ゲートを備え、上記ｍ段の
シフトレジスタの各段（ｍ，m-1…１）に元〓
（ak−1，ak-2，…a0，am-1，am-2，…ak）を入
力し、その各段の出力と元〓（b0，b1，…bm-1）
とを上記ｍ個の論理積ゲートに入力し、上記ｍ段
のシフトレジスタをｍ−１回シフト動作を行い、
上記排他的論理和ゲートから求める乗算結果〓
（ck−1，ck-2，…C0，cm-1，cm-2，…ck）を順
次出力するようにした有限体乗算回路。 ２ ガロア体GF（2m）の任意の二つの元（〓
（am−1，am-2，…a1，a0），〓（bm−1，bm-2，
…b1，b0）〕の乗算において、GF（2m）を導くた
めに原始多項式としてｆ(Z)＝Zm＋Zk＋１の３多
項式を用いた場合であつて、 最終ｍ段目の出力と途中ｍ−ｋ段目の出力との
排他的論理和をとり、１段目の入力とするｍ段シ
フトレジスタ、 上記ｍ段シフトレジスタの各段の出力（Fm，
Fm-1，…F1）と元〓（b0，b1，…bm-1）との２
入力論理積をとるｍ個の論理積ゲート、 この論理積ゲートのｍ個の出力の排他的論理和
を求める排他的論理和ゲート、 この排他的論理和ゲートからの出力を受けて各
段の出力を取り出すようにしたｍ−１段の並列出
力用シフトレジスタを備え、 上記ｍ段のシフトレジスタの各段（ｍ，m-1，
１）に元〓（ak−1，ak-2，…a0，am-1，am-2，
…ak）を入力し、その各段の出力と元〓（b0，
b1，…bm-1）とを上記ｍ個の論理積ゲートに入
力し、上記ｍ段のシフトレジスタｍ−１回シフト
動作を行い、上記排他的論理和ゲートから求める
乗算結果〓（ck−1，ck-2，…co，cm-1，cm-2，
…ck）を順次出力すると共に上記並列出力用シ
フトレジスタに入力して上記m-1回のシフト動作
を行い、並列出力として取出すようにした有限体
乗算回路。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP62102530A JPS63268037A (ja) | 1987-04-24 | 1987-04-24 | 有限体乗算回路 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP62102530A JPS63268037A (ja) | 1987-04-24 | 1987-04-24 | 有限体乗算回路 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS63268037A JPS63268037A (ja) | 1988-11-04 |
| JPH0584931B2 true JPH0584931B2 (ja) | 1993-12-03 |
Family
ID=14329861
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP62102530A Granted JPS63268037A (ja) | 1987-04-24 | 1987-04-24 | 有限体乗算回路 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS63268037A (ja) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP4472808B2 (ja) * | 1999-08-19 | 2010-06-02 | ネッツエスアイ東洋株式会社 | 積和演算装置及びこれを用いた暗号・復号装置 |
| JP4484002B2 (ja) * | 1999-10-04 | 2010-06-16 | ネッツエスアイ東洋株式会社 | 演算プロセッサ |
-
1987
- 1987-04-24 JP JP62102530A patent/JPS63268037A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS63268037A (ja) | 1988-11-04 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPS60144834A (ja) | 有限体の演算回路 | |
| US5227992A (en) | Operational method and apparatus over GF(2m) using a subfield GF(2.sup. | |
| JPH02148225A (ja) | 有限体の乗法的逆数元を計算するデータ処理方法及び装置 | |
| US6052704A (en) | Exponentiation circuit and inverter based on power-sum circuit for finite field GF(2m) | |
| KR100322739B1 (ko) | 유한체연산방법및그장치 | |
| US4638449A (en) | Multiplier architecture | |
| JPH09231742A (ja) | 非同期ｆｉｆｏにおいてハーフフルフラグ及びハーフエンプティフラグを作成するステートマシンの構成 | |
| US5964826A (en) | Division circuits based on power-sum circuit for finite field GF(2m) | |
| US5931894A (en) | Power-sum circuit for finite field GF(2m) | |
| Chren Jr | Low delay-power product CMOS design using one-hot residue coding | |
| US5691930A (en) | Booth encoder in a binary multiplier | |
| Cardarilli et al. | RNS-to-binary conversion for efficient VLSI implementation | |
| JPH10187471A (ja) | ガロア域２５６演算用の組合せ多項式乗算器 | |
| JPS63268037A (ja) | 有限体乗算回路 | |
| Gorodecky et al. | Efficient hardware operations for the residue number system by Boolean minimization | |
| JPH03661B2 (ja) | ||
| JPS63219066A (ja) | 直交変換装置 | |
| JPH0519170B2 (ja) | ||
| JPS5841532B2 (ja) | セキワケイサンカイロ | |
| JPS63221426A (ja) | ＧＦ（２▲上ｍ▼）のガロア体に属する元の乗算装置 | |
| JP2701378B2 (ja) | 演算方式 | |
| JP3346204B2 (ja) | 可変長符号復号装置 | |
| JPH1196030A (ja) | 有限体上の乗算方法及び乗算回路 | |
| JP3433487B2 (ja) | ２進１０進変換器 | |
| KR100265358B1 (ko) | 고속의쉬프팅장치 |