(57)【特許請求の範囲】
【請求項１】
クロックによって制御される構成可能な線形フィードバックシフトレジスタにおける状態遷移を実現するための方法であって、前記構成可能な線形フィードバックシフトレジスタの長さはＮによって表され、状態ベクトルが前記構成可能な線形フィードバックシフトレジスタの状態を表し、前記構成可能な線形フィードバックシフトレジスタの出力がＷ出力シンボルを有し、Ｗは少なくとも２であり、前記出力シンボルは１クロックサイクルの間に生成され、前記構成可能な線形フィードバックシフトレジスタの状態遷移は、多重状態遷移行列と称されるＷのべき乗までの状態遷移行列による前記状態ベクトルの乗算を介して１クロックサイクルの間に実現される方法において、前記多重状態遷移行列は第一の行列と第二の行列とに分解され、前記第一の行列は多くともＮ＋Ｗ＋１の異なる数式を有し、前記第二の行列は多くともＮ＋Ｗ＋１の異なる数式を有する方法。
【請求項２】
前記第一の行列の前記数式は、前記構成可能な線形フィードバックシフトレジスタの前記命令の構成段階の間に評価される請求項１に記載の方法。
【請求項３】
前記第二の行列の前記成分は、
0004436830.tif 000012
によって規定され、前記第一の行列の前記成分は、
0004436830.tif 000013
によって規定され、
０＜ｉ＜Ｎ
に対して、
0004436830.tif 000014
であり、ｇ０乃至ｇＮ−１は、前記状態遷移行列において構成されるコンフィギュレーションシンボルを表す請求項１に記載の方法。
【請求項４】
クロックによって制御される構成可能な線形フィードバックシフトレジスタであって、前記構成可能な線形フィードバックシフトレジスタの長さはＮによって表され、状態ベクトルが前記構成可能な線形フィードバックシフトレジスタの状態を表し、前記構成可能な線形フィードバックシフトレジスタは、Ｗ出力シンボルを有する出力を生成するように構成され、Ｗは少なくとも２であり、１クロックサイクルの間に前記出力シンボルを生成するために、前記構成可能な線形フィードバックシフトレジスタは、多重状態遷移行列と称されるＷのべき乗までの状態遷移行列による前記状態ベクトルの乗算を介して１クロックサイクルの間に前記構成可能な線形フィードバックシフトレジスタの状態遷移を実現するための乗算手段を有する構成可能な線形フィードバックシフトレジスタおいて、前記多重状態遷移行列は第一の行列と第二の行列とに分解され、前記第一の行列は多くともＮ＋Ｗ＋１の異なる数式を有し、前記第二の行列は多くともＮ＋Ｗ＋１の異なる数式を有する構成可能な線形フィードバックシフトレジスタ。
【請求項５】
前記乗算手段は、前記第二の行列によって前記状態ベクトルの前記乗算を実行するための論理ユニットの第一のセットと、前記第一の行列によって前記状態ベクトルの前記乗算を実行するための論理ユニットの第二のセットとを有する請求項４に記載の構成可能な線形フィードバックシフトレジスタ。
【請求項６】
前記第一の行列を計算するための論理ユニットの第三のセットを有する請求項５に記載の構成可能な線形フィードバックシフトレジスタ。
【請求項７】
前記論理ユニットの第三のセットは、前記構成可能な線形フィードバックシフトレジスタの命令の構成段階の間に、前記第一の行列の計算を実行するように構成される請求項６に記載の構成可能な線形フィードバックシフトレジスタ。
【請求項８】
前記論理ユニットの第二のセットは、中間データレジスタを介して前記論理ユニットの第一のセットに結合される請求項７に記載の構成可能な線形フィードバックシフトレジスタ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クロックによって制御される構成可能な線形フィードバックシフトレジスタ（コンフィギュラブルリニアフィードバックシフトレジスタ（configurable linear feedback shift register (LFSR)））における状態遷移を実現するための方法であって、前記構成可能な線形フィードバックシフトレジスタの長さはＮによって表され、状態ベクトルが前記構成可能な線形フィードバックシフトレジスタの状態を表し、前記構成可能な線形フィードバックシフトレジスタの出力がＷの出力シンボル（符号（symbol））を有し、Ｗは少なくとも２であり、前記出力シンボルは１クロックサイクルの間に生成され、前記構成可能な線形フィードバックシフトレジスタの状態遷移は、Ｗのべき乗までの状態遷移行列（マトリックス）（多重（複数）状態遷移行列（multiple state transition matrix））による前記状態ベクトルの乗算を介して１クロックサイクルの間に実現される方法に関する。
【０００２】
本発明は、クロックによって制御される構成可能な線形フィードバックシフトレジスタであって、前記構成可能な線形フィードバックシフトレジスタの長さはＮによって表され、状態ベクトルが前記構成可能な線形フィードバックシフトレジスタの状態を表し、前記構成可能な線形フィードバックシフトレジスタは、Ｗ出力シンボルを有する出力を生成するように構成され、Ｗは少なくとも２であり、１クロックサイクルの間に前記出力シンボルを生成するために、前記構成可能な線形フィードバックシフトレジスタは、Ｗのべき乗までの状態遷移行列（多重状態遷移行列）による前記状態ベクトルの乗算を介して１クロックサイクルの間に前記構成可能な線形フィードバックシフトレジスタの状態遷移を実現するための乗算手段を有する構成可能な線形フィードバックシフトレジスタにも関する。
【背景技術】
【０００３】
線形フィードバックシフトレジスタは多くのアプリケーションを有する。通常の例は、第三世代（３Ｇ）ワイヤレス通信、特に符号分割多重接続（code division multiple access (CDMA)）規格及びＣＤＭＡを使用する基地局に基づくモバイル電話の分野から知られている。他のアプリケーションは、通信又は記憶システムにおける誤り訂正（エラーコレクション（error correction））及び誤り保護（エラープロテクション（error protection））と、通信又は記憶システムにおける暗号化（cryptography）と、超大規模集積回路（very large scale integrated (VLSI) circuit）又はメモリシステムの組み込み自己テスト（ビルトインセルフテスト（built-in self test (BIST)））と、全世界測位システム（global positioning systems (GPS)）とである。
【０００４】
通常、ＬＦＳＲは、クロックによって制御される特定の種類のデータレジスタになる。ＬＦＳＲは、状態遷移の間にＬＦＳＲのコンテンツ（内容）を決定するフィードバックループによって特徴付けられる。ＬＦＳＲの動作、特に各々のクロックの後に記憶されるシンボルのシーケンスは、数学的にモデリングされ得る。当該状況（コンテキスト（context））において、シンボルはデータ、例えばビット又は他の数値を表している。数学（数式）モデルは、シンボルのシーケンスを表す状態ベクトル及び状態遷移を実現する状態遷移行列を有している。記憶されたシンボルの数はＬＦＳＲの長さと称される。シンボルの新たなシーケンスは、状態遷移行列によって状態ベクトルの乗算を介して生成され、それ故にＬＦＳＲの新たなコンテンツがもたらされる。状態遷移は１クロックサイクルの間に実現される。出力も１クロックサイクルの間に生成される。単一のシンボルが１クロックサイクルの間の出力として生成される場合、ＬＦＳＲはシングルステップＬＦＳＲ（single-step LFSR）として識別され、少なくとも二つのシンボルが１クロックサイクルの間の出力として生成される場合、ＬＦＳＲはマルチステップＬＦＳＲ（multi-step LFSR）として識別される。ステップサイズWシンボル及び長さNシンボルを備えるマルチステップ線形フィードバックシフトレジスタは、N／Ｗ−LFSRと称される。例えば、シンボルがビットを表す場合、プロセッサが、３２ビットの長さ及び１６ビットのステップサイズを有する32/16-LFSRを有していてもよい。
【０００５】
構成可能なLFSRは、プログラムされ得ると共にコンフィギュレーション（構成）シンボル（configuration symbol）で書き換えられ（再プログラムされ）得るＬＦＳＲになる。コンフィギュレーションシンボルはＬＦＳＲの状態遷移を決定する。通常、当該シンボルは状態遷移行列の構成成分になる。例えば、暗号化アプリケーションにおいて、コンフィギュレーションシンボルは、１クロックサイクルの間にＬＦＳＲの新たなコンテンツを計算するための符号化（コーディング（coding））情報を表し得る。コンフィギュレーションシンボルの数はＬＦＳＲの長さに等しくなる。状態遷移行列はコンフィギュレーションシンボルを有するので、各々のクロックサイクルの間のＬＦＳＲの新たなコンテンツは、ＬＦＳＲのコンフィギュレーションによって決定される。ＬＦＳＲの数学モデルにおいて、コンフィギュレーションシンボルは、生成多項式（generator polynomial）によって表される。ＬＦＳＲのコンフィギュレーションは、ＬＦＳＲの初期設定（イニシャライゼーション（initialization））と同じにならない。初期設定は、ＬＦＳＲにおけるシンボルの最初（初期）のシーケンスを記憶することによってなされ得る。
【０００６】
最新技術によれば、マルチステップ線形フィードバックシフトレジスタの状態遷移は、状態遷移行列による状態ベクトルのＷ回乗算を介して実現され得る。ここでＷは、ＬＦＳＲのステップサイズを表しており、ステップサイズは、１クロックサイクルの間に生成される出力シンボルの数として規定される。状態遷移行列がＦによって表される場合、ＷステップＬＦＳＲは、Ｆによる乗算ベクトルのＷ回乗算を必要とする。当該ＬＦＳＲを実現するのに必要とされる回路アーキテクチャは、Ｗ論理積／排他的論理和スライス（AND/XOR slice）スタックを有し、論理積スライスは複数の論理積ゲートを有し、排他的論理和スライスは複数の排他的論理和ゲートを有する。１クロックサイクルの間、ＬＦＳＲのコンテンツを表す状態ベクトルは、状態遷移行列によってＷ回乗算されなければならない。結果として、ＬＦＳＲの状態遷移を実現するのに必要とされる回数は、Ｗに比例して増加する。状態遷移行列による状態ベクトルのＷ回乗算は長クロックサイクル時間をもたらし、その結果、いくつかのアプリケーションに対する問題がもたらされる。状態遷移行列による状態ベクトルのＷ回乗算の代わりに、状態ベクトルは、Ｗのべき乗までの状態遷移行列によって乗算され得る。状態遷移行列がFによって表される場合、ＷステップＬＦＳＲは、ＦＷによる状態ベクトルの乗算を必要とする。当該アプローチは許容可能なクロックサイクル時間をもたらすが、ＦＷを計算するのに必要とされる追加の論理積／排他的論理和ゲートの数量は比較的多くなる。多数のＦＷでの複雑な数式（complex expression）を評価するために追加のハードウエアが必要とされる。Ｗのべき乗までの状態遷移行列は、多重状態遷移行列とも称される。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明の目的は、多重状態遷移行列による状態ベクトルの乗算を簡略化する、示されている種類の方法を提供することにある。
【０００８】
本発明の他の目的は、第二の行列及び第一の行列による状態ベクトルの乗算のための乗算手段をもたらすと共にＬＦＳＲの命令の構成段階（コンフィギュレーションステージ（configuration stage））の間に第一の行列を計算する手段をもたらす、示されている種類の線形フィードバックシフトレジスタ（ＬＦＳＲ）を提供することにある。  
【課題を解決するための手段】
【０００９】
前記目的を達成するために、本方法は、請求項１の特徴部分によって特徴付けられる。前記他の目的を達成するために、ＬＦＳＲは、請求項４の特徴部分によって特徴付けられる。
【００１０】
クロックによって制御されるマルチステップＬＦＳＲにおいて、１クロックサイクルの間に少なくとも二つの出力シンボルが生成される。アクセス可能なクロックサイクル時間を保証するために、ＬＦＳＲにおいて記憶されるシンボルのシーケンスを表す状態ベクトルは、Ｗのべき乗まで累乗される状態遷移行列によって乗算されなければならない。ここでＷはＬＦＳＲのステップサイズを表す。例えば、ステップサイズが５に等しくなる場合、状態ベクトルは５のべき乗まで状態遷移行列によって乗算されなければならない。Ｆ５は多くの複雑な数式を含んでいるため、Ｆ５の計算は多数の追加の論理積／排他的論理和ゲートを必要とする。
【００１１】
本発明による方法は、同じ状態遷移を実現する二つの行列に多重状態遷移行列を分解することによってマルチステップＬＦＳＲの状態遷移を簡略化する。追加のハードウエア、特に追加の論理積／排他的論理和ゲートの数量は、簡略化された状態遷移に対してかなり少なくなる。
【００１２】
請求項２において規定される実施例は、コンフィギュレーションシンボルがあまり頻繁に更新されないＬＦＳＲにおいて好ましい。ＬＦＳＲが構成され、コンフィギュレーションシンボルが与えられるときに、第一の行列の成分（要素）は計算され得る。このことは定期的に、例えば毎Ｘクロックサイクル後に一度起こってもよい。Ｘは１０００のような比較的大きな数になり得る。第一の行列の成分の計算は、Ｘクロックサイクル毎に繰り返されればよいと共に第一の行列における数式は比較的単純になるため、この計算は計算のクリティカルパスの範囲内にない。この場合、クロックサイクル時間は、第一の行列の特性を使用して低減されてもよいという更なる利点がもたらされる。
【００１３】
請求項３において規定される実施例は特に多重状態遷移行列の有利な分解になり、第一の行列及び第二の行列の成分の正確な基準（スペック（specification））をもたらす。
【００１４】
請求項４によるＬＦＳＲは、多重状態遷移行列の分解を反映する。
【００１５】
請求項５において規定される更なる実施例は、第二の行列による状態ベクトルの乗算のための論理ユニットの第一のセットを有し、第一の行列による状態ベクトルの乗算のための論理ユニットの第二のセットを有する。
【００１６】
請求項６において規定される更なる実施例は、第一の行列の計算のための論理ユニットの第三のセットを有する。
【００１７】
請求項７において規定される実施例は、定期的だが、あまり頻繁にならないようにＬＦＳＲが構成される場合に好ましい。第一の行列の計算、特に第一の行列における数式の評価は、各々のクロックサイクルの間に実行されない。ＬＦＳＲの構成に対するインタバルが適切に選択される場合、第一の行列における数式は比較的単純になると共に当該数式は頻繁に評価されないため、第一の行列の計算は計算のクリティカルパスの外でなされる。
【００１８】
請求項８において規定される実施例は、遅延させられたシーケンスが生成されるべきである場合に好ましいＬＦＳＲの拡張をもたらす。
【００１９】
出力を生成するのに必要とされる時間の量はかなり低減させられ得るため、本発明は、構成可能なマルチステップ線形フィードバックシフトレジスタの欠点を克服する。このことは、ＬＦＳＲの次の段階を計算するのに必要とされる追加のハードウエアの数量が比較的少なくなる一方で、クロックサイクル時間を最小限化することによって実現される。
【００２０】
マルチステップ線形フィードバックシフトレジスタが、米国特許第US 5,412,665号公報から知られていることは注意される。ＷはＮよりも小さくなるか、又はＮに等しくなる（Ｗ≦Ｎ）という条件下で当該マルチステップＬＦＳＲは長さＮビット及び可変ステップサイズＷビットを有する。当該特定のＬＦＳＲを実現するのに必要とされる回路アーキテクチャは、Ｗ論理積／排他的論理和スライスのスタックを有する。本文献は、本発明による第一及び第二の行列における多重状態遷移行列を分解することを開示するものではなく、示唆するものでもない。
【００２１】
本発明は、図面を参照して更に詳細に記載される。
【発明を実施するための最良の形態】
【００２２】
図１は8/1-LFSR及びその数学モデルを示す。クロック１１０はＬＦＳＲを制御し、各々のクロックサイクルの間、変数ｔは１でインクリメントされる。最初に変数ｔは値‘０’を有し、１クロックサイクル後、ｔは値‘１’を有し、２クロックサイクル後、ｔは値‘２’を有する。次の状態関数（next-state function）１２０は、１クロックサイクルの間にＬＦＳＲの状態遷移を実現させ、状態ベクトル１３０は、数学モデルにおけるＬＦＳＲのコンテンツを表す。１クロックサイクルの間に出力１４０は１ビットを有し、ＬＦＳＲはシングルステップＬＦＳＲになる。ｔ＝５において、すなわち５クロックサイクル後、五つの出力ビットが生成されている。５クロックサイクル後の状態ベクトル１６０は、ｔ＝５におけるＬＦＳＲを表す。状態遷移は、次の状態関数１２０を介して、特に状態遷移行列１５０による状態ベクトル１３０の乗算を介して１クロックサイクルの間に実現される。各々のクロックサイクルの間、状態遷移行列による状態ベクトルの正確に一つの乗算が実行される。
【００２３】
状態遷移行列Ｆは以下の形態を有する。
【数１】
0004436830.tif 000002
【００２４】
変数Ｎは、ＬＦＳＲの長さを表し、変数ｇ０、ｇ１、．．．、ｇＮ−１（ｇ０乃至ｇＮ−１（ｇ０、ｇ１からｇＮ−１以下））は、状態遷移行列の数式とも称され、ＬＦＳＲのコンフィギュレーション（構成）ビットを表す。この場合、コンフィギュレーションシンボルはビットを表す。行列における空の値（エンプティーバリュー（empty value））は値‘０’として読み出されなければならない。コンフィギュレーションビットの数は、ＬＦＳＲの長さに等しくなるので、8/1-LFSRの次の状態関数は、以下の状態遷移行列Ｆをもたらす。
【数２】
0004436830.tif 000003
【００２５】
例として、コンフィギュレーションビットは、値g0=1, g1=0, g2=1, g3=1, g4=0, g5=1, g6=0 及び g7=0を与えている。従って、図１、図２、及び図３の例において使用される状態遷移行列Ｆは以下のようになる。
【数３】
0004436830.tif 000004
【００２６】
図２は、8/5-LFSR及びその数学モデルを示す。ここでも、クロック２１０はＬＦＳＲを制御し、各々のクロックサイクルの間、変数ｔは１でインクリメントされる。最初に変数ｔは値‘０’を有し、１クロックサイクル後、ｔは値‘１’を有する。次の状態関数２２０は、１クロックサイクルの間にＬＦＳＲの状態遷移を実現させ、状態ベクトル２３０は、数学モデルにおけるＬＦＳＲのコンテンツを表す。１クロックサイクルの間に出力２４０は５ビットを有し、ＬＦＳＲは５ステップＬＦＳＲになる。ｔ＝１において、すなわち１クロックサイクル後、五つの出力ビットが生成されている。１クロックサイクル後の状態ベクトル２６０は、ｔ＝１におけるＬＦＳＲを表す。状態遷移は、次の状態関数２２０を介して１クロックサイクルの間に実現される。しかしながら、次の状態関数はこの場合、ＬＦＳＲの状態遷移を実現させるために、状態遷移行列１５０を５回展開しなければならない。状態ベクトルは、状態遷移行列２５０によって５回乗算される。このアプローチプは、シングルステップＬＦＳＲと比較して更なるハードウエアを必要とし、クロックサイクル時間はかなり増大させられる。
【００２７】
代わりに、状態遷移行列２５０は、５のべき乗にまで累乗され、それから状態ベクトルはＦ５によって乗算される（図示略）。このアプローチは、許容可能なクロックサイクル時間をもたらすが、Ｆ５における数式を評価するのに必要とされる更なるハードウエアの数量が比較的多くなる。
【００２８】
図３は、本発明による8/5-LFSRを示す。クロック３１０はＬＦＳＲを制御し、各々のクロックサイクルの間、変数ｔは１でインクリメントされる。最初に変数ｔは値‘０’を有し、１クロックサイクル後、ｔは値‘１’を有する。次の状態関数３２０は、１クロックサイクルの間にＬＦＳＲの状態遷移を実現させ、状態ベクトル３３０は、数学モデルでＬＦＳＲのコンテンツを表す。１クロックサイクルの間に出力３４０は５ビットを有し、ＬＦＳＲは５ステップＬＦＳＲになる。ｔ＝１において、すなわち１クロックサイクル後、五つの出力ビットが生成されている。１クロックサイクル後の状態ベクトル３８０は、ｔ＝１におけるＬＦＳＲを表す。ここでも状態遷移は、次の状態関数を介して１クロックサイクルの間に実現される。しかしながら、次の状態関数３２０は異なるアプローチを使用する。５のべき乗までの状態遷移行列３５０による状態ベクトル３３０の乗算によって後続される状態遷移行列３５０の累乗（involution）は、あまり複雑でない方法によって、特に第一の行列３６０及び第二の行列３７０による状態ベクトル３３０の乗算によって置換される。第一の行列３６０は、N + W + 1 = 8 + 5 + 1 = 14であるため、多くとも１４の異なる数式を有する。第二の行列３７０も、N + W + 1 = 8 + 5 + 1 = 14であるため、多くとも１４の異なる数式を有する。
【００２９】
状態遷移行列Fは、５のべき乗まで累乗され、Ｆ５がもたらされる。行列Ｆ５は、P5 * G5に分解される。ここで、P5 は第一の行列３６０であり、G5は第二の行列３７０である。これらの例において、第一の行列３６０及び第二の行列３７０はそれぞれ以下の形態を有する。
【数４】
0004436830.tif 000005
【００３０】
当該例において、第一の行列P5は５の異なる数式（p0, p1, ．．．, p4（p0乃至p4））を有しており、第二の行列G5は８の異なる数式（g0, g1, ．．．, g7（g0乃至g7））を有している。G5における数式は、それらの値が既に与えられているため、評価される必要はない。P5における数式は評価される必要があるが、それらの複雑性は、Ｆ５における数式の複雑性（複雑さ）と比較して比較的低くなる。数式の複雑性における差を示すために、P5における数式及びＦ５の第四の列における数式が例として与えられる。シンボルがビットを表す場合、P5における数式piは以下のように算出される。
【数５】
0004436830.tif 000006
【００３１】
行列Ｆ５の第四の列における数式は以下のように算出される。
【数６】
0004436830.tif 000007
【００３２】
同様に、Ｆ５の残りの列は、相互に異なると共に他の列における数式と異なる五つの数式を有している。Ｆ５における異なる数式の総数は４０に等しくなる。当該総数は本発明による１４の異なる数式の最大数を明らかに超えている。更に、Ｆ５の残りの列は同様の複雑度の数式を有しており、従ってＦ５の全体的な複雑性は、P5の複雑性よりもかなり高くなる。数式g0, g1, ．．．, g7は、ＬＦＳＲのコンフィギュレーションビットを表す簡単な数式であり、数式p0, p1, ．．．, p4は、簡単な数式g0, g1, ．．．, g7に依存して、計算された値を有する。
【００３３】
N/W-LFSRの場合、第二の行列３７０の成分は
【数７】
0004436830.tif 000008
によって規定され、第一の行列３６０の成分は
【数８】
0004436830.tif 000009
によって規定される。ここで０＜ｉ＜Ｎの場合、p0＝１かつ
【数９】
0004436830.tif 000010
となる。
【００３４】
行列の成分を計算するために上記の等式を使用して、第一の行列３６０及び第二の行列３７０は、
【数１０】
0004436830.tif 000011
になる。
【００３５】
前記行列Ｆ５、P5、及びG5は、図３の例において実行される計算で使用される。この場合、Ｎは８に等しくなり、Ｗは５に等しくなる。本発明は、可変長さ及び可変ステップサイズでＬＦＳＲの実施例に適用される。変数ＮはＬＦＳＲの長さを表し、変数ＷはＬＦＳＲのステップサイズを表す。
【００３６】
図４は、本発明によるN/W-LFSRのための回路アーキテクチャを示す。論理ユニットは論理積スライス及び排他的論理和スライスを有する。論理積スライスは複数の論理積ゲートを有し、排他的論理和スライスは複数の排他的論理和ゲートを有する。更に論理積／排他的論理和スライスは、行列乗算によるベクトルに対して必要とされる乗算及び加算命令を実行し得る。論理ユニットの三つのセットは、
論理積スライス４０８及び排他的論理和スライス４１０の第一のセット４０２と、
論理積スライス４１６及び排他的論理和スライス４１８の第二のセット４０６と、
論理積スライス４１２及び排他的論理和スライス４１４の第三のセット４０４と
に識別される。
【００３７】
生成多項式４２２は、数学モデルにおけるＬＦＳＲのコンフィギュレーションビットを表す。生成多項式の成分は、状態遷移行列３５０における簡単な数式として使用され、当該数式は、第一の行列３６０の数式piの構成要素になる。ＬＦＳＲのコンテンツは状態ベクトル４２６によって表され、１クロックサイクルの間、状態ベクトルは第二の行列３７０によって乗算され、中間ベクトルが第一の行列３６０によって乗算される。１クロックサイクルの間、出力ビット４２４が生成され、出力ビットの数量はＬＦＳＲのステップサイズＷに等しくなる。
【００３８】
第二の行列３７０による状態ベクトル４２６の乗算は、論理積スライス４０８及び排他的論理和スライス４１０の第一のセット４０２によって実行される。第一の行列３６０による結果としてもたらされる中間ベクトルの乗算は、論理積スライス４１６及び排他的論理和スライス４１８の第二のセット４０６によって実行される。論理積スライス４１２及び排他的論理和スライス４１４の第三のセット４０４は、第一の行列３６０を計算するために、特に第一の行列における数式piを評価するためにもたらされる。
【００３９】
本願に記載の実施例は、ＬＦＳＲのコンテンツを更新するためにフィードバックループ及び出力ストリームを有するＬＦＳＲに適用される。この種のＬＦＳＲは通常、生成器（ジェネレータ（generator））、例えば擬似ランダム雑音（Pseudo Random Noise (PRN)）生成器にもたらされる。入力の供給源はフィードバックループのみであり、フィードバックループは、出力部上に次の状態関数を有する。本願に記載のＬＦＳＲは、シンボリックフォーム（記号形態（symbolic form））５１０を有する。
【００４０】
図５に示されているように当該ＬＦＳＲの二つの重要なバリエーション（変形体）が存在する。本願に記載の方法は、これらのバリエーション（変形体）においても適用され得る。第一のバリエーションは通常、巡回冗長検査（cyclic redundancy check (CRC)）アプリケーション、又はハードウエアの組み込み自己テスト（BIST）のための署名分析（シグナチャアナリシス（signature analysis））にもたらされる。当該バリエーションは、ＬＦＳＲのコンテンツを更新するために入力ストリーム及びフィードバックループを有するが、出力ストリームを有さない。第一のバリエーションはシンボリックフォーム５２０を有する。第二のバリエーションは通常、暗号化アプリケーションにもたらされる。当該バリエーションは、入力部と共にＬＦＳＲのコンテンツを更新するために入力ストリーム、出力ストリーム、及びフィードバックループを有する。フィードバックループは入力ストリームを暗号化するために使用される。すなわち、出力ストリームは、暗号化された入力ストリームである。第二のバリエーションはシンボリックフォーム５３０を有する。
【００４１】
第一のバリエーション５２０は、入力ストリームが考慮されなければならないため、わずかに異なる状態遷移の計算を必要とする。このことは図６に示されている。ここでもクロック６１０はＬＦＳＲを制御し、各々のクロックサイクルの間、変数ｔは１でインクリメントされる。最初に変数ｔは値‘０’を有し、１クロックサイクル後、ｔは値‘１’を有する。次の状態関数６２０は、１クロックサイクルの間にＬＦＳＲの状態遷移を実現させ、状態ベクトル６３０は、数学モデルでＬＦＳＲのコンテンツを表す。ＬＦＳＲは、５入力ビットを消費するが出力を生成しないため、５ステップＬＦＳＲになる。入力部６４０は１クロックサイクルの間に五つのビットを有する。状態ベクトル６９０は、ｔ＝１におけるＬＦＳＲのコンテンツを表す。多重状態遷移行列は第一の行列６５０と第二の行列６６０とに分解される。次に、状態ベクトル６３０は第二の行列６６０によって乗算される。それから入力ベクトル６６５は第一の中間ベクトル６７０に加算され、入力ベクトルの下位五つの値は五つの入力ビットに対応する。最終的に、第二の中間ベクトル６８０は第一の行列６５０によって乗算される。状態遷移の計算のための同様のアプローチが第二のバリエーション５３０に対して使用され得る（図示略）。
【００４２】
ＬＦＳＲが使用されるアプリケーションによって課せられる要求仕様によりＬＦＳＲを拡張させることは可能である。特に有利な拡張は、図７に記載されているように、遅延シーケンスを生成するためにパイプラインレジスタとも称される中間データレジスタを有することである。このコンテンツにおいて、遅延シーケンスは、任意の数のシンボルによって遅延させられるシンボルのシーケンスの複製である。パイプラインレジスタを初期化することによって、前記シンボルの数がセットされる。シンボルのシーケンス及び遅延シーケンスは、シンボルのシーケンスが偶数クロックサイクルの間に、遅延シーケンスが奇数のクロックサイクルの間に（又はその逆に）それぞれタイミング通りにインタリーブ（output interleave）されて出力される。パイプラインベクトル７１０は、パイプラインレジスタのコンテンツを表す。この拡張されたＬＦＳＲのための回路アーキテクチャは、論理積スライス４０８及び排他的論理和スライス４１０の第一のセット４０２がパイプラインレジスタを介して論理積スライス４１６及び排他的論理和スライス４１８の第二のセット４０６に結合されることを除いて同じままである。パイプラインは、図７に示されているように、別個のエンティティ（実体（entity））として実現されてもよく、又はパイプラインレジスタは、第一のセット４０２若しくは第二のセット４０６の何れかで構成されてもよい。利点は、たった一つの追加のレジスタの犠牲で回路アーキテクチャにおいて、クロックサイクル時間はかなり低減され得る一方で、遅延シーケンスが二つのクロックサイクルの間に生成され得ることにある。
【００４３】
本発明の保護範囲はここに記載されている実施例に限定されないことは注意されるべきである。本発明の保護範囲は、請求項に記載の参照番号によっても限定されるものではない。単語“有する”は、請求項に記載される構成要素以外に構成要素の存在を排除するものではない。構成要素に先行する冠詞“a”又は“aｎ”は、複数の構成要素を排除するものではない。本発明の構成要素を形成する手段は、専用のハードウエアの態様又はプログラムされた汎用のプロセッサの態様の両方で実現されてもよい。本発明は、各々の新たな特徴又は特徴の組み合わせに帰するものである。
【図面の簡単な説明】
【００４４】
【図１】最新技術による8/1-LFSR及びその数学モデルを示す。
【図２】最新技術による8/5-LFSR及びその数学モデルを示す。
【図３】本発明による8/5-LFSR及びその数学モデルを示す。
【図４】本発明によるN/W-LFSRのための回路アーキテクチャを示す。
【図５】8/5-LFSRの複数の変形例を示す。
【図６】本発明による8/5-LFSR及びその数学モデルの変形例を示す。
【図７】中間データレジスタで拡張されるN/W-LFSRのための回路アーキテクチャを示す。
【図１】
0004436830.tif 000015
【図２】
0004436830.tif 000016
【図３】
0004436830.tif 000017
【図４】
0004436830.tif 000018
【図５】
0004436830.tif 000019
【図６】
0004436830.tif 000020
【図７】
0004436830.tif 000021