使用者:AnthonyDonlon/wip/M-序列
M-序列,也稱最大長度序列(英文:Maximum length sequence),是一種偽隨機二進制序列。
M-序列是使用具有最大周期的線性反饋移位寄存器生成的位序列。是因為它們是周期性的,並且再現了可以由移位寄存器表示的每個二進制序列(零矢量除外)(即,對於長度為m的寄存器,它們生成一個序列長度2 m − 1)。M-序列的頻譜是平坦的,除了接近零的直流分量。
一個M序列可以用 Z/2Z 上的多項式環中不可約多項式的係數的表示。
M序列的實際應用包括測量脈衝響應(例如房間中混響的響應)。它還可用作推導採用直接序列擴頻或跳頻擴頻的傳輸系統、光介電多層反射器設計的數字通信系統中偽隨機序列的基礎[1],以及某些功能性磁共振成像(fMRI)的有效設計及實驗[2]。
生成
編輯M-序列使用具有最大周期的線性反饋移位寄存器生成。圖1顯示了具有4位移位寄存器的M-序列生成系統。每一個寄存器的變化可以使用以下遞歸關係表示:
其中 n 是時間索引,而
表示模-2加法。若使用布爾代數的FALSE
和TRUE
分別表示序列中的0
和1
,則其中的模-2加法等效與異或操作。
由於MLS是周期性的,並且移位寄存器在每個可能的二進制值(零矢量除外)中循環,因此寄存器可以初始化為任何狀態(零矢量除外)。
多項式解釋
編輯可以將GF(2)上的多項式與線性反饋移位寄存器關聯。它具有移位寄存器長度的度數,係數為0或1,與為異或門供電的寄存器的抽頭相對應。例如,對應於圖1的多項式為x 4 + X 1 + 1。
LFSR生成的序列最大長度的必要和充分條件是其對應的多項式是本原的。 [3]
實現
編輯MLS在硬件或軟件中實現起來比較方便,使用相對低階的反饋移位寄存器就可以生成長度較大的序列。如使用長度僅為20的移位寄存器即可生成長度為220 − 1(1,048,575)的M-序列。
性質
編輯M序列具有以下性質:[4]
均衡性
編輯序列中0
和1
的出現頻率大致相同。具體地,周期為 的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-序列的相關性。
參見
編輯參考文獻
編輯- 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:伪随机性]]
- ^ 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 (英語).
- ^ 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.
- ^ "Linear Feedback Shift Registers- Implementation, M-Sequence Properties, Feedback Tables", New Wave Instruments (NW), Retrieved 2013.12.03.
- ^ Golomb, Solomon W. Shift register sequences. Holden-Day. 1967. ISBN 0-89412-048-4.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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
- ^ Chan, Ian H. Swept Sine Chirps for Measuring Impulse Response (PDF). thinksrs.com. [2016-05-19].
- ^ 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.
- ^ 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.