Ｍ系列の生成多項式

LFSR によるシーケンス生成

PN9 sequence
Ch.1: M-series, Ch.2: Correration
2026-08-01 改訂
2004-07-23
細田 隆之

Ｍ系列

デジタル通信分野で広く用いられているＭ系列(Maximum length sequence) と呼ばれる n ビットのシフトレジスタと フィードバックで生成される、周期が 2n - 1 の符号列がある。

回路構成

Ｍ系列生成回路は一般的にシフトレジスタに線形帰還をかけた LFSR (Linear Feedback Shift Register) で構成される。

LFSR はフィードバックの仕方で fig.1 に示す Fibonacci LFSR と fig.2 に示す Galois LFSR の２形式がある。

各図中の (＋) 印は排他的論理和（eXclusive-OR）である。 このシフトレジスタとフィードバックで形成している回路はつまり原始多項式での除算器であると言える。

Fibonacci model Linear Feedback Shift Registers Output
fig.1 A Fibonacci model LFSR and its Generator Polynomial
Galois model Linear Feedback Shift Registers Output
fig.2 A Galois model LFSR and its Generator Polynomial

特徴と用途

応用的には、デジタル通信や計測のさまざまなところに使われていて、例えば フレーム同期ワードやスクランブル、周波数拡散用の拡散符号や誤り率測定や測距や位置検出、 擬似雑音発生などに利用されている。

このように広く使われている訳は、Ｍ系列で生成されるビット列には、次のような特徴があるからである。

  1. 連続する 1 の長さは n 以下である
  2. 0 と 1 の発生個数が 1 周期で 1 だけ違う（0 と 1 の発生確率がほぼ同じ）
  3. 自己相関のピークが１周期に１度だけある。つまり、周期を N、ずれをτ として τ = k N (k = 0, 1, 2, …) の時 N で、それ以外のとき -1 である
  4. n ビットのＭ系列の 1 周期の中の連続する n ビットはユニークである

1, 2 番めの特徴はＭ系列の１周期の平均値が 2n - 1 / (2n - 1) であるということであって、 スクランブル等に利用されている。

3 番目の特徴はその１周期中に１度の大きな相関のため、雑音や誤りの影響があっても検知しやすく同期信号に多用されている。
また、周期を長く、つまり N を十分大きく取れば、ほとんどホワイトノイズに近似できるということでもある。(fig.4)

4 番目の特徴は、Ｍ系列中の n ビットから、ずれ τ が一意に決まるため、測距や絶対位置エンコーダーなどにも利用されている。

correlations
fig.3 自己相関の例 (n = 7)
PN9 FFT
fig.4 実際の波形の例(n = 9, 7.3728 Mbps)
Ch1 : Pseudo-random pattern for systems using 29 -1 pattern length
Ch2 : Correlation
Math: FFT (Hamming windowed)
同期ワード（Syncword）

現実的には、フレームのプレアンブルとの関係や、 その１周期の長さが 2n - 1 であるため、フレームで良く使われる 16 や 32 といった 2の冪の長さに合わず、 M系列の１周期がそのまま同期ワードとしてそのまま用いられることは多くない。
では、どのようなシーケンスが使われているかの一例を上げておく。

生成多項式

下に筆者の知る範囲でまとめた主な生成多項式を示す。

簡便のため生成多項式は最下位の 1 を省き係数が 1 の次数のみを表記する。

e.g. X 9 + X 4 + 1 → (9, 4)

係数の上位〜下位を入れ替えた生成多項式は互いに逆順の出力シーケンスとなるため、係数の小さい方のみを記載している。

但し、ITU-T の勧告では、この係数が大きい３項生成多項式を Fibonacci LFSR で用いているため、* 付きの太字で示してある。
e.g. 生成多項式 *(9,4) は (9,5) 即ち X 9 + X 5 + 1 を意味する。

次数: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
33, 35, 41, 47, 49, 52, 55, 57, 58, 61,
63, 65, 89, 127, 255, 521, 607, 756

REFFERENCES

  1. W. P. Horton, "Shift Counters," Computer Control Corporation.
  2. W. W. Peterson, "Error Correctiong Codes," MIT Press, Wiley, New York.
  3. R. C. White, Jr., "Experiments with Digital Computer Simulation of Pseudo-Random Noise Gerenatiors, " IEEE Trans. Elect. Comp., June 1967.
  4. M. Goresky and A. M. Klapper, "Fibonacci and Galois representations of feedback-with-carry shift registers," in IEEE Transactions on Information Theory, vol. 48, no. 11, pp. 2826-2836, Nov. 2002, doi: 10.1109/TIT.2002.804048.
  5. ITU-T O.151
  6. ITU-T O.153
  7. J. Lindner, "Binary sequences up to length 40 with best possible autocorrelation function," Electronics Letters, vol. 11, no. 21, p. 507, 16 Oct. 1975.
  8. S. Tyler and J. Loftsson, "Periodic Binary Sequences With Very Good Autocorrelation Properties," TDA Progress Report 42-82, pp. 143-158, Sep. 1985.
  9. A. N. Leukhin and E. N. Potehin, "Binary sequences with minimum peak sidelobe level up to length 68," arXiv preprint arXiv:1212.4930, 2012.

履歴

関連項目

  1. コセット型アブソリュートエンコーダ — グレイコード・Ｍ系列に次ぐ第３の方式のアブソリュートエンコーダ
  2. 簡易シリアル通信テスタ 及び AHDL 実例
www.finetune.co.jp [Mail] © 2000 Takayuki HOSODA.