(57)【特許請求の範囲】
【請求項１】
生成多項式により固定される第１マスク変換行列と変換前のマスクベクトルとの積で新たなマスクベクトルを求める第１ステップと、
シフト量データのＭＳＢがゼロでない場合に、生成多項式により固定される第２マスク変換行列と前記第１ステップで求めたマスクベクトルとの積で新たなマスクベクトルを求める第２ステップと、
前記シフト量データをＭＳＢ側へシフトする第３ステップと、
前記第１ステップと前記第２ステップと前記第３ステップを指定回数繰り返した後にマスクベクトルに基づくマスクパターンを出力する第４ステップと、
を含んだことを特徴とする符号発生方法。
【請求項２】
生成多項式により固定される第１マスク変換行列と変換前のマスクベクトルとの積で新たなマスクベクトルを求め、シフト量データのＭＳＢがゼロでない場合に、生成多項式により固定される第２マスク変換行列と前記マスクベクトルとの積で新たなマスクベクトルを求める演算手段と、
前記シフト量データをＭＳＢ側へシフトするシフト手段と、
前記演算手段と前記シフト手段を指定回数動作させた後にマスクベクトルに基づくマスクパターンを出力する出力手段と、
を備えたことを特徴とする符号発生装置。
【請求項３】
前記演算手段と前記シフト手段と前記出力手段とを用いて、任意の初期状態を表すデータを、設定された位相シフト量だけシフトさせるマスクパターンを生成し、以降、クロックが入力される度に１位相ずつシフトさせるマスクパターンを生成するマスクパターン生成手段と、
前記マスクパターン生成手段で生成された前記設定された位相シフト量だけシフトさせるマスクパターンで、任意の初期状態を表すデータをマスクして１Ｂｉｔの符号を得て、以降、前記１位相ずつシフトさせるマスクパターンを用いて順次１Ｂｉｔずつ符号を得るマスク手段と、
を備えたことを特徴とする請求項２に記載の符号発生装置。
【請求項４】
生成多項式により固定される第１マスク変換行列と符号発生器の状態を表す状態ベクトルとの積を求める第１演算手段と、
位相シフトと符号発生のいずれか一方を指示するモードに応じて前記第１演算手段の出力と前記状態ベクトルとのいずれか一方を選択する第１セレクタと、
生成多項式により固定される第２マスク変換行列と第１セレクタ出力との積を求める第２演算手段と、
位相シフトと符号発生のいずれか一方を指示するモードおよびシフトデータのＭＳＢに応じて前記第１セレクタか、前記第２演算手段の出力のいずれか一方を選択し、新たな状態ベクトルとする第２セレクタと、
を備えたことを特徴とする符号発生装置。
【請求項５】
前記状態ベクトルは、セレクタを介して位相の異なる符号をシフトさせる複数のシフトレジスタに接続されることを特徴とする請求項４に記載の符号発生装置。
【請求項６】
前記第１マスク変換行列は、前記第２マスク変換行列による位相シフト処理の２倍の位相シフトが可能なマスクパターンに基づいて特定することを特徴とする請求項４または５に記載の符号発生装置。
【請求項７】
さらに、前記第１マスク変換行列は、
生成多項式ｆ（ｘ）＝ｇnｘn＋ｇn-1ｘn-1＋ｇn-2ｘn-2＋…＋ｇ0ｘ0で、かつｎが偶数の場合、
【数１４】
0003618554.tif 000031
とし、
生成多項式ｆ（ｘ）＝ｇnｘn＋ｇn-1ｘn-1＋ｇn-2ｘn-2＋…＋ｇ0ｘ0で、かつｎが奇数の場合、
【数１５】
0003618554.tif 000032
とすることを特徴とする請求項６に記載の符号発生装置。
【請求項８】
生成多項式により固定される第１マスク変換行列と符号発生器の状態を表す状態ベクトルとの積を求める第１の演算ステップと、
位相シフトと符号発生のいずれか一方を指示するモードに応じて、前記第１の演算ステップによる演算結果と前記状態ベクトルのいずれか一方を選択する第１の選択ステップと、
生成多項式により固定される第２マスク変換行列と前記第１の選択ステップによる選択結果との積を求める第２の演算ステップと、
位相シフトと符号発生のいずれか一方を指示するモードおよびシフトデータのＭＳＢに応じて、前記第１の選択ステップによる選択結果と前記第２の演算ステップによる演算結果のいずれか一方を選択し、その選択結果を新たな状態ベクトルとする第２の選択ステップと、
を含み、
さらに、前記第１マスク変換行列は、前記第２マスク変換行列による位相シフト処理の２倍の位相シフトが可能なマスクパターンに基づいて特定される行列とし、
前記第１マスク変換行列および前記第２マスク変換行列の組み合わせによって、任意の位相シフト処理を行うことを特徴とする符号発生方法。
【請求項９】
さらに、前記第１マスク変換行列として、
生成多項式ｆ（ｘ）＝ｇｎｘｎ＋ｇｎ−１ｘｎ−１＋ｇｎ−２ｘｎ−２＋…＋ｇ０ｘ０で、かつｎが偶数の場合は、
【数１６】
0003618554.tif 000033
を用い、
生成多項式ｆ（ｘ）＝ｇｎｘｎ＋ｇｎ−１ｘｎ−１＋ｇｎ−２ｘｎ−２＋…＋ｇ０ｘ０で、かつｎが奇数の場合は、
【数１７】
0003618554.tif 000034
を用いることを特徴とする請求項８に記載の符号発生方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、符号発生方法および符号発生装置に関し、詳細には、Ｍ系列、ＧＯＬＤ系列などの符号系列を発生する符号発生方法および符号発生装置に関するものである。
【０００２】
【従来の技術】
近年、移動体通信において、チャネル容量が多いことからＣＤＭＡ（Ｃｏｄｅ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ａｃｃｅｓｓ）  方式が次世代通信方式として注目されている。ＣＤＭＡ方式では各チャネルを分離するためにチャネル毎に異なるＰＮ系列が用いられ、このＰＮ系列にはＭ系列（ｍａｘｉｍｕｍ−ｌｅｎｇｔｈ  ｓｅｑｕｅｎｃｅ；最大周期系列）やＭ系列より生成されるＧＯＬＤ系列等が頻繁に用いられている。
【０００３】
しかしながら、このＭ系列の周期が長い場合は、任意に位相シフトした系列を生成するために膨大な演算処理を必要とする。このため、高速で、かつ、少ないメモリ量および回路規模で位相シフトの演算を行う方法を確立することは極めて重要なことである。任意にシフトしたＭ系列の生成法として、マスクパターンによりＭ系列をシフトさせることができるが、マスクパターンの生成には膨大な演算処理が必要となる。
【０００４】
この種のＭ系列生成装置として、たとえば、特開平７−２９７６８５号公報、同８−１８５５０号公報がある。
【０００５】
まず、図２４を参照して特開平７−２９７６８５号公報開示の技術について説明する。図２４には上記特開平７−２９７６８５号公報の符号発生装置が開示されている。図２４に示した符号発生装置は、ＰＮ系列を生成するＰＮ生成器１０１、該ＰＮ生成器１０１から出力されるＰＮ系列をＰＮマスク変換器１０２から出力されるＰＮマスクデータでマスクしてから出力するマスク回路１０３、該マスク回路１０３にＰＮマスクデータを供給するＰＮマスク変換器１０２を備えている。
【０００６】
つづいて、上記ＰＮマスク変換器１０２について図２５を用いて説明する。図２５はＰＮマスク変換器１０２のマスク変換方法について説明するフローチャートであり、図２６はＭ，ＬＳＢの変化に対応するｍ，位相の変化を示している。図２５、図２６において、初期のマスクパターンをｋシフトのｍｋ  とし、ｍｋ  からさらに１００シフトしたマスクパターンＭｌ  １００  ｍｋ  ＝ｍｋ＋１００  を求める。シフト量Ｌ＝１００＝１１００１００ｂ（ｂは２進）、Ｍｌ  は１シフトする行列、１ステップはループの１周に対応する。図２５では、シフト量の１１００１００ｂを右シフトさせながらＬＳＢを取り出し、ＬＳＢ＝１の場合にｍ←Ｍｍを実行する。
【０００７】
具体的には、まずシフト量が０より大きく（ステップＳ１０１、Ｙｅｓルート）、かつ、シフト量のＬＳＢが０の場合（ステップＳ１０２、Ｙｅｓルート）、Ｍｍをｍに挿入して（ステップＳ１０３）、シフト量を右にシフトする操作が実施される（ステップＳ１０４）。またシフト量のＬＳＢが０以外の場合には（ステップＳ１０２、Ｎｏルート）、ステップＳ１０４においてシフト量を右にシフトする操作が実施される。
【０００８】
その後、シフト量が０より大きな場合は（ステップＳ１０５、Ｙｅｓルート）、Ｍ←ＭＭの処理が実施される（ステップＳ１０６）。またシフト量が０の場合には（ステップＳ１０５、Ｎｏルート）、そのまま処理はステップＳ１０１に戻る。なお、ステップＳ１０１においてシフト量が０の場合には、マスクパターンがマスク回路１０３へ供給される。
【０００９】
つぎに、図２７を参照して特開平８−１８５５０号公報に開示された技術について説明する。図２７には特開平８−１８５５０号公報による符号発生装置が示されている。図２７に示した符号発生装置は、レジスタ２０１、演算回路２０２、メモリ２０３、スイッチ２０４、および、制御回路２０５を備えている。
【００１０】
図２７に示したように、符号発生装置に、ｎビットの符号を保持するレジスタ２０１と、このレジスタ２０１に対して行列演算を施す演算回路２０２とを設けることで、その演算結果をレジスタ２０１に帰還することにより、逐次的に符号系列を発生する演算回路２０２の行列を、メモリ２０３とスイッチ２０４とにより変更して繰り返し用いて所望の符号系列を発生させるものである。
【００１１】
【発明が解決しようとする課題】
ところが、上記特開平７−２９７６８５号公報に開示の符号発生装置では、汎用の行列×ベクトルの演算が必要となり、ハードウェアにより１ステップで行うには回路規模が大きくなる。また、ソフトで実現するにはｎステップが必要であり、処理時間が長くなるという問題点があった。さらに、上記特開平７−２９７６８５号公報に開示の符号発生装置では、ＰＮ生成器１０１や行列×行列の演算が必要になることから、回路規模が大きくなるという問題点もあった。
【００１２】
また、特開平８−１８５５０号公報開示の符号発生装置では、ＲＯＭ（メモリ２０３）が必要となることから、回路規模が大きくなるとともに、汎用の行列×ベクトルの演算回路２０２が必要となることから、回路規模が大きくなり、さらに、演算にｎ２  ステップ数が必要となってステップ数が多くなることから、処理時間が長くなるという問題点があった。
【００１３】
本発明は、上述した従来の問題を解消するため、マスクパターンの高速生成と回路の小型化を実現することが可能な符号生成方法および符号発生装置を得ることを目的とする。
【００１４】
また、本発明は、マスクパターンの計算とＭ系列の生成法の類似性に着目し、マスクパターンを用いずに直接シフトレジスタの初期状態を生成することが可能な符号発生装置を得ることを目的とする。
【００１５】
【課題を解決するための手段】
上述した課題を解決し、目的を達成するため、この発明にかかる符号発生装置は、生成多項式により固定される第１マスク変換行列と変換前のマスクベクトルとの積で新たなマスクベクトルを求める第１ステップと、シフト量データのＭＳＢがゼロでない場合に、生成多項式により固定される第２マスク変換行列と前記第１ステップで求めたマスクベクトルとの積で新たなマスクベクトルを求める第２ステップと、前記シフト量データをＭＳＢ側へシフトする第３ステップと、前記第１ステップと前記第２ステップと前記第３ステップを指定回数繰り返した後にマスクベクトルに基づくマスクパターンを出力する第４ステップと、を含んだものである。
【００１６】
この発明によれば、生成多項式により固定される第１マスク変換行列と変換前のマスクベクトルとの積で新たなマスクベクトルを求め、シフト量データのＭＳＢがゼロでない場合に、生成多項式により固定される第２マスク変換行列とマスクベクトルとの積で新たなマスクベクトルを求め、シフト量データをＭＳＢ側へシフトし、上記各ステップを指定回数繰り返した後にマスクベクトルに基づくマスクパターンを出力するので、マスクパターンを高速に生成することができ、これにより、高速で小型の回路を実現することが可能となる。
【００１７】
つぎの発明にかかる符号発生装置は、生成多項式により固定される第１マスク変換行列と変換前のマスクベクトルとの積で新たなマスクベクトルを求め、シフト量データのＭＳＢがゼロでない場合に、生成多項式により固定される第２マスク変換行列と前記マスクベクトルとの積で新たなマスクベクトルを求める演算手段と、前記シフト量データをＭＳＢ側へシフトするシフト手段と、前記演算手段と前記シフト手段を指定回数動作させた後にマスクベクトルに基づくマスクパターンを出力する出力手段と、を備えたものである。
【００１８】
この発明によれば、演算手段により生成多項式により固定される第１マスク変換行列と変換前のマスクベクトルとの積で新たなマスクベクトルを求め、シフト量データのＭＳＢがゼロでない場合に、生成多項式により固定される第２マスク変換行列とマスクベクトルとの積で新たなマスクベクトルを求め、シフト手段によりシフト量データをＭＳＢ側へシフトし、出力手段により上記演算手段とシフト手段を指定回数動作させた後にマスクベクトルに基づくマスクパターンを出力するようにしたので、マスクパターンを高速に生成することができ、これにより、高速で小型の回路を実現することが可能となる。
【００１９】
つぎの発明にかかる符号発生装置は、前記演算手段と前記シフト手段と前記出力手段とを用いて、任意の初期状態を表すデータを、設定された位相シフト量だけシフトさせるマスクパターンを生成し、以降、クロックが入力される度に１位相ずつシフトさせるマスクパターンを生成するマスクパターン生成手段と、前記マスクパターン生成手段で生成された前記設定された位相シフト量だけシフトさせるマスクパターンで、任意の初期状態を表すデータをマスクして１Ｂｉｔの符号を得て、以降、前記１位相ずつシフトさせるマスクパターンを用いて順次１Ｂｉｔずつ符号を得るマスク手段と、を備えたものである。
【００２０】
この発明によれば、マスクパターンを生成して、初期状態をマスクすることによりシフトを行うようにしたので、マスクパターンに応じて符号が生成され、専用の符号発生器が不要となることから、回路規模の削減を図ることが可能となる。
【００２１】
つぎの発明にかかる符号発生装置は、生成多項式により固定される第１マスク変換行列と符号発生器の状態を表す状態ベクトルとの積を求める第１演算手段と、位相シフトと符号発生のいずれか一方を指示するモードに応じて前記第１演算手段の出力と前記状態ベクトルとのいずれか一方を選択する第１セレクタと、生成多項式により固定される第２マスク変換行列と第１セレクタ出力との積を求める第２演算手段と、位相シフトと符号発生のいずれか一方を指示するモードおよびシフトデータのＭＳＢに応じて前記第１セレクタか、前記第２演算手段の出力のいずれか一方を選択し、新たな状態ベクトルとする第２セレクタと、を備えたものである。
【００２２】
この発明によれば、第１演算手段により生成多項式により固定される第１マスク変換行列と符号発生器の状態を表す状態ベクトルとの積を求め、第１セレクタにより位相シフトと符号発生のいずれか一方を指示するモードに応じて第１演算手段の出力と状態ベクトルとのいずれか一方を選択し、第２演算手段により生成多項式により固定される第２マスク変換行列と第１セレクタ出力との積を求め、第２セレクタにより位相シフトと符号発生のいずれか一方を指示するモードおよびシフトデータのＭＳＢに応じて第１セレクタか、第２演算手段の出力のいずれか一方を選択し、新たな状態ベクトルとするようにしたので、簡単な構成でマスクパターンを用いず、直接に符号発生装置としての初期状態を生成すること、および符号を生成することが可能となる。
【００２３】
つぎの発明にかかる符号発生装置において、前記状態ベクトルは、セレクタを介して位相の異なる符号をシフトさせる複数のシフトレジスタに接続されるものである。
【００２４】
この発明によれば、状態ベクトルを、セレクタを介して位相の異なる符号をシフトさせる複数のシフトレジスタに接続させたので、一つの回路構成で符号発生を行うだけで、マスクを用いなくても、異なる位相の符号を多数得ることが可能となる。
【００２５】
つぎの発明にかかる符号発生装置おいて、前記第１マスク変換行列は、前記第２マスク変換行列による位相シフト処理の２倍の位相シフトが可能なマスクパターンに基づいて特定することを特徴とする。
【００２６】
この発明によれば、上記第１マスク変換行列および第２マスク変換行列のみを用いて位相シフト処理を行う構成としたため、マスクパターンを計算せずに、回路の状態を直接求めることができる。
【００２７】
つぎの発明にかかる符号発生装置は、さらに、前記第１マスク変換行列は、生成多項式ｆ（ｘ）＝ｇｎｘｎ＋ｇｎ−１ｘｎ−１＋ｇｎ−２ｘｎ−２＋…＋ｇ０ｘ０で、かつｎが偶数の場合、
【数１８】
0003618554.tif 000002
とし、生成多項式ｆ（ｘ）＝ｇｎｘｎ＋ｇｎ−１ｘｎ−１＋ｇｎ−２ｘｎ−２＋…＋ｇ０ｘ０で、かつｎが奇数の場合、
【数１９】
0003618554.tif 000003
とすることを特徴とする。
【００２８】
この発明によれば、特定構造を有する第１のマスク変換行列を用いることで設計が容易になり、さらに、回路規模を小さくすることができる。
【００２９】
つぎの発明にかかる符号発生方法は、生成多項式により固定される第１マスク変換行列と符号発生器の状態を表す状態ベクトルとの積を求める第１の演算ステップと、位相シフトと符号発生のいずれか一方を指示するモードに応じて、前記第１の演算ステップによる演算結果と前記状態ベクトルのいずれか一方を選択する第１の選択ステップと、生成多項式により固定される第２マスク変換行列と前記第１の選択ステップによる選択結果との積を求める第２の演算ステップと、位相シフトと符号発生のいずれか一方を指示するモードおよびシフトデータのＭＳＢに応じて、前記第１の選択ステップによる選択結果と前記第２の演算ステップによる演算結果のいずれか一方を選択し、その選択結果を新たな状態ベクトルとする第２の選択ステップと、を含み、さらに、前記第１マスク変換行列は、前記第２マスク変換行列による位相シフト処理の２倍の位相シフトが可能なマスクパターンに基づいて特定される行列とし、前記第１マスク変換行列および前記第２マスク変換行列の組み合わせによって、任意の位相シフト処理を行うことを特徴とする。
【００３０】
この発明によれば、上記第１マスク変換行列および第２マスク変換行列のみを用いて位相シフト処理を行うこととしたため、マスクパターンを計算せずに、回路の状態を直接求めることができる。
【００３１】
つぎの発明にかかる符号発生方法において、さらに、前記第１マスク変換行列としては、生成多項式ｆ（ｘ）＝ｇｎｘｎ＋ｇｎ−１ｘｎ−１＋ｇｎ−２ｘｎ−２＋…＋ｇ０ｘ０で、かつｎが偶数の場合、
【数２０】
0003618554.tif 000004
を用い、生成多項式ｆ（ｘ）＝ｇｎｘｎ＋ｇｎ−１ｘｎ−１＋ｇｎ−２ｘｎ−２＋…＋ｇ０ｘ０で、かつｎが奇数の場合は、
【数２１】
0003618554.tif 000005
を用いることを特徴とする。
【００３２】
この発明によれば、特定構造を有する第１のマスク変換行列を用いることで設計が容易になり、さらに、回路規模を小さくすることができる。
【００３３】
【発明の実施の形態】
以下に添付図面を参照して、この発明にかかる符号発生方法および符号発生装置の好適な実施の形態を詳細に説明する。
【００３４】
実施の形態１．
まず、本実施の形態の説明に入る前に、マスクパターンによる任意位相のＭ系列の生成原理について一般的に用いられているものを説明する。ここでは、符号発生装置の一例としてＭ系列発生器を例に挙げる。
【００３５】
（Ｍ系列の生成原理）
一例として特性多項式  ｆ（ｘ）  ＝  ｘ４  ＋  ｘ３  ＋  １  のＭ系列をとりあげる。図１に特性多項式  ｆ（ｘ）  ＝  ｘ４  ＋  ｘ３  ＋  １  のＭ系列を発生するＭ系列発生器を示す。図１に示した符号発生器は、ＥＸ−ＯＲ１１と４段のシフトレジスタ１２とを備えている。特性多項式の次数が４であるので、シフトレジスタ１２の段数は４となる。また、ｘ４を除いたｘ３と１  ＝  ｘ０が帰還タップの位置である３  と０  を示している。
【００３６】
図１に示すＭ系列発生器の各フリップフロップＤ０〜Ｄ３の状態を下記の表１に示す。特性多項式の次数が４  であるのでＭ系列の周期は２４−１  ＝  １５  となり、表１のｓｔｅｐ１４のつぎはｓｔｅｐ０  から繰り返し同じ動作となる。表１の場合はすべて１の場合を初期値としているが、Ｍ系列発生器の状態はすべて０の場合以外のすべての状態をとるので、初期値はすべて０  以外のパターンなら任意に設定することができる。
【００３７】
【表１】
0003618554.tif 000006
【００３８】
（シフトしたＭ系列の生成）
まず、Ｍ系列の性質について説明する。図１のＭ系列発生器より生成されるＭ系列は図２に示すようになり、このＭ系列はＭ系列発生器の動作を考慮すると図３に示すような性質があることがわかる。このように上記の演算を左右に動かした場合に常に入力と出力は正しくなっている。ここで  ｘｎ  を組み合わせて書くと図４に示すようになる。
【００３９】
以下の演算は、ＧＦ（２）上の演算であり、演算結果のモジュロ２を取ることと等価である。
ｘ  ｎ＋４  ＝  ｘ  ｎ＋３  ＋  ｘ  ｎ
ｘ  ｎ＋４  ＋  ｘ  ｎ＋３  ＋  ｘ  ｎ  ＝  ０（ＧＦ（２）上の演算では、＋と−は同じ）
ｘ  ｎ  （ｘ  ４  ＋  ｘ３  ＋  １）  ＝  ０
ここで、特性多項式ｆ（ｘ）  ＝  ｘ４  ＋ｘ３  ＋  １  が現れている。
より一般には、
Ｇ（ｘ）ｆ（ｘ）  ＝  ０  （  Ｇ（ｘ）は任意の多項式  ）
であり、式（１）が成立する。
【００４０】
ここで、例えば以下の式を考える。
0003618554.tif 000007
となり、図５に示す関係があることが分かる。このように特性多項式ｆ（ｘ）に掛けるＧ（ｘ）によりＭ系列の各位相の関係を計算することができる。
【００４１】
つぎにｘ  ｍ  をｆ（ｘ）で割った剰余Ｒ（Ｘ）について考えると、ｘ  ｍ  をｆ（ｘ）で割った商をＱ（ｘ）とすると、以下の式が成り立つ。
ｘ  ｍ  ＝  Ｑ（ｘ）ｆ（ｘ）  ＋  Ｒ（ｘ）
式（１）より
Ｑ（ｘ）ｆ（ｘ）  ＝  ０
なので、
ｘ  ｍ  ＝  Ｒ（ｘ）
となり、式（２）が成立する。
【００４２】
つぎに、マスクパターンによるＭ系列のシフトについて説明する。Ｍ系列発生器の動作を示した表１にｘ  ｎ  を合わせて表示すると表２となる。
【００４３】
【表２】
0003618554.tif 000008
【００４４】
ここで、式（２）よりｘ  ｍ  ＝  Ｒ（ｘ）であり、Ｒ（ｘ）はｘ  ｍ  をｆ（ｘ）で割った剰余であるからその次数はｆ（ｘ）の次数より小さい。すなわち、、ｆ（ｘ）  ＝  ｘ４  ＋  ｘ  ３  ＋  １  の場合はＲ（ｘ）＝ｒ３  ｘ３  ＋  ｒ２  ｘ２  ＋  ｒ１ｘ  ＋  ｒ０  と表わすことができる。これより以下の式が成り立つ。
ｘｍ  ＝ｒ３ｘ３  ＋  ｒ２ｘ２  ＋  ｒ１ｘ  ＋  ｒ０  
ｘｎ＋ｍ  ＝ｒ３ｘｎ＋３  ＋  ｒ３ｘ  ｎ＋２  ＋  ｒ３ｘ  ｎ＋１  ＋  ｒ３ｘ  ｎ  
【００４５】
表２と見比べるとｘ  ｎ＋３，  ｘ  ｎ＋２，  ｘ  ｎ＋１，  ｘ  ｎはＭ系列発生器に現れている。このため、図７には、図１に示したＭ系列発生器に加算器１３を付加した構成が示されている。図７に示すように各タップの出力をマスクパターンにしたがって合成できる構成にすることによって、任意の位相シフトを行ったＭ系列を得ることができる。
ｏｕｔ２  ＝ｒ０Ｄ０  ＋  ｒ１Ｄ１  ＋  ｒ２Ｄ２  ＋  ｒ３Ｄ３  
を計算することによりシフトしたＭ系列を得る。より一般には、位相の異なるＭ系列が次数個あるならそれらの線形結合ですべての位相を表現することができる。
【００４６】
つぎに、マスクパターン生成法について説明する。Ｌ位相シフトしたＭ系列を生成するマスクパターンを得るには、「ｘ  Ｌ  ÷特性多項式ｆ（ｘ）」を行い、剰余  Ｒ（ｘ）  を求めればよい。特性多項式  ｆ（ｘ）  ＝  ｘ４＋ｘ３＋１  を例に５位相シフトする場合のマスクパターンを求めるには「ｘ５÷（ｘ４＋ｘ３＋１）」の剰余を求める。以下に  「ｘ５  ÷（ｘ４＋ｘ３＋１）」の計算を示す。
【００４７】
【数１】
0003618554.tif 000009
【００４８】
計算の結果得られた剰余  Ｒ（ｘ）  ＝  ｘ３＋ｘ１＋１  よりマスクパターンは以下のようにになる。
（ｒ３，ｒ２，ｒ１，ｒ０  ）＝  （１，０，１，１）
【００４９】
このマスクパターンより５シフトしたＭ系列は  Ｄ３＋Ｄ１＋Ｄ０より得られることがわかる。実際に上記のマスクパターンで図７の動作を調べると表３のようになり、ｓｔｅｐ  ｎのＤ０と  ｓｔｅｐ  ｎ−５  のＤ３＋Ｄ１＋Ｄ０が同じであることがわかる。すなわち、Ｄ３＋Ｄ１＋Ｄ０は、Ｄ０に対して  ５  ｓｔｅｐ  未来の出力である。
【００５０】
【表３】
0003618554.tif 000010
【００５１】
つぎに、本実施の形態についての説明に入る。論理演算によりマスクパターンを求める方法について説明する。以下演算はＧＦ（２）  上の演算である。
【００５２】
（アルゴリズム）
Ｌ位相シフトしたＭ系列を生成するマスクパターンを得るには、「ｘ  Ｌ  ÷特性多項式ｆ（ｘ）」を行い、剰余  ＲＬ  （ｘ）  を求めればよい。以下に提案するアルゴリズムを説明する。以後、「ｇ（ｘ）÷ｆ（ｘ）」の剰余  Ｒ（ｘ）  は  Ｒ（ｘ）  ＝Ｒ  ｆ（ｘ）［ｇ（ｘ）］と表わす。また、Ｒ  Ｌ  （ｘ）  ＝Ｒ  ｆ（ｘ）［ｘＬ  ］  とする。
【００５３】
Ｒ０（ｘ）  ＝Ｒ  ｆ（ｘ）［ｘ０  ］  より、
▲１▼  Ｒ０（ｘ）  ＝  １
一般に、
Ｒ  ｆ（ｘ）［ｘ（ｘ）］＝  ｘ（ｘ）  ＋  Ｑｘ（ｘ）  ｆ（ｘ）
Ｒ  ｆ（ｘ）［ｙ（ｘ）］＝  ｙ（ｘ）  ＋  Ｑｙ（ｘ）  ｆ（ｘ）
Ｑｘ（ｘ）  はｘ（ｘ）を  ｆ（ｘ）  で割った商、Ｑｙ（ｘ）  はｙ（ｘ）を  ｆ（ｘ）  で割った商、と表わせるので、
Ｒ  ｆ（ｘ）［ｘ（ｘ）］Ｒ  ｆ（ｘ）［ｙ（ｘ）］＝  ｘ（ｘ）  ｙ（ｘ）  ＋  （  Ｑｘ（ｘ）  ｙ（ｘ）  ＋  Ｑｙ（ｘ）  ｘ（ｘ）  ＋  Ｑｘ（ｘ）Ｑｙ（ｘ）ｆ（ｘ）  ）  ｆ（ｘ）  より、
Ｒ  ｆ（ｘ）［  Ｒ  ｆ（ｘ）［ｘ（ｘ）］  Ｒｆ（ｘ）［ｙ（ｘ）］  ］＝Ｒ  ｆ（ｘ）［ｘ（ｘ）  ｙ（ｘ）］  となり逆も同様に成り立つ。
【００５４】
よって、
▲２▼  Ｒ２ｋ（ｘ）  ＝  Ｒ  ｆ（ｘ）［Ｒｋ  （ｘ）２］
▲３▼  Ｒｋ＋１（ｘ）  ＝Ｒ  ｆ（ｘ）［ｘＲ  ｋ  （ｘ）］
の如く、  式（３）が成立する。
【００５５】
上記式（３）の▲１▼，  ▲２▼，  ▲３▼を組み合わせて任意のＬについてＲ  Ｌ  （ｘ）  を求めることができる。
たとえば  Ｒ１０（ｘ）  を求めると、
Ｒ１０（ｘ）  ＝Ｒ  ｆ（ｘ）［Ｒ５（ｘ）２］            ▲２▼
Ｒ５（ｘ）  ＝  Ｒ  ｆ（ｘ）［ｘＲ４（ｘ）］      ▲３▼
Ｒ４（ｘ）  ＝Ｒｆ（ｘ）［Ｒ２（ｘ）２］                ▲２▼
Ｒ２（ｘ）  ＝Ｒｆ（ｘ）［Ｒ１（ｘ）２］                ▲２▼
Ｒ１（ｘ）  ＝Ｒｆ（ｘ）［ｘＲ０（ｘ）］        ▲３▼
Ｒ０（ｘ）  ＝  １                    ▲１▼
の如く式（４）が成立する。
【００５６】
Ｒ  ｋ  （ｘ）  のｋ  が偶数なら式▲２▼、奇数なら式▲３▼を順次おこないｋ＝０  となるまで行う。ｋ＝０  なら式▲１▼となる。式（４）を逆から計算すればつぎのようにＲ１０（ｘ）を求めることができる。
Ｒ１０（ｘ）  ＝Ｒ  ｆ（ｘ）［Ｒｆ（ｘ）［ｘＲ  ｆ（ｘ）［Ｒｆ（ｘ）［Ｒｆ（ｘ）［ｘＲ０（ｘ）］２］２］］２］
式（４）の演算は、１０  ＝５  ×２  、５＝４＋１  、４＝２  ×２  、２＝１  ×２  、より１０＝（（１×２）×２＋１）×２  と展開しているが、この展開はＬを２進数に表わすことにより簡単に求められる。
Ｌ  ＝  ｌ０  ＋  ２ｌ１  ＋  ２２ｌ２  ＋  …  ＋  ２ｎ−２ｌｎ−２  ＋  ２  ｎ−１ｌｎ−１  ＝        （  （  …  （  ｌｎ−１  ×２  ＋  ｌ  ｎ−２  ）  ×２  ＋  …  ＋  ｌ２  ）  ×２  ＋  ｌ１  ）  ×２  ＋  ｌ０
【００５７】
ここで、式▲２▼式▲３▼をまとめＡ  ｆ（ｘ）［ｇ（ｘ）  ，  ｉ  ］  ｉ  ＝  ［１  ，０］  を定義する。以下の式（５）が成立する。
【００５８】
【数２】
0003618554.tif 000011
【００５９】
Ａ  ｆ（ｘ）［ｇ（ｘ）  ，  ｉ  ］  を用いてＲ  Ｌ  （ｘ）  を、以下に示すように式（６）を求めることができる。
Ａ０（ｘ）  ＝  Ｒ０（ｘ）
Ａ  ｋ  （ｘ）  ＝  Ａ  ｆ（ｘ）［Ａｋ−１（ｘ）  ，  ｌｎ−１−ｋ  ］
Ｒ  Ｌ  （ｘ）  ＝  Ａ  ｎ−１（ｘ）
ただし、Ｌ  ＝  ｌ０  ＋  ２ｌ１  ＋  ２２ｌ２  ＋  …  ＋  ２ｎ−２ｌｎ−２  ＋  ２  ｎ−１ｌｎ−１  
上記式に示すように式（６）の演算をｎ  （ｆ（ｘ）の次数）回行うことによりＲ  Ｌ  （ｘ）  を求めることができる。
【００６０】
つづいてハードウェアによる実現方法について説明する。マスクパターン生成法をハードウェアにより実現するには上式（６）をハードウェア化すればよい。ここでは一例として特性多項式  ｆ（ｘ）  ＝  ｘ７  ＋  ｘ３  ＋  １  の場合を取り上げる。
【００６１】
まず、２乗回路から説明する。一般に  ｇ（ｘ）  ＝  ｘ  ｋ  ＋ｘｊ  ＋ｘｉ  ＋  …  ＋１  であれば、ｇ（ｘ）２  ＝  ｘ２ｋ  ＋ｘ２ｊ＋ｘ２ｉ＋  …  ＋１  と簡単に求められる。ｆ（ｘ）の次数が７であるから式（６）の入力と出力の多項式の次数は６である。ここで、Ａ（ｘ）を、
Ａ（ｘ）  ＝  ａ６ｘ６  ＋  ａ５ｘ５  ＋  ａ４ｘ４  ＋  ａ３ｘ３  ＋  ａ２ｘ２  ＋  ａ１ｘ  ＋  ａ０
と定義すると、
Ａ２（ｘ）  ＝  ａ６ｘ１２  ＋  ａ５ｘ１０  ＋  ａ４ｘ８  ＋  ａ３ｘ６  ＋  ａ２ｘ４  ＋  ａ１ｘ２  ＋  ａ０
と求められる。
【００６２】
Ｒ  ｆ（ｘ）  ［Ａ２（ｘ）］を求めると以下のようになる。
Ｒ  ｆ（ｘ）［Ａ２（ｘ）］＝Ｒ  ｆ（ｘ）［ａ６ｘ１２  ＋  ａ５ｘ１０  ＋  ａ４ｘ８  ＋  ａ３ｘ６  ＋  ａ２ｘ４  ＋  ａ１ｘ２  ＋  ａ０］    ＝ａ６Ｒ  ｆ（ｘ）［ｘ１２］＋  ａ５Ｒｆ（ｘ）［ｘ１０］＋  ａ４Ｒｆ（ｘ）［ｘ８］  ＋  ａ３ｘ６  ＋  ａ２ｘ４  ＋  ａ１ｘ２  ＋  ａ０
ｆ（ｘ）は７次であるから６次以下の項については剰余を求める必要はない。
Ｒ  ｆ（ｘ）［ｘ１２］＝ｘ５  ＋  ｘ４  ＋  ｘ
Ｒ  ｆ（ｘ）［ｘ１０］＝ｘ６  ＋  ｘ３  
Ｒ  ｆ（ｘ）［ｘ８  ］＝ｘ４  ＋  ｘ
より、
Ｒ  ｆ（ｘ）  ［Ａ２（ｘ）］＝（ａ５  ＋  ａ３）  ｘ６  ＋  ａ６ｘ５  ＋  （ａ６  ＋  ａ４  ＋  ａ２）  ｘ４  ＋  ａ５ｘ３  ＋  ａ１ｘ２  ＋  （ａ６  ＋  ａ４）  ｘ  ＋  ａ０  
これが、式（７）となる。
【００６３】
つぎに、Ｒ  ｆ（ｘ）［ｘＡ２（ｘ）］を求める。Ｒ  ｆ（ｘ）［Ａ２（ｘ）］  ＝  ｂ６ｘ６  ＋  ｂ５ｘ５  ＋  ｂ４ｘ４  ＋  ｂ３ｘ３  ＋  ｂ２ｘ２  ＋  ｂ１ｘ  ＋  ｂ０  とする。
ただし、式（７）より、
ｂ６＝ａ５  ＋  ａ３、ｂ５＝ａ６  
ｂ４＝ａ６  ＋  ａ４  ＋  ａ２  
ｂ３＝ａ５  
ｂ２＝ａ１  
ｂ１＝ａ６  ＋  ａ４
ｂ０＝ａ０  
0003618554.tif 000012
Ｒ  ｆ（ｘ）［ｘ７］＝ｘ３  ＋  １  より、
Ｒ  ｆ（ｘ）［ｘＡ２（ｘ）］＝ｂ５ｘ６  ＋  ｂ４ｘ５  ＋  ｂ３ｘ４  ＋  （ｂ２  ＋  ｂ６）  ｘ３  ＋  ｂ１ｘ２  ＋  ｂ０ｘ  ＋  ｂ６
の如く式（８）が成立する。
【００６４】
式（７）、式（８）より式（５）をハードウェア化すると図８に示すように簡単な構成で実現することができる。図８に示した演算器は、ＥＸ−ＯＲ、セレクタなどにより構成される。図８に示した回路は、以下の式をハードウェア化したものである。
【００６５】
【数３】
0003618554.tif 000013
【００６６】
マスクパターンを生成するには式（６）に示すように式（５）を繰り返せばよく、ハードウェアにすると図９に示すように構成すればよい。図９には、マスクパターン生成回路が示され、２１は図８の演算器を示し、２２，２３はシフトレジスタをそれぞれ示す。なお、図９の変形例として、図１０のように並列接続させた構成にしてもよい。図１０には、マスクパターン生成回路２１Ａ〜２１Ｇが直列に接続されている。
【００６７】
図９の構成は特性多項式の次数ステップでマスクパターンを得ることができるが、図１０のように構成すれば、さらに高速にマスクパターンを得ることができる。ただし、特性多項式の次数が大きな場合には図９に比べ図１０の構成は回路規模が非常に大きなものとなる。論理圧縮することにより図１０の構成を若干小さくすることは可能である。
【００６８】
つづいて、マスクパターン生成器の動作について説明する。まず、図９の回路の動作を説明する。Ｌ＝１００の場合の動作を表４に示す。１００を２進数で表わすと１１００１００であるからｉ  にこれをＭＳＢから入力する。フリップフロップの出力であるＤ６〜Ｄ０と  Ａ  ｆ（ｘ）［ｇ（ｘ）  ，  ｉ］回路の内部にあるｂ６〜ｂ０を示す。特性多項式ｆ（ｘ）  ＝  ｘ７  ＋  ｘ３  ＋  １の次数は７であるからｓｔｅｐ７  でマスクパターン１１１０１１１を得ることができる。
【００６９】
【表４】
0003618554.tif 000014
【００７０】
ここで、従来例として挙げた特開平７−２９７６８５号公報開示の技術との対応を考え、具体的な動作の流れについて説明する。図１１は本実施の形態１による動作を説明するフローチャートであり、図１２はＭＳＢの変化に対応するｍ、位相の変化を説明する図である。
【００７１】
本実施の形態１では、まずカウンタ値が０より大きければ（ステップＳ１、Ｙｅｓルート）、ｍ←Ｐｍの演算が行われる（ステップＳ２）。この場合には、シフト量のＭＳＢが０でないとき（ステップＳ３、Ｎｏルート）、さらにｍ←Ａｍの演算が行われ（ステップＳ４）、シフト量は左にシフトの操作となり（ステップＳ５）、カウント値は１引かれる（ステップＳ６）。なお、シフト量のＭＳＢが０のとき（ステップＳ３、Ｙｅｓルート）、ステップＳ４の演算を飛ばしてステップＳ５においてシフト量は左にシフトされ、ステップＳ６においてカウント値を１引く操作となる。この後、処理はステップＳ１に戻る。また、ステップＳ１においてシフト量が０以下の場合には、マスクパターン出力が実施される。
【００７２】
図１２においては、シフト量Ｌ＝１００＝１１００１００ｂ、１ステップはループの１周に対応している。生成多項式の次数を７とすると、Ｍ系列の周期は、２７  −１＝１２７となる。１２７ｋの位相シフトは、０シフトと同じになり、１２８ｋシフトはｋシフトと同じになる。このため、１２８ｋ＋１００＝ｋ＋１００となる。
【００７３】
以上によれば、Ｍ←ＭＭに相当する演算は必要なく、ｍ←Ｐｍの演算はＭ←ＭＭの演算に比べてはるかに小さな回路規模および演算量で実現することができる。従来では、Ｍ←ＭＭの演算を１番目の行ベクトルのみを求め、他の行はそこから計算するようにしているので、演算量は２ｎ−１ステップ必要となっていた。それに比べると、本実施の形態１では、小規模な回路で１ステップで実現することが可能である。なお、ソフトウェアで実現する場合にも、行列とベクトルの積なので、ｎステップで実現することが可能である。
【００７４】
とくに、従来、原理的に行列を固定にできない分、本実施の形態１では、行列Ａや行列Ｐの演算は、生成多項式により固定にできるので、ハードウェアを非常に小さい規模で設けることが可能となる。
【００７５】
実施の形態２．
さて、前述の実施の形態１によるマスクパターン生成法を用いれば、Ｍ系列発生器の位相を任意にシフトすることができるが、以下に説明する実施の形態２では、任意の初期状態より任意に位相シフトしたＭ系列の生成について説明する。上述のようなマスクパターン生成法を用いれば、Ｍ系列発生器の位相を任意にシフトできるが、ここではＭ系列発生器とマスクパターン生成回路を共用化し、ハードウェア規模を縮小した回路構成を説明する。
【００７６】
Ｌ位相シフトするマスクパターン  Ｒ（ｘ）  が求まっているとすると、Ｌ＋１位相シフトしたマスクパターンはＲ  ｆ（ｘ）［ｘＲ（ｘ）］  で求めることができる。この回路はすでにマスクパターン生成回路に組み込まれているので容易に実現できる。そこで、図８に示したＡ  ｆ（ｘ）［ｇ（ｘ）  ，  ｉ］を実現した回路を図１３に示すように改良する。図１３に示した回路は、ＥＸ−ＯＲ、セレクタにより構成される。この回路を式で表現すると、つぎのようになる。
【００７７】
【数４】
0003618554.tif 000015
【００７８】
ｍｏｄｅ  ＝  ０  の場合は前記マスクパターン生成回路と同じ動作をし、ｍｏｄｅ  ＝  １の場合は１位相シフトしたマスクパターンを求める。
【００７９】
図１３に示した回路をマスクパターン生成回路として用い、これによりＭ系列を生成するＭ系列発生器を構成する。図１４に任意の初期状態から任意にシフトしたＭ系列を生成するＭ系列発生器を示す。図１４に示したＭ系列発生器は、図７に示したマスクパターンを生成するマスクパターン生成回路３１、クロックにより初期状態バッファ３３から供給されるデータをマスクして出力するマスク回路３２、初期状態のデータをマスク回路３２に供給する初期状態バッファ３３、クロックによりシフト量データをＭＳＢより取り出すシフト量バッファ、すなわちシフトレジスタ３４、クロックにしたがってマスク回路３２の出力を保持するフリップフロップ３５を備えている。
【００８０】
動作は、まず初期状態バッファ３３にＭ系列の始めのｎ個のデータを書き込み、シフトレジスタ３４に初期状態からのシフト量を書き込む。つぎに、ｍｏｄｅ  ＝  ０でｃｌｋ  をｆ（ｘ）の次数ｎ回入力し、シフトレジスタ３４に設定したシフト量のマスクパターンを生成し、初期状態からシフト量シフトしたＭ系列を１ｂｉｔ得る。つぎに、ｍｏｄｅ  ＝  １としｃｌｋ  を入力する毎に１つシフトしたマスクパターンを生成することにより順次１ｂｉｔずつＭ系列を得ることができる。
【００８１】
マスク回路３２の内部構成を図１５に示す。このマスク回路３２は、ＥＸ−ＯＲとＡＮＤとの組み合わせで構成される。図７に示した構成と同様であるが、初期状態が固定であれば回路を削減できる。特に初期状態に１が一つしか無いような場合には、マスク回路は不必要である。
【００８２】
つぎに動作について説明する。実際に初期状態１１１１１１１  で１００  シフトした場合のＭ系列を生成すると表５に示すようになる。
【００８３】
【表５】
0003618554.tif 000016
【００８４】
ｓｔｅｐ０  〜ｓｔｅｐ６  でマスクパターンを生成しＭｏｄｅ  ＝  ０  とし、表４と同じ動作である。ｓｔｅｐ７  からＭｏｄｅ  ＝  １  としＭ系列生成を始める。実際に特性多項式  ｆ（ｘ）  ＝  ｘ７  ＋  ｘ３  ＋  １  初期状態１１１１１１１  のＭ系列は表６に示すようになり、１００  シフトした場合は０１０１１１であり表５の出力と一致している。
【００８５】
【表６】
0003618554.tif 000017
【００８６】
ここで示した任意にシフトしたＭ系列を生成する回路は、任意にシフトした場合の初期設定に必要な時間が短いのが特徴である。
【００８７】
実施の形態３．
以下に説明する実施の形態３では、マスクパターンを用いずに、論理演算により任意に位相シフトする方法について説明する。シフトしたＭ系列の生成法として、マスクパターンによりＭ系列をシフトさせることができる。この実施の形態３ではマスクパターンを用いないＭ系列の高速シフトの新しいアルゴリズムと、それのハードウェアによる実現方法を示す。以下演算はＧＦ（２）  上の演算である。
【００８８】
まずＭ系列発生回路の行列表示について説明する。論理演算によりマスクパターンを求める方法では、Ａ  ｆ（ｘ）［ｇ（ｘ），ｉ］を定義し、これを用いてマスクパターンを生成し、Ｍ系列の位相シフトを行う方法を提案したが、実用的にはＭ系列を生成するシフトレジスタの初期値を求めたい場合が多く、そのような方法ではマスクパターンの生成とシフトレジスタの初期値の生成の２段階の操作が必要になる。そこでマスクパターンを求めずに直接シフトレジスタの初期値を生成する方法を考える。
【００８９】
図１６は、特性多項式  ｆ（ｘ）  ＝  ｘ４＋ｘ３＋１  のＭ系列発生器であり、４１はＥＸ−ＯＲ、４２はシフトレジスタ、ａ０〜ａ３はそれぞれのタップの出力である。これを行列表示すると以下のようになる。
【００９０】
【数５】
0003618554.tif 000018
【００９１】
初期状態をａ０とすればｎシフトした状態は次式で表わせる。
ａ  ｎ  ＝  Ａｎ  ａ０
一般にｎ段のＬＦＳＲはｎ×ｎの行列を用いて表現できる。行列ＡのようにＭ系列を生成する行列は一つの特性多項式に対して多数存在する。詳細は省くが、ａ  の各要素はそれぞれ異なる位相のＭ系列となるため一つの特性多項式について（２  ｎ  −  ２）Ｐ（ｎ−１）  個存在する。これは、つぎに示すように正則な行列Ｔによって関係づけられる。
Ａ’＝Ｔ−１ＡＴ
【００９２】
つづいてマスクパターンを用いない任意シフトの方法について説明する。一般例の説明では、以下の三つの式よりマスクパターンを求めていたが、初期値を固定とし、マスクパターンを順次進めながらＭ系列を生成できることを考えれば式▲３▼自体がＭ系列を生成することがわかる。
▲１▼    Ｒ０  （ｘ）  ＝  １
▲２▼    Ｒ２ｋ（ｘ）  ＝  Ｒ  ｆ（ｘ）［Ｒｋ  （ｘ）２］
▲３▼    Ｒｋ＋１（ｘ）  ＝  Ｒｆ（ｘ）  ［ｘＲｋ  （ｘ）］
上式▲３▼を回路で表わせば図１７のようになる。図１７に示したＭ系列発生器は、４段のシフトレジスタ４６の２つのレジスタ（Ｄ２  、Ｄ３  ）間に、ＥＸ−ＯＲ４５を接続させた構成である。
【００９３】
先ほどと同様に行列で表わすと、以下のように表され、Ｂ＝  ＡＴ  となっていることがわかる。
【００９４】
【数６】
0003618554.tif 000019
【００９５】
同様に式▲２▼を行列で表わすとつぎのようになる。
【００９６】
【数７】
0003618554.tif 000020
【００９７】
前述の実施の形態１で説明した一般的な方法を行列を用いて説明すると、ｂ０＝  （１，０，０，０）  として、行列Ｂ、Ｃを用いて任意にシフトさせるマスクパターンを作成している。行列Ｂ、Ｃはつぎの演算を行う行列である。
ｂ  ｋ＋１  ＝  Ｂ  ｂ  ｋ  
ｂ  ２ｋ  ＝  Ｃ  ｂ  ｋ  
ｂ０は０シフトするマスクパターンであり、例えば１１シフトするマスクパターンはつぎのように表わされる。
ｂ１１＝Ｂ１１ｂ０
【００９８】
一般的な方法では１１シフトする場合は１１を２進数で表わし１０１１ｂ  であるから１  を（ＢＣ）、０を（Ｃ）としてＭＳＢより順次掛け合わせ、次式（式（９））とする。
（ＢＣ）（ＢＣ）（Ｃ）（ＢＣ）ｂ０
【００９９】
一方、行列Ｂ、Ｃの間にはＢ＝  Ｃ−１Ｂ２  Ｃとなる関係があり、
ＣＢ＝Ｂ２  Ｃが成り立ち、
0003618554.tif 000021
０シフトを２倍シフトしても０シフトなのでＣｂ０＝ｂ０  であり、
（ＢＣ）（ＢＣ）（Ｃ）（ＢＣ）ｂ０＝  Ｂ１１ｂ０
となる。
【０１００】
ここで、一般的な方法では触れなかったが初期値としてｂ０ではなくｂ  ｋ  を用いた場合は、つぎのようになる。
0003618554.tif 000022
Ｍ系列の周期性よりＢ２４＝  Ｂとなる。
【０１０１】
よって、
Ｂ１１Ｃ４ｂｋ  ＝  Ｂ１１  ＋  ｋｂ０＝  Ｂ１１ｂ  ｋ  
であり、初期値によらず１１シフトしたマスクパターンが得られ、このことはシフト量１１によらず一般的に成り立ち、ｂ  ｋ  は０以外のあらゆるパターンを取り得ることによりＣ４  ＝  Ｅであることがわかる。よって、次式（式（１０））が成立する。
（ＢＣ）（ＢＣ）（Ｃ）（ＢＣ）＝  Ｂ１１
【０１０２】
一般に特性多項式の次数がｎの場合はＣｎ  ＝  Ｅである。
ここで、
Ａ  ＝Ｔ−１ＢＴ              式（１１）
となるＴを求めると、例えば以下のようになる。説明は省くがＡ  ＝Ｔ−１ＢＴを満たすＴは多数存在する。
【０１０３】
【数８】
0003618554.tif 000023
【０１０４】
ここで、Ｃに対応してＰを定義する。
Ｐ  ＝Ｔ−１ＣＴ              式（１２）
行列Ｐを用いて１１シフトを行うと、
0003618554.tif 000024
となり１１シフトを行うことができる。一般にはＡ，Ｐ  を求めれば任意にシフトを行うことができ、マスクパターンを計算せずに図１６の回路の状態を直接求めることができる。
【０１０５】
つぎにハードウェアによる実現を例に挙げる。ここで具体的にＰを計算すると式（１２）の行列Ｔの場合は、以下の式となる。
【０１０６】
【数９】
0003618554.tif 000025
【０１０７】
これを回路で表わすとたとえばＥＸ−ＯＲ  ２個で実現できる。Ｔの取り方によってＰは異なる行列となり回路規模も異なってくる。たとえば、Ｔ’＝ＢＴとした場合式（１１）より、
Ａ  ＝Ｔ−１ＢＴ＝（Ｂ−１Ｔ’）−１Ｔ’  ＝  Ｔ’  −１ＢＴ’
となり、Ｔ’  を用いてＰ’  を定義すると、次式となる。
【０１０８】
【数１０】
0003618554.tif 000026
【０１０９】
Ｐ’  を用いてもＰを用いた場合と同様に位相シフトを行うことができるが、Ｐ’  を回路にした場合はＥＸ−ＯＲ  ３個を必要とする。このようにＰによって回路規模が異なるため、回路規模を小さくするＰを求める必要があり、つぎのように設計すると回路規模が小さく、また設計も簡単である。
【０１１０】
たとえば、特性多項式  ｆ（ｘ）  ＝  ｇ４ｘ４  ＋  ｇ３ｘ３  ＋  ｇ２ｘ２  ＋  ｇ１ｘ１  ＋  ｇ０ｘ０とすると、次式が成立する。
【０１１１】
【数１１】
0003618554.tif 000027
【０１１２】
特性多項式  ｆ（ｘ）  ＝  ｇ５ｘ５  ＋  ｇ４ｘ４  ＋  ｇ３ｘ３  ＋  ｇ２ｘ２  ＋  ｇ１ｘ１  ＋  ｇ０ｘ０  の場合は、次式が成立する。
【０１１３】
【数１２】
0003618554.tif 000028
【０１１４】
その結果、比較的小さな回路となり、しかも面倒な計算をせずにＰを求めることができる。
【０１１５】
たとえば特性多項式ｆ（ｘ）  ＝  ｘ７  ＋  ｘ３  ＋  １の場合、次式が成立する。
【０１１６】
【数１３】
0003618554.tif 000029
【０１１７】
この設計法では状態がａ＝  （１  ０  ０  ０  ０  ０  ０  ）Ｔ  の場合を０位相として位相を２倍にする行列Ｐを求めることができる。行列Ａ  によるＭ系列発生器の動作を示した表７を用いて行列Ｐの動作を確認すると、
ｂ  ＝Ｐａとして
ａ  ＝（１  ０  ０  ０  ０  ０  ０  ）Ｔ  ：位相０→ｂ  ＝（１  ０  ０  ０  ０  ０  ０  ）Ｔ  ：位相０
ａ  ＝（０  ０  ０  ０  ０  ０  １  ）Ｔ  ：位相１→ｂ  ＝（０  ０  ０  ０  ０  １  ０  ）Ｔ  ：位相２
ａ  ＝（０  ０  ０  ０  ０  １  ０  ）Ｔ  ：位相２→ｂ  ＝（０  ０  ０  １  ０  ０  ０  ）Ｔ  ：位相４
ａ  ＝（０  ０  ０  ０  １  ０  ０  ）Ｔ  ：位相３→ｂ  ＝（０  １  ０  ０  ０  １  ０  ）Ｔ  ：位相６
ａ  ＝（０  ０  ０  １  ０  ０  ０  ）Ｔ  ：位相４→ｂ  ＝（０  ０  ０  １  ０  ０  １  ）Ｔ  ：位相８
ａ  ＝（０  ０  １  ０  ０  ０  １  ）Ｔ  ：位相５→ｂ  ＝（０  １  ０  ０  １  １  ０  ）Ｔ  ：位相１０
ａ  ＝（０  １  ０  ０  ０  １  ０  ）Ｔ  ：位相６→ｂ  ＝（０  ０  １  １  ０  ０  ０  ）Ｔ  ：位相１２
となり、独立な７種類（次数種類）の状態ａに対して位相が２倍になっているのでこの行列Ｐは正しいことがわかる。
【０１１８】
【表７】
0003618554.tif 000030
【０１１９】
行列Ｐ、行列Ａを回路で表わすとそれぞれ図１８、図１９になる。図１８、図１９にそれぞれ示した行列Ｐ，行列Ａの演算を行う回路は、それぞれＥＸ−ＯＲで構成される。図１８では、ｂ＝Ｐａを実現し、図１９はｃ＝Ａｂを実現する。図１８、図１９を用いて位相シフトおよびＭ系列発生器を構成すると、例えば図２０になる。
【０１２０】
図２０の構成は特性多項式の次数ステップでＭ系列発生器の初期値を得ることができ、モードを切り換えてＭ系列を生成する。図２０に示したＭ系列発生器は、図１８に示した行列Ｐを実現する回路５１、図１９に示した行列Ａを実現する回路５２、Ｄフリップフロップ５３、シフトレジスタ５４、セレクタ５５，５６、ＮＡＮＤ５７を備えている。
【０１２１】
なお、図２０の回路を図２１のように変形すれば、さらに高速にＭ系列発生器の初期値を得ることができる。
【０１２２】
図１４で示した回路と比べマスク回路が不要となり、回路削減されている。さらに、図２０の場合はＭ系列発生器の初期状態が次数ステップで得られるので一般的な構成よりも半分のステップ数で他のＭ系列発生器等に初期状態をロードすることが可能となる。
【０１２３】
一例として図２０の回路の動作を初期状態ｉｎｉｔＤＡＴＡを１１１１１１１ｂとし、ｐｈＤＡＴＡを１１００１００ｂとし１００  シフトした場合を図２２に示す。
【０１２４】
図２２において、ｉは位相シフト量ＬをＭＳＢから入力し、これが１の場合には位相を２倍＋１、０の場合には２倍とする。ステップ７では、位相は１２８ｋ＋１００となるが、位相１２８ｋは位相ｋと同じなので、ｋ＋１００となる。初期状態は、１１１１１１１ｂとしたが、この発明によれば、初期状態の位相ｋは何であっても、初期状態から１００シフトした状態をステップ７で得ることができる。
【０１２５】
ｓｔｅｐ０  〜ｓｔｅｐ６  でマスクパターンを生成しｓｔｅｐ７  からＭ系列生成を始める。実際に特性多項式  ｆ（ｘ）  ＝  ｘ７  ＋  ｘ３  ＋  １  初期状態１１１１１１１  のＭ系列を１００  シフトしたＭ系列は０１０１１１１  であり表５の例と一致している。
【０１２６】
ここで、マスクパターンを用いず高速にシフトを行った後のＭ系列発生器の状態を計算する方法と、その設計方法およびハードウェアによる実現方法について考える。前述の実施の形態２では、まずマスクパターンを計算しその後にＭ系列を生成するが、本実施の形態３では、マスクパターンの計算とＭ系列の生成法の類似性に着目し、マスクパターンを用いず直接にＭ系列発生器の初期状態を生成する方法を実現できる。
【０１２７】
また、これを実現する回路は多数存在することを示し、その中で経験的に小さな回路規模で簡単に設計できる構成を得ることができる。前述の実施の形態２に示した方式に比べて、マスク回路が不要となり回路規模が削減される。また、Ｍ系列発生器の任意にシフト状態を得たい場合は、シフトした状態を並列に得ることができるので前述の実施の形態２と比べ半分のステップ数で計算することができる。
【０１２８】
以上によれば、ＲＯＭが必要なく、行列Ａ，Ｐは固定の行列となって簡単な回路で済む。また、行列Ａや行列Ｐの演算は、１クロックで実現することができるので、演算処理を高速化することが可能である。さらに、ｎクロックで任意にシフトした位相を得ることができる。
【０１２９】
実施の形態４．
前述の実施の形態３の応用として、位相の異なる符号を生成する回路を実現することができる。図２３は本発明の実施の形態４による符号発生装置の一構成例を示すブロック図である。図２３において、実施の形態３のレジスタ５４の出力は、スイッチ８５を介してたとえば４つのシフトレジスタ８１，８２，８３，８４に結合される。各シフトレジスタ８１，８２，８３，８４からは、位相の違う符号が出力される。
【０１３０】
このようにして、初期値の計算が高速に行えるので、一つの初期値計算で複数の符号発生器の初期状態を作り出すことができる。これにより、マスクを用いなくても異なる位相の符号を多数得ることが可能である。
【０１３１】
以上、本発明を実施の形態１〜４により説明したが、この発明の主旨の範囲内で種々の変形が可能であり、これらをこの発明の範囲から排除するものではない。
【０１３２】
【発明の効果】
以上説明したように、この発明によれば、生成多項式により固定される第１マスク変換行列と変換前のマスクベクトルとの積で新たなマスクベクトルを求め、シフト量データのＭＳＢがゼロでない場合に、生成多項式により固定される第２マスク変換行列とマスクベクトルとの積で新たなマスクベクトルを求め、シフト量データをＭＳＢ側へシフトし、上記各ステップを指定回数繰り返した後にマスクベクトルに基づくマスクパターンを出力するので、マスクパターンを高速に生成することができ、これにより、高速で小型の回路を実現することが可能な符号発生方法が得られるという効果を奏する。
【０１３３】
つぎの発明によれば、演算手段により生成多項式により固定される第１マスク変換行列と変換前のマスクベクトルとの積で新たなマスクベクトルを求め、シフト量データのＭＳＢがゼロでない場合に、生成多項式により固定される第２マスク変換行列とマスクベクトルとの積で新たなマスクベクトルを求め、シフト手段によりシフト量データをＭＳＢ側へシフトし、出力手段により上記演算手段とシフト手段を指定回数動作させた後にマスクベクトルに基づくマスクパターンを出力するようにしたので、マスクパターンを高速に生成することができ、これにより、高速で小型の回路を実現することが可能な符号発生装置が得られるという効果を奏する。
【０１３４】
つぎの発明によれば、マスクパターンを生成して、初期状態をマスクすることによりシフトを行うようにしたので、マスクパターンに応じて符号が生成され、専用の符号発生器が不要となることから、回路規模の削減を図ることが可能な符号発生装置が得られるという効果を奏する。
【０１３５】
つぎの発明によれば、第１演算手段により生成多項式により固定される第１マスク変換行列と符号発生器の状態を表す状態ベクトルとの積を求め、第１セレクタにより位相シフトと符号発生のいずれか一方を指示するモードに応じて第１演算手段の出力と状態ベクトルとのいずれか一方を選択し、第２演算手段により生成多項式により固定される第２マスク変換行列と第１セレクタ出力との積を求め、第２セレクタにより位相シフトと符号発生のいずれか一方を指示するモードおよびシフトデータのＭＳＢに応じて第１セレクタか、第２演算手段の出力のいずれか一方を選択し、新たな状態ベクトルとするようにしたので、簡単な構成でマスクパターンを用いず、直接に符号発生装置としての初期状態を生成すること、および符号を生成することが可能な符号発生装置が得られるという効果を奏する。
【０１３６】
つぎの発明によれば、状態ベクトルを、セレクタを介して位相の異なる符号をシフトさせる複数のシフトレジスタに接続させたので、一つの回路構成で符号発生を行うだけで、マスクを用いなくても、異なる位相の符号を多数得ることが可能な符号発生装置が得られるという効果を奏する。
【０１３７】
つぎの発明によれば、上記第１マスク変換行列および第２マスク変換行列のみを用いて位相シフト処理を行う構成としたため、マスクパターンを計算せずに、回路の状態を直接求めることが可能な符号発生装置を得ることができる、という効果を奏する。
【０１３８】
この発明によれば、特定構造を有する第１のマスク変換行列を用いる構成としたため、回路規模を大幅に小さくすることが可能な符号発生装置を得ることができる、という効果を奏する。
【０１３９】
つぎの発明によれば、上記第１マスク変換行列および第２マスク変換行列のみを用いて位相シフト処理を行うこととしたため、マスクパターンを計算せずに、回路の状態を直接求めることが可能な符号発生方法を得ることができる、という効果を奏する。
【０１４０】
この発明によれば、特定構造を有する第１のマスク変換行列を用いることとしたため、回路規模を小さくすることが可能な符号発生方法を得ることができる、という効果を奏する。
【図面の簡単な説明】
【図１】一般的なＭ系列発生器の一例を示すブロック図である。
【図２】Ｍ系列の性質を説明する図である。
【図３】Ｍ系列の性質を説明する図である。
【図４】Ｍ系列の性質を説明する図である。
【図５】Ｍ系列の性質を説明する図である。
【図６】一般的なＭ系列発生器の他の例を示すブロック図である。
【図７】本発明の実施の形態１によるマスクパターン生成回路の一構成例を示す回路図である。
【図８】本発明の実施の形態１によるＭ系列発生器の一構成例を示すブロック図である。
【図９】本実施の形態１の変形例を示すブロック図である。
【図１０】本実施の形態１の動作を説明するフローチャートである。
【図１１】本実施の形態１による位相シフトの手順を説明する図である。
【図１２】本発明の実施の形態２によるマスクパターン生成回路の他の例を示す回路図である。
【図１３】本発明の実施の形態２によるＭ系列発生器の一構成例を示すブロック図である。
【図１４】本実施の形態２によるマスク回路の一構成例を示す回路図である。
【図１５】本発明の実施の形態３によるＭ系列発生器の原理を説明する図である。
【図１６】本発明の実施の形態３によるＭ系列発生器の原理を別の観点から説明する図である。
【図１７】本実施の形態３による一行列を実現する一構成例を示す回路図である。
【図１８】本実施の形態３による他の行列を実現する別の構成例を示す回路図である。
【図１９】本実施の形態３によるＭ系列発生器の一構成例を示すブロック図である。
【図２０】本実施の形態３によるＭ系列発生器の変形例を示す図である。
【図２１】本実施の形態３による位相シフトの手順を説明する図である。
【図２２】本発明の実施の形態４によるＭ系列発生器の一構成例を示すブロック図である。
【図２３】従来例による符号発生装置の一例を示すブロック図である。
【図２４】従来例によるマスク変換動作を説明するフローチャートである。
【図２５】従来例による位相シフトの手順を説明する図である。
【図２６】従来例による符号発生装置の他の例を示すブロック図である。
【符号の説明】
２１  演算器、２１Ａ〜２１Ｇ  マスクパターン生成回路、２２，２３  シフトレジスタ、３１  マスクパターン生成回路、３２  マスク回路、３３  初期状態バッファ、３４  シフトレジスタ、３５  フリップフロップ、４１，４５  ＥＸ−ＯＲ、４２，４６  シフトレジスタ、５１，５１Ａ，５１Ｂ，５１Ｃ  回路、５２，５２Ａ，５２Ｂ，５２Ｃ  回路、５３  Ｄフリップフロップ、５４  シフトレジスタ、５５，５６，６１Ａ，６１Ｂ，６１Ｃ  セレクタ、５７  ＮＡＮＤ、８５  スイッチ、８１〜８４  シフトレジスタ。
【図１】
0003618554.tif 000035
【図２】
0003618554.tif 000036
【図３】
0003618554.tif 000037
【図４】
0003618554.tif 000038
【図５】
0003618554.tif 000039
【図６】
0003618554.tif 000040
【図７】
0003618554.tif 000041
【図８】
0003618554.tif 000042
【図９】
0003618554.tif 000043
【図１０】
0003618554.tif 000044
【図１１】
0003618554.tif 000045
【図１２】
0003618554.tif 000046
【図１３】
0003618554.tif 000047
【図１４】
0003618554.tif 000048
【図１５】
0003618554.tif 000049
【図１６】
0003618554.tif 000050
【図１７】
0003618554.tif 000051
【図１８】
0003618554.tif 000052
【図１９】
0003618554.tif 000053
【図２０】
0003618554.tif 000054
【図２１】
0003618554.tif 000055
【図２２】
0003618554.tif 000056
【図２３】
0003618554.tif 000057
【図２４】
0003618554.tif 000058
【図２５】
0003618554.tif 000059
【図２６】
0003618554.tif 000060