快速哈达玛变换设计与实现（毕业设计42页、16032字）
摘要：快速哈达玛变换（FHT）是数字信号处理中的基本变换之一，在移动通信、多媒体编解码中得到了广泛的应用。哈达玛变换同傅立叶变换一样，随着计算长度的增加，实现复杂度急剧增长，因此研究其快速实现结构，以及低复杂度实现电路具有重要意义。本文在研究哈达玛变换及其快速算法的基础上，分析了哈达玛变换的全并行结构，并根据其结构特性提出了哈达玛变换(FHT)的快速算法，快速算法的设计主要是从折叠结构出发，本文介绍了级间折叠和两点折叠这两种折叠结构，在FPGA中实现了16点快速哈达玛变换。结果表明在点数较多时用全并行结构实现哈达玛变换时的运算量很大，在用快速算法后运算量大大降低，在使用级间折叠时可节约资源数目 ，在使用两点折叠时可节约资源数目 ，从而达到大大节约资源的目的。
关键词：折叠结构；快速哈达玛变换；VHDL
Design and Implementation of Fast Hadamard Transform
Abstract：Fast Hadamard transform (FHT) is a basic transformation in digital signal processing, which is widely used in mobile communications and Multimedia coding. Hadamard transform will become very complex with the increase of calculating length as Fourier transform. So, the study on its rapid achieving structure and low complex circuit has important significance. The dissertation analyzes the entire parallel structure of Hadamard transform on the basis of the study on Hadamard transform and its fast algorithm, then gives the fast algorithm of Hadamard transform according to its structure. The dissertation introduces stages folding and two point folding structure, and 16 points fast Hadamard transform achieve in FPGA. The experimental results show that the resource is saved greatly by using two point folding structure when there are large points.
Key words: Folding structure, Fast Hadamard Transform, Very High Speed Integrated Circuit Hardware Description
目 录
第1章 前 言 1
1.1 研究背景 1
1.2 国内外研究现状 1
1.3 选题目的及意义 2
1.4 主要研究内容 2
第2章 快速哈达玛变换基本理论 3
2.1 沃尔什--哈达玛变换 3
2.1.1 哈达玛变换 3
2.1.2 沃尔什--哈达玛变换 4
2.2 快速哈达玛变换 8
2.2.1 速哈达玛变换算法的基本特点 8
2.2.2 快速哈达玛变换算法分析 8
第3章 设计与实现 10
3.1 EDA设计平台 10
3.2 哈达玛变换中辅助同步码算法分析 12
3.2.1 辅助同步码产生方法 12
3.2.2 算法分析 12
3.3 哈达玛变换的全并行结构 13
3.4 快速哈达玛变换的几种折叠结构设计 15
3.4.1级间复用N点蝶形运算单元的折叠结构设计 16
3.4.2 整个哈达玛变换单元分时复用2点蝶形运算单元 17
3.4.3在不同的信道（或支路）折叠使用快速哈达玛变换单元 18
3.5 快速哈达玛算法在FPGA中实现 19
第4章 调试结果与分析 22
4.1 调试结果 22
4.2 性能分析 26
结论 28
致谢 29
参考文献 30
附录1 16点快速哈达玛的VHDL源代码 31
附录2 四路选择器的程序代码 34
附录3 全加器的程序代码 35
附录4 锁存器的程序代码 35
附录5 计数器的程序代码 36
第1章 前 言
1.1 研究背景
在步入3G时代的今天，通信技术是一门超快速发展的科学。而在目前的通信系统中都少不了编码技术，快速哈达玛变换在这方面有着重要的作用，它的主要优点就是运算速度快。另外，快速哈达玛变换的运算中都是很简单的加减法运算，使得它被广泛应用在各个领域。
在数字水印技术中，先产生一个基于m序列和快速沃尔什-哈达玛变换的矩阵，在嵌入与检测时使用一个私钥来产生伪随机序列，以此生成原始水印。这使得攻击者在没有密钥的情况下无法取得水印的信息，增强了保密性[1]。
在3GPP中,FHT是3GPP协议采用的算法之一。为了提高码距,TFCI采用了基于RM码的超码编码方式,这使得接收端的译码难度加大。利用快速哈达玛变换,结合超码译码算法,可以给出TFCI译码算法,包括对双极性序列的变换和去除掩码的处理过程。大量的仿真数据表明，该方法极具应用价值[2]。
W-CDMA系统中,各基站之间是异步时序关系。为了快速识别基站,3GPP协议引入了三步同步的小区搜索算法，采用传统的匹配滤波器组结构运算复杂度比较大。根据其构造特性，提出的部分快速哈达玛变换算法，减少了接近70%的运算量 [3]。
1.2 国内外研究现状
近年来，国内外对于快速哈达玛的研究一直都是一个很热门的课题，从下一代网络（NGN）及3G演进与下一代宽带无线（NGBW）发展观点看，H.264/AVC这一面向IP及无线/移动应用的视频压缩编码新标准[4]。由于其高的自适应压缩效率及优良的自适应分层结构特征，使其可适应不同的网络传输环境，定会在未来包括HDTV质量要求的视频、多媒体/超媒体业务领域，即如视频广播、视频通信、视频流媒体、Internet视频传送、异构网上的多点通信、压缩视频存储、视频数据库、高质量视频文档等各方面获得广泛的应用[5]。
在越来越多的协议跟编码中，快速哈达玛变换得到了广泛的应用，而且在频谱资源受限的无线、卫星及移动通信领域更有其大展鸿图的机会与潜力。尽管目前手机视频大都仅利用H.263/H.263+ 之类协议，而卫星应用的DVB-S2标准已开始引入H.264/AVC及LDPC等源编码及信道编码新技术，以适应竞争环境中新的市场需求。同时，有效处理好我国音视频标准AVS与H.264/AVC的关系，对发展我国宽带视频、多媒体/超媒体产业与市场应用有极重要的现实意义与战略价值。
1.3 选题目的及意义
在通信编码技术中越来越多的使用到了哈达玛变换。由于它的折叠结构在一定程度上可以节约芯片资源，这对硬件实现起着相当重要的作用。该选题需要完成的主要是快速哈达玛变换的设计及其VHDL硬件描述，最终目的是把它应用到3GPP、H.263、CDMA这些领域中去。而该设计的主要目的就是为了设计出一种简单而且快速的算法实现快速哈达玛变换。设计的优劣直接关系到运算的效率和资源的利用。因此，该课题具有很高的实用价值。
1.4 主要研究内容
首先，本文研究了快速哈达玛变换的基本原理，哈达玛变换的基本公式，以及它可以实现快速算法的原因；其次，快速哈达玛变换在FPGA中的实现也是该研究的一个重点。
论文的章节安排如下：
第二章介绍了快速哈达玛算法；
第三章介绍了VHDL软件的开发环境和具体的应用，主要是编程的应用；
第四章介绍了结合以上二者，用VHDL语言来进行快速哈达玛算法的设计及实现；
第五章介绍了实验调试的结果以及其分析；
| 