JP3618554B2 - Code generation method and code generation apparatus - Google Patents

Description

とし、生成多項式ｆ（ｘ）＝ｇ _ｎ ｘ ^ｎ ＋ｇ _ｎ−１ ｘ ^ｎ−１ ＋ｇ _ｎ−２ ｘ ^ｎ−２ ＋…＋ｇ _０ ｘ ^０ で、かつｎが奇数の場合、
【数１９】

とすることを特徴とする。
【００２８】
この発明によれば、特定構造を有する第１のマスク変換行列を用いることで設計が容易になり、さらに、回路規模を小さくすることができる。
【００２９】
つぎの発明にかかる符号発生方法は、生成多項式により固定される第１マスク変換行列と符号発生器の状態を表す状態ベクトルとの積を求める第１の演算ステップと、位相シフトと符号発生のいずれか一方を指示するモードに応じて、前記第１の演算ステップによる演算結果と前記状態ベクトルのいずれか一方を選択する第１の選択ステップと、生成多項式により固定される第２マスク変換行列と前記第１の選択ステップによる選択結果との積を求める第２の演算ステップと、位相シフトと符号発生のいずれか一方を指示するモードおよびシフトデータのＭＳＢに応じて、前記第１の選択ステップによる選択結果と前記第２の演算ステップによる演算結果のいずれか一方を選択し、その選択結果を新たな状態ベクトルとする第２の選択ステップと、を含み、さらに、前記第１マスク変換行列は、前記第２マスク変換行列による位相シフト処理の２倍の位相シフトが可能なマスクパターンに基づいて特定される行列とし、前記第１マスク変換行列および前記第２マスク変換行列の組み合わせによって、任意の位相シフト処理を行うことを特徴とする。
【００３０】
この発明によれば、上記第１マスク変換行列および第２マスク変換行列のみを用いて位相シフト処理を行うこととしたため、マスクパターンを計算せずに、回路の状態を直接求めることができる。
【００３１】
つぎの発明にかかる符号発生方法において、さらに、前記第１マスク変換行列としては、生成多項式ｆ（ｘ）＝ｇ _ｎ ｘ ^ｎ ＋ｇ _ｎ−１ ｘ ^ｎ−１ ＋ｇ _ｎ−２ ｘ ^ｎ−２ ＋…＋ｇ _０ ｘ ^０ で、かつｎが偶数の場合、
【数２０】

を用い、生成多項式ｆ（ｘ）＝ｇ _ｎ ｘ ^ｎ ＋ｇ _ｎ−１ ｘ ^ｎ−１ ＋ｇ _ｎ−２ ｘ ^ｎ−２ ＋…＋ｇ _０ ｘ ^０ で、かつｎが奇数の場合は、
【数２１】

を用いることを特徴とする。
【００３２】
この発明によれば、特定構造を有する第１のマスク変換行列を用いることで設計が容易になり、さらに、回路規模を小さくすることができる。
【００３３】
【発明の実施の形態】
以下に添付図面を参照して、この発明にかかる符号発生方法および符号発生装置の好適な実施の形態を詳細に説明する。
【００３４】
実施の形態１．
まず、本実施の形態の説明に入る前に、マスクパターンによる任意位相のＭ系列の生成原理について一般的に用いられているものを説明する。ここでは、符号発生装置の一例としてＭ系列発生器を例に挙げる。
【００３５】
（Ｍ系列の生成原理）
一例として特性多項式 ｆ（ｘ） ＝ ｘ^４ ＋ ｘ^３ ＋ １ のＭ系列をとりあげる。図１に特性多項式 ｆ（ｘ） ＝ ｘ^４ ＋ ｘ^３ ＋ １ のＭ系列を発生するＭ系列発生器を示す。図１に示した符号発生器は、ＥＸ−ＯＲ１１と４段のシフトレジスタ１２とを備えている。特性多項式の次数が４であるので、シフトレジスタ１２の段数は４となる。また、ｘ^４を除いたｘ^３と１ ＝ ｘ^０が帰還タップの位置である３ と０ を示している。
【００３６】
図１に示すＭ系列発生器の各フリップフロップＤ_０〜Ｄ_３の状態を下記の表１に示す。特性多項式の次数が４ であるのでＭ系列の周期は２^４−１ ＝ １５ となり、表１のｓｔｅｐ１４のつぎはｓｔｅｐ０ から繰り返し同じ動作となる。表１の場合はすべて１の場合を初期値としているが、Ｍ系列発生器の状態はすべて０の場合以外のすべての状態をとるので、初期値はすべて０ 以外のパターンなら任意に設定することができる。
【００３７】
【表１】

【００３８】
（シフトしたＭ系列の生成）
まず、Ｍ系列の性質について説明する。図１のＭ系列発生器より生成されるＭ系列は図２に示すようになり、このＭ系列はＭ系列発生器の動作を考慮すると図３に示すような性質があることがわかる。このように上記の演算を左右に動かした場合に常に入力と出力は正しくなっている。ここで ｘ^ｎ を組み合わせて書くと図４に示すようになる。
【００３９】
以下の演算は、ＧＦ（２）上の演算であり、演算結果のモジュロ２を取ることと等価である。
ｘ ^ｎ＋４ ＝ ｘ ^ｎ＋３ ＋ ｘ ^ｎ
ｘ ^ｎ＋４ ＋ ｘ ^ｎ＋３ ＋ ｘ ^ｎ ＝ ０（ＧＦ（２）上の演算では、＋と−は同じ）
ｘ ^ｎ （ｘ ^４ ＋ ｘ^３ ＋ １） ＝ ０
ここで、特性多項式ｆ（ｘ） ＝ ｘ^４ ＋ｘ^３ ＋ １ が現れている。
より一般には、
Ｇ（ｘ）ｆ（ｘ） ＝ ０ （ Ｇ（ｘ）は任意の多項式 ）
であり、式（１）が成立する。
【００４０】
ここで、例えば以下の式を考える。

となり、図５に示す関係があることが分かる。このように特性多項式ｆ（ｘ）に掛けるＧ（ｘ）によりＭ系列の各位相の関係を計算することができる。
【００４１】
つぎにｘ ^ｍ をｆ（ｘ）で割った剰余Ｒ（Ｘ）について考えると、ｘ ^ｍ をｆ（ｘ）で割った商をＱ（ｘ）とすると、以下の式が成り立つ。
ｘ ^ｍ ＝ Ｑ（ｘ）ｆ（ｘ） ＋ Ｒ（ｘ）
式（１）より
Ｑ（ｘ）ｆ（ｘ） ＝ ０
なので、
ｘ ^ｍ ＝ Ｒ（ｘ）
となり、式（２）が成立する。
【００４２】
つぎに、マスクパターンによるＭ系列のシフトについて説明する。Ｍ系列発生器の動作を示した表１にｘ ^ｎ を合わせて表示すると表２となる。
【００４３】
【表２】

【００４４】
ここで、式（２）よりｘ ^ｍ ＝ Ｒ（ｘ）であり、Ｒ（ｘ）はｘ ^ｍ をｆ（ｘ）で割った剰余であるからその次数はｆ（ｘ）の次数より小さい。すなわち、、ｆ（ｘ） ＝ ｘ^４ ＋ ｘ ^３ ＋ １ の場合はＲ（ｘ）＝ｒ_３ ｘ^３ ＋ ｒ_２ ｘ^２ ＋ ｒ_１ｘ ＋ ｒ_０ と表わすことができる。これより以下の式が成り立つ。
ｘ^ｍ ＝ｒ_３ｘ^３ ＋ ｒ_２ｘ^２ ＋ ｒ_１ｘ ＋ ｒ_０
ｘ^ｎ＋ｍ ＝ｒ_３ｘ^ｎ＋３ ＋ ｒ_３ｘ ^ｎ＋２ ＋ ｒ_３ｘ ^ｎ＋１ ＋ ｒ_３ｘ ^ｎ
【００４５】
表２と見比べるとｘ ^ｎ＋３， ｘ ^ｎ＋２， ｘ ^ｎ＋１， ｘ ^ｎはＭ系列発生器に現れている。このため、図７には、図１に示したＭ系列発生器に加算器１３を付加した構成が示されている。図７に示すように各タップの出力をマスクパターンにしたがって合成できる構成にすることによって、任意の位相シフトを行ったＭ系列を得ることができる。
ｏｕｔ２ ＝ｒ_０Ｄ_０ ＋ ｒ_１Ｄ_１ ＋ ｒ_２Ｄ_２ ＋ ｒ_３Ｄ_３
を計算することによりシフトしたＭ系列を得る。より一般には、位相の異なるＭ系列が次数個あるならそれらの線形結合ですべての位相を表現することができる。
【００４６】
つぎに、マスクパターン生成法について説明する。Ｌ位相シフトしたＭ系列を生成するマスクパターンを得るには、「 ｘ ^Ｌ ÷特性多項式 ｆ（ｘ） 」を行い、剰余 Ｒ（ｘ） を求めればよい。特性多項式 ｆ（ｘ） ＝ ｘ^４＋ｘ^３＋１ を例に５位相シフトする場合のマスクパターンを求めるには「 ｘ ^５ ÷ （ｘ ^４ ＋ｘ ^３ ＋１） 」の剰余を求める。以下に 「 ｘ ^５ ÷ （ｘ ^４ ＋ｘ ^３ ＋１） 」の計算を示す。
【００４７】
【数１】

【００４８】
計算の結果得られた剰余 Ｒ（ｘ） ＝ ｘ^３＋ｘ^１＋１ よりマスクパターンは以下のようにになる。
（ｒ３，ｒ２，ｒ１，ｒ０ ）＝ （１，０，１，１）
【００４９】
このマスクパターンより５シフトしたＭ系列は Ｄ_３＋Ｄ_１＋Ｄ_０より得られることがわかる。実際に上記のマスクパターンで図７の動作を調べると表３のようになり、ｓｔｅｐ ｎのＤ_０と ｓｔｅｐ ｎ−５ のＤ_３＋Ｄ_１＋Ｄ_０が同じであることがわかる。すなわち、Ｄ_３＋Ｄ_１＋Ｄ_０は、Ｄ_０に対して ５ ｓｔｅｐ 未来の出力である。
【００５０】
【表３】

【００５１】
つぎに、本実施の形態についての説明に入る。論理演算によりマスクパターンを求める方法について説明する。以下演算はＧＦ（２） 上の演算である。
【００５２】
（アルゴリズム）
Ｌ位相シフトしたＭ系列を生成するマスクパターンを得るには、「 ｘ ^Ｌ ÷特性多項式 ｆ（ｘ） 」を行い、剰余 Ｒ_Ｌ （ｘ） を求めればよい。以下に提案するアルゴリズムを説明する。以後、「 ｇ（ｘ） ÷ ｆ（ｘ） 」の剰余 Ｒ（ｘ） は Ｒ（ｘ） ＝Ｒ _ｆ（ｘ）［ｇ（ｘ）］と表わす。また、Ｒ _Ｌ （ｘ） ＝Ｒ _ｆ（ｘ）［ｘ^Ｌ ］ とする。
【００５３】
Ｒ_０（ｘ） ＝Ｒ _ｆ（ｘ）［ｘ^０ ］ より、
▲１▼ Ｒ_０（ｘ） ＝ １
一般に、
Ｒ _ｆ（ｘ）［ｘ（ｘ）］＝ ｘ（ｘ） ＋ Ｑｘ（ｘ） ｆ（ｘ）
Ｒ _ｆ（ｘ）［ｙ（ｘ）］＝ ｙ（ｘ） ＋ Ｑｙ（ｘ） ｆ（ｘ）
Ｑｘ（ｘ） はｘ（ｘ）を ｆ（ｘ） で割った商、Ｑｙ（ｘ） はｙ（ｘ）を ｆ（ｘ） で割った商、と表わせるので、
Ｒ _ｆ（ｘ）［ｘ（ｘ）］Ｒ _ｆ（ｘ）［ｙ（ｘ）］＝ ｘ（ｘ） ｙ（ｘ） ＋ （ Ｑｘ（ｘ） ｙ（ｘ） ＋ Ｑｙ（ｘ） ｘ（ｘ） ＋ Ｑｘ（ｘ）Ｑｙ（ｘ）ｆ（ｘ） ） ｆ（ｘ） より、
Ｒ _ｆ（ｘ）［ Ｒ _ｆ（ｘ）［ｘ（ｘ）］ Ｒ_ｆ（ｘ）［ｙ（ｘ）］ ］＝Ｒ _ｆ（ｘ）［ｘ（ｘ） ｙ（ｘ）］ となり逆も同様に成り立つ。
【００５４】
よって、
▲２▼ Ｒ_２ｋ（ｘ） ＝ Ｒ _ｆ（ｘ）［Ｒ_ｋ （ｘ）^２］
▲３▼ Ｒ_ｋ＋１（ｘ） ＝Ｒ _ｆ（ｘ）［ｘＲ _ｋ （ｘ）］
の如く、 式（３）が成立する。
【００５５】
上記式（３）の▲１▼， ▲２▼， ▲３▼を組み合わせて任意のＬについてＲ _Ｌ （ｘ） を求めることができる。
たとえば Ｒ_１０（ｘ） を求めると、
Ｒ_１０（ｘ） ＝Ｒ _ｆ（ｘ）［Ｒ_５（ｘ）^２］ ▲２▼
Ｒ_５（ｘ） ＝ Ｒ _ｆ（ｘ）［ｘＲ_４（ｘ）］ ▲３▼
Ｒ_４（ｘ） ＝Ｒ_ｆ（ｘ）［Ｒ_２（ｘ）^２］ ▲２▼
Ｒ_２（ｘ） ＝Ｒ_ｆ（ｘ）［Ｒ_１（ｘ）^２］ ▲２▼
Ｒ_１（ｘ） ＝Ｒ_ｆ（ｘ）［ｘＲ_０（ｘ）］ ▲３▼
Ｒ_０（ｘ） ＝ １ ▲１▼
の如く式（４）が成立する。
【００５６】
Ｒ _ｋ （ｘ） のｋ が偶数なら式▲２▼、奇数なら式▲３▼を順次おこないｋ＝０ となるまで行う。ｋ＝０ なら式▲１▼となる。式（４）を逆から計算すればつぎのようにＲ_１０（ｘ）を求めることができる。
Ｒ_１０（ｘ） ＝Ｒ _ｆ（ｘ）［Ｒ_ｆ（ｘ）［ｘＲ _ｆ（ｘ）［Ｒ_ｆ（ｘ）［Ｒ_ｆ（ｘ）［ｘＲ_０（ｘ）］^２］^２］］^２］
式（４）の演算は、１０ ＝５ ×２ 、５＝４＋１ 、４＝２ ×２ 、２＝１ ×２ 、より１０＝（（１×２）×２＋１）×２ と展開しているが、この展開はＬを２進数に表わすことにより簡単に求められる。
Ｌ ＝ ｌ_０ ＋ ２ｌ_１ ＋ ２^２ｌ_２ ＋ … ＋ ２^ｎ−２ｌ_ｎ−２ ＋ ２ ^ｎ−１ｌ_ｎ−１ ＝ （ （ … （ ｌ_ｎ−１ ×２ ＋ ｌ _ｎ−２ ） ×２ ＋ … ＋ ｌ_２ ） ×２ ＋ ｌ_１ ） ×２ ＋ ｌ_０
【００５７】
ここで、式▲２▼式▲３▼をまとめＡ _ｆ（ｘ）［ｇ（ｘ） ， ｉ ］ ｉ ＝ ［１ ，０］ を定義する。以下の式（５）が成立する。
【００５８】
【数２】

【００５９】
Ａ _ｆ（ｘ）［ｇ（ｘ） ， ｉ ］ を用いてＲ _Ｌ （ｘ） を、以下に示すように式（６）を求めることができる。
Ａ_０（ｘ） ＝ Ｒ_０（ｘ）
Ａ _ｋ （ｘ） ＝ Ａ _ｆ（ｘ）［Ａ_ｋ−１（ｘ） ， ｌ_{ｎ−１−ｋ} ］
Ｒ _Ｌ （ｘ） ＝ Ａ _ｎ−１（ｘ）
ただし、Ｌ ＝ ｌ_０ ＋ ２ｌ_１ ＋ ２^２ｌ_２ ＋ … ＋ ２^ｎ−２ｌ_ｎ−２ ＋ ２ ^ｎ−１ｌ_ｎ−１
上記式に示すように式（６）の演算をｎ （ｆ（ｘ）の次数）回行うことによりＲ _Ｌ （ｘ） を求めることができる。
【００６０】
つづいてハードウェアによる実現方法について説明する。マスクパターン生成法をハードウェアにより実現するには上式（６）をハードウェア化すればよい。ここでは一例として特性多項式 ｆ（ｘ） ＝ ｘ^７ ＋ ｘ^３ ＋ １ の場合を取り上げる。
【００６１】
まず、２乗回路から説明する。一般に ｇ（ｘ） ＝ ｘ ^ｋ ＋ｘ^ｊ ＋ｘ^ｉ ＋ … ＋１ であれば、ｇ（ｘ）^２ ＝ ｘ^２ｋ ＋ｘ^２ｊ＋ｘ^２ｉ＋ … ＋１ と簡単に求められる。ｆ（ｘ）の次数が７であるから式（６）の入力と出力の多項式の次数は６である。ここで、Ａ（ｘ）を、
Ａ（ｘ） ＝ ａ_６ｘ^６ ＋ ａ_５ｘ^５ ＋ ａ_４ｘ^４ ＋ ａ_３ｘ^３ ＋ ａ_２ｘ^２ ＋ ａ_１ｘ ＋ ａ_０
と定義すると、
Ａ^２（ｘ） ＝ ａ_６ｘ^１２ ＋ ａ_５ｘ^１０ ＋ ａ_４ｘ^８ ＋ ａ_３ｘ^６ ＋ ａ_２ｘ^４ ＋ ａ_１ｘ^２ ＋ ａ_０
と求められる。
【００６２】
Ｒ _ｆ（ｘ） ［Ａ^２（ｘ）］を求めると以下のようになる。
Ｒ _ｆ（ｘ）［Ａ^２（ｘ）］＝Ｒ _ｆ（ｘ）［ａ_６ｘ^１２ ＋ ａ_５ｘ^１０ ＋ ａ_４ｘ^８ ＋ ａ_３ｘ^６ ＋ ａ_２ｘ^４ ＋ ａ_１ｘ^２ ＋ ａ_０］ ＝ａ_６Ｒ _ｆ（ｘ）［ｘ^１２］＋ ａ_５Ｒ_ｆ（ｘ）［ｘ^１０］＋ ａ_４Ｒ_ｆ（ｘ）［ｘ^８］ ＋ ａ_３ｘ^６ ＋ ａ_２ｘ^４ ＋ ａ_１ｘ^２ ＋ ａ_０
ｆ（ｘ）は７次であるから６次以下の項については剰余を求める必要はない。
Ｒ _ｆ（ｘ）［ｘ^１２］＝ｘ^５ ＋ ｘ^４ ＋ ｘ
Ｒ _ｆ（ｘ）［ｘ^１０］＝ｘ^６ ＋ ｘ^３
Ｒ _ｆ（ｘ）［ｘ^８ ］＝ｘ^４ ＋ ｘ
より、
Ｒ _ｆ（ｘ） ［Ａ^２（ｘ）］＝（ａ_５ ＋ ａ_３） ｘ^６ ＋ ａ_６ｘ^５ ＋ （ａ_６ ＋ ａ_４ ＋ ａ_２） ｘ^４ ＋ ａ_５ｘ^３ ＋ ａ_１ｘ^２ ＋ （ａ_６ ＋ ａ_４） ｘ ＋ ａ_０
これが、式（７）となる。
【００６３】
つぎに、Ｒ _ｆ（ｘ）［ｘＡ^２（ｘ）］を求める。Ｒ _ｆ（ｘ）［Ａ^２（ｘ）］ ＝ ｂ_６ｘ^６ ＋ ｂ_５ｘ^５ ＋ ｂ_４ｘ^４ ＋ ｂ_３ｘ^３ ＋ ｂ_２ｘ^２ ＋ ｂ_１ｘ ＋ ｂ_０ とする。
ただし、式（７）より、
ｂ_６＝ａ_５ ＋ ａ_３、ｂ_５＝ａ_６
ｂ_４＝ａ_６ ＋ ａ_４ ＋ ａ_２
ｂ_３＝ａ_５
ｂ_２＝ａ_１
ｂ_１＝ａ_６ ＋ ａ_４
ｂ_０＝ａ_０

Ｒ _ｆ（ｘ）［ｘ^７］＝ｘ^３ ＋ １ より、
Ｒ _ｆ（ｘ）［ｘＡ^２（ｘ）］＝ｂ_５ｘ^６ ＋ ｂ_４ｘ^５ ＋ ｂ_３ｘ^４ ＋ （ｂ_２ ＋ ｂ_６） ｘ^３ ＋ ｂ_１ｘ^２ ＋ ｂ_０ｘ ＋ ｂ_６
の如く式（８）が成立する。
【００６４】
式（７）、式（８）より式（５）をハードウェア化すると図８に示すように簡単な構成で実現することができる。図８に示した演算器は、ＥＸ−ＯＲ、セレクタなどにより構成される。図８に示した回路は、以下の式をハードウェア化したものである。
【００６５】
【数３】

【００６６】
マスクパターンを生成するには式（６）に示すように式（５）を繰り返せばよく、ハードウェアにすると図９に示すように構成すればよい。図９には、マスクパターン生成回路が示され、２１は図８の演算器を示し、２２，２３はシフトレジスタをそれぞれ示す。なお、図９の変形例として、図１０のように並列接続させた構成にしてもよい。図１０には、マスクパターン生成回路２１Ａ〜２１Ｇが直列に接続されている。
【００６７】
図９の構成は特性多項式の次数ステップでマスクパターンを得ることができるが、図１０のように構成すれば、さらに高速にマスクパターンを得ることができる。ただし、特性多項式の次数が大きな場合には図９に比べ図１０の構成は回路規模が非常に大きなものとなる。論理圧縮することにより図１０の構成を若干小さくすることは可能である。
【００６８】
つづいて、マスクパターン生成器の動作について説明する。まず、図９の回路の動作を説明する。Ｌ＝１００の場合の動作を表４に示す。１００を２進数で表わすと１１００１００であるからｉ にこれをＭＳＢから入力する。フリップフロップの出力であるＤ_６〜Ｄ_０と Ａ _ｆ（ｘ）［ｇ（ｘ） ， ｉ］回路の内部にあるｂ_６〜ｂ_０を示す。特性多項式ｆ（ｘ） ＝ ｘ^７ ＋ ｘ^３ ＋ １の次数は７であるからｓｔｅｐ７ でマスクパターン１１１０１１１を得ることができる。
【００６９】
【表４】

【００７０】
ここで、従来例として挙げた特開平７−２９７６８５号公報開示の技術との対応を考え、具体的な動作の流れについて説明する。図１１は本実施の形態１による動作を説明するフローチャートであり、図１２はＭＳＢの変化に対応するｍ、位相の変化を説明する図である。
【００７１】
本実施の形態１では、まずカウンタ値が０より大きければ（ステップＳ１、Ｙｅｓルート）、ｍ←Ｐｍの演算が行われる（ステップＳ２）。この場合には、シフト量のＭＳＢが０でないとき（ステップＳ３、Ｎｏルート）、さらにｍ←Ａｍの演算が行われ（ステップＳ４）、シフト量は左にシフトの操作となり（ステップＳ５）、カウント値は１引かれる（ステップＳ６）。なお、シフト量のＭＳＢが０のとき（ステップＳ３、Ｙｅｓルート）、ステップＳ４の演算を飛ばしてステップＳ５においてシフト量は左にシフトされ、ステップＳ６においてカウント値を１引く操作となる。この後、処理はステップＳ１に戻る。また、ステップＳ１においてシフト量が０以下の場合には、マスクパターン出力が実施される。
【００７２】
図１２においては、シフト量Ｌ＝１００＝１１００１００ｂ、１ステップはループの１周に対応している。生成多項式の次数を７とすると、Ｍ系列の周期は、２^７ −１＝１２７となる。１２７ｋの位相シフトは、０シフトと同じになり、１２８ｋシフトはｋシフトと同じになる。このため、１２８ｋ＋１００＝ｋ＋１００となる。
【００７３】
以上によれば、Ｍ←ＭＭに相当する演算は必要なく、ｍ←Ｐｍの演算はＭ←ＭＭの演算に比べてはるかに小さな回路規模および演算量で実現することができる。従来では、Ｍ←ＭＭの演算を１番目の行ベクトルのみを求め、他の行はそこから計算するようにしているので、演算量は２ｎ−１ステップ必要となっていた。それに比べると、本実施の形態１では、小規模な回路で１ステップで実現することが可能である。なお、ソフトウェアで実現する場合にも、行列とベクトルの積なので、ｎステップで実現することが可能である。
【００７４】
とくに、従来、原理的に行列を固定にできない分、本実施の形態１では、行列Ａや行列Ｐの演算は、生成多項式により固定にできるので、ハードウェアを非常に小さい規模で設けることが可能となる。
【００７５】
実施の形態２．
さて、前述の実施の形態１によるマスクパターン生成法を用いれば、Ｍ系列発生器の位相を任意にシフトすることができるが、以下に説明する実施の形態２では、任意の初期状態より任意に位相シフトしたＭ系列の生成について説明する。上述のようなマスクパターン生成法を用いれば、Ｍ系列発生器の位相を任意にシフトできるが、ここではＭ系列発生器とマスクパターン生成回路を共用化し、ハードウェア規模を縮小した回路構成を説明する。
【００７６】
Ｌ位相シフトするマスクパターン Ｒ（ｘ） が求まっているとすると、Ｌ＋１位相シフトしたマスクパターンはＲ _ｆ（ｘ）［ｘＲ（ｘ）］ で求めることができる。この回路はすでにマスクパターン生成回路に組み込まれているので容易に実現できる。そこで、図８に示したＡ _ｆ（ｘ）［ｇ（ｘ） ， ｉ］を実現した回路を図１３に示すように改良する。図１３に示した回路は、ＥＸ−ＯＲ、セレクタにより構成される。この回路を式で表現すると、つぎのようになる。
【００７７】
【数４】

【００７８】
ｍｏｄｅ ＝ ０ の場合は前記マスクパターン生成回路と同じ動作をし、ｍｏｄｅ ＝ １の場合は１位相シフトしたマスクパターンを求める。
【００７９】
図１３に示した回路をマスクパターン生成回路として用い、これによりＭ系列を生成するＭ系列発生器を構成する。図１４に任意の初期状態から任意にシフトしたＭ系列を生成するＭ系列発生器を示す。図１４に示したＭ系列発生器は、図７に示したマスクパターンを生成するマスクパターン生成回路３１、クロックにより初期状態バッファ３３から供給されるデータをマスクして出力するマスク回路３２、初期状態のデータをマスク回路３２に供給する初期状態バッファ３３、クロックによりシフト量データをＭＳＢより取り出すシフト量バッファ、すなわちシフトレジスタ３４、クロックにしたがってマスク回路３２の出力を保持するフリップフロップ３５を備えている。
【００８０】
動作は、まず初期状態バッファ３３にＭ系列の始めのｎ個のデータを書き込み、シフトレジスタ３４に初期状態からのシフト量を書き込む。つぎに、ｍｏｄｅ ＝ ０でｃｌｋ をｆ（ｘ）の次数ｎ回入力し、シフトレジスタ３４に設定したシフト量のマスクパターンを生成し、初期状態からシフト量シフトしたＭ系列を１ｂｉｔ得る。つぎに、ｍｏｄｅ ＝ １としｃｌｋ を入力する毎に１つシフトしたマスクパターンを生成することにより順次１ｂｉｔずつＭ系列を得ることができる。
【００８１】
マスク回路３２の内部構成を図１５に示す。このマスク回路３２は、ＥＸ−ＯＲとＡＮＤとの組み合わせで構成される。図７に示した構成と同様であるが、初期状態が固定であれば回路を削減できる。特に初期状態に１が一つしか無いような場合には、マスク回路は不必要である。
【００８２】
つぎに動作について説明する。実際に初期状態１１１１１１１ で１００ シフトした場合のＭ系列を生成すると表５に示すようになる。
【００８３】
【表５】

【００８４】
ｓｔｅｐ０ 〜ｓｔｅｐ６ でマスクパターンを生成しＭｏｄｅ ＝ ０ とし、表４と同じ動作である。ｓｔｅｐ７ からＭｏｄｅ ＝ １ としＭ系列生成を始める。実際に特性多項式 ｆ（ｘ） ＝ ｘ^７ ＋ ｘ^３ ＋ １ 初期状態１１１１１１１ のＭ系列は表６に示すようになり、１００ シフトした場合は０１０１１１であり表５の出力と一致している。
【００８５】
【表６】

【００８６】
ここで示した任意にシフトしたＭ系列を生成する回路は、任意にシフトした場合の初期設定に必要な時間が短いのが特徴である。
【００８７】
実施の形態３．
以下に説明する実施の形態３では、マスクパターンを用いずに、論理演算により任意に位相シフトする方法について説明する。シフトしたＭ系列の生成法として、マスクパターンによりＭ系列をシフトさせることができる。この実施の形態３ではマスクパターンを用いないＭ系列の高速シフトの新しいアルゴリズムと、それのハードウェアによる実現方法を示す。以下演算はＧＦ（２） 上の演算である。
【００８８】
まずＭ系列発生回路の行列表示について説明する。論理演算によりマスクパターンを求める方法では、Ａ _ｆ（ｘ）［ｇ（ｘ），ｉ］を定義し、これを用いてマスクパターンを生成し、Ｍ系列の位相シフトを行う方法を提案したが、実用的にはＭ系列を生成するシフトレジスタの初期値を求めたい場合が多く、そのような方法ではマスクパターンの生成とシフトレジスタの初期値の生成の２段階の操作が必要になる。そこでマスクパターンを求めずに直接シフトレジスタの初期値を生成する方法を考える。
【００８９】
図１６は、特性多項式 ｆ（ｘ） ＝ ｘ^４＋ｘ^３＋１ のＭ系列発生器であり、４１はＥＸ−ＯＲ、４２はシフトレジスタ、ａ_０〜ａ_３はそれぞれのタップの出力である。これを行列表示すると以下のようになる。
【００９０】
【数５】

【００９１】
初期状態をａ_０とすればｎシフトした状態は次式で表わせる。
ａ _ｎ ＝ Ａ^ｎ ａ_０
一般にｎ段のＬＦＳＲはｎ×ｎの行列を用いて表現できる。行列ＡのようにＭ系列を生成する行列は一つの特性多項式に対して多数存在する。詳細は省くが、ａ の各要素はそれぞれ異なる位相のＭ系列となるため一つの特性多項式について（２ ^ｎ − ２）Ｐ（ｎ−１） 個存在する。これは、つぎに示すように正則な行列Ｔによって関係づけられる。
Ａ’＝Ｔ^−１ＡＴ
【００９２】
つづいてマスクパターンを用いない任意シフトの方法について説明する。一般例の説明では、以下の三つの式よりマスクパターンを求めていたが、初期値を固定とし、マスクパターンを順次進めながらＭ系列を生成できることを考えれば式▲３▼自体がＭ系列を生成することがわかる。
▲１▼ Ｒ_０ （ｘ） ＝ １
▲２▼ Ｒ_２ｋ（ｘ） ＝ Ｒ _ｆ（ｘ）［Ｒ_ｋ （ｘ）^２］
▲３▼ Ｒ_ｋ＋１（ｘ） ＝ Ｒ_ｆ（ｘ） ［ｘＲ_ｋ （ｘ）］
上式▲３▼を回路で表わせば図１７のようになる。図１７に示したＭ系列発生器は、４段のシフトレジスタ４６の２つのレジスタ（Ｄ_２ 、Ｄ_３ ）間に、ＥＸ−ＯＲ４５を接続させた構成である。
【００９３】
先ほどと同様に行列で表わすと、以下のように表され、Ｂ＝ Ａ^Ｔ となっていることがわかる。
【００９４】
【数６】

【００９５】
同様に式▲２▼を行列で表わすとつぎのようになる。
【００９６】
【数７】

【００９７】
前述の実施の形態１で説明した一般的な方法を行列を用いて説明すると、ｂ_０＝ （１，０，０，０） として、行列Ｂ、Ｃを用いて任意にシフトさせるマスクパターンを作成している。行列Ｂ、Ｃはつぎの演算を行う行列である。
ｂ _ｋ＋１ ＝ Ｂ ｂ _ｋ
ｂ _２ｋ ＝ Ｃ ｂ _ｋ
ｂ_０は０シフトするマスクパターンであり、例えば１１シフトするマスクパターンはつぎのように表わされる。
ｂ_１１＝Ｂ^１１ｂ_０
【００９８】
一般的な方法では１１シフトする場合は１１を２進数で表わし１０１１ｂ であるから１ を（ＢＣ）、０を（Ｃ）としてＭＳＢより順次掛け合わせ、次式（式（９））とする。
（ＢＣ）（ＢＣ）（Ｃ）（ＢＣ）ｂ_０
【００９９】
一方、行列Ｂ、Ｃの間にはＢ＝ Ｃ^−１Ｂ^２ Ｃとなる関係があり、
ＣＢ＝Ｂ^２ Ｃが成り立ち、

０シフトを２倍シフトしても０シフトなのでＣｂ_０＝ｂ_０ であり、
（ＢＣ）（ＢＣ）（Ｃ）（ＢＣ）ｂ_０＝ Ｂ^１１ｂ_０
となる。
【０１００】
ここで、一般的な方法では触れなかったが初期値としてｂ_０ではなく ｂ _ｋ を用いた場合は、つぎのようになる。

Ｍ系列の周期性よりＢ^２４＝ Ｂとなる。
【０１０１】
よって、
Ｂ^１１Ｃ^４ｂ_ｋ ＝ Ｂ^{１１ ＋ ｋ}ｂ_０＝ Ｂ^１１ｂ _ｋ
であり、初期値によらず１１シフトしたマスクパターンが得られ、このことはシフト量１１によらず一般的に成り立ち、ｂ _ｋ は０以外のあらゆるパターンを取り得ることによりＣ^４ ＝ Ｅであることがわかる。よって、次式（式（１０））が成立する。
（ＢＣ）（ＢＣ）（Ｃ）（ＢＣ）＝ Ｂ^１１
【０１０２】
一般に特性多項式の次数がｎの場合はＣ^ｎ ＝ Ｅである。
ここで、
Ａ ＝Ｔ^−１ＢＴ 式（１１）
となるＴを求めると、例えば以下のようになる。説明は省くがＡ ＝Ｔ^−１ＢＴを満たすＴは多数存在する。
【０１０３】
【数８】

【０１０４】
ここで、Ｃに対応してＰを定義する。
Ｐ ＝Ｔ^−１ＣＴ 式（１２）
行列Ｐを用いて１１シフトを行うと、

となり１１シフトを行うことができる。一般にはＡ，Ｐ を求めれば任意にシフトを行うことができ、マスクパターンを計算せずに図１６の回路の状態を直接求めることができる。
【０１０５】
つぎにハードウェアによる実現を例に挙げる。ここで具体的にＰを計算すると式（１２）の行列Ｔの場合は、以下の式となる。
【０１０６】
【数９】

【０１０７】
これを回路で表わすとたとえばＥＸ−ＯＲ ２個で実現できる。Ｔの取り方によってＰは異なる行列となり回路規模も異なってくる。たとえば、Ｔ’＝ＢＴとした場合式（１１）より、
Ａ ＝Ｔ^−１ＢＴ＝（Ｂ^−１Ｔ’）^−１Ｔ’ ＝ Ｔ’ ^−１ＢＴ’
となり、Ｔ’ を用いてＰ’ を定義すると、次式となる。
【０１０８】
【数１０】

【０１０９】
Ｐ’ を用いてもＰを用いた場合と同様に位相シフトを行うことができるが、Ｐ’ を回路にした場合はＥＸ−ＯＲ ３個を必要とする。このようにＰによって回路規模が異なるため、回路規模を小さくするＰを求める必要があり、つぎのように設計すると回路規模が小さく、また設計も簡単である。
【０１１０】
たとえば、特性多項式 ｆ（ｘ） ＝ ｇ_４ｘ^４ ＋ ｇ_３ｘ^３ ＋ ｇ_２ｘ^２ ＋ ｇ_１ｘ^１ ＋ ｇ_０ｘ^０とすると、次式が成立する。
【０１１１】
【数１１】

【０１１２】
特性多項式 ｆ（ｘ） ＝ ｇ_５ｘ^５ ＋ ｇ_４ｘ^４ ＋ ｇ_３ｘ^３ ＋ ｇ_２ｘ^２ ＋ ｇ_１ｘ^１ ＋ ｇ_０ｘ^０ の場合は、次式が成立する。
【０１１３】
【数１２】

【０１１４】
その結果、比較的小さな回路となり、しかも面倒な計算をせずにＰを求めることができる。
【０１１５】
たとえば特性多項式ｆ（ｘ） ＝ ｘ^７ ＋ ｘ^３ ＋ １の場合、次式が成立する。
【０１１６】
【数１３】

【０１１７】
この設計法では状態がａ＝ （１ ０ ０ ０ ０ ０ ０ ）^Ｔ の場合を０位相として位相を２倍にする行列Ｐを求めることができる。行列Ａ によるＭ系列発生器の動作を示した表７を用いて行列Ｐの動作を確認すると、
ｂ ＝Ｐａとして
ａ ＝（１ ０ ０ ０ ０ ０ ０ ）^Ｔ ：位相０→ｂ ＝（１ ０ ０ ０ ０ ０ ０ ）^Ｔ ：位相０
ａ ＝（０ ０ ０ ０ ０ ０ １ ）^Ｔ ：位相１→ｂ ＝（０ ０ ０ ０ ０ １ ０ ）^Ｔ ：位相２
ａ ＝（０ ０ ０ ０ ０ １ ０ ）^Ｔ ：位相２→ｂ ＝（０ ０ ０ １ ０ ０ ０ ）^Ｔ ：位相４
ａ ＝（０ ０ ０ ０ １ ０ ０ ）^Ｔ ：位相３→ｂ ＝（０ １ ０ ０ ０ １ ０ ）^Ｔ ：位相６
ａ ＝（０ ０ ０ １ ０ ０ ０ ）^Ｔ ：位相４→ｂ ＝（０ ０ ０ １ ０ ０ １ ）^Ｔ ：位相８
ａ ＝（０ ０ １ ０ ０ ０ １ ）^Ｔ ：位相５→ｂ ＝（０ １ ０ ０ １ １ ０ ）^Ｔ ：位相１０
ａ ＝（０ １ ０ ０ ０ １ ０ ）^Ｔ ：位相６→ｂ ＝（０ ０ １ １ ０ ０ ０ ）^Ｔ ：位相１２
となり、独立な７種類（次数種類）の状態ａに対して位相が２倍になっているのでこの行列Ｐは正しいことがわかる。
【０１１８】
【表７】

【０１１９】
行列Ｐ、行列Ａを回路で表わすとそれぞれ図１８、図１９になる。図１８、図１９にそれぞれ示した行列Ｐ，行列Ａの演算を行う回路は、それぞれＥＸ−ＯＲで構成される。図１８では、ｂ＝Ｐａを実現し、図１９はｃ＝Ａｂを実現する。図１８、図１９を用いて位相シフトおよびＭ系列発生器を構成すると、例えば図２０になる。
【０１２０】
図２０の構成は特性多項式の次数ステップでＭ系列発生器の初期値を得ることができ、モードを切り換えてＭ系列を生成する。図２０に示したＭ系列発生器は、図１８に示した行列Ｐを実現する回路５１、図１９に示した行列Ａを実現する回路５２、Ｄフリップフロップ５３、シフトレジスタ５４、セレクタ５５，５６、ＮＡＮＤ５７を備えている。
【０１２１】
なお、図２０の回路を図２１のように変形すれば、さらに高速にＭ系列発生器の初期値を得ることができる。
【０１２２】
図１４で示した回路と比べマスク回路が不要となり、回路削減されている。さらに、図２０の場合はＭ系列発生器の初期状態が次数ステップで得られるので一般的な構成よりも半分のステップ数で他のＭ系列発生器等に初期状態をロードすることが可能となる。
【０１２３】
一例として図２０の回路の動作を初期状態ｉｎｉｔＤＡＴＡを１１１１１１１ｂとし、ｐｈＤＡＴＡを１１００１００ｂとし１００ シフトした場合を図２２に示す。
【０１２４】
図２２において、ｉは位相シフト量ＬをＭＳＢから入力し、これが１の場合には位相を２倍＋１、０の場合には２倍とする。ステップ７では、位相は１２８ｋ＋１００となるが、位相１２８ｋは位相ｋと同じなので、ｋ＋１００となる。初期状態は、１１１１１１１ｂとしたが、この発明によれば、初期状態の位相ｋは何であっても、初期状態から１００シフトした状態をステップ７で得ることができる。
【０１２５】
ｓｔｅｐ０ 〜ｓｔｅｐ６ でマスクパターンを生成しｓｔｅｐ７ からＭ系列生成を始める。実際に特性多項式 ｆ（ｘ） ＝ ｘ^７ ＋ ｘ^３ ＋ １ 初期状態１１１１１１１ のＭ系列を１００ シフトしたＭ系列は０１０１１１１ であり表５の例と一致している。
【０１２６】
ここで、マスクパターンを用いず高速にシフトを行った後のＭ系列発生器の状態を計算する方法と、その設計方法およびハードウェアによる実現方法について考える。前述の実施の形態２では、まずマスクパターンを計算しその後にＭ系列を生成するが、本実施の形態３では、マスクパターンの計算とＭ系列の生成法の類似性に着目し、マスクパターンを用いず直接にＭ系列発生器の初期状態を生成する方法を実現できる。
【０１２７】
また、これを実現する回路は多数存在することを示し、その中で経験的に小さな回路規模で簡単に設計できる構成を得ることができる。前述の実施の形態２に示した方式に比べて、マスク回路が不要となり回路規模が削減される。また、Ｍ系列発生器の任意にシフト状態を得たい場合は、シフトした状態を並列に得ることができるので前述の実施の形態２と比べ半分のステップ数で計算することができる。
【０１２８】
以上によれば、ＲＯＭが必要なく、行列Ａ，Ｐは固定の行列となって簡単な回路で済む。また、行列Ａや行列Ｐの演算は、１クロックで実現することができるので、演算処理を高速化することが可能である。さらに、ｎクロックで任意にシフトした位相を得ることができる。
【０１２９】
実施の形態４．
前述の実施の形態３の応用として、位相の異なる符号を生成する回路を実現することができる。図２３は本発明の実施の形態４による符号発生装置の一構成例を示すブロック図である。図２３において、実施の形態３のレジスタ５４の出力は、スイッチ８５を介してたとえば４つのシフトレジスタ８１，８２，８３，８４に結合される。各シフトレジスタ８１，８２，８３，８４からは、位相の違う符号が出力される。
【０１３０】
このようにして、初期値の計算が高速に行えるので、一つの初期値計算で複数の符号発生器の初期状態を作り出すことができる。これにより、マスクを用いなくても異なる位相の符号を多数得ることが可能である。
【０１３１】
以上、本発明を実施の形態１〜４により説明したが、この発明の主旨の範囲内で種々の変形が可能であり、これらをこの発明の範囲から排除するものではない。
【０１３２】
【発明の効果】
以上説明したように、この発明によれば、生成多項式により固定される第１マスク変換行列と変換前のマスクベクトルとの積で新たなマスクベクトルを求め、シフト量データのＭＳＢがゼロでない場合に、生成多項式により固定される第２マスク変換行列とマスクベクトルとの積で新たなマスクベクトルを求め、シフト量データをＭＳＢ側へシフトし、上記各ステップを指定回数繰り返した後にマスクベクトルに基づくマスクパターンを出力するので、マスクパターンを高速に生成することができ、これにより、高速で小型の回路を実現することが可能な符号発生方法が得られるという効果を奏する。
【０１３３】
つぎの発明によれば、演算手段により生成多項式により固定される第１マスク変換行列と変換前のマスクベクトルとの積で新たなマスクベクトルを求め、シフト量データのＭＳＢがゼロでない場合に、生成多項式により固定される第２マスク変換行列とマスクベクトルとの積で新たなマスクベクトルを求め、シフト手段によりシフト量データをＭＳＢ側へシフトし、出力手段により上記演算手段とシフト手段を指定回数動作させた後にマスクベクトルに基づくマスクパターンを出力するようにしたので、マスクパターンを高速に生成することができ、これにより、高速で小型の回路を実現することが可能な符号発生装置が得られるという効果を奏する。
【０１３４】
つぎの発明によれば、マスクパターンを生成して、初期状態をマスクすることによりシフトを行うようにしたので、マスクパターンに応じて符号が生成され、専用の符号発生器が不要となることから、回路規模の削減を図ることが可能な符号発生装置が得られるという効果を奏する。
【０１３５】
つぎの発明によれば、第１演算手段により生成多項式により固定される第１マスク変換行列と符号発生器の状態を表す状態ベクトルとの積を求め、第１セレクタにより位相シフトと符号発生のいずれか一方を指示するモードに応じて第１演算手段の出力と状態ベクトルとのいずれか一方を選択し、第２演算手段により生成多項式により固定される第２マスク変換行列と第１セレクタ出力との積を求め、第２セレクタにより位相シフトと符号発生のいずれか一方を指示するモードおよびシフトデータのＭＳＢに応じて第１セレクタか、第２演算手段の出力のいずれか一方を選択し、新たな状態ベクトルとするようにしたので、簡単な構成でマスクパターンを用いず、直接に符号発生装置としての初期状態を生成すること、および符号を生成することが可能な符号発生装置が得られるという効果を奏する。
【０１３６】
つぎの発明によれば、状態ベクトルを、セレクタを介して位相の異なる符号をシフトさせる複数のシフトレジスタに接続させたので、一つの回路構成で符号発生を行うだけで、マスクを用いなくても、異なる位相の符号を多数得ることが可能な符号発生装置が得られるという効果を奏する。
【０１３７】
つぎの発明によれば、上記第１マスク変換行列および第２マスク変換行列のみを用いて位相シフト処理を行う構成としたため、マスクパターンを計算せずに、回路の状態を直接求めることが可能な符号発生装置を得ることができる、という効果を奏する。
【０１３８】
この発明によれば、特定構造を有する第１のマスク変換行列を用いる構成としたため、回路規模を大幅に小さくすることが可能な符号発生装置を得ることができる、という効果を奏する。
【０１３９】
つぎの発明によれば、上記第１マスク変換行列および第２マスク変換行列のみを用いて位相シフト処理を行うこととしたため、マスクパターンを計算せずに、回路の状態を直接求めることが可能な符号発生方法を得ることができる、という効果を奏する。
【０１４０】
この発明によれば、特定構造を有する第１のマスク変換行列を用いることとしたため、回路規模を小さくすることが可能な符号発生方法を得ることができる、という効果を奏する。
【図面の簡単な説明】
【図１】一般的なＭ系列発生器の一例を示すブロック図である。
【図２】Ｍ系列の性質を説明する図である。
【図３】Ｍ系列の性質を説明する図である。
【図４】Ｍ系列の性質を説明する図である。
【図５】Ｍ系列の性質を説明する図である。
【図６】一般的なＭ系列発生器の他の例を示すブロック図である。
【図７】本発明の実施の形態１によるマスクパターン生成回路の一構成例を示す回路図である。
【図８】本発明の実施の形態１によるＭ系列発生器の一構成例を示すブロック図である。
【図９】本実施の形態１の変形例を示すブロック図である。
【図１０】本実施の形態１の動作を説明するフローチャートである。
【図１１】本実施の形態１による位相シフトの手順を説明する図である。
【図１２】本発明の実施の形態２によるマスクパターン生成回路の他の例を示す回路図である。
【図１３】本発明の実施の形態２によるＭ系列発生器の一構成例を示すブロック図である。
【図１４】本実施の形態２によるマスク回路の一構成例を示す回路図である。
【図１５】本発明の実施の形態３によるＭ系列発生器の原理を説明する図である。
【図１６】本発明の実施の形態３によるＭ系列発生器の原理を別の観点から説明する図である。
【図１７】本実施の形態３による一行列を実現する一構成例を示す回路図である。
【図１８】本実施の形態３による他の行列を実現する別の構成例を示す回路図である。
【図１９】本実施の形態３によるＭ系列発生器の一構成例を示すブロック図である。
【図２０】本実施の形態３によるＭ系列発生器の変形例を示す図である。
【図２１】本実施の形態３による位相シフトの手順を説明する図である。
【図２２】本発明の実施の形態４によるＭ系列発生器の一構成例を示すブロック図である。
【図２３】従来例による符号発生装置の一例を示すブロック図である。
【図２４】従来例によるマスク変換動作を説明するフローチャートである。
【図２５】従来例による位相シフトの手順を説明する図である。
【図２６】従来例による符号発生装置の他の例を示すブロック図である。
【符号の説明】
２１ 演算器、２１Ａ〜２１Ｇ マスクパターン生成回路、２２，２３ シフトレジスタ、３１ マスクパターン生成回路、３２ マスク回路、３３ 初期状態バッファ、３４ シフトレジスタ、３５ フリップフロップ、４１，４５ ＥＸ−ＯＲ、４２，４６ シフトレジスタ、５１，５１Ａ，５１Ｂ，５１Ｃ 回路、５２，５２Ａ，５２Ｂ，５２Ｃ 回路、５３ Ｄフリップフロップ、５４ シフトレジスタ、５５，５６，６１Ａ，６１Ｂ，６１Ｃ セレクタ、５７ ＮＡＮＤ、８５ スイッチ、８１〜８４ シフトレジスタ。[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a code generation method and a code generation device, and more particularly to a code generation method and a code generation device for generating a code sequence such as an M sequence or a GOLD sequence.
[0002]
[Prior art]
In recent years, CDMA (Code Division Multiple Access) has attracted attention as a next-generation communication method because of its large channel capacity in mobile communication. In the CDMA system, a different PN sequence is used for each channel in order to separate each channel. For this PN sequence, an M-sequence (maximum-length sequence), a GOLD sequence generated from the M sequence, and the like are frequently used. UsedThising.
[0003]
However, when the period of the M sequence is long, an enormous amount of arithmetic processing is required to generate an arbitrarily phase-shifted sequence. For this reason, it is very important to establish a method for performing phase shift calculation at high speed, with a small amount of memory and a circuit scale. As a method for generating an arbitrarily shifted M-sequence, the M-sequence can be shifted by a mask pattern, but enormous calculation processing is required to generate a mask pattern.
[0004]
As this type of M-sequence generation device, there are, for example, Japanese Patent Application Laid-Open Nos. 7-297855 and 8-18550.
[0005]
First, the technique disclosed in Japanese Patent Laid-Open No. 7-297865 will be described with reference to FIG. FIG. 24 discloses a code generator disclosed in the above-mentioned Japanese Patent Application Laid-Open No. 7-297685. The code generator shown in FIG. 24 outputs a PN generator 101 that generates a PN sequence, masks the PN sequence output from the PN generator 101 with the PN mask data output from the PN mask converter 102, and outputs the PN sequence. And a PN mask converter 102 for supplying PN mask data to the mask circuit 103.
[0006]
Next, the PN mask converter 102 will be described with reference to FIG. FIG. 25 is a flowchart for explaining a mask conversion method of the PN mask converter 102, and FIG. 26 shows m and phase changes corresponding to changes in M and LSB. 25 and 26, the initial mask pattern is changed to m of k shift._kAnd m_kMask pattern M shifted by 100 from_l ¹⁰⁰m_k= M_{k + 100}Ask for. Shift amount L = 100 = 1100100b (b is binary), M_lIs a matrix shifted by 1 and 1 step corresponds to one round of the loop. In FIG. 25, the LSB is extracted while shifting the shift amount 1100100b to the right, and m ← Mm is executed when LSB = 1.
[0007]
Specifically, when the shift amount is larger than 0 (step S101, Yes route) and the LSB of the shift amount is 0 (step S102, Yes route), Mm is inserted into m (step S103). An operation for shifting the shift amount to the right is performed (step S104). If the LSB of the shift amount is other than 0 (step S102, No route), an operation for shifting the shift amount to the right is performed in step S104.
[0008]
Thereafter, if the shift amount is greater than 0 (step S105, Yes route), the process of M ← MM is performed (step S106). If the shift amount is 0 (step S105, No route), the process directly returns to step S101. When the shift amount is 0 in step S101, the mask pattern is supplied to the mask circuit 103.
[0009]
Next, the technique disclosed in Japanese Patent Laid-Open No. 8-18550 will be described with reference to FIG. FIG. 27 shows a code generator according to Japanese Patent Laid-Open No. 8-18550. 27 includes a register 201, an arithmetic circuit 202, a memory 203, a switch 204, and a control circuit 205.
[0010]
As shown in FIG. 27, the code generator is provided with a register 201 that holds an n-bit code and an arithmetic circuit 202 that performs a matrix operation on the register 201, so that the operation result is stored in the register 201. By performing feedback, the matrix of the arithmetic circuit 202 that sequentially generates the code sequence is changed by the memory 203 and the switch 204 and repeatedly used to generate a desired code sequence.
[0011]
[Problems to be solved by the invention]
However, the code generator disclosed in the above-mentioned Japanese Patent Application Laid-Open No. 7-297685 requires a general-purpose matrix × vector operation, and the circuit scale becomes large to perform in one step by hardware. In addition, n steps are required to realize with software, and there is a problem that processing time becomes long. Furthermore, the code generator disclosed in the above-mentioned Japanese Patent Application Laid-Open No. 7-297865 has a problem that the circuit scale becomes large because the PN generator 101 and the matrix × matrix operation are required.
[0012]
Further, since the code generator disclosed in Japanese Patent Laid-Open No. 8-18550 requires a ROM (memory 203), the circuit scale is increased and a general-purpose matrix × vector arithmetic circuit 202 is required. , The circuit scale becomes larger and n²Since the number of steps is required and the number of steps increases, there is a problem that the processing time becomes long.
[0013]
The present invention solves the above-mentioned conventional problems,High-speed mask pattern generation and circuit miniaturizationAn object of the present invention is to provide a code generation method and a code generation apparatus capable of realizing the above.
[0014]
In addition, the present invention pays attention to the similarity between the calculation of the mask pattern and the M-sequence generation method, and does not use the mask patternDirectly into the shift registerAn object of the present invention is to obtain a code generator capable of generating an initial state.
[0015]
[Means for Solving the Problems]
In order to solve the above-described problems and achieve the object, a code generator according to the present invention obtains a new mask vector by a product of a first mask transformation matrix fixed by a generator polynomial and a mask vector before transformation. And a second step of obtaining a new mask vector by a product of the second mask transformation matrix fixed by the generator polynomial and the mask vector obtained in the first step when the MSB of the shift amount data is not zero. A third step of shifting the shift amount data to the MSB side, a fourth step of outputting a mask pattern based on a mask vector after repeating the first step, the second step, and the third step a specified number of times, Is included.
[0016]
According to the present invention, a new mask vector is obtained by the product of the first mask transformation matrix fixed by the generator polynomial and the mask vector before conversion, and is fixed by the generator polynomial when the MSB of the shift amount data is not zero. Since a new mask vector is obtained by the product of the second mask transformation matrix and the mask vector, the shift amount data is shifted to the MSB side, and after repeating the above steps a specified number of times, a mask pattern based on the mask vector is output. A mask pattern can be generated at high speed, which makes it possible to realize a small circuit at high speed.
[0017]
The code generator according to the next invention obtains a new mask vector by the product of the first mask transformation matrix fixed by the generator polynomial and the mask vector before the transformation, and generates when the MSB of the shift amount data is not zero. An arithmetic means for obtaining a new mask vector by a product of a second mask transformation matrix fixed by a polynomial and the mask vector, a shift means for shifting the shift amount data to the MSB side, the arithmetic means and the shift means Output means for outputting a mask pattern based on a mask vector after operating for a specified number of times.
[0018]
According to the present invention, a new mask vector is obtained by the product of the first mask transformation matrix fixed by the generator polynomial by the arithmetic means and the mask vector before conversion, and when the MSB of the shift amount data is not zero, the generator polynomial is obtained. A new mask vector is obtained by the product of the second mask transformation matrix and the mask vector fixed by the step, the shift amount data is shifted to the MSB side by the shift means, and the arithmetic means and the shift means are operated a specified number of times by the output means. After that, since the mask pattern based on the mask vector is output, the mask pattern can be generated at a high speed, whereby a high-speed and small circuit can be realized.
[0019]
The code generator according to the next invention is:Using the arithmetic means, the shift means, and the output means, a mask pattern for shifting data representing an arbitrary initial state by a set phase shift amount is generated. A mask pattern generating means for generating a mask pattern to be shifted phase by phase, and a mask pattern for shifting by the set phase shift amount generated by the mask pattern generating means, and masking data representing an arbitrary initial state to 1 bit A mask means for obtaining the code sequentially by 1 bit using the mask pattern for shifting by one phase,It is equipped with.
[0020]
According to this invention, since the mask pattern is generated and the initial state is masked to perform the shift, a code is generated according to the mask pattern, and a dedicated code generator is not required. It is possible to reduce the circuit scale.
[0021]
The code generator according to the next invention is a first arithmetic means for obtaining a product of a first mask transformation matrix fixed by a generator polynomial and a state vector representing a state of the code generator, and any one of phase shift and code generation A first selector that selects one of the output of the first computing means and the state vector in accordance with a mode for instructing one, a second mask transformation matrix fixed by a generator polynomial, and a first selector output; A second calculating means for obtaining a product, a mode for instructing one of phase shift and code generation, and either the first selector or the output of the second calculating means in accordance with the MSB of the shift data And a second selector for setting a new state vector.
[0022]
According to this invention, the product of the first mask transformation matrix fixed by the generator polynomial by the first arithmetic means and the state vector representing the state of the code generator is obtained, and either the phase shift or the code generation is obtained by the first selector. Either one of the output of the first calculation means and the state vector is selected according to the mode for instructing one of them, and the product of the second mask transformation matrix fixed by the generator polynomial by the second calculation means and the first selector output The second selector selects either the first selector or the output of the second calculation means in accordance with the mode instructing one of phase shift and code generation by the second selector and the MSB of the shift data, and a new state is obtained. Since the vector is used, the initial state as a code generator can be directly generated and the code can be generated without using a mask pattern with a simple configuration. It is possible.
[0023]
Code generator according to next inventionInThe state vector is connected to a plurality of shift registers for shifting codes having different phases through a selector.
[0024]
According to the present invention, since the state vector is connected to the plurality of shift registers that shift the codes having different phases through the selector, it is possible to generate a code with one circuit configuration without using a mask. It is possible to obtain a large number of codes having different phases.
[0025]
In the code generator according to the next invention, the first mask transformation matrix is specified on the basis of a mask pattern capable of a phase shift twice as large as the phase shift processing by the second mask transformation matrix. .
[0026]
According to the present invention, since the phase shift process is performed using only the first mask transformation matrix and the second mask transformation matrix, the circuit state can be directly obtained without calculating the mask pattern.
[0027]
In the code generator according to the next invention, the first mask transformation matrix further includes a generator polynomial f (x) = g _n x ⁿ + G _n-1 x ^n-1 + G _n-2 x ^n-2 + ... + g ₀ x ⁰ And n is an even number,
[Expression 18]

And the generator polynomial f (x) = g _n x ⁿ + G _n-1 x ^n-1 + G _n-2 x ^n-2 + ... + g ₀ x ⁰ And n is an odd number,
[Equation 19]

It is characterized by.
[0028]
According to the present invention, the design is facilitated by using the first mask transformation matrix having a specific structure, and the circuit scale can be reduced.
[0029]
A code generation method according to the next invention includes a first calculation step for obtaining a product of a first mask transformation matrix fixed by a generator polynomial and a state vector representing a state of the code generator, and any of phase shift and code generation. A first selection step of selecting one of the calculation result of the first calculation step and the state vector, a second mask transformation matrix fixed by a generator polynomial, The selection by the first selection step according to the second calculation step for obtaining the product of the selection result by the first selection step, the mode for instructing one of phase shift and code generation, and the MSB of the shift data One of the result and the calculation result of the second calculation step is selected, and the selection result is used as a new state vector. And the first mask transformation matrix is a matrix specified based on a mask pattern capable of a phase shift twice the phase shift processing by the second mask transformation matrix, and the first mask transformation Arbitrary phase shift processing is performed by a combination of a matrix and the second mask transformation matrix.
[0030]
According to the present invention, since the phase shift process is performed using only the first mask transformation matrix and the second mask transformation matrix, the circuit state can be directly obtained without calculating the mask pattern.
[0031]
In the code generation method according to the next invention, as the first mask transformation matrix, a generator polynomial f (x) = g _n x ⁿ + G _n-1 x ^n-1 + G _n-2 x ^n-2 + ... + g ₀ x ⁰ And n is an even number,
[Expression 20]

And the generator polynomial f (x) = g _n x ⁿ + G _n-1 x ^n-1 + G _n-2 x ^n-2 + ... + g ₀ x ⁰ And n is an odd number,
[Expression 21]

It is characterized by using.
[0032]
According to the present invention, the design is facilitated by using the first mask transformation matrix having a specific structure, and the circuit scale can be reduced.
0033]
DETAILED DESCRIPTION OF THE INVENTION
Exemplary embodiments of a code generation method and a code generation apparatus according to the present invention will be explained below in detail with reference to the accompanying drawings.
0034]
Embodiment 1 FIG.
First, before starting the description of the present embodiment, a description will be given of what is generally used for the principle of generating an M-phase with an arbitrary phase using a mask pattern. Here, an M-sequence generator is taken as an example of the code generator.
0035]
(M-sequence generation principle)
As an example, the characteristic polynomial f (x) = x⁴  + X³Take the M series of +1. FIG. 1 shows a characteristic polynomial f (x) = x⁴  + X³Fig. 2 shows an M-sequence generator for generating an M sequence of +1. The code generator shown in FIG. 1 includes an EX-OR 11 and a four-stage shift register 12. Since the degree of the characteristic polynomial is 4, the number of stages of the shift register 12 is 4. X⁴X excluding³And 1 = x⁰Indicates 3 and 0 which are the positions of the feedback taps.
0036]
Each flip-flop D of the M-sequence generator shown in FIG.₀~ D₃The state is shown in Table 1 below. Since the order of the characteristic polynomial is 4, the period of the M sequence is 2⁴−1 = 15, and after step 14 in Table 1, the same operation is repeated from step 0. In the case of Table 1, the case of all 1 is the initial value, but since the state of the M sequence generator takes all the states other than the case of all 0, the initial value should be arbitrarily set if the pattern is all other than 0. Can do.
0037]
[Table 1]

0038]
(Generation of shifted M-sequence)
First, the nature of the M sequence will be described. The M sequence generated from the M sequence generator of FIG. 1 is as shown in FIG. 2, and it is understood that this M sequence has the properties shown in FIG. 3 in consideration of the operation of the M sequence generator. In this way, the input and output are always correct when the above calculation is moved left and right. Where xⁿPairOnlyWhen combined, it becomes as shown in FIG.
0039]
The following operation is an operation on GF (2) and is equivalent to taking the modulo 2 of the operation result.
x^{n + 4}  = X^{n + 3}  + Xⁿ
x^{n + 4}  + X^{n + 3}  + Xⁿ  = 0 (+ and-are the same in the calculation on GF (2))
xⁿ  (X⁴+ X³  + 1) = 0
Here, the characteristic polynomial f (x) = x⁴+ X³+1 appears.
More generally,
G (x) f (x) = 0 (G (x) is an arbitrary polynomial)
And Equation (1) is established.
0040]
Here, for example, consider the following equation.

Thus, it can be seen that there is a relationship shown in FIG. In this way, the relationship of each phase of the M series can be calculated by G (x) multiplied by the characteristic polynomial f (x).
0041]
Then x^mAnd the remainder R (X) divided by f (x), x^mIs divided by f (x), and Q (x), the following equation holds.
x^m= Q (x) f (x) + R (x)
From equation (1)
Q (x) f (x) = 0
So,
x^m= R (x)
Thus, Expression (2) is established.
0042]
Next, the shift of the M series by the mask pattern will be described. Table 1 shows the operation of the M-sequence generator.ⁿAre displayed together as shown in Table 2.
0043]
[Table 2]

0044]
Here, x from Formula (2)^m= R (x), where R (x) is x^mIs the remainder of dividing f by (x), so the order is smaller than the order of f (x). That is, f (x) = x⁴+ X³In the case of +1, R (x) = r₃x³  + R₂x²  + R₁x + r₀Can be expressed as From this, the following equation holds.
x^m= R₃x³+ R₂x²  + R₁x + r₀
x^{n + m}= R₃x^{n + 3}+ R₃x^{n + 2}+ R₃x^{n + 1}+ R₃xⁿ
0045]
Compared with Table 2, x^{n + 3}, X^{n + 2}, X^{n + 1}, XⁿAppears in the M-sequence generator. For this reason, FIG. 7 shows a configuration in which an adder 13 is added to the M-sequence generator shown in FIG. As shown in FIG. 7, an M-sequence with an arbitrary phase shift can be obtained by using a configuration in which the output of each tap can be synthesized according to a mask pattern.
out2 = r₀D₀  + R₁D₁+ R₂D₂  + R₃D₃
A shifted M sequence is obtained by calculating. More generally, if there are several orders of M sequences with different phases, all phases can be expressed by their linear combination.
0046]
Next, a mask pattern generation method will be described. To obtain a mask pattern that generates an L-phase shifted M sequence," x ^L ÷ characteristic polynomial f (x) "To obtain the remainder R (x). Characteristic polynomial f (x) = x⁴+ X³To find the mask pattern when shifting -5 phases for example +1" x ⁵ ÷ (X ⁴ + X ³ +1) "Find the remainder. less than " x ⁵ ÷ (X ⁴ + X ³ +1) "The calculation of is shown.
0047]
[Expression 1]

0048]
Remainder obtained as a result of calculation R (x) = x³+ X¹From +1, the mask pattern is as follows.
(R3, r2, r1, r0) = (1, 0, 1, 1)
0049]
M series shifted by 5 from this mask pattern is D₃+ D₁+ D₀It turns out that it is obtained more. When the operation of FIG. 7 is actually examined with the above mask pattern, it becomes as shown in Table 3, and D of step n₀And D of step n-5₃+ D₁+ D₀Are the same. That is, D₃+ D₁+ D₀D₀5 step is the future output.
0050]
[Table 3]

0051]
Next, the description of the present embodiment will be started. A method for obtaining a mask pattern by a logical operation will be described. The following operations are operations on GF (2).
0052]
(algorithm)
In order to obtain a mask pattern for generating an L-phase shifted M sequence," x ^L ÷ characteristic polynomial f (x) "The remainder R_L(X) may be obtained. The proposed algorithm is described below. After that" g (x) ÷ f (x) "The remainder R (x) is R (x) = R_{f (x)}[G (x)]. R_L(X) = R_{f (x)}[X^L]
0053]
R₀(X) = R_{f (x)}[X⁰] Than,
▲ 1 ▼ R₀(X) = 1
In general,
R_{f (x)}[X (x)] = x (x) + Qx (x) f (x)
R_{f (x)}[Y (x)] = y (x) + Qy (x) f (x)
Qx (x) can be expressed as a quotient obtained by dividing x (x) by f (x), and Qy (x) can be expressed as a quotient obtained by dividing y (x) by f (x).
R_{f (x)}[X (x)] R_{f (x)}[Y (x)] = x (x) y (x) + (Qx (x) y (x) + Qy (x) x (x) + Qx (x) Qy (x) f (x)) f ( x)
R_{f (x)}[R_{f (x)}[X (x)] R_{f (x)}[Y (x)]] = R_{f (x)}[X (x) y (x)] and vice versa.
0054]
Therefore,
▲ 2 ▼ R_2k(X) = R_{f (x)}[R_k(X)²]
▲ 3 ▼ R_{k + 1}(X) = R_{f (x)}[XR_k(X)]
As shown, Equation (3) is established.
0055]
R for any L by combining (1), (2), and (3) in the above formula (3)_L(X) can be obtained.
For example R₁₀(X),
R₁₀(X) = R_{f (x)}[R₅(X)²] (2)
R₅(X) = R_{f (x)}[XR₄(X)] ▲ 3 ▼
R₄(X) = R_{f (x)}[R₂(X)²] (2)
R₂(X) = R_{f (x)}[R₁(X)²] (2)
R₁(X) = R_{f (x)}[XR₀(X)] ▲ 3 ▼
R₀(X) = 1 (1)
Equation (4) is established as follows.
0056]
R_kIf k in (x) is an even number, the equation (2) is repeated, and if k is an odd number, the equation (3) is sequentially performed until k = 0. If k = 0, equation (1) is obtained. If equation (4) is calculated from the reverse, R₁₀(X) can be obtained.
R₁₀(X) = R_{f (x)}[R_{f (x)}[XR_{f (x)}[R_{f (x)}[R_{f (x)}[XR₀(X)]²]²]]²]
The calculation of equation (4) is expanded as 10 = 5 × 2, 5 = 4 + 1, 4 = 2 × 2, 2 = 1 × 2, and 10 = ((1 × 2) × 2 + 1) × 2. This expansion is easily obtained by expressing L in a binary number.
L = l₀  + 2l₁  +2²l₂+… + 2^n-2l_n-2+2^n-1l_n-1= ((... (l_n-1× 2 + l_n-2) X2 + ... + l₂) X 2 + l₁) X 2 + l₀
0057]
Here, formula (2) and formula (3) are summarized A_{f (x)}Define [g (x), i] i = [1, 0]. The following formula (5) is established.
0058]
[Expression 2]

0059]
A_{f (x)}R using [g (x), i]_LEquation (6) can be obtained from (x) as shown below.
A₀(X) = R₀(X)
A_k(X) = A_{f (x)}[A_k-1(X), l_n-1-k]
R_L(X) = A_n-1(X)
However, L = l₀  + 2l₁  +2²l₂+… + 2^n-2l_n-2+2^n-1l_n-1
As shown in the above equation, the calculation of equation (6) is performed n (order of f (x)) times to obtain R_L(X) can be obtained.
0060]
Next, a hardware implementation method will be described. In order to realize the mask pattern generation method by hardware, the above equation (6) may be realized by hardware. Here, as an example, the characteristic polynomial f (x) = x⁷  + X³Take the case of +1.
0061]
First, the squaring circuit will be described. In general g (x) = x^k+ X^j+ XⁱIf + ... + 1, then g (x)²= X^2k+ X^2j+ X²ⁱ+ ... +1 is easily obtained. Since the order of f (x) is 7, the order of the polynomial in the input and output of Equation (6) is 6. Where A (x) is
A (x) = a₆x⁶+ A₅x⁵  + A₄x⁴+ A₃x³  + A₂x²+ A₁x + a₀
Defined as
A²(X) = a₆x¹²+ A₅x¹⁰+ A₄x⁸  + A₃x⁶+ A₂x⁴  + A₁x²+ A₀
Is required.
0062]
R_{f (x)}  [A²(X)] is obtained as follows.
R_{f (x)}[A²(X)] = R_{f (x)}[A₆x¹²  + A₅x¹⁰  + A₄x⁸+ A₃x⁶  + A₂x⁴+ A₁x²  + A₀] = A₆R_{f (x)}[X¹²] + A₅R_{f (x)}[X¹⁰] + A₄R_{f (x)}[X⁸] + A₃x⁶+ A₂x⁴  + A₁x²+ A₀
Since f (x) is 7th order, it is not necessary to obtain a remainder for terms of 6th order or less.
R_{f (x)}[X¹²] = X⁵  + X⁴+ X
R_{f (x)}[X¹⁰] = X⁶  + X³
R_{f (x)}[X⁸] = X⁴  + X
Than,
R_{f (x)}  [A²(X)] = (a₅  + A₃X⁶+ A₆x⁵  + (A₆  + A₄+ A₂X⁴  + A₅x³+ A₁x²  + (A₆  + A₄) X + a₀
This is Equation (7).
0063]
Next, R_{f (x)}[XA²(X)] is obtained. R_{f (x)}[A²(X)] = b₆x⁶  + B₅x⁵+ B₄x⁴  + B₃x³+ B₂x²  + B₁x + b₀And
However, from equation (7)
b₆= A₅+ A₃, B₅= A₆
b₄= A₆+ A₄  + A₂
b₃= A₅
b₂= A₁
b₁= A₆+ A₄
b₀= A₀

R_{f (x)}[X⁷] = X³From +1,
R_{f (x)}[XA²(X)] = b₅x⁶+ B₄x⁵  + B₃x⁴+ (B₂+ B₆X³  + B₁x²+ B₀x + b₆
Formula (8) is materialized as follows.
0064]
If Formula (5) is implemented by hardware from Formula (7) and Formula (8), it is easy as shown in FIG.NaIt can be realized with a configuration. The arithmetic unit shown in FIG. 8 includes an EX-OR, a selector, and the like. The circuit shown in FIG. 8 is a hardware implementation of the following equation.
0065]
[Equation 3]

0066]
In order to generate the mask pattern, the equation (5) may be repeated as shown in the equation (6), and the hardware may be configured as shown in FIG. FIG. 9 shows a mask pattern generation circuit, 21 indicates the arithmetic unit of FIG. 8, and 22 and 23 indicate shift registers, respectively. In addition, as a modification of FIG. 9, a configuration in which parallel connection is made as shown in FIG. 10 may be adopted. In FIG. 10, mask pattern generation circuits 21A to 21G are connected in series.
0067]
The configuration of FIG. 9 can obtain a mask pattern in the order of the characteristic polynomial, but if configured as shown in FIG. 10, a mask pattern can be obtained at a higher speed. However, when the degree of the characteristic polynomial is large, the circuit configuration of FIG. 10 is much larger than that of FIG. It is possible to make the configuration of FIG. 10 slightly smaller by performing logical compression.
0068]
Next, the operation of the mask pattern generator will be described. First, the operation of the circuit of FIG. 9 will be described. Table 4 shows the operation when L = 100. When 100 is expressed in binary, it is 1100100, so this is input to i 2 from the MSB. D which is the output of the flip-flop₆~ D₀And A_{f (x)}[G (x), i] b inside the circuit₆~ B₀Indicates. Characteristic polynomial f (x) = x⁷+ X³  Since the order of +1 is 7, the mask pattern 1110111 can be obtained in step 7.
0069]
[Table 4]

0070]
Here, considering the correspondence with the technique disclosed in Japanese Patent Laid-Open No. 7-297865 cited as a conventional example, a specific flow of operation will be described. FIG. 11 is a flowchart for explaining the operation according to the first embodiment, and FIG. 12 is a diagram for explaining m and phase changes corresponding to MSB changes.
0071]
In the first embodiment, first, if the counter value is larger than 0 (step S1, Yes route), the calculation of m ← Pm is performed (step S2). In this case, when the MSB of the shift amount is not 0 (step S3, No route), m ← Am is further calculated (step S4), and the shift amount is shifted to the left (step S5). The value is subtracted by 1 (step S6). When the MSB of the shift amount is 0 (step S3, Yes route), the calculation of step S4 is skipped, the shift amount is shifted to the left in step S5, and the count value is subtracted by 1 in step S6. Thereafter, the process returns to step S1. If the shift amount is 0 or less in step S1, mask pattern output is performed.
0072]
In FIG. 12, the shift amount L = 100 = 1100100b, and one step corresponds to one round of the loop. If the degree of the generator polynomial is 7, the period of the M sequence is 2⁷−1 = 127. The 127k phase shift is the same as the 0 shift, and the 128k shift is the same as the k shift. Therefore, 128k + 100 = k + 100.
0073]
According to the above, the calculation corresponding to M ← MM is not necessary, and the calculation of m ← Pm can be realized with a much smaller circuit scale and calculation amount than the calculation of M ← MM. Conventionally, since the calculation of M ← MM is obtained only for the first row vector and the other rows are calculated therefrom, the amount of calculation requires 2n-1 steps. Compared to this, the first embodiment can be realized in one step with a small circuit. Even when implemented by software, since it is a product of a matrix and a vector, it can be implemented in n steps.
0074]
In particular, in the first embodiment, since the matrix cannot be fixed in principle, in the first embodiment, the calculation of the matrix A and the matrix P can be fixed by a generator polynomial, so that hardware can be provided on a very small scale. It becomes.
0075]
Embodiment 2. FIG.
By using the mask pattern generation method according to the first embodiment described above, the phase of the M-sequence generator can be arbitrarily shifted. However, in the second embodiment described below, the phase can be arbitrarily changed from any initial state. Generation of the phase-shifted M sequence will be described. If the mask pattern generation method as described above is used, the phase of the M-sequence generator can be arbitrarily shifted. Here, a circuit configuration in which the M-sequence generator and the mask pattern generation circuit are shared and the hardware scale is reduced will be described. To do.
0076]
If a mask pattern R (x) that shifts by L phase is obtained, the mask pattern that is shifted by L + 1 phase is R_{f (x)}[XR (x)]. Since this circuit is already incorporated in the mask pattern generation circuit, it can be easily realized. Therefore, A shown in FIG._{f (x)}The circuit realizing [g (x), i] is improved as shown in FIG. The circuit shown in FIG. 13 includes an EX-OR and a selector. This circuit is expressed as follows.
0077]
[Expression 4]

0078]
When mode = 0, the same operation as that of the mask pattern generation circuit is performed, and when mode = 1, a mask pattern shifted by one phase is obtained.
0079]
The circuit shown in FIG. 13 is used as a mask pattern generation circuit, thereby configuring an M-sequence generator that generates an M-sequence. FIG. 14 shows an M-sequence generator that generates an M-sequence arbitrarily shifted from an arbitrary initial state. The M-sequence generator shown in FIG. 14 includes a mask pattern generation circuit 31 that generates the mask pattern shown in FIG. 7, a mask circuit 32 that masks and outputs data supplied from the initial state buffer 33 by a clock, and an initial state Is provided with an initial state buffer 33 for supplying the data to the mask circuit 32, a shift amount buffer for extracting the shift amount data from the MSB by the clock, that is, a shift register 34, and a flip-flop 35 for holding the output of the mask circuit 32 according to the clock. .
0080]
The operation first writes the first n data of the M series in the initial state buffer 33 and writes the shift amount from the initial state in the shift register 34. Next, when mode = 0, clk is input n times of the order of f (x), a shift amount mask pattern set in the shift register 34 is generated, and 1 bit is obtained for the M sequence shifted from the initial state. Next, by generating a mask pattern shifted by one every time clk is input with mode = 1, it is possible to obtain M sequences sequentially by 1 bit.
0081]
The internal configuration of the mask circuit 32 is shown in FIG. The mask circuit 32 is composed of a combination of EX-OR and AND. Although the configuration is the same as that shown in FIG. 7, the circuit can be reduced if the initial state is fixed. In particular, when there is only one 1 in the initial state, the mask circuit is unnecessary.
0082]
Next, the operation will be described. Table 5 shows the M sequence generated when the initial state 1111111 is actually shifted by 100.
0083]
[Table 5]

0084]
A mask pattern is generated in step 0 to step 6 to set Mode = 0, and the same operation as in Table 4 is performed. From step 7, Mode = 1 is set and M-sequence generation is started. Actually the characteristic polynomial f (x) = x⁷  + X³The M sequence in the +1 initial state 1111111 is as shown in Table 6, and when it is shifted by 100, it is 0101111, which matches the output of Table 5.
0085]
[Table 6]

0086]
The circuit for generating the arbitrarily shifted M-sequence shown here is characterized in that the time required for the initial setting when arbitrarily shifted is short.
0087]
Embodiment 3 FIG.
In the third embodiment described below, a method for arbitrarily shifting a phase by a logical operation without using a mask pattern will be described. As a method for generating a shifted M sequence, the M sequence can be shifted by a mask pattern. In this third embodiment, a new algorithm for M-sequence high-speed shift without using a mask pattern and a hardware implementation method thereof will be described. The following operations are operations on GF (2).
0088]
First, the matrix display of the M series generation circuit will be described. In the method of obtaining a mask pattern by a logical operation, A_{f (x)}[G (x), i] is defined, a mask pattern is generated using this, and a method of performing M-sequence phase shift has been proposed. In many cases, such a method requires two-stage operations of mask pattern generation and shift register initial value generation. Therefore, a method for directly generating the initial value of the shift register without obtaining the mask pattern is considered.
0089]
FIG. 16 shows the characteristic polynomial f (x) = x⁴+ X³+1 M-sequence generator, 41 is EX-OR, 42 is a shift register, a₀~ A₃Is the output of each tap. When this is displayed in matrix, it becomes as follows.
0090]
[Equation 5]

0091]
The initial state is a₀Then, the n-shifted state can be expressed by the following equation.
a_n= Aⁿa₀
In general, an n-stage LFSR can be expressed using an n × n matrix. There are many matrices that generate M sequences, such as the matrix A, for one characteristic polynomial. Although details are omitted, since each element of a is an M-sequence with a different phase, one characteristic polynomial (2ⁿ-2) There are P (n-1). This is related by a regular matrix T as shown below.
A '= T^-1AT
0092]
Next, an arbitrary shift method without using a mask pattern will be described. In the description of the general example, the mask pattern is obtained from the following three formulas. However, considering that the M value can be generated while the initial value is fixed and the mask pattern is sequentially advanced, the formula (3) itself generates the M sequence. I understand that
▲ 1 ▼ R₀(X) = 1
▲ 2 ▼ R_2k(X) = R_{f (x)}[R_k(X)²]
▲ 3 ▼ R_{k + 1}(X) = R_{f (x)}  [XR_k(X)]
If the above equation (3) is represented by a circuit, it will be as shown in FIG. The M-sequence generator shown in FIG. 17 has two registers (D₂, D₃) Between the EX-OR45.
0093]
When expressed in a matrix as before, it is expressed as follows: B = A^TIt turns out that it is.
0094]
[Formula 6]

0095]
Similarly, expression (2) can be expressed as a matrix as follows.
0096]
[Expression 7]

0097]
The general method described in the first embodiment will be described using a matrix.₀= Mask pattern to be arbitrarily shifted using matrices B and C as (1, 0, 0, 0)-Is creating. The matrices B and C are matrices for performing the following operations.
b_{k + 1}= B b_k
b_2k= C b_k
b₀Is a mask pattern shifted by 0. For example, a mask pattern shifted by 11 is expressed as follows.
b₁₁= B¹¹b₀
0098]
In a general method, when 11 shifts are performed, 11 is represented by a binary number and is 1011b. Therefore, 1 is (BC) and 0 is (C) and is sequentially multiplied from the MSB to obtain the following formula (formula (9)).
(BC) (BC) (C) (BC) b₀
0099]
On the other hand, B = C between the matrices B and C^-1B²There is a relationship of C,
CB = B²C holds,

Even if 0 shift is doubled, it is 0 shift, so Cb₀= B₀And
(BC) (BC) (C) (BC) b₀= B¹¹b₀
It becomes.
[0100]
Here, although it was not mentioned in the general method, the initial value b₀Well thenThe b _k TheWhen used, it is as follows.

B from M-sequence periodicity²⁴= B
[0101]
Therefore,
B¹¹C⁴b_k= B^{11 + k}b₀= B¹¹b_k
A mask pattern shifted by 11 is obtained regardless of the initial value, and this is generally true regardless of the shift amount of 11, and b_kCan take any pattern other than zeroInMore C⁴It can be seen that = E. Therefore, the following formula (Formula (10)) is established.
(BC) (BC) (C) (BC) = B¹¹
[0102]
Generally, when the degree of the characteristic polynomial is n, Cⁿ= E.
here,
A = T^-1BT equation (11)
For example, T is obtained as follows. A = T^-1There are many Ts that satisfy BT.
[0103]
[Equation 8]

[0104]
Here, P is defined corresponding to C.
P = T^-1CT formula (12)
When 11 shifts are performed using the matrix P,

11 shifts can be performed. In general, if A and P are obtained, an arbitrary shift can be performed, and the state of the circuit of FIG. 16 can be directly obtained without calculating a mask pattern.
[0105]
Next, realization by hardware is given as an example. Here, when P is specifically calculated, the formula (12In the case of the matrix T), the following equation is obtained.
[0106]
[Equation 9]

[0107]
If this is expressed by a circuit, it can be realized by two EX-ORs, for example. Depending on how T is taken, P becomes a different matrix and the circuit scale also differs. For example, when T ′ = BT, from equation (11):
A = T^-1BT = (B^-1T ’)^-1T '= T'^-1BT ’
When P ′ is defined using T ′, the following equation is obtained.
[0108]
[Expression 10]

[0109]
Even if P ′ is used, the phase shift can be performed in the same manner as in the case of using P, but when P ′ is used as a circuit, three EX-ORs are required. Since the circuit scale differs depending on P as described above, it is necessary to obtain P for reducing the circuit scale. If the following design is performed, the circuit scale is small and the design is simple.
[0110]
For example, characteristic polynomial f (x) = g₄x⁴  + G₃x³+ G₂x²  + G₁x¹+ G₀x⁰Then, the following equation is established.
[0111]
## EQU11 ##

[0112]
Characteristic polynomial f (x) = g₅x⁵  + G₄x⁴+ G₃x³  + G₂x²+ G₁x¹  + G₀x⁰In this case, the following equation is established.
[0113]
[Expression 12]

[0114]
As a result, a relatively small circuit can be obtained, and P can be obtained without troublesome calculations.
[0115]
For example, characteristic polynomial f (x) = x⁷+ X³  In the case of +1, the following equation holds.
[0116]
[Formula 13]

[0117]
In this design method, the state is a = (1 0 0 0 0 0 0)^TIt is possible to obtain a matrix P that doubles the phase with 0 as the zero phase. When the operation of the matrix P is confirmed using Table 7 showing the operation of the M-sequence generator according to the matrix A 1,
As b = Pa
a = (1 0 0 0 0 0 0)^T: Phase 0 → b = (1 0 0 0 0 0 0)^T: Phase 0
a = (0 0 0 0 0 0 1)^T: Phase 1 → b = (0 0 0 0 0 1 0)^T: Phase 2
a = (0 0 0 0 0 1 0)^T: Phase 2 → b = (0 0 0 1 0 0 0)^T: Phase 4
a = (0 0 0 0 1 0 0)^T: Phase 3 → b = (0 1 0 0 0 1 0)^T: Phase 6
a = (0 0 0 1 0 0 0)^T: Phase 4 → b = (0 0 0 1 0 0 1)^T: Phase 8
a = (0 0 1 0 0 0 1)^T: Phase 5 → b = (0 1 0 0 1 1 0)^T: Phase 10
a = (0 1 0 0 0 1 0)^T: Phase 6 → b = (0 0 1 1 0 0 0)^T: Phase 12
Since the phase is doubled with respect to seven independent (order types) states a, it can be seen that this matrix P is correct.
[0118]
[Table 7]

[0119]
When the matrix P and the matrix A are represented by circuits, they are shown in FIGS. 18 and 19, respectively. The circuits that perform the operations of the matrix P and the matrix A shown in FIG. 18 and FIG. In FIG. 18, b = Pa is realized, and in FIG. 19, c = Ab is realized. When the phase shift and M-sequence generator is configured using FIGS. 18 and 19, for example, FIG. 20 is obtained.
[0120]
The configuration of FIG. 20 can obtain the initial value of the M-sequence generator in the order step of the characteristic polynomial, and generates the M-sequence by switching the mode. 20 includes a circuit 51 that implements the matrix P shown in FIG. 18, a circuit 52 that implements the matrix A shown in FIG. 19, a D flip-flop 53, a shift register 54, and selectors 55 and 56. , NAND57 is provided.
[0121]
If the circuit of FIG. 20 is modified as shown in FIG. 21, the initial value of the M-sequence generator can be obtained at a higher speed.
[0122]
Compared with the circuit shown in FIG. 14, a mask circuit is not necessary and the number of circuits is reduced. Further, in the case of FIG. 20, since the initial state of the M-sequence generator is obtained in the order step, it is possible to load the initial state to another M-sequence generator or the like with half the number of steps than the general configuration. .
[0123]
As an example, FIG. 22 shows a case where the operation of the circuit of FIG. 20 is shifted by 100 with the initial state initDATA set to 1111111b and phDATA set to 1100100b.
[0124]
In FIG. 22, i inputs the phase shift amount L from the MSB, and when this is 1, the phase is doubled +1, and when it is 0, the phase is doubled. In step 7, the phase is 128k + 100, but since phase 128k is the same as phase k, k + 100. Although the initial state is 1111111b, according to the present invention, a state shifted by 100 from the initial state can be obtained in step 7 regardless of the phase k of the initial state.
[0125]
A mask pattern is generated in step 0 to step 6 and M-sequence generation is started from step 7. Actually the characteristic polynomial f (x) = x⁷  + X³The M sequence obtained by shifting the M sequence in the +1 initial state 1111111 by 100 is 0101111, which is consistent with the example in Table 5.
[0126]
Here, high-speed shift without using mask patternGoMethod for calculating the state of the M-sequence generator after it has been generated, its design method and hardwareYeThink about the realization method. In the second embodiment described above, the mask pattern is first calculated and then the M series is generated. In the third embodiment, the mask pattern is calculated by focusing on the similarity between the mask pattern calculation and the M series generation method. A method of generating the initial state of the M-sequence generator directly without using it can be realized.
[0127]
Further, it is shown that there are many circuits that realize this, and among them, a configuration that can be easily designed with a small circuit scale can be obtained. Compared to the method described in the second embodiment, a mask circuit is not required and the circuit scale is reduced. In addition, when it is desired to obtain an arbitrarily shifted state of the M-sequence generator, the shifted state can be obtained in parallel, so that the calculation can be performed with half the number of steps as compared with the second embodiment.
[0128]
According to the above, there is no need for a ROM, and the matrices A and P are fixed and a simple circuit is sufficient. In addition, since the calculation of the matrix A and the matrix P can be realized with one clock, the calculation processing can be speeded up. Furthermore, a phase shifted arbitrarily by n clocks can be obtained.
[0129]
Embodiment 4 FIG.
As an application of the above-described third embodiment, a circuit that generates codes having different phases can be realized. FIG. 23 is a block diagram showing a configuration example of a code generation apparatus according to Embodiment 4 of the present invention. In FIG. 23, the output of the register 54 of the third embodiment is coupled to, for example, four shift registers 81, 82, 83, and 84 via a switch 85. Each shift register 81, 82, 83, 84 outputs a code having a different phase.
[0130]
In this way, since the initial value can be calculated at high speed, the initial states of a plurality of code generators can be created with one initial value calculation. This makes it possible to obtain a large number of codes having different phases without using a mask.
[0131]
As mentioned above, although this invention was demonstrated by Embodiment 1-4, a various deformation | transformation is possible within the range of the main point of this invention, and these are not excluded from the scope of this invention.
[0132]
【The invention's effect】
As described above, according to the present invention, a new mask vector is obtained by the product of the first mask transformation matrix fixed by the generator polynomial and the mask vector before the transformation, and the MSB of the shift amount data is not zero. A mask based on the mask vector is obtained after obtaining a new mask vector by the product of the second mask transformation matrix fixed by the generator polynomial and the mask vector, shifting the shift amount data to the MSB side, and repeating the above steps a specified number of times. Since the pattern is output, the mask pattern can be generated at a high speed, thereby producing a code generation method capable of realizing a small circuit at a high speed.
[0133]
According to the next invention, a new mask vector is obtained by the product of the first mask transformation matrix fixed by the generator polynomial by the arithmetic means and the mask vector before the transformation, and generated when the MSB of the shift amount data is not zero. A new mask vector is obtained by the product of the second mask transformation matrix fixed by the polynomial and the mask vector, the shift amount data is shifted to the MSB side by the shift means, and the arithmetic means and the shift means are operated a specified number of times by the output means. Since the mask pattern based on the mask vector is output after the generation, the mask pattern can be generated at a high speed, thereby obtaining a code generator capable of realizing a small circuit at a high speed. There is an effect.
[0134]
According to the next invention, since the mask pattern is generated and the initial state is masked to perform the shift, a code is generated according to the mask pattern, and a dedicated code generator is not required. There is an effect that a code generator capable of reducing the circuit scale can be obtained.
[0135]
According to the next invention, the product of the first mask transformation matrix fixed by the generator polynomial by the first computing means and the state vector representing the state of the code generator is obtained, and either the phase shift or the code generation is obtained by the first selector. Either one of the output of the first calculation means and the state vector is selected according to the mode for instructing one of the second mask transformation matrix and the first selector output fixed by the generator polynomial by the second calculation means. The product is obtained, the second selector selects either the first selector or the output of the second arithmetic means according to the mode instructing one of phase shift and code generation and the MSB of the shift data, and a new Since the state vector is used, an initial state as a code generator is directly generated and a code is generated without using a mask pattern with a simple configuration. An effect that bets are capable of code generation apparatus is obtained.
[0136]
According to the next invention, since the state vector is connected to the plurality of shift registers that shift the codes having different phases through the selector, it is possible to generate the code with one circuit configuration without using a mask. There is an effect that a code generator capable of obtaining a large number of codes having different phases can be obtained.
[0137]
According to the next invention, since the phase shift process is performed using only the first mask transformation matrix and the second mask transformation matrix, it is possible to directly obtain the circuit state without calculating the mask pattern. There is an effect that a code generator can be obtained.
[0138]
According to the present invention, since the first mask transformation matrix having the specific structure is used, there is an effect that it is possible to obtain a code generation device capable of greatly reducing the circuit scale.
[0139]
According to the next invention, since the phase shift processing is performed using only the first mask transformation matrix and the second mask transformation matrix, it is possible to directly obtain the circuit state without calculating the mask pattern. There is an effect that a code generation method can be obtained.
[0140]
According to the present invention, since the first mask transformation matrix having a specific structure is used, there is an effect that a code generation method capable of reducing the circuit scale can be obtained.
[Brief description of the drawings]
FIG. 1 is a block diagram showing an example of a general M-sequence generator.
FIG. 2 is a diagram illustrating the nature of an M sequence.
FIG. 3 is a diagram for explaining the nature of an M sequence.
FIG. 4 is a diagram for explaining the nature of an M sequence.
FIG. 5 is a diagram illustrating the nature of an M sequence.
FIG. 6 is a block diagram showing another example of a general M-sequence generator.
FIG. 7 is a circuit diagram showing a configuration example of a mask pattern generation circuit according to the first embodiment of the present invention.
FIG. 8 is a block diagram showing a configuration example of an M-sequence generator according to Embodiment 1 of the present invention.
FIG. 9 is a block diagram showing a modification of the first embodiment.
FIG. 10 is a flowchart illustrating the operation of the first embodiment.
FIG. 11 is a diagram illustrating a phase shift procedure according to the first embodiment.
FIG. 12 is a circuit diagram showing another example of a mask pattern generation circuit according to the second embodiment of the present invention.
FIG. 13 is a block diagram showing a configuration example of an M-sequence generator according to the second embodiment of the present invention.
FIG. 14 is a circuit diagram showing a configuration example of a mask circuit according to the second embodiment.
FIG. 15 is a diagram illustrating the principle of an M-sequence generator according to Embodiment 3 of the present invention.
FIG. 16 is a diagram illustrating the principle of the M-sequence generator according to the third embodiment of the present invention from another viewpoint.
FIG. 17 is a circuit diagram showing a configuration example for realizing one matrix according to the third embodiment.
FIG. 18 is a circuit diagram showing another configuration example for realizing another matrix according to the third embodiment.
FIG. 19 is a block diagram showing a configuration example of an M-sequence generator according to the third embodiment.
FIG. 20 shows a modification of the M-sequence generator according to the third embodiment.
FIG. 21 is a diagram illustrating a phase shift procedure according to the third embodiment.
FIG. 22 is a block diagram showing a configuration example of an M-sequence generator according to Embodiment 4 of the present invention.
FIG. 23 is a block diagram illustrating an example of a code generation device according to a conventional example.
FIG. 24 is a flowchart illustrating a mask conversion operation according to a conventional example.
FIG. 25 is a diagram illustrating a phase shift procedure according to a conventional example.
FIG. 26 is a block diagram showing another example of a conventional code generator.
[Explanation of symbols]
21 arithmetic units, 21A to 21G mask pattern generation circuit, 22, 23 shift register, 31 mask pattern generation circuit, 32 mask circuit, 33 initial state buffer, 34 shift register, 35 flip-flop, 41, 45 EX-OR, 42, 46 shift register, 51, 51A, 51B, 51C circuit, 52, 52A, 52B, 52C circuit, 53D flip-flop, 54 shift register, 55, 56, 61A, 61B, 61C selector, 57 NAND, 85 switch, 81- 84 Shift register.

Claims (9)

A first step of obtaining a new mask vector by a product of a first mask transformation matrix fixed by a generator polynomial and a mask vector before transformation;
A second step of obtaining a new mask vector by a product of the second mask transformation matrix fixed by the generator polynomial and the mask vector obtained in the first step when the MSB of the shift amount data is not zero;
A third step of shifting the shift amount data to the MSB side;
A fourth step of outputting a mask pattern based on a mask vector after repeating the first step, the second step, and the third step a specified number of times;
A code generation method comprising: A new mask vector is obtained by the product of the first mask transformation matrix fixed by the generator polynomial and the mask vector before conversion, and the second mask transformation matrix fixed by the generator polynomial when the MSB of the shift amount data is not zero. Computing means for obtaining a new mask vector by a product of the mask vector and the mask vector;
Shift means for shifting the shift amount data to the MSB side;
An output means for outputting a mask pattern based on a mask vector after operating the arithmetic means and the shift means a specified number of times;
A code generation apparatus comprising: Using the arithmetic means, the shift means, and the output means, a mask pattern for shifting data representing an arbitrary initial state by a set phase shift amount is generated. Mask pattern generating means for generating a mask pattern for shifting by phase ;
Wherein the mask pattern to be shifted mask pattern phase shift said set generated by the generating means, to obtain the sign of 1Bit masks the data representing the arbitrary initial state, after the mask is shifted by the first phase Mask means for sequentially obtaining 1-bit codes using a pattern ;
The code generator according to claim 2, further comprising: First computing means for obtaining a product of a first mask transformation matrix fixed by a generator polynomial and a state vector representing the state of the code generator;
A first selector that selects one of the output of the first calculation means and the state vector in accordance with a mode for instructing one of phase shift and code generation;
Second computing means for obtaining a product of the second mask transformation matrix fixed by the generator polynomial and the first selector output;
A second state vector is selected as a new state vector by selecting either the first selector or the output of the second computing means in accordance with the mode for instructing one of phase shift and code generation and the MSB of the shift data. A selector,
A code generation apparatus comprising: The code generator according to claim 4, wherein the state vector is connected to a plurality of shift registers that shift codes having different phases through a selector. 6. The code generation device according to claim 4, wherein the first mask transformation matrix is specified based on a mask pattern capable of performing a phase shift twice as large as a phase shift process by the second mask transformation matrix. . Further, the first mask transformation matrix is
Generator polynomial f (x) = g _n x ⁿ + g _n-1 x ^n-1 + g _n-2 x ^n-2 +... + G ₀ x ⁰ and n is an even number,

age,
Generator polynomial f (x) = g _n x ⁿ + g _n-1 x ^n-1 + g _n-2 x ^n-2 + ... + g ₀ x ⁰ and n is an odd number,

The code generator according to claim 6 . A first calculation step for obtaining a product of a first mask transformation matrix fixed by a generator polynomial and a state vector representing a state of the code generator;
  A first selection step of selecting one of the calculation result of the first calculation step and the state vector according to a mode for instructing one of phase shift and code generation;
  A second calculation step for obtaining a product of the second mask transformation matrix fixed by the generator polynomial and the selection result by the first selection step;
  According to the mode for instructing either one of phase shift and code generation and the MSB of the shift data, one of the selection result by the first selection step and the calculation result by the second calculation step is selected, A second selection step in which the selection result is a new state vector;
  Including
  Furthermore, the first mask transformation matrix is a matrix identified based on a mask pattern capable of a phase shift twice as large as the phase shift processing by the second mask transformation matrix,
  An arbitrary phase shift process is performed by a combination of the first mask transformation matrix and the second mask transformation matrix. Further, as the first mask transformation matrix,
  Generator polynomial f (x) = g _n x ⁿ + G _n-1 x ^n-1 + G _n-2 x ^n-2 + ... + g ₀ x ⁰ And n is an even number,

  Use
  Generator polynomial f (x) = g _n x ⁿ + G _n-1 x ^n-1 + G _n-2 x ^n-2 + ... + g ₀ x ⁰ And n is an odd number,

  The code generation method according to claim 8, wherein:

Images