正交编码与伪随机序列————————————————————————————————作者: ————————————————————————————————日期：ﻩ3. 正交编码与伪随机序列在数字通信中,正交编码与伪随机序列都是十分重要的技术。
正交编码不仅可以用作纠错编码，还可用来实现码分多址通信。
伪随机序列在误码率测量、时延测量、扩频通信、通信加密及分离多径等方面有十分广泛的应用。
3.1. 正交编码一、几个概念 1、互相关系数设长为ｎ的编码中码元只取+１、-1，x 和ｙ是其中两个码组)...,(21n x x x x =，)...,(21n y y y y =,其中)1,1(,-+∈i i y x则ｘ、y 间的互相关系数定义为∑==ni i i y x n y x 11),(ρ如果用0表示+1、1表示-1，则DA DA y x +-=),(ρ,其中A 是相同码元的个数，D 为不同码元的个数。
2、自相关系数自相关系数定义为:∑=+=ni j i i x x x n j 11)(ρ，其中下标的计算按模n 计算。
3、正交编码若码组C y x ∈∀,，（C 为所有编码码组的集合)满足0),(=y x ρ,则称C 为正交编码。
即：正交编码的任意两个码组都是正交的。
例1：已知编码的4个码组如下:)1,1,1,1();1,1,1,1();1,1,1,1();1,1,1,1(4321--=--=--=++++=S S S S试计算1S 的自相关系数、21,S S 的互相关系数。
4、超正交编码若两个码组的互相关系数0<ρ，则称这两个码组互相超正交。
如果一种编码中任何两个码组间均超正交,则称这种编码为超正交编码。
例２:例1中取后三个码组,且去掉第１位构成的编码为超正交编码。
(０,1,1），（１,１,０)（1,0,１） 5、双正交编码由正交编码及其反码便组成双正交编码。
例3:正交编码(1,1，1，１)（1,１,0，0）（１,０，０，1）（1,0,1,0） 反码为（0,０，０,0）（０,0,1，1）(0,1，１，0）(０,1,0,１） 双正交码中任意两个码组间的互相关系数为０或-1。
二、哈达玛矩阵哈达玛矩阵的行、列都构成正交码组，在正交编码的构造中具有很重要的作用。
哈达玛矩阵的构成： 2阶哈达玛矩阵⎥⎦⎤⎢⎣⎡-=11112H 4阶哈达玛矩阵⎥⎦⎤⎢⎣⎡-=22224H H H H H … 哈达玛矩阵的所有行之间互相正交,所有列之间互相正交。
哈达玛矩阵经过行列交换后得到的矩阵仍然正交,沃尔什矩阵可以通过哈达玛矩阵按交变的次数排列顺序构成。
例4：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡------=1111111111111111W 3.2. 伪随机序列伪随机序列的应用:通信系统的测试、保密通信、扰码等。
伪随机序列的产生：m 序列、M 序列、GOLD 序列等。
3.2.1. ｍ序列一、m 序列的产生1、最长线性反馈移位寄存器序列m 序列是最长线性反馈移位寄存器序列的简称,它是由带线性反馈的移位寄存器产生的周期最长的序列。
举例说明：输出输出图1A 图1B图1A ： 图１B 初始状态： １00０ １0００ 11001１001110 ０1１0 11１1 101１ 01１１ 0１01 1０１1 0010 0101 0001 101０ 1000 110１ 0１10 ０011 １00１ ０１０0 ０010 00０1 1000可以看到图1Ａ的输出的周期为1５,除去全０外,图１A 的输出是周期最长的的序列。
我们希望尽可能少的级数产生尽可能长的序列。
一般说来,一个n 级反馈移存器可能产生的最长周期为12-n 。
反馈电路如何连接才能输出序列最长？是本节要讨论的问题。
2、m 序列的特征方程移存器的结构用特征方程表示：∑==+++=ni i i nn x c x c x c c x f 010...)(3、m 序列的递推方程∑=-=ni i k i k a c a 14、m 序列的母函数∑∞==++++=010......)(k k k nn x a x a x a a x G5、几个有用的定理用来构造m 序列定理一、)()()(x h x G x f =,其中)(x h 为次数低于)(x f 的次数的多项式。
证明：∑∑∑∑∑∞=--==--∞=∞====1100)(k i k ik ni ii ini ik ik i k k kkx axc x xac x ax G∑∑=∞=----++=ni k k k iiii x a x a x ax c 111)...(∑∑==----+++=ni ni i i iii i x G x c x a x ax c 1111)()...(∑∑==----++=+ni ni i i i i ii x a x a x c x G x c 1111)...()()1(10=c 得到如下关系：)()()(x h x G x f =可以看到，)(x h 的次数小于n 。
当电路给定后，)(x h 只取决于初始状态。
定理二、一ｎ级线性反馈移位寄存器的相继状态具有周期性,周期为12-≤np 。
证明:反馈寄存器状态取决于前一状态，因此只要产生的状态与前面某一时刻相同，则以后的状态肯定是循环的，因此具有周期性。
移存器一共有n 个,因此只有n 2种组合，因此经过它的周期最大为n 2。
而在线性结构中,全0状态的下一状态为0，因此在长周期的序列中，寄存器状态不应该出现全０,因此寄存器状态周期12-≤np 。
定理三、若序列}{k a A =具有最长周期12-=np ,则其特征多项式)(x f 应为既约多项式。
证明:用反证法。
若)()()(21x f x f x f = 则：)()()()()()()(2211x f x h x f x h x f x h x G +==且有)(),(21x f x f 的次数21,n n 满足n n n =+21。
可以将上述序列看成2个序列的和，因此他们的周期分别为21,p p ，根据定理二,12321222)12)(12(),(212121-<-≤+--=--≤=n n n n n n n p p LCM p不是最长序列。
定理四、一个线性移位寄存器的特征多项式)(x f 若为既约的,则由其产生的序列}{k a A =的周期等于使)(x f 能整除的)1(+p x 最小正整数ｐ。
证明：∑∞===0)()()(k k k x a x G x f x h ......)(...)(...02101110++++++++=--a x x a a x x a x a a p p p p)......)(1(11102--+++++=p p p p x a x a a x x )...(111110--++++=p p px a x a a x经整理后，得到1110...)()1)((--+++=+p p p x a x a a x f x x h因此,)(x f 是)1(px +的因子,即周期为p 的序列的f )(x 整除能)1(px +。
反之,若)(x f 能整除)1(px +，令其商为1110...--+++p p x b x b b则因为)(x f 为既约的，因此序列的长度与初始状态无关,取初始状态为0０0.．1)......)(1(1...)(1)()()(111021110----+++++=++++===p p p p pp p x b x b b x x x x b x b b x f x f x h x G 周期为p 。
5、本原多项式若一个n 次多项式满足如下条件: （1)、)(x f 是既约的(2)、)(x f 可整除mx +1,12-=nm (3)、)(x f 除不尽1+qx ,m q < 则称)(x f 为本原多项式。
由本原多项式产生的序列一定是m 序列。
二、m 序列的性质 1、均衡性在m 序列的一个周期中,“0”“1”的数目基本相等。
“1”比“０”多一个。
2、游程分布游程：序列中取值相同的那些相继的元素合称为一个“游程”。
游程长度:游程中元素的个数。
m 序列中，长度为1的游程占总游程数的一半;长度为2的游程占总游程的1/4， 长度为ｋ的游程占总游程数的k-2。
且长度为ｋ的游程中,连０与连１的游程数各占一半。
如上例：１001,1001游程总数:ｋ=4 １；k ＝３ 1；k=2 ２;k=1 4游程的分布与随机序列的分布一致。
3、移位相加特性一个ｍ序列p M 与其经任意延迟移位产生的另一不同序列r M 模2相加，得到的仍是p M 的某次延迟移位序列s M ,即s r p M M M =⊕。
如果将m 序列的所有移位码组构成一个编码，则该编码一定是线性循环码,由于线性循环码的特性可以得到上述的性质。
4、自相关函数周期函数)(t s 的自相关函数定义为:⎰-+=2/2/000)()(1)(T T dt t s t s T R ττ,式中0T 是)(t s 的周期。
定义序列),...,(21n x x x x =的自相关函数为∑∑⎰⎰∑=+=-+-===+=ni j i i ni i j i i i i ni x x n dt x x n dt j t s t s n j R 11)1(0)1(0111)()(1)(000τττττττ nD A -=n x x x x j i j i 的数目的数目]1[]0[=+-=+=m 序列的自相关函数：由m 序列的性质，移位相加后还是ｍ序列，因此0的个数比1的个数少1个。
所以,当i j ≠时，nj R 1)(-= ⎩⎨⎧-=n j R /11)(1...2,10-==n j j 连续的表示⎪⎩⎪⎨⎧-=≤-≤-+-=p i p T iT iT T p R /1...2,1,0,/||0||11)(0000τττ 见图10-４。
5、功率谱密度对上述自相关函数进行傅立叶变换,得到ｍ序列的功率谱密度:∑∞≠-∞=+-⎥⎦⎤⎢⎣⎡+=0202002)(1)2(2/)/sin(1)(n n s pT n p T p T p p P ωδπωδωωω当∞→∞→00/,T m T ,可以看到m 序列的噪声功率谱密度为近似白噪声功率谱。
6、伪噪声特性如果我们对一个正态的白噪声进行采样，若取样值为‘＋’，则记为1,为‘-’记为0，则构成一个随机序列,该随机序列有如下性质：（1）序列中0、1个数出现概率相等（2）序列中长度为1的游程占1／2，长度为２的游程占1/4,…且长度为k的游程中,０游程与1游程个数相同。
（3）该序列的噪声功率谱为常数。
可见，ｍ序列的性质与随机噪声相似，因此称为伪随机序列。
