《通信原理》-樊昌信-曹丽娜-编著第六版课件-第12章教案资料.ppt

,通信原理(第6版),单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,通信原理,1,通信原理,第12章 正交编码与伪随机序列,2,第12章 正交编码与伪随机序列,引言,正交编码与伪随机序列在数字通信技术中都是十分重要的。正交编码不仅可以用作纠错编码，还可以用来实现码分多址通信，目前已经广泛用于蜂窝网中。伪随机序列在误码率测量、时延测量、扩谱通信、密码及分离多径等方面都有着十分广泛的应用。因此，本章将在简要讨论正交编码概念之后，着重讨论伪随机序列及其应用。,3,第12章 正交编码与伪随机序列,12.2 正交编码,12.2.1 正交编码的基本概念,正交性,若两个周期为,T,的模拟信号,s,1,(,t,)和,s,2,(,t,)互相正交，则有,同理，若,M,个周期为,T,的模拟信号,s,1,(,t,)，,s,2,(,t,)，,s,M,(,t,)构成一个正交信号集合，则有,互相关系数,对于二进制数字信号，用一数字序列表示码组。这里，我们只讨论二进制且码长相同的编码。这时，两个码组的正交性可用如下形式的互相关系数来表述。,i,j,；,i,j,1,2,M,4,第12章 正交编码与伪随机序列,设长为,n,的编码中码元只取值+1和-1，以及,x,和,y,是其中两个码组：,其中,则,x,和,y,间的互相关系数定义为,若码组,x,和,y,正交，则必有,(,x,y,)=0。,5,第12章 正交编码与伪随机序列,正交编码,例如，下图所示4个数字信号可以看作是如下4个码组：,按照互相关系数定义式计算容易得知，,这4个码组中任意两者之间的相关系数,都为0，即这4个码组两两正交。我们,把这种两两正交的编码称为正交编码。,s,1,(,t,),s,2,(,t,),s,3,(,t,),s,4,(,t,),6,第12章 正交编码与伪随机序列,自相关系数,：,类似上述互相关系数的定义，可以对于一个长为,n,的码组,x,定义其自相关系数为,式中，,x,的下标按模,n,运算，即有,x,n,k,x,k,。例如，设,则有,7,第12章 正交编码与伪随机序列,用二进制数字表示互相关系数,在二进制编码理论中，常采用二进制数字“0”和“1”表示码元的可能取值。这时，若规定用二进制数字“0”代替上述码组中的“1”，用二进制数字“1”代替“1”，则上述互相关系数定义式将变为,式中，A,x,和,y,中对应码元相同的个数；,D,x,和,y,中对应码元不同的个数。,例如，按照上式规定，上面例子可以改写成,8,第12章 正交编码与伪随机序列,用二进制数字表示自相关系数,上式中，若用,x,的,j,次循环移位代替,y,，就得到,x,的自相关系数,x,(,j,)。具体地讲，令,代入定义式,就得到自相关系数,x,(,j,)。,9,第12章 正交编码与伪随机序列,超正交码和双正交码,超正交码,：,相关系数,的取值范围在,1之间，即有-1,+1。若两个码组间的相关系数,0，则称这两个码组互相超正交。如果一种编码中任两码组间均超正交，则称这种编码为超正交码。,例如，在上例中，若仅取后3个码组，并且删去其第一位，构成如下新的编码：,则不难验证，由这3个码组所构成的编码是超正交码。,10,第12章 正交编码与伪随机序列,双正交编码,由正交编码和其反码便可以构成双正交编码。,例：上例中正交码为,其反码为,上两者,的总体即构成如下双正交码：,(0,0,0,0)(1,1,1,1)(0,0,1,1)(1,1,0,0),(0,1,1,0)(1,0,0,1)(0,1,0,1)(1,0,1,0),此码共有8种码组，码长为4，任两码组间的相关系数为0或1。,11,第12章 正交编码与伪随机序列,12.2.2 阿达玛矩阵,定义：,阿达玛矩阵简记为,H,矩阵,。它是一种方阵，仅由元素+1和1构成，而且其各行（和列）是互相正交的。最低阶的,H,矩阵是2阶的，即,下面为了简单，把上式中的1和1简写为和，这样上式变成,12,第12章 正交编码与伪随机序列,阶数为2的幂的高阶,H,矩阵可以从下列递推关系得出,H,N,H,N,/2,H,2,式中，,N,2,m,；,直积。,上式中直积是指将矩阵,H,N,/2,中的每一个元素用矩阵,H,2,代替。例如：,13,第12章 正交编码与伪随机序列,上面给出几个,H,矩阵的例子，都是对称矩阵，而且第一行和第一列的元素全为“”。我们把这样的,H,矩阵称为阿达玛矩阵的,正规形式,，或称为,正规阿达玛矩阵,。,14,第12章 正交编码与伪随机序列,性质,在,H,矩阵中，交换任意两行，或交换任意两列，或改变任一行中每个元素的符号，或改变任一列中每个元素的符号，都不会影响矩阵的正交性质。因此，正规,H,矩阵经过上述各种交换或改变后仍为,H,矩阵，但不一定是正规的了。,按照递推关系式可以构造出所有2,k,阶的,H,矩阵。可以证明，高于2阶的,H,矩阵的阶数一定是4的倍数。不过，以4的倍数作为阶数是否一定存在,H,矩阵，这一问题并未解决。,H,矩阵是正交方阵。若把其中每一行看作是一个码组，则这些码组也是互相正交的，而整个,H,矩阵就是一种长为,n,的正交编码，它包含,n,个码组。因为长度为,n,的编码共有2,n,个不同码组，现在若只将这,n,个码组作为准用码组，其余(2,n,-,n,)个为禁用码组，则可以将其多余度用来纠错。这种编码在纠错编码理论中称为,里德-缪勒(Reed-Muller)码,。,15,第12章 正交编码与伪随机序列,12.2.3 沃尔什函数和沃尔什矩阵,沃尔什函数定义,式中,p,=0或1，,j,=0，1，2，,，及指数中的j/2表示取j/2的整数部分。,正弦和余弦函数可以构成一个完备正交函数系。由于正弦和余弦函数具有完备和正交性，所以由其构成的无穷级数或积分（即傅里叶级数和傅里叶积分）可以表示任一波形。类似地，由取值“1”和“1”构成的沃尔什函数也具有完备正交性，也可以用其表示任一波形,16,第12章 正交编码与伪随机序列,前8个沃尔什函数的波形示于下图中,+1,0,+1,0,-1,+1,0,-1,+1,0,-1,+1,0,-1,+1,0,-1,+1,0,-1,+1,0,-1,17,第12章 正交编码与伪随机序列,由于沃尔什函数的取值仅为“1”和“1”，所以可以用其离散的抽样值表示成矩阵形式。例如，上图中的8个沃尔什函数可以写成如下沃尔什矩阵：,由上图和矩阵可以看出，沃尔什矩阵是按照每一行中“1”和“1”的交变次数由少到多排列的。,沃尔什函数（矩阵）天生具有数字信号的特性，所以它们在数字信号处理和编码理论中有不小应用前景。,18,第12章 正交编码与伪随机序列,12.3 伪随机序列,12.3.1 基本概念,什么是伪随机噪声？,具有类似于随机噪声的某些统计特性，同时又能够重复产生的波形,。,优点：它具有随机噪声的优点，又避免了随机噪声的缺点，因此获得了日益广泛的实际应用。,如何产生伪随机噪声？,目前广泛应用的伪随机噪声都是由周期性数字序列经过滤波等处理后得出的。在后面我们将这种周期性数字序列称为伪随机序列。它有时又称为伪随机信号和伪随机码。,12.3.2,m,序列,m,序列的产生：,m,序列是最长线性反馈移位寄存器序列的简称。它是由带线性反馈的移存器产生的周期最长的一种序列。,19,第12章 正交编码与伪随机序列,例：下图中示出一个4级线性反馈移存器。,设其初始状态为(,a,3,a,2,a,1,a,0,)=(1,0,0,0)，则,在移位1次时，由,a,3,和,a,0,模2相加产生新的输入,a,4,=1,0=1，新的状,态变为(,a,4,a,3,a,2,a,1,)=(,1,1,0,0)。这样移位15,次后又回到初始状态(1,0,0,0)。,若初始状态为全“0”，即,(0,0,0,0)，则移位后得,到的仍为全“0”状态。应,该避免出现全“0”状态，,否则移存器的状态将不,会改变。,20,第12章 正交编码与伪随机序列,因为4级移存器共有2,4,=16种可能的状态。除全“0”状态外，只剩15种状态可用。这就是说，由任何4级反馈移存器产生的序列的周期最长为15。,我们常常希望用尽可能少的级数产生尽可能长的序列。由上例可见，一般来说，一个,n,级线性反馈移存器可能产生的最长周期等于(2,n,-1)。我们将这种最长的序列称为最长线性反馈移存器序列，简称,m,序列。,反馈电路如何连接才能使移存器产生的序列最长，这就是本节将要讨论的主题。,21,第12章 正交编码与伪随机序列,一般的线性反馈移存器原理方框图,图中各级移存器的状态用,a,i,表示，,a,i,=0或1，,i,整数。,反馈线的连接状态用,c,i,表示，,c,i,1表示此线接通（参加反馈）；,c,i,0表示此线断开。,反馈线的连接状态不同，就可能改变此移存器输出序列的周期,p,。,22,第12章 正交编码与伪随机序列,基本的关系式,递推方程,设一个,n,级移存器的初始状态为：,a,1,a,2,a,n,，经过1次移位后，状态变为,a,0,a,1,a,n,1,。经过,n,次移位后，状态为,a,n,1,a,n,2,a,0,，上图所示就是这一状态。再移位1次时，移存器左端新得到的输入,a,n,，按照图中线路连接关系，可以写为,因此，一般说来，对于任意一个输入,a,k,，有,称为递推方程,它给出移位输入,a,k,与移位前各级状态的关系。按照递推方程计算，可以用软件产生,m,序列，不必须用硬件电路实现。,23,第12章 正交编码与伪随机序列,特征方程,（特征多项式）,c,i,的取值决定了移存器的反馈连接和序列的结构，故,c,i,是一个很重要的参量。现在将它用下列方程表示：,特征方程,式中,x,i,仅指明其系数（1或0）代表,c,i,的值，,x,本身的取值并无实际意义，也不需要去计算,x,的值。例如，若特征方程为,则它仅表示,x,0,，,x,1,和,x,4,的系数,c,0,c,1,c,4,1，其余的,c,i,为0，即,c,2,c,3,0。按照这一特征方程构成的反馈移存器就是上图所示的。,24,第12章 正交编码与伪随机序列,母函数,我们也可以将反馈移存器的输出序列,a,k,用代数方程表示为,上式称为母函数。,递推方程、特征方程和母函数就是我们要建立的3个基本关系式。下面的几个定理将给出它们与线性反馈移存器及其产生的序列之间的关系。,25,第12章 正交编码与伪随机序列,定理,【,定理12.1,】,式中，,h,(,x,)为次数低于,f,(,x,)的次数的多项式。,【证】将递推方程代入母函数，得到,移项整理后，得到,26,第12章 正交编码与伪随机序列,将上式右端用符号,h,(,x,)表示，并因,c,0,1，故上式变成,式中,由此式可以看出，当电路给定后，,h,(,x,)仅决定于初始状态(,a,-i,a,-1,)。,再将特征方程代入上式，最后得出,27,第12章 正交编码与伪随机序列,在,中，若,a,1,=1，则,h,(,x,)的最高次项为,x,n,-1,；若,a,1,=0，则最高项次数 0，,f,2,(,x,)的次数为n,2,，n,2,0，,且有,30,第12章 正交编码与伪随机序列,令,则上式可以改写成,上式表明，输出序列,G,(,x,)可以看成是两个序列,G,1,(,x,)和,G,2,(,x,)之和，其中,G,1,(,x,)是由特征多项式,f,1,(,x,)产生的输出序列，,G,2,(,x,)是由特征多项式,f,2,(,x,)产生的输出序列。而且，由定理12.2可知，,G,1,(,x,)的周期为,G,2,(,x,)的周期为,所以，,G,(,x,)的周期,p,应是,p,1,和,p,2,的最小公倍数LCM,p,1,p,2,，即,上式表明，,p,一定小于最长可能周期(2,n,-1)。,若,f,(,x,)可以分解成两个相同的因子，即上面的,f,1,(,x,),f,2,(,x,)，同样可以证明p 2,n,1。,所以，若,f,(,x,)能分解因子，必定有,p,2,n,1。【证毕】,31,第12章 正交编码与伪随机序列,【,定理12.4,】一个,n,级移存器的特征多项式,f,(,x,)若为既约的，则由其产生的序列,A,=,a,k,的周期等于使,f,(,x,)能整除的(,x,p,+1)中最小正整数,p,。,【证】若序列,A,具有周期,p,，则有,上式移项整理后，变成,32,第12章 正交编码与伪随机序列,由定理12.1可知，,h,(,x,)的次数比,f,(,x,)的低，而且现已假定,f,(,x,)为既约的，所以上式表明(,x,p,+1)必定能被,f,(,x,)整除。,应当注意，此时序列,A,之周期,p,与初始状态或者说与,h,(,x,)无关。当然，这里不考虑全“0”作为初始状态。,上面证明了若序列,A,具有周期,p,，则(,x,p,+1)必能被,f,(,x,)整除。另一方面，若,f,(,x,)能整除(,x,p,+1)，令其商为,又因为在,f,(,x,)为既约的条件下，周期,p,与初始状态无关，现在考虑初始状态,a,1,a,2,a,n,1,0，a,n,1，由式,可知，此时有,h,(,x,)=1。故有,33,第12章 正交编码与伪随机序列,上式表明，序列,A,以,p,或,p,的某个因子为周期。若,A,以,p,的某个因子,p,1,为周期，,p,1,p,，则由式,已经证明(,x,p,1,+1)必能被,f,(,x,)整除。,所以，序列,A,之周期等于使,f,(,x,)能整除的中最小正整数,p,。【证毕】,34,第12章 正交编码与伪随机序列,本原多项式,定义：若一个,n,次多项式,f,(,x,)满足下列条件：,f,(,x,)为既约的；,f,(,x,)可整除(,x,m,+1)，,m,=2,n,1；,f,(,x,)除不尽(,x,q,+1)，,q,m,；,则称,f,(,x,)为本原多项式。,由定理12.4可以简单写出一个线性反馈移存器能产生,m,序列的,充要条件,为：,反馈移存器的特征多项式为本原多项式。,35,第12章 正交编码与伪随机序列,【例】要求用一个4级反馈移存器产生,m,序列，试求其特征多项式。,这时，,n,=4，故此移存器产生的,m,序列的长度为,m,=2,n,1=15。由于其特征多项式,f,(,x,)应可整除(,x,m,+1)=(,x,15,+1)，或者说，应该是(,x,15,+1)的一个因子，故我们将(,x,15,+1)分解因子，从其因子中找,f,(,x,)：,f,(,x,)不仅应为(,x,15,+1)的一个因子，而且还应该是一个4次本原多项式。上式表明，(,x,15,+1)可以分解为5个既约因子，其中3个是4次多项式。可以证明，这3个4次多项式中，前2个是本原多项式，第3个不是。因为,36,第12章 正交编码与伪随机序列,这就是说，(,x,4,+,x,3,+,x,2,+,x,+1)不仅可整除(,x,15,+1)，而且还可以整除(,x,5,+1)，故它不是本原的。于是，我们找到了两个4次本原多项式：和。由其中任何一个都可以产生,m,序列，用作为特征多项式构成的4级反馈移存器就是上图中给出的。,本原多项式表,由上述可见，只要找到了本原多项式，我们就能由它构成,m,序列产生器。但是寻找本原多项式并不是很简单的。经过前人大量的计算，已将常用本原多项式列成表备查。在下表中列出了部分已经找到的本原多项式。,37,第12章 正交编码与伪随机序列,n,本原多项式,n,本原多项式,代数式,8进制表示法,代数式,8进制表示法,2,3,4,5,6,7,8,9,10,11,12,13,x,2,+,x,+1,x,3,+,x,+1,x,4,+,x,+1,x,5,+,x,2,+1,x,6,+,x,+1,x,7,+,x,3,+1,x,8,+,x,4,+,x,3,+,x,2,+1,x,9,+,x,4,+1,x,10,+,x,3,+1,x,11,+,x,2,+1,x,12,+,x,6,+,x,4,+,x,+1,x,13,+,x,4,+,x,3,+,x,+1,7,13,23,45,103,211,435,1021,2011,4005,10123,20033,14,15,16,17,18,19,20,21,22,23,24,25,x,14,+,x,10,+,x,6,+,x,+1,x,15,+,x,+1,x,16,+,x,12,+,x,3,+,x,+1,x,17,+,x,3,+1,x,18,+,x,7,+1,x,19,+,x,5,+,x,2,+,x,+1,x,20,+,x,3,+1,x,21,+,x,2,+1,x,22,+,x,+1,x,23,+,x,5,+1,x,24,+,x,7,+,x,2,+,x,+1,x,25,+,x,3,+1,42103,100003,210013,400011,1000201,2000047,4000011,10000005,20000003,40000041,100000207,200000011,38,第12章 正交编码与伪随机序列,在制作,m,序列产生器时，移存器反馈线（及模2加法电路）的数目直接决定于本原多项式的项数。为了使,m,序列产生器的组成尽量简单，我们希望使用项数最少的那些本原多项式。,由表可见，本原多项式最少有3项（这时只需要用一个模2加法器）。对于某些,n,值，由于不存在3项的本原多项式，我们只好列入较长的本原多项式。,由于本原多项式的逆多项式也是本原多项式，例如，(,x,15,+1)的因子中的(,x,4,+,x,+1)与(,x,4,+,x,3,+1)互为逆多项式，即10011与11001互为逆码，所以在表中每一本原多项式可以组成两种,m,序列产生器。,39,第12章 正交编码与伪随机序列,在一些书刊中，有时将本原多项式用8进制数字表示。我们也将这种表示方法示于此表中右侧。例如，对于n=4表中给出“23”，它表示,2 3,0 1 00 1 1,c,5,c,4,c,3,c,2,c,1,c,0,即,c,0,=,c,1,=,c,4,=1，,c,2,=,c,3,=,c,5,=0。,40,第12章 正交编码与伪随机序列,m,序列的性质,均衡性,在,m,序列的一个周期中，“1”和“0”的数目基本相等。准确地说，“1”的个数比“0”的个数多一个。,【证】设一个,m,序列的周期为,m,=2,n,1，则此序列可以表示为,由于此序列中任何相继的,n,位都是产生此序列的,n,级移存器的一个状态，而且此移存器共有,m,个不同状态，所以可以把此移存器的这些相继状态列表，如下表所示。表中每一行为移存器的一个状态。,m,个相继的状态构成此,m,序列的一个周期。由此表直接看出，最后一列的元素按自上而下排列次序就构成上式中的,m,序列。自然，其他各列也构成同样的,m,序列，只是初始相位不同。,41,第12章 正交编码与伪随机序列,a,n-1,a,n,a,n+i-1,a,n-2,a,n-1,a,n-2,a,n-1,a,n+i-2,a,n-3,a,n-2,a,2,a,3,a,i+2,a,1,a,2,a,1,a,2,a,i+1,a,0,a,1,a,0,a,1,a,i,a,n-1,a,0,42,第12章 正交编码与伪随机序列,因为此表中每一元素为一位2进制数字，即,a,i,(0,1)，,i,=0,1,，(,m,-1)。所以表中每一位移存器状态可以看成是一个,n,位2进制数字。这,m,个不同状态对应1至(2,n,1)间的,m,个不同的2进制数字。由于1和,m,=(2,n,1)都是奇数，故1至(2,n,1)间这,m,个整数中奇数比偶数多1个。在2进制中，奇数的末位必为“1”，偶数的末位必为“0”，而此末位数字就是表中最后一列。故表中最右列的相继,m,个二进数字中“1”比“0”多一个。由于每列都构成一,m,序列，所以,m,序列中“1”比“0”多一个。【证毕】,43,第12章 正交编码与伪随机序列,游程分布,我们把一个序列中取值相同的那些相继的（连在一起的）元素合称为一个“,游程,”。在一个游程中元素的个数称为,游程长度,。例如，在前例中给出的,m,序列可以重写如下：,在其一个周期（,m,个元素）中，共有8个游程，其中长度为4的游程有1个，即“1 1 1 1”，长度为3的游程有1个，即“0 0 0”，长度为2的游程有2个，即“1 1”和“0 0”，长度为1的游程有4个，即两个“1”和两个“0”。,一般说来，在,m,序列中，长度为1的游程占游程总数的1/2；长度为2的游程占游程总数的1/4；长度为3的游程占1/8；.。,1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0,m,15,44,第12章 正交编码与伪随机序列,严格讲，长度为,k,的游程数目占游程总数的2,-,k,，其中1,k,(,n,-1),。而且在长度为,k,的游程中其中1,k,(,n,-2),，连“1”的游程和连“0”的游程各占一半。下面我们就来证明游程的这种分布规律。,【证】在上表中，每一行有,n,个元素。我们考虑恰好含有连续,k,个“1”的那些行，它们具有形状：,其中左侧(,k,+2)个元素中两端为“0”，中间全为“1”，这样就保证恰好含有连续,k,个“1”，而右侧的(,n,2,k,)个元素用“,”表示，它们可以任意取值“0”或“1”，不受限制。在上表的一个周期(,m,=2,n,1行)中，符合上式形式的行的数目，按排列组合理论可知，等于2,n,2,k,。,0 1 1 1,1 0,k,个,(,n,2,k,)个,（1,k,n,2),45,第12章 正交编码与伪随机序列,由反馈移存器产生,m,序列的原理可知，形式如上式的一行中的,k,个“1”，必定经过逐次位移最后输出，在输出序列中构成长度为,k,的一个连“1”游程。反之，输出序列中任何一个长度为,k,的连“1”游程，必然对应上表中这样的一行。所以，在,m,序列一个周期中长度为,k,的连“1”游程数目也等于2,n,k,2,。,同理，长度为,k,的连“0”游程数目也等于,2,n,k,2,。所以长度为,k,的游程总数（包括连“1”和连“0”的两种游程）等于,在序列的每一周期中，长度在1,k,(,n,-2)范围内的游程所包含的总码元数等于,上式求和计算中利用了下列算术几何级数公式：,46,第12章 正交编码与伪随机序列,因为序列的每一周期中共有(2,n,1)个码元，所以除上述码元外，尚余(2,n,1)(2,n,2,n,)=(2,n,1)个码元。这些码元中含有的游程长度，从上表观察分析可知，应该等于,n,和(,n,1)，即应有长为,n,的连“1”游程一个，长为(,n,1)的连“0”游程一个，这两个游程长度之和恰为(2n 1)。并且由此构成的序列一个周期中，“1”的个数恰好比“0”的个数多一个。,最后，我们得到，在每一周期中，游程总数为,计算上式求和时，利用了下列等比级数公式：,所以，长度为,k,的游程占游程总数的比例为,47,第12章 正交编码与伪随机序列,由于长度为,k,=(,n,1)的游程只有一个，它在游程总数2,n,-1,中占的比例为1/2,n,-1,=2,-(,n,-1),，所以上式仍然成立。因此，可将上式改写为,长度为,k,的游程所占比例=2,-,k,，1,k,(,n,1)【证毕】,48,第12章 正交编码与伪随机序列,移位相加特性,一个,m,序列,M,p,与其经过任意次延迟移位产生的另一个不同序列,M,r,模2相加，得到的仍是,M,p,的某次延迟移位序列,M,s,，即,M,p,M,r,=,M,s,现在分析一个,m,=7的,m,序列,M,p,作为例子。设,M,p,的一个周期为1110010。另一个序列,M,r,是,M,p,向右移位一次的结果，即,M,r,的一个相应周期为0121001。这两个序列的模2和为,1110010,0111001=1001011,上式得出的为,M,s,的一个相应的周期，它与,M,p,向右移位5次的结果相同。下面我们对,m,序列的这种移位相加特性作一般证明。,49,第12章 正交编码与伪随机序列,【证】设产生序列,M,p,的,n,级反馈移存器的初始状态如下图所示。,这一初始状态也就是上表中第一行的,a,0,a,1,a,2,a,n,-1,。由这一初始状态代入递推方程式得到移存器下一个输入为,若将序列,M,p,的初始状态的,r,次延迟移位作为序列,M,r,的初始状态，则将,M,r,的初始状态,a,r,a,r,+1,a,r,+2,a,n,+,r,+1,代入递推方程式，得到下一个输入：,50,第12章 正交编码与伪随机序列,将上两式相加（模2），得到,上式右端,n,个括弧中两元素模2相加的结果一定是上表中另一行的元素。这是因为表中的各行包含了除全“0”外的全部,n,位二进数字。设相加结果为,则上式可以改写为,上式表明(,a,n,+,a,n,+,r,)仍为原,n,级反馈移存器按另一初始状态(,a,i,+,n,-1,a,i,+,n,-2,a,i,+1,a,i,)产生的输入，这是因为,c,1,c,2,c,n,未改变，移存器的反馈线接法也未改变。这个初始状态比,M,p,的初始状态延迟了,i,位。故序列,M,p,和,M,r,之和是,M,p,经过延迟,i,位的移位序列。【证毕】,51,第12章 正交编码与伪随机序列,自相关函数,现在我们讨论,m,序列的自相关函数。由12.2节互相关系数定义式得知，,m,序列的自相关函数可以定义为：,式中,A,m,序列与其,j,次移位序列一个周期中对应元素相同的数目；,D,m,序列与其,j,次移位序列一个周期中对应元素不同的数目；,m,m,序列的周期。,上式还可以改写成如下形式：,52,第12章 正交编码与伪随机序列,由,m,序列的延迟相加特性可知，上式分子中的,a,i,a,i+j,仍为,m,序列的一个元素。所以上式分子就等于,m,序列一个周期中“0”的数目与“1”的数目之差。另外，由,m,序列的均衡性可知，,m,序列一个周期中“0”的数目比“1”的数目少一个。所以上式分子等于1。这样，就有,当,j,=0时，显然,(0)=1。所以，我们最后写成：,不难看出，由于,m,序列有周期性，故其自相关函数也有周期性，周期也是,m,，即,而且,(,j,)是偶函数，即有,53,第12章 正交编码与伪随机序列,上面数字序列的自相关函数,(,j,)只定义在离散的点上（,j,只取整数）。但是，若把,m,序列当作周期性连续函数求其自相关函数，则从周期函数的自相关函数的定义：,式中,T,0,s,(,t,),的周期，,可以求出其自相关函数,R,(,)的表示式为,54,按照上面的公式画出的,(,j,)和,R,(,)的曲线示于下图中。,图中的圆点表示,j,取整数时的,(,j,)取值，而折线是,R,(,)的连续曲线。可以看出，两者是重合的。由图还可以看出，当周期,T,0,非常长和码元宽度,T,0,/m,极小时，,R,(,)近似于冲激函数,(,t,)的形状。,由上述可知，,m,序列的自相关函数只有两种取值：,0,和,(1/,m,),。有时把这类序列称为,双值自相关,序列。,第12章 正交编码与伪随机序列,(,j,),T,0,R,(,),55,第12章 正交编码与伪随机序列,功率谱密度,信号的自相关函数与功率谱密度构成一对傅里叶变换。因此，很容易对,m,序列的自相关函数式作傅里叶变换，求出其功率谱密度,按照上式画出的曲线示于下图中。由此图可见，在,T,0,和,m/T,0,时，,P,s,(,),的特性趋于白噪声的功率谱密度特性。,56,第12章 正交编码与伪随机序列,伪噪声特性,我们对一正态分布白噪声取样，若取样值为正，则记为“”；若取样值为负，则记为“”。将每次取样所得极性排成序列，例如,这是一个随机序列，它具有如下,3,个基本性质：,序列中“”和“”的出现概率相等。,序列中长度为,1,的游程约占,1/2,；长度为,2,的游程约占,1/4,；长度为,3,的游程约占,1/8,；,.,。一般说来，长度为,k,的游程约占,1/2,k,。而且在长度为,k,的游程中，“”游程和“”游程约各占一半。,由于白噪声的功率谱密度为常数，功率谱密度的逆傅里叶变换，即自相关函数，为一冲激函数,(,),。当,0,时，,(,),0,。仅当,=0,时，,(,),是个面积为,1,的脉冲。,57,第12章 正交编码与伪随机序列,由于,m,序列的均衡性、游程分布和自相关特性与上述随机序列的基本性质极相似，所以通常将,m,序列称为伪噪声,(PN),序列，或称为伪随机序列。,但是，具有或部分具有上述基本性质的,PN,序列不仅只有,m,序列一种。,m,序列只是其中最常见的一种。除,m,序列外，,M,序列、二次剩余序列（或称为,Legendre,序列）、霍尔,(Hall),序列和双素数序列等都是,PN,序列。,58,第12章 正交编码与伪随机序列,59,第12章 正交编码与伪随机序列,12.3.3 其他伪随机序列简介,M,序列,定义：由非线性反馈移存器产生的周期最长的序列称为,M,序列。,由上节对,m,序列产生器的分析可知，一个,n,级,m,序列产生器只可能有,(2,n,1),种不同的状态。但是,n,级移存器最多可有,2,n,种状态，在,m,序列中不能出现的是全“,0”,状态。在线性反馈条件下，全“,0”,状态出现后，产生器的状态将不会再改变；但是在非线性反馈条件下，却不一定如此。因此，非线性反馈移存器的最长周期可达,2,n,，我们称这种周期长达,2,n,的序列为,M,序列,。,60,第12章 正交编码与伪随机序列,M,序列的产生方法,目前，如何产生,M,序列,的问题，尚未从理论上,完全解决，人们只找到,很少几种构造它的方法。,下面仅简单介绍利用,m,序列产生器构成,M,序列,产生器的方法。,首先观察右图中的例子。,它是一个,n,=4,级的,m,序,列产生器。图中给出了,它的,15,种状态。若使它,增加一个“,000”,状态，就,可变成,M,序列产生器了。,61,第12章 正交编码与伪随机序列,因为移存器中后级状态必须是由其前级状态移入而得，故此“,0000”,状态必须处于初始状态“,1000”,之前和“,0001”,状态之后。这就是说，我们需要将其递推方程修改为非线性方程，使“,0001”,状态代入新的递推方程后，产生状态“,0000”,（而不是“,1000”,），并且在“,0000”,状态代入后产生状态“,1000”,（而不是保持“,0000”,不变）。,修改前的递推方程为,为满足上述要求，修改后的递推方程应为,62,第12章 正交编码与伪随机序列,对于,n,级,m,序列产生器也一样。为使,n,级,m,序列产生器变成,M,序列产生器，也只需使其递推方程改为,有了递推方程，就不难构造出此,M,序列产生器。例如用这种方法得到的一个,4,级,M,序列产生器如下图所示。,63,第12章 正交编码与伪随机序列,M,序列的性质,M,序列与,m,序列类似，也在一定程度上具有噪声特性。它满足,m,序列的前两个性质，即：,在,M,序列的一个周期中，出现“,0”,与“,1”,的数目相等。,在,n,级,M,序列的一个周期中，游程共有,2,n,-1,个，其中长度为,k,的游程占,1/2,k,，,1,k,n,2,；长为,n,的游程有两个，没有长为,(,n,1),的游程。在同长的游程中，“,0”,游程和“,1”,游程各占一半。这两个性质的证明方法与,m,序列的一样。,但是，,M,序列不再具有,m,序列的移位相加特性及双值自相关特性。,64,第12章 正交编码与伪随机序列,M,序列的优点,M,序列与,m,序列相比，最主要的优点是数量大，即同样级数,n,的移存器能够产生的平移不等价,M,序列总数比,m,序列的大得多，且随,n,的增大迅速增加。在下表中给出了级数,n,与可能产生的两种序列数目的比较。,M,序列的数量虽然相当大，但是目前能够实际产生出来的,M,序列数目却还不很多。这还有待于今后继续研究。,n,1 2 3 4 5 6 7 8 9 10,m,序列数目,1 1 2 2 6 6 18 16 48 60,M,序列数目,1 1 2 16 2048 6.71088 1.44115 1.32922 2.26156 1.30935,10,7,10,17,10,36,10,74,10,151,65,第12章 正交编码与伪随机序列,二次剩余序列,定义：二次剩余又称平方剩余数，例如，,3,2,=9,；,9,被,7,除得到的余数是,2,，即有,3,2,=9,2(mod 7),则称,2,为模,7,的平方剩余数。,一般说来，如果能找到一个整数,x,，它使,x,2,i,(mod,p,),若此方程成立，我们就认为这个方程有解。满足此方程的,i,就是模,p,的二次剩余；否则，,i,就是模,p,的二次非剩余。当规定,a,0,=-1,，且,其中,p,为奇数，则称,a,i,为二次剩余序列，,i,=0,1,2,.,，其周期为,p,。,66,第12章 正交编码与伪随机序列,例：设,p,=19,，容易算出,12,1(mod 19),，,22,4(mod 19),，,32,9(mod 19),，,42,16(mod 19),，,52,6(mod 19),，,62,17(mod 19),，,72,11(mod 19),，,82,7(mod 19),，,92,5(mod 19),，,102,5(mod 19),，,112,7(mod 19),，,122,11(mod 19),，,132,17(mod 19),，,142,6(mod 19),，,152,16(mod 19),，,162,9(mod 19),，,172,4(mod 19),，,182,1(mod 19),。,因此，,1,、,4,、,5,、,6,、,7,、,9,、,11,、,16,、,17,是模,19,的二次剩余；而,2,、,3,、,8,、,10,、,12,、,13,、,14,、,15,、,18,是模,19,的非二次剩余。,67,第12章 正交编码与伪随机序列,这样，得到周期,p,=19,的二次剩余序列为：,式中,1,；,1,。,这种序列具有随机序列基本性质的第,1),条性质，但一般不具备第,2),条性质。当,p=4t 1,时（,t=,正整数），它是双值自相关序列，即具有近于随机序列基本性质第,3),条的性质；当,p,=4,t,+1,时，它不是双值自相关序列。但是若,p,很大，它仍具有近于第,3),条的性质。一般认为它也属于伪随机序列。,68,第12章 正交编码与伪随机序列,双素数序列,上述二次剩余序列的周期,p,为素数。在双素数序列中，周期,p,是两个素数,p,1,和,p,2,的乘积，而且,p,2,=,p,1,+2,，即有,定义：双素数序列,a,i,的定义为：,式中,(,i,，,p,)=1,表示,i,和,p,互为素数（最大公因子为,1,）。,69,第12章 正交编码与伪随机序列,例：设,p,1,=3,，,p,2,=5,，,p,=3,5=15,。这时在一个周期中满足,(,i,p,)=1,条件的,i,，即小于,15,且与,15,互素的正整数有：,1,、,2,、,4,、,7,、,8,、,11,、,13,、,14,。对于这些,i,值，可以计算出：,70,第12章 正交编码与伪随机序列,对这些,i,值作,(,i,/,p,1,)(,i,/,p,2,),的运算后，得出,a,1,=,a,2,=,a,4,=,a,8,=1,以及,a,7,=,a,11,=,a,13,=,a,14,=-1,。又因,i,=0,5=10(mod 5),，故,a,0,=,a,5,=,a,10,=1,。对于其余的,i,，有,a,3,=,a,6,=,a,9,=,a,12,=-1,。所以此双素数序列为：,式中 ,1,；,1,。,可以验证，双素数序列也基本满足随机序列的基本性质，所以也属于,PN,序列。,71,第12章 正交编码与伪随机序列,12.4,扩展频谱通信,分类：,直接序列,(DS),扩谱：它通常用一段伪随机序列（又称为伪码）表示一个信息码元，对载波进行调制。伪码的一个单元称为一个,码片,。由于码片的速率远高于信息码元的速率，所以已调信号的频谱得到扩展。,跳频,(FH),扩谱：它使发射机的载频在一个信息码元的时间内，按照预定的规律，离散地快速跳变，从而达到扩谱的