M系列信号とは～生成法や定義を解説～

みなさん，こんにちは．
おかしょです．

今回はM系列信号とは何なのか，どうやって生成するのかについて解説していきます．

この記事を読むと以下のようなことがわかる・できるようになります．

M系列信号の生成方法
M系列信号とは何か

M系列信号とは
M系列信号の生成
M系列信号を手計算で求める．
M系列信号のプログラムの書き方
M系列信号の定義
まとめ
続けて読む
1. 共有:
2. 関連

M系列信号とは

M系列信号とは，簡単に言うと「規則性と不規則性を有する信号」のことです．

「規則性」と「不規則性」は反対の意味を表していて，そのどちらの要素も持つ信号なんてあるわけがないと思うかもしれません．

たしかに，その考え方は間違っていません．

M系列は間違いなく規則的な信号です．

しかし，不規則な信号に見えるため，M系列信号は規則性と不規則性をあわせもった信号と表現されることが多いです．

M系列信号は不規則なように見える規則的な信号であるため，プログラムで書いて，生成することが可能です．

以下では，M系列信号の生成の仕方を解説していきます．

M系列信号の生成

まずはM系列の定義などは後回しにして，どのようにしたらM系列信号ができるのかを解説していきます．

M系列信号は以下の図のようにして生成されます．

この図で言うと，xが生成されるM系列信号になります．

xの添え字のiには0, 1, 2, …が入ります．

$h_{0}, h_{1}, h_{2}, …, h_{n-1}$には0もしくは1の任意の値が入ります．

nはM系列信号の周期を決定する値

Zは1ステップ前の信号に戻すブロックです．

上の図を見ると分かるように，M系列信号はhの値とM系列信号の初期値によって決定されます．

この時，初期値もhと同様で0もしくは1となります．

ここで，注意しなければならないのは，M系列は0もしくは1の二値系列信号であるということです．

そのため，図中のプラスマークは単なる足し算ではなく，排他的論理和を表します．

排他的論理和とは，入力される値が一致するときは0を返し，一致しない時は1を返します．

この計算を行うことによってM系列信号は生成されます．

この図を式で表すと以下のようになります．

$$ x_{i+n} = \displaystyle \sum_{j=0}^{n-1} h_{j} x_{i+j} $$

ここで，Σは排他的論理和を表していることに注意

M系列信号を手計算で求める．

ここまでの説明でM系列について何となくわかった方と，なんだかよくわからない方がいるかもしれません．

そのような方のために，M系列信号を手計算で求める方法をご紹介します．

あとで，プログラムで求める方法も示しますので，あわせて確認してみてください．

まず，準備として以下のような表を作ります．

ここでは，上に示した式で$n=4$としてM系列を生成します．

また，$h_0=1, h_1=0, h_2=0, h_3=1$としました．

上の図は，書かなくてもかまいませんが，確認のために書いておきました．

それでは，まず初期値を設定します．

初期値は適当で大丈夫ですが，すべて0にしないようにしてください．

今回は以下のようにしました．

初期値の設定ができたら，$i=1, j=5$の値を求めます．

図に示したように，左から順番に排他的論理和を行います．

まずはこの部分を計算します．

$$ x_1\cdot h_0 \quad mod2 \quad x_2\cdot h_1=0\cdot1 \quad mod2 \quad 0\cdot 0=0 $$

次にこの部分を計算します．

$$ (x_1\cdot h_0\quad mod2\quad x_2\cdot h_1)\quad mod2\quad x_3\cdot h_2=0\quad mod2\quad 0\cdot 0=0 $$

このようにして計算を繰り返していくと$x_5=1$となります．

次に$i=1, j=2~5$の値を$i=2, j=1~4$に入れます．

これで先程と同じ計算をして$i=2, j=5$の値を求めていきます．

これを繰り返して，表を埋めていくと以下のようになります．

最終的に求められたM系列信号は以下のように矢印の向きに読むことで求められます．

$$ 000111101011001 00011… $$

M系列信号のプログラムの書き方

プログラムの書き方を説明する前に，最初にM系列を生成するプログラムを以下に示します．

ただ，動作確認はしていないため，使用する場合はご注意ください．

uint8_t M[50][1];
uint8_t H[4][1];

uint8_t n = 4;
 
M[0] = 0;
M[1] = 0;
M[2] = 0;
M[3] = 1;

H[0] = 1;
H[1] = 0;
H[2] = 0;
H[3] = 1;

for (uint16_t i = n; i<50; i++)
  {
    M[i] = (((M[i-n]*h[0]+M[i-(n-1)]*h[1])%2+M[i-(n-2)]*h[2])%2+M[i-(n-3)]*h[3])%2;
  }
end

これを実行すると以下のようなM系列が生成される．

それではプログラムの解説をしていきます．

uint8_t M[50][1];
uint8_t H[4][1];

このプログラムでM系列信号を保存する配列Mと係数Hを定義します．

もっと多くのM系列信号が欲しい場合は50よりも大きな値を指定します．

uint8_t n = 4;

今回は$n=4$としたので，このように定義します．

M[0] = 0;
M[1] = 0;
M[2] = 0;
M[3] = 1;

M系列信号の初期値をnの個数分設定します．

H[0] = 1;
H[1] = 0;
H[2] = 0;
H[3] = 1;

係数Hも同様にして設定します．

for (uint16_t i = n; i<50; i++)
  {
    M[i] = (((M[i-n]*h[0]+M[i-(n-1)]*h[1])%2+M[i-(n-2)]*h[2])%2+M[i-(n-3)]*h[3])%2;
  }
end

このfor文で排他的論理和の処理を行います．

for文のかっこの中ではiを定義し，初期値以降のM系列を求めるため$$i=nから50$$で設定しています．

先程も述べましたが，50よりも多くのデータが必要な場合は変更してください．

そしてfor文の中では対応するM系列信号と係数Hをかけます．

その値を足し合わせて，2で割った余りが排他的論理和の解となります．

C言語では割り算の余りはa%bでaをbで割った余りが求められます．

これをすべての係数に対して行うことで，新たなM系列信号を求めることができます．

M系列信号の定義

プログラムによって生成されたM系列信号は本当にM系列信号になっているのかを確認します．

そのためにはM系列とは何なのかを知っておく必要があります．

先程もM系列とは不規則なように見える規則信号だと言いましたが，ここではさらに数学的にどのように定義されているのかを確認します．

定義1. 周期

M系列信号はある一定の周期をもちます．

この周期はM系列信号を生成する際に設定する，nによって以下のように定まります．

$$ T=2^{n} -1 $$

先程のプログラムで計算すると，n=4であるから周期はT=15になるはずです．

ここで生成されたM系列信号を見てみます．

$$ 000111101011001\quad 000111101… $$

周期が計算通り，15であることが確認できました．

なので，周期の面で見れば，生成された信号はM系列信号であるということができます．

他のM系列信号の定義についても見ていきます．

定義2. 出現回数

上記で述べたようにM系列信号は周期的な信号であり，1周期あたりに0や1の出現回数が一定で決まっています．

この出現回数もnによって決まります．

1が1周期あたりに出現する回数は$2^{n-1}$

0が1周期あたりに出現する回数は$2^{n-1}-1$

となります．

生成された信号を見て，数えてみると1の出現回数は8回，0の出現回数は7回でした．

定義にのっとって計算してみても同じ回数であることが確認できます．

定義3. 連続性

M系列信号は0や1が連続して出現する回数にも決まりがあります．

その回数を定義するのが，この連続性です．

1周期内に連なる回数は以下の式によって求められます．

$$ 2^{n-k-1} $$

式中のnはこれまで通り，使用してきたものになります．

kは連なる数を表しています．

例えば，先程のプログラムで生成されたM系列信号で数字が2回連続で出現する回数について調べます．

上の式の通りに計算すると

$$ 2^{4-2-1} = 2 $$

となります．

先程の信号を確認すると，

$$ 000111101011001 000111101… $$

1が2回連続で出てくるのが1回，0が2回連続で出てくるのが1回あり，計算通り2回出現することが確認できました．

また，上の例からもわかるようにM系列信号は同じ数字が連続で出現する回数は0と1で同じ回数となります．

他の連続性についても見てみましょう．

同じ数字が4回，3回連続で出現する回数について調べてみます．

$$ 2^{4-4-1} = 0.5 $$

$$ 2^{4-3-1} = 1 $$

これを見るとおかしなことが起きています．

出現する回数を調べているにもかかわらず，4回連続で出現する回数が0.5回となっています．

さらに，3回連続で出現する回数も1回となっています．

0と1で同じ回数連続するはずなので，この値は偶数にならなければおかしいはずです．

「じゃあ，これはM系列ではない」

と思うかもしれませんが，これでもM系列です．

特例として$k=n$もしくは$k=n-1$となる時は上の式とは違った回数となります．

$k=n$の時は1が連続してn回出現するのが1回，$k=n-1$の時は0が連続してn-1回連続して出現するのが1回となります．

生成されたM系列信号を見ても，1が4回連続して出現するのが1回，0が3回連続して出現するのが1回となっていることが確認できます．

定義4. シフト巡回性

ここで説明する定義が，M系列信号を特徴づける重要な定義となります．

この性質は他の系列には見られないものなので，もし生成したM系列に自信がない場合はこの定義に当てはまるのかを確認するといいと思います．

さて，このシフト順回生とは何なのか説明します．

まず，生成したM系列信号の1周期分を取り出します．

上記の例で言うと，以下のようになります．

$$ 000111101011001 $$

また，左に任意の回数M系列信号をシフトした信号を用意します．

今回は5回シフトした以下の信号を用意しました．

$$ 110101100100011 $$

この二つの信号に対して，各項ごとに排他的論理和を行います．

そうして得られた信号は元のM系列信号を何回かシフトした信号となります．

これが，シフト巡回性という定義です．

では，確認してみましょう．

上の二つの信号を各項ごとに排他的論理和をすると，以下のような信号が求められます．

$$ 110010001111010 $$

この信号，よく見てみると

$$ 11001\quad 0001111\quad 010 $$

この部分に初期値と同じ信号があります．

確認すると，元の信号を左に10回シフトした信号となっています．

定義まとめ

以上のことから生成された信号はM系列信号であることが確認できました．

以下に，M系列信号の定義をまとめます．

周期Tは$2^{n} -1$に従う．
1周期あたりに0が出現する回数は$2^{n-1}-1$
1が出現する回数は$2^{n-1}$
信号が連続してk回出現する回数は
k=nの時は1が連続して1回
k=n-1の時は0が連続して1回
それ以外の時は$2^{n-k-1}$回となる．
この時，0と1は同じ回数となる．
1周期分の信号と任意の回数左にシフトした信号の排他的論理和は，元の信号を数回シフトしたものと一致する．