正交编码与伪随机序列.ppt
《正交编码与伪随机序列.ppt》由会员分享,可在线阅读,更多相关《正交编码与伪随机序列.ppt(93页珍藏版)》请在三一文库上搜索。
1、1,通信原理,2,通信原理,第12章 正交编码与伪随机序列,3,第12章 正交编码与伪随机序列,引言 正交编码与伪随机序列在数字通信技术中都是十分重要的。正交编码不仅可以用作纠错编码,还可以用来实现码分多址通信,目前已经广泛用于蜂窝网中。伪随机序列在误码率测量、时延测量、扩谱通信、密码及分离多径等方面都有着十分广泛的应用。因此,本章将在简要讨论正交编码概念之后,着重讨论伪随机序列及其应用。,4,第12章 正交编码与伪随机序列,12.2 正交编码 12.2.1 正交编码的基本概念 正交性 若两个周期为T的模拟信号s1(t)和s2(t)互相正交,则有 同理,若M个周期为T的模拟信号s1(t),s2
2、(t),sM(t)构成一个正交信号集合,则有 互相关系数 对于二进制数字信号,用一数字序列表示码组。这里,我们只讨论二进制且码长相同的编码。这时,两个码组的正交性可用如下形式的互相关系数来表述。,i j;i, j1, 2, , M,5,第12章 正交编码与伪随机序列,设长为n的编码中码元只取值+1和-1,以及x和y是其中两个码组: 其中 则x和y间的互相关系数定义为 若码组x和y正交,则必有(x, y) = 0。,6,第12章 正交编码与伪随机序列,正交编码 例如,下图所示4个数字信号可以看作是如下4个码组: 按照互相关系数定义式计算容易得知, 这4个码组中任意两者之间的相关系数 都为0,即这
3、4个码组两两正交。我们 把这种两两正交的编码称为正交编码。,7,第12章 正交编码与伪随机序列,自相关系数: 类似上述互相关系数的定义,可以对于一个长为n的码组x定义其自相关系数为 式中,x的下标按模n运算,即有xnk xk 。例如,设 则有,8,第12章 正交编码与伪随机序列,用二进制数字表示互相关系数 在二进制编码理论中,常采用二进制数字“0”和“1”表示码元的可能取值。这时,若规定用二进制数字“0”代替上述码组中的“1”,用二进制数字“1”代替“1”,则上述互相关系数定义式将变为 式中,A x和y中对应码元相同的个数; D x和y中对应码元不同的个数。 例如,按照上式规定,上面例子可以改
4、写成,9,第12章 正交编码与伪随机序列,用二进制数字表示自相关系数 上式中,若用x的j次循环移位代替y,就得到x的自相关系数x (j)。具体地讲,令 代入定义式 就得到自相关系数x (j)。,10,第12章 正交编码与伪随机序列,超正交码和双正交码 超正交码:相关系数 的取值范围在1之间,即有-1 +1。若两个码组间的相关系数 0,则称这两个码组互相超正交。如果一种编码中任两码组间均超正交,则称这种编码为超正交码。 例如,在上例中,若仅取后3个码组,并且删去其第一位,构成如下新的编码: 则不难验证,由这3个码组所构成的编码是超正交码。,11,第12章 正交编码与伪随机序列,双正交编码 由正交
5、编码和其反码便可以构成双正交编码。 例: 上例中正交码为 其反码为 上两者的总体即构成如下双正交码: (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。,12,第12章 正交编码与伪随机序列,12.2.2 阿达玛矩阵 定义: 阿达玛矩阵简记为H矩阵。它是一种方阵,仅由元素+1和1构成,而且其各行(和列)是互相正交的。最低阶的H矩阵是2阶的,即 下面为了简单,把上式中的1和1简写为和,这样上式变成,13,第12章 正交编码与伪随机
6、序列,阶数为2的幂的高阶H矩阵可以从下列递推关系得出 H N H N / 2 H 2 式中,N 2m; 直积。 上式中直积是指将矩阵HN / 2中的每一个元素用矩阵H2代替。例如:,14,第12章 正交编码与伪随机序列,上面给出几个H矩阵的例子,都是对称矩阵,而且第一行和第一列的元素全为“”。我们把这样的H矩阵称为阿达玛矩阵的正规形式,或称为正规阿达玛矩阵。,15,第12章 正交编码与伪随机序列,性质 在H矩阵中,交换任意两行,或交换任意两列,或改变任一行中每个元素的符号,或改变任一列中每个元素的符号,都不会影响矩阵的正交性质。因此,正规H矩阵经过上述各种交换或改变后仍为H矩阵,但不一定是正规
7、的了。 按照递推关系式可以构造出所有2k阶的H矩阵。可以证明,高于2阶的H矩阵的阶数一定是4的倍数。不过,以4的倍数作为阶数是否一定存在H矩阵,这一问题并未解决。 H矩阵是正交方阵。若把其中每一行看作是一个码组,则这些码组也是互相正交的,而整个H矩阵就是一种长为n的正交编码,它包含n个码组。因为长度为n的编码共有2n个不同码组,现在若只将这n个码组作为准用码组,其余(2n - n)个为禁用码组,则可以将其多余度用来纠错。这种编码在纠错编码理论中称为里德-缪勒(Reed-Muller)码。,16,第12章 正交编码与伪随机序列,12.2.3 沃尔什函数和沃尔什矩阵 沃尔什函数定义 式中 p =
8、0或1,j = 0,1,2,及指数中的j / 2表示取j / 2的整数部分。 正弦和余弦函数可以构成一个完备正交函数系。由于正弦和余弦函数具有完备和正交性,所以由其构成的无穷级数或积分(即傅里叶级数和傅里叶积分)可以表示任一波形。类似地,由取值“1”和“1”构成的沃尔什函数也具有完备正交性,也可以用其表示任一波形,17,第12章 正交编码与伪随机序列,前8个沃尔什函数的波形示于下图中,18,第12章 正交编码与伪随机序列,由于沃尔什函数的取值仅为“1”和“1”,所以可以用其离散的抽样值表示成矩阵形式。例如,上图中的8个沃尔什函数可以写成如下沃尔什矩阵: 由上图和矩阵可以看出,沃尔什矩阵是按照每
9、一行中“1”和“1”的交变次数由少到多排列的。 沃尔什函数(矩阵)天生具有数字信号的特性,所以它们在数字信号处理和编码理论中有不小应用前景。,19,第12章 正交编码与伪随机序列,12.3 伪随机序列 12.3.1 基本概念 什么是伪随机噪声? 具有类似于随机噪声的某些统计特性,同时又能够重复产生的波形。 优点:它具有随机噪声的优点,又避免了随机噪声的缺点,因此获得了日益广泛的实际应用。 如何产生伪随机噪声? 目前广泛应用的伪随机噪声都是由周期性数字序列经过滤波等处理后得出的。在后面我们将这种周期性数字序列称为伪随机序列。它有时又称为伪随机信号和伪随机码。 12.3.2 m序列 m序列的产生:
10、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”状态, 否则移存器的
11、状态将不 会改变。,21,第12章 正交编码与伪随机序列,因为4级移存器共有24 = 16种可能的状态。除全“0”状态外,只剩15种状态可用。这就是说,由任何4级反馈移存器产生的序列的周期最长为15。 我们常常希望用尽可能少的级数产生尽可能长的序列。由上例可见,一般来说,一个n级线性反馈移存器可能产生的最长周期等于(2n - 1)。我们将这种最长的序列称为最长线性反馈移存器序列,简称m序列。 反馈电路如何连接才能使移存器产生的序列最长,这就是本节将要讨论的主题。,22,第12章 正交编码与伪随机序列,一般的线性反馈移存器原理方框图 图中各级移存器的状态用ai表示,ai = 0或1,i 整数。
12、反馈线的连接状态用ci表示,ci1表示此线接通(参加反馈);ci0表示此线断开。 反馈线的连接状态不同,就可能改变此移存器输出序列的周期p。,23,第12章 正交编码与伪随机序列,基本的关系式 递推方程 设一个n级移存器的初始状态为:a1 a2 an,经过1次移位后,状态变为a0 a1 an1。经过n次移位后,状态为an1 an2 a0,上图所示就是这一状态。再移位1次时,移存器左端新得到的输入an,按照图中线路连接关系,可以写为 因此,一般说来,对于任意一个输入ak,有 称为递推方程 它给出移位输入ak与移位前各级状态的关系。按照递推方程计算,可以用软件产生m序列,不必须用硬件电路实现。,2
13、4,第12章 正交编码与伪随机序列,特征方程(特征多项式) ci的取值决定了移存器的反馈连接和序列的结构,故ci是一个很重要的参量。现在将它用下列方程表示: 特征方程 式中xi仅指明其系数(1或0)代表ci的值,x本身的取值并无实际意义,也不需要去计算x的值。例如,若特征方程为 则它仅表示x0,x1和x4的系数c0c1c41,其余的ci为0,即c2c30。按照这一特征方程构成的反馈移存器就是上图所示的。,25,第12章 正交编码与伪随机序列,母函数 我们也可以将反馈移存器的输出序列 ak用代数方程表示为 上式称为母函数 。 递推方程、特征方程和母函数就是我们要建立的3个基本关系式。下面的几个定
14、理将给出它们与线性反馈移存器及其产生的序列之间的关系。,26,第12章 正交编码与伪随机序列,定理 【定理12.1】 式中,h(x)为次数低于f(x)的次数的多项式。 【证】将递推方程代入母函数,得到 移项整理后,得到,27,第12章 正交编码与伪随机序列,将上式右端用符号h(x)表示,并因c0 1,故上式变成 式中 由此式可以看出,当电路给定后,h(x)仅决定于初始状态(a-i a-1)。 再将特征方程代入上式,最后得出,28,第12章 正交编码与伪随机序列,在 中,若a1 = 1,则h(x)的最高次项为xn-1;若a1 = 0,则最高项次数 (n 1),所以我们得知h(x)的最高项次数 (
15、n 1),而f(x)的最高项次数= n,因为已规定cn1,特征方程中最高项为xn。故h(x)的次数必定低于f(x)的次数。【证毕】,29,第12章 正交编码与伪随机序列,【定理12.2】一个n级线性反馈移存器之相继状态具有周期性,周期为p 2n1。 【证】线性反馈移存器的每一状态完全决定于前一状态。因此,一旦产生一状态R,若它与以前的某一状态Q相同,则状态R后之相继状态必定和Q之相继状态相同,这样就可以具有周期性。 在n级移存器中,每级只能有两种状态:“1”或“0”。故n级移存器最多仅可能有2n 种不同状态。所以,在连续(2n + 1)个状态中必有重复。如上所述,一旦状态重复,就有周期性。这时
16、周期p 2n。 若一旦发生全“0”状态,则后继状态也为全“0”,这时的周期p1。因此,在一个长的周期中不能包括全“0”状态。所以周期p (2n - 1)。【证毕】,30,第12章 正交编码与伪随机序列,【定理12.3】若序列A = ak 具有最长周期(p = 2n - 1),则其特征多项式f(x)应为既约多项式。 【证】所谓既约多项式是指不能分解因子的多项式。若一n次多项式f (x)能分解成两个不同因子,则可令 这样,式 可以写成如下部分分式之和: 式中 f1(x)的次数为n1,n1 0, f2(x)的次数为n2,n2 0, 且有,31,第12章 正交编码与伪随机序列,令 则上式可以改写成 上
17、式表明,输出序列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的最小公倍数LCMp1, p2,即 上式表明,p 一定小于最长可能周期(2n - 1)。 若f(x)可以分解成两个相同的因子,即上面的f1(x)f2(x),同样可以证明p 2n1。 所以,若f (x)能分解因子,必定有p 2n 1。【证毕】,32,第12章 正交编码与伪随机序列,【定理12.4】一个n级移存器的特征多项式f
18、 (x)若为既约的,则由其产生的序列A = ak 的周期等于使f (x)能整除的(xp + 1)中最小正整数 p。 【证】若序列A 具有周期p,则有 上式移项整理后,变成,33,第12章 正交编码与伪随机序列,由定理12.1可知,h(x)的次数比f (x)的低,而且现已假定f (x)为既约的,所以上式表明(xp + 1)必定能被f (x)整除。 应当注意,此时序列A之周期p与初始状态或者说与h(x)无关。当然,这里不考虑全“0”作为初始状态。 上面证明了若序列A具有周期p,则(xp +1)必能被f (x)整除。另一方面,若f(x)能整除(xp +1),令其商为 又因为在f (x)为既约的条件下
19、,周期p与初始状态无关,现在考虑初始状态a1a2an10,an1,由式 可知,此时有h(x) = 1。故有,34,第12章 正交编码与伪随机序列,上式表明,序列A以p或p的某个因子为周期。若A以p的某 个因子p1为周期,p1 p,则由式 已经证明(xp1 + 1)必能被f (x)整除。 所以,序列A之周期等于使f (x)能整除的中最小正整数p。 【证毕】,35,第12章 正交编码与伪随机序列,本原多项式 定义:若一个n次多项式f(x)满足下列条件: f (x)为既约的; f (x)可整除(xm + 1),m = 2n 1; f (x)除不尽(xq + 1),q m; 则称 f (x)为本原多项
20、式。 由定理12.4可以简单写出一个线性反馈移存器能产生m序列的充要条件为:反馈移存器的特征多项式为本原多项式。,36,第12章 正交编码与伪随机序列,【例】要求用一个4级反馈移存器产生m序列,试求其特征多项式。 这时,n = 4,故此移存器产生的m序列的长度为m = 2n 1 = 15。由于其特征多项式f (x)应可整除(xm + 1) = (x15 + 1),或者说,应该是(x15+1)的一个因子,故我们将(x15+1)分解因子,从其因子中找 f (x): f(x)不仅应为(x15+1)的一个因子,而且还应该是一个4次本原多项式。上式表明,(x15+1)可以分解为5个既约因子,其中3个是4
21、次多项式。可以证明,这3个4次多项式中,前2个是本原多项式,第3个不是。因为,37,第12章 正交编码与伪随机序列,这就是说,(x4 + x3 +x2 +x + 1)不仅可整除(x15+1),而且还可以整除(x5+1),故它不是本原的。于是,我们找到了两个4次本原多项式:和。由其中任何一个都可以产生m序列,用作为特征多项式构成的4级反馈移存器就是上图中给出的。 本原多项式表 由上述可见,只要找到了本原多项式,我们就能由它构成m序列产生器。但是寻找本原多项式并不是很简单的。经过前人大量的计算,已将常用本原多项式列成表备查。在下表中列出了部分已经找到的本原多项式。,38,第12章 正交编码与伪随机
22、序列,39,第12章 正交编码与伪随机序列,在制作m序列产生器时,移存器反馈线(及模2加法电路)的数目直接决定于本原多项式的项数。为了使m序列产生器的组成尽量简单,我们希望使用项数最少的那些本原多项式。 由表可见,本原多项式最少有3项(这时只需要用一个模2加法器)。对于某些n值,由于不存在3项的本原多项式,我们只好列入较长的本原多项式。 由于本原多项式的逆多项式也是本原多项式,例如, (x15 + 1)的因子中的(x4 + x + 1)与(x4 + x3 + 1)互为逆多项式,即10011与11001互为逆码,所以在表中每一本原多项式可以组成两种m序列产生器。,40,第12章 正交编码与伪随机
23、序列,在一些书刊中,有时将本原多项式用8进制数字表示。我们也将这种表示方法示于此表中右侧。例如,对于n = 4表中给出“23”,它表示 2 3 0 1 0 0 1 1 c5c4c3 c2c1c0 即c0 = c1 = c4 = 1,c2 = c3 = c5 = 0。,41,第12章 正交编码与伪随机序列,m序列的性质 均衡性 在m序列的一个周期中,“1”和“0”的数目基本相等。准确地说,“1”的个数比“0”的个数多一个。 【证】设一个m序列的周期为m = 2n 1,则此序列可以表示为 由于此序列中任何相继的n位都是产生此序列的n级移存器的一个状态,而且此移存器共有m个不同状态,所以可以把此移存
24、器的这些相继状态列表,如下表所示。表中每一行为移存器的一个状态。m个相继的状态构成此m序列的一个周期。由此表直接看出,最后一列的元素按自上而下排列次序就构成上式中的m序列。自然,其他各列也构成同样的m序列,只是初始相位不同。,42,第12章 正交编码与伪随机序列,43,第12章 正交编码与伪随机序列,因为此表中每一元素为一位2进制数字,即ai (0, 1),i = 0, 1, ,(m - 1)。所以表中每一位移存器状态可以看成是一个n位2进制数字。这m个不同状态对应1至(2n 1)间的m个不同的2进制数字。由于1和m = (2n 1)都是奇数,故1至(2n 1)间这m个整数中奇数比偶数多1个。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 正交 编码 随机 序列
链接地址:https://www.31doc.com/p-2746865.html