(57)【特許請求の範囲】
【請求項１】
線形帰還シフト・レジスタ（ＬＦＳＲ）を統合する方法であって：
当初の線形有限状態マシーン回路を取得するステップであって、前記回路が、複数のメモリ素子と線形論理ゲートとを有し、出力シーケンスを生成することが可能であるところのステップ；
前記当初の回路におけるフィードバック接続を決定するステップであって、前記フィードバック接続が、複数のメモリ素子にわたって張られており、関連するフィードバック接続線によって接続された起点タップと宛先タップとを有するところのステップ；および
複数のメモリ素子にわたって前記フィードバック接続の前記起点および宛先タップを同一方向にシフトさせるステップ；
より成り、前記当初の回路を、前記当初の回路と同一の出力シーケンスを提供することが可能な修正された線形有限状態マシーン回路に変換することを特徴とする方法。
【請求項２】
請求項１記載の方法において、前記フィードバック接続の前記起点タップおよび前記宛先タップが、同数のメモリ素子にわたってシフトされることを特徴とする方法。
【請求項３】
請求項１記載の方法において、フィードバック接続の前記タップが、前記関連するフィードバック接続線の長さを減少させることを特徴とする方法。
【請求項４】
請求項１記載の方法において、フィードバック接続の前記タップが、前記当初の回路における線形論理ゲートのレベルを減少させることを特徴とする方法。
【請求項５】
請求項１記載の方法において、フィードバック接続の前記タップが、前記当初の回路の内部ファン・アウト数を減少させることを特徴とする方法。
【請求項６】
請求項１記載の方法において、前記当初の回路が、最大長出力シーケンスを生成する最大長線形帰還シフト・レジスタであり、前記修正された回路が、前記当初の回路と同一の最大長シーケンスを提供することが可能であることを特徴とする方法。
【請求項７】
請求項１記載の方法において、当該方法がコンピュータ内で実行されることを特徴とする方法。
【請求項８】
請求項１記載の方法において、前記当初の線形有限状態マシーン回路が、線形帰還シフト・レジスタ回路であることを特徴とする方法。
【請求項９】
請求項８記載の方法において、前記線形帰還シフト・レジスタ回路が、タイプＩまたはタイプＩＩのＬＦＳＲであることを特徴とする方法。
【請求項１０】
請求項１記載の方法において、前記線形有限状態マシーンが、セルラ・オートマトンであることを特徴とする方法。
【請求項１１】
請求項１記載の方法において、前記フィードバック接続のタップが複数のメモリ素子にわたって左にシフトされる場合に、フィードバック接続の外にシフトされるメモリ素子に、同一の論理値を有する初期値を提供することを特徴とする方法。
【請求項１２】
請求項１１記載の方法において、前記当初の回路の前記線形論理ゲートがＸＯＲであるならば前記同一の論理値がゼロであり、前記線形論理ゲートがＸＮＯＲであるならば１であることを特徴とする方法。
【請求項１３】
請求項１記載の方法において、前記フィードバック接続のタップが複数のメモリ素子にわたって右にシフトされる場合に、フィードバック接続の内にシフトされるメモリ素子に、同一の論理値を有する初期値を提供することを特徴とする方法。
【請求項１４】
請求項１３記載の方法において、前記当初の回路の前記線形論理ゲートがＸＯＲであるならば前記同一の論理値がゼロであり、前記線形論理ゲートがＸＮＯＲであるならば１であることを特徴とする方法。
【請求項１５】
請求項１記載の方法において、前記当初の回路が、宛先タップに宛先線形論理ゲートを各々が有する第１および第２フィードバック接続を有し、当該方法が、前記第２フィードバック接続の前記起点および宛先タップを左にシフトさせる場合において、前記第２フィードバック接続の起点タップが前記第１フィードバック接続の前記宛先線形論理ゲートを越えるならば、前記第１フィードバック接続の起点タップと、前記第２フィードバック接続のシフトされた宛先タップにおける宛先線形論理ゲートとの間にフィードバック接続線を追加するステップより成ることを特徴とする方法。
【請求項１６】
請求項１記載の方法において、前記当初の回路が、宛先タップに宛先線形論理ゲートを各々が有する第１および第２フィードバック接続を有し、当該方法が、前記第２フィードバック接続の前記起点および宛先タップを右にシフトさせる場合において、前記第２フィードバック接続の起点タップが前記第１フィードバック接続の前記宛先線形論理ゲートを越えるならば、前記第１フィードバック接続の起点タップと、前記第２フィードバック接続の初期の宛先タップにおける宛先線形論理ゲートとの間にフィードバック接続線を追加するステップより成ることを特徴とする方法。
【請求項１７】
請求項１記載の方法において、前記当初の回路が、宛先タップに宛先線形論理ゲートを各々が有する第１および第２フィードバック接続を有し、当該方法が、前記第１フィードバック接続の前記起点および宛先タップを左にシフトさせる場合において、前記第１フィードバック接続の宛先タップが前記第２フィードバック接続の前記起点タップを越えるならば、前記第１フィードバック接続の当初の起点タップと、前記第２フィードバック接続の宛先タップにおける宛先線形論理ゲートとの間にフィードバック接続線を追加するステップより成ることを特徴とする方法。
【請求項１８】
請求項１記載の方法において、前記当初の回路が、宛先タップに宛先線形論理ゲートを各々が有する第１および第２フィードバック接続を有し、当該方法が、前記第１フィードバック接続の前記起点および宛先タップを右にシフトさせる場合において、前記第１フィードバック接続の宛先タップが前記第２フィードバック接続の前記起点タップを越えるならば、前記第１フィードバック接続の起点タップと、前記第２フィードバック接続の宛先タップにおける宛先線形論理ゲートとの間にフィードバック接続線を追加するステップより成ることを特徴とする方法。
【請求項１９】
当初の線形有限状態マシーン回路を取得するステップであって、前記回路が、複数のメモリ素子と線形論理ゲートとを有し、出力シーケンスを生成することが可能であるところのステップ；
前記当初の回路におけるフィードバック接続を決定するステップであって、前記フィードバック接続が、複数のメモリ素子にわたって張られており、関連するフィードバック接続線によって接続された起点タップと宛先タップとを有するところのステップ；および
複数のメモリ素子にわたって前記フィードバック接続の前記起点および宛先タップを同一方向にシフトさせるステップ；
を実行させ、前記当初の回路を、前記当初の回路と同一の出力シーケンスを提供することが可能な修正された線形有限状態マシーン回路に変換するコンピュータ読み取り可能な命令を格納するコンピュータ読み取り可能な媒体。
【請求項２０】
線形有限状態マシーンを統合する方法であって：
当初の線形有限状態マシーン回路を取得するステップであって、前記回路が、複数のメモリ素子と線形論理ゲートとを有し、出力シーケンスを生成することが可能であるところのステップ；
前記当初の回路におけるフィードバック接続を決定するステップであって、前記フィードバック接続は、複数のメモリ素子にわたって張られており、起点タップと、宛先線形論理ゲートを各々が有する複数の宛先タップとを含み、前記タップは関連するフィードバック接続線により結合されるところのステップ；および
前記起点タップを少なくとも２つの起点タップに分割し；および前記起点タップの１つと前記宛先タップの１つを複数のメモリ素子にわたってシフトさせることによって、フィードバック接続を対応する別個のフィードバック接続に分割するステップ；
より成り、前記当初の回路より少ない内部ファン・アウトを有するが、前記当初の回路と同一の出力シーケンスを提供することが可能な修正された線形有限状態マシーンに、前記当初の回路を変換することを特徴とする方法。
【請求項２１】
請求項２０記載の方法において、前記フィードバック接続の前記起点タップおよび宛先タップが、メモリ素子にわたって同一方向にシフトされることを特徴とする方法。
【請求項２２】
請求項２０記載の方法において、前記フィードバック接続の前記起点タップおよび宛先タップが、同数のメモリ素子にわたってシフトされることを特徴とする方法。
【請求項２３】
線形有限状態マシーンを統合する方法であって：
当初の線形有限状態マシーン回路を取得するステップであって、前記回路が、複数のメモリ素子と線形論理ゲートとを有し、出力シーケンスを生成することが可能であるところのステップ；
前記当初の回路における少なくとも第１および第２フィードバック接続を決定するステップであって、各フィードバック接続が、複数のメモリ素子にわたって張られており、関連するフィードバック接続線により接続された起点タップおよび宛先タップを含み、前記宛先タップが宛先線形論理ゲートを含むところのステップ；
前記第２フィードバック接続の起点および宛先タップを左にシフトさせるステップであって、前記第２フィードバック接続の前記起点タップが前記第１フィードバック接続の前記宛先線形論理ゲートを越えるところのステップ；および
前記第１フィードバック接続の前記起点タップと、前記第２フィードバック接続のシフトされた宛先タップにおける宛先線形論理ゲートとの間にフィードバック接続線を付加するステップ；
より成り、前記当初の回路を、前記当初の回路と同一の出力シーケンスを提供することが可能な修正された線形有限状態マシーン回路に変換することを特徴とする方法。
【請求項２４】
線形有限状態マシーンを統合する方法であって：
当初の線形有限状態マシーン回路を取得するステップであって、前記回路が、複数のメモリ素子と線形論理ゲートとを有し、出力シーケンスを生成することが可能であるところのステップ；
前記当初の回路における少なくとも第１および第２フィードバック接続を決定するステップであって、各フィードバック接続が、複数のメモリ素子にわたって張られており、関連するフィードバック接続線により接続された起点タップおよび宛先タップを含み、前記宛先タップが宛先線形論理ゲートを含むところのステップ；
前記第２フィードバック接続の起点および宛先タップを右にシフトさせるステップであって、前記第２フィードバック接続の前記起点タップが前記第１フィードバック接続の前記宛先線形論理ゲートを越えるところのステップ；および
前記第１フィードバック接続の前記起点タップと、前記第２フィードバック接続の当初の宛先タップにおける宛先線形論理ゲートとの間にフィードバック接続線を付加するステップ；
より成り、前記当初の回路を、前記当初の回路と同一の出力シーケンスを提供することが可能な修正された線形有限状態マシーン回路に変換することを特徴とする方法。
【請求項２５】
線形有限状態マシーンを統合する方法であって：
当初の線形有限状態マシーン回路を取得するステップであって、前記回路が、複数のメモリ素子と線形論理ゲートとを有し、出力シーケンスを生成することが可能であるところのステップ；
前記当初の回路における少なくとも第１および第２フィードバック接続を決定するステップであって、各フィードバック接続が、複数のメモリ素子にわたって張られており、関連するフィードバック接続線により接続された起点タップおよび宛先タップを含み、前記宛先タップが宛先線形論理ゲートを含むところのステップ；
前記第１フィードバック接続の起点および宛先タップを左にシフトさせるステップであって、前記第１フィードバック接続の前記宛先タップが前記第２フィードバック接続の起点タップを越えるところのステップ；および
前記第１フィードバック接続の当初の起点タップと、前記第２フィードバック接続の宛先タップにおける宛先線形論理ゲートとの間にフィードバック接続線を付加するステップ；
より成り、前記当初の回路を、前記当初の回路と同一の出力シーケンスを提供することが可能な修正された線形有限状態マシーン回路に変換することを特徴とする方法。
【請求項２６】
線形有限状態マシーンを統合する方法であって：
当初の線形有限状態マシーン回路を取得するステップであって、前記回路が、複数のメモリ素子と線形論理ゲートとを有し、出力シーケンスを生成することが可能であるところのステップ；
前記当初の回路における少なくとも第１および第２フィードバック接続を決定するステップであって、各フィードバック接続が、複数のメモリ素子にわたって張られており、関連するフィードバック接続線により接続された起点タップおよび宛先タップを含み、前記宛先タップが宛先線形論理ゲートを含むところのステップ；
前記第１フィードバック接続の起点および宛先タップをシフトさせるステップであって、前記第１フィードバック接続の前記宛先タップが前記第２フィードバック接続の起点タップを越えるところのステップ；および
前記第１フィードバック接続のシフトされた起点タップと、前記第２フィードバック接続の宛先タップにおける宛先線形論理ゲートとの間にフィードバック接続線を付加するステップ；
より成り、前記当初の回路を、前記当初の回路と同一の出力シーケンスを提供することが可能な修正された線形有限状態マシーン回路に変換することを特徴とする方法。
【請求項２７】
線形有限状態マシーンを統合する方法であって：
当初の線形有限状態マシーン回路を取得するステップであって、前記回路が、複数のメモリ素子と線形論理ゲートとを有し、出力シーケンスを生成することが可能であるところのステップ；
前記当初の回路における少なくとも第１および第２フィードバック接続を決定するステップであって、各フィードバック接続が、複数のメモリ素子にわたって張られており、関連するフィードバック接続線により接続された起点タップおよび宛先タップを含み、前記宛先タップが宛先線形論理ゲートを含むところのステップ；
前記第１フィードバックの前記宛先タップと前記第２フィードバック接続の前記起点タップが交差するように、前記第２フィードバック接続の起点および宛先タップをシフトさせるステップ；および
前記第１フィードバック接続の前記起点タップと、前記第２フィードバック接続の宛先タップにおける宛先線形論理ゲートとの間にフィードバック接続線を付加するステップ；
より成り、前記当初の回路を、前記当初の回路と同一の出力シーケンスを提供することが可能な修正された線形有限状態マシーン回路に変換することを特徴とする方法。
【請求項２８】
請求項２７記載の方法において、フィードバック接続の前記起点タップおよび宛先タップが、メモリ素子にわたって同一方向にシフトされることを特徴とする方法。
【請求項２９】
請求項２７記載の方法において、フィードバック接続の前記起点タップおよび宛先タップが、同数のメモリ素子にわたってシフトされことを特徴とする方法。
【請求項３０】
請求項２７記載の方法において、フィードバック接続線が付加される第１フィードバック接続の起点タップが、当初の起点タップまたはシフトされた起点タップを含むことを特徴とする方法。
【請求項３１】
請求項２７記載の方法において、フィードバック接続線が付加される第２フィードバック接続の宛先タップが、当初の宛先タップまたはシフトされた宛先タップを含むことを特徴とする方法。
【請求項３２】
線形有限状態マシーンを統合する装置であって：
当初の線形有限状態マシーン回路を取得する手段であって、前記回路が、複数のメモリ素子と線形論理ゲートとを有し、出力シーケンスを生成することが可能であるところの手段；
前記当初の回路におけるフィードバック接続を決定する手段であって、前記フィードバック接続が、複数のメモリ素子にわたって張られており、関連するフィードバック接続線によって接続された起点タップと宛先タップとを有するところの手段；および
複数のメモリ素子にわたって前記フィードバック接続の前記起点および宛先タップを同一方向にシフトさせる手段；
より成り、前記当初の回路を、前記当初の回路と同一の出力シーケンスを提供することが可能な修正された線形有限状態マシーン回路に変換することを特徴とする装置。
【請求項３３】
線形有限状態マシーンを統合する装置であって：
当初の線形有限状態マシーン回路を取得する手段であって、前記回路が、複数のメモリ素子と線形論理ゲートとを有し、出力シーケンスを生成することが可能であるところの手段；
前記当初の回路における少なくとも第１および第２フィードバック接続を決定する手段であって、各フィードバック接続が、複数のメモリ素子にわたって張られており、関連するフィードバック接続線によって接続された起点タップと宛先タップとを有し、前記宛先タップが宛先線形論理ゲートを含むところの手段；および
前記第１フィードバックの宛先タップおよび前記第２フィードバックの前記起点タップが交差するように、互いに対して前記フィードバック接続の前記起点および宛先タップをシフトさせる手段；および
前記第１フィードバック接続の起点タップおよび前記第２フィードバック接続の宛先タップにおける宛先線形論理ゲートの間に、フィードバック接続線を付加する手段；
より成り、前記当初の回路を、前記当初の回路と同一の出力シーケンスを提供することが可能な修正された線形有限状態マシーン回路に変換することを特徴とする装置。
【請求項３４】
線形有限状態マシーンを統合する方法であって：
当初の線形有限状態マシーン回路を取得するステップであって、前記回路が、複数のメモリ素子と線形論理ゲートとを有し、出力シーケンスを生成することが可能であるところのステップ；
前記当初の回路におけるフィードバック接続を決定するステップであって、前記フィードバック接続が、複数のメモリ素子にわたって張られており、関連するフィードバック接続線によって接続された起点タップと宛先タップとを有するところのステップ；および
複数のメモリ素子にわたって前記フィードバック接続の前記起点および宛先タップを同一方向にシフトさせるステップ；
より成り、前記当初の回路を、前記当初の回路と同一の出力シーケンスを提供することが可能な修正された線形有限状態マシーン回路に変換することを特徴とする方法。
【請求項３５】
線形有限状態マシーンを統合する方法であって：
当初の線形有限状態マシーン回路を取得するステップであって、前記回路が、複数のメモリ素子と線形論理ゲートとを有するところのステップ；
前記当初の回路における少なくとも第１および第２フィードバック接続を決定するステップであって、各フィードバック接続が、複数のメモリ素子にわたって張られており、関連するフィードバック接続線によって接続された起点タップと宛先タップとを有し、前記宛先タップが宛先線形論理ゲートを含むところのステップ；および
前記第１フィードバックの宛先タップおよび前記第２フィードバックの前記起点タップが交差するように、互いに対して前記フィードバック接続の前記起点および宛先タップをシフトさせるステップ；および
前記第１フィードバック接続の起点タップおよび前記第２フィードバック接続の宛先タップにおける宛先線形論理ゲートの間に、フィードバック接続線を付加するステップ；
より成り、前記当初の回路を、前記当初の回路と同一の出力シーケンスを提供することが可能な修正された線形有限状態マシーン回路に変換することを特徴とする方法。
【発明の詳細な説明】
【０００１】
［技術分野］
本発明は一般に線形有限状態マシーンに関し、特にそのようなマシーンの統合化に関する。
【０００２】
［背景］
線形帰還シフト・レジスタ（ＬＦＳＲ： ｌｉｎｅａｒ ｆｅｅｄｂａｃｋ ｓｈｉｆｔ ｒｅｇｉｓｔｅｒ）およびセルラ・オートマトン（ＣＡ： ｃｅｌｌｕｌａｒ ａｕｔｏｍａｔａ）のような線形有限状態マシーン（ＬＦＳＭ： ｌｉｎｅａｒ ｆｉｎｉｔｅ ｓｔａｔｅ ｍａｃｈｉｎｅｓ）は、擬似ランダム・シーケンスを生成するためにしばしば使用される。そのような装置は当該技術分野で良く知られており、Ｖ．Ｎ． Ｙａｒｍｏｌｉｋ ａｎｄ Ｓ．Ｎ．Ｄｅｍｉｄｅｎｋｏ， Ｇｅｎｅｒａｔｉｏｎ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎ ｏｆ Ｐｓｅｕｄｏｒａｎｄｏｍ Ｓｅｑｕｅｎｃｅｓ ｆｏｒ Ｒａｄｏｍ Ｔｓｔｉｎｇ， Ｊ．Ｗｉｌｅｙ ａｎｄ Ｓｏｎｓ， Ｎｅｗ Ｙｏｒｋ， １９８８．のような多数の参考文献に広く記載されている。ＬＦＳＲは、フリップ・フロップのようなメモリ素子、および図１に示されるように結合されたＸＯＲ又はＸＮＯＲゲートのような線形論理ゲートを含む。長さｎのＬＦＳＲは、特性多項式ｈｎｘｎ＋ｈｎ−１ｘｎ−１＋…＋ｈ０により数学的に表現され、ここでｈｉｘｉ項は、レジスタのｉ番目のフリップ・フロップを表わし、ｈｉ＝１ならば、そのフリップ・フロップから取り出されるフィードバック・タップが存在する。また、ｈ０＝１である。所与の多項式に従って適切なタップ接続が形成される場合には、各段の結合された（モジュロ２で加算された）出力は、ＬＦＳＲの第１段にフィードバックされる。このような実現化はタイプＩのＬＦＳＲまたはフィボナッチ（Ｆｉｂｏｎａｃｃｉ）生成器と呼ばれる。ＬＦＲＳの動作を開始させるため、ゼロでないｎビット・ベクトル（しばしば、シード（ｓｅｅｄ）と呼ばれる）がレジスタにロードされ、適切なレートでクロックが与えられる。上述のように初期化されたＬＦＳＲは、初期状態に戻ってくるまでに、多数の状態を通じて巡回する。ｎビットＬＦＳＲが可能な総ての２ｎ−１のゼロでない状態を巡回し得るならば、その特性多項式は、基本特性多項式（ｐｒｉｍｉｔｉｖｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃ ｐｏｌｙｎｏｍｉａｌ）と呼ばれる。そのようなＬＦＳＲは、しばしば最大長ＬＦＳＲと呼ばれ、その結果生じる出力シーケンスは、最大長シーケンスまたはｍ−シーケンスと呼ばれる。Ｍ−シーケンスは、Ｐ．Ｈ．Ｂａｒｄｅｌｌ， Ｗ．Ｈ．ＭｃＡｎｎｅｙ， ａｎｄ Ｊ．Ｓａｖｉｒ， Ｂｕｉｌｔ−Ｉｎ Ｔｅｓｔ ｆｏｒ ＶＬＳＩ： Ｐｓｅｕｄｏｒａｎｄｏｍ Ｔｅｃｈｎｉｑｕｉｅｓ， Ｊｏｈｎ Ｗｉｌｅｙ ＆ Ｓｏｎｓ， １９８７．に述べられているような多数の固有の性質を有する。
【０００３】
代替的なＬＦＳＲ実現化は図２に示されている。これはタイプＩＩＬＦＳＲ又はガロア真法（Ｇａｌｏｉｓ ｔｒｕｅ ｄｉｖｉｓｏｒ）と呼ばれる。この実現化の明確な特徴は、ＬＦＳＲの最終段の出力が、使用される特性多項式で示される先行する段にフィードバックされることである。タイプＩのＬＦＳＲと同様に、基本特性多項式に従って構築され、ゼロでないｎビット・ベクトルがロードされたタイプＩＩのＬＦＳＲは、２ｎ−１のゼロでない状態を生成する。
【０００４】
同一の基本特性多項式に従って構築されたタイプＩ又はタイプＩＩのＬＦＳＲの最終段から出力が取り出される場合に、生じるｍ−シーケンスは異なる。しかしながら、同一のｍ−シーケンスが取得され得るのは、所与の基本特性多項式およびその逆数（ｒｅｃｉｐｒｏｃａｌ）を利用して、タイプＩおよびタイプＩＩのＬＦＳＲをそれぞれ実現化し、両レジスタが適切に初期化される場合である。
【０００５】
上述したＬＦＳＲのようなＬＦＳＭは、誤り検出および訂正、データ伝送、移動電話、暗号、大規模集積回路の検査、データ圧縮およびハードウエア・ホワイト・ノイズ生成を含む非常に広範な用途に使用される。ハイ・パフォーマンス用途に対して、要求されるデータ生成および圧縮は、ハイ・パフォーマンス回路によってのみ達成され得る。従来のＬＦＳＲに基づく生成器、エンコーダ、デコーダまたはコンパクタ（ｃｏｍｐａｃｔｏｒ）の最高動作速度は、それら各自の要素の実行性によって制限される。タイプＩのＬＦＳＲに対しては、実行性は、フィードバック経路における組み合わせ論理の深さ（すなわち、レベル数）によって制限される。タイプＩＩのＬＦＳＲに対しては、実行性は、最終段の出力における内部ファン・アウト（ｆａｎ−ｏｕｔ）に対する補償に必要なフィードバック経路内のバッファによって制限される。さらに、バッファは回路の動作を遅くする。ＬＦＳＲの両タイプにおいて、多くの項数を有する特性多項式のＬＦＳＲに対して、そのような制限が特に顕著である。
【０００６】
従来のＬＦＳＲの実行性を改善する試みがなされている。そのいくつかは、Ｐ．Ｈ． Ｂａｒｄｅｌｌ， “Ｄｅｓｉｇｎ Ｃｏｎｓｉｄｅｒａｔｉｏｎｓ ｆｏｒ Ｐａｒａｌｌｅｌ Ｐｓｅｕｄｏｒａｎｄｏｍ Ｐａｔｔｅｒｎ Ｇｅｎｅｒａｔｉｏｎｓ，” Ｊｏｕｒｎａｌ ｏｆ Ｅｌｅｃｔｒｏｎｉｃ Ｔｅｓｔｉｎｇ： Ｔｈｅｏｒｙ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ， Ｎｏ． １， ｐｐ． ７３−８７， １９９０．に述べられている。他に様々な米国特許に述べられている。例えば、外部回路により強化されたＬＦＳＲを利用して、総ての２ｎのベクトルを生成することを意図する線形擬似ランダム・テスト・パターン生成器は、米国特許第４，９７４，１８４号に開示されている。この手法は、生成用のレジスタのフィードバック・ネットワークに付加された切り替え回路を利用して、「スタック状態（ｓｔｕｃｋ ｓｔａｔｅ）」と呼ばれる適切な位置に挿入し、これは従来の線形有限状態マシーンでは得られなかったものである。一般に、スタック状態は総て０のパターンより成り、いくつかの検査手法（例えば、メモリ・テスト）で有利に使用され得る。
【０００７】
米国特許５，２６８，９４９は、従来のＬＦＳＲより高い動作速度を有する擬似ランダム・テスト・パターン生成器を述べている。ＬＦＳＲの速度は、生成器を構成する各要素の実行性によって決定される。特に、ＬＦＳＲが多数のフィードバック・タップを特徴とするならば、ＸＯＲフィードバック・ネットワークは顕著な遅延を導入し得る。この特許は、並列に結合され低いクロックで動作する複数のＬＦＳＲの利用を提案し、実際の出力信号をマルチプレクスで生成するものである。しかしながら、このアーキテクチャは典型的なＬＦＳＲより多くのオーバーヘッド領域を有し、その実行性は出力機能におけるマルチプレクサによって制限される。
【０００８】
米国特許第５，４１２，６６５号は、他の並列動作の高速テスト・パターン生成器、および低速要素を利用して実現されるテスト応答簡素化（ｃｏｍｐａｃｔｉｏｎ）を開示する。これは、多数のフリップ・フロップおよび接続された組み合わせ論理ネットワークを使用する。各ネットワークは、並列出力である擬似ランダム・パターンを提供し、回路領域の増加と共に、高速データ・フローを形成する。
【０００９】
米国特許第５，４６６，６８３号は、プログラム可能なＬＦＳＲを開示し、可変な特性多項式を有する擬似ランダム・パターンを生成する。このシーケンス生成器は、特性多項式の対応する項が１の係数を有する場合には、制御信号が１の値を有するようにして、適切な制御信号を印加することによって駆動される。したがって、提案される手法は、ＸＯＲゲートおよび関連する双方向マルチプレクサを各ＬＦＳＲ段の前に配置するので、顕著に大きなオーバーヘッド領域を招く。初期化回路を有するプログラム可能なＬＦＳＲの同様なアーキテクチャが、米国特許第５，０９０，０３５号に与えられている。
【００１０】
米国特許第５，７９０，６２６号は、２重（順方向および逆方向）入力を有する双方向ＬＦＳＲを開示する。ＬＦＳＲは、両者の状態軌跡を生成し得る：当初のフィードバック多項式およびその逆の対応物のそれぞれに対応する、パターンの順方向シーケンス、および逆のものである。レジスタは、一度に独占的に動作する２つの異なる線形帰還ネットワークを特徴とするが、順および逆のステップを混合することも可能であり、一度に両方向でＬＦＳＲの負のシーケンスによるベクトル生成プロセスを可能にする。同様な概念は、米国特許第５，７１９，９１３号にも開示されており、フィードバック・ネットワークにおけるＸＯＲゲートが、双方向マルチプレクサの多重化によって駆動される。
【００１１】
しかしながら、これら従来の手法はいずれも、上述したおよびＬＦＳＭに見出される実行性制限に対する最適な解決手段を提供するものではない。
【００１２】
［概要］
本発明の一形態では、線形帰還シフト・レジスタ（ＬＦＳＲ）を統合する方法は以下のステップを包含する。当初の（ｏｒｉｇｉｎａｌ）線形有限状態マシーン回路が取得され、その回路は複数のメモリ素子および線形論理ゲートを有し、出力シーケンスを生成することが可能である。当初回路におけるフィードバック接続が決定され、フィードバック接続は複数のメモリ素子に及ぶものであり、フィードバック接続線で結合された起点タップ（ｓｏｕｒｃｅ ｔａｐ）および宛先タップ（ｄｅｓｔｉｎａｔｉｏｎ ｔａｐ）を包含する。フィードバック接続の１つ又はそれ以上の起点および宛先タップは、その後に、同一方向で複数のメモリ素子にわたってシフトされる。これらのシフトは、当初の回路を、修正された線形有限状態マシーン回路に変換し、当初の回路と同一の出力シーケンスを提供し得るが、より少ない論理レベルおよびより低い内部ファン・アウト（ｉｎｔｅｒｎａｌ ｆａｎ−ｏｕｔ）を利用するものである。
【００１３】
本発明の他の形態では、線形有限状態マシーンを統合する方法は、以下のステップより成る。当初の線形有限状態マシーン回路が取得され、前記回路が、複数のメモリ素子と線形論理ゲートとを有し、出力シーケンスを生成する。前記当初の回路における少なくとも第１および第２フィードバック接続が決定され、各フィードバック接続は、複数のメモリ素子にわたって張られており、関連するフィードバック接続線によって接続された起点タップと宛先タップとを有し、宛先タップが宛先線形論理ゲートを有する。フィードバック接続の起点および宛先タップは、その後に互いにシフトされ、第１フィードバックの宛先タップおよび第２フィードバック接続の起点タップが交差するようにする。他のフィードバック接続線は、第１フィードバック接続の起点タップと、第２フィードバック接続の宛先タップにおける宛先線形論理ゲートとの間に付加される。これらのシフトおよび付加的なフィードバック線は、当初の回路を、当初の回路と同一の出力シーケンスを提供し得る修正された有限状態マシーン回路に変換する。
【００１４】
本発明の更なる形態では、線形有限状態マシーン回路は、複数のメモリ素子および線形論理ゲートより成り、回路内のファン・アウトは、２より大きくなく、回路内の線形論理のレベル数は１より大きくない。
【００１５】
本発明のこれらおよび他の形態は、添付図面を参照する以下の詳細な説明に記述される。
【００１６】
［詳細な説明］
ここに示され開示される例示的な実施例において、本発明によるＬＦＳＭを統合する方法は、コンピュータ読み取り可能な媒体に格納されるソフトウエアで実現され、汎用コンピュータ・システムで実行される。そのようなコンピュータ・システムは図３のブロック１８に表現される。例えば、本発明は、可能な解決手段の範囲、およびＬＦＳＲのレイアウトに関する様々なトレード・オフを探索するコンピュータ支援設計ツールで実現される。簡単のため、本発明に関するソフトウエアの形態のみが説明され；当該技術分野で周知の製品の詳細は省略される。同様な理由により、コンピュータ・ハードウエアは詳細に説明されない。本発明は、コンピュータ・システム１８、特定のコンピュータ言語またはプログラムと共に利用することに限定されない。
【００１７】
図２は、フリップ・フロップまたはラッチのようなｎ個のメモリ素子および複数のフィードバック接続を有する、任意的な最大長タイプＩＩ型ＬＦＳＲの形式におけるＬＦＳＭを示す。各フィードバック接続は、その特定の接続を提供するメモリ素子の出力に対応する起点タップと、使用される基本特性多項式により定義されるメモリ素子数に及ぶフィードバック接続線と、フィードバック接続線の宛先タップに、すなわち他のメモリ素子への入力に設けられたＸＯＲゲートのような線形ゲートとを含む。説明される統合方法に従って、メモリ素子にわたってフィードバック接続をシフトすることによって、ＬＦＳＲアーキテクチャは変換されることが可能であり、実行性の最適化およびフィードバック線の全長を最小化する。これらの変換は、修正されたＬＦＳＲ回路が当初の回路のものとは異なる状態軌跡を与えるが、当初のＬＦＳＲ回路のｍ−シーケンスを保存するように実行され得る。すなわち、ＬＦＳＲ状態軌跡（任意の所与の時刻におけるメモリ素子の内容）は、当初のものと修正回路の間では異なるが、各々の回路から取得されるｍ−シーケンスは保存される。同一のＬＦＳＲシード（ｓｅｅｄ）が両回路に使用され、異なるメモリ素子から取得される場合には、ｍ−シーケンスは同じになる。異なるＬＦＳＲシードが利用可能ならば、同一のメモリ素子から取得される場合にｍ−シーケンスが同一になり得る。
【００１８】
図３は、第１の統合方法のフローチャートであり、図４ＡおよびＢは、左への基本シフトまたはＥＬ（ｅｌｅｍｅｎｔａｒｙ ｓｈｉｆｔ ｔｏ ｔｈｅ ｌｅｆｔ）と呼ばれるＬＦＳＲ変換の適用例を示す。図４Ａは、複数のメモリ素子にわたって、メモリ素子Ｘの出力に起点タップ２２とメモリ素子Ｃへの入力に宛先タップ（宛先ＸＯＲゲート２４を含む）とを有するフィードバック接続線２０を有する、当初のＬＦＳＲ回路を示す。タップは関連するフィードバック接続線により接続される。図４Ｂは、変換により修正された結果のＬＦＳＲ回路を示す。図４Ａでは、最も右側のもの（Ｚ）を除いて総てのメモリ素子が、最初にシンボルａ，ｂ，ｃ，．．．，ｐを包含することを想定する。メモリ素子Ｚは、０に初期化される（あるいは、ＸＯＲゲートの場所にＸＮＯＲゲートが使用されるならば、１に初期化される。）。１シフトの後（図４Ａ）、新規のシンボルｄがメモリ素子Ａに入るので、メモリ素子は、シンボルｄ，ａ，ｂ，．．．，ｑ，ｐを包含する。次のシフトの後に、メモリ素子の内容は、次のようになる：
【００１９】
【外１】
0003595537.tif 000002
ＬＦＳＲの更なる動作は、示されるようなデータの更なるシフトを生成する。ここで、図４Ｂにおいて、変換ＥＬが当初のＬＦＳＲ回路に適用され、メモリ素子Ｂの入力にＸＯＲゲート２４を設け、それに応じてフィードバック接続２０の起点タップ２２をメモリ素子Ｙの出力に移動させる。以前と同じ初期状態を仮定すると（特に、メモリ素子Ｚに０の値がロードされる）、観測され得ることは、当初のフィードバック線によって張られていたメモリ素子の内容、すなわちフリップ・フロップＣ，．．．，Ｙ，Ｚは、当初の回路におけるフリップ・フロップＣ，．．．，Ｙ，Ｚの出力に生じるシンボルに一致する。したがって、これらのメモリ素子の出力に生成されるｍ−シーケンスは保存され、変換されたＬＦＳＲは最大長回路であり続ける。しかしながら、メモリ素子Ｂは両者の場合で異なるシンボルを受信するので、その軌跡は当初のモノとは異なることに留意すべきである。同様にして、変換ＥＲ（右への基本シフト）がＬＦＳＲに応用され得る。フリップ・フロップＺが初期にリセットされるとすると、変換後にフィードバック線によって張られるビットに生成される総てのｍ−シーケンスは保存される。
【００２０】
上記のＬＦＳＲ変換により実行される動作は、コンピュータ・システム１８に関連して図３により一般的に説明される。統合ソフトウエアまたは等価ツールにより、当初のＬＦＳＲ回路のコピーが取得され（２６）、ユーザによる直接的な介入がなされるならば、二次的格納部から又はメモリから取得される。図４ＡのＬＦＳＲ回路におけるメモリ素子ＣないしＺにわたって張るフィードバック接続のように、当初の回路におけるフィードバック接続が決定される。１つ又はそれ以上のフィードバック接続が、当初の回路における同一方向に複数のメモリ素子にわたってシフトされる（３０）。これらのシフトが実行され、フィードバック線の長さを減少させ、線形論理のレベルを減少させ、当初回路の内部ファン・アウトを減少させる。
【００２１】
図５は、適切なシード（ｓｅｅｄ）を選択することによって、フィードバック接続がメモリ素子にわたってシフトされるにもかかわらず、修正されたＬＦＳＲ回路でｍ−シーケンスがどのようにして保存されるかを示す。シフトの方向が決定される（３２）−左（メモリ素子のデータ・フロー方向に対して上りとして定められる。）又は右（メモリ素子のデータ・フロー方向に対して下りとして定められる）である。シフトがＬＦＳＲで左ならば（３４）、初期ＬＦＳＲベクトル又はシードは、シフトの結果としてフィードバック接続の外にシフトされるメモリ素子に、同一の論理値が提供される。シフトがＬＦＳＲで右ならば（３６）、初期ＬＦＳＲベクトル又はシードは、シフトの結果としてフィードバック接続内にシフトされるメモリ素子に、同一の論理値が提供される。いずれの場合であっても、当初回路の線形ゲートがＸＯＲゲートならば、同一の論理値はゼロであり、当初回路の線形ゲートがＸＮＯＲゲートならば、同一の論理値は１である。
【００２２】
移動させるフィードバック接続の宛先ゲート（又は起点タップ）が他の宛先ゲート（又は起点タップ）と交差するような場合を取り扱うために、変換ＥＬおよびＥＲが拡張され得る。これらの状況の例が図６ＡおよびＢ，７ＡおよびＢに示される。示されているように、図６Ａ，７Ａにおいて内部（短い）フィードバック接続４０，４２が、それぞれ図６Ｂ，７Ｂの左又は右側にシフトされ、更なる変換は必要とされない。変換されたフィードバック接続は、その内容が変換ＥＬまたはＥＲによって影響されずに残るところのシンボルをメモリ素子に提供する。変換のその形式は、回路の最大長の特性を保存し、総てのメモリ素子が上述した適切なシードで初期されていることを想定している。特に、図６ＡおよびＢにおけるフリップ・フロップＱ、図７ＡおよびＢにおけるフリップ・フロップＹは、変換ＥＬおよびＥＲが実行される際にそれぞれ０に初期化される。
【００２３】
図８は、第２の統合方法を図示するフローチャートであり、フィードバック接続シフトが、一方のフィードバック接続における宛先ゲートおよび他のフィードバック接続における起点タップを交差させるものである。当初のＬＦＳＲ回路が少なくとも２つのフィードバック接続（５０）を有する場合に、本方法が利用され得る。シフトの後に、回路トポロジ（ｔｏｐｏｌｏｇｙ）が検査され、宛先ゲートおよび起点タップが交差したか否かを判定する（５２）。しかしながら、宛先ゲートおよび起点タップが交差するならば、以下に説明するように、ＬＦＳＲ回路に適切なフィードバック接続が付加される（５６）。フィードバック接続は右または左に移動させることが可能であるので、そのような交差から生じ得る４つの対応する変換が存在する：ＳＤＬ（左に移動する際に、起点タップが宛先ゲートと交差する）；ＳＤＲ（右に移動する際に、起点タップが宛先ゲートと交差する）；ＤＳＬ（左に移動する際に、宛先ゲートが起点タップと交差する）；およびＤＳＲ（右に移動する際に、宛先ゲートが起点タップと交差する）である。
【００２４】
変換ＳＤＬは図９Ａ−Ｃに示されている。これが使用されるのは、２つのフィードバック接続５８，５９が、第１フィードバック接続の宛先タップにおける（図示されているＸＯＲゲートのような）線形ゲート６０が、図９Ａに示されるように、単独のメモリ素子の分だけ第２フィードバック接続の起点タップから離れているように、並ぶ場合である。変換の第１部分の間に、起点タップ６２はそのメモリ素子を超えてシフトする（図９Ｂ）。第２フィードバック接続の宛先タップにおけるＸＯＲゲート６４は、それに従って左にシフトする。個の動作は先に説明した変換ＥＬと同様なので、この操作は、ＬＦＳＲの最大長の特性を保存する。しかしながら、その後に、起点タップ６２は更に移動し、第１フィードバック接続５８（図９Ｃ）のＸＯＲゲート６０と交差する。第２フィードバック接続５９により搬送されるシンボルは、もはや、
【００２５】
【外２】
0003595537.tif 000003
ではなく；それはちょうどｂに等しい。宛先ＸＯＲゲート６４の出力において同一の機能性を維持するためには、シンボルａが第１フィードバック接続５８の起点タップ６６からＸＯＲゲート６４に提供される必要がある。これは、起点タップ６６、およびシフトされた宛先タップのＸＯＲゲート６４の間にフィードバック接続を付加することによって達成される。言及に価することは、シンボルａは、この特定のゲートにおいて、各自の宛先に到達するいくつかのフィードバック経路を代表し得ることである。このような場合に、これら総てのフィードバック接続は、変換ＳＤＬにより必要とされるよう拡張される。同様の規則が変換ＳＤＲ，ＤＳＬ，ＤＳＲに適用される。
【００２６】
図１０Ａ−Ｃには変換ＳＤＲが示される。最初に、この操作に包含される両フィードバック接続７８，６９は、何らの共通のメモリ素子を含まない（図１０Ａ）。つまり、右にシフトされる第２フィードバック接続７９は、第１フィードバック接続７８の宛先タップにおいて、ＸＯＲゲート８０に供給するフィリップ・フロップの出力において起点タップ８２を有する。したがって、ゲート８０の出力は、
【００２７】
【外３】
0003595537.tif 000004
に等しい。第１の操作の間に、起点タップ８２はＸＯＲゲート８０を交差し、この回路の機能を変化させる（図１０Ｂ）。第２フィードバック接続７９の宛先タップにおけるＸＯＲゲート８４の出力における以前の値を維持するために、フィードバック接続線８８が、ＸＯＲゲート８４、および第１フィードバック接続７８の起点タップ８６の間に付加される。付加されたフィードバック線８８は、シンボルａの影響を補償し、これは、
【００２８】
【外４】
0003595537.tif 000005
の式を考慮することによるものである。最後に、ＬＦＳＲの機能に影響を及ぼさないで、第２フィードバック接続７９において、ＥＲ変換が実行され、この変換は付加的なＸＯＲゲート８９を追加する（図１０Ｃ）。
【００２９】
変換ＤＳＬは図１１Ａ−Ｃに示される。第１の操作に加えて初期設定（図１１Ａ）は、変換ＳＤＲのものと同様である。したがって、新たなフィードバック接続線９０が付加され、回路の当初の機能を保持する（図１１Ｂ）。しかしながら、最後の操作の間に（図１１Ｃ）、変換ＥＬが第１フィードバック接続９２に行われ、１メモリ素子の分だけ左にシフトした第１フィードバック接続のＸＯＲゲート９４を有する構造となる。
【００３０】
変換ＤＳＲは図１２Ａ−Ｃに示される。当初の回路から修正されたＬＦＳＲを形成する場合に、変換ＥＲが最初に第１フィードバック接続１００に適用される（図１２Ｂ）。その後に、第１フィードバックのＸＯＲゲート１０２がシフトされ、第２フィードバック接続１０６の起点タップ１０４を横切り、または等価的に、起点タップ１０４がＸＯＲゲート１０２の出力からゲートの入力に移動される（図１２Ｃ）。この最終的な操作は、シンボルａを、総和の
【００３１】
【外５】
0003595537.tif 000006
から除去し、これは第２フィードバック接続のＸＯＲゲート１０８に提供される。この喪失は、第１フィードバック接続１００の起点タップ１１２およびＸＯＲゲート１０８の間にフィードバック接続１１０を付加することによって補償される必要があり、ゲートの入力において引数ａおよびｂの両者を維持する（図９Ｃ）。
【００３２】
説明した変換（ＥＬ，ＥＲ，ＳＤＬ，ＳＤＲ，ＤＳＬ，ＤＳＲ）は、ＬＦＳＭを統合する際に１回又はそれ以上利用されることが可能である。それらは、統合化における他の変換と組み合わせることも可能である。これら可能な応用例は以下に説明される。これらの変換により得られる修正された線形有限状態マシーンのアーキテクチャは、２より大きくない内部ファン・アウト、線形論理ゲートの１レベルに過ぎないこと、および短いフィードバック接続線により特徴付けられる。
【００３３】
図１３Ａ−Ｄは、連続的なＥＬ変換による、タイプＩのＬＦＳＲ、タイプＩＩのＬＦＳＲおよび線形セルラ・オートマトンを有する様々な形式のＬＦＳＭからＬＦＳＲを統合する例である。特に、図１３Ａに示されるＬＦＳＲの構造は、基本多項式ｘ３２＋ｘ３０＋ｘ２１＋ｘ１６＋ｘ１１＋ｘ４＋１を実行する真のガロア法（ｔｒｕｅ Ｇａｌｏｉｓ ｄｉｖｉｓｏｒ）またはタイプＩＩのシフト・レジスタであり、共通の起点タップ１２９からＸＯＲゲート１３０−１３８を含む別個の宛先タップへ各々結合するライン１２０−１２８を含む５つのフィードバック接続を有する。このＬＦＳＲでは、ＸＯＲゲートが、一連のメモリ素子に沿う各々の順方向伝送経路にそれぞれ配置される。たとえば、各ＸＯＲゲートは、先行する段の出力に結合された１つの入力と、連続する段の入力に結合する出力と、メモリ素子０の出力で発するフィードバック経路に結合される第２入力を有する。ＬＦＳＲ回路の全体的なレイアウトは、リング構造を形成することによって、更なる変換に先立って最適化されている。そして、本願の統合方法の最も重要な利点の２つが図１３Ｄに現れ、これは図１３Ａの当初のタイプＩＩのＬＦＳＲ回路から修正されたＬＦＳＲ回路への変換を示す。理解されるように、図１３Ｄの修正されたＬＦＳＲ回路は、変換ＥＬを５つのフィードバック接続（係数ｘ３０，ｘ２１，ｘ１６，ｘ１１およびｘ４により表現される）にそれぞれ１，５，８，１０および１４回適用することによって得られる。これは、移動、起点タップ１２９の５つの別々のタップへの分割、およびＸＯＲゲート１３０−１３８の移動になる。したがって、修正されたＬＦＳＲ回路におけるフィードバック線１２０−１２８の組み合わせられた全長は、当初のＬＦＳＲ回路のものに比べて顕著に短くなる。ＬＦＳＲの内部ファン・アウトは、３の因子により減少し、当初のＬＦＳＲ回路のフリップ・フロップ０により供給される６つの素子（メモリ素子３１および５つのＸＯＲゲート１３０−１３８）から、修正されたＬＦＳＲ回路におけるフリップ・フロップにより供給されるわずか２つの素子（次のメモリ素子および１つのＸＯＲ）に減少する。さらに、図１３Ｄの修正されたＬＦＳＲ回路は、最悪の場合であっても、任意のフリップ・フロップの対の間でＸＯＲ論理の１レベルしか有しない。
【００３４】
また、ＬＦＳＲは、他のタイプのＬＦＳＭから統合されることも可能である。たとえば、図１３Ｄに示される修正されたＬＦＳＲは、上述した変換を適用することによって、図１３ＡのタイプＩのＬＦＳＲ（同一の基本多項式ｘ３２＋ｘ３０＋ｘ２１＋ｘ１６＋ｘ１１＋ｘ４＋１を実行する）から得ることが可能である。さらに、図１３Ｄの修正されたＬＦＳＲは、図に示されるようなヌル（ｎｕｌｌ）境界条件を利用してこれらの変換を適用することによって、図１３Ｃの３２ビット線形セルら・オートマトン（同一の基本多項式ｘ３２＋ｘ３０＋ｘ２１＋ｘ１６＋ｘ１１＋ｘ４＋１を実行する）から取得され得る。
【００３５】
図１４Ａ−Ｄは、上記の変換の組み合わせの応用により、ＬＦＳＲを統合する例であり、この場合においてＥＬ変換およびＳＤＬ変換が使用される。図１４Ａは、基本多項式ｘ８＋ｘ６＋ｘ５＋ｘ＋１を実行するタイプＩＩのＬＦＳＲを示す。係数ｘで表現されるフィードバック接続（起点タップ１３０および宛先タップ１３４を有するフィードバック接続１３０）に変換ＥＬを４回適用し、図１４Ｂに示す回路を導出する。その後に、変換ＳＤＬがフィードバック接続１３０をさらに左に１メモリ素子だけシフトし、ＸＯＲゲート１３４の入力にフィード縛接続１３６を付加する（図１４Ｃ）。しかしながら、同一の接続を有する他のＸＯＲゲート１３８がフリップ・フロップ６の出力にすでに存在するので、ゲート１３４および接続１３６は捨てられ得る。このことは、ＬＦＳＲにおけるＸＯＲゲート数を３から２に減少させる。（図１４ＣにおけるＸＯＲゲート１４０，１３８を駆動する）フリップ・フロップ５の負荷を減少させるため、追加の変換ＥＬが図１４Ｄに適用され、フィードバック接続１３０を更に左にシフトさせる。
【００３６】
以上、例示的な実施例で本発明の原理を図示および説明してきたが、当業者に明らかであろうことは、例示的実施例はそのような原理から逸脱することなしに、形態および詳細において修正され得ることである。たとえば、その用途が有益で、具体的で明白な結果を生成する限り、本発明は望まれるのであればコンピュータの支援なしに実行される。本発明は、ＬＦＳＲおよびセルラ・オートマトン以外のＬＦＳＭを統合するために使用され得る。本発明が適用され得る多くの実施例に関し、理解されるべきことは、説明した実施例はこれらの原理を教示することを意図するものであり、本発明の範囲を限定しないことである。したがって、特許請求の範囲および均等物の範囲にそれらのすべてが包含されることを意図する。
【図面の簡単な説明】
【図１】図１は、タイプＩのＬＦＳＲの図である。
【図２】図２は、タイプＩＩのＬＦＳＲの図である。
【図３】図３は、本発明による第１の統合方法のフローチャートである。
【図４Ａ】図４ＡおよびＢは、本方法によるＬＦＳＲのＥＬ変換を示す。
【図４Ｂ】図４ＡおよびＢは、本方法によるＬＦＳＲのＥＬ変換を示す。
【図５】図５は、本方法によるＬＦＳＲを初期化する方法のフローチャートである。
【図６Ａ】図６ＡおよびＢは、ＬＦＳＲにおける２つの線形論理ゲートを交差させる左への基本シフト（ＥＬ）変換の応用例を示す。
【図６Ｂ】図６ＡおよびＢは、ＬＦＳＲにおける２つの線形論理ゲートを交差させる左への基本シフト（ＥＬ）変換の応用例を示す。
【図７Ａ】図７ＡおよびＢは、ＬＦＳＲにおける２つの起点タップを交差させる右（Ｅ）へのＥ基本シフト変換の応用例を示す。
【図７Ｂ】図７ＡおよびＢは、ＬＦＳＲにおける２つの起点タップを交差させる右（Ｅ）へのＥ基本シフト変換の応用例を示す。
【図８】図８は、本発明による第２の統合方法のフローチャートである。
【図９Ａ】図９Ａ−Ｃは、第２方法に従って、左移動における宛先タップを横切る起点タップ（ＳＤＬ）変換の応用例を示す。
【図９Ｂ】図９Ａ−Ｃは、第２方法に従って、左移動における宛先タップを横切る起点タップ（ＳＤＬ）変換の応用例を示す。
【図９Ｃ】図９Ａ−Ｃは、第２方法に従って、左移動における宛先タップを横切る起点タップ（ＳＤＬ）変換の応用例を示す。
【図１０Ａ】図１０Ａ−Ｃは、第２方法に従って、右移動における宛先タップを横切る起点タップ（ＳＤＲ）変換の応用例を示す。
【図１０Ｂ】図１０Ａ−Ｃは、第２方法に従って、右移動における宛先タップを横切る起点タップ（ＳＤＲ）変換の応用例を示す。
【図１０Ｃ】図１０Ａ−Ｃは、第２方法に従って、右移動における宛先タップを横切る起点タップ（ＳＤＲ）変換の応用例を示す。
【図１１Ａ】図１１Ａ−Ｃは、第２方法に従って、左移動における起点タップを横切る宛先タップ（ＤＳＬ）変換の応用例を示す。
【図１１Ｂ】図１１Ａ−Ｃは、第２方法に従って、左移動における起点タップを横切る宛先タップ（ＤＳＬ）変換の応用例を示す。
【図１１Ｃ】図１１Ａ−Ｃは、第２方法に従って、左移動における起点タップを横切る宛先タップ（ＤＳＬ）変換の応用例を示す。
【図１２Ａ】図１２Ａ−Ｃは、第２方法に従って、右移動における起点タップを横切る宛先タップ（ＤＳＲ）変換の応用例を示す。
【図１２Ｂ】図１２Ａ−Ｃは、第２方法に従って、右移動における起点タップを横切る宛先タップ（ＤＳＲ）変換の応用例を示す。
【図１２Ｃ】図１２Ａ−Ｃは、第２方法に従って、右移動における起点タップを横切る宛先タップ（ＤＳＲ）変換の応用例を示す。
【図１３Ａ】図１３Ａ−Ｄは、タイプＩのＬＦＳＲ、タイプＩＩのＬＦＳＲおよび線形セルラ・オートマトンの３つの形式のＬＦＳＭからＬＦＳＲを統合する例である。
【図１３Ｂ】図１３Ａ−Ｄは、タイプＩのＬＦＳＲ、タイプＩＩのＬＦＳＲおよび線形セルラ・オートマトンの３つの形式のＬＦＳＭからＬＦＳＲを統合する例である。
【図１３Ｃ】図１３Ａ−Ｄは、タイプＩのＬＦＳＲ、タイプＩＩのＬＦＳＲおよび線形セルラ・オートマトンの３つの形式のＬＦＳＭからＬＦＳＲを統合する例である。
【図１３Ｄ】図１３Ａ−Ｄは、タイプＩのＬＦＳＲ、タイプＩＩのＬＦＳＲおよび線形セルラ・オートマトンの３つの形式のＬＦＳＭからＬＦＳＲを統合する例である。
【図１４Ａ】図１４Ａ−Ｄは、当初のＬＦＳＲ回路に対する異なる変換の組み合わせを適用することによるＬＦＳＲを統合する例である。
【図１４Ｂ】図１４Ａ−Ｄは、当初のＬＦＳＲ回路に対する異なる変換の組み合わせを適用することによるＬＦＳＲを統合する例である。
【図１４Ｃ】図１４Ａ−Ｄは、当初のＬＦＳＲ回路に対する異なる変換の組み合わせを適用することによるＬＦＳＲを統合する例である。
【図１４Ｄ】図１４Ａ−Ｄは、当初のＬＦＳＲ回路に対する異なる変換の組み合わせを適用することによるＬＦＳＲを統合する例である。
【図１】
0003595537.tif 000007
【図２】
0003595537.tif 000008
【図３】
0003595537.tif 000009
【図４Ａ】
0003595537.tif 000010
【図４Ｂ】
0003595537.tif 000011
【図５】
0003595537.tif 000012
【図６Ａ】
0003595537.tif 000013
【図６Ｂ】
0003595537.tif 000014
【図７Ａ】
0003595537.tif 000015
【図７Ｂ】
0003595537.tif 000016
【図８】
0003595537.tif 000017
【図９Ａ】
0003595537.tif 000018
【図９Ｂ】
0003595537.tif 000019
【図９Ｃ】
0003595537.tif 000020
【図１０Ａ】
0003595537.tif 000021
【図１０Ｂ】
0003595537.tif 000022
【図１０Ｃ】
0003595537.tif 000023
【図１１Ａ】
0003595537.tif 000024
【図１１Ｂ】
0003595537.tif 000025
【図１１Ｃ】
0003595537.tif 000026
【図１２Ａ】
0003595537.tif 000027
【図１２Ｂ】
0003595537.tif 000028
【図１２Ｃ】
0003595537.tif 000029
【図１３Ａ】
0003595537.tif 000030
【図１３Ｂ】
0003595537.tif 000031
【図１３Ｃ】
0003595537.tif 000032
【図１３Ｄ】
0003595537.tif 000033
【図１４Ａ】
0003595537.tif 000034
【図１４Ｂ】
0003595537.tif 000035
【図１４Ｃ】
0003595537.tif 000036
【図１４Ｄ】
0003595537.tif 000037