伪随机序列及编码

指导教师:杨建国二零零七年十一月指导教师:杨建国二零零八年三月2盛威网：专业的计算机学习网站第十一章伪随机序列及其编码11.1伪随机序列的概念11.2正交码与伪随机码11.3伪随机序列的产生11.4m序列11.5M序列11.6Gold序列11.7正交沃尔什函数11.8伪随机序列的应用3盛威网：专业的计算机学习网站11.1伪随机序列的概念在通信技术中，随机噪声是造成通信质量下降的重要因素，因而它最早受到人们的关注。如果信道中存在着随机噪声，对于模拟信号来说，输出信号就会产生失真，对于数字信号来说，解调输出就会出现误码。另外，如果信道的信噪比下降，那么信道的传输容量将会受到限制。4盛威网：专业的计算机学习网站伪随机序列应当具有类似随机序列的性质。在工程上常用二元{0，1}序列来产生伪噪声码，它具有以下几个特点：(1)在随机序列的每一个周期内0和1出现的次数近似相等。(2)每一周期内，长度为n的游程取值(相同码元的码元串)出现的次数比长度为n+1的游程次数多一倍。(3)随机序列的自相关类似于白噪声自相关函数的性质。5盛威网：专业的计算机学习网站11.2正交码与伪随机码若M个周期为T的模拟信号s1(t)，s2(t)，…，sM(t)构成正交信号集合，则有jijittstsTji,0,d)()(0常数(11-1)设序列周期为p的编码中，码元只取值+1和-1,而x和y是其中两个码组:),,,(),,,(2121nnyyyyxxxx6盛威网：专业的计算机学习网站式中，xi,yi∈（+1，-1）,i=1,2,…，n,则x和y之间的互相关函数定义为11,),(pyxyxii(11-2)若码组x和y正交，则有ρ(x,y)=0。如果一种编码码组中任意两者之间的相关系数都为0，即码组两两正交，这种两两正交的编码就称为正交编码。由于正交码各码组之间的相关性很弱，受到干扰后不容易互相混淆，因而具有较强的抗干扰能力。7盛威网：专业的计算机学习网站类似地，对于长度为ρ的码组x的自相关函数定义为(11-3)对于{0，1}二进制码，式(11-2)的互相关函数定义可简化为ρ(x,y)=(A-D)/(A+D)=(A-D)/p(11-4)式中，A是x和y中对应码元相同的个数；D是x和y中对应码元不同的个数。式(11-3)ρx(j)=(A-D)/(A+D)=(A-D)/p(11-5)nijiixpxxj1)(8盛威网：专业的计算机学习网站式中，A是码字xi与其位移码字xi+j的对应码元相同的个数：D是对应码元不同的个数。伪随机码具有白噪声的统计特性，因此，(1)凡自相关函数具有nijiiniixjppxxjpxj1120101)(（11-6）形式的码，称为伪随机码，又称为狭义伪随机码。9盛威网：专业的计算机学习网站（2）凡自相关函数具有nijiiniixjapxxjpxj11201/01/)(（11-7）形式的码，称为广义伪随机码。狭义伪随机码是广义伪随机码的特例。10盛威网：专业的计算机学习网站11.3伪随机序列的产生编码理论的数学基础是抽象代数的有限域理论。一个有限域是指集合F元素个数是有限的，而且满足所规定的加法运算和乘法运算中的交换律、结合律、分配律等。常用的只含（0，1）两个元素的二元集F2,由于受自封性的限制，这个二元集只有对模二加和模二乘才是一个域。一般来说，对整数集Fp={0,1,2,…,p-1},若p为素数，对于模p的加法和乘法来说，Fp是一个有限域。11盛威网：专业的计算机学习网站可以用移位寄存器作为伪随机码产生器，产生二元域F2及其扩展域F2m中的各个元，m为正整数。可用域上多项式来表示一个码组，域上多项式定义为niiinnxaxaxaxaaxf02210def)(（11-8）称其为F的n阶多项式，加号为模二和。式中，ai是F的元，anxn称为f(x)的首项，an是f(x)的首项系数。记F域上所有多项式组成的集合为F(x)。12盛威网：专业的计算机学习网站若g(x)是F(x)中的另一多项式，miiixbxg0)(（11-9）如果n≥m，规定f(x)和g(x)miiiixbaxgxf0)()()(（11-10）其中,bm+1=bm+2=…=bn=0。规定f(x)和g(x)的模二乘为mniijiiijxbaxgxf00)()()(（11-11）13盛威网：专业的计算机学习网站若g(x)≠0，则在F(x)总能找到一对多项式q(x)(称为商)和r(x)(称为余式)使得f(x)=q(x)g(x)+r(x)（11-12）这里r(x)的阶数小于g(x)的阶数。式（11-12）称为带余除法算式，当余式r(x)=0,就说f(x)可被g(x)整除。14盛威网：专业的计算机学习网站图11-1是一个4级移位寄存器，用它就可产生伪随机序列。规定移位寄存器的状态是各级存数从右至左的顺序排列而成的序列，这样的状态叫正状态或简称状态；反之，称移位寄存器状态是各级存数从左至右的顺序排列而成的序列叫反状态。图11-143nnnaaa(11-13)15盛威网：专业的计算机学习网站图11-14级移位寄存器16盛威网：专业的计算机学习网站当移位寄存器的初始状态是1000时，即an-4=1,an-3=0,an-2=0,an-1=0,经过一个时钟节拍后，各级状态自左向右移到下一级，末级输出一位数，与此同时模二加法器输出加到移位寄存器第一级，从而形成移位寄存器的新状态，下一个时钟节拍到来又继续上述过程，末级输出序列就是伪随机序列。在这种条件下，图11-1产生的伪随机序列是{an-4}=1000100110101111000100110101111…P=15这是一个周期长度p=15的随机序列。17盛威网：专业的计算机学习网站当图11-1的初始状态是0状态时，即an-4=an-3=an-2=an-1=0移存器的输出是一个0序列。4级移存器共有16个状态，除去一个0状态外，还有15个状态。对于图11-1来说，只要随机序列的周期达到最大值，这时无论如何改变移存器的初始状态，其输出只改变序列的初相，序列的排序规律不会改变。但是，如果改变图11-1四级移存器的反馈逻辑，其输出序列就会发生变化。例如，当反馈逻辑变成42nnnaaa(11-14)18盛威网：专业的计算机学习网站时，给定不同的初始状态1111、0001、1011，可以得到三个完全不同的输出序列111100111100…，000101000001…，101101101101它们的周期分别是6、6和3。19盛威网：专业的计算机学习网站由此，我们可以得出以下几点结论：（1）线性移位寄存器的输出序列是一个周期序列。（2）当初始状态是0状态时，线性移位寄存器的输出是一个0序列。（3）级数相同的线性移位寄存器的输出序列与寄存器的反馈逻辑有关。（4）序列周期p2n-1(n级线性移位寄存器)的同一个线性移存器的输出还与起始状态有关。（5）序列周期p=2n-1的线性移位寄存器，改变移位寄存起初始状态只改变序列的起始相位，而周期序列排序规律不变。20盛威网：专业的计算机学习网站11.4m序列11.4.1线性反馈移位寄存器的特征多项式1.线性反馈移位寄存器的递推关系式递推关系式又称为反馈逻辑函数或递推方程。设图11-2所示的线性反馈移位寄存器的初始状态为(a0a1…an-2an-1)，经一次移位线性反馈，移位寄存器左端第一级的输入为niininnnnnacacacacaca1011221121盛威网：专业的计算机学习网站若经k次移位，则第一级的输入为niililaca1(11-15)其中，l=n+k-1≥n,k=1,2,3,…由此可见，移位寄存器第一级的输入，由反馈逻辑及移位寄存器的原状态所决定。式(11-15)称为递推关系式。22盛威网：专业的计算机学习网站图11-2m序列的线性反馈移位寄存器的一般结构图23盛威网：专业的计算机学习网站2.线性反馈移位寄存器的特征多项式用多项式f(x)来描述线性反馈移位寄存器的反馈连接状态：niiinnxcxcxccxf010)((11-16)式(11-16)称为特征多项式或特征方程。其中，xi存在，表明ci=1，否则ci=0，x本身的取值并无实际意义。ci的取值决定了移位寄存器的反馈连接。由于c0=cn=1，因此，f(x)是一个常数项为1的n次多项式，n为移位寄存器级数。24盛威网：专业的计算机学习网站可以证明，一个n级线性反馈移位寄存器能产生m序列的充要条件是它的特征多项式为一个n次本原多项式。若一个n次多项式f(x)满足下列条件:(1)f(x)为既约多项式(即不能分解因式的多项式)(2)f(x)可整除(xp+1),p=2n-1;(3)f(x)除不尽(xq+1),qp。则称f(x)为本原多项式。以上为我们构成m序列提供了理论根据。25盛威网：专业的计算机学习网站11.4.2m用线性反馈移位寄存器构成m序列产生器，关键是由特征多项式f(x)来确定反馈线的状态，而且特征多项式f(x)必须是本原多项式。现以n=4为例来说明m序列产生器的构成。用4级线性反馈移位寄存器产生的m序列，其周期为p=24-1=15，其特征多项式f(x)是4次本原多项式，能整除(x15+1)。先将(x15+1)分解因式，使各因式为既约多项式，再寻找f(x)。)1)(1()1)(1)(1(1234344215xxxxxxxxxxxx26盛威网：专业的计算机学习网站其中，4次既约多项式有3个，但(x4+x3+x2+x+1)能整除(x5+1)，故它不是本原多项式。因此找到两个4次本原多项式(x4+x+1)和(x4+x3+1)。由其中任何一个都可产生m序列。用f(x)=(x4+x+1)构成的m序列产生器如图11-3所示。27盛威网：专业的计算机学习网站图11-3m序列产生器a31a22＋a13a04ak1000110011101111011110110101101011010110001110010100001000011000…………28盛威网：专业的计算机学习网站设4级移位寄存器的初始状态为1000。c4=c1=c0=1,c3=c2=0。输出序列{ak}的周期长度为15。29盛威网：专业的计算机学习网站11.4.3m序列的性质1.均衡特性(平衡性)m序列每一周期中1的个数比0的个数多1个。由于p=2n-1为奇数，因而在每一周期中1的个数为(p+1)/2=2n-1(偶数)，而0的个数为(p-1)/2=2n-1-1(奇数)。上例中p=15,1的个数为8，0的个数为7。当p足够大时，在一个周期中1与0出现的次数基本相等。30盛威网：专业的计算机学习网站2.游程特性(游程分布的随机性)我们把一个序列中取值(1或0)相同连在一起的元素合称为一个游程。在一个游程中元素的个数称为游程长度。例如图11-2中给出的m序列{ak}=000111101011001…在其一个周期的15个元素中，共有8个游程，其中长度为4的游程1个，即1111;长度为3的游程1个，即000；长度为2的游程2个，即11与00；长度为1的游程4个，即2个1与2个0。31盛威网：专业的计算机学习网站m序列的一个周期(p=2n-1)中，游程总数为2n-1。其中，长度为1的游程个数占游程总数的1/2；长度为2的游程个数占游程总数的1/22=1/4；长度为3的游程个数占游程总数的1/23=1/8；等等。一般地，长度为k的游程个数占游程总数的1/2k=2-k，其中1≤k≤(n-2)。而且，在长度为k的游程中，连1游程与连0游程各占一半，长为(n-1)的游程是连0游程，长为n的游程是连1游程。32盛威网：专业的计算机学习网站3.移位相加特性(线性叠加性)m序列和它的位移序列模二相加后所得序列仍是该m序列的某个位移序列。设mr是周期为p的m