M序列

[拼音]：M xulie

[外文]：M sequence

由 n级移位寄存器所能产生的周期最长的序列。这种序列必须由非线性移位寄存器产生，并且周期为2n（n为移位寄存器的级数）。例如，考察图中a的非线性反馈移位寄存器，其状态转移关系如表：

状态(ak-3，ak-2，ak-1)的接续状态是(ak-2，ak-1，ak)，其中ak=ak-3嘰ak-1嘰1嘰ak-2ak-1是一种非线性逻辑。从任一状态出发，例如从(000)出发，其接续状态恰好构成一个完全循环(图b)，由此产生一个周期为23=8的3级序列。M序列最早是用抽象的数学方法构造的。它出现于组合数学的一些数学游戏中，例如L.欧拉关于哥尼斯堡的七桥问题等。后来发现这种序列具有某些良好的伪随机特性。例如，M序列在一个周期中，0与1的个数各占一半。同时，同样长度的0游程与 1游程也各占一半。所有这些性质在数据通信、自动控制、光学技术和密码学诸领域中均有重要应用。M序列的理论有许多困难问题尚未解决。