JPH0783277B2 - ガロア体上の元の表現形式変換回路 - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はデジタル処理回路に関し、特にその符号化・復
号回路において用いられるガロア体（galois体：加減乗
除の四則演算が行える元の集合で元の数が有限であるも
の。通常、ｑを元の数としてGF（ｑ）で表わす。）上の
元の指数・ベクトル変換回路に関する。

〔従来技術〕

従来、ガロア体上の元の指数・ベクトル変換は処理が非
常に複雑であるので、指数・ベクトル変換回路としては
ROM（リードオンメモリー）に指数−ベクトル対応テー
ブルを生成しておきそれにより変換処理を行なうのが通
常であった。

〔従来技術の問題点〕

しかしながらROMは回路構成が大きいので回路構成の簡
略化には不適であった。このためROMに変わる簡単で回
路量の小さい指数・ベクトル変換回路が望まれていた。

〔問題点を解決するための手段〕

本発明は、ROMを用いず、ゲート回路及び乗算回路によ
ってガロア体上の元の指数・ベクトル変換を行なう簡単
な回路の指数・ベクトル変換回路を提供することを目的
とする。

かかる目的を達成するために、本発明では、αを原始元
とするガロア体GF（2^m）上の任意の元α^ｎについて、指
数表現をｎ＝2^m-1・N_m-1＋2^m-2・N_m-2＋・・・＋２・N₁
＋N₀とするとき、入力されるN_i（ｉ＝0,1,・・・,m−
１）が１のときにαの2ⁱ乗を出力し、０のときに１を出
力する論理回路手段と、記憶手段と、該記憶手段の記憶
内容と前記論理回路手段からの出力とを乗算する乗算手
段と、該乗算手段の乗算結果を前記記憶手段に更新記憶
するように制御する制御手段とを具える。

〔実施例〕

以下、本発明の実施例について説明する。

指数・ベクトル変換回路においては指数ｎはバイナリで
入力され、次のように表される。それからα^ｎを生成す
るために次のように分解される。

ｎ＝N7・128＋N6・64＋N5・32 ＋N4・16＋N3・８＋N2・４＋N1・２＋N0・１ α^ｎ＝α^N7・128・α^N6・64・α^N5・32・α^N4・16 ・α^N3・８・α^N2・４・α^N1・２・α^N0 従って、Ni（ｉ＝０・・・７）が１のときα^{2^i}を出力
し、０のとき１を出力する回路を構成し、その出力を順
次乗じていけばよい。そのブロック図を第１図に示し、
その動作タイミングを第２図に示す。符号長ｎのバイナ
リー表現がN0→N7の順で送られてきたときバスラインＹ
にはα^N0→α^N7・128が出力され乗算回路２に送られ
る。乗算回路２の出力Ｚからは順次α^N0〜α^N7・128を
乗じた出力が出力される。その出力をレジスタ３にとり
こみ、乗算回路２のもう一つの入力端子Ｘに出力する。
ただし、Ｘには、最初Ｙがα^N0を出力した時１を出力す
るようにレジスタの内容をセツトしておく。α^N7・128
が出力されたときα^ｎが生成される。

HCKは、N0〜N7が出力されている間図示しないクロツク
発振器から出力されているクロツクパルスである。

ここでN0〜N7に従ってα^N0〜^N7・128を出力する指数／
ベクトル回路１の構成を第３図に示す。

この回路は従来はROMによって生成されていたが本実施
例ではゲート回路によって構成してある。尚、第３図に
おいて▲［＋］▼はExclusive OR（排他的論理和）回
路、 はバスラインを示す。第３図の回路は既約多項式がｐ
（ｘ）＝x⁸＋x⁴＋x³＋x²＋１の場合においてNi＝１（ｉ
＝０→７）のとき順次α＝（01000000），α^２＝（0010
0000），α^４＝（00001000），α^８＝（10111000），α
¹⁶＝（00110010），α³²＝（10111001），α⁶⁴＝（1111
1010），α¹²⁸＝（10100001）を出力し、Ni＝０のとき
１を出力するゲート回路構成になっている。

以上の構成によって、指数表現ｎから、ベクトル表現α
^ｎへの変換を簡略化されたゲート回路と乗算回路によっ
て行なうことができる。

第１図の例ではα^ｎ生成までにN0〜N7をシリアルに出力
するために８クロツク入力必要であるが、クロツク入力
数を少なくしたい場合N0〜N7をパラレルに出力し、乗算
回路をそれに応じて複数もつことによってクロツク入力
にすることもできる。その場合回路量が多少本実施例よ
り多くなる。

〔発明の効果〕

以上説明したように、本発明によれば、ガロア体上の元
の指数表現からベクトル表現への変換を、演算により実
現するようにしたので、両表現を対応させたテーブルを
利用する場合に比して、小さな回路規模で、この変換を
行うことができるという効果がある。

【図面の簡単な説明】

第１図は本発明の実施例に係る指数・ベクトル変換回路
のブロツク図、第２図は第１図のブロツク図の動作タイ
ミングチヤート、第３図は指数／ベクトル回路の構成を
示す図である。 １……指数／ベクトル回路 ２……乗算回路 ３……レジスタ

Claims (1)

【特許請求の範囲】
1. 【請求項１】αを原始元とするガロア体GF（2^m）上の任
   意の元α^ｎについて、指数表現を ｎ＝2^m-1・N_m-1＋2^m-2・N_m-2＋・・・＋２・N₁＋N₀ とするとき、入力されるN_i（ｉ＝0,1,・・・,m−１）が
   １のときにαの2ⁱ乗を出力し、０のときに１を出力する
   論理回路手段と、 記憶手段と、 該記憶手段の記憶内容と前記論理回路手段からの出力と
   を乗算する乗算手段と、 該乗算手段の乗算結果を前記記憶手段に更新記憶するよ
   うに制御する制御手段とを具え、前記論理回路手段にN_i
   （ｉ＝0,1,・・・,m−１）を順次入力して、前記元α^ｎ
   のベクトル表現を生成することを特徴とするガロア体上
   の元の表現形式変換回路。