(57)【特許請求の範囲】
【請求項１】
Ｎビット入力値を変換されたＮビット出力値に変換するシステムであって、
複数の線形帰還シフト・レジスタ（ＬＦＳＲ）（５０、５２、５４）であって、各々がその出力に前記ＬＦＳＲのどの他のものによっても発生されない全ての可能なＮビット値の副集合を周期的に発生し、前記複数のＬＦＳＲが共同して全ての可能なＮビット値の集合を周期的に発生する複数の線形帰還シフト・レジスタ（ＬＦＳＲ）（５０、５２、５４）と、
周期的に発生される前記Ｎビット出力値のどれが前記Ｎビット入力値と一致するか判定するために前記Ｎビット出力値の各々を前記Ｎビット入力値と比較する手段（５６、５８、６０）と、
前記変換されたＮビット出力値としてＬＦＳＲのＮビット出力値が前記Ｎビット入力値と一致すると判定されるＬＦＳＲ以外の前記ＬＦＳＲの１つの出力を選択する手段（６４）と、を含み、
前記ＬＦＳＲ（５０、５２、５４）が循環群として順序付けられて配置されるので、前記循環群内の前記ＬＦＳＲの１つのＮビット出力値が前記Ｎビット入力と一致すると判定されるとき、前記変換されたＮビット出力値として前記循環群内の次の順番のＬＦＳＲの出力が選択されるシステム。
【請求項２】
請求項１記載のシステムにおいて、前記循環群内の前記ＬＦＳＲ（５０、５２、５４）が等しいサイクル長を有するシステム。
【請求項３】
請求項１記載のシステムにおいて、前記循環群内の前記ＬＦＳＲ（５０、５２、５４）の少なくとも１つのＬＦＳＲについて、前記少なくとも１つのＬＦＳＲのＮビット出力値が前記Ｎビット入力値と一致すると判定されたサイクルに続くサイクルで前記変換されたＮビット出力として前記循環群内の次のＬＦＳＲの出力が選択されるシステム。
【請求項４】
請求項１記載のシステムにおいて、前記変換されたＮビット出力値が前記Ｎビット入力値の誤り訂正コーディング又は暗号化に使用されるシステム。
【請求項５】
Ｎビット入力値を変換されたＮビット出力値に変換するシステムであって、
各可能なＮビット入力値毎に、対応する前記Ｎビット出力値を記憶する記憶手段にして、全ての可能なＮビット入力値の集合を分割して、各々が少なくとも１つの可能なＮビット値を含む複数の相互排他的副集合であって、任意の１の副集合に含まれるＮビット値が他の副集合に含まれないように構成された複数の相互排他的副集合を予め記憶し、前記対応するＮビット出力値は、前記１つの可能なＮビット入力値が属する副集合以外の副集合からのどれか１つの可能なＮビット入力値に対応するＮビット出力値が選択される前記記憶手段と、
前記入力されたＮビット入力値から前記記憶手段へのアドレスを形成するアドレス指定手段にして、前記アドレスが前記入力されたＮビット入力値に対応するＮビット出力値を記憶する前記記憶手段内の場所に関連している前記アドレス指定手段と、
前記変換されたＮビット出力値として使用するために前記場所から前記対応するＮビット出力値を検索する手段と
を含むシステム。
【請求項６】
請求項５記載のシステムにおいて、前記記憶手段が読み取り専用メモリ（ＲＯＭ）であるシステム。
【請求項７】
請求項５記載のシステムにおいて、前記変換されたＮビット出力値が前記印加されたＮビット入力値の誤り訂正コーディング又は暗号化に使用されるシステム。
【請求項８】
Ｎビット入力値を変換されたＮビット出力値に変換する方法であって、
各々が少なくとも１つの可能なＮビット値を含む複数の相互排他的副集合として全ての可能なＮビット値の集合を与えるステップと、
前記Ｎビット入力値が前記副集合のどの１つに属するか判定するために前記Ｎビット入力値を前記副集合の各々と比較するステップと、
前記変換されたＮビット出力値として前記副集合の他の１つからのＮビット値を選択するステップとを含み、
前記副集合の各々が線形帰還シフト・レジスタ（ＬＦＳＲ）内で周期的に発生される方法。
【請求項９】
請求項８記載の方法において、前記副集合の少なくと或るいくつかが循環群として順序付けられて配置され、そうすることにより前記Ｎビット入力値が前記循環群内の前記副集合の１つに属すると判定されるとき、前記変換されたＮビット出力値として前記循環群内の次の順番の副集合からの出力値が選択される方法。
【請求項１０】
請求項８記載の方法において、前記変換されたＮビット出力値が前記Ｎビット入力値の誤り訂正コーディング又は暗号化に使用される方法。
【請求項１１】
Ｎビット入力値を変換されたＮビット出力値に変換する方法であって、
各々が少なくとも１つの可能なＮビット値を含む複数の相互排他的副集合として全ての可能なＮビット値の集合を与えるステップと、
前記Ｎビット入力値が前記副集合のどの１つに属するか判定するために前記Ｎビット入力値を前記副集合の各々と比較するステップと、
前記変換されたＮビット出力値として前記副集合の他の１つからのＮビット値を選択するステップとを含み、
前記副集合の各々がメモリに記憶される方法。
【発明の詳細な説明】
発明の背景
発明の分野
本発明は、ディジタル・データの伝送に使用される誤り訂正コーディング・システム及び／又は暗号化システムに関する。特に、本発明は、非線形、１：１マッピングを使用して入力値を出力値に変換することに関する。
関連先行技術システム
誤り訂正コーディング・システム及び暗号化システムは共に、ディジタル情報ビット・ストリーム又はデータ・ブロックを、伝送に先立ち、それぞれ、コード化ブロック又は暗号化ブロックに変換するディジタル論理回路を通常含み、これらのブロックでは各変換されたビットが原情報ビットのいくつかに依存する。誤り訂正コーディングに使用されるとき、このような回路は、原情報ビットの各々がいくつもの転送されたビットによって表されているから、たとえ伝送誤りが変換されたビットの１つ以上を崩壊させても、原情報ビットが有効に回復され得ることを保証する。暗号化に使用されるとき、このよう回路は、伝送されたデータ（すなわち、もし誤りコーディングが使用されないならば原情報、又はもし誤りコーディングが使用されるならば変換されたビット）を「マスクする」又は偽装する（ｄｉｓｇｕｉｓｉｎｇ）ことによってそれらのデータを意図しない受信から保護する。これは、典型的に、情報ビット又は変換されたビットを送信機又は意図した受信機によってのみ所有されるマスキング・ビットとビット単位で排他的ＯＲ演算する（ｂｉｔｗｉｓｅ  Ｅｘｃｌｕｓｉｖｅ  ＯＲｉｎｇ）ことによって遂行される。これらのマスキング・ビットは「キー」ビットとして普通知られる所定数のビットから通常発生され、キー・ビットは疑似ランダム・プロセスに適用され、このプロセスはマスキング・ビットとして使用するためにキー・ビットの種々の組み合わせを順序に発生する。
それゆえ、コーディング及び暗号化は共にマルチビット出力を発生する機構を必要とし、マルチビット出力ではそれらのビットの各々がマルチビット入力の関数であることが分る。入力ビットのこの「スクラブル（ｓｃｒａｍｂｌｉｎｇ）」を達成するために、先行技術は、線形帰還シフト・レジスタ、非線形帰還シフト・レジスタ、及びいわゆる「ワンタイム・パッド（ｏｎｅ−ｔｉｍｅ  ｐａｄ）」を含むルックアップ・テーブルを使用してきた。図１は先行技術線形帰還シフト・レジスタを示すのに対して、図２は非線形帰還シフト・レジスタを示す。図１で、線形帰還シフト・レジスタはＮ段シフト・レジスタ１０を含み、これの内容をＮ段各々にクロック・パルスを印加することによって右へ１位置だけシフトさせることができる。技術上周知のように、シフト・レジスタ１０内のＮ段は、各々、クロック入力、１ビット・データ入力、及び１ビット・データ出力を有するＤ形フロップ・フロップで以て実現することができる。便宜上及び簡単のために、これらのフリップ・フロップの各々の、個別クロック入力、分離１ビット入力／出力（入出力）を図１では全体的にて矢印によって示す。
図１から判るように、最左端（Ｎ−１）フリップ・フロップは、排他的ＯＲ（ＸＯＲ）ゲート２２、２４、及び２６を含む（破線ボックスによって示された）組み合わせ論理回路２０の出力を受け取り、これらのゲートはシフト・レジスタ１０内の選択されたフリップ・フロップの出力を組み合わせる。ＸＯＲゲート２６の現在出力は、各新クロック・パルスの印加の後にＮ−１フリップ・フロップへの次の入力となる。良く判るのは、組み合わせ論理回路２０はＸＯＲゲート２２、２４、及び２６から厳密に構成されていてこれらのゲートの各々は線形モジュロ２加算を遂行するから、図１のシフト・レシスタ１０内の最左端段の入力に帰還されるＸＯＲゲート２６からの出力ビットは、シフト・レジスタ１０の或る定まった選択された内容の線形組み合わせであることである。しかしながら、図２では、シフト・レジスタ１０への帰還入力ビットは、ＸＯＲゲート３２及び３８で構成された線形組み合わせ論理だけでなく、またＡＮＤゲート３４及びＯＲゲート３６及び４０で構成された非線形組み合わせ論理を含む（破線ボックス内に示された）組み合わせ論理回路３０によって形成される。それゆえ、図２のシフト・レジスタ１０内の最左端段の入力に帰還されるＯＲゲート４０の出力は、シフト・レジスタ１０の或る定まった内容の非線形組み合わせである。
図１の線形帰還シフト・レジスタ及び図２の非線形シフト・レジスタは共に、先ず入出力ポートを通してシフト・レジスタ１０内へ入力ビットをロードすることによって、次いで、定められた回数に相当する数のクロック・パルスをクロック・ポートに印加してレジスタの内容をこの回数だけシフトさせることによって、最後に入出力ポートからスクランブルされた内容を抽出することによって、いくつもの入力ビットの所望論理機能を形成するために使用することができる。したがって、抽出された出力の各ビットは、原入力ビットの所望論理機能の１つを表すことになる。しかしながら、線形帰還シフト・レジスタ及び非線形帰還シフト・レジスタの各々は、下に更に説明するように、それ特有の利点及び欠点を有する。
線形帰還シフト・レジスタの利点は、抽出された出力ビット・パターンが繰り返しを開始する前に印加することができるクロック・パルスの最大数を精確に予測する能力であって、これは非線形帰還シフト・レジスタにとっては常に可能であるとは限らない。技術上周知のように、Ｎ段（Ｎビット）線形帰還シフト・レジスタにとって最大サイクル長は、２N-1である。これは、特定開始状態（Ｎビット値）に対して、シフト・レジスタ１０がその初期状態に復帰する前に２N-1の状態（異なるＮビット値）を通してサイクルすることを意味する。一般に、線形帰還シフト・レジスタにとっての実際サイクル長は、入力ビットの数及び帰還ビットを発生するために使用された出力ビット（タップ）の位置の両方の関数であり、かつ、通常、最大サイクル長よりいくらか短い。他方、非線形帰還シフト・レジスタは「短サイクル」と呼ばれるかなり短いサイクル長をときどき示し、短サイクルは、それらが、例えば、マスキングの効果を次第に損なうので好ましくない。しかしながら、このような短サイクルは、例えば、図１に示された線形帰還シフト・レジスタを使用することによって、かつ（全零入力値は、その出力値が印加されたクロック・パルスの数にかかわらず全零であるので、全零入力は長さ１の短サイクルを生じるから、全零入力値は回避される旨の注意をもって）帰還ビットを形成するために使用されるタップを慎重に選択することによって、回避することができる。
線形帰還シフト・レジスタの他の利点は、それらが「１：１マッピング」変換又は「情報損失無し（ｉｎｆｏｒｍａｔｉｏｎ−ｌｏｓｓｌｅｓｓ）」変換として知られたことを遂行することである。用語「１：１マッピング」は、入力ビットの各可能パターン毎に、出力ビットの一意の（ｕｎｉｑｕｅ）対応するパターンがあることを意味する。それゆえ、変換を逆にしかつ入力ビットのどんなパターンが特定出力パターンを起こさせたか判定することが論理的に可能である。用語「情報損失無し」は、原入力情報を全面的に回復することができると云う理由から適用される。しかしながら、非線形帰還シフト・レジスタによって遂行されるマッピングは、必ずしも１：１でなく、しばしば多（ＭＡＮＹ）：１である。これは、いくつかの異なる入力ビット・パターンが同じ出力パターンに変換することがあることを意味する。このようなマッピング・プロセスは、はっきりとは可逆的でなく、このゆえに、出力状態の知識は、原入力状態を演繹し得ることを保証しない。換言すれば、このようなプロセスは、「情報損失性（ｉｎｆｏｒｍａｔｉｏｎ  ｌｏｓｓｙ）」であることがある。
他方、線形帰還シフト・レジスタの欠点は、このようなレジスタを使用して暗号化された情報を意図しない受信機が回復することができるについてのその比較的容易さである。受信機で検波された出力ビットの特定列が与えられるならば、この出力を発生したレジスタに関する内部構成（すなわち、どのタップが帰還ビットを形成するために使用されたか）を判定することが可能であり、かつ、それゆえ、レジスタ及び原入力情報を復元することが可能である。このような復元は、非線形帰還シフト・レジスタの場合はより困難であって、かつ不経済的な量の計算を必要とすると云ってよい。暗号化に非線形帰還シフト・レジスタを使用することに関連して強化された安全性と云う利点は、上に説明した他の文脈では、欠点（例えば、多：１マッピング）と考えられていたこれらのレジスタの同じ性質に由来する。逆に、暗号化文脈における線形帰還シフト・レジスタの低い安全性と云う欠点は、上に説明した他の文脈では、利点（例えば、１：１マッピング）であると考えられていたこれらのレジスタの同じ性質に由来する。明らかに、線形帰還シフト・レジスタ及び非線形帰還シフト・レジスタの両方の利点を組み合わせる一方、これらの付随する欠点を回避するのが好ましいことになる。
出力への入力の非線形マッピングであって、１：１であることをなお保証されるマッピングを施すことへの１つのアプローチは、いわゆる置換ボックス（Ｓボックス）又はルックアップ・テーブルを使用することである。入力ビットの数Ｎが小さい（例えば、４〜１６）のとき、２Nの可能な入力に対応する一意出力のテーブルをメモリに記憶することができる。それゆえ、４ビット入力に対しては、メモリは１６出力パターンを記憶することになるの一方、１６ビット入力に対しては、メモリは６５，５３６出力パターンを記憶しなければならないことになる。もちろん、メモリ寸法及びコストがＳボックスの使用に実用上の制限を課する。原理的に、Ｓボックスの内容は、所望１：１関係を保全するために、出力パターンを２度以上使用しない限り完全にランダムに選択することができる。
Ｓボックスの早い時機での実現は、「ワンタイム・パッド（ｏｎｅ−ｔｉｍｅ  ｐａｄｓ）」として知られた、入力パターンの本及び対応する出力パターンの本が送信通信者（ｔｒａｎｓｍｉｔｔｉｎｇ  ｃｏｒｒｅｓｐｏｎｄｅｎｔ）と受信通信者（ｒｅｃｅｉｖｉｎｇ  ｃｏｒｒｅｓｐｏｎｄｅｎｔ）に提供された手動暗号化システムに見られた。メッセージを暗号化する又は復号するためにその本中のパターンのページを使用して後、そのページを引きちぎりかつ破ることになっていた。しかしながら、人間の間違いがワンタイム・パッドの誤った使用をしばしば招きかつ意図した安全を守れない結果をもたらした。セルラ無線呼び出しの不正受信に対して保護するような最近の応用には、自動電子システムが必要である。このようなシステムは、本発明によって提供される。
発明の要約
本発明はＮビット入力値をＮビット出力値に変換するシステム及び方法を提供し、変換されたＮビット出力値をＮビット入力値の誤り訂正コーディング又は暗号化に使用することができる。
１態様では、本発明のシステムは複数の線形帰還シフト・レジスタ（ＬＦＳＲ）を含み、これらのシフト・レジスタの各々はその出力にこれらのＬＦＳＲのどの他のものによっても発生されない全ての可能なＮビット値の副集合（ｓｕｂｓｅｔ）を巡回的に発生し、これらのＬＦＳＲは共同して全ての可能なＮビット値の集合（ｓｅｔ）を巡回的に発生する。このシステムは、これらのＬＦＳＲによって巡回的に発生されるＮビット出力値のどれがＮビット入力値と一致するかを判定するためにこれらのＮビット出力値の各々をＮビット入力値と比較する手段、及び変換されたＮビット出力値としてＬＦＳＲのＮビット出力値がＮビット入力値と一致すると判定されるそのＬＳＦＲ以外のＬＦＳＲの１つの出力を選択する手段を更に含む。このシステムの１実施例では、ＬＦＳＲの少なくとも或るいくつかが循環（ｃｉｒｃｕｌａｒ）群に配置され、従って循環群内のＬＦＳＲの１つのＮビット出力値がＮビット入力と一致すると判定されるとき、変換されたＮビット出力値として循環群内の次のＬＦＳＲの出力が選択される。
他の態様では、本発明のシステムは、各々が少なくとも１つの可能なＮビット値を含む複数の相互排他的（ｍｕｔｕａｌｌｙ  ｅｘｃｌｕｓｉｖｅ）副集合として全ての可能なＮビット値の集合を与える手段、Ｎビット入力値がこれらの副集合のどの１つに属するか判定するためにＮビット入力値をこれらの副集合の各各と比較する手段、及び変換されたＮビット出力値として副集合の他の１つからのＮビット値を選択する手段を含む。このシステムの１実施例では、副集合の各各が線形帰還シフト・レジスタ（ＬＳＦＲ）内で巡回的に発生される。このシステムの他の実施例では、副集合の各々がメモリに記憶される。どちらの実施例でも、副集合の少なくとも或るいくつかが循環群に配置されるので、Ｎビット入力値が循環群内の副集合の１つに属すると判定されるとき、変換されたＮビット出力値として循環群内の次の副集合からの出力値が選択される。
なお他の態様では、本発明の方法は、各々が少なくとも１つの可能なＮビット値を含む複数の相互排他的副集合として全ての可能なＮビット値の集合を与えるステップ、Ｎビット入力値が副集合のどの１つに属するか判定するためにＮビット入力値を副集合の各々と比較するステップ、及び変換されたＮビット出力値として副集合の他の１つからのＮビット値を選択するステップを含む。この方法の１実施例では、副集合の各々は、線形帰還シフト・レジスタ（ＬＦＳＲ）内で巡回的に発生される。この方法の他の実施例では、副集合の各々がメモリに記憶される。どちらの実施例でも、副集合の少なくとも或るいくつかが循環群に配置されるので、Ｎビット入力値が循環群内の副集合の１つに属すると判定されるとき、変換されたＮビット出力値として循環群内の次の副集合からの出力値が選択される。
【図面の簡単な説明】
本発明は、次の添付図面を参照することによって、技術の熟練者にいっそう良く理解されかつその多数の目的及び利点が明らかになる。これらの図面のうちで、
図１は、Ｎビット入力値を変換されたＮビット出力値に変化するために使用されることがある先行技術線形帰還シフト・レジスタのブロック図である。
図２は、Ｎビット入力値を変換されたＮビット出力値に変化するためにまた使用されることがある先行技術非線形帰還シフト・レジスタのブロック図である。
図３は、本発明に従って構成されたＮビット変換回路のブロック図である。
詳細な説明
図３を参照すると、本発明の模範的実施例は、入力Ｃ0を有する第１のＬＦＳＲ（ＬＦＳＲ0）５０、入力Ｃ1を有する第２のＬＦＳＲ（ＬＦＳＲ1）５２、及び入力ＣM-1を有する第ＭのＬＦＳＲ（ＬＦＳＲM-1）５４のような台数ＭのＮビット線形帰還シフト・レジスタ（ＬＦＳＲ）を含む。ＬＦＳＲ５０、５２、及び５４は、各々が合計２Nの可能出力ビット・パターンの副集合を発生しこの副集合が他のＬＦＳＲによって発生された副集合と重なり合わないように選択される。換言すれば、各ＬＦＳＲ５０、５２、及び５４は、他のＬＦＳＲのどれによってもなんら発生されないＮビット出力の明確に区別される群を発生する。出力パターンの各副集合は定められた長さの短サイクルを表すとみなしてよい一方、副集合の組み合わせはＮビットＬＦＳＲにとっての最大サイクル長を表すと考えてよい。
全ての可能な出力パターンを考慮に入れる限りＬＦＳＲ５０、５２、及び５４のどれかによって発生された出力パターンの特定副集合を選択するに当たって大きな柔軟性度があることであることが理解されよう。例えば、もしＭ＝６かつＮ＝８ならば、ＬＦＳＲ0、ＬＦＳＲ1、ＬＦＳＲ2、及びＬＦＳＲ3を、初期出力に復帰しかつサイクルを繰り返す前にクロック・パルスの連続印加の際６０の異なる出力を発生するように選択することができる。同様に、ＬＦＳＲ4及びＬＦＳＲ5を、それぞれ、１２及び４の異なる出力を発生するように選択することができる。この例における全てのＬＦＳＲにとってのサイクル長の和は２５６であり、これは発生しなければならない可能な出力ビット・パターンの合計数２8に等しい。
図３の回路を初期化する際、各ＬＦＳＲ５０、５２、及び５４は、各ＬＦＳＲが発生できる出力ビット・パターンの副集合内にある指定開始状態Ｃ0からＣM-1までをロードされるが、それ以外の場合は、この状態が送信機及び受信機の両方に知られている限り任意であることができる（例えば、開始状態Ｃ0からＣMまでを相当する副集合内で定数に固定してもよい）。次いで、入力ビット・パターンがＬＦＳＲ５０、５２、及び５４の出力にそれぞれ接続されたＭ台の比較器５６、５８、及び６０の各々に印加される。開始状態Ｃ0からＣM-1までがＬＦＳＲ５０、５２、及び５４にロードされかつ入力が比較器５６、５８、及び６０に印加された後、クロック・パルス発生器６２がＬＦＳＲ５０、５２、及び５４の内容をシフトさせるために連続クロック・パルスを発生する。各クロック・サイクル中、比較器５６、５８、及び６０の各々は、入力ビット・パターンを、それぞれ、対応するＬＦＳＲ５０、５２、及び５４の出力と比較し、かつ入力パターンと出力パターンとが同じであるときセレクタ６４へ「一致（ｍａｔｃｈ）」信号を発生する。セレクタ６４は、立ち代わって、比較器５６、５８、及び６０のどれが一致信号を発生したかに依存する所定数のクロック・パルスの後クロック・パルス発生器６２へ「停止」信号を発生する。好適実施例では、クロック・パルスのこの数は、比較器５６、５８、及び６０の１つを除く全てに対しては零であり、かつ、例えば、最終比較器６０であるとすることができる残りの比較器に対しては１である。この例では、セレクタ６４は、比較器５６及び５８のどれかから一致信号を受け取ると直ちに停止信号を発生することになるが、しかし一致信号を比較器６０から受け取るときは停止信号を発生する前に１クロック・パルスだけ待機することになる。
停止信号を発生する際、セレクタ６４は、印加された入力に対応する変換された出力としてＬＦＳＲ５０、５２、及び５４の所定の１つの出力を選択する。次いで、次の入力値が印加され、かつクロック・パルス発生器６２が再始動される。新入力値の各印加毎に、その出力が変換された出力として選択されるべきＬＦＳＲは、比較器５６、５８、及び６０のどれが一致信号を発生したかに依存するが、しかし、もちろん比較器が一致信号を発生したＬＦＳＲは除外しなければならない（そうでなければ、選択された出力は印加された入力と単に等しいことになる）。出力はその比較器が一致信号を発生したＬＦＳＲ以外のＬＦＳＲから選択されるので、入力から出力へのマッピングを非線形にすることができる。本発明の１実施例では、もしＬＦＳＲLに対応する比較器が一致信号を発生するならば、出力はＬＦＳＲL+1から選択され、Ｌ＝Ｍ−１のとき出力はＬＦＳＲ0から選択される（すなわち、ＬはＬ＋１モジュロＭへ増分される）。しかしながら、この実施例は、もしＬＦＳＲLのサイクル長がＬＦＳＲL+1のサイクル長より実質的に長いならば好適ではない。例えば、もしＬＦＳＲLのサイクル長が２１７でありかつＬＦＳＲL+1のサイクル長が３１であるならば、２１７連続クロック・パルスの印加中ＬＦＳＲLは１回サイクルするのに対してＬＦＳＲL+1は７回サイクルする。それゆえ、７つの異なる入力値に対応するＬＦＳＲLの７つの異なる値があることになって、同じ出力値がＬＦＳＲL+1から選択される結果を生じ得る。これは、多：１（すなわち、７：１）マッピングを構成し、より望ましい情報損失無し（すなわち、１：１）マッピングではない。
しかしながら、もしその比較器が一致信号を発生したＬＦＳＲと同じサイクル長を有するＬＦＳＲから出力が常に選択されるならば、所望１：１マッピングを得ることができる。例えば、もしＭ＝６かつ６つのＬＦＳＲのサイクル長が、それぞれ、６０、６０、６０、６０、１２、及び４であるならば、ＬＦＳＲ0に対応する比較器からの一致信号はＬＦＳＲ1に対応する比較器からの現在出力を選択させることができ、ＬＦＳＲ1に対応する比較器からの一致信号はＬＦＳＲ2からの現在出力を選択させることができ、ＬＦＳＲ2に対応する比較器からの一致信号はＬＦＳＲ3からの現在出力を選択させることができ、及びＬＦＳＲ3に対応する比較器からの一致信号はＬＦＳＲ0からの出力を１余剰（ｅｘｔｒａ）クロック・パルス遅く選択させること（これは１だけ増分されたＬＦＳＲ0の現在出力を選択することと等価であることになる）ができる。この余剰クロック・パルスは、ＬＦＳＲ0からＬＦＳＲ3までのどれかよって発生された値の副集合内に入る所与の入力値の繰り返し印加が、その結果、同じ出力値をこのループ内の次のＬＦＳＲから繰り返し選択させるのではなく、結果の出力値を、事実、このループ内の次のＬＦＳＲによって発生される全て６０の値を通してサイクルさせることを保証するために使用される。それぞれ、１２及び４のサイクル長を有する残りのシフト・レジスタＬＦＳＲ4及びＬＦＳＲ5の各各にとっては、それと対になることができる等しいサイクル長を有する他のＬＦＳＲはなく、それゆえこれらのＬＦＳＲの各々はそれより短いサイクル長又は長いサイクル長のどちらかを有するＬＦＳＲと対にならなければならず、結果として、多：１又は１：多（情報損失性）マッピングをもたらす。これに代えて、これらのＬＦＳＲの各々をそれ自体上へ１余剰クロック・パルスだけシフトさせてマップさせることもでき、その結果、線形であるけれども、１：１マッピングを生じる。
最も好適なマッピングは、もちろん、非線形１：１マッピングである。一般に、これは、或る決まったサイクル長の各ＬＦＳＲ毎に、同じサイクル長の少なくとも１つの他のＬＦＳＲがあって、その出力を第１ＬＦＳＲによって一致信号が発生されてから１（又はもしかするとこれより多い）余剰クロック・パルス後に選択することができることを必要とする。しかしながら、判るのは、或るいくつかのＬＦＳＲが同じサイクル長を有しかつ他のものが有さない場合、同じサイクル長を有するＬＦＳＲの全てを循環群に配置することができ、この群内で１つのＬＦＳＲに対応する比較器によって発生された一致信号がこの群内の次のＬＦＳＲの出力の選択を起こさせること、ただし、例外としてこの群内の最終ＬＦＳＲに対応する比較器によって発生された一致信号は余剰クロック・パルスの発生後この群内の第１のＬＦＳＲからの出力の選択を起こさせることである。満たすべき他の規準（ｃｒｉｔｅｒｉａ）は、ＬＦＳＲの全てのサイクル長の合計が２Nに等しく、ここにＮは入力ビットの数であることだけである。
実際には、Ｎの所与の値に対する前掲の規準を満たすことができるＬＦＳＲのいくつかの異なる構成がある。例えば、もしＮ＝８（２N＝２５６）ならば、２つの循環群に配置された４つのＬＦＳＲを使用することが可能であり、第１群は各々が１２４のサイクル長を有する２つのＬＦＳＲで構成され、かつ第２群は各各が４のサイクル長を有する２つのＬＦＳＲで構成される。これに代えて、各々が８５のサイクル長を有する３つのＬＦＳＲ、及び各々が１のサイクル長を有する第４のＬＦＳＲ（この場合、第４のＬＦＳＲに対応する１つの入力値は単にそれ自身に変換することができる）の循環群を使用することが可能である。２つの循環群に配置された８つのＬＦＳＲを使用することもまた可能であり、第１群は各々５６のサイクル長を有する４つのＬＦＳＲで構成され、かつ第２群は各々８のサイクル長を有する４つのＬＦＳＲで構成される。もちろん、これらの例は、Ｎ＝８の場合に技術の熟練者に明らかである可能な構成を尽くしていない。同様に、Ｎ＞８の場合、上掲の規準を満たすいっそう多くのサイクル長組み合わせが存在することを見付けることができる。
図３に示された、本発明によって提供された変換機能は、ＬＦＳＲ及び関連比較器以外の構成要素を使用することによっても実現できることは、当業者に理解されることである。例えば、Ｎビット入力値に対して、可能なＮビット値の全ての集合を複数の副集合の形で読取り専用メモリ（ＲＯＭ）に記憶してよく、これらの副集合の各々は図３のＬＦＳＲ５０、５２、及び５４の相当する１によって発生されたＮビット出力値に等価な値を含むと考えてよい。入力ビット値がどの記憶された副集合に属するか判定するために入力値がＲＯＭの内容と比較される。次いで、出力値を、上に説明した図３の回路の動作と等価な方法で、他の副集合から選択することができる。代替実施例では、本発明に従って構成されたＲＯＭは、各可能Ｎビット入力値毎に図３の変換機能を使用して事前計算（ｐｒｅｃｏｍｐｕｔｅ）されてある一意Ｎビット出力値を記憶する。特定Ｎビット入力値が印加されるとき、その値が対応するＮビット出力値を読み出す（検索する）ようにＲＯＭへのアドレスを形成するために使用され、次いで、この出力値を所望変換値として使用することができる。
一般に、技術の熟練に容易に認められるように、本発明の範囲に実質的に反することなく、ここに開示されている本発明の実施例に多くの修正及び変更を施すことができる。したがって、ここに開示された本発明の形は、模範的であるのであって、次の請求の範囲によって明確にされた本発明の範囲への制限として意図されているのではない。
【図１】
0004094671.tif 000002
【図２】
0004094671.tif 000003
【図３】
0004094671.tif 000004