算数 数学

1と0 update 20190107

計算機の世界

数を数えるとき、大抵の人間は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):M系列があります。

 

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

 

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

 

ガロア体とは?
→加法(+)、減法(-)、乗法(×)、除法(÷)に関して、閉じている集合(ただし÷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のM系列を生成する、ということです。

 

注意・・・・・・・・・・
■ここで表現されている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={ 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]、・・・ }、

 

→s={ 0、0、0、1、0、0、1、1、0、1、0、1、1、1、1、0、・・・・・・ }

 

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

 

ページのトップへ

 

----- ここまで 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+1)^30*(x^2+x+1)^7*
(x^3+x+1)^3*(x^3+x^2+1)^3*(x^4+x^3+x^2+x+1)^2*
(x^6+x^3+1)*(x^10+x^9+x^8+x^7+x^6+x^5+x^4
+x^3+x^2+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^4+x+1、x^4+x^3+1の2つです。
→式の次数の並びを逆にすると、f[0]+f[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+x^3+x^6+x^7、
 1+x+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次特性多項式の表現方法

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

 

特性多項式の表現方法はいろいろあるようですが、
f(x)=f[0]1+f[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に戻る

M系列回路を設計してみます

ディジタル回路のシフトレジタと排他的論理和でM系列を生成できると述べました。小学算数と中学(以降の)数学について見つめなおす、というサイトの趣旨から離れますが、どのように構成したらディジタル回路で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でVccに供給します。

 

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

 

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

 

ブレッドボード用ジャンパワイヤセット(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以外の多種多様な無料の電子回路シミュレータもあるようなので、そちらでシミュレートするのも良いでしょう。