m序列的生成算法研究.pdfVIP

m 序列的生成算法研究 马吉康, 张国花, 王梨, 史志亮 北京邮电大学计算机科学与技术学院，北京（100876 ） E-mail： majikang2193828@163.com 摘 要：本文实现了生成m 序列的矩阵法和长除法两种算法，并对长除法作了部分改进。最 后结合本原多项式法，对这三种算法作了比较，并给出了他们的使用范围。所有算法的实现 和相互比较都基于Matlab 实现。 关键词：m 序列，矩阵法，长除法，本原多项式 中图分类号：TP-301.6 1. 引言 [1] 近年来，扩频技术在无线通信中的应用和发展都非常迅速 。而最早用到的也最基础的 扩频码是m序列，它可以由线性反馈移位寄存器生成。其他伪随机码，如Gold码、M序列等 都是在m序列的基础上生成的。因此m序列的有效生成至关重要。 [2 ] [3] [2] 本文在通过对m序列特性 和相关数学理论 的研究，根据文献 的叙述归纳出两种m 序列的生成算法：矩阵法和长除法。但原来的长除法存在计算复杂繁琐和确定周期麻烦等缺 点，所以本文采取了移位计算来进行改进，改进后的算法不仅避免了原来的缺点，还便于算 法实现。最后结合本原多项式法[4]，在时间复杂度上对这三种算法进行了比较。给定寄存器 位数，这三种算法就能够生成所有的m序列，对扩频领域有一定的实用性。 2. 基础知识 m 序列是伪随机序列中最重要的序列之一，可通过线性反馈移位寄存器得到，设移位寄 存器结构如图1： + + + + + + c0 c 1 c2 L cr −1 cr a a a a n −1 n − 2 L n −( r -1 ) n − r 图1 线性反馈移位寄存器结构 在图1 中， 为 级寄存器的状态（为0 或1），反馈的连接状 an−1, an−2 ,L , an−(r −1) , an−r r 态由开关 表示， 表示反馈断开， ci ci 0 ci 1表示反馈接通，且cr c0 1 。寄存器的每 一级输出经反馈后作为最高位的输入 a 。反馈移位寄存器的序列多项式为 n ∞ G( x) a =+a x +a x2 +L +a xn +L ∑a xn ，a (n 0, 1, L ) 是二元素域，而特征 0 1 2 n n n n 0 r 多项式f (x ) c =+c x +c x 2 +L +c x r ∑c xi ，c c 1，c (0 ≤i ≤r) 是反馈系数