12正交编码和伪随机序列

12.1正交编码12.2伪随机序列12.4伪随机序列的其它应用12.5小结第12章正交编码和伪随机序列引言：正交编码可用作纠错码；也可用来实现码分多址通信。伪随机序列可广泛应用于误码率测量、时延测量、扩频通信、通信加密及分离多径等方面。12.1正交编码12.1.1正交编码的基本概念1、连续信号的正交0021Tdttsts2、数字信号（码组或码字）的正交nnyyyyyxxxxx，，，，，，，，32132112.1正交编码1,11,1yxyxnyxniii＝定义相关系数：例如：右图所示可看成四个码组：3、正交编码s1(t)s2(t)s3(t)s4(t))1,1,1,1(:)()1,1,1,1(:)()1,1,1,1(:)()1,1,1,1(:)(4321tstststs12.1正交编码类似上述互相关系数的定义，可以对于一个长为n的码组x定义其自相关系数为式中，x的下标按模n运算，即有xn＋k≡xk。例如，设4、自相关系数1,1,011njxxnjnijiix12.1正交编码)1,1,1,1()(4321xxxxx12.1正交编码041413141412041411141034231241132413423112144332211112xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxniiixniiixniiixniix用二进制数字表示互相关系数：则上述互相关系数定义式将变为按上述规定，上面的例子可改写成：。中对应码元不同的个数和；中对应码元相同的个数和yxDyxADADAyx,)1,0,1,0(:)()0,1,1,0(:)()1,1,0,0(:)()0,0,0,0(:)(4321tstststs12.1正交编码将其代入12.1－8，计算出的互相关系数仍为零。上式中，若用x的j次循环移位代替y，就得到x的自相关系数ρx(j)。具体地讲，令jnjjnxxxxxxyxxxx，，，，，，，，，，21212112.2.2哈达玛矩阵12.1正交编码矩阵的每一行或每一列都是正交码组。是法国数学家Hadamard首先构造出来的，简记为H矩阵，仅由元素+1和-1构成。2H12.1正交编码1、最低阶的H矩阵：222HHHNN、2222224HHHHHHH12.1正交编码式中，N＝2m；－直积。上式中直积是指将矩阵HN/2中的每一个元素用矩阵H2代替。例如：－＋＋－＋－－＋＋＋－－－－＋＋＋－＋－－＋－＋－－－－＋＋＋＋＋－－＋＋－－＋－－＋＋－－＋＋－＋－＋－＋－＋＋＋＋＋＋＋＋＋＝4444248HHHHHHH12.1正交编码12.1正交编码性质：正规H矩阵经过各种交换或改变后仍为H矩阵，但不一定是正规的了。H矩阵是正交方阵。若把其中每一行看作是一个码组，则这些码组也是互相正交的，这种编码在纠错编码理论中称为里德-缪勒(Reed-Muller)码。12.1正交编码12.2.3沃尔什函数和沃尔什矩阵1、沃尔什函数定义)]4/1(2,[)1()]4/1(2,[()1(),2(2/jwaljwalpjwalpjpj2/1,2/102/12/11),0(wal式中p=0或1，j=0，1，2，，及指数中的[j/2]表示整数。12.1正交编码2、正弦和余弦函数可以构成一个完备正交函数系。由于正弦和余弦函数具有完备和正交性，所以由其构成的无穷级数或积分（即傅里叶级数和傅里叶积分）可以表示任一波形。类似地，由取值“＋1”和“－1”构成的沃尔什函数也具有完备正交性，也可以用其表示任一波形12.1正交编码3、前8个沃尔什函数的波形示于下图中+10+10-1+10-1+10-1+10-1+10-1+10-1+10-112.1正交编码4、沃尔什函数表示成矩阵形式例如，上图中的8个沃尔什函数可以写成如下沃尔什矩阵：W12.1正交编码由上图和矩阵可以看出，沃尔什矩阵是按照每一行中“＋1”和“－1”的交变次数由少到多排列的。沃尔什函数（矩阵）天生具有数字信号的特性，所以它们在数字信号处理和编码理论中有不小应用前景。21jfknnnkPfDTFTRkRkexi+1的取值与xi无关，+1、-1的概率各为½，此为真随机序列。满足WSS（广义平稳）特性，且均值为0。功率谱：12.2.1基本概念1、真随机序列（二进制噪声序列）nRkEnikni12.2伪随机序列2、伪随机序列简介具有类似于随机噪声的一些统计特性，同时又便于重复产生和处理。优点：它具有随机噪声的优点，又避免了随机噪声的缺点，因此获得了日益广泛的实际应用。12.2伪随机序列目前广泛应用的伪随机噪声都是由周期性数字序列经过滤波等处理后得出的。12.2.2m序列1、m序列的产生m序列是由带线性反馈的移存器产生的周期最长的一种序列。12.2伪随机序列1、举例说明，如下图所示12.2伪随机序列12.2伪随机序列其初始状态为(a3,a2,a1,a0)=(1,0,0,0)。4级移存器可以有24=16种可能的不同状态，除全零外，只有15种可用，即由4级移存器产生的序列周期最长为15。由上例可见，一般来说，一个n级线性反馈移存器可能产生的最长周期等于(2n-1)。2、一般产生方法12.2伪随机序列）（模210112211niininnnnnacacacacaca递推方程：niikikaca1◆特征方程（特征多项式）ci的取值决定了移存器的反馈连接和序列的结构，故ci是一个很重要的参量。现在将它用下列方程表示：称特征方程。上例的特征方程为12.2伪随机序列niiinnxcxcxcxccxf02210)(41)(xxxf定理12.3：若序列A={ak}具有最长周期(p=2n-1)，则其特征多项式f(x)应为既约多项式。所谓既约多项式是指不能分解因子的多项式。定理12.4：一个线性反馈移存器能产生m序列的充要条件为：反馈移存器的特征多项式为本原多项式。12.2伪随机序列游程是指一个序列中取值相同的那些相继的元素。元素个数称为游程长度。2、m序列的性质（1）均衡性在m序列的一个周期中，“1”和“0”的数目基本相等，准确地说，“1”的个数比“0”的个数多1个。（2）游程分布12.2伪随机序列比如上例中，长度为4的游程有一个，为“1111”，长度为3的游程有一个，为“000”，长度为2的游程有2个，即“11”与“00”，····。一般来说，在m序列中，长度为1的游程占游程总数的1/2，长度为2的游程占游程总数的1/4，长度为3的占1/8，·············12.2伪随机序列（3）移位相加特性一个m序列Mp与其经过任意次延迟移位产生的另一个不同序列Mr模2相加，得到的仍是Mp的某次延迟移位序列Ms，即MpMr=Ms（4）自相关函数12.2伪随机序列现在我们讨论m序列的自相关函数。由12.2节互相关系数定义式得知，m序列的自相关函数可以定义为：式中A－对应元素相同的数目；D－对应元素不同的数目；m－m序列的周期。12.2伪随机序列121,mjmDAj、、、上式还可以改写成如下形式：121101121,1mjmjjRmjmjR、、、、、、12.2伪随机序列由m序列的延迟相加特性可知，01()miijiijaaaaj的数目的数目R(j)是偶函数，即有：m序列的连续相关函数R(τ)可表示如下：如下图所示、、、，－＝21001110000imTiTiTTmmR12.2伪随机序列整数，－jjRjR12.2伪随机序列（5）功率谱密度如下图所示20,020021222sin1mTnmTmTmmPnns12.2伪随机序列12.2伪随机序列(6)伪噪声特性具有如下基本性质：A）序列中“＋”和“－”的出现概率相等；B）一般来说，长度为k的游程占游程总数的2-k，“＋”游程和“－”游程约各占一半。12.2伪随机序列C）白噪声的功率谱密度为常数，功率谱密度的逆傅里叶变换，即自相关函数，为一冲激函数()。由于m序列的均衡性、游程分布、自相关特性和功率谱与上述随机序列的基本性质很相似，所以通常认为m序列属于伪噪声序列或伪随机序列。12.2伪随机序列12.2.3其他伪随机序列简介1、M序列定义：由非线性反馈移存器产生的周期最长的序列称为M序列。由上节对m序列产生器的分析可知，一个n级m序列产生器只可能有(2n–1)种不同的状态。但是n级移存器最多可有2n种状态，12.2伪随机序列在m序列中不能出现的是全“0”状态。在线性反馈条件下，全“0”状态出现后，产生器的状态将不会再改变；但是在非线性反馈条件下，却不一定如此。因此，非线性反馈移存器的最长周期可达2n，我们称这种周期长达2n的序列为M序列12.2伪随机序列12.2伪随机序列◆M序列的产生方法：目前，如何产生M序列的问题，尚未从理论上完全解决，人们只找到很少几种构造它的方法。下面仅简单介绍利用m序列产生器构成M序列产生器的方法。首先观察下图中的例子。它是一个n=4级的m序列产生器。图中给出了它的15种状态。若使它增加一个“000”状态，就可变成M序列产生器了。12.2伪随机序列因为移存器中后级状态必须是由其前级状态移入而得，故此“0000”状态必须处于初始状态“1000”之12.2伪随机序列前和“0001”状态之后。这就是说，我们需要将其递推方程修改为非线性方程，使“0001”状态代入新的递推方程后，产生状态“0000”（而不是“1000”），并且在“0000”状态代入后产生状态“1000”（而不是保持“0000”不变）。12.2伪随机序列修改前的递推方程为为满足上述要求，修改后的递推方程应为411kkniikikaaaca41321321414321432141ikkkikikkkkkkkkkkkkkkkkaaaacaaaaaaaaaaaaaaaa12.2伪随机序列对于n级m序列产生器也一样。为使n级m序列产生器变成M序列产生器，也只需使其递推方程改为有了递推方程，就不难构造出此M序列产生器。例如用这种方法得到的一个4级M序列产生器如下图所示11141121njikniikiinkkkikikaacaaaaca12.2伪随机序列12.2伪随机序列◆M序列的性质M序列与m序列类似，也在一定程度上具有噪声特性。它满足m序列的前两个性质，即：在M序列的一个周期中，出现“0”与“1”的数目相等。在n级M序列的一个周期中，游程共有2n-1个，其中长度为k的游程12.2伪随机序列占1/2k，1kn–2；长为n的游程有两个，没有长为(n–1)的游程。在同长的游程中，“0”游程和“1”游程各占一半。这两个性质的证明方法与m序列的一样。但是，M序列不再具有m序列的移位相加特性及双值自相关特性。12.2伪随机序列2、二次剩余序列定义：二次