正交编码和伪随机序列.ppt

1,通信原理,2,通信原理,第12章 正交编码与伪随机序列,3,第12章 正交编码与伪随机序列,引言正交编码与伪随机序列在数字通信技术中都是十分重要的正交编码不仅可以用作纠错编码，还可以用来实现码分多址通信，目前已经广泛用于蜂窝网中伪随机序列在误码率测量、时延测量、扩谱通信、密码及分离多径等方面都有着十分广泛的应用因此，本章将在简要讨论正交编码概念之后，着重讨论伪随机序列及其应用4,第12章 正交编码与伪随机序列,12.2 正交编码 12.2.1 正交编码的基本概念 正交性 若两个周期为T的模拟信号s1(t)和s2(t)互相正交，则有同理，若M个周期为T的模拟信号s1(t)，s2(t)，…，sM(t)构成一个正交信号集合，则有互相关系数 对于二进制数字信号，用一数字序列表示码组这里，我们只讨论二进制且码长相同的编码这时，两个码组的正交性可用如下形式的互相关系数来表述i  j；i, j＝1, 2, …, M,5,第12章 正交编码与伪随机序列,设长为n的编码中码元只取值+1和-1，以及x和y是其中两个码组：其中 则x和y间的互相关系数定义为若码组x和y正交，则必有(x, y) = 0。

6,第12章 正交编码与伪随机序列,正交编码例如，下图所示4个数字信号可以看作是如下4个码组：按照互相关系数定义式计算容易得知，这4个码组中任意两者之间的相关系数都为0，即这4个码组两两正交我们把这种两两正交的编码称为正交编码7,第12章 正交编码与伪随机序列,自相关系数：类似上述互相关系数的定义，可以对于一个长为n的码组x定义其自相关系数为式中，x的下标按模n运算，即有xn＋k  xk 例如，设则有,,,,8,第12章 正交编码与伪随机序列,用二进制数字表示互相关系数 在二进制编码理论中，常采用二进制数字“0”和“1”表示码元的可能取值这时，若规定用二进制数字“0”代替上述码组中的“＋1”，用二进制数字“1”代替“－1”，则上述互相关系数定义式将变为式中，A — x和y中对应码元相同的个数；D — x和y中对应码元不同的个数 例如，按照上式规定，上面例子可以改写成,,,9,第12章 正交编码与伪随机序列,用二进制数字表示自相关系数 上式中，若用x的j次循环移位代替y，就得到x的自相关系数x (j)具体地讲，令代入定义式就得到自相关系数x (j)10,第12章 正交编码与伪随机序列,超正交码和双正交码 超正交码：相关系数 的取值范围在1之间，即有-1    +1。

若两个码组间的相关系数 < 0，则称这两个码组互相超正交如果一种编码中任两码组间均超正交，则称这种编码为超正交码 例如，在上例中，若仅取后3个码组，并且删去其第一位，构成如下新的编码：则不难验证，由这3个码组所构成的编码是超正交码11,第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或－112,第12章 正交编码与伪随机序列,12.2.2 阿达玛矩阵 定义： 阿达玛矩阵简记为H矩阵它是一种方阵，仅由元素+1和－1构成，而且其各行（和列）是互相正交的最低阶的H矩阵是2阶的，即下面为了简单，把上式中的＋1和－1简写为＋和－，这样上式变成,,,13,第12章 正交编码与伪随机序列,阶数为2的幂的高阶H矩阵可以从下列递推关系得出H N＝ H N / 2  H 2 式中，N ＝ 2m； － 直积。

上式中直积是指将矩阵HN / 2中的每一个元素用矩阵H2代替例如：,,14,第12章 正交编码与伪随机序列,上面给出几个H矩阵的例子，都是对称矩阵，而且第一行和第一列的元素全为“＋”我们把这样的H矩阵称为阿达玛矩阵的正规形式，或称为正规阿达玛矩阵15,第12章 正交编码与伪随机序列,性质 在H矩阵中，交换任意两行，或交换任意两列，或改变任一行中每个元素的符号，或改变任一列中每个元素的符号，都不会影响矩阵的正交性质因此，正规H矩阵经过上述各种交换或改变后仍为H矩阵，但不一定是正规的了 按照递推关系式可以构造出所有2k阶的H矩阵可以证明，高于2阶的H矩阵的阶数一定是4的倍数不过，以4的倍数作为阶数是否一定存在H矩阵，这一问题并未解决H矩阵是正交方阵若把其中每一行看作是一个码组，则这些码组也是互相正交的，而整个H矩阵就是一种长为n的正交编码，它包含n个码组因为长度为n的编码共有2n个不同码组，现在若只将这n个码组作为准用码组，其余(2n - n)个为禁用码组，则可以将其多余度用来纠错这种编码在纠错编码理论中称为里德-缪勒(Reed-Muller)码16,第12章 正交编码与伪随机序列,12.2.3 沃尔什函数和沃尔什矩阵 沃尔什函数定义式中 p = 0或1，j = 0，1，2，，及指数中的[j / 2]表示取j / 2的整数部分。

正弦和余弦函数可以构成一个完备正交函数系由于正弦和余弦函数具有完备和正交性，所以由其构成的无穷级数或积分（即傅里叶级数和傅里叶积分）可以表示任一波形类似地，由取值“＋1”和“－1”构成的沃尔什函数也具有完备正交性，也可以用其表示任一波形,,,17,第12章 正交编码与伪随机序列,前8个沃尔什函数的波形示于下图中,18,第12章 正交编码与伪随机序列,由于沃尔什函数的取值仅为“＋1”和“－1”，所以可以用其离散的抽样值表示成矩阵形式例如，上图中的8个沃尔什函数可以写成如下沃尔什矩阵：由上图和矩阵可以看出，沃尔什矩阵是按照每一行中“＋1”和“－1”的交变次数由少到多排列的沃尔什函数（矩阵）天生具有数字信号的特性，所以它们在数字信号处理和编码理论中有不小应用前景19,第12章 正交编码与伪随机序列,12.3 伪随机序列 12.3.1 基本概念 什么是伪随机噪声？具有类似于随机噪声的某些统计特性，同时又能够重复产生的波形 优点：它具有随机噪声的优点，又避免了随机噪声的缺点，因此获得了日益广泛的实际应用 如何产生伪随机噪声？目前广泛应用的伪随机噪声都是由周期性数字序列经过滤波等处理后得出的在后面我们将这种周期性数字序列称为伪随机序列。

它有时又称为伪随机信号和伪随机码 12.3.2 m序列 m序列的产生：m序列是最长线性反馈移位寄存器序列的简称它是由带线性反馈的移存器产生的周期最长的一种序列20,第12章 正交编码与伪随机序列,例： 下图中示出一个4级线性反馈移存器设其初始状态为(a3, a2, a1, a0) = (1, 0, 0, 0)，则在移位1次时，由a3和a0模2相加产生新的输入a4 = 1  0 = 1，新的状态变为(a4, a3, a2, a1) = (1, 1, 0, 0)这样移位15次后又回到初始状态(1,0, 0, 0)若初始状态为全“0”，即(0, 0, 0, 0)，则移位后得到的仍为全“0”状态应该避免出现全“0”状态，否则移存器的状态将不会改变21,第12章 正交编码与伪随机序列,因为4级移存器共有24 = 16种可能的状态除全“0”状态外，只剩15种状态可用这就是说，由任何4级反馈移存器产生的序列的周期最长为15我们常常希望用尽可能少的级数产生尽可能长的序列由上例可见，一般来说，一个n级线性反馈移存器可能产生的最长周期等于(2n - 1)我们将这种最长的序列称为最长线性反馈移存器序列，简称m序列。

反馈电路如何连接才能使移存器产生的序列最长，这就是本节将要讨论的主题22,第12章 正交编码与伪随机序列,一般的线性反馈移存器原理方框图图中各级移存器的状态用ai表示，ai = 0或1，i ＝整数反馈线的连接状态用ci表示，ci＝1表示此线接通（参加反馈）；ci＝0表示此线断开反馈线的连接状态不同，就可能改变此移存器输出序列的周期p23,第12章 正交编码与伪随机序列,基本的关系式 递推方程 设一个n级移存器的初始状态为：a－1 a－2 a－n，经过1次移位后，状态变为a0 a－1 a－n＋1经过n次移位后，状态为an－1 an－2 a0，上图所示就是这一状态再移位1次时，移存器左端新得到的输入an，按照图中线路连接关系，可以写为因此，一般说来，对于任意一个输入ak，有－称为递推方程它给出移位输入ak与移位前各级状态的关系按照递推方程计算，可以用软件产生m序列，不必须用硬件电路实现24,第12章 正交编码与伪随机序列,特征方程（特征多项式）ci的取值决定了移存器的反馈连接和序列的结构，故ci是一个很重要的参量现在将它用下列方程表示：－ 特征方程式中xi仅指明其系数（1或0）代表ci的值，x本身的取值并无实际意义，也不需要去计算x的值。

例如，若特征方程为则它仅表示x0，x1和x4的系数c0＝c1＝c4＝1，其余的ci为0，即c2＝c3＝0按照这一特征方程构成的反馈移存器就是上图所示的25,第12章 正交编码与伪随机序列,母函数我们也可以将反馈移存器的输出序列{ ak}用代数方程表示为上式称为母函数 递推方程、特征方程和母函数就是我们要建立的3个基本关系式下面的几个定理将给出它们与线性反馈移存器及其产生的序列之间的关系26,第12章 正交编码与伪随机序列,【定理12.2】一个n级线性反馈移存器之相继状态具有周期性，周期为p  2n－1证】线性反馈移存器的每一状态完全决定于前一状态因此，一旦产生一状态R，若它与以前的某一状态Q相同，则状态R后之相继状态必定和Q之相继状态相同，这样就可以具有周期性在n级移存器中，每级只能有两种状态：“1”或“0”故n级移存器最多仅可能有2n 种不同状态所以，在连续(2n + 1)个状态中必有重复如上所述，一旦状态重复，就有周期性这时周期p  2n若一旦发生全“0”状态，则后继状态也为全“0”，这时的周期p＝1因此，在一个长的周期中不能包括全“0”状态所以周期p  (2n - 1)证毕】,27,第12章 正交编码与伪随机序列,【定理12.3】若序列A = { ak }具有最长周期(p = 2n - 1)，则其特征多项式f(x)应为既约多项式。

证】所谓既约多项式是指不能分解因子的多项式若一n次多项式f (x)能分解成两个不同因子，则可令这样，式可以写成如下部分分式之和：式中 f1(x)的次数为n1，n1 > 0，f2(x)的次数为n2，n2 > 0，且有,,,,28,第12章 正交编码与伪随机序列,令则上式可以改写成上式表明，输出序列G(x)可以看成是两个序列G1(x)和G2(x)之和，其中G1(x)是由特征多项式f1(x)产生的输出序列，G2(x)是由特征多项式f2(x)产生的输出序列而且，由定理12.2可知，G1(x)的周期为G2(x)的周期为所以，G(x)的周期p应是p1和p2的最小公倍数LCM[p1, p2]，即上式表明，p 一定小于最长可能周期(2n - 1)若f(x)可以分解成两个相同的因子，即上面的f1(x)＝f2(x)，同样可以证明p < 2n－1所以，若f (x)能分解因子，必定有p < 2n – 1证毕】,,,,,,,29,第12章 正交编码与伪随机序列,【定理12.4】一个n级移存器的特征多项式f (x)若为既约的，则由其产生的序列A = { ak }的周期等于使f (x)能整除的(xp + 1)中最小正整数 p。

证】若序列A 具有周期p，则有上式移项整理后，变成,,30,第12章 正交编码与伪随机序列,本原多项式 定义：若一个n次多项式f(x)满足下列条件：f (x)为既约的；f (x)可整除(xm + 1)，m = 2n – 1；f (x)除不尽(xq + 1)，q < m；则称 f (x)为本原多项式 由定理12.4可以简单写出一个线性反馈移存器能产生m序列的充要条件为：反馈移存器的特征多项式为本原多项式。