User:AkaDonlon/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:伪随机性]]