第10章正交编码与伪随机序列

1、第,10,章,正交编码与伪随机序列,第,10,章,正交编码与伪随机序列,10.1,引言,10.2,正交编码,10.3,伪随机序列,10.4,伪随机序列的应用,第,10,章,正交编码与伪随机序列,10.1,引言,正交编码,应用：,用作纠错码；还可用来实现码分多址通信。,伪随机序列,应用：,在误码率测量、时延测量、扩谱通信、通信加密及分离,多径等方面都有广泛的应用。,第,10,章,正交编码与伪随机序列,10.2,正交编码,1.,模拟信号,正交性,若两个周期为,T,的模拟信号,s,1,(,t,),和,s,2,(,t,),互相正交,，则,?,T,0,s,1,(,t,),s,2,(,t,),dt,?,0

2、,若,M,个周期为,T,的模拟信号,s,1,(,t,),，,s,2,(,t,),，,，,s,M,(,t,),构成一,正交,信号集合,，则有,?,T,0,s,i,(,t,),s,j,(,t,),dt,?,0,i,?,j,;,i,j,?,1,2,?,M,2.,互相关系数,两个码组：,x,?,(,x,1,x,2,?,x,n,),y,?,(,y,1,y,2,?,y,n,),x,i,y,i,?,?,1,?,1,i,?,1,2,?,n,1,n,?,(,x,y,),?,?,x,i,y,i,;,?,1,?,?,(,x,y,),?,1,n,i,?,1,x,和,y,间的,互相关系数,为,第,10,章,正交编码与伪

3、随机序列,若码组,x,和,y,正交,，则必有,?,(,x,y,),?,0,图中,4,个数字信号为,?,?,s,1,(,t,),:,(,?,1,?,1,?,1,?,1,),?,?,s,2,(,t,),:,(,?,1,?,1,?,1,?,1,),?,s,3,(,t,),:,(,?,1,?,1,?,1,?,1,),?,?,s,4,(,t,),:,(,?,1,?,1,?,1,?,1,),这,4,个码组中任意两者之间的,互相关,都为零，,这,4,个码组两两正交。,把两两正交的编码称为,正交编码,。,系数,第,10,章,正交编码与伪随机序列,3.,自相关系数,n,1,?,x,(,j,),?,?,x,i,x

4、,i,?,j,;,j,?,0,1,?,(,n,?,1,);,x,n,?,k,?,x,k,n,i,?,1,设,x,?,(,x,1,x,2,x,3,x,4,),?,(,?,1,?,1,?,1,?,1,),1,2,?,x,(,0,),?,?,x,i,?,1,4,i,?,1,1,4,1,1,?,x,(,1,),?,?,x,i,x,i,?,1,?,(,x,1,x,2,?,x,2,x,3,?,x,3,x,4,?,x,4,x,1,),?,(,?,1,?,1,?,1,?,1,),?,0,4,i,?,1,4,4,1,1,1,?,x,(,2,),?,?,x,i,x,i,?,2,?,(,x,1,x,3,?,x,2,

5、x,4,?,x,3,x,1,?,x,4,x,2,),?,(,?,1,?,1,?,1,?,1,),?,?,1,4,i,?,1,4,4,1,1,1,?,x,(,3,),?,?,x,i,x,i,?,3,?,(,x,1,x,4,?,x,2,x,1,?,x,3,x,2,?,x,4,x,3,),?,(,?,1,?,1,?,1,?,1,),?,0,4,i,?,1,4,4,4,4,4,第,10,章,正交编码与伪随机序列,若规定用二进数字“,0”,代替上述码组中的“,+1”,，,用二进数字“,1”,代替“,-,1”,，,互相关系,数定义变为,A,?,D,?,(,x,y,),?,A,?,D,A,x,和,y,中对应

6、码元,相同,的个数；,D,x,和,y,中对应码元,不同,的个数；,若用,x,的,j,次循环移位代替,y,，就得到,x,的,自相关系数,。,4.,超正交码,若两个码组间的,互相关系数,0,，称这两个码组互相,超正交,。,如果一种编码中,任,两码组间均,超正交,，则称这种编码为超正交,编码。,?,(,t,),:,(,0,1,1,),?,s,1,?,?,(,t,),:,(,1,1,0,),?,s,2,?,?,(,t,),:,(,1,0,1,),?,s,3,这三个码组所构成的编码是超正交码。,第,10,章,正交编码与伪随机序列,5.,双正交编码,由正交编码和其反码构成,双正交编码,。,正交码为,(,0

7、,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,),双正交编码,正交,(,0,0,0,0,),(,0,0,1,1,),(,0,1,1,0,),(,0,1,0,1,),(,1,1,1,1,),(,1,1,0,0,),(,1,0,0,1,),(,1,0,1,0,),共有,8,种码组，码长为,4,，任两码组间的相关系数为,0,或,-l,。,第,10,章,正交编码与伪随机序列,6.,哈达玛（,Hadama

8、rd,）矩阵,它用以构成超正交码和双正交码。,它的每一行,(,或列,),都是一,正交码组,。,a. 2,阶哈达玛矩阵,(,最低阶,),H,?,?,1,?,1,?,2,?,?,?,?,1,?,1,?,?,b. 4,阶哈达玛矩阵,H,H,?,H,2,4,?,2,?,H,2,?,?,?,H,2,H,?,?,?,?,2,?,?,?,?,?,?,?,?,?,?,?,?,?,H,?,2,?,?,?,?,?,?,H,?,?,?,?,?,2,?,?,?,?,?,?,?,?,?,直积,?,?,?,?,?,?,?,简写为,第,10,章,正交编码与伪随机序列,c. 8,阶哈达玛矩阵,?,H,4,H,8,?,H,4,

9、?,H,2,?,?,?,H,4,d. N,阶哈达玛矩阵,(N=2,m,),?,?,?,?,?,?,?,?,H,4,?,?,?,?,?,?,H,4,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,H,N,/,2,H,N,?,H,N,/,2,?,H,2,?,?,?,H,N,/,2,H,N,/,2,?,?,?,H,N,/,2,?,第

10、一行和第一列的元素全为“,+”,，这样的,H,矩阵称为哈达玛矩阵,的,正规形式,(,正规哈达玛矩阵,),。,H,矩阵中各行（或列）是相互正交的,(,正交方阵,),。,若把其中每一行看作是一个码组，则这些码组也是互相正交的，,整个,H,矩阵就是一种长为,n,的正交编码，包含,n,个码组。,第,10,章,正交编码与伪随机序列,7.,沃尔什矩阵,(Walsh),将,H,矩阵中行的次序按“,+l”,和“,-,l”,交变次数的多少重新排,列，得到沃尔什矩阵。,?,?,?,?,?,?,?,?,W,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?

11、,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,第,10,章,正交编码与伪随机序列,10.3,伪随机序列,香农,(Shannon),指出，为了实现,最有效,的通信，应采用具有白,噪声的统计特性的信号。,为了实现高可靠的保密通信，也利用随机噪声。,随机噪声的缺点：,难,以重复,产生,和,处理,。,伪随机噪声具有,类似,于随机,噪声,的一些统计特性，又便于重复,产生和处理。,伪随机噪声都是由数字电路产生的周期序列,(,伪随机序

12、列,),。,PN,序列,(Pseudo Noise),产生伪随机序列的电路为一,反馈移存器,。,它又可分为线性反馈移存器和非线性反馈移存器两类。,由线性反馈移存器产生出的周期,最长,的二进制数字序列称为,最,大长度线性反馈移存器序列,(m,序列,),。,10.3.1 m,序列,1. m,序列的产生,第,10,章,正交编码与伪随机序列,1. 4,级反馈移存器。,1),初始状态为,(,a,3,a,2,a,1,a,0,),?,(,1,0,0,0,),输出周期最长为,15,的序列：,000 111 101 011 001,2),初始状态为,(,a,3,a,2,a,1,a,0,),?,(,0,0,0,0

13、,),移位后得到的仍为全“,0”,状态。,反馈移存器中应避免出现全“,0”,状,态。,用尽可能少的级数产生尽可能长的,序列。,2.,n,级反馈移存器,一个,n,级反馈移存器可能产生的最,第,10,章,正交编码与伪随机序列,反馈电路如何,连接,才能使移存器产生的序列最长,.,反馈线的连接状态用,c,i,表示,:,c,i,= 1,表示此线,接通,;,c,i,=,0,表示此线,断开,。,设,n,级移位寄存器的初始状态为：,a,?,1,a,?,2,?,a,?,n,?,1,a,?,n,经过一次移位后，状态变为,:,a,0,a,?,1,?,a,?,n,?,2,a,?,n,?,1,经过,n,次移位后，状态变

14、为,:,a,n,?,1,a,n,?,2,?,a,1,a,0,n,i,?,1,线路连接关系,a,n,?,c,1,a,n,?,1,?,c,2,a,n,?,2,?,?,?,c,n,?,1,a,1,?,c,n,a,0,?,?,c,i,a,n,?,i,第,10,章,正交编码与伪随机序列,a),递推方程,n,任意一状态,a,k,?,?,c,i,a,k,?,i,i,?,1,b),特征方程（或特征多项式）,移位寄存器的反馈连接,n,f,(,x,),?,c,?,c,2,n,0,1,x,?,c,2,x,?,?,?,c,n,x,?,?,c,i,i,x,n,次多项式,f,(,x,),满足下列条件,:,i,?,0,(1

15、),f,(,x,),为既约的,(,不能分解因子的多项式,);,(2),f,(,x,),可整除,(,x,m,+ 1),，,m,= 2,n,l;,(3),f,(,x,),除不尽,(,x,q,+ 1),，,q,m,;,f,(,x,),为,本原多项式,。,一,n,级线性反馈移位寄存器能产生,m,序列的充要条件为：,特征多项式,为,n,次本原多项式。,具有最长周期,m,= 2,n,l,，周期与初始状态,无关,。,0”,状态。,若一个,则称,反馈移位寄存器的,初始状态不考虑全“,第,10,章,正交编码与伪随机序列,例,要求用一个,4,级反馈移位寄存器产生,m,序列，,试求其特征多项式。,n,= 4,，移位

16、寄存器产生的,m,序列的长度为,m =,2,n,1 = 15,，,图,10-2,x,15,?,1,?,(,x,4,?,x,?,1,)(,x,4,?,x,3,?,1,)(,x,4,?,x,3,?,x,2,?,x,?,1,)(,x,2,?,x,x,5,?,1,?,(,x,4,?,x,3,?,x,2,?,x,?,1,)(,x,?,1,),4,次本原多项式：,(,x,4,?,x,?,1,),(,x,4,?,x,3,?,1,),图,10-2,是,4,级反馈移位寄存器，其特征多项式为,(,x,4,?,x,?,1,),本原多项式的逆多项式也是本原多项式，,(,x,4,?,x,?,1,),与,(,x,4,?,

17、x,3,?,1,),互为逆多项式。,以组成两种,m,序列产生器。,?,1,)(,x,?,1,),第,10,章,正交编码与伪随机序列,为了使,m,序列产生器的组成尽量简单，使用项数最少的那些本,原多项式。,本原多项式最少有三项（这时只需用一个模,2,加法器）。,第,10,章,正交编码与伪随机序列,3. m,序列的性质,1),均衡性,在,m,序列的一周期中，“,1”,和“,0”,的数目基本相等。,“,1”,的个数比“,0”,的个数,多,一个。,2),游程分布,把一个序列中取值相同的那些连在一起的元素合称为一个,“游程”。,在一个游程中元素的个数称为游程长度。,例如，在,图,10-2,中给出的,m,

18、序如下：,000 111 101 011 001,共有,8,个游程：,长度为,4,的游程有一个；长度为,3,的游程有一个；,长度为,2,的游程有两个；长度为,1,的游程有,4,个。,第,10,章,正交编码与伪随机序列,在,m,序列中，,长度为,1,的游程占游程总数的,1/2,；,长度为,2,的游程占游程总数的,1/4,；,长度为,3,的游程占游程总数的,1/8,；,。,1,?,k,?,(,n,?,1,),长度为,k,的游程数目占游程总数的,2,k,，,而且在长度为,k,的游程中,l,k,(,n,2),，连“,l”,的游程和连“,0”,的,游程各占一半。,3),移位相加特性,一个,m,序列,M,

19、p,与其经任意次迟延移位产生的另一不同序列,M,r,模,2,相加，得到的仍是,M,p,的某次迟延移位序列,M,s,，即,M,p,?,M,r,?,M,s,例, m = 7,的,m,序列,M,p,= 1110010,M,r,= 0111001,M,s,?,M,p,?,M,r,?,1110010,?,0111001,?,1001011,M,s,与,M,p,向右移位,5,次的结果相同。,第,10,章,正交编码与伪随机序列,4),自相关函数,自相关函数,A,?,D,A,?,D,R,(,j,),?,?,A,?,D,m,A,该序列与其,j,次移位序列一个周期中对应元素,相同,的数目；,D,该序列与其,j,次

20、移位序列一个周期中对应元素,不同,的数目；,m,该序列的周期。,x,i,?,x,i,?,j,?,0,的数目,?,x,i,?,x,i,?,j,?,1,的数目,改写成,R,(,j,),?,m,由,m,序列的迟延相加特性可知，,x,i,?,x,i,?,j,仍为,m,序列的一个元素，,上式分子就等于,m,序列一个周期中“,0”,的数目与“,1”,的数目之,差；,由,m,序列的均衡性可知，,m,序列一周期中“,0”,的数目比“,l”,的数,1,j,?,0,?,?,目少一个，,R,(,j,),?,?,1,?,j,?,1,2,?,m,?,1,?,?,m,自相关函数也有周期性，周期也是,m;,自相关函数是偶函

21、数,.,第,10,章,正交编码与伪随机序列,10.3.2,其他伪随机序列简介,非线性反馈移存器序列。,1,二次剩余序列,(,平方剩余数序列,),2,3,?,9,?,2,(m,od,7,),则称,2,为模,7,的平方剩余数。,如果能找到一个整数,x,，它使,2,x,?,i,(mod,p,),满足此方程的,i,就是模,p,的,二次剩余,；,否则，,i,就是模,p,的二次,非,剩余。,当规定,a,0,= -1,，且,若,i,是模,p,的二次剩余,?,1,a,i,?,?,?,?,1,若,i,是模,p,的非二次剩余,a,0,a,1,?,a,p,?,2,a,p,?,1,为二次剩余序列,其周期为,p(p,为

22、奇素数,),。,第,10,章,正交编码与伪随机序列,例,设,p = 19,，算出,1,?,1,?,1,(m,od,19,),4,?,16,?,16,(m,od,19,),7,?,49,?,11,(m,od,19,),10,?,100,?,5,(m,od,19,),2,2,2,2,2,2,?,4,?,4,(m,od,19,),5,?,25,?,6,(mod,19,),8,?,64,?,7,(mod,19,),11,?,121,?,7,(m,od,19,),2,2,2,2,2,3,?,9,?,9,(mod,19,),6,?,36,?,17,(m,od,19,),9,?,81,?,5,(m,od,1

23、9,),12,?,144,?,11,(m,od,19,),15,?,225,?,16,(mod,19,),18,?,324,?,1,(mod,19,),2,2,2,2,2,2,13,?,169,?,17,(m,od,19,),14,?,196,?,6,(m,od,19,),16,?,256,?,9,(m,od,19,),2,17,?,289,?,4,(m,od,19,),2,l,，,4,，,5,，,6,，,7,，,9,，,11,，,16,，,17,是模,19,的二次剩余；,2,，,3,，,8,，,10,，,12,，,13,，,14,，,15,，,18,是模,19,的非二次剩余。,得到周期,p,

24、19,的二次剩余序列为,-+-,-+ +-,+-+ -,-+ -,第,10,章,正交编码与伪随机序列,2. M,序列,由,非线性,反馈移存器产生的周期最长的序列简称为,M,序列。,在,m,序列中不能出现的是全“,0,状态。,非线性反馈移存器的最长周期可达,2,n,，称这种周期长达,2,n,的序列,为,M,序列。,图,10-2,中,，,n,4,级的,m,序列产生器，它有的,15,种状态。,若使它增加一个“,0000”,状态，就可变成,M,序列产生器了。,“,0000”,状态必须处于初始状态“,1000”,之前和“,0001”,状态之后。,第,10,章,正交编码与伪随机序列,10.4,伪随机序列的

25、应用,10,4,1,误码率测量,在实际测量数字通信系统的误码率时，,测量结果与信源送出信号的统计特性有关,.,认为二进制信号中,0,和,1,是以等概率随机出现的。,测量误码率时最理想的,信源,应是,随机序列,产生器。,1.,闭环线路的测试,数字通信发送设备和接收设备放在,同一地点,，这种闭环测试,法所用信道,不,符合实际情况，,实际通信中一般都是单程传输信息的。,在测量单程数字通信的误码率时，只好用性能相近的,伪随机,序列,代替它。,第,10,章,正交编码与伪随机序列,2.,单程测试法,数字通信的发送设备和接收设备分处,两地,。,由于发送端用的是,伪随机序列,(,通常是,m,序列,),，,接收

26、端用,同样,的,m,序列产生器，由同步信号控制，产生出相同,的,本地序列,。,本地序列和接收序列相比较，就可以检测误码。,用于数据传输,设备,测量误码的,m,序列周期是,2,9,-1=511,，其特征,多项式建议采用,x,9,?,x,5,?,1,用于数字传输,系统,测量的,m,序列周期是,2,15,1 = 32767,，其特征,多项式建议采用,x,15,?,x,14,?,1,第,10,章,正交编码与伪随机序列,10.4.2,时延测量,1.,测量迟延的基本办法,由脉冲源产生一,周期,性,窄,脉冲序列，,调节标准迟延线的迟延时间，使比较电路中两路脉冲同时到达，,这时标准迟延线的迟延时间就等于被测传

27、输路径的迟延时间。,2.,采用,m,序列的办法,用一移位的,m,序列与被测量的经过传输路径迟延的,m,序列相关。,当两个序列的,相位相同,时，可得到相关峰，由移位,m,序列与原,m,序列的,相位差,可以求得迟延。,第,10,章,正交编码与伪随机序列,10.4.3,噪声产生器,要求能产生限带,白色高斯,噪声。,m,序列的功率谱密度的包络是,(sin,x,/,x,),形的。,设,m,序列的码元宽度为,T,1,秒，则大约在零至,(1/,T,1,),45%Hz,的频,率范围内，可以认为它具有,均匀,的功率谱密度。,对于多次进行某一测量，都有较好的可,重复,性。,10.4.4,通信加密,将信源产生的二进制数字消息和一个周期很长的伪随机序列模,2,相加，这样就将原消息变成不可理解的另一序列。,第,10,章,正交编码与伪随机序列,10.4.5,数据序列的扰乱与解扰,1.,假定信源送出的“,0”,和“,1”,码元是,等概率,的。,2.,在有些数字通信设备中，从“,0”,和“,1”,码元的交变点提取,位,定时,信息，若经常出现长的“,0”,或“,l”,游程，则将影响位同,步的建立和保持。,3.,电路中存在的不同程度的非线性，有可能使其在多路通信系,统其他路中造成串扰。为了限制这种串扰，常要求数字