用戶:AnthonyDonlon/wip/M-序列

M-序列,也稱最大長度序列(英文:Maximum length sequence),是一種偽隨機二進制序列

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

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

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

生成

編輯
 
在長度為 4 的反饋移位寄存器中,a3的下一個值是由a0a1的模2加法

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

 

其中 n 是時間索引,而 表示模-2加法。若使用布爾代數的FALSETRUE分別表示序列中的01,則其中的模-2加法等效與異或操作。

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

多項式解釋

編輯

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

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

實現

編輯

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

性質

編輯

M序列具有以下性質:[4]

均衡性

編輯

序列中01的出現頻率大致相同。具體地,周期為 的M-序列的一個周期中內包含 1 0。其中1的數目等於0的數目多1,因為LFSR中不可能包含全為零的狀態。

遊程特性

編輯

M-序列中連續的1或連續的0的子序列稱為一個遊程。遊程數是這樣的子序列的數目。  [<span title="This information is too vague. (February 2018)">模糊</span>] 在序列一個周期的所有遊程中 :

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

相關特性

編輯

M序列的循環自相關克羅內克δ函數[5][6] (具有直流偏移和時間延遲)。對於±1約定,即,分配了位值1  位值為0   ,將XOR映射到產品的負數:

 

其中 表示復共軛, 表示循環移位

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

脈衝響應提取

編輯

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

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

 

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

 

並假設φSS是脈衝(有效期長序列)

 

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

與阿達馬變換的關係

編輯

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

參見

編輯

參考文獻

編輯

外部連結

編輯

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

  1. ^ Poudel, Khem Narayan; Robertson, William M. Maximum length sequence dielectric multilayer reflector. OSA Continuum. 2018-10-15, 1 (2): 358–372. ISSN 2578-7519. doi:10.1364/OSAC.1.000358 (英語). 
  2. ^ Buracas GT, Boynton GM. Efficient design of event-related fMRI experiments using M-sequences. NeuroImage. July 2002, 16 (3 Pt 1): 801–13. PMID 12169264. doi:10.1006/nimg.2002.1116. 
  3. ^ "Linear Feedback Shift Registers- Implementation, M-Sequence Properties, Feedback Tables", New Wave Instruments (NW), Retrieved 2013.12.03.
  4. ^ Golomb, Solomon W. Shift register sequences. Holden-Day. 1967. ISBN 0-89412-048-4. 
  5. ^ Jacobsen, Finn; Juhl, Peter Moller. Fundamentals of General Linear Acoustics. John Wiley & Sons. 2013-06-04. ISBN 978-1118636176 (英語). A maximum-length sequence is a binary sequence whose circular autocorrelation (except for a small DC-error) is a delta function. 
  6. ^ Sarwate, D. V.; Pursley, M. B. Crosscorrelation properties of pseudorandom and related sequences. Proceedings of the IEEE. 1980-05-01, 68 (5): 593–619. ISSN 0018-9219. doi:10.1109/PROC.1980.11697. 
  7. ^ A Little MLS (Maximum-Length Sequence) Tutorial | dspGuru.com. dspguru.com. [2016-05-19]. its RMS and peak values are both X, making its crest factor (peak/RMS) equal to 1, the lowest it can get. 
  8. ^ Other Electro-Acoustical Measurement Techniques. www.clear.rice.edu. [2016-05-19]. The crest factor for MLS is very close to 1, so it makes sense to use this kind of input signal when we need a high signal-to-noise ratio for our measurement 
  9. ^ Chan, Ian H. Swept Sine Chirps for Measuring Impulse Response (PDF). thinksrs.com. [2016-05-19]. 
  10. ^ Friese, M. Multitone signals with low crest factor (PDF). IEEE Transactions on Communications. 1997-10-01, 45 (10): 1338–1344. ISSN 0090-6778. doi:10.1109/26.634697. 
  11. ^ Cohn, M.; Lempel, A. On Fast M-Sequence Transforms. IEEE Trans. Inf. Theory. January 1977, 23 (1): 135–7. doi:10.1109/TIT.1977.1055666.