算数 数学

トップページ ＞ 1と０

１と０　update 20190122

数を数えるとき、大抵の人間は10進数で数えます。12進数でダースやグロスで数えたりするところもあります。時を数えるとき10進数と60進数を組み合わせて数えます。

 

1と0の2種類しか使わない2進数は、人間の実社会でほとんど使われない数ですが、ディジタルコンピュータの世界では必須な数です。

 

1または0の二つの値だけを持つ変数を用いる論理を、ブール代数といいます。論理代数におけるすべての演算（論理演算）は、論理積（∧，・，AND）、論理和（∨，＋，OR），否定論理（¬，^，NOT）の三つの基本演算の組み合わせで表現でき、この論理演算はオン、オフというスイッチの組み合わせで実現できます。
すなわち、コンピュータは、算術計算を電気的なスイッチの組み合わせ（論理回路）で作られているのです。

 

第1世代のコンピュータは真空管をスイッチ回路として用いました。その次の世代はトランジスタをスイッチ回路として、その次の世代は集積回路（IC：Integrated circuit）をスイッチ回路として、その次の世代は大規模集積回路（LSI：Large Scale IC）をスイッチ回路として、・・・と発展してきました。

1と0はコンピュータの世界のほかに別の世界を持っています。
それは、1と0のみの数列で作られる疑似不規則信号や疑似乱数の世界で、計測や科学シミュレーションで使用されています。この数列のひとつに最大周期列（squence of maximal period）：Ｍ系列があります。

 

Ｍ系列は、コンピュータープログラムでソフトウェアとして作り出せるほかに、シフトレジスタと排他的論理和（EX-OR）の組み合わせでハードウェアとしても作り出せます。

 

Ｍ系列とは？
→ガロア体GF(q)上のn次多項式 f(x)が原始的（primitive）であるとき、最大周期q^n-1を持つ数列をf(x)により生成できます。この原始多項式で生成される数列が最大周期列（squence of maximal period）を形成するのですが、qが2のときの最大周期列をＭ系列と呼んでいます。

 

ガロア体とは？
→加法（+）、減法（-）、乗法（×）、除法（÷）に関して、閉じている集合（ただし÷0を除く）を「体（field）」といい、有限個からなる体を有限体またはガロア体（Galois field）といいます。q個の要素からなる有限体をGF(q)で表します。q=2のとき、GF(2)と表記され、要素{1,0}が対象となります。

 

GF(2)とは？
→{0,1} という，要素数が2の有限集合を考えます。そして，四則演算を「整数の世界で四則演算をして，それを 2 で割った余り」と定義します。例えば，1+1=0，1×0=0，0-1=1という感じです。
この定義は四則演算が満たすべき性質（体の公理）を満たしているので，有限体になっています。

 

多項式が原始的であるとは？
→与えられた多項式のすべての係数の最大公約数のことを「内容」というのですが、この内容が「1」に等しいことです。このときの多項式を「原始多項式」であるといいます。すなわち、与えられた多項式の各項の係数が1か0ということです。

 

排他的論理和とは？
→2つの入力のどちらか片方が真でもう片方が偽の時には結果が真となり、両方とも真あるいは両方とも偽の時は偽となる演算（論理演算）のことです。

 

シフトレジスタとは？
→複数のフリップフロップ回路をカスケード接続したデジタル回路のことです。データ（1または0）がその回路を移動(シフト)していくよう構成されています。

 

フリップフロップ回路とは？
→ディジタル回路の一種で、「0」または「1」の値を保持することができる回路のことです。

 

カスケード接続とは？
→複数の回路素子などを縦一列につなぐことをいいます。直列接続。

 

【定理】〜〜〜〜〜〜〜〜〜〜
■f(x)がGF(2)上の多項式
　　f(x)=f[0]+f[1]x+f[2]x^2+・・・+f[m]x^m
　（f[0]=f[m]=1、[・]は添え字を表します）
で、その次数をmとする。
f(x)は多項式x^(2^m-1)-1を割り切るが、t＜2^m-1に対し、f(x)は多項式x^t-1を割り切らないとする。
このとき、すべてのs∈S[f(x)]　(ただし、s=(0,0,0,・・・・,0)は除く）
について（その周期）P(s)=2^m-1である。
〜〜〜〜〜〜〜〜〜〜〜〜〜〜

 

上の定理を具体的な数字を入れて、考えてみます。
f(x)がGF(2)上の多項式
　　f(x)=1+1･x+0･x^2+0･x^3+1･x^4
　　　→次数m=4で、f[0]=1、f[1]=1、f[2]=0、f[3]=0、f[4]=1であるとき

 

f(x)は多項式x^(2^4-1)-1=x^(16-1)-1=x^15-1を割り切るが、
多項式x^14-1、x^13-1、・・・x^5-1、x^4-1を割り切らない、
とは、

 

x^15-1を因数分解（mod2）したとき、因数f(x)=1+x+x^4をもつ、ということ。

 

また、多項式x^14-1、x^13-1、・・・、x^4-1を割り切らない
とは、

 

各多項式を因数分解（mod2）したとき、因数f(x)=1+x+x^4をもたない、ということ。

 

x^15-1を因数分解(mod2)します。

 

x^15-1
→　(1+x)*(1+x+x^2)*(1+x+x^4)*(1+x^3+x^4)*(1+x+x^2+x^3+x^4)

 

第3項目がf(x)なので、f(x)は多項式x^15-1を割り切ります。

 

x^t-1のとき、t＜15の多項式を因数分解（mod2)してf(x)を因数にもつか調べます。。

 

■x^14-1　
→　(x+1)^2*(x^3+x+1)^2*(x^3+x^2+1)^2、
■x^13-1　
→　(x+1)*(x^12+x^11+x^10+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1)、
■x^12-1　
→　(x+1)^4*(x^2+x+1)^4、
■x^11-1　
→　(x+1)*(x^10+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1)、
■x^10-1　
→　(x+1)^2*(x^4+x^3+x^2+x+1)^2、
■x^9-1　
→　(x+1)*(x^2+x+1)*(x^6+x^3+1)、
■x^8-1　
→　(x+1)^8、
■x^7-1、　
→　(x+1)*(x^3+x+1)*(x^3+x^2+1)、
■x^6-1　
→　(x+1)^2*(x^2+x+1)^2、
■x^5-1　
→　(x+1)*(x^4+x^3+x^2+x+1)、
■x^4-1　
→　(x+1)^4、

 

f(x)=1+x+x^4
を因数に持たないことがわかりました。

 

同時に
g(x)=1+x^3+x^4
も因数に持たないことがわかりました。

 

すなわち、原始多項式　f(x)=1+x+x^4、および　g(x)=1+x^3+x^4　は、特性多項式であって、
最大周期P(s)=15のＭ系列を生成する、ということです。

 

注意↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
■ここで表現されているxのベキ、x^0、x^1、x^2、・・・、x^m は、
2進数{f[0]、f[1]、f[2]、・・・、f[m]}の順序付けに使われるシンボルに過ぎません。
また+x^n=-x^n（すなわち、+1=-1）等の性質をもっています。

 

この意味で、
　　f(x)=f[0]+f[1]x+f[2]x^2+・・・+f[m]x^m　　　（f[0]=f[m]=1）、
の右辺は、変数xの関数と考えてはいけません。

 

また、当然ですが、係数f[i]はmodulo2（あるいはmod2、あるいは法2）の演算規則に従います。
↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑

 

〜〜〜〜〜〜〜〜〜〜〜〜〜〜
■ある固定したmについて、
　　s[0]=a[0]、s[1]=a[1]、・・・・、s[m-1]=a[m-1] →添え字を[・]で表します。
を与えると、mod2の線形漸化式、
　　f[0]s[i-m]+f[1]s[i-m+1]+・・・・+f[m]s[i]=0 ； （mod2）、
　　（i=m、m+1、m+2、・・・・ ； f[m]≠0、f[0]≠0）、
により、要素{0,1}の無限数列、
　　s=(s[0],s[1],・・・,s[m-1],s[m],・・・)、
が順次（再帰的に）得られます。
〜〜〜〜〜〜〜〜〜〜〜〜〜〜

 

これをm=4に固定して具体的に考えてみます。
　a[0]=0、a[1]=0、a[2]＝0、a[3]=1　とします（初期値）。
したがって、
　s[0]=0、s[1]=0、s[2]＝0、s[3]=1　（数列の始まり）。

 

このときmod2の線形漸化式は、
　f[0]*s[0]+f[1]*s[1]+f[2]*s[2]+f[3]*s[3]+f[4]*s[4]=0、
　（i=4、i=5、i=6、・・・；f[0]=f[4]=1）

 

ここで4次の原始多項式、
　f(x)=f[0]+f[1]*x+f[2]*x^2+f[3]*x^3+f[4]*x^4、
の係数を、
f[0]=1、f[1]=1、f[2]=0、f[3]=0、f[4]=1とします。
→　f(x)=1+x+x^4、

 

はじめにi=4

 

　f[0]*s[0]+f[1]*s[1]+f[2]*s[2]+f[3]*s[3]+f[4]*s[4]=0、
→　s[0]+s[1]+s[4]=0、
→　0+0+s[4]=0、
∴　s[4]=0

 

次にi=5

 

　f[0]*s[1]+f[1]*s[2]+f[2]*s[3]+f[3]*s[4]+f[4]*s[5]=0、
→　0+0+s[5]=0、
∴　s[5]=0

 

次にi=6

 

　f[0]*s[2]+f[1]*s[3]+f[2]*s[4]+f[3]*s[5]+f[4]*s[6]=0、
→　s[2]+s[3]+s[6]=0、
→　0+1+s[6]=0、
∴　s[6]=1

 

次にi=7

 

　f[0]*s[3]+f[1]*s[4]+f[2]*s[5]+f[3]*s[6]+f[4]*s[7]=0、
→　s[3]+s[4]+s[7]=0、
→　1+0+s[7]=0、
∴　s[7]=1

 

次にi=8

 

　f[0]*s[4]+f[1]*s[5]+f[2]*s[6]+f[3]*s[7]+f[4]*s[8]=0、
→　s[4]+s[5]+s[8]=0、
→　0+0+s[8]=0、
∴　s[8]=0

 

次にi=9

 

　f[0]*s[5]+f[1]*s[6]+f[2]*s[7]+f[3]*s[8]+f[4]*s[9]=0、
→　s[5]+s[6]+s[9]=0、
→　0+1+s[9]=0、
∴　s[9]=1

 

次にi=10

 

　f[0]*s[6]+f[1]*s[7]+f[2]*s[8]+f[3]*s[9]+f[4]*s[10]=0、
→　s[6]+s[7]+s[10]=0、
→　1+1+s[10]=0、
∴　s[10]=0

 

次にi=11

 

　f[0]*s[7]+f[1]*s[8]+f[2]*s[9]+f[3]*s[10]+f[4]*s[11]=0、
→　1+0+s[11]=0、
∴　s[11]=1、

 

次にi=12

 

　f[0]*s[8]+f[1]*s[9]+f[2]*s[10]+f[3]*s[11]+f[4]*s[12]=0、
→　s[8]+s[9]+s[12]=0、
→　0+1+s[12]=0、
∴　s[12]=1

 

次にi=13

 

　f[0]*s[9]+f[1]*s[10]+f[2]*s[11]+f[3]*s[12]+f[4]*s[13]=0、
→　s[9]+s[10]+s[13]=0、
→　1+0+s[13]=0、
∴　s[13]=1

 

次にi=14

 

　f[0]*s[10]+f[1]*s[11]+f[2]*s[12]+f[3]*s[13]+f[4]*s[14]=0、
→　s[10]+s[11]+s[14]=0、
→　0+1+s[14]=0、
∴　s[14]=1

 

次にi=15

 

　f[0]*s[11]+f[1]*s[12]+f[2]*s[13]+f[3]*s[14]+f[4]*s[15]=0、
→　s[11]+s[12]+s[15]=0、
→　1+1+s[15]=0、
∴　s[15]=0
・
・
・

 

数列sは、
→s[0]、s[1]、s[2]、s[3]、s[4]、s[5]、s[6]、s[7]、s[8]、s[9]、s[10]、s[11]、s[12]、s[13]、s[14]、s[15]、・・・

 

→0、0、0、1、0、0、1、1、0、1、0、1、1、1、1、0、・・・・・・

 

無限数列が生成されました。

 

この無限数列がＭ系列であることを確認する方法として、
�@この数列を左から4個づつ区切り、その塊を2進数表示ととらえて10進数に変換すると、1周期で1〜15までの数値がすべて1回づつ出現する。
�A自己相関関数φ（ファイ）を計算するとズレ量τ（タウ）が0の位置で最大値1を示し、それ以外では1以下の一定値を示す。

 

まず�@ですが、以下のようになります。1〜15がもれなく出現しています。

 

 

また�Aの自己相関関数φは、ズレ量τが0のところで1、それ以外では0.467の一定値を示しています。

 

 

したがって、定義の漸化式から生成される無限数列は、確かにＭ系列なのです。

 

ページのトップへ

 

----- ここまで　20181215 -----

 

HOMEに戻る

エクセルで　f(x)=1+x+x^4　の特性多項式から生成される無限数列の最初の1周期分（i=0〜14）を作ってみましょう。
4個の数列の初期値と排他的論理和を組み合わせたブロック図を考えます。
基本形は下図の通りです。

 

係数f[0]=1、f[1]=1、f[2]=0、f[3]=0、f[4]=1、と　i=0　のときの数列の初期値s[0]=0、s[1]=0、s[2]=0、s[3]=1、を設定します。

 

係数は、1か0なので、以下のように省略して書くことができます。

 

初期値0、0、0、1　を使って、s[0]=0、s[1]=0の排他的論理和から、s[4]を計算ます。エクセルでは、論理式「=if(s(i-4)=s(i-3),0,1)」を使います。
→s[4]=if(s[0]=s[1],0,1)、

 

そのあとは、ひとつづつずらして
→s[5]=if(s[1]=s[2],0,1)、
→s[6]=if(s[2]=s[3],0,1)、
→s[7]=if(s[3]=s[4],0,1)、
→s[6]=if(s[4]=s[5],0,1)、
・・・・
というように計算していきます。

 

 

あとは、この周期でくりかえし数列が生成されていきます。

 

ページのトップへ

 

----- ここまで　20181223 -----

 

HOMEに戻る

M系列を生成する特性多項式は、次数nが4の場合について具体的に計算して求めました。

 

次数が4のときは、f(x)=x^(2^4-1)-1=x^15-1の因数（多項式）のうち、x^14-1、x^13-1、・・・、x^3-1、x^2-1、x-1が持つ因数（多項式）のどれとも共通しない因数（多項式）が特性多項式でした。

 

今、((x^15-1)/((x^14-1)*(x^13-1)*(x^12-1)*(x^11-1)*(x^10-1)*(x^9-1)*(x^8-1)*(x^7-1)*(x^6-1)*(x^5-1)*(x^4-1)*(x^3-1)*(x^2-1)*(x-1)))という割り算式をつくり、数式処理ソフトMaximaで因数分解（当然mod2です）します。
すると、共通因数は約分されるので、分子に残るのは、特性多項式になります。

 

分子は、(x^4+x+1)*(x^4+x^3+1)となり、「x^4+x+1」及び「x^4+x^3+1」の2つの多項式が抽出されたことが分かります。
→式の次数の並びを逆にすると、f[0]+ｆ[1]x+f[2]x^2+・・・、の形式に一致するので見やすくなります。今後は、因数分解した直後の多項式はMaximaの計算結果のそものを記述しますが、特性多項式として扱う際に、式の左から小さい次数で並べた形で説明します。

 

→n=4のときの特性多項式は、
　1+x+x^4、
　1+x^3+x^4
です。

 

では、次々に計算してみましょう。

 

n=5のとき、
((x^31-1)/((x^30-1)*(x^29-1)*(x^28-1)*(x^27-1)*(x^26-1)*(x^25-1)*(x^24-1)*(x^23-1)*(x^22-1)*(x^21-1)*(x^20-1)*(x^19-1)*(x^18-1)*(x^17-1)*(x^16-1)*(x^15-1)*(x^14-1)*(x^13-1)*(x^12-1)*(x^11-1)*(x^10-1)*(x^9-1)*(x^8-1)*(x^7-1)*(x^6-1)*(x^5-1)*(x^4-1)*(x^3-1)*(x^2-1)*(x-1)))

 

因数分解後の分子は、
(x^5+x^2-1)*(x^5+x^3+1)*(x^5+x^3+x^2+x+1)*(x^5+x^4+x^2+x+1)*(x^5+x^4+x^3+x+1)*(x^5+x^4+x^3+x^2+1)

 

特性多項式は、
　1+x^2+x^5、
　1+x^3+x^5、
　1+x+x^2+x^3+x^5、
　1+x+x^2+x^4+x^5、
　1+x+x^3+x^4+x^5、
　1+x^2+x^3+x^4+x^5

 

n=6のとき、
((x^63-1)/((x^62-1)*(x^61-1)*(x^60-1)*(x^59-1)*(x^58-1)*(x^57-1)*(x^56-1)*(x^55-1)*(x^54-1)*(x^53-1)*(x^52-1)*(x^51-1)*(x^50-1)*(x^49-1)*(x^48-1)*(x^47-1)*(x^46-1)*(x^45-1)*(x^44-1)*(x^43-1)*(x^42-1)*(x^41-1)*(x^40-1)*(x^39-1)*(x^38-1)*(x^37-1)*(x^36-1)*(x^35-1)*(x^34-1)*(x^33-1)*(x^32-1)*(x^31-1)*(x^30-1)*(x^29-1)*(x^28-1)*(x^27-1)*(x^26-1)*(x^25-1)*(x^24-1)*(x^23-1)*(x^22-1)*(x^21-1)*(x^20-1)*(x^19-1)*(x^18-1)*(x^17-1)*(x^16-1)*(x^15-1)*(x^14-1)*(x^13-1)*(x^12-1)*(x^11-1)*(x^10-1)*(x^9-1)*(x^8-1)*(x^7-1)*(x^6-1)*(x^5-1)*(x^4-1)*(x^3-1)*(x^2-1)*(x-1)))

 

因数分解後の分子は、
(x^6+x+1)*(x^6+x^4+x^3+x+1)*(x^6+x^5+1)*(x^6+x^5+x^2+x+1)*(x^6+x^5+x^3+x^2+1)*(x^6+x^5+x^4+x+1)

 

特性多項式は
　1+x+x^6、
　1+x^5+x^6、
　1+x+x^3+x^4+ x^6、
　1+x+x^2+x^5+x^6、
　1+x^2+x^3+x^5+x^6、
　1+x+x^4+x^5+x^6

 

n=7のとき
((x^127-1)/((x^126-1)*(x^125-1)*(x^124-1)*(x^123-1)*(x^122-1)*(x^121-1)*(x^120-1)*(x^119-1)*(x^118-1)*(x^117-1)*(x^116-1)*(x^115-1)*(x^114-1)*(x^113-1)*(x^112-1)*(x^111-1)*(x^110-1)*(x^109-1)*(x^108-1)*(x^107-1)*(x^106-1)*(x^105-1)*(x^104-1)*(x^103-1)*(x^102-1)*(x^101-1)*(x^100-1)*(x^99-1)*(x^98-1)*(x^97-1)*(x^96-1)*(x^95-1)*(x^94-1)*(x^93-1)*(x^92-1)*(x^91-1)*(x^90-1)*(x^89-1)*(x^88-1)*(x^87-1)*(x^86-1)*(x^85-1)*(x^84-1)*(x^83-1)*(x^82-1)*(x^81-1)*(x^80-1)*(x^79-1)*(x^78-1)*(x^77-1)*(x^76-1)*(x^75-1)*(x^74-1)*(x^73-1)*(x^72-1)*(x^71-1)*(x^70-1)*(x^69-1)*(x^68-1)*(x^67-1)*(x^66-1)*(x^65-1)*(x^64-1)*(x^63-1)*(x^62-1)*(x^61-1)*(x^60-1)*(x^59-1)*(x^58-1)*(x^57-1)*(x^56-1)*(x^55-1)*(x^54-1)*(x^53-1)*(x^52-1)*(x^51-1)*(x^50-1)*(x^49-1)*(x^48-1)*(x^47-1)*(x^46-1)*(x^45-1)*(x^44-1)*(x^43-1)*(x^42-1)*(x^41-1)*(x^40-1)*(x^39-1)*(x^38-1)*(x^37-1)*(x^36-1)*(x^35-1)*(x^34-1)*(x^33-1)*(x^32-1)*(x^31-1)*(x^30-1)*(x^29-1)*(x^28-1)*(x^27-1)*(x^26-1)*(x^25-1)*(x^24-1)*(x^23-1)*(x^22-1)*(x^21-1)*(x^20-1)*(x^19-1)*(x^18-1)*(x^17-1)*(x^16-1)*(x^15-1)*(x^14-1)*(x^13-1)*(x^12-1)*(x^11-1)*(x^10-1)*(x^9-1)*(x^8-1)*(x^7-1)*(x^6-1)*(x^5-1)*(x^4-1)*(x^3-1)*(x^2-1)*(x-1)))

 

因数分解後の分子は、因数分解後の分子は、
(x^7+x+1)*(x^7+x^3+1)*(x^7+x^3+x^2+x+1)*(x^7+x^4+1)*(x^7+x^4+x^3+x^2+1)*(x^7+x^5+x^2+x+1)*(x^7+x^5+x^3+x+1)*(x^7+x^5+x^4+x^3-1)*(x^7+x^5+x^4+x^3+x^2+x+1)*(x^7+x^6+1)*(x^7+x^6+x^3+x+1)*(x^7+x^6+x^4+x+1)*(x^7+x^6+x^4+x^2+1)*(x^7+x^6+x^5+x^2+1)*(x^7+x^6+x^5+x^3+x^2+x+1)*(x^7+x^6+x^5+x^4+1)*(x^7+x^6+x^5+x^4+x^2+x+1)*(x^7+x^6+x^5+x^4+x^3+x^2+1)

 

特性多項式は
　1+x+x^7、
　1+x^3+x^7、
　1+x^4+x^7、
　1+x^6+x^7、
　1+ｘ+x^3+x^6+x^7、
　1+ｘ+x^4+x^6+x^7、
　1+x+x^2+x^3+x^7、
　1+x^2+x^3+x^4+x^7、
　1+x+x^2+x^5+x^7、
　1+x+x^3+x^5+x^7、
　1+x^3+x^4+x^5+x^7、
　1+^2+x^4+x^6+x^7、
　1+x^2+x^5+x^6+x^7、
　1+x^4+x^5+x^6+x^7、
　1+x+x^2+x^3+x^4+x^5+x^7、
　1+x+x^2+x^3+x^5+x^6+x^7、
　1+x+x^2+x^4+x^5+x^6+x^7、
　1+x^2+x^3+x^4+x^5+x^6+x^7

 

n=8のとき
((x^255-1)/((x^254-1)*(x^253-1)*(x^252-1)*(x^251-1)*(x^250-1)*(x^249-1)*(x^248-1)*(x^247-1)*(x^246-1)*(x^245-1)*(x^244-1)*(x^243-1)*(x^242-1)*(x^241-1)*(x^240-1)*(x^239-1)*(x^238-1)*(x^237-1)*(x^236-1)*(x^235-1)*(x^234-1)*(x^233-1)*(x^232-1)*(x^231-1)*(x^230-1)*(x^229-1)*(x^228-1)*(x^227-1)*(x^226-1)*(x^225-1)*(x^224-1)*(x^223-1)*(x^222-1)*(x^221-1)*(x^220-1)*(x^219-1)*(x^218-1)*(x^217-1)*(x^216-1)*(x^215-1)*(x^214-1)*(x^213-1)*(x^212-1)*(x^211-1)*(x^210-1)*(x^209-1)*(x^208-1)*(x^207-1)*(x^206-1)*(x^205-1)*(x^204-1)*(x^203-1)*(x^202-1)*(x^201-1)*(x^200-1)*(x^199-1)*(x^198-1)*(x^197-1)*(x^196-1)*(x^195-1)*(x^194-1)*(x^193-1)*(x^192-1)*(x^191-1)*(x^190-1)*(x^189-1)*(x^188-1)*(x^187-1)*(x^186-1)*(x^185-1)*(x^184-1)*(x^183-1)*(x^182-1)*(x^181-1)*(x^180-1)*(x^179-1)*(x^178-1)*(x^177-1)*(x^176-1)*(x^175-1)*(x^174-1)*(x^173-1)*(x^172-1)*(x^171-1)*(x^170-1)*(x^169-1)*(x^168-1)*(x^167-1)*(x^166-1)*(x^165-1)*(x^164-1)*(x^163-1)*(x^162-1)*(x^161-1)*(x^160-1)*(x^159-1)*(x^158-1)*(x^157-1)*(x^156-1)*(x^155-1)*(x^154-1)*(x^153-1)*(x^152-1)*(x^151-1)*(x^150-1)*(x^149-1)*(x^148-1)*(x^147-1)*(x^146-1)*(x^145-1)*(x^144-1)*(x^143-1)*(x^142-1)*(x^141-1)*(x^140-1)*(x^139-1)*(x^138-1)*(x^137-1)*(x^136-1)*(x^135-1)*(x^134-1)*(x^133-1)*(x^132-1)*(x^131-1)*(x^130-1)*(x^129-1)*(x^128-1)*(x^127-1)*(x^126-1)*(x^125-1)*(x^124-1)*(x^123-1)*(x^122-1)*(x^121-1)*(x^120-1)*(x^119-1)*(x^118-1)*(x^117-1)*(x^116-1)*(x^115-1)*(x^114-1)*(x^113-1)*(x^112-1)*(x^111-1)*(x^110-1)*(x^109-1)*(x^108-1)*(x^107-1)*(x^106-1)*(x^105-1)*(x^104-1)*(x^103-1)*(x^102-1)*(x^101-1)*(x^100-1)*(x^99-1)*(x^98-1)*(x^97-1)*(x^96-1)*(x^95-1)*(x^94-1)*(x^93-1)*(x^92-1)*(x^91-1)*(x^90-1)*(x^89-1)*(x^88-1)*(x^87-1)*(x^86-1)*(x^85-1)*(x^84-1)*(x^83-1)*(x^82-1)*(x^81-1)*(x^80-1)*(x^79-1)*(x^78-1)*(x^77-1)*(x^76-1)*(x^75-1)*(x^74-1)*(x^73-1)*(x^72-1)*(x^71-1)*(x^70-1)*(x^69-1)*(x^68-1)*(x^67-1)*(x^66-1)*(x^65-1)*(x^64-1)*(x^63-1)*(x^62-1)*(x^61-1)*(x^60-1)*(x^59-1)*(x^58-1)*(x^57-1)*(x^56-1)*(x^55-1)*(x^54-1)*(x^53-1)*(x^52-1)*(x^51-1)*(x^50-1)*(x^49-1)*(x^48-1)*(x^47-1)*(x^46-1)*(x^45-1)*(x^44-1)*(x^43-1)*(x^42-1)*(x^41-1)*(x^40-1)*(x^39-1)*(x^38-1)*(x^37-1)*(x^36-1)*(x^35-1)*(x^34-1)*(x^33-1)*(x^32-1)*(x^31-1)*(x^30-1)*(x^29-1)*(x^28-1)*(x^27-1)*(x^26-1)*(x^25-1)*(x^24-1)*(x^23-1)*(x^22-1)*(x^21-1)*(x^20-1)*(x^19-1)*(x^18-1)*(x^17-1)*(x^16-1)*(x^15-1)*(x^14-1)*(x^13-1)*(x^12-1)*(x^11-1)*(x^10-1)*(x^9-1)*(x^8-1)*(x^7-1)*(x^6-1)*(x^5-1)*(x^4-1)*(x^3-1)*(x^2-1)*(x-1)))

 

因数分解後の分子は、
(x^8+x^4+x^3+x^2+1)*(x^8+x^5+x^3+x+1)*(x^8+x^5+x^3+x^2+1)*(x^8+x^6+x^3+x^2-1)*(x^8+x^6+x^4+x^3+x^2+x+1)*(x^8+x^6+x^5+x-1)*(x^8+x^6+x^5+x^2-1)*(x^8+x^6+x^5+x^3-1)*(x^8+x^6+x^5+x^4+1)*(x^8+x^7+x^2+x+1)*(x^8+x^7+x^3+x^2+1)*(x^8+x^7+x^5+x^3+1)*(x^8+x^7+x^6+x+1)*(x^8+x^7+x^6+x^3+x^2+x+1)*(x^8+x^7+x^6+x^5+x^2+x+1)*(x^8+x^7+x^6+x^5+x^4+x^2+1)

 

特性多項式は
　1+x^2+x^3+x^4+x^8、
　1+x+x^3+x^5+x^8、
　1+x^2+x^3+x^5+x^8、
　1+x^2+x^3+x^6+x^8、
　1+x+x^5+x^6+x^8、
　1+x^2+x^5+x^6+x^8、
　1+x^3+x^5+x^6+x^8、
　1+x^4+x^5+x^6+x^8、
　1+x+x^2+x^7+x^8、
　1+x^2+x^3+x^7+x^8、
　1+x^3+x^5+x^7+x^8、
　1+x+x^6+x^7+x^8、
　1+x+x^2+x^3+x^4+x^6+x^8、
　1+x+x^2+x^3+x^6+x^7+x^8、
　1+x+x^2+x^5+x^6+x^7+x^8、
　1+x^2+x^4+x^5+x^6+x^7+x^8、

 

とりあえず、手元にある道具（Maxima）でここまでやってみました。

n次の特性多項式をブロック図に展開すると下図のようになります。

 

特性多項式の表現方法はいろいろあるようですが、
f(x)=f[0]1+ｆ[1]x+.f[2]x^2・・・+f[j]x^j+・・・+f[n-1]x^(n-1)+f[n]x^n
の表現のほかに、f[0]とf[n]を除く係数が1になるf[j]のjを小さい順位に並べる方法があります。

 

例えば、n=5のときの
　1+x^3+x^5　は　(3)、
　1+x+x^2+x^3+x^5　は　(1,2,3)、
と表現します。

 

n=4〜8の一覧表を作ってみます。

 

nが4〜24の一覧表をネットで見つけたので紹介します。この表にはn=4を除いて意図的にjが3個の組み合わせしか記述されていません。それは、M系列を乱数ととらえると、jが3個のときの性質が他の組み合わせのときの性質よりもとても良いからだそうです。

 

さらに、nが4〜8の部分で2つの表を比較すると、Maximaで求めた特性多項式のすべてが取り上げられていないことが分かります。これも乱数としての性質から取捨選択された結果なのでしょうか？

 

 

ちなみに、n=24のM系列の周期は　16,777,216-1　です。
これってすごい周期に思えますが、intelのCPUcorei7のクロック周波数は3GHz〜4GHzですので、約0.005秒分です。

 

ページのトップへ

 

----- ここまで　20181229 -----

 

HOMEに戻る

Ｍ系列は、シフトレジスタと排他的論理和（EX-OR）の組み合わせでハードウェアとしてもを生成できると述べました。どのように構成したらディジタル回路でM系列信号を発生できるか検討してみます。

 

 

IC（集積回路）に74シリーズがあります。1962年にテキサス・インスツルメンツ社が製造をはじめた単電源[+5V]で動作する汎用ICで、74で始まる4桁または5桁の型番が付いているため74シリーズと呼ばれています。

 

7486が排他的論理和（EX-OR）で入力端子2・出力端子1のものが4個配置されています。

 

また、74164は8ビットのシフトレジスタです。
このシフトレジスタは初期値を設定できませんので、電源スイッチを入れたときに各ビットに偶然に設定された値（1か0）を初期値としてM系列を発生することになります。もし、この電源投入時に8ビット全部が0に設定されてしまったら、M系列は発生しません。そのときは、電源をいったん切って、再投入してみることになります。

 

偶然の初期値設定が嫌なときは、74195の4ビットシフトレジスタを使います。ロード信号を入力すると4ビットの初期値設定（任意の1か0）ができます。

 

シフトレジスタのデータの移動（シフト）は、入力するクロックの立ち上がりのタイミングで行われます。

 

クロックとは？
→汎用ICの中で、シフトレジスタやカウンタ等は、外部から入力されるクロックという矩形波の信号の立ち上がり（または立下り）のタイミングで一斉動作するように設計されています。この矩形波の凹（0V）と凸（5V）の1組で1周期を形成して、1秒間に1回の凹凸で1Hz（1ヘルツ）と数えます。

 

7486、74164及び74195のピン配置は下図の通りです。

 

 

電源は直流+5VでＶccに供給します。

 

さて、8ビットシフトレジスタとEX-ORで、次数n=8のM系列信号発生回路を設計してみます。
8次の特性多項式のなかから、f(x)=1+x^3+x^5+x^7+x^8を使ってみましょう（3,5,7)。

 

クロック（CK）周波数は、74HC164のタイプで最大21MHzです。

 

HCとは？
→ノーマルタイプ（この場合74164）より低消費電力かつ回路の反応速度がそこそこのタイプ

 

クロック発生回路は、ICのインバータ（論理否定）と水晶発振子、抵抗とコンデンサで作成します。

 

74HCU04を使った配線図は以下の通りです。

 

20MHz以下のクロックを作成する際の抵抗、コンデンサの値は以下の通りです。

74HCU04　1個30円
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜

 

74HC86　1個30円
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜

 

74HC164　1個30円
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜

 

水晶振動子20MHz　1個30円
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜

 

+5V直流スイッチング電源　1個3,690円
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜

 

カーボン抵抗（炭素被膜抵抗）1MΩ　1袋（100本入り）100円
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜

 

セラミックコンデンサ22pF　1個5円
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜

 

ブレッドボード　270円
【PR文引用】おもいついたことをすぐに実行できるブレッドボード。 電子回路の勉強や、回路の組み換えがすぐにできます。 簡単な回路の実験、部品の差し替えをすぐにしたい回路、ＣＲの定数決めや高価なパーツの評価にも最適です。 はんだごてを使用しないのでやけどの心配もありません。

 

【使用例】
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜

 

ブレッドボード用ジャンパワイヤセット（10cm）　18本180円
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜

 

ディジタルオシロスコープは電子部品ではありませんが、回路の作成途中にICが正常に作動して希望する信号波形が生成されているか確かめることに使います。また、M系列信号がきちんと発生しているかの確認にも使います。
たかだか20MHzの信号を測定するのに200MHzの帯域をもつオシロスコープが必要？と思うでしょうが、信号の遅延差でヒゲと呼ばれる悪さをするナノ秒オーダーのパルスが発生することがあるので、それを見つけるために必要になってきます。

 

ディジタルオシロスコープ200MHz　54,000円
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜

 

30円+30円+30円+30円+3,690円+100円+5円+5円+270円+180円+54,000円=58,370円
【秋月電子通商】の通信販売で購入可能です。
↓　　　↓　　　↓
http://akizukidenshi.com/catalog/

 

ページのトップへ

 

----- ここまで　20190107 -----

 

HOMEに戻る

めったにしない電子工作のためだけに、3千円以上もする電源を買ったり、5万円以上もするオシロスコープを買うのはなんとももったいないので、回路シミュレータを使うことにします。

 

現在、手元にあるのは、「CD-ROM付 電子回路シミュレータ入門 増補版」 (ブルーバックス)【2005年9月21日発売：定価1,600円】です。CD-ROMに収録されているのはCircuitMaker Student版で、一度に組める素子数は50個までという制限はあります。それでも、なかなかの優れものだと思います。

 

「有料版のCircuitMakerは電子回路教育の教材として使いやすく人気がありましたが， 販売元のAltium社はこの製品を販売中止にし、Student版の無料配布も停止してしまいました。2007年10月の時点で、すでに、CircuitMaker入手の唯一の方法が講談社ブルーバックスを購入すること」・・という記事がありました。

 

ですので、CircuitMaker に興味を持ち、入手を希望するときには、amazon等から中古本「CD-ROM付 電子回路シミュレータ入門 増補版」 (ブルーバックス)を購入するしかないようです。
amazonで検索しました。「中古品-可」で124円、送料257円で合わせて381円で売っていました。
試しに買ってみました。「中古品-可」というので、日焼け、書き込み等あるのかと思っていましたが、新品のようでしたので「いいじゃん、いいじゃん」と喜んでいましたら、CD-ROMがありません。「それはないじゃん」・・がっかりです。
中古品には当たり、外れがあるということですね。（それとも、CD-ROMは、CDとしてamazonで別売り？？）

 

すでに販売終了したものを使うのはいかがなものか？と思われる方は、インターネット上にはCircuitMaker以外の多種多様な無料の電子回路シミュレータもあるようなので、そちらでシミュレートするのも良いでしょう。

 

 

PCにCircuitMaker Student版をインストールしました。動作が保証されているWindowsXPから3世代も離れているWindows10ですが、それとなく動いています。10に移行する際に動かなくなるソフトがちらほらあったとの噂があったので心配していました。大丈夫のようです。

 

CircuitMakerで構築した回路はシミュレーションスタート時の初期値がオール”ゼロ”なので、M系列が生成されません。そこで初期値が設定できる74LS195の4ビットシフトレジスタを使い以下のように回路を組みました。

 

■「Ｃ（緑色）」：クロック信号。
■「Ａ（水色）」：ロード信号。
　→信号”Ｌ”（=0V）のときに4ビットシフトレジスタに初期値D3=1、D2=0、D1=0、D0=0、が設定。
■「Ｂ（黄色）」：M系列の出力信号。

 

74LS195を1個しか使わず、n=4の特性多項式f(x)=1+x^3+x^4（もう一つに表現→(3)）、周期=15のM系列にしたのは、ディジタルオシロスコープに信号の全体像を表示して、M系列信号が確かに発生していることを確認しやすくするためです。

 

このときのディジタルオシロスコープ画面は以下の通りです。

 

特性多項式f(x)=1+x^3+x^4、初期値1、0、0、0の1周期（=15）分のM系列は、
1、0、0、0、1、1、1、1、0、1、0、1、1、0、0。
オシロスコープの信号と比較して・・・、

 

 

合致しています。（よかった、よかった）

 

ちなみに、この信号はＭ系列と決めつけていますが、確かめてみます。

 

 

1〜15までの数字が出現しています。

 

 

自己相関関数φもτ=0で最大値1を示し、その他は1より小さい一定値を示しています。
Ｍ系列信号を発生していることが確認できました。（再び、よかった、よかった）

 

ページのトップへ

 

----- ここまで　20190119 -----

 

HOMEに戻る

M系列から高度に進化した擬似乱数生成アルゴリズムにメルセンヌ・ツイスタ（以下MT）があります。
このMTは2人の日本人、松本眞氏と西村拓士氏によって開発されました。
しかも、疑似乱数生成アルゴリズムとして現在最も高い評価を得ています。

 

松本氏と西村氏は、MTを考案する前に、M系列を発展させたTwisted General Feedback Shift Register(以下TGFSR)を提案しました。

 

これは

 

x[n+p]=x[n+q]+x[n]Ａ　　 (p>q>0)　　(1)、

 

を用いて疑似乱数列を生成します。

 

ここでＡ はTwisterと呼ばれる GF(2)（←ガロア体、M系列を扱うのだからこうなりますよね） の元（←1と0）を要素とする ω×ω の行列（←個人的には行列表現は苦手）です。
ただし x[n]∈GF(2)^ω （←どうゆうこと？）です。

 

TGFSRは 2^(pω)-1 の最大周期をもちます。また計算が高速になるような Ａを選択することができます。
TGFSRを改良したものがMTで、以下により疑似乱数列を生成します。

 

x[n+p]=x[n+q]+x[n+1]Ｂ+x[n]Ｃ (p>q>0)　　(2)、

 

式(2)による最大周期が 2^(19937)-1 のとき、特にMT19937と呼ばれいます。普通にMTというときは、MT19937を指します。

 

 

ページのトップへ

 

----- ここまで　20190122 -----

 

HOMEに戻る