当前位置:首页 > 理财有道

huffman编码 静态哈夫曼编码的快速硬件实现

王李成泽石奥开李菁

中国电子科技大学(四川成都610054)

首届(2016-2017)全国本科集成电路创新创业大赛全国总决赛FPGA设计方向二等奖

本文提出的方案主要功能是连续接收0-9之间的256个任意值,对这256个数据完成输入数据元素的霍夫曼编码,最后先输出0-9个元素对应的编码,再根据输入数据序列输出每个数据对应的霍夫曼编码。

1系统设计方案

霍夫曼编码的基本思想是用较短的编码来表示出现概率较高的数据,而用较长的编码来表示出现概率较低的数据。通常的做法是根据输入数据的频率构造一个霍夫曼树,然后通过遍历树中的每个节点来生成叶节点,即输入数据的霍夫曼码。但是传统的方法有两大缺陷:一是构造Huffman树时,每次生成一个父节点,都会排序一次,不仅耗时,而且消耗大量硬件资源;第二,编码操作在霍夫曼二叉树生成后进行。事实上,每次生成父节点时,父节点中包含的叶节点的霍夫曼编码的一位已经被确定。因此,如果采用传统的方法,必须节省整个二叉树,生成二叉树的时间没有得到有效利用,浪费了更多的资源和时间。

基于以上两点,本文提出以下改进方案,操作步骤如下:

(1)统计所有输入数据元素的频率,依次将输入数据存入FIFO。

(2)将所有频率数据排序一次,给出排序后的频率数据。

(3)根据有序频率数据生成霍夫曼二叉树,每次生成一个父节点时,确定父节点中包含的叶节点的霍夫曼码的一位,并在构建二叉树时生成所有叶节点的霍夫曼码。

(4)根据生成的霍夫曼码,先依次输出0~9对应的码,然后根据输入的数据依次输出每个数据对应的霍夫曼码。

图1系统框图

对应于该方案的系统框图如图1所示,其中每个模块对应于上述操作步骤。

2系统实施

本部分将分模块介绍整个系统的实现方案。因为统计模块和输出模块没有优化,所以只介绍排序模块、二叉树和代码生成模块中使用的算法。

2.1分类模块

排序模块的主要功能是实现10个频率数据的排序操作。常用的排序算法有冒泡排序、快速排序、合并排序等。考虑到硬件实现的难度、分拣周期的数量以及消耗的硬件资源,我们选择使用分拣网络进行分拣。

图2奇偶校验排序网络

分类网络有很多种。本文主要使用的排序网络是奇偶排序网络,如图2所示,是一个四输入奇偶排序网络。图中有四条横线,分别代表四个网络a1、a2、a3和a4。网络之间的垂直连接线表示比较操作,在每次比较中,大的数字被切换到网络的上层,小的数字被切换到网络的下层。在第一个时钟周期,a1和a2,a3和a4同时比较排序,即均匀排序;在第二时钟周期中,a2和a3同时被比较和排序,即奇数排序;在第三时钟周期中,a1和a2、a3和a4同时被比较和排序;并且在第四时钟周期中,a2和a3被比较和排序。四个时钟周期后,四个网络上的数据将从大到小排列。

同样,使用排序网络对10个数据进行排序时,总共需要10个网络,消耗10个时钟周期。偶数排序和奇数排序交替进行5次,其中偶数排序同时进行5次比较运算,奇数排序同时进行4次比较运算。因此,分拣网络充分利用了硬件并行的特点,有利于缩短分拣周期。而且偶排序和奇排序的比较操作每次都是一样的,所以偶排序模块和奇排序模块可以复用,有利于减少硬件资源的消耗,整个排序模块只消耗9个比较器。

2.2二叉树和代码生成模块

排序操作完成后,为了更快地完成输入数据元素的霍夫曼编码,本文提出了二叉树生成和编码同时进行的方案,下面将结合实例给出该方案的具体实现过程。

图3二叉树生成和编码

这个方案的一个例子如图3所示。图中有五组寄存器:(1)叶节点寄存器a0~a4,存储元素0~4及其频率从小到大。例如,a0中的“4:2”表示元素4的频率为2。(2)父节点寄存器b0~b2按照父节点的生成顺序依次存储生成的父节点频率,因此父节点频率也是从小到大排列的。为了避免影响指针搜索的最小两个频率,将其初始值设置为一个较大的数,这里为255;(3)指针pta0、pta1、ptb0和ptb1指向要比较的四个数字。通过比较这四个数字,我们可以在所有频率中找到最小的两个频率,并生成一个父节点。可以用反证法证明,最小的两个频率一定在这四个指针所指的数据中。比较方法是比较pta0和ptb1指向的数字,比较pta1和ptb0指向的数字。根据比较结果,可以确定最小的两个频率。因为两次比较是同时进行的,所以只需要一次比较时间就可以确定最小的两个频率值,也避免了重新排序。每次比较后,指针会根据比较结果移动。(4)叶节点码寄存器,如a0~a4下面两行数据所示,用于存储霍夫曼码和叶节点的码长。(5)父节点中包含的叶节点寄存器,如图中指针上方的数据所示,用于存储父节点中包含的叶节点。如果b0的第00位为1,则表示其中包含的叶节点为元素0。

在初始状态下,每个寄存器的值如图3 (a)所示。通过比较四个指针,可以确定最小的两个频率是4和2。比较完成后,指针移动到图(b)所示的位置,频率4和2相结合,生成父节点6,存储在第一个父节点寄存器b0中。相应地,父节点的叶节点寄存器被修改为“11000”,表示父节点包含三个和四个。因此,获得了第一次比较完成后的图3(b)所示的状态。在这种状态下,类似地,根据四个指针确定最小的两个频率值,移动指针,生成父节点,修改父节点寄存器及其对应的叶节点寄存器,修改叶节点对应的编码寄存器。如此反复,直到只剩下两个节点,剩下的节点直接赋码。最后,修改相应的编码寄存器,得到每个数据元素对应的霍夫曼码,如图3(c)所示。图中,节点a0对应的叶节点码为“0000”,对应的长度为3,表示元素4的霍夫曼码为“000”。

从上述过程可以看出,这种方案的优势在于生成二叉树的同时生成数据元素的代码,因此代码生成不需要额外的时间,有效减少了编码周期的总数,生成二叉树时不需要保存整个二叉树。与传统方案相比,只需要保存父节点中包含的叶节点,减少了寄存器的使用,进一步降低了硬件消耗。

图4模拟时序图

3硬件实现

基于上述系统设计方案,本文采用Xilinx的Vivado软件平台进行综合实现。使用的芯片型号为xc7a100tcsg324-1。根据仿真结果,该设计从数据输入结束到编码完成总共消耗32个时钟周期,最差情况下运行频率达到250MHz。如图4所示,仿真时序图显示data_in为输入数据,output_data为编码后的串行数据输出。起始信号有效后,连续输入256个数据,系统根据输入的数据完成编码。最后,霍夫曼编码和编码的数据序列通过output_start信号串行输出,输出后的一个时钟周期内ouput _ done信号被拉高。

参考文献:

王芳秀,周康。引用该论文王志平,王志平,王志平.武汉轻工业学院学报,2011,30(4):45-48。

吴、。引用该论文王志平,王志平,王志平.计算机技术与发展,2009,19(10):51-53。

[3] Matai J,Kim J Y,Kastner R .能效规范霍夫曼编码[C]// IEEE,特定应用系统、架构和处理器国际会议。IEEE,2014:202-209。

娜娜。霍夫曼树算法的改进[J]。《计算机知识与技术》,2010(29):8224-8226。

[5]托马斯。科曼。算法导论[M]。机械工业出版社,2007。

1.《huffman编码 静态哈夫曼编码的快速硬件实现》援引自互联网,旨在传递更多网络信息知识,仅代表作者本人观点,与本网站无关,侵删请联系页脚下方联系方式。

2.《huffman编码 静态哈夫曼编码的快速硬件实现》仅供读者参考,本网站未对该内容进行证实,对其原创性、真实性、完整性、及时性不作任何保证。

3.文章转载时请保留本站内容来源地址,https://www.lu-xu.com/caijing/1599281.html

上一篇

潮州龙湖古寨 千年古潮州的缩影,寻古探秘龙湖古寨

下一篇

潜规则图片 刘萌萌潜规则照片外泄 刘萌萌被韦正潜规则真相

中国社会焦点网 百度沸点2019报告出炉,大数据下中国网民的人生百态与社会焦点

中国社会焦点网 百度沸点2019报告出炉,大数据下中国网民的人生百态与社会焦点

都市报记者黄 一年一度的百度沸点年度榜单于12月15日正式发布。今年百度开出了年度关键词榜、年度民族自豪感榜、年度沸点星等13个榜单。,呈现了2019年各领域网民最关注的话题。看2019年沸点榜单,“新中国成立70周年”占据了几个榜单的C位;与此同时,以AI和5G为首的科技热词搜索继续有增无减。目...

b超单上的秘密三数据 孕早期B超单上的这几个数据,孕妈看懂能知道胎儿的“小秘密”了

  • b超单上的秘密三数据 孕早期B超单上的这几个数据,孕妈看懂能知道胎儿的“小秘密”了
  • b超单上的秘密三数据 孕早期B超单上的这几个数据,孕妈看懂能知道胎儿的“小秘密”了
  • b超单上的秘密三数据 孕早期B超单上的这几个数据,孕妈看懂能知道胎儿的“小秘密”了

OSM 【教你一招】OSM数据获取、清洗整理、典型应用全套技术大公开!

  • OSM 【教你一招】OSM数据获取、清洗整理、典型应用全套技术大公开!
  • OSM 【教你一招】OSM数据获取、清洗整理、典型应用全套技术大公开!
  • OSM 【教你一招】OSM数据获取、清洗整理、典型应用全套技术大公开!

aced 十大ACE/ACED专家齐聚一堂,一场不容错过的数据技术盛会

  • aced 十大ACE/ACED专家齐聚一堂,一场不容错过的数据技术盛会
  • aced 十大ACE/ACED专家齐聚一堂,一场不容错过的数据技术盛会
  • aced 十大ACE/ACED专家齐聚一堂,一场不容错过的数据技术盛会

qq飞车微博 QQ飞车IP数据分析:贴吧425万粉丝 微博129万关注 中年玩家是主力

  • qq飞车微博 QQ飞车IP数据分析:贴吧425万粉丝 微博129万关注 中年玩家是主力
  • qq飞车微博 QQ飞车IP数据分析:贴吧425万粉丝 微博129万关注 中年玩家是主力
  • qq飞车微博 QQ飞车IP数据分析:贴吧425万粉丝 微博129万关注 中年玩家是主力

缔凡化妆品 化妆品行业年度十大数据:谁会恐慌,谁又在期待?

  • 缔凡化妆品 化妆品行业年度十大数据:谁会恐慌,谁又在期待?
  • 缔凡化妆品 化妆品行业年度十大数据:谁会恐慌,谁又在期待?
  • 缔凡化妆品 化妆品行业年度十大数据:谁会恐慌,谁又在期待?
感知网 数据中心感知网络技术漫谈

感知网 数据中心感知网络技术漫谈

======= 感知网络最早是弗吉尼亚理工大学提出的。感知网络是指通信网络能够感知现有的网络环境,通过了解环境实时调整通信网络的配置,智能适应专业环境的变化。从字面上看,不难理解,感知网络其实可以看作是SDN的升级版。SDN用软件定义网络,把软件和硬件分开,通过软件集中控制网络。此外,感知...

星际机甲战歌 包包紫笔下的科幻小说《外挂也疯狂》《末世好孕》《我只是数据》

  • 星际机甲战歌 包包紫笔下的科幻小说《外挂也疯狂》《末世好孕》《我只是数据》
  • 星际机甲战歌 包包紫笔下的科幻小说《外挂也疯狂》《末世好孕》《我只是数据》
  • 星际机甲战歌 包包紫笔下的科幻小说《外挂也疯狂》《末世好孕》《我只是数据》