JPH0724016B2 - ＧＦ（２▲上ｍ▼）のガロア体に属する元の乗算装置 - Google Patents
ＧＦ（２▲上ｍ▼）のガロア体に属する元の乗算装置Info
- Publication number
- JPH0724016B2 JPH0724016B2 JP62056339A JP5633987A JPH0724016B2 JP H0724016 B2 JPH0724016 B2 JP H0724016B2 JP 62056339 A JP62056339 A JP 62056339A JP 5633987 A JP5633987 A JP 5633987A JP H0724016 B2 JPH0724016 B2 JP H0724016B2
- Authority
- JP
- Japan
- Prior art keywords
- register
- multiplier
- result
- bit
- contents
- 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
- Error Detection And Correction (AREA)
- Detection And Correction Of Errors (AREA)
Description
【発明の詳細な説明】 〔産業上の利用分野〕 本発明は凝似乱数系列符号、即ちPN符号を発生するため
の原始既約多項式を算出する等の2m有限体、換言すれば
GF（2m）にて表わされるガロア体に属する２つの元（ベ
クトルとも呼ばれる）の乗算を行なわせる分野において
用いられるものである。
の原始既約多項式を算出する等の2m有限体、換言すれば
GF（2m）にて表わされるガロア体に属する２つの元（ベ
クトルとも呼ばれる）の乗算を行なわせる分野において
用いられるものである。
従来、この種の有限体理論に基づいて、その有限体に属
する元の乗算は高級な電子計算機を用いて、有限体理論
に基づく部分の演算については、其の部分専用のサブル
ーチンを組んで、極めて処理時間の掛る、効率の悪るい
手法によっていた。従って演算結果其の物を実時間処理
にて直ちに用いる事は行なわれていなかった。
する元の乗算は高級な電子計算機を用いて、有限体理論
に基づく部分の演算については、其の部分専用のサブル
ーチンを組んで、極めて処理時間の掛る、効率の悪るい
手法によっていた。従って演算結果其の物を実時間処理
にて直ちに用いる事は行なわれていなかった。
上述した従来の高級な電子計算機を用いて、有限体理論
に基づく、元の乗算を行なわせる方法においては、有限
体理論に基づく演算そのものが、解析学理論とは全く異
質であるため、電子計算機においては、取扱上不得意な
理論構成である分野に属していた。
に基づく、元の乗算を行なわせる方法においては、有限
体理論に基づく演算そのものが、解析学理論とは全く異
質であるため、電子計算機においては、取扱上不得意な
理論構成である分野に属していた。
従って、例えば有限体における元の乗算過程を不可欠と
する原始既約多項式を演算によって求める場合を例にと
ると、演算結果を算出するに何時間も掛る性質を持つ結
果になるので、新らたな原始既約多項式を求めて、先と
は異なるPN時系列符号に切換えて、用いることは、実用
上為し得ないものとして、通常扱われていた。
する原始既約多項式を演算によって求める場合を例にと
ると、演算結果を算出するに何時間も掛る性質を持つ結
果になるので、新らたな原始既約多項式を求めて、先と
は異なるPN時系列符号に切換えて、用いることは、実用
上為し得ないものとして、通常扱われていた。
この様な必要性がある場合には、多数の原始既約多項式
を別途に算出しておいて、この算出結果をROM等に記憶
させておき、これを随時取出して用いる方法が取られて
いた。併しながらGF（2m）のガロア体においては、原始
既約多項式の数は 存在している。（注こゝに（2m−１）は（2m−１）の
オイラー関数である。）いま、ｍの数のいくつかについ
て、其の数を求めると、 ｍ＝25のとき1,382,400ケ、ｍ＝26のとき1,719,900ケ、
ｍ＝27のとき4,202,496ケ、ｍ＝28のとき4,741,632ケの
多数存在する。記憶させておく手法によっては、この様
な多数を収容し切れないので、実際上はほんの１部しか
用いられないのが従来における実情である。
を別途に算出しておいて、この算出結果をROM等に記憶
させておき、これを随時取出して用いる方法が取られて
いた。併しながらGF（2m）のガロア体においては、原始
既約多項式の数は 存在している。（注こゝに（2m−１）は（2m−１）の
オイラー関数である。）いま、ｍの数のいくつかについ
て、其の数を求めると、 ｍ＝25のとき1,382,400ケ、ｍ＝26のとき1,719,900ケ、
ｍ＝27のとき4,202,496ケ、ｍ＝28のとき4,741,632ケの
多数存在する。記憶させておく手法によっては、この様
な多数を収容し切れないので、実際上はほんの１部しか
用いられないのが従来における実情である。
本発明はこの様な原始既約多項式算出の場合に限るもの
ではないが、GF（2m）のガロア体の理論において、通常
の電子計算機が最も不得手とする元の乗算を簡単な外付
回路によって、演算処理を著るしく高速にして、実時間
処理を可能にせんとするものである。
ではないが、GF（2m）のガロア体の理論において、通常
の電子計算機が最も不得手とする元の乗算を簡単な外付
回路によって、演算処理を著るしく高速にして、実時間
処理を可能にせんとするものである。
本発明により上述の問題点を解決するには、GF（2m）の
ガロア体における原始既約多項式接続されたシフトレジ
スタと、マイクロプロセッサーを備え、マイクロプロセ
ッサーに従属するRAMに多項式の係数表示された被乗数
の元および乗数の元を格納するレジスター領域を備え、
更に演算結果を格納するレジスター領域を備える。又マ
イクロプロセッサーに従属するROMの領域を備え、先づ
被乗数の元を原始既約多項式接続されたシフトレジスタ
ーに書き込む、つぎに乗数の元の最下位桁の１セット
が、“0"であれば結果レジスターは全ビット“0"のまゝ
にし、“1"であれば原始既約多項式接続されたシフトレ
ジスターの内容を其のまゝ結果レジスターに全ビット取
り込み転記する。つぎに乗数の元を格納した乗数レジス
ターを最下位の方へ１ビットシフトさせると共に原始既
約多項式接続されたシフトレジスターを最上位の方へ向
って１ビットシフトさせる。つぎに乗数レジスター内容
の新らたな最下位ビット（即ち、もとの乗数元の最下位
より１ビット分上位のビット）が“0"であるなら其のま
ゝ、“1"であるなら新らたな原始既約多項式接続された
シフトレジスターの内容を取り込み、結果レジスターの
内容と全ｍビットに就いてビット毎の排他論理和を求
め、新らたに結果レジスター内容として格納する。以下
順次乗数レジスターを下位の方へシフトさせると共に原
始既約多項式接続されたシフトレジスターを上位の方に
シフトさせつゝ其の都度新らたな乗数レジスターの最下
位ビットが“1"なるか“0"なるかによって同様に取扱か
って結果レジスターを更新する。しかして（ｍ−１）回
のシフトを行なわせた後の結果レジスターの内容が求め
る乗算結果なるよう命令が書き込まれている前記ROM領
域を備える手段によって、GF（2m）のガロア体の元の乗
算を遂行することにより達成され得る。
ガロア体における原始既約多項式接続されたシフトレジ
スタと、マイクロプロセッサーを備え、マイクロプロセ
ッサーに従属するRAMに多項式の係数表示された被乗数
の元および乗数の元を格納するレジスター領域を備え、
更に演算結果を格納するレジスター領域を備える。又マ
イクロプロセッサーに従属するROMの領域を備え、先づ
被乗数の元を原始既約多項式接続されたシフトレジスタ
ーに書き込む、つぎに乗数の元の最下位桁の１セット
が、“0"であれば結果レジスターは全ビット“0"のまゝ
にし、“1"であれば原始既約多項式接続されたシフトレ
ジスターの内容を其のまゝ結果レジスターに全ビット取
り込み転記する。つぎに乗数の元を格納した乗数レジス
ターを最下位の方へ１ビットシフトさせると共に原始既
約多項式接続されたシフトレジスターを最上位の方へ向
って１ビットシフトさせる。つぎに乗数レジスター内容
の新らたな最下位ビット（即ち、もとの乗数元の最下位
より１ビット分上位のビット）が“0"であるなら其のま
ゝ、“1"であるなら新らたな原始既約多項式接続された
シフトレジスターの内容を取り込み、結果レジスターの
内容と全ｍビットに就いてビット毎の排他論理和を求
め、新らたに結果レジスター内容として格納する。以下
順次乗数レジスターを下位の方へシフトさせると共に原
始既約多項式接続されたシフトレジスターを上位の方に
シフトさせつゝ其の都度新らたな乗数レジスターの最下
位ビットが“1"なるか“0"なるかによって同様に取扱か
って結果レジスターを更新する。しかして（ｍ−１）回
のシフトを行なわせた後の結果レジスターの内容が求め
る乗算結果なるよう命令が書き込まれている前記ROM領
域を備える手段によって、GF（2m）のガロア体の元の乗
算を遂行することにより達成され得る。
次に、本発明について図面について図面を参照して説明
する。
する。
第３図はGF（2m）のガロア体に属する元の乗算の特異性
に就いて説明するためｍ＝４である場合の（24）のガロ
ア体の総べての元の表である。但し“0"の元は乗算した
とき何れと乗算しても“0"となる性質があるので、除い
てある。また第３図の表はGF（24）の第１次の原始既約
多項式X4＋Ｘ＋１によって表わされた場合を掲げたもの
である。
に就いて説明するためｍ＝４である場合の（24）のガロ
ア体の総べての元の表である。但し“0"の元は乗算した
とき何れと乗算しても“0"となる性質があるので、除い
てある。また第３図の表はGF（24）の第１次の原始既約
多項式X4＋Ｘ＋１によって表わされた場合を掲げたもの
である。
第３図のGF（24）の表から“0"の元を除く、元の総数は
α０〜α14までの15ケである。こゝにαは原始根であっ
てガロアの虚数とも呼ばれるものである。亦ガロア体の
特異な性格から解析学的に定義の出来ない観念的なもの
ではある。亦GF（2m）におけるガロア体の理論上の約束
事項としてmodulo2（mod2）であるから、αの多項式表
示の各元の係数は２で割った余りであるので、“1"又は
“0"である。乗法群としてのGF（2m）の各元の総数は
（2m−１）である。このことは第３図の示す表の各元の
多項式の係数のみに注目すればall“0"を除くｍビット
の２進符号の総てを夫々１つづつ表わしている。亦第３
図の表において、α14＝α３＋１にαを乗ずるとα15＝
α４＋αであるが、原始既約多項式のX4＋Ｘ＋１の約束
事に従いX4＝Ｘ＋１（mod2であるから移項しても符号は
変わらない）であるからα４＝α＋１ 故にα15＝α４
＋α＝α＋１＋α＝１（mod2）即ち なる関係にある。
α０〜α14までの15ケである。こゝにαは原始根であっ
てガロアの虚数とも呼ばれるものである。亦ガロア体の
特異な性格から解析学的に定義の出来ない観念的なもの
ではある。亦GF（2m）におけるガロア体の理論上の約束
事項としてmodulo2（mod2）であるから、αの多項式表
示の各元の係数は２で割った余りであるので、“1"又は
“0"である。乗法群としてのGF（2m）の各元の総数は
（2m−１）である。このことは第３図の示す表の各元の
多項式の係数のみに注目すればall“0"を除くｍビット
の２進符号の総てを夫々１つづつ表わしている。亦第３
図の表において、α14＝α３＋１にαを乗ずるとα15＝
α４＋αであるが、原始既約多項式のX4＋Ｘ＋１の約束
事に従いX4＝Ｘ＋１（mod2であるから移項しても符号は
変わらない）であるからα４＝α＋１ 故にα15＝α４
＋α＝α＋１＋α＝１（mod2）即ち なる関係にある。
以上の説明の範囲にても解るように、GF（2m）内の演算
はmodulo2の演算であること、各元のべき数については2
m−１にて還元する。即ち、modulo（2m−１）の性質が
ある。亦GF（2m）に属する各元は、原始既約多項式に従
って、αｍの要素はαm-1以下のべき数の多項式に置き
換えられる特異性を有している。これらの特異性がある
ので通常の電子計算機にては扱い難い性質となっている
のである。
はmodulo2の演算であること、各元のべき数については2
m−１にて還元する。即ち、modulo（2m−１）の性質が
ある。亦GF（2m）に属する各元は、原始既約多項式に従
って、αｍの要素はαm-1以下のべき数の多項式に置き
換えられる特異性を有している。これらの特異性がある
ので通常の電子計算機にては扱い難い性質となっている
のである。
更に本発明の実施例の説明に入る前に、本発明にて達成
しようとする乗算がどの様な性質を持っているか乗算の
例を説明する。
しようとする乗算がどの様な性質を持っているか乗算の
例を説明する。
α９＝α３＋αとα13＝α３＋α２＋１を乗じて、α９
×α13＝α22＝α７（べき乗数についてmod15）を得る
計算を行なって見よう。
×α13＝α22＝α７（べき乗数についてmod15）を得る
計算を行なって見よう。
α３＋α＋１は正しくα７である。本発明は、この様な
演算を合理的且つ迅速に行なわしめるものである。
演算を合理的且つ迅速に行なわしめるものである。
つぎに本発明の実施例である第１図に就き説明する。図
において、１はGF（24）の第１次の原始既約多項式接続
されたシフトレジスターである。このシフトレジスター
１は最下位がX0＝１と見做され順次上位に向ってX1,X2,
X3と見做される、また４のリードを通じてCLKよりクロ
ックを加えられると、シフトレジスターは最下位から最
上位に向って送られる。このことはシフトレジスターに
表示されたX3〜X0にて表わされた多項式にＸを乗じたこ
とに相当している。亦、X3が送り出されてX4となるとX0
＝１に書き込まれ、且つ前のX0＝１が送られた値とX4か
らの出力の排他論理和が11の排他論理和回路にて得ら
れ、その結果がX1に書込まれる様になされている。即ち
X3に値が有り、X0＝１に値が無ければ、CLKにクロック
が加えられてX3がX4になると、X1及びX0＝１に値が表わ
れＸ＋１となる。X3に値がありX0＝１に値があるとき、
CLKにクロックが加えられるとX4出力が出るのでX0＝１
に値が表らわれるが、X1には前のX0＝１とX4出力との排
他論理和がX1に書き込まれるので、X1の値は“0"とな
る。この関係は、modulo2の演算のもとにX4＝Ｘ＋１、
即ちX4＋Ｘ＋１なる原始既約多項式接続が施されている
関係である。また排他論理和回路11がmodulo2加算器で
ある事は公知の事柄である。
において、１はGF（24）の第１次の原始既約多項式接続
されたシフトレジスターである。このシフトレジスター
１は最下位がX0＝１と見做され順次上位に向ってX1,X2,
X3と見做される、また４のリードを通じてCLKよりクロ
ックを加えられると、シフトレジスターは最下位から最
上位に向って送られる。このことはシフトレジスターに
表示されたX3〜X0にて表わされた多項式にＸを乗じたこ
とに相当している。亦、X3が送り出されてX4となるとX0
＝１に書き込まれ、且つ前のX0＝１が送られた値とX4か
らの出力の排他論理和が11の排他論理和回路にて得ら
れ、その結果がX1に書込まれる様になされている。即ち
X3に値が有り、X0＝１に値が無ければ、CLKにクロック
が加えられてX3がX4になると、X1及びX0＝１に値が表わ
れＸ＋１となる。X3に値がありX0＝１に値があるとき、
CLKにクロックが加えられるとX4出力が出るのでX0＝１
に値が表らわれるが、X1には前のX0＝１とX4出力との排
他論理和がX1に書き込まれるので、X1の値は“0"とな
る。この関係は、modulo2の演算のもとにX4＝Ｘ＋１、
即ちX4＋Ｘ＋１なる原始既約多項式接続が施されている
関係である。また排他論理和回路11がmodulo2加算器で
ある事は公知の事柄である。
図において２は全体としてマイクロコンピュータを構成
している。この内部の記号CPUは通常マイクロプロセッ
サーと呼ばれる部分である。記号のRAMは通常ランダム
アクセスメモリーと呼ばれる読み出し、書込みの能力を
有するメモリーであって、其の内部に被乗数の元を格納
するレジスター領域21と、乗数の元を格納するレジスタ
ー領域22と演算結果を格納するレジスター領域23を備え
ている。また、記号のROMは通常リードオンリーメモリ
ーと呼ばれ、読出し専用である。其の書込まれた内容は
本発明の乗算機能を遂行するプログラムが含まれてい
る。マイクロプロセッサCPUに対して、RAM及びROMは常
にマイクロコンピュータの機能を遂行するものとして、
従属しているものである。これら３つは夫々が独立した
機能素子である場合もあれば、２の部分全体が一つの素
子となった、所謂、ワンチップマイクロコンピュータと
なっている場合もある。これら何れの場合であっても本
発明の機能遂行に支障なく用い得るものである。
している。この内部の記号CPUは通常マイクロプロセッ
サーと呼ばれる部分である。記号のRAMは通常ランダム
アクセスメモリーと呼ばれる読み出し、書込みの能力を
有するメモリーであって、其の内部に被乗数の元を格納
するレジスター領域21と、乗数の元を格納するレジスタ
ー領域22と演算結果を格納するレジスター領域23を備え
ている。また、記号のROMは通常リードオンリーメモリ
ーと呼ばれ、読出し専用である。其の書込まれた内容は
本発明の乗算機能を遂行するプログラムが含まれてい
る。マイクロプロセッサCPUに対して、RAM及びROMは常
にマイクロコンピュータの機能を遂行するものとして、
従属しているものである。これら３つは夫々が独立した
機能素子である場合もあれば、２の部分全体が一つの素
子となった、所謂、ワンチップマイクロコンピュータと
なっている場合もある。これら何れの場合であっても本
発明の機能遂行に支障なく用い得るものである。
以下第１図の動作について、先のα９とα13の乗算例に
沿って説明する。α９＝α３＋αであるからこれを係数
のみ降べきの順に表示すると1010である。亦α13＝α３
＋α２＋１であるから同様に1101にて表わされる。
沿って説明する。α９＝α３＋αであるからこれを係数
のみ降べきの順に表示すると1010である。亦α13＝α３
＋α２＋１であるから同様に1101にて表わされる。
α９は被乗数の元であるからRAM内部の被乗数レジスタ
領域21に1010が格納される。
領域21に1010が格納される。
α13は乗数の元であるからRAM内部の乗数レジスター領
域22に1101と格納される。先づROM内容の指示命令に従
って係数表示被乗数1010はRAMの領域21より一旦CPU内部
のアキュムレータに取り込まれた後、書き込みリード３
を通じて原始既約多項式接続されたシフトレジスタ１へ
CPUのアキュムレータより転送し書き込まれる。従ってX
3には1,X2には0,X1には1,X0には０が書き込まれる。つ
ぎにCPUのアキュムレータに乗数レジスター領域22の内
容の下位を取り込み、取り込みを完了すればアキュムレ
ータ上にて最下位が１であるから、原始既約多項式接続
されたシフトレジスタ内容をそのまゝCPUを経て結果レ
ジスタ23に取り込む。
域22に1101と格納される。先づROM内容の指示命令に従
って係数表示被乗数1010はRAMの領域21より一旦CPU内部
のアキュムレータに取り込まれた後、書き込みリード３
を通じて原始既約多項式接続されたシフトレジスタ１へ
CPUのアキュムレータより転送し書き込まれる。従ってX
3には1,X2には0,X1には1,X0には０が書き込まれる。つ
ぎにCPUのアキュムレータに乗数レジスター領域22の内
容の下位を取り込み、取り込みを完了すればアキュムレ
ータ上にて最下位が１であるから、原始既約多項式接続
されたシフトレジスタ内容をそのまゝCPUを経て結果レ
ジスタ23に取り込む。
即ち、 被乗数 MSB 1010 LSB 乗 数 1101 結果レジスター 1010 こゝにMSBは最上位、LSBは最下位である。
この結果レジスター内容を多項式にて表わせば、 α３＋α つぎにリード４を通じて原始既約多項式接続されたシフ
トレジスター１のCLK端子よりクロックを加えて１ビッ
ト最上位の方に向って１ビットシフトさせると共に乗数
レジスター22の内容を最下位の方に１ビットシフトさせ
て、アキュムレータに下位部分を取り込んで新らたな最
下位を見て、これが０であるから結果レジスター23は其
のまゝとする。併しながら此の過程にてX4に１が現らわ
れたので原始既約多項式接続の結果つぎのようになる。
トレジスター１のCLK端子よりクロックを加えて１ビッ
ト最上位の方に向って１ビットシフトさせると共に乗数
レジスター22の内容を最下位の方に１ビットシフトさせ
て、アキュムレータに下位部分を取り込んで新らたな最
下位を見て、これが０であるから結果レジスター23は其
のまゝとする。併しながら此の過程にてX4に１が現らわ
れたので原始既約多項式接続の結果つぎのようになる。
シフトレジスター１の内容 MSB 0111 LSB １シフトした乗数 0110 １ 結果レジスター 1010 したがって結果レジスター23の内容はα３＋αのまゝに
相当する。
相当する。
同様に第２回目のシフトを遂行すると、新らたな乗数の
最下位は１なので結果レジスター23の内容は前の結果レ
ジスター内容と新らたな原始既約多項式接続されたシフ
トレジスター１の内容がビット毎の排他論理和を取った
値に更新される。即ち シフトレジスター１の内容 MSB 1110 LSB ２シフト乗数 0011 01 結果レジスター 0100 したがって結果レジスター23の内容は、この段階にてα
２に相当する。
最下位は１なので結果レジスター23の内容は前の結果レ
ジスター内容と新らたな原始既約多項式接続されたシフ
トレジスター１の内容がビット毎の排他論理和を取った
値に更新される。即ち シフトレジスター１の内容 MSB 1110 LSB ２シフト乗数 0011 01 結果レジスター 0100 したがって結果レジスター23の内容は、この段階にてα
２に相当する。
同様に第３回目のシフトを遂行すると レジスター１の内容 MSB 1111 LSB ３シフト乗数 0001 101 結果レジスター 1011 即ち、この演算の結果レジスター内容はα３＋α＋１で
あって正しくα７となって求まっている。
あって正しくα７となって求まっている。
以上の過程を先の計算式（１）と比較すると、１回目の
シフトまでは第１ステップに相当している。また２回目
のシフトにおいては、第１ステップと第２ステップのmo
dulo2の和が得られている。最後の３回目のシフトにて
完了した時は更に第３ステップとのmodulo2加算が遂行
されている。計算式（１）における説明と第１図の実施
例における動作説明を見較べれば内容的に同様な性質を
有する処理手段でありながらより効率的に結果を求め得
るものであることが解るであろう。
シフトまでは第１ステップに相当している。また２回目
のシフトにおいては、第１ステップと第２ステップのmo
dulo2の和が得られている。最後の３回目のシフトにて
完了した時は更に第３ステップとのmodulo2加算が遂行
されている。計算式（１）における説明と第１図の実施
例における動作説明を見較べれば内容的に同様な性質を
有する処理手段でありながらより効率的に結果を求め得
るものであることが解るであろう。
また、ROMに書込まれたプログラム命令内容が簡単なも
のであり、従って高速な演処理を遂行可能な事も自明の
事柄である。
のであり、従って高速な演処理を遂行可能な事も自明の
事柄である。
更に以上の説明から判るように原始既約多項式接続され
たシフトレジスター１が果たしているガロア体理論に基
づいた役割を若し、マイクロコンピュータ内部のみにて
処理させようとするならば、ビット単位にて扱うプログ
ラムにては非常に煩雑なものとなり従って高速の処理は
不可能となる。更にバイト単位（８ビット）にて扱うに
してもさ程プログラムは簡略化されないのみで無く、ハ
ードウェアーの増大を招いてしまう。まして、第３図の
説明においては説明の便宜上ｍ＝４の場合に就いて説明
したが、より実用的なｍの値として25〜32の様に増大し
た場合、処理時間の差及びプログラムの煩雑化の差は著
るしく増大する。要するにマイクロコンピュータ２に
て、処理するに適切さの欠けた処理部分のみを外付の原
始既約多項式接続されたシフトレジスター１にて処理さ
せ、マイクロコンピュータ２にては処理する事が適切な
部分のみを遂行するように構成した点が本発明の骨子で
ある。また、本発明における原始既約多項式接続された
シフトレジスター１は原始既約多項式がPN符号を発生し
得る能力を有しているものなので生成多項式とも呼ば
れ、また本発明においてはこれを演算器として、働作さ
せているので生成多項式アキュムレータとも称し得る。
たシフトレジスター１が果たしているガロア体理論に基
づいた役割を若し、マイクロコンピュータ内部のみにて
処理させようとするならば、ビット単位にて扱うプログ
ラムにては非常に煩雑なものとなり従って高速の処理は
不可能となる。更にバイト単位（８ビット）にて扱うに
してもさ程プログラムは簡略化されないのみで無く、ハ
ードウェアーの増大を招いてしまう。まして、第３図の
説明においては説明の便宜上ｍ＝４の場合に就いて説明
したが、より実用的なｍの値として25〜32の様に増大し
た場合、処理時間の差及びプログラムの煩雑化の差は著
るしく増大する。要するにマイクロコンピュータ２に
て、処理するに適切さの欠けた処理部分のみを外付の原
始既約多項式接続されたシフトレジスター１にて処理さ
せ、マイクロコンピュータ２にては処理する事が適切な
部分のみを遂行するように構成した点が本発明の骨子で
ある。また、本発明における原始既約多項式接続された
シフトレジスター１は原始既約多項式がPN符号を発生し
得る能力を有しているものなので生成多項式とも呼ば
れ、また本発明においてはこれを演算器として、働作さ
せているので生成多項式アキュムレータとも称し得る。
尚、乗数元をシフトさせて演算を遂行することは、乗数
元の下位から遂次上位の値を見る事と等価なのでこの様
な変形本発明の権利の及ぶ範囲である。
元の下位から遂次上位の値を見る事と等価なのでこの様
な変形本発明の権利の及ぶ範囲である。
つぎに第２図について説明する。第２図も亦本発明の実
施例である。図においては、GF（24）のガロア体の乗算
機能とGF（25）のガロア体の乗算機能を切換えて、夫々
遂行出来る様な原始既約多項式接続がなされたシフトレ
ジスター１が用いられている。第２図において第１図と
同一の記号のものは、全く同一の役割を果たすものであ
る。特に２のマイクロコンピュータの部分はその内部を
含めて全く第１図の場合と同一である。原始既約多項式
接続されたシフトレジスター１は、２つの原始既約多項
式接続される様になされている。以下この点について説
明する。11と12は、夫々排他論理和回路13,14,15は夫々
論理回路即ち、AND回路である。16は論理和回路即ちOR
回路、又、17は反転回路即ちインバータである。マイク
ロコンピュータ２の側から切換リード６に“1"の信号を
与えられると、反転回路17の出力は“0"となる。これに
よって論理積回路15はX4の信号を適さない、しかも出力
は“0"の状態となるので、排他論理和回路12はX0＝１の
出力が“1"なるか“0"なるかに伴なって、そのまゝX1に
加えられる状態となる。即ち有っても無いと同じ状態の
12になる。このとき論理積回路13と14は、夫々X3の出力
をX4に通じる様に開らき、またX4の出力であるX5信号
は、排他論理和回路11に加えられる状態となる。11の出
力を受けるところはX2になっている。また、14の出力は
（X5信号）は論理和回路16を通じてX0＝１に加えられる
様になる。従って、X5＋X2＋１なる接続になる。これは
GF（25）における第１次の原始既約多項式接続状態であ
る。
施例である。図においては、GF（24）のガロア体の乗算
機能とGF（25）のガロア体の乗算機能を切換えて、夫々
遂行出来る様な原始既約多項式接続がなされたシフトレ
ジスター１が用いられている。第２図において第１図と
同一の記号のものは、全く同一の役割を果たすものであ
る。特に２のマイクロコンピュータの部分はその内部を
含めて全く第１図の場合と同一である。原始既約多項式
接続されたシフトレジスター１は、２つの原始既約多項
式接続される様になされている。以下この点について説
明する。11と12は、夫々排他論理和回路13,14,15は夫々
論理回路即ち、AND回路である。16は論理和回路即ちOR
回路、又、17は反転回路即ちインバータである。マイク
ロコンピュータ２の側から切換リード６に“1"の信号を
与えられると、反転回路17の出力は“0"となる。これに
よって論理積回路15はX4の信号を適さない、しかも出力
は“0"の状態となるので、排他論理和回路12はX0＝１の
出力が“1"なるか“0"なるかに伴なって、そのまゝX1に
加えられる状態となる。即ち有っても無いと同じ状態の
12になる。このとき論理積回路13と14は、夫々X3の出力
をX4に通じる様に開らき、またX4の出力であるX5信号
は、排他論理和回路11に加えられる状態となる。11の出
力を受けるところはX2になっている。また、14の出力は
（X5信号）は論理和回路16を通じてX0＝１に加えられる
様になる。従って、X5＋X2＋１なる接続になる。これは
GF（25）における第１次の原始既約多項式接続状態であ
る。
つぎに、マイクロコンピュータ２の側から切換リード６
に“0"の信号を加えると、論理積回路13と14は閉ぢる。
従って、X3からX4へ信号が送られることは無くなる。ま
た、14の出力は“0"となるので排他論理和回路11は有っ
て無きものの様にX1の出力をそのまゝX2え伝える。更に
反転回路17の出力は“1"となるので論理積回路15はX3の
出力であるX4信号を排他論理和回路12に加える。また15
の出力は論理和回路16を通じてX4信号をX0＝１に加える
ような状態となる。この接続状態はX4＋Ｘ＋１であるか
ら第１図の場合と同じGF（24）の第１次の原始既約多項
式接続された状態が得られる。以上を総合すれば切換リ
ード６に“1"を加えればｍ＝５に“0"を加えればｍ＝４
に切換えられる。この様にｍの値を切換える能力を備え
た原始既約多項式接続されたシフトレジスター１を備え
た第２図によればGF（25）の元の乗算とGF（24）の元の
乗算をなし得ることは、第１図の説明に照らして明白で
ある。
に“0"の信号を加えると、論理積回路13と14は閉ぢる。
従って、X3からX4へ信号が送られることは無くなる。ま
た、14の出力は“0"となるので排他論理和回路11は有っ
て無きものの様にX1の出力をそのまゝX2え伝える。更に
反転回路17の出力は“1"となるので論理積回路15はX3の
出力であるX4信号を排他論理和回路12に加える。また15
の出力は論理和回路16を通じてX4信号をX0＝１に加える
ような状態となる。この接続状態はX4＋Ｘ＋１であるか
ら第１図の場合と同じGF（24）の第１次の原始既約多項
式接続された状態が得られる。以上を総合すれば切換リ
ード６に“1"を加えればｍ＝５に“0"を加えればｍ＝４
に切換えられる。この様にｍの値を切換える能力を備え
た原始既約多項式接続されたシフトレジスター１を備え
た第２図によればGF（25）の元の乗算とGF（24）の元の
乗算をなし得ることは、第１図の説明に照らして明白で
ある。
以上述べたごとく、本発明を基本として、原始既約多項
式を求めるような複雑な算出過程を経る様な場合に著る
しい高速算出効果の得られるものであって、ｍの値が30
前後従って、原始既約多項式の総数20,000,000ケもある
様な場合の計算において、その何れを算出するにも２〜
３秒にて結果が得られる多大の効果を挙げ得た。従って
この手法が実時間処理として応用出来る分野を開拓する
ものである。この様な多大な効果を挙げるに僅少な外付
回路で済むことは、もたらす経済効果も多大である。
式を求めるような複雑な算出過程を経る様な場合に著る
しい高速算出効果の得られるものであって、ｍの値が30
前後従って、原始既約多項式の総数20,000,000ケもある
様な場合の計算において、その何れを算出するにも２〜
３秒にて結果が得られる多大の効果を挙げ得た。従って
この手法が実時間処理として応用出来る分野を開拓する
ものである。この様な多大な効果を挙げるに僅少な外付
回路で済むことは、もたらす経済効果も多大である。
また他の応用分野として誤り訂正符号の作成、処理の能
力も持っている。この様な分野では、GF（2m）の割り算
器が欠かせないが、べき数2m−１は０なので例えば、α
ｓで割ると云うことは、α-sを掛けることを意味するか
ら を求めて乗算することにて除算も可能となる。従って、
本発明がもたらす技術分野の開拓と、経済効果は多大で
あると信ずる。
力も持っている。この様な分野では、GF（2m）の割り算
器が欠かせないが、べき数2m−１は０なので例えば、α
ｓで割ると云うことは、α-sを掛けることを意味するか
ら を求めて乗算することにて除算も可能となる。従って、
本発明がもたらす技術分野の開拓と、経済効果は多大で
あると信ずる。
第１図、第２図は本発明の実施例のブロック図、第３図
はGF（24）のガロア体の表を示す図である。 １……原始既約多項式接続されたシフトレジスタ、２…
…マイクロコンピュータ、３……書き込みリード、４…
…リード（クロック用）、５……読み出しリード、６…
…切換リード、11,12……排他論理和回路、13,14,15…
…論理積回路、16……論理和回路、17……反転回路、21
……被乗数レジスタ領域、22……乗数レジスタ領域、23
……結果レジスタ領域、CPU……マイクロプロセッサ
ー、RAM……ランダムアクセスメモリー、ROM……読み出
し専用メモリー。
はGF（24）のガロア体の表を示す図である。 １……原始既約多項式接続されたシフトレジスタ、２…
…マイクロコンピュータ、３……書き込みリード、４…
…リード（クロック用）、５……読み出しリード、６…
…切換リード、11,12……排他論理和回路、13,14,15…
…論理積回路、16……論理和回路、17……反転回路、21
……被乗数レジスタ領域、22……乗数レジスタ領域、23
……結果レジスタ領域、CPU……マイクロプロセッサ
ー、RAM……ランダムアクセスメモリー、ROM……読み出
し専用メモリー。
───────────────────────────────────────────────────── フロントページの続き (72)発明者 本間 孝道 神奈川県大和市上草柳350番地 日本電気 無線電子株式会社内 (72)発明者 青木 正次 神奈川県大和市上草柳350番地 日本電気 無線電子株式会社内 (72)発明者 常富 博司 神奈川県大和市上草柳350番地 日本電気 無線電子株式会社内 審査官 武井 袈裟彦
Claims (1)
- 【請求項１】GF（2m）のガロア体における原始既約多項
式接続されたシフトレジスターと、マイクロプロセッサ
ーを備え、マイクロプロセッサーに従属するRAMに多項
式の係数表示された被乗数の元および乗数の元を格納す
るレジスター領域を備え、更に演算結果を格納するレジ
スター領域を備える。又マイクロプロセッサーに従属す
るROMの領域を備え、先づ被乗数の元を原始既約多項式
接続されたシフトレジスターに書き込む。つぎに乗数の
元の最下位桁の１ビットが“0"であれば結果レジスター
は全ビット“0"のまゝにし、“1"であれば原始既約多項
式接続されたシフトレジスタの内容を其のまゝ結果レジ
スターに全ビット取り込み転記し、乗数の元を格納した
乗数レジスターを最下位の方へ１ビットシフトさせると
共に原始既約多項式接続されたシフトレジスターを最上
位の方へ向って１ビットシフトさせ、乗数レジスター内
容の新らたな最下位ビット（即ち、もとの乗数元の最下
位より１ビット分上位のビット）が“0"であるなら其の
まゝ“1"であるなら新らたな原始既約多項式接続された
シフトレジスターの内容を取り込み、結果レジスターの
内容と全ｍビットに就いてビット毎の排他論理和を求め
新らたに結果レジスターの内容として格納し、以下順次
乗数レジスターを下位の方へシフトさせると共に原始既
約多項式接続されたシフトレジスターを上位の方にシフ
トさせつゝ其の都度新らたな乗数レジスタの最下位ビッ
トが“1"なるか“0"なるかによって同様に取扱って結果
レジスターを更新し、（ｍ−１）回のシフトを行なわせ
た後の結果レジスターの内容が求める乗算結果となるよ
う命令が書き込まれている前記ROM領域を備えて成る、G
F（2m）ガロア体に属する元の乗算装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP62056339A JPH0724016B2 (ja) | 1987-03-10 | 1987-03-10 | ＧＦ（２▲上ｍ▼）のガロア体に属する元の乗算装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP62056339A JPH0724016B2 (ja) | 1987-03-10 | 1987-03-10 | ＧＦ（２▲上ｍ▼）のガロア体に属する元の乗算装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS63221426A JPS63221426A (ja) | 1988-09-14 |
| JPH0724016B2 true JPH0724016B2 (ja) | 1995-03-15 |
Family
ID=13024459
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP62056339A Expired - Lifetime JPH0724016B2 (ja) | 1987-03-10 | 1987-03-10 | ＧＦ（２▲上ｍ▼）のガロア体に属する元の乗算装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0724016B2 (ja) |
Families Citing this family (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO1999016175A1 (fr) * | 1997-09-24 | 1999-04-01 | Hitachi, Ltd. | Circuit integre a semi-conducteurs et systeme de traitement de donnees |
| JP4472808B2 (ja) * | 1999-08-19 | 2010-06-02 | ネッツエスアイ東洋株式会社 | 積和演算装置及びこれを用いた暗号・復号装置 |
| JP4484002B2 (ja) * | 1999-10-04 | 2010-06-16 | ネッツエスアイ東洋株式会社 | 演算プロセッサ |
| JP5101253B2 (ja) * | 2007-11-15 | 2012-12-19 | アンリツ株式会社 | ランダムエラー発生装置、ｍ系列発生回路及びその設計方法 |
-
1987
- 1987-03-10 JP JP62056339A patent/JPH0724016B2/ja not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JPS63221426A (ja) | 1988-09-14 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Berlekamp | Bit-serial Reed- Solomon encoders | |
| EP2283417B1 (en) | Implementation of arbitrary galois field arithmetic on a programmable processor | |
| EP0080528A1 (en) | Computational method and apparatus for finite field arithmetic | |
| JP2000124813A (ja) | リードソロモン符号化装置およびその方法とリードソロモン復号装置およびその方法 | |
| US7296049B2 (en) | Fast multiplication circuits | |
| US6917218B2 (en) | Serial finite field multiplier | |
| US5777916A (en) | Method for the production of an error correction parameter associated with the implementation of modular operations according to the montgomery method | |
| US6609142B1 (en) | Method of performing multiplication with accumulation in a Galois body | |
| US5825681A (en) | Divider/multiplier circuit having high precision mode | |
| US7574469B2 (en) | Method for generating the multiplicative inverse in a finite field GF(p) | |
| US5912904A (en) | Method for the production of an error correction parameter associated with the implementation of modular operations according to the Montgomery method | |
| JP2000503146A (ja) | 整数除算回路を有するモジュラ算術演算コプロセッサ | |
| US6470372B1 (en) | Method for the performance of an integer division | |
| JPS63221426A (ja) | ＧＦ（２▲上ｍ▼）のガロア体に属する元の乗算装置 | |
| US4276608A (en) | Fibonacci p-code parallel adder | |
| JP3913921B2 (ja) | 有限フィールドでの任意要素の逆数具現回路 | |
| EP0584864B1 (en) | A hardware-efficient method and device for encoding BCH codes and in particular Reed-Solomon codes | |
| JPH06230991A (ja) | 有限体での任意元素の逆数算出方法及び装置 | |
| JPH0731593B2 (ja) | ＧＦ（２▲上ｍ▼）のガロア体の原始根のべき乗演算装置 | |
| JP3850512B2 (ja) | リードソロモン復号装置 | |
| JP3210420B2 (ja) | 整数上の乗算回路 | |
| US6275837B1 (en) | Method for the implementation of an elementary modular operation according to the Montgomery method | |
| US6578062B1 (en) | Method and circuit for digital division | |
| KR100265358B1 (ko) | 고속의쉬프팅장치 | |
| JP2914813B2 (ja) | 誤り訂正復号装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| S533 | Written request for registration of change of name |
Free format text: JAPANESE INTERMEDIATE CODE: R313533 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| EXPY | Cancellation because of completion of term |