基于SOPC的指纹数据压缩模块毕业设计.doc

《基于SOPC的指纹数据压缩模块毕业设计.doc》由会员分享，可在线阅读，更多相关《基于SOPC的指纹数据压缩模块毕业设计.doc（37页珍藏版）》请在三一办公上搜索。

1、 毕业设计（论文）题目： 基于SOPC的数据压缩模块姓名 学号所在单位指导教师 完成日期基于SOPC的指纹数据压缩模块摘 要图像压缩直接影响着指纹识别系统的准确率，因此研究优良的指纹压缩算法是指纹识别技术领域的一个重要课题。基于此本文对此课题展开了研究并提出了小波变换+霍夫曼编码组合使用的图像压缩算法。在实际应用中，如果采用软件进行霍夫曼编码，编码速度将处理器时钟频率的制约，并且功耗太高，因而无法应用在高速的或者要求低功耗的环境中，因此文章设计一种能够使用硬件实现的霍夫曼算法。而小波变换则采用经典的Mallet算法进行了设计。关键词：小波变换，指纹识别，霍夫曼编码AbstractImage c

2、ompression directly affect the accuracy of fingerprint identification system, so the study of excellent fingerprint compression algorithm is fingerprint identification technology, an important subject. Based on this in this paper, this topic research and put forward on the wavelet transform + Huffma

3、n coding the image compression algorithm combined. In practical application, if the software Huffman coding, encoding speed will processor clock frequency of the restriction, and power consumption is too high, and thus could not be used in high speed or requirements of low power consumption environm

4、ent, so the design of a kind to be able to use hardware implementation algorithm of hoffman. And wavelet transform, the use of the classic Mallet algorithm design. Keywords: wavelet transform, the fingerprint identification, Huffman coding 目录第一章绪论：51.1 背景51.2 指纹识别系统的构成61.3 国际较为流行的图像压缩算法61.3.1算法介绍61.

5、3.2 JPEG图像压缩标准71.3.3 WSQ指纹压缩算法标准7第二章 算法总体结构72.1 图像处理中的频域分析法72.11傅立叶变换82.1.2 小波变换82.1.3 小波变换的优势82.2 图像压缩算法设计的基本思想82.2.1 算法的流程图82.2.2 小波变换模块简介102.2.3压缩编码模块简介10第三章 小波变换模块123.1 小波变换Mallet算法123.2 Mallat算法系统设计123.3 二抽值模块的设计133.4滤波模块的设计 （DA算法）153.4.1FIR数字滤波器的系数计算153.4.2滤波器的VHDL实现：173.4.3 移位寄存器的实现183.4.4 查找

6、表的实现193.4.5 寄存器的实现203.5 总结22第四章 基于小波变换的压缩编码234.1霍夫曼编码234.1.1 霍夫曼编码的理论基础234.1.2 霍夫曼编码基本流程234.1.3 树的构造基本思想244.1.4 树的构造实现24第五章 设计验证265.1 小波变换设计验证265.1.1 DA算法结构正确性验证265.1.2 移位寄存器功能验证275.1.3 latch1和latch2功能验证275.1.4 DA滤波器的性能分析285.2 霍夫曼树的验证29第六章 总结与展望31参 考 文 献32致 谢33第一章 绪论1.1 背景随着计算机技术，电路集成技术，图像处理技术和模式识别技

7、术的飞速发展，安全方便的自动指纹识别系统已开始应用于桌面电脑，笔记本电脑，提款机，蜂窝电话，考勤系统，门禁控制以及电子商务安全系统。遍及军队、银行、保险、边防检查、公安、医疗卫生及网络接入等各个领域。一幅指纹图像经过指纹采集器的采集和处理，得到的数据比特往往很大，而数据比特的多少会直接影响着指纹识别系统识别的速度和所需的储存空间。所以指纹图像数据的压缩也变得越来越重要，要完整的体现出指纹图像的基本特征，又要尽可能多的压缩冗余的数据。因此，研究指纹图像的压缩技术，保证高压缩比和优良的恢复效果是指纹识别技术研究领域的一个重要课题。1.2 指纹识别系统的构成一个指纹识别系统一般由两部分构成：指纹图像

8、采集部分和指纹识别部分。指纹图像采集部分通过特殊的光电转换设备（既指纹采集器）将指纹图像采集到计算机中以便进行图像处理。采集模块采集指纹图像数据，经过图像判定，细化，二值化等步骤进行图像数据处理，再将指纹信息和相关的身份信息存入数据库；鉴别模块通过指纹采集器采集待识别的指纹数据，经过图像判定，如果通过再进行图像处理，提取信息，然后在数据库中进行检索，找到最佳匹配鉴定模式或者根据用户所宣称的身份，从数据库中调出相应的指纹信息，决定它们是否匹配。 图1 典型的指纹识别系统框图1.3 国际较为流行的图像压缩算法1.3.1算法介绍小波变换+压缩编码是国际上较为流行的指纹压缩算法形式。因为小波变换比DC

9、T这样的傅立叶变换的性能更优越，是一种自适应的时频分析方法，具有多分辨分析功能，也被誉为数学显微镜。图像数字化后的数据量是巨大的，如何快速有效地存储或传输这些数据，成为当前信息社会的一个研究热点。例如，一幅1024*768的24位BMP图像，其数据量约为2.25MB。如此庞大的数据量，无疑给存储容量、通信线路的传输带宽以及计算机的处理能力提出了更高的要求。单纯依赖于提高计算机硬件和通信设施的性能是跟不上应用需求的。由于图像信息中存在着大量的冗余信息，数据间存在着关联性，所以基于保密和方便信息传输与存储的目的，往往还要对采集到的指纹图像数据进行压缩编码，以提高存储、传输和处理速度，节省存储空间。

10、1.3.2 JPEG图像压缩标准就图像压缩方面，最新的静态图像压缩标准JPEG2000采用离散小波变换（DWT）作为其变换编码，支持图像的多分辨率表示。正是小波变换编码的使用，使JPEG2000标准具有超低比特率性能、分辨率渐进传输等众多优点，受到数码厂商的青睐。根据有关JPEG2000计算复杂度的分析报告显示，JPEG2000的高强度+计算任务包括嵌入式优化截断块编码(EBCOT)的Tier-1以及离散小波变换模块，它们几乎贡献了全部计算复杂度的80%，构成了JPEG2000高速实时运行的严重瓶颈1.3.3 WSQ指纹压缩算法标准由美国FBI发布的基于小波变换的WSQ指纹压缩算法标准，也采用

11、了小波变换+标量量化和压缩编码等技术。在压缩指纹时也都取得了很好的编码效果。因此基于小波变换的指纹图像压缩算法目前成为研究的热点问题，同时也必将在以后图像压缩领域占据主导地位，前景广阔。 基于此本文提出的指纹图像压缩算法也基于小波变换+压缩编码的形式。小波变换方面本文将着重讨论当今最为流行的设计算法Mallet算法，并给出设计方法。在压缩编码方面，本文将讨论霍夫曼编码。第二章 算法总体结构2.1 图像处理中的频域分析法 数字图像处理的方法有两大类：一种是空间域处理，另一种是频域分析法，把图像信号从空间域变换到频域便可以从另一个角度来分析 图像信号的特性。图像的频域处理最突出的特点是其处理速度高

12、，并可采用已有的二维数字滤波进行所需要的各种图像处理，图像处理中经常用到的傅立叶变换，小波变换都属于图像的频域处理方法，得到了广泛的应用。 2.11傅立叶变换 信号处理中，重要的方法之一是傅立叶变换，它架起了时间域和频率域之间桥梁。傅立叶变换一直统治着线性时不变信号处理，最主要的原因是傅立叶变换手所用的复正弦波ejwt是所有线性时不变算子的特征向量。 从物理意义上讲，傅立叶变换的实质是把f(t)波形分解成许多不同频率的正弦波的叠加和，这样我们就可以从时域转换到频域实现对信号的分析。但是虽然傅立叶变换能够将信号的时域性和频域性联系起来，但我们只能从信号的时域和频域分别观察，不能将二者结合起来。这

13、是因为信号时域波形中不包含任何信息，而其傅立叶谱是信号的统计特性，它是信号整个时域内的积分，没有局部化分析信号的功能，所以不具备时域信息。这样信号分析中的一对矛盾产生了：时域和频域的局部化矛盾。 在实际生活中，瞬变信号范围比平衡信号大得多，也更加复杂，信号在某一时刻附近的频域特征都很重要，这就激励着我们去寻找一种新的分析方法，即能将时域和频域结合起来描述观察信号的联合性。2.1.2 小波变换 小波变换的数学基础是傅立叶变换，小波分析方法是一种窗口大小固定但其形状可改变，时间窗和频率窗都可改变的时频局域化分析方法，即在低频部分具有较高的频率分辨率和较低的时间分辨率，在高频具有较高的时间分辨率和较

14、低的频率分辨率，所以被称为数学显微镜。正是这种特性，使小波变换具有对信号的自适应性。与传统的信号分析技术相比，小波分析能在没有明显损失的情况下，对信号进行压缩和去噪。2.1.3 小波变换的优势在频域中，傅立叶变换具有较好的局部化能力，特别是对于那些频率成分比较简单的确定性信号，傅立叶变换很容易把信号表示成各频率成分的叠加和的形式，但在时域中，傅立叶变换没有局部化能力，无法从信号f(t)的傅立叶变换F(w)中看出f(t)的任一时间点附近的性态。因此，小波变换在对瞬态信号分析中拥有更大优势。2.2 图像压缩算法设计的基本思想2.2.1 算法的流程图 、图2 算法总体流程图图3 指纹识别系统硬件总体

15、设计框图2.2.2 小波变换模块简介小波变换的工作主要是将指纹采集器采集到的原始信号分为低频和高频分量，依据图像的低频分量能够近似反映原始图像，而高频分量只仅仅起一个修饰作用的原理，只保留低频分量，从而起到压缩图像数据的作用。 图4 小波变换流程图2.2.3 压缩编码模块简介为了节省储存空间和传输时间，需要对小波变换后所得的系数进行编码，最后得到需要的图像压缩数据。压缩编码一般分为有损压缩和无损压缩两种，无损编码可以完全恢复原始图像而不引入失真，它利用数据的统计特性来进行数据压缩，解压缩后的还原图像与原始图像完全一致。有损编码不能完全恢复原始数据，而是利用人的视觉特性使解压缩后的图像和原来一样

16、。本文将介绍的霍夫曼编码是无损编码的一种，是一种基于统计特性的可变字长的编码方法。在可变字长编码中，对于出现概率大的符号编码成短字长的编码，对于概率小的符号，编以较长的字长编码。如果码字长严格按照所对应符号的出现概率的大小逆序列排列，则平均码长一定小于其他任何符号顺序方式，即这是一种最接近于熵值的“最佳编码”。而霍夫曼编码正因为其是可变长编码，所以在硬件实现起来会有一定的难度。第三章 小波变换模块3.1 小波变换Mallet算法执行离散小波变换的有效方法一种是使用滤波器，该方法是Mallet于1988提出的，称为Mallet算法。这种算法实际上是一种信号分解的方法，在数字信号处理中常称为双通道

17、子带编码。用滤波器执行离散小波变换的概念如图2所示通过两个互补的滤波器组，其中一个滤波器为低通滤波器，通过该滤波器可得到信号的近似值，另一个为高通滤波器，通过该滤波器可得到信号的细节值。 图5 MALLET 算法流程图小波变换Mallet算法的工作过程可分为两个部分：(1) 指纹采集器采集的数据分别通过低通和高通滤波器。(2) 通过低通滤波器和产高通滤波器的数据再次通过二抽值模块，得到近似小波系数和细节小波系数，作为下一步工作的数据。3.2 Mallat算法系统设计基于前述Mallet算法，小波变换的系统架构，如下图所示： 图6 Mallet算法系统框图下面将介绍主要模块设计与实现 。3.3

18、二抽值模块的设计 二抽取的FPGA实现结构如图5所示：二抽取通过调用Altera的IP核FIFO实现。调用IP核，使得该模块具有很高的效率，并且该部分结构和功能均已得到了很好的优化。 图7 二抽值结构图计数模块（cnt3)设计思想：由rdreq作为计数器的时钟，时钟翻转一个高电平，计数器计数加一。当时钟连续再次出现高电平时（即连续读入两个小波系数），根据二抽值模块的算法要求，计数器输出一个高电平（作为选择模块的控制信号）同时计数清零。所以基于此，计数模块整体需要一个计数器和一个控制器，如图所示： 控制器的输出作为计数器的清零信号，计数器的设计如图： 数据选择器的设计:利用计数模块最后的输出信号

19、sign作为数据选择器的控制信号，当sign为高电平时，则输出FIFO输出端q端的数值。其实相当于一个D触发器。最后数据选择器输出的数据进入寄存器。3.4滤波模块的设计 （DA算法）滤波模块的设计可以采用分布式算法（DA算法），滤波器的设计我们可以参照FIR滤波器的设计，一个N阶的FIR滤波器的输出可由线性卷积求出： 对于传统的MAC，每次采样，yn都要经过N次乘法和N-1次加法操作，在硬件实现中，既占用资源，又影响速度。 由于FIR滤波器的系数具有对称性，分布式算法（DA算法）提出可将乘法去处转换为移位相加，从而节约硬件资源，下面看乘积和公式：假设FIR系数hn已知。有符号的xn可以用B位的

20、二进制补码表示为： 其中，最高位为符号位。将公式（3）代入公式（2），可得：=+ 由上式可知，分布式算法的实质就是：将输入变量的一个数据位和所有滤波器抽头系数h0-hn-1的每一位进行“与”运算并求和，而指数部分则说明了求和结果的位权，整数乘以2b就是左移b位，对此可以通过硬件连线实现，不占用逻辑资源。下面依据分布式算法，设计滤波器的步骤为：1 求出滤波器系数。2用VHDL语言设计逻辑电路。3.4.1FIR数字滤波器的系数计算本文通过MATLAB的Fdatool软件实现求得滤波器的系数。输入数据X(n)为16位，输出Y（n）为16位的低通滤波器,设计方法为FIR采用窗口法。滤波器阶数定为16，

21、窗口类型Kaiser,Bete为0.5，Fs为48KHZ,Fc为10.8KHZ，运行得到滤波系数如下： 对系数进行调整，同时将所有系数扩大倍进行运算。3.4.2滤波器的VHDL实现：滤波器的结构图如下： 图8 DA算法结构图设计思想：构造16行的移位寄存器，每个移位寄存器能储存b（本文b=16）个比特数据，四个4输入的查找表，加法器和寄存器。此图目的是实现4式，当一个时钟上跳沿到来之后，移位寄存器向右移一位，同时16个并行的移位寄存器分别进入查找表进行运算。经查找表运算的4个数据同时相加，通过累加器，在时钟下跳沿到来时存入寄存器并将寄存器里的数据乘以后进入累加器进行运算。直至16个时钟之后，所

22、有数据运算完毕，经过latch2输出的最后数据则为经过滤波的数据。这样可以通过建立查找表来实现上述运算，采用DA算法的FIR滤波器在具体实现时可以采用一个查找表LUT实现映射f(h(n), )。预先设定的查找表LUT接受输入向量：=，输出为f(h(n), )。各个映射值都由相应的二次幂加权并累加。利用相应的移位加法器就能够有效地实现累加。在K次(K为采样数据宽度。本文假设为16位)查询循环后就完成了对内积y的计算。所以查找表的设计对滤波器的实现十分重要。假设本文设计的滤波器为16阶，照“分解级联”的处理方式。查找表设计为四个4输入的LUTs。查找表的总深度为4x=64。若用一个查找表则深度为=

23、65536可见前者极大地减小了查找表规模。下面就介绍此图主要部分的设计思想。3.4.3 移位寄存器的实现本文一共需要16个并行的相同的移位寄存器，此处以其中一个为例，寄存器的端口设定如下： 其中k信号是移位寄存器的读入信号，ready信号是寄存器的输出使能信号。移位寄存器的主要功能：当时钟上跳沿到来后，寄存器整体向右移一位。基于此设计代码如下： 其RTL图如下： 图9 移位寄存器的RTL图3.4.4 查找表的实现以其中一个查找为例： 图10 查找表的RTL图设计的查找表输入4位，输出为采样值和滤波系数的乘积。ROM 中参数的设定如表2所示：对于系数h0h3可以做一张类似的查找表, ROM 中参

24、数的设定如表1示：查找表输入查找表输出查找表输入查找表输出000001000h(0)0001h(3)1001h(0)+h(3)0010h(2)1010h(0)+h(2)0011h(2)+h(3)1011h(0)+h(2)+h(3)0100h(1)1100h(0)+h(1)0101h(1)+h(3)1101h(0)+h(1)+h(3)0110h(1)+h(2)1110h(0)+h(1)+h(2)0111h(1)+h(2)+h(3)1111h(1)+h(2)+h(3)+h(4)表1 查找表中参数设定其代码如下： 3.4.5 寄存器的实现 本文一共设计了两个寄存器，latch1的作用是在低电平到来时

25、存储累加器输出的数据，并输出，将数据反馈回累加器参与运算。latch2的作用是输出最后滤波得到的数据（在图5中没有画latch2）。latch1具体工作过程;当时钟下跳沿到来时，寄存器储存从累加器输出的数据，并输出，经过mul（此模块的作用是将输入的数据减半输出）反回累加器进行运算。其RTL结构如下： 图11 latch 1 RTL图其关键代码如下：latch2具体过程：每来一个ready高电平计数一次，当计数值16次后（即16个时钟后）寄存器输出数据，即为滤波器工作后最终得到的数据。其RTL结构如下： 图12 latch2 RTL结构图 其实现代码如下：3.5 总结 本文对小波变换Malle

26、t算法展开深入研究，基本实现算法中的滤波器组和二抽值模块功能构建。本文在这里只给出了低通滤波器的设计，高通滤波器的设计只需将所求的滤波系数进行更换，结构不变。但本文并没有基于实际的开发板，指纹采集器等进行研究，所以无法检验模块整体连接后的功能是否正确，性能如何，这也是本文的一大不足。同时本文也只基于对图像进行一级小波变换分解，如果对压缩要求更高而对失真程度要求不严，可以继续进行二级和三级等等分解，步骤就是将上一级得到的低频分量继续通过滤波器组进行分解。第四章 基于小波变换的压缩编码4.1霍夫曼编码简介霍夫曼编码是迄今为止运用最为广泛的无损压缩编码。是一种经典而有效的编码方式，在对信源概率精确统

27、计的情况下，霍夫曼编码往往能取得最佳的压缩效果。在实际应用中，如果采用软件进行霍夫曼编码，编码速度将受处理器时钟频率的制约，并且功耗太高，因而无法应用在高速的或者要求低功耗的环境中，因此必须采用硬件编码器。而硬件实现霍夫曼编码因为码字长度不等存在比较大的难度，所以本文将对此展开研究。4.1.1 霍夫曼编码的理论基础 根据信息论中信源编码理论，当平均码长R大于等于图像熵H时，总可设计出一种无失真编码。当平均码长大于图像熵时，表明该编码方法效率很低；当平均码长等于或很接近于(但不大于)图像熵时，称此编码方法为最佳编码，此时不会引起图像失真。当平均码长大于图像熵时，压缩比较高，但会引起图像失真。有变

28、长编码中，如果码字长度严格按照对应符号出现的概率大小逆序排列，则其平均码字长度为最小，这就是变长最佳编码定理。变长最佳编码定理是霍夫曼编码的理论基础。设D为编码所使用的数制，则变长最佳编码的平均码字长度R的范围为4.1.2 霍夫曼编码基本流程 霍夫曼编码是以信源概率分布为基础的，通常采用对大量数据进行统计后得到的近似分布来代替，霍夫曼编码的一般流程如下：（1） 首先统计信源中各符号出现的概率，出现的概率从 大到小排序。（2） 把最小的两个概率相加合并成新的概率，与剩余的概率组成新的概率集合。（3） 对新的概率集合重新排序，再次把其中最小的两个概率相加，组成新的概率集合。如此重复进行，直到最后两

29、个概率的和为1。（4） 分配码字。码字分配从最后一步开始反向进行，对于每次相加的两个概率，给大的赋“0”，小的赋“1”（也可以相反，如果两个概率相等，则从中任选一个赋“0”,另一个赋“1”即可），读出时由该符号开始一直直到最后的概率和“1”，将路线上所遇到的“0”和“1”按最低位到最高位的顺序就是该符号的霍夫曼编码。 从霍夫曼编码的流程看出树的构建在霍夫曼编码中占有很重要的地位，因为在构建树的过程中可以获得整个树的节点全部信息以用于编码。流程中的2，3步都是在实现树的构建过程。所以，霍夫曼编码的最终实现可以分为两步：1树的构造。2分配编码。下面就将对此进行详细研究。4.1.3 树的构造基本思想

30、 本文从研究树的构造入手来实现算法，这一过程可通过节点序列描述在静态哈夫曼编码中，各输入符号按事先统计的出现次数(即权重)降序排列，所得序列记为，ss = ， ， ， ，其中表示排在第k位的符号，N 是符号的个数。树的构造过程中将产生N1个内部节点。定义序列ns=, 其中表示编号为k的内部节点霍夫曼树构造完成后，ns中的元素将按权升序排列初始时则假设各内部节点的权重为无穷大序列ss确定后，即可按下述方法构造霍夫曼树。设立指针i指向，t和m指向。选出i所指的元素 和前一个元素 ，以及t所指的元素及。用其中权重最小的两个节点构造子二叉树，并生成新的内部节点其编号等于已生成内部节点的总数加1，以保证

31、ns中的元素按权重升序排列最后，根据选择结果移动i,t,m直到m指向(即根节点)在上述过程中，子二叉树的构造具有一定的随机性为确保惟一性，作如下规定： 当和权重相等时。认为权重较小。 当 和权重相等时，认为 权重较小。 当符号和内部节点权重相等时，认为符号权重较小。上述规定使霍夫曼树可由ss惟一确定。构造树完成后，将树中节点按从上到下、从右到左的顺序排列，得到序列s=(，),设立指针n指向S序列即是第n个节点。显然，s中各节点的排序代表了它们被选出构造子二叉树的先后次序故s代表了霍夫曼树的构造过程。4.1.4 树的构造实现本文在实现树的构造过程中，因为硬件对浮点数的处理十分困难，所以本文将输入

32、的数值全部按比例放大100倍进行设计。假设输入处理8bit数据，设置3个整形的数组如下：type array_ss is array (8 downto 0) of integer range 0 to 101 ;type array_ns is array (6 downto 0) of integer range 0 to 101 ;type array_s is array (15 downto 0) of integer range 0 to 100;signal ss:array_ss;signal ns:array_ns;signal s :array_s ;为计算方便，ss数组中

33、多设置一位，令其等于101。同时ns中所有元素的初值为101。令i,t,m，n分别指向数组ss，ns，s。t,m和区别是，t指向的数据参与和ss（i）的运算，而m的指向作为ns的存储位。初始时，i0，t6，m6，n0， 在进行运算时，选出ss(i),ss(i+1),ns(t),ns(t+1)四个数据进行比较取较小的两个数相加，相加值存入ns（m），而相加的两个数，按大小顺序存入s（n）和s(n+1)中。因为ss按降序排列，ns按升序排列，所以每次相加的两个数只可能是ss(i)+ss(i+1),ss(i)+ns(t),ns(t)+ns(t-1)三种组合，指针的移动情况如下表：组合情况itmnss

34、(i)+ss(i+1)i=i+2不变m=m-1n=n+2ss(i)+ns(t)i=i+1t=t-1m=m-1n=n+2ns(t)+ns(t-1)不变t=t-2m=m-1n=n+2表2 指针移动的情况4.1.5分配编码的实现在构建霍夫曼树时同时构建一个霍夫曼表，主要作用是存放每个节点的基本信息，从而得到整个树的信息。例如，子节点，父节点等，整个霍夫曼树的所有节点的信息将以串行的形式储存在一个数组a中。以一个节点的信息为例（左节点小于右节点）：父节点值右子节点值左子节点值在整个霍夫曼树中的所有节点可以分为两类，即输入的叶节点和在树的构建中得到的内部节点。在分配编码时，不可避免的叶节点和内部节点可能

35、值会相等，从而造成分配编码出现错误，基于此再设计一个数组f作为指示a中所存节点为叶节点或者为内部节点。因为整个分配编码的过程存在着一个对a顺序遍历的过程，如果在叶节点中有值相同的两个节点，后一个节点的分配编码将会受到影响，所以设立一个数组d用于标识值有重复的叶节点：如有重复值，标识后一个重复值的叶节点为1。设立一个指针z指向a，o指向f，e指向d。设立指针y遍历树，要求得输入所有叶节点的编码算法分两个部分：1.在数组a中找到本次计算的叶节点。2.对这个叶节点进行遍历，同时分配编码。具体步骤如下：1.将ss(j)赋给y（初始j=0），并在数组a中找到相应的叶节点。2. 对找到的叶节点进行遍历，如

36、果y代表的节点是左子节点，则赋0，反之赋1。然后令y指向当前遍历节点的父节点。当当前遍历节点的父节点为100时，停止遍历，同时指针a,o清零，j,e同时加一。至此得到一个叶节点的编码。3.按照1，2步骤进行运算，直到j=7。此时，得到所有的叶节点的编码。4.1.6 总结 本章对霍夫曼编码的硬件实现算法进行了研究设计，其基本思想是首先构建霍夫曼树，同时得到霍夫曼树节点的基本信息，构建出霍夫曼表，最后依据霍夫曼表进行分配码字。硬件实现霍夫曼编码的主要优势在于其更高的速度和更低的功耗。本文设计的霍夫曼编码结构采用的是一种比较传统的串行编码结构，可以从综合图中看出，其结构十分复杂，是典型的以资源换取速

37、度，功耗的消耗也不能保证，如果系统对数据处理量不大，分辨率要求不高可以使用，如果系统要求很高，则不能满足其要求。所以，并行的编码器将是以后研究和发展的重点。第五章 设计验证5.1 小波变换设计验证5.1.1 DA算法结构验证 本文设计的滤波模块采用的DA算法是输出是基于FIR滤波器的输出表达式改进来的，最终采用DA算法设计得到的滤波器输出为=+ 。现令; ; 依次类推，得出。将滤波器的输出化简为= +。 现在模拟本文设计的DA滤波器的工作过程，得到累加器和latch1（这里将latch1和mul模块整体看作latch1）在每个时钟到来后的输出结果，其结果如表2：时钟累加器latch112+（+

38、）3+（+）16+（+）（16个时钟后，一轮运算结束）。表3 累加器和latch1的输出结果latch1最终输出=+=(+。而在设计的最开始，我们已将求得的滤波器的系数扩大了倍，所以最后滤波器的输出结果为=+，与推导出来的公式一样，即本文设计的滤波器结构能够完全实现滤波功能。5.1.2 移位寄存器仿真验证 本文设计的移位寄存器的功能是在时钟上跳沿到来后，如果控制信号=1则数据写入寄存器，当输出使能信号=1时，输出当前移位寄存器的第一位，同时移位寄存器整体向右移一位。其仿真波形如下图： 图17 移位寄存器的仿真波形可以从图中看出移位寄存器的功能与设计相符，能够满足要求。 5.1.3 latch1

39、和latch2仿真验证latch1在每个时钟下跳沿到来后，储存累加器的输出结果并输出，latch2当第16个ready高电平到来后，输出latch1的输出结果，此即为最终滤波完成的数据。其功能仿真图如下： 图18 latch1功能仿真图图19 latch2功能仿真图从图中看出latch1的功能从图中看出就是实现了一个D触发器的功能，而latch2在ready信号到来16个后输出最后的输入值，实现了设计目标。5.1.4 DA滤波器的性能分析使用DA算法实现滤波器的核心是将滤波器的乘法运算转换为查找表运算，从而大大的减少了乘法器和累加器的使用。在查找表的实现环节上，通过“分解级联”的方式简化了查找

40、的规模，使之能够实现高阶FIR滤波器。滤波器功能验证时设定波形图中时钟周期clk为10ns，通过分析其仿真波形图可以发现，每隔180 ns左右的时间就可以得到一个输出，证明DA算法的运算速度仅仅只与输入数据序列的位宽有关。由表3可以看出系统耗用的资源也很少：Logic utilizationusedavailablcutilizationLogic elements327332161%Combination functions305332161%pins26647556%表4 系统综合的资源使用状况同时本次设计的滤波器一共使用了294个寄存器。滤波器仿真波形如下： 图20 滤波器的仿真波形图可

41、以看出经历18个时钟周期后，滤波器得到输出结果，与设计相符。 5.2 霍夫曼编码验证5.2.1霍夫曼树验证 输入9个数据101,59,11,10,7,6,5,2,0其中101为无穷大项，运行程序得到仿真图为： 图21 输入数组ss图22 得到的霍夫曼树序列s仿真图中，输出的第15个端口即为构建的霍夫曼树的根结点，整个霍夫曼树按照从上至下，从右至左的顺序放到序列s中。5.2.2分配编码验证 以上节输入叶节点为例，依据第四章的构建霍夫曼树的规则，我们可以得到一个如下图的霍夫曼树： 图23 构建的霍夫曼树从上至下，从右至左的将节点记下，得到的正是上节仿真得到的序列s。y在分配编码中的作用是作为指针参

42、与所有叶节点的遍历，所以通过y的值的变化可以看出遍历的正确性与否，以值等于6的叶节点为例，查看y的遍历（图中第三行put0输出y值）如下图所示：图24 叶节点值为6的节点的遍历过程 对照图23霍夫曼树中叶节点值为6的节点，其遍历过程正如仿真图所示，证明本文设计的编码算法的正确性。对所有的叶节点进行相同的遍历后得到最后的霍夫曼编码(b代表霍夫曼编码的输出)，如下图所示：图25 所有叶节点的霍夫曼编码跟据图23所示的霍夫曼树，可以求得每个叶节点（左节点赋0，反之赋1）的编码如下表：叶节点值霍夫曼编码000000200001500016011070111100011101059 1表5 每个叶节点的

43、霍夫曼编码所有叶节点的编码为10100010111011000010000100000跟图25所示的仿真值相等，所以霍夫曼编码算法完全正确。5.2.3 霍夫曼编码算法性能分析 本文设计的霍夫曼编码算法分为两部：先构建霍夫曼树然后再分配编码。本文输入8Bit数据，构建出一个霍夫曼树需要7个时钟周期。分配编码所用的时间较长，因为对每个叶节点需要对整个霍夫曼表进行一次遍历需要7个时钟周期，所以，所有的运算需要63个时钟周期左右才能完成。同时有的节点需要几个时钟周期才能遍历到，所以每生一个编码所需的时间是不确定的。所以本文设计的霍夫曼编码速度上不够理想。 第六章 总结与展望 本次毕业设计的主要研究对象

44、是基于SOPC的指纹识别系统数据压缩模块，经过查阅资料，本文主要对小波变换+压缩编码形式的压缩算法进行了较为详细的阐述。 本文首先介绍了指纹识别系统在当今世界的广泛应用，以及数据压缩模块对于指纹识别系统的重要性。同时对世界上较为通用的几个算法标准进行了简单的介绍。在第二章，我们就对本次算法的总体结构进行了大体的介绍。在第三章本文介绍了Mallet算法实现小波变换。在滤波器实现方面，采用DA算法实现，这种算法的优点是将传统FIR滤波器的乘法和累加以查找表的形式代替，使系统减少了大量的乘法器和累加器，从而大大的提高了滤波器的运算速度。本文设计的滤波器得到输出结果只需要18个时钟周期，这说明采用DA算法的滤波器的运算速度只与输入数据序列位宽有关。所以这种滤波器也很适合利用在大型工程中。其后就对二抽值模块设计进行了简要的介绍。第四章就霍夫曼编码展开了讨论，本文设计基于硬件可以实现的霍夫曼编码，具体思路是首先建立起霍夫曼树从而能