扩频通信第三章伪随机编码理论.ppt

第三章 伪随机编码理论,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的伪随机码序列a0，a1，aN-1，其中， 当N为奇数时，上面定义的 正是所谓的勒让德符号 于是 因此，平方剩余序列又称为勒让德序列，简称L序列。,一、线性反馈移位寄存器 在讲解m序列之前，首先讲讲回顾一下移位寄存器的基本原理。,图 线性反馈移位寄存器,3.4 m序列,1、可由移位寄存器和反馈逻辑产生。,正状态（状态）：各级移位寄存器的寄存数从右至左的顺序排列（逆着移位脉冲的方向）。 由于带有反馈，因此在移位脉冲作用下，移位寄存器各级的状态将不断变化 通常移位寄存器的最后一级做输出，输出序列为,输出序列是一个周期序列,. 举例,假设初始状态为(an- an- an-2 an-1) (1000)，其反馈逻辑为：,输出,4. 结论 线性移位寄存器的输出序列是一个周期系列 初始状态是时，输出序列也是零； 级数相同的线性移位寄存器的输出序列与寄存器的反馈逻辑有关； 输出序列与初始状态有关； 序列周期p2n-1（n为移位寄存器的级数）;,3.4.1 m序列的定义 1、m序列：由n级线性移位寄存器产生的最大周期的序列（最大长度序列） ，其周期为：2n-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)可整除(xp+1), p=2n-1; (3) f(x)除不尽(xq+1), qp。 则称f(x)为本原多项式。 一般本原多项式可通过计算机穷举法来验证。,例：设 n 4，m = 24 1 = 15 通过穷举法，可找出所有可整除 的多项式： 通过穷举法，还可证明，在 n 4 的多项式中： 是本原多项式。而 不是本原多项式。 因为有 即其可整除 q 5 15 的因式 x51,以 为特征多项式，得到如下的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=2n-1)中，游程总数为2n-1。 长度为k的游程个数占游程总数的 1/2k=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的游程 “11111”。,例：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序列mP与其任意次移位后的序列mr模二相加，所得序列mS必是mP某次移位后的序列，即mr仍是周期为P的m序列。,m序列：000111101011001000111101011001000,左移4：111010110010001111010110010001111,左移3 ：111101011001000111101011001000111,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/2k，而且+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。,r次多项式 的互反多项式 定义为 理论上已经证明，不可约多项式的互反多项式为不可约多项式，本原多项式的互反多项式也为本原多项式。根据互反多项式的定义， 的互反多项式为,其结构逻辑图见图b。,伪随机序列的应用,扩频通信； 加密 扰码 误码测量 码分多址等,通信加密 信源与周期很长m序列模二加，变成不可理解的另一序列,图11-10 利用m序列加密,图11-11 数字信号的加密与解密,误码率的测量,图 11-12 误码率测试,数字信息序列的扰码和解扰,扰码器结构,由图直接可得：G(n) = S(n)iCiG(n-i), ( i mod2 和） 当输入S(n) 为全“0”时，输出为m序列(初态不全为“0”)； 一般S(n)出现长串长“0”或“1”时，输出伪随机序列。,D,D,D,D,D,C1,+,C2,+,C3,+,Cn-1,+,C0= 1,Cn= 1,输出序列R(n),+,输入 序列 G(n),Gn-1,Gn-2,Gn-3,G1,G0,解扰器结构 由：G(n) = S(n) iCiG(n-i) R(n) = G(n)iCiG(n-i)(S(n