单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 伪随机编码理论,3.1 有限域理论简介,3.2 伪随机编码的基本概念,3.3 伪随机编码的分类及构造原理,3.4 m序列,3.5 Gold序列,3.6 M序列,3.7 截短序列,3.8 其他扩频序列,3.1 有限域理论简介,自学,（掌握的基本概念）,自封的或封闭；,有限域；,1、基本概念,确定序列：,可以预先确定且能重复实现的序列随机序列：,既不能预先确定也不能重复实现的序列，性能与噪声性能类似（噪声序列）伪随机序列：,貌似随机序列的确定序列（伪随机码、伪噪声序列、码）,作用：,误码率的测量、通信加密、数据序列的扰码和解码、扩频通信等3.1 有限域理论简介,3.2 伪随机编码的基本概念,1、伪随机码定义以及特点：,定义：,伪随机码又叫伪噪声码，简称PN码简单地说，伪随机码是一种具有类似白噪声性质的码特点：,1）白噪声是一种随机过程；2）瞬时值服从正态分布，功率谱在很宽的频带内均匀的；3）白噪声具有优良的相关特性，但是至今无法实现工程上：,只能用类似于白噪声统计特性的伪随机码信号来逼近，并作为扩频通信系统的扩频码。
3.2 伪随机编码的基本概念,2、伪随机码的实现：,伪随机码都是周期码，可以人为的加以产生与复制通常用二进制移位寄存器产生3、工程上伪随机码的特点：,采用二元域0，1内的0和1的序列来表示伪随机码每一个周期内，0和1出现的次数近似相等，最后只差一次在每一个周期内，长度为k比特的元素游程出现次数比k+1比特的元素游程出现的次数多一倍3.2 伪随机编码的基本概念,（补充：游程：连续出现r个比特的同种元素叫做长度为r比特的元素游程）,序列的自相关函数是一周期函数，且具有双值特性，满足：,式中：N为二元序列的周期，又称码长或长度；,k为小于N的整数；,码元延时3.2 伪随机编码的基本概念,作为扩频码的伪随机信号，应具有下列特点：,(1)伪随机信号必须具有尖锐的自相关函数，而互相关函数值应接近零值；,(2)有足够长的码周期，以确保抗侦破和抗干扰的要求；,(3)码的数量足够多，用来作为独立的地址，以实现码分多址的要求；,(4)工程上易于产生、加工、复制和控制3.3 伪随机编码的分类及构造原理,3.3.1 几个基本定义,讨论前提：仅限等长二进制码，即码字长度(周期)相等，且码元都是二元域的-1，+1元素。
设 和 是周期为,N,的两个码序列，即 ，码字 和 的互相关函数 定义为,若 ，则两码字正交长度为N的码序列 的自相关函数 定义为,3.3.1 几个基本定义,计算自相关和互相关的另一种方法：,A是码字 和 或者 对应码元相同的数目(同为1或同为0的数目)，D是对应码元不相同的数目伪随机码的具体定义：,(1)若码序列 的自相关函数具有,的形式，码序列 称为伪随机码，又称为狭义伪随 机码2)若码序列 的自相关函数具有,的形式，码序列 称为广义伪随机码狭义伪随机码是广义伪随机码的特例3.3.2 双值自相关序列,1、定义：,如果一个码长为N的周期序列 ，自相关函数满足,把具有双值自相关函数特性的序列 叫作双值自相关序列根据前面伪随机码的定义，双值自相关序列属于广义伪随机码序列若 ，则 为狭义伪随机码序列2、双值自相关码的产生：,有差集产生，即可以用构造差集的方法来构造,双值自相关码序列3、,差集的构建原理：,一个差集通常可用3个参数来表征：,n，k,和,设有一个模,v,的整数集V,，,存在一个含有,k,个元素的子集,D,，即,且,di-dj(modv),恰好遍取1，2，,v,-1各,次，我们把这样的整数集V的子集D，称为差集。
例题,（验证差集）,设,n,=7，,k,=3,=1，则在整数集,中存在一个含有3个元素的子集,这个子集就具有差集的性质，因为,可见D内各差恰好遍取1，2，3，4，5，6各1次,，,因而是一个差集通常我们用,n,，,k,和,这3个参数来表示一个差集，记为 我们可以通过差集与双值自相关码的关系来构造双值自相关码方法：,对于给定的差集 ，可以写出,令,为一长度等于v的码，且,则 就是一个双值自相关的广义伪随机码，可以证明其自相关函数为,例题：,参照课本的64页3.3.3 狭义伪噪声序列,由,n,，,k,，,所确定的差集,D,构成的伪随机码序列，可能是广义的伪随机码序列，也可能是狭义的伪随机码序列，要由具体的,n,，,k,，,数值来确定，当 成立时，所得到的是狭义伪随机码序列；,否则是广义伪随机码序列介绍几种狭义伪随机码序列：,平方剩余码序列；双素数序列；霍尔序列；巴克,码我们仅仅需要掌握,平方剩余码序列,平方剩余码序列,对于某个整数,i,是模,N,的平方剩余，是指存在某个与,N,互为素数的整数,i,，使 有解当 为一素数(,t,为整数)时，模,N,的平方剩余构成一个差集例题：，模11的平方剩余,即 是,n,=11，,k,=5，,=2的差集，于,是可写出对应的伪随机序列为,它的自相关函数为,这样得到的伪随机序列，称为平方剩余序列或平方余数序列。
若 为素数，则存在一个周期为,N,的伪随机码序列,a,0,，,a,1,，,a,N,-1,，其中，,当N为奇数时，上面定义的 正是所谓的勒让德符号,于是,因此，平方剩余序列又称为勒让德序列，简称L序列一、线性反馈移位寄存器,在讲解m序列之前，首先讲讲回顾一下移位寄存器的基本原理图 线性反馈移位寄存器,3.4 m序列,1、可由,移位寄存器和反馈逻辑,产生a,n,1,a,n,2,c,0,1,输出,a,k,a,n,a,n,正状态（,状态,）：各级移位寄存器的寄存数从右至左的顺序排列（逆着移位脉冲的方向）由于带有反馈，因此在移位脉冲作用下，移位寄存器各级的状态将不断变化,通常移位,寄存器的最后一级做输出，输出序列为,输出序列是一个周期序列,.举例,假设初始状态为(,a,n,-,a,n,-,a,n,-2,a,n,-1,)(1000)，其反馈逻辑为：,a,n,1,a,n,2,c,0,1,输出,a,k,a,n,a,n,时钟节拍,a,n-1,a,n-2,a,n-3,a,n-4,0,0,0,0,1,1,1,0,0,0,2,0,1,0,0,3,0,0,1,0,4,1,0,0,1,5,1,1,0,0,6,0,1,1,0,7,1,0,1,1,8,0,1,0,1,9,1,0,1,0,10,1,1,0,1,11,1,1,1,0,12,1,1,1,1,13,0,1,1,1,14,0,0,1,1,15,0,0,0,1,输出,4.结论,线性移位寄存器的输出序列是一个周期系列,初始状态是时，输出序列也是零；,级数相同的线性移位寄存器的,输出,序列与寄存器的,反馈逻辑,有关；,输出序列与初始状态有关,；,序列周期,p,2,n,-1,（,n,为移位寄存器的级数）,;,3.4.1 m序列的定义,1、m序列：由n级线性移位寄存器产生的最大周期的序列（最大长度序列），其周期为：2,n,-1,（经历除全零外的所有可能状态的）,反馈移位寄存器输出序列,周期越长,，,越接近随机序列,。
2、,m,序列产生的条件,找到相应的反馈逻辑,若改变起始状态，只能改变m序列的起始相位，而周期序列排序规律不变3、,m,序列产生器,下图给出了产生m序列的线性反馈移位寄存器的一般结构图：,1）、起始状态为：,2）、,2）.线性反馈移位寄存器的,特征多项式,用多项式,f,(,x,)来描述线性反馈移位寄存器的反馈连接状态：,f(x)是一个常数项为1的n次多项式，它反映了反馈线的状态1）.线性反馈移位寄存器的,递推关系式,可以证明：产生m序列的特征多项式 为一个n次本原多项式若一个,n,次多项式,f,(,x,)满足下列条件,(1),f,(,x,)为既约多项式(即不能分解因式的多项式)；,(2),f,(,x,)可整除(,x,p,+1),p,=2,n,-1;,(3),f,(,x,)除不尽(,x,q,+1),q,p,则称,f,(,x,)为,本原多项式,一般本原多项式可通过计算机,穷举法,来验证例,：设 n 4，m=2,4,1=15,通过穷举法，可找出所有可整除 的多项式：,通过穷举法，还可证明，在 n 4 的多项式中：,是本原多项式而 不是本原多项式因为有,即其可整除 q 5 15 的因式 x,5,1,以为特征多项式，得到如下的,m,序列产生器,试画出以 为特征多项式的m序列发生器？,思考：,若改变初态，则输出？,a,3,1,a,2,2,a,1,3,a,0,4,a,k,1 0 0 0,1 1 0 0,1 1 1 0,1 1 1 1,0 1 1 1,1 0 1 1,0 1 0 1,1 0 1 0,1 1 0 1,0 1 1 0,0 0 1 1,1 0 0 1,0 1 0 0,0 0 1 0,0 0 0 1,1 0 0 0,1)均衡特性(平衡性)：,m,序列每一周期中,1,的个数比,0,的个数多,1,个，,在每一周期中,1,的个数为偶数，,0,的个数为奇数，,当,p,足够大时，在一个周期中,1,与,0,出现的次数基本相等。
4,m,序列的性质,例：m序列：,0 0 0,1,0 0,1 1,0,1,0,1 1 1,0000,1,00,11,0,1,0,1111 1,2)游程特性(游程分布的随机性),m,序列的一个周期,(,p,=2,n,-1),中，游程总数为,2,n,-1,长度为,k,的游程个数占游程总数的,1/2,k,=2,-,k,，,其中,1k(,n,-2),在长度为,k,游程中，连,1,游程与连,0,游程各占一半，长为,(,n,-1),的游程是连,0,游程，长为,n,的游程是连,1,游程补充概念：,游程：,序列中取值,(1,或,0),相同连在一起的元素合称为一个游程游程长度,：一个游程中元素的个数长度为1的游程 8 个，占1/2;,长度为2的游程 4 个，占1/4;,长度为3的游程 2个，占1/8;,长度为4的游程，为0000,剩下一个长度最长为,5,的游程“1111,1”,例：m序列：,0 0 0,1,0 0,1 1,0,1,0,1 1 1,0000,1,00,11,0,1,0,1111 1,3).移位相加特性（线性叠加性）,一个周期为P的m序列,m,P,与其任意次移位后的序列,m,r,模二相加，所得序列,m,S,必是,m,P,某次移位后的序列，即,m,r,仍是周期为P的m序列。
m序列：000,左移4：111,+),左移3：111,4)自相关特性,自相关函数R(i)是周期函数：,规一化,5.伪噪声特性,对一个正态分布白噪声取样，若取样值为正，记为+1，取样值为负，记为-1，将每次取样所得极性排成序列，可以写成,+1,-1,+1,+1,+1,-1,-1,+1,-1,这是一个随机序列，它具有如下基本性质：,(1)序列中+1 和-1 出现的概率相等；,(2)序列中长度为 1 的游程约占 1/2，长度为 2 的游程约占 1/4，长度为 3 的游程约占 1/8,一般地，长度为k的游程约占1/2,k,，而且+1,-1 游程的数目各占一半；,(3)由于白噪声的功率谱为常数，因此其自相关函数为一冲击函数()把m序列与上述随机序列进行比较，当周期p很大时，m序列与随机序列的性质十分相似3.4.3 m序列的构造,构造一个产生m序列的线性移位寄存器：,1）确定本原多项式；,2）本原多项式确定后，根据本原多项式构造出m序列移位寄存器的机构逻辑图本原多项式的寻找方法：,在所有的r次多项式中去掉其中的可约多项式，在剩下的r次不可约多项式中，根据定义用试探的方法得到目前采用可计算机编程实现）,目前设计可以参考附录,具体的例子：,r=5，从附录2中可查出三个本原多项式分别为45、75和67。
其中八进制数45用二进制数表示为100101，对应的本原多项式为 ，其逻辑图见下图a。