（通信与信息系统专业论文）fft与fht快速相关检测算法的研究.pdf

一删删必必 r e s e a r c ho ff f tf a s tc o r r e l a t i o na l g o r i t h m s a n df h tf a s tc o r r e l a t i o na l g o r i t h m s at h e s i ss u b m i t t e dt o s o u t h e a s tu n i v e r s 时 f o rm ea c a d e m i cd e g r e eo fm a s t e ro f e n g i n e e r i n g b y z h 葫gp i n g y i s u p e r v i s e db y p r o 、7 以m gj i e s c h 0 0 1o fi n f o m a t i o ns c i e n c ea n d e n g i n e e r i n g s o u t h e a s t u h i v e r s 时 j a n u 唧2 0 l o 1 一 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 研究生签名：三率日 期：出工十 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 研究生签名：刍堕晕i 导师签名： 一一 摘要 摘要 直接序列扩频通信是实现极低谱密度无线通信的途径之一，得到了广泛的应用，例 如卫星定位导航系统等扩频通信技术。直接序列扩频通信技术通过将传送的信息数据用 伪随机编码调制，实现频谱扩展以后再传输，接收端则采用相同的编码进行解调和相关 处理，恢复原始数据，因此对长伪随机码的相关检测是直接序列扩频通信技术中很重要 的一步。 本论文详细描述了基于f f t ( f a s tf o u r i e rt r a i l s f o r m ) 的相关检测算法并针对f f t 移位重复法的性能中存在的偏差给出了改进的方法，重点研究了用f h t ( f a s t h a d 删 t r a l l s f o 肌) 代替f f t 对各种伪随机序列进行快速相关检测的算法，并对这一系列算法 进行了计算复杂度的分析与比较，主要工作可以概括如下： 首先，主要介绍了伪随机码的特点和性质，在现有的f f t 快速相关检测方法的研究 基础上，针对f f t 移位重复法的性能中存在的偏差给出了改进的方法，改进后的方法与 之前有损的f f t 移位重复法相比，复杂度没有增加。 。其次，阐述了f h t 相关检测算法的基本原理，并结合g o l d 序列、k a s 锄i 大小集合 序列等伪随机码的特点，用f h t 代替f f t ，完成对基于m 序列构造的伪随机序列的快 速相关检测。 由于f h t 相关检测算法是根据h a d a m a r d 矩阵和哈达码变换的性质和原理，利用m 序列构成的m 矩阵与w a l s h - h a d a h l a r d 矩阵之间的关系，计算得到某个序列和m 序列之 间的互相关值，且f h t 中不包含乘法运算，只有加法运算，因此f h t 相关检测算法相 比f f t 相关检测算法具有算法复杂度的优势。 研究分析结果表明，对于g o l d 码、k a s 锄i 小集合序列和某些k a s 锄i 大集合序列， 采用本文提出的相应f 肿快速相关方法检测算法比f f t 频域相关法进行相关检测，在 相关检测性能一致的情况下，能节省9 0 以上的运算量，并且节约的运算量随着码长的 增加而增大。 关键字：快速傅里叶变换( f f t ) ，快速哈达码变换( f h t ) ，快速相关检测，g o l d 序列， k a s 锄i 序列 a b s t r a c t d i r e c ts e q u e i l c es p r e a d s p e c 咖mc o m 舢l i l i c a t i o nt e c h n o l o g yi so n eo fw a y t 0 笛h i e v e t h ev e r yl o ws p e c 仃a ld e 璐i t yo fw i r e l e s sc o i i l 】m u l l i c a t i o n s ，s u c ha st h es a t e l l i t ep o s i t i o n i n g 锄d m v i 弘t i o ns y s t e m s d 曲c ts e q u e n c es p r e a d s p e c t m mc o m i n u i l i c a t i o nt e c h n o l o g y t os 明d i i l f b m a t i o na n dd a t ab yu s i n gp s e u d o r a n d o mc o d e di n o d u l a t i o nt oa c v et l l es p 赋l d s p e c t m mt r a n s m i s s i o i l ，i nt h er e c e i v e r t h es 锄ec o d ea n dd e m o d u l a t i o na n dc o l l r d a t i o n p r o c e s s i n gi su s e dt or e s t o r et h ed a t a ，s 0t h cf a s tc o r r e l a t i o nd e t e c t i o n i sa i lh p o r t 觚tt 叩i cf o r t h ed i r e 畋s e q v e n c es p r e a d s p e c t m mc o m r n u i l i c a t i o nt e c t m o l o 醪 i nt h ep a p e r m ef a s tc o r r l a t i o nd e t e c t i o na l g o r i t h m sb a s e do nf f t ( f a s tf 0 1 1 r i 盱 1 r a n s f o 册) a r ed e s c r i l ) e dmd e t a i l ，a n dam o d i 丘e dm e t h o di sp r e s e n t e dt or e m o v e 也e d e v i a t i o n se x i s ti nf a s ta c q u i s i t i o ni i lm e o 疆w ea l s of o c u so u rr e s e a r c hi nu s i i l gf h t ( f a s t h a d a m a r dt r a i l s f 0 姗) h l s t e a do ff f tf o rv a r i o u sp s e u d o r a n d o ms e q u e n c e so ff 瓠 c o n l a t i o nd e t e c t i o na l g o r i t h m s ；c o m p u t a t i o l l a lc o i n p l e x i t ya n a l y s i sa n dc o m p a r i s o na r c c a r r i e do u tf o rs e r i e so fa l g o r i t l l i n s t h em a i nw o r kc 锄b es u m m a r 疏d a sf o l l o w s ： f i r s t l y ，w ei n t r o d u c et h ec h a r a c t e ra n dn a t u r eo ft h ep s e u d o r a n d o mc o d e ，m e na m o d i f i e dm e t h o di sp r e s e n t e dt 0r e i n o v et h ed e v i a t i o n se x i s ti nf 酤tc o r r e l a t i o nd e t e c t i o n m e db 嬲e do nf f ri i lt h e o r 弘w i t h o u tc o m p u t a t i o n a lc o n l p l e x i 够i 1 1 c r e a s i l l g s e c o n d ，w ee x p o u n dt h cb a s i cp r 硫i p l e so ft h cf h tc o r r e l a t i o nd e t e c t i o na 1 9 0 r i t h i n c o i l s i d e 血gt h ec 1 1 a r a c t e r i s t i c so f ( 沁l ds e q u e n c e s ，k a s 锄is e q u e n c e s e t c ，u s i n gf h t i n s t e a d o ff f tt 0c o m p l e t et h ef a s tc o 盯e l a t i o nd e t e c t i o no fp s e u d 0 一r a n d o ms e q u e n c eb a s e do nm s e q u e n e s f h tc o h e l a t i o nd e t e c t i o na i g o r i t l l i i li sb a s e do nh a d a m a r dm a t r i c e sa i 岖h a d a m a r d t r a l l s f o h n ，u s 洫gt h ef e l a t i o i l s h i p b e 觚e e nm m a t r 改c o l l s i s t so fms e q u e n c e sa n dt h e w a l s h - h a d a m a r dm a t r i ) 【w ec a l c u l a t et h ev a l u eo fc r o s s c o l l r e l a t i o nb e t w e e nas e q u e n c ea n d ms e q u e n c e b e c a u s et h cf 肿d o e sn o tc o n t a i 璐瑚i u l t i p l i c a t i o no p e r a t i o n s ，b u to n l yt h e a d d i t i o no p e r a t i o n s ，s ot h ef 玎 c o n e l a t i o nd e t e c t i o n a l g o r i t l l i i lc o m p a r e dw i t h f f t c o n e l a t i o nd e t e c t i o na l g o r i t h mh a sc o m p u t a t i o i l a lc o m p l e x i t ya d v a n t a g e 8 t h er e s e a r c hr e s u l t ss h o wt h a t ，f o rt h eg o l dc o d e ，t h es m a l ls e to fk a s a 【i l is e q u e n c e sa n d s o m et y p eo ft h el a r g es e t sk a s 锄is e q u e n c e s ，u s i n gt h ec o r r e s p o n d i n gf h rc o r r e l a t i o n d e t e c t i o na l g o r i t 胁sc o m p a r e dw i t ht h ef f t 厅e q u e n c yd o m a mc o r r e l a t i o nd e t e c t i o nm e t h o d ， c a i ls a v eo v e r9 0 o ft h ec o n l p u t a t i o nu n d e rt h es a m ed e t e c t i o np e r f b 肌a n c e ，a n dt h e 锄o u n t o fc o l i l p l e x i t yr e d u c t i o ni n c r e a s e sw i t hi n c r e a s i n gc o d el e n 舀h 目录 目录 摘要i a b s t r a c t i 目录v 第一章绪论l 1 1 现代通信技术l 1 2 极低谱密度无线通信的研究动态2 1 3 本课题的研究意义3 1 4 论文内容和章节安排3 第二章伪随机码及其相关检测算法介绍5 2 1 伪随机码5 2 1 1 伪随机码的自相关性5 2 1 1 伪随机码的互相关性6 2 2f f t 相关检测算法6 2 2 1 时域相关6 2 2 2 循环相关。6 2 2 3f f t 相关检测7 2 3f h t 相关检测算法7 2 3 1h a d 锄a r d 矩阵7 2 3 2 哈达码变换8 2 33f h t 相关检测。9 2 4 本章小结。9 第三章f f t 相关检测算法l l 3 1 基于f f t 的相关检测算法及其优势。1 1 3 2 移位重复法的f f t 研究：1 5 3 2 1 改进的f f t 移位重复法1 5 3 2 2f f t 移位重复法的复杂度比较1 7 3 3f f t 移位重复法的性能仿真1 7 3 4 本章小结1 9 第四章g o l d 序列的f h t 相关检测2 l 4 1g 0 1 d 序列2 1 4 2g o l d 序列的f h t 相关检测方法2 3 4 3g 0 1 d 序列的f h t 相关检测方法的性能分析2 5 4 4 本章小结2 7 第五章k a s a m i 小集合序列的f h t 相关检测2 9 5 1k a s a m i 小集合序列的构成2 9 5 2k a s a m i 小集合序列的f h t 相关检测方法3 0 5 2 1u - f h t 算法3 0 5 2 2w - f h t 算法3 l 5 3k a s a m i 小集合序列的f h t 相关检测方法的性能分析。3 3 5 。4 本章小结3 5 第六章k a s 锄i 大集合序列的f h t 相关检测3 7 6 1k a s 锄i 大集合序列的构成3 7 v 东南大学硕士学位论文 6 1 1g o i d k a s a r n i 大集合序列3 7 6 1 2g o l d 1 i k e k a s a m i 大集合序列3 8 6 2 a m i 序列的f h t 相关检测方法3 9 6 2 1g o i d k a s a i i l i 大集合序列的f h t 相关检测方法3 9 6 2 2g o l d 1 i k e k a s a m i 大集合序列的f h t 相关检测方法5 2 6 3 a m i 大集合序列的f h t 相关检测方法的性能分析6 l 6 3 1g o l d k a s a r i l i 大集合序列的f h t 相关检测方法的性能分析6 l 6 3 2g o l d 1 i k e k a s a m i 大集合序列的f h t 相关检测方法的性能分析6 4 6 5 本章小结6 7 第七章全文总结6 9 7 1 本论文的研究成果6 9 7 2 进一步的研究方向7 0 j g 【谢7 l 参考文献7 3 绪论 第一章绪论 现代通信技术是2 0 世纪8 0 年代以来发展最快的领域之一，特别是2 1 世纪以来， 其发展及更新更是让人眼花缭乱。现代通信的最终目标是实现任何人可以在任何地点、 任何时间与其它任何人进行任何方式的通信。随着人们对实时信息交流的需求的提高， 新的技术和新的业务不断涌现。目前在深空通信、全球定位系统( g n s s ) 、军事通信和 无线传感器等通信领域中，对扩频技术下的极低谱密度信号的快速相关检测是目前的一 个研究重点，对提高相关无线通信领域的通信质量具有重大意义。 本章将就现代通信技术、极低谱密度信号的研究动态以及本课题的研究意义做进一 步的详述。 1 1 现代通信技术 现代主要通信技术【卜6 】有数字通信技术，卫星通信技术、移动通信技术、扩频通信 技术等。 数字通信是用数字信号作为载体来传输信息，数字通信以其抗干扰能力强，通信质 量不受距离的影响，便于存储和保密，处理和交换等特点，已经成为现代通信网中的最 主要的通信技术基础，广泛应用于现代通信网的各种通信系统。 卫星通信简单地说就是无线电通信站利用人造地球卫星作为中继站，在两个或多个 地球站之间进行的通信，主要包括卫星和地球站两部分。卫星通信的主要优点有：通信 范围大；不易受陆地灾害的影响；可以同时在多处接收，能经济地实现广播、多址通信 等。卫星通信的应用范围很广，不仅应用于语音、电报、数据等的传输，还特别适用于 广播电视节目的传播，2 0 世纪9 0 年代以来，卫星通信也向全面满足个人通信和宽带通 信需求的方向发展。 移动通信是指通信的双方至少有一方是在移动中进行信息交换的通信方式，是固定 通信的延伸，也是实现人类理想通信必不可少的手段。移动通信具有以下特点：利用无 线电波进行传播，多径效应引起信号衰落；移动形成的多普勒频移将产生附加调制：强 干扰情况下工作，主要干扰有人为干扰、互调干扰、邻道干扰以及同频干扰；无线频率 资源有限，必须采用频谱和无线频道有效利用技术；移动台随持有者经常移动，故移动 通信必须具有位置登记，越区切换以及漫游访问等跟踪交换技术。目前移动通信朝着高 码率、高频带、低价格的方向发展。 扩频通信技术即扩展频谱通信技术是当今信息社会最为先进的无线电通信技术之 一，将待传送的信息数据被伪随机编码调制，实现频谱扩展以后再传输；接收端则采用 相同的编码进行解调和相关处理，恢复原始数据。由于扩频通信具有抗干扰能力强，抗 截获，抗多径，保密性好和测距精度高等一系列优点，使得扩频技术在卫星定位通信、 东雨大学硕士学位论文 3 g 移动通信、航天通信和深空探测等诸多领域都得到了广泛的应用。 扩频通信所传递的消息的信号带宽远远大于原始信息本身的带宽，按照频谱扩展方 式的不同，扩频通信可以分为以下几种基本形式：直接序列扩频、跳频、跳时、线性调 频扩频、混合扩频等。 几乎各类扩频通信系统都有伪随机编码序列，具有良好的随机特性和相关特性的长 p n 码对扩频通信非常重要，在扩频通信系统中，抗干扰、抗截获、信息数据隐秘和保 密、多径保护和抗衰落、多址通信、实现同步捕获等都与扩频编码密切相关。长p n 码 有很多种，大多数都是以m 序列为基础而构成的。 d s c d m a ( d h c ts e q u e n c e c o d ed i v i s i o nm u l t i p l ea c c e s s ) 是直接接序列扩频码分 多址通信，多址方式是以正交的伪随机码即p n ( p e s u d o ) 码，作为不同的地址码区分 用户进行多址通信。对于码分多址的扩频通信方式，只有在接收端本地伪码与发端伪码 处于相同相位状态时，有用的信息才能被解出。因此扩频序列相位的捕获与跟踪是扩频 系统的关键，尤其伪码序列相位的捕获是一般常规通信所没有的( 跟踪技术与常规通信 中的方法类似) 。扩频通信早在二次世界大战时已开始研究，其后在军事通信方面以其 保密性好和抗强干扰等优点得到广泛应用。而目前的c d m a 技术的应用以c d m a 蜂窝 移动电话的推出为主，例如美国高通公司的c d m a 蜂窝移动电话，主要就是扩频技术 的应用成果。c d m a 蜂窝移动电话在容量、通话质量、保密性、功耗等方面比以前的蜂 窝系统有了很大的进步。此外扩频通信在卫星通信、无线本地环路、无线局域网、集群 通信等无线通信领域都有着广泛应用前景。 1 2 极低谱密度无线通信的研究动态 极低谱密度信号【7 ，8 】是指信噪比极低的信号，实现极低谱密度无线通信，有诸如深 空通信、全球导航卫星系统( g n s s ) 、军事通信和无线传感器网络等，采用的通信技术 有超宽带1m ，b ( u l t r aw i d e b a n d ) 和扩频通信等。 超宽带u w b 是一种无载波通信技术，即它不采用载波，利用纳秒至微秒级的非正 弦波窄脉冲传输数据，占用的频偏范围 良宽。扩频通信是传输信息使用的射频带宽是信 息带宽的1 0 倍至1 0 0 倍以上的通信体制。信息本身不再是决定传输带宽的决定因素， 传输带宽主要由发信机和对应的收信机预先制定的扩频码( 又称地址码) 序列确定。 u w b 在短距离的家庭无线网络方面具有很好的发展前景。目前u w b 无线通信系 统的主要实现方式可以分为基带脉冲方式和载波调制方式。基带脉冲方式是u 、b 通信 的传统方式。载波调制方式可以分为基于正交频分复用( o f d m ) 技术的多频带正交频 分复用( m u l t i b a n do n h o g o n a lf r e q u e n c yd i v i s i o nm u l t i p l e 妇n g ，m b o f d m ) 和基于 c d m a 技术的直接序列码分多址( d i r e c ts e q u e n c ec o d ed i v i s i o nm u l t i p l ea c c e s s ， d s c d m a ) 两大方案。c d m a 技术广泛应用于2 g 和3 g 移动通信系统，在u w b 系统 中使用的c d m a 技术与在传统通信系统中使用的c d m a 技术没有本质的区别，只是使 用了很高的码片速率，以获得符合u w b 技术标准的超宽带宽。o f d m 则是应用于e 3 g 、 b 3 g 的核心技术，具有频谱效率高、抗多径干扰和抗窄带干扰能力强等优点。 采用扩频技术对极低谱密度信号进行无线通信，特别是直接序列扩频对长伪随机码 的快速相关检测是极低谱密度无线通信系统的一项关键技术，目前比较广为人知的相关 特性良好的伪随机码【9 ，i o 】有最大移位寄存器序列( 简称m 序列) 、戈尔德( g o l d ) 序列、 锄i 序列等等。常规实现长伪随机码快速捕获的方法，1 2 ，1 3 ，1 4 1 有时域并行相关法和 f f t ( f a s tf o 嘶e r t r a l l s f o 衄) 频域相关法，前者的运算量极大，复杂度和成本极高；后 者虽然具有方便快捷、易于实现伪随机码相位和载波频偏的并行搜索等优点，但由于其 运算中存在很小数值的复权值，导致复数乘法的比特位数多，运算复杂度仍旧很高，而 且f f t 相关算法必须使用i f f t ，用正f t 将伪随机码捕获最终回到时域以确定伪随机码 相位，这也增加了运算量。扩频通信系统通常采用码分多址以提高频带的利用率，即各 用户使用彼此正交或接近正交的扩频编码，实现在同一扩频带宽内同时互不干扰的发送 和接收信号。扩频码分多址通信主要有两种工作方式：随机多址扩频通信方式和同步多 址扩频方式，两者的区别在于用户之间的发射信号是否同步。其中，前者因为用户之间 发射状态是完全随机的，没有同步的开销，。是常用的易于实现的扩频通信方式。 尽管超宽带和扩频技术同样具有扩展带宽的这一特点，但是获得大带宽的方法是这 两项技术之间的主要差别，这两种技术也可以结合起来使用，例如直接序列超宽带，就 是一种使用窄超宽带脉冲以及时域信号处理与直接序列扩频技术相结合以发射和接收 信息的单带方法。 1 ：3 本课题的研究意义 0 基于上述的研究动态，本课题将针对使用扩频技术实现极低谱密度条件下的无线通 信对基于f f t 的大频偏极低谱密度条件下的快速捕获技术进行深入研究。 首先在现有的f f t 快速相关检测方法的研究基础上，针对f f t 移位重复法的性能 中存在的偏差给出改进的方法；再结合伪随机码的特点，通过f h t ( f a s th a d 撇r d t r a i l s f o r m ) 这种只包含加法运算的快速相关检测方法，用f h t 代替f f t ，完成对基于 m 序列构造的伪随机序列的快速相关检测，由于f h t 快速相关检测方法中使用的f h t 与f f t 相比，具有只包含加减运算，没有乘法运算的优势，所以相对于f f t 频域相关 检测法，f h t 相关检测算法能极大的减少运算量。 伪随机码的相关检测是扩频技术中很重要的一步，快速的相关检测能缩短通信连接 的时间，这也是现代通信的发展要求。 1 4 论文内容和章节安排 本论文的内容主要是研究基于f f t 的相关检测算法，并针对f f t 移位重复法的性 能中存在的偏差给出改进的方法；以及用f h t 代替f f t 对各种伪随机序列进行快速相 关检测的算法，并且对这一系列的检测算法进行复杂度性能分析。从第二章开始，本论 3 垄堕奎兰堡主兰垡笙茎 一 - _ - - _ _ - - _ _ _ _ _ _ _ _ _ _ - - _ _ _ i l _ _ _ - - l _ _ - _ _ _ _ _ - _ - - _ _ - _ - - _ _ _ - - - _ _ _ - - - _ - _ _ l _ _ i _ _ _ - - - _ _ _ _ _ - _ _ _ 一一 文的章节安排如下： 第二章，主要介绍伪随机码，f f t 、f h t 等相关检测算法原理，最后详述了f h t 相关检测算法的基本原理，本章介绍的f h t 相关检测算法是后面几章p n 序列的f h t 相关检测的基础。 第三章，主要给出了基于f f t 的相关检测算法及其优势，在大频偏极低谱密度条件 下，对伪随机码的基于f f t 的快速相关检测方法的改进。 第四章，阐述g o l d 序列的f h t 相关检测，并对其算法复杂度和性能进行分析，最 后分析其算法复杂度，并和f f t 相关检测方法进行了比较。 第五章，根据k a s a m i 小集合序列构造的特点，介绍k a s a m i 小集合序列的f h t 相 关检测，并对其性能进行分析，最后分析其计算复杂度，并和f f t 相关检测方法进行了 比较。 第六章，根据k a s 锄i 大集合序列构造的特点，介绍k 且s 锄i 大集合序列的f h t 相 关检测，并对其性能进行分析，最后分析其计算复杂度，并和f f t 相关检测方法进行了 比较。 第七章，全文总结，针对尚未解决的问题，提出进一步的研究方向。 4 伪随机码及其相关检测算法介绍 第二章伪随机码及其相关检测算法介绍 随着通信理论的发展，早在2 0 世纪4 0 年代末，香农( s h a 衄0 n ) 就曾指出，在某 些情况下，为了实现最有效的通信，应采用具有白噪声的统计特性的信号，然而利用随 机噪声的最大困难是它难以重复产生和处理，直到6 0 年代，伪随机噪声的出现才使这 一困难得到解决。 本章首先对伪随机码的产生原理和特点做介绍，然后分析了f f t 相关检测算法及其 应用，最后给出f h t 相关检测算法的基本原理。 2 1 伪随机码 伪随机码( p s e u d or a n d o mc o d e ) 又称为伪噪声码( p s e u d 0n o i s ec o d e ) ，简称p n 码。香农编码定理指出：只要信息速率足小于或等于信道容量c ，则可以找到某种编 码方法，是在码字相当长的条件下，能够几乎无差错地从遭受高斯白噪声干扰的信号中 恢复出原发送信号，香农在证明编码定理的时候，提出了用具有白噪声的统计特性的信 号来编码。这里的白噪声是一种随机过程，瞬时值服从正态分布，功率谱在很宽的频带 范围内都是均匀的，但是至今无法实现对白噪声的放大、调制、检测、同步及控制，只 能用具有类似于带限白噪声统计特性的伪随机码来逼近它，作为扩频系统的扩频码，因 此简单的说，伪随机码是一种具有类似白噪声性质的码。 作为扩频码的伪随机信号，应具有下列特点： ( 1 ) 伪随机信号必须具有尖锐的自相关函数，而且互相关函数值应接近0 值； ( 2 ) 有足够长的码周期，以确保抗侦破与抗干扰的要求； ( 3 ) 码的数量足够多，用来作为独立的地址，以实现码分多址的要求； ( 4 ) 工程上易于产生、加工、复制与控制； 常见的p n 序列有最大长度移位寄存器序列( m 序列) 、戈尔德( g o l d ) 序列、k a s a i n i 序列等等。 2 1 1 伪随机码的自相关性 采用二进制的伪随机码，周期为p 的码序列z 的自相关函数愿( 7 ) 为 p 愿( 丁) = 墨， 2 1 扛：1 式中，墨是周期长度为p 的某一码序列，是墨移位7 - 后的码序列。 将相关函数归一化，用相关系数来表相关性，对式( 2 1 ) 进行归一化，则自相关 系数以( 丁) 为： 气 东南大学硕士学位论文 以下) = ；喜砜， 从式( 2 - 2 ) 可以看出，自相关系数值最大不超过l 。 2 1 1 伪随机码的互相关性 两个不同码序列之间的相关性，可以用互相关函数( 对于二进制代码序列，周期均为p 的两个码序列z 和 数，记做嗣为劝，即 p 顾墨们= 嚷弘 扛1 其互相关系数记做p ( 为奶，为 如奶= 喜墨酞 2 4 在扩频通信中，希望采用互相关小的码序列，理想情况是希望p 毛f ( 丁) = o ，即两个 码序列完全正交。 j ? ot 。? ：。 2 2f f t 相关检测算法 2 2 1 时域相关 两个p n 信号之间的相关，最简单的方法是时域相关法【1 5 】，例如佗点的p n 码，逐 点相乘，得到的所有竹点乘积相加得到一次相关结果，再循环移位1 次，做同样的操作， 得到一次相关结果，依次类推，得到竹个相关结果后，就可以判定，相关的两个p n 序 列是否相同，如果相同，n 个相关结果有一个峰值，根据这个峰值的位置，可以确定两 个p n 码之间的位移大小，但是这样做需要的n 钆次乘法。 2 2 2 循环相关 但是通过相关与卷积之间的关系，可以将时域相关变换到频域，再返回到时域，同 样得到点相关值，这就是循环相关。 假如输入信号为缸呐，通过线性是不变系统，系统的脉冲响应为m 呐，通过卷积可 以得到输出甄呐： ，： - 1 ，。 甄脚= 缸m ) 以n m ) = d 呐木以脚= f 1 【丑( 动双助】 2 - 5 # 0 其中，砸动和日( 动分别是d 呐和联哟的频域响应。 观察到缸呐和以呐之间的相关运算表示为： 6 竺墅! 里墨苎塑叁丝型簦鲨坌望 一l 须哟= m ) 以n + 硼 2 - 6 f r # 0 上式与卷积的唯一不同点就在于以n + 州中的m 前面的符号不同。对反询进行f f t 变 换为： 以助= 日( 动r 1 ( 功 2 7 这里r 1 ( 妫表示离散傅立叶反变换。 上述关系式可以用于得到输入信号和本地信号的相关值。 2 2 3f f t 相关检测 根据上面讨论的循环相关的运算法则，利用这些运算法则就可以执行f f t 频域相关 检测【1 6 ，1 7 】了。然而在实际检测中，需要经过以下几个步骤： ( 1 ) 对输入信号呐进行快速傅立时变换f f t ，将输入转换到频域，值为双功。 ( 2 ) 取双妫的复共轭，值为r ( 助。 ( 3 ) 对本地码k 哟进行f f t ，变换到频域中，值为乞( 动。 ( 4 ) 将r ( 勋与乞( 动逐点相乘，结果为吃( 助。 ( 5 ) 对瓦( 妨进行逆傅立叶变化，变换到时域中的值为吃( 哟，得到其绝对值k ( 呐i 。 ( 6 ) i 吃( 哟i 最大值中的第n 位给出了伪随机码的起始点。 2 3f h t 相关检测算法 磬 。扣 竺2 3 1h a d 撇r d 矩阵 h a d a i m r d 矩阵【1 8 ，1 9 1 是法国数学家m j h a d a m a r d 于1 8 9 3 年首先构造出来的，简记 为h 矩阵。它是一种方阵，仅由元素+ l 和1 构成，而且其各行( 和列) 都是互相正交 的，所以也是正交方阵，若把其中每一行看作是一个码组，则这些码组也是互相正交的， 而整个h a d a m a r d 矩阵就是一种长为刀的正交编码，它包含，1 个码组。 设h 为的矩阵，在= 2 p ( p 为正整数) 的情况下，h 可以由以下的递 推公式求得： 叫乏斟一驯2 2 删 | 1】1 h 22 1 1 1 l 2 - 8 ( b ) 例如，h 。和h 。可以通过如下递推来求得： 东南大学硕 叫耄二：1 _ n s 一【芸：三。1 _ + 1 + 1 + 1 + 1 + 1 1 + 1 1 哈达码矩阵h 。，的符号沿着行( 或列) 变化的次数也称为行( 或列) 序率。随着h 的行号或列号的增加，序率增加，这一特性称为顺序的( o r d e r e d ) 。 对于式( 2 8 ) 的情况，随着行或列的不同，序率是没有规律的，这样的哈达码矩阵称 为是非顺序的( n o n - o r d e r e d ) 。 当哈达码矩阵变为顺序的哈达码矩阵时，哈达码矩阵与沃尔什( w a l s h ) 矩阵完全 一致，即将h 矩阵中行的次序按+ l ”和“：l ”交换次数的多少重新排列，可以得到沃尔什 ( w a l s h ) 矩阵，简记为w 矩阵，例如，h 4 = w j ，h 8 = w j 。 h 。= w 8 从上面可以看出，h 矩阵和w a i s h 矩阵之间的关系式可以相互转换的。 2 3 2 哈达码变换 设h 的( 凫+ 1 ，n + 1 ) 元素为，删岛呐，则变换核采用哈达码函数，洌砖呐时的变换 为 一一1 砸动= 缸哟，删岛呐，免= o ，1 ，一1 2 - 9 ，l = 0 称之为哈达码变换1 9 1 ( h a d 锄a r dt r a n s f o n l l ) ，与此相对应，哈达码反变换( h l v e r s e h a d a n l a r dt r a n s f o r m ) 由下式给出： r + 一 一 + 一 + + 一 1 1 1 1 1 1 1 1 t t 一 一 一 一 + + 1 1 1 1 1 1 1 上1 + 一 + 一 一 + 一 + l 1 1 1 1 1 1 1 + + + + 一 一 一 一 1 1 1 1 1 1 1 1 + 一 一 + + 一 一 + l 1 工 1 1 上1 工 1 1 工1 上 + + 一 一 十+ 一 一 l l 1 1 1 1 1 _ 1 1 上 + l + 一 十 一 + 一 l 1 1 1 1 1 1 _ 1 _ + + + + + + + + + 一 + 一 + 一 + 一 l l 1 上 1 1 工1 工1 工1 工 + 一 + 一 一 + 一 十 1 1 1 1上11 1 l t 一 一 + 一 + + 一 l l l 1 1 1i1_1 + 一 一 + + 一 一 + 1 1 工1 _ 1 上1 上1 工 1 1 上 + + 一 一 + + 一 一 l 1 _ 1 1 1_1上1 1 t + 一 一 一 一 + + l 1 工1 工1 1 工l 1 工1 + + + + 一 一 一 一 l 1 1 1 工1 工1 工1 工 1+ + + + + + + + 2 3 3f h t 相关检测 定义m 矩阵去掉第一行和第一列后的子矩阵的每行每列都是一个m 序列反呐，该 子矩阵相邻两行或两列满足循环移每一位的关系【2 们，例如反呐：f + 1 ，+ 1 ，一1 ， 十1 ，一1 一1 ，一1 】： 矩阵m = 2 1 l 。矗 因此计算某个序列叹呐和m 序列反呐的相关c ( 丁) = 霎r ( 咖( 鬲) 可以f h t 变 帑 换来实现【2 l 】： c c ( o c ( 1 c ( 2 c ( 3 c ( 口一2 ) + 1 + 1 + 1 名( i - ) 0 7 ( o 7 ( 1 r f 2 7 ( 3 ； ； 7 ( g 一2 ) 2 1 2 由于m 矩阵和w a l s h - h a d 锄a r d 矩阵之间能够互相等效，根据文献 2 2 ，2 3 】，上式f m 变换可以等效成f h t 变换，且计算复杂度仅为q 1 。g ：( 口) 。在本例中，口：8 。 2 4 本章小结 本章主要介绍了伪随机码的特点和性质，然后分析了f f t 相关检测算法和基于f f t 相关检测算法的应用，最后给出了f h t 相关检测算法的基本原理。 f f t 相关检测算法是由相关与卷积之间的关系，将两个相关的信号从时域变换到频 域，用f f t 计算，再返回到时域得到相关值的算法。本章讨论的f f t 相关检测算法， 9 + 一 + + 一 + 一 1 1-1_1 1-1-1 l + 一 一 + + 一 + 一 1 工1 1 工1 1 1 1 1 1 + 一 一 一 + + 一 + 1一1上1工1上 1 l l l + + 一 一 一 + + 一 1 1 1 工l l l l l + 一 + 一 一 一 + + 1 11 1 1 l l l + + 一 + 一 一 一 + l 1 1 1 1 l l l + + + 一 + 一 一 一 1 - 1 j 1 11_1 1 l+ + + + + + + + 奎塑奎堂堡主竺垡笙茎 相比传统的时域相关算法，一次运算就能得到所有相位的相关值，具有方便快捷、运算 量小等优点。 根据h a d a m a r d 矩阵和哈达码变换的性质和原理，利用m 序列构成的m 矩阵与 w a l s h - h a d a m a r d 矩阵之间的关系，计算得到某个序列和m 序列之间的互相关值；且f h t 中不包含乘法运算，只有加法运算，因此f h t 相关检测算法相比f f