最大長シーケンス

最大長シーケンス( MLS ) は、疑似ランダム 2 進シーケンスの一種です。

これらは最大線形フィードバックシフトレジスタを使用して生成されるビットシーケンスであり、周期的であり、シフトレジスタによって表すことができるすべてのバイナリシーケンス（ゼロベクトルを除く）を再現するため、このように呼ばれています（つまり、長さがmのレジスタの場合、長さが2 ^m − 1のシーケンスを生成します）。MLSは、 nシーケンスまたはmシーケンス と呼ばれることもあります。MLSは、ほぼゼロのDC項を除いて、 スペクトル的に平坦です。

これらの数列は、 Z/2Z上の多項式環の既約多項式の係数として表すことができます。

MLSの実際の応用としては、インパルス応答（例えば、室内の残響や海中の曳航音源からの到着時間など）の測定などが挙げられる^{[1] 。また、}直接拡散スペクトルや周波数ホッピング拡散スペクトル 伝送システムを採用したデジタル通信システムで疑似ランダムシーケンスを導出するための基礎として、また一部のfMRI実験の効率的な設計にも使用されている^[2]。

MLS は最大線形フィードバックシフトレジスタを使用して生成されます。長さ 4 のシフトレジスタを持つ MLS 生成システムを図 1 に示します。これは次の再帰関係を使用して表現できます。

${\displaystyle {\begin{cases}a_{3}[n+1]=a_{0}[n]+a_{1}[n]\\a_{2}[n+1]=a_{3}[n]\\a_{1}[n+1]=a_{2}[n]\\a_{0}[n+1]=a_{1}[n]\\\end{cases}}}$

ここで、n は時間インデックスであり、モジュロ 2 の加算を表します。ビット値 0 = FALSE または 1 = TRUE の場合、これは XOR 演算と同等です。 ${\displaystyle +}$

MLS は周期的であり、シフト レジスタはすべての可能なバイナリ値 (ゼロ ベクトルを除く) を循環するため、レジスタはゼロ ベクトルを除く任意の状態に初期化できます。

GF(2)上の多項式は、線形フィードバック シフト レジスタに関連付けることができます。この多項式は、シフト レジスタの長さの次数を持ち、係数は 0 または 1 で、XOR ゲートに入力されるレジスタのタップに対応します。たとえば、図 1 に対応する多項式は です。 ${\displaystyle x^{4}+x+1}$

LFSRによって生成されるシーケンスが最大長になるための必要かつ十分な条件は、対応する多項式が原始的であることである。^[3]

MLS はハードウェアまたはソフトウェアで実装するのに安価であり、比較的低次のフィードバック シフト レジスタは長いシーケンスを生成できます。長さ 20 のシフト レジスタを使用して生成されるシーケンスの長さは 2 ²⁰  − 1 サンプル (1,048,575 サンプル) です。

MLSはソロモン・ゴロムによって定式化された以下の特性を持つ。^[4]

シーケンス内の 0 と 1 の出現はほぼ同じである必要があります。より正確には、長さの最大長シーケンスには1 と0があります。0 のみの状態は発生しないため、1 の数は 0 の数に 1 を加えた数に等しくなります。 ${\displaystyle 2^{n}-1}$${\displaystyle 2^{n-1}}$${\displaystyle 2^{n-1}-1}$

「ラン」とは、関係する MLS 内の連続する「1」または連続する「0」のサブシーケンスです。ランの数は、そのようなサブシーケンスの数です。^[曖昧]

シーケンス内のすべての「ラン」（「1」または「0」で構成）のうち、

• ランの半分の長さは 1 です。
• ランの 4 分の 1 は長さ 2 です。
• ランの 8 分の 1 の長さは 3 です。
• ...などなど...

MLSの円自己相関はクロネッカーデルタ関数^{[5] [6]}である（実装に応じてDCオフセットと時間遅延を伴う）。±1規則の場合、つまりビット値1が割り当てられ、ビット値0が割り当てられ、XORが積の負にマッピングされます。 ${\displaystyle s=+1}$${\displaystyle s=-1}$

${\displaystyle R(n)={\frac {1}{N}}\sum _{m=1}^{N}s[m]\,s^{*}[m+n]_{N}={\begin{cases}1&{\text{if }}n=0,\\-{\frac {1}{N}}&{\text{if }}0<n<N.\end{cases}}}$

ここで は複素共役を表し、 は円シフトを表します。 ${\displaystyle s^{*}}$${\displaystyle [m+n]_{N}}$

MLS の線形自己相関はクロネッカー デルタに近似します。

線形時不変(LTI) システムのインパルス応答を MLS を使用して測定する場合、 MLS との循環相互相関を取ることで、測定されたシステム出力y [ n ] から応答を抽出できます。これは、MLS の自己相関がゼロ遅延の場合は 1 であり、他のすべての遅延の場合はほぼゼロ (-1/ N、Nはシーケンス長) であるためです。言い換えると、MLS の自己相関は、MLS の長さが長くなるにつれて単位インパルス関数に近づくと言えます。

システムのインパルス応答がh [ n ]でMLSがs [ n ]の場合、

${\displaystyle y[n]=(h*s)[n].\,}$

両辺の s [ n ]に関する相関をとると、

${\displaystyle {\phi }_{sy}=h[n]*{\phi }_{ss}\,}$

φ _{ss が}インパルスであると仮定すると（長いシーケンスに有効）

${\displaystyle h[n]={\phi }_{sy}.\,}$

インパルス的な自己相関を持つ信号であればどれでもこの目的に使用できますが、インパルス自体のような波高率の高い信号は、信号対雑音比の悪いインパルス応答を生成します。MLSはフルスケール値のみで構成され、デジタル波高率は最小の0 dBであるため、MLSが理想的な信号であると一般的に考えられています。^{[7] [8]} しかし、アナログ再構成後、信号の急激な不連続性によって強いサンプル間ピークが生成され、波高率が4～8 dB以上低下し、信号長とともに増加して、正弦波スイープよりも悪くなります。^[9] 他の信号は波高率が最小限になるように設計されていますが、3 dBを超えて改善できるかどうかは不明です。^[10]

CohnとLempel ^{[11]は、MLSと}アダマール変換の関係を示した。この関係により、FFTに似た高速アルゴリズムでMLSの相関を計算することができる。

• バーカーコード
• 相補的配列
• 連邦規格 1037C
• 周波数応答
• ゴールドコード
• インパルス応答
• 多項式環

• Golomb, Solomon W.; Guang Gong (2005)。良好な相関のための信号設計: 無線通信、暗号化、レーダー用。ケンブリッジ大学出版局。ISBN 978-0-521-82104-9。

• Bristow-Johnson、Robert。「MLS の簡単なチュートリアル」。— MLS を使用して線形時間不変システムのインパルス応答を取得する方法を説明した短いオンライン チュートリアル。また、システム内の非線形性が、見かけ上のインパルス応答に偽のスパイクとして現れる可能性がある方法についても説明します。
• Hee, Jens. 「MLS を使用したインパルス応答測定」(PDF)。 — MLS 生成について説明した論文。最大 18 タップの LFSR と、インパルス応答抽出用のマッチング アダマール変換を使用した MLS 生成の C コードが含まれています。
• Schäfer, Magnus (2012 年 10 月)。「Aachen Impulse Response データベース」。RWTH Aachen University 通信システムおよびデータ処理研究所。V1.4。最大長シーケンスによって生成された (バイノーラル) 室内インパルス応答データベース。
• 「効率的なシフト レジスタ、LFSR カウンター、および長い疑似ランダム シーケンス ジェネレーター - 廃止」(PDF)。Xilinx。1996 年 7 月。XAPP052 v1.1。— FPGA での lfsr の実装には、3 ～ 168 ビットのタップのリストが含まれます。