JPH02148225A

JPH02148225A - 有限体の乗法的逆数元を計算するデータ処理方法及び装置

Info

Publication number: JPH02148225A
Application number: JP1269241A
Authority: JP
Inventors: Hendrik D L Hollmann; ヘンドリック　ディルク　ローデウィエイク　ホールマン
Original assignee: Philips Gloeilampenfabrieken NV
Current assignee: Koninklijke Philips NV
Priority date: 1988-10-18
Filing date: 1989-10-18
Publication date: 1990-06-07
Anticipated expiration: 2013-04-28
Also published as: EP0364627A1; KR900006851A; EP0364627B1; DE3855497T2; DE3855497D1; JP2744091B2; KR100202206B1; US4989171A

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】（産業上の利用分野）本発明はガロア体元ＧＦ（ｑ″′）をベクトル表現で供
給する際このガロア体元の乗法逆数を４算する方法、特
にデータ処理方法に関するものである。

（従来の技術）上記ガロア体元ＧＦ（ｑ’　）のｑは指数乗された素数
であり、通常絶対的ではないがＱ＝２’＝２とする。多
くの用途に対し、ｍは偶数とし、しばしばｍ＝８とする
。従って、かかる計算は、リードソロモン符号、高速フ
ーリエ変換等による如き、暗号、誤り防護の目的のバイ
ト状データ処理を表わす。従って、このデータは、“°
コンパクトディスクパ又は“ディジタルオーディオテー
ブパ記録サンプルを２バイト又は測定結果により構成す
るビデオデータ又はオーディオデータに相当する。この
種の方法の文献としては米国特許第４５７８６２７号明
細書がある。

（発明が解決しようとする課題）以下ガロア体における基本的特性及び計算演算は通常既
知であるものとする。一般に、任意のガロア体元は、２
８の種々の可能な入力組合せの各々に対して８ピント出
力が必要であるものとする限りではＧ１７（２８）のよ
うな相当な体に対してハードウェアの著しく拡大された
量を必要とする変換テーブル（ＰＲＯＭ又はＲＯＭ）に
よって反転させることができる。例えばプログラムされ
たプロセッサを用いる他の方法は、大きなパイプライン
処理、従って著しく計算遅延を必要とする。

本発明は部分体の概念を用い、特に主有限体の部分体の
逆数によって有限体、主有限体のへりトル表現された元
の乗法的逆数を計算する。この有限体ＧＦ（ｑ’　）に
は、ｍ＝ｒｎ（本発明では１例としてｒ＝２とする）の
場合に、部分体としてＧＦ（ｑ’）を含むようにする。

しかし、本発明の原理はｒを他の値に適用し得ることで
ある。部分体上の主有限体の指標をｒとする。主有限体
の部分体の関連する演算よりも少いベクトル係数で部分
体の計算を行う限りにおいては、部分体の計算は容易及
び／又は迅速となる。

本発明は縮小の１部分を成す二次形式を標準形式に有効
に組合せることにより部分体、特に指標２の部分体に逆
数を用いることにより制限されたハードウェアの要求で
迅速に作動する有限体で乗法的逆数元を計算するデータ
処理方法及び装置を提供することを目的とする。

（課題を解決するための手段）本発明は有限主体が部分体よりも二次的に大きな数の元
を含むように指標２の部分体を含む有限主体の入力元の
乗法的逆数を計算するに当り、ａ）第１集合のベクトル
成分（χ０ＩＸ１１−−−ＸＺ１１−１）、（ｎは有限
主体の大きさを示す）で表わされる入力元Ｘを受け、ｂ）この第１集合のベクトル成分から第２集合の一次形
式発生器（Ｘ）　（ここにｉ＝０．−−−−、ｎ−１、
及びｊ　＝　１　、−−−−、２ｎ）と、第３集合のマ
トリックス構成−火影弐Ｗ（、（χ）、（ここにβ−〇
。

２、、−＋　、　　ｋ＝ｏ−−−−、ｎ　　１　）とを
これら成分の選択排他的Ｏｆ？処理によって発生し、Ｃ
）第３集合の二次形式を発生する体状乗算によって前記
第２集合の元を対状に組合せると共に排他的ＯＲ処理に
よりかかる二次形式を組合せて］１訂記部分体の関連す
る他のベクトル係数Ｇｏ（Ｘ）、−し−１（×）を表わ
すものとして第４集合の二次形式を発生させ、ｄ）前記部分体において前記他のベクトル係数により表
わされる部分ベクトルを逆数部分ベクトルに変換し、ｅ）前記逆数部分ベクトルの元を前記第３集合の一次形
式の個別の元により乗算してこの乗算により得られた積
の加算と相俟って乗法逆数の成分を発生ずることを特徴
とする。

又、本発明はベクトル表現で受信された主ガロア体の入
力元の乗法的逆数を計算する装置に関するものである。

斯る装置によって“コンパクトディスク゛′デコーダそ
の他データ処理装置のナブシステムを表わすことができ
る。

本発明装置は、指標２の部分体を含み、前記有限主体の
大きさ２ｎが前記部分体よりも二次的に大きな数の元を
含み、前記入力元からその乗法逆数光を計算する主有限
体の入力元を受信する装置において、ａ）ベクトル表現（Ｘｏ、−−−−９Ｘｚ、、−１）　
（Ｄ入力元を受信する入力端子（２０）と、ｂ）この入力端子により供給されベクトル表現に基き、
２進−人形式り、（Ｘ）　　（ｉ　＝Ｏ。

ｎ−１及びｊ　＝　１　、−−−−、２ｎ）の第１アレ
イを第１出力端子（２４）に発生ずると共に２進−人形
式ＩＱｎ−　ｋ　（Ｘ）の第２マトリンクスアレイを第
２出力端子（２６）に発生する一次形式発生器（２２）
と、Ｃ）前記第１出力端子により供給され、体乗法で前
記第１アレイの元を合成アレイに対状に組合せると共に
この合成アレイを排他的ＯＲ処理して前記部分体におい
て第２ベクトル表現された二次形式〇Ｇ（Ｘ）、　−−
−−、Ｑｎ−１（Ｘ）の第３アレイを発生する二次形式
発生器（２８）と、ｄ）この二次形式発生器により供給され、前記第２ベク
トル表現の二次形式の第３アレイを受けてこれを前記部
分体で逆数部分ベクトルに反転する反転器（３０）と、ｅ）この反転器により供給される逆数部分ベクトルを受
けると共に前記一次形式発生器の第２出力端子により供
給される第２マトリ・ンクスアレイを受けて前記逆数部
分ベクトルの成分を前記−人形式の第３集合の路光で乗
算し、且つ前記乗算逆数の前記乗算成分により得られた
積と加算して前記乗法逆数の元を発生するマトリックス
エハリュエータ（３２）とを具えることを特（牧とする
。

（実施例）以下、本発明を先ずはその数学的見地について、ついで
順次の演算課程及びハードウェア回路について、最後に
図面を参照して特定例について詳細に説明する。

木λ班■歎ネ町長戎囮筒車なために、本発明を有限体ＧＦ（２″）（ここにｍ
＝２ｎ）について説明する。この場合にはｑ−３によっ
てビットの代りに３値元となり、これらの元は原則とし
て従来の論理回路によって実現することができる。有限
主体ＧＦ（２’″）はｍ＝８の場合に例えば生成多項式
ｇ（Ｘ）＝Ｘ’＋Ｘ４＋−Ｘ３＋Ｘ２＋　１を有する。

この多項式の元は標準基数（１，ｄ−ｄ７）に対して表
わされ、ｇ（ｄ）　＝　Ｏの解によって与えられる。本
発明の出発点は弐、即ちｘ−１−（Ｘ２−１）　−１、
ｙ、Ｚ　　を用いてＸ−Ｘ−’４．：よりＧＦ（２’″
）にて求めた元Ｘの乗法逆数九Ｘ−１を計算することに
ある。なお、−Ｌ式の（）内は部分体の元であるが、Ｘ
はを限主体の元である。

ＣＦ（２’　）からＧＦ（２）までのＧＩ’（２″）に
わたる−火影代置Ｘ）の関数をＬ（Ｘ）　＝Ｌｏ　・Ｘ
ｏ　＋Ｌ＋　・Ｌ　＋＋Ｌ、、　　・Ｘ１１１−１　と
規定する。ここに規定したような一次形式はＸのベクト
ル表現の選択係数のモジュロ２加算値である。ＧＦ（２
′′）〜ＧＦ（２）までのＧＦ　（２’″）における二
次形式０（×）はつぎのような関数として規定される。

即ち、Ｑ（Ｘ）＝Σ　Ｃｉ　　−Ｘｉ＋Σ　ａｉ　　−Ｘｉ・
ＸｊここにＣｉ、　ａｉｊ　Ｅ　ＧＦ（２）である。な
お、−Ｅ−は「成る元Ｊを意味する。従って、上述した
ように規定される二次形式はＸのベクトル表現の選択係
数と、選択したＡＮＤεＤ係数対とのモジュロ２加算値
である。概略同じような方法で高次形式を規定すること
ができる。

ｚ＃＋１そこで、Ｌ（Ｘ）＝Ｘ２　　及びＱ（Ｘ）＝Ｘ　　　　
（ここにＸ　Ｅ　ＧＦ（２”ｔ″）　テある）に対する
Ｌ　（Ｘ）は、成る標準化協定に従って固定化した標準
基数を必要としないＧＦ（２’　）における成る基数に
対しＬ（Ｘ）−（Ｌ、（Ｘ）、　−−−−ｔ、、−＋（
ｘ））として書き表わすことができる。ここに、各係数
Ｌ　ｉ　（Ｘ）は−成形式である。実際上、Ｘ、　ＹＥ
　ＧＦ（２’　）　ニ対してはＸＹ　＋　ＸＹ　−〇で
あり、又（ＸｔＹ）”−Ｘ２−＋Ｙ”″であるため、（
ＸｔＹ）”　＝Ｘ２＋２ＸＹ　＋Ｙ”＝Ｘ”＋Ｙ”テあ
る。従ッテ、Ｘからしく×）までの遷移部は一次演算と
なり、各Ｌｉ（Ｘ）は−成形式である。

そコテ、Ｘ　Ｅ　ＧＦ（２”）　ニ対して、Ｑ　（Ｘ）
はＧＦ　（２’）内にある。実際上、ＧＦ（２″′）の
成分ＸはＸ”　　＝Ｘを満足する。さらに、ＧＦ（２’
　）　−ＧＦ（２″′）の元ＹはＹ２　＝Ｙを満足する
元そのものである。ところで、（Ｑ　（×）　）　”　
′＝　Ｘ　ｚ　！″＋　２″′＝Ｘ　２　ＪＦ″−Ｘ”
’＝Ｘ　　−Ｘ”’−Ｑ（Ｘ）テある。ＧＦ（２’　）
　　ニおける基数す、、　ｂｂ、、−１ニ対するＱ　（
Ｘ）はｑ（ｘ）＝（Ｏｏ（ｘ）、　Ｑｌ（Ｘ）。

［１，、−、（Ｘ））と書き表わすことができ、これか
ら係数の値に影響を及ぼす基数を選定する９この場合の各係数ＱＪ（Ｘ）は二次形式のものである。

実際上、Ｂ（Ｘ、Ｙ）　−〇（ＸｔＹ）　十〇（Ｘ）　
＋Ｑ（Ｙ）に対する係数はＢ（Ｘ、Ｙ）＝（Ｘ”　＋Ｙ
２）（Ｘ−１−Ｙ）　）−Ｘ”　’＋−Ｙ２゛’−Ｘ−
・Ｙ−ｔ−Ｘ・Ｙ２＝Ｌ（Ｘ）−Ｙ−１−Ｘ−Ｌ（Ｙ）
となるため、Ｂ　（Ｘ　、　Ｙ）は正に双線形演算を規
定する。

このことはＱＪ（Ｘ）についての先の説明を立証間する
ことになる。

び二　　　Ｌ（Ｘ）、　Ｑｂ（Ｘ）の　　の・めＧＦ（
２’　）における所定の基数α０−−−一α１−１及び
ＣＩ？（２’　）における基数β。−一−−β。−１に
対する先に述べた一次形式り、　（Ｘ）、　ｉ　＝　Ｏ
−−−−ｍ　−１及び二次形式〇ｉ　（Ｘ）　、Ｊ　＝
　Ｏ−−−−ｎ　　１の表現を計算するには簡単な方法
がある。従って、このような計算はコンピュータプログ
ラムによって自動的に行なうことができる。

全てのｉ、ｊに対し、αム　・α、′十α、１〜α、Ｅ
　ＧＦ（２°）；α、″”Ｅ　ＧＦ（２°）：α、ｚ　
Ｅ　ＧＦ（２’）となる。これに対して、全てのｌ、ｊ
に対する所定数Ｃｉｊ＋ｂｉｊ＋ａｉ、ｋ　Ｅ　ＧＦ（
２）に対しては、　、、ｈる。これがためつぎのように
なる。

及びＱ（Ｘ）＝Ｘ”　”＝　（ΣＸ、　−ａｉ）２”この結
果としてつぎのようになる。

Ｌ、　　（Ｘ）　　＝＝Σ　Ｃｚｊ−Ｘｔ（ｊ＝０ｍ−
１）Ｑｎ−　（Ｘ）　＝、Ｘ　ｂｔ＋＋　’　Ｘ１＋　Σａ
＝ｉｈ　’　Ｌ　’　Ｌ（ｋ＝ｏ、−−−−ｎ−１）上式からして、そのように規定される二次形式はより一
層取扱い易い表現で書き表わすことができる。この際、
Ｍ（Ｘ、Ｙ）を考察するに、これは（Ｘ２６・ｙ）とし
て規定され、ここにＸ　Ｅ　ＧＦ（２’　）及びＹεＧ
Ｆ（２’″）である。又、×２　−ΣＬ、　（Ｘ）α、
；１、Ｊ（Ｘ）　　−Σ（ｌ　ｉｊ・Ｘ　。

；　Ｙ＝ΣＹ　ｋ　・　β。

である。従ッテ、Ｍ（Ｘ、Ｙ）−ΣΣし、（Ｘ）　　−
Ｙ、α。

・βアとなり、α４　・β、−Σｄ、ｋｆｆｉ・α尼と
表わすことができる。従って、次式が成立する。

Ｍ（Ｘ、Ｙ）＝ΣΣΣ　ｌ−＝　　（Ｘ）　・Ｙｋ’ｄ
　ｊｋｃ　’　αｎ＝、”Ｆ、−、’ａ１．　（：）１
．’Ｙ、　−：’ｉ：、Ｊ、Ｘ；　（、Ｔ：ｒ、−、Ｃ
＝、ａ、ｅ）Ｗ、ｈ　（Ｘ） −ｙ」、・Ｖ−さ、、・　ｄ、、　ｆｆｉとすると、Ｌ
　ｋ（Ｘ）がＧＦ（２″）全体にて一次形式となること
を証明することができる。従って、Ｍ（Ｘ、Ｙ）は成分
（０−−−−ｍ　−１）　、即ちΣｙｋ−ｗｔ１、（ｘ
）　　（ｐ−一〇、１．−−−−ｍ−１）を有する。こ
の際、ＧＦ（２′″）からＧＦ（２）までの関数しくＸ
）は、１、（Ｘ）そのものか、又は１＋Ｌ（Ｘ）が一次
形式のものである場合には本来−次関数であると称する
。従って、っぎのようなことが成立することがわかる。

ＣＦ　（２″′）における二次形式とすべき０（×）に
対しては、このＱ（Ｘ）に必要とされるような一次形式
の必要数２ｋをＧＦ（２″′）におけるＱ（Ｘ）のＯの
数だけで決定する場合のＱ（Ｘ）＝Ｌｌ（Ｘ）　　・Ｌ２（Ｘ）　＋ｔ、ｚ（Ｘ
）　　・Ｌｉ（Ｘ）　　＋−−−−−１−Ｌｚｍ−＋（
Ｘ）　　・Ｌｚｋ　（Ｘ）、又はＬ　Ｉ　（Ｘ）−−−
−１、ｚｈ　　（Ｘ）　）　　ｌのような本来一次形式
Ｌｉ　（Ｘ）を求めることができる。二次形式〇、（Ｘ
）の数は１＋（２°＋１）（２°−’−１）に等しくな
り、しかもその数は実際に用いるＧＦ（２”　）におけ
る基数（α、）及びＧＦ（２”）における基数（βｊ）
に無関係であることを確かめた。実際上、このようなＯ
はｘ　２　’　１　　２　Ｉ　の場＝ｙ合に生成され、この場合にはＸ＝Ｙ＝Ｏか、又は２″中
１（Ｘ／Ｙ）　　　　＝　１　ノイずれかである。ＣＦ　
（２°）における原始光をαとする場合には、式ｚ２−
１　＝　ｌはｊ＝ｏ、−−−−２”に対して確実に２ｎ
＋１個の解Ｊ−ｃｘ”　−’ンを有する。従ッテ、Ｇ（
Ｘ）＝Ｘ”　’はＯの２′″″１倍正確に異なる各値を
とる。

Ｑ（Ｘ）Ｅ　ＧＦ（２°）であるため、Ｇｆ’（２２）
は２２　　個の元を有し、又ＧＦ（２”）　　は２７個
の元を有し、Ｑ　（Ｘ）は０の２ｎ＋１倍確実に異なる
ＧＦ（２″）における各値をとり、−旦は正確に値ＯＪ
なる。そこで、ＹがＧＦ（２’　）の全ての元に及ぶ場
合には成る固定の基数に対するＹの各係数は対称性の理
由からして、事例の数の半分は確実に０となる。従って
、ＧＦ　（２’）における全ての非ゼロ元のいずれの特
定係数も確実に０の２’−’−１倍となる。

二次形式Ｑｆ　（Ｘ）の表現に必要な本質的な一次形式
の数２にはＧＦ（２’　）上の１つの二次形式Ｑ　（Ｘ
）内の零の数、即ち１　＋　（２’＋１）　＋　（２”
−１）により決まる。これがため本質的な一次形式は次
の如き二次形式を与える。Ｑｉ　（Ｘ）　＝　Ｌｉ　、
　１（χ）・　Ｌｉ　＋２（Ｘ）＋−−−−＋　　Ｌｉ
　　、　　２ｎ−＋（Ｘ）　　・ｌ、ｔ　　、　　２ｎ
（Ｘ）の−　として八　　　れた　−の以上に従って、乗法逆数は次のように計算する。

ｘ−ｎ＝ｘＺ％＋１．Ｘ２’ ここに、Ｌ（Ｘ）　＝Ｘ”　Ｅ　ＧＦ　（２″′）Ｑ（
Ｘ）＝Ｘ”　　”ＩＥ　ＧＦ　　（２’　　）最初に、
２つの基数、即ちＧＦ（２″′＞：αＯ＋　　αｈ−−−−α２ｎ−１Ｇ
Ｆ（２”）：β。、　βｈ−−−−β口を選択する。特
に、第２の基数の選択は任意である。第１の基数で表わ
すと、Ｌ（Ｘ）　＝　（（ＬＯ（Ｘ）、−Ｌｚ、、−＋
（Ｘ））になり、ここで係数は一次形式であるが、明確
に計算されない。更に、Ｑ　（Ｘ）　＝　（ＱＯ（Ｘ）
　。

０．１（Ｘ））になり、ここで係数は二次形式である。

基数は第２ガロア体に対し自由に選択することができる
点に注意されたい。

今、第１の目的は部分体ＧＦ（２’　）内のＱ（×）の
逆数であるｌ？（Ｘ）＝（１７０（Ｘ）、−−−−、Ｉ
’１．１（Ｘ））を計算することにある。この場合には
次の積を計算する。

Ｌ　（Ｘ）・Ｒ（Ｘ）− らは特に計算する必要のある一次形式である。

要するに、求めるべき逆数量の第に成分はで与えられる
。ここでＪ　（Ｘ）（ｊ）から口ｊ（Ｘ）　（ｊ）を発
生させる必要がある。前述したところから、であること
明らかである。ここにおいて、ＩＬ、は−成形式である
。次に、次の量を発生させる必要がある。

ｓ　＝　０−−−−２ｎ−Ｉｔ　ｊ＝　Ｏ−−−−ｎ　
　ｌに対するＬｊＳ（Ｘ）ｋ　＝　Ｏ−−−−２，−１
，ｊ　＝　Ｏ−−−−ｎ　　１に対するＷｊｋ（Ｘ）後
記の実施例に示すように、これらの計算の所定の部分を
結合することができる。次に、量Ｑｎ−（Ｘ）を形成し
、これと−緒にｆｉＱ（ｘ）を発生させる。

斯る後に、Ｑ（Ｘ）の逆数（Ｒ（Ｘ）と称す）を部分体
内でその係数Ｒ４（Ｘ）を用いて計算する。この計算は
一般に古典的方法で行なわれる。或は又、逆数の部分体
を二次部分体内の他の逆数に分割することができる。最
後に、主体内の逆数の係数はＸ−’にの表示により与え
られる。

仝ニエ差１７（２リロ１１誠ｊ第１図は本発明装置の基本ブロック図である。

第ルベルでは種々のサブシステムがブロックとして示さ
れているにすぎない。これらのサブシステムは、旧Ｆｌ
オーディオコンパクトディスクシステムに対し定義され
ている、クロスインターリーブリードソロモン符号に基
づく誤り訂正を行なう単一ガロア体を超高速演算するハ
ードウェアロジックとしても、或いは他の信号処理用の
ハードウェアロジックとしても実現することができる。

或は又、種々のブロックを８ピントマイクロプロセン゛
す゛のような一般に応用し得るプロセッサブロックのプ
ログラム制御によって実現することができる。後者の場
合には複数の機能の間で種々のブロックの時分割使用を
実行し、チップ面積を減少させることができると共に、
他の利点も得ることができる。処理能力対演算速度は矛
盾すると考えられること勿論である。後者の実現法は更
に主体内の直接逆数に必要とされる長いパイプライン方
式に改善を示す。更に、単一主ガロア体のみにおける演
算に対するあからさまな制限が存在せず、種々の体の交
換及び／又は対応する体に対する種々の基数の交換を完
全に実行することができる。簡単のために、斯る標準構
成ブロックのこれ以上の説明は省略する。

さて、第１図の回路において、入力端子２０は２ｎビッ
トの入力量を並列に搬送する。ブロック２２において一
次形式Ｌｊｊ　（ｘ）及びｕ、　、　（Ｘ）の計算が行
なわれ、２ｎ２個の一次形式を発生する。ワイルドロジ
ックの場合には、装置のゲート深さを最大で（１モＫ）
とする（ここでＫ　＝２１ｏｇｎ又はその次の整数）。

従ってコンパクトディスクに対してはに＝３である。以
上ではｉＬ及びＷの計算を結合する効果は考えてない。

−成形式り、Ｊ（Ｘ）はブロック２４に至る相互接続ラ
イン２４に出力され、−成形式Ｗｔ　ｋ　（ｘ）はブロ
ック３２へと直接至る相互接続ライン２６に出力される
。相互接続ライン２４．２６のピント幅は明示してない
。

ブロック２８において、−吹膨弐がペアに組合わされ、
加算されてｌ　Ｑｉ　（Ｘ）を発生しくここでｉ−〇−
−−−ｎ　−１）　、すべての加算はモジュロ２加算で
実行される。これは１＋にのロジックゲート深さに対し
全部でｎｔのＡＮＤ演算とｎ　（ｎ−１）のＸＯＲ演算
を必要とする。その結果はｎビット幅量としてブロック
３０に出力される。

ブロック３０において逆数量Ｒ（Ｘ）　＝Ｑ（Ｘ）−’
が部分体ＧＦ（２″）内で、例えばプログラムドテーブ
ルメモリを用いて計算される。その結果はｎビット幅量
としてブロック３２に出力される。

ブロック３２は部分体内の逆数を受信すると共に一吹膨
弐−Ｌｋ（×）も受信して次式：％式％（）を計算する（ここでｎ＝ｏ−−−−２゜−２）。この演
算は（Ｋ４−１）の総合ロジックゲート深さに対して全
部で２１２のＡＮＤ演算と２ｎ　（ｎ−１）のＸＯＲ演
算を必要とする。従ってＸＯＲ演算の総数は８ｎ　３　
　ｎ　ｚ３ｎであり、これはｎの合理的な値（〉４）に
対しては約８ｎ３になる。更に３　ｎ　ＺのへＮＤ演算
の構造が著しく簡単であるためにかなり無視することが
できる。総合ロジックゲート深さは３＋３にである。

上述の変換の構造は固定することができるが、精密な実
現に関してはなおかなりの自由度がある。

主体内の基数が既に指定されている場合でも、次のオプ
ションが存在する。

ａ）ＧＦ（２’　）内の基数β。−−−一β１−３の選
択。この選択は一次形式Ｗｔｋｍ　、二次形式Ｑｉ　（
Ｘ’）及び従って一吹膨弐Ｌｉ、（Ｘ）に影響を与える
。

ｂ）　　ＧＦ（２’　）内の基数（β。−−ｍ−β７−
１）の選択を定めた後でも、本質的な一次形式の積とし
てのＱｉ（Ｘ）の表現、即ち一次形式Ｌｉｊ　（Ｘ）の
精密な公式化が選択のために開放されている。

特に、上述した第２の方法を選択するのが有利である。

多くの場合、一次形式Ｌ　ｉ　ｊ　（Ｘ）を選択し、各
々が（２ｎ個の代わりに）係数の多くともｎ個のみを含
むようにすることができる。この場合、論理深度が１だ
け減少され、Ｌｉ　、　（Ｘ）を計算するＸＯＲ演算の
回数が半分となる。更に、種々の中間結果を、量Ｌｉ　
ｊ　（ｘ）およびＸＯＲ演算を更に減少させる量ＷＬｋ
（Ｘ）の双方の計算に対しそれぞれの間で共有すること
ができる。実際にはＸＯＲ演算の回数は１・・・１　”
”）・ｎ３にする必要がある。双方の基数α及びβを自
由に選択しうる場合には、正ｊＡ基数を選択することが
提案される。この場合、逆数の係数の各々を計算するの
に同じハードウェアを用いることができる。またこの場
合ハードウェアの構造全体が一層規則的となる。或いは
また、逆数の係数を順次に計算しうる場合には、これら
係数の各々に対し同じハードウェアを順次に用いうる。

方法９ＪＪｍｌ’Ａ以下に一例としてＧＦ（２’）における逆数（ｍ−２ｎ
＝４　）を説明する。有限体ＧＦ（２’）はＧＦ（２）
に亘る既約多項式ｇ（Ｘ）　＝Ｘ’＋Ｘ＋ｌによって発
生させる。

αをｇ　（Ｘ）の形式的な零とすると、α４−α＋１と
なる。ＧＦ（２’）における基数として（１，α、α２
α３）を取る。この際、ＣＦ（２’）はＧＦ（２”）を
含む。実際Ｇｌ’（２”）の元は（０，１，α５．α１
０）として占き表わすことができる。ＧＦ（２”）にお
けるベースとして正規基数（αＳ、α１０）を選択する
。

この際、逆数とすべきベクトルはＸ　−（ＸｏｔＬＪｚ＋Ｌ）　−Ｘｏ＋　Ｘ、α＋Ｘ、
α”＋Ｘ−ａｒｘ”　Ｔ：ある。またＱ（Ｘ）　−Ｑｏ
（Ｘ）　ｉｒ’＋Ｑｎ−　（Ｘ）　α”と書く。これに
より今必要とする２つのみの二次形式に対する以下の式
が得られる。

Ｑｏ（Ｘ）＝Ｘｏ＋Ｘ＋＋Ｘ３＋ＸｏＸ＋＋ＸｏＸｚ＋
Ｘ１Ｘｚ＋ＸｌＸ３Ｑ＋　（Ｘ）＝Ｘ、＋Ｘ、＋Ｘ３＋
Ｘ、Ｌ　）ＸｏＬ＋ＸｏＸ３＋ｘ２Ｘ３ここで弐〇　（
Ｘ）・×２゛１　を用い、次にこの弐をその基数元に対
して解く。

この簡単な部分体では元ｙ、α５＋Ｙ２α１０の逆数を
直接Ｙ２α５＋Ｙ１α１０として書き表わすことができ
る為、Ｒ，（Ｘ）　＝ＱＯ（Ｘ）及びＲｏ　（Ｘ）　４
＋　（Ｘ）　となる。より大きな部分体では逆数自体が
表−Ｒ叶により一射的なものとなる。ここで形式Ｌ　ｗ
　（Ｘ）を計算すると、以下のものが得られる。

Ｘｏ−’、Ｒｏ　　・　（Ｘｚ）＋Ｒ，−（ＸＯ＋Ｘ１
４Ｘ３）Ｘｎ−’＝Ｉｌｏ　Ｈ（Ｘ０＋Ｘ１）＋ＲＩ・
（ＸＯ＋Ｘ３）×２−１”Ｒｏ　・（Ｘ（１４Ｘ２＋Ｘ
い＋Ｒ１’　（ＸＯ）Ｘ３”’＝Ｒｏ　・（Ｘ＋＋Ｘｚ
）＋ＲＩ・（Ｘ１＋Ｘｚ＋Ｌ）ｎｏ（Ｘ）、Ｑｉ（Ｘ）
に対する代りの式は以下の通りである。

Ｇｏ（Ｘ）＝１＋（Ｘｏ＋Ｘ１）　　値Ｘｚ）＋（ＸＯ
＋Ｌ）’　てＸｌ）Ｑｌ（Ｘ）＝１＋ｎ７■Ｄ・Ｔｌ賢
ｘｏ＋ｘ＊）　・（ＸＩ）Ｘ２）ここに、かっこ内の式
は実質的に一次形式を表わし、上側の横線は反転論理値
を表わす。部分用は数回用いられ、ａｌ、Ｘｏ＋Ｌ　　　ａ４＝ａ＋＋Ｘ３＝Ｘｏ＋Ｘ１＋
Ｘ３ａｚ＝Ｘ６＋Ｘｓ　　　ａ５・ａｚ＋Ｘｚ□Ｘｏ＋
Ｘｚ＋Ｘ３ａｚ＝ＸＩ＋Ｘｚ　　　ａｉ、＝ａｚ＋ｘ、
Ｊ＝Ｘｔ＋Ｘｚ＋Ｌによって共有しうる。

必要とするＥＸＯＲ−加算の回数は前に特定した上界よ
りも著しく少なくなる（４ｎ２（２ｎ−１）・４８）。

より大きな主体では、従ってより大きな関連の部分体で
は、計算により多くの■が含まれ、従って必要とするゲ
ートの入力端子が一層多くなり、論理深度も大きくなる
。すべてをひとまとめにして考えると、計算の原理は同
しであり、この計算は前述した一般的な処理に沿って行
なう。

好ｊｌ毎」片９説１明細書末尾に示す表ＩＡ〜ＩＥはコンパクトディスクガ
ロア体ＧＦ（２８）における逆数に対する好適実施例を
表で表わすものである。ゲートの標準の個数は４ｎ”（
２ｎ−１）・４４８個程度である。ゲートは３列で示し
である。第１列はゲートの名前を挙げており、この名前
はゲートの出力信号の名前としても用いられる。第２列
はゲートの機能を挙げている。第３列は関連のゲートの
入力信号を挙げている。表ＩＡの一番上の２行は入力ベ
クトルの８つの成分（Ｉ７〜１０）　　と、人力ベクト
ルの乗法逆数である出力ベクトルの８つの成分（Ｊ７〜
ＪＯ）とヲソれぞれ規定している。

３５個のＤ−ゲートは部分体における反転を行なう。

この反転はそれ自体で実際にテーブルルックアップに対
応する。この反転は人力信号として、後に説明する種々
のＣ信号を用い且つ反転アレイ自体で生ぜしめられる種
々の中間信号をも用いる。ゲートライブラリは本発明で
用いる以下の素子を有する。

ＱＮＯＲ２７２人力ＮＯＲゲートＱＮＡＮＤ２：２人力ＮＡＮＤゲートＱＩＮＩ　　：１人力インバータＱＩＮ２　　：大きなファンアウトを有する１人力イン
パ“−タＱＡＮＤ３　：３人力ＡＮＤゲートｆｌＮＯＲ３：３人力ＮＯＲゲートＱＡＮＤ４　：４人力ＡＮＤゲート０ＮＡＮＤ３：３人力ＮＡＮＤゲートＱＸＮＯＲ：２人力排他的ＮＯＲゲートＱＯＲ３：３人
力ＯＲゲートＱＩＮ３　４更に大きなファンアウトを有する１人力イ
ンバータ叶０６：４つの入力信号ａ１〜ａ４の列に対しくａｌ＋
ａｚ＋ａ３・ａｓ）として表現される第１特別関数ＱＦＯ８：５つの入力信号ａ、〜ａ、の列に対しくａｌ
＋８２・ａｌ＋　ａ、・ａ５）として表現される第２特
別関数ライブラリの他の素子は簡単には特定できない。

第１図のブロック２２では、種々の一次形式が計算され
る。この計算はゲートＮ４７から開始しゲートＢ２５６
　（或いはゲートＮ５）までのゲートの組によって行な
う。これらの−成形式は排他的ＯＲゲート、排他的ＮＯ
Ｒゲート及びインバータのみである。

ブロック２８では、二次形式が計算される。この計算は
ゲー）ＮＣＯＩから開始しゲートＣ３までのゲートの組
によって行われる。その後、必要とするベクトル成分Ｃ
Ｏ〜Ｃ３がブロック３０において処理準備完了状態とな
る。部分体における反転が行なわれてベクトル成分Ｄｏ
−０３を生ぜしめた後、ブロック３２において乗算が行
なわれる。この乗算はゲートＮＪＯＩから開始するゲー
トによって行なわれる。

合計のゲート数は以下の通りである。

ブロック２２ニア６ブロツク２８：　３２ブロック３０：　３５ブロック３２：　６４合計：２０７環−説前述した方法を以下に概説する。

最終結果はＸ”’にとすべきである。すなわち逆ベクト
ルのに番目の成分はとなる。ＲＪ　（Ｘ）　Ｕ＝０〜ロー１）を得るために
は、二次形式〇、　（Ｘ）　（ｊ・０〜ｎ−１）を計算
する必要があった。

この効果のために、を書いた。双方のＬは一次形式である。実際には一次形
式％式％を計算した。

口、　（Ｘ）は式（Ｂ）から得られ、これにより口（χ
）を得る。Ｊ（Ｘ）（ｊ＝ｏ　〜ｎ−１）　は０（×）
を反転させることより得られる。最後にＸ−’ｋを式（
八）から得る。

【図面の簡単な説明】

第１図は本発明装置の構成を示すブロック回路図である
。２０・・・入力端子２２・・・−吹膨弐発生器２４・・・第１出力端子２６・・・第２出力端子２８・・・二次形式発生器３０・・・反転器

Claims

【特許請求の範囲】１、有限主体が部分体よりも二次的に大きな数の元を含
むように指標２の部分体を含む有限主体の入力元の乗法
的逆数を計算するに当り、ａ）第１集合のベクトル成分
（Ｘ＿０、Ｘ＿１、−−−Ｘ＿２＿ｎ＿−＿１）、（ｎ
は有限主体の大きさを示す）で表わされる入力元Ｘを受
け、ｂ）この第１集合のベクトル成分から第２集合の一次形式Ｌ＿ｉ＿ｊ（Ｘ）（ここにｉ＝０、−−
−−、ｎ−１、及びｊ＝１、−−−−、２ｎ）と、第３
集合のマトリックス構成一次形式Ｗ＿ｌ＿ｋ（Ｘ）、（
ここにｌ＝０、２＿ｎ＿−＿１、ｋ＝０−−−−、ｎ−
１）とをこれら成分の選択排他的ＯＲ処理によって発生
し、ｃ）第３集合の二次形式を発生する体状乗算によって前記第２集合の元を対状に組合せると共に排
他的ＯＲ処理によりかかる二次形式を組合せて前記部分
体の関連する他のベクトル係数Ｑ＿０（Ｘ）、−−−−
、Ｑ＿ｎ＿−＿１（Ｘ）を表わすものとして第４集合の
二次形式を発生させ、ｄ）前記部分体において前記他のベクトル係数により表わされる部分ベクトルを逆数部分ベクトル
に変換し、ｅ）前記逆数部分ベクトルの元を前記第３集合の一次形式の個別の元により乗算してこの乗算によ
り得られた積の加算と相俟って乗法逆数の成分を発生す
ることを特徴とする有限主体の入力元の乗法的逆数を計
算する方法。２、指標２の部分体を含み、前記有限主体の大きさ２ｎ
が前記部分体よりも二次的に大きな数の元を含み、前記
入力元からその乗法逆数元を計算する主有限体の入力元
を受信する装置において、ａ）ベクトル表現（Ｘ＿０、−−−−、Ｘ＿２＿ｎ＿−
＿１）の入力元を受信する入力端子（２０）と、ｂ）この入力端子により供給されベクトル表現に基き、２進一次形式Ｌ＿ｉ＿ｊ（Ｘ）（ｉ＝０、
−−−−、ｎ−１及びｊ＝１、−−−−、２ｎ）の第１
アレイを第１出力端子（２４）に発生すると共に２進一
次形式Ｗ＿ｌ＿ｋ（Ｘ）の第２マトリックスアレイを第
２出力端子（２６）に発生する一次形式発生器（２２）
と、ｃ）前記第１出力端子により供給され、体乗法で前記第１アレイの元を合成アレイに対状に組合せ
ると共にこの合成アレイを排他的ＯＲ処理して前記部分
体において第２ベクトル表現された二次形式Ｑ＿０（Ｘ
）、−−−−、Ｑ＿ｎ＿−＿１（Ｘ）の第３アレイを発
生する二次形式発生器（２８）と、ｄ）この二次形式発
生器により供給され、前記第２ベクトル表現の二次形式の第３アレイを受けて
これを前記部分体で逆数部分ベクトルに反転する反転器
（３０）と、ｅ）この反転器により供給される逆数部分ベクトルを受けると共に前記一次形式発生器の第２出力
端子により供給される第２マトリックスアレイを受けて
前記逆数部分ベクトルの成分を前記一次形式の第３集合
の各元で乗算し、且つ前記乗算逆数の前記乗算成分によ
り得られた積と加算して前記乗法逆数の元を発生するマ
トリックスエバリュエータ（３２）とを具えることを特
徴とする主有限体の入力元を受信する装置。３、前記入力端子を２ｎビットの広さとし、前記マトリ
ックスエバリュエータの他の出力端子を２ｎビットの広
さとしたことを特徴とする請求項２に記載の装置。