(57)【要約】【課題】符号理論および暗号理論で用いる場合でも、所望の用途に可変できる汎用性のある線形フィードバックシフトレジスタを提供でき、また、ガロアおよびフィボナッチの両タイプの線形フィードバックシフトレジスタを用いるシステムにおいて、低コスト化を図ることができる線形フィードバックシフトレジスタを提供する。【解決手段】線形フィードバックシフトレジスタであって、排他的論理和の対象であって入力ビットに影響を与えるビットを出力するタップを選択するタップ選択手段と、ビット列の何れのビットをフィードバックループの始めのビットとするかを選択するフィードバック開始位置選択手段とを備え、タップ選択手段によってタップを選択することで、線形フィードバックシフトレジスタで実現される多項式の項を規定し、フィードバック開始位置選択手段によってフィードバックループの開始位置を設定することで、多項式の最大次数を決定する。【選択図】図１
2014175834.tif 000002
【特許請求の範囲】
【請求項１】
ビット列を構成する一部のビットの排他的論理和を入力ビットとしてフィードバックする線形フィードバックシフトレジスタであって、
排他的論理和の対象であって前記入力ビットに影響を与えるビットを出力するタップを選択するタップ選択手段と、
前記ビット列の何れのビットをフィードバックループの始めのビットとするかを選択するフィードバック開始位置選択手段と、を備え、
前記タップ選択手段によって前記タップを選択することで、前記線形フィードバックシフトレジスタで実現される多項式の項を規定し、
前記フィードバック開始位置選択手段によって前記フィードバックループの開始位置を設定することで、前記多項式の最大次数を決定する、線形フィードバックシフトレジスタ。
【請求項２】
前記線形フィードバックシフトレジスタは、
シフトレジスタを構成する複数のフリップフロップのそれぞれの出力信号を受ける複数の排他的論理和素子を有し、
前記タップ選択手段は、
一方入力に、前記複数の排他的論理和素子のそれぞれを実質的に不活性状態とするか、活性状態を維持するかを設定するタップ選択信号を受け、他方入力に排他的論理和の対象となる信号を受け、その出力を前記複数の排他的論理和素子のそれぞれに与える複数の論理ゲートを有し、
前記タップ選択信号によって活性状態を維持する排他的論理和素子に出力を与えるフリップフロップをタップとして選択し、
前記フィードバック開始位置選択手段は、
前記複数のフリップフロップのそれぞれの出力信号を一方の入力に受け、他方の入力にフィードバック信号を受け、フィードバック開始位置選択信号によりどちらかを選択して出力する複数のセレクタを有し、
前記フィードバック開始位置選択信号により選択される所定のフリップフロップの出力信号を、前記フィードバックループの前記始めのビットとする、請求項１記載の線形フィードバックシフトレジスタ。
【請求項３】
前記線形フィードバックシフトレジスタは、
前記複数の排他的論理和素子が、前記複数のフリップフロップのそれぞれの間に介挿されたガロア線形フィードバックシフトレジスタであって、
前記複数の論理ゲートは、複数のＡＮＤゲートであって、
前記他方入力には前記排他的論理和の対象となる信号として前記フィードバック信号を受ける、請求項２記載の線形フィードバックシフトレジスタ。
【請求項４】
前記線形フィードバックシフトレジスタは、
前記複数の排他的論理和素子が、前記フィードバックループ中に介挿されたフィボナッチ線形フィードバックシフトレジスタであって、
前記複数の論理ゲートは、複数のＡＮＤゲートであって、
前記他方入力には、前記排他的論理和の対象となる信号として、前記複数のフリップフロップのそれぞれの出力信号を受ける、請求項２記載の線形フィードバックシフトレジスタ。
【請求項５】
前記複数の排他的論理和素子は、複数の第１の排他的論理和素子と、複数の第２の排他的論理和素子とを含み、
前記線形フィードバックシフトレジスタは、
前記複数の第１の排他的論理和素子が、前記複数のフリップフロップのそれぞれの間に介挿されたガロア線形フィードバックシフトレジスタと、
前記複数の第２の排他的論理和素子が、前記フィードバックループ中に介挿されたフィボナッチ線形フィードバックシフトレジスタと、を有し、
前記複数の論理ゲートは、複数の第１のＡＮＤゲートと、複数の第２のＡＮＤゲートとを含み、
前記タップ選択信号は、前記複数の第１のＡＮＤゲートの前記一方入力に与えられる第１のタップ選択信号と、前記複数の第２のＡＮＤゲートの前記一方入力に与えられる第２のタップ選択信号とを含み、
前記複数の第１のＡＮＤゲートのそれぞれの前記他方入力には前記排他的論理和の対象となる信号として前記フィードバック信号を受け、
前記複数の第２のＡＮＤゲートのそれぞれの前記他方入力には、前記排他的論理和の対象となる信号として、前記複数のフリップフロップのそれぞれの出力信号を受け、
前記第１および第２のタップ選択信号の設定により、前記ガロア線形フィードバックシフトレジスタを使用するか、前記フィボナッチ線形フィードバックシフトレジスタを使用するかを切り替える、請求項２記載の線形フィードバックシフトレジスタ。
【請求項６】
請求項３記載の線形フィードバックシフトレジスタと、
誤り訂正回路と、を備え、
前記線形フィードバックシフトレジスタは、
入力されたデータのシンドロームを生成して前記誤り訂正回路に与え、
前記誤り訂正回路は、
前記シンドロームに基づいて前記データの誤り訂正を行う、データ処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は線形フィードバックシフトレジスタおよびそれを有したデータ処理装置に関する。
【背景技術】
【０００２】
線形フィードバックシフトレジスタ（ＬＦＳＲ：linear feedback shift register）はガロア線形フィードバックシフトレジスタとフィボナッチ線形フィードバックシフトレジスタに分類される。両線形フィードバックシフトレジスタは用途によって使い分けられ、ガロア線形フィードバックシフトレジスタは暗号回路や符号理論(例えば、誤り訂正の符号化)に用いられ、フィボナッチ線形フィードバックシフトレジスタはＭ系列（maximal length sequence）の擬似乱数生成に用いられる。
【０００３】
これらの線形フィードバックシフトレジスタをハードウエアで構成する場合、従来的には既約多項式の次数に合わせてハードウエアを設計するため、既約多項式の次数は固定されてしまう。また、両タイプの線形フィードバックシフトレジスタを実装するシステムでは、それぞれの線形フィードバックシフトレジスタをハードウエアで実装することになるが、この場合、暗号の高度化に伴い、既約多項式の次数が大きくなる昨今では、回路規模が増大し、回路コストがますます増加するという問題がある。
【０００４】
特許文献１には、Montgomery乗算剰余方式を用いて任意の次数の演算を可能とする構成が開示されているが、Montgomery乗算に特化した構成の線形フィードバックシフトレジスタであり汎用性がない。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第４１７７５２６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明は上記のような問題点を解消するためになされたもので、符号理論および暗号理論で用いる場合でも、所望の用途に可変できる汎用性のある線形フィードバックシフトレジスタを提供でき、また、ガロアおよびフィボナッチの両タイプの線形フィードバックシフトレジスタを用いるシステムにおいて、低コスト化を図ることができる線形フィードバックシフトレジスタを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明に係る線形フィードバックシフトレジスタの第１の態様は、ビット列を構成する一部のビットの排他的論理和を入力ビットとしてフィードバックする線形フィードバックシフトレジスタであって、排他的論理和の対象であって前記入力ビットに影響を与えるビットを出力するタップを選択するタップ選択手段と、前記ビット列の何れのビットをフィードバックループの始めのビットとするかを選択するフィードバック開始位置選択手段と、を備え、前記タップ選択手段によって前記タップを選択することで、前記線形フィードバックシフトレジスタで実現される多項式の項を規定し、前記フィードバック開始位置選択手段によって前記フィードバックループの開始位置を設定することで、前記多項式の最大次数を決定する。
【０００８】
本発明に係る線形フィードバックシフトレジスタの第２の態様は、前記線形フィードバックシフトレジスタが、シフトレジスタを構成する複数のフリップフロップのそれぞれの出力信号を受ける複数の排他的論理和素子を有し、前記タップ選択手段は、一方入力に、前記複数の排他的論理和素子のそれぞれを実質的に不活性状態とするか、活性状態を維持するかを設定するタップ選択信号を受け、他方入力に排他的論理和の対象となる信号を受け、その出力を前記複数の排他的論理和素子のそれぞれに与える複数の論理ゲートを有し、前記タップ選択信号によって活性状態を維持する排他的論理和素子に出力を与えるフリップフロップをタップとして選択し、前記フィードバック開始位置選択手段は、前記複数のフリップフロップのそれぞれの出力信号を一方の入力に受け、他方の入力にフィードバック信号を受け、フィードバック開始位置選択信号によりどちらかを選択して出力する複数のセレクタを有し、前記フィードバック開始位置選択信号により選択される所定のフリップフロップの出力信号を、前記フィードバックループの前記始めのビットとする。
【０００９】
本発明に係る線形フィードバックシフトレジスタの第３の態様は、前記線形フィードバックシフトレジスタが、前記複数の排他的論理和素子が、前記複数のフリップフロップのそれぞれの間に介挿されたガロア線形フィードバックシフトレジスタであって、前記複数の論理ゲートは、複数のＡＮＤゲートであって、前記他方入力には前記排他的論理和の対象となる信号として前記フィードバック信号を受ける。
【００１０】
本発明に係る線形フィードバックシフトレジスタの第４の態様は、前記線形フィードバックシフトレジスタが、前記複数の排他的論理和素子が、前記フィードバックループ中に介挿されたフィボナッチ線形フィードバックシフトレジスタであって、前記複数の論理ゲートは、複数のＡＮＤゲートであって、前記他方入力には、前記排他的論理和の対象となる信号として、前記複数のフリップフロップのそれぞれの出力信号を受ける。
【００１１】
本発明に係る線形フィードバックシフトレジスタの第５の態様は、前記複数の排他的論理和素子は、複数の第１の排他的論理和素子と、複数の第２の排他的論理和素子とを含み、前記線形フィードバックシフトレジスタは、前記複数の第１の排他的論理和素子が、前記複数のフリップフロップのそれぞれの間に介挿されたガロア線形フィードバックシフトレジスタと、前記複数の第２の排他的論理和素子が、前記フィードバックループ中に介挿されたフィボナッチ線形フィードバックシフトレジスタとを有し、前記複数の論理ゲートは、複数の第１のＡＮＤゲートと、複数の第２のＡＮＤゲートと、を含み、前記タップ選択信号は、前記複数の第１のＡＮＤゲートの前記一方入力に与えられる第１のタップ選択信号と、前記複数の第２のＡＮＤゲートの前記一方入力に与えられる第２のタップ選択信号とを含み、前記複数の第１のＡＮＤゲートのそれぞれの前記他方入力には前記排他的論理和の対象となる信号として前記フィードバック信号を受け、前記複数の第２のＡＮＤゲートのそれぞれの前記他方入力には、前記排他的論理和の対象となる信号として、前記複数のフリップフロップのそれぞれの出力信号を受け、前記第１および第２のタップ選択信号の設定により、前記ガロア線形フィードバックシフトレジスタを使用するか、前記フィボナッチ線形フィードバックシフトレジスタを使用するかを切り替える。
【００１２】
本発明に係るデータ処理装置の態様は、線形フィードバックシフトレジスタの第３の態様の線形フィードバックシフトレジスタと、誤り訂正回路とを備え、前記線形フィードバックシフトレジスタが、入力されたデータのシンドロームを生成して前記誤り訂正回路に与え、前記誤り訂正回路が、前記シンドロームに基づいて前記データの誤り訂正を行う。
【発明の効果】
【００１３】
本発明によれば、タップ選択手段によってタップを選択することで、線形フィードバックシフトレジスタで実現される多項式を任意に設定でき、フィードバック開始位置選択手段によってフィードバックループの開始位置を設定することで、最大次数以下であれば多項式の最大次数を任意に設定し、変更することができる。このように、次数を任意に設定でき、可変できることから、符号理論および暗号理論で用いる場合でも、所望の用途に可変できる汎用性のある線形フィードバックシフトレジスタを得ることができる。
【図面の簡単な説明】
【００１４】
【図１】本発明に係る実施の形態１の動的可変型ガロア線形フィードバックシフトレジスタの構成を示す回路図である。
【図２】本発明に係る実施の形態１の動的可変型ガロア線形フィードバックシフトレジスタの動作を説明する図である。
【図３】本発明に係る実施の形態１の動的可変型ガロア線形フィードバックシフトレジスタの動作を説明する等価回路図である。
【図４】本発明に係る実施の形態１の動的可変型ガロア線形フィードバックシフトレジスタの動作を説明する図である。
【図５】本発明に係る実施の形態２の動的可変型フィボナッチ線形フィードバックシフトレジスタの構成を示す回路図である。
【図６】本発明に係る実施の形態２の動的可変型フィボナッチ線形フィードバックシフトレジスタの動作を説明する図である。
【図７】本発明に係る実施の形態２の動的可変型フィボナッチ線形フィードバックシフトレジスタの動作を説明する等価回路図である。
【図８】本発明に係る実施の形態２の動的可変型フィボナッチ線形フィードバックシフトレジスタの動作を説明する図である。
【図９】本発明に係る実施の形態３の動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタの構成を示す回路図である。
【図１０】本発明に係る実施の形態３の動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタの動作を説明する図である。
【図１１】本発明に係る実施の形態３の動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタの動作を説明する等価回路図である。
【図１２】本発明に係る実施の形態３の動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタの動作を説明する図である。
【図１３】本発明に係る実施の形態３の動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタの動作を説明する等価回路図である。
【図１４】本発明に係る実施の形態３の動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタの動作を説明する図である。
【図１５】本発明に係る線形フィードバックシフトレジスタの適用例の構成を示すブロック図である。
【図１６】本発明に係る線形フィードバックシフトレジスタの適用例の構成を示すブロック図である。
【図１７】本発明に係る線形フィードバックシフトレジスタの適用例の動作を説明するフローチャートである。
【図１８】本発明に係る線形フィードバックシフトレジスタの適用例の動作を説明するフローチャートである。
【発明を実施するための形態】
【００１５】
＜実施の形態１＞
＜装置構成＞
図１は本発明に係る実施の形態１の動的可変型ガロア線形フィードバックシフトレジスタ１００の構成を示す回路図である。
【００１６】
図１に示す動的可変型ガロア線形フィードバックシフトレジスタ１００は最大８次の既約多項式を規定することができ、フリップフロップＦ１，Ｆ２，Ｆ３，Ｆ４，Ｆ５，Ｆ６，Ｆ７およびＦ８と、２入力のＡＮＤゲートＧ１，Ｇ２，Ｇ３，Ｇ４，Ｇ５，Ｇ６，Ｇ７およびＧ８と、２入力のセレクタＳ１，Ｓ２，Ｓ３，Ｓ４，Ｓ５，Ｓ６およびＳ７と、排他的論理和素子Ａ１，Ａ２，Ａ３，Ａ４，Ａ５，Ａ６，Ａ７およびＡ８を備えている。
【００１７】
入力データを受ける排他的論理和素子Ａ１の出力は、フリップフロップＦ１の入力に接続され、フリップフロップＦ１の出力は排他的論理和素子Ａ２の入力に接続され、排他的論理和素子Ａ２の出力はフリップフロップＦ２の入力に接続され、フリップフロップＦ２の出力は排他的論理和素子Ａ３の入力に接続され、排他的論理和素子Ａ３の出力はフリップフロップＦ３の入力に接続され、フリップフロップＦ３の出力は排他的論理和素子Ａ４の入力に接続され、排他的論理和素子Ａ４の出力はフリップフロップＦ４の入力に接続され、フリップフロップＦ４の出力は排他的論理和素子Ａ５の入力に接続され、排他的論理和素子Ａ５の出力はフリップフロップＦ５の入力に接続され、フリップフロップＦ５の出力は排他的論理和素子Ａ６の入力に接続され、排他的論理和素子Ａ６の出力はフリップフロップＦ６の入力に接続され、フリップフロップＦ６の出力は排他的論理和素子Ａ７の入力に接続され、排他的論理和素子Ａ７の出力はフリップフロップＦ７の入力に接続され、フリップフロップＦ７の出力は排他的論理和素子Ａ８の入力に接続され、排他的論理和素子Ａ８の出力はフリップフロップＦ８の入力に接続され、フリップフロップＦ８の出力が出力データとなる。
【００１８】
フリップフロップＦ８の出力はＡＮＤゲートＧ８の一方入力に接続されると共に、セレクタＳ７の「０」入力に接続されている。なお、セレクタＳ７の「１」入力にはフリップフロップＦ７の出力が接続され、セレクタＳ７の選択入力には次数を決める選択信号ＳＥＬ[６]が与えられる。そして、ＡＮＤゲートＧ８の他方入力にはタップを選択するタップ選択信号ＰＡ[７]が与えられ、ＡＮＤゲートＧ８の出力は排他的論理和素子Ａ８の入力に接続されている。
【００１９】
セレクタＳ７の出力はＡＮＤゲートＧ７の一方入力に接続されると共に、セレクタＳ６の「０」入力に接続されている。なお、セレクタＳ６の「１」入力にはフリップフロップＦ６の出力が接続され、セレクタＳ６の選択入力には次数を決める選択信号ＳＥＬ[５]が与えられる。そして、ＡＮＤゲートＧ７の他方入力にはタップを選択するタップ選択信号ＰＡ[６]が与えられ、ＡＮＤゲートＧ７の出力は排他的論理和素子Ａ７の入力に接続されている。
【００２０】
セレクタＳ６の出力はＡＮＤゲートＧ６の一方入力に接続されると共に、セレクタＳ５の「０」入力に接続されている。なお、セレクタＳ５の「１」入力にはフリップフロップＦ５の出力が接続され、セレクタＳ５の選択入力には次数を決める選択信号ＳＥＬ[４]が与えられる。そして、ＡＮＤゲートＧ６の他方入力にはタップを選択するタップ選択信号ＰＡ[５]が与えられ、ＡＮＤゲートＧ６の出力は排他的論理和素子Ａ６の入力に接続されている。
【００２１】
セレクタＳ５の出力はＡＮＤゲートＧ５の一方入力に接続されると共に、セレクタＳ４の「０」入力に接続されている。なお、セレクタＳ４の「１」入力にはフリップフロップＦ４の出力が接続され、セレクタＳ４の選択入力には次数を決める選択信号ＳＥＬ[３]が与えられる。そして、ＡＮＤゲートＧ５の他方入力にはタップを選択するタップ選択信号ＰＡ[４]が与えられ、ＡＮＤゲートＧ５の出力は排他的論理和素子Ａ５の入力に接続されている。
【００２２】
セレクタＳ４の出力はＡＮＤゲートＧ４の一方入力に接続されると共に、セレクタＳ３の「０」入力に接続されている。なお、セレクタＳ３の「１」入力にはフリップフロップＦ３の出力が接続され、セレクタＳ３の選択入力には次数を決める選択信号ＳＥＬ[２]が与えられる。そして、ＡＮＤゲートＧ４の他方入力にはタップを選択するタップ選択信号ＰＡ[３]が与えられ、ＡＮＤゲートＧ４の出力は排他的論理和素子Ａ４の入力に接続されている。
【００２３】
セレクタＳ３の出力はＡＮＤゲートＧ３の一方入力に接続されると共に、セレクタＳ２の「０」入力に接続されている。なお、セレクタＳ２の「１」入力にはフリップフロップＦ２の出力が接続され、セレクタＳ２の選択入力には次数を決める選択信号ＳＥＬ[１]が与えられる。そして、ＡＮＤゲートＧ３の他方入力にはタップを選択するタップ選択信号ＰＡ[２]が与えられ、ＡＮＤゲートＧ３の出力は排他的論理和素子Ａ３の入力に接続されている。
【００２４】
セレクタＳ２の出力はＡＮＤゲートＧ２の一方入力に接続されると共に、セレクタＳ１の「０」入力に接続されている。なお、セレクタＳ１の「１」入力にはフリップフロップＦ１の出力が接続され、セレクタＳ１の選択入力には次数を決める選択信号ＳＥＬ[０]が与えられる。そして、ＡＮＤゲートＧ２の他方入力にはタップを選択するタップ選択信号ＰＡ[１]が与えられ、ＡＮＤゲートＧ２の出力は排他的論理和素子Ａ２の入力に接続されている。
【００２５】
セレクタＳ１の出力はＡＮＤゲートＧ１の一方入力に接続され、ＡＮＤゲートＧ１の他方入力にはタップを選択するタップ選択信号ＰＡ[０]が与えられ、ＡＮＤゲートＧ１の出力は排他的論理和素子Ａ１の入力に接続されている。
【００２６】
＜動作＞
このような構成を有する動的可変型ガロア線形フィードバックシフトレジスタ１００においては、８ビットのタップ選択信号ＰＡと７ビットの選択信号ＳＥＬを適宜設定することで、最大８次の既約多項式を規定することができる。
【００２７】
例えば、既約多項式Ｘ４＋Ｘ３＋Ｘ２＋１を規定したい場合には、タップ選択信号ＰＡ[７：０]＝００００１１０１とすることで、図２に示されるように、排他的論理和素子を不活性状態または活性状態としてタップを選択し、また、選択信号ＳＥＬ[６：０]＝０００１０００とすることで、図２に示されるように、フィードバックループを何れのフリップフロップの出力から始めるかを選択する。
【００２８】
すなわち、図２に示されるように、選択信号ＳＥＬ[３]＝１とすることで、フリップフロップＦ４の出力が循環する構成となり、フリップフロップＦ４よりデータの流れで下流側となるフリップフロップＦ５〜Ｆ８はフィードバックシフトレジスタとしては機能しなくなり、フリップフロップＦ４の出力が出力データとなる。
【００２９】
このように、セレクタＳ１〜Ｓ７は、どのフリップフロップの出力をフィードバックループの始めのビットとするかを選択するので、フィードバック開始位置選択手段と呼称することができ、選択信号ＳＥＬは、フィードバック開始位置選択信号と呼称することができる。
【００３０】
また、タップ選択信号ＰＡ[１]＝０とすることでＡＮＤゲートＧ２の出力は０となり、排他的論理和素子Ａ２はフリップフロップＦ１の出力をそのままフリップフロップＦ２に送るだけの実質的に不活性な状態となる。一方、排他的論理和素子Ａ３、Ａ４は活性状態を維持する。この結果、動的可変型ガロア線形フィードバックシフトレジスタ１００は、図３に示す等価回路のように、フリップフロップＦ４、Ｆ３およびＦ２がいわゆるタップとなり、既約多項式Ｘ４＋Ｘ３＋Ｘ２＋１が規定されることとなる。
【００３１】
このように、ＡＮＤゲートＧ２〜Ｇ８は、排他的論理和の対象であって入力ビットに影響を与えるビットを出力するタップを選択するタップ選択手段と呼称することができる。
【００３２】
また、動的可変型ガロア線形フィードバックシフトレジスタ１００においては、全ての排他的論理和素子を実質的に不活性状態とし、８ビットの単純なシフトレジスタとすることも可能である。
【００３３】
すなわち、タップ選択信号ＰＡ[７：０]＝００００００００とし、選択信号ＳＥＬ[６：０]＝０００００００とすることで、動的可変型ガロア線形フィードバックシフトレジスタ１００は、図４に示されるようにフリップフロップＦ１〜Ｆ８が直列に接続された８ビットのシフトレジスタとなる。
【００３４】
以上説明したように、実施の形態１の動的可変型ガロア線形フィードバックシフトレジスタ１００によれば、選択信号ＳＥＬを適宜に設定することで、ハードウエアとして設定された最大次数以下であれば既約多項式の次数を任意に設定し、変更することができる。次数を任意に設定できることから、符号理論で用いる場合には符号長を可変にでき、また、誤り訂正能力を可変にすることができる。また、暗号理論で用いる場合には、異なる次数の剰余乗算に可変することができる。
【００３５】
また、タップ選択信号ＰＡを適宜に設定することで、タップとなるフリップフロップを任意に設定できるので、ハードウエアとして設定された最大次数以下であれば既約多項式を任意に設定し、また、変更することができる。タップとなるフリップフロップを任意に設定することでタップ位置を可変できることから、符号理論や暗号理論で用いる場合には、所望の既約多項式への対応が可能となる。
【００３６】
また、線形フィードバックシフトレジスタとして使用しない場合には、単純なシフトレジスタとして使用することもできるので、汎用性を高めることができる。
【００３７】
＜実施の形態２＞
＜装置構成＞
図５は本発明に係る実施の形態２の動的可変型フィボナッチ線形フィードバックシフトレジスタ２００の構成を示す回路図である。
【００３８】
図５に示す動的可変型フィボナッチ線形フィードバックシフトレジスタ２００は最大８次の既約多項式を規定することができ、フリップフロップＦ１１，Ｆ１２，Ｆ１３，Ｆ１４，Ｆ１５，Ｆ１６，Ｆ１７およびＦ１８と、２入力のＡＮＤゲートＧ１１，Ｇ１２，Ｇ１３，Ｇ１４，Ｇ１５，Ｇ１６，Ｇ１７およびＧ１８と、２入力のセレクタＳ１１，Ｓ１２，Ｓ１３，Ｓ１４，Ｓ１５，Ｓ１６およびＳ１７と、排他的論理和素子Ａ１１，Ａ１２，Ａ１３，Ａ１４，Ａ１５，Ａ１６，Ａ１７およびＡ１８を備えている。
【００３９】
入力データを受ける排他的論理和素子Ａ１１の出力は、フリップフロップＦ１１の入力に接続され、フリップフロップＦ１１の出力はフリップフロップＦ１２の入力に接続され、フリップフロップＦ１２の出力はフリップフロップＦ１３の入力に接続され、フリップフロップＦ１３の出力はフリップフロップＦ１４の入力に接続され、フリップフロップＦ１４の出力はフリップフロップＦ１５の入力に接続され、フリップフロップＦ１５の出力はフリップフロップＦ１６の入力に接続され、フリップフロップＦ１６の出力はフリップフロップＦ１７の入力に接続され、フリップフロップＦ１７の出力はフリップフロップＦ１８の入力に接続され、フリップフロップＦ１８の出力が出力データとなる。
【００４０】
フリップフロップＦ１８の出力は排他的論理和素子Ａ１８の入力に接続され、フリップフロップＦ１７の出力はＡＮＤゲートＧ１８の一方入力に接続されると共に、セレクタＳ１７の「１」入力に接続されている。なお、セレクタＳ１７の選択入力には次数を決める選択信号ＳＥＬ[６]が与えられる。そして、ＡＮＤゲートＧ１８の他方入力にはタップを選択するタップ選択信号ＰＡ[７]が与えられ、ＡＮＤゲートＧ１８の出力は排他的論理和素子Ａ１８の入力に接続され、排他的論理和素子Ａ１８の出力はセレクタＳ１７の「０」入力に接続されている。
【００４１】
セレクタＳ１７の出力は排他的論理和素子Ａ１７の入力に接続され、排他的論理和素子Ａ１７の出力はセレクタＳ１６の「０」入力に接続されている。
【００４２】
フリップフロップＦ１６の出力はＡＮＤゲートＧ１６の一方入力に接続されると共に、セレクタＳ１６の「１」入力に接続されている。なお、セレクタＳ１６の選択入力には次数を決める選択信号ＳＥＬ[５]が与えられる。そして、ＡＮＤゲートＧ１７の他方入力にはタップを選択するタップ選択信号ＰＡ[６]が与えられ、ＡＮＤゲートＧ１７の出力は排他的論理和素子Ａ１７の入力に接続されている。
【００４３】
セレクタＳ１６の出力は排他的論理和素子Ａ１６の入力に接続され、排他的論理和素子Ａ１６の出力はセレクタＳ１５の「０」入力に接続されている。
【００４４】
フリップフロップＦ１５の出力はＡＮＤゲートＧ１６の一方入力に接続されると共に、セレクタＳ１５の「１」入力に接続されている。なお、セレクタＳ１５の選択入力には次数を決める選択信号ＳＥＬ[４]が与えられる。そして、ＡＮＤゲートＧ１６の他方入力にはタップを選択するタップ選択信号ＰＡ[５]が与えられ、ＡＮＤゲートＧ１６の出力は排他的論理和素子Ａ１６の入力に接続されている。
【００４５】
セレクタＳ１５の出力は排他的論理和素子Ａ１５の入力に接続され、排他的論理和素子Ａ１５の出力はセレクタＳ１４の「０」入力に接続されている。
【００４６】
フリップフロップＦ１４の出力はＡＮＤゲートＧ１５の一方入力に接続されると共に、セレクタＳ１４の「１」入力に接続されている。なお、セレクタＳ１４の選択入力には次数を決める選択信号ＳＥＬ[３]が与えられる。そして、ＡＮＤゲートＧ１５の他方入力にはタップを選択するタップ選択信号ＰＡ[４]が与えられ、ＡＮＤゲートＧ１５の出力は排他的論理和素子Ａ１５の入力に接続されている。
【００４７】
セレクタＳ１４の出力は排他的論理和素子Ａ１４の入力に接続され、排他的論理和素子Ａ１４の出力はセレクタＳ１３の「０」入力に接続されている。
【００４８】
フリップフロップＦ１３の出力はＡＮＤゲートＧ１４の一方入力に接続されると共に、セレクタＳ１３の「１」入力に接続されている。なお、セレクタＳ１３の選択入力には次数を決める選択信号ＳＥＬ[２]が与えられる。そして、ＡＮＤゲートＧ１４の他方入力にはタップを選択するタップ選択信号ＰＡ[３]が与えられ、ＡＮＤゲートＧ１４の出力は排他的論理和素子Ａ１４の入力に接続されている。
【００４９】
セレクタＳ１３の出力は排他的論理和素子Ａ１３の入力に接続され、排他的論理和素子Ａ１３の出力はセレクタＳ１２の「０」入力に接続されている。
【００５０】
フリップフロップＦ１２の出力はＡＮＤゲートＧ１３の一方入力に接続されると共に、セレクタＳ１２の「１」入力に接続されている。なお、セレクタＳ１２の選択入力には次数を決める選択信号ＳＥＬ[１]が与えられる。そして、ＡＮＤゲートＧ１３の他方入力にはタップを選択するタップ選択信号ＰＡ[２]が与えられ、ＡＮＤゲートＧ１３の出力は排他的論理和素子Ａ１３の入力に接続されている。
【００５１】
セレクタＳ１２の出力は排他的論理和素子Ａ１２の入力に接続され、排他的論理和素子Ａ１２の出力はセレクタＳ１１の「０」入力に接続されている。
【００５２】
フリップフロップＦ１１の出力はＡＮＤゲートＧ１２の一方入力に接続されると共に、セレクタＳ１１の「１」入力に接続されている。なお、セレクタＳ１１の選択入力には次数を決める選択信号ＳＥＬ[０]が与えられる。そして、ＡＮＤゲートＧ１２の他方入力にはタップを選択するタップ選択信号ＰＡ[１]が与えられ、ＡＮＤゲートＧ１２の出力は排他的論理和素子Ａ１２の入力に接続されている。
【００５３】
セレクタＳ１１の出力はＡＮＤゲートＧ１１の一方入力に接続され、ＡＮＤゲートＧ１１の他方入力にはタップを選択するタップ選択信号ＰＡ[０]が与えられ、ＡＮＤゲートＧ１１の出力は排他的論理和素子Ａ１１の入力に接続されている。
【００５４】
＜動作＞
このような構成を有する動的可変型フィボナッチ線形フィードバックシフトレジスタ２００においては、８ビットのタップ選択信号ＰＡと７ビットの選択信号ＳＥＬを適宜設定することで、最大８次の既約多項式を規定することができる。
【００５５】
例えば、既約多項式Ｘ４＋Ｘ２＋１を規定したい場合には、タップ選択信号ＰＡ[７：０]＝０００００１０１とすることで、図６に示されるように、排他的論理和素子を不活性状態または活性状態としてタップを選択し、また、選択信号ＳＥＬ[６：０]＝０００１０００とすることで、図６に示されるようにフィードバックループを何れのフリップフロップの出力から始めるかを選択する。
【００５６】
すなわち、図６に示されるように、選択信号ＳＥＬ[３]＝１とすることで、フリップフロップＦ１４の出力が循環する構成となり、フリップフロップＦ１４よりデータの流れで下流側となるフリップフロップＦ１５〜Ｆ１８はフィードバックシフトレジスタとしては機能しなくなり、フリップフロップＦ１４の出力が出力データとなる。
【００５７】
このように、セレクタＳ１１〜Ｓ１７は、どのフリップフロップの出力をフィードバックループの始めのビットとするかを選択するので、フィードバック開始位置選択手段と呼称することができ、選択信号ＳＥＬは、フィードバック開始位置選択信号と呼称することができる。
【００５８】
また、タップ選択信号ＰＡ[１]＝０およびＰＡ[３]＝０とすることでＡＮＤゲートＧ１２およびＧ１４の出力は０となり、排他的論理和素子Ａ１２およびＡ１４は、それぞれセレクタＳ１２およびＳ１４の出力をそのままセレクタＳ１１およびＳ１３に送るだけの実質的に不活性な状態となる。一方、排他的論理和素子Ａ１３は活性状態を維持する。この結果、動的可変型フィボナッチ線形フィードバックシフトレジスタ２００は、図７に示す等価回路のように、フリップフロップＦ１４およびＦ１２がいわゆるタップとなり、既約多項式Ｘ４＋Ｘ２＋１が規定されることとなる。
【００５９】
このように、ＡＮＤゲートＧ１２〜Ｇ１８は、排他的論理和の対象であって入力ビットに影響を与えるビットを出力するタップを選択するタップ選択手段と呼称することができる。
【００６０】
また、動的可変型フィボナッチ線形フィードバックシフトレジスタ２００においては、全ての排他的論理和素子を実質的に不活性状態とし、８ビットの単純なシフトレジスタとすることも可能である。
【００６１】
すなわち、タップ選択信号ＰＡ[７：０]＝００００００００とし、選択信号ＳＥＬ[６：０]＝０００００００とすることで、動的可変型フィボナッチ線形フィードバックシフトレジスタ２００は、図８に示されるようにフリップフロップＦ１１〜Ｆ１８が直列に接続された８ビットのシフトレジスタとなる。
【００６２】
以上説明したように、実施の形態２の動的可変型フィボナッチ線形フィードバックシフトレジスタ２００によれば、選択信号ＳＥＬを適宜に設定することで、ハードウエアとして設定された最大次数以下であれば既約多項式の次数を任意に設定し、変更することができる。次数を任意に設定できることから、乱数生成に用いる場合には、乱数生成器の乱数発生の周期を可変することができる。
【００６３】
また、タップ選択信号ＰＡを適宜に設定することで、タップとなるフリップフロップを任意に設定できるので、ハードウエアとして設定された最大次数以下であれば既約多項式を任意に設定し、また、変更することができる。タップとなるフリップフロップを任意に設定することでタップ位置を可変できることから、所望の既約多項式への対応が可能となる。
【００６４】
また、線形フィードバックシフトレジスタとして使用しない場合には、単純なシフトレジスタとして使用することもできるので、汎用性を高めることができる。
【００６５】
＜実施の形態３＞
＜装置構成＞
図９は本発明に係る実施の形態３の動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタ３００の構成を示す回路図である。
【００６６】
図９に示す動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタ３００は最大５次の既約多項式を規定することができ、フリップフロップＦ２１，Ｆ２２，Ｆ２３，Ｆ２４およびＦ２５と、２入力のＯＲゲートＧ２０と、２入力のＡＮＤゲートＧ２１，Ｇ２２，Ｇ２３，Ｇ２４、Ｇ２５、Ｇ３１，Ｇ３２，Ｇ３３およびＧ３４と、２入力のセレクタＳ２１，Ｓ２２，Ｓ２３およびＳ２４と、排他的論理和素子Ａ２１，Ａ２２，Ａ２３，Ａ２４，Ａ２５，Ａ３１，Ａ３２，Ａ３３およびＡ３４を備えている。
【００６７】
入力データを受ける排他的論理和素子Ａ２１の出力は、フリップフロップＦ２１の入力に接続され、フリップフロップＦ２１の出力は排他的論理和素子Ａ２２の入力に接続され、排他的論理和素子Ａ２２の出力はフリップフロップＦ２２の入力に接続され、フリップフロップＦ２２の出力は排他的論理和素子Ａ２３の入力に接続され、排他的論理和素子Ａ２３の出力はフリップフロップＦ２３の入力に接続され、フリップフロップＦ２３の出力は排他的論理和素子Ａ２４の入力に接続され、排他的論理和素子Ａ２４の出力はフリップフロップＦ２４の入力に接続され、フリップフロップＦ２４の出力は排他的論理和素子Ａ２５の入力に接続され、排他的論理和素子Ａ２５の出力はフリップフロップＦ２５の入力に接続され、リップフロップＦ２５の出力が出力データとなる。
【００６８】
フリップフロップＦ２５の出力はＡＮＤゲートＧ２５の一方入力に接続されると共に、排他的論理和素子Ａ３４の入力に接続されている。そして、ＡＮＤゲートＧ２５の他方入力にはタップを選択するタップ選択信号ＧＰＡ[４]が与えられ、ＡＮＤゲートＧ２５の出力は排他的論理和素子Ａ２５の入力に接続されている。
【００６９】
フリップフロップＦ２４の出力は排他的論理和素子Ａ２５の入力に接続される共に、ＡＮＤゲートＧ３４の一方入力およびセレクタＳ２４の「１」入力に接続されている。なお、セレクタＳ２４の選択入力には次数を決める選択信号ＤＳＥＬ[３]が与えられる。そして、ＡＮＤゲートＧ３４の他方入力にはタップを選択するタップ選択信号ＦＰＡ[４]が与えられ、ＡＮＤゲートＧ３４の出力は排他的論理和素子Ａ３４の入力に接続され、排他的論理和素子Ａ３４の出力はセレクタＳ２４の「０」入力に接続されている。
【００７０】
セレクタＳ２４の出力はＡＮＤゲートＧ２４の一方入力に接続されると共に、排他的論理和素子Ａ３３の入力に接続されている。そして、ＡＮＤゲートＧ２４の他方入力にはタップを選択するタップ選択信号ＧＰＡ[３]が与えられ、ＡＮＤゲートＧ２４の出力は排他的論理和素子Ａ２４の入力に接続されている。
【００７１】
フリップフロップＦ２３の出力は排他的論理和素子Ａ２４の入力に接続される共に、ＡＮＤゲートＧ３３の一方入力およびセレクタＳ２３の「１」入力に接続されている。なお、セレクタＳ２３の選択入力には次数を決める選択信号ＤＳＥＬ[２]が与えられる。そして、ＡＮＤゲートＧ３３の他方入力にはタップを選択するタップ選択信号ＦＰＡ[３]が与えられ、ＡＮＤゲートＧ３３の出力は排他的論理和素子Ａ３３の入力に接続され、排他的論理和素子Ａ３３の出力はセレクタＳ２３の「０」入力に接続されている。
【００７２】
セレクタＳ２３の出力はＡＮＤゲートＧ２３の一方入力に接続されると共に、排他的論理和素子Ａ３２の入力に接続されている。そして、ＡＮＤゲートＧ２３の他方入力にはタップを選択するタップ選択信号ＧＰＡ[２]が与えられ、ＡＮＤゲートＧ２３の出力は排他的論理和素子Ａ２３の入力に接続されている。
【００７３】
フリップフロップＦ２２の出力は排他的論理和素子Ａ２３の入力に接続される共に、ＡＮＤゲートＧ３２の一方入力およびセレクタＳ２２の「１」入力に接続されている。なお、セレクタＳ２２の選択入力には次数を決める選択信号ＤＳＥＬ[１]が与えられる。そして、ＡＮＤゲートＧ３２の他方入力にはタップを選択するタップ選択信号ＦＰＡ[２]が与えられ、ＡＮＤゲートＧ３２の出力は排他的論理和素子Ａ３２の入力に接続され、排他的論理和素子Ａ３２の出力はセレクタＳ２２の「０」入力に接続されている。
【００７４】
セレクタＳ２２の出力はＡＮＤゲートＧ２２の一方入力に接続されると共に、排他的論理和素子Ａ３１の入力に接続されている。そして、ＡＮＤゲートＧ２２の他方入力にはタップを選択するタップ選択信号ＧＰＡ[１]が与えられ、ＡＮＤゲートＧ２２の出力は排他的論理和素子Ａ２２の入力に接続されている。
【００７５】
フリップフロップＦ２１の出力は排他的論理和素子Ａ２２の入力に接続される共に、ＡＮＤゲートＧ３１の一方入力およびセレクタＳ２１の「１」入力に接続されている。なお、セレクタＳ２１の選択入力には次数を決める選択信号ＤＳＥＬ[０]が与えられる。そして、ＡＮＤゲートＧ３１の他方入力にはタップを選択するタップ選択信号ＦＰＡ[１]が与えられ、ＡＮＤゲートＧ３１の出力は排他的論理和素子Ａ３１の入力に接続され、排他的論理和素子Ａ３１の出力はセレクタＳ２１の「０」入力に接続されている。
【００７６】
セレクタＳ２１の出力はＡＮＤゲートＧ２１の一方入力に接続され、ＡＮＤゲートＧ２１の他方入力にはＯＲゲートＧ２０の出力が与えられる。なお、ＯＲゲートＧ２０の入力にはタップを選択するタップ選択信号ＦＰＡ[０]およびＧＰＡ[０]が与えられる。
【００７７】
＜動作＞
このような構成を有する動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタ３００においては、５ビットのタップ選択信号ＧＰＡ（第１のタップ選択信号）、タップ選択信号ＦＰＡ（第２のタップ選択信号）および４ビットの選択信号ＤＳＥＬを適宜設定することで、ガロア線形フィードバックシフトレジスタまたはフィボナッチ線形フィードバックシフトレジスタとして構成し、最大５次の既約多項式を規定することができる。
【００７８】
例えば、ガロア線形フィードバックシフトレジスタを構成し、既約多項式Ｘ４＋Ｘ３＋Ｘ２＋１を規定したい場合には、タップ選択信号ＧＰＡ[４：０]＝０１１０１およびタップ選択信号ＦＰＡ[４：０]＝０００００とすることで、図１０に示されるように、排他的論理和素子を不活性状態または活性状態としてタップを選択し、また、選択信号ＤＳＥＬ[３：０]＝１０００とすることで、図１０に示されるようにフィードバックループを何れのフリップフロップの出力から始めるかを選択する。
【００７９】
すなわち、図１０に示されるように、選択信号ＤＳＥＬ[３]＝１とすることで、フリップフロップＦ２４の出力が循環する構成となり、フリップフロップＦ２４よりデータの流れで下流側となるフリップフロップＦ２５はフィードバックシフトレジスタとしては機能しなくなり、フリップフロップＦ２４の出力が出力データとなる。
【００８０】
このように、セレクタＳ２１〜Ｓ２４は、どのフリップフロップの出力をフィードバックループの始めのビットとするかを選択するので、フィードバック開始位置選択手段と呼称することができ、選択信号ＤＳＥＬは、フィードバック開始位置選択信号と呼称することができる。
【００８１】
また、タップ選択信号ＧＰＡ[１]＝０とすることでＡＮＤゲートＧ２２の出力は０となり、排他的論理和素子Ａ２２はフリップフロップＦ２１の出力をそのままフリップフロップＦ２２に送るだけの実質的に不活性な状態となる。一方、排他的論理和素子Ａ２３、Ａ２４は活性状態を維持する。また、タップ選択信号ＦＰＡ[３]、ＦＰＡ[２]およびＦＰＡ[１]は何れも０であるので排他的論理和素子Ａ３３、Ａ３２およびＡ３１は何れも実質的に不活性な状態となる。この結果、動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタ３００は、図１１に示す等価回路のように、フリップフロップＦ２４、Ｆ２３およびＦ２２がいわゆるタップとなり、既約多項式Ｘ４＋Ｘ３＋Ｘ２＋１が規定されることとなる。
【００８２】
このように、ＡＮＤゲートＧ２２〜Ｇ２５は、排他的論理和の対象であって入力ビットに影響を与えるビットを出力するタップを選択するタップ選択手段と呼称することができる。
【００８３】
また、フィボナッチ線形フィードバックシフトレジスタを構成し、既約多項式Ｘ４＋Ｘ２＋１を規定したい場合には、タップ選択信号ＧＰＡ[４：０]＝０００００とし、タップ選択信号ＦＰＡ[４：０]＝００１０１とすることで、図１２に示されるように、排他的論理和素子を不活性状態または活性状態としてタップを選択し、また、選択信号ＤＳＥＬ[３：０]＝１０００とすることで、図１２に示されるようにフィードバックループを何れのフリップフロップの出力から始めるかを選択する。
【００８４】
すなわち、図１２に示されるように、選択信号ＤＳＥＬ[３]＝１とすることで、フリップフロップＦ２４の出力が循環する構成となり、フリップフロップＦ２４よりデータの流れで下流側となるフリップフロップＦ２５はフィードバックシフトレジスタとしては機能しなくなり、フリップフロップＦ２４の出力が出力データとなる。
【００８５】
また、タップ選択信号ＦＰＡ[１]＝０およびＦＰＡ[３]＝０とすることでＡＮＤゲートＧ３１およびＧ３３の出力は０となり、排他的論理和素子Ａ３１およびＡ３３は、それぞれセレクタＳ２２およびＳ２４の出力をそのままセレクタＳ２１およびＳ２３に送るだけの実質的に不活性な状態となる。一方、排他的論理和素子Ａ３２は活性状態を維持する。この結果、動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタ３００は、図１３に示す等価回路のように、フリップフロップＦ２４およびＦ２２がいわゆるタップとなり、既約多項式Ｘ４＋Ｘ２＋１が規定されることとなる。
【００８６】
このように、ＡＮＤゲートＧ３１〜Ｇ３４は、排他的論理和の対象であって入力ビットに影響を与えるビットを出力するタップを選択するタップ選択手段と呼称することができる。
【００８７】
また、動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタ３００においては、全ての排他的論理和素子を実質的に不活性状態とし、５ビットの単純なシフトレジスタとすることも可能である。
【００８８】
すなわち、タップ選択信号ＧＰＡ[４：０]およびＦＰＡ[４：０]を何れも０００００とし、選択信号ＤＳＥＬ[３：０]＝００００とすることで、動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタ３００は、図１４に示されるようにフリップフロップＦ２１〜Ｆ２５が直列に接続された５ビットのシフトレジスタとなる。
【００８９】
以上説明したように、実施の形態３の動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタ３００によれば、タップ選択信号ＧＰＡおよびＦＰＡの設定により、ガロア線形フィードバックシフトレジスタまたはフィボナッチ線形フィードバックシフトレジスタとして使用することができるので、例えば、１つのシステムで、ガロア、フィボナッチの両線形フィードバックシフトレジスタを備える必要がある場合に、動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタを１つ実装すれば、用途に応じて変形させて使い分けると言った柔軟な使用が可能となる。
【００９０】
また、動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタでは、フリップフロップはガロア、フィボナッチの両線形フィードバックシフトレジスタで共用できるので、回路規模の増大を抑制したシステムを構築でき、回路コストの増加を抑制して低コスト化を図ることができる。
【００９１】
また、選択信号ＤＳＥＬを適宜に設定することで、ハードウエアとして設定された最大次数以下であれば既約多項式の次数を任意に設定し、変更することができる。次数を任意に設定できることから、ガロア線形フィードバックシフトレジスタとして符号理論で用いる場合には、符号長を可変にでき、また誤り訂正能力を可変にすることができる。また、暗号理論で用いる場合には、異なる次数の剰余乗算に可変することができる。また、フィボナッチ線形フィードバックシフトレジスタとして乱数生成に用いる場合には、乱数生成器の乱数発生の周期を可変することができる。
【００９２】
また、タップ選択信号ＧＰＡおよびＦＰＡを適宜に設定することで、タップとなるフリップフロップを任意に設定できるので、ハードウエアとして設定された最大次数以下であれば既約多項式を任意に設定し、また、変更することができる。タップとなるフリップフロップを任意に設定することでタップ位置を可変できることから、ガロア線形フィードバックシフトレジスタとして符号理論や暗号理論で用いる場合には、所望の既約多項式への対応が可能となる。また、フィボナッチ線形フィードバックシフトレジスタとして用いる場合には、所望の既約多項式への対応が可能となる。
【００９３】
また、線形フィードバックシフトレジスタとして使用しない場合には、単純なシフトレジスタとして使用することもできるので、汎用性を高めることができる。
【００９４】
なお、以上説明した実施の形態１および２の動的可変型ガロア線形フィードバックシフトレジスタ１００および動的可変型フィボナッチ線形フィードバックシフトレジスタ２００においては、最大８次の既約多項式を規定できる構成を示し、実施の形態３の動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタ３００においては、最大５次の既約多項式を規定できる構成を示したがこれに限定されるものではなく、フリップフロップ等を増加すれば、規定できる次数は任意に増やすことができる。
【００９５】
＜変形例＞
以上説明した実施の形態１および２の動的可変型ガロア線形フィードバックシフトレジスタ１００および動的可変型フィボナッチ線形フィードバックシフトレジスタ２００、実施の形態３の動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタ３００は、ハードウエアにより実装されるものとして説明したが、ソフトウェアにより実装することも可能である。
【００９６】
＜適用例＞
次に、以上説明した動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタを適用したシステムの一例について図１５〜図１８を用いて説明する。
【００９７】
図１５および図１６は、ＮＡＮＤフラッシュメモリ３０の制御装置１０の構成を示すブロック図であり、図１５は書き込み動作を説明する図であり、図１６は読み出し動作を説明する図である。
【００９８】
図１５および図１６に示すように、制御装置１０は、ＣＰＵ等のホスト装置２０との間で信号の授受を行うホストインタフェース１と、ホストインタフェース１に接続されたデータデスクランブル制御部２と、データデスクランブル制御部２との間で信号の授受を行う動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタ３と、動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタ３およびホストインタフェース１に接続されたデータスクランブル制御部４と、データデスクランブル制御部２に接続されたデコーダ部５および誤り訂正回路６と、ＮＡＮＤフラッシュメモリ３０との間で信号の授受を行うメモリインタフェース７と、メモリインタフェース７およびデータスクランブル制御部４に接続された誤り訂正回路８とを備えている。なお、制御装置１０は、電子データを処理するので、データ処理装置と呼称することができる。
【００９９】
ここで、データデスクランブル制御部２およびデータスクランブル制御部４は、Ｍ系列の擬似乱数を扱う部位であり、誤り訂正回路６は誤り訂正に用いるシンドロームを生成する部位であり、誤り訂正回路８は復号化の際の誤り訂正を行う部位である。
【０１００】
動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタ３は、誤り訂正回路６との間でも信号の授受を行うと共に、デコーダ部５からの信号を受ける。また、デコーダ部５および誤り訂正回路６はメモリインタフェース７にも接続されている。
【０１０１】
次に、図１５を参照しつつ、図１７に示すフローチャートを用いて、ＮＡＮＤフラッシュメモリ３０へのデータの書き込み動作を説明する。
【０１０２】
書き込み動作の開始にあたって、ホスト装置２０に電源が投入されていない場合、ホスト装置２０の電源スイッチＳＷがオンされることで制御装置１０も起動し、動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタ３は予め定めた次数とタップを有するフィボナッチ線形フィードバックシフトレジスタ３として初期化される（ステップＳＴ１）。
【０１０３】
次に、ホスト装置２０はスクランブル済み書き込みコマンドと書き込みデータをホストインタフェース１に送信する（ステップＳＴ２）。
【０１０４】
ホストインタフェース１は、ホスト装置２０から受信したスクランブル済み書き込みコマンドおよびスクランブル済み書き込みデータを、データデスクランブル制御部２に転送する（ステップＳＴ３）。
【０１０５】
次に、データデスクランブル制御部２は、フィボナッチ線形フィードバックシフトレジスタ３にスクランブル済み書き込みコマンドおよびスクランブル済み書き込みデータを転送する（ステップＳＴ４）。
【０１０６】
フィボナッチ線形フィードバックシフトレジスタ３は、受け取ったスクランブル済み書き込みコマンドおよびスクランブル済み書き込みデータをデスクランブルし、デスクランブル済み書き込みコマンドおよびデスクランブル済み書き込みデータとしてデータデスクランブル制御部２に転送する（ステップＳＴ５）。なお、デスクランブルにおいては、例えば図１２に示したフィボナッチ線形フィードバックシフトレジスタの構成において入力データとしてスクランブル済み書き込みコマンドおよびスクランブル済み書き込みデータを入力することで、デスクランブル済み書き込みコマンドおよびデスクランブル済み書き込みデータが出力データとして出力される。
【０１０７】
次に、データデスクランブル制御部２は、デスクランブル済み書き込みコマンドをデコーダ部５に転送し（ステップＳＴ６）、また、デスクランブル済み書き込みデータを誤り訂正回路６に転送する（ステップＳＴ７）。
【０１０８】
デコーダ部５は、書き込みコマンドを認識し、それに基づいて動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタ３を、予め定めた次数とタップを有するガロア線形フィードバックシフトレジスタ３に変更する（ステップＳＴ８）。
【０１０９】
そして、誤り訂正回路６は、デスクランブル済み書き込みデータをガロア線形フィードバックシフトレジスタ３に転送する（ステップＳＴ９）。
【０１１０】
ガロア線形フィードバックシフトレジスタ３は、デスクランブル済み書き込みデータからシンドロームを生成し、誤り訂正回路６に転送する（ステップＳＴ１０）。なお、シンドロームの生成においては、例えば図１０に示したガロア線形フィードバックシフトレジスタの構成において入力データとしてデスクランブル済み書き込みデータを入力することで、シンドロームが出力データとして出力される。
【０１１１】
また、デコーダ部５は、書き込みコマンドから書き込みアドレスを抽出し、書き込み制御信号を生成してメモリインタフェース７に転送する（ステップＳＴ１１）。
【０１１２】
誤り訂正回路６では、デスクランブル済み書き込みデータとシンドロームをメモリインタフェース７に転送する（ステップＳＴ１２）。
【０１１３】
メモリインタフェース７は、書き込み制御信号に基づいてＮＡＮＤフラッシュメモリ３０にデスクランブル済み書き込みデータとシンドロームの書き込み制御を開始する（ステップＳＴ１３）。
【０１１４】
デコーダ部５は、書き込み制御が終了すると、動的可変型ガロア・フィボナッチ線形フィードバックシフトレジスタ３を、予め定めた次数とタップを有するフィボナッチ型フィードバックシフトレジスタ３に変更し（ステップＳＴ１４）、一連の書き込み動作が終了する。
【０１１５】
次に、図１６を参照しつつ、図１８に示すフローチャートを用いて、ＮＡＮＤフラッシュメモリ３０からのデータの読み出し動作を説明する。
【０１１６】
読み出し動作を開始すると、まず、ホスト装置２０はスクランブル済み読み出しコマンドをホストインタフェース１に送信する（ステップＳＴ２１）。
【０１１７】
ホストインタフェース１は、ホスト装置２０から受信したスクランブル済み読み出しコマンドを、データデスクランブル制御部２に転送する（ステップＳＴ２２）。
【０１１８】
次に、データデスクランブル制御部２は、フィボナッチ線形フィードバックシフトレジスタ３にスクランブル済み読み出しコマンドを転送する（ステップＳＴ２３）。
【０１１９】
フィボナッチ線形フィードバックシフトレジスタ３は、受け取ったスクランブル済み読み出しコマンドをデスクランブルし、デスクランブル済み読み出しコマンドとしてデータデスクランブル制御部２に転送する（ステップＳＴ２４）。なお、デスクランブルにおいては、例えば図１２に示したフィボナッチ線形フィードバックシフトレジスタの構成において入力データとしてスクランブル済み読み出しコマンドを入力することで、デスクランブル済み読み出しコマンドが出力データとして出力される。
【０１２０】
次に、データデスクランブル制御部２は、デスクランブル済み読み出しコマンドをデコーダ部５に転送する（ステップＳＴ２５）。
【０１２１】
デコーダ部５は、読み出しコマンドを認識し、読み出しコマンドから読み出しアドレスを抽出し、読み出し制御信号をメモリインタフェース７に転送する（ステップＳＴ２６）。
【０１２２】
メモリインタフェース７は、読み出し制御信号に基づいてＮＡＮＤフラッシュメモリ３０からのデータの読み出し制御を開始する（ステップＳＴ２７）。
【０１２３】
ＮＡＮＤフラッシュメモリ３０は、読み出したデータとシンドロームをメモリインタフェース７に送信する（ステップＳＴ２８）。
【０１２４】
メモリインタフェース７は、ＮＡＮＤフラッシュメモリ３０から読み出したデータとシンドロームを誤り訂正回路８に転送する（ステップＳＴ２９）。
【０１２５】
誤り訂正回路８は、読み出したシンドロームを用い、読み出したデータの誤りを訂正し、誤り訂正済み読み出しデータとしてデータスクランブル制御部４に転送する（ステップＳＴ３０）。
【０１２６】
データスクランブル制御部４は、フィボナッチ線形フィードバックシフトレジスタ３に誤り訂正済み読み出しデータを転送する（ステップＳＴ３１）。
【０１２７】
フィボナッチ線形フィードバックシフトレジスタ３は、データスクランブル制御部４から受け取った誤り訂正済み読み出しデータをスクランブルし、スクランブル済み読み出しデータとしてデータスクランブル制御部４に転送する（ステップＳＴ３２）。なお、スクランブルにおいては、例えば図１２に示したフィボナッチ線形フィードバックシフトレジスタの構成において入力データとして誤り訂正済み読み出しデータを入力することで、スクランブル済み読み出しデータが出力データとして出力される。
【０１２８】
データスクランブル制御部４は、スクランブル済み読み出しデータをホストインタフェース１に転送する（ステップＳＴ３３）。
【０１２９】
ホストインタフェース１は、スクランブル済み読み出しデータをホスト装置２０に送信し（ステップＳＴ３４）、一連の読み出し動作が終了する。
【符号の説明】
【０１３０】
Ｇ１〜Ｇ８，Ｇ１１〜Ｇ１８，Ｇ２１〜Ｇ２４，Ｇ３１〜Ｇ３４  ＡＮＤゲート
Ｓ１〜Ｓ７，Ｓ１１〜Ｓ１７，Ｓ２１〜Ｓ２４  セレクタ
Ａ１〜Ａ８，Ａ１１〜Ａ１８，Ａ２１〜Ａ２５，Ａ３１〜Ａ３４  排他的論理和素子
【図１】
2014175834.tif 000003
【図２】
2014175834.tif 000004
【図３】
2014175834.tif 000005
【図４】
2014175834.tif 000006
【図５】
2014175834.tif 000007
【図６】
2014175834.tif 000008
【図７】
2014175834.tif 000009
【図８】
2014175834.tif 000010
【図９】
2014175834.tif 000011
【図１０】
2014175834.tif 000012
【図１１】
2014175834.tif 000013
【図１２】
2014175834.tif 000014
【図１３】
2014175834.tif 000015
【図１４】
2014175834.tif 000016
【図１５】
2014175834.tif 000017
【図１６】
2014175834.tif 000018
【図１７】
2014175834.tif 000019
【図１８】
2014175834.tif 000020