(57)【特許請求の範囲】
【請求項１】
第１と第２のオペランドを乗算するためのガロワ体乗算器であって、該第１と第２のオペランドは選択されたガロワ体において許された数の組の内の数であり、
前記第１のオペランドを整列されたビット位置の最も左のビットにシフト・アップし、そして前記シフトされた第１のオペランドを出力に提出する第１のシフト・アップ回路と、
第２のオペランドをビット・バイ・ビット方式で前記第１のシフト・アップ回路の出力の前記左にシフトされた第１のオペランドと論理積を取り、順番に配列された中間出力を作るＡＮＤゲートと、
前記選択されたガロワ体の原始多項式に対応した原始値を整列されたビット位置の最も左のビットにシフト・アップし、そして前記シフトされた原始値を出力に提出する第２のシフト・アップ回路と、
最上位ビットから最下位ビットまで順番に配置され、前記複数の中間出力と前記シフトされた原始値を受け取る複数の排他的論理和ゲートであって、前記連続した複数の排他的論理和ゲートの第１の排他的論理和ゲートは第１の前記中間出力の２つの最上位ビットを結合して部分和を作り、
前記連続した複数の排他的論理和ゲートのそれぞれお互いの排他的論理和ゲートは、前記シフトされた原始値に応じて、前記複数の排他的論理和ゲートの前方のものからの部分和を対応する前記中間出力と結合して部分和を作り、そして
前記連続した複数の排他的論理和ゲートの最後の排他的論理和ゲートは、最後の部分和を作る、前記複数の排他的論理和ゲートと、
前記最後の部分和を整列されたビット位置の最も右のビットにシフト・ダウンし、前記第１と第２のオペランドのガロワ体の積を作るシフト・ダウン・ゲートと
を備えたガロワ体乗算器。
【請求項２】
第１と第２のオペランドを乗算するためのガロワ体乗算の方法において、該第１と第２のオペランドは選択されたガロワ体において許された数の組の内の数であり、
前記ガロワ体の第１のオペランドを整列されたビット位置の最も左のビットにシフト・アップするステップと、
前記第２のオペランドと前記シフトされた第１のオペランドとでビット・バイ・ビットで論理和を取るためにＡＮＤゲートを動作させ、複数の中間結果を作るステップと、
前記選択されたガロワ体の原始多項式に対応したディジタル原始値を整列されたビット位置の最も左のビットにシフト・アップするステップと、
前記複数の中間出力と前記シフトされた原始値の最上位ビットから最下位ビットまで連続した排他的論理和オペレーションを行うステップであって、連続オペレーションの第１の排他的論理和オペレーションは前記シフトされた原始値に応じて前記中間出力の第１の２つの最上位ビットを結合して部分和を作り、
連続オペレーションのそれぞれ互いの排他的論理和オペレーションは、前記シフトされた原始値に応じて、連続オペレーションの前方のものからの部分和を対応する前記中間出力と結合して部分和を作り、そして
連続オペレーションの最後の排他的論理和オペレーションは、最後の部分和を作る、前記ステップと、
前記連続操作の最後の排他的論理和オペレーションの前記部分和を整列されたビット位置の最も右のビットにシフト・ダウンし、前記第１と第２のオペランドのガロワ体の積を作るステップと
を備えたガロワ体乗算の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、ガロワ体の演算装置及び方法に関し、特に多次元のガロワ体乗算器及びガロワ体乗算の方法に関する。
【０００２】
【従来の技術】
ガロワ体演算は、ガロワ体内の２つの任意数上で実行される任意のオペレーションがガロワ体に、ある数を生成させるような巡回有限体演算(cyclic finite field arithmetic)である。即ち、ガロワ体内の２つの任意数上で実行されてガロワ体外のある数を発生し得るオペレーションは、存在しない。有限体演算は下記の表に示す範囲の数からなる実数を用いる。例えば、０から７（０，１，２，３，４，５，６，７）までの整数範囲は、このガロワ体が８つの元を有するので、ＧＦ（８）のガロワ体表現即ち表示を有し、一方整数０〜１の範囲は、ガロワ体が単なる２元を有するので、ＧＦ（２）のガロワ体を有する等である。加えて、ディジタル・システムは複数のビットによりデータを送信する。これらのビットは、二進数であるので、２値のうちの１つ、０か又は１のみを取ことができる。これらのビットを互いにグループ化して１つのシンボルを形成することは、ディジタル・システムにおいて一般的なことである。これらのグループ化は全て２の累乗に基づいている。表１はディジタル・シンボル対ＧＦ表示を記載している。
【０００３】
【表１】
0004210378.tif 000002
【０００４】
与えられた任意のガロワ体の有限体における数を表すためにいくつかの方法がある。例えば、表２に示すデータは、ＧＦ（８）の整数、二進及び多項式表示を示す。
【０００５】
【表２】
0004210378.tif 000003
【０００６】
加えて、各ガロワ体は１又はそれより多くの原始多項式を有し、これらの原始多項式は、連続的な特定の整数集合がどの程度大きいのかに従って、更に１又はそれより多くの素数を有する連続的な特定の実整数集合に似ている。原始多項式ｐ（ｘ）は、各体に関して演算関数を定義するために用いられる多項式である。例えば、ガロワ体演算では、算術演算のように、交換法則、結合法則等のようにある数学的な特性が存在する。従って、ガロワ体内の任意の２つの元の和又は積は何であるかを判断するときに、このような法則を適用した後であれば、和及び積はガロワ体の外に存在することになり、その和又は積は予め定めた原始多項式により割り算される。このようにしてガロワ体が保存される。表３はＧＦ（８）からＧＦ（２５６）までに関する全ての原始多項式の整数表現を記載している。
【０００７】
【表３】
0004210378.tif 000004
【０００８】
以上の表から明らかなように、ガロワ体が小さいためにＧＦ（８）及びＧＦ（１６）に関してただ一つの原始多項式が存在する。しかしながら、ＧＦ（１２８）は９つの原始多項式を有し、またＧＦ（２５６）は８つの原始多項式を有する。先に述べたように、これらの整数表現はそれぞれ対応する多項式表現を有する。例えば、ＧＦ（２５６）用の１つの原始多項式ｐ（ｘ）は２８５であり、これはｐ（ｘ）＝ｘ8 ＋ｘ4 ＋ｘ3 ＋ｘ2 ＋１に対応する。
【０００９】
有限体における乗算は、原始多項式を使用して容易に計算される。下記の例では、表４及び５における乗算テーブルを構成するためにＧＦ（８）及びｐ（ｘ）＝ｘ３  ＋ｘ  ＋１を使用する。この原始多項式を使用して積又は和の結果を再びガロワ体に変形即ち「保持」する。
【００１０】
【数１】
0004210378.tif 000005
ただし、ｘ4 はＧＦ（８）の構成要素ではない。そのときは、原始多項式ｐ（ｘ）を多項式割り算に使用して下記剰余を生成する。
【００１１】
【数２】
0004210378.tif 000006
【００１２】
特定のＧＦの関して１以上の原始多項式が存在していても、同一の原始多項式を使用して乗算テーブル全体／ＧＦを生成する。
【００１３】
【表４】
0004210378.tif 000007
【００１４】
【発明が解決しようとする課題】
ガロワ体（ＧＦ）乗算は、重要かつ必要な機能である、即ちリード・ソロモン（ＲＳ）符号において多数回実行される。ＲＳ符号は、ディジタル・データ伝送のフィードフォワード誤り訂正ツールとして、衛星、モデム、オーディオ・コンパクト・ディスク及びセット・トップ・ボックスのような多くの通信アプリケーションに使用されている。これらのアプリケーションは、それぞれが異なる標準を有する。各標準は、シンボル・サイズ、ＧＦ及び原始多項式を定義している。各アプリケーションは、固有のＧＦ乗算器、又は少なくともシンボル・サイズ、使用されるガロワ体及び原始多項式のサイズに従って生成されるべき固有の構成を有したＧＦ乗算器を必要とする。費用効果的な方法により全て異なる標準を実施できるＧＦ乗算器は存在していなかった。
【００１５】
【課題を解決するための手段】
ＧＦ（８）からＧＦ（２５６）までのガロワ体用の多次元ＧＦ乗算器の一実施を開示する。このＧＦ乗算器は、異なる複数のシンボル・サイズ、異なる複数のＧＦ、及び異なる複数の原始多項式を有する標準のように、異なる多くの通信標準をサポートすることができる。ＧＦ乗算器の一実施が異なる全てのガロワ体サイズを実行可能にする鍵は、更に以下の項において説明し、かつ図１，図３及び図６に示すように、ＧＦのサイズに従って、入力オペランドＢ及び原始多項式ＰＰ信号を左にシフトし、かつ出力ＺＯを右にシフトすることである。これらの信号をシフトすることにより、ＭＵＬＴ  ＸＯＲ（多数の排他的論理和）アレーが全ての体上で単に２つだけのＸＯＲゲート／ブロックの最小遅延を有する正確に同一のハードウェアにより、動作できるようにする。換言すれば、各ＭＵＬＴ  ＸＯＲブロックのクリティカル・パスは単なる２つのＸＯＲゲートである。提供される解決方法は費用効果的な乗算器構成となる。
【００１６】
【発明の実施の形態】
表３に記載した全部で２５の原始多項式、及び８と２５６との間の全てのＧＦについて動作するガロワ体乗算器を開示する．従って、ＧＦ乗算器の一実施は，ｐｐ（１２）として示した任意の（特定のＧＦ用の）ｐ（ｘ）、入力としての特定のＧＦ（１４）、並びに特定のＧＦ内の元となるＡ及びＢオペランド（１６）によるＧＦ乗算を計算できる必要がある。ブロック図１に最高レベルのブロックを示す。ＧＦ（８）は二進数０００００１０００に等しく、またＧＦ（２５６）は二進数１００００００００に等しい。下位ビット（２：０）は一定であり、この回路では必要でないが、明確にするために示されている。
【００１７】
図２はＢ「シフト・アップ・ブロック」（１８）及び６４  ＡＮＤ（ゲート）ブロック（２０）についてのブロック図を示す。この実施例において、Ｂシフト・アップ・ブロック（１８）は、ＧＦの相対サイズに従って、Ｂオペランド（１６）をある位置数だけ左へシフトさせ、次いで下位ビットをゼロ（０）にセットする。ＧＦ（２５６）のときは、Ａオペランド及びＢオペランド（１６）がそれぞれ８ビットであるので、シフトは不必要であり、また８ビットが出力されるので、シフトは不必要である。７ビット・オペランド（１６）に対応するＧＦ（１２８）のときは、７ビットを入力し、かつ８ビット出力を得るので、Ｂ（６：０）が左へ１ビット・シフトされ、かつＢ  ＴＭＰ（０）が０にセットされる。６ビット・オペランド（１６）に対応するＧＦ（６４）のときは、Ｂ（５：０）が左へ２ビット・シフトされ、かつＢ  ＴＭＰ（１：０）（ビット位置０及び１）が０にセットされる。このアップ・シフト・パターンは、同一の形式で他の全ての体に対して実行される。更に、図４に示すように、代わってそれぞれの及びあらゆるＭＵＬＴ  ＸＯＲブロックにおいてシフト・オペレーションを実行するのに対し、オペランド・レベルにおいて、原始多項式レベルにおいて、及び最後にＭＵＬＴ  ＸＯＲブロックの出力において、シフト・オペレーションを実行する大きな利点がある。乗算器内の前段でシフト・オペレーションを実行することにより、実行されるべきシフトをより少なくするので、より小さな、かつより簡単な乗算器に帰結する。
【００１８】
図２は更に６４  ＡＮＤブロック（２０）のブロック図も示している。このＡＮＤブロック（２０）は６４  ＡＮＤゲートを含む。Ａ（７：０）とＢ  ＴＭＰ（７：０）とのあらゆる可能組み合わせは、相互に論理積が取られる。Ａ７（７：０）はＡ（７）とＢ  ＴＭＰ（７：０）の全８信号との論理積の出力である。
Ａ６（７：０）はＡ（６）とＢ  ＴＭＰ（７：０）の全８信号との論理積の出力である。このパターンの論理積はＡ５、Ａ４、Ａ３、Ａ２、Ａ１及びＡ０について続けられ、Ａ０〜Ａ７（７：０）（２２）の出力を発生し、これらは図４に示すように後段における入力となる。
【００１９】
図３に示すように、原始多項式ｐｐ（７：０）（１２）上で独立してシフト・アップ・オペレーションが実行される。原始多項式（１２）は、図２に示したＢオペランドのシフト・アップ・ブロックに開示し、かつ説明したＧＦ内のビット数と比較したときに、原始多項式が備えているビット数に従って、ある位置数がシフト・アップされる。このブロック機能は、図２に示したＢシフト・アップ・ブロックと同一であり、Ａ０〜Ａ７（７：０）（２２）のように、図４に示した後段に対する入力となるＰ  ＴＭＰ（７：０）を生成する。
【００２０】
図４はＭＵＬＴ  ＸＯＲアレー（２６）を示す。ＧＦ（１２８）を使用する例によれば、このアレーは、入力としてＰ  ＴＭＰ（２４）及びＡ０〜Ａ７（７：０）（２２）、及び出力としてＺ０〜Ｚ６（７：０）（２８）を有する７ＭＵＬＴ  ＸＯＲブロック（３０）からなる。１つのＭＵＬＴ  ＸＯＲブロック（３０）の論理的な構成要素及び構成を図５に示す。図５に示すように、ＭＵＬＴ  ＸＯＲブロック（３０）に対する入力は、Ｐ  ＴＭＰ（２４）のＡ０〜Ａ７（７：０）（２２）及びＺＩ（３２）信号である。各ＭＵＬＴ  ＸＯＲブロック（３０）において、Ｐ  ＴＭＰ（２４）入力信号は、図３に示すように、原始多項式（１２）のシフト・アップ・ブロックの結果であり、Ａ０〜Ａ７（２２）は以下のうちの１つ、Ａ６、Ａ５、Ａ４、Ａ３、Ａ２、Ａ１又はＡ０であり、入力信号は以下のうちの１つ、Ａ７、Ｚ６、Ｚ５、Ｚ４、Ｚ３、Ｚ２、Ｚ１又はＺ０である。各ＭＵＬＴ  ＸＯＲブロック（３０）の出力は出力信号ＺＯ（２８）であり、出力信号ＺＯ（２８）は以下のうちの１つ、Ｚ６、Ｚ５、Ｚ４、Ｚ３、Ｚ２、Ｚ１又はＺ０となる。勿論、正確な入出力信号は、図４のブロック内でいずれのＭＵＬＴ  ＸＯＲブロック（３０）が動作しているかによる。
【００２１】
ＭＵＬＴ  ＸＯＲブロック（３０）はいくつかの機能を実行する。各ブロックは２列のＸＯＲゲート（３４）を有する。これらのＸＯＲゲート（３４）は各ビットにＧＦ（２）加算を実行する。この加算は、有限体の巡回特性に対応するシフトのために、各ブロックにおいて暗黙的に左へ１ビットのシフトとなる。前のブロックの最上位ビット（ＭＳＢ）がハイ、即ちＺ６  ７であれば、現在ブロックは原始多項式（Ｐ  ＴＭＰ（７：０））（２４）により多項式割り算を実行するためにレディー（可能状態）でなければならない。前のブロックのＭＳＢは、図５に示すように、原始多項式（Ｐ  ＴＭＰ（７：０））（２４）と論理積が取られ、その中間結果は結果Ｚ０と排他的論理和が取られる。これらの機能は、図４に示すように、７ブロックに対応して７回繰り返される。
【００２２】
ＧＦ（２５６）乗算のときは、７ＭＵＬＴ  ＸＯＲブロック（３０）を必要とする。ＧＦ（１２８）乗算のときは、６ＭＵＬＴ  ＸＯＲブロック（３０）を必要とするだけである。ＧＦ（６４）乗算のときは、５ＭＵＬＴ  ＸＯＲブロック（３０）を必要とするだけである。このパターンは小さいガロワ体の全てについて繰り返される。一つの実施が異なる全てのＧＦサイズについて実行できるようにする鍵は、以上及び以下の項で説明しているように、また図１，図３及び図６に示したように、全てＧＦのサイズに従って、入力オペランドＢ（又はオペランドＡ）（１６）信号及び原始多項式ｐｐ（１２）信号を左へシフトし、また中間出力Ｚ０（２８）を右へシフトさせることである。以上で認識された信号のシフトは、設計が同一の７ＭＵＬＴ  ＸＯＲアレーを含められるようにする。加えて、この設計は、単なる２つのＸＯＲゲート／ブロックの最小遅延を有する正確に同一のハードウェアにより全ての体上で動作することができる。換言すれば、各ＭＵＬＴ  ＸＯＲブロックのクリティカル・パスは、単なる２つのＸＯＲゲートである。
【００２３】
図６はＺＯシフト・ダウン・ブロック（３６）又は右シフト・ブロックを示す。ＺＯシフト・ダウン・ブロック（３６）は、原始多項式（１２）の相対サイズに従って中間出力Ｚ０（２８）を右へシフトさせ、次いで最上位ビットを０にセットする。ＧＦ（２５６）のときは、図１及びＢオペランドを参照して説明したように、シフトは不要である。ＧＦ（１２８）のときは、Ｚ０（７：１）を右へ１ビットだけシフトし、かつ出力（３８）のＹ（７）を０にセットする。ただし、Ｙ（７：０）すなわち、出力（３８）はＺＯシフト・ダウン・ブロック（３６）の出力である。ＧＦ（６４）のときは、ＺＯ（７：２）を右へ２ビットだけシフトし、かつＹ（７：６）を０にセットする。このようにして、このダウン・シフトのパターンを他の全ての体について実行する。
【００２４】
図６において説明したブロックは、ＶＨＤＬによりモデル化された。ＶＨＤＬモデルはＡ、Ｂ、ＧＦ及びｐ（ｘ）の可能な組み合わせの全てにより模擬され、その結果はＣモデルに対して検査された。６８７，４２４可能組み合わせが存在する。
【００２５】
複数のＶＨＤＬモデルＬがテキサス・インスツルメンツのＴＳＣ５０００ＵＬＶ  ＡＳＩＣライブラリを使用して統合された。図５にＭＵＬＴ  ＸＯＲブロック（３０）に関する統合結果を示す。ＭＵＬＴ  ＸＯＲブロック（３０）は、４３．７５ゲートを必要とし、かつ最悪ケースの遅延０．６０ｎｓを有する。図４に示すように、ＭＵＬＴ  ＸＯＲアレー構造を保持しながら、残りの設計を統合すると、５６３．７５ゲートによる設計に帰結した。この設計はＡ入力及びＢ入力からＹ出力まで最悪ケースの遅延６．８３ｎｓを有する。ＧＦ又はＰＰからＹ出力までの遅延は、僅かに大きくなるが、全てのアプリケーションの観点からは重大ではなく、ＧＦ及びＰＰは特定のエンコード又はデコードに関して一定のままとなる。
【００２６】
第２の好ましい実施例はブロックの「平坦化」を伴う。ブロックの「平坦化」は全ての小さな機能ブロックを一つの大きなブロックに組み合わせ、かつ冗長な機能を除去する、又は多数の機能をより小さな領域かつ／又は小さな回路遅延を有し得る１つの大きく、より効率的な機能により置換する方法である。この実施は、６５５．５０ゲートを必要とし、かつ最悪ケースの遅延５．３４ｎｓを有する設計に帰結する。
【００２７】
以上の項で説明したこの発明の第１及び第２の実施例による実施は、ガロワ体８、１６、３２、６４、１２８及び２５６に関するものである。２の累乗を有する更なるＧＦが付加されてもよい。更に、いくつかのＧＦは、面積を節約するため、かつ／又は回路のクリティカル遅延を減少させるために除去されてもよい。例えば、ＧＦ（２５６）は８ビット・オペランド及び７ＭＵＬＴ  ＸＯＲブロック（３０）を必要とする。ＧＦ（１２８）は７ビット・オペランド及び６ＭＵＬＴ  ＸＯＲブロックを必要とする。従って、ＧＦ（２５６）オペランド上で動作しない設計をしたいときは、全てのバスから１ビットを除去してもよく、また設計から１ＭＵＬＴ  ＸＯＲブロック（３０）を削除してもよい。他の例として、表３に記載された２５原始多項式が存在する。図５に示したブロックは、全て８ビット用のＡＮＤ機能を有する。全てのビットはこれらのＡＮＤゲートを有するので、８又はそれ未満の次数を有する全ての原始多項式はこの回路により実行されてもよい。加えて、アプリケーションが回路において処理できる原始多項式の数を削減させたいときは、任意の未使用ＡＮＤゲートを省略してもよい。例えば、図７に示すように、ＧＦ（２５６）のときは、ｐ（ｘ）＝ｘ8 ＋ｘ4 ＋ｘ2 ＋１。従って、０を有する全てのＡＮＤゲートを除去することができる。更に、ＸＯＲゲートに印加された０を除去してもよい。この設計は１０ゲートだけ小さくなる。これは、ここでも、面積を節約し、かつ／又はクリティカル・パスを短縮することができる。
【００２８】
以上の説明に関して更に以下の項を開示する。
【００２９】
（１）ガロワ体であって、関連されたガロワ体数、前記ガロワ体内の第１及び第２のオペランド、及び前記ガロワ体の原始多項式を有する前記ガロワ体と、前記第１のオペランドか又は第２のオペランドをシフト・アップするシフト・アップ回路と、
シフト・アップされなかったオペランドを前記シフト・アップ回路の対応する出力と論理積を取る第１のＡＮＤゲートと、
前記原始多項式をシフト・アップする第２のシフト・アップ回路と、
前記第１のＡＮＤゲートの出力値における２最上位ビットの値と、前記第２のシフト・アップ回路の対応する出力とについて動作する第１の排他的論理和ゲートと、
第２の排他的論理和ゲート及び次の排他的論理和ゲートを備え、前記第１のＡＮＤゲートの出力値における次の最上位ビットの値、前記第２のシフト・アップ回路の対応する出力、及び前記第１の排他的論理和ゲートの出力値について動作する複数の排他的論理和ゲートであって、次に連続する排他的論理和オペレーションのために前記第２の排他的論理和ゲートの出力が前記次の排他的論理和ゲートに対する次の入力となる前記複数の排他的論理和ゲートと、
前記複数の排他的論理和ゲートの前記出力をシフト・ダウンするシフト・ダウン・ゲートと
を備えたガロワ体乗算器。
【００３０】
（２）前記シフト・アップ回路は、
前記ガロワ体における元の数の値、及び前記オペランドにおける元の数の値に従って、前記オペランドの最上位ビットの値から下位ビットの値までをレジスタ内の最上位ビット位置から下位ビット位置までへシフトし、次いで前記レジスタ内のあらゆる位置を満たすために必要なゼロを加算する前記レジスタであって、前記レジスタは前記ガロワ体数のビット位置を有する
第１項記載のガロワ体乗算器。
【００３１】
（３）前記シフト・ダウン回路は、
前記ガロワ体における元の数の値、及び前記排他的論理和ゲートの前記出力における元の数の値に従って、前記排他的論理和ゲートの最下位ビットの値から前記出力値の最上位ビットまでをレジスタ内の最下位ビット位置から最上位ビット
位置までへシフトし、次いで前記レジスタ内のあらゆる位置を満たすために必要なゼロを加算する前記レジスタであって、前記レジスタは前記ガロワ体数のビット位置を有する
第１項記載のガロワ体乗算器。
【００３２】
（４）更に、シフトするオペレーション及びゼロを加算するオペレーションを実行する複数の乗算器を備えている第２項記載のガロワ体乗算器。
【００３３】
（５）更に、シフトするオペレーション及びゼロを加算するオペレーションを実行する複数のマルチプレクサを備えている第３項記載のガロワ体乗算器。
【００３４】
（６）ガロワ体乗算の方法において、
ガロワ体を供給するステップであって、関連されたガロワ体数、前記ガロワ体内の第１及び第２のオペランド、及び前記ガロワ体の原始多項式を有する前記ガロワ体を供給する前記ステップと、
前記第１のオペランドか又は第２のオペランドをシフト・アップするステップと、
シフト・アップされなかったオペランドを前記シフト・アップのオペレーションの対応する出力と論理積を取るステップと、
前記原始多項式をシフト・アップするステップと、
前記論理積オペレーションの出力値における２最上位ビットの値と、前記原始多項式の前記シフト・アップの対応する出力値との排他的論理和第１オペレーションを実行するステップと、
前記論理積オペレーションの出力値の次の最上位ビットの値と、前記原始多項式の前記シフト・アップの対応する出力値と、前記排他的論理和第１オペレーションの出力値との排他的論理和第２オペレーションを実行し、かつ前記３入力の連続的な排他的論理和を取るステップであって、前記排他的論理和第２オペレーションの前記出力値が次の排他的論理和オペレーションに対する連続的な入力となる前記ステップと、
前記排他的論理和オペレーションの出力を値をシフト・ダウンするステップと
を備えたガロワ体乗算の方法。
【００３５】
（７）前記ガロワ体における元の数の値、及び前記オペランドにおける元の数の値に従って、前記オペランドの最上位ビットの値から下位ビットの値までをレジスタ内の最上位ビット位置から下位ビット位置までへシフトするステップと、
前記レジスタ内のあらゆる位置を満たすために必要なゼロを加算するステップであって、前記レジスタは前記ガロワ体数のビット位置を有するステップと
を備えた第６項記載のガロワ体乗算の方法。
【００３６】
（８）前記ガロワ体における元の数の値、及び前記排他的論理和オペレーションの前記出力値における元の数の値に従って、前記排他的論理和オペレーションの前記出力における最上位ビットの値から最下位ビットの値を、１レジスタ内の最上位ビット位置から最下位ビット位置までへシフトするステップと、
前記レジスタ内のあらゆる位置を満たすために必要なゼロを加算するステップであって、前記レジスタは前記ガロワ体数のビット位置を有するステップと
を備えた第６項記載のガロワ体乗算の方法。
【００３７】
（９）更に、前記オペランドを多重化してゼロをシフトするオペレーション及び加算するオペレーションを実行するステップを備えた第７項記載のガロワ体乗算の方法。
【００３８】
（１０）前記複数の排他的論理和オペレーションの前記出力値を多重化してゼロをシフトするオペレーション及び加算するオペレーションを実行するステップを備えた第８項記載のガロワ体乗算の方法。
【００３９】
（１１）異なるサイズのガロワ体の乗算を可能とし、かつ単独に実施され得る多次元ガロワ体乗算の方法において、
ガロワ体、前記ガロワ体内の２つのオペランド、及び前記ガロワ体に関連された原始多項式を供給するステップと、
前記オペランドの比較サイズ及び前記ガロワ体のサイズに対して比較されるときの原始多項式に従って、前記オペランドのうちの１つ及び前記原始多項式を左へシフトさせるステップと、
前記ガロワ体のサイズに対して比較されるときの前記中間出力の比較サイズに従って、前記中間出力を右へシフトするステップと
を備えている多次元ガロワ体乗算の方法。
【００４０】
（１２）費用効果的な形式により種々のシンボル・サイズ１６、異なる複数のＧＦ１４及び異なる複数の原始多項式１２を有する多くの通信標準をサポート可能な多次元ガロワ体乗算器及びガロワ体多次元乗算の方法の実施を開示する。１つの実施が異なる全てのＧＦサイズに関して実行するのを可能にする鍵は、いずれへシフトしていても、オペランド、原始多項式又は中間出力のサイズに比較するときの前記ＧＦ１４の相対サイズに従って、２つのオペランド１６のうちの１つ及び原始多項式１２を左へシフトし、かつ前記中間出力ＺＯ２８を右へシフトすることである。以上で述べた信号のシフトは、ＭＵＬＴ  ＸＯＲアレー２６が２ゲート／ブロックの最小遅延、又は２ＥＸＯＲゲートのクリティカル遅延と正確に同一のハードウェアにより全ての体上で動作可能にさせる。
【図面の簡単な説明】
【図１】本発明の好ましい実施例によるＧＦ乗算器を示す最高レベルのブロック図。
【図２】本発明の好ましい実施例によるシフト・アップ・ブロック及び６４ＡＮＤブロックを示すブロック図。
【図３】原始多項式ｐ（ｘ）シフト・アップ・ブロックを示すブロック図。
【図４】本発明の好ましい実施例によるＭＵＬＴ  ＸＯＲアレーを示すブロック図。
【図５】本発明の好ましい実施例による図４のＭＵＬＴ  ＸＯＲアレーを示す概要ブロック図。
【図６】本発明の好ましい実施例によるシフト・ダウン・ブロックを示すブロック図。
【図７】図５に示したＭＵＬＴ  ＸＯＲアレーの変形形式を示す概要ブロック図。
【符号の説明】
１８  Ｂシフト・アップ・ブロック
２０  ６４  ＡＮＤブロック
２６  ＭＵＬＴ  ＸＯＲアレー
３０  ＭＵＬＴ  ＸＯＲブロック
３６  シフト・ダウン・ブロック
【図１】
0004210378.tif 000008
【図２】
0004210378.tif 000009
【図３】
0004210378.tif 000010
【図４】
0004210378.tif 000011
【図５】
0004210378.tif 000012
【図６】
0004210378.tif 000013
【図７】
0004210378.tif 000014