(57)【特許請求の範囲】
【請求項１】
ワードメモリと、イニシャライザと、出力シーケンスセレクタと、新規メモリーワードセレクタとを備える擬似ランダムノイズ生成器が擬似ランダムノイズシーケンスを生成する方法であって、
前記ワードメモリが、メモリーエレメントのセットを形成する形成工程であって、各メモリーエレメントが任意のワード長を有するメモリーワードを格納する、形成工程と、
前記イニシャライザが、前記形成工程で形成された各メモリーエレメントを初期状態値で初期化する初期化工程であって、各メモリーエレメントの初期化に用いられる前記初期状態値が前記メモリーエレメントに格納されるメモリーワードを形成する、初期化工程と、
前記出力シーケンスセレクタが、出力シーケンスを形成するために、少なくとも一つの前記メモリーエレメントに格納された少なくとも一つの前記メモリーワードを選択する選択工程であって、前記出力シーケンスは、擬似ランダムノイズシーケンスの一部を形成する、選択工程と、
前記新規メモリーワードセレクタが、前記メモリーエレメントのセットの少なくとも一つの前記メモリーエレメントに格納される少なくとも一つの新規のメモリーワードを選択する工程であって、前記新規メモリーワードは、前記メモリーエレメントセット内の前記メモリーエレメントに格納された前記メモリーワードの任意の結合で構成され、前記少なくとも一つの新規メモリーワードのワード長は、前記出力シーケンスを形成するために選択されたメモリーワードのワード長と一致する、工程と
を備え、
前記擬似ランダムノイズシーケンスが所定の次数のウィンドミル多項式によって生成された値と一致する値を有し、前記所定の次数は、少なくとも部分的に、前記形成工程において形成された前記メモリーエレメントセットの前記メモリーエレメントの数に限定される
ことを特徴とする方法。
【請求項２】
前記メモリーエレメントセットのメモリーエレメントの数が、さらに前記各メモリーワードを形成するワード長に反比例することを特徴とする、請求項１に記載の方法。
【請求項３】
前記メモリーエレメントセットを形成するメモリーエレメントの数が、選択された次数に正比例することを特徴とする請求項２に記載の方法。
【請求項４】
前記形成工程において形成された前記メモリーエレメントセットが、出力メモリーエレメントを形成するために選択された複数メモリーエレメントのスタックのうちの少なくとも一つのメモリーエレメントである、メモリーワードのスタックを形成する、前記メモリーエレメントの論理的に連続したグループを備え、少なくとも一つの前記メモリーワードを選択する前記工程において選択されたメモリーワードの少なくとも一つが、出力メモリーエレメントに格納された少なくとも一つのメモリーワードを備えることを特徴とする請求項１に記載の方法。
【請求項５】
前記メモリーエレメントの論理的に連続するグループの連続が列を定義し、かつ、メモリーワードを列方向に、メモリーエレメントのスタックを通してシフトされることを特徴とする請求項４に記載の方法。
【請求項６】
前記少なくとも一つの新規メモリーワードを選択する工程において選択された前記少なくとも一つの新規メモリーワードが、前記任意の次数のウィンドミル多項式によって生成された帰還値に一致する値のメモリーワードを備えることを特徴とする請求項５に記載の方法。
【請求項７】
前記メモリーエレメントの任意の少なくとも一つに、少なくとも一つの巡回更新ポインタが割り当てられることを特徴とする請求項１に記載の方法。
【請求項８】
割り当てられた前記少なくとも一つの巡回更新ポインタが、前記選択工程において選択されたメモリーワードが格納されている少なくとも一つの前記メモリーエレメントを識別することを特徴とする請求項７に記載の方法。
【請求項９】
割り当てられた前記少なくとも一つの巡回更新ポインタが、少なくとも一つの新規メモリーワードを選択する前記工程において選択され、前記少なくとも一つの新規メモリーワードが格納される、少なくとも一つのメモリーエレメントを識別することを特徴とする請求項８に記載の方法。
【請求項１０】
前記形成工程において形成されたメモリーエレメントのそれぞれに格納されている前記メモリーワードのそれぞれの任意のワード長が、互換性のあるワード長を形成する任意のワード長の少なくとも一つの倍数となるように選択され、前記選択工程において選択された少なくとも一つのメモリーワードが、少なくとも一つの単一メモリーワードの倍数を備えることを特徴とする請求項１に記載の方法。
【請求項１１】
前記出力シーケンスを構成するために前記メモリーワードの少なくとも一つを選択し、かつ、前記新規メモリーワードの少なくとも一つを選択する前記工程が、反復的に実施されることを特徴とする請求項１に記載の方法。
【請求項１２】
任意のウィンドミル多項式のために、共通の擬似ランダムシーケンスを生成するためのウィンドミル多項式生成器の代替構成の互換性を決定する、特徴付け手段と、決定手段と、識別手段とを備える装置における、該互換性の決定方法であって、前記任意のウィンドミル多項式がウィンドミル多項式次元及び、ウィンドミル多項式重みによって識別される方法が、
前記特徴付け手段が、第一の多項式部分と、第二の多項式部分とによって前記ウィンドミル多項式を特徴付ける工程であって、前記第一の多項式部分の次数が前記ウィンドミル多項式の次数と一致している、工程と、
前記決定手段が、前記第二の多項式部分の特性を決定する工程であって、前記第二の多項式部分は前記第一の多項式部分と結合して前記ウィンドミル多項式を形成し、前記第二の多項式部分の各特性がウィンドミル多項式生成器の分離構成を識別し、前記第二の多項式部分の特性のそれぞれが所定の基準を満たすかどうかを決定する、工程と、
前記識別手段が、前記特性が前記所定の基準を満たしている場合に、ウィンドミル多項式生成器が互換性のある代替構成を有すると識別する工程と
を備えることを特徴とする方法。
【請求項１３】
前記第二の多項式部分の各特性が、ワードサイズを識別する設計べき指数と関連することを特徴とする、請求項１２に記載の方法。
【請求項１４】
前記第二の多項式部分が前記所定の基準を満たすかどうかを決定するための前記所定の基準が、等式１=L mod vを備え、ここで、Ｌが前記ウィンドミル多項式の次数であり、ｖが前記第二の多項式部分に関連する設計べき指数であることを特徴とする請求項１２に記載の方法。
【請求項１５】
前記所定の基準を前記特性のそれぞれが満たすかどうかを決定するための前記所定の基準が、等式 v-1=L mod vを備え、ここで、Ｌが前記ウィンドミル多項式の次数であり、ｖが前記第二の多項式部分に関連する設計べき指数であることを特徴とする請求項１２に記載の方法。
【請求項１６】
擬似ランダムノイズシーケンスを生成するための擬似ランダムノイズ生成器であって、
任意のワード長を有するメモリーワードをそれぞれのメモリーエレメントに格納するためのメモリーエレメントセットと、
前記セットの各メモリーエレメントを初期状態値で初期化するためのイニシャライザと、
前記セットのメモリーエレメントの少なくとも一つに格納されている、少なくとも一つのメモリーワードを選択するための出力シーケンスセレクタであって、前期出力シーケンスが擬似ランダムノイズシーケンスの一部を構成する出力シーケンスセレクタと、
前記セットのメモリーエレメントの少なくとも一つに格納される、少なくとも一つの新規メモリーワードを選択するための新規メモリーワードセレクタであって、前記新規メモリーワードが、前記メモリーエレメントのセットのメモリーエレメントに格納されたメモリーワードの任意の結合から構成されており、少なくとも一つの新規メモリーワードのワード長が出力シーケンスを構成するために選択されたメモリーワードのワード長と一致する、新規メモリーワードセレクタと
を備え、
前記擬似ランダムノイズシーケンスが所定の次数のウィンドミル多項式によって生成された値と一致する値を有し、前記所定の次数は、少なくとも部分的に、前記形成工程において形成された前記メモリーエレメントセットの前記メモリーエレメントの数に限定される
ことを特徴とする擬似ランダムノイズ生成器。
【請求項１７】
任意のウィンドミル多項式のために、共通擬似ランダムシーケンスを生成するための、ウィンドミル多項式生成器の代替構成の互換性を決定する装置であって、前記任意のウィンドミル多項式が、ウィンドミル多項式次数及びウィンドミル多項式重みシーケンスによって識別される装置が、
前記ウィンドミル多項式を第一の多項式部分と第二の多項式部分とにより特徴づける特徴付け手段であって、前記第一の多項式部分の次数は、前記ウィンドミル多項式の次数と一致している、特徴付け手段と、
前記第二の多項式部分の特性を決定する決定手段であって、前記第二の多項式部分の各特性によりウィンドミル多項式生成器の分離構成を識別し、所定の基準を前記第二の多項式部分の各特性が満たすかどうかを決定する決定手段と、
前記所定の基準を前記特性が満たす場合には、ウィンドミル多項式生成器が互換性のある代替構成を有すると識別するための識別手段と
を備えることを特徴とする決定装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は一般には、例えば暗号化処理において利用されるような擬似乱数シーケンスの生成に関連する。より詳細には、本発明は、任意のウィンドミル多項式により生成されたシーケンスに一致する擬似乱数シーケンスを生成するための擬似乱数シーケンス生成器及び、生成方法に関連する。本発明は、さらには、ウィンドミル多項式ベースの擬似乱数シーケンス生成器の異なる構成間の互換性を決定する方法と関連する。
【０００２】
ワード志向のメモリーエレメントは擬似乱数シーケンスを形成するワードを格納するために利用される。メモリーワードのサイズは、ウィンドミル生成器の代替的な互換性のある構成に一致する、同一の擬似乱数シーケンスの生成を増加促進するために、継続的な反復動作の間にウィンドミルによって生成されるシーケンス部が直ちに増加するように選択される。
【０００３】
本発明の実施形態により生成される擬似乱数シーケンスは、セルラー通信システムの移動局と無線基地局の間で形成されるような、無線リンクを介して通信されるデータを暗号化するためにシステムの一部として有益に利用される。本発明の実施形態の作用により生成される擬似乱数シーケンスはまた、スペクトル拡散通信（ＣＤＭＡ）、自動レンジングシステム、音声信号圧縮方法、及びレーダーシステムにおいて有益に利用される。
【０００４】
【従来の技術】
[発明の背景]
通信システムは、送信局と受信局の間で通信チャネル方法により情報通信を行うことができる。有線通信システムでは、通信チャネルが送受信局の間で固定的な接続により形成されている。そして、無線通信システムでは、通信チャネルは電磁波周波数スペクトラムの一部を形成する。無線通信システムの送受局間で通信チャネルを形成するのに固定的な接続は必要とされないので、送受信局間での固定的な接続が実用的でない場合にも通信が可能となる。
【０００５】
ディジタル通信システムは、送信局から受信局に通信される情報がディジタル化される通信システムである。ディジタル通信システムは、有線通信システム及び無線通信システムの両方で実現できる。ディジタル通信システムは、送受信局間に及ぶ通信チャネルのより効果的な利用を可能とし、これにより通信システムの通信容量は従来のアナログ通信システムよりも増加することになる。
【０００６】
送受信局間の通信は時には必然的に秘密であることが要求される。即ち、通信信号を送受信する当事者が、送受信当事者のみが通信信号の情報の内容にアクセスできることを意図することがある。特に、通信チャネルが無線通信システムの無線通信チャネルである場合は、送受信局間の通信プライバシーには問題が多い。無線チャネルは元来全く公のものであるので、通信チャネルにより転送される通信信号は、通信信号の範囲内の、無線チャネルに同調されたいかなる受信局によっても検出できる。不許可のパーティーは、例えば、無線受信機を通信信号が伝送される無線チャネルの周波数に同調させることができ、これにより通信信号を受信できる。同様のセキュリティー問題は、不許可のパーティーによる有線通信チャネルへのアクセスが増加する状況では、有線通信システムにおける考慮事項でもある。
【０００７】
通信システムにおける通信の安全性を改善する一つの手法は、通信信号を形成する情報を暗号化することである。許可されたパーティーのみが暗号化された通信信号を復号化できるとすると、不許可のパーティーは通信チャネルで伝送される通信信号の情報内容を理解できない。これにより、通信の秘密がより保証されることになる。
【０００８】
ディジタル情報信号は特に暗号化処理と相性がよい。ディジタル情報信号は、ビットシーケンスで形成され、要求があれば、情報信号の各ビットは送信局において通信チャネルでの伝送前に暗号化される。情報信号の暗号化方法を知らない不許可のパーティーは、受信信号を復号化して伝送信号の情報内容を復元することができない。暗号化された信号を復号化できる受信局のみが、受信信号の情報内容を復元できる。
【０００９】
さまざまな手法がディジタル情報信号を暗号化するために利用されている。セルラー通信において用いられるような典型的な暗号化手法は、情報信号のディジタルビットが擬似乱数シーケンス生成器により生成される擬似乱数シーケンスのビットと結合される暗号化手法を利用している。擬似乱数シーケンス生成器は、対称暗号化方式において、送信局及び許可された受信局に既知な秘密鍵と結合して実現される。秘密鍵は許可された受信局で受信した暗号化信号を復号化するのに利用され、それにより伝送信号の情報内容が復元される。
【００１０】
擬似乱数シーケンスは場合によっては、ウィンドミル多項式の計算から導出される。ハードウェアやソフトウェアで実装されようと、擬似乱数シーケンスをこの手法で生成する構成は、ウィンドミル生成器として引用されることがある。ウィンドミル生成器により生成される出力ビットは、とりわけ情報信号を暗号化するために利用される擬似乱数シーケンスを形成する。ウィンドミル生成器は、ある有限体ＧＦ(q)上の選択された原始多項式に直接関連する。q=2の場合、有限体GF(2)は、バイナリケースとして引用され、ディジタル通信において特に重要である。ウィンドミル生成器を導く原始多項式の数は、多項式の多くの制約により制限される。特にバイナリケースにおいて、出力に必要な処理を最小にするために、多項式のノンゼロ係数がわずかでなければならない場合は、ウィンドミル多項式を形成するために利用される適切な多項式の数は制限される。多項式のノンゼロ係数の数は、多項式の重みとして引用される。
【００１１】
ＧＦ(2)のバイナリケースならば、３つまたは５つのノンゼロ係数及び５０００次までの次数を有する多項式のような、原始多項式をリストするテーブルが存在する。
【００１２】
重み３のバイナリウィンドミル多項式で生成される、ここでしばしｎタプルとして引用される出力のランダム性は一般に乏しく、出力のランダム性を増加させるために高い重みの多項式が必要となる。しかし、そのような改善されたランダム性は、処理要求の増大による出費の原因となる。既存のテーブルは、擬似乱数シーケンスを導くためのウィンドミル多項式を選択するのに必ずしも利用することができない。というのも、そのような既存のテーブルが３つまたは５つのノンゼロ係数を伴う全ての原始多項式を必ずしも示す訳ではないからである。特に、擬似乱数シーケンスが暗号化処理に利用される場合には、有限体GF(2)での任意の次数の全てのウィンドミル多項式が分かっていることは価値がある。しかし、そのような知識を導くための方法はない。代わりに、従来、Knuth Allanenテストのような原始的であるかどうかのテストを含む検証プロセスが実施される。
【００１３】
従来のウィンドミル生成器から得られるヴェインは、生成器で形成された出力のビットサイズ、即ち、nタプルを決定する。処理速度のより高い処理装置の連続的な発生と共に処理性能が改善されるので、膨大なヴェインを有する従来ウィンドミル生成器はいよいよ実用的なものとなる。多数のヴェインを有するウィンドミル生成器からは、より大きなビットサイズの出力を得ることができる。ゆえに、擬似乱数シーケンスをより早く生成することができる。
【００１４】
ウィンドミル生成器が他のウィンドミル生成器と互換性のある構成の場合、同一擬似乱数シーケンスは各構成の生成器で生成される。そのような互換性は、異なる構成のウィンドミル生成器を利用する装置及び方法から同一結果を得るために一般に必要とされる。
【００１５】
しかしながら、ウィンドミル生成器の異なる構成の互換性を簡単に決定する方法は存在しない。従来、分離構成間の互換性は、ある構成のある初期状態を別の構成のそれに写像することによってのみ実現された。しかし、そのような写像は、膨大な操作を必要とした。しかしながら、特別のウィンドミル多項式は、構成間の実に単純な変換を可能とする。
【００１６】
従って、共通の擬似乱数シーケンスを生成するためのウィンドミル生成器の代替的構成の互換性を決定する方法を提供することは有効である。
【００１７】
さらに、単純化された構成であって、任意のウィンドミル多項式に一致する擬似乱数シーケンスを生成するだけでなく、要求があれば代替構成に簡単に変換することができるウィンドミル生成器を提供することは有効である。
【００１８】
擬似乱数シーケンスの生成に関連するこの発明の背景を考慮して、本発明の重要な改良点を以下に説明する。
【００１９】
[発明の要約]
本発明は、共通の擬似乱数シーケンスを生成するウィンドミル生成器の代替構成の互換性を決定する方法を提供するものである。
【００２０】
本発明は、さらに、単純化された構成であって、選択されたウィンドミル多項式に一致する擬似乱数シーケンスを生成するだけでなく、要求があれば代替構成に変換することができるウィンドミル生成器を提供することができる。
【００２１】
ウィンドミル生成器の構成は、任意の初期状態で初期化された場合、同一の擬似乱数シーケンスを形成するnタプルを生成するものと同一視される。同一視された構成は、単純な関係をお互いに有する。即ち、同一擬似乱数シーケンスを生成する異なる構成操作において、任意の関係の結果の初期状態値を単にコピーすることによって同一視される。そのようなコピーは、状態空間内の次元、即ち生成する多項式の次数で線形複雑度を有し、従来ある初期状態を等価な状態に写像することを必要とするに二次元複雑度を有しない。
【００２２】
一の実施態様では、本発明の実施形態であるウィンドミル生成器により生成される擬似乱数シーケンスは、受信局へ送信局から伝送される情報の暗号化のための補助構成部分として利用される。典型的な実施形態において、通信システムは、セルラー通信システムを構成し、移動局とセルラー通信システムのネットワークインフラとの間で通信される情報は、ウィンドミル生成器によって生成された擬似乱数を利用して暗号化される。受信信号の復号化は、同様にまたウィンドミル生成器によって生成された擬似乱数シーケンスを利用して行われる。
【００２３】
本発明の別の側面では、特定の最長シーケンス及びフルレングスシーケンスにおける擬似ランダムノイズシーケンスの有効な一貫性のあるブロックを生成することにより能率的な方法を提供する。擬似乱数シーケンスを生成するためにワード志向のメモリーを利用しているので、そのようなシーケンスはすばやく生成され、膨大な計算量を必要とすることもない。そして、メモリーワードサイズを適切に選択することで、ウィンドミル生成器の代替構成が実現され、擬似乱数シーケンスは互換性を有することとなる。
【００２４】
これらの側面において、方法及び関連する装置は、擬似ランダムノイズシーケンスを生成する。メモリーエレメントのセットは、セットのメモリーエレメントのそれぞれが、その任意のワードプレーンのメモリーワードを格納する。メモリーエレメントのそれぞれは、初期状態値によって初期化される。メモリーエレメントそれぞれの初期化に用いられる初期状態値は、そこに格納されるメモリーワードを構成する。少なくとも一つのメモリーエレメントに格納される少なくとも一つのメモリーワードが、出力シーケンスを生成するために選択される。出力シーケンスは、擬似ランダムノイズシーケンスの一部を構成する。少なくとも一つの新規メモリーワードが、メモリーエレメントセットの少なくとも一つのメモリーエレメントに格納されるために選択される。新規メモリーワードは、メモリーエレメントセットのメモリーエレメントに格納されたメモリーワードの任意の結合から構成される。新規メモリーワードの少なくとも一つの数は、出力シーケンスを形成するために選択されたメモリーワードの数と一致する。
【００２５】
本発明のより完全な理解及び範囲は、以下に簡単な概要を示した添付図面、発明の好適な実施形態に係る以下の詳細な説明、及び、請求の範囲の記載より得ることができる。
【００２６】
[発明の実施形態]
最初に図１を参照すると、１０で示される典型的なウィンドミル生成器は、複数の遅延要素１２で形成され、かつ、ヴェインｖのセットに分割されている。ここで、各ヴェインは長さLiを有し、各ヴェインｖは加算器１６の入力端と接続される帰還ループ１４を含む。右端のヴェインｖは左端のヴェインの入力端と帰還ループ１８によって更に接続される。
【００２７】
タップ２２は、ヴェインｖの各々からとられ、かつ、タップ２２から提供されるシーケンスについて順列を行う順列器へ提供される。順列器２４で形成された出力シーケンスは、ライン２６上に生成される出力エンドタプルを形成し、図中Ｓ3j、Ｓ3j+1、Ｓ3j+2で表される。
【００２８】
各ヴェインｖの長さＬは、Ｌi（i=0,1,...v-1）で定義される。Ｌ0からＬv-1の長さのセットは、既知の手法によって決定される。Ｌ＝Ｌ0＋Ｌ1＋.....Ｌv-1の場合は、以下の式を満たす。
【００２９】
Ｌ＝１ mod v (Lをｖで割った余りが１) 又は
Ｌ＝(v-1) mod v
上記第一の式に従えば、順列器２４によって行われる順列を、同一順列、即ち0,1,...v-1を0,1,...v-1に写像するように選ぶことができる。この場合、長さＬiは、次式を満たす。
Ｌ0＝...＝Ｌv-2＝(Ｌ-1)/ｖ、Ｌv-1＝１+(Ｌ-1)/ｖ
出力タップ２２は各(Ｌ-1)/v番目の遅延要素１２の後得られる。
【００３０】
上記第二の式を考慮すれば、順列の選択を、0,1,...v-1をv-1,...1,0に写像する、“逆順”にすることができる。長さＬは、この場合、次式によって定義される。
Ｌ0＝...＝Ｌv-2＝(Ｌ+1)/ｖ、Ｌv-1＝-１+(Ｌ+1)/ｖ
各ヴェインｖから得られた出力タップ２２は、p番目の遅延要素１２の後ろに配置される。ここでpは、最大許容互換ｖ値に依存する数である。ウィンドミル生成器１０の初期状態ｖとウィンドミル生成器１０の初期状態ｖ'との間に、両ウィンドミル生成器１０が同一の出力シーケンスを生成するための単純な写像関係があれば、ｖ及びｖ'の二つの値は互換性を有する。即ち、ウィンドミル生成器１０の出力は、次式を満たす。
【００３１】
Ｓj＝ｆ1Ｓ(j-1)＋ｆ2Ｓ(j-2)＋...＋ｆLＳ(j-L)  ここで、j=n,n+1,... また、+は有限体GF(2)における加算を意味し、f(x)=1-f1xL-...-fL-1xL-1-fLxL
図２は、ウィンドミル生成器１０の９時限j=0-8の連続的な反復操作を行った場合の、遅延要素１２における値をリストしたテーブルを示す。テーブル２８の右側は、ウィンドミル生成器１０によってライン２２上に生成された出力をリストしたものであり、順列器２４による同一順列によってライン２６上でも同順である。
【００３２】
図３は、ヴェインｖのグループ、遅延要素１２、帰還ループ１４、加算器１６からなるウィンドミル生成器を示す図である。帰還ループ１８はまた、右端ヴェインｖと左端ヴェインｖとの間でも形成される。タップ２２は、再度ヴェインvから取られている。ここで、ウィンドミル生成器１０が６つのヴェインを包含するように、生成器１０は６つのタップ２２を包含する。同一順列で順列を行う順列器２４及び、そこからの出力２６が再度図示されている。
【００３３】
図４は、テーブル２８と類似するリストを含むテーブル３４を図示するが、ここでは、図３の６ヴェインウィンドミル生成器の遅延要素１２の状態値も示している。右端列は、タップ２２によってタップされ、ライン２６上に生成された値を示す。図１と図３及びテーブル２８及び３４に示されたウィンドミル生成器１０のシーケンス出力を比較するとその共通性が分かる。
【００３４】
図１のウィンドミル生成器１０のそれぞれのヴェインｖは、同一の帰還接続を持っている。同様に、図３のウィンドミル生成器１０の各ヴェインｖも同一の帰還接続を含んでおり、これは、ウィンドミル多項式f(x)から導かれる。ウィンドミル多項式f(x)は、第一の多項式部分と第二の多項式部分に書き換えることができる。それは以下のようになる。
【００３５】
f(x)=1-f1x1-...-fL-1xL-1-xL  (fiは,GF(q)の要素である。)
=b(xv)-xL
多項式f(x)がこれにより再度特徴付けられる時、ヴェインｖにおけるフィードバックは、多項式b(x)によって特定される。
【００３６】
バイナリの場合、即ち、有限体がGF(2)で、f(x)が以下で表される場合は、
f(x)=1+f1x1...+fL-1xL-1+xL  ７次のウィンドミル多項式は、
f(x)=x7+x6+1  となる。
【００３７】
これにより図１及び図３に示されたウィンドミル生成器を実現し、ウィンドミル多項式は以下のように書き換えることができる。
f(x)=b(x3)+x7
ここで、b(x)=1+x2。F(x)はまた、他の方法によっても書き換えることができ、二つの独立多項式部により形成され、例えば、
f(x)=b(x6)+x7
ここで、b(x)=1+x and v=6
図１及び図３に示されたウィンドミル生成器の遅延要素１２のそれぞれの初期状態値の適切な選択を通じて、ウィンドミル生成器の独立構成により、生成器１０のそれぞれの構成のライン２６上の連続的なエンドタプルから形成される同一擬似乱数シーケンスの生成が可能となり得る。Ｌ次のウィンドミル多項式は、ウィンドミル生成器１０を許容し、ｖ１ヴェインまたはｖ２ヴェインを有し、上記等式（1=L mod v1=L mod v2, v-1=L mod v1=L mod v2）を満たす場合、初期状態値の簡単な写像は、同一の擬似乱数シーケンスを生成する異なる構成を許容する。
【００３８】
図５は、典型的な７次のウィンドミル多項式における写像を示す。上段は、初期状態値を図示するもので、図１のウィンドミル生成器１０のヴェイン２、ヴェイン１、ヴェイン０における文字a,b,c,d,e,f及びxで示されている。下段は、図３に示されたウィンドミル生成器１０のヴェイン５、ヴェイン４、ヴェイン３、ヴェイン２、ヴェイン１、ヴェイン０の６ヴェインｖに写像された初期状態値を図示するものである。図示された初期値の写像は、同一擬似ランダム出力シーケンスを生成するための図１及び図３それぞれのウィンドミル生成器１０の独立の構成を許容する。
【００３９】
v1-1=Ｌ mod v1,v2-1=L mod v2の時、互換値ｖの簡単な写像、異なる構成のウィンドミル生成器の形成は、以下の等式で決定される。ここでｐは、例えば、ｐ番目の遅延要素のように使用されるが、最大許容互換ｖ値に依存する数である。
【００４０】
p=(L+1-vmax)/v
ここで、vmaxは、あるウィンドミル多項式についてのｖの最大互換値である。
【００４１】
例えば、１７次のウィンドミル多項式ならば、ｆ(ｘ)=x17+x12+1、vmax=6 かつp=4となる。
【００４２】
図６は、上記二つの場合における出力エンドタプルを示す。図の左部において、各ヴェインにおける出力タップを形成するビットは、ｐで示される列から取られる。その一方で、図の右部は、vmaxの値により異なる列から取られた出力ビットを示す。
【００４３】
図７は、バイナリ３タプルのブロックを生成するために利用される１２７次までのウィンドミル多項式のテーブルを示す。各３タプルは６３nタプルまでの同一ウィンドミル多項式を導くことができるウィンドミル生成器によって生成されるような８値の整数番号を表す。図７のテーブルはさらに、同一擬似乱数シーケンスを生成できるウィンドミル生成器の異なる構成をもたらすヴェインｖの許容値を示す。
【００４４】
図８は、各ウィンドミル多項式についての許容ｖ値を生成する、一般に５２において示される方法を図示する。方法５２は、選択されたウィンドミル多項式について、共通の擬似乱数シーケンスを生成するウィンドミル多項式生成器の代替構成の互換性を決定することができる。第一に、ブロック５４に示されているように、選択されたウィンドミル多項式は、第一の多項式部分及び第二の多項式部分によって特徴付けられる。即ち、ウィンドミル多項式ｆ(ｘ)は、b(xv)-xLによって上述のように特徴付けられ、ｆ(ｘ)は原始的かどうかをチェックされる。そして、ブロック５６に示されるように、第二の多項式部分の特性は、第一の多項式部分と足し合わされると、任意のウィンドミル多項式を構成する。第二の多項式部分のそれぞれの特性は、ウィンドミル生成器の独立した構成と結びつく。すなわち、b(xv)の異なる値が選択される。
【００４５】
そして、ブロック５８に示されているように、b(xv)の特性のそれぞれが任意の基準を満たすかどうかが決定される。即ち、選択された基準は1=L mod v又は v-1=L mod vのいずれかを満たすことを要求する。
【００４６】
最後に、ブロック６２に示されているように、ウィンドミル生成器の特徴は、もし任意の基準をその特徴が満足するならば、互換性のある代替構成として識別される。
【００４７】
図９は、本発明の実施形態に基づくウィンドミル生成器（１００）を示す。ウィンドミル生成器１００は、図１及び図３に示されたウィンドミル生成器１０と機能的に等価であるが、ここではワード用メモリを使って実現されている。ここで、メモリーエレメント１０４のスタック１０２が形成されている。メモリーエレメント１０４のそれぞれは、任意のワード長を有し、スタック１０２はメモリーエレメント１０４の任意の数Ｍから構成される。
【００４８】
Ｍの値は、以下の式の一に従って決定される。
M=2+(l-1)/v
M=1+(L+1)/v
【００４９】
メモリーエレメント１０４のコンテンツは、イニシャライザ１０８、出力シーケンスセレクタ１０２、及び新規メモリーワードセレクタ１１４によって表されるアプリケーションを実行することができる処理部１０６の操作を通じて選択的に作用する。イニシャライザ１０８は、メモリーエレメントを初期状態値のメモリーワードに初期化することができる。出力シーケンスセレクタ１０２は、nタプル出力シーケンスを構成するための、任意のメモリーワードの読出しを行うことができる。新規メモリーワードセレクタは、生成器１００の動作中に任意の1以上のメモリーエレメント１０４に書込まれる新規メモリーワードの選択を行うことができる。
【００５０】
図１０は、本発明の実施形態の動作中におけるメモリーワードの写像を示すものである。メモリーエレメントがイニシャライザ１０８の動作により初期状態値で1度初期化されると、メモリーワードは図の１１８で示される矢印に従って反復的にシフトされる。出力シーケンス生成器１１２の動作を介して、メモリーワードの一つがメモリーエレメントから読出されエンドタプル出力を形成する。そして、メモリーエレメント１０４中の任意部分に格納されたメモリーワード部分の任意のコンビネーションで形成される、新規入力ワードは、新規メモリーワードセレクタ１１４の動作を介して利用可能なメモリーエレメント１０４へ挿入される。図に示されるように、メモリーエレメント１０４に格納されているメモリーワードの要素の内容は列方向に写像される。そして、新規入力ワードセレクタ１１４の動作を介して、新規メモリーワードが利用可能なメモリーエレメント１０４へ挿入される。メモリーワードの連続的なシフト、任意のnタプルの出力及び新規入力ワードの形成は、擬似乱数シーケンスの生成を可能とする。ウィンドミル生成器１００のワード志向により、もしより多くのnタプル出力が必要であれば、複数のメモリーエレメント１０４に格納された複数のメモリーワードの出力nタプルを生成器１００の動作の反復の間に出力することができる。
【００５１】
図１１は、図９、図１０に示されたメモリーエレメント１０４のスタック１０２を図示する。ここでは、新規メモリーワードセレクタが利用可能なメモリーエレメントに挿入される新規メモリーワードの値を形成する手法を示す。メモリーワードが1度出力され出力nタプルが形成されると、矢印１２８と１３２で示されるように、各ヴェインの最後のdエレメントの値が利用される。その後、矢印１３４でしめすように、行成分が巡回的に同一の場所で回転する。その後、矢印１３６で示すように、加算的フィードバックが行われる。そして、矢印１３８で示すように、形成されたワードがコラム方向に上へシフトされる。
【００５２】
図１２は、本発明の別の実施形態のウィンドミル生成器１００を示すものである。ここでは、メモリーエレメント１０４のスタック１０２が同様に形成され、メモリーエレメントには長さＭのメモリーワードが同様に格納されている。そして、同様に、処理部１０６は、イニシャライザ１０８、出力シーケンスセレクタ１１２及び新規メモリーワードセレクタ１１４で表されるアプリケーションを実行することができる。ここでは、生成器１００のそれぞれの動作の反復の間にメモリーワードの内容をシフトするのではなく、矢印１４８で表される新規入力ワードポインタが巡回的にスタック１０２を形成するＭワードの間を移動する。即ち、新規入力ワードの位置がメモリーワードの間で巡回的に再識別される。低消費電力が操作における重要な目的であるならば、ポインタ１４８の再配置で消費する電力は、スタック１０２全体を各メモリーワードがシフトするよりもより少なくなる。
【００５３】
図１３は、図１２に類似するウィンドミル生成器１００の実施形態を示すものである。しかし、ここでは唯一の周期的な更新ポインタ１４８が利用され、セットだけが、データが読出されるか又は格納されるべき、メモリにおけるワードの正確な位置にポイントをオフセットする。
【００５４】
本発明の様々な実施形態の動作により、任意のウィンドミル多項式のためのウィンドミル生成器の互換性のある構成が決定される。任意のメモリーワードを連続的な生成器の反復動作の間に単に連続的に読出すことにより擬似乱数シーケンスを簡単に生成するワード志向のウィンドミル生成器が実現される。
【００５５】
これまでの記載は、発明の実施のための最適な実施形態に関するもので、発明の範囲はこの記載に必ずしも限定されるべきではない。発明の範囲は、請求の範囲に基づき定義されるものである。
【図面の簡単な説明】
【図１】  ３タプル出力を生成可能な第一の構成におけるウィンドミル生成器のブロック図を示す。
【図２】  図１に示すウィンドミル生成器の遅延要素における値及び、ウィンドミル生成器の反復生成された３タプルの出力のテーブルリストを示す図である。
【図３】  ６タプルの出力を生成可能な第二の構成におけるウィンドミル生成器のブロック図を示す。
【図４】  図３に示すウィンドミル生成器の遅延要素における値及び、ウィンドミル生成器の反復生成された６タプルの出力のテーブルリストを示す図である。
【図５】  図１及び図３に示すウィンドミル生成器の構成のための初期状態値及び、両構成が同一の擬似乱数出力シーケンスを生成できるようにするためのその間の写像を示す。
【図６】  二つの手法において決められる出力エンドタップを示す図である。
【図７】  １２７次までのウィンドミル多項式及び、本名発明の実施形態の操作において計算される許容値ｖを示すテーブルを表す図である。
【図８】  図７における許容値を決定するためのステップを示す、フローチャートである。
【図９】  本発明の実施形態に基づくウインドミル生成器のブロック図である。
【図１０】  図９に示すウィンドミル生成器の操作におけるメモリーワードの写像を示す図である。
【図１１】  図９に示すウィンドミル生成器の操作における新規入力ワードの生成手法を示す図である。
【図１２】  本発明の別の実施形態に基づくウィンドミル生成器のブロック図である。
【図１３】  本発明の別の実施形態に基づくウィンドミル生成器のブロック図である。
【図１】
0004652568.tif 000002
【図２】
0004652568.tif 000003
【図３】
0004652568.tif 000004
【図４】
0004652568.tif 000005
【図５】
0004652568.tif 000006
【図６】
0004652568.tif 000007
【図７】
0004652568.tif 000008
【図８】
0004652568.tif 000009
【図９】
0004652568.tif 000010
【図１０】
0004652568.tif 000011
【図１１】
0004652568.tif 000012
【図１２】
0004652568.tif 000013
【図１３】
0004652568.tif 000014