(57)【要約】  【解決手段】ガロア体乗算システム（10）は、ガロア体上の２つの係数付き多項式を乗算して乗算値を得る乗算回路（12）と、乗算回路に応答して多項式乗算値の既約多項式によるモジュロ余りを予測するガロア体線型変換回路（18）と、ガロア体線型変換回路にモジュロ余りの予測に必要な所定の規約多項式の係数群を供給する記憶回路（20）とを含む。
2005512183.tif 000002
【特許請求の範囲】
【請求項１】
ガロア体上の２つの係数付き多項式を乗算して積を得る乗算回路、前記乗算回路に応答して多項式の積の既約多項式によるモジュロ余剰を推定するガロア体線型変換回路、及び前記ガロア体線型変換回路に所定既約多項式のモジュロ余剰推定用の係数群を供給する記憶回路を備えてなるガロア体乗算システム。
【請求項２】
請求項１のガロア体乗算システムにおいて、前記ガロア体線型変換回路により前記既約多項式で前記多項式の積を除算して前記モジュロ余剰を得てなるガロア体乗算システム。
【請求項３】
請求項１のガロア体乗算システムにおいて、前記乗算回路に前記多項式の積の各項のためのガロア乗算用論理積回路を含めてなるガロア体乗算システム。
【請求項４】
請求項１のガロア体乗算システムにおいて、前記乗算回路に前記多項式の積の各項対のためのガロア加算用排他的論理和回路を含めてなるガロア体乗算システム。
【請求項５】
請求項１のガロア体乗算システムにおいて、前記ガロア体線型変換回路に１以上のビット・ストリーム中の複数入力ビットに応答し且つその複数入力ビットのガロア体線型変換結果を出力する複数の出力端を有するマトリクスを含め、前記マトリクスに複数の素子を含めて各素子に排他的論理和回路と該排他的論理和回路に接続された出力端及び前記入力ビットの何れかに接続された入力端を有する論理積回路とをそれぞれ設け、前記記憶回路により前記入力の複数サイクルによるガロア体線型変換を単一サイクルで得るための前記係数群を供給してマトリクスに設定してなるガロア体乗算システム。
【請求項６】
請求項１のガロア体乗算システムにおいて、前記ガロア体線型変換回路に複数のガロア体変換装置を含め、前記記憶回路により前記ガロア体変換装置に前記係数群を並列に供給してなるガロア体乗算システム。
【請求項７】
請求項１のガロア体乗算システムにおいて、前記ガロア体線型変換回路に複数のガロア体変換装置を含め、前記記憶回路に前記ガロア体変換装置の各々にそれぞれ結合された複数の記憶装置を含めてなるガロア体乗算システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ガロア体乗算システムに関する。
【０００２】
関連する出願
本出願は、２００１年１１月３０日出願のステイン等による米国仮出願６０／３３４，６６２号「ＧＦ２−ＡＬＵ」に基づく優先権主張を伴う２００２年１月１８日出願のステイン等による米国出願「ガロア体線形変換器」（特許文献１参照）に関連する。本出願は、２００１年１１月３０日出願のステイン等による仮出願「並列ガロア体乗算器」に基づく優先権主張を伴う。
【背景技術】
【０００３】
ガロア体（GF；Galois Fields）上の係数付き多項式の乗算は、リードソロモン（RS；Reed Solomon）符号及び米国政府標準暗号（AES；Advanced Encryption Standard）のため、通信システムにおいて広く利用されている。ガロア体上の乗算は、伝統的なデジタル信号処理装置（DSP；Digital Signal Processors）では実行が難しく時間がかかる。デジタル信号処理装置は、有限インパルス応答（FIR；Finite Impulse Response）フィルタ処理及びその他の積和（MAC；Multiply Accumulate）要求処理に最適化されているが、ガロア体型演算を効率的に処理できない。
１つの解決方法は、一度に１ビットを処理する線形フィードバック・シフトレジスタ群（LFSR's；Linear Feedback Shift Registers）を使ってガロア体上の多項式の直接的な乗算及び除算を用いるものである。しかし、これは非常に遅い処理である。例えば、ＡＥＳ型アプリケーションのブロードバンド通信において、ビットレートが毎秒４０メガビット以上である場合に、毎秒当たりのガロア体乗算数は５百万回単位（MPS；Million GF multiplications Per Second）以上となり、乗算毎に６０〜１００程度の多くの演算を必要とする。他の解決方法は、ガロア体乗算を実行するためにルックアップ・テーブルを用いるものである。典型的には、この解決方法は５mpsのために１０〜２０以上のサイクルを必要とし、結果として幾分少ないが依然として例えば２０×５＝１００mps以上の非常に多くの演算を必要とする。
リードソロモン符号は、ブロードバンド・ネットワーク用の好ましい誤り制御符号の設計として広く受け入れられてきている。リードソロモン符号器及び複合器のプログラムによる実装は、チャネル状態に基づき望まれる誤り訂正能力とデータ・バンド幅とをトレードオフする唯一の融通性をシステム設計者に与えるので、魅力的な解決である。リードソロモン復号器の第１ステップは、シンドローム（syndrome）の算出である。シンドロームＳｉは、形式的には受信符号多項式Ｒを生成多項式Ｇで割った余剰（Si＝R mod G，ｉ＝（０，１，……，１５））として定義される。受信符号語の長さがＮである場合、受信符号語は多項式表現でRi＝r0XN-1＋r1XN-2＋……rN-1として表現される。シンドロームの計算は、生成多項式のi'乗根のj'累乗により定義される根の群によるガロア体上の多項式の評価に帰すると考えられる。リードソロモン・アルゴリズムの受信符号語毎に、計算すべきシンドロームは１６個存在し、それら１６要素による演算数は毎秒１．６ギガに達し、現在のマイクロ・プロセッサ上での実行は困難である。
ガロア体乗算の必要性は、通信分野の拡大と通信データ上の暗号化要求の負担と共に劇的に増大している。このことは、異なるルックアップ・テーブル群を必要とする異なるガロア体上において各ドメインの誤り訂正及び暗号化用のガロア体乗算を必要とするので、更に事態を複雑化している。
【特許文献１】米国特許第６５８７８６４号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００４】
従って本発明の目的は、新規な改良形ガロア体乗算システムを提供することにある。
【０００５】
本発明の他の目的は、従来のルックアップ・テーブルや線形フィードバック・シフトレジスタ群（LFSR）に比し迅速である新規な改良形ガロア体乗算システムを提供することにある。
【０００６】
本発明の更に他の目的は、必要な記憶装置容量を削減する新規な改良形ガロア体乗算システムを提供することにある。
【０００７】
本発明の他の目的は、毎秒当たりの要求演算数を劇的に削減する新規な改良形ガロア体乗算システムを提供することにある。
【０００８】
本発明の更なる目的は、サイクルの部分当たりの要求演算数を削減できる新規な改良形ガロア体乗算システムを提供することにある。
【課題を解決するための手段】
【０００９】
本発明は、ガロア体上の２つの係数付き多項式の積を得る乗算第１ステップとその積の所定既約多項式によるモジュロ余剰を得る除算第２ステップとからなる２ステップの単一サイクルで１つ以上のガロア体乗算を行うことによりガロア体乗算が実現できるとの知見、及び乗算の積に応答してモジュロ余剰を推定するガロア体線型変換回路とそのガロア体線型変換回路に所定既約多項式のモジュロ余剰推定用の係数群を供給する記憶回路とを有するシステムによりそのようなガロア体乗算を達成できるとの更なる知見に基づき、完成に至ったものである。
【００１０】
本発明のガロア体乗算システムは、ガロア体上の２つの係数付き多項式を乗算して積を得る乗算回路と、乗算回路に応答して多項式の積の既約多項式によるモジュロ余剰を推定するガロア体線型変換回路とを備えたものである。記憶回路により、ガロア体線型変換回路に所定既約多項式のモジュロ余剰推定用の係数群を供給する。
【００１１】
好ましい実施例では、ガロア体線型変換回路により既約多項式で多項式の積を除算してモジュロ余剰を得ることができる。乗算回路に、多項式の積の各項のためのガロア乗算用論理積（AND-logic）回路を含めることができる。また乗算回路に、多項式の積の各項対のためのガロア加算用排他的論理和（exclusiveOR-logic）回路を含めることができる。ガロア体線型変換回路には、１以上のビット・ストリーム中の複数入力ビットに応答し且つその複数入力ビットのガロア体線型変換結果を出力する複数の出力端を有するマトリクスが設けられたガロア体線型変換器を含めることができる。そのマトリクスに複数の素子を含め、各素子に排他的論理和回路とその排他的論理和回路に接続された出力端及び入力ビットの何れかに接続された入力端を有する論理積回路とをそれぞれ設けることができる。ガロア体線型変換回路には複数のガロア体変換装置を含め、記憶回路によりガロア体変換装置に係数群を並列に供給することができる。ガロア体線型変換回路に、ガロア体変換装置の各々にそれぞれ結合された複数の記憶装置を含めることができる。その場合は記憶回路により、論理積回路の入力端に、複数入力ビットの複数サイクルによるガロア体線型変換を単一サイクルで得るための係数群を供給してマトリクスに設定することができる。
【発明を実施するための最良の形態】
【００１２】
ガロア体GF(n)は、その上で２つの二項演算（加算及び乗算）が行える元の集合である。加算及び乗算は交換法則、結合法則及び分配法則を満たさねばならない。有限数の元からなる体は有限体である。２を法とするモジュロ加算及び２を法とするモジュロ乗算の下で２個の元からなる体は集合{0,1}であり、ガロア体GF(2)と表される。２を法とするモジュロ加算及び乗算は、以下の表１のように定義される。第１行及び第１列は、ガロア体加算器及び乗算器の入力を示す。例えば、１＋１＝０、１＊１＝１である。
【００１３】
【表１】
2005512183.tif 000003
【００１４】
一般的に、ｐが任意の素数であれば、ガロア体GF(p)は元の個数ｐの有限体であり、ガロア体GF(pm)は元の個数pmの拡大体であると考えることができる。また、ガロア体の様々な元を、その体上の１つの元αを異なる冪乗とすることにより、αの様々な冪乗として生成できる。例えば、ガロア体GF(256)は、原始元αを２５６種類の異なる冪乗とすることにより生成された２５６の元を有する。
【００１５】
更に、ガロア体GF(2)に属する二進数を係数とする多項式を考える。ガロア体GF(2)上の次数ｍの多項式は、ガロア体GF(2)上の０より大きくｍより小さい次数の多項式で割り切れない場合は、既約多項式と呼ばれる。多項式F(X)＝X2＋X＋1は、XでもX＋1でも割り切れないので既約多項式である。X2m-1＋1の因数である次数ｍの既約多項式は、原始多項式として知られている。所与のｍに対し、１つ以上の原始多項式が存在する場合がある。多くの通信標準で頻繁に用いられるｍ＝８の原始多項式の一例は、F(X)＝x8＋x4＋x3＋x2＋x＋1である。
【００１６】
ガロア体上の加算は、モジュロ加算と同じであるから、ソフトウェア内に容易に実装できる。例えば、２９及び１６がガロア体GF(28)の２つの元である場合、それらの加算は(1)式のような排他的論理和（XOR）演算で簡単に行える。
【００１７】
他方、ガロア体上の乗算は、以下の例に示すように原始元αの繰り返し乗算によりガロア体GF(24)の全ての元を算出せねばならないので、少し複雑である。ガロア体GF(24)の元を生成するため、ｍ＝４の原始多項式G(X)として、次のG(X)＝X4＋X＋1を選ぶ。乗算結果がガロア体の元となるように乗算をモジュロ演算とするため、次の恒等式F(α)＝α4＋α＋1＝０を用いて、５番目ビット・セット付きの元を４ビットの結果に表現し直す。この恒等式は、α4＝α＋1での置き換えのため、ガロア体上の異なる元を形成する際に繰り返し使用される。このようにして、ガロア体上の元は(2)式のように列挙できる。(2)式においてαはガロア体GF(24)の原始元αである。αを２とすると、ガロア体GF(24)上の元は(3)式のようになる。
【００１８】
【数２】
2005512183.tif 000004
【００１９】
ガロア体上の多項式の乗算は、２つの基本ステップで実装できると考えられる。第１ステップは、代数的に拡張された多項式生成物c(x)＝a(x)＊b(x)の算出であり、類似の冪乗を（対応する項の間の排他的論理和（XOR）演算に対応する加算により）集積してc(x)とする。例えば、c(x)＝（a3x3＋a2x2＋a1x1＋a0）＊（b3x3＋b2x2＋b1x1＋b0）の積は、C(x)＝c6x6＋c5x5＋c4x4＋c3x3＋c2x2＋c1x1＋c0となる。ここで係数c6、c5、c4、c3、c2、c1、c0は表２（チャート１）の通りである。
【００２０】
【表２】
2005512183.tif 000005
【００２１】
第２ステップは、c(x)をp(x)で割った余剰d(x)（d(x)＝c(x) modulo p(x)）の算出である。実例で説明すると乗算は、多項式の積を既約多項式で割った余剰の算出により実行される。例えば、既約多項式をm(x)＝x8＋x4＋x3＋x＋1とした場合、{57}＊{87}＝{c1}は表３の通りとなる。
【００２２】
【表３】
2005512183.tif 000006
【００２３】
この解決方法を示す図１の改良形ガロア体乗算システム10は、R1レジスタ14の多項式x0〜x7及びR0レジスタ16の多項式y0〜y7の２つのガロア体上の２つの係数付き多項式を乗算して積を得る乗算回路12を含む。乗算回路12は、実際には複数の乗算素子12a、12b、12c、……、12nを含む。
【００２４】
各項は記号＊で表される論理積機能を含み、各項対は記号
2005512183.tif 000007
で表される排他的論理和で結合される。表２（チャート１）に示されたこの積は、それぞれ１５×８の素子35を有する複数のガロア体線型変換器装置18a、18b、18c、……、18nが設けられたガロア体線型変換器回路18に供給され、そのガロア体線型変換器回路18が乗算回路12の積に応答して多項式の積の所定既約多項式によるモジュロ余剰を推定する。係数x0、y0の乗算を装置18aで、係数x1、y1の乗算を装置18bで、係数x2、y2の乗算を装置18cで、係数xn、ynの乗算を装置18nでそれぞれ実行する。この独特のガロア体線型変換器回路及び各変換器装置における操作は、ここにその全体を援用するステイン等の米国出願「ガロア体線形変換器」の明細書（特許文献１参照）に詳述されている。ガロア体線型変換器装置の各々により、多項式の積を既約多項式で除算してモジュロ余剰を推定する。その既約多項式は、例えば表４（チャート２）に示した何れかとすることができる。
【００２５】
【表４】
2005512183.tif 000008
【００２６】
ガロア体GF(28)として例示したガロア体乗算器は、表４（チャート２）に示した条件下で28の全ての累乗を実行できる。より次数の低い多項式に対してはその選択次数より高い次数の係数をゼロとすればよく、例えばガロア体GF(25)を実装する場合はGF(25)とGF(28)との間の係数をゼロとする。こうすることにより、そのレベル以上の予測値は生成されない。
【００２７】
特定例として、GF(28)グループ中の既約多項式又は原始多項式0x11Dを選択したとする。その特定の原始多項式又は既約多項式のモジュロ余剰推定用の係数群を、記憶回路20からガロア体線型変換器回路に供給する。既約多項式0x11Dのガロア体GF(28)用として、記憶回路20は図１Ａに示すマトリクス設定値を作成する。同図において、各線の交点22はガロア体線型変換器装置18a、18b、18c、……、18nの素子35（図４参照）を表す。各交点における黒丸24は、記憶回路20の関連する記憶装置26内の信号'１'の存在により活性化された素子を示す。図示例の列28は、単一サイクルで既約多項式のモジュロ余剰推定値を作成するための信号'１'の適切なパターンを供給する記憶回路20の記憶装置26のプログラミングを示す。図１Ａに示すマトリクスは、１５個の入力端と８個の出力端との配列である。８個の出力端は１バイトを表し、１５個の入力端c0〜c14は余剰結果が８ビット内に収まるようにモジュロ（the modulo）より１次元小さくしている。本発明によるガロア体乗算の一例は、表５のように行われる。
【００２８】
【表５】
2005512183.tif 000009
【００２９】
図２に示すように、多項式乗算回路12の各素子29は、それぞれ多項式の各項に対応する複数の論理積ゲート30と、それぞれ多項式の各項対に対応する排他的論理和ゲート32とを含む。論理積ゲート30で乗算を実行し、排他的論理和ゲート32で加算を行う。ガロア体線型変換器装置18の素子35（図４参照）は、先行素子から入力信号Ｉを受け取り、後続素子に出力信号を供給する。先頭素子の入力端は接地する。図３に示す記憶回路20の各素子33は、データのＤ入力端とWrのクロック入力端とEnableのＱ出力端とが設けられたフリップ・フロップ34を含む。ガロア体線型変換器回路及びそのガロア体線型変換器回路の１以上の装置の各素子は、図４に示すように論理積ゲート36と排他的論理和ゲート38とを有する素子35を含む。
ここにその全体を援用した２００２年１月１８日出願のステイン等の米国出願「ガロア体線形変換器」の明細書（特許文献１参照）でも説明したように、各素子29、33及び35の図示例による特定の構成は本発明を限定するものではない。例えば記憶装置33はフリップ・フロップにより実現する必要はなく、他の記憶装置を使用することができる。図２及び図４では、素子29及び35がそれぞれ論理積ゲート及び排他的論理和ゲートを必要としているが、排他的論理和ゲート及び論理積ゲートと同様のブール代数機能を実行できる論理回路であれば、特定の排他的論理和ゲート又は論理積ゲートを必要としない他の様々な方法で素子を実装することができる。例えば、論理積機能を実行する図４Ａの２対１入力のマルチプレクサ37を用いれば、特定の論理積ゲートがなくても論理積機能を達成できる。
【００３０】
ガロア体線型変換器回路18は、図５に示すデジタル信号処理装置（DSP）40又は集積回路で実現された汎用マイクロ・プロセッサ等のプログラム論理装置内の機能ユニットとして実装することができる。この機能ユニットは、バス42及び44上で適切な命令をユニットに指令する処理装置の命令によって操作する。ユニットの入力データ又は出力データの流れは、ガロア体線型変換器回路18が演算論理回路48自体の一部として機能するように、オンチップ・データレジスタ46を用いて行われる。
ガロア体線型変換器回路18と演算論理回路48付き乗算回路12との組み合わせは、単に誤り訂正や暗号だけでなく、様々な幅広いアルゴリズムの実装を可能とする従来の操作と共にガロア体乗算システムの実行を可能とするので、一層融通性の高い機能を達成可能とする。単一の記憶回路20で各ガロア体線型変換器装置18a、18b、18c、……、18nの各々の値を設定することは、２つの理由で有利である。ハードウェアを節約すると共に、１回の操作によって同時に単一サイクルで全ての値を設定することが可能となる。このことは、入力信号に制約がある場合にとくに有用である。例えば、サイクル毎の入力が３２バイトに制限されている場合は、装置18a、18b、18c、……、18nの各々の設定に多数のサイクルが必要となり得るが、本発明によれば必要に応じて各ガロア体線型変換器装置18a、18b、18c、……、18nに個別の記憶装置20a、20b、20c、……、20nを結合させることを検討することができる。
【００３１】
図６に示すようにガロア体線型変換器回路18を、単に演算論理ユニットと結合するだけでなく、演算論理ユニットの一部分を用いて実装することができる。すなわち、装置18'a、18'b、18'c、……、18'nを、演算論理回路48の一部分48'a、48'b、48'c、……、48'nにより構成することができる。
【００３２】
本発明のある特色を一部の図に示し他のものに示さなかったが、これは便宜上のことに過ぎず、本発明の各特色は他の任意の若しくは全ての諸特色と組合せることができる。本文で用いた「含む」、「からなる」、「有する」、「と共に」の語は、広義且つ包括的に解すべきであり物理的な相互関係に限定されない。更に、本出願で開示した実施例は、可能な実施態様に過ぎないものと理解すべきではない。当業者は、特許請求の範囲内において他の諸実施例に想到し得るであろう。また、添付図に示す好ましい実施例から当業者は他の目的、特色、及び利点を見出すであろう。
【図面の簡単な説明】
【００３３】
【図１】本発明のガロア体乗算システムの図式的ブロック図である。
【図１Ａ】図１中のガロア体線形変換器の図式的説明図であり、その素子群のプログラミング及び推定値を得るための関連する記憶素子群を表す。
【図２】ガロア体GF(2n)内の係数付き多項式を乗算する図１の乗算回路用の多孔式乗算素子の図式的説明図である。
【図３】図１の記憶回路用の記憶装置の図式的説明図である。
【図４】図１のガロア体線形変換回路の素子の図式的説明図である。
【図４Ａ】特別なANDゲートなしに論理的AND演算を実行するガロア体線形変換器装置の他の構成の図式的説明図である。
【図５】デジタル信号処理装置と組み合わせた本発明のガロア体乗算システムの図式的説明図である。
【図６】ガロア体演算論理回路に組み込んだ本発明のガロア体乗算システムの図式的ブロック図である。
【符号の説明】
【００３４】
10…乗算システム        12…乗算器回路
14…レジスタ            16…レジスタ
18…ガロア体線形変換器回路
18a、18b、18c、18n…線型変換器装置（ユニット）
20…記憶回路
20a、20b、20c、20n…記憶装置
22…交点                24…黒丸
26…記憶素子
28…列                  29…乗算器回路素子
30…論理積（AND）ゲート
32…排他的論理和（XOR）ゲート
33…記憶回路素子        34…フリップ・フロップ
35…線型変換器素子      36…論理積ゲート
37…マルチプレクサ      38…排他的論理和ゲート
40…デジタル信号処理装置
42…バス                44…バス
46…レジスタ            48…演算論理装置（ユニット）
【図１】
2005512183.tif 000010
【図１Ａ】
2005512183.tif 000011
【図２】
2005512183.tif 000012
【図３】
2005512183.tif 000013
【図４】
2005512183.tif 000014
【図４Ａ】
2005512183.tif 000015
【図５】
2005512183.tif 000016
【図６】
2005512183.tif 000017
【国際調査報告】
2005512183.tif 000018