发布时间 : 星期日 文章m序列在扩频通信中的应用研究更新完毕开始阅读
m序列在扩频通信中的应用研究
第二章 序列的基础理论
2.1 有限域上的基本概念
我们研究的序列都是有限域上的序列,因此,作为序列设计与分析基础理论知识,我们有必要介绍一下有限域的相关理论。 2.1.1 有限域的代数结构
定义2.1 含有有限个元素的域叫做有限域(Galois域)。
最简单而又最基本的有限域是整数环Z模P的剩余类z/(p),其中p为素数.为方便起见,用GF(p)={0,1,?,p一1),表示p元有限域z/(p),而对于一般的有限域则用GF(q)来表示,记GF(q)??GF(q)/{0},表示是GF(q)中的乘法群,它是一个q-1阶循环群。
域F的所有子域的交集仍是F的子域,我们称这个子域为F的素域,易知素域是F的最小子域.设F是任意域,则F的素域或者同构于有理数域Q,或者同构于整数环Z模某个素数P的剩余类z/(p)。
定义2.2 设F是任意域,如果F的素域同构于有理数域Q,则称域F的特征为0,记为CharF=0;如果F的素域同构于整数环Z模某个素数P的剩余类环z/(p),则称域F的特征为p,记为CharF=p。
域特征的定义还等价于:设e是域F的单位元,如果对于任意正整数n,均有
ne?0,则称F的特征为0;否则称满足ne?0的最小正整数n为域F的特征.若域F
的特征为P,则对于任意??F,p??0。
ppp定理2.1 设有限域F的特征为P,则对F中任意元素α,β,(???)????,ppp(???)???? 。
设E是域F的扩域,0≠α∈E,如果存在F[x]中的非零多项式f(x),使f(α)=0,则称α为F的代数元;否则称α为F的超越元.如果E中每个元素都是F的代数元,则称E为F的代数扩张;否则称E为F的超越扩张.域F的全体代数元组成的集合称为F的代数闭包。
定理2.2 设F是一个域,f(x)∈F[X]为不可约多项式,则存在F的扩域E,使得E包含F的全部根.若E为F的代数扩张,则E中每个元素都是F的代数元,从而是F[x]中某个不可约多项式的根。
定义2.3 设E是F的代数扩张,f(x)是F[x]中首项系数为l的多项式, Deg f(x)≥1,如果满足:
4
m序列在扩频通信中的应用研究
(1) f(x)在E中能够分解成一次因式的乘积,即
f(x)?(x??1)(x??2)?(x??3),?i?E(i?1,2,?,s)
(2) E?F(?1,?2,??s),即E是F添加?1,?2,??s得到的有限扩张。则称E是f(x)在F上的分裂域。
由分裂域的定义知,f(x)在F上的分裂域实质上是F包含f(x)全部根的最小扩域.对每个素数P和每个正整数n,都存在一个pn元有限域,并且pn元有限域都同构于xp?x在GF(p)上的分裂域。
设??GF(pn), ?在有限域GF(pn)上的极小多项式定义为GF(pn)上以a为 根的首项系数为1且次数最低的多项式,记之为m?(x)。一般而言,若a是GF(pn)上的代数元,则a的极小多项式m?(x)一定是GF(pn)[x]中的不可约多项式.有限域GF(pn)的乘法群GF(pn)?的生成元称为GF(pn)的本原元,而以本原元为根的极小多项式称为GF(pn)的本原多项式。
若f(x)是f(x)?GF(q)[x]中n次不可约多项式,则GF(qn)包含f(x)的全部根.特别地,如果a为f(x)在GF(qn)中一根,则f(x)在GF(qn)中的n个不同根为
?,?,?qq2n,?,?qn?1,称这些根为f(x)的共轭根。
定义2.4 设f(x)?GF(q)[x],若f(O)≠0,则f(x)的阶定义为满足f(x)xe?1的最小正整数e,记为ord(f);若f(O)=0,则存在h∈N,使得f(x)?xhg(x),其中g(O)≠0,这时f(x)的阶定义为g(x)的阶ord(g)。
多项式f(x)的阶也称为f(x)的周期或f(x)的指数,也记为P(f)。 定理2.3 设f(x)?GF(q)[x]为n次不可约多项式,则 ord(f)等于f(x)的任意一个根在GF(qn)?中的阶。
推论2.1 若f(x)?GF(q)[x]为n次不可约多项式,则ord(f)qm?1。 2.1.2 有限域上的迹函数理论
定义2.5 设有限域是有限域GF(pn)的e次扩张(n?em),则对任意的
??GF(q),定义GF(p)到GF(p)的迹函数如下:
n?nm
Tr(a)?a?anmpm?ap2m???ap(t?1)m
迹函数具有下列性质:
(1)对任意??GF(pn),Trmn(api)?Trmn(a)pi,i?0,1,2,3,?
m(2)对任意??GF(pn),Trmn(?p)?Trmn(?)
(3)对任意u,v?GF(pm), ?,??GF(pn),Trmn(?????)??Trmn(?)??Trmn(?)
6
m序列在扩频通信中的应用研究
(4)对任意??GF(pm),Trmn(?)?e? ; (5)对任意??GF(pm),方程Trmn(x)??在中解数恰为pn?m
n(6)对任意??GF(pn),Trmn(?)?TrmrmTrrm(?),其中re。
由性质(3)知,迹函数是从有限域GF(pn)到它的一个子域GF(pm)上的线性映射.进一步,它还可以描述出所有从GF(pn)到GF(pm)上的线性变换,并且与选择的基无关。
一般情况下,有限域E到它的子域F的迹函数可以记为TrE/F(?), 在不至于混淆的情况下也可以记为Tr(·)。
定理2.4 设F是一有限域,E是F的一个有限扩张,E可看作是F上的向量空
间,则从E到F的线性变换可表示为L?,??F,其中L?(x)?TrE/F(?x), ?x?E 。 进一步地,如果β,λ∈E,β≠λ,则有L??L?。
定理2.5 设F=GF(q)是一有限域,E是F的一个有限扩张,则对
??E,TrE/F(?)?0当且仅当存在β∈E,使得???q??。
定理2.6 设p是素数,ω为P次单位根,Tr(?)表示GF(pn)到GF(p)的迹函数,则对于???GF(pn) ,有
??nTr(?x)x?GF(p)??0,??0??n??p,??0
定理2.6对于求解序列的互相关函数起着至关重要的影响,目前大多数的序列能够求出其互相关函数都归功于这个引理。
设F是有限域K的有限扩张,{?1,?2,?,?m}是F在K的一组基,则对于任一元素ξ∈F有唯一的表示:
??c1(?)a1?c2(?)a2??cm(?)am
其中cj(?)?K,1?j?m,1≤j≤m且cj由ξ唯一确定.从而,cj:??cj(?)是F到K的线性变换,根据定理2.4,存在?j?F使得cj(?)?TrF/K(?j?)对所有ξ∈F都成立,令???i, i=1,2,?,m,则当j=i时,cj(?i)?TrF/K(?j?i)?1;当j?i时,
cj(?i)?TrF/K(?j?i)?0 若对等式
d1?1?d2?2??dm?m?0,di?K,i?1,2,?,m两边同时乘以?i,再取迹函数TrF/K(?)便可得di?0,i?1,2,?,m.从而,
{?1,?2,??m}也是有限域F在其子域K上的一组基。
{?1,?2,??m}和{?1,?2,??m}是定义2.6 设K是有限域,F是K的有限扩张,
F到K上的两组基,若对1≤i、j≤m,有
7
m序列在扩频通信中的应用研究
则称这两组基为对偶基。
?0, i?jTrF/K(?i?j)???1, i?j
由上面的讨论知道,对于F在K上的任意一组基{?1,?2,??m},都存在一组对偶基{?1,?2,??m}。
记Vpn为有限域GF(p)上的n维向量空间,则有限域GF(pn)中元素x与向量
空间Vpn中元素x有如下关系:
n
x??x?ii?1i??x?(x1,x2,?xn)
其中,1≤i≤n,{?1,?2,??m}是有限域GF(pn)在其子域GF(p)上的一组基.这就是说有限域GF(pn)中的元素与向量空间Vpn中的元素有一一对应的关系.令ff(x)是从向量空间Vpn到有限域GF(p)的函数,用有限域GF(pn)中的元素x代替向量空间Vpn中的元素x,则由GF(pn)到GF(p)的函数f(x)等同于由向量空间Vpn到GF(p)的函数f(x).特别地,当f(x)?Tr(bx)时,令
n
b??b?ii?1i??b?(b1,b2,?bn)
这里{?1,?2,??m}为{?1,?2,??m}的一组对偶基,则
Tr(bx)?b?x
2.2 线性反馈移位寄存器序列
在序列密码中,设明文消息序列为P?p1p2?,密钥流K?k1k2?(密钥流是 由密钥或者是种子密钥通过密钥流生成器得到),密文序列C?c1c2?由明文消息 序列与密钥流逐位模二相加得到,即C?P?K,其中ci?pi?ki,解密过程和加密过程一样,P?C?K,其中pi?ci?ki。
序列密码具有实现简单、便于硬件实现、加解密处理速度快、没有或只有 有限的错误传播等特点,在实际应用中,特别是专门的机密机构中保持着优势,典型的应用领域包括军事通信等。1949年Shannon证明了“一次一密”密码体制是绝对安全的,这给序列密码技术的研究以强大的理论支持,序列密码的加密方案的发展是模仿“一次一密\系统的尝试,如果序列密码所产生的是真正随机的、 与消息流长度相同的密钥流,则此时的序列密码就是“一次一密\密码体制。但 我们知道序列密码的密钥流是基于一定的算法产生的看似随机的序列流,我们称 之为伪随机序列,它不可能完全随机,我们希望这伪随机序列满足尽可能多的随
8