跳转到内容

用户: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-序列的一个周期中内包含10。其中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.