(57)【要約】  ガロア拡大体線形変換器（２８）は、一つ又は複数のビットストリーム内の多くの入力ビットに応答するとともにこれらビットのガロア拡大体線形変換を与える複数の出力を有するマトリックスであって、マトリックスは複数のセル（４０，４２，…７０）を含み、各セルは排他的論理和論理回路（３６）を含み、論理積論理回路（３４）は前記排他的論理和論理回路に接続された出力と前記入力ビットの一つに接続された入力とを有するマトリックスと、シングルサイクルで前記入力のマルチサイクルのガロア拡大体線形変換を得るために前記マトリックスをセットするために関連する論理積論理回路への入力を提供するプログラマぶる記憶装置（３２）と、を含む。
2005512129.tif 000002
【特許請求の範囲】
【請求項１】
一つ又は複数のビットストリーム内の多くの入力ビットに応答するとともに、これらビットのガロア拡大体線形変換を提供する複数の出力を有する、マトリックスであって、該マトリックスは複数のセルを含み、各セルは排他的論理和論理回路を含み、論理積論理回路が前記排他的論理和論理回路に接続された出力と前記入力ビットの一つに接続された入力とを有する、マトリックスと；
シングルサイクルで前記入力のマルチサイクルのガロア拡大体線形変換を得るために前記マトリックスをセットするために関連する論理積論理回路へ入力を提供するプログラマブル記憶装置と；
を備えることを特徴とするガロア拡大体線形変換器。
【請求項２】
請求項１記載のガロア拡大体線形変換器において、
各前記排他的論理和ゲートは、最後の排他的論理和論理回路を除く次の連続する排他的論理和論理回路に接続された出力を有し、前記最後の排他的論理和論理回路の出力は、前記マトリックスの出力と、入力がゼロレベルに接続された第１排他的論理和倫理回路と、に接続されていることを特徴とするガロア拡大体線形変換器。
【請求項３】
請求項１記載のガロア拡大体線形変換器において、
前記プログラマブル記憶装置は多くの記憶ユニットを含み、各記憶ユニットは異なるガロア拡大体線形変換を可能にするためにプログラムされていることを特徴とするガロア拡大体線形変換器。
【請求項４】
請求項１記載のガロア拡大体線形変換器において、
前記マトリックスに対する前記入力は、前記マトリックスのガロア拡大体線形出力の前の状態条件を表す状態入力を含むことを特徴とするガロア拡大体線形変換器。
【請求項５】
請求項４記載のガロア拡大体線形変換器において、
前記マトリックスに対する前記入力は、前記マトリックスのガロア拡大体線形出力によって表された前記前の状態条件からフィードバックされた状態入力を含むことを特徴とするガロア拡大体線形変換器。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ガロア拡大体線形変換器に関し、より詳細にはシングルサイクルでマルチサイクルの変換を達成するそのようなガロア拡大体線形変換器（Galois field linear transformer）に関する。
【背景技術】
【０００２】
誤り訂正、誤り検出、通信、符号化、復号化、及びガロア拡大体線形変換を用いる一般のビット操作、に用いられる従来の算術論理回路は、ハードウェア及びソフトウェアで実行することができる。ハードウェア手段は高価であり、かなりのチップスペース及びエネルギーを要求し、一般的にはプログラムすることができない。ソフトウェア手段はこれらの欠点のいくつかを回避するが、独自の欠点を有している。例えばソフトウェア手段は、処理のためにビットあたり多くの命令を要求する可能性がある。このようにビットあたり４つの命令（サイクル）を要求する手段では、１６ビットの入力をすると６４サイクルのマシンタイムを消費する。より現実的には、１ビットあたり４又は５つの命令（サイクル）を用いて１秒あたり６００万ビットを処理する典型的なソフトウェア手段では、２４００〜３０００万の命令すなわちサイクルが必要とされる。よくあることだが１つよりも多くの、例えば４又は５つの回路が用いられる場合、要求されるサイクルは１億２０００万から１億５０００万まで増加する。送信機及び受信機両方を用いるシステムに対しては２倍となる。これは従来のプロセッサの能力の本質的な部分である。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
したがって、この発明の目的は、多項式を用いた例えばビット操作、誤り訂正、誤り検出、通信、符号化、復号化、暗号化、暗号解読、スクランブル化、アンスクランブル化、及び周期冗長検査（cyclical redundancy checking）のための改善されたガロア拡大体線形変換器を提供することにある。
【０００４】
この発明のさらなる目的は、シングルサイクルでマルチサイクルのガロア拡大体線形変換を達成するそのような改善されたガロア拡大体線形変換器を提供することにある。
【課題を解決するための手段】
【０００５】
本発明は、シングルサイクルでマルチビット、マルチサイクルの変換を達成する速く、効果的で、経済的なガロア拡大体線形変換器が、複数のセルを含むマトリックスであって、各セルが排他的論理和ゲートを含み、論理積ゲートが排他的論理和ゲートに接続された出力を有するマトリックスと、シングルサイクルでマルチサイクルのガロア拡大体線形変換を得るためにマトリックスをセットするために関連する論理積ゲートへ入力を提供するプログラマブル記憶装置と、を用いて達成され得ることを具現化したものである。
【０００６】
この発明は、ガロア拡大体線形変換器が、一つ又は複数のビットストリーム内の多くの入力ビットに応答するとともに、これらビットのガロア拡大体線形変換を与える複数の出力を有する、マトリックスを含むことを特徴とする。マトリックスは複数のセルを含み、各セルは、排他的論理和論理回路に接続された出力と入力ビットの一つに接続された入力とを有する排他的論理和論理回路と論理積論理回路とを含み、プログラマブル記憶装置は、シングルサイクルで入力のマルチサイクルのガロア拡大体線形変換を得るためにマトリックスをセットするために関連する論理積論理回路への入力を提供する。
【０００７】
好ましい実施例では、各排他的論理和論理回路は、出力がマトリックスの出力へ接続された最後の排他的論理和論理回路と入力がゼロレベルに接続された第１排他的論理和論理回路とを除いて、次の連続する排他的論理和論理回路の入力へ接続された出力を有することができる。プログラマブル記憶装置は多くの記憶ユニットを含むことができ、各記憶ユニットは異なるガロア拡大体線形変換を可能にするためにプログラムされる。マトリックスに対する入力は、マトリックスに対するガロア拡大体線形出力の以前の状態条件を表す状態入力を含むことができ、状態入力は、マトリックスのガロア拡大体線形出力によって表された以前の状態条件からフィードバックされ得る。
【０００８】
他の目的、特徴、及び優位点は、次の好ましい実施例の記述、及び添付の図面から当業者に見出されるであろう。
【発明を実施するための最良の形態】
【０００９】
２つの記憶装置、フリップフロップ１２、フリップフロップ１４、及び２つの排他的論理和ゲート１６及び１８を含むガロア拡大体線形変換回路１０を実現するための従来のハードワイヤード回路が図１に示されている。この特定の従来技術の装置では、２つのビットストリーム、排他的論理和１６に対するｘビットストリーム入力２０と排他的論理和１８に対する入力として与えられるｙビットストリーム２２と、が提供されている。Ａで示されたフリップフロップ１２からの出力は、排他的論理和ゲート１８への一つの入力を与える。第２の入力は入力２２上のｙ入力であり、第３の入力はフリップフロップ１４の出力Ｂである。フリップフロップ１４の出力Ｂはまた、排他的論理和ゲート１６に対する第２の入力をも提供する。
【００１０】
この特定の場合において、回路１０は、３つのビットのセットがｘ及びｙ入力のそれぞれで受け取られた後、フリップフロップ１２及び１４の状態又は出力の決定を、目的として有する。このように、重要な入力は入力２０上のｘ０，ｘ１，ｘ２とｙ入力ライン２２上の入力ビットｙ０，ｙ１，及びｙ２である。図示されたフィードバックループを用いて排他的論理和ゲート１６及び１８、及びフリップフロップ１２及び１４の演算をうまく処理することによって、出力が、図２の図表に示されたようになることが理解できる。ｘ及びｙ入力の初期状態がない場合には、フリップフロップ１６及び１８の出力はＡ及びＢとして示される。これはフリップフロップの初期状態である。ゼロとするか、又はあらゆる他の値又はレベルとすることができる。
【００１１】
ｘ０及びｙ０が導入された後、入力はｘ０及びｙ０としてひとりでに示される。フリップフロップ１６の出力はｘ０＋Ｂとして示され、フリップフロップ１８の出力はｙ０＋Ａ＋Ｂとして示される。ビットｘ１及びｙ１の入力後、回路周辺での同一の論理の結果、フリップフロップ１６はｘ１＋ｙ０＋Ａ＋Ｂの出力を有し、フリップフロップ１８はｘ０＋ｙ１＋ｙ０＋Ａの出力を有する。最終的に第３のビットｘ２及びｙ２が導入された後、フリップフロップ１６の出力はｘ２＋ｘ０＋ｙ１＋ｙ０＋Ａとして示され、フリップフロップ１８の出力はｘ１＋Ｂ＋ｙ２＋ｘ０＋ｙ１として示される。
【００１２】
この点に達するために、多くのサイクルの操作とかなりの量のハードウェアとが取られた。これはまた、背景技術で説明されたようにビットのそれぞれが、４つ又はそれよりも多くの命令、すなわちサイクルの演算を要求するソフトウェアで実行されてきたこともあり、これはちょうど図１及び図２に関して図示されたような単純な場合に対するものである。例えばもしより多くのビットストリームｚ，ｔ，ｕ，ｖ．．．が用いられた場合には、目的に到達するためにビットストリームあたりより多くのビット、例えばビットストリームあたり５つのビット、又は８又は６４又は１２８が要求され、図１におけるハードウェアのサイズと従来技術によって教えられたようなソフトウェアに要求される時間とは非常に不利となったであろう。
【００１３】
この発明は、たった１サイクルで直ちに出力目標を予測するマトリックス、例えば図３に示されたマトリックスを生成することによって、ガロア拡大体線形変換を実行するためのこのマルチサイクル演算が回避され得る、ということを実現したものである。マトリックスが図３に示されたように構成されたならば、２つのビットストリーム内の３つのビットのそれぞれが処理された後のフリップフロップ１２及び１４の最終出力又は状態は、シングルサイクルで達成され得る。すなわちマトリックスは、通常多くのサイクルで生成される出力を１サイクルで予測することができる。
【００１４】
上述のことを達成するために、マトリックスは単にＡ，Ｂ，ｘ入力ｘ０〜ｘ２，及びｙ入力ｙ０〜ｙ２を含む多くの入力を有する。フリップフロップ１６に対する最終状態Ａ０を生成するためには、図２の図表に示されたような最終結果を得るために、入力Ａ，ｘ０，ｘ２，ｙ０，及びｙ１を接続する必要があるだけである。同様に図２に示されたようなフリップフロップ１８に対する最終結果Ｂ０を得るために、入力Ｂ，ｘ０，ｘ１，ｙ１，及びｙ２を接続する必要があるだけである。
【００１５】
そのようなマトリックスを作成するためには、論理積ゲート３４への一つの入力を与え、他の入力がビット入力、例えばｘ０，ｘ１，ｘ２，ｙ０，ｙ１，ｙ２，Ａ，又はＢである記憶装置３２を図４の各セル３０が含む、セルから構成されていなければならない。記憶装置３２の適切なビットレベルは、ビット入力レベルとライン７７上の書き込み信号又はクロックパルスとによって決定される。論理積ゲート３４の出力は、排他的論理和ゲート３６へ送られる。排他的論理和ゲートの出力は、ライン内で次の排他的論理和ゲートへ進み、排他的論理和ゲート３６への他の入力は、ライン内の前の排他的論理和ゲートから来る。行内の最後の排他的論理和ゲートの出力は実際にはマトリックスの出力を構成し、第１排他的論理和ゲートへの入力はゼロレベルに接続され、それよりも前には排他的論理和ゲートがない。
【００１６】
記憶装置３２は、ガロア拡大体線形変換によって要望された最後の出力に寄与することを可能にするために、論理積ゲート３４へ送られるべき一つのビットを格納する単一の記憶装置とすることができる。あるいは記憶装置３２は、３２′及び３２″で象徴的に示されるように多くの記憶ユニットを含むことができるか、又は単に演算のモードと排他的論理和ゲート３６に誘起されるべき所望の振る舞いとに依存して論理積ゲート３４へ選択的に送られ得る、内部に多くの異なるビットを有するレジスタを含むことができる。
【００１７】
複数のセル３０を用いたマトリックスの完全な装置は図５に示されている。しかしながら、図５の説明を始める前に、図３に示され図５に提供されたマトリックスは特定の構造を有するが、これは本発明に必須の制限ではないということを理解されたい。例えば、図３及び図５のマトリックスにおいて、Ａ及びＢの初期状態が入力として与えられている。しかし、これは常に必要というわけではない。例えば、Ａ及びＢの初期状態がゼロならば、入力を消費する必要はない。これらの入力は、他の目的のために用いることができる。加えて、いくつかの応用では、入力としてＡ及びＢの値を与えること、及び図３に象徴的に示されたように出力からの簡単なフィードバックによってこれらの値を与えることが望ましい。加えて、それぞれが使えるようになった３ビットからなる２つのビットストリームとする必要はない。より少ない又はより多いビットを有する一つのビットストリームがあってよく、又はそれぞれが処理すべき各セットに、より多い又はより少ないビットを有する、ｘ及びｙに加えて多くのビットストリームがあってもよい。
【００１８】
本発明に係る図３のマトリックスの装置は、図４に示されたような複数の排他的論理和セル３０を使用する図５に示されている。
【００１９】
この図５の特定の装置において、マトリックスは、８つの入力Ａ，Ｂ，ｘ０，ｘ１，ｘ２，ｙ０，ｙ１，ｙ２を処理して２つの出力Ａ０及びＢ０を与えるために１６のセルを含む。セル４０，４２，４４，４６，４８，５０，５２，及び５４からなる第１行のそれぞれは入力Ａ，Ｂ，ｘ０，ｘ１，ｘ２，ｙ０，ｙ１，ｙ２を受け取るとともに出力Ａ０を与え、他方でセル５６，５８，６０，６２，６４，６６，６８，及び７０からなる第２行は第２出力Ｂ０を与えるために同一の入力に対して応答する。
【００２０】
最初は、ライン７２上の書き込み信号又はクロックパルスは、第１行におけるセルのそれぞれにおいて、各記憶装置３２に、装置の最終的な目標を１サイクルで予測するよう排他的論理和ゲート３６をセットするために関連する論理積ゲート３４に対して、適切なビットレベル１又は０を与えることができる。同様にセル５６，５８，６０，６２，６４，６６，６８，７０からなる第２行に関して、クロック７４上の書き込み信号は、各セル内の記憶装置３２に、関連する排他的論理和ゲートに対して示されたようなビットレベルを与えることができ、１サイクルでＢ０の最終出力を直ちに予測（predict）することができる。他のクロック信号、例えば７６及び７８は、レジスタ内の付加的な記憶装置又は段階に書き込み信号を提供するのに役立つ。
【００２１】
他のモードの演算に対するマトリックスをプログラムするために、各行におけるセルのそれぞれは、出力がマトリックスの出力を構成する最後のセルと、先立つセルをもたずかつ以前に説明されたようなゼロレベルを入力として有する第１セルと、を除いて、入力として次のセルに対する出力を与える。装置の現在の状態を表す出力Ａ０及びＢ０は、Ａ及びＢとしてフィードバックされ得るか、又はシステムが適切でないモード、例えばＡ及びＢがゼロの値を有するモードで用いられる場合には、これらの入力は、無視され得るか又は他の入力例えばｘ３及びｙ４に対して利用され得る。
【００２２】
状態は繰り返されるということを理解されたい。すなわち、同一の出力が、次の３つのビットｘ３，ｘ４，ｘ５及びｙ３，ｙ４，ｙ５、次の組ｘ６，ｘ７，ｘ８及びｙ６，ｙ７，ｙ８、等に対して得られる。かくしてこの発明のマトリックスは、同一のタスクを繰り返して実行し、一つのビットストリーム、２つのビットストリーム、又は多くのビットストリームがあるか、及び処理すべきビットのセットがここで示されたようにちょうど３つ、又は４つ、又は１０つ、又は６４又は１２８又は４１７又はあらゆる他の数だけ含むか、を繰り返して実行する。
【００２３】
図４及び図５における各セルの装置はフリップフロップを有する特定の排他的論理和ゲート及び論理積ゲートを用いるが、これは本発明の制約ではない。例えば、フリップフロップは、あらゆる種類のプログラマブル記憶装置を用いて実行することができる。加えて論理積ゲートと排他的論理和ゲートとは、排他的論理和ゲート及び論理積ゲートのようなブールの意味（Boolean sense）で機能する論理回路がある限り、同じやり方で実行する必要はない。例えば図７では、記憶装置３２ｂは排他的論理和ゲート３６ｂ及び２：１のマルチプレクサ回路３４ｂと一緒に作動する。ライン１１０上の制御信号がゼロである場合には、入力１１２は先立つセル、ライン１１４から次のセル、ライン１１６へ通過し、ライン１１４上の入力は抑制される。ライン１１０上の信号が一つである場合には、ライン１１２上の信号は抑制され、ライン１１４上の信号は通過する。２つの信号のうちの一つのみがマルチプレクサ回路３４ｂによって一度に通過することができる。このようにブールの論理積の機能はなお、マルチプレクサ３４ｂによって提供される論理積論理回路によって実行される。
【００２４】
ガロア拡大体線形変換器２８は、図６のデジタル信号プロセッサ（ＤＳＰ）１００、又は集積回路として実現される汎用マイクロプロセッサのようなプログラマブル論理装置内の関数ユニットとして提供される。この関数ユニットは、バス１０２，１０３上の適切なオペランドをユニットに提供する特殊なプロセッサ命令によって作動される。ユニットへの及びユニットからのデータストリームは、オンチップデータレジスタ（on chip data register）１０４を用いて、ガロア拡大体線形変換器２８が演算装置１０６自身の一部として機能する形態で行われる。ガロア拡大体線形変換器と演算装置とのこの組み合わせは、広い範囲の異なるアルゴリズムの実行を可能にする他の従来の演算の間でガロア拡大体線形変換が実行され得る、より万能の機能を可能にする。多くの異なる種類のアーキテクチャとプログラマブル論理装置とは、この発明の使用によって利益を得ることができる。より詳細には、この発明に係るユニットは、カスタム論理回路として又はコプロセッサ又は専用のサブシステムとして選択的に実行することができる。
【００２５】
本発明の具体的な特徴はいくつかの図面に示され他には示されていないが、これは便宜上のためであり、各特長を本発明に係る他の特徴のいくつか又は全てと組み合わせることができるだけである。ここで用いられたような「含む」、「有する」、及び「備える」との語は、広範囲にかつ包括的に解釈されるべきであり、あらゆる物理的な相互接続に制限されない。その上、当出願に開示されたあらゆる実施例は単なる可能な実施例として捉えられるべきではない。
【００２６】
他の実施例は当業者に見出され、それは特許請求の範囲内にある。
【００２７】
この発明は、２００１年１１月３０日に出願された仮特許出願番号６０／３３４，６６２の優先権を主張する。
【図面の簡単な説明】
【００２８】
【図１】マルチビット、マルチサイクルの従来技術のガロア拡大体線形変換器を示す概略図である。
【図２】図１の従来技術のガロア拡大体線形変換器の信号状態を示す図である。
【図３】図１及び図２に描かれたマルチサイクル変換、シングルサイクルで実行するためのこの発明に係るマトリックスを示す概念図である。
【図４】この発明のマトリックスで利用される単一の排他的論理和セルを示す概略図である。
【図５】この発明に係るマトリックスの一手段を示す概略図である。
【図６】デジタル信号プロセッサと関連づけられたこの発明に係るガロア拡大体線形変換器を示す概略図である。
【図７】特定の論理積ゲートなしに論理積の機能を果たすこの発明のマトリックスで使用できるセルの代わりの手段を示す図である。
【符号の説明】
【００２９】
２８  ガロア拡大体線形変換器
３２  記憶装置
３６  排他的論理和ゲート
４０，４２，４４，４６，４８，５０，５２，５４  セル
５６，５８，６０，６２，６４，６６，６８，７０  セル
【図１】
2005512129.tif 000003
【図２】
2005512129.tif 000004
【図３】
2005512129.tif 000005
【図４】
2005512129.tif 000006
【図５】
2005512129.tif 000007
【図６】
2005512129.tif 000008
【図７】
2005512129.tif 000009
【国際調査報告】
2005512129.tif 000010