(57)【要約】      （修正有）【課題】より小さく、より高速で、かつ、より効率的な複合ガロア体エンジンを提供する。【解決手段】ガロア体除算器エンジンおよび方法は、１および第１のガロア体の元をガロア体逆数生成器に入力して、出力を得て、ガロア体逆数生成器内で、第１のガロア体の元にガロア体逆数生成器の第１の元を掛けて、ｍ−２回（ここでｍはガロア体の次数である）で既約多項式の多項式積の二乗のモジュロ剰余を予測して、第１のガロア体の元の逆数を得て、かつ、ガロア体逆数エンジン内で、第１のガロア体の元の逆数に第２のガロア体の元を掛けて、既約多項式のための多項式積のモジュロ剰余を予測して、ｍ周期内で２つのガロア体の元の商を得る。より広い意味で、一連の多項式入力上で一連のガロア体線形変換を実行して、最終的な出力を得るための複合ガロア体エンジンを含んでいる。【選択図】図１
2010102351.tif 000002
【特許請求の範囲】
【請求項１】
一連のガロア体線形変換を実行するための複合ガロア体エンジンにおいて、各ガロア体線形変換は、既約ガロア体多項式のために、一連の多項式の中の１つの多項式のモジュロ剰余を予測して最終的な出力を得て、連続の中の各多項式のうち、最初のもの以外は、連続の中の直前の多項式のガロア体線形変換を実行することによって得られ、
連続の中で第１の多項式を供給するための入力回路と、
連続の中の第１の多項式に応じて、一変換動作中に、一連のガロア体線形変換のモジュロ剰余を予測するように構成された、セルのマトリックスを有するガロア体線形変換器とを備えていることを特徴とする複合ガロア体エンジン。
【請求項２】
２つの部分を有していて、各部分がセルのマトリックスを有している複合ガロア体線形変換器を備えている複合ガロア体エンジンにおいて、
変換器の第１の部分は、既約ガロア体多項式のために、多項式乗算器の出力のモジュロ剰余を予測し、
変換器の第２の部分は、既約ガロア体多項式のために、二乗器の出力のモジュロ剰余を予測する
ことを特徴とする複合ガロア体エンジン。
【請求項３】
第１の部分に対応するセルのマトリックスの部分は、単位マトリックスに対応することを特徴とする請求項２に記載の複合ガロア体エンジン。
【請求項４】
第２の部分に対応するセルのマトリックスの部分は、単位マトリックスに対応することを特徴とする請求項２に記載の複合ガロア体エンジン。
【請求項５】
第１の部分に対応するセルのマトリックスの部分は、単位マトリックスに対応し、かつ第２の部分に対応するセルのマトリックスの部分は、単位マトリックスに対応することを特徴とする請求項２に記載の複合ガロア体エンジン。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ガロア体除算器エンジンおよび方法に関し、より一般的には、一変換演算中に一連のガロア体変換を実行するための複合(compound)ガロア体エンジンに関する。
【０００２】
本出願は、Stein他によるA COMPACT GALOIS FIELD MULTIPLIERと題された２００２年１０月９日に出願された米国仮出願（ＡＤ−３３７Ｊ）、２００１年１１月３０日に出願されたStein他によるGF2-ALUと題された米国仮出願第６０／３３４，６６２号（ＡＤ−２３９Ｊ）、２００１年１１月２０日に出願されたStein他によるPARALLEL GALOIS FIELD MULTIPLIERと題された米国仮出願第６０／３３４，５１０号（ＡＤ−２４０Ｊ）、２００１年１２月１８日に出願されたStein他によるGALOIS FIELD MULTIPLY ADD (MPA) USING GF2-ALUと題された米国仮出願第６０／３４１，６３５号（ＡＤ−２９９Ｊ）、２００１年１２月１８日に出願されたStein他によるPROGRAMMABLE GF2-ALU LINEAR FEEDBACK SHIFT REGISTER-INCOMING DATA SELECTIONと題された米国仮出願第６０／３４１，７３７号（ＡＤ−３００Ｊ）の優先権を主張する。本出願は、更に、２００３年３月２４日に出願されたStein他によるCOMPACT GALOIS FIELD MULTIPLIER ENGINEと題された米国特許出願第１０／３９５，６２０号（ＡＤ−３３７Ｊ）、２００２年１月１８日に出願されたStein他によるGALOIS FIELD LINEAR TRANSFORMERERと題された米国特許出願第１０／０５１，５３３号（ＡＤ−２３９Ｊ）、２００２年１月３０日に出願されたStein他によるGALOIS FIELD MULTIPLIER SYSTEMと題された米国特許出願第１０／０６０，６９９号（ＡＤ−２４０Ｊ）、２００２年８月２６日に出願されたStein他によるGALOIS FIELD MULTIPLY/MULTIPLY-ADD/MULTIPLY ACCUMULATEと題された米国特許出願第１０／２２８，５２６号（ＡＤ−２９９Ｊ）、および２００２年５月１日に出願されたStein他によるRECONFIGURABLE INPUT GALOIS FIELD LINEAR TRANSFORMERER SYSTEMと題された米国特許出願第１０／１３６，１７０号（ＡＤ−３００Ｊ）の優先権を主張する。
【背景技術】
【０００３】
ある応用、例えば暗号化および誤り制御符号化において、算術演算、例えばガロア体上での加算、減算、平方根、乗算、および除算を実行する必要がある。ガロア体内の任意の２つの要素間の任意のこのような演算は、同じガロア体内の別の値である出力（和、差、平方根、積、商）に帰着する。ガロア体内の元の数は２ｍである。ここでｍは体の次数(degree)である。例えば、ＧＦ（２４）は、その中に１６個の異なる元を持っている。ＧＦ（２８）は２５６個持っている。ガロア体は、特定の累乗における既約多項式から生成される。特定の次数の各ガロア体は、多くの既約多項式の形式を持っていて、その各々は、同じ項を用いているが、異なる位数の異なる体を考え出すことができる。
【０００４】
ガロア体上の除算は、被除数に除数の逆数を掛けることによって行われる。この除数の逆数は、多くの方法で生成することができる。１つの方法は、逆数の格納されたルックアップテーブルを持つことであり、ここで除数はテーブルのためのアドレスになる。このアプローチにまつわる１つの問題は、各既約多項式の各体のために別々のテーブルを格納しなければならないことである。加えて、テーブルは、直列にしかアクセスすることができない。もし並列演算が必要なら、各テーブルのコピーを、各並列演算のために提供しなければならない。別のアプローチは、各々の格納されたガロア体の元に特定の除数を掛けることである。積が１になる値が、特定の除数の逆数である。この値の全てを、もう一度、格納しなければならない。そして、もし並列演算を企図するのであれば、複数のコピーが必要になる。そして、ガロア体乗算器は、ただ検索を達成することだけを要求される。第３のアプローチは、２つの線形フィードバックシフトレジスタ（ＬＦＳＲ）を用いる。各々は、特定の既約多項式の選択されたガロア体を生成するように構成される。第１のものは、除数に初期化される。第２のものは、“１”に初期化される。除数の値からスタートし、２つは、同期をとってクロック制御される。第１のＬＦＳＲの積が“１”になったとき、除数は、その逆数を掛けられていたことになる。その時点での第２のＬＦＳＲの積が、除数の逆数であるガロア体の元である。このアプローチにまつわる１つの問題は、各次数のための各既約多項式の各ガロア体のために、別々のＬＦＳＲの対が必要になることである。上記の２番目のルックアップテーブルアプローチおよびＬＦＳＲアプローチの両方において、逆数の検索は、最高２ｍ−１回の繰り返しを必要とする。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
それゆえに、本発明の目的は、改良されたガロア体除算器エンジンおよび方法を提供することである。
【０００６】
本発明の更なる目的は、ｍ−１回の繰り返し内で除数の逆数の検索を完了することができるような、改良されたガロア体除算器エンジンを提供することである。
【０００７】
本発明の更なる目的は、さまざまな既約多項式を、さまざまな次数のガロア体に合わせるように容易に再構成することができるような、改良されたガロア体除算器エンジンを提供することである。
【０００８】
本発明の更なる目的は、除数の逆数を生成し、かつそれに被除数を掛けるように機能することができるように、改良されたガロア体除算器エンジンを提供することである。
【０００９】
本発明の更なる目的は、より少ない電力および面積しか必要としないような、改良されたガロア体除算器エンジンを提供することである。
【００１０】
本発明の更なる目的は、より一般的に、改良された、一変換演算中に一連のガロア体変換を実行するための複合ガロア体エンジンを提供することである。
【課題を解決するための手段】
【００１１】
本発明は、より小さく、より高速で、かつより効率的であるような改良されたガロア体除算エンジンおよび方法が、ガロア体逆数生成器および入力選択回路を用いて達成され得るという認識からもたらされる。前記入力選択回路は、最初に、１および第１のガロア体の元を前記ガロア体逆数生成器に入力して、出力を得て、続いて、ガロア体逆数生成器内で、第１のガロア体の元にガロア体逆数生成器の出力を掛けて、ｍ−２回（ここでｍはガロア体の次数である）で既約多項式の多項式積の二乗のモジュロ(modulo)剰余を予測して、第１のガロア体の元の逆数を得て、かつ、ガロア体逆数エンジン内で、第１のガロア体の元の逆数に第２のガロア体の元を掛けて、既約多項式のための多項式積のモジュロ剰余を予測して、ｍ周期内で２つのガロア体の元の商を得る。
【００１２】
また、より一般的に、多項式入力の連続上でガロア体線形変換の連続を実行して、最終的な出力を得るための、改良された複合ガロア体エンジンは、最初のもの以外の各入力は、先行するガロア体線形変換の出力であり、第１の入力を供給するための入力回路と、第１の入力に応じて、一変換中に、一連の既約ガロア体多項式のガロア体線形変換のモジュロ剰余を直ちに予測して、第１の入力から、直接、ガロア体線形変換の最終的な出力を得るように構成された、セルのマトリックスを有するガロア体線形変換器とを用いて達成され得ることが認識された。
【００１３】
本発明は、ガロア体逆数生成器および入力選択回路を備えるガロア体除算器エンジンを特徴とする。前記入力選択回路は、最初に、１および第１のガロア体の元をガロア体逆数生成器に入力して、出力を得て、続いて、ガロア体逆数生成器内で、第１のガロア体の元にガロア体逆数生成器の出力を掛けて、ｍ−２回（ここでｍはガロア体の次数である）で既約多項式の多項式積の二乗のモジュロ剰余を予測して、第１のガロア体の元の逆数を得て、かつ、ガロア体逆数エンジン内で、第１のガロア体の元の逆数に第２のガロア体の元を掛けて、既約多項式のための多項式積のモジュロ剰余を予測して、ｍ周期内で２つのガロア体の元の商を得る。
【００１４】
好ましい実施形態において、逆数生成器は、第１および第２のガロア体乗算器を有していてもよい。第１のガロア体乗算器は、第１の多項式乗算器回路および第１のガロア体線形変換器を有していてもよい。第１のガロア体線形変換器は、セルのマトリックスを有していてもよい。第１のガロア体線形変換は、マトリックスセクションおよび単位(unity)マトリックスセクションを有していてもよい。第２のガロア体乗算器は、第２の多項式乗算器回路および第２のガロア体線形変換器を有していてもよい。第２のガロア体線形変換器は、セルのマトリックスを有していてもよい。セルの第２のガロア体線形変換器マトリックスは、マトリックスセクションおよび単位マトリックスセクションを有していてもよい。第１のガロア体乗算器の出力は、第２のガロア体線形乗算器の両方の乗算入力に供給され、その出力の二乗が提供されてもよい。ガロア体逆数生成器は、第１の多項式乗算器および第１のガロア体変換器および第２のガロア体変換器を含むガロア体乗算器を有していて、第１のガロア体乗算器の出力の二乗を計算してもよい。第２のガロア体変換器は、第１のガロア体変換器の約半分の大きさであってもよい。第１および第２のガロア体変換器は、各々、セルのマトリックスを有していてもよく、第２のガロア体変換器は、第１のガロア体変換器のセルの約半分の数を有していてもよい。ガロア体逆数エンジンは、ガロア体乗算器と、ガロア体乗算器をプログラムして、乗算演算に続いて、ｍ−２回の間、複合乗算−二乗演算を実行するためのプログラム回路とを有していてもよい。
【００１５】
本発明は、また、より広い意味で、一連の多項式入力上で一連のガロア体線形変換を実行して、最終的な出力を得るための複合ガロア体エンジンであることを特徴とする。ここで、最初のもの以外の各入力は、先行するガロア体線形変換の出力である。第１の入力を供給するための入力回路と、第１の入力に応じて、一変換中に、一連の既約ガロア体多項式のガロア体線形変換のモジュロ剰余を直ちに予測して、第１の入力から、直接、ガロア体線形変換の最終的な出力を得るように構成された、セルのマトリックスを有するガロア体線形変換器とを備えている。
【００１６】
本発明は、また、ガロア体除算の方法において、最初に、１および第１のガロア体の元をガロア体逆数生成器に入力して、出力を得るステップと、ガロア体逆数生成器内で、第１のガロア体の元にガロア体逆数生成器の出力を掛けて、ｍ−２回（ここでｍはガロア体の次数である）で既約多項式の多項式積の二乗のモジュロ剰余を予測して、第１のガロア体の元の逆数を得るステップと、ガロア体逆数エンジン内で、第１のガロア体の元の逆数に第２のガロア体の元を掛けて、既約多項式のための多項式積のモジュロ剰余を予測して、ｍ周期内で２つのガロア体の元の商を得るステップとを有していることを特徴とする。
【００１７】
本発明は、また、ガロア体平方根エンジンにおいて、ガロア体平方根生成器と、ガロア体の元をガロア体平方根生成器に入力して、１周期内でガロア体の元の平方根を得るための入力回路とを備えていることを特徴とする。
【００１８】
好ましい実施形態において、ガロア体平方根エンジンは、ガロア体乗算器と、ガロア体乗算器をプログラムして、１周期内でｍ−１回の複合二乗演算を実行するためのプログラム回路とを有していてもよい。
【００１９】
本発明は、また、ガロア体平方根方法において、ガロア体の元をガロア体平方根生成器に入力して、出力を得るステップと、ガロア体平方根生成器内で、ガロア体平方根生成器の出力を二乗して、ｍ−１回（ここでｍはガロア体の次数である）で既約多項式の多項式積の二乗のモジュロ剰余を予測して、（ｍ−１）周期内でガロア体の元の平方根を得るステップとを有していることを特徴とする。
【００２０】
他の目的、特徴および利点は、当業者によって、以下の好ましい実施形態の説明および添付の図面から見いだされるであろう。
【図面の簡単な説明】
【００２１】
【図１】本発明によるコンパクトなガロア体乗算器エンジンの機能ブロック図である。
【図２】従来のガロア体乗算器エンジンのより詳細な機能ブロック図である。
【図３】図１のコンパクトなガロア体乗算器エンジンのより詳細な機能ブロック図であり、本発明の縮小された大きさのガロア体線形変換器の単位マトリックスの特徴を示している。
【図４】図２および３のガロア体線形変換器回路のマトリックスのための典型的なプログラマブルＸ−ＯＲ回路セルの回路図である。
【図５】図３および９のガロア体線形変換器回路の簡略化された回路図であり、特定の８乗の多項式のための本発明によるマトリックスセクションおよび単位マトリックスセクションセルのプログラミングを示している。
【図６】図３および９のガロア体線形変換器回路の簡略化された回路図であり、別の８乗の多項式のための本発明によるマトリックスセクションおよび単位マトリックスセクションセルのプログラミングを示している。
【図７】図３および９のガロア体線形変換器回路の簡略化された回路図であり、更に別の４乗の多項式のための本発明によるマトリックスセクションおよび単位マトリックスセクションセルのプログラミングを示している。
【図８】図３および９のガロア体線形変換器回路の簡略化された回路図であり、この特定の実施形態における半分の累乗（４乗）と全部の累乗（８乗）との間の多項式の累乗をサポートするための、まばらなマトリックスとしての第２のマトリックスセクションのプログラミングを示している。
【図９】図１のコンパクトなガロア体乗算器エンジンのより詳細なブロック図であり、本発明の特徴である縮小された大きさのマトリックスおよび縮小されたハードウェアおよびローカライズされたバスを組み込んでいる。
【図１０】本発明のガロア体乗算器エンジンのブロック図であり、多くのガロア体線形変換器ユニットを用いている。
【図１１】図２、３、５および９において使用可能な多項式乗算器の概略図である。
【図１２】図１１の多項式乗算器のための伝達関数の図である。
【図１３】本発明による除算器エンジンの簡略化された概略ブロック図である。
【図１４】図１３における、ガロア体乗算器および二乗器のより詳細な図である。
【図１５】図１２の多項式乗算器のための縮小された伝達関数値の図である。
【図１６】図１４と同様のガロア体乗算器および二乗器の図であり、図１５の縮小された伝達関数を実現する。
【図１７】図１４のガロア体線形変換器のイネーブルにされたセルのパターンの略図である。
【図１８】図１６のガロア体線形変換器のイネーブルにされたセルのパターンの略図であり、縮小された伝達関数を用いている。
【図１９】本発明のより一般的な特徴による、一連の多項式入力上で一連のガロア体線形変換を実行して、最終的な出力を得る、例えば除算のための、複合ガロア体エンジンのための複合ガロア体線形エンジンのイネーブルにされたセルのパターンの略図である。
【図２０】複合ガロア体エンジンの簡略化された回路図であり、図１９に示したガロア体変換を用いている。
【図２１】本発明によるガロア体除算方法のフローチャートである。
【図２２】本発明による平方根エンジンの概略ブロック図である。
【図２３】本発明のより一般的な特徴による、図２２に示したような、一連の多項式入力上で一連のガロア体線形変換を実行して、最終的な出力を得る、例えば平方根のための、複合ガロア体線形エンジンのイネーブルにされたセルのパターンの略図である。
【図２４】本発明によるガロア体平方根算出方法のフローチャートである。
【図２５】本発明による複合ガロア体エンジンの簡略化されたブロック図である。
【発明を実施するための形態】
【００２２】
以下に開示した好ましい実施形態のほかに、本発明は、他の実施形態が可能であり、かつ様々な方法で実施または実行されることが可能である。従って、本発明は、その出願の中で、以下の説明に記載または図面に示した、構成の細部および構成要素の配置に限定されないものと理解されるべきである。
【００２３】
本発明の複合ガロア体エンジンおよび除算器エンジンおよび方法を開示する前に、よりよい理解のために、ガロア体変換器および乗算器の説明を行う。
【００２４】
ガロア体ＧＦ（ｎ）は、その上で２つの２元演算を実行可能な元の集合である。加算および乗算は、交換、結合および分配の法則を満たさなければならない。有限の数の元を有する体は、有限体である。２元体の例は、モジュロ２(modulo 2)加算およびモジュロ２乗算の下での集合｛０，１｝であり、ＧＦ（２）と表記される。モジュロ２加算および乗算の演算は、以下に示す表によって定義される。最初の行および最初の列は、ガロア体加算器および乗算器への入力を示している。例えば、１＋１＝０、１＊１＝１である。
【００２５】
【表１】
2010102351.tif 000003
【００２６】
【表２】
2010102351.tif 000004
【００２７】
一般に、ｐが素数であれば、ＧＦ（ｐ）はｐ個の元を有する有限体であり、ＧＦ（ｐｍ）はｐｍ個の元を有する拡大体であることを示すことができる。加えて、体のさまざまな元を、１つの体の元βのさまざまな累乗として、それをさまざまに累乗することによって生成することができる。例えば、ＧＦ（２５６）は２５６個の元を有していて、それは、原始元βを２５６通りにさまざまに累乗することによって、全て生成することができる。
【００２８】
加えて、係数が二進数である多項式は、ＧＦ（２）に属している。次数ｍのＧＦ（２）上の多項式は、それがｍより小さく、ゼロより大きい次数のＧＦ（２）上の多項式で割り切れないならば、既約であるという。多項式Ｆ（Ｘ）＝Ｘ２＋Ｘ＋１は、ＸまたはＸ＋１のどちらでも割り切れないので、既約多項式である。Ｘ２ｍ−１＋ｌを割る次数ｍの既約多項式は、原始多項式として知られている。与えられたｍに対して、複数の原始多項式があってもよい。大部分の通信規格でしばしば用いられる、ｍ＝８に対する原始多項式の例は、Ｆ（Ｘ）＝０ｘ１１ｄ＝ｘ８＋ｘ４＋ｘ３＋ｘ２＋１である。
【００２９】
ガロア体加算は、モジュロ加算と同じなので、ソフトウェアで実現するのは簡単である。例えば、もし２９および１６がＧＦ（２８）内の２つの元であるならば、それらの加算は、簡単に、ＸＯＲ演算として次のように行われる。
【００３０】
【数１】
2010102351.tif 000005
【００３１】
他方で、ガロア体乗算は、以下の例で示すように、少し複雑であり、それは、原始元βの繰り返される乗算によって、ＧＦ（２４）の全ての元を計算する。ＧＦ（２４）のための体の元を生成するために、次数ｍ＝４の原始多項式Ｇ（ｘ）は、次のようにＧ（ｘ）＝Ｘ４＋Ｘ＋１に選ばれる。乗算の結果が依然として体の元であるように、乗算をモジュロにするために、第５のビットの集合を有するいかなる元も、以下の恒等式Ｆ（β）＝β４＋β＋１＝０を用いて、４ビットにされる。この恒等式は、繰り返し用いられ、β４＝１＋βを設定することによって、体のさまざまな元を形成する。従って、体の元は、次のように列挙され得る。
｛０，１，β，β２，β３，１＋β，β＋β２，β２＋β３，１＋β＋β３，．．．，１＋β３｝
βはＧＦ（２４）のための原始元なので、それは、２に設定されて、ＧＦ（２４）の体の元を｛０，１，２，４，８，３，６，１２，１１，．．．，９｝のように生成することができる。
【００３２】
ガロア体多項式乗算は、２つの基本的なステップで実行することができることが分かる。第一は、代数学的に拡張された多項式積ｃ（ｘ）＝ａ（ｘ）＊ｂ（ｘ）の計算であり、同様の累乗が集められ、（加算は、対応する項間のＸＯＲ演算に対応する）ｃ（ｘ）が与えられる。
例えば、ｃ（ｘ）＝（ａ３ｘ３＋ａ２ｘ２＋ａｌｘｌ＋ａ０）＊（ｂ３ｘ３＋ｂ２ｘ３＋ｂ１ｘ１＋ｂ０）
ｃ（ｘ）＝ｃ６ｘ６＋ｃ５ｘ５＋ｃ４ｘ４＋ｃ３ｘ３＋ｃ２ｘ２＋ｃ１ｘ１＋ｃ０  ここで、
【００３３】
【数２】
2010102351.tif 000006
【００３４】
第二は、ｄ（ｘ）＝ｃ（ｘ）モジュロｐ（ｘ）の計算である。
【００３５】
実例を示すために、多項式モジュロ既約多項式の乗算を有する乗算を実行する。例えば、（もし、ｍ（ｘ）＝ｘ８＋ｘ４＋ｘ３＋ｘ＋１であれば）｛５７｝＊｛８３｝＝｛ｃ１｝  なぜなら、
【００３６】
【数３】
2010102351.tif 000007
【００３７】
このアプローチを除外した、改良されたガロア体乗算器システム１０は、Ａレジスタ内の多項式ａ０−ａ７と、Ｂレジスタ内の多項式ｂ０−ｂ７との２つを、ガロア体上の係数と共に乗算して、それらの積を得るための乗算器回路を備えていて、チャートIIのように定義される、１５項の多項式ｃ（ｘ）によって与えられる。乗算器回路は、実際には、複数の乗算器セルを有している。
【００３８】
【数４】
2010102351.tif 000008
【００３９】
ガロア体乗算器システムの演算は、Stein他によるGALOIS FIELD MULTIPLIER SYSTEMと題された２００２年１月３０日に出願された米国特許出願第１０／０６０，６９９号［ＡＤ−２４０Ｊ］の中で説明されており、これは、この参照によって、ここで完全に組み込まれる。
１５個の多項式ｃ（ｘ）の項の各々は、＊によって表されるＡＮＤ関数を含んでいて、項の各対は、下記の記号によって表される排他的論理和で結合されている。
【００４０】
【数５】
2010102351.tif 000009
【００４１】
チャートIIで表されるような、この積は、ガロア体線形変換器回路に提出される。これは、各々が１５ｘ８のセルから成る多くのガロア体線形変換器ユニットを有していてもよく、これは、乗算器回路によって生成される積に応じて、あらかじめ決められた既約多項式のための多項式積のモジュロ剰余を予測する。Ａ０，Ｂ０乗算は第一のユニットで実行され、Ａ１，Ｂ１は第二のユニットで、Ａ２，Ｂ２は第三のユニットで、そしてＡｎ，Ｂｎは最後のユニットで実行される。ガロア体線形変換器回路およびその変換器ユニットの各々の演算は、Stein他によるGALOIS FIELD LINEAR TRANSFORMERと題された２００２年１月１８日の出願日の米国特許出願第１０／０５１，５３３号［ＡＤ−２３９Ｊ］の中で説明されており、これは、この参照によって、ここで完全に組み込まれる。ガロア体線形変換器ユニットの各々は、多項式積を既約多項式で割ることによって、モジュロ剰余を予測する。その既約多項式は、例えば、チャートIIIに示すもののうちのどれであってもよい。
【００４２】
【数６】
2010102351.tif 000010
【００４３】
【数７】
2010102351.tif 000011
【００４４】
ここで示したガロア体乗算器ＧＦ（２８）は、累乗２８および累乗２４と共に、チャートIIIに示すようなものの下で実行可能である。
ＧＦ乗算の例は、次のように行われる。
【００４５】
【数８】
2010102351.tif 000012
【００４６】
図１に、Ａ入力レジスタ１２、Ｂ入力レジスタ１４および出力レジスタ１６が付いた、コンパクトなガロア体乗算器エンジン１０が示されている。コンパクトなガロア体エンジン１０は、乗算、乗算−加算および乗算−累積(accumulate)を含む、多くのさまざまな演算が可能である。
【００４７】
図２の従来のガロア体乗算器エンジン１０ａは、３つのレジスタ、すなわちＡレジスタ１２ａ、Ｂレジスタ１４ａおよびＣレジスタ２６ａを必要とする。これらのレジスタの荷物(burden)は、関連するデジタルシグナルプロセッサ（ＤＳＰ）コア２８によって運ばれなければならない。そして、大規模な外部バスワークを必要とする。データをＡレジスタ１２ａに供給するためのバス３０、データをＢレジスタ１４ａに供給するためのバス３４およびデータをＣレジスタ２６ａに供給するためのバス３６に加えて、レジスタ１６ａからの出力をデジタルシグナルプロセッサ２８にフィードバックするためのバス３２、およびデジタルシグナルプロセッサ２８からのその出力をＢレジスタ１４ａまたはＣレジスタ２６ａにフィードバックするためのバス３４またはバス３６が必要である。バス３１は、ガロア体線形変換器回路２０の出力と出力レジスタ１６ａを接続する。従って、多項式乗算器回路１８は、ガロア体線形変換器回路２０のマトリックス２２の乗算(multiple)入力４０に、Ｃレジスタ２６ａからマトリックス２２の加算器入力４２に供給される値と共に、適切な値を供給して、乗算、乗算−加算および乗算−累積関数を実行することができる。マトリックス２２は、ここでは８×１５のマトリックスとして示され、８乗の多項式の乗算をサポートするが、供給されるべき多項式の累乗に応じて、より多いまたは少ないセル２４を含むように、より大きくまたは小さくすることができる。
【００４８】
図３における、エンジン１０ｂ内のガロア体線形変換器回路２０ｂのマトリックス２２ｂの行当たりのセル２４ｂの数は、マトリックス２２ｂを２マトリックスセクション構成、すなわちマトリックスセクション５０および単位マトリックスセクション５２の構成とすることによって、ほぼ半分まで減らすことができる。単位マトリックスセクションは、乗算器回路の出力が既約多項式の累乗より小さい累乗を有する多項式であるときに、これらの単位マトリックスセクションセルが剰余の予測を表す、ただ一組のセル５４のみを必要とする。従って、図３においては、既約多項式が８の累乗を有するので、８より小さい、いかなる多項式も、このモジュロを超えない。そして、マトリックスを通して右へ通過する。従って、単位マトリックスセクション５２における欠けているセルは、必要ない。これは、マトリックス２２ｂに必要なセルのほぼ半分を節約し、より小さく、より簡単かつより高速なエンジンをもたらす。
【００４９】
図４における各セル２４ｂは、ＡＮＤ回路１００および排他的論理和回路１０２を含んでいる。データ入力１０４およびイネーブル入力１０６がある。排他的論理和回路１０２は、出力がマトリックスの出力に接続されている最後の排他的論理和回路、および入力が図３の加算器入力４２ｂまたは図９の４２ｇに接続されている最初の排他的論理和回路を除いて、次の排他的論理和回路の入力へのライン１０８上に出力を供給し、その入力１１０で前の排他的論理和回路からの出力を受け取る。ライン１０６上のイネーブル信号は、ライン１０４上のデータをイネーブルにして、ＡＮＤゲート１００を通過させ、排他的論理和回路１０２によってライン１１０上の入力との排他的論理和をとる。ライン１０６上にイネーブル信号がない場合には、単にライン１１０上の入力を、排他的論理和ゲート１０２を通して通過させ、ライン１０８に出力する。ライン１０６上のイネーブル信号は、セル２４ｂをイネーブルにする。このような方法で、マトリックス全体を、いかなる特定の既約多項式に対しても再構成することができる。
【００５０】
図３におけるエンジン１０ｂの有効性は、前記チャートIIIから既約多項式を選んで、必要なセルをイネーブルにすることによってそれを実行することによって理解され得る。例えば、０ｘ１１ｄと称される、既約多項式ｘ８＋ｘ４＋ｘ３＋ｘ２＋１を表している、８乗の１番目の多項式を実行するために、イネーブルにされたセルは、一般に２４ｃｃで示すが、既に図３にも示した、１ラインのセル５４ｃを有する図５の単位マトリックス５２ｃを形成する。チャートIIIから２番目の既約多項式０ｘ１２ｂを選ぶと、この既約多項式ｘ８＋ｘ５＋ｘ３＋ｘ＋１は、図６における、マトリックスセクション５０ｄおよび単位マトリックス５２ｄ内の、イネーブルにされたセル２４ｄｄのパターンを生成し、ここで、再び、単位マトリックスセクション５２ｄが、１ラインのイネーブルにされたセル５４ｄをもたらす。
【００５１】
必要なセルの数の低減は、既約多項式と同じ累乗を有する多項式のみに限定されない。それは、既約多項式の半分の累乗または少ない累乗を有するもののうちのいずれにも適用される。例えば、図３に示し、かつ図５および６における説明のために参照した８×１５マトリックス２２ｂは、１、２、３または４乗の多項式もサポートすることができる。しかし、５、６および７乗は、できない。もし既約多項式が１６乗であったら、それをサポートしたマトリックスは、８乗までの多項式もサポートすることができる。しかし、９乗から１５乗は、できない。もしそれが３２乗であったら、それは３２乗および１６乗までの多項式をサポートすることができる。しかし、１７乗から３１乗は、できない。例えば、図７に示すように、４乗の既約多項式に対しては、マトリックスセクション５０ｅおよび単位マトリックスセクション５２ｅは、より小さくなり、かつマトリックス２２ｅ内のどこででも実行され得る。ここで、マトリックスセクション５０ｅは、単位マトリックス５２ｅ内のイネーブルにされたセルと共に、複数のイネーブルにされたセル２４ｅｅを有していて、それは、より小さいラインのイネーブルにされたセル５４ｅを有していて、単位マトリックスセクション５２ｅを構成している。
【００５２】
もし５、６および７乗の中間の多項式を供給することが望ましいのであれば、単位マトリックスセクションは、図８における、まばらな(sparse)マトリックスセクション５２ｆと置き換えることができ、イネーブルにされたセル５４ｆｆ、５４ｆｆｆ、５４ｆｆｆｆの追加のラインが、それぞれ７、６および５乗の多項式をサポートするために用いられ得る。しかし、それは、マトリックスの大きさおよび必要なセルの数の低減がやや少ない。
【００５３】
入力レジスタの数は、３から２に減らすことができ、かつ図９におけるデジタルシグナルプロセッサ（ＤＳＰ）２８ｇと通信するために必要な外部バスの数も、減らすことができ、エンジン１０ｇ自体の内部にあるものとしてローカライズされる。従って、図９に示すように、２つの入力レジスタＡ  １２ｇおよびＢ  １４ｇがあり、出力３１ｇからのフィードバックは、ＤＳＰ  ２８ｇを通過する必要はなく、直接、局所的に、エンジン１０ｇ上で内部バス６０を通って乗算器入力選択回路６２および加算器入力選択回路６４に行く。デジタルシグナルプロセッサ２８ｇは、乗算器入力選択回路６２へのライン６６上および加算器入力選択回路６４へのライン６８上に制御信号を供給する必要があるだけである。従って、乗算モードにおいては、乗算器入力選択回路６２は、Ｂレジスタ１４ｇからの入力を多項式乗算器回路１８ｇへ通過させる一方で、加算器入力選択回路６４は、加算の恒等式レベルを供給する。この場合、ガロア体線形変換器回路２０ｇの加算器入力４２ｇに、接地レベル７０を供給する。乗算−加算モードにおいては、デジタルシグナルプロセッサ２８は、乗算器入力選択回路６２に、マトリックス２２ｇからの出力をライン６０を通して多項式乗算器回路１８ｇにフィードバックするように指示し、かつ加算器入力選択回路６４に、Ｂレジスタ１４ｇ内の多項式をガロア体線形変換器回路２０ｇの加算器入力４２ｇへ通過させるように指示する。乗算−累積モードにおいては、デジタルシグナルプロセッサ２８ｇは、乗算器入力選択回路６２に、Ｂレジスタ１４ｇからの多項式を多項式乗算器回路１８ｇに供給するように指示し、かつ加算器入力選択回路６４に、ガロア体線形変換器回路２０ｇのライン６０上の出力をフィードバックするように指示する。
【００５４】
別の特徴は、セル２４ｇの選択を可能にすることによる、ガロア体線形変換器回路２０ｇの再構成可能性である。再構成可能な制御回路８０は、選択された既約多項式の係数を実現するのに必要なセル２４ｇの１つ１つを選択的に使用可能にする。そして、それ自体の大きさを縮小することができる。なぜなら、それが制御する必要があるセルの数が減らされるからである。
【００５５】
ガロア体線形変換器回路の再構成可能な入力の動作は、２００２年５月１日に出願されたStein他によるRECONFIGURABLE INPUT GALOIS FIELD LINEAR TRANSFORMERER SYSTEMと題された米国特許出願第１０／１３６，１７０号（ＡＤ−３００Ｊ）および全てのその優先権出願および文献の中で説明されていて、それは、それらの全てが、この参照によって、ここで組み込まれる。
【００５６】
ここまで、説明を簡単にするために、１つのみのエンジンに関して説明してきたが、図１０に示すように、多くのエンジンを一緒に用いることもできる。各エンジンは、乗算器回路１０ｈ，１０ｉ，１０ｊ，１０ｋ，．．．，１０ｎおよびガロア体線形変換器回路２０ｈ，２０ｉ，２０ｊ，２０ｋ，．．．，２０ｎを有している。それら全てを制御している単一の再構成可能な中央制御回路８０’を有している。これらのエンジンは、同じ幅［３２，６４，１２８］ビットのＡおよびＢレジスタを共有することができる。各々は、別々の８ビット（バイト）セグメント上で動作することもできる。すなわち、各々は、それ自体の再構成可能な制御ユニット８０ｈ，８０ｉ，８０ｊ，８０ｋ，．．．，８０ｎによってサービスされ得る。そして、各々は、ＡおよびＢレジスタのそれ自体の対、すなわちＡ０およびＢ０（１２ｈおよび１４ｈ）、Ａ１およびＢ１（１２ｉおよび１４ｉ）、Ａ２およびＢ２（１２ｊおよび１４ｊ）、Ａ３およびＢ３（１２ｋおよび１４ｋ）などによってサービスされ得る。
【００５７】
出力ｃ０−ｃ１４を供給するために、ここで示す実施形態の中で使用できる、図１１における多項式乗算器回路１８ｌは、複数のＡＮＤゲート１２０を含んでいて、それらは排他的論理和ゲート１２２と接続されている。そして、Ａレジスタ１２ｌおよびＢレジスタ１４ｌからの多項式の任意の対の乗算を行うことができる。例えば、図１２におけるテーブル１２４に示すような、多項式ａ０−ａ７、多項式ｂ０−ｂ７である。
【００５８】
図１３に、ガロア体乗算器１５２および二乗関数を実行するための第２のガロア体乗算器１５４を有する、ガロア体逆数生成器１５５を含む、本発明によるガロア体除算器エンジン１５０が示されている。エンジン１５０は、演算βｌ＊１／βｋを実行することによって、除算βｌ／βｋを実行する。ここでβｌおよびβｋはガロア体の元であり、例えば、ｍ＝８であれば、それはＧＦ（２８））であり、体の次数は８である。最初に、ガロア体乗算器１５２は、１およびβｋを受け取り、それらの乗算を行う。次に、その出力が、ガロア体乗算器１５４において二乗され、そして、ガロア体乗算器１５２にフィードバックされる。この結果に、ｍ−２回の間、何度もβｋが掛けられ、合計でｍ−１回の繰り返しが行われる。この時点で、逆数１／βｋが得られる。そして、ｍ−２回の繰り返しの各々の間、供給されてきた、βｋの代わりに、今度は、乗算βｌ＊（１／βｋ）を実行するために、βｌが供給される。従って、除算全体は、合計ｍ回の繰り返しによって行われる。ｍ−１回の繰り返しによって逆数が生成され、もう１回によって除数の逆数と被除数を掛けて、商を得る。“１”、βｋおよびβｌの適時の使用は、入力選択回路１７１によって行われる。
【００５９】
【数９】
2010102351.tif 000013
【００６０】
が、以下の説明によって示される。体ＧＦ（ｑ）は、数｛０，１，．．．，（ｑ−１）｝から成る。β（βは体の要素であって、０ではない）を｛１，２，．．．，（ｑ−１）｝の各要素に掛けて、｛１β，２β，．．．，（ｑ−１）β｝を得れば、再び（その位数が変更された）同じ集合が得られることは容易に分かる。これは、１・２・．．．・（ｑ−１）＝１β・２β・．．．・（ｑ−１）β＝１・２・．．．・（ｑ−１）β（ｑ−１）を意味し、両辺の因数１・２・．．．・（ｑ−１）を約すことによって、下記の式が得られる。
βｑ−１＝１      （１）
従って、
β−１＝βｑ−２      （２）
【００６１】
ｑを２ｍに置き換えると、下記の式が得られる。
【００６２】
【数１０】
2010102351.tif 000014
図１３は、この式の直接の実現である。
【００６３】
ｎ＝７に対する式（３）によれば、β２５４を計算する必要がある。β２５４は、β１２８・β６４・β３２・β１６・β８・β４・β２として計算することができる。これは、以下のように繰り返し計算することができる。
【００６４】
【数１１】
2010102351.tif 000015
【００６５】
図１３の回路は、１の初期値からスタートし、１５５で、以下の連続する値を生成する。
【００６６】
【表３】
2010102351.tif 000016
【００６７】
最終的な値であるβ−１が、（ｎ−ｌ）周期において得られることが分かる。同じ回路が、全ての中間のｍ乗ＧＦ（２ｍ）｛ｍ＝３．７｝に対するβ−１を生成する。例えば、ｍ＝４であれば、下記の式がｎ＝３で生成される。
【００６８】
【数１２】
2010102351.tif 000017
【００６９】
一実施形態において、図１４のガロア体逆数生成器１５５ａは、ガロア体乗算器１５２ａおよびガロア体乗算器１５４ａを有している。ガロア体乗算器１５２ａは、ガロア体線形変換器１５６および多項式乗算器１５８を有している。ガロア体乗算器１５６は、２つのセクション、すなわちマトリックスセクション１６０および縮小された(reduced)単位マトリックスセクション１６２を持つ排他的論理和セルのマトリックスを含むものとして示されているが、これは、本発明の必須の限定ではない。なぜなら、単位マトリックスセクション１６２は、もし大きさが問題ではないならば、マトリックスセクション１６０と同様に、完全(full)マトリックスで実現してもよいからである。ガロア体乗算器１５４ａも、多項式乗算器１６４およびガロア体変換器１６６を有していて、ガロア体変換器１６６は、必須ではないが、完全マトリックスセクション１６８および縮小された単位マトリックスセクション１７０を更に含んでいてもよい。ここで再び、単位セクション１７０は、コストおよび面積に関して有利である。しかし、完全セクションをそこで用いることができるとき、それは必須ではない。ガロア体除算器エンジン１５０ａは、ｍ回の繰り返し内で除算を実行する。最初の繰り返しにおいて、入力選択回路１７１は、βｋと共に、１をガロア体乗算器１５２ａに導入する。これは、出力βｋをライン１７２上に生成し、それは、ガロア体乗算器１５４ａの両方の多項式乗算器入力１７４、１７６に供給される。従って、二乗関数が実行され、その出力は、入力選択回路１７１の入力１７８にフィードバックされる。この繰り返しがｍ−２回行われる。ここでｍはガロア体の次数である。ｍ−２回の繰り返しの後、入力選択回路１７１は、被除数βｌをガロア体乗算器１５２ａに導入する。なぜなら、その時、出力１７８の値は、逆数１／βｋであるからである。そして、被除数βｌ×除数１／βｋを計算することによって、βｌがβｋによって割られ、１８０でガロア体除算の商を得る。
【００７０】
入力１７４および１７６での値は、最上位桁から最下位桁に向かって、ｂ７−ｂ０およびａ７−ａ０の形をとる。ここで二乗関数が実行される。ｂ７−ｂ０の各値は、それぞれ、ａ７−ａ０の各値と同じである。なぜなら、それらは同じ数であるからである。桁数ｂ７−ｂ０、ａ７−ａ０は、多項式のサイズに依存し、ｍが８であるこの場合には、８桁である。たとえどんなサイズであっても、値は両方の入力で同じなので、排他的論理和関数は、ゼロになる。すなわち、排他的論理和ゲートへの同じ入力に対しては、周知のように、ゼロ出力が返される。従って、再び図１２を参照すると、多項式乗算出力ｃ０−ｃ１４の各々に対して、図１２内の奇数番号のものは、同一の値の対を含むことが分かる。例えば、ｃ１は、下記の式に等しい。
【００７１】
【数１３】
2010102351.tif 000018
【００７２】
二乗を行うので、入力１７４と１７６に与えられる２つの値は同じであり、従ってａ０とｂ０は同じであり、ａ１とｂ１も同じである。従って、排他的論理和をとったｃ１の値はゼロになる。他の奇数番号のガロア体乗算器出力ｃ３，ｃ５，ｃ７，ｃ９，ｃ１１，ｃ１３についても同じことが言える。その結果を図１５の１８２に示す。奇数番号のｃ１−ｃ１３の結果であるゼロの値だけではなく、残りのゼロではない偶数番号の値も示されている。偶数番号の値は、排他的論理和ゲートを必要とせず、乗算しか必要としない。例えば、ｃ０はａ０＊ｂ０である。しかし、これは簡単なＡＮＤ関数であり、その結果はａ０の値になる。同様に、ｃ２に関しては、値ａ１にｂ１が掛けられるが、ＡＮＤ関数が与えられると、その結果はａ１という簡単な出力になる。ｃ４，ｃ６，ｃ８，ｃ１０，ｃ１２，およびｃｌ４においても同じ結果になる。同じことがガロア体乗算器１５６ｂにも適用される。二乗関数を遂行するガロア体乗算器１５４ｂは、大きさが半分に縮小され得る。これは、マトリックスセクション１６８ｂおよび単位セクション１７０ｂが半分に縮小されることによる。また、図１５の列１８４に示すように、関数が簡単な入力に変わったので、２つの別々の入力は必要なく、従って、多項式乗算器１６４も、もはや必要ない。
【００７３】
図１７におけるガロア体変換器１５６ｃおよび１６６ｃも同様に実現される。黒丸は、各々の変換器においてイネーブルにされた排他的論理和ゲートセルを示している。プログラミングは、列１９０におけるコードによって行われ、これは変換器１５６ｃおよび１６６ｃの両方について同様である。変換器１５６ｃは、入力ｃ０−ｃ１４を受け取り、出力Ａ０−Ａ７を提供する。これらは、ゼロと共に、ガロア体線形変換器１６６ｃのＡ０−Ａ７の入力を形成し、最終的な出力はＢ０−Ｂ７である。両方の変換器は、既約多項式（０ｘ１２ｂ）のための次数８のガロア体ＧＦ（２８）（ｍ＝８）のためのものである。図１５に示した縮小が遂行されるとき、図１８におけるガロア体乗算器１５６ｄは、列１９０ｄ内のプログラミングインストラクションの全てを行うので、同じ状態に保たれるが、ガロア体線形変換器１６６ｄは、１つおきの列しか有していない。ゼロの列は除去され、結果として図１６に示した構造になる。
【００７４】
ガロア体除算器エンジンが図１６に示したように縮小されるとき、更なる縮小を行うことができる。ガロア体除算器エンジン１５４ｂは、第２のガロア体変換器１６６ｂ内に多項式乗算器を有していないので、単一のマトリックスまたは変換器を構成することができる。それは、１周期内で、図１９における単一の線形変換器２００を用いて、中間のＡ０−Ａ７の項なしで、ｃ０−ｃ１４から、直接、出力Ｂ０−Ｂ７を供給する。変換器２００は、１つのガロア体線形変換器内かつ一演算内で、両方のガロア体線形変換を実行するために、黒丸によってイネーブルにされたことを示した排他的論理和セルの組み合わせを有するようにプログラムされている。従って、入力ｃ０−ｃ１４は、ガロア体線形変換器２００によって、最終的な出力Ｂ０−Ｂ７に、直接、変換される。図１８における２つのマトリックス１５６ｄおよび１６６ｄを、図１９における単一のマトリックスのガロア体線形変換器２００に縮小する複合は、図１８におけるＢ７を用いる簡単な例によって理解することができる。それは、ガロア体線形変換器１６６ｄ内に示された、Ａ７と、Ａ６と、Ａ５との排他的論理和に等しいことが分かる。次に、ガロア体線形変換器１５６ｄを参照すると、以下のことが分かる（ここで、バックスラッシュは、項のキャンセルを示している。なぜなら、それは、二重になっているからである。）。
【００７５】
【数１４】
2010102351.tif 000019
【００７６】
全ては、それらの間に排他的論理和関数を有している。これは、出力が、ｃ１４と、ｃ１３と、ｃ１２と、ｃ９と、ｃ８と、ｃ７と、ｃ６と、ｃ５との排他的論理和という結果になる。従って、図１９のマトリックス２００において、Ｂ７は、ｃ１４と、ｃ１３と、ｃ１２と、ｃ９と、ｃ８と、ｃ７と、ｃ６と、ｃ５との排他的論理和の組み合わせを有することが分かる。このような複合ガロア体除算器エンジン２０２の１つの実施が、図２０に示されていて、ここには、多項式乗算器２０４および２つの入力選択ユニット２０６、２０８を有する入力選択回路１７１ｅと共に、図１９におけるガロア体線形変換マトリックス２００が示されている。ここでは、ガロア体逆数生成器２０５は、単一の複合ガロア体線形変換器２００によって実現されている。入力選択ユニット２０６は、乗算−加算（ＭＰＡ）、乗算−累積（ＭＡＣ）、および乗算（ＭＰＹ）を行うことができる。入力選択ユニット２０８も、同様に機能し、ガロア体線形変換器２００に、前述したような加算器入力を供給する。プログラムシーケンサ２１０は、制御フリップフロップ２１２のマッピングを提供し、それは、排他的論理和ゲートを含んでいるセルのマトリックスをイネーブルおよびディスエーブルにする。プログラムシーケンサは、除算のための１周期内で（ＧＦ＿ＭＰＹ（α，β））２を実行する複合乗算器として、乗算のためのガロア体乗算器として、乗算および累積のための乗算および累積器として、そして乗算−加算関数のための乗算−加算器として、ＧＦＬＴマトリックス２００をプログラムすることができる。
【００７７】
動作において、最初に、ＧＦＬＴは、（ＧＦ＿ＭＰＹ（α、β））２を実行する複合乗算器としてプログラムされる。１が入力２１４に供給され、βｋが入力２１６に供給される。それに続いて、ｍ−２回の繰り返しの間、出力１８０は入力２１４にフィードバックされ、一方、βｋは入力２１６に残っている。ｍ−２回の繰り返しの後、システムが合計ｍ−１回の繰り返しを通り抜けたとき、２１４での入力は、βｋの逆数になる。この時点で、ＧＦＬＴは、ガロア体乗算器としてプログラムされ、入力２１６におけるβｋは、入力βｌに置き換えられ、これにより次の乗算、すなわちｍ回目の繰り返しである、βｌ×（βｋの逆数）が計算され、出力であるβｌ÷βｋが提供される。
【００７８】
本発明のガロア体除算方法を図２１に示す。除数βｋおよび被除数βｌが、開始２４０で供給される。次に、ステップ２４２で、この繰り返しがｍ回目の繰り返しであるかどうかについて問い合わせられる。ここでｍは、伴っているガロア体の次数である。もし、それがｍ回目の繰り返しであれば、システムは、直接、ステップ２４４へ行き、ここで、βｌに、ガロア体線形変換出力である逆数１／βｋを掛けるガロア体乗算が実行される。そして商が２４６で生成される。もし、繰り返しがｍ回に達していなければ、ステップ２４８で、それが最初の繰り返しであるかどうかについて問い合わせられる。もし、そうであれば、βｋに１を掛ける乗算が、ステップ２５０で遂行され、そして、ステップ２５２で、その値の二乗が、ガロア体上で実行される。もし、それが最初の繰り返しではないのであれば、ステップ２５４で、βｋにガロア体線形変換出力を掛けるガロア体乗算が実行され、そして、ステップ２５２で、二乗が、ガロア体乗算器内で実行される。そして、ステップ２４２で、二乗計算からの出力がフィードバックされ、繰り返しが再び始まる。
【００７９】
ここまで、本発明は、ガロア体除算器エンジンおよび方法、および、最初に、ガロア体線形変換器のうちの１つの大きさを縮小して、かつ多項式乗算器のうちの１つを除去することによって、次に、２つの線形変換器の機能を結合することによって、そのエンジンの大きさを縮小する能力に焦点を合わせてきた。これにより、一連の多項式入力上での一連のガロア体線形変換が実行され、図１９および２０に示したような最終的な出力（商）が得られる。しかし、これは本発明の必須の限定ではない。すなわち、それは除算のみに限定されない。本発明による複合ガロア体エンジンは、一連の多項式入力上で任意の一連のガロア体線形変換を実行して、最終的な出力を得ることができる。ここで、最初のものを除く各入力は、先行するガロア体線形変換の出力である。すなわち、一変換内で、既約ガロア体多項式の一連のガロア体線形変換のモジュロ剰余を直ちに予測して、最初の入力から、直接、ガロア体線形変換の最終的な出力を得ることができる。
【００８０】
このことの別の例を、ガロア体の要素βの平方根演算の中で見ることができる。図２２に、本発明による複合ガロア体エンジン３００が示されていて、それは、（ｍ−１）回、連続するガロア体線形変換３０２、３０４、．．．、３０６を実行する。最初の入力β，３０８は、ガロア体変換器３０２に提出され、そして、変換された出力が、次のガロア体線形変換器３０４への入力になり、その出力が、次のガロア体線形変換器への入力になり、等々、それが、この場合における最終的な変換器３０６、すなわち√β出力に達するまで続く。本発明によれば、図２３の３１０に示すように、ガロア体線形変換器を複合することによって、図２２の（ｍ−１）回の変換器を縮小して、図２３に示した１つのＧＦＬＴだけの単純化された実施を生み出すことができる。ここでは、最初の入力βは、複合ガロア体線形変換器平方根エンジン３３０によって、単一の演算内で変換され、１回の繰り返しで√β出力を提供することができる。
【００８１】
以下の解説によって
【００８２】
【数１５】
2010102351.tif 000020
が示される。
式（１）に、βｑ−１＝１が示されている。
ｑを２ｍに置き換えて、両辺にβを掛けると、下記の式になる。
【００８３】
【数１６】
2010102351.tif 000021
両辺の√をとると、下記の式になる。
【００８４】
【数１７】
2010102351.tif 000022
図２２は、この式の直接の実現である。
【００８５】
本発明のガロア体平方根算出方法を、図２４に示す。体の元βが、開始３１２で供給される。次に、ステップ３１４で、この繰り返しがｍ−１回目の繰り返しであるかどうかが問い合わせられる。ここでｍは、伴っているガロア体の次数である。もし、それがｍ−１回目の繰り返しであれば、システムは、直接、ステップ３１６へ行き、ここでβのガロア体平方根が生成される。もし、繰り返しがｍ−１回に達していなければ、ステップ３１８で、それが最初の繰り返しであるかどうかが問い合わせられる。もし、そうであれば、ステップ３２０で、そのβ値の二乗が、ガロア体上で実行される。もし、それが最初の繰り返しではないのであれば、ステップ３２２で、ガロア体線形変換出力の二乗が、ガロア体上で実行される。そして、ステップ３１４で、二乗計算からの出力がフィードバックされ、再び繰り返しが始まる。プログラミング回路、制御フリップフロップ２１２ａおよびプログラミングシーケンサ２１０ａは、図２３に示したようにガロア体線形変換器平方根エンジン３３０をプログラムする。
【００８６】
要約すると、一般に、本発明による図２５の複合ガロア体エンジン２６０は、多くの連続するガロア体線形変換２６２、２６４、２６６、２６８を実行することができる。最初の入力Ａ，２７０は、ガロア体変換器２６２に提出され、そして、変換された出力Ｂが、次のガロア体線形変換器２６４への入力になり、その出力Ｃが、次のガロア体線形変換器２６６への入力になり、その出力Ｄが、次のガロア体線形変換器２６８への入力になる。この場合、最終的な出力は、Ｅである。本発明によれば、図１８の２つの変換器を縮小して、図１９に示したようにガロア体線形変換器を複合することによって、図２０に示した実施を生み出す。最初の入力Ａは、複合ガロア体線形変換器２８０によって、単一の演算内で変換され、その１回の繰り返し内で最終的な出力Ｅを提供することができる。
【００８７】
本発明の特定の特徴が、いくつかの図面には示され、他のものには示されていないが、これは、便宜のみのためである。本発明によれば、各特徴は、他の特徴のいくつかまたは全てと組み合わせることができる。ここで用いた単語"including"、"comprising"、"having"、および"with"は、広く、かつ包括的に解釈されるべきであり、いかなる物理的な相互連結にも限定されない。さらに、対象出願の中で開示された、いかなる実施形態も、唯一可能な実施形態として、とらえられるべきではない。
【００８８】
当業者であれば、請求項の範囲内で、他の実施形態も見いだすであろう。
【符号の説明】
【００８９】
１０ｂ  ガロア体乗算器エンジン
２０ｂ  ガロア体線形変換器回路
２２ｂ  マトリックス
２４ｂ  セル
５０  マトリックスセクション
５２  単位マトリックスセクション
５４  一組のセル
【図１】
2010102351.tif 000023
【図２】
2010102351.tif 000024
【図３】
2010102351.tif 000025
【図４】
2010102351.tif 000026
【図５】
2010102351.tif 000027
【図６】
2010102351.tif 000028
【図７】
2010102351.tif 000029
【図８】
2010102351.tif 000030
【図９】
2010102351.tif 000031
【図１０】
2010102351.tif 000032
【図１１】
2010102351.tif 000033
【図１２】
2010102351.tif 000034
【図１３】
2010102351.tif 000035
【図１４】
2010102351.tif 000036
【図１５】
2010102351.tif 000037
【図１６】
2010102351.tif 000038
【図１７】
2010102351.tif 000039
【図１８】
2010102351.tif 000040
【図１９】
2010102351.tif 000041
【図２０】
2010102351.tif 000042
【図２１】
2010102351.tif 000043
【図２２】
2010102351.tif 000044
【図２３】
2010102351.tif 000045
【図２４】
2010102351.tif 000046
【図２５】
2010102351.tif 000047