用戶:AnthonyDonlon/wip/M-序列

M-序列，也稱最大長度序列（英文：Maximum length sequence），是一種偽隨機二進制序列。

Ｍ-序列是使用具有最大周期的線性反饋移位寄存器生成的位序列。是因為它們是周期性的，並且再現了可以由移位寄存器表示的每個二進制序列（零向量除外）（即，對於長度為m的寄存器，它們生成一個序列長度2 ^m − 1）。M-序列的頻譜是平坦的，除了接近零的直流分量。

一個Ｍ序列可以用 Z/2Z 上的多項式環中不可約多項式的係數的表示。

M序列的實際應用包括測量脈衝響應（例如房間中混響的響應）。它還可用作推導採用直接序列擴頻或跳頻擴頻的傳輸系統、光介電多層反射器設計的數字通信系統中偽隨機序列的基礎，以及某些功能性磁共振成像（fMRI）的有效設計及實驗。

生成

在長度為 4 的反饋移位寄存器中，a₃的下一個值是由a₀和a₁的模2加法

Ｍ-序列使用具有最大周期的線性反饋移位寄存器生成。圖1顯示了具有4位移位寄存器的Ｍ-序列生成系統。每一個寄存器的變化可以使用以下遞歸關係表示：

${\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加法。若使用布爾代數的FALSE和TRUE分別表示序列中的0和1，則其中的模-2加法等效與異或操作。

由於MLS是周期性的，並且移位寄存器在每個可能的二進制值（零向量除外）中循環，因此寄存器可以初始化為任何狀態（零向量除外）。

多項式解釋

可以將GF(2)上的多項式與線性反饋移位寄存器關聯。它具有移位寄存器長度的度數，係數為0或1，與為異或門供電的寄存器的抽頭相對應。例如，對應於圖1的多項式為x ⁴ + X ¹ + 1。

LFSR生成的序列最大長度的必要和充分條件是其對應的多項式是本原的。

實現

MLS在硬件或軟件中實現起來比較方便，使用相對低階的反饋移位寄存器就可以生成長度較大的序列。如使用長度僅為20的移位寄存器即可生成長度為2²⁰ − 1（1,048,575）的M-序列。

性質

M序列具有以下性質：

均衡性

序列中0和1的出現頻率大致相同。具體地，周期為$2^{n}-1$的Ｍ-序列的一個周期中內包含$2^{n-1}$個1和$2^{n-1}-1$個0。其中1的數目等於0的數目多1，因為LFSR中不可能包含全為零的狀態。

遊程特性

Ｍ-序列中連續的1或連續的0的子序列稱為一個遊程。遊程數是這樣的子序列的數目。  在序列一個周期的所有遊程中 ：

• 長度為1的遊程佔總遊程數的1/2
• 長度為2的遊程佔總遊程數的1/4
• 長度為3的遊程佔總遊程數的1/8
• ...

相關特性

M序列的循環自相關是克羅內克δ函數 （具有直流偏移和時間延遲）。對於±1約定，即，分配了位值1 $s=+1$位值為0 $s=-1$ ，將XOR映射到產品的負數：

$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}}$

其中$s^{*}$表示復共軛，$[m+n]_{N}$表示循環移位。

此外，M序列的線性自相關函數近似於克羅內克δ函數。

脈衝響應提取

如果要使用MLS測量線性時不變（LTI）系統的脈衝響應，則可以通過與MLS進行圓形互相關來從測量的系統輸出y [ n ]中提取響應。這是因為對於零延遲，MLS的自相關為1，而對於所有其他延遲，MLS的自相關幾乎為零（ − 1 / N ，其中N為序列長度）；換句話說，隨着MLS長度的增加，MLS的自相關可以說接近單位脈衝功能。

如果系統的脈衝響應為h[n]，而MLS用s[n]表示，則

$y[n]=h[n]*s[n].\,$

在兩側取關於s[n]的互相關函數，

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

並假設_φSS是脈衝（有效期長序列）

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

具有脈衝自相關的任何信號都可以用於此目的，但是具有高波峰因數的信號（例如脈衝本身）會產生信噪比較差的脈衝響應。通常假定MLS將是理想信號，因為它僅由滿量程值組成，並且其數字波峰因數為最小值，即0 D b。 但是，經過模擬重建後，信號中的尖銳不連續性會產生很強的採樣間峰值，從而將波峰因數降低4-8 dB或更高，隨着信號長度的增加而增加，使其比正弦掃描差。 其他信號的波峰因數最小，但尚不清楚是否可以提高到3以上 D b。

與阿達馬變換的關係

Cohn 和 Lempel 證明了M-序列與阿達馬變換的關係。這種關係允許以類似於FFT的快速算法來計算M-序列的相關性。

參見

• 巴克碼
• 互補序列
• 聯邦標準1037C
• 頻率響應
• 黃金代碼
• 衝動反應
• 多項式環

參考文獻

• Golomb, Solomon W.; Guang Gong. Signal Design for Good Correlation: For Wireless Communication, Cryptography, and Radar. Cambridge University Press. 2005. ISBN 978-0-521-82104-9. Golomb, Solomon W.; Guang Gong. Signal Design for Good Correlation: For Wireless Communication, Cryptography, and Radar. Cambridge University Press. 2005. ISBN 978-0-521-82104-9.  Golomb, Solomon W.; Guang Gong. Signal Design for Good Correlation: For Wireless Communication, Cryptography, and Radar. Cambridge University Press. 2005. ISBN 978-0-521-82104-9.   

外部連結

• Bristow-Johnson, Robert. A Little MLS Tutorial.  — Short on-line tutorial describing how MLS is used to obtain the impulse response of a linear time-invariant system. Also describes how nonlinearities in the system can show up as spurious spikes in the apparent impulse response.
• Hee, Jens. Impulse response measurement using MLS (PDF).  — Paper describing MLS generation. Contains C-code for MLS generation using up to 18-tap-LFSRs and matching Hadamard transform for impulse response extraction.
• Kerr, Wesley. Creation of M-Sequences. Geoffrey Aguirre Lab. University of Pennsylvania. 
• Linear Feedback Shift Registers. New Wave Instruments. 2005.  — Properties of maximal length sequences, and comprehensive feedback tables for maximal lengths from 7 to 16,777,215 (3 to 24 stages), and partial tables for lengths up to 4,294,967,295 (25 to 32 stages).
• Schäfer, Magnus. Aachen Impulse Response Database. Institute of Communication Systems and Data Processing, RWTH Aachen University. October 2012.  A (binaural) room impulse response database generated by means of maximum length sequences]
• Efficient Shift Registers, LFSR Counters, and Long Pseudo-Random Sequence Generators — Obsolete (PDF). Xilinx. July 1996.  — Implementing lfsr's in FPGAs includes listing of taps for 3 to 168 bits

[[Category:多項式]] [[Category:伪随机性]]