人類の全ての活動がリモートで可能かどうか試されている今、リモートで再生される音声を同期させたいということもあるかと思います。リモート演奏等。
そこでM系列符号で自己同期を取る方法を思い出しましたので、簡単にご紹介します。
M系列符号とは
M系列符号とは、nビットのシフトレジスタから生成される周期が2^n-1の符号列なのですが、とても便利な特徴があります。
- 自己相関のピークが1周期に1回（ぴったり合った時）だけあり、それ以外は-1（相関ほぼ無し）になる。
- 0と1の発生確率がほぼ等しい。（擬似ノイズとしても使える）
この自己相関の特徴が、同期を取るのに大変便利なので、同期処理や測位など幅広く使われています。
自己相関のイメージ図を書きます。3ビットのシフトレジスタから生成された7ビットのM系列符号の例です。
7ビットのM系列符号を１ビットずつずらし、各ビットをXOR計算して加算したものが自己相関です。(XORで0の場合に-1を加算します。）上の図のようにぴったり合ってる場所だけが自己相関値が７になり、その他は-1（3勝4敗）になります。ほぼ無相関です。これを使えば、どこが始まりかわからない信号でも先頭を検出できます。
M系列符号生成のサンプルプログラム
M系列符号は、生成多項式から構成されるシフトレジスタの出力で作れるのですが、下記のようなプログラムで生成できます。生成多項式x^8 + x^4 + x^3 + x^2 + 1で生成する255ビットのM系列符号の例です。
#define SpreadingRate (255)
#define Generator (11101)
#define MaxBit (0x0100)
#define XorBit (0x011d)
char * code_generator()
{
int i;
char *code;
unsigned int shift = Generator;
code = (char *)calloc(SpreadingRate, sizeof(char));
for(i = 0; i < SpreadingRate; i++){
if(shift & 0x01){
code[i] = 1;
}else{
code[i] = 0;
}
shift = shift << 1;
if(shift & MaxBit){
shift = shift ^ XorBit;
}
}
return(code);
}
SpreadingRateは符号ビット長になり、生成多項式の次元数nの2^n-1になります。Generatorは、シフトレジスタの初期値なので何でも良いです。変えると符号ビット列が巡回します。MaxBitは最高次のみ1とするビット列で、XorBitは最高次を含めた各係数のビット列です。
M系列符号の自己同期で遊んでみました
M系列符号を音声信号にしてスピーカから送信し、マイクで録音して自己同期をとるという遊びをしてみました。図に書きます。
encoderは、M系列符号を音響信号にしてWaveファイルを生成します。このWaveファイルをスピーカで再生し、マイクで録音してWaveファイルにします。この録音Waveファイルをdecoderで自己相関計算し、ピーク（同期ポイント）が検出できるかをやってみました。
こちらが1サンプルずつずらして自己相関を計算した相関値です。あるポイントだけ鋭いピークが立っているので、ここがM系列符号の始まりだということがわかります。反射波などがあれば、他の場所にも少しピークが立ちます。つまり音響経路のインパルス応答と見なせます。
ちなみにM系列符号は、下図の左側のようにそのまま矩形波で送っても良いですし、右側のように位相変調して送っても同じ信号で相関を取ればよいのでどちらでも可能です。
この遊びのサンプルプログラムをこちらにおきますので、何かお役に立てそうでしたらお使いください。