(57)【要約】  外部メモリ内の参照テーブルのセットの参照テーブルアドレス指定は、データワードを計算ユニットからデータアドレス生成器内の入力レジスタに転送し、データアドレス生成器内の少なくとも１つのデポジットインクリメントインデックスレジスタに、メモリ内のテーブルのセットの位置を識別するためのテーブルベースフィールドと、変位フィールドを提供し、テーブルにおける特定のエントリの位置を識別するために、データワードのセクションをインデックスレジスタの変位フィールドに配置することによって達成される。
2009514096.tif 000002
【特許請求の範囲】
【請求項１】
外部メモリ内の参照テーブルのセットを有する参照テーブルアドレス指定システムであって、
計算ユニットからデータワードを受け取るための入力レジスタ、及びメモリ内のテーブルのセットの位置を識別するためのテーブルベースと特定のテーブルにおける特定のエントリの位置を識別するための変位フィールドを含む少なくとも１つのデポジットインクリメントインデックスレジスタを有するデータアドレス生成器を備え、
前記データアドレス生成器が、特定のエントリにアクセスするために、前記データワードのセクションを前記変位フィールドに配置するように構成される
ことを特徴とする参照テーブルアドレス指定システム。
【請求項２】
前記エントリが、前記データワードの対応するセクションの部分的な結果を含む
ことを特徴とする請求項１に記載の参照テーブルアドレス指定システム。
【請求項３】
アキュムレータ、参照テーブル宛先レジスタ、及び結合回路を有する計算ユニットを更に備え、
前記計算ユニットが、最終結果を獲得するために、データワードの全セクションからの前記部分的な結果を累算するように構成される
ことを特徴とする請求項１に記載の参照テーブルアドレス指定システム。
【請求項４】
前記宛先レジスタが、計算ユニットデータレジスタファイルのあらゆる宛先レジスタであり得る
ことを特徴とする請求項３に記載の参照テーブルアドレス指定システム。
【請求項５】
前記データアドレス生成器が、複数のポインタレジスタを備え、
前記デポジットインクリメントインデックスレジスタが、前記ポインタレジスタの内の１つによって実現される
ことを特徴とする請求項１に記載の参照テーブルアドレス指定システム。
【請求項６】
前記データアドレス生成器が、複数のポインタレジスタを備え、
前記デポジットインクリメント入力レジスタが、前記ポインタレジスタの内の１つによって実現される
ことを特徴とする請求項１に記載の参照テーブルアドレス指定システム。
【請求項７】
前記データアドレス生成器が、更に、セットにおける次のテーブルを識別するために、前記デポジットインクリメントインデックスレジスタのインデックスフィールドをインクリメントするように構成される
ことを特徴とする請求項１に記載の参照テーブルアドレス指定システム。
【請求項８】
前記部分的な結果が、対応するセクションのデータビットを含むと共に、
前記データアドレス生成器が、更に、それらのビットを所定の出力ワードに割り当てるように構成される
ことを特徴とする請求項２に記載の参照テーブルアドレス指定システム。
【請求項９】
宛先ワード及びデータワードが、同一のビット数を有している
ことを特徴とする請求項１に記載の参照テーブルアドレス指定システム。
【請求項１０】
宛先ワード及びデータワードが、同一でないビット数を有している
ことを特徴とする請求項１に記載の参照テーブルアドレス指定システム。
【請求項１１】
前記結合回路が、排他的論理和回路である
ことを特徴とする請求項３に記載の参照テーブルアドレス指定システム。
【請求項１２】
前記結合回路が、加算回路である
ことを特徴とする請求項３に記載の参照テーブルアドレス指定システム。
【請求項１３】
前記データアドレス生成器が、第２のデポジットインクリメントインデックスレジスタを備え、
前記データアドレス生成器が、前記データワードの第２のセクションを第２のデポジットインクリメントインデックスレジスタの変位フィールドに配置するように構成される
ことを特徴とする請求項１に記載の参照テーブルアドレス指定システム。
【請求項１４】
前記データアドレス生成器が、前記インデックスレジスタを既知のテーブルアドレスにあらかじめ読み込むように構成される
ことを特徴とする請求項１に記載の参照テーブルアドレス指定システム。
【請求項１５】
前記既知のテーブルアドレスが、開始アドレスである
ことを特徴とする請求項１に記載の参照テーブルアドレス指定システム。
【請求項１６】
前記セクションが、ビットフィールドである
ことを特徴とする請求項１に記載の参照テーブルアドレス指定システム。
【請求項１７】
前記ビットフィールドが、１バイトである
ことを特徴とする請求項１６に記載の参照テーブルアドレス指定システム。
【請求項１８】
前記ビットフィールドが、１ニブルである
ことを特徴とする請求項１６に記載の参照テーブルアドレス指定システム。
【請求項１９】
外部メモリ内の参照テーブルのセットを使用可能にするための参照テーブルアドレス指定方法であって、
データワードを計算ユニットからデータアドレス生成器内の入力レジスタに転送する段階と、
データアドレス生成器内の少なくとも１つのインデックスレジスタに、メモリ内のテーブルのセットの位置を識別するためのテーブルベースフィールド、及び変位フィールドを提供する段階と、
テーブルにおける特定のエントリの位置を識別するために、データワードのセクションを前記インデックスレジスタ内の変位フィールドに配置する段階と
を含むことを特徴とする参照テーブルアドレス指定方法。
【請求項２０】
前記エントリが、前記データワードの対応するセクションの部分的な結果を含む
ことを特徴とする請求項１９に記載の参照テーブルアドレス指定方法。
【請求項２１】
最終結果を獲得するために、データワードの全セクションからの部分的な結果を累算する段階を更に含む
ことを特徴とする請求項１９に記載の参照テーブルアドレス指定方法。
【請求項２２】
セットにおける次のテーブルを識別するために、データアドレス生成器において、テーブルベースフィールドをインクリメントする段階を更に含む
ことを特徴とする請求項１９に記載の参照テーブルアドレス指定方法。
【請求項２３】
前記部分的な結果が、データビットを含むと共に、
前記方法が、それらのビットを所定の出力ワードに割り当てる段階を更に含む
ことを特徴とする請求項２２に記載の参照テーブルアドレス指定方法。
【請求項２４】
出力ワード及びデータワードが、同一のビット数を有している
ことを特徴とする請求項１９に記載の参照テーブルアドレス指定方法。
【請求項２５】
出力ワード及びデータワードが、同一でないビット数を有している
ことを特徴とする請求項１９に記載の参照テーブルアドレス指定方法。
【請求項２６】
累算することが、排他的論理和を計算することを含む
ことを特徴とする請求項２１に記載の参照テーブルアドレス指定方法。
【請求項２７】
累算することが、加算することを含む
ことを特徴とする請求項２１に記載の参照テーブルアドレス指定方法。
【請求項２８】
データワードのセクションを前記インデックスレジスタ内の変位フィールドに配置するのと並行して、データワードの第２のセクションを、別の特定のエントリの位置を識別するための別のインデックスレジスタの変位フィールドに配置する段階を更に含む
ことを特徴とする請求項１９に記載の参照テーブルアドレス指定方法。
【請求項２９】
インデックスレジスタを既知のテーブルアドレスにあらかじめ読み込む段階を更に含む
ことを特徴とする請求項１９に記載の参照テーブルアドレス指定方法。
【請求項３０】
前記インデックスレジスタが、開始アドレスにあらかじめ読み込まれる
ことを特徴とする請求項２９に記載の参照テーブルアドレス指定方法。
【請求項３１】
前記セクションが、ビットフィールドである
ことを特徴とする請求項２９に記載の参照テーブルアドレス指定方法。
【請求項３２】
前記ビットフィールドが、１バイトである
ことを特徴とする請求項３１に記載の参照テーブルアドレス指定方法。
【請求項３３】
前記ビットフィールドが、１ニブルである
ことを特徴とする請求項３１に記載の参照テーブルアドレス指定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、改良された参照テーブルアドレス指定システム及び方法に関係する。
【背景技術】
【０００２】
コンピュータの速度が３３［ＭＨｚ］から１．０［ＧＨｚ］に、そしてそれを超えて増加したので、コンピュータ動作は、１サイクルの間に完了されないであろう。その結果、パイプライン方式で運ぶ技術が、更に高いプロセッサ性能を最も効率的に使用して、そしてスループットを改善するために採用された。現在、パイプライン方式の深さは、少なくとも１５ステージか、それ以上を使用する。一般的に、パイプライン方式で構成された計算システムでは、同時に動作するいくつかのパラレル構成のブロックが存在し、そこでは各ブロックが全体プロセスの異なる部分を処理する。例えば、そこには、計算を実行する計算ユニット（ＣＵ）、選択されたアドレスモードに従って、データをフェッチすると共にメモリに格納するデータアドレス生成器（ＤＡＧ）を含むアドレスユニット、そして命令を解読すると共に分配するシーケンサまたは制御回路が存在する。ＤＡＧは、メモリを扱うことができる唯一の構成要素である。従って、深いパイプライン方式で構成された計算システムでは、もし命令が以前の命令の結果に依存している場合、動作を再開する前に、問題となっている命令が終了するのを待ってそのパイプラインが止まることになる、パイプラインの機能停止が起こることになる。例えば、もし計算の後でＣＵの出力が次のデータフェッチのためにＤＡＧによって必要とされる場合に、それは、データフェッチに備えて調整されるように直接ＤＡＧに届けられることができず、次のデータフェッチをするために、それがＤＡＧによって処理され得る前に、それはパイプラインを通じて伝搬されなければならない。つまりこれは、ＤＡＧのみが、メモリにアクセスすることができると共に、所望のデータの場所を示すために、計算ユニットの結果をアドレスポインタに変換することができるからである。マルチタスク汎用コンピュータにおいて、この機能停止は重要ではないかもしれないが、、例えば携帯電話、デジタルカメラにおいて使用されるような、リアルタイムコンピュータシステムでは、これらの機能停止は問題となる。“Wilson”等により２００５年１０月２６日に出願されたと共に、その全体が参照によってここに組み込まれた、“IMPROVED PIPELINE DIGITAL SIGNAL PROCESSOR”と表題をつけられた米国特許出願シリアル番号第１１／２５８，８０１号明細書を参照すること。
【０００３】
１つのアプリケーションにおいて、ビットの並べ換えが、データの暗号化を達成するために使用される。これは、ＣＵにおいて実行され得るが、しかし、ＣＵにおける演算論理回路（ＡＬＵ）は、１６、３２、または６４ビット動作のために最適化されているので、ビット単位の並べ換えは効率的ではない。例えば、もしその並べ換えがＡＬＵによって実行されるならば、各ビットは、“マスク”、“シフト”、そして“論理和（ＯＲ）”の３つの動作サイクルを必要とする。従って、１つの３２ビットワードを並べ換えることは、９６サイクルか、それ以上を必要とする。
【０００４】
並び替えをＡＬＵにおいて実行する代わりの別のアプローチにおいて、並び替えの値は、外部記憶装置に配置された参照テーブルに格納され得る。しかしながら、ここで、ＡＬＵ内のＲレジスタは、ワード、例えば３２ビットのワードを、外部記憶装置の参照テーブルを扱うことができるＤＡＧ内のポインタ（Ｐ）レジスタに、供給しなければならない。しかし、これは、莫大な参照テーブル（ＬＵＴ）、すなわち２３２ビットかそれ以上の処理で、その場合に３３．５メガバイトのメモリを必要とする。この問題を解決するために、ＡＬＵ内のＲレジスタにおける３２ビットワードは、例えば４個のバイト（８ビット）、または８個のニブル（４ビット）として処理され得る。これは、必要とされるメモリサイズを減少させ、４個のバイトでは、各々が３２ビットの２５６個のエントリの４テーブル（または、４キロバイトＬＵＴ）が必要とされると共に、８個のニブルでは、各々が３２ビットの１６個のエントリの８テーブル（または、５１２バイトＬＵＴ）が必要とされる。しかし、これは、ここでＡＬＵが、１つの３２ビットワードに対して、４個の（バイト）または８個の（ニブル）がＤＡＧのＰレジスタへ転送されることを必要とする、という更なる問題を生成する。上に論じられたように、同様に、各転送は多くのパイプラインの機能停止を引き起こす。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
個々の、しかし関連する問題において、リニアフィードバックシフトレジスタ（linear feedback shift register：ＬＦＳＲ）、例えばＣＲＣ、スクランブラ、デスクランブラ、トレリス符号化が、広く通信システムにおいて使用される。同じ問題によって上で説明されたように、ＬＦＳＲの動作は、ＣＵによって、マスク／シフト／論理和のサイクルを使用して、１回に１ビットに縮小される。または、１サイクル当たり４、８、または１６ビットを使用してＬＦＳＲ問題を解決する特定のハードウェアブロック、例えばＡＳＩＣ、ＦＰＧＡが使用され得る。ＣＵにおけるマスク／シフト／論理和のアプローチ、そしてＡＳＩＣのアプローチの両方は、外部記憶装置の参照テーブルまたは複数の参照テーブルを使用することによって解決され得るが、しかし前述の欠点の全てを有している。
【０００６】
改良された参照テーブルアドレス指定システム及び方法を提供することが、従って本発明の目的である。
【０００７】
計算ユニットとデータアドレス生成器との間のパイプラインの機能停止を最小限にする、そのような改良された参照テーブルアドレス指定システム及び方法を提供することが、本発明の更なる目的である。
【０００８】
参照テーブルの大きさを最適化する、そのような改良された参照テーブルアドレス指定システム及び方法を提供することが、本発明の更なる目的である。
【０００９】
追加の専用のハードウェア、例えばＡＳＩＣまたはＦＰＧＡなしで、リニアフィードバックシフトレジスタの動作を加速する、そのような改良された参照テーブルアドレス指定システム及び方法を提供することが、本発明の更なる目的である。
【００１０】
更に高速で、そして比較的少ない電力を必要とする、そのような改良された参照テーブルアドレス指定システム及び方法を提供することが、本発明の更なる目的である。
【００１１】
現存するプロセッサコンポーネントを再使用し得る、そのような改良された参照テーブルアドレス指定システム及び方法を提供することが、本発明の更なる目的である。
【００１２】
追加のハードウェア、例えばＡＳＩＣまたはＦＰＧＡなしで、並べ換え動作を加速する、そのような改良された参照テーブルアドレス指定システム及び方法を提供することが、本発明の更なる目的である。
【００１３】
更に大きなメモリの要求を受け入れるのに十分に拡大縮小可能（scalable）である、そのような改良された参照テーブルアドレス指定システム及び方法を提供することが、本発明の更なる目的である。
【００１４】
様々な異なるアプリケーション、例えば、暗号化、並べ換え、そしてＣＲＣ、スクランブリング、デスクランブリング、及びトレリスを含むリニアフィードバックシフトレジスタの実装に適用可能である、そのような改良された参照テーブルアドレス指定システム及び方法を提供することが、本発明の更なる目的である。
【課題を解決するための手段】
【００１５】
本発明は、パイプラインの機能停止を最小限にし、参照テーブルの大きさを最適化し、より高速であり、少ない電力を使用し、現存するプロセッサコンポーネントを再使用し、拡大縮小可能であり、様々な異なるアプリケーションに適用可能である改良された参照テーブルアドレス指定システム及び方法が、データワードを計算ユニットからデータアドレス生成器内の入力レジスタに転送し、メモリ内のテーブルのセットの位置を識別するためのテーブルベースフィールドを有するデータアドレス生成器内の少なくとも１つのデポジットインクリメントインデックスレジスタに、テーブルの特定のセットの位置を識別するためのテーブルインデックスフィールドと、変位フィールドを提供し、テーブルにおける特定のエントリの位置を識別するために、データワードのセクションをデポジットインクリメントインデックスレジスタの変位フィールドに配置することによって達成され得る、という認識に起因する。
【００１６】
しかしながら、従属する発明は、他の実施例において、全てのこれらの目的を達成する必要があるとは限らず、そしてこれに関する請求項は、これらの目的を達成することが可能である構造及び方法に制限されるべきでない。
【００１７】
この発明は、計算ユニットからデータワードを受け取るための入力レジスタを有するデータアドレス生成器と、メモリ内のテーブルのセットの位置を識別するためのテーブルベースを有するデポジットインクリメントインデックスレジスタとを備える、外部メモリ内の参照テーブルのセットを有する参照テーブルアドレス指定システムを特徴として有している。変位フィールドは、その特定のテーブルにおける特定のエントリの位置を識別すると共に、データアドレス生成器は、特定のエントリにアクセスするために、データワードのセクションを変位フィールドに配置するように構成される。
【００１８】
好ましい実施例において、それらのエントリは、データワードの対応するセクションの部分的な結果を含む。計算ユニットは、アキュムレータレジスタ、参照テーブル宛先レジスタ、及び結合回路を備え得ると共に、計算ユニットは、最終結果を獲得するために、データワードの全セクションからの部分的な結果を累算するように構成され得る。宛先レジスタは、計算ユニットデータレジスタファイルのあらゆる宛先レジスタであり得る。データアドレス生成器は、複数のポインタレジスタを備え得ると共に、デポジットインクリメントインデックスレジスタは、ポインタレジスタの内の１つによって実現され得る。データアドレス生成器は、同様に、複数のポインタレジスタを備え得ると共に、デポジットインクリメント入力レジスタは、ポインタレジスタの内の１つによって実現され得る。デポジットインクリメントインデックスレジスタのインデックスフィールドは、セットにおける次のテーブルを識別するためにインクリメントするように構成され得る。部分的な結果が、対応するセクションのデータビットを含み得ると共に、データアドレス生成器が、更に、それらのビットを所定の出力ワードに割り当てるように構成され得る。宛先ワード及びデータワードは、同一のビット数を有し得る。宛先ワード及びデータワードは、同一でないビット数を有し得る。結合回路は、排他的論理和回路であり得る。結合回路は、加算回路であり得る。データアドレス生成器は、第２のデポジットインクリメントインデックスレジスタを備え得ると共に、データアドレス生成器は、データワードの第２のセクションを第２のデポジットインクリメントインデックスレジスタの変位フィールドに配置するように構成され得る。データアドレス生成器は、インデックスレジスタを既知のテーブルアドレスにあらかじめ読み込むように構成され得る。既知のテーブルアドレスは、開始アドレスであり得る。ビットフィールドは、１バイトであり得る。ビットフィールドは、１ニブルであり得る。
【００１９】
本発明は、同様に、データワードを計算ユニットからデータアドレス生成器内の入力レジスタに転送する段階を含む外部メモリ内の参照テーブルのセットを使用可能にするための参照テーブルアドレス指定方法を特徴として有している。データアドレス生成器内の少なくとも１つのインデックスレジスタに、メモリ内のテーブルのセットの位置を識別するためのテーブルベースフィールド、及びテーブルにおける特定のエントリの位置を識別するための変位フィールドを含む段階が提供される。
【００２０】
好ましい実施例において、エントリは、データワードの対応するセクションの部分的な結果を含み得る。最終結果を獲得するために、データワードの全セクションからの部分的な結果が累算され得る。セットにおける次のテーブルを識別するために、データアドレス生成器において、テーブルベースフィールドがインクリメントされ得る。部分的な結果は、データビットを含み得ると共に、方法は、それらのビットを所定の出力ワードに割り当てる段階を更に含み得る。出力ワード及びデータワードは、同一のビット数を有し得る。出力ワード及びデータワードは、同一でないビット数を有し得る。累算することは、排他的論理和を計算することを含み得る。累算することは、加算することを含み得る。方法は、データワードのセクションをインデックスレジスタ内の変位フィールドに配置するのと並行して、データワードの第２のセクションを、別の特定のエントリの位置を識別するための別のインデックスレジスタの変位フィールドに配置する段階を含み得る。方法は、インデックスレジスタを既知のテーブルアドレスにあらかじめ読み込む段階を含み得る。インデックスレジスタは、開始アドレスにあらかじめ読み込まれ得る。セクションは、ビットフィールドであり得る。ビットフィールドは、１バイトか、または１ニブルであり得る。
【発明を実施するための最良の形態】
【００２１】
他の目的、特徴、及び利点が好ましい実施例、及び添付された図面の以下の説明から当業者の心に浮かぶであろう。
【００２２】
以下で開示された好ましい実施例または複数の実施例以外に、本発明は、他の実施例が可能であると共に、様々な方法で実施するか、または実行されることが可能である。従って、本発明は、その適用において、以下の説明で述べられるか、または図面の中で例示される、構成及び部品の配置の詳細に制限されない、ということが理解されるべきである。もし一実施例だけがここで説明される場合、ここでの請求項は、その実施例に制限されるべきではない。更に、ここでの請求項は、特定の除外、制限、または注意書きを明らかにする、明瞭で説得力のある証拠がない限り、制限的に読まれるべきではない。
【００２３】
図１において示されるように、外部メモリ１６内の参照テーブルのセットを使用可能にするための、既存のデータアドレス生成器（ＤＡＧ）１２及び計算ユニット（ＣＵ）１４によって実行された本発明による参照テーブルアドレス指定システム１０が存在する。ＤＡＧ１２、及びＣＵ１４は、ディジタルシグナルプロセッサ（ＤＳＰ）のような従来のプロセッサの一部分であり得る。ＤＡＧには、１つ目はデータワード入力レジスタ１８としてのレジスタであり、２つ目はデポジットインクリメントインデックスレジスタ２０としてのレジスタである２つのポインタ（Ｐ）レジスタと、インクリメント回路（incrementing circuit）２２と、プリロード回路（preload circuit）２４とが存在する。ＣＵ１４には、参照テーブル（ＬＵＴ）宛先レジスタ２６と、アキュムレータ２８と、ここではＧＦ−２加算器（排他的論理和回路：ＸＯＲ）または加算回路として簡単に示される結合回路３０とが存在する。ＣＵ１４において、そのレジスタファイルのうちのどれでもが、ＬＵＴ宛先レジスタ２６として使用され得る。外部メモリ１６は、そこに格納されるデータの残りの中に、多くの個々のテーブルを含む参照テーブル３２のセットを備える。例えば、もし参照テーブルアドレス指定システム１０が、ニブル、すなわち４ビットのグループによって、３２ビットデータワードに作用することであるならば、その場合に、それぞれ１６個のエントリを有する８つのテーブルか、または、もしバイトによって３２ビットデータワードに作用することであるならば、それぞれ２５６個のエントリを有する４つのテーブルが存在するであろう。
【００２４】
ＬＵＴデポジットインクリメントインデックスレジスタ２０は、テーブルベースビットフィールド３８、テーブルインデックスビットフィールド４０、デポジットビットフィールド３６、及びゼロビットフィールド４１の関数として、効果的なメモリアドレスを生成する。動作中、ＣＵ１４が提供するデータワードは、ＤＡＧデータ入力ワードレジスタ１８に供給される。例えば、それの１つのセクションである第１のニブル３４は、直接変位ビットフィールド３６に配置される。テーブルベースビットフィールド３８は、外部メモリ１６内のテーブル３２のセットの開始位置を識別する。インデックスフィールド４０は、テーブルセット３２における特定のテーブル３２−１からテーブル３２−８までの位置を識別すると共に、ゼロフィールド４１は、ＬＵＴのエントリの幅に対応する。もし３２ビットＬＵＴアクセスが使用されるならば、ゼロフィールドは２つのゼロを含み、もし１６ビットＬＵＴアクセスが使用されるならば、ゼロフィールドは１つのゼロを含むであろう。変位フィールド３６に配置されたセクションまたはニブル３４は、特定のテーブルにおける特定のエントリ、例えばエントリ４２のアドレスの変位である。システムがＤＡＧの入力レジスタ１８に転送された３２ビットワードを１度に１ニブル並び換えるために使用されていると仮定すると、その場合に、エントリ４２は、更に３２ビットワードに４ビットのマッピングロケーションを含むことになる。４ビットは、変位フィールド３６に配置されるニブル３４におけるビットの並び換えである。これらの４ビット及び３２ビットワードにおいてそれらの位置を割り当てる情報は、ＣＵ１４内の３２ビットＬＵＴ宛先レジスタ２６に供給される。特定のエントリ４２が提供する４ビットは、エントリ４２におけるマッピング情報に従って、それらの３２個の位置の内の４つに読み込まれることになる。この部分的な結果は、結合回路またはＧＦ−２加算器３０（排他的論理和回路：ＸＯＲ）によって、アキュムレータレジスタ２８の内容と結合される。これが動作の最初のサイクルであるので、レジスタ２８はゼロを含む。従って、加算器３０において２つのレジスタの出力を結合した後で、レジスタ２８における累算された結果は、ＬＵＴ宛先レジスタ２６の内容でしかない。次に、インクリメント回路２２は、システムがテーブル２（符号３２−２）に移動するように、テーブルインデックス４０の値を１つだけインクリメントすると共に、それを新しいテーブルインデックスとしてフィードバックする。同時に、データワード入力レジスタ１８におけるデータワードの次のセクション、すなわちデータワード入力レジスタ１８の次のセクション４４におけるニブルは、変位フィールド３６に供給される。これは、直ちに、ＬＵＴ宛先レジスタ２６に割り当てられる、テーブル２における別の特定のエントリ４６を識別する。レジスタ２６が提供する出力は、再度ＧＦ−２加算器３０（排他的論理和回路：ＸＯＲ）によって、レジスタ２８の内容と結合されると共に、結合結果は、レジスタ２８に累算されて、格納される。ここで、レジスタ２８は、その４ビットが３２ビットワードフォーマットの中の４つの他の位置に割り当てられる特定のエントリ４６と結合された、３２ビットワードフォーマットに割り当てられた特定のエントリ４２が提供するデータの組み合わせを含む。これが、レジスタ１８に存在する３２ビットワードの全ての８個のニブルが完了されるまで続く。インクリメント回路が“８”に到達した時点で、プリロード回路２４は、テーブルベースをテーブルのセットの最初に戻すようにあらかじめ読み込む（プリロードする）ことになる。プリロード回路２４は、実際には、テーブルベースフィールド３８をあらゆる特定の場所にあらかじめ読み込む（プリロードする）であろう。
【００２５】
本発明の利点は、それを従来の動作と比較することによって発見され得る。従来の動作において、データワードは、ＣＵ内のＲレジスタからＤＡＧ内のインプットＰ入力レジスタに対して、一度に１ニブルか、または１バイト移動される。深いパイプライン動作において、これは、そのように転送される各ニブルまたはバイトに対していくつかの機能停止があることを意味する。更に、ニブルまたはバイトデータを変位フィールドに配置すると共に、次のテーブルにインクリメントする動作は、ＤＡＧによってマニュアルで実行されなければならない。一方、この発明に関して、全体のデータワードは、ＣＵにおけるＲレジスタからＤＡＧにおけるＰ入力レジスタに対して、一度に転送され、従って、許容されなければならないいくつかの機能停止は、各８ニブルまたは各４バイトに対して１度よりむしろ、全体のデータワードに対して１度だけ許容される。更に、ニブルまたはバイトデータを変位フィールドに配置すると共に、次のテーブルにインクリメントする動作は、ＤＡＧ自身の回路によって、ここでは毎回自動的に実行されることができる。
【００２６】
ＤＡＧには、１を超える利用可能な入力レジスタ１８ａ及びデポジットインクリメントインデックスレジスタ２０ａがあり得る。入力レジスタ１８及び１８ａは、実際には、デポジットインクリメントインデックスレジスタ２０とデポジットインクリメントインデックスレジスタ２０ａとを使用可能にする単一のレジスタであり得る。同様に、追加のインクリメント回路２２ａ、及びプリロード回路２４ａが存在し得る。
【００２７】
そのような場合に、ＣＵ１４内の第２のＬＵＴ宛先レジスタ２６ａを用いて、その動作は２倍速く実行され得る。入力レジスタ１８及び入力レジスタ１８ａに設定された同じデータワードに関して、システムは、レジスタ１８内のニブル３４を検査すると共に、それをレジスタ２０内の変位フィールド３６に供給することができ、一方レジスタ１８ａ内のニブル４４ａは、変位フィールド３６ａに供給されることができる。従って、レジスタ２６に割り当てられたニブルとレジスタ２６ａに割り当てられたニブルが一緒にアキュムレータレジスタ２８の内容と結合されるように、そしてシステムが２倍速く動くことができるように、図１におけるＤＡＧ１２がテーブル１内の特定のエントリ４２を取り出す一方、ＤＡＧ１２ａは、テーブル２内の特定のエントリ４６を取り出すと共に、それをＬＵＴ宛先レジスタ２６ａに供給することができる。次のサイクルにおいて、システムは、テーブル３及びテーブル４に移動し、次にテーブル５及びテーブル６に移動し、最終的にテーブル７及びテーブル８に移動することになる。
【００２８】
符号１８のような３２ビット入力レジスタの並べ換えは、例えば、入力レジスタを８つのニブル、すなわち８つの４ビットのグループに分割すると共に、全ての並べ替えられたニブルの部分的な結果を結合することによって実行される。図１のレジスタ１８におけるニブル３４のような第１のニブルは、図２に示されるように、図１のアキュムレータレジスタ２８における３２ビットワードフォーマット５０に割り当てられて示される。この第１の動作の４つの割り当てられたビットは、“１”の表示を有する“Ｘ”の印で示される。次のニブル４４に関して、図２の符号５２で示されるように、“２”の表示が添付してある“Ｘ”の印で示されるビットは、ＬＵＴ宛先レジスタ２６に割り当てられると共に、図２の３２ビットフォーマット５２に、結合結果が示される。第３のニブルの後で、アキュムレータレジスタ２８におけるワードフォーマットは、図２の符号５４で示される。全ての８つの動作サイクルの後で、図１のレジスタ２８の内容は、４ビットの８つのグループまたはニブル内の全ての３２ビットが、符号５０、符号５２、符号５４で示されるそれぞれの部分的な結果を結合することによって、それぞれ符号５６で示される最終結果に割り当てられた、図２のワードフォーマット５６で示されたように現れると共に、ここでは中間の状態は単純化のために示されなかった。
【００２９】
代替の構成では、図３の２つのＰインデックスレジスタ２０ｂ、２０ｂｂが存在し得ると共に、それは、参照テーブルセット３２ｂからエントリを取り出すために、インタリーブされた方式で動作する。例えば、示されるように、３２ビットデータワードの並べ換えの場合において、インデックスレジスタ２０ｂ内のゼロフィールド４１ｂは、３２ビットデータワードの全ての偶数ビットをフェッチするために、全て“０”を含み得ると共に、一方インデックスレジスタ２０ｂｂ内のゼロフィールド４１ｂｂは、３２ビットデータワードの全ての奇数ビットをフェッチするために、後ろに２つの“０”が続く“１”を含み得る。そして、インデックスレジスタ２０ｂｂがその変位フィールド３６ｂｂ内のニブル３４を処理すると共に、テーブル２から特定のエントリ４２ｂを取り出す一方、その変位フィールド３６ｂにニブル４４を受け取ったインデックスレジスタ２０ｂは、テーブル１から特定のエントリ４６ｂを探すことになる。テーブル３とテーブル４、テーブル５とテーブル６、テーブル７とテーブル８のアドレス指定可能なデータ入力がインタリーブされたのと同様に、テーブル１とテーブル２のアドレス指定可能なデータ入力がインタリーブされたことに注意が必要である。テーブルインデックスをインクリメントした後で、インデックスレジスタ２０は、今度はインデックスレジスタ２０’として現れる。この場合、第２のＰインデックスレジスタ２０ｂｂを使用することによって、３２ビット入力レジスタは、２倍速く並べ換えられ得る。これまでのところ本発明は並べ換え動作に関してのみ説明されたが、それは、大きい利点に対する多くの他の応用において使用され得る。例えば、図４において、本発明の参照テーブルアドレス指定システム１０ａは、参照テーブルアドレス指定システムを２回使用することによって、ＤＥＳ暗号化システム６０を実現するために使用される。第１の参照テーブルセットは、３２ビット入力レジスタ１８を４８ビット表示に並べ換えて拡張すると共に、ＤＥＳシステム６０のレジスタ７０に配置される。それは、その場合に、加算回路７４を用いて、レジスタ７２に格納される４８ビット巡回鍵（round key）と結合される。本発明によるＰの並べ換えを従えているＳ−Ｂｏｘを実装する第２の参照テーブルセット１０ｂは、ＤＥＳシステム６０のレジスタ７０から６個のビットグループを取得すると共に、特定のＤＥＳ規則に従って、それらを３２ビットに戻るように変換し、アキュムレータレジスタ２８ｂに最終結果を配置するために使用され得る。図４のＤＥＳアプリケーションにおいて、結合回路は排他的論理和ゲート３０ａとして実装されることに注意が必要である。
【００３０】
本発明は、一般的に、そこからシステムが出力１１２及び“Ｓｎ＋１”として指定される新しいトレリス状態出力１１４を生成する、“ｕ３”、“ｕ２”、及び“ｕ１”として指定された１つ以上のトレリスビットストリーム内の多数の入力ビット、及び“Ｓｎ”として指定されたマトリクスのトレリス状態出力を受信するトレリスシステムである、図５におけるガロアフィールド線形変換（Galois Field Linear Transformer：ＧＦＬＴ）ＬＦＳＲ１１０のような、線形フィードバックシフトレジスタ（ＬＦＳＲ）に関連する大きい利点に同じく使用され得る。図６のＣＲＣ、図７のスクランブラ、図８のデスクランブラ、図９のトレリスを含む多くの異なる種類の線形フィードバックシフトレジスタが存在する。本発明のそのようなシステムへの応用は、ここで図９から図１３を参照して説明されることになる。
【００３１】
図９において示されるように、ＡＤＳＬモデムトレリス１２０のような一般的なトレリスシステムは、線形フィードバックシフトレジスタ（ＬＦＳＲ）１２２としてハードウェアで実現される。線形フィードバックシフトレジスタ１２２は、線形フィードバックシフトレジスタの状態“ｓ０”、状態“ｓ１”、状態“ｓ２”、及び状態“ｓ３”を表す４つの記憶装置、フリップフロップ１２４、フリップフロップ１２６、フリップフロップ１２８、及びフリップフロップ１３０を備える。トレリスビットストリーム“ｕ３”、トレリスビットストリーム“ｕ２”、及びトレリスビットストリーム“ｕ１”は、それぞれビット“ｕ３０、ｕ３１、ｕ３２、ｕ３３．．．ｕ３７．．．”、ビット“ｕ２０、ｕ２１、ｕ２２、ｕ２３．．．ｕ２７．．．”、ビット“ｕ１０、ｕ１１、ｕ１２、ｕ１３．．．ｕ１７．．．”のストリームとして入力１３２に現れる。ビットストリーム“ｕ３”は、直接入力１３２で出力“ｖ０”を供給する。出力“ｖ１”は、“ｕ３”入力と“ｕ１”入力に応答する排他的論理和ゲート１３４によって生成される。出力“ｗ０”は、“ｕ３”入力と“ｕ２”入力に応答する排他的論理和ゲート１３６によって生成される。出力“ｗ１”は、入力“ｕ３”、“ｕ２”、“ｕ１”にライン１４０上の線形フィードバックシフトレジスタ１２２の出力状態“ｓ３”を加えた全てに応答する排他的論理和ゲート１３８によって供給される。
【００３２】
クロックの各サイクルの動作において、図１０の列１５０のように、“ｕ１〜ｕ３”入力の関数としての状態“ｓ０”、状態“ｓ１”、状態“ｓ２”、及び状態“ｓ３”と、以前の“Ｓ１〜Ｓ３”状態が図表Ｉに示されることになる。
【００３３】
図１１のガロアフィールド線形変換器トレリスシステム１１０ａは、特定のアプリケーションに受け入れ可能なガロアフィールド線形変換器のマトリクスのサイズに応じて、同時に４、８、１２、１６、またはあらゆるビット数を処理し得る。これは図１１において示されると共に、ここでは、一般化されたトレリスビットストリーム入力“ｕ１０〜ｕ１３”、“ｕ２０〜ｕ２３”、“ｕ３０〜ｕ３３”が全て同時に受け入れられたことが示される。特定のビットは、第１の目盛り（tick）またはクロックサイクルに関して、“ｚ１０”から“ｚ１３”、そして“ｙ２０”から“ｙ２３”、及び“ｘ３０”から“ｘ３３”として示される。この特別な例において、ＧＦＬＴトレリスシステム１０が一度に４ビットを受け入れているので、真のガロアフィールド変換器形式におけるその出力は、図１０の図表Ｉにおける四角で囲まれたエリア１５２において、第４のクロックサイクルまたはクロックサイクル番号“３”に対応する出力を提示することになる。符号１５４、符号１５６、符号１５８、及び符号１６０で示された、状態“ｓ０”、状態“ｓ１”、状態“ｓ２”、及び状態“ｓ３”に関するこれらの値は、従って、図１１の新しいトレリス状態１５４ａ、新しいトレリス状態１５６ａ、新しいトレリス状態１５８ａ、及び新しいトレリス状態１６０ａである。それらは、新しいトレリス状態“ｓ０ｎ＋１”、新しいトレリス状態“ｓ１ｎ＋１”、新しいトレリス状態“ｓ２ｎ＋１”、新しいトレリス状態“ｓ３ｎ＋１”であると共に、トレリス入力“ｓ３ｎ、ｓ２ｎ、ｓ１ｎ、ｓ０ｎ”にフィードバックされる。
【００３４】
図１２の図表ＩＩのクロックサイクル“１”で示される次のクロックサイクルまたは第２のクロックサイクルにおいて、ｓ３、ｙ２１（ｙ２１はｕ２１の現在の値である）、ｓ０、ｙ２０（ｙ２０はｕ２０の現在の値である）、及びｚ１２（ｚ１２はｕ１２の現在の値である）の排他的論理和結合として、状態“ｓ０ｎ＋１”が列１５１に示される。これは、次のトレリス状態を提供するために、第２の列１５３において示されたように拡張され、その後第３の列１５５において示されたように消去された冗長性（２つの加算のモジュロ演算）を有すると共に、“ｓ１ｎ＋１”、“ｓ２ｎ＋１”、及び“ｓ３ｎ＋１”に関して同じ事が実行され得る。例えば図１３のガロアフィールド線形変換トレリスシステムマトリクス１６０に示されたように、出力ｖ０、出力ｖ１、出力ｗ０、及び出力ｗ１は、それらが信号の簡単な排他的論理和結合であるので、図表形式において一覧にされない。ここで、マトリクス１６０の行と列の選択された接合点において排他的論理和ゲートセル１６２を有効にすることによって、図表Ｉ及び図表ＩＩにおいて要求された出力が獲得されるということがわかる。例えば、図１２の図表ＩＩを参照すると、ｓ０３の値は、ｓ１、ｓ２、ｓ３、ｕ２１、ｕ２２、ｕ１３の排他的論理和結合と見なされ得ると共に、ｗ０３に関して、例えばその表現は、単にｕ３３とｕ２３とが排他的に論理和結合され、ｖ１２に関して、例えばその表現は、単にｕ３２とｕ１２とが排他的に論理和結合される等と見なされ得る。
【００３５】
更なる説明のためには、“Stein”等によって２００４年１月７日に出願されたと共に、参照によってその全体がここに組み込まれた、“GALOIS FIELD LINEAR TRANSFORMER TRELLIS SYSTEM”と表題をつけられた米国特許出願番号第１０／７５３，３０１号明細書を参照すること。
【００３６】
この環境における本発明の使用の１つの利点は、排他的論理和ゲートの３２×３２のマトリクス、または２３２の容量を有する参照テーブルの必要性が回避され得るということである。これは、図１４において教えられ、ここで、その１つがｕ１として表現された、図１３が提供する１ニブルは、その４つの列の３２行を必要とする全ての排他的論理和ゲート１６２を繰り返して再度示している。この発明に従って、４ビットのニブルにおいて発生し得る“１”と“０”との１６個の異なる可能な組み合わせが、列１８２の１６個の行１８０で示される。ＬＵＴ出力１８４は、列１８６の対応する行１８０において示される。例えば、符号１８０ａで示されるように、“ｕ１”に関してビット“００１１”の組み合わせを選択すると、１つが“０”ポジションに、もう一つが“３”ポジションに配置された２つの排他的論理和ゲートを含む１２番目の行１８８に対するＬＵＴ出力は、“１”である。同じビットの組み合わせ“００１１”を有する、１つの排他的論理和ゲートを含む１９番目の行１９０に関して、ＬＵＴの出力は“１”である。従って、排他的論理和ゲートの全体のマトリクスは、参照テーブルと交換され得ると共に、この発明に従って、その参照テーブルは、各々が３２ビットである２３２のエントリを必要としないが、各々が３２ビットである１６個エントリを有する８つのテーブル（または、５１２バイトＬＵＴ）を含むテーブルのセットのグループであり得る。
【００３７】
本発明は、ＤＡＧ１２、ＣＵ１４、及びメモリ１６が、相互に、そしてシーケンサ２０２と、様々なバス２０４を用いて通信する図１５のデジタルシグナルプロセッサＤＳＰ２００のようなプロセッサにおいて都合よく実行され得る。ＤＡＧ１２は、入力レジスタ１８とデポジットインクリメントインデックスレジスタ２０とを含むポインタレジスタファイル２０６と、従来のＩレジスタ、Ｌレジスタ、そしてＭレジスタのような他のレジスタ２０８を備える。ＣＵ１４は、乗算及び累算ユニット２１０、演算論理回路２１２、及びシフタ２１４と一緒に、ＬＵＴ宛先レジスタ２６及びアキュムレータレジスタ２８のようなデータレジスタファイル２０９を備え得る。
【００３８】
本発明による、図１６の参照テーブルアドレス指定方法３００の１つの実施例は、データワードを計算ユニットからデータアドレス生成器内の入力レジスタに転送する転送段階３０２を含む。段階３０４において、ＤＡＧ内の各インデックスレジスタに、テーブルベースフィールド、テーブルインデックスフィールド、及び変位フィールドが提供される。段階３０６において、外部メモリ内の参照テーブルにおける特定のエントリの場所を示すために、データワードの１バイトまたは１ニブルのようなセクションが、変位フィールドに配置される。段階３０８において、各セクションから出力ワードに特定のエントリが割り当てられる。段階３１０において、テーブルインデックスフィールドが次のテーブルへインクリメントされる。この後、完了するべき残されたセクションが存在する限り、システムは段階３０６に戻る。その後で、段階３１２において、出力ワードを完成するために、全てのセクションから、特定のエントリが、例えば合計演算、加算、排他的論理和演算によって累算される。最終的に、段階３１４において、インデックスレジスタは、既知のアドレス、例えばスタートアドレスにあらかじめ読み込まれる（プリロードされる）と共に、システムは、データワードを取得して転送する段階３０２に、再度戻る。
【００３９】
本発明の特定の特徴が他のものではなく、いくつかの図面において表されるが、各特徴が本発明による他の特徴の一部もしくは全部と結合され得るように、これは利便性のためだけのものである。ここで使用されるように、用語“含む”、“備える”、“持つ”、及び“有する”は、広く、そして分かりやすく解釈されるべきであると共に、物理的な相互接続に全く制限されない。更に、対象の特許出願において開示された実施例は、唯一の可能な実施例と考えられるべきではない。
【００４０】
更に、この特許のための特許出願の審査手続の間に提示されたあらゆる補正は、出願された特許出願において提示されたあらゆる請求項要素の否定ではなく、当業者は、文字通りに全ての可能な等価物を包囲するであろう請求項を起草すると合理的に予測できず、（どちらかといえば）多くの等価物は、補正の時に予測不可能であり、何が諦められるべきであるかの公正な解釈を越えており、補正の基礎となる論理的根拠は多くの等価物とわずかな接線の関係しか持たないか、及び／または、そこには出願人が補正されたあらゆる請求項要素に対する特定の実体のない代わりの物を説明すると期待されることができない多くの他の理由がある。
【００４１】
他の実施例が当業者の心に浮かぶと共に、それらは添付の特許請求の範囲の中にある。
【図面の簡単な説明】
【００４２】
【図１】ＤＳＰのＤＡＧ及びＣＵに実装された本発明による参照テーブルアドレス指定システムの構成図である。
【図２】３２ビットワードフォーマットにおける最終結果に対する多くの部分的な結果の累積的なマッピングの表現を示す図である。
【図３】図１のシステムのＤＡＧ部分の代替実施例の概要の構成図である。
【図４】図３の実施例によって修正された、図１の参照テーブルアドレス指定システムを２つ用いて実施されるＤＥＳ暗号化システムの概要の構成図である。
【図５】本発明によって実現可能な線形フィードバックシフトレジスタトレリスシステムのガロアフィールド線形変換器の実施の概要の構成図である。
【図６】ＬＦＳＲによるＣＲＣの概要の構成図である。
【図７】ＬＦＳＲによるスクランブラの概要の構成図である。
【図８】ＬＦＳＲによるデスクランブラの概要の構成図である。
【図９】ＬＦＳＲによるトレリスの概要の構成図である。
【図１０】８つのクロックサイクルに関する図９のＡＤＳＬモデムトレリスの４つの階層の状態を例証する図表Ｉである。
【図１１】図５の再構成可能なガロアフィールド線形変換器トレリスシステムの更に詳細な概要の構成図である。
【図１２】図１１のガロアフィールド線形変換器システムにおいて発生する状態を例証する図表ＩＩである。
【図１３】１つのサイクルにおける入力ビットからトレリス出力チャネル記号を生成するように構成されたガロアフィールド線形変換器マトリクスの更に詳細な構成図である。
【図１４】図１３のマトリクスの１ニブルから本発明による参照テーブルアドレス指定システムへの変換を描写する図である。
【図１５】本発明を実施するために使用されるデジタルシグナルプロセッサの概要の構成図である。
【図１６】本発明による参照テーブルアドレス指定方法の構成図である。
【符号の説明】
【００４３】
１０    参照テーブルアドレス指定システム
１０ａ    参照テーブルアドレス指定システム
１２    データアドレス生成器（ＤＡＧ）
１２ａ    ＤＡＧ
１４    計算ユニット（ＣＵ）
１６    外部メモリ
１８    データワード入力レジスタ
１８ａ    入力レジスタ
２０    デポジットインクリメントインデックスレジスタ
２０ａ    デポジットインクリメントインデックスレジスタ
２０ｂ、２０ｂｂ    Ｐインデックスレジスタ
２０、２０’    インデックスレジスタ
２２    インクリメント回路
２２ａ    インクリメント回路
２４    プリロード回路
２４ａ    プリロード回路
２６    参照テーブル（ＬＵＴ）宛先レジスタ
２６ａ    第２のＬＵＴ宛先レジスタ
２８    アキュムレータレジスタ
２８ｂ    アキュムレータレジスタ
３０    結合回路（排他的論理和ゲート）
３０ａ    排他的論理和ゲート
３２    参照テーブル
３２−１    テーブル１
３２−２    テーブル２
３２−３    テーブル３
３２−８    テーブル８
３４    ニブル
３６    変位ビットフィールド
３６ａ    変位フィールド
３６ｂ、３６ｂｂ    変位フィールド
３８    テーブルベースビットフィールド
４０    テーブルインデックスビットフィールド
４１    ゼロビットフィールド
４１ｂ、４１ｂｂ    ゼロフィールド
４２    特定のエントリ
４２ｂ    特定のエントリ
４６ｂ    特定のエントリ
４４    次のセクション
４４ａ    ニブル
４６    特定のエントリ
５０、５２、５４、５６    ３２ビットワードフォーマット
６０    ＤＥＳ暗号化システム
７０    レジスタ
７２    レジスタ
７４    加算回路
１１０    ガロアフィールド線形変換（ＧＦＬＴ）ＬＦＳＲ
１１０ａ    ガロアフィールド線形変換器トレリスシステム
１１２    出力
１１４    新しいトレリス状態出力
１２０    ＡＤＳＬモデムトレリス
１２２    線形フィードバックシフトレジスタ（ＬＦＳＲ）
１２４、１２６、１２８、１３０    フリップフロップ
１３２    入力
１３４、１３６、１３８    排他的論理和ゲート
１４０    ライン
１６０    ガロアフィールド線形変換トレリスシステムマトリクス
１６２    排他的論理和ゲートセル
２００    デジタルシグナルプロセッサＤＳＰ
２０２    シーケンサ
２０４    様々なバス
２０６    ポインタレジスタファイル
２０８    他のレジスタ
２０９    データレジスタファイル
２１０    乗算及び累算ユニット
２１２    演算論理回路
２１４    シフタ
【図１】
2009514096.tif 000003
【図２】
2009514096.tif 000004
【図３】
2009514096.tif 000005
【図４】
2009514096.tif 000006
【図５】
2009514096.tif 000007
【図６】
2009514096.tif 000008
【図７】
2009514096.tif 000009
【図８】
2009514096.tif 000010
【図９】
2009514096.tif 000011
【図１０】
2009514096.tif 000012
【図１１】
2009514096.tif 000013
【図１２】
2009514096.tif 000014
【図１３】
2009514096.tif 000015
【図１４】
2009514096.tif 000016
【図１５】
2009514096.tif 000017
【図１６】
2009514096.tif 000018
【国際調査報告】
2009514096.tif 000019