小型ガロア体乗算器エンジン
【課題】
【解決手段】 小型ガロア体並列乗算器エンジンは、乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する乗算回路と、ガロア体線形変換回路であって、既約多項式について前記多項式の積の剰余を予測するため、前記乗算回路からの乗算入力を有するガロア体線形変換回路と、第１の多項式入力および第２の多項式入力とを含み、前記ガロア体線形変換回路は、行列部および単位行列部で設定された複数のセルを含んでよく、前記単位行列部のセルは、前記乗算回路の出力が、前記既約多項式の次数未満の次数を伴う多項式である場合に剰余の予測を表す。
【解決手段】 小型ガロア体並列乗算器エンジンは、乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する乗算回路と、ガロア体線形変換回路であって、既約多項式について前記多項式の積の剰余を予測するため、前記乗算回路からの乗算入力を有するガロア体線形変換回路と、第１の多項式入力および第２の多項式入力とを含み、前記ガロア体線形変換回路は、行列部および単位行列部で設定された複数のセルを含んでよく、前記単位行列部のセルは、前記乗算回路の出力が、前記既約多項式の次数未満の次数を伴う多項式である場合に剰余の予測を表す。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は小型ガロア体乗算器エンジンに関し、具体的にはガロア体上で乗算と乗加算と乗累算とを行える小型ガロア体乗算器エンジンに関するものである。
【０００２】
本出願は、２００３年３月２４日出願済み米国特許出願第１０／３９５，６２０号、Ｓｔｅｉｎら、表題ＣＯＭＰＡＣＴ ＧＡＬＯＩＳ ＦＩＥＬＤ ＭＵＬＴＩＰＬＩＥＲ（ＡＤ−３３７Ｊ）と、２００２年１０月９日出願済み米国仮出願第６０／４１７，３８４号、Ｓｔｅｉｎら、表題Ａ ＣＯＭＰＡＣＴ ＧＡＬＯＩＳ ＦＩＥＬＤ ＭＵＬＴＩＰＬＩＥＲ（ＡＤ−３３７Ｊ）と、２００１年１１月３０日出願済み米国仮出願第６０／３３４，６６２号、Ｓｔｅｉｎら、表題ＧＦ２−ＡＬＵ（ＡＤ−２３９Ｊ）と、２００１年１１月２０日出願済み米国仮出願第６０／３３４，５１０号、Ｓｔｅｉｎら、表題ＰＡＲＡＬＬＥＬ ＧＡＬＯＩＳ ＦＩＥＬＤ ＭＵＬＴＩＰＬＩＥＲ（ＡＤ−２４０Ｊ）と、２００１年１２月１８日出願済み米国仮出願第６０／３４１，６３５号、Ｓｔｅｉｎら、表題ＧＡＬＯＩＳ ＦＩＥＬＤ ＭＵＬＴＩＰＬＹ ＡＤＤ （ＭＰＡ） ＵＳＩＮＧ ＧＦ２−ＡＬＵ（ＡＤ−２９９Ｊ）と、２００１年１２月１８日出願済み米国仮出願第６０／３４１，７３７号、Ｓｔｅｉｎら、表題ＰＲＯＧＲＡＭＭＡＢＬＥ ＧＦ２−ＡＬＵ ＬＩＮＥＡＲ ＦＥＥＤＢＡＣＫ ＳＨＩＦＴ ＲＥＧＩＳＴＥＲ-ＩＮＣＯＭＩＮＧ ＤＡＴＡ ＳＥＬＥＣＴＩＯＮ（ＡＤ−３００Ｊ）とに対して優先権を主張するものである。本出願は、さらに、２００２年１月１８日出願済み米国特許出願第１０／０５１，５３３号、Ｓｔｅｉｎら、表題ＧＡＬＯＩＳ ＦＩＥＬＤ ＬＩＮＥＡＲ ＴＲＡＮＳＦＯＲＭＥＲＥＲ（ＡＤ−２３９Ｊ）と、２００２年１月３０日出願済み米国特許出願第１０／０６０，６９９号、Ｓｔｅｉｎら、表題ＧＡＬＯＩＳ ＦＩＥＬＤ ＭＵＬＴＩＰＬＩＥＲ ＳＹＳＴＥＭ（ＡＤ−２４０Ｊ）と、２００２年８月２６日出願済み米国特許出願第１０／２２８，５２６号、Ｓｔｅｉｎら、表題ＧＡＬＯＩＳ ＦＩＥＬＤ ＭＵＬＴＩＰＬＹ／ＭＵＬＴＩＰＬＹ - ＡＤＤ／ＭＵＬＴＩＰＬＹ ＡＣＣＵＭＵＬＡＴＥ（ＡＤ−２９９Ｊ）と、２００２年５月１日出願済み米国特許出願第１０／１３６，１７０号、Ｓｔｅｉｎら、表題ＲＥＣＯＮＦＩＧ．ＵＲＡＢＬＥ ＩＮＰＵＴ ＧＡＬＯＩＳ ＦＩＥＬＤ ＬＩＮＥＡＲ ＴＲＡＮＳＦＯＲＭＥＲＥＲ ＳＹＳＴＥＭ（ＡＤ−３００Ｊ）とに対して優先権を主張するものである。
【背景技術】
【０００３】
ガロア体（Ｇａｌｏｉｓ ｆｉｅｌｄ、略称ＧＦ）での係数付き多項式の乗算は、リードソロモン（Ｒｅｅｄ Ｓｏｌｏｍｏｎ、略称ＲＳ）コーディング用の通信システムにおいて、また高度な暗号化規格（ＡＥＳ）において広く行われている。一部の場合では、基本的なガロア体乗算だけでは不十分で、より高度なガロア体演算、例えばガロア体乗累算（Ｇａｌｏｉｓ ｆｉｅｌｄｓ ｍｕｌｔｉｐｌｙ ａｎｄ ａｃｃｕｍｕｌａｔｅ、略称ＧＦ−ＭＡＣ）またはガロア体乗加算（Ｇａｌｏｉｓ ｆｉｅｌｄｓ ｍｕｌｔｉｐｌｙ ａｎｄ ａｄｄ、略称ＧＦ−ＭＰＡ）が必要とされる。ガロア体乗算は、従来のデジタル信号プロセッサ（ｄｉｇｉｔａｌ ｓｉｇｎａｌ ｐｒｏｃｅｓｓｏｒ、略称ＤＳＰ）での実行は困難で時間がかかる。ＤＳＰは、有限インパルス応答（ｆｉｎｉｔｅ ｉｍｐｕｌｓｅ ｒｅｓｐｏｎｓｅ、略称ＦＩＲ）フィルタリング、および他の乗累算（ｍｕｌｔｉｐｌｙ ａｃｃｕｍｕｌａｔｅ、略称ＭＡＣ）の多い演算用に最適化されているが、ガロア体タイプの演算を効率的に処理することはできない。アプローチの１つに、１ビットずつ処理を行う線形フィードバックシフトレジスタ（ｌｉｎｅａｒ ｆｅｅｄｂａｃｋ ｓｈｉｆｔ ｒｅｇｉｓｔｅｒｓ、略称ＬＦＳＲ）を使ってガロア体上で単純な多項式乗除算を行うというものがあるが、これは非常に緩慢な処理である。例えば、ブロードバンド通信におけるＡＥＳタイプの応用ではビットレートが最高４０メガビット／秒で、最高５百万ＧＦ乗算／秒（ＧＦ ｍｕｌｔｉｐｌｉｃａｔｉｏｎｓ ｐｅｒ ｓｅｃｏｎｄ、略称ＧＦ−ＭＰＳ）となり、各乗算が６０〜１００演算などの多数になる。別のアプローチでは、ルックアップテーブルを使ってガロア体乗算が実行される。典型的に、このアプローチは１０〜２０サイクル以上を要し、５ ＧＦ−ＭＰＳではやや低めではあるが非常に多数の演算、例えば２０×５＝１００ ＭＩＰＳ以上の結果が得られる。リードソロモン符号は、ブロードバンドネットワーク用の好適なエラー制御コーディングスキームとして広く受け入れられてきている。リードソロモン式エンコーダおよびデコーダをプログラム可能に実施するアプローチは、チャネル条件に基づいて望まれるデータ帯域幅とエラー補正能力とをトレードオフできるという独自の柔軟性をシステム設計者に提供するため、魅力的な解決法である。リードソロモンデコーディングの第１のステップは、シンドロームの計算である。シンドロームは、Ｓｉ＝Ｒ ｍｏｄ Ｇの公式で定義できる。ここで、ｉ＝（０，１…１５）である。受信された符号語は、多項式形式でＲｉ＝ｒｏＸＮ−１＋ｒ１ＸＮ−２＋…ｒＮ−１と表現される。ここで、受信語の長さはＮである。最終的には、ガロア体上におけるシンドローム計算は、生成多項式のｉ’番目の根のｊ’乗で定義される根の多項式評価につながると見なすことができる。各受信語につき、リードソロモンアルゴリズムには計算すべきシンドロームが１６あり、これにより現行のマイクロプロセッサでの演算数は１６倍の１６億／秒（ｂｉｌｌｉｏｎ ｏｐｅｒａｔｉｏｎｓ ｐｅｒ ｓｅｃｏｎｄ、略称ＢＯＰＳ）となる。ルックアップテーブルの代わりに単純な乗算を使用すると、演算率は６．４ ＢＯＰＳまで増加する。通信分野の拡張と、通信データの暗号化要件とにより、ガロア体乗算の必要性は劇的に増加しており、各ドメインエラーチェックおよび暗号化は、異なるルックアップテーブルのセットを要する異なるガロア体上のガロア体乗算を必要とするため、さらに状況を複雑にしている。ガロア体乗算器システムまたはガロア体乗算器エンジンの近年の改善により演算は高速化し格納要件も低められてはきているが、依然、より高速で低電力、小型設計のものへの需要が高い。
【発明の開示】
【課題を解決するための手段】
【０００４】
従って、本発明の目的は、新規で改善された小型ガロア体乗算器エンジンを提供することである。
【０００５】
本発明の更なる目的は、このような新規で改善された小型ガロア体乗算器エンジンを提供することにより、サイズがさらに縮小され伝搬経路がさらに短縮された結果、より小型化、単純化、および高速化した設計になることである。
【０００６】
本発明の更なる目的は、このような新規で改善された小型ガロア体乗算器エンジンを提供することにより、必要な格納量をさらに削減することである。
【０００７】
本発明の更なる目的は、このような新規で改善された小型ガロア体乗算器エンジンを提供することにより、必要な外部バスの数を削減し、付随するＤＳＰのレジスタなどの資源（リソース）をより少量使用することである。
【０００８】
本発明の更なる目的は、このような新規で改善された小型ガロア体乗算器エンジンを提供することにより、新規多項式用の再設定に必要な時間を短縮できることである。
【０００９】
本発明の更なる目的は、このような改善された新規な小型ガロア体乗算器エンジンを提供することにより、１サイクルの乗算を実行するだけでなく、乗加算および乗累算の演算も実行するという観点で、より多くの機能を提供することである。
【００１０】
本発明は、ガロア体における入力多項式の乗算機能、乗加算機能、および乗累算機能のうち１若しくはそれ以上を取得でき、軽減された外部バスおよびＤＳＰ資源の要件を有する、小型ガロア体乗算器エンジンが、乗算回路および加算器入力選択回路を使用し、ガロア体線形変換ユニットの前記乗算回路および加算器入力に適切な入力多項式を供給することによりもたらされるということと、また、行列および単位行列であって、そのセルが、前記乗算回路の出力が前記既約多項式の次数未満の次数を伴う多項式である場合に剰余の予測を表す、行列および単位行列で、ガロア体線形変換回路を設定することにより格納要件が軽減されるということと、さらに、前記乗算器エンジンを単一用途（例えば乗算、乗加算、乗累算）専用にした場合、前記加算器入力選択回路および乗算入力選択回路が排除可能になりうること、という知見に基づいている。
【００１１】
本発明は、小型ガロア体並列乗算器エンジンであって、ガロア体上の係数を伴う２つの多項式を乗算しその積を取得する乗算回路を含む小型ガロア体並列乗算器エンジンを特徴とする。また、ガロア体線形変換回路であって、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有するガロア体線形変換回路が提供される。前記乗算回路には、第１の多項式入力と、第２の多項式入力と、乗算モードでは前記第２の多項式を、乗加算モードでは前記ガロア体線形変換回路の出力を、そして乗累算モードでは前記第２の多項式を、前記乗算回路に提供する乗算器入力選択回路とが提供される。加算器入力選択回路は、前記入力多項式のガロア体乗算関数、ガロア体乗加算関数、およびガロア体乗累算関数を取得するため、前記乗算モードでは加法単位元を、前記乗加算モードでは前記第２の多項式入力を、そして前記乗累算モードでは前記ガロア体線形変換回路の出力を、前記ガロア体線形変換回路の加算入力に提供する。
【００１２】
好適な実施形態では、前記乗算回路は、ガロア乗算器を実現するため、前記多項式の積の各項用にＡＮＤ論理回路を含んでよい。前記乗算回路は、ガロア体における総和をもたらすため、前記多項式の積における項の各対に排他的ＯＲ論理回路を含んでよい。前記ガロア体線形変換回路は、セルの行列であって、各セルが排他的ＯＲ論理回路と、前記排他的ＯＲ論理回路に接続された出力を有するＡＮＤ論理回路と、入力データビットを受信するための入力とを含む、セルの行列を含んでよい。前記ガロア体線形変換回路の出力は、前記エンジンのローカルバス経由で前記乗算器入力選択回路および前記加算器入力選択回路に戻される。前記乗算器入力選択回路は、前記ガロア体線形変換回路の出力からの入力と、前記第２の多項式からの入力とを含んでよい。前記加算器入力選択回路は、前記ガロア体線形変換回路の出力からの入力と、前記第２の多項式からの入力と、制御入力とを含んでよい。各前記排他的ＯＲ論理回路は、出力が前記行列の出力に接続された最後の排他的ＯＲ論理回路と、入力が加法単位元レベルに接続された最初の排他的ＯＲ論理回路とを除いて、次に続く排他的ＯＲ論理回路の入力に接続された出力を有してよい。再設定可能な制御回路であって、所定の既約多項式に関する剰余を予測するための係数のセットを、前記ガロア体線形変換回路に供給する再設定可能な制御回路があってもよい。前記ガロア体線形変換回路は複数のガロア体変換ユニットを含んでよく、前記再設定可能な制御回路は、前記係数を並行して前記ガロア体変換ユニットに供給してよい。前記ガロア体線形変換回路は、行列部および単位行列部で設定された複数のセルを含んでよく、前記単位行列部のセルは、前記乗算回路の出力が、前記既約多項式の次数未満の次数を伴う多項式である場合に剰余の予測を表す。前記ガロア体線形変換回路は複数のガロア体変換ユニットを含んでよく、前記再設定可能な制御回路は、前記係数を並行して前記ガロア体変換ユニットに供給してよい。前記ガロア体線形変換回路は複数のガロア体変換ユニットを含んでよく、前記再設定可能な制御回路は、それぞれが各前記ガロア体線形変換ユニットに関連付けられた複数の再設定可能な制御ユニットを含んでよい。前記加法単位元レベルはヌルレベルであってよく、前記入力多項式の前記関数は１サイクルで取得されてよい。
【００１３】
また本発明は、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する乗算回路を含む小型ガロア体乗算器エンジンを特徴とする。ガロア体線形変換回路は、前記乗算回路からの乗算入力を有し、既約多項式について前記多項式の積の剰余を予測する。前記乗算回路には、第１の多項式入力と、第２の多項式入力と、入力多項式のガロア体乗算関数を取得するため前記ガロア体線形変換回路の加算入力に乗算モードで加法単位元レベルを提供する乗算器入力選択回路とが提供される。
【００１４】
また本発明は、小型ガロア体乗算器エンジンであって、ガロア体上の係数を伴う２つの多項式を乗算しその積を取得する乗算回路を含む小型ガロア体乗算器エンジンを特徴とする。ガロア体線形変換回路は、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有する。前記乗算回路には、第１の多項式入力と、第２の多項式入力と、入力多項式のガロア体乗加算関数を取得するため前記ガロア体線形変換回路の加算入力に乗加算モードで前記第２の多項式入力を提供する乗算器入力選択回路とが提供される。
【００１５】
本発明は、小型ガロア体乗算器エンジンであって、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する乗算回路を含む小型ガロア体乗算器エンジンを特徴とする。ガロア体線形変換回路は、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有する。前記乗算回路には、第１の多項式入力と、第２の多項式入力と、入力多項式のガロア体乗累算関数を取得するため前記ガロア体線形変換回路の加算入力に乗累算モードで前記ガロア体線形変換回路の出力を提供する乗算器入力選択回路とが提供される。
【００１６】
また本発明は、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する乗算回路を含む小型ガロア体乗算器エンジンを特徴とする。ガロア体線形変換回路は、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有する。前記乗算回路には、第１の多項式入力と、第２の多項式入力と、入力多項式のガロア体乗算関数およびガロア体乗加算関数を取得するため、乗算器入力選択回路であって、乗算モードでは前記第２の多項式を、そして乗加算モードでは前記ガロア体線形変換回路の出力を、前記乗算回路に提供する乗算器入力選択回路と、加算器入力選択回路であって、前記乗算モードでは加法単位元レベルを、そして前記乗加算モードでは前記第２の多項式入力を、前記ガロア体線形変換回路の加算入力に提供する加算器入力選択回路とが提供される。
【００１７】
また本発明は、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する乗算回路を含む小型ガロア体乗算器エンジンを特徴とする。ガロア体線形変換回路は、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有する。前記乗算回路には、第１の多項式入力と、第２の多項式入力と、入力多項式のガロア体乗算関数およびガロア体乗累算関数を取得するため、乗算器入力選択回路であって、乗算モードでは前記第２の多項式を、そして乗累算モードでは前記第２の多項式を、前記乗算回路に提供する乗算器入力選択回路と、加算器入力選択回路であって、前記乗算モードでは加法単位元レベルを、そして前記乗累算モードでは前記ガロア体線形変換回路の出力を、前記ガロア体線形変換回路の加算入力に提供する加算器入力選択回路とが提供される。
【００１８】
また本発明は、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する乗算回路を含む小型ガロア体乗算器エンジンを特徴とする。ガロア体線形変換回路は、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有する。前記乗算回路には、第１の多項式入力と、第２の多項式入力と、入力多項式のガロア体乗算関数およびガロア体乗累算関数を取得するため、乗算器入力選択回路であって、乗加算モードでは前記ガロア体線形変換回路の出力を、そして乗累算モードでは前記第２の多項式を、前記乗算回路に提供する乗算器入力選択回路と、加算器入力選択回路であって、乗加算モードでは前記第２の多項式入力を、そして乗累算モードでは前記ガロア体線形変換回路の出力を、前記ガロア体線形変換回路の加算入力に提供する加算器入力選択回路とが提供される。
【００１９】
また本発明は、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する乗算回路を含む小型ガロア体線形乗算回路と、既約多項式に関する多項式の積の剰余を予測するためのガロア体線形変換回路であって、行列部および単位行列部で設定された複数のセルを含み、前記単位行列部のセルは、前記乗算回路の出力が、前記既約多項式の次数未満の次数を伴う多項式である場合に剰余の予測を表す、ガロア体線形変換回路とを特徴とする。
【００２０】
好適な実施形態では、各セルはプログラム可能な排他的ＯＲセルを含んでよい。このプログラム可能な排他的ＯＲセルは、排他的ＯＲ回路およびＡＮＤ回路を含んでよい。再設定可能な制御回路であって、所定の既約多項式に関する剰余を予測するための係数のセットを、前記ガロア体線形変換回路に供給する再設定可能な制御回路があってもよい。前記ガロア体線形変換回路は、複数のガロア体線形変換回路ユニットを含んでよい。前記再設定可能な制御回路は、前記係数を並行して前記ガロア体変換ユニットに供給してよく、あるいは、前記再設定可能な制御回路は、それぞれが各前記ガロア体線形変換ユニットに関連付けられた複数の再設定可能な制御ユニットを含んでよい。
【００２１】
本発明はまた、より単純なガロア体乗算器エンジンであって、加算器入力選択回路および乗算器入力選択回路を使用することなく、乗算演算、乗加算演算、および乗累算演算から選択された演算に適合する、より単純なガロア体乗算器エンジンを特徴とする。
【発明を実施するための最良の形態】
【００２２】
本発明では、以下に開示する好適な実施形態以外の他の実施形態が可能であり、種々の方法で実施または実行することができる。このように、本発明はその用途において、以下の説明に記載され図面に例示された構造の詳細およびコンポーネントの配置に限定されるものではないことは言うまでもない。
【００２３】
ガロア体ＧＦ（ｎ）は、２つの２項演を実行できる算元（要素）のセットである。加算および乗算は、交換法則、結合法則、および分配法則を満たさなければならない。有限数の元を伴う体は、有限体である。２元体の例には法２（ｍｏｄ ２）の加算および法２の乗算におけるセット｛０，１｝があり、これはＧＦ（２）と表される。この法２の加算演算と乗算演算とは、次の表により定義される。第１行および第１列は、ガロア体加算器およびガロア体乗算器への入力を示している。ここでは例えば１＋１＝０および１＊１＝１が成り立つ。
【００２４】
【数１】
【００２５】
【数２】
【００２６】
一般に、ｐが任意の素数である場合、ＧＦ（ｐ）はｐ個の元を伴う有限体であり、ＧＦ（ｐｍ）はｐｍ個の元を伴う拡大体であると示すことができる。また、体の種々の元は、その体の元の１つであるαに種々の指数を伴わせ、この指数を異なる値に増加させることにより生成できる。例えば、ＧＦ（２５６）は２５６個の元を有し、これらはすべて原始元αの指数を２５６まで増加させることにより生成できる。
【００２７】
また、二項係数を伴う多項式はＧＦ（２）に属する。ＧＦ（２）上のｍ次多項式は、ＧＦ（２）上のｍ次未満の任意多項式で割り切れず、且つゼロより大きい場合、既約であると言うことができる。多項式Ｆ（Ｘ）＝Ｘ２＋Ｘ＋１はＸでもＸ＋１でも割り切れないため、既約多項式である。Ｘ２ｍ−１＋１を除算するｍ次の既約多項式は、原始多項式として知られている。所与のｍに対しては、原始多項式が２つ以上ある可能性がある。大部分の通信規格で頻繁に使われるｍ＝８の原始多項式の例は、Ｆ（Ｘ）＝０ｘ１１ｄ＝ｘ８＋ｘ４＋ｘ３＋ｘ２＋１である。
【００２８】
ガロア体の加算は、モジュロ（剰余）加算と同じであるためソフトウェアでの実施が容易である。例えば、２９および１６がＧＦ（２８）における２つの元である場合、これらの加算は単に次のＸＯＲ演算を行うだけでよい。
【００２９】
【数３】
【００３０】
他方、ガロア体の乗算は以下の例に示すとおりやや複雑になり、原始元αの乗算を反復してＧＦ（２４）のすべての元を計算する。体ＧＦ（２４）の元を生成するため、次数ｍ＝４の原始多項式Ｇ（ｘ）がＧ（ｘ）＝Ｘ４＋Ｘ＋１と選ばれる。乗算をモジュロ（剰余）形式で行うため、乗算の結果はこの体の元となり、５桁目のビットセットを有する任意の元は、単位元Ｆ（α）＝α４＋α＋１＝０を使って桁数を減らし、４ビットにする。この単位元は繰り返し使われ、α４＝１＋αの設定により前記体の異なる元を形成する。このように、この体の元は次のように列挙される。
【００３１】
【数４】
【００３２】
αはＧＦ（２４）の原始元であるため、２と設定して、この体ＧＦ（２４）の元を｛０，１，２，４，８，３，６，１２，１１…９｝として生成することができる。
【００３３】
ガロア体の多項式乗算は、２つの基本ステップで実施できると見なせる。その第１は多項式の積ｃ（ｘ）＝ａ（ｘ）＊ｂ（ｘ）の計算で、これを代数的に展開し、同じ次数のものをまとめると（加算は対応する項同士のＸＯＲ演算に対応する）ｃ（ｘ）が得られる。
【００３４】
【数５】
【００３５】
【表１】
【００３６】
第２のステップは、ｄ（ｘ）＝ｃ（ｘ） ｍｏｄ（ｍｏｄｕｌｏ） ｐ（ｘ）の計算である。
【００３７】
例示のため、既約多項式を法とする多項式の乗算を行う。例えば、（ｍ（ｘ）＝ｘ８＋ｘ４＋ｘ３＋ｘ＋１の場合）
｛５７｝＊｛８３｝＝｛ｃ１｝であり、これは以下の理由による。
【００３８】
【数６】
【００３９】
【数７】
【００４０】
このアプローチを採用した、改善されたガロア体乗算器システム１０は、ガロア体上の係数を伴う２つの多項式、Ａレジスタ内の多項式ａ０〜ａ７およびＢレジスタ内の多項式ｂ０〜ｂ７を乗算し、その積を取得する乗算回路を含み、この積はチャートＩＩで定義される１５項多項式ｃ（ｘ）で与えられる。この乗算回路は、実際には複数の乗算器セルを含む。
【００４１】
【表２】
【００４２】
ガロア体乗算器システムの演算は、２００２年１月３０日出願済み米国特許出願第１０／０６０，６９９号、Ｓｔｅｉｎら、表題ＧＡＬＯＩＳ ＦＩＥＬＤ ＭＵＬＴＩＰＬＩＥＲ ＳＹＳＴＥＭ ［ＡＤ−２４０Ｊ］に説明されており、この参照によりその全体が本明細書に組み込まれるものである。
【００４３】
前記多項式ｃ（ｘ）の１５項は、それぞれ「＊」（アスタリスク記号）で表されるＡＮＤ関数を含み、項の各対は
【００４４】
【数８】
【００４５】
（円内にプラスのある記号）で表される論理排他的ＯＲと組み合わされる。チャートＩＩで表した積は、それぞれ１５×８セルからなる複数のガロア体線形変換ユニットを含んでよいガロア体線形変換回路へ送信され、このガロア体線形変換回路は、前記乗算回路により生成された前記積に応答して所定の既約多項式について多項式の積の剰余を予測する。Ａ０およびＢ０の乗算は第１のユニットで、Ａ１およびＢ１の乗算は第２のユニットで、Ａ２およびＢ２の乗算は第３ユニットで、そしてＡｎおよびＢｎの乗算は最後のユニットで実行される。ガロア体線形変換回路と、その各変換ユニットとの演算は、２００２年１月１８日出願済み米国特許出願第１０／０５１，５３３号、Ｓｔｅｉｎら、表題ＧＡＬＯＩＳ ＦＩＥＬＤ ＬＩＮＥＡＲ ＴＲＡＮＳＦＯＲＭＥＲ［ＡＤ−２３９Ｊ］に説明されており、この参照によりその全体が本明細書に組み込まれるものである。各前記ガロア体線形変換ユニットは、前記多項式の積を既約多項式で除算することにより前記剰余を予測する。その既約多項式は、例えば、チャートＩＩＩに示したもののいずれでもよい。
【００４６】
【表３】
【００４７】
【表４】
【００４８】
本明細書で開示するガロア体乗算器ＧＦ（２８）では、チャートＩＩＩに示すとおり指数８（２８）および指数４（２４）以下を実行できる。
【００４９】
本発明に係るＧＦ乗算の例は、以下のように実行される。
【００５０】
【数９】
【００５１】
図１ａは、本発明に従う小型ガロア体乗算器エンジン１０と、それに伴うＡ入力レジスタ１２と、Ｂ入力レジスタ１４と、出力レジスタ１６とを示したものである。小型ガロア体エンジン１０は、乗算と、乗加算と、乗累算とを含む複数の異なる演算を行うことができる。
【００５２】
図２の従来のガロア体乗算器エンジン１０ａでは、３つのレジスタ、Ａレジスタ１２ａと、Ｂレジスタ１４ａと、Ｃレジスタ２６ａとが必要である。これらのレジスタによる負荷は、付随するデジタル信号プロセッサ（ｄｉｇｉｔａｌ ｓｉｇｎａｌ ｐｒｏｃｅｓｓｏｒ、略称ＤＳＰ）のコア２８にかかり、多大な外部バス作業が必要とされる。Ａレジスタ１２ａにデータを供給するバス３０と、Ｂレジスタ１４ａにデータを供給するバス３４と、Ｃレジスタ２６ａにデータを供給するバス３６とに加え、レジスタ１６ａからの出力を前記デジタル信号プロセッサ２８に戻すバス３２と、デジタル信号プロセッサ２８からの出力をＢレジスタ１４ａまたはＣレジスタ２６ａへ戻すバス３４またはバス３６とが必要である。バス３１は、ガロア体線形変換回路２０の出力と、出力レジスタ１６ａとを接続する。これにより、多項式乗算回路１８は、Ｃレジスタ２６ａから行列２２の加算器入力４２に供給される値とともに、ガロア体線形変換回路２０の行列２２の乗算入力４０に適切な値を供給でき、乗算、乗加算、および乗累算の演算を実行することができる。８×１５の行列としてここに示した行列２２は、８次多項式の乗算をサポートするものであるが、扱う多項式の次数に応じてこれより大きくても小さくてもよく、また多数または少数のセル２４を含んでよい。
【００５３】
本発明によれば、図３のエンジン１０ｂにおけるガロア体線形変換回路２０ｂの行列２２ｂの１行あたりのセル２４ｂの数は、行列２２ｂを２つの行列部と、行列部５０と、単位行列部５２とで設定することにより、ほぼ半数にまで減らし得る。前記単位行列部にはセル５４が１セットだけ必要で、これらの単位行列部のセルは、前記乗算回路の出力が、前記既約多項式の次数未満の次数を伴う多項式である場合に、剰余の予測を表す。これにより、図３において、前記既約多項式が次数８を有する場合、８次未満の任意の多項式は法を超えることがなく、前記行列を素通りするため、単位行列部５２内の空のセルは不要となる。これにより、前記行列２２ｂに必要なセルのほぼ半数が節約され、その結果より小型、単純、高速なエンジンが得られる。
【００５４】
図４の各セル２４ｂは、ＡＮＤ回路１００および排他的ＯＲ回路１０２を含んでよい。データ入力１０４および有効化入力１０６が提供される。排他的ＯＲ回路１０２は、出力が前記行列の出力に接続された最後の排他的ＯＲ回路と、入力が前記加算器入力、図３の４２ｂまたは図９の４２ｇに接続された最初の排他的ＯＲ回路とを除き、次の排他的ＯＲ回路の入力に線１０８で出力を提供し、前の排他的ＯＲ回路からの出力を入力１１０で受信する。線１０６上の許可信号により、線１０４上のデータはＡＮＤゲート１００を通過できるようになり、排他的ＯＲ回路１０２により線１１０上の入力と排他的論理和が取得される。線１０６上に許可信号がない場合、線１１０上の入力は、単に前記排他的ＯＲゲート１０２を通過し線１０８へ出力される。線１０６上の許可信号は、セル２４を有効にする。このように、前記行列全体はいかなる特定の既約多項式にも再設定できる。
【００５５】
図３のエンジン１０ｂの有効性は、チャートＩＩＩ（上記参照）から既約多項式を選択し、必要なセルを有効化することにより選択した既約多項式を導入するステップにより理解できる。例えば、既約多項式ｘ８＋ｘ４＋ｘ３＋ｘ２＋１を表す０ｘ１１ｄで表された８次の第１の多項式を導入する際は、総括的に２４ｃｃで示された有効化されたセルが、図３に示した一列のセル５４ｃが図５の単位行列５２ｃを形成する。第２の既約多項式をチャートＩＩＩから選ぶ際は、既約多項式ｘ８＋ｘ５＋ｘ３＋ｘ＋１である０ｘ１２ｂが図６の行列部５０ｄおよび単位行列５２ｄで有効化されたセル２４ｄｄのパターンを生成し、ここでも前記単位行列部５２ｄが再び一列に並んだ有効化されたセル５４ｄを形成する。
【００５６】
必要なセルの数の削減は、前記既約多項式と同じ次数を有する多項式だけに制限されない。これは、前記既約多項式の次数の半分以下の次数を有する任意の多項式にも適用される。例えば、図３に示し図５および図６の説明で言及している８×１５の行列２２ｂは、前記既約多項式の次数が１６で、これをサポートする行列が最高８次の多項式まではサポートしても９〜１５次の多項式はサポートしない場合、次数１、２、３、または４の多項式もサポートできるが、次数５、６、および７の多項式はサポートしない。これが次数３２の場合は、次数３２の多項式と次数１６までの多項式をサポートするが、次数１７〜３１の多項式はサポートしない。例えば図７に示したように、４次の既約多項式の場合、行列部５０ｅおよび単位行列部５２ｅは縮小し、行列２２ｅ内で実施可能になる。ここで、前記行列部５０ｅは、複数の有効化されたセル２４ｅｅとともに、単位行列５２ｅ内にも上記より短い列の有効化されたセルを有し、単位行列部５２ｅを形成している。
【００５７】
次数５、６、および７の中間体多項式に対応することが望ましい場合は、前記単位行列部を図８の疎行列部５２ｆで置換できる。ここで、次数７、６、および５の多項式をサポートするため、有効化されたセル５４ｆｆ、５４ｆｆｆ、および５４ｆｆｆｆを追加行として使用できる。ただし、行列サイズおよび必要なセル数の節約の度合いは落ちる。
【００５８】
本発明の別の特徴によれば、入力レジスタの数は３から２に削減でき、図９のデジタル信号プロセッサ（ＤＳＰ）２８ｇとの通信に必要な外部バスの数を削減し、エンジン１０ｇ自体の内部へと局在化できる。これにより、図９に示したように、入力レジスタはＡ １２ｇおよびＢ １４ｇの２つだけになり、出力３１ｇからのフィードバックはＤＳＰ ２８ｇを通過する必要がなくなり、その代わり直接ローカルにエンジン１０ｇ上において内部バス６０経由で乗算器入力選択回路６２および加算器入力選択回路６４へ送信されるようになる。デジタル信号プロセッサ２８ｇは、乗算器入力選択回路６２へは線６６で、加算器入力選択回路６４へは線６８で、制御信号を提供するだけで済むようになる。このように、乗算モードでは、乗算器入力選択回路６２は、Ｂレジスタ１４ｇから多項式乗算回路１８ｇへ入力を渡す一方、加算器入力選択回路６４は、加法単位元レベル、この場合アースレベル７０をガロア体線形変換回路２０ｇの前記加算器入力４２ｇに提供する。乗加算モードにおいて、デジタル信号プロセッサ２８は、行列２２ｇからの出力を線６０で多項式乗算回路１８ｇに戻すよう乗算器入力選択回路６２に命令し、Ｂレジスタ１４ｇ内の多項式をガロア体線形変換回路２０ｇの前記加算器入力４２ｇへ渡すよう加算入力選択回路６４に命令する。乗累算モードにおいて、デジタル信号プロセッサ２８ｇは、多項式をＢレジスタ１４ｇから多項式乗算回路１８ｇへ送信するよう乗算器入力選択回路６２に命令し、ガロア体線形変換回路２０ｇの出力を線６０で戻すよう加算入力選択回路６４に命令する。
【００５９】
本発明の更なる特徴は、セル２４ｇの選択的有効化によるガロア体線形変換回路２０ｇの再設定可能性である。再設定可能な制御回路８０は、セル２４ｇのうち選択された既約多項式の係数の実施に必要なものを選択的に有効にし、制御に必要なセル数は本発明に従い低減済みであるため、それ自体サイズが縮小可能である。
【００６０】
再設定可能なガロア体線形変換回路の演算は、２００２年５月１日出願済み米国特許出願第１０／１３６，１７０号、Ｓｔｅｉｎら、表題ＲＥＣＯＮＦＩＧ．ＵＲＡＢＬＥ ＩＮＰＵＴ ＧＡＬＯＩＳ ＦＩＥＬＤ ＬＩＮＥＡＲ ＴＲＡＮＳＦＯＲＭＥＲＥＲ ＳＹＳＴＥＭ（ＡＤ−３００Ｊ）に説明されており、そのすべての優先権出願および文書はこの参照によりその全体が本明細書に組み込むまれるものである。
【００６１】
上記では本発明についてエンジン１つだけに関し簡略化した説明をしてきたが、図１０に示したように複数のエンジンをまとめて使用してもよい。この図では、各エンジンが乗算回路１０ｈ、１０ｉ、１０ｊ、１０ｋ…１０ｎと、ガロア体線形変換回路２０ｈ、２０ｉ、２０ｊ、２０ｋ…２０ｎとを有し、これらすべてを再設定可能な単一の中央制御回路８０’が制御している。これらのエンジンは、同じビット数の多い（ワイドビット）［３２，６４，１２８］のＡレジスタおよびＢレジスタを共有し、それぞれ異なる８ビット（１バイト）セグメント上で動作するか、あるいはそれぞれ独自の再設定可能な制御ユニット８０ｈ、８０ｉ、８０ｊ、８０ｋ…８０ｎにより制御され、それぞれ独自のＡレジスタおよびＢレジスタの対Ａ０およびＢ０（１２ｈおよび１４ｈ）、Ａ１およびＢ１（２ｉおよび１４ｉ）、Ａ２およびＢ２（１２ｊおよび１４ｊ）、Ａ３およびＢ３（１２ｋおよび１４ｋ）などにより制御されることができる。
【００６２】
本明細書で示した出力ｃ０〜ｃ１４を提供する実施形態で使用可能な図１１の多項式乗算回路１８ｌは、複数のＡＮＤゲート１２０であって、排他的ＯＲゲート１２２と組み合わせることにより、図１２の表（チャート）１２４に例示したように、Ａレジスタ１２ｌおよびＢレジスタ１４ｌからの任意の多項式の対、例えば多項式ａ０〜ａ７、多項式ｂ０〜ｂ７を乗算できる複数のＡＮＤゲート１２０を含む。
【００６３】
この乗算器エンジンを乗算、乗加算、乗累算など単一用途専用にする場合、前記乗算器入力選択回路および加算器入力選択回路は、図１３、図１４、および図１５に示したように構造簡略化のため省略できる。
【００６４】
図１３のこのようなガロア体乗算器エンジン１００は、多項式乗算器回路１８ｐと、ガロア体変換回路２０ｐであって、前記乗算回路１８ｐから多項式の積を受信し、それを加算器入力４２ｐに加算して１０２で出力を生成する、ガロア体変換回路２０ｐとを含むが、ここでは加法単位元レベルが加算器入力に供給されている。
【００６５】
図１４のガロア体乗累算エンジン１０４は、多項式乗算回路１８ｑと、ガロア体変換回路２０ｑであって、乗算回路１８ｑから多項式の積を受信し、それを加算器入力４２ｑに加算して１０２ｑで出力を生成する、ガロア体変換回路２０ｑとを含む。ただし、ここでは前記出力１０２ｑは加算器入力４２ｐに戻されている。
【００６６】
図１５のガロア体乗加算エンジン１０８は、多項式乗算回路１８ｒと、ガロア体変換回路２０ｒであって、乗算回路１８ｒから多項式の積を受信し、それを加算器入力４２ｒに加算して１０２ｒで出力を生成する、ガロア体変換回路２０ｒとを含む。ただし、ここでは前記出力１０２ｒは乗算回路１８ｒに戻されている。
【００６７】
各特徴は、図面の一部のみで本発明の具体的な特徴を示しているが、これは単に便宜上のものであり、本発明に従って他の特徴のいずれか、またはすべてと組み合わせてもよい。本明細書における用語「含む」と「有する」と「伴う」とは、広義かつ包括的に解釈されるべきものであり、いかなる物理的相互接続にも限定されるものではない。さらに、掲題の用途に開示したいかなる実施形態も、考えうる唯一の実施形態として解釈されるべきではない。
【００６８】
当業者であれば、他の実施形態も以下の特許請求の範囲内であることが理解されるであろう。
【図面の簡単な説明】
【００６９】
当業者であれば、他の目的、特徴、および優位性が、以下の好適な実施形態の説明および添付の図面から理解されるであろう。
【図１】図１は、本発明に従う小型ガロア体乗算器エンジンの機能ブロック図。
【図２】図２は、本発明に従う従来の小型ガロア体乗算器エンジンの、より詳細な機能ブロック図。
【図３】図３は、本発明の特徴である小型化されたガロア体線形変換ユニット行列を示した、図１の小型ガロア体乗算器エンジンの、より詳細な機能ブロック図。
【図４】図４は、図２および図３のガロア体線形変換回路（乗算器エンジン）の前記行列用の典型的プログラム可能なＸＯＲ（またはＸ−ＯＲ）回路セルの概略図。
【図５】図５は、次数８の特定の多項式について、本発明による行列部および単位行列部のセルのプログラミングを例示した、図３および図９のガロア体線形変換回路の簡略化した模式図。
【図６】図６は、次数８の別の多項式について、本発明に係る行列部および単位行列部のセルのプログラミングを例示した、図３および図９のガロア体線形変換回路の簡略化した模式図。
【図７】図７は、次数４のさらに別の多項式について、本発明に従う行列部および単位行列部のセルのプログラミングを例示した、図３および図９のガロア体線形変換回路の簡略化した模式図。
【図８】図８は、この特定の実施形態において、半分の（４）次数および完全な（８）次数の間の多項式次数をサポートする疎行列としての第２行列部のプログラミングを例示した、図３および図９のガロア体線形変換回路の簡略化した模式図。
【図９】図９は、本発明の特徴である縮小サイズの行列と、縮小したハードウェアおよびローカルバスとの双方を組み込んだ、図１の小型ガロア体乗算器エンジンの、より詳細な機能ブロック図。
【図１０】図１０は、複数のガロア体線形変換ユニットを使用した、本発明に従うガロア体乗算器エンジンのブロック図。
【図１１】図１１は、図２、３、５、および９で使用可能な多項式乗算器の概略図。
【図１２】図１２は、図１１の多項式乗算器の伝達関数を例示した図。
【図１３】図１３は、本発明に従う乗算演算専用のガロア体乗算器エンジンの簡略化した模式図。
【図１４】図１４は、本発明に従う乗累算演算専用のガロア体乗算器エンジンの簡略化した模式図。
【図１５】図１５は、本発明に従う乗加算演算専用のガロア体乗算器エンジンの簡略化した模式図。
【技術分野】
【０００１】
本発明は小型ガロア体乗算器エンジンに関し、具体的にはガロア体上で乗算と乗加算と乗累算とを行える小型ガロア体乗算器エンジンに関するものである。
【０００２】
本出願は、２００３年３月２４日出願済み米国特許出願第１０／３９５，６２０号、Ｓｔｅｉｎら、表題ＣＯＭＰＡＣＴ ＧＡＬＯＩＳ ＦＩＥＬＤ ＭＵＬＴＩＰＬＩＥＲ（ＡＤ−３３７Ｊ）と、２００２年１０月９日出願済み米国仮出願第６０／４１７，３８４号、Ｓｔｅｉｎら、表題Ａ ＣＯＭＰＡＣＴ ＧＡＬＯＩＳ ＦＩＥＬＤ ＭＵＬＴＩＰＬＩＥＲ（ＡＤ−３３７Ｊ）と、２００１年１１月３０日出願済み米国仮出願第６０／３３４，６６２号、Ｓｔｅｉｎら、表題ＧＦ２−ＡＬＵ（ＡＤ−２３９Ｊ）と、２００１年１１月２０日出願済み米国仮出願第６０／３３４，５１０号、Ｓｔｅｉｎら、表題ＰＡＲＡＬＬＥＬ ＧＡＬＯＩＳ ＦＩＥＬＤ ＭＵＬＴＩＰＬＩＥＲ（ＡＤ−２４０Ｊ）と、２００１年１２月１８日出願済み米国仮出願第６０／３４１，６３５号、Ｓｔｅｉｎら、表題ＧＡＬＯＩＳ ＦＩＥＬＤ ＭＵＬＴＩＰＬＹ ＡＤＤ （ＭＰＡ） ＵＳＩＮＧ ＧＦ２−ＡＬＵ（ＡＤ−２９９Ｊ）と、２００１年１２月１８日出願済み米国仮出願第６０／３４１，７３７号、Ｓｔｅｉｎら、表題ＰＲＯＧＲＡＭＭＡＢＬＥ ＧＦ２−ＡＬＵ ＬＩＮＥＡＲ ＦＥＥＤＢＡＣＫ ＳＨＩＦＴ ＲＥＧＩＳＴＥＲ-ＩＮＣＯＭＩＮＧ ＤＡＴＡ ＳＥＬＥＣＴＩＯＮ（ＡＤ−３００Ｊ）とに対して優先権を主張するものである。本出願は、さらに、２００２年１月１８日出願済み米国特許出願第１０／０５１，５３３号、Ｓｔｅｉｎら、表題ＧＡＬＯＩＳ ＦＩＥＬＤ ＬＩＮＥＡＲ ＴＲＡＮＳＦＯＲＭＥＲＥＲ（ＡＤ−２３９Ｊ）と、２００２年１月３０日出願済み米国特許出願第１０／０６０，６９９号、Ｓｔｅｉｎら、表題ＧＡＬＯＩＳ ＦＩＥＬＤ ＭＵＬＴＩＰＬＩＥＲ ＳＹＳＴＥＭ（ＡＤ−２４０Ｊ）と、２００２年８月２６日出願済み米国特許出願第１０／２２８，５２６号、Ｓｔｅｉｎら、表題ＧＡＬＯＩＳ ＦＩＥＬＤ ＭＵＬＴＩＰＬＹ／ＭＵＬＴＩＰＬＹ - ＡＤＤ／ＭＵＬＴＩＰＬＹ ＡＣＣＵＭＵＬＡＴＥ（ＡＤ−２９９Ｊ）と、２００２年５月１日出願済み米国特許出願第１０／１３６，１７０号、Ｓｔｅｉｎら、表題ＲＥＣＯＮＦＩＧ．ＵＲＡＢＬＥ ＩＮＰＵＴ ＧＡＬＯＩＳ ＦＩＥＬＤ ＬＩＮＥＡＲ ＴＲＡＮＳＦＯＲＭＥＲＥＲ ＳＹＳＴＥＭ（ＡＤ−３００Ｊ）とに対して優先権を主張するものである。
【背景技術】
【０００３】
ガロア体（Ｇａｌｏｉｓ ｆｉｅｌｄ、略称ＧＦ）での係数付き多項式の乗算は、リードソロモン（Ｒｅｅｄ Ｓｏｌｏｍｏｎ、略称ＲＳ）コーディング用の通信システムにおいて、また高度な暗号化規格（ＡＥＳ）において広く行われている。一部の場合では、基本的なガロア体乗算だけでは不十分で、より高度なガロア体演算、例えばガロア体乗累算（Ｇａｌｏｉｓ ｆｉｅｌｄｓ ｍｕｌｔｉｐｌｙ ａｎｄ ａｃｃｕｍｕｌａｔｅ、略称ＧＦ−ＭＡＣ）またはガロア体乗加算（Ｇａｌｏｉｓ ｆｉｅｌｄｓ ｍｕｌｔｉｐｌｙ ａｎｄ ａｄｄ、略称ＧＦ−ＭＰＡ）が必要とされる。ガロア体乗算は、従来のデジタル信号プロセッサ（ｄｉｇｉｔａｌ ｓｉｇｎａｌ ｐｒｏｃｅｓｓｏｒ、略称ＤＳＰ）での実行は困難で時間がかかる。ＤＳＰは、有限インパルス応答（ｆｉｎｉｔｅ ｉｍｐｕｌｓｅ ｒｅｓｐｏｎｓｅ、略称ＦＩＲ）フィルタリング、および他の乗累算（ｍｕｌｔｉｐｌｙ ａｃｃｕｍｕｌａｔｅ、略称ＭＡＣ）の多い演算用に最適化されているが、ガロア体タイプの演算を効率的に処理することはできない。アプローチの１つに、１ビットずつ処理を行う線形フィードバックシフトレジスタ（ｌｉｎｅａｒ ｆｅｅｄｂａｃｋ ｓｈｉｆｔ ｒｅｇｉｓｔｅｒｓ、略称ＬＦＳＲ）を使ってガロア体上で単純な多項式乗除算を行うというものがあるが、これは非常に緩慢な処理である。例えば、ブロードバンド通信におけるＡＥＳタイプの応用ではビットレートが最高４０メガビット／秒で、最高５百万ＧＦ乗算／秒（ＧＦ ｍｕｌｔｉｐｌｉｃａｔｉｏｎｓ ｐｅｒ ｓｅｃｏｎｄ、略称ＧＦ−ＭＰＳ）となり、各乗算が６０〜１００演算などの多数になる。別のアプローチでは、ルックアップテーブルを使ってガロア体乗算が実行される。典型的に、このアプローチは１０〜２０サイクル以上を要し、５ ＧＦ−ＭＰＳではやや低めではあるが非常に多数の演算、例えば２０×５＝１００ ＭＩＰＳ以上の結果が得られる。リードソロモン符号は、ブロードバンドネットワーク用の好適なエラー制御コーディングスキームとして広く受け入れられてきている。リードソロモン式エンコーダおよびデコーダをプログラム可能に実施するアプローチは、チャネル条件に基づいて望まれるデータ帯域幅とエラー補正能力とをトレードオフできるという独自の柔軟性をシステム設計者に提供するため、魅力的な解決法である。リードソロモンデコーディングの第１のステップは、シンドロームの計算である。シンドロームは、Ｓｉ＝Ｒ ｍｏｄ Ｇの公式で定義できる。ここで、ｉ＝（０，１…１５）である。受信された符号語は、多項式形式でＲｉ＝ｒｏＸＮ−１＋ｒ１ＸＮ−２＋…ｒＮ−１と表現される。ここで、受信語の長さはＮである。最終的には、ガロア体上におけるシンドローム計算は、生成多項式のｉ’番目の根のｊ’乗で定義される根の多項式評価につながると見なすことができる。各受信語につき、リードソロモンアルゴリズムには計算すべきシンドロームが１６あり、これにより現行のマイクロプロセッサでの演算数は１６倍の１６億／秒（ｂｉｌｌｉｏｎ ｏｐｅｒａｔｉｏｎｓ ｐｅｒ ｓｅｃｏｎｄ、略称ＢＯＰＳ）となる。ルックアップテーブルの代わりに単純な乗算を使用すると、演算率は６．４ ＢＯＰＳまで増加する。通信分野の拡張と、通信データの暗号化要件とにより、ガロア体乗算の必要性は劇的に増加しており、各ドメインエラーチェックおよび暗号化は、異なるルックアップテーブルのセットを要する異なるガロア体上のガロア体乗算を必要とするため、さらに状況を複雑にしている。ガロア体乗算器システムまたはガロア体乗算器エンジンの近年の改善により演算は高速化し格納要件も低められてはきているが、依然、より高速で低電力、小型設計のものへの需要が高い。
【発明の開示】
【課題を解決するための手段】
【０００４】
従って、本発明の目的は、新規で改善された小型ガロア体乗算器エンジンを提供することである。
【０００５】
本発明の更なる目的は、このような新規で改善された小型ガロア体乗算器エンジンを提供することにより、サイズがさらに縮小され伝搬経路がさらに短縮された結果、より小型化、単純化、および高速化した設計になることである。
【０００６】
本発明の更なる目的は、このような新規で改善された小型ガロア体乗算器エンジンを提供することにより、必要な格納量をさらに削減することである。
【０００７】
本発明の更なる目的は、このような新規で改善された小型ガロア体乗算器エンジンを提供することにより、必要な外部バスの数を削減し、付随するＤＳＰのレジスタなどの資源（リソース）をより少量使用することである。
【０００８】
本発明の更なる目的は、このような新規で改善された小型ガロア体乗算器エンジンを提供することにより、新規多項式用の再設定に必要な時間を短縮できることである。
【０００９】
本発明の更なる目的は、このような改善された新規な小型ガロア体乗算器エンジンを提供することにより、１サイクルの乗算を実行するだけでなく、乗加算および乗累算の演算も実行するという観点で、より多くの機能を提供することである。
【００１０】
本発明は、ガロア体における入力多項式の乗算機能、乗加算機能、および乗累算機能のうち１若しくはそれ以上を取得でき、軽減された外部バスおよびＤＳＰ資源の要件を有する、小型ガロア体乗算器エンジンが、乗算回路および加算器入力選択回路を使用し、ガロア体線形変換ユニットの前記乗算回路および加算器入力に適切な入力多項式を供給することによりもたらされるということと、また、行列および単位行列であって、そのセルが、前記乗算回路の出力が前記既約多項式の次数未満の次数を伴う多項式である場合に剰余の予測を表す、行列および単位行列で、ガロア体線形変換回路を設定することにより格納要件が軽減されるということと、さらに、前記乗算器エンジンを単一用途（例えば乗算、乗加算、乗累算）専用にした場合、前記加算器入力選択回路および乗算入力選択回路が排除可能になりうること、という知見に基づいている。
【００１１】
本発明は、小型ガロア体並列乗算器エンジンであって、ガロア体上の係数を伴う２つの多項式を乗算しその積を取得する乗算回路を含む小型ガロア体並列乗算器エンジンを特徴とする。また、ガロア体線形変換回路であって、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有するガロア体線形変換回路が提供される。前記乗算回路には、第１の多項式入力と、第２の多項式入力と、乗算モードでは前記第２の多項式を、乗加算モードでは前記ガロア体線形変換回路の出力を、そして乗累算モードでは前記第２の多項式を、前記乗算回路に提供する乗算器入力選択回路とが提供される。加算器入力選択回路は、前記入力多項式のガロア体乗算関数、ガロア体乗加算関数、およびガロア体乗累算関数を取得するため、前記乗算モードでは加法単位元を、前記乗加算モードでは前記第２の多項式入力を、そして前記乗累算モードでは前記ガロア体線形変換回路の出力を、前記ガロア体線形変換回路の加算入力に提供する。
【００１２】
好適な実施形態では、前記乗算回路は、ガロア乗算器を実現するため、前記多項式の積の各項用にＡＮＤ論理回路を含んでよい。前記乗算回路は、ガロア体における総和をもたらすため、前記多項式の積における項の各対に排他的ＯＲ論理回路を含んでよい。前記ガロア体線形変換回路は、セルの行列であって、各セルが排他的ＯＲ論理回路と、前記排他的ＯＲ論理回路に接続された出力を有するＡＮＤ論理回路と、入力データビットを受信するための入力とを含む、セルの行列を含んでよい。前記ガロア体線形変換回路の出力は、前記エンジンのローカルバス経由で前記乗算器入力選択回路および前記加算器入力選択回路に戻される。前記乗算器入力選択回路は、前記ガロア体線形変換回路の出力からの入力と、前記第２の多項式からの入力とを含んでよい。前記加算器入力選択回路は、前記ガロア体線形変換回路の出力からの入力と、前記第２の多項式からの入力と、制御入力とを含んでよい。各前記排他的ＯＲ論理回路は、出力が前記行列の出力に接続された最後の排他的ＯＲ論理回路と、入力が加法単位元レベルに接続された最初の排他的ＯＲ論理回路とを除いて、次に続く排他的ＯＲ論理回路の入力に接続された出力を有してよい。再設定可能な制御回路であって、所定の既約多項式に関する剰余を予測するための係数のセットを、前記ガロア体線形変換回路に供給する再設定可能な制御回路があってもよい。前記ガロア体線形変換回路は複数のガロア体変換ユニットを含んでよく、前記再設定可能な制御回路は、前記係数を並行して前記ガロア体変換ユニットに供給してよい。前記ガロア体線形変換回路は、行列部および単位行列部で設定された複数のセルを含んでよく、前記単位行列部のセルは、前記乗算回路の出力が、前記既約多項式の次数未満の次数を伴う多項式である場合に剰余の予測を表す。前記ガロア体線形変換回路は複数のガロア体変換ユニットを含んでよく、前記再設定可能な制御回路は、前記係数を並行して前記ガロア体変換ユニットに供給してよい。前記ガロア体線形変換回路は複数のガロア体変換ユニットを含んでよく、前記再設定可能な制御回路は、それぞれが各前記ガロア体線形変換ユニットに関連付けられた複数の再設定可能な制御ユニットを含んでよい。前記加法単位元レベルはヌルレベルであってよく、前記入力多項式の前記関数は１サイクルで取得されてよい。
【００１３】
また本発明は、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する乗算回路を含む小型ガロア体乗算器エンジンを特徴とする。ガロア体線形変換回路は、前記乗算回路からの乗算入力を有し、既約多項式について前記多項式の積の剰余を予測する。前記乗算回路には、第１の多項式入力と、第２の多項式入力と、入力多項式のガロア体乗算関数を取得するため前記ガロア体線形変換回路の加算入力に乗算モードで加法単位元レベルを提供する乗算器入力選択回路とが提供される。
【００１４】
また本発明は、小型ガロア体乗算器エンジンであって、ガロア体上の係数を伴う２つの多項式を乗算しその積を取得する乗算回路を含む小型ガロア体乗算器エンジンを特徴とする。ガロア体線形変換回路は、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有する。前記乗算回路には、第１の多項式入力と、第２の多項式入力と、入力多項式のガロア体乗加算関数を取得するため前記ガロア体線形変換回路の加算入力に乗加算モードで前記第２の多項式入力を提供する乗算器入力選択回路とが提供される。
【００１５】
本発明は、小型ガロア体乗算器エンジンであって、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する乗算回路を含む小型ガロア体乗算器エンジンを特徴とする。ガロア体線形変換回路は、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有する。前記乗算回路には、第１の多項式入力と、第２の多項式入力と、入力多項式のガロア体乗累算関数を取得するため前記ガロア体線形変換回路の加算入力に乗累算モードで前記ガロア体線形変換回路の出力を提供する乗算器入力選択回路とが提供される。
【００１６】
また本発明は、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する乗算回路を含む小型ガロア体乗算器エンジンを特徴とする。ガロア体線形変換回路は、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有する。前記乗算回路には、第１の多項式入力と、第２の多項式入力と、入力多項式のガロア体乗算関数およびガロア体乗加算関数を取得するため、乗算器入力選択回路であって、乗算モードでは前記第２の多項式を、そして乗加算モードでは前記ガロア体線形変換回路の出力を、前記乗算回路に提供する乗算器入力選択回路と、加算器入力選択回路であって、前記乗算モードでは加法単位元レベルを、そして前記乗加算モードでは前記第２の多項式入力を、前記ガロア体線形変換回路の加算入力に提供する加算器入力選択回路とが提供される。
【００１７】
また本発明は、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する乗算回路を含む小型ガロア体乗算器エンジンを特徴とする。ガロア体線形変換回路は、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有する。前記乗算回路には、第１の多項式入力と、第２の多項式入力と、入力多項式のガロア体乗算関数およびガロア体乗累算関数を取得するため、乗算器入力選択回路であって、乗算モードでは前記第２の多項式を、そして乗累算モードでは前記第２の多項式を、前記乗算回路に提供する乗算器入力選択回路と、加算器入力選択回路であって、前記乗算モードでは加法単位元レベルを、そして前記乗累算モードでは前記ガロア体線形変換回路の出力を、前記ガロア体線形変換回路の加算入力に提供する加算器入力選択回路とが提供される。
【００１８】
また本発明は、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する乗算回路を含む小型ガロア体乗算器エンジンを特徴とする。ガロア体線形変換回路は、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有する。前記乗算回路には、第１の多項式入力と、第２の多項式入力と、入力多項式のガロア体乗算関数およびガロア体乗累算関数を取得するため、乗算器入力選択回路であって、乗加算モードでは前記ガロア体線形変換回路の出力を、そして乗累算モードでは前記第２の多項式を、前記乗算回路に提供する乗算器入力選択回路と、加算器入力選択回路であって、乗加算モードでは前記第２の多項式入力を、そして乗累算モードでは前記ガロア体線形変換回路の出力を、前記ガロア体線形変換回路の加算入力に提供する加算器入力選択回路とが提供される。
【００１９】
また本発明は、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する乗算回路を含む小型ガロア体線形乗算回路と、既約多項式に関する多項式の積の剰余を予測するためのガロア体線形変換回路であって、行列部および単位行列部で設定された複数のセルを含み、前記単位行列部のセルは、前記乗算回路の出力が、前記既約多項式の次数未満の次数を伴う多項式である場合に剰余の予測を表す、ガロア体線形変換回路とを特徴とする。
【００２０】
好適な実施形態では、各セルはプログラム可能な排他的ＯＲセルを含んでよい。このプログラム可能な排他的ＯＲセルは、排他的ＯＲ回路およびＡＮＤ回路を含んでよい。再設定可能な制御回路であって、所定の既約多項式に関する剰余を予測するための係数のセットを、前記ガロア体線形変換回路に供給する再設定可能な制御回路があってもよい。前記ガロア体線形変換回路は、複数のガロア体線形変換回路ユニットを含んでよい。前記再設定可能な制御回路は、前記係数を並行して前記ガロア体変換ユニットに供給してよく、あるいは、前記再設定可能な制御回路は、それぞれが各前記ガロア体線形変換ユニットに関連付けられた複数の再設定可能な制御ユニットを含んでよい。
【００２１】
本発明はまた、より単純なガロア体乗算器エンジンであって、加算器入力選択回路および乗算器入力選択回路を使用することなく、乗算演算、乗加算演算、および乗累算演算から選択された演算に適合する、より単純なガロア体乗算器エンジンを特徴とする。
【発明を実施するための最良の形態】
【００２２】
本発明では、以下に開示する好適な実施形態以外の他の実施形態が可能であり、種々の方法で実施または実行することができる。このように、本発明はその用途において、以下の説明に記載され図面に例示された構造の詳細およびコンポーネントの配置に限定されるものではないことは言うまでもない。
【００２３】
ガロア体ＧＦ（ｎ）は、２つの２項演を実行できる算元（要素）のセットである。加算および乗算は、交換法則、結合法則、および分配法則を満たさなければならない。有限数の元を伴う体は、有限体である。２元体の例には法２（ｍｏｄ ２）の加算および法２の乗算におけるセット｛０，１｝があり、これはＧＦ（２）と表される。この法２の加算演算と乗算演算とは、次の表により定義される。第１行および第１列は、ガロア体加算器およびガロア体乗算器への入力を示している。ここでは例えば１＋１＝０および１＊１＝１が成り立つ。
【００２４】
【数１】
【００２５】
【数２】
【００２６】
一般に、ｐが任意の素数である場合、ＧＦ（ｐ）はｐ個の元を伴う有限体であり、ＧＦ（ｐｍ）はｐｍ個の元を伴う拡大体であると示すことができる。また、体の種々の元は、その体の元の１つであるαに種々の指数を伴わせ、この指数を異なる値に増加させることにより生成できる。例えば、ＧＦ（２５６）は２５６個の元を有し、これらはすべて原始元αの指数を２５６まで増加させることにより生成できる。
【００２７】
また、二項係数を伴う多項式はＧＦ（２）に属する。ＧＦ（２）上のｍ次多項式は、ＧＦ（２）上のｍ次未満の任意多項式で割り切れず、且つゼロより大きい場合、既約であると言うことができる。多項式Ｆ（Ｘ）＝Ｘ２＋Ｘ＋１はＸでもＸ＋１でも割り切れないため、既約多項式である。Ｘ２ｍ−１＋１を除算するｍ次の既約多項式は、原始多項式として知られている。所与のｍに対しては、原始多項式が２つ以上ある可能性がある。大部分の通信規格で頻繁に使われるｍ＝８の原始多項式の例は、Ｆ（Ｘ）＝０ｘ１１ｄ＝ｘ８＋ｘ４＋ｘ３＋ｘ２＋１である。
【００２８】
ガロア体の加算は、モジュロ（剰余）加算と同じであるためソフトウェアでの実施が容易である。例えば、２９および１６がＧＦ（２８）における２つの元である場合、これらの加算は単に次のＸＯＲ演算を行うだけでよい。
【００２９】
【数３】
【００３０】
他方、ガロア体の乗算は以下の例に示すとおりやや複雑になり、原始元αの乗算を反復してＧＦ（２４）のすべての元を計算する。体ＧＦ（２４）の元を生成するため、次数ｍ＝４の原始多項式Ｇ（ｘ）がＧ（ｘ）＝Ｘ４＋Ｘ＋１と選ばれる。乗算をモジュロ（剰余）形式で行うため、乗算の結果はこの体の元となり、５桁目のビットセットを有する任意の元は、単位元Ｆ（α）＝α４＋α＋１＝０を使って桁数を減らし、４ビットにする。この単位元は繰り返し使われ、α４＝１＋αの設定により前記体の異なる元を形成する。このように、この体の元は次のように列挙される。
【００３１】
【数４】
【００３２】
αはＧＦ（２４）の原始元であるため、２と設定して、この体ＧＦ（２４）の元を｛０，１，２，４，８，３，６，１２，１１…９｝として生成することができる。
【００３３】
ガロア体の多項式乗算は、２つの基本ステップで実施できると見なせる。その第１は多項式の積ｃ（ｘ）＝ａ（ｘ）＊ｂ（ｘ）の計算で、これを代数的に展開し、同じ次数のものをまとめると（加算は対応する項同士のＸＯＲ演算に対応する）ｃ（ｘ）が得られる。
【００３４】
【数５】
【００３５】
【表１】
【００３６】
第２のステップは、ｄ（ｘ）＝ｃ（ｘ） ｍｏｄ（ｍｏｄｕｌｏ） ｐ（ｘ）の計算である。
【００３７】
例示のため、既約多項式を法とする多項式の乗算を行う。例えば、（ｍ（ｘ）＝ｘ８＋ｘ４＋ｘ３＋ｘ＋１の場合）
｛５７｝＊｛８３｝＝｛ｃ１｝であり、これは以下の理由による。
【００３８】
【数６】
【００３９】
【数７】
【００４０】
このアプローチを採用した、改善されたガロア体乗算器システム１０は、ガロア体上の係数を伴う２つの多項式、Ａレジスタ内の多項式ａ０〜ａ７およびＢレジスタ内の多項式ｂ０〜ｂ７を乗算し、その積を取得する乗算回路を含み、この積はチャートＩＩで定義される１５項多項式ｃ（ｘ）で与えられる。この乗算回路は、実際には複数の乗算器セルを含む。
【００４１】
【表２】
【００４２】
ガロア体乗算器システムの演算は、２００２年１月３０日出願済み米国特許出願第１０／０６０，６９９号、Ｓｔｅｉｎら、表題ＧＡＬＯＩＳ ＦＩＥＬＤ ＭＵＬＴＩＰＬＩＥＲ ＳＹＳＴＥＭ ［ＡＤ−２４０Ｊ］に説明されており、この参照によりその全体が本明細書に組み込まれるものである。
【００４３】
前記多項式ｃ（ｘ）の１５項は、それぞれ「＊」（アスタリスク記号）で表されるＡＮＤ関数を含み、項の各対は
【００４４】
【数８】
【００４５】
（円内にプラスのある記号）で表される論理排他的ＯＲと組み合わされる。チャートＩＩで表した積は、それぞれ１５×８セルからなる複数のガロア体線形変換ユニットを含んでよいガロア体線形変換回路へ送信され、このガロア体線形変換回路は、前記乗算回路により生成された前記積に応答して所定の既約多項式について多項式の積の剰余を予測する。Ａ０およびＢ０の乗算は第１のユニットで、Ａ１およびＢ１の乗算は第２のユニットで、Ａ２およびＢ２の乗算は第３ユニットで、そしてＡｎおよびＢｎの乗算は最後のユニットで実行される。ガロア体線形変換回路と、その各変換ユニットとの演算は、２００２年１月１８日出願済み米国特許出願第１０／０５１，５３３号、Ｓｔｅｉｎら、表題ＧＡＬＯＩＳ ＦＩＥＬＤ ＬＩＮＥＡＲ ＴＲＡＮＳＦＯＲＭＥＲ［ＡＤ−２３９Ｊ］に説明されており、この参照によりその全体が本明細書に組み込まれるものである。各前記ガロア体線形変換ユニットは、前記多項式の積を既約多項式で除算することにより前記剰余を予測する。その既約多項式は、例えば、チャートＩＩＩに示したもののいずれでもよい。
【００４６】
【表３】
【００４７】
【表４】
【００４８】
本明細書で開示するガロア体乗算器ＧＦ（２８）では、チャートＩＩＩに示すとおり指数８（２８）および指数４（２４）以下を実行できる。
【００４９】
本発明に係るＧＦ乗算の例は、以下のように実行される。
【００５０】
【数９】
【００５１】
図１ａは、本発明に従う小型ガロア体乗算器エンジン１０と、それに伴うＡ入力レジスタ１２と、Ｂ入力レジスタ１４と、出力レジスタ１６とを示したものである。小型ガロア体エンジン１０は、乗算と、乗加算と、乗累算とを含む複数の異なる演算を行うことができる。
【００５２】
図２の従来のガロア体乗算器エンジン１０ａでは、３つのレジスタ、Ａレジスタ１２ａと、Ｂレジスタ１４ａと、Ｃレジスタ２６ａとが必要である。これらのレジスタによる負荷は、付随するデジタル信号プロセッサ（ｄｉｇｉｔａｌ ｓｉｇｎａｌ ｐｒｏｃｅｓｓｏｒ、略称ＤＳＰ）のコア２８にかかり、多大な外部バス作業が必要とされる。Ａレジスタ１２ａにデータを供給するバス３０と、Ｂレジスタ１４ａにデータを供給するバス３４と、Ｃレジスタ２６ａにデータを供給するバス３６とに加え、レジスタ１６ａからの出力を前記デジタル信号プロセッサ２８に戻すバス３２と、デジタル信号プロセッサ２８からの出力をＢレジスタ１４ａまたはＣレジスタ２６ａへ戻すバス３４またはバス３６とが必要である。バス３１は、ガロア体線形変換回路２０の出力と、出力レジスタ１６ａとを接続する。これにより、多項式乗算回路１８は、Ｃレジスタ２６ａから行列２２の加算器入力４２に供給される値とともに、ガロア体線形変換回路２０の行列２２の乗算入力４０に適切な値を供給でき、乗算、乗加算、および乗累算の演算を実行することができる。８×１５の行列としてここに示した行列２２は、８次多項式の乗算をサポートするものであるが、扱う多項式の次数に応じてこれより大きくても小さくてもよく、また多数または少数のセル２４を含んでよい。
【００５３】
本発明によれば、図３のエンジン１０ｂにおけるガロア体線形変換回路２０ｂの行列２２ｂの１行あたりのセル２４ｂの数は、行列２２ｂを２つの行列部と、行列部５０と、単位行列部５２とで設定することにより、ほぼ半数にまで減らし得る。前記単位行列部にはセル５４が１セットだけ必要で、これらの単位行列部のセルは、前記乗算回路の出力が、前記既約多項式の次数未満の次数を伴う多項式である場合に、剰余の予測を表す。これにより、図３において、前記既約多項式が次数８を有する場合、８次未満の任意の多項式は法を超えることがなく、前記行列を素通りするため、単位行列部５２内の空のセルは不要となる。これにより、前記行列２２ｂに必要なセルのほぼ半数が節約され、その結果より小型、単純、高速なエンジンが得られる。
【００５４】
図４の各セル２４ｂは、ＡＮＤ回路１００および排他的ＯＲ回路１０２を含んでよい。データ入力１０４および有効化入力１０６が提供される。排他的ＯＲ回路１０２は、出力が前記行列の出力に接続された最後の排他的ＯＲ回路と、入力が前記加算器入力、図３の４２ｂまたは図９の４２ｇに接続された最初の排他的ＯＲ回路とを除き、次の排他的ＯＲ回路の入力に線１０８で出力を提供し、前の排他的ＯＲ回路からの出力を入力１１０で受信する。線１０６上の許可信号により、線１０４上のデータはＡＮＤゲート１００を通過できるようになり、排他的ＯＲ回路１０２により線１１０上の入力と排他的論理和が取得される。線１０６上に許可信号がない場合、線１１０上の入力は、単に前記排他的ＯＲゲート１０２を通過し線１０８へ出力される。線１０６上の許可信号は、セル２４を有効にする。このように、前記行列全体はいかなる特定の既約多項式にも再設定できる。
【００５５】
図３のエンジン１０ｂの有効性は、チャートＩＩＩ（上記参照）から既約多項式を選択し、必要なセルを有効化することにより選択した既約多項式を導入するステップにより理解できる。例えば、既約多項式ｘ８＋ｘ４＋ｘ３＋ｘ２＋１を表す０ｘ１１ｄで表された８次の第１の多項式を導入する際は、総括的に２４ｃｃで示された有効化されたセルが、図３に示した一列のセル５４ｃが図５の単位行列５２ｃを形成する。第２の既約多項式をチャートＩＩＩから選ぶ際は、既約多項式ｘ８＋ｘ５＋ｘ３＋ｘ＋１である０ｘ１２ｂが図６の行列部５０ｄおよび単位行列５２ｄで有効化されたセル２４ｄｄのパターンを生成し、ここでも前記単位行列部５２ｄが再び一列に並んだ有効化されたセル５４ｄを形成する。
【００５６】
必要なセルの数の削減は、前記既約多項式と同じ次数を有する多項式だけに制限されない。これは、前記既約多項式の次数の半分以下の次数を有する任意の多項式にも適用される。例えば、図３に示し図５および図６の説明で言及している８×１５の行列２２ｂは、前記既約多項式の次数が１６で、これをサポートする行列が最高８次の多項式まではサポートしても９〜１５次の多項式はサポートしない場合、次数１、２、３、または４の多項式もサポートできるが、次数５、６、および７の多項式はサポートしない。これが次数３２の場合は、次数３２の多項式と次数１６までの多項式をサポートするが、次数１７〜３１の多項式はサポートしない。例えば図７に示したように、４次の既約多項式の場合、行列部５０ｅおよび単位行列部５２ｅは縮小し、行列２２ｅ内で実施可能になる。ここで、前記行列部５０ｅは、複数の有効化されたセル２４ｅｅとともに、単位行列５２ｅ内にも上記より短い列の有効化されたセルを有し、単位行列部５２ｅを形成している。
【００５７】
次数５、６、および７の中間体多項式に対応することが望ましい場合は、前記単位行列部を図８の疎行列部５２ｆで置換できる。ここで、次数７、６、および５の多項式をサポートするため、有効化されたセル５４ｆｆ、５４ｆｆｆ、および５４ｆｆｆｆを追加行として使用できる。ただし、行列サイズおよび必要なセル数の節約の度合いは落ちる。
【００５８】
本発明の別の特徴によれば、入力レジスタの数は３から２に削減でき、図９のデジタル信号プロセッサ（ＤＳＰ）２８ｇとの通信に必要な外部バスの数を削減し、エンジン１０ｇ自体の内部へと局在化できる。これにより、図９に示したように、入力レジスタはＡ １２ｇおよびＢ １４ｇの２つだけになり、出力３１ｇからのフィードバックはＤＳＰ ２８ｇを通過する必要がなくなり、その代わり直接ローカルにエンジン１０ｇ上において内部バス６０経由で乗算器入力選択回路６２および加算器入力選択回路６４へ送信されるようになる。デジタル信号プロセッサ２８ｇは、乗算器入力選択回路６２へは線６６で、加算器入力選択回路６４へは線６８で、制御信号を提供するだけで済むようになる。このように、乗算モードでは、乗算器入力選択回路６２は、Ｂレジスタ１４ｇから多項式乗算回路１８ｇへ入力を渡す一方、加算器入力選択回路６４は、加法単位元レベル、この場合アースレベル７０をガロア体線形変換回路２０ｇの前記加算器入力４２ｇに提供する。乗加算モードにおいて、デジタル信号プロセッサ２８は、行列２２ｇからの出力を線６０で多項式乗算回路１８ｇに戻すよう乗算器入力選択回路６２に命令し、Ｂレジスタ１４ｇ内の多項式をガロア体線形変換回路２０ｇの前記加算器入力４２ｇへ渡すよう加算入力選択回路６４に命令する。乗累算モードにおいて、デジタル信号プロセッサ２８ｇは、多項式をＢレジスタ１４ｇから多項式乗算回路１８ｇへ送信するよう乗算器入力選択回路６２に命令し、ガロア体線形変換回路２０ｇの出力を線６０で戻すよう加算入力選択回路６４に命令する。
【００５９】
本発明の更なる特徴は、セル２４ｇの選択的有効化によるガロア体線形変換回路２０ｇの再設定可能性である。再設定可能な制御回路８０は、セル２４ｇのうち選択された既約多項式の係数の実施に必要なものを選択的に有効にし、制御に必要なセル数は本発明に従い低減済みであるため、それ自体サイズが縮小可能である。
【００６０】
再設定可能なガロア体線形変換回路の演算は、２００２年５月１日出願済み米国特許出願第１０／１３６，１７０号、Ｓｔｅｉｎら、表題ＲＥＣＯＮＦＩＧ．ＵＲＡＢＬＥ ＩＮＰＵＴ ＧＡＬＯＩＳ ＦＩＥＬＤ ＬＩＮＥＡＲ ＴＲＡＮＳＦＯＲＭＥＲＥＲ ＳＹＳＴＥＭ（ＡＤ−３００Ｊ）に説明されており、そのすべての優先権出願および文書はこの参照によりその全体が本明細書に組み込むまれるものである。
【００６１】
上記では本発明についてエンジン１つだけに関し簡略化した説明をしてきたが、図１０に示したように複数のエンジンをまとめて使用してもよい。この図では、各エンジンが乗算回路１０ｈ、１０ｉ、１０ｊ、１０ｋ…１０ｎと、ガロア体線形変換回路２０ｈ、２０ｉ、２０ｊ、２０ｋ…２０ｎとを有し、これらすべてを再設定可能な単一の中央制御回路８０’が制御している。これらのエンジンは、同じビット数の多い（ワイドビット）［３２，６４，１２８］のＡレジスタおよびＢレジスタを共有し、それぞれ異なる８ビット（１バイト）セグメント上で動作するか、あるいはそれぞれ独自の再設定可能な制御ユニット８０ｈ、８０ｉ、８０ｊ、８０ｋ…８０ｎにより制御され、それぞれ独自のＡレジスタおよびＢレジスタの対Ａ０およびＢ０（１２ｈおよび１４ｈ）、Ａ１およびＢ１（２ｉおよび１４ｉ）、Ａ２およびＢ２（１２ｊおよび１４ｊ）、Ａ３およびＢ３（１２ｋおよび１４ｋ）などにより制御されることができる。
【００６２】
本明細書で示した出力ｃ０〜ｃ１４を提供する実施形態で使用可能な図１１の多項式乗算回路１８ｌは、複数のＡＮＤゲート１２０であって、排他的ＯＲゲート１２２と組み合わせることにより、図１２の表（チャート）１２４に例示したように、Ａレジスタ１２ｌおよびＢレジスタ１４ｌからの任意の多項式の対、例えば多項式ａ０〜ａ７、多項式ｂ０〜ｂ７を乗算できる複数のＡＮＤゲート１２０を含む。
【００６３】
この乗算器エンジンを乗算、乗加算、乗累算など単一用途専用にする場合、前記乗算器入力選択回路および加算器入力選択回路は、図１３、図１４、および図１５に示したように構造簡略化のため省略できる。
【００６４】
図１３のこのようなガロア体乗算器エンジン１００は、多項式乗算器回路１８ｐと、ガロア体変換回路２０ｐであって、前記乗算回路１８ｐから多項式の積を受信し、それを加算器入力４２ｐに加算して１０２で出力を生成する、ガロア体変換回路２０ｐとを含むが、ここでは加法単位元レベルが加算器入力に供給されている。
【００６５】
図１４のガロア体乗累算エンジン１０４は、多項式乗算回路１８ｑと、ガロア体変換回路２０ｑであって、乗算回路１８ｑから多項式の積を受信し、それを加算器入力４２ｑに加算して１０２ｑで出力を生成する、ガロア体変換回路２０ｑとを含む。ただし、ここでは前記出力１０２ｑは加算器入力４２ｐに戻されている。
【００６６】
図１５のガロア体乗加算エンジン１０８は、多項式乗算回路１８ｒと、ガロア体変換回路２０ｒであって、乗算回路１８ｒから多項式の積を受信し、それを加算器入力４２ｒに加算して１０２ｒで出力を生成する、ガロア体変換回路２０ｒとを含む。ただし、ここでは前記出力１０２ｒは乗算回路１８ｒに戻されている。
【００６７】
各特徴は、図面の一部のみで本発明の具体的な特徴を示しているが、これは単に便宜上のものであり、本発明に従って他の特徴のいずれか、またはすべてと組み合わせてもよい。本明細書における用語「含む」と「有する」と「伴う」とは、広義かつ包括的に解釈されるべきものであり、いかなる物理的相互接続にも限定されるものではない。さらに、掲題の用途に開示したいかなる実施形態も、考えうる唯一の実施形態として解釈されるべきではない。
【００６８】
当業者であれば、他の実施形態も以下の特許請求の範囲内であることが理解されるであろう。
【図面の簡単な説明】
【００６９】
当業者であれば、他の目的、特徴、および優位性が、以下の好適な実施形態の説明および添付の図面から理解されるであろう。
【図１】図１は、本発明に従う小型ガロア体乗算器エンジンの機能ブロック図。
【図２】図２は、本発明に従う従来の小型ガロア体乗算器エンジンの、より詳細な機能ブロック図。
【図３】図３は、本発明の特徴である小型化されたガロア体線形変換ユニット行列を示した、図１の小型ガロア体乗算器エンジンの、より詳細な機能ブロック図。
【図４】図４は、図２および図３のガロア体線形変換回路（乗算器エンジン）の前記行列用の典型的プログラム可能なＸＯＲ（またはＸ−ＯＲ）回路セルの概略図。
【図５】図５は、次数８の特定の多項式について、本発明による行列部および単位行列部のセルのプログラミングを例示した、図３および図９のガロア体線形変換回路の簡略化した模式図。
【図６】図６は、次数８の別の多項式について、本発明に係る行列部および単位行列部のセルのプログラミングを例示した、図３および図９のガロア体線形変換回路の簡略化した模式図。
【図７】図７は、次数４のさらに別の多項式について、本発明に従う行列部および単位行列部のセルのプログラミングを例示した、図３および図９のガロア体線形変換回路の簡略化した模式図。
【図８】図８は、この特定の実施形態において、半分の（４）次数および完全な（８）次数の間の多項式次数をサポートする疎行列としての第２行列部のプログラミングを例示した、図３および図９のガロア体線形変換回路の簡略化した模式図。
【図９】図９は、本発明の特徴である縮小サイズの行列と、縮小したハードウェアおよびローカルバスとの双方を組み込んだ、図１の小型ガロア体乗算器エンジンの、より詳細な機能ブロック図。
【図１０】図１０は、複数のガロア体線形変換ユニットを使用した、本発明に従うガロア体乗算器エンジンのブロック図。
【図１１】図１１は、図２、３、５、および９で使用可能な多項式乗算器の概略図。
【図１２】図１２は、図１１の多項式乗算器の伝達関数を例示した図。
【図１３】図１３は、本発明に従う乗算演算専用のガロア体乗算器エンジンの簡略化した模式図。
【図１４】図１４は、本発明に従う乗累算演算専用のガロア体乗算器エンジンの簡略化した模式図。
【図１５】図１５は、本発明に従う乗加算演算専用のガロア体乗算器エンジンの簡略化した模式図。
【特許請求の範囲】
【請求項１】
小型ガロア体乗算器エンジンであって、
乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する乗算回路と、
ガロア体線形変換回路であって、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有する、ガロア体線形変換回路と、
前記乗算回路への第１の多項式入力と、
第２の多項式入力と、
乗算器入力選択回路であって、乗算モードでは前記第２の多項式を、乗加算モードでは前記ガロア体線形変換回路の出力を、そして乗累算モードでは前記第２の多項式を前記乗算回路に提供する、乗算器入力選択回路と、
加算器入力選択回路であって、前記乗算モードでは加法単位元を、前記乗加算モードでは前記第２の多項式入力を、そして前記乗累算モードでは前記ガロア体線形変換回路の出力を、前記ガロア体線形変換回路の加算入力に提供し、前記入力多項式のガロア体乗算関数と、ガロア体乗加算関数と、ガロア体乗累算関数とを取得する、加算器入力選択回路と
を有する小型ガロア体乗算器エンジン。
【請求項２】
請求項１の小型ガロア体乗算器エンジンにおいて、前記乗算回路は、前記多項式の積の各項用にＡＮＤ論理回路を含み、ガロア体乗算器を実現するものである。
【請求項３】
請求項１の小型ガロア体乗算器エンジンにおいて、前記乗算回路は、ガロア体における総和をもたらすため、前記多項式の積における項の各対に排他的ＯＲ論理回路を含むものである。
【請求項４】
請求項１の小型ガロア体乗算器エンジンにおいて、前記ガロア体線形変換回路は、セルの行列であって、各セルが排他的ＯＲ論理回路と、前記排他的ＯＲ論理回路に接続された出力を有するＡＮＤ論理回路と、入力データビットを受信するための入力とを含む、セルの行列を含むものである。
【請求項５】
請求項１の小型ガロア体乗算器エンジンにおいて、前記ガロア体線形変換回路の出力は、前記エンジンのローカルバス経由で前記乗算器入力選択回路および前記加算器入力選択回路に戻されるものである。
【請求項６】
請求項１の小型ガロア体乗算器エンジンにおいて、前記乗算器入力選択回路は、前記ガロア体線形変換回路の出力からの入力と、前記第２の多項式からの入力とを含むものである。
【請求項７】
請求項１の小型ガロア体乗算器エンジンにおいて、前記加算器入力選択回路は、前記ガロア体線形変換回路の出力からの入力と、前記第２の多項式からの入力と、加法単位元入力とを含むものである。
【請求項８】
請求項４の小型ガロア体乗算器エンジンにおいて、各前記排他的ＯＲ論理回路は、出力が前記行列の出力に接続された最後の排他的ＯＲ論理回路と、入力が前記加算器入力選択回路に接続された最初の排他的ＯＲ論理回路とを除き、次に続く排他的ＯＲ論理回路の入力に接続された出力を有するものである。
【請求項９】
請求項１の小型ガロア体乗算器エンジンにおいて、この小型ガロア体乗算器エンジンは、さらに、
所定の既約多項式に関する剰余を予測するための係数のセットを前記ガロア体線形変換回路に供給する再設定可能な制御回路を含むものである。
【請求項１０】
請求項９の小型ガロア体乗算器エンジンにおいて、前記ガロア体線形変換回路は複数のガロア体変換ユニットを含み、前記再設定可能な制御回路は、前記係数を並行して前記ガロア体変換ユニットに供給するものである。
【請求項１１】
請求項１の小型ガロア体乗算器エンジンにおいて、前記ガロア体線形変換回路は、行列部および単位行列部で設定された複数のセルを含み、前記単位行列部のセルは、前記乗算回路の出力が、前記既約多項式の次数未満の次数を伴う多項式である場合に剰余の予測を表すものである。
【請求項１２】
請求項９の小型ガロア体乗算器エンジンにおいて、前記ガロア体線形変換回路は複数のガロア体変換ユニットを含み、前記再設定可能な制御回路は、それぞれが各前記ガロア体線形変換ユニットに関連付けられた複数の再設定可能な制御ユニットを含むものである。
【請求項１３】
請求項１の小型ガロア体乗算器エンジンにおいて、前記入力多項式の前記関数は１サイクルで生成されるものである。
【請求項１４】
請求項９の小型ガロア体乗算器エンジンにおいて、前記加法単位元はヌルレベルである。
【請求項１５】
小型ガロア体乗算器エンジンであって、
乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する、乗算回路と、
ガロア体線形変換回路であって、前記乗算回路からの乗算入力を有し、既約多項式について前記多項式の積の剰余を予測する、ガロア体線形変換回路と、
前記乗算回路への第１の多項式入力と、
第２の多項式入力と、
加算器入力選択回路であって、前記ガロア体線形変換回路の加算入力に乗算モードで加法単位元レベルを提供し、入力多項式のガロア体乗算関数を取得する、加算器入力選択回路と
を有する小型ガロア体乗算器エンジン。
【請求項１６】
請求項１５の小型ガロア体乗算器エンジンにおいて、前記乗算回路は、前記多項式の積の各項用にＡＮＤ論理回路を含み、ガロア乗算器を実現するものである。
【請求項１７】
請求項１５の小型ガロア体乗算器エンジンにおいて、前記乗算回路は、前記多項式の積における項の各対に排他的ＯＲ論理回路を含み、ガロア体における総和をもたらすものである。
【請求項１８】
請求項１５の小型ガロア体乗算器エンジンにおいて、前記ガロア体線形変換回路は、セルの行列であって、各セルが排他的ＯＲ論理回路と、前記排他的ＯＲ論理回路に接続された出力を有するＡＮＤ論理回路と、入力データビットを受信するための入力とを含む、セルの行列を含むものである。
【請求項１９】
請求項１５の小型ガロア体乗算器エンジンにおいて、前記加算器入力選択回路は、前記ガロア体線形変換回路の出力からの入力と、前記第２の多項式からの入力と、加法単位元入力とを含むものである。
【請求項２０】
請求項１８の小型ガロア体乗算器エンジンにおいて、各前記排他的ＯＲ論理回路は、出力が前記行列の出力に接続された最後の排他的ＯＲ論理回路と、入力が前記加算器入力選択回路に接続された最初の排他的ＯＲ論理回路とを除き、次に続く排他的ＯＲ論理回路の入力に接続された出力を有するものである。
【請求項２１】
請求項１５の小型ガロア体乗算器エンジンにおいて、この小型ガロア体乗算器エンジンは、さらに、
所定の既約多項式に関する剰余を予測するための係数のセットを前記ガロア体線形変換回路に供給する再設定可能な制御回路を含むものである。
【請求項２２】
請求項２１の小型ガロア体乗算器エンジンにおいて、前記ガロア体線形変換回路は複数のガロア体変換ユニットを含み、前記再設定可能な制御回路は、前記係数を並行して前記ガロア体変換ユニットに供給するものである。
【請求項２３】
請求項１５の小型ガロア体乗算器エンジンにおいて、前記ガロア体線形変換回路は、行列部および単位行列部で設定された複数のセルを含み、前記単位行列部のセルは、前記乗算回路の出力が、前記既約多項式の次数未満の次数を伴う多項式である場合に剰余の予測を表すものである。
【請求項２４】
請求項２１の小型ガロア体乗算器エンジンにおいて、前記ガロア体線形変換回路は複数のガロア体変換ユニットを含み、前記再設定可能な制御回路は、それぞれが各前記ガロア体線形変換ユニットに関連付けられた複数の再設定可能な制御ユニットを含むものである。
【請求項２５】
請求項１５の小型ガロア体乗算器エンジンにおいて、前記入力多項式の前記関数は１サイクルで生成されるものである。
【請求項２６】
請求項１５の小型ガロア体乗算器エンジンにおいて、前記加法単位元レベルはヌルレベルである。
【請求項２７】
小型ガロア体乗算器エンジンであって、
乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する、乗算回路と、
ガロア体線形変換回路であって、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有する、ガロア体線形変換回路と、
前記乗算回路への第１の多項式入力と、
第２の多項式入力 前記ガロア体線形変換回路の出力
加算器入力選択回路であって、前記ガロア体線形変換回路の加算入力に、乗加算モードで前記第２の多項式入力を提供し、入力多項式のガロア体乗加算関数を取得する、加算器入力選択回路と
を有する小型ガロア体乗算器エンジン。
【請求項２８】
請求項２７の小型ガロア体乗算器エンジンにおいて、前記入力多項式の前記関数は１サイクルで生成されるものである。
【請求項２９】
請求項２７の小型ガロア体乗算器エンジンにおいて、前記加法単位元レベルはヌルレベルである。
【請求項３０】
小型ガロア体乗算器エンジンであって、
乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する、乗算回路と、
ガロア体線形変換回路であって、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有する、ガロア体線形変換回路と、
前記乗算回路への第１の多項式入力と、
第２の多項式入力と、
加算器入力選択回路であって、前記ガロア体線形変換回路の加算入力に、乗累算モードで前記ガロア体線形変換回路の出力を提供し、入力多項式のガロア体乗累算関数を取得する、加算器入力選択回路と
を有する小型ガロア体乗算器エンジン。
【請求項３１】
請求項３０の小型ガロア体乗算器エンジンにおいて、前記入力多項式の前記関数は１サイクルで生成されるものである。
【請求項３２】
請求項３０の小型ガロア体乗算器エンジンにおいて、前記加法単位元レベルはヌルレベルである。
【請求項３３】
小型ガロア体乗算器エンジンであって、
乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する、乗算回路と、
ガロア体線形変換回路であって、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有する、ガロア体線形変換回路と、
前記乗算回路への第１の多項式入力と、
第２の多項式入力と、
乗算器入力選択回路であって、乗算モードでは前記第２の多項式を、そして乗加算モードでは前記ガロア体線形変換回路の出力を、前記乗算回路に提供する乗算器入力選択回路と、
加算器入力選択回路であって、前記乗算モードでは加法単位元レベルを、そして前記乗加算モードでは前記第２の多項式入力を、前記ガロア体線形変換回路の加算入力に提供し、入力多項式のガロア体乗算関数およびガロア体乗加算関数を取得する、加算器入力選択回路と
を有する小型ガロア体乗算器エンジン。
【請求項３４】
請求項３３の小型ガロア体乗算器エンジンにおいて、前記入力多項式の前記関数は１サイクルで生成されるものである。
【請求項３５】
請求項３３の小型ガロア体乗算器エンジンにおいて、前記加法単位元レベルはヌルレベルである。
【請求項３６】
小型ガロア体乗算器エンジンであって、
乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する、乗算回路と、
ガロア体線形変換回路であって、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有する、ガロア体線形変換回路と、
前記乗算回路への第１の多項式入力と、
第２の多項式入力と、
乗算器入力選択回路であって、乗算モードでは前記第２の多項式を、そして乗累算モードでは前記第２の多項式を、前記乗算回路に提供する乗算器入力選択回路と、
加算器入力選択回路であって、前記乗算モードでは加法単位元レベルを、前記乗累算モードでは前記ガロア体線形変換回路の出力を、前記ガロア体線形変換回路の加算入力に提供し、入力多項式のガロア体乗算関数およびガロア体乗累算関数を取得する、加算器入力選択回路と
を有する小型ガロア体乗算器エンジン。
【請求項３７】
請求項３６の小型ガロア体乗算器エンジンにおいて、前記入力多項式の前記関数は１サイクルで生成されるものである。
【請求項３８】
請求項３６の小型ガロア体乗算器エンジンにおいて、前記加法単位元レベルはヌルレベルである。
【請求項３９】
小型ガロア体乗算器エンジンであって、
乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する、乗算回路と、
ガロア体線形変換回路であって、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有する、ガロア体線形変換回路と、
前記乗算回路への第１の多項式入力と、
第２の多項式入力と、
乗算器入力選択回路であって、乗加算モードでは前記ガロア体線形変換回路の出力を、そして乗累算モードでは前記第２の多項式を、前記乗算回路に提供する乗算器入力選択回路と、
加算器入力選択回路であって、前記乗加算モードでは前記第２の多項式入力を、前記乗累算モードでは前記ガロア体線形変換回路の出力を、前記ガロア体線形変換回路の加算入力に提供し、入力多項式のガロア体乗加算関数およびガロア体乗累算関数を取得する、加算器入力選択回路と
を有する小型ガロア体乗算器エンジン。
【請求項４０】
請求項３９の小型ガロア体乗算器エンジンにおいて、前記入力多項式の前記関数は１サイクルで生成されるものである。
【請求項４１】
請求項３９の小型ガロア体乗算器エンジンにおいて、前記加法単位元レベルはヌルレベルである。
【請求項４２】
小型ガロア体並列乗算回路であって、
乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する、乗算回路と、
既約多項式に関する多項式の積の剰余を予測するためのガロア体線形変換回路であって、行列部および単位行列部で設定された複数のセルを含み、前記単位行列部のセルは、前記乗算回路の出力が、前記既約多項式の次数未満の次数を伴う多項式である場合に剰余の予測を表す、ガロア体線形変換回路と
を有する小型ガロア体並列乗算回路。
【請求項４３】
請求項４２の小型ガロア体並列乗算回路において、各前記セルは、プログラム可能な排他的ＯＲセルを含むものである。
【請求項４４】
請求項４３の小型ガロア体並列乗算回路において、前記プログラム可能な排他的ＯＲセルは、排他的ＯＲ回路およびＡＮＤ回路を含むものである。
【請求項４５】
請求項４２の小型ガロア体並列乗算回路において、この小型ガロア体並列乗算回路は、さらに、
所定の既約多項式について剰余を予測するための係数のセットを前記ガロア体線形変換回路に供給する再設定可能な制御回路を含むものである。
【請求項４６】
請求項４５の小型ガロア体並列乗算回路において、前記ガロア体線形変換回路は、複数のガロア体線形変換ユニットを含むものである。
【請求項４７】
請求項４５の小型ガロア体並列乗算回路において、前記再設定可能な制御回路は、前記係数を並行して前記ガロア体線形変換ユニットに供給するものである。
【請求項４８】
請求項４５の小型ガロア体並列乗算回路において、前記再設定可能な制御回路は、それぞれが各前記ガロア体線形変換ユニットに関連付けられた複数の再設定可能な制御ユニットを含むものである。
【請求項４９】
小型ガロア体乗算器エンジンであって、
乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する乗算回路と、
前記乗算回路への第１の多項式入力と、
前記乗算回路への第２の多項式入力と、
ガロア体線形変換回路であって、既約多項式について前記多項式の積の剰余を予測する目的で、前記乗算回路からの乗算入力を有し、前記入力多項式のガロア体乗算関数を取得する、ガロア体線形変換回路と
を有する小型ガロア体乗算器エンジン。
【請求項５０】
請求項４９の小型ガロア体乗算器エンジンにおいて、前記ガロア体線形変換回路は、セルの行列であって、各セルが排他的ＯＲ論理回路と、前記排他的ＯＲ論理回路に接続された出力を有するＡＮＤ論理回路と、入力データビットを受信するための入力とを含む、セルの行列を含むものである。
【請求項５１】
請求項５０の小型ガロア体乗算器エンジンにおいて、各前記排他的ＯＲ論理回路は、出力が前記行列の出力に接続された最後の排他的ＯＲ論理回路と、前記入力多項式のガロア体乗算関数を取得するため入力が加法単位元レベルに接続された最初の排他的ＯＲ論理回路とを除き、次に続く排他的ＯＲ論理回路の入力に接続された出力を有するものである。
【請求項５２】
小型ガロア体乗加算エンジンであって、
乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、それらの多項式の積を取得する乗算回路と、
ガロア体線形変換回路であって、前記乗算回路からの前記多項式の積と、前記ガロア体線形変換回路の加算入力における多項式入力とに応答し、入力多項式のガロア体乗加算関数を取得するため、既約多項式に関する前記多項式の積の予測剰余を前記加算入力に加算することにより前記多項式入力の１つを前記乗算器に提供する、ガロア体線形変換回路と
を有する小型ガロア体乗加算エンジン。
【請求項５３】
請求項５２の小型ガロア体乗加算エンジンにおいて、前記ガロア体線形変換回路は、セルの行列であって、各セルが排他的ＯＲ論理回路と、前記排他的ＯＲ論理回路に接続された出力を有するＡＮＤ論理回路と、入力データビットを受信するための入力とを含む、セルの行列を含むものである。
【請求項５４】
請求項５３の小型ガロア体乗加算エンジンにおいて、各前記排他的ＯＲ論理回路は、出力が前記行列の出力に接続された最後の排他的ＯＲ論理回路と、前記入力多項式のガロア体乗加算関数を取得するため入力が第２の多項式入力に接続された最初の排他的ＯＲ論理回路とを除き、次に続く排他的ＯＲ論理回路の入力に接続された出力を有するものである。
【請求項５５】
小型ガロア体乗累算エンジンであって、
乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、それらの多項式の積を取得する乗算回路と、
前記乗算回路への第１の多項式入力と、
前記乗算回路への第２の多項式入力と、
ガロア体線形変換回路であって、前記乗算回路からの前記多項式の積と、多項式加算入力であって、既約多項式に関する前記多項式の積の予測剰余を前記加算入力に加算するための多項式加算入力とに応答し、入力多項式のガロア体乗累算関数を取得する、ガロア体線形変換回路と
を有し、
前記出力が、前記ガロア体線形変換回路の加算入力に前記多項式を提供する
小型ガロア体乗累算エンジン。
【請求項５６】
請求項５５の小型ガロア体乗累算エンジンにおいて、前記ガロア体線形変換回路は、セルの行列であって、各セルが排他的ＯＲ論理回路と、前記排他的ＯＲ論理回路に接続された出力を有するＡＮＤ論理回路と、入力データビットを受信するための入力とを含む、セルの行列を含むものである。
【請求項５７】
請求項５の小型ガロア体乗算器エンジンにおいて、各前記排他的ＯＲ論理回路は、出力が前記行列の出力に接続された最後の排他的ＯＲ論理回路と、前記入力多項式のガロア体乗累算関数を取得するため入力が前記ガロア体線形変換回路の出力に接続された最初の排他的ＯＲ論理回路とを除き、次に続く排他的ＯＲ論理回路の入力に接続された出力を有するものである。
【請求項１】
小型ガロア体乗算器エンジンであって、
乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する乗算回路と、
ガロア体線形変換回路であって、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有する、ガロア体線形変換回路と、
前記乗算回路への第１の多項式入力と、
第２の多項式入力と、
乗算器入力選択回路であって、乗算モードでは前記第２の多項式を、乗加算モードでは前記ガロア体線形変換回路の出力を、そして乗累算モードでは前記第２の多項式を前記乗算回路に提供する、乗算器入力選択回路と、
加算器入力選択回路であって、前記乗算モードでは加法単位元を、前記乗加算モードでは前記第２の多項式入力を、そして前記乗累算モードでは前記ガロア体線形変換回路の出力を、前記ガロア体線形変換回路の加算入力に提供し、前記入力多項式のガロア体乗算関数と、ガロア体乗加算関数と、ガロア体乗累算関数とを取得する、加算器入力選択回路と
を有する小型ガロア体乗算器エンジン。
【請求項２】
請求項１の小型ガロア体乗算器エンジンにおいて、前記乗算回路は、前記多項式の積の各項用にＡＮＤ論理回路を含み、ガロア体乗算器を実現するものである。
【請求項３】
請求項１の小型ガロア体乗算器エンジンにおいて、前記乗算回路は、ガロア体における総和をもたらすため、前記多項式の積における項の各対に排他的ＯＲ論理回路を含むものである。
【請求項４】
請求項１の小型ガロア体乗算器エンジンにおいて、前記ガロア体線形変換回路は、セルの行列であって、各セルが排他的ＯＲ論理回路と、前記排他的ＯＲ論理回路に接続された出力を有するＡＮＤ論理回路と、入力データビットを受信するための入力とを含む、セルの行列を含むものである。
【請求項５】
請求項１の小型ガロア体乗算器エンジンにおいて、前記ガロア体線形変換回路の出力は、前記エンジンのローカルバス経由で前記乗算器入力選択回路および前記加算器入力選択回路に戻されるものである。
【請求項６】
請求項１の小型ガロア体乗算器エンジンにおいて、前記乗算器入力選択回路は、前記ガロア体線形変換回路の出力からの入力と、前記第２の多項式からの入力とを含むものである。
【請求項７】
請求項１の小型ガロア体乗算器エンジンにおいて、前記加算器入力選択回路は、前記ガロア体線形変換回路の出力からの入力と、前記第２の多項式からの入力と、加法単位元入力とを含むものである。
【請求項８】
請求項４の小型ガロア体乗算器エンジンにおいて、各前記排他的ＯＲ論理回路は、出力が前記行列の出力に接続された最後の排他的ＯＲ論理回路と、入力が前記加算器入力選択回路に接続された最初の排他的ＯＲ論理回路とを除き、次に続く排他的ＯＲ論理回路の入力に接続された出力を有するものである。
【請求項９】
請求項１の小型ガロア体乗算器エンジンにおいて、この小型ガロア体乗算器エンジンは、さらに、
所定の既約多項式に関する剰余を予測するための係数のセットを前記ガロア体線形変換回路に供給する再設定可能な制御回路を含むものである。
【請求項１０】
請求項９の小型ガロア体乗算器エンジンにおいて、前記ガロア体線形変換回路は複数のガロア体変換ユニットを含み、前記再設定可能な制御回路は、前記係数を並行して前記ガロア体変換ユニットに供給するものである。
【請求項１１】
請求項１の小型ガロア体乗算器エンジンにおいて、前記ガロア体線形変換回路は、行列部および単位行列部で設定された複数のセルを含み、前記単位行列部のセルは、前記乗算回路の出力が、前記既約多項式の次数未満の次数を伴う多項式である場合に剰余の予測を表すものである。
【請求項１２】
請求項９の小型ガロア体乗算器エンジンにおいて、前記ガロア体線形変換回路は複数のガロア体変換ユニットを含み、前記再設定可能な制御回路は、それぞれが各前記ガロア体線形変換ユニットに関連付けられた複数の再設定可能な制御ユニットを含むものである。
【請求項１３】
請求項１の小型ガロア体乗算器エンジンにおいて、前記入力多項式の前記関数は１サイクルで生成されるものである。
【請求項１４】
請求項９の小型ガロア体乗算器エンジンにおいて、前記加法単位元はヌルレベルである。
【請求項１５】
小型ガロア体乗算器エンジンであって、
乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する、乗算回路と、
ガロア体線形変換回路であって、前記乗算回路からの乗算入力を有し、既約多項式について前記多項式の積の剰余を予測する、ガロア体線形変換回路と、
前記乗算回路への第１の多項式入力と、
第２の多項式入力と、
加算器入力選択回路であって、前記ガロア体線形変換回路の加算入力に乗算モードで加法単位元レベルを提供し、入力多項式のガロア体乗算関数を取得する、加算器入力選択回路と
を有する小型ガロア体乗算器エンジン。
【請求項１６】
請求項１５の小型ガロア体乗算器エンジンにおいて、前記乗算回路は、前記多項式の積の各項用にＡＮＤ論理回路を含み、ガロア乗算器を実現するものである。
【請求項１７】
請求項１５の小型ガロア体乗算器エンジンにおいて、前記乗算回路は、前記多項式の積における項の各対に排他的ＯＲ論理回路を含み、ガロア体における総和をもたらすものである。
【請求項１８】
請求項１５の小型ガロア体乗算器エンジンにおいて、前記ガロア体線形変換回路は、セルの行列であって、各セルが排他的ＯＲ論理回路と、前記排他的ＯＲ論理回路に接続された出力を有するＡＮＤ論理回路と、入力データビットを受信するための入力とを含む、セルの行列を含むものである。
【請求項１９】
請求項１５の小型ガロア体乗算器エンジンにおいて、前記加算器入力選択回路は、前記ガロア体線形変換回路の出力からの入力と、前記第２の多項式からの入力と、加法単位元入力とを含むものである。
【請求項２０】
請求項１８の小型ガロア体乗算器エンジンにおいて、各前記排他的ＯＲ論理回路は、出力が前記行列の出力に接続された最後の排他的ＯＲ論理回路と、入力が前記加算器入力選択回路に接続された最初の排他的ＯＲ論理回路とを除き、次に続く排他的ＯＲ論理回路の入力に接続された出力を有するものである。
【請求項２１】
請求項１５の小型ガロア体乗算器エンジンにおいて、この小型ガロア体乗算器エンジンは、さらに、
所定の既約多項式に関する剰余を予測するための係数のセットを前記ガロア体線形変換回路に供給する再設定可能な制御回路を含むものである。
【請求項２２】
請求項２１の小型ガロア体乗算器エンジンにおいて、前記ガロア体線形変換回路は複数のガロア体変換ユニットを含み、前記再設定可能な制御回路は、前記係数を並行して前記ガロア体変換ユニットに供給するものである。
【請求項２３】
請求項１５の小型ガロア体乗算器エンジンにおいて、前記ガロア体線形変換回路は、行列部および単位行列部で設定された複数のセルを含み、前記単位行列部のセルは、前記乗算回路の出力が、前記既約多項式の次数未満の次数を伴う多項式である場合に剰余の予測を表すものである。
【請求項２４】
請求項２１の小型ガロア体乗算器エンジンにおいて、前記ガロア体線形変換回路は複数のガロア体変換ユニットを含み、前記再設定可能な制御回路は、それぞれが各前記ガロア体線形変換ユニットに関連付けられた複数の再設定可能な制御ユニットを含むものである。
【請求項２５】
請求項１５の小型ガロア体乗算器エンジンにおいて、前記入力多項式の前記関数は１サイクルで生成されるものである。
【請求項２６】
請求項１５の小型ガロア体乗算器エンジンにおいて、前記加法単位元レベルはヌルレベルである。
【請求項２７】
小型ガロア体乗算器エンジンであって、
乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する、乗算回路と、
ガロア体線形変換回路であって、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有する、ガロア体線形変換回路と、
前記乗算回路への第１の多項式入力と、
第２の多項式入力 前記ガロア体線形変換回路の出力
加算器入力選択回路であって、前記ガロア体線形変換回路の加算入力に、乗加算モードで前記第２の多項式入力を提供し、入力多項式のガロア体乗加算関数を取得する、加算器入力選択回路と
を有する小型ガロア体乗算器エンジン。
【請求項２８】
請求項２７の小型ガロア体乗算器エンジンにおいて、前記入力多項式の前記関数は１サイクルで生成されるものである。
【請求項２９】
請求項２７の小型ガロア体乗算器エンジンにおいて、前記加法単位元レベルはヌルレベルである。
【請求項３０】
小型ガロア体乗算器エンジンであって、
乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する、乗算回路と、
ガロア体線形変換回路であって、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有する、ガロア体線形変換回路と、
前記乗算回路への第１の多項式入力と、
第２の多項式入力と、
加算器入力選択回路であって、前記ガロア体線形変換回路の加算入力に、乗累算モードで前記ガロア体線形変換回路の出力を提供し、入力多項式のガロア体乗累算関数を取得する、加算器入力選択回路と
を有する小型ガロア体乗算器エンジン。
【請求項３１】
請求項３０の小型ガロア体乗算器エンジンにおいて、前記入力多項式の前記関数は１サイクルで生成されるものである。
【請求項３２】
請求項３０の小型ガロア体乗算器エンジンにおいて、前記加法単位元レベルはヌルレベルである。
【請求項３３】
小型ガロア体乗算器エンジンであって、
乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する、乗算回路と、
ガロア体線形変換回路であって、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有する、ガロア体線形変換回路と、
前記乗算回路への第１の多項式入力と、
第２の多項式入力と、
乗算器入力選択回路であって、乗算モードでは前記第２の多項式を、そして乗加算モードでは前記ガロア体線形変換回路の出力を、前記乗算回路に提供する乗算器入力選択回路と、
加算器入力選択回路であって、前記乗算モードでは加法単位元レベルを、そして前記乗加算モードでは前記第２の多項式入力を、前記ガロア体線形変換回路の加算入力に提供し、入力多項式のガロア体乗算関数およびガロア体乗加算関数を取得する、加算器入力選択回路と
を有する小型ガロア体乗算器エンジン。
【請求項３４】
請求項３３の小型ガロア体乗算器エンジンにおいて、前記入力多項式の前記関数は１サイクルで生成されるものである。
【請求項３５】
請求項３３の小型ガロア体乗算器エンジンにおいて、前記加法単位元レベルはヌルレベルである。
【請求項３６】
小型ガロア体乗算器エンジンであって、
乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する、乗算回路と、
ガロア体線形変換回路であって、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有する、ガロア体線形変換回路と、
前記乗算回路への第１の多項式入力と、
第２の多項式入力と、
乗算器入力選択回路であって、乗算モードでは前記第２の多項式を、そして乗累算モードでは前記第２の多項式を、前記乗算回路に提供する乗算器入力選択回路と、
加算器入力選択回路であって、前記乗算モードでは加法単位元レベルを、前記乗累算モードでは前記ガロア体線形変換回路の出力を、前記ガロア体線形変換回路の加算入力に提供し、入力多項式のガロア体乗算関数およびガロア体乗累算関数を取得する、加算器入力選択回路と
を有する小型ガロア体乗算器エンジン。
【請求項３７】
請求項３６の小型ガロア体乗算器エンジンにおいて、前記入力多項式の前記関数は１サイクルで生成されるものである。
【請求項３８】
請求項３６の小型ガロア体乗算器エンジンにおいて、前記加法単位元レベルはヌルレベルである。
【請求項３９】
小型ガロア体乗算器エンジンであって、
乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する、乗算回路と、
ガロア体線形変換回路であって、前記乗算回路からの乗算入力と、加算入力と、既約多項式に関する多項式の積の予測剰余を前記加算入力に加算するための出力とを有する、ガロア体線形変換回路と、
前記乗算回路への第１の多項式入力と、
第２の多項式入力と、
乗算器入力選択回路であって、乗加算モードでは前記ガロア体線形変換回路の出力を、そして乗累算モードでは前記第２の多項式を、前記乗算回路に提供する乗算器入力選択回路と、
加算器入力選択回路であって、前記乗加算モードでは前記第２の多項式入力を、前記乗累算モードでは前記ガロア体線形変換回路の出力を、前記ガロア体線形変換回路の加算入力に提供し、入力多項式のガロア体乗加算関数およびガロア体乗累算関数を取得する、加算器入力選択回路と
を有する小型ガロア体乗算器エンジン。
【請求項４０】
請求項３９の小型ガロア体乗算器エンジンにおいて、前記入力多項式の前記関数は１サイクルで生成されるものである。
【請求項４１】
請求項３９の小型ガロア体乗算器エンジンにおいて、前記加法単位元レベルはヌルレベルである。
【請求項４２】
小型ガロア体並列乗算回路であって、
乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する、乗算回路と、
既約多項式に関する多項式の積の剰余を予測するためのガロア体線形変換回路であって、行列部および単位行列部で設定された複数のセルを含み、前記単位行列部のセルは、前記乗算回路の出力が、前記既約多項式の次数未満の次数を伴う多項式である場合に剰余の予測を表す、ガロア体線形変換回路と
を有する小型ガロア体並列乗算回路。
【請求項４３】
請求項４２の小型ガロア体並列乗算回路において、各前記セルは、プログラム可能な排他的ＯＲセルを含むものである。
【請求項４４】
請求項４３の小型ガロア体並列乗算回路において、前記プログラム可能な排他的ＯＲセルは、排他的ＯＲ回路およびＡＮＤ回路を含むものである。
【請求項４５】
請求項４２の小型ガロア体並列乗算回路において、この小型ガロア体並列乗算回路は、さらに、
所定の既約多項式について剰余を予測するための係数のセットを前記ガロア体線形変換回路に供給する再設定可能な制御回路を含むものである。
【請求項４６】
請求項４５の小型ガロア体並列乗算回路において、前記ガロア体線形変換回路は、複数のガロア体線形変換ユニットを含むものである。
【請求項４７】
請求項４５の小型ガロア体並列乗算回路において、前記再設定可能な制御回路は、前記係数を並行して前記ガロア体線形変換ユニットに供給するものである。
【請求項４８】
請求項４５の小型ガロア体並列乗算回路において、前記再設定可能な制御回路は、それぞれが各前記ガロア体線形変換ユニットに関連付けられた複数の再設定可能な制御ユニットを含むものである。
【請求項４９】
小型ガロア体乗算器エンジンであって、
乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、その積を取得する乗算回路と、
前記乗算回路への第１の多項式入力と、
前記乗算回路への第２の多項式入力と、
ガロア体線形変換回路であって、既約多項式について前記多項式の積の剰余を予測する目的で、前記乗算回路からの乗算入力を有し、前記入力多項式のガロア体乗算関数を取得する、ガロア体線形変換回路と
を有する小型ガロア体乗算器エンジン。
【請求項５０】
請求項４９の小型ガロア体乗算器エンジンにおいて、前記ガロア体線形変換回路は、セルの行列であって、各セルが排他的ＯＲ論理回路と、前記排他的ＯＲ論理回路に接続された出力を有するＡＮＤ論理回路と、入力データビットを受信するための入力とを含む、セルの行列を含むものである。
【請求項５１】
請求項５０の小型ガロア体乗算器エンジンにおいて、各前記排他的ＯＲ論理回路は、出力が前記行列の出力に接続された最後の排他的ＯＲ論理回路と、前記入力多項式のガロア体乗算関数を取得するため入力が加法単位元レベルに接続された最初の排他的ＯＲ論理回路とを除き、次に続く排他的ＯＲ論理回路の入力に接続された出力を有するものである。
【請求項５２】
小型ガロア体乗加算エンジンであって、
乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、それらの多項式の積を取得する乗算回路と、
ガロア体線形変換回路であって、前記乗算回路からの前記多項式の積と、前記ガロア体線形変換回路の加算入力における多項式入力とに応答し、入力多項式のガロア体乗加算関数を取得するため、既約多項式に関する前記多項式の積の予測剰余を前記加算入力に加算することにより前記多項式入力の１つを前記乗算器に提供する、ガロア体線形変換回路と
を有する小型ガロア体乗加算エンジン。
【請求項５３】
請求項５２の小型ガロア体乗加算エンジンにおいて、前記ガロア体線形変換回路は、セルの行列であって、各セルが排他的ＯＲ論理回路と、前記排他的ＯＲ論理回路に接続された出力を有するＡＮＤ論理回路と、入力データビットを受信するための入力とを含む、セルの行列を含むものである。
【請求項５４】
請求項５３の小型ガロア体乗加算エンジンにおいて、各前記排他的ＯＲ論理回路は、出力が前記行列の出力に接続された最後の排他的ＯＲ論理回路と、前記入力多項式のガロア体乗加算関数を取得するため入力が第２の多項式入力に接続された最初の排他的ＯＲ論理回路とを除き、次に続く排他的ＯＲ論理回路の入力に接続された出力を有するものである。
【請求項５５】
小型ガロア体乗累算エンジンであって、
乗算回路であって、ガロア体上の係数を伴う２つの多項式を乗算し、それらの多項式の積を取得する乗算回路と、
前記乗算回路への第１の多項式入力と、
前記乗算回路への第２の多項式入力と、
ガロア体線形変換回路であって、前記乗算回路からの前記多項式の積と、多項式加算入力であって、既約多項式に関する前記多項式の積の予測剰余を前記加算入力に加算するための多項式加算入力とに応答し、入力多項式のガロア体乗累算関数を取得する、ガロア体線形変換回路と
を有し、
前記出力が、前記ガロア体線形変換回路の加算入力に前記多項式を提供する
小型ガロア体乗累算エンジン。
【請求項５６】
請求項５５の小型ガロア体乗累算エンジンにおいて、前記ガロア体線形変換回路は、セルの行列であって、各セルが排他的ＯＲ論理回路と、前記排他的ＯＲ論理回路に接続された出力を有するＡＮＤ論理回路と、入力データビットを受信するための入力とを含む、セルの行列を含むものである。
【請求項５７】
請求項５の小型ガロア体乗算器エンジンにおいて、各前記排他的ＯＲ論理回路は、出力が前記行列の出力に接続された最後の排他的ＯＲ論理回路と、前記入力多項式のガロア体乗累算関数を取得するため入力が前記ガロア体線形変換回路の出力に接続された最初の排他的ＯＲ論理回路とを除き、次に続く排他的ＯＲ論理回路の入力に接続された出力を有するものである。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【公表番号】特表２００６−５０３３８２（Ｐ２００６−５０３３８２Ａ）
【公表日】平成１８年１月２６日（２００６．１．２６）
【国際特許分類】
【出願番号】特願２００５−５０１１２７（Ｐ２００５−５０１１２７）
【出願日】平成１５年１０月９日（２００３．１０．９）
【国際出願番号】ＰＣＴ／ＵＳ２００３／０３１８８６
【国際公開番号】ＷＯ２００４／０３４２０７
【国際公開日】平成１６年４月２２日（２００４．４．２２）
【出願人】（５０２１１１１１２）アナログ デバイシーズ インク (31)
【Ｆターム（参考）】
【公表日】平成１８年１月２６日（２００６．１．２６）
【国際特許分類】
【出願日】平成１５年１０月９日（２００３．１０．９）
【国際出願番号】ＰＣＴ／ＵＳ２００３／０３１８８６
【国際公開番号】ＷＯ２００４／０３４２０７
【国際公開日】平成１６年４月２２日（２００４．４．２２）
【出願人】（５０２１１１１１２）アナログ デバイシーズ インク (31)
【Ｆターム（参考）】
[ Back to top ]