JP3556461B2 - Ｍ系列の位相シフト係数算出方式 - Google Patents
Ｍ系列の位相シフト係数算出方式 Download PDFInfo
- Publication number
- JP3556461B2 JP3556461B2 JP6822698A JP6822698A JP3556461B2 JP 3556461 B2 JP3556461 B2 JP 3556461B2 JP 6822698 A JP6822698 A JP 6822698A JP 6822698 A JP6822698 A JP 6822698A JP 3556461 B2 JP3556461 B2 JP 3556461B2
- Authority
- JP
- Japan
- Prior art keywords
- output
- value
- circuit
- bit
- input
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04J—MULTIPLEX COMMUNICATION
- H04J13/00—Code division multiplex systems
- H04J13/0074—Code shifting or hopping
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/58—Random or pseudo-random number generators
- G06F7/582—Pseudo-random number generators
- G06F7/584—Pseudo-random number generators using finite field arithmetic, e.g. using a linear feedback shift register
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04B—TRANSMISSION
- H04B1/00—Details of transmission systems, not covered by a single one of groups H04B3/00 - H04B13/00; Details of transmission systems not characterised by the medium used for transmission
- H04B1/69—Spread spectrum techniques
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04J—MULTIPLEX COMMUNICATION
- H04J13/00—Code division multiplex systems
- H04J13/0007—Code type
- H04J13/0022—PN, e.g. Kronecker
- H04J13/0025—M-sequences
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/06—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols the encryption apparatus using shift registers or memories for block-wise or stream coding, e.g. DES systems or RC4; Hash functions; Pseudorandom sequence generators
- H04L9/065—Encryption by serially and continuously modifying data stream elements, e.g. stream cipher systems, RC4, SEAL or A5/3
- H04L9/0656—Pseudorandom key sequence combined element-for-element with data sequence, e.g. one-time-pad [OTP] or Vernam's cipher
- H04L9/0662—Pseudorandom key sequence combined element-for-element with data sequence, e.g. one-time-pad [OTP] or Vernam's cipher with particular pseudorandom sequence generator
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
- G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
- G06F7/724—Finite field arithmetic
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- General Physics & Mathematics (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computer Security & Cryptography (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- Computational Mathematics (AREA)
- Error Detection And Correction (AREA)
- Complex Calculations (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は、拡散変調方式による通信システム等に適用される、擬似雑音系列を指定された任意の位相で発生するための技術に関する。
【０００２】
【従来の技術】
スペクトル拡散変調を用いた通信方式においては、符号分割多元接続（Ｃｏｄｅ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅ Ａｃｃｅｓｓ：ＣＤＭＡ）によって、多数の信号のスペクトルを広帯域に拡散させ多重化して伝送することが可能である。図９は、ＣＤＭＡ通信システムの一原理構成を示す図である。
【０００３】
ＣＤＭＡ送信機９０１側では、送信信号源９０３から出力される例えば周波数変調又は位相変調された送信信号は、拡散変調部９０５によって、拡散符号生成部９０４が生成する拡散符号を使ってスペクトル拡散変調され、その結果得られる送信信号が伝送路９０６に送出される。
【０００４】
ＣＤＭＡ受信機９０２においては、逆拡散復調部９０８が、送信側の拡散符号と同じ系列及び位相を有し送信側のタイミングに同期して逆拡散符号生成部９０７から出力される逆拡散符号を使って、受信信号に対し、逆拡散（復調）処理を行う必要がある。
【０００５】
従って、逆拡散符号生成部９０７には、タイミング同期信号（通常は、ＣＤＭＡ受信機９０２内部において受信信号から自律的に生成される）に従って、任意の位相を有する系列符号を生成する機能が必要とされる。
【０００６】
ＣＤＭＡ通信においては、スペクトルを拡散するための拡散符号（及び逆拡散符号）は、広帯域信号であることに加え、（１）多くのユーザへの符号の割当てを可能とするために符号の種類が多いこと、（２）異なるユーザの符号との識別を可能とするために相互相関が小さいこと、（３）自局宛の信号に対する同期が確実にとれるようにするために鋭い自己相関特定を有すること、及び（４）通信信号の秘話性を高めるためにできるだけランダムで周期が長く解読が困難であること、等の条件が要求される。
【０００７】
このような条件を満足する符号として、従来、擬似雑音（ＰＮ：ＰｓｅｕｄｏｒａｎｄｏｍＮｏｉｓｅ）系列が知られている。
ＰＮ系列は、シフトレジスタを用いて発生させることができるため、その発生過程は、確定的（ｄｅｔｅｒｍｉｎｉｓｔｉｃ ）であり真にランダムではない。しかし、ＰＮ系列は、以下のランダム性の性質（ｒａｎｄｏｍｎｅｓｓ ｐｒｏｐｅｒｔｙ ）を満足する符号であるため、上記条件を必要とするＣＤＭＡ通信の拡散符号として適している。
性質１：平衡性（ｂａｌａｎｃｅ ｐｒｏｐｅｒｔｙ）
系列の１周期内で、“１”の出現回数と“０”の出現回数は、高々１しか違わない。
性質２：連なり性（ｒｕｎ ｐｒｏｐｅｒｔｙ）
１周期に含まれる「１の連なり」と「０の連なり」のうち、それぞれの連なりの長さは、連なりの分類数の１／２が“１”、１／４が“２”、１／８が“３”、・・・である。すなわち、連なり数ｋの連なりは｛（連なりの分類数）×（１ ／２ｋ ）｝個存在する。なお、この個数が１より小さくなる連なりは、無意味な連なりとなる。
性質３：相関性（ｃｏｒｒｅｌａｔｉｏｎ ｐｒｏｐｅｒｔｙ）
系列を巡回させ、あらゆる状態で２つの系列間でそれらの各桁ごとに各系列の符号値の比較を行った場合、符号値が一致する桁の数と一致しない桁の数は、高々１しか違わない。
このような性質を満足するＰＮ系列の代表例として、Ｍ系列（ｍａｘｉｍｕｍ ｌｅｎｇｔｈｓｅｑｕｅｎｃｅ：最大周期系列）が知られている。Ｍ系列は、図１０に示される、ｎ段のシフトレジスタを含む回路を用いて、発生される。
【０００８】
図１０で、ｎ段のシフトレジスタの各段の出力に係数ｆｉ （＝０又は１）が乗算され、その乗算結果が、排他的論理和回路（図中の丸で囲まれた“＋”記号）を介してシフトレジスタの入力側にフィードバックされる。
【０００９】
初期状態が、シフトレジスタの各段が全て０である状態ではない場合に、係数ｆｉ が特定の条件を満たすときに、シフトレジスタから出力される系列ａｉ の周期が、ｎ段のシフトレジスタによって発生できる最大周期（２ｎ −１）となる。このような系列が、Ｍ系列と呼ばれる。
【００１０】
いま、図１０の回路は、次式によって表現できる。
【００１１】
【数１】
【００１２】
この式において、ｆｎ ＝１とおけば、次式が得られる。
【００１３】
【数２】
【００１４】
上記数１式又は数２式は、線形再帰式（ｌｉｎｅａｒ ｒｅｃｕｒｒｉｎｇ ｅｑｕａｔｉｏｎ ）とよばれる。ここで、ａｉ＋ｊ ＝ｘｊ ａｉ となるような遅延演算子ｘを導入すると、数２式は、次式で表現される。
【００１５】
【数３】
【００１６】
上記数３式の左辺の括弧内の項によって表現される、次式の多項式ｆ（ｘ） は、特性多項式（ｃｈａｒａｃｔｅｒｉｓｔｉｃ ｐｏｌｙｎｏｍｉａｌ ）と呼ばれる。
【００１７】
【数４】
【００１８】
この数４式に示される係数ｆｊ がガロア体ＧＦ（２ｎ ）に属し、ｆ（ｘ） が、ガロア体ＧＦ（２ｎ ）の原始元αが有する最小多項式である場合に、ｎ段のシフトレジスタを含む図１０に示される回路は、最大周期（２ｎ −１）を有するＭ系列を発生できることが知られている。この最小多項式は、ｋ次原始多項式（ｐｒｉｍｉｔｉｖｅ ｐｏｌｙｎｏｍｉｎａｌ ｏｆ ｄｅｇｒｅｅ ｋ ）と呼ばれている。詳細は、例えば文献：「センシング／認識シリーズ 第８巻、Ｍ系列とその応用／１６頁〜」（柏木 濶著／昭晃堂）に示されている。
【００１９】
原始多項式は、上記文献の１７１頁〜１９１頁に示されるようにして算出することができ、また、そこで引用されているいくつかの文献によって、多くの種類の原始多項式が既に求められている。
【００２０】
例えば、ガロア体ＧＦ（２４ ）の原始多項式ｆ（ｘ） ＝ｘ４ ＋ｘ＋１に対応する数４式に示される係数ｆｊ は、ｆ０ ＝１，ｆ１ ＝１，ｆ２ ＝ｆ３ ＝０，ｆ４ ＝１となる。この結果、図１０に基づいて、図１１に示されるＭ系列発生回路を構成することができる。
【００２１】
ここで、図１１に示されるＭ系列発生回路で、Ｍ系列の出力ａｉ に対して位相がｄビットだけシフトしたＭ系列ｘｄ ａｉ を得ることを考える。Ｍ系列は、ｎ段（図１１の場合は４段）のシフトレジスタの所定の初期状態が与えられれば、それから後の全ての状態が定まるから、任意の位相を有するＭ系列は、次式に示されるように、シフトレジスタの各段の出力の線形結合によって得られることがわかる。
【００２２】
【数５】
【００２３】
これより、４段のシフトレジスタを含む図１１に示されるＭ系列発生回路から、任意の位相を有するＭ系列を発生する回路は、図１２に示されるように構成することができる。
【００２４】
図１２で、ＰＮ発生器（ＰＮＧ）１２０１内の４段のシフトレジスタ（ＳＲ）１２０３の各段には、それぞれ初期値が与えられる。タップ（ＴＡＰ）１２０４により、図１１に相当するフィードバックが与えられる。可変タップ（ＡＴＡＰ）１２０２内の４つのアンド回路（ＡＮＤ）１２０６には、数５式の各係数ｂ０ 〜ｂ３ に対応するタップ情報（ＴＡＰＩＮＦＯ）１２０５が与えられる。この結果、ＳＲ１２０３の各段の出力のうち、上記ＴＡＰＩＮＦＯ１２０５によって選択された出力が、それに対応するアンド回路（ＡＮＤ）１２０６及び排他的論理和回路（ＥＸＯＲ）１２０７によって他の出力と加算され、それらの加算結果として、任意の位相ｄを有するＭ系列ｘｄ ａｉ が出力される。
【００２５】
なお、ＳＲ１２０３の初期値を与える手段、及びシフト動作を実現するためのクロックを供給する手段等については、省略し図示していない。
次に、ＴＡＰＩＮＦＯ１２０５を構成する数５式の係数ｂ０ 〜ｂ３ の算出原理について説明する。
【００２６】
まず、図１２に示されるＰＮＧ１２０１において、Ｍ系列の出力ａｉ に対してそれぞれ１〜３ビットだけ位相がシフトした各Ｍ系列ｘ１ ａｉ 〜ｘ３ ａｉ は、図１３に示されるように、第２段め〜第４段めの各シフトレジスタ段ＳＲ１〜ＳＲ４の各出力にほかならない。すなわち、
【００２７】
【数６】
【００２８】
である。
次に、Ｍ系列の出力ａｉ に対して４ビット位相がシフトしたＭ系列ｘ４ ａｉ を考える。この場合、原始多項式ｆ（ｘ） ＝ｘ４ ＋ｘ＋１において、
【００２９】
【数７】
【００３０】
とおくと、ガロア体上の演算により、下記各式が成り立つ。
【００３１】
【数８】
【００３２】
【数９】
【００３３】
上記数９式より、Ｍ系列の出力ａｉ に対して位相が４ビットシフトしたＭ系列ｘ４ ａｉ は、ａｉ 自身と、ａｉ に対して位相が１ビットシフトした出力ｘ１ ａｉ との排他的論理和によって表現できることがわかる。すなわち、図１４に示されるように、ａｉ に対して位相が４ビットシフトしたＭ系列ｘ４ ａｉ は、第１段めのシフトレジスタ段ＳＲ０の出力と、第２段めのシフトレジスタ段ＳＲ１の出力の排他的論理和によって得られる。すなわち、
【００３４】
【数１０】
【００３５】
である。
続いて、Ｍ系列の出力ａｉ に対して位相が５ビットシフトしたＭ系列ｘ５ ａｉ は、数９式の両辺にｘを乗算することによって得られる下記数１１式より、図１４に示されるように、第２段めのシフトレジスタ段ＳＲ１の出力と、第３段めのシフトレジスタ段ＳＲ２の出力の排他的論理和によって得られる。
【００３６】
【数１１】
【００３７】
すなわち、
【００３８】
【数１２】
【００３９】
である。
更に、Ｍ系列の出力ａｉ に対し位相が６ビットシフトしたＭ系列ｘ６ ａｉ は、数１１式の両辺に更にｘを乗算することによって得られる下記数１３式より、第３段めのシフトレジスタ段ＳＲ２の出力と、第４段めのシフトレジスタ段ＳＲ３の出力の排他的論理和によって得られる。
【００４０】
【数１３】
【００４１】
すなわち、
【００４２】
【数１４】
【００４３】
である。
以上に示される規則でＴＡＰＩＮＦＯ１２０５を構成する係数ｂ０ 〜ｂ３ を順次出力する回路として、従来、図１５に示されるものが知られている。
【００４４】
この回路では、原始多項式ｆ（ｘ） ＝ｘ４ ＋ｘ＋１に対応して４段のシフトレジスタ（ＳＲ）１５０１が用いられ、数７式の右辺を構成する各項１＝ｘ０ ，ｘ＝ｘ１ に対応するシフトレジスタ段ａ０ ，ａ１ の入力側に排他的論理和回路ＥＸＯＲ１５０２が挿入され、そこにシフトレジスタの出力段ａ４ の出力（数７式の左辺項ｘ４ に対応する）がフィードバックされる。なお、シフトレジスタ段ａ０ の前段は存在しないため、その入力側には出力段ａ４ の出力が直接フィードバックされる。
【００４５】
より一般的には、原始多項式ｆ（ｘ） の次数に対応する段数のシフトレジスタが用いられ、ｆ（ｘ） ＝０とすることによって、数７式と同様にして、最高次数の項が左辺、それ以外の次数の項が右辺となる等式が構成される。そして、その等式の右辺を構成する各項に対応するシフトレジスタ段の入力側に排他的論理和回路が挿入され、そこにシフトレジスタの出力段の出力（その等式の左辺項に対応する）がフィードバックされる。
【００４６】
続いて、図１５において、ＳＲ１５０１の初期値として、第１段めのシフトレジスタ段ａ０ に１がセットされ、それ以外のシフトレジスタ段ａ１ 〜ａ３ には０がセットされる。
【００４７】
そして、所望の位相シフト量に対応する回数だけシフト動作が実行されることにより、ＳＲ１５０１の各段ａ０ 〜ａ３ の各出力として、図１２に示されるＴＡＰＩＮＦＯ１２０５を構成する各係数ｂ０ 〜ｂ３ が決定される。
【００４８】
【発明が解決しようとする課題】
しかし、図１５に示される従来技術では、所望の位相シフト量に対応するＴＡＰＩＮＦＯ１２０５を算出するためには、そのシフト量に対応する回数だけシフト動作を実行する必要がある。従って、Ｍ系列の周期が長くなった場合（例えば１０分程度となった場合）には、ＴＡＰＩＮＦＯ１２０５の算出に膨大な時間がかかってしまうという問題点を有していた。
【００４９】
本発明の課題は、各位相シフト量に対応する各タップ情報の算出を高速に実行することにある。
【００５０】
【課題を解決するための手段】
本発明は、ｎ次の原始多項式ｆ（ｘ） により生成されるＭ系列の出力ａｉ に対し位相がｄビットだけシフトしたＭ系列ｘｄ ａｉ を、前記出力ａｉ に対しそれぞれ位相が０〜ｎ−１ビットだけシフトした各Ｍ系列ｘ０ ａｉ 〜ｘｎ−１ ａｉ の線形結合、
ｂ０ ｘ０ ａｉ ＋ｂ１ ｘ１ ａｉ ＋ｂ２ ｘ２ ａｉ ＋・・・＋ｂｎ−１ ｘｎ−１ ａｉ
によって得るための各位相シフト係数ｂ０ 〜ｂｎ−１ を算出するための技術を前提とする。
【００５１】
本発明の第１の過程では、まず、位相シフト量ｄの２進値が入力される。
第２の過程では、１０進値の１に対応するｎビットのベクトル値が初期入力ベクトル値として設定される。
【００５２】
第３の過程では、対象ビットが、第１の過程において入力された位相シフト量ｄの２進値の最上位ビットとして設定される。
第４の過程では、対象ビットが“１”である場合に、入力ベクトル値に、ガロア体ＧＦ（２ｎ ）内で、原始元αのベクトル値が乗算され、その乗算結果が出力ベクトル値とされ、対象ビットが“０”である場合に、入力ベクトル値がそのまま出力ベクトル値とされる。
【００５３】
第５の過程では、第４の過程において得られる出力ベクトル値に対してガロア体ＧＦ（２ｎ ）内で自乗演算が実行される。
第６の過程では、第１の過程において入力された位相シフト量ｄの２進値において、対象ビットの位置が１ビット最下位ビット側にシフトされ、第５の過程における自乗演算結果を新たな入力ベクトル値として、第４及び第５の過程が実行させられる。
【００５４】
第７の過程では、第１の過程において入力された位相シフト量ｄの２進値を構成する全てのビットについて第４及び第５の過程の実行が終了した時点で、それまでに得られた演算結果の各要素が位相シフト係数ｂ０ 〜ｂｎ−１ として出力される。
【００５５】
【発明の実施の形態】
以下、図面を参照しながら、本発明の実施の形態について詳細に説明する。
＜本発明の実施の形態の原理＞
まず、本発明の実施の形態の原理について説明する。
【００５６】
本発明の実施の形態は、一例として、４段のシフトレジスタ（ＳＲ）１２０３を含み任意の位相を有するＭ系列を発生することのできる図１２に示される回路を前提とする。
【００５７】
今、ガロア体ＧＦ（２ｎ ）の原始元をαとする。この場合、図１２に示されるＴＡＰＩＮＦＯ１２０５である前述の数５式の係数ｂ０ 〜ｂｎ−１ は、αをｎビットのベクトルで表現したときに、そのベクトルについて、ガロア体ＧＦ（２ｎ ）内でαｄ を演算して得られるベクトルの各ビットの値に等価である。
【００５８】
図１は、原始多項式ｆ（ｘ） ＝ｘ４ ＋ｘ＋１に対応するガロア体ＧＦ（２４ ）の原始元αのベクトル表現と、そのベキ乗（ｅｘｐｏｎｅｎｔｉａｔｉｏｎ）のベクトル表現を示す図である。この場合に、αのベクトル表現は（０（ＭＳＢ） ，０，１，０（ＬＳＢ） ）（１０進表現で２）である。そして、例えばα１ 〜α６ のベクトル表現の各ビット値は、前述した従来技術における数６式、数１０式、数１２式、及び数１４式によって示される各係数値ｂ０ 〜ｂ３ とよく一致することがわかる。
【００５９】
ここで、αｄ は、下記数１５式に示されるように分解することができる。
【００６０】
【数１５】
【００６１】
そして、数１５式の分解演算によって得られる項αｓ においてｓをｄに置き換えて更に数１５式の分解演算を行う、という操作を繰り返すことにより、例えばα６ は、次式のように分解することができる。
【００６２】
【数１６】
【００６３】
これよりαｄ のベクトル表現値は、数１６式の右辺のように分解された括弧の入れ子構造の最も内側から順に、「現在ベクトル値にαのベクトル表現値を乗算しそのベクトル乗算結果を自乗する演算」又は「現在ベクトル値をそのまま自乗する演算」を、ガロア体ＧＦ（２ｎ ）内で、概略｛ｌｏｇ（ｄ）／ｌｏｇ（２）｝回繰り返し実行するだけで算出することができる。
【００６４】
そして、ガロア体ＧＦ（２ｎ ）内での、「現在ベクトル値にαのベクトル表現値を乗算しそのベクトル乗算結果を自乗する演算」又は「現在ベクトル値をそのまま自乗する演算」をハードウエアで実現することができれば、αｄ のベクトル表現値、すなわち前述した数５式の係数ｂ０ 〜ｂｎ−１ は、シフトレジスタの段数ｎが大きければ大きいほど、従来必要であったシフト動作回数ｄ回よりも大幅に少ない繰り返し回数で算出することが可能となる。
【００６５】
図２は、任意の位相シフト量ｄが与えられたときに、図１２のＴＡＰＩＮＦＯ１２０５である前述した数５式の係数ｂ０ 〜ｂｎ−１ を算出するための上記繰返し演算を特定するアルゴリズムの原理図である。
ステップ１：
まず、位相シフト量ｄの２進表現値が入力される。例えば、位相シフト量ｄ＝６としたとき、それに対する４ビットの２進表現値は、図２（ａ） に示されるように、（０（ＭＳＢ） ，１，１，０（ＬＳＢ） ）となる。
ステップ２：
ｎビットのベクトル値（０（ＭＳＢ） ，０，０，１（ＬＳＢ） ）（１０進値の１）を、初期入力ベクトル値とする。
ステップ３：
対象ビットが、ステップ１で入力された位相シフト量ｄの２進表現値のＭＳＢ（最上位ビット）とされる。
ステップ４：
対象ビットが“１”なら、入力ベクトル値に、ガロア体ＧＦ（２ｎ ）内で、原始元αのベクトル値が乗算され、その乗算結果がステップ４の出力ベクトル値とされる（操作Ｉ）。例えば、原始多項式ｆ（ｘ） ＝ｘ４ ＋ｘ＋１に対応するガロア体ＧＦ（２４ ）の原始元αのベクトル値は、図１に示されるように（０（ＭＳＢ） ，０，１，０（ＬＳＢ） ）、すなわち１０進値で２である。従って、この場合には、入力ベクトル値に対して、１ビット左シフト演算が実行される。
【００６６】
対象ビットが“０”なら、入力ベクトル値がそのままステップ２の出力ベクトル値とされる。
ステップ５：
ステップ４の出力ベクトル値がガロア体ＧＦ（２ｎ ）内で自乗され、その演算結果がステップ５の出力ベクトル値とされる（操作ＩＩ）。具体的には、ステップ４の出力ベクトル値のｉ番目の要素ａｉ （０≦ｉ≦ｎ−１）がセットされている場合には、ａｉ がクリアされ要素ａ２ｉに、ｍｏｄ ２で１が加算され、その加算結果がステップ５の出力ベクトル値とされる。但し、２ｉがｎ以上の場合には、ガロア体ＧＦ（２ｎ ）内の原始多項式ｆ（ｘ） によって定まるα２ｉと等価な１本以上の要素ａｊ に対して、ｍｏｄ ２で１が加算され、その加算結果がステップ５の出力ベクトル値とされる。
ステップ６：
ステップ１で入力された位相シフト量ｄの２進表現値において、対象ビットの位置が１ビットＬＳＢ側にシフトされ、ステップ５の出力ベクトル値が新たな入力ベクトル値とされて、上記ステップ４とステップ５が再度実行される。
【００６７】
ＬＳＢに対するステップ４とステップ５の処理が終了したら、そのステップ５で得られた出力ベクトル値の各要素が、図１２のＴＡＰＩＮＦＯ１２０５とされる。
以上のステップ１〜ステップ６のアルゴリズムをハードウエアで実現することにより、任意の位相シフト量ｄに対する図１２のＴＡＰＩＮＦＯ１２０５を高速に演算することが可能となる。
【００６８】
図２（ｂ） は、位相シフト量ｄ＝６に対応する図２（ａ） に示される４ビットの位相シフト量（０（ＭＳＢ） ，１，１，０（ＬＳＢ） ）に対して、上記ステップ１〜ステップ６が実行される手順を示した図である。
【００６９】
また、図２（ｃ） は、図２（ｂ） の各演算手順に対する数学的な演算結果を示した図である。図２（ｃ） の最終的な演算結果α６ ＝α３ ＋α２ は、数１３式に示される従来の演算結果と良く一致している。
＜本発明の実施の形態の全体構成＞
図３は、４段のシフトレジスタ（ＳＲ）１２０３を含み任意の位相を有するＭ系列を発生することのできる図１２に示される回路を前提とし、図１２のＴＡＰＩＮＦＯ１２０５を生成する、本発明の実施の形態の回路の構成図である。
【００７０】
また、図４は、図３の回路の動作タイミングチャートである。
今、原始多項式をｆ（ｘ） ＝ｘ４ ＋ｘ＋１とすれば、位相シフト量（ＳＦＴＶＡＬ）３０１、ラッチ出力（ＬＡＴＯＵＴ）３０６、自乗演算部出力（ＭＵＬＯＵＴ）３０８、及び２倍演算部出力（ＤＢＬＯＵＴ）３１０等の信号は、４ビット幅のベクトル信号となる。
【００７１】
まず、ＳＦＴＶＡＬ３０１がシフト量レジスタ（ＳＲＥＧ）３０２に予め設定されている。この動作は、前述した＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ１に対応する。図４の例では、例えば、位相シフト量ｄ＝６であって、ＳＲＥＧ３０２には、その４ビットの２進表現値（０（ＭＳＢ） ，１，１，０（ＬＳＢ） ）が設定される。
【００７２】
またラッチ部（ＬＡＴ）３０５には、４ビットのベクトル値（０（ＭＳＢ） ，０，０，１（ＬＳＢ） ）が、予め初期入力ベクトル値（ＬＡＴＩＮＩ）３０４として設定されている。この動作は、前述した＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ２に対応する。この結果、ＬＡＴＯＵＴ３０６は、初期ベクトル値（０（ＭＳＢ） ，０，０，１（ＬＳＢ） ）（１０進表現の１）を示し、従って、自乗演算部（ＭＵＬ）３０７から出力されるＭＵＬＯＵＴ３０８も同じベクトル値となる。
【００７３】
次に図４に示されるタイミングＴ０で、ＳＲＥＧ３０２からスイッチ（ＳＷ）３０３に、ＳＦＴＶＡＬ３０１の２進表現値（０（ＭＳＢ） ，１，１，０（ＬＳＢ） ）の第４ビット値（ＭＳＢ値）“０”が、選択制御信号（ＳＥＬ）３１１として出力される。この動作は、前述した＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ３に対応する。
【００７４】
ＳＷ３０３は、ＳＥＬ３１１の値が“０”である場合には、ＭＵＬＯＵＴ３０８を選択する。そして、図４に示されるように、タイミングＴ１において、ＳＷ３０３が選択しているＭＵＬＯＵＴ３０８のベクトル値（０（ＭＳＢ） ，０，０，１（ＬＳＢ） ）が、ＬＡＴ３０５にラッチされる。この動作は、前述した＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ４における対象ビットが“０”である場合の処理に対応する。
【００７５】
この結果、ＬＡＴＯＵＴ３０６は、ベクトル値（０（ＭＳＢ） ，０，０，１（ＬＳＢ） ）（１０進表現の１）を示し、従って、ＭＵＬ３０７から出力されるＭＵＬＯＵＴ３０８も同じベクトル値となる。この動作は、前述した＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ５に対応する。
【００７６】
次に、図４に示されるように、タイミングＴ２で、ＳＲＥＧ３０２の内容がシフトされ、ＳＲＥＧ３０２からＳＷ３０３に、ＳＦＴＶＡＬ３０１の２進表現値（０（ＭＳＢ） ，１，１，０（ＬＳＢ） ）の第３ビット値“１”が、ＳＥＬ３１１として出力される。この動作は、前述した＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ６に対応する。
【００７７】
ＳＷ３０３は、ＳＥＬ３１１の値が“１”である場合には、ＤＢＬＯＵＴ３１０を選択する。ここで、２倍演算部（ＤＢＬ）３０９は、ＭＵＬＯＵＴ３０８のベクトル値（０（ＭＳＢ） ，０，０，１（ＬＳＢ） ）に対して１ビット左シフト演算を実行することによって、ＤＢＬＯＵＴ３１０として、ベクトル値（０（ＭＳＢ） ，０，１，０（ＬＳＢ） ）を出力する。そして、図４に示されるように、タイミングＴ３において、ＳＷ３０３が選択しているＤＢＬＯＵＴ３１０の上記ベクトル値が、ＬＡＴ３０５にラッチされる。この動作は、前述の＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ４における対象ビットが“１”である場合の処理に対応する。
【００７８】
この結果、ＬＡＴＯＵＴ３０６は、ベクトル値（０（ＭＳＢ） ，０，１，０（ＬＳＢ） ）を示し、従って、ＭＵＬ３０７から出力されるＭＵＬＯＵＴ３０８は、ベクトル値（０（ＭＳＢ） ，１，０，０（ＬＳＢ） ）を示す。この動作は、前述した＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ５に対応する。
【００７９】
次に、図４に示されるように、タイミングＴ４で、ＳＲＥＧ３０２の内容がシフトされ、ＳＲＥＧ３０２からＳＷ３０３に、ＳＦＴＶＡＬ３０１の２進表現値（０（ＭＳＢ） ，１，１，０（ＬＳＢ） ）の第２ビット値“１”が、ＳＥＬ３１１として出力される。この動作は、前述した＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ６に対応する。
【００８０】
ＳＷ３０３は、ＳＥＬ３１１の値が“１”である場合には、ＤＢＬＯＵＴ３１０を選択する。ここで、２倍演算部（ＤＢＬ）３０９は、ＭＵＬＯＵＴ３０８のベクトル値（０（ＭＳＢ） ，１，０，０（ＬＳＢ） ）に対して１ビット左シフト演算を実行することによって、ＤＢＬＯＵＴ３１０として、ベクトル値（１（ＭＳＢ） ，０，０，０（ＬＳＢ） ）を出力する。そして、図４に示されるように、タイミングＴ５において、ＳＷ３０３が選択しているＤＢＬＯＵＴ３１０の上記ベクトル値が、ＬＡＴ３０５にラッチされる。この動作は、前述の＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ４における対象ビットが“１”である場合の処理に対応する。
【００８１】
この結果、ＬＡＴＯＵＴ３０６は、ベクトル値（１（ＭＳＢ） ，０，０，０（ＬＳＢ） ）を示し、従って、ＭＵＬ３０７から出力されるＭＵＬＯＵＴ３０８は、ベクトル値（１（ＭＳＢ） ，１，０，０（ＬＳＢ） ）を示す。この動作は、前述した＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ５に対応する。
【００８２】
次に、図４に示されるように、タイミングＴ４で、ＳＲＥＧ３０２の内容がシフトされ、ＳＲＥＧ３０２からＳＷ３０３に、ＳＦＴＶＡＬ３０１の２進表現値（０（ＭＳＢ） ，１，１，０（ＬＳＢ） ）の第１ビット値（ＬＳＢ）“０”が、ＳＥＬ３１１として出力される。この動作は、前述した＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ６に対応する。
【００８３】
ＳＷ３０３は、ＳＥＬ３１１の値が“０”である場合には、ＭＵＬＯＵＴ３０８のベクトル値（１（ＭＳＢ） ，１，０，０（ＬＳＢ） ）を選択する。そして、図４に示されるように、タイミングＴ７において、ＳＷ３０３が選択しているＭＵＬＯＵＴ３０８の上記ベクトル値が、ＬＡＴ３０５にラッチされる。この動作は、前述した＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ４における対象ビットが“０”である場合の処理に対応する。
【００８４】
この結果、ＬＡＴＯＵＴ３０６は、ベクトル値（１（ＭＳＢ） ，１，０，０（ＬＳＢ） ）を示す。そして、８タイミングめのタイミングＴ７の終了に同期して、ＬＡＴＯＵＴ３０６のベクトル値（１（ＭＳＢ） ，１，０，０（ＬＳＢ） ）が、位相シフト量ｄ＝６に対応する図１２のＴＡＰＩＮＦＯ１２０５として得られる。
【００８５】
このベクトル値は、図２（ｃ） の最終的な演算結果α６ ＝α３ ＋α２ 、又は数１３式に示される従来の演算結果と良く一致している。
＜本発明の実施の形態におけるＭＵＬ３０７の第１の回路構成＞
図５は、図３のＭＵＬ３０７の第１の回路構成図である。
【００８６】
この回路は、入力信号線ａ０ 〜ａ３ （図３のＬＡＴＯＵＴ３０６）と出力信号線ｂ０ 〜ｂ３ （図３のＭＵＬＯＵＴ３０８）との間で、次のような接続を実現する。すなわち、
（１）まず一般に入力信号線ａｉ （０≦ｉ≦ｎ−１）につき、ｉ≦［ｎ／２］（但し、［ｘ］はｘを超えない整数）である場合は、入力信号線ａｉ は出力信号線ｂ２ｉに接続される。具体的には、入力信号線ａｏ は排他的論理和回路（ＥＸＯＲ）５０１を介して出力信号線ｂｏ に接続され、入力信号線ａ１ はＥＸＯＲ５０１を介して出力信号線ｂ２ に接続される。
【００８７】
（２）次に一般に入力信号線ａｉ （０≦ｉ≦ｎ−１）につき、ｉ＞［ｎ／２］である場合には、入力信号線ａｉ は、ガロア体ＧＦ（２ｎ ）内の原始多項式ｆ（ｘ） ＝ｘ４ ＋ｘ＋１により定まるα２ｉと等価な１本以上の出力信号線ｂｊ （但し、０≦ｊ≦ｎ−１）に接続される。具体的には、入力信号線ａ２ は、出力信号線ｂ１ とＥＸＯＲ５０１を介して出力信号線ｂ０ とに接続され、入力信号線ａ３ は、出力信号線ｂ３ とＥＸＯＲ５０１を介して出力信号線ｂ２ とに接続される。
【００８８】
上述のように、１つの出力信号線に対し、複数の入力信号線が接続される場合には、複数の入力信号線はＥＸＯＲ５０１を介して出力信号線に接続される。
以上の構成により、図３のガロア体ＧＦ（２ｎ ）内の自乗演算を実行するＭＵＬ３０７は、１クロックで動作するハードウエアとして実現できる。
＜本発明の実施の形態におけるＭＵＬ３０７の第２の回路構成＞
図６は、図３のＭＵＬ３０７の第２の回路構成図である。
【００８９】
この回路は、入力信号線ａ０ 〜ａｎ−１ （図６ではｎ＝４）の各信号値を保持する入力レジスタ６０１と、ガロア体ＧＦ（２ｎ ）内の原始元αに対応する各演算値α０ ，α２ ，・・・，α２ｎを示す係数値を記憶するタップテーブル６０２と、ｎビットの各信号値ｂ０ 〜ｂｎ−１ を保持するラッチ６０３と、ラッチ６０３の各出力値とタップテーブル６０２の各出力値との排他的論理和をそれぞれ演算し、その演算結果をラッチ６０１の入力側にフィードバックするｎ個の排他的論理和回路（ＥＸＯＲ）６０４とを有する。
【００９０】
動作開始時には、まず、ラッチ６０３の内容が全て０にリセットされる。
次に、入力レジスタ６０１に設定された入力信号線ａ０ 〜ａｎ−１ （図３のＬＡＴＯＵＴ３０６）のうち、入力信号線ａ０ の信号値から順に入力信号線ａｎ−１ の信号値まで、下記動作が繰り返し実行される。
【００９１】
（１）現在処理中の入力信号線ａｉ の信号値に対応するタップテーブル６０２内の係数値群が読み出され、それぞれの係数値がｎ個のＥＸＯＲ６０４のそれぞれに入力される。各ＥＸＯＲ６０４には、ラッチ６０３の各出力も入力している。
【００９２】
（２）各ＥＸＯＲ６０４がラッチ６０３の各入力にフィードバックされる。
（３）次の入力信号線ａｉ＋１ が選択され、上記（１）及び（２）の動作が再度実行される。
【００９３】
（４）入力信号線ａｎ−１ に対し上記（１）及び（２）の動作が終了したら、各ＥＸＯＲ６０４の出力が出力信号ｂ０ 〜ｂ３ （図３のＭＵＬＯＵＴ３０８）として出力される。
【００９４】
以上の構成により、図３のガロア体ＧＦ（２ｎ ）内の自乗演算を実行するＭＵＬ３０７は、最大ｎクロックで動作するハードウエアとして実現できる。
＜本発明の実施の形態におけるＤＢＬ３０９の第１の回路構成＞
図７は、図３のＤＢＬ３０９の第１の回路構成図である。
【００９５】
この回路は、入力信号線ａ０ 〜ａ３ （図３のＭＵＬＯＵＴ３０８）と出力信号線ｂ０ 〜ｂ３ （図３のＤＢＬＯＵＴ３１０）との間で、次のような接続を実現する。すなわち、
（１）まず一般に入力信号線ａｉ （０≦ｉ≦ｎ−１）につき、ｉ＜ｎ−１の場合は、入力信号線ａｉ は出力信号線ｂｉ＋１ に接続される。具体的には、入力信号線ａｏ ，ａ１ ，ａ２ はそれぞれ、出力信号線ｂ１ ，ｂ２ ，ｂ３ に接続される。
【００９６】
（２）次に一般に入力信号線ａｉ （０≦ｉ≦ｎ−１）につき、ｉ＝ｎ−１の場合は、入力信号線ａｉ は、ガロア体ＧＦ（２ｎ ）内の原始多項式ｆ（ｘ） ＝ｘ４ ＋ｘ＋１によって定まるαｎ と等価な１本以上の出力信号線ｂｊ （但し、０≦ｊ≦ｎ−１）に接続される。具体的には、入力信号線ａ３ は、出力信号線ｂ０ とＥＸＯＲ７０１を介して出力信号線ｂ１ とに接続される。
【００９７】
上述のように、１つの出力信号線に対し、複数の入力信号線が接続される場合には、複数の入力信号線はＥＸＯＲ７０１を介して出力信号線に接続される。
以上の構成により、図３のガロア体ＧＦ（２ｎ ）内の２倍演算を実行するＤＢＬ３０９は、１クロックで動作するハードウエアとして実現できる。
＜本発明の実施の形態におけるＤＢＬ３０９の第２の回路構成＞
図８は、図３のＤＢＬ３０９の第２の回路構成図である。
【００９８】
この回路は、ｎ（図８ではｎ＝４）段のシフトレジスタ（ＳＲ）８０１に加えて、ガロア体ＧＦ（２ｎ ）内の原始多項式ｆ（ｘ） ＝ｘ４ ＋ｘ＋１によって定まるαｎ と等価な１個以上の係数の位置に対応するＳＲ８０１の１個以上の所定段の出力とＳＲ８０１の最終段の出力とに対してそれぞれ排他的論理和を演算し、各演算結果をＳＲ８０１の上記各所定段の次段への各入力信号として出力する１個以上の排他的論理和回路（ＥＸＯＲ）８０２とを有する。図８の例では、ＳＲ８０１の第１段めａｏ と第２段めａ１ との間にＥＸＯＲ８０２が挿入される。
【００９９】
動作時には、ＳＲ８０１の各段に入力信号（図３のＭＵＬＯＵＴ３０８）が入力され、１段分のシフト動作が実行された後に、ＳＲ８０１の各段の内容が出力信号（図３のＤＢＬＯＵＴ３１０）として出力される。
【０１００】
以上の構成により、図３のガロア体ＧＦ（２ｎ ）内の２倍演算を実行するＤＢＬ３０９は、１クロックで動作するハードウエアとして実現できる。
【０１０１】
【発明の効果】
本発明によれば、「現在ベクトル値に原始元αのベクトル表現値を乗算しそのベクトル乗算結果を自乗する演算」又は「現在ベクトル値をそのまま自乗する演算」を、ガロア体ＧＦ（２ｎ ）内で、概略｛ｌｏｇ（ｄ）／ｌｏｇ（２）｝回繰り返し実行するだけで算出することが可能となる。
【０１０２】
そして、ガロア体ＧＦ（２ｎ ）内での、上記２種類の演算は、コンパクトな規模のハードウエアで実現することが可能である。
この結果、Ｍ系列の周期が長いほど、その位相シフト係数算出を、従来よりも大幅に少ない繰り返し回数で算出することが可能となる。
【図面の簡単な説明】
【図１】原始多項式ｆ（ｘ） ＝ｘ４ ＋ｘ＋１に対応するガロア体ＧＦ（２４ ）の原始元αのベクトル表現と、そのベキ乗のベクトル表現を示す図である。
【図２】本発明の操作原理の説明図である。
【図３】本発明の実施の形態の回路の構成図である。
【図４】本発明の実施の形態の回路の動作タイミングチャートである。
【図５】自乗演算部（ＭＵＬ）の第１の回路構成図である。
【図６】自乗演算部（ＭＵＬ）の第２の回路構成図である。
【図７】２倍演算部（ＤＢＬ）の第１の回路構成図である。
【図８】２倍演算部（ＤＢＬ）の第２の回路構成図である。
【図９】ＣＤＭＡ通信システムの一原理構成を示す図である。
【図１０】Ｍ系列を発生する回路の構成図である。
【図１１】４段のＭ系列を発生する回路の構成図である。
【図１２】任意の位相を有するＭ系列を発生する回路の構成図である。
【図１３】任意の位相を有するＭ系列の発生原理の説明図（その１）である。
【図１４】任意の位相を有するＭ系列の発生原理の説明図（その２）である。
【図１５】任意の位相を有するＭ系列を発生するためのタップ情報ＴＡＰＩＮＦＯの生成回路の従来技術の構成図である。
【符号の説明】
３０１ ＳＦＴＶＡＬ
３０２ ＳＲＥＧ
３０３ ＳＷ
３０４ ＬＡＴＩＮＩ
３０５ ＬＡＴ
３０６ ＬＡＴＯＵＴ
３０７ ＭＵＬ
３０８ ＭＵＬＯＵＴ
３０９ ＤＢＬ
３１０ ＤＢＬＯＵＴ
３１１ ＳＥＬ
５０１、６０４、７０１、８０２、１２０７、１５０２ ＥＸＯＲ
６０１ 入力レジスタ
６０２ タップテーブル
６０３ ラッチ
８０１、１２０３、１５０１ ＳＲ
９０１ ＣＤＭＡ送信機
９０２ ＣＤＭＡ受信機
９０３ 送信信号源
９０４ 拡散符号生成部
９０５ 拡散変調部
９０６ 伝送路
９０７ 逆拡散符号生成部
９０８ 逆拡散復調部
９０９ 受信信号処理部
１２０１ ＰＮＧ
１２０２ ＡＴＡＰ
１２０４ ＴＡＰ
１２０５ ＴＡＰＩＮＦＯ
１２０６ ＡＮＤ
【発明の属する技術分野】
本発明は、拡散変調方式による通信システム等に適用される、擬似雑音系列を指定された任意の位相で発生するための技術に関する。
【０００２】
【従来の技術】
スペクトル拡散変調を用いた通信方式においては、符号分割多元接続（Ｃｏｄｅ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅ Ａｃｃｅｓｓ：ＣＤＭＡ）によって、多数の信号のスペクトルを広帯域に拡散させ多重化して伝送することが可能である。図９は、ＣＤＭＡ通信システムの一原理構成を示す図である。
【０００３】
ＣＤＭＡ送信機９０１側では、送信信号源９０３から出力される例えば周波数変調又は位相変調された送信信号は、拡散変調部９０５によって、拡散符号生成部９０４が生成する拡散符号を使ってスペクトル拡散変調され、その結果得られる送信信号が伝送路９０６に送出される。
【０００４】
ＣＤＭＡ受信機９０２においては、逆拡散復調部９０８が、送信側の拡散符号と同じ系列及び位相を有し送信側のタイミングに同期して逆拡散符号生成部９０７から出力される逆拡散符号を使って、受信信号に対し、逆拡散（復調）処理を行う必要がある。
【０００５】
従って、逆拡散符号生成部９０７には、タイミング同期信号（通常は、ＣＤＭＡ受信機９０２内部において受信信号から自律的に生成される）に従って、任意の位相を有する系列符号を生成する機能が必要とされる。
【０００６】
ＣＤＭＡ通信においては、スペクトルを拡散するための拡散符号（及び逆拡散符号）は、広帯域信号であることに加え、（１）多くのユーザへの符号の割当てを可能とするために符号の種類が多いこと、（２）異なるユーザの符号との識別を可能とするために相互相関が小さいこと、（３）自局宛の信号に対する同期が確実にとれるようにするために鋭い自己相関特定を有すること、及び（４）通信信号の秘話性を高めるためにできるだけランダムで周期が長く解読が困難であること、等の条件が要求される。
【０００７】
このような条件を満足する符号として、従来、擬似雑音（ＰＮ：ＰｓｅｕｄｏｒａｎｄｏｍＮｏｉｓｅ）系列が知られている。
ＰＮ系列は、シフトレジスタを用いて発生させることができるため、その発生過程は、確定的（ｄｅｔｅｒｍｉｎｉｓｔｉｃ ）であり真にランダムではない。しかし、ＰＮ系列は、以下のランダム性の性質（ｒａｎｄｏｍｎｅｓｓ ｐｒｏｐｅｒｔｙ ）を満足する符号であるため、上記条件を必要とするＣＤＭＡ通信の拡散符号として適している。
性質１：平衡性（ｂａｌａｎｃｅ ｐｒｏｐｅｒｔｙ）
系列の１周期内で、“１”の出現回数と“０”の出現回数は、高々１しか違わない。
性質２：連なり性（ｒｕｎ ｐｒｏｐｅｒｔｙ）
１周期に含まれる「１の連なり」と「０の連なり」のうち、それぞれの連なりの長さは、連なりの分類数の１／２が“１”、１／４が“２”、１／８が“３”、・・・である。すなわち、連なり数ｋの連なりは｛（連なりの分類数）×（１ ／２ｋ ）｝個存在する。なお、この個数が１より小さくなる連なりは、無意味な連なりとなる。
性質３：相関性（ｃｏｒｒｅｌａｔｉｏｎ ｐｒｏｐｅｒｔｙ）
系列を巡回させ、あらゆる状態で２つの系列間でそれらの各桁ごとに各系列の符号値の比較を行った場合、符号値が一致する桁の数と一致しない桁の数は、高々１しか違わない。
このような性質を満足するＰＮ系列の代表例として、Ｍ系列（ｍａｘｉｍｕｍ ｌｅｎｇｔｈｓｅｑｕｅｎｃｅ：最大周期系列）が知られている。Ｍ系列は、図１０に示される、ｎ段のシフトレジスタを含む回路を用いて、発生される。
【０００８】
図１０で、ｎ段のシフトレジスタの各段の出力に係数ｆｉ （＝０又は１）が乗算され、その乗算結果が、排他的論理和回路（図中の丸で囲まれた“＋”記号）を介してシフトレジスタの入力側にフィードバックされる。
【０００９】
初期状態が、シフトレジスタの各段が全て０である状態ではない場合に、係数ｆｉ が特定の条件を満たすときに、シフトレジスタから出力される系列ａｉ の周期が、ｎ段のシフトレジスタによって発生できる最大周期（２ｎ −１）となる。このような系列が、Ｍ系列と呼ばれる。
【００１０】
いま、図１０の回路は、次式によって表現できる。
【００１１】
【数１】
この式において、ｆｎ ＝１とおけば、次式が得られる。
【００１３】
【数２】
上記数１式又は数２式は、線形再帰式（ｌｉｎｅａｒ ｒｅｃｕｒｒｉｎｇ ｅｑｕａｔｉｏｎ ）とよばれる。ここで、ａｉ＋ｊ ＝ｘｊ ａｉ となるような遅延演算子ｘを導入すると、数２式は、次式で表現される。
【００１５】
【数３】
上記数３式の左辺の括弧内の項によって表現される、次式の多項式ｆ（ｘ） は、特性多項式（ｃｈａｒａｃｔｅｒｉｓｔｉｃ ｐｏｌｙｎｏｍｉａｌ ）と呼ばれる。
【００１７】
【数４】
この数４式に示される係数ｆｊ がガロア体ＧＦ（２ｎ ）に属し、ｆ（ｘ） が、ガロア体ＧＦ（２ｎ ）の原始元αが有する最小多項式である場合に、ｎ段のシフトレジスタを含む図１０に示される回路は、最大周期（２ｎ −１）を有するＭ系列を発生できることが知られている。この最小多項式は、ｋ次原始多項式（ｐｒｉｍｉｔｉｖｅ ｐｏｌｙｎｏｍｉｎａｌ ｏｆ ｄｅｇｒｅｅ ｋ ）と呼ばれている。詳細は、例えば文献：「センシング／認識シリーズ 第８巻、Ｍ系列とその応用／１６頁〜」（柏木 濶著／昭晃堂）に示されている。
【００１９】
原始多項式は、上記文献の１７１頁〜１９１頁に示されるようにして算出することができ、また、そこで引用されているいくつかの文献によって、多くの種類の原始多項式が既に求められている。
【００２０】
例えば、ガロア体ＧＦ（２４ ）の原始多項式ｆ（ｘ） ＝ｘ４ ＋ｘ＋１に対応する数４式に示される係数ｆｊ は、ｆ０ ＝１，ｆ１ ＝１，ｆ２ ＝ｆ３ ＝０，ｆ４ ＝１となる。この結果、図１０に基づいて、図１１に示されるＭ系列発生回路を構成することができる。
【００２１】
ここで、図１１に示されるＭ系列発生回路で、Ｍ系列の出力ａｉ に対して位相がｄビットだけシフトしたＭ系列ｘｄ ａｉ を得ることを考える。Ｍ系列は、ｎ段（図１１の場合は４段）のシフトレジスタの所定の初期状態が与えられれば、それから後の全ての状態が定まるから、任意の位相を有するＭ系列は、次式に示されるように、シフトレジスタの各段の出力の線形結合によって得られることがわかる。
【００２２】
【数５】
これより、４段のシフトレジスタを含む図１１に示されるＭ系列発生回路から、任意の位相を有するＭ系列を発生する回路は、図１２に示されるように構成することができる。
【００２４】
図１２で、ＰＮ発生器（ＰＮＧ）１２０１内の４段のシフトレジスタ（ＳＲ）１２０３の各段には、それぞれ初期値が与えられる。タップ（ＴＡＰ）１２０４により、図１１に相当するフィードバックが与えられる。可変タップ（ＡＴＡＰ）１２０２内の４つのアンド回路（ＡＮＤ）１２０６には、数５式の各係数ｂ０ 〜ｂ３ に対応するタップ情報（ＴＡＰＩＮＦＯ）１２０５が与えられる。この結果、ＳＲ１２０３の各段の出力のうち、上記ＴＡＰＩＮＦＯ１２０５によって選択された出力が、それに対応するアンド回路（ＡＮＤ）１２０６及び排他的論理和回路（ＥＸＯＲ）１２０７によって他の出力と加算され、それらの加算結果として、任意の位相ｄを有するＭ系列ｘｄ ａｉ が出力される。
【００２５】
なお、ＳＲ１２０３の初期値を与える手段、及びシフト動作を実現するためのクロックを供給する手段等については、省略し図示していない。
次に、ＴＡＰＩＮＦＯ１２０５を構成する数５式の係数ｂ０ 〜ｂ３ の算出原理について説明する。
【００２６】
まず、図１２に示されるＰＮＧ１２０１において、Ｍ系列の出力ａｉ に対してそれぞれ１〜３ビットだけ位相がシフトした各Ｍ系列ｘ１ ａｉ 〜ｘ３ ａｉ は、図１３に示されるように、第２段め〜第４段めの各シフトレジスタ段ＳＲ１〜ＳＲ４の各出力にほかならない。すなわち、
【００２７】
【数６】
である。
次に、Ｍ系列の出力ａｉ に対して４ビット位相がシフトしたＭ系列ｘ４ ａｉ を考える。この場合、原始多項式ｆ（ｘ） ＝ｘ４ ＋ｘ＋１において、
【００２９】
【数７】
とおくと、ガロア体上の演算により、下記各式が成り立つ。
【００３１】
【数８】
【数９】
上記数９式より、Ｍ系列の出力ａｉ に対して位相が４ビットシフトしたＭ系列ｘ４ ａｉ は、ａｉ 自身と、ａｉ に対して位相が１ビットシフトした出力ｘ１ ａｉ との排他的論理和によって表現できることがわかる。すなわち、図１４に示されるように、ａｉ に対して位相が４ビットシフトしたＭ系列ｘ４ ａｉ は、第１段めのシフトレジスタ段ＳＲ０の出力と、第２段めのシフトレジスタ段ＳＲ１の出力の排他的論理和によって得られる。すなわち、
【００３４】
【数１０】
である。
続いて、Ｍ系列の出力ａｉ に対して位相が５ビットシフトしたＭ系列ｘ５ ａｉ は、数９式の両辺にｘを乗算することによって得られる下記数１１式より、図１４に示されるように、第２段めのシフトレジスタ段ＳＲ１の出力と、第３段めのシフトレジスタ段ＳＲ２の出力の排他的論理和によって得られる。
【００３６】
【数１１】
すなわち、
【００３８】
【数１２】
である。
更に、Ｍ系列の出力ａｉ に対し位相が６ビットシフトしたＭ系列ｘ６ ａｉ は、数１１式の両辺に更にｘを乗算することによって得られる下記数１３式より、第３段めのシフトレジスタ段ＳＲ２の出力と、第４段めのシフトレジスタ段ＳＲ３の出力の排他的論理和によって得られる。
【００４０】
【数１３】
すなわち、
【００４２】
【数１４】
である。
以上に示される規則でＴＡＰＩＮＦＯ１２０５を構成する係数ｂ０ 〜ｂ３ を順次出力する回路として、従来、図１５に示されるものが知られている。
【００４４】
この回路では、原始多項式ｆ（ｘ） ＝ｘ４ ＋ｘ＋１に対応して４段のシフトレジスタ（ＳＲ）１５０１が用いられ、数７式の右辺を構成する各項１＝ｘ０ ，ｘ＝ｘ１ に対応するシフトレジスタ段ａ０ ，ａ１ の入力側に排他的論理和回路ＥＸＯＲ１５０２が挿入され、そこにシフトレジスタの出力段ａ４ の出力（数７式の左辺項ｘ４ に対応する）がフィードバックされる。なお、シフトレジスタ段ａ０ の前段は存在しないため、その入力側には出力段ａ４ の出力が直接フィードバックされる。
【００４５】
より一般的には、原始多項式ｆ（ｘ） の次数に対応する段数のシフトレジスタが用いられ、ｆ（ｘ） ＝０とすることによって、数７式と同様にして、最高次数の項が左辺、それ以外の次数の項が右辺となる等式が構成される。そして、その等式の右辺を構成する各項に対応するシフトレジスタ段の入力側に排他的論理和回路が挿入され、そこにシフトレジスタの出力段の出力（その等式の左辺項に対応する）がフィードバックされる。
【００４６】
続いて、図１５において、ＳＲ１５０１の初期値として、第１段めのシフトレジスタ段ａ０ に１がセットされ、それ以外のシフトレジスタ段ａ１ 〜ａ３ には０がセットされる。
【００４７】
そして、所望の位相シフト量に対応する回数だけシフト動作が実行されることにより、ＳＲ１５０１の各段ａ０ 〜ａ３ の各出力として、図１２に示されるＴＡＰＩＮＦＯ１２０５を構成する各係数ｂ０ 〜ｂ３ が決定される。
【００４８】
【発明が解決しようとする課題】
しかし、図１５に示される従来技術では、所望の位相シフト量に対応するＴＡＰＩＮＦＯ１２０５を算出するためには、そのシフト量に対応する回数だけシフト動作を実行する必要がある。従って、Ｍ系列の周期が長くなった場合（例えば１０分程度となった場合）には、ＴＡＰＩＮＦＯ１２０５の算出に膨大な時間がかかってしまうという問題点を有していた。
【００４９】
本発明の課題は、各位相シフト量に対応する各タップ情報の算出を高速に実行することにある。
【００５０】
【課題を解決するための手段】
本発明は、ｎ次の原始多項式ｆ（ｘ） により生成されるＭ系列の出力ａｉ に対し位相がｄビットだけシフトしたＭ系列ｘｄ ａｉ を、前記出力ａｉ に対しそれぞれ位相が０〜ｎ−１ビットだけシフトした各Ｍ系列ｘ０ ａｉ 〜ｘｎ−１ ａｉ の線形結合、
ｂ０ ｘ０ ａｉ ＋ｂ１ ｘ１ ａｉ ＋ｂ２ ｘ２ ａｉ ＋・・・＋ｂｎ−１ ｘｎ−１ ａｉ
によって得るための各位相シフト係数ｂ０ 〜ｂｎ−１ を算出するための技術を前提とする。
【００５１】
本発明の第１の過程では、まず、位相シフト量ｄの２進値が入力される。
第２の過程では、１０進値の１に対応するｎビットのベクトル値が初期入力ベクトル値として設定される。
【００５２】
第３の過程では、対象ビットが、第１の過程において入力された位相シフト量ｄの２進値の最上位ビットとして設定される。
第４の過程では、対象ビットが“１”である場合に、入力ベクトル値に、ガロア体ＧＦ（２ｎ ）内で、原始元αのベクトル値が乗算され、その乗算結果が出力ベクトル値とされ、対象ビットが“０”である場合に、入力ベクトル値がそのまま出力ベクトル値とされる。
【００５３】
第５の過程では、第４の過程において得られる出力ベクトル値に対してガロア体ＧＦ（２ｎ ）内で自乗演算が実行される。
第６の過程では、第１の過程において入力された位相シフト量ｄの２進値において、対象ビットの位置が１ビット最下位ビット側にシフトされ、第５の過程における自乗演算結果を新たな入力ベクトル値として、第４及び第５の過程が実行させられる。
【００５４】
第７の過程では、第１の過程において入力された位相シフト量ｄの２進値を構成する全てのビットについて第４及び第５の過程の実行が終了した時点で、それまでに得られた演算結果の各要素が位相シフト係数ｂ０ 〜ｂｎ−１ として出力される。
【００５５】
【発明の実施の形態】
以下、図面を参照しながら、本発明の実施の形態について詳細に説明する。
＜本発明の実施の形態の原理＞
まず、本発明の実施の形態の原理について説明する。
【００５６】
本発明の実施の形態は、一例として、４段のシフトレジスタ（ＳＲ）１２０３を含み任意の位相を有するＭ系列を発生することのできる図１２に示される回路を前提とする。
【００５７】
今、ガロア体ＧＦ（２ｎ ）の原始元をαとする。この場合、図１２に示されるＴＡＰＩＮＦＯ１２０５である前述の数５式の係数ｂ０ 〜ｂｎ−１ は、αをｎビットのベクトルで表現したときに、そのベクトルについて、ガロア体ＧＦ（２ｎ ）内でαｄ を演算して得られるベクトルの各ビットの値に等価である。
【００５８】
図１は、原始多項式ｆ（ｘ） ＝ｘ４ ＋ｘ＋１に対応するガロア体ＧＦ（２４ ）の原始元αのベクトル表現と、そのベキ乗（ｅｘｐｏｎｅｎｔｉａｔｉｏｎ）のベクトル表現を示す図である。この場合に、αのベクトル表現は（０（ＭＳＢ） ，０，１，０（ＬＳＢ） ）（１０進表現で２）である。そして、例えばα１ 〜α６ のベクトル表現の各ビット値は、前述した従来技術における数６式、数１０式、数１２式、及び数１４式によって示される各係数値ｂ０ 〜ｂ３ とよく一致することがわかる。
【００５９】
ここで、αｄ は、下記数１５式に示されるように分解することができる。
【００６０】
【数１５】
そして、数１５式の分解演算によって得られる項αｓ においてｓをｄに置き換えて更に数１５式の分解演算を行う、という操作を繰り返すことにより、例えばα６ は、次式のように分解することができる。
【００６２】
【数１６】
これよりαｄ のベクトル表現値は、数１６式の右辺のように分解された括弧の入れ子構造の最も内側から順に、「現在ベクトル値にαのベクトル表現値を乗算しそのベクトル乗算結果を自乗する演算」又は「現在ベクトル値をそのまま自乗する演算」を、ガロア体ＧＦ（２ｎ ）内で、概略｛ｌｏｇ（ｄ）／ｌｏｇ（２）｝回繰り返し実行するだけで算出することができる。
【００６４】
そして、ガロア体ＧＦ（２ｎ ）内での、「現在ベクトル値にαのベクトル表現値を乗算しそのベクトル乗算結果を自乗する演算」又は「現在ベクトル値をそのまま自乗する演算」をハードウエアで実現することができれば、αｄ のベクトル表現値、すなわち前述した数５式の係数ｂ０ 〜ｂｎ−１ は、シフトレジスタの段数ｎが大きければ大きいほど、従来必要であったシフト動作回数ｄ回よりも大幅に少ない繰り返し回数で算出することが可能となる。
【００６５】
図２は、任意の位相シフト量ｄが与えられたときに、図１２のＴＡＰＩＮＦＯ１２０５である前述した数５式の係数ｂ０ 〜ｂｎ−１ を算出するための上記繰返し演算を特定するアルゴリズムの原理図である。
ステップ１：
まず、位相シフト量ｄの２進表現値が入力される。例えば、位相シフト量ｄ＝６としたとき、それに対する４ビットの２進表現値は、図２（ａ） に示されるように、（０（ＭＳＢ） ，１，１，０（ＬＳＢ） ）となる。
ステップ２：
ｎビットのベクトル値（０（ＭＳＢ） ，０，０，１（ＬＳＢ） ）（１０進値の１）を、初期入力ベクトル値とする。
ステップ３：
対象ビットが、ステップ１で入力された位相シフト量ｄの２進表現値のＭＳＢ（最上位ビット）とされる。
ステップ４：
対象ビットが“１”なら、入力ベクトル値に、ガロア体ＧＦ（２ｎ ）内で、原始元αのベクトル値が乗算され、その乗算結果がステップ４の出力ベクトル値とされる（操作Ｉ）。例えば、原始多項式ｆ（ｘ） ＝ｘ４ ＋ｘ＋１に対応するガロア体ＧＦ（２４ ）の原始元αのベクトル値は、図１に示されるように（０（ＭＳＢ） ，０，１，０（ＬＳＢ） ）、すなわち１０進値で２である。従って、この場合には、入力ベクトル値に対して、１ビット左シフト演算が実行される。
【００６６】
対象ビットが“０”なら、入力ベクトル値がそのままステップ２の出力ベクトル値とされる。
ステップ５：
ステップ４の出力ベクトル値がガロア体ＧＦ（２ｎ ）内で自乗され、その演算結果がステップ５の出力ベクトル値とされる（操作ＩＩ）。具体的には、ステップ４の出力ベクトル値のｉ番目の要素ａｉ （０≦ｉ≦ｎ−１）がセットされている場合には、ａｉ がクリアされ要素ａ２ｉに、ｍｏｄ ２で１が加算され、その加算結果がステップ５の出力ベクトル値とされる。但し、２ｉがｎ以上の場合には、ガロア体ＧＦ（２ｎ ）内の原始多項式ｆ（ｘ） によって定まるα２ｉと等価な１本以上の要素ａｊ に対して、ｍｏｄ ２で１が加算され、その加算結果がステップ５の出力ベクトル値とされる。
ステップ６：
ステップ１で入力された位相シフト量ｄの２進表現値において、対象ビットの位置が１ビットＬＳＢ側にシフトされ、ステップ５の出力ベクトル値が新たな入力ベクトル値とされて、上記ステップ４とステップ５が再度実行される。
【００６７】
ＬＳＢに対するステップ４とステップ５の処理が終了したら、そのステップ５で得られた出力ベクトル値の各要素が、図１２のＴＡＰＩＮＦＯ１２０５とされる。
以上のステップ１〜ステップ６のアルゴリズムをハードウエアで実現することにより、任意の位相シフト量ｄに対する図１２のＴＡＰＩＮＦＯ１２０５を高速に演算することが可能となる。
【００６８】
図２（ｂ） は、位相シフト量ｄ＝６に対応する図２（ａ） に示される４ビットの位相シフト量（０（ＭＳＢ） ，１，１，０（ＬＳＢ） ）に対して、上記ステップ１〜ステップ６が実行される手順を示した図である。
【００６９】
また、図２（ｃ） は、図２（ｂ） の各演算手順に対する数学的な演算結果を示した図である。図２（ｃ） の最終的な演算結果α６ ＝α３ ＋α２ は、数１３式に示される従来の演算結果と良く一致している。
＜本発明の実施の形態の全体構成＞
図３は、４段のシフトレジスタ（ＳＲ）１２０３を含み任意の位相を有するＭ系列を発生することのできる図１２に示される回路を前提とし、図１２のＴＡＰＩＮＦＯ１２０５を生成する、本発明の実施の形態の回路の構成図である。
【００７０】
また、図４は、図３の回路の動作タイミングチャートである。
今、原始多項式をｆ（ｘ） ＝ｘ４ ＋ｘ＋１とすれば、位相シフト量（ＳＦＴＶＡＬ）３０１、ラッチ出力（ＬＡＴＯＵＴ）３０６、自乗演算部出力（ＭＵＬＯＵＴ）３０８、及び２倍演算部出力（ＤＢＬＯＵＴ）３１０等の信号は、４ビット幅のベクトル信号となる。
【００７１】
まず、ＳＦＴＶＡＬ３０１がシフト量レジスタ（ＳＲＥＧ）３０２に予め設定されている。この動作は、前述した＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ１に対応する。図４の例では、例えば、位相シフト量ｄ＝６であって、ＳＲＥＧ３０２には、その４ビットの２進表現値（０（ＭＳＢ） ，１，１，０（ＬＳＢ） ）が設定される。
【００７２】
またラッチ部（ＬＡＴ）３０５には、４ビットのベクトル値（０（ＭＳＢ） ，０，０，１（ＬＳＢ） ）が、予め初期入力ベクトル値（ＬＡＴＩＮＩ）３０４として設定されている。この動作は、前述した＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ２に対応する。この結果、ＬＡＴＯＵＴ３０６は、初期ベクトル値（０（ＭＳＢ） ，０，０，１（ＬＳＢ） ）（１０進表現の１）を示し、従って、自乗演算部（ＭＵＬ）３０７から出力されるＭＵＬＯＵＴ３０８も同じベクトル値となる。
【００７３】
次に図４に示されるタイミングＴ０で、ＳＲＥＧ３０２からスイッチ（ＳＷ）３０３に、ＳＦＴＶＡＬ３０１の２進表現値（０（ＭＳＢ） ，１，１，０（ＬＳＢ） ）の第４ビット値（ＭＳＢ値）“０”が、選択制御信号（ＳＥＬ）３１１として出力される。この動作は、前述した＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ３に対応する。
【００７４】
ＳＷ３０３は、ＳＥＬ３１１の値が“０”である場合には、ＭＵＬＯＵＴ３０８を選択する。そして、図４に示されるように、タイミングＴ１において、ＳＷ３０３が選択しているＭＵＬＯＵＴ３０８のベクトル値（０（ＭＳＢ） ，０，０，１（ＬＳＢ） ）が、ＬＡＴ３０５にラッチされる。この動作は、前述した＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ４における対象ビットが“０”である場合の処理に対応する。
【００７５】
この結果、ＬＡＴＯＵＴ３０６は、ベクトル値（０（ＭＳＢ） ，０，０，１（ＬＳＢ） ）（１０進表現の１）を示し、従って、ＭＵＬ３０７から出力されるＭＵＬＯＵＴ３０８も同じベクトル値となる。この動作は、前述した＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ５に対応する。
【００７６】
次に、図４に示されるように、タイミングＴ２で、ＳＲＥＧ３０２の内容がシフトされ、ＳＲＥＧ３０２からＳＷ３０３に、ＳＦＴＶＡＬ３０１の２進表現値（０（ＭＳＢ） ，１，１，０（ＬＳＢ） ）の第３ビット値“１”が、ＳＥＬ３１１として出力される。この動作は、前述した＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ６に対応する。
【００７７】
ＳＷ３０３は、ＳＥＬ３１１の値が“１”である場合には、ＤＢＬＯＵＴ３１０を選択する。ここで、２倍演算部（ＤＢＬ）３０９は、ＭＵＬＯＵＴ３０８のベクトル値（０（ＭＳＢ） ，０，０，１（ＬＳＢ） ）に対して１ビット左シフト演算を実行することによって、ＤＢＬＯＵＴ３１０として、ベクトル値（０（ＭＳＢ） ，０，１，０（ＬＳＢ） ）を出力する。そして、図４に示されるように、タイミングＴ３において、ＳＷ３０３が選択しているＤＢＬＯＵＴ３１０の上記ベクトル値が、ＬＡＴ３０５にラッチされる。この動作は、前述の＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ４における対象ビットが“１”である場合の処理に対応する。
【００７８】
この結果、ＬＡＴＯＵＴ３０６は、ベクトル値（０（ＭＳＢ） ，０，１，０（ＬＳＢ） ）を示し、従って、ＭＵＬ３０７から出力されるＭＵＬＯＵＴ３０８は、ベクトル値（０（ＭＳＢ） ，１，０，０（ＬＳＢ） ）を示す。この動作は、前述した＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ５に対応する。
【００７９】
次に、図４に示されるように、タイミングＴ４で、ＳＲＥＧ３０２の内容がシフトされ、ＳＲＥＧ３０２からＳＷ３０３に、ＳＦＴＶＡＬ３０１の２進表現値（０（ＭＳＢ） ，１，１，０（ＬＳＢ） ）の第２ビット値“１”が、ＳＥＬ３１１として出力される。この動作は、前述した＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ６に対応する。
【００８０】
ＳＷ３０３は、ＳＥＬ３１１の値が“１”である場合には、ＤＢＬＯＵＴ３１０を選択する。ここで、２倍演算部（ＤＢＬ）３０９は、ＭＵＬＯＵＴ３０８のベクトル値（０（ＭＳＢ） ，１，０，０（ＬＳＢ） ）に対して１ビット左シフト演算を実行することによって、ＤＢＬＯＵＴ３１０として、ベクトル値（１（ＭＳＢ） ，０，０，０（ＬＳＢ） ）を出力する。そして、図４に示されるように、タイミングＴ５において、ＳＷ３０３が選択しているＤＢＬＯＵＴ３１０の上記ベクトル値が、ＬＡＴ３０５にラッチされる。この動作は、前述の＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ４における対象ビットが“１”である場合の処理に対応する。
【００８１】
この結果、ＬＡＴＯＵＴ３０６は、ベクトル値（１（ＭＳＢ） ，０，０，０（ＬＳＢ） ）を示し、従って、ＭＵＬ３０７から出力されるＭＵＬＯＵＴ３０８は、ベクトル値（１（ＭＳＢ） ，１，０，０（ＬＳＢ） ）を示す。この動作は、前述した＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ５に対応する。
【００８２】
次に、図４に示されるように、タイミングＴ４で、ＳＲＥＧ３０２の内容がシフトされ、ＳＲＥＧ３０２からＳＷ３０３に、ＳＦＴＶＡＬ３０１の２進表現値（０（ＭＳＢ） ，１，１，０（ＬＳＢ） ）の第１ビット値（ＬＳＢ）“０”が、ＳＥＬ３１１として出力される。この動作は、前述した＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ６に対応する。
【００８３】
ＳＷ３０３は、ＳＥＬ３１１の値が“０”である場合には、ＭＵＬＯＵＴ３０８のベクトル値（１（ＭＳＢ） ，１，０，０（ＬＳＢ） ）を選択する。そして、図４に示されるように、タイミングＴ７において、ＳＷ３０３が選択しているＭＵＬＯＵＴ３０８の上記ベクトル値が、ＬＡＴ３０５にラッチされる。この動作は、前述した＜本発明の実施の形態の原理＞で示される演算アルゴリズムのステップ４における対象ビットが“０”である場合の処理に対応する。
【００８４】
この結果、ＬＡＴＯＵＴ３０６は、ベクトル値（１（ＭＳＢ） ，１，０，０（ＬＳＢ） ）を示す。そして、８タイミングめのタイミングＴ７の終了に同期して、ＬＡＴＯＵＴ３０６のベクトル値（１（ＭＳＢ） ，１，０，０（ＬＳＢ） ）が、位相シフト量ｄ＝６に対応する図１２のＴＡＰＩＮＦＯ１２０５として得られる。
【００８５】
このベクトル値は、図２（ｃ） の最終的な演算結果α６ ＝α３ ＋α２ 、又は数１３式に示される従来の演算結果と良く一致している。
＜本発明の実施の形態におけるＭＵＬ３０７の第１の回路構成＞
図５は、図３のＭＵＬ３０７の第１の回路構成図である。
【００８６】
この回路は、入力信号線ａ０ 〜ａ３ （図３のＬＡＴＯＵＴ３０６）と出力信号線ｂ０ 〜ｂ３ （図３のＭＵＬＯＵＴ３０８）との間で、次のような接続を実現する。すなわち、
（１）まず一般に入力信号線ａｉ （０≦ｉ≦ｎ−１）につき、ｉ≦［ｎ／２］（但し、［ｘ］はｘを超えない整数）である場合は、入力信号線ａｉ は出力信号線ｂ２ｉに接続される。具体的には、入力信号線ａｏ は排他的論理和回路（ＥＸＯＲ）５０１を介して出力信号線ｂｏ に接続され、入力信号線ａ１ はＥＸＯＲ５０１を介して出力信号線ｂ２ に接続される。
【００８７】
（２）次に一般に入力信号線ａｉ （０≦ｉ≦ｎ−１）につき、ｉ＞［ｎ／２］である場合には、入力信号線ａｉ は、ガロア体ＧＦ（２ｎ ）内の原始多項式ｆ（ｘ） ＝ｘ４ ＋ｘ＋１により定まるα２ｉと等価な１本以上の出力信号線ｂｊ （但し、０≦ｊ≦ｎ−１）に接続される。具体的には、入力信号線ａ２ は、出力信号線ｂ１ とＥＸＯＲ５０１を介して出力信号線ｂ０ とに接続され、入力信号線ａ３ は、出力信号線ｂ３ とＥＸＯＲ５０１を介して出力信号線ｂ２ とに接続される。
【００８８】
上述のように、１つの出力信号線に対し、複数の入力信号線が接続される場合には、複数の入力信号線はＥＸＯＲ５０１を介して出力信号線に接続される。
以上の構成により、図３のガロア体ＧＦ（２ｎ ）内の自乗演算を実行するＭＵＬ３０７は、１クロックで動作するハードウエアとして実現できる。
＜本発明の実施の形態におけるＭＵＬ３０７の第２の回路構成＞
図６は、図３のＭＵＬ３０７の第２の回路構成図である。
【００８９】
この回路は、入力信号線ａ０ 〜ａｎ−１ （図６ではｎ＝４）の各信号値を保持する入力レジスタ６０１と、ガロア体ＧＦ（２ｎ ）内の原始元αに対応する各演算値α０ ，α２ ，・・・，α２ｎを示す係数値を記憶するタップテーブル６０２と、ｎビットの各信号値ｂ０ 〜ｂｎ−１ を保持するラッチ６０３と、ラッチ６０３の各出力値とタップテーブル６０２の各出力値との排他的論理和をそれぞれ演算し、その演算結果をラッチ６０１の入力側にフィードバックするｎ個の排他的論理和回路（ＥＸＯＲ）６０４とを有する。
【００９０】
動作開始時には、まず、ラッチ６０３の内容が全て０にリセットされる。
次に、入力レジスタ６０１に設定された入力信号線ａ０ 〜ａｎ−１ （図３のＬＡＴＯＵＴ３０６）のうち、入力信号線ａ０ の信号値から順に入力信号線ａｎ−１ の信号値まで、下記動作が繰り返し実行される。
【００９１】
（１）現在処理中の入力信号線ａｉ の信号値に対応するタップテーブル６０２内の係数値群が読み出され、それぞれの係数値がｎ個のＥＸＯＲ６０４のそれぞれに入力される。各ＥＸＯＲ６０４には、ラッチ６０３の各出力も入力している。
【００９２】
（２）各ＥＸＯＲ６０４がラッチ６０３の各入力にフィードバックされる。
（３）次の入力信号線ａｉ＋１ が選択され、上記（１）及び（２）の動作が再度実行される。
【００９３】
（４）入力信号線ａｎ−１ に対し上記（１）及び（２）の動作が終了したら、各ＥＸＯＲ６０４の出力が出力信号ｂ０ 〜ｂ３ （図３のＭＵＬＯＵＴ３０８）として出力される。
【００９４】
以上の構成により、図３のガロア体ＧＦ（２ｎ ）内の自乗演算を実行するＭＵＬ３０７は、最大ｎクロックで動作するハードウエアとして実現できる。
＜本発明の実施の形態におけるＤＢＬ３０９の第１の回路構成＞
図７は、図３のＤＢＬ３０９の第１の回路構成図である。
【００９５】
この回路は、入力信号線ａ０ 〜ａ３ （図３のＭＵＬＯＵＴ３０８）と出力信号線ｂ０ 〜ｂ３ （図３のＤＢＬＯＵＴ３１０）との間で、次のような接続を実現する。すなわち、
（１）まず一般に入力信号線ａｉ （０≦ｉ≦ｎ−１）につき、ｉ＜ｎ−１の場合は、入力信号線ａｉ は出力信号線ｂｉ＋１ に接続される。具体的には、入力信号線ａｏ ，ａ１ ，ａ２ はそれぞれ、出力信号線ｂ１ ，ｂ２ ，ｂ３ に接続される。
【００９６】
（２）次に一般に入力信号線ａｉ （０≦ｉ≦ｎ−１）につき、ｉ＝ｎ−１の場合は、入力信号線ａｉ は、ガロア体ＧＦ（２ｎ ）内の原始多項式ｆ（ｘ） ＝ｘ４ ＋ｘ＋１によって定まるαｎ と等価な１本以上の出力信号線ｂｊ （但し、０≦ｊ≦ｎ−１）に接続される。具体的には、入力信号線ａ３ は、出力信号線ｂ０ とＥＸＯＲ７０１を介して出力信号線ｂ１ とに接続される。
【００９７】
上述のように、１つの出力信号線に対し、複数の入力信号線が接続される場合には、複数の入力信号線はＥＸＯＲ７０１を介して出力信号線に接続される。
以上の構成により、図３のガロア体ＧＦ（２ｎ ）内の２倍演算を実行するＤＢＬ３０９は、１クロックで動作するハードウエアとして実現できる。
＜本発明の実施の形態におけるＤＢＬ３０９の第２の回路構成＞
図８は、図３のＤＢＬ３０９の第２の回路構成図である。
【００９８】
この回路は、ｎ（図８ではｎ＝４）段のシフトレジスタ（ＳＲ）８０１に加えて、ガロア体ＧＦ（２ｎ ）内の原始多項式ｆ（ｘ） ＝ｘ４ ＋ｘ＋１によって定まるαｎ と等価な１個以上の係数の位置に対応するＳＲ８０１の１個以上の所定段の出力とＳＲ８０１の最終段の出力とに対してそれぞれ排他的論理和を演算し、各演算結果をＳＲ８０１の上記各所定段の次段への各入力信号として出力する１個以上の排他的論理和回路（ＥＸＯＲ）８０２とを有する。図８の例では、ＳＲ８０１の第１段めａｏ と第２段めａ１ との間にＥＸＯＲ８０２が挿入される。
【００９９】
動作時には、ＳＲ８０１の各段に入力信号（図３のＭＵＬＯＵＴ３０８）が入力され、１段分のシフト動作が実行された後に、ＳＲ８０１の各段の内容が出力信号（図３のＤＢＬＯＵＴ３１０）として出力される。
【０１００】
以上の構成により、図３のガロア体ＧＦ（２ｎ ）内の２倍演算を実行するＤＢＬ３０９は、１クロックで動作するハードウエアとして実現できる。
【０１０１】
【発明の効果】
本発明によれば、「現在ベクトル値に原始元αのベクトル表現値を乗算しそのベクトル乗算結果を自乗する演算」又は「現在ベクトル値をそのまま自乗する演算」を、ガロア体ＧＦ（２ｎ ）内で、概略｛ｌｏｇ（ｄ）／ｌｏｇ（２）｝回繰り返し実行するだけで算出することが可能となる。
【０１０２】
そして、ガロア体ＧＦ（２ｎ ）内での、上記２種類の演算は、コンパクトな規模のハードウエアで実現することが可能である。
この結果、Ｍ系列の周期が長いほど、その位相シフト係数算出を、従来よりも大幅に少ない繰り返し回数で算出することが可能となる。
【図面の簡単な説明】
【図１】原始多項式ｆ（ｘ） ＝ｘ４ ＋ｘ＋１に対応するガロア体ＧＦ（２４ ）の原始元αのベクトル表現と、そのベキ乗のベクトル表現を示す図である。
【図２】本発明の操作原理の説明図である。
【図３】本発明の実施の形態の回路の構成図である。
【図４】本発明の実施の形態の回路の動作タイミングチャートである。
【図５】自乗演算部（ＭＵＬ）の第１の回路構成図である。
【図６】自乗演算部（ＭＵＬ）の第２の回路構成図である。
【図７】２倍演算部（ＤＢＬ）の第１の回路構成図である。
【図８】２倍演算部（ＤＢＬ）の第２の回路構成図である。
【図９】ＣＤＭＡ通信システムの一原理構成を示す図である。
【図１０】Ｍ系列を発生する回路の構成図である。
【図１１】４段のＭ系列を発生する回路の構成図である。
【図１２】任意の位相を有するＭ系列を発生する回路の構成図である。
【図１３】任意の位相を有するＭ系列の発生原理の説明図（その１）である。
【図１４】任意の位相を有するＭ系列の発生原理の説明図（その２）である。
【図１５】任意の位相を有するＭ系列を発生するためのタップ情報ＴＡＰＩＮＦＯの生成回路の従来技術の構成図である。
【符号の説明】
３０１ ＳＦＴＶＡＬ
３０２ ＳＲＥＧ
３０３ ＳＷ
３０４ ＬＡＴＩＮＩ
３０５ ＬＡＴ
３０６ ＬＡＴＯＵＴ
３０７ ＭＵＬ
３０８ ＭＵＬＯＵＴ
３０９ ＤＢＬ
３１０ ＤＢＬＯＵＴ
３１１ ＳＥＬ
５０１、６０４、７０１、８０２、１２０７、１５０２ ＥＸＯＲ
６０１ 入力レジスタ
６０２ タップテーブル
６０３ ラッチ
８０１、１２０３、１５０１ ＳＲ
９０１ ＣＤＭＡ送信機
９０２ ＣＤＭＡ受信機
９０３ 送信信号源
９０４ 拡散符号生成部
９０５ 拡散変調部
９０６ 伝送路
９０７ 逆拡散符号生成部
９０８ 逆拡散復調部
９０９ 受信信号処理部
１２０１ ＰＮＧ
１２０２ ＡＴＡＰ
１２０４ ＴＡＰ
１２０５ ＴＡＰＩＮＦＯ
１２０６ ＡＮＤ
Claims (6)
- ｎ次の原始多項式ｆ（ｘ） により生成されるＭ系列の出力ａｉ に対し位相がｄビットだけシフトしたＭ系列ｘｄ ａｉ を、前記出力ａｉ に対しそれぞれ位相が０〜ｎ−１ビットだけシフトした各Ｍ系列ｘ０ ａｉ 〜ｘｎ−１ ａｉ の線形結合、
ｂ０ ｘ０ ａｉ ＋ｂ１ ｘ１ ａｉ ＋ｂ２ ｘ２ ａｉ ＋・・・＋ｂｎ−１ ｘｎ−１ ａｉ
によって得るための各位相シフト係数ｂ０ 〜ｂｎ−１ を算出するための方法であって、
前記位相シフト量ｄの２進値を入力する第１の過程と、
１０進値の１に対応するｎビットのベクトル値を初期入力ベクトル値として設定する第２の過程と、
対象ビットを、前記第１の過程において入力された位相シフト量ｄの２進値の最上位ビットとして設定する第３の過程と、
対象ビットが“１”である場合に、入力ベクトル値に、ガロア体ＧＦ（２ｎ ）内で、原始元αのベクトル値を乗算し、その乗算結果を出力ベクトル値とし、対象ビットが“０”である場合に、入力ベクトル値をそのまま出力ベクトル値とする第４の過程と、
該第４の過程において得られる出力ベクトル値に対してガロア体ＧＦ（２ｎ ）内で自乗演算を実行する第５の過程と、
前記第１の過程において入力された位相シフト量ｄの２進値において、対象ビットの位置を１ビット最下位ビット側にシフトし、前記第５の過程における自乗演算結果を新たな入力ベクトル値として、前記第４及び第５の過程を実行させる第６の過程と、
前記第１の過程において入力された位相シフト量ｄの２進値を構成する全てのビットについて前記第４及び第５の過程の実行が終了した時点で、それまでに得られた演算結果の各要素を前記位相シフト係数ｂ０ 〜ｂｎ−１ として出力する第７の過程と、
を含むことを特徴とするＭ系列の位相シフト係数算出方法。 - ｎ次の原始多項式ｆ（ｘ） により生成されるＭ系列の出力ａｉ に対し位相がｄビットだけシフトしたＭ系列ｘｄ ａｉ を、前記出力ａｉ に対しそれぞれ位相が０〜ｎ−１ビットだけシフトした各Ｍ系列ｘ０ ａｉ 〜ｘｎ−１ ａｉ の線形結合、
ｂ０ ｘ０ ａｉ ＋ｂ１ ｘ１ ａｉ ＋ｂ２ ｘ２ ａｉ ＋・・・＋ｂｎ−１ ｘｎ−１ ａｉ
によって得るための各位相シフト係数ｂ０ 〜ｂｎ−１ を算出するための装置であって、
前記位相シフト量ｄに対応するｎビットの２進値が設定され、クロックに同期したシフト動作を実行すると共に、最上位ビット側出力をスイッチ制御信号として出力するｎ段のシフトレジスタ回路と、
１０進値の１に対応するｎビットのベクトル値が初期入力ベクトル値として設定され、それ以降前記クロックに同期して、ｎビットの入力を順次保持するラッチ回路と、
該ラッチ回路のｎビットの出力に対してガロア体ＧＦ（２ｎ ）内で自乗演算を実行する自乗演算回路と、
該自乗演算回路のｎビットの出力に対してガロア体ＧＦ（２ｎ ）内で２倍演算を実行する２倍演算回路と、
前記自乗演算回路のｎビットの出力又は前記２倍演算回路のｎビットの出力の何れかを、前記スイッチ制御信号に従って選択して前記ラッチ回路に出力するスイッチ回路と、
を含み、
ｎ回の前記シフト動作及びラッチ動作の後に、前記ラッチ回路のｎビットの出力が前記各位相シフト係数ｂ０ 〜ｂｎ−１ として出力される、
ことを特徴とするＭ系列の位相シフト係数算出装置。 - 請求項２に記載の装置であって、
前記自乗演算回路は、ｎビットの入力信号線ａ０ 〜ａｎ−１ とｎビットの出力信号線ｂ０ 〜ｂｎ−１ との間で、ｉがｎ／２を超えない最大整数以下である場合に、前記入力信号線ａｉ が前記出力信号線ｂ２ｉに接続され、ｉがｎ／２を超えない最大整数よりも大きい場合に、前記入力信号線ａｉ が、ガロア体ＧＦ（２ｎ ）内の原始元αが有する原始多項式ｆ（ｘ） により定まる値α２ｉと等価な１本以上の出力信号線ｂｊ （但し、０≦ｊ≦ｎ−１）に接続され、１つの出力信号線に対し複数の入力信号線が接続される場合には複数の入力信号線は排他的論理和回路を介して該出力信号線に接続されるように構成される、
ことを特徴とするＭ系列の位相シフト係数算出装置。 - 請求項２に記載の装置であって、
前記自乗演算回路は、
ｎビットの入力信号線の各信号値を保持する入力レジスタ回路と、
ガロア体ＧＦ（２ｎ ）内の原始元αが有する原始多項式ｆ（ｘ） により定まる各演算値α０ ，α２ ，・・・，α２ｎを示す係数値を記憶するタップテーブル記憶回路と、
ｎビットの各信号値を保持するラッチ回路と、
該ラッチ回路の各出力値と前記タップテーブル記憶回路の各出力値との排他的論理和をそれぞれ演算して、該各演算結果を前記ラッチ回路の入力側にフィードバックするｎ個の排他的論理和回路と、
を含み、
動作開始時に前記ラッチ回路の内容が全て０にリセットされた後、
現在処理中の入力信号線の信号値に対応する前記タップテーブル記憶回路内の係数値群を読み出し、それぞれの係数値を前記ｎ個の排他的論理和回路に入力させ、前記ラッチ回路に対してラッチ動作を行わせる動作を、最下位ビットの入力信号線の信号値から最上位ビットの入力信号線の信号値まで順に、前記入力レジスタ回路に設定された入力信号線の各信号値に対して順次繰り返し実行する、
ことを特徴とするＭ系列の位相シフト係数算出装置。 - 請求項２に記載の装置であって、
前記２倍演算回路は、ｎビットの入力信号線ａ０ 〜ａｎ−１ とｎビットの出力信号線ｂ０ 〜ｂｎ−１ との間で、ｉ＜ｎ−１である場合に、前記入力信号線ａｉ が前記出力信号線ｂｉ＋１ に接続され、ｉ＝ｎ−１である場合に、前記入力信号線ａｉ が、ガロア体ＧＦ（２ｎ ）内の原始元αが有する原始多項式ｆ（ｘ） によって定まる値αｎ と等価な１本以上の出力信号線ｂｊ （０≦ｊ≦ｎ−１）に接続され、１つの出力信号線に対し複数の入力信号線が接続される場合には複数の入力信号線は排他的論理和回路を介して該出力信号線に接続されるように構成される、
ことを特徴とするＭ系列の位相シフト係数算出装置。 - 請求項２に記載の装置であって、
前記２倍演算回路は、
ｎ段のシフトレジスタ回路と、ガロア体ＧＦ（２ｎ ）内の原始元αが有する原始多項式ｆ（ｘ） により定まる値αｎ と等価な１個以上の係数の位置に対応する前記シフトレジスタ回路の１個以上の所定段の出力と該シフトレジスタ回路の最終段の出力とに対してそれぞれ排他的論理和を演算し、各演算結果を前記各所定段の次段への各入力信号として出力する１個以上の排他的論理和回路とを含み、
動作開始時に、前記シフトレジスタ回路の各段にｎビットの入力信号が入力され、１段分のシフト動作が実行された後に、前記シフトレジスタ回路の各段の内容がｎビットの出力信号として出力される、
ことを特徴とするＭ系列の位相シフト係数算出装置。
Priority Applications (5)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP6822698A JP3556461B2 (ja) | 1998-03-18 | 1998-03-18 | Ｍ系列の位相シフト係数算出方式 |
| US09/154,496 US6636549B1 (en) | 1998-03-18 | 1998-09-16 | Method for calculating phase shift coefficients of an M sequence |
| EP19980117649 EP0949764B1 (en) | 1998-03-18 | 1998-09-17 | Method for calculating phase shift coefficients of an M sequence |
| DE1998620026 DE69820026T2 (de) | 1998-03-18 | 1998-09-17 | Verfahren zur Berechnung von Phasenverschiebungs-Koeffizienten einer M-Folge |
| CN98122809A CN1120592C (zh) | 1998-03-18 | 1998-11-26 | 计算m序列的相移系数的方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP6822698A JP3556461B2 (ja) | 1998-03-18 | 1998-03-18 | Ｍ系列の位相シフト係数算出方式 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH11265276A JPH11265276A (ja) | 1999-09-28 |
| JP3556461B2 true JP3556461B2 (ja) | 2004-08-18 |
Family
ID=13367693
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP6822698A Expired - Fee Related JP3556461B2 (ja) | 1998-03-18 | 1998-03-18 | Ｍ系列の位相シフト係数算出方式 |
Country Status (5)
| Country | Link |
|---|---|
| US (1) | US6636549B1 (ja) |
| EP (1) | EP0949764B1 (ja) |
| JP (1) | JP3556461B2 (ja) |
| CN (1) | CN1120592C (ja) |
| DE (1) | DE69820026T2 (ja) |
Families Citing this family (17)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| FI107094B (fi) * | 1999-05-10 | 2001-05-31 | Nokia Mobile Phones Ltd | Menetelmä päivittää koodigeneraattorin lineaarinen palautesiirtorekisteri |
| US6968493B1 (en) * | 1999-09-14 | 2005-11-22 | Maxtor Corporation | Randomizer systems for producing multiple-symbol randomizing sequences |
| JP3314181B2 (ja) * | 2000-04-07 | 2002-08-12 | 独立行政法人通信総合研究所 | 擬似乱数列の出力装置、送信装置、受信装置、通信システム、フィルタ装置、擬似乱数列の出力方法、送信方法、受信方法、フィルタ方法、ならびに、情報記録媒体 |
| JP2001345738A (ja) * | 2000-06-06 | 2001-12-14 | Sony Corp | 同期検出装置 |
| KR100403374B1 (ko) * | 2000-09-27 | 2003-10-30 | 광주과학기술원 | 입력연산자 정규화를 이용한 테이블참조 기반 고속통신용위상계산기 |
| CN100530157C (zh) * | 2003-04-08 | 2009-08-19 | 阿纳洛格装置公司 | 伽罗瓦域线性变换器格栅系统 |
| US20070127431A1 (en) * | 2005-11-11 | 2007-06-07 | Samsung Electronics Co., Ltd. | Method and apparatus for generating pseudorandom binary sequence in communication system using linear feedback shift register |
| JP5101253B2 (ja) * | 2007-11-15 | 2012-12-19 | アンリツ株式会社 | ランダムエラー発生装置、ｍ系列発生回路及びその設計方法 |
| CN102084335B (zh) * | 2008-05-12 | 2015-01-07 | 高通股份有限公司 | 任意伽罗瓦域算术在可编程处理器上的实施 |
| TWI406138B (zh) * | 2010-04-01 | 2013-08-21 | Ind Tech Res Inst | 循序運算的伽羅瓦乘法架構與方法 |
| KR101818441B1 (ko) * | 2011-06-30 | 2018-01-16 | 삼성전자주식회사 | 데이터 처리 장치 및 이의 동작 방법 |
| RU2491571C2 (ru) * | 2011-08-19 | 2013-08-27 | Российская Федерация в лице Министерства промышленности и торговли РФ | Способ и устройство фазовой синхронизации |
| JP2014057203A (ja) * | 2012-09-12 | 2014-03-27 | Samsung Electronics Co Ltd | ガロア体演算回路、及びメモリ装置 |
| KR102021560B1 (ko) * | 2012-09-24 | 2019-09-16 | 삼성전자주식회사 | 오류 위치 탐색 회로, 그리고 그것을 포함하는 오류 검출 정정 회로 및 메모리 장치 |
| DE102016113126A1 (de) * | 2016-07-15 | 2018-01-18 | Tdk-Micronas Gmbh | Verfahren zur Berechnung der Phasenverschiebung oder Amplitude eines Drei-Phasen-Systems |
| US10235170B2 (en) * | 2016-09-30 | 2019-03-19 | International Business Machines Corporation | Decimal load immediate instruction |
| US10673662B2 (en) * | 2018-05-11 | 2020-06-02 | Keysight Technologies, Inc. | Methods and circuits for generating parallel pseudorandom binary sequences |
Family Cites Families (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS57194621A (en) * | 1981-05-26 | 1982-11-30 | Nec Corp | Random number generator |
| US4785410A (en) * | 1985-06-05 | 1988-11-15 | Clarion Co., Ltd. | Maximum length shift register sequences generator |
| US4776012A (en) * | 1987-04-17 | 1988-10-04 | Unisys Corporation | Method of jumping composite PN codes |
| US5210770A (en) * | 1991-09-27 | 1993-05-11 | Lockheed Missiles & Space Company, Inc. | Multiple-signal spread-spectrum transceiver |
| US5228054A (en) * | 1992-04-03 | 1993-07-13 | Qualcomm Incorporated | Power-of-two length pseudo-noise sequence generator with fast offset adjustment |
| US6404828B2 (en) * | 1997-03-12 | 2002-06-11 | Interdigital Technology Corporation | Multichannel decoder |
| US6009135A (en) * | 1997-10-10 | 1999-12-28 | Interdigtal Technology Corporation | Method and apparatus for generating a stream cipher |
| US6038577A (en) * | 1998-01-09 | 2000-03-14 | Dspc Israel Ltd. | Efficient way to produce a delayed version of a maximum length sequence using a division circuit |
-
1998
- 1998-03-18 JP JP6822698A patent/JP3556461B2/ja not_active Expired - Fee Related
- 1998-09-16 US US09/154,496 patent/US6636549B1/en not_active Expired - Fee Related
- 1998-09-17 DE DE1998620026 patent/DE69820026T2/de not_active Expired - Lifetime
- 1998-09-17 EP EP19980117649 patent/EP0949764B1/en not_active Expired - Lifetime
- 1998-11-26 CN CN98122809A patent/CN1120592C/zh not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| EP0949764A2 (en) | 1999-10-13 |
| CN1230058A (zh) | 1999-09-29 |
| DE69820026T2 (de) | 2004-08-26 |
| CN1120592C (zh) | 2003-09-03 |
| EP0949764B1 (en) | 2003-11-26 |
| JPH11265276A (ja) | 1999-09-28 |
| EP0949764A3 (en) | 2003-02-26 |
| DE69820026D1 (de) | 2004-01-08 |
| US6636549B1 (en) | 2003-10-21 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3556461B2 (ja) | Ｍ系列の位相シフト係数算出方式 | |
| CA2270827C (en) | Pseudorandom binary sequence block shifter | |
| JPH04250490A (ja) | ケーオス論に基づく暗号化システム | |
| WO2004112271A1 (ja) | 通信装置および通信方法 | |
| EP1489761B1 (en) | Method and apparatus for generating complex four-phase sequences for a cdma communication system | |
| JP2000200177A (ja) | デ―タの最大長シ―ケンスを発生する方法と装置 | |
| US6005888A (en) | Method for providing offset mask for pseudo-noise sequence generator | |
| US4890252A (en) | Long period pseudo random number sequence generator | |
| US8374289B2 (en) | Generation and detection of non-binary digital sequences | |
| US20040054703A1 (en) | Method and device for generating a pseudo-random sequence using a discrete logarithm | |
| CN100542029C (zh) | 伪随机序列发生装置 | |
| EP0878932B1 (en) | Circuit and method for arbitrarily shifting M-sequence | |
| Jin et al. | A new family of binary sequences with low correlation via elliptic curves | |
| JPH11224183A (ja) | 擬似乱数発生装置 | |
| Pandian et al. | Five decade evolution of feedback shift register: algorithms, architectures and applications | |
| US7317776B2 (en) | Efficient pseudo-noise sequence generation for spread spectrum applications | |
| US5835528A (en) | Method for fast determination of puesdo-noise code generator state | |
| JPWO2001067605A1 (ja) | 疑似ランダム信号生成方法及びその装置 | |
| JPH0577223B2 (ja) | ||
| WO2001067605A1 (fr) | Procede et dispositif de production d'un signal pseudo-aleatoire | |
| RU2212105C1 (ru) | Способ передачи дискретной информации в радиолинии с псевдослучайной перестройкой рабочей частоты | |
| JP3799355B2 (ja) | 通信システム、送信装置、受信装置、位相拡散符号生成装置、送信方法、受信方法、位相拡散符号生成方法、ならびに、プログラム | |
| RU2096918C1 (ru) | Способ шифрования двоичной информации и устройство для его осуществления | |
| US6910056B1 (en) | Method and apparatus for implementing a multi-step pseudo random sequence generator | |
| JPH1011268A (ja) | 擬似ランダム系列符号発生装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20040426 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20040511 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20040512 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080521 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090521 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090521 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100521 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100521 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110521 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120521 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130521 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20140521 Year of fee payment: 10 |
|
| LAPS | Cancellation because of no payment of annual fees |