Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
M-SEQUENCE GENERATING CIRCUIT, METHOD FOR PROVIDING THE SAME, AND RANDOM ERROR GENERATING APPARATUS USING M-SEQUENCE GENERATING CIRCUIT
Document Type and Number:
WIPO Patent Application WO/2009/063948
Kind Code:
A1
Abstract:
An M-sequence generating circuit, which is applicable to a random error generating apparatus, has a plurality of registers that are cascade connected and a plurality of exclusive-OR gates that feed bit data stored in the respective registers back to the respective registers each time a clock being inputted to the plurality of registers, and outputs the bit data from the registers in parallel manner. The M-sequence generating circuit includes a Galois field multiplication part, which is so configured as to include the plurality of exclusive-OR gates and arrange that the period of a cyclic group {(α1k), (α2k), (α3k),...,}, which is generated by using, as a generator (αk), an element (αk) obtained by exponentiating, with a specified exponent k where k is equal to or greater than two (k ≥ 2), the root α of one, which has a large number of terms, of a plurality of polynomials of Galois field GF (2m) having an order m where m is equal to the number of the registers (m = a positive integer equal to or greater than two), be within the longest period (2m - 1). The Galois field multiplication part receives, at one of its terminals, the bit data outputted in parallel manner from the registers each time the clock is inputted, while receiving, at the other of its terminals, the generator (αk), and then performs Galois field multiplication between each bit data and the generator (αk). The Galois field multiplication part then outputs the results of Galois field multiplications to the registers in parallel manner as the bit data fed back to the registers.

Inventors:
FURUYA TAKASHI (JP)
KURODA MASAHIRO (JP)
ISHIBE KAZUHIKO (JP)
Application Number:
PCT/JP2008/070702
Publication Date:
May 22, 2009
Filing Date:
November 13, 2008
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
ANRITSU CORP (JP)
FURUYA TAKASHI (JP)
KURODA MASAHIRO (JP)
ISHIBE KAZUHIKO (JP)
International Classes:
H04L1/24; H03K3/84; H03M13/01; H04L69/40
Domestic Patent References:
WO2008087948A12008-07-24
Foreign References:
JPH04117521A1992-04-17
JPS63221426A1988-09-14
JPH10197610A1998-07-31
Attorney, Agent or Firm:
SUZUYE, Takehiko et al. (1-12-9 Toranomon, Minato-ku, Tokyo 01, JP)
Download PDF:
Claims:
 縦続接続された複数個のレジスタと、該複数個のレジスタにそれぞれクロックが入力する毎に、各レジスタに記憶された各ビットデータを各レジスタにそれぞれ帰還させる複数個の排他的論理和ゲートとを有し、前記各レジスタから前記各ビットデータを並列に出力するM系列発生回路であって、
 前記複数個のレジスタの数m(m=2以上の正整数)を次数mとするガロア体GF(2m)の複数の多項式のうちの項数が多い多項式の一つの根αを2以上(k≧2)の指定べき乗値kでべき乗して得られる元(α k )を生成元(α k )として生成される巡回群{ (α 1k )、(α 2k )、(α 3k )、…、}の周期が最大長周期(2 m -1)以内であり、
 前記クロックが入力する毎に前記各レジスタから並列に出力される前記各ビットデータが一端に入力され、前記生成元(α k )が他端に入力され、前記各ビットデータと前記生成元(α k )との間のガロア体乗算を行い、そのガロア体乗算結果を前記各レジスタに対する各帰還ビットデータとして当該各レジスタへ並列に出力する、前記複数個の排他的論理和ゲートを含んで構成されるガロア体乗算部を備えたM系列発生回路。
 前記多項式の一つの根が、前記αでなく、eであるとき、該多項式の一つの根eを2以上(k≧2)の指定べき乗値kでべき乗して得られる元(e k )を生成元(e k )として生成される巡回群{(e 1k )、(e 2k )、(e 3k )、…、}の周期が最大長周期(2 m -1)以内であり、
 前記ガロア体乗算部は、前記クロックが入力する毎に前記各レジスタから並列に出力される前記各ビットデータが一端に入力され、前記生成元(e k )が他端に入力され、前記各ビットデータと前記生成元(e k )との間のガロア体乗算を行う請求項1に記載のM系列発生回路。
 縦続接続された複数個のレジスタと、該複数個のレジスタにそれぞれクロックが入力する毎に、各レジスタに記憶された各ビットデータを各レジスタにそれぞれ帰還させる複数個の排他的論理和ゲートとを有し、前記各レジスタから前記各ビットデータを並列に出力するM系列発生回路の提供方法であって、
 前記複数のレジスタの個数m(m=正整数)を3以上に選択設定するレジスタ個数選択ステップと、
 前記レジスタ個数選択ステップで選択された前記複数のレジスタの個数mを次数mとする2元の拡大ガロア体GF(2 m )における次数mの複数の原始多項式をデータベースから検索する原始多項式検索ステップと、
 前記原始多項式検索ステップで検索された前記複数の原始多項式のうち一つの原始多項式p(x)を選択する原始多項式選択ステップと、
 前記原始多項式選択ステップで選択された前記一つの原始多項式の根の一つである原始元αをデータベースから求める原始元算出ステップと、
 前記2元の拡大ガロア体GF(2 m )を原始元αのべき乗の級数で表現した場合の2乗以上(k≧2)の指定べき乗値α k を選択する指定べき乗値選択ステップと、
 前記指定べき乗値選択ステップで選択された指定基準べき乗値α k の前記縦続接続された複数レジスタの1番からm番までの各レジスタにそれぞれ帰還される各データ値にガロア体乗算する各指定基準べき乗値α k のべき乗値(α k 、α k+1 、α k+2 、…、α k+m-1 )を算出するべき乗値算出ステップと、
 前記縦続接続された複数レジスタに前記クロックがそれぞれ入力する毎に、前記各レジスタにそれぞれ帰還される前記各ビットデータの値に対して前記べき乗値(α k )をガロア体乗算するガロア体乗算部を設定するガロア体乗算部設定ステップと、
 前記べき乗値算出ステップで算出された前記各レジスタに対応するべき乗値(α k 、α k+1 、α k+2 、…、α k+m-1 )の前記各レジスタに対応する桁の値が「1」の場合に、該当レジスタからビットデータを前記桁が示すレジスタへ前記ガロア体乗算部を構成する前記複数個の排他的論理和ゲートを介して帰還させる帰還路を作成する帰還路作成ステップと
を備えたM系列発生回路の提供方法。
 縦続接続された複数個のレジスタと、該複数個のレジスタにそれぞれクロックが入力する毎に、各レジスタに記憶された各ビットデータを各レジスタにそれぞれ帰還させる複数個の排他的論理和ゲートとを有し、前記各レジスタから前記各ビットデータを並列に出力するM系列発生回路と、このM系列発生回路から前記クロックに同期して並列に出力された複数のビットデータが一端に入力され、この入力された複数のビットデータを一つの数値として取込み、この数値が他端に入力された指定誤り率に対応する基準値以下のときエラービットとなるランダムエラー信号を出力する比較器とを備えたランダムエラー発生装置であって、
 前記M系列発生回路は、
 前記複数個のレジスタの数m(m=2以上の正整数)を次数mとするガロア体GF(2m)の複数の多項式のうちの項数が多い多項式の一つの根αを2以上(k≧2)の指定べき乗値kでべき乗して得られる元(α k )を生成元(α k )として生成される巡回群{ (α 1k )、(α 2k )、(α 3k )、…、}の周期が最大長周期(2 m -1)以内であり、
 前記クロックが入力する毎に前記各レジスタから並列に出力される前記各ビットデータが一端に入力され、前記生成元(α k )が他端に入力され、前記各ビットデータと前記生成元(α k )との間のガロア体乗算を行い、そのガロア体乗算結果を前記各レジスタに対する各帰還ビットデータとして当該各レジスタへ並列に出力する、前記複数個の排他的論理和ゲートを含んで構成されるガロア体乗算部を備えたランダムエラー発生装置。
 前記クロックが入力する毎に前記各レジスタから並列に出力される複数のビットデータと前記生成元(α k )との間のガロア体乗算によって、各レジスタに記憶されたビットデータの前記複数個の排他的論理和ゲートを介した各レジスタに対する帰還路が定まる請求項4に記載のランダムエラー発生装置。
 前記M系列発生回路として複数のM系列発生回路が備えられるとともに、
 この複数のM系列発生回路における各M系列発生回路からクロックに同期して並列に出力された複数のビットデータがそれぞれ入力され、これらそれぞれ入力された複数のビットデータのデータ位置を入れ替えるデータ位置入替回路がさらに備えられ、
 このデータ位置入替回路でデータ位置が入れ替えられた複数のビットデータが前記比較器の一端に入力される請求項4に記載のランダムエラー発生装置。
 前記複数個のレジスタの数m(m=2以上の正整数)が、それぞれ互いに素の関係を有し、
 前記M系列発生回路として複数のM系列発生回路が備えられるとともに、
 この複数のM系列発生回路における各M系列発生回路からクロックに同期して並列に出力された複数のビットデータが全部のM系列発生回路のビットデータに亘って並列に前記比較器の一端に入力される請求項4に記載のランダムエラー発生装置。
 前記最大長周期(2 m -1)がメルセンヌ素数となるような、前記複数のレジスタの数mが素数に設定されており、前記選択された原始多項式の項数は前記レジスタの数mの半数程度に設定され、前記指定べき乗値α k のべき乗kは前記最大長周期(2 m -1)の1/3程度に設定されている請求項4に記載のランダムエラー発生装置。
 前記各レジスタに擬似乱数値を初期設定する初期設定部さらにを備えた請求項4に記載のランダムエラー発生装置。
Description:
M系列発生回路及びその提供方法 並びにM系列発生回路を用いるランダムエラ 発生装置

 本発明はM系列発生回路(M-sequence generator) びその提供方法並びにM系列発生回路を用い るランダムエラー発生装置に係り、特に、指 定された誤り率(エラーレート)を有し、かつ のエラー分布が光通信や電気通信で発生す 雑音等に起因するエラー分布に近似するラ ダムエラー信号を出力するランダムエラー 生装置及びそれに適用可能なM系列発生回路 並びにその提供方法に関する。

 一般の電気信号ケーブルを用いたデジタ 通信網や光ファイバケーブルを用いた光通 網に組込まれた各種通信機器に対する各種 験を実施する試験装置においては、試験対 の通信機器に対して、この通信機器の実際 使用状況に合致した試験信号を入力して、 の通信機器の応答動作を評価する。

 このような通信機器に対する評価試験の つの種類として、測定対象の通信機器に送 する試験信号として、実際の使用状況に合 した故意にエラーを含ませた試験信号を採 する。

 そして、通信機器が、試験信号に含まれ エラーの発生率(誤り率)Eがどの程度まで正 に動作するかを評価する。

 この試験信号にランダムにエラーを含ま るランダムエラー発生装置の一例が特許文 1に提案されている。

 この特許文献1には、ランダムエラー発生 装置としての詳細構成が明確に記載されてい ないにもかかわらず、それに添付されている 明細書、図面の記載から、このランダムエラ ー発生装置は図15、図16に示すような構成を しているものと推定される。

 M(最大長周期:maximum length periodic sequence) 列発生回路1は、図16にその1例を示すように 、直列接続されたm段のレジスタ2と1個又は複 数の排他的論理和ゲート3とで構成されてい 。

 そして、外部のクロック回路4から各レジス タ2にクロック(CLK)が印加されると、出力端子 5から(2 m -1)の周期を有するデジタル直列信号であるPN( 擬似雑音:pseudo noise)信号が出力される。

 また、クロック(CLK)が入力される毎に、m の各レジスタ2に記憶されている各ビットデ ータが並列に出力される。

 M系列発生回路1から並列に出力された各 ットデータは、比較器6の一方の入力端子(X 子)に印加される。

 この比較器6の他方の入力端子(Y端子)には 、基準値設定回路7で操作者により入力され 並列mビットの基準値が入力される。

 比較器6は、一方の入力端子(X端子)に印加 された並列m個のビットデータを一つの数値A して取込むとともに、他方の入力端子(Y端 )に印加された並列mビットの基準値Bも一つ 数値として取込む。

 そして、比較器6は、一方の入力端子(X端 )から取込んだ数値Aが他方の入力端子(Y端子 )から取込んだ基準値B以下の場合、エラービ トとなるラムダムエラー信号aを出力する。

 基準値Bは、このランダムエラー発生装置 から出力されるランダムエラー信号aのエラ 発生率(誤り率)Eに対応して設定される。

 例えば、誤り率Eが0.004(0.4%)で、X端子の取 り得る値Aが1~1000の場合においては、基準値B 「4」に設定される。

 この場合、数値Aが4以下になる確率は4/1000 なるので、誤り率Eが0.004のラムダムエラー 号aが得られる。

特開2002-330192号公報

 しかしながら、図15、図16に示すランダム エラー発生装置においても、まだ解消すべき 次のような課題がある。

 すなわち、例えば、図15に示す直列接続 れたm個のレジスタ2が組込まれたM系列発生 路1において、このM系列発生回路1からクロ クに同期して出力端子5から順次出力される ータの系列(データ列)は、排他的論理和ゲ ト3の設置数、設置位置に応じて変化する。

 そして、出力される系列(データ列)にお る同一データ列の繰り返しを示す周期も変 する。

 そして、最大長周期(2 m -1)が得られる系列も複数存在する。

 すなわち、周知のように、M(最大長周期)系 は、2元の拡大ガロア体GF(Galois Field)(2 m )における零元「0」を除く全ての元(element)が 始元(primitive element)αをべき乗して得られる 下記の周期系列で示される。

 α 0 、α 1 、α 2 、α 3 、…、
 ここで、原始元αとは、ガロア体GF(p m )の零元(zero element)「0」を除く全ての元がα べき乗によって生成される特別な元を示す

 ガロア素体(Galois prime fieled)GF(p)を拡大して 得られるガロア体を拡大ガロア体GF(p m )と言う。但し、pは素数、mは2以上の正整数 ある。ガロア素体GF(p)は拡大ガロア体GF(p m )の基礎体と言われている。

 ガロア基礎体GF(p)の元を係数とする多項 を「ガロア基礎体GF(p)上の多項式」と呼ぶ。

 この多項式は、ガロア基礎体GF(p)がGF(2)の場 合の元は[0,1]であるから、ガロア基礎体GF(2) の前記元(b 0 、b 1 、b 2 、b 3 、…b m )を係数とするm次の多項式
 q(x)=b m x m +b m-1 x m-1 +、…、+b 1 x+b 0
で表せる
したがって、この多項式は、(2 m+1 )個存在する。

 ガロア基礎体GF(2)上のm次多項式q(x)の根と は、q(x)=0を満たすxである。

 多項式q(x)がガロア基礎体GF(p)の元とする を持たない場合、その多項式q(x)はガロア基 礎体GF(p)上で既約(irreducible)であると言う。

 あるいは、多項式q(x)はガロア基礎体GF(p) の既約多項式であると言う。

 例えば、ガロア基礎体GF(p)がGF(2)の場合、
 多項式q(x)=x 3 +x+1
は、ガロア基礎体GF(p)上の既約多項式である

 これは、ガロア基礎体GF(2)の元である「0 と「1」を多項式q(x)に代入して容易に確か ることができる。

 例えば、x=0、x=1を上式に代入すると、
 q(0)=0 3 +0+1≠0、
 q(1)=1 3 +1+1=1≠0
となるから、多項式q(x)の根は、「0」でも、 1」でもない。

 よって、この場合の多項式q(x)はガロア体 GF(2)の上で既約多項式である。

 そして、この既約多項式の中の最大長周期( 2 m -1)を有す多項式を原始多頂式p(x)と定義して る。

 多頂式が既約多項式p(x)であるためには、 その多項式の項数は奇数でなければならない ことは容易に証明できる。

 そして、図9、図10に示すように、次数mが高 くなると、この最大長周期(2 m -1)が得られる原始多項式(primitive polynomial)p(x) も複数存在する。

 そして、原始多項式p(x)の根である元が前 述した原始元αとなる。

 しかし、従来のM系列発生回路1において 、回路構成を簡素化するために、最小の項 (3項又は5項)の原始多項式p(x)を採用すること が多い。

 図16に示すM系列発生回路1においては、下 記に示すように、採用された原始多項式p(x) 3項式(trinomial)で構成されている。

 p(x)=x 10 +x 3 +1
 専門書や文献等に記載されている原始多項 は、通常、3項式または5項式(pentanomial)であ ことが多い。

 しかし、このようなM系列発生回路1によ て生成される疑似乱数の確率分布は前述し 自然に発生する雑音の発生確率分布に比較 て大きな差異があり、M系列発生回路として 記の(a)、(b)、(c)に示す特性的に改良すべき がある。

 (a) シフトレジスタによって構成されるM 列発生回路1では1クロック(CLK)の入力に対し てシフトレジスタの内容が元の内容を左又は 右に1 ビット分シフトしただけのものになる 確率が高いので、エラービットが生じると、 同一エラービットが複数クロックに亘って、 継続する可能性が高い。

 特に、これは生成多項式として項数の少 い原始多頂式p(x)を選んでいる場合に、発生 しやすい問題である。

 例えば、図10に、従来のM系列発生回路1に 採用されている、次数(段数)m=3から次数m=32ま での原始多項式p(x)の例を示す。

 この図10における各次数mにおける原始多 式p(x)は、前述した、図9で示す該当次数mに ける複数の原始多頂式p(x)の中から、項数が 最小である原始多項式p(x)である。

 ところで、項数が奇数の最小項数の原始 項式は、図10に示すように、3項式であるが 任意の次数(段数)mに対して3項式の原始多頂 式p(x)が必ず存在するとは言えない。

 例えば、次数(段数)m=8の場合、最小項数 原始多項式p(x)は、下記のような5項式である 。

 p(x)=x 8 +x 7 +x 2 +x+1
 いずれにせよ、項数が最小である原始多項 p(x)を選ぶようにしている。

 このように、採用する原始多項式p(x)の項 数が少ないと、例えば、図16に示すM系列発生 回路1における先頭のレジスタ2へ後段の各レ スタ2から排他的論理和ゲート3を介して帰 されるビットデータの数が少なくなる。

 その結果、このM系列発生回路1からクロッ (CLK)に同期して順次出力される最大長周期(2 m -1)のビットデータ列に、「1」又は「0」の同 値が連続する確率が高くなる。

 したがって、このようなM系列発生回路1 は、目標とするよりランダムなエラー分布 得られない。

 (b) M(最大長周期)系列発生回路1において 次数(段数)mを大きくする、すなわち、周期 のものを長くすることだけでは、このM(最 長周期)系列発生回路1で生成される疑似乱数 の確率分布を前述した自然に発生する雑音の 発生確率分布に近づけることはできない。

 確かに、最大長周期系列の周期を長くす ことは、確率分布の特性を改善するための 要条件ではある。

 しかるに、周期がある値を越えると、長 期化の発生確率分布の特性向上に対する寄 率は低下する。

 例えば、127段(m=127)のシフトレジスタを用い たM系列発生回路1においては、周期(2 127 -1)すなわち、略1.7×10 38 の周期系列が得られる。

 この周期略1.7×10 38 は事実上無限長に等しい。

 しかし、実際の試験測定に際しては比較 短い試験時間においても、確率分布特性が れていることが要求される。

 このような要求に対しては周期系列の周 を長くすることだけでは対応できないこと 明らかである。

 このように、従来のM系列発生回路1、及 ランダムエラー発生装置においては、回路 模を最小化でき、かつ高速動作が可能であ 長所を有する反面、出力されるランダムエ ー信号の確率分布特性及び確率過程特性は だ向上の余地がある。

 (c) 図16に示すM系列発生回路1においては このM系列発生回路1をコンピュータのアプ ケーションプログラム上で実現する場合に いては、各レジスタ2に入出力される各デー を前述した原始多項式p(x)を含むガロア体乗 算で求めている。

 しかるに、この場合、クロック回路4から 出力される1クロック(CLK)のみで、このガロア 体乗算を実施することができない。

 すなわち、図16に示すように、10段(次数m=10) のシフトレジスタ2からなるM系列発生回路1に おいては、各レジスタ2はクロックに応じて 段のレジスタ2のデータを取込むので、クロ ク回路4から出力される1クロック(CLK)のみで は、図10における次数m=10における3項式の
 原始多項式p(x)=x 10 +x 3 +1
のガロア体乗算が完結しない。

 図16においては、レジスタ2の段数m(=10)分 10クロック(CLK)が必要である。

 したがって、図16のM系列発生回路1を含む ランダムエラー発生装置の高速性能が低下す ることになる。

 本発明の目的は、これらの問題を解決し 使用する回路規模を過度に大きく設定する となく、光通信や電気通信において発生す 雑音等に起因するエラー分布に近似するよ 一層ランダムなランダムエラー信号を出力 るランダムエラー発生装置、このランダム ラー発生装置に適用可能なM系列発生回路及 びこのM系列発生回路の提供方法を提供する とである。

 上記目的を達成するために、本発明の第1の 態様によると、
 縦続接続された複数個のレジスタ(12)と、該 複数個のレジスタ(12)にそれぞれクロック(CLK) が入力する毎に、各レジスタ(12)に記憶され 各ビットデータを各レジスタ(12)にそれぞれ 還させる複数個の排他的論理和ゲート(17)と を有し、前記各レジスタ(12)から前記各ビッ データを並列に出力するM系列発生回路(11)で あって、
 前記複数個のレジスタ(12)の数m(m=2以上の正 数)を次数mとするガロア体GF(2 m )の複数の多項式のうちの項数が多い多項式 一つの根αを2以上(k≧2)の指定べき乗値kでべ き乗して得られる元(α k )を生成元(α k )として生成される巡回群{(α 1k )、(α 2k )、(α 3k )、…、}の周期が最大長周期(2 m -1)以内であり、
 前記クロック(CLK)が入力する毎に前記各レ スタから並列に出力される前記各ビットデ タが一端に入力され、前記生成元(α k )が他端に入力され、前記各ビットデータと 記生成元(α k )との間のガロア体乗算を行い、そのガロア 乗算結果を前記各レジスタ(12)に対する各帰 ビットデータとして当該各レジスタ(12)へ並 列に出力する、前記複数個の排他的論理和ゲ ート(17)を含んで構成されるガロア体乗算部(1 3)を備え
たことを特徴とするM系列発生回路(11)が提供 れる。

 このように構成された複数m(m=2以上の正整 )個のレジスタ(12)を有するM系列発生回路(11) おいては、最大長周期(2 m -1)を実現できる次数mの2元の拡大ガロア体GF(2 m )における複数の原始多項式p(x)のうちの項数 多い原始多項式p(x)を採用している。

 前述したように、従来のM系列発生回路(1) に採用される原始多項式p(x)は、項数が少な 原始多項式p(x)が採用されている。

 しかし、本発明においては、項数が多い 始多項式p(x)を採用している。

 両者を比較すると、最大長周期(2 m -1)が等しい条件においては、項数が多い原始 多項式p(x)ほど、M系列発生回路(11)における各 レジスタ(12)へ自己を含む各レジスタ(12)から 他的論理和ゲート(17)を介して帰還されるビ ットデータの数が多くなる。

 その結果、このM系列発生回路(11)からクロ ク(CLK)に同期して順次出力される最大長周期 (2 m -1)のビットデータ列に、「1」又は「0」の同 値が連続する確率が低くなる。

 さらに、本発明においては、クロック(CLK) 入力する毎に、ガロア体乗算部(13)で、各レ スタ(12)から並列に出力される複数のビット データと、生成元(α k )との間でガロア体乗算を行う。

 また、1番目からm番目までの1つ(j番目)のレ スタ(12)に自己を含む各レジスタ(12)から帰 される各ビットデータに対してガロア体乗 される各べき乗値は、従来の原始元αのべき 乗値(α 1 、α 2 、…、α m )ではなくて、原始元αに対する指定べき乗値 α k の各べき乗値(α k 、α k+1 、α k+2 、…、α k+m-1 )である。

 したがって、1番目からm番目までの各レ スタ(12)に入力されるビットデータ値がより 層ランダムになる。

 上記目的を達成するために、本発明の第2の 態様によると、
 前記多項式の一つの根が、前記αでなく、e あるとき、該多項式の一つの根eを2以上(k≧ 2)の指定べき乗値kでべき乗して得られる元(e k )を生成元(e k )として生成される巡回群{(e 1k )、(e 2k )、(e 3k )、…、}の周期が最大長周期 (2 m -1)以内であり、
 前記ガロア体乗算部(13)は、前記クロック(CL K)が入力する毎に前記各レジスタ(12)から並列 に出力される前記各ビットデータが一端に入 力され、前記生成元(e k )が他端に入力され、前記各ビットデータと 記生成元(e k )との間のガロア体乗算を行うことを特徴と る第1の態様に従うM系列発生回路(11)が提供 れる。

 このように構成されたM系列発生回路(11) おいては、採用する多項式(生成多項式)は原 始多項式p(x)に限定せずに、一つの多項式を 成多項式として採用する。

 したがって、実際のM系列発生回路から出力 されるビットデータの周期が最大長周期(2 m -1)に、必ずしも一致するとは限らない。

 しかしながら、このM系列発生回路(11)に いては、使用するレジスタ(12)の数mを任意に 設定できる設計の自由度を確保できる。

 また、上記目的を達成するために、本発明 第3の態様によると、
 縦続接続された複数個のレジスタ(12)と、該 複数個のレジスタにそれぞれクロック(CLK)が 力する毎に、各レジスタ(12)に記憶された各 ビットデータを各レジスタ(12)にそれぞれ帰 させる複数個の排他的論理和ゲート(17)とを し、前記各レジスタ(12)から前記各ビットデ ータを並列に出力するM系列発生回路(11)の提 方法であって、
 前記複数のレジスタ(12)の個数m(m=正整数)を3 以上に選択設定するレジスタ個数選択ステッ プと、
 前記レジスタ個数選択ステップで選択され 前記複数のレジスタ(12)の個数mを次数mとす 2元の拡大ガロア体GF(2 m )における次数mの複数の原始多項式をデータ ースから検索する原始多項式検索ステップ 、
 前記原始多項式検索ステップで検索された 記複数の原始多項式のうち一つの原始多項 p(x)を選択する原始多項式選択ステップと、
 前記原始多項式選択ステップで選択された 記一つの原始多項式の根の一つである原始 αをデータベースから求める原始元算出ス ップと、
 前記2元の拡大ガロア体GF(2 m )を原始元αのべき乗の級数で表現した場合の 2乗以上(k≧2)の指定べき乗値α k を選択する指定べき乗値選択ステップと、
 前記指定べき乗値選択ステップで選択され 指定基準べき乗値α k の前記縦続接続された複数レジスタ(12)の1番 らm番までの各レジスタ(12)にそれぞれ帰還 れる各データ値にガロア体乗算する各指定 準べき乗値α k のべき乗値(α k 、α k+1 、α k+2 、…、α k+m-1 )を算出するべき乗値算出ステップと、
 前記縦続接続された複数レジスタ(12)に前記 クロック(CLK)がそれぞれ入力する毎に、前記 レジスタ(12)にそれぞれ帰還される前記各ビ ットデータの値に対して前記べき乗値(α k )をガロア体乗算するガロア体乗算部(13)を設 するガロア体乗算部設定ステップと、
 前記べき乗値算出ステップで算出された前 各レジスタ(12)に対応するべき乗値(α k 、α k+1 、α k+2 、…、α k+m-1 )の前記各レジスタ(12)に対応する桁の値が「1 」の場合に、該当レジスタ(12)からビットデ タを前記桁が示すレジスタ(12)へガロア体乗 部(13)を構成する前記複数個の排他的論理和 ゲート(17)を介して帰還させる帰還路を作成 る帰還路作成ステップと
を備えたことを特徴とするM系列発生回路の 供方法が提供される。

 このように構成されたM系列発生回路の提 供方法においては、上述したM系列発生回路(1 1)とほぼ同じ作用効果を奏することが可能で る。

 さらに、この発明のM系列発生回路の提供方 法においては、各レジスタ(12)のデータと指 べき乗値(α k )をガロア体乗算するガロア体乗算部(13)にお るガロア体乗算の定義により、図12の(a)、(b )に示すように、2元のガロア体GF(2)において 、加算は実計算の排他的論理和(XOR)に相当し ており、乗算は実計算の論理積(AND)に相当す 。

 したがって、各べき乗値(α k 、α k+1 、α k+2 、…、α k+m-1 )の各レジスタ(12)に対応する桁の値が「1」の 場合にのみ、該当レジスタ(12)からビットデ タを桁が示すレジスタ(12)へガロア体乗算部( 13)を構成する前記複数個の排他的論理和ゲー ト(17)を介して帰還させる帰還路を形成すれ よい。

 また、上記目的を達成するために、本発明 第4の態様によると、
 縦続接続された複数個のレジスタ(12)と、該 複数個のレジスタ(12)にそれぞれクロック(CLK) が入力する毎に、各レジスタ(12)に記憶され 各ビットデータを各レジスタ(12)にそれぞれ 還させる複数個の排他的論理和ゲート(17)と を有し、前記各レジスタ(12)から前記各ビッ データを並列に出力するM系列発生回路(11)と 、このM系列発生回路(11)から前記クロック(CLK )に同期して並列に出力された複数のビット ータが一端に入力され、この入力された複 のビットデータを一つの数値として取込み この数値が他端に入力された指定誤り率に 応する基準値以下のときエラービットとな ランダムエラー信号を出力する比較器(6)と 備えたランダムエラー発生装置であって、
 前記M系列発生回路(11)は、
 前記複数個のレジスタ(12)の数m(m=2以上の正 数)を次数mとするガロア体GF(2m)の複数の多 式のうちの項数が多い多項式の一つの根αを 2以上(k≧2)の指定べき乗値kでべき乗して得ら れる元(α k )を生成元(α k )として生成される巡回群{(α 1k )、(α 2k )、(α 3k )、…、}の周期が最大長周期(2 m -1)以内であり、
 前記クロック(CLK)が入力する毎に前記各レ スタ(12)から並列に出力される前記各ビット ータが一端に入力され、前記生成元(α k )が他端に入力され、前記各ビットデータと 記生成元(α k )との間のガロア体乗算を行い、そのガロア 乗算結果を前記各レジスタ(12)に対する各帰 ビットデータとして当該各レジスタ(12)へ並 列に出力する、前記複数個の排他的論理和ゲ ート(17)を含んで構成されるガロア体乗算部(1 3)を備え
たことを特徴とするランダムエラー発生装置 が提供される。

 このように構成されたランダムエラー発生 置に組込まれたm個のレジスタを有するM系 発生回路(11)においては、最大長周期(2 m -1)が実現できる次数mの2元の拡大ガロア体GF(2 m )における複数の原始多項式p(x)のうちの項数 多い原始多項式p(x)を採用している。

 前述したように、従来のM系列発生回路(1) に採用される原始多項式p(x)は、項数が少な 原始多項式p(x)が採用されている。

 しかし、本発明においては、項数の多い 始多項式p(x)が採用されている。

 両者を比較すると、最大長周期(2 m -1)が等しい条件においては、項数が多い原始 多項式p(x)ほど、M系列発生回路における各レ スタ(12)へ自己を含む各レジスタ(12)から前 複数個の排他的論理和ゲート(17)を介して帰 されるビットデータの数が多くなる。

 その結果、このM系列発生回路(11)からクロ ク(CLK)に同期して順次出力される最大長周期 (2 m -1)のビットデータ列に、「1」又は「0」の同 値が連続する確率が低くなる。

 したがって、本発明においては、目標と るよりランダムなエラー分布が得られる。

 さらに、本発明においては、ガロア体乗算 (13)で、クロック(CLK)が入力する毎に、各レ スタ(12)から並列に出力される複数のビット データと、生成元(α k )との間でガロア体乗算を行う。

 また、本発明のガロア体乗算部(13)において 、1番目からm番目までの1つ(j番目)のレジスタ (12)に自己を含む各レジスタ(12)から帰還され 各ビットデータに対してガロア体乗算され 各べき乗値は、従来の原始元αのべき乗値( 1 、α 2 、…、α m )ではなくて、原始元αに対する指定べき乗値 α k の各べき乗値(α k 、α k+1 、α k+2 、…、α k+m-1 )である。

 したがって、本発明においては、1番目か らm番目までの各レジスタ(12)に入力されるビ トデータ値がより一層ランダムになる。

 このような構成のM系列発生回路(11)が組 まれたランダムエラー発生装置においては M系列発生回路(11)は、クロック(CLK)が入力さ る毎に、M系列発生回路(11)のm個の各レジス (12)に記憶されている各ビットデータを並列 に出力する。

 そして、このM系列発生回路(11)から並列 出力された各ビットデータは比較器(6)の一 の入力端子に印加される。

 この比較器(6)の他方の入力端子には基準 が入力される。

 これにより、比較器(6)は、一方の入力端 から取込んだ各ビットデータの数値が他方 入力端子から取込んだ基準値以下の場合、 ラービットとなるラムダムエラー信号を出 する。

 したがって、このランダムエラー発生装 は指定された誤り率を有した、より一層ラ ダムなラムダムエラー信号を出力する。

 また、上記目的を達成するために、本発明 第5の態様によると、
 前記クロック(CLK)が入力する毎に並列に出 される複数のビットデータと前記生成元(α k )との間のガロア体乗算によって、各レジス (12)に記憶されたビットデータの前記複数個 排他的論理和ゲート(17)を介した各レジスタ に対する帰還路が定まる
ことを特徴とする第4の態様に従うランダム ラー発生装置が提供される。

 また、上記目的を達成するために、本発明 第6の態様によると、
 前記M系列発生回路(11)として複数のM系列発 回路(23 1 、23 2 、…、23 n )が備えられるとともに、
 この複数のM系列発生回路(23 1 、23 2 、…、23 n )における各M系列発生回路(23 1 、23 2 、…、23 n )からクロック(CLK)に同期して並列に出力され た複数のビットデータがそれぞれ入力され、 これらそれぞれ入力された複数のビットデー タのデータ位置を入れ替えるデータ位置入替 回路(26)がさらに備えられ、
 このデータ位置入替回路(26)でデータ位置が 入れ替えられた複数のビットデータが前記比 較器(6)の一端に入力される
ことを特徴とする第4の態様に従うランダム ラー発生装置が提供される。

 このように構成されたランダムエラー発生 置においては、複数のM系列発生回路(23 1 、23 2 、…、23 n )が組込まれており、各M系列発生回路(23 1 、23 2 、…、23 n )からクロック(CLK)に同期して並列に出力され た複数のビットデータは、データ位置入替回 路(26)によって、そのデータ位置が全部のM系 発生回路(23 1 、23 2 、…、23 n )のビットデータに亘って入替えられた後、 較器(6)の一端に入力される。

 したがって、クロック(CLK)に同期して、 較器(6)の一端に入力される並列のビットデ タからなる数値が先のクロック(CLK)における 数値と同一値になることをより確実に防止で きる。

 さらに、複数のM系列発生回路(23 1 、23 2 、…、23 n )で先の発明の1台のM系列発生回路(11)とほぼ 等の周期を実現している。

 この場合、複数のM系列発生回路(23 1 、23 2 、…、23 n )を備えていることにより、ほぼ同等の周期 得るための回路構成が簡素化される。

 上記目的を達成するために、本発明の第7の 態様によると、
 前記複数個のレジスタ(12)の数m(m=2以上の正 数)が、それぞれ互いに素の関係を有し、
 前記M系列発生回路(11)として複数のM系列発 回路(23 1 、23 2 、…、23 n )が備えられるとともに、
 この複数のM系列発生回路(23 1 、23 2 、…、23 n )における各M系列発生回路(23 1 、23 2 、…、23 n )からクロック(CLK)に同期して並列に出力され た複数のビットデータが全部のM系列発生回 (23 1 、23 2 、…、23 n )のビットデータに亘って並列に前記比較器(6 )の一端に入力される
ことを特徴とする第4の態様に従うランダム ラー発生装置が提供される。

 このように構成されたランダムエラー発生 置においては、上述した発明のランダムエ ー発生装置におけるデータ位置入替回路(26) が除去されており、各M系列発生回路(23 1 、23 2 、…、23 n )から出力された複数のビットデータがその ま比較器(6)の一端に全部のM系列発生回路(23 1 、23 2 、…、23 n )に亘って並列に入力される。

 この場合、各M系列発生回路(23 1 、23 2 、…、23 n )の各レジスタ(12)の個数mは互いに素の関係に 維持されているので、各M系列発生回路(23 1 、23 2 、…、23 n )から出力される複数のビットデータのデー 列で形成される符号列の周期が互いに異な ので、比較器(6)の一端に入力される全部のM 列発生回路(23 1 、23 2 、…、23 n )に亘る複数のビットデータのデータ列で形 される符号列の周期を長くできる。

 上記目的を達成するために、本発明の第8の 態様によると、
 前記最大長周期(2 m -1)がメルセンヌ素数となるような、前記複数 のレジスタ(12)の数mが素数に設定されており 前記選択された原始多項式の項数は前記レ スタ(12)の数mの半数程度に設定され、前記 定べき乗値α k のべき乗kは前記最大長周期(2 m -1)の1/3程度に設定されていることを特徴とす る第4の態様に従うランダムエラー発生装置 提供される。

 このようにレジスタ数mが、素数であるとと もに、最大長周期(2 m -1)が素数であるメルセンヌ素数になる値に設 定される。

 図9は、各レジスタ数m(次数m)と、メルセ ヌ素数との関係を示している。

 「素数」と「メルセンヌ素数」との両方を たすレジスタ数m(次数m)は
  「2、3、5、7、13、17、19、31、61、89、107、1 27」
の合計12個存在する。

 この12個のうちの1つのレジスタ数m(次数m)を 選択することによって、周期が前記最大長周 期(2 m -1)である原始多項式p(x)を確実に選択できる

 さらに、項数がレジスタ数mの半数程度の 原始多項式p(x)を選択することによって、良 なランダム特性を維持した状態で、回路構 を簡素化できる。

 上記目的を達成するために、本発明の第9の 態様によると、
 前記各レジスタ(12)に擬似乱数値を初期設定 する初期設定部(14)さらにを備えたことを特 とする第4の態様に従うランダムエラー発生 置が提供される。

 このように、各レジスタ(12)に擬似乱数値 を初期設定することによって、各レジスタ(12 )から並列に出力されるビットデータのラン ム性をより一層向上できる。

 以上のようにして、本発明のランダムエ ー発生装置、M系列発生回路、及びM系列発 回路の提供方法においては、使用する回路 模を過度に大きく設定することなく、光通 や電気通信において発生する雑音等に起因 るエラー分布に近似するより一層ランダム ランダムエラーを実現できる。

図1は、本発明の第1実施形態に係わるM 列発生回路が組込まれるランダムエラー発 装置の概略構成を説明するために示すブロ ク図である。 図2は、図1のランダムエラー発生装置 組込まれるM系列発生回路の概略回路を説明 るために示すブロック図である。 図3は、図1のランダムエラー発生装置 組込まれるM系列発生回路の動作原理を説明 るために示すブロック図である。 図4は、図1のランダムエラー発生装置に組込 れるM系列発生回路を提供するための指定べ き乗値(α k )のデータ一覧テーブルを示す図である。 図5の(a),(b)は、図1のランダムエラー発生装置 に組込まれるM系列発生回路を提供するため 指定べき乗値(α k )のデータ一覧テーブル及び選択された各レ スタの一覧テーブルを示す図である。 図6は、図1のランダムエラー発生装置 組込まれるM系列発生回路として提供されたM 系列発生回路の一部を示す実際の回路図であ る。 図7は、図1のランダムエラー発生装置 組込まれるM系列発生回路として提供されたM 系列発生回路の一部を示す実際の回路図であ る。 図8は、本発明の第2実施形態に係わるM 列発生回路の提供方法を説明するために示 フローチャートである。 図9は、図8のM系列発生回路の提供方法 用いられる2元の拡大ガロア体GF(2m)における 次数mと原始多項式数との関係を示す図であ 。 図10は、図8のM系列発生回路の提供方 で用いられる2元の拡大ガロア体GF(2m)におけ 各次数mの原始多項式を示す図である。 図11は、図8のM系列発生回路の提供方 で用いられる2元の拡大ガロア体GF(2m)におけ 各次数mの原始多項式を示す図 図12の(a),(b)は、図8のM系列発生回路の 供方法で用いられる2元のガロア体における 加算と乗算の定義を示す図である。 図13は、本発明の第4実施形態に係わる ランダムエラー発生装置の概略構成を説明す るために示すブロック図である。 図14は、本発明の第5実施形態に係わる ランダムエラー発生装置の概略構成を説明す るために示すブロック図である。 図15は、従来のランダムエラー発生装 の概略構成を説明するために示すブロック である。 図16は、従来のランダムエラー発生装 に組込まれるM系列発生回路の概略構成を説 明するために示すブロック図である。

 以下、本発明の各実施形態を図面を用い 説明する。

  (第1実施形態)
 図1は本発明の第1実施形態に係わるM系列発 回路が組込まれたランダムエラー発生装置 概略構成図である。

 なお、図1において、図15に示した従来の ンダムエラー発生装置と同一部分には同一 号を付して重複する説明は省略する。

 M(最大長周期)系列発生回路11は、複数m個( m:2以上の正整数)のレジスタ12とガロア体乗算 部13とで構成されている。

 初期値設定部14は、このM系列発生回路11 起動時に0番から(m-1)番までの各レジスタ12に 擬似乱数を構成する各1ビットの非零の初期 を設定する。

 指定べき乗値設定部15は、このM系列発生回 11で採用されている次数mの原始多項式p(x)の 根の一つである原始元αを指定べき乗kした値 である指定べき乗値α k をガロア体乗算部13の一端に印加している。

 このkの値と2 m -1の値は互いに素となっている。

 この指定べき乗値α k は2進のmビット構成である。

 ガロア体乗算部13は、クロック回路16からク ロック(CLK)が入力される毎に、各レジスタ12 ら出力されるビットデータ値(=変数)に対し 指定べき乗値設定部15から印加されている指 定べき乗値(α k )(=定数)をガロア体乗算して、ガロア体乗算 果を各レジスタ12に書込む。

 また、このM系列発生回路11は、クロック 路16からクロック(CLK)が入力される毎に、m の各レジスタ12に記憶されている各ビットデ ータを並列に出力する。

 M系列発生回路11から並列に出力された各 ットデータは、比較器6の一方の入力端子(X 子)に印加される。

 この比較器6の他方の入力端子(Y端子)には 、基準値設定回路7で操作者によって操作入 された並列mビットの基準値が入力される。

 比較器6は、一方の入力端子(X端子)に印加 された並列m個のビットデータを一つの数値A して取込むとともに、他方の入力端子(Y端 )に印加された並列mビットの基準値Bも一つ 数値として取込む。

 そして、比較器6は、一方の入力端子(X端 )から取込んだ数値Aが他方の入力端子(Y端子 )から取込んだ基準値B以下の場合、エラービ トとなるラムダムエラー信号aを出力する。

 基準値Bは、このランダムエラー発生装置 から出力されるランダムエラー信号aのエラ 発生率(誤り率)Eに対応して設定される。

 したがって、このランダムエラー発生装 から指定された誤り率を有するランダムエ ー信号aが得られる。

 このように構成されたランダムエラー発 装置に組込まれたM系列発生回路11のガロア 乗算部13を実際の回路素子に置き換えると M系列発生回路11は図2に示す構成となる。

 すなわち、M系列発生回路11は、各レジス 12にクロック(CLK)が入力する毎に、各レジス タ12に記憶された各ビットデータを自己を含 各レジスタ12に複数個の排他的論理和ゲー 17を介して帰還させる。

 次に、上述したガロア体乗算部13におけ ガロア体乗算で図2に示すm個のレジスタ12及 複数個の排他的論理和ゲート17が組込まれ M系列発生回路11を実現する具体的計算手順 図3を用いて説明する。

 各レジスタ12にクロック(CLK)が入力される毎 に、各レジスタ12から出力されるビットデー 値をv(x)(=変数)とし、指定べき乗値設定部15 ら印加されている指定べき乗値(α k )をc(x)(=定数)とし、各レジスタ12に帰還され ビットデータをガロア体乗算の乗算結果y(x) する。

 この場合の各値v(x)、c(x)、y(x)を多項式で すと下式となる。

 v(x)=v m-1 x m-1 +v m-2 x m-2 +…+v 1 x+v 0
 c(x)=c m-1 x m-1 +c m-2 x m-2 +…+c 1 x+c 0
 y(x)=y m-1 x m-1 +y m-2 x m-2 +…+y 1 x+y 0
 y(x)=c(x)・v(x)
 ここで、全ての多項式の各次の係数は基礎 ロア体GF(2)の元であり、c(x)は定数であるの 、基礎ガロア体GF(2)上において、下記係数 は既知である。

 c m-1 ,c m-2 ,…+c 1 ,c 0
したがって、
 x 0 c(x),x 1 c(x),x 2 c(x),x 3 c(x),…、x m-1 c(x)
を予め計算して、求めておくことができる。

 この実施形態における生成多項式の各元は 項式表現が可能であるので、c(x)は、例えば 、生成多項式f(x)=x 4 +x+1で生成されるガロア体GF(16)の元として、 らに、c(x)=xとすると、下記の(4×4)の行列Tが られる。

 この行列Tを基に、y(x)=c(x)・xの結果を与え y(x)の各係数y 0 、y 1 、y 2 、…、y m-1 を求めることができる。

 例えば、y(x)の0次の係数y 0 は、上記右側の行列Tにおける右端の第4列の 終行の3行の「1」を見て、y 0 =v 3 の式を得る。

 同様に、y(x)の1次の係数y 1 は、上記右側の行列Tにおけるの第3列の最終 の3行の「1」と先頭行(0行)の「1」を見て、y 1 =v 3 +v 0 の式を得る。

 このように、y(x)の各係数y 0 ~y 3 をv(x)係数v 0 ~v 3 で簡素化して表現できる。

 y 0 =v 3 、y 1 =v 3 +v 0 、y 2 =v 1 、y 3 =v 2
 このことは、生成多項式f(x)で表現されるガ ロア体GF( )の各元の行列Tが定まれば、各レ スタ12にどのレジスタ12の出力を帰還すべき が一義的に定まることを意味する。

 言い換えれば、各レジスタ12にどのレジス 12からのビットデータを帰還させるかは、指 定べき乗値設定部15から印加されているmビッ ト構成の指定べき乗値(α k )の各桁の「1」又は「0」の値によって定まる 。

 さらに、前記多項式v(x)、y(x)を、各要素 それぞれの係数であり、かつ要素数が4であ それぞれの行ベクトルV、Yで表す。

 V=[v 3  v 2  v 1  v 0 ]
 Y=[y 3  y 2  y 1  y 0 ]
 これにより、上述したガロア体乗算「y(x)=c( x)・v(x)」の乗算結果y (x)は、下記に示すよう に、要素数4の行ベクトルVと4×4の行列Tとの で要素数4の行ベクトルですことが可能であ 。

 Y=V×T
 次に、元αの指定べき乗値kで得られる生成 (α k )が定数としてガロア体演算部13へ入力される 場合を考える。

 この場合、拡大ガロア体GF(2 m )の一つの多項式f(x)の根の一つがαであるの 、このαを多項式形式で表現すると、「1」 は「0」の要素数mの行となる。

 α=[a m-1  a m-2 …a 1  a 0 ]
 α 2 は、このαにαを掛けることによって求める

 このようにして、先に求めた値を順番に掛 ていって、生成元(α k )の「1」又は「0」の要素数mの行が求められ 。

 α k =[a m-1  a m-2 …a 1  a 0 ]
 そして、変数×定数のm×mのガロア体乗算が 要であるので、前述した手法で、各べき乗 α k 、α k+1 、α k+2 、…、α k+m-1 の各多項式形式で表現された「1」又は「0」 要素数mの行を算出する。

 その結果、前述した(m×m)の行列Tが得られ る。

 具体的には、図4に示すように、指定べき乗 値(α k )のさらにべき乗値(α k 、α k+1 、α k+2 、…、α k+m-1 )のmビット(m桁)のデータ一覧テーブル20に前 した手法で算出した(m×m)の行列Tの各値を書 む・
 そして、0番から(m―1)番までの各レジスタ12 に帰還される各ビットデータ値にガロア体乗 算する各指定べき乗値α k の各べき乗値(α k 、α k+1 、α k+2 、…、α k+m-1 )の各レジスタ12に対応する桁の値が「1」の 合に、該当レジスタ12からビットデータを桁 が示すレジスタ12へガロア体乗算部13として 複数個の排他的論理和ゲート17を介して帰還 させる帰還路18が形成される。

 次に、コンピュータ上で実際に作成したM 系列発生回路11を図5、図6、図7を用いて説明 る。

 この実施形態のM系列発生回路11においては 図6、図7に示すように、Q 0 ~Q 12 の合計13個(m=13)のレジスタ12、同じく各レジ タ12に自己を含む各レジスタ12からビットデ タが帰還される複数個の排他的論理和ゲー 17が組込まれた複数の帰還路18が組込まれて いる。

 このM系列発生回路11においては、レジスタ1 2の数mは、図9において、m=13(素数)に設定され 、最大長周期(2 m -1)は8191であり、この値はメルセンヌ素数で る。

 そして、この次数m=13の2元の拡大ガロア体GF (2 m )の原始多項式p(x)の数は、630個存在する。

 この630個の原始多項式p(x)のうち、項数が 多い5項数の下記に示す原始多項式p(x)を採用 ている。

 p(x)=x 13 +x 5 +x 2 +x+1
 そして、この原始多項式p(x)の根の一つであ る、最大mビット構成の原始元αの指定べき乗 kを107に設定している(k=107)。

 したがって、このM系列発生回路11内におけ ガロア体乗算部13に印加する指定べき乗値( k )は、(α 107 )となる。

 この指定べき乗値(α k )の各べき乗値(α k 、α k+1 、α k+2 、…、α k+m-1 )である各べき乗値(α 107 、α 107+1 、α 107+2 、…、α 107+12 )のそれぞれ多項式形式で表現した値である ビットデータ(13桁)を算出して、図5の(a)に示 すデータ一覧テーブル20に書込む。

 そして、先頭のレジスタ12(Q 0 )に帰還路18が形成されるレジスタ12は、各べ 乗値(α 107 、α 107+1 、α 107+2 、…、α 107+12 )の各ビットデータの最下位桁が「1」である べき乗0、1、…、12に対応する番号のレジス タ12である。

 この例では、図5の(b)に示す検索結果テーブ ル21に示すように、Q 0 、Q 2 、Q 3 、Q 4 、Q 5 、Q 6 、Q 7 、Q 10 、Q 11 、Q 12 の合計10個のレジスタ12である。

 さらに、2番目のレジスタ12(Q 1 )に帰還路18が形成される、レジスタ12は、各 き乗値(α 107 、α 107+1 、α 107+2 、…、α 107+12 )の各ビットデータの最下位桁から2番目の桁 「1」である各べき乗0、1、…、12に対応す 番号のレジスタ12である。

 同様に、最下位から2番目のレジスタ12(Q 11 )に帰還路18が形成される、レジスタ12は、各 き乗値(α 107 、α 107+1 、α 107+2 、…、α 107+12 )の各ビットデータの最下位桁から12番目の桁 が「1」である各べき乗0、1、…、12に対応す 番号のレジスタ12である。

 この例では、検索結果テーブル21に示すよ に、Q 0 、Q 6 、Q 8 の合計3個のレジスタ12のみである。

 図6、図7は、図5の(b)に示す検索結果テー ル21に登録されている帰還路18が形成される レジスタ12相互間に実際に帰還路18を記載し M系列発生回路11の実回路図である。

 このように、ガロア体乗算部13を採用す ことにより、M系列発生回路11の設計処理速 が上昇して、効率的に回路設計を実施でき 。

 さらに、このM系列発生回路11の各レジス 12は、図16に示す従来のM系列発生回路1のシ トレジスタ構成ではなくて、互いに独立し いる。

 よって、このM系列発生回路11によれば、 つのデータを計算するのに、1クロックで実 施しているので、ランダムエラー信号作成の 高速化を図ることが可能である。

  (第2実施形態)
 図8は本発明の第2実施形態に係わる、図6、 7に示すM系列発生回路の提供方法の手順を すフーローチャートである。

 先ず、ステップS1にて、使用するレジス 12の個数m(m=正整数)が選択的に設定される。

 具体的には、図9、図10の一覧テーブルを参 して、レジスタ数mは、素数であるとともに 、最大長周期(2 m -1)が素数であるメルセンヌ素数になる値に設 定される。

 具体的には、「素数」と「メルセンヌ素 」との両方を満たす前述した「2、3、5、7、 13、17、19、31、61、89、107、127」の合計12個の ちの1つが選択される。

 さらに、項数が比較的多い例えば5項式の原 始多項式p(x)を複数個、2元の拡大ガロア体GF(2 m )で実現できるレジスタ数m(次数)が選択され 。

 この例では、m=13が選択的に設定されてい る。

 次に、この選択された数mを次数mとする2元 拡大ガロア体GF(2 m )における次数mの複数の原始多項式p(x)を図示 しないデータベースから検索する。

 このデータベースには、図11の原始多項 一覧表22に示すように、各次数mに対して存 する全ての原始多項式p(x)が書込まれている( 以上、ステップS2)。

 この例では、図9に示すように、m=13にお ては、630個の原始多項式p(x)が存在する。

 この場合、原始多項式p(x)の個数λ(m)は、 イラーのφ関数を用いて、次式で示される

 λ(m)=φ(2 m -1)/m
 そして、この検索された複数の原始多項式p (x)のうちの一つの原始多項式p(x)が選択され 。

 この例では、630個の原始多項式p(x)のうち 、5項数の1個の下記の原始多項式p(x)を選択さ れる(ステップS3)。

 p(x)=x 13 +x 5 +x 2 +x+1
 次に、選択された原始多項式p(x)の根の一つ である原始元αが算出される。

 具体的には、典型的な原始多項式p(x)の各 根である各原始元αは予め算出されていて、 ンピュータのデータベースに記憶されてい ものとする。

 したがって、このデータベースから一つ 原始元αが選択される(ステップS4)。

 また、前記2元の拡大ガロア体GF(2 m )を原始元αのべき乗の下記に示すような級数 で表現した場合の2乗以上(k≧2)の指定べき乗 (α k )が選択される(ステップS5)。

  (α 1k )、(α 2k )、(α 3k )、…
 このべき乗kは最大長周期(2 m -1)の1/3程度が望ましい。

 この例では、最大長周期(2 m -1)=8191に対して、約1/20のk=107に設定されてい 。

 このように、クロック(CLK)に同期して、順 乗算されるデータを原始元αでなくて指定べ き乗値(α k )とすることにより、各レジスタ12に各クロッ ク毎に書込まれるビットデータをよりランダ ムにできる。

 次に、この選択された指定基準べき乗値(α k )の0番から(m-1)番までの各レジスタ12に帰還さ れる各データ値にガロア体乗算する各指定基 準べき乗値α k のべき乗値(α k 、α k+1 、α k+2 、…、α k+m-1 )が算出される。

 そして、この各指定基準べき乗値α k のべき乗値(α k 、α k+1 、α k+2 、…、α k+m-1 )が、図4、図5の(a)に示すように、データ一覧 テーブル20に書込まれる(ステップS6)。

 また、図1に示すように、クロック(CLK)が入 する毎に、各レジスタ12に帰還されるビッ データ値に対してべき乗値(α k )がガロア体乗算するガロア体乗算部13に設定 される(ステップS7)。

 そして、前述したように、データ一覧テー ル20に記載された各レジスタ12に対応するべ き乗値(α k 、α k+1 、α k+2 、…、α k+m-1 )の各レジスタに対応する桁の値が「1」の場 に、該当レジスタからビットデータを桁が すレジスタ12へガロア体乗算部13としての複 数個の排他的論理和ゲート17を介して帰還さ る帰還路18が作成される(S8)。

 その結果、図2、図6、図7に示すM系列発生 回路11が提供される。

 なお、本発明は上述した第1、第2実施形 のM系列発生回路に限定されるものではない

  (第3実施形態)
 本発明の第3実施形態のM系列発生回路にお ては、レジスタ12の数m(m=2以上の正整数)を次 数mとする2元の拡大ガロア体GF(2 m )の複数の多項式のうちの項数が多い多項式 根の一つが前記元αでなく、多項式の根の一 つが元eであるとき、元eの2以上(k≧2)の指定 き乗値(e k )をさらにべき乗して配列した周期系列{(α1k) (2k)、(α3k)、…、}の周期が最大長周期(2 m -1)以内である。

 このように構成された第3実施形態のM系 発生回路においては、採用する多項式(生成 項式)は原始多項式p(x)に限定されない。

 したがって、実際におけるM系列発生回路か ら出力されるビットデータの周期が最大長周 期(2 m -1)に、必ずしも一致するとは限らない。

 しかしながら、この場合には、レジスタ 数mを任意に設定できる。

  (第4実施形態)
 図13は、本発明の第4実施形態に係わるラン ムエラー発生装置の概略構成を示す図であ 。

 なお、図13において、図1に示した第1実施 形態のランダムエラー発生装置と同一部分に は、同一符号を付して、重複説明を省略する 。

 この第4実施形態のランダムエラー発生装置 においては、n台のM系列発生回路23 1 、23 2 、…、23 n が設けられている。

 各M系列発生回路23 1 、23 2 、…、23 n は、第1実施形態のM系列発生回路11とほぼ同 構成であり、異なるところは、レジスタ数m それぞれ異なる値m 1 、m 2 、…、m n に設定されていることである。

 さらに、べき乗値設定部24 1 、24 2 、…、24 n が、各M系列発生回路23 1 、23 2 、…、23 n 内のガロア体乗算部13に印加するべき乗値(α k )のべき乗kは、各M系列発生回路23 1 、23 2 、…、23 n 毎に異なる値k=k 1 、k 2 、…、k m に設定されている。

 また、初期値設定部25 1 、25 2 、…、25 n が、各M系列発生回路23 1 、23 2 、…、23 n 内の各レジスタ12に初期設定する擬似乱数値 各M系列発生回路23 1 、23 2 、…、23 n 毎に異なる値に設定される。

 さらに、各M系列発生回路23 1 、23 2 、…、23 n には、一つのクロック回路16から共通のクロ ク(CLK)が印加される。

 各M系列発生回路23 1 、23 2 、…、23 n は、クロック回路16からクロック(CLK)が入力 れる毎に、それぞれ、m 1 、m 2 、…、m n ビット構成の並列ビットデータを出力して、 データ位置入替回路26の入力部26aへ送出する

 このデータ位置入替回路26の入力部26aには 各M系列発生回路23 1 、23 2 、…、23 n から出力される各並列ビットデータのビット 数m 1 、m 2 、…、m n を加算したビット数m=m 1 +m 2 +、…、+m n の入力端子を有する。

 一方、データ位置入替回路26の出力部26b も入力部26aと同数であるm個の出力端子が設 られている。

 そして、データ位置入替回路26は、入力 26aの合計m個の各入力端子から出力部26bの出 端子への接続先がランダムに割り振られて る。

 したがって、このデータ位置入替回路26 、入力部26aに入力された合計mビットのデー 位置をランダムに入れ替えて出力部26bから 力する。

 これにより、このデータ位置入替回路26 らクロック(CLK)に同期して出力されるmビッ データのランダム性が向上する。

 このデータ位置入替回路26の出力部26bか 出力された並列mビットデータは、比較器6一 方の入力端子(X端子)に印加される。

 この比較器6の他方の入力端子(Y端子)には 基準値設定回路7で操作者によって操作入力 れた並列mビットの基準値が入力される。

 そして、比較器6は、一方の入力端子(X端 )から取込んだ数値Aが他方の入力端子(Y端子 )から取込んだ基準値B以下の場合、エラービ トとなるラムダムエラー信号aを出力する。

 このように構成された第4実施形態のランダ ムエラー発生装置においては、各M系列発生 路23 1 、23 2 、…、23 n におけるレジスタ数は互いに異なる値に設定 されているので、各M系列発生回路23 1 、23 2 、…、23 n 毎に出力されるビットデータ列の周期が異な る。

 さらに、データ位置入替回路26で全部のM系 発生回路23 1 、23 2 、…、23 n のビットデータのデータ位置を全部のM系列 生回路23 1 、23 2 、…、23 n に亘って入れ替えているので、このランダム エラー発生装置から出力されるラムダムエラ ー信号aのランダム性をより一層向上できる

 さらに、この第4実施形態においては、n台 M系列発生回路23 1 、23 2 、…、23 n で、図1に示した1台のM系列発生回路11とほぼ 等の周期を実現している。

 この場合、ほぼ同等の周期を得るための 路構成が図1に示した1台のM系列発生回路11 比較して簡素化される。

 すなわち、一般に、M系列発生回路の回路 構成の規模は、レジスタの数(次数m)のほぼ二 乗に比例することが実験的にも理論的にも実 証されている。

 その理由は、ガロア体上の乗算がほぼ次 mの二乗に比例する回路規模を必要とするか らである。

 例えば、1台のM系列発生回路11で次数m=30の 大長周期(2 m -1)を実現する場合には、30 2 ×K(定数)=900×Kの回路規模が必要である。

 これに対して、それぞれ、次数m 1 =13、次数m 2 =17の2台のM系列発生回路23で構成した場合(m=m 1 +m 2 =30)の合計の回路規模は、
 13 2 K+17 2 K=(169+289)K=458×K
となり、1台のM系列発生回路11で構成した場 より回路規模を大幅に縮小できる。

 なお、複数のM系列発生回路23を並列使用し より長い周期の周期系列を生成する場合、 際に実現される合成の周期は各M系列発生回 路23の周期の最小公倍数になるので、各M系列 発生回路23の次数m 1 、m 2 の関係を互いに素の関係に設定することが望 ましい。

  (第5実施形態)
 図14は、本発明の第5実施形態に係わるラン ムエラー発生装置の概略構成を示す図であ 。

 図14において、図13に示した第4実施形態 ランダムエラー発生装置と同一部分には、 一符号を付して、重複説明を省略する。

 この第5実施形態のランダムエラー発生装 置においては、図13に示した第4実施形態のラ ンダムエラー発生装置におけるデータ位置入 替回路26が除去されている。

 さらに、各M系列発生回路23 1 、23 2 、…、23 n のレジスタの個数m 1 、m 2 …、m n は互いに素の関係に維持されている。

 そして、各M系列発生回路23 1 、23 2 、…、23 n は、クロック回路16からクロック(CLK)が入力 れる毎に、それぞれ、m 1 、m 2 …、m n ビット構成の並列ビットデータが出力されて 、比較器6の一方の入力端子(X端子)に印加さ る。

 この比較器6の一方の入力端子(X端子)は、各 M系列発生回路23 1 、23 2 、…、23 n から出力される各並列ビットデータのビット 数m 1 、m 2 …、m n を加算したビット数m=m 1 +m 2 +、…、m n の端子を有する。

 一方、この比較器6の他方の入力端子(Y端 )には、基準値設定回路7で操作者によって 作入力された並列mビットの基準値が入力さ る。

 そして、比較器6は、一方の入力端子(X端 )から取込んだ数値Aが他方の入力端子(Y端子 )から取込んだ基準値B以下の場合、エラービ トとなるラムダムエラー信号aを出力する。

 このように構成された第5実施形態のランダ ムエラー発生装置においては、各M系列発生 路23 1 、23 2 、…、23 n におけるレジスタ数は互いに素の関係に設定 されているので、各M系列発生回路23 1 、23 2 、…、23 n 毎に出力されるビットデータ列の周期が互い に異なる。

 したがって、比較器6の一方の入力端子(X端 )に入力される全部のM系列発生回路23 1 、23 2 、…、23 n に亘る複数のビットデータのデータ列の周期 を長くできるので、このエラー発生装置から 出力されるラムダムエラー信号aのランダム を十分向上できる。

 一般の電気信号ケーブルを用いたデジタ 通信網や光ファイバケーブルを用いた光通 網に組込まれた各種通信機器に対する各種 験を実施する試験装置においては、試験対 の通信機器に対して、この通信機器の実際 使用状況に合致した試験信号を入力して、 の通信機器の応答動作を評価することが必 となる。

 このような通信機器に対する評価試験の つの種類として、測定対象の通信機器に送 する試験信号として、実際の使用状況に合 した故意にエラーを含ませた試験信号を採 することにより、通信機器が、試験信号に まれるエラーの発生率(誤り率)Eがどの程度 で正常に動作するかを評価することが必要 なる。

 本発明によるランダムエラー発生装置は 上述の試験信号として利用可能な指定され 誤り率を有し、かつそのエラー分布が光通 や電気通信で発生する雑音等に起因するエ ー分布に近似するランダムエラー信号を出 する。

 また、本発明によるM系列発生回路は、上 述のランダムエラー発生装置を実現するため に適用可能である。