用户:AnthonyDonlon/wip/M-序列
M-序列,也称最大长度序列(英文:Maximum length sequence),是一种伪随机二进制序列。
M-序列是使用具有最大周期的线性反馈移位寄存器生成的位序列。是因为它们是周期性的,并且再现了可以由移位寄存器表示的每个二进制序列(零矢量除外)(即,对于长度为m的寄存器,它们生成一个序列长度2 m − 1)。M-序列的频谱是平坦的,除了接近零的直流分量。
一个M序列可以用 Z/2Z 上的多项式环中不可约多项式的系数的表示。
M序列的实际应用包括测量脉冲响应(例如房间中混响的响应)。它还可用作推导采用直接序列扩频或跳频扩频的传输系统、光介电多层反射器设计的数字通信系统中伪随机序列的基础[1],以及某些功能性磁共振成像(fMRI)的有效设计及实验[2]。
生成
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/0/01/MLS_shiftregisters_L4.png/350px-MLS_shiftregisters_L4.png)
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.