正交编码与伪随机序列
————————————————————————————————作者: ————————————————————————————————日期：
ﻩ
3. 正交编码与伪随机序列
在数字通信中,正交编码与伪随机序列都是十分重要的技术。正交编码不仅可以用作纠错编码，还可用来实现码分多址通信。伪随机序列在误码率测量、时延测量、扩频通信、通信加密及分离多径等方面有十分广泛的应用。
3.1. 正交编码
一、几个概念 1、互相关系数
设长为ｎ的编码中码元只取+１、-1，x 和ｙ是其中两个码组
)...,(21n x x x x =，)...,(21n y y y y =,其中)1,1(,-+∈i i y x
则ｘ、y 间的互相关系数定义为
∑==n
i i i y x n y x 1
1),(ρ
如果用0表示+1、1表示-1，则
D
A D
A y x +-=
),(ρ,其中A 是相同码元的个数，D 为不同码元的个数。 2、自相关系数
自相关系数定义为:∑=+=n
i j i i x x x n j 1
1)(ρ，其中下标的计算按模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阶哈达玛矩阵
⎥⎦
⎤
⎢
⎣⎡-=2222
4H H H H H … 哈达玛矩阵的所有行之间互相正交,所有列之间互相正交。
哈达玛矩阵经过行列交换后得到的矩阵仍然正交,沃尔什矩阵可以通过哈达玛矩阵按交变的次数排列顺序构成。 例4：
⎥⎥⎥⎥
⎦
⎤⎢⎢⎢
⎢⎣⎡------=1111111111111111W 3.2. 伪随机序列
伪随机序列的应用:通信系统的测试、保密通信、扰码等。 伪随机序列的产生：m 序列、M 序列、GOLD 序列等。
3.2.1. ｍ序列
一、m 序列的产生
1、最长线性反馈移位寄存器序列
m 序列是最长线性反馈移位寄存器序列的简称,它是由带线性反馈的移位寄存器产生的周期最长的序列。 举例说明：
输出输出
图1A 图1B
图1A ： 图１B 初始状态： １00０ １0００ 11001１00
1110 ０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 序列的特征方程
移存器的结构用特征方程表示：
∑==+++=n
i i i n
n x c x c x c c x f 0
10...)(
3、m 序列的递推方程
∑=-=n
i i k i k a c a 1
4、m 序列的母函数
∑∞
==++++=0
10......)(k k k n
n x a x a x a a x G
5、几个有用的定理用来构造m 序列
定理一、)()()(x h x G x f =,其中)(x h 为次数低于)(x f 的次数的多项式。
证明：∑∑∑∑
∑∞
=--==--∞
=∞
====
1
100)(k i k i
k n
i i
i i
n
i i
k i
k i k k k
k
x a
x
c x x
a
c x a
x G
∑∑=∞
=----++=n
i k k k i
i
i
i x a x a x a
x c 1
1
1)...(
∑∑==----+++=
n
i n
i i i i
i
i i x G x c x a x a
x c 11
1
1)()...(
∑∑==----++=+n
i n
i i i i i i
i x a x a x c x G x c 1
1
11)...()()1(
10=c 得到如下关系：
)()()(x h x G x f =
可以看到，)(x h 的次数小于n 。当电路给定后，)(x h 只取决于初始状态。 定理二、一ｎ级线性反馈移位寄存器的相继状态具有周期性,周期为12-≤n
p 。 证明:反馈寄存器状态取决于前一状态，因此只要产生的状态与前面某一时刻相同，则以后的状态肯定是循环的，因此具有周期性。
移存器一共有n 个,因此只有n 2种组合，因此经过它的周期最大为n 2。
而在线性结构中,全0状态的下一状态为0，因此在长周期的序列中，寄存器状态不应该出现全０,因此寄存器状态周期12-≤n
p 。
定理三、若序列}{k a A =具有最长周期12-=n
p ,则其特征多项式)(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
