yabo2008

:在图像处理、文件传真、视频压缩编码中,哈夫曼编码是最常用的一种编码方式。本文设计并实现了对一段数字序列进行哈夫曼编码并将编码结果串行输出的电路模块,电路由输入数据的排序、数据的哈夫曼编码、数据序列编码的结果输出三个核心模块组成,在Xilinx平台上通过硬件描述语言实现该电路。仿真结果表明,该电路编码正确,并具有较高的工作频率和编码效率。

作者孟欢 包海燕 潘飞 电子科技大学 微电子与固体电子学院(四川 成都 610054)

摘要:在图像处理、文件传真、视频压缩编码中,哈夫曼编码是最常用的一种编码方式。本文设计并实现了对一段数字序列进行哈夫曼编码并将编码结果串行输出的电路模块,电路由输入数据的排序、数据的哈夫曼编码、数据序列编码的结果输出三个核心模块组成,在Xilinx平台上通过硬件描述语言实现该电路。仿真结果表明,该电路编码正确,并具有较高的工作频率和编码效率。

哈夫曼编码是一种可变字长的无损编码方式。对于出现概率大的元素编以短字长的码,对于出现概率小的元素编以长字长的码,来实现平均码长最短。多媒体技术的广泛应用导致数据量的迅速增大,对哈夫曼编码在速度上有了更高的需求。利用硬件设计的大流量和并行性处理的优势,可以大大地提高编码效率和传输速度。哈夫曼编码的核心即建立最优二叉树,各元素的路径就是它所对应的编码结果。主要内容包括数据的排序和元素的编码两个方面。

本文是完全在硬件条件下实现哈夫曼编码设计的,在排序部分采用流水线结构,通过流水线实现对数据频数比较,控制数据按照频数大小由小到大排序。在编码模块创新性地采用自顶而下的查找方式,由状态机寻址得到父节点的哈夫曼编码,进而得到左右子节点的哈夫曼编码结果。在输出模块中通过4个寄存器对编码结果进行缓存,控制寄存器读写指针进行编码结果的缓存与输出,保证数据输出的连续性。

利用vivado的设计平台[1],以xc7a100tcg324-1作为目标芯片,对输入的数据序列进行哈夫曼编码及输出,设计电路。电路的接口时序如图1所示。

1)复位结束,在开始信号start产生后,将一段数字序列(256个0~9的数据元素)输入电路进行哈夫曼编码,data_in的数据宽度为4,输入需要256个时钟周期。

3)output_data数据包含2个部分。先输出0~9元素对应的编码结果,接着输出数据序列的哈夫曼编码,输出完毕后产生output_done信号。

hfm_build:完成元素排序。根据输入的频数大小,输出各节点元素的排序结果。

hfm_code:数据编码模块。根据hfm_build输出的元素排序结果,自顶向下完成0到9这10个元素的哈夫曼编码。

output_data:数据输出格式。使用brk信号作为0~9元素的编码输出和序列编码输出的分隔,此时输出为0,之后输出数据序列对应的编码即图中ram_data_out信号,也就是序列对应的编码。所有的编码结果都是先输出低位再输出高位。

统计部分结束之后需要对数据进行排序,根据输入数据各元素的频次大小,对数据进行排序。该部分主要采用流水线的设计思路,当数据和频次进入排序模块之后,与模块内已经进来的所有数据的频次进行比较,输出频数较大的数据,寄存频数较小的数据。流水线单级结构RTL级电路[2]设计如图3所示。in_count和in_data为频数和对应元素的输入端,out_count和out_data分别对应频数和对应元素的输出端。

10个元素对应18个子节点,要完成对二叉树18个子节点的排序,则总的排序电路由18个单级排序结构组成,根据哈夫曼编码的性质,本设计将每次排序得到的最小两个元素的频数相加作为新元素的频数。例如频数最小的两个元素为9和5,作为左右子节点,父节点对应的频数为9和5的频数之和,其对应的元素为10,生成的父节点依次为11、12….17,新生成的父结点与剩下的元素进行新一轮的排序,而已经比较出两个最小频数的元素,不再参与排序。排序结构的各级输入通过计数器来控制。排序完以后,取每级寄存器中的元素bit0~bit17,即18个节点按照频数由小到大排序的元素序列,输出给编码模块。

该部分设计主要包括编码FSM、状态控制模块、计数模块、数据编码模块和流水线译码输出模块,其中zero_flag为数据频数为0的标志信号。数据编码模块结构框图如图4所示。

根据排序模块的规律,bit0和bit1的父节点是元素10,bit2和bit3的父节点是元素11,bit4和bit5的父节点是元素12,bit6和bit7的父节点是元素13,bit8和bit9的父节点是元素14,bit10和bit11的父节点是元素15,bit12和bit13的父节点是元素16,bit14和bit15的父节点是元素17,bit16和bit17的父节点是根节点。根据哈夫曼树的特点,父节点的编码为xxxxxxxxx,则左节点的哈夫曼编码为xxxxxxxx0,右节点的哈夫曼编码为xxxxxxxx1。

编码FSM依次控制输出父节点17至父节点10,首先当输出父节点17时,它为根节点的左节点或右节点,通过查找到排序结果中的对应位置bit16或者bit17,假定bit16的编码为0,bit17的编码为1,则父节点17的编码可以确定,那么它左节点bit14,右节点bit15的编码也就确定了。当编码FSM输出父节点10时,通过查找确定元素10的编码,那么bit0和bit1作为元素10的左右节点,编码结果同样也可以确定。至此,数据0~17对应的code0~code17都已确定。

本文设计了流水线比较输出电路来确定数据0-9对应的哈夫曼编码。流水线个元素对应的编码,那么需要级联10级流水线比较的单级结构。其中code0~code17依次送入in_bit端,第i级的Cmp_bit为i,当In_bit[i]和Cmp_bit[i]相同时,那么In_code[i]即为元素i对应的哈夫曼编码,输出为code[i]。如果In_bit[i]和Cmp_bit[i]不相同时,将Out_bit[i]和Out_code[i]输出给下一级继续比较。当10级电路都参与比较以后,每级比较结构对应的输出端code[i]为0-9对应的哈夫曼编码(i=0….9)。

在输出阶段,先输出0~9对应的哈夫曼编码,接着输出数字序列对应的哈夫曼编码。考虑到哈夫曼编码变字长输出的特性,那么,编码输出的连续是本模块设计的难点,为了使编码在输出端连续输出,在编码的阶段,进行了每个数据元素编码长度的统计,同时配合4个缓冲寄存器,来实现输出的连续性。哈夫曼输出模块的结构图如图6所示。

输入的数据序列,在统计频数后存入ram中,在还没开始输出的时候,从ram中一次读出4个数据,并将对应的编码存入4个缓存寄存器中。当0~9数据元素的编码输出完以后,这时,开始输出reg1中的值,每输出1位,编码长度length减1,同时编码结果code右移1位进行输出。当length为1时,读出ram下一地址的数据,并将对应的编码结果写入reg1中,同时开始输出reg2中的编码值,这样读写在四个reg中的轮流切换,实现了数据的连续输出。

为了直接明了判断设计的正确性,本文设计的测试方案是:将一组随机数据序列存入rand_bin.txt中,先采用C语言完成哈夫曼编码的软件设计[3],按照统一的格式存入hafuman.txt文件中,与本设计结果进行比较。

创建激励文件test_bench,首先在start信号之后,将rand_bin.txt文件里的数据读出并送给data_in信号,在output_start信号之后,将hafuman.txt文件里的数读出来送给soft_result信号,作为软件编码的结果,将硬件编码结果output_data与软件编码结果soft_result比较,如果相同,那么error信号为低,如果其中有数据不相同,则error变高,提示此次编码有误。

测试结果如图7所示。其中error信号保持为低电平,表明哈夫曼编码正确。

电路功能正确实现后,对工作时钟进行了约束[4],将pll倍频到245M时,如图8所示,观察到电路中各触发器的建立时间余量为正,表明时序通过。

在设置好合适的综合策略后[5],对电路进行后防线,在某一组随机数据下,本设计需要的工作周期数(start信号到output_start的时钟周期)为316个,其中数据输入的时钟周期数为256,编码生成到编码开始输出的时钟周期数为60。由于哈夫曼编码是变字长的,所以数据序列的编码长度根据输入数据的不同而有所差异,即output_start到output_done之间的时钟周期数在不同的输入数据下结果不同。

[2]张颖超.基于FPGA的Huffman编码并行实现及高速存储系统设计[D].西安:长安大学,2015.

本文来源于《电子产品世界》2017年第11期第51页,欢迎您写论文时引用,并注明出处。

更多精彩尽在这里,详情点击:https://pnwfx.net/,弗赖堡队

鸭脖体育是什么

哈夫曼编码(HuffmanCoding),又称霍夫曼编码,是一种编码方式,可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短…

一、基本概念最基本的压缩编码方法是赫夫曼编码。赫夫曼编码的定义如下:二、概念详解1、赫夫曼树将一个班级每个学生的百分制成绩根据统一的标准换算成五级分制的成绩,标准如下:假设学生的成绩在五个等级上的分布…博文来自:阿兵-AI医疗的专栏

霍夫曼在1952年提出了霍夫曼编码,霍夫曼编码是一种无损的统计编码方法,利用信息符号概率分布特性来改编字长进行编码。适用于多元独立信源。霍夫曼编码对于出现概率大的信息符号用字长小的符号表示,对于出现概…博文来自:revitalise的博客

1.问题描述假设某文本文档只包含26个英文字母,应用哈夫曼算法对该文档进行压缩和解压缩操作,使得该文档占用较少的存储空间。2.基本要求(1)假设文档内容从键盘输入;(2)设计哈夫曼算法的存储结构;(3…博文来自:鸽子的博客

霍夫曼编码(HuffmanCoding)是一种编码方法,霍夫曼编码是可变字长编码(VLC)的一种。霍夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出…博文来自:summer

1)初始化:根据给定的n个权值 ,构造n棵只有一个根结点的二叉树, n个权值分别是这些二叉树根结点的权。2)找最小树:在F中选取两棵根结点树值最小的树作为左、右子树,构造一颗新的二叉树,置新二叉树根的…博文来自:程序媛的自学笔记

哈夫曼树哈夫曼树, 即带权路径最小的树, 权值最小的结点远离根结点, 权值越大的结点越靠近根结点图解图(3)即为哈夫曼树哈夫曼编码左孩子路径编码为 0, 右孩子路径编码为 1图解即A 的编码: 0D …博文来自:Sock的博客

2018.5.16最近一段时间忙于实验室各种项目和辅导员的各种杂活,间隔了半周没有耐下心学习。导师最近接了一个要PK京东方的项目让我来做总负责,确实是很惊喜了。责任心告诉我不能把工作做水了,但是还是尝…博文来自:NJU_ChopinXBP的博客

描述 实践是检验真理的唯一标准。 很多课程只有亲手实践才会真正掌握。一起看看下面的关于课本上的Huffman Code的问题吧 现在有篇文章,请用二进制前缀编码对文章中出现所有字符进行其编码,使编码后论坛

Huffman编码霍夫曼编码(英语:Huffman Coding),又译为哈夫曼编码、赫夫曼编码,是一种用于无损数据压缩的熵编码(权编码)算法。由美国计算机科学家大卫·霍夫曼(David Albert…博文来自:的博客

哈夫曼编码(Huffman Coding)是一种根据字符出现的概率对字符进行编码的编码方法哈夫曼编码的算法用java实现哈夫曼编码1.统计文本中各字符的出现次数方法一:/* * 输入一个文本,输出该…博文来自:smlt

解决问题:在信息传输、数据压缩的问题中,我们总希望能够找到一种编码能够将待处理数据压缩得尽可能短。对于这类问题,我们可以采用哈夫曼编码解决。解决问题的方法:我们可以通过构建哈夫曼树来得到哈夫曼编码。关…博文来自:我的博客

给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树。由此得到的二进制前缀编码称为哈夫曼编码。例如权w={5,29,7,8,14,23…博文来自:shayashi的博客

哈夫曼树的特点: 父节点是两个子节点的和。 利用最小堆来做,每次从最小堆中取出两个分别放到新树的左节点和右节点,然后父节点的值等于左右节点的权值和,再将此父节点插入到最小堆中。 因此哈夫曼树没有度(子…博文来自:u013245479的博客

数据结构—哈夫曼编码1.哈夫曼树简介哈夫曼(Huffman)编码算法是基于二叉树构建编码压缩结构的,它是数据压缩中经典的一种算法。算法根据文本字符出现的频率,重新对字符进行编码。因为为了缩短编码的长度…博文来自:wintershii的博客

赫夫曼编码(huffman codes)是一种非常有用的数据压缩方法,通常能将数据压缩20%~90%。从具体问题出发,假设我们有一包含10000个字符的文件,这些字符仅由6个不同的字符组成,就设这6个…博文来自:leafinsnowfield的专栏

贪心算法的原理:赫夫曼编码可以很有效地压缩数据:通常可以节省20%~90%的空间。根据每个字符的出现频率,赫夫曼贪心算法构造出字符的最优二进制表示。变长编码可以达到定长编码好得多的压缩率,其思想是赋予…博文来自:勇气与行动

哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛,如JPEG中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有…博文来自:u014028063的博客

假设有如下图的数据:数字表示每个词出现的次数。 我们根据每个词出现的频数,画出如下这样的图。其实就是先从最小的频数出发,比如F,H,出现的是1,而他们两个加起来就是2,因此他们的上一节点就是2。以此一…博文来自:多元思考力

在一般的数据结构的书中,树的那章后面,著者一般都会介绍一下哈夫曼(HUFFMAN)树和哈夫曼编码。
更多精彩尽在这里,详情点击:https://pnwfx.net/,弗赖堡队哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛,如JPEG中就应用了哈夫曼编码。 首先介绍什么是哈…博文来自:Y_23k_bug的专栏

读书笔记:现实中,文件可能相当大。在传输过程中,希望降低编码总的所需的比特数。哈夫曼编码的主要思想就是降低出现频率高的字符的码字长度。例如我们日常对话中,“我”,“你”,“他”,这种汉字出现频率高的汉…博文来自:wupeizhi的博客

现有一段文言文,要通过二进制哈夫曼编码进行压缩。假设这段文言文只由4个汉字“之”“乎”“者”“也”组成,它们出现的次数分别为700、600、300、200。那么,“也”字的编码长度是(3 )。哈弗曼编…博文来自:weixin_30399155的博客

Question请设计一个算法,给一个字符串进行二进制编码,使得编码后字符串的长度最短。Algorithm哈夫曼编码,权为各个字符出现的频率,再借助小根堆计算。 比如: MT-TECH-TEAM 哈希…博文来自:Dufre

转自:在一般的数据结构的书中,树的那章后面,著者一般都会介绍一下哈夫曼(HUFF…博文来自:Magician的博客

哈弗曼树及编码哈弗曼树算法第一步:初始化n个单节点的树,并为它们表上字母中的字符。把每个字符的概率记在树的根中,用来指出树的权重(更一般地说,树的权重等于树中所有叶子的概率之和)。第二部:重复下面的操…博文来自:Rp的博客

一 . 基本概念:赫夫曼树:给定带权的N个叶子构成的所有二叉树中,树的带权路径长度最小的二叉树(最优二叉树)带权路径长度:所有树叶到树根之间的路径长度与该节点上权的乘积权:赋予节点的有意义的参数二 ….博文来自:Kprogram的博客

由于我之前一直强调数据结构以及算法学习的重要性,所以就有一些读者经常问我,数据结构与算法应该要学习到哪个程度呢?,说实话,这个问题我不知道要怎么回答你,主要取决于你想学习到哪些程度,不过针对这个问题,…博文来自:帅地

大学四年,看课本是不可能一直看课本的了,对于学习,特别是自学,善于搜索网上的一些资源来辅助,还是非常有必要的,下面我就把这几年私藏的各种资源,网站贡献出来给你们。主要有:电子书搜索、实用工具、在线视频…博文来自:帅地

人生苦短,我用 Python前文传送门:小白学 Python 爬虫(1):开篇小白学 Python 爬虫(2):前置准备(一)基本类库的安装小白学 Python 爬虫(3):前置准备(二)Linux基…博文来自:极客挖掘机

作者 Rocky0429来源 Python空间大家好,我是 Rocky0429,一个喜欢在网上收集各种资源的蒟蒻…网上资源眼花缭乱,下载的方式也同样千奇百怪,比如 BT 下载,磁力链接,网…博文来自:Rocky0429

夜深人静,电视和电脑都已经关机休息,但是我还在默默工作,我安静地趴在你家中的某个地方,7*24小时不眠不休,任劳任怨,目的只有一个,能让你舒服地躺在床上,畅快地刷手机!没错,这就是我,……博文来自:码农翻身

yabovip2022

更多精彩尽在这里,详情点击:https://pnwfx.net/,弗赖堡队

:传统的硬件实现哈夫曼编码的方法主要有:预先构造哈夫曼编码表,编码器通过查表的方法输出哈夫曼编码[1];编码器动态生成哈夫曼树,通过遍历节点方式获取哈夫曼编码[2-3]。第一种方法从平均码长角度看,在很多情况下非最优;第二种方法需要生成完整的哈夫曼树,会产生大量的节点,且需遍历哈夫曼树获取哈夫曼编码,资源占用多,实现较为麻烦。本文基于软件实现[4]时,使用哈夫曼树,会提出一种适用于硬件并行实现的新数据结构——字符池,通过对字符池的频数属性比较和排序来决定各个字符节点在字符池中的归属。配置字符池的同时逐步生成

作者/ 贾先韬 张旭 刘泽曦 山东大学 物理学院(山东 济南 250100)

摘要:传统的硬件实现哈夫曼编码的方法主要有:预先构造哈夫曼编码表,编码器通过查表的方法输出哈夫曼编码[1];编码器动态生成哈夫曼树,通过遍历节点方式获取哈夫曼编码[2-3]。第一种方法从平均码长角度看,在很多情况下非最优;第二种方法需要生成完整的哈夫曼树,会产生大量的节点,且需遍历哈夫曼树获取哈夫曼编码,资源占用多,实现较为麻烦。本文基于软件实现[4]时,使用哈夫曼树,会提出一种适用于硬件并行实现的新数据结构——字符池,通过对字符池的频数属性比较和排序来决定各个字符节点在字符池中的归属。配置字符池的同时逐步生成哈夫曼编码,可以提高硬件利用率,并且无需额外操作来提取哈夫曼编码。

哈夫曼(Huffman)编码对出现频率较高的字符采用较短的编码,对出现频率较低的字符采用较长的编码,它可以保证平均码长最短,具有较高的编码效率。因而哈夫曼编码被广泛应用于数据压缩领域。已有的硬件实现方法包括预先构造哈夫曼编码表和模仿软件实时生成完整哈夫曼树两种。前一种方法在大多数情况下不是最优编码,后一种方法不仅需要生成大量节点,而且需要额外硬件模块实现遍历节点操作。针对这些问题,本文提出一种新的适用于硬件实现的数据结构——字符池来对输入数据实时生成哈夫曼编码。

哈夫曼编码是一种不等长编码,根据每个字符出现频率进行编码,每个字符的编码不能是其他字符编码的前缀,所有字符编码总长度相比原码而言将会降低。

本文采用自顶而下的设计方式。总体框架由一个顶层模块、接收模块、计算模块、输出模块和FIFO模块构成。顶层模块由其余4个模块连接而成,系统总体结构如图1所示。

接收模块:接收数据源并分类统计各字符出现的频数,数据接收完成后,接收模块向计算模块发送开始计算信号。计算模块进行计算,生成各字符对应的编码值,做成编码表,结束后向输出模块发送输出信号。最后输出模块通过查表方式输出各字符的编码值以及哈夫曼编码结果。FIFO模块用于接收原始数据和向输出模块提供数据源。

本文使用verilog语言在vivado平台上进行哈夫曼编码硬件模块的实现,选用器件为xc7a100tcsq324-1。

本文的FIFO模块使用vivado的IP核生成,设计时选择好相应参数配置,生成verilog文件后即可直接调用。

使用多个计数器对输入各字符频数以及输入字符总量进行计数,频数被存放在寄存器中,当字符输入结束(例如输入字符总量达到了约定值)时,输入模块向计算模块输出计算开始信号,同时频数寄存器中的数据被并行输出至计算模块。

本文基于哈夫曼树的思想构建了新的数据结构——字符池用于硬件实现哈夫曼编码。根据n种字符构建n个字符池和n个字符节点。每个字符池包含一个属性:包含的所有字符的频数之和。每个字符节点包含以下属性:所属字符池序号、自身编码值和自身编码长度。因此,定义n个寄存器记录字符节点对应的字符池序号、n个寄存器记录编码值、n个寄存器记录编码长度以及n个寄存器记录字符池的频数。

进行哈夫曼编码计算时,计算模块通过执行循环操作完成各字符编码的生成以及字符在字符池中的移动。以图2中的实例描述计算流程。

图2中共有5种字符,各自频数为:“0”:5,“1”:10,“2”:20,“3”:30,“4”:35。

图2(a)为初始化效果,此时每个字符池包含一个字符,每个字符池的频数恰为那个字符的频数;每个字符的编码值和编码长度清零。图2(a)到图2(d)共经过4次循环操作,最终可以从图2(d)中读取出每个字符的编码值和编码长度,“0”编码值为0011,“1”编码值为1011,“2”编码值为111,“3”编码值为01,“4”编码值为0。

每次循环操作包含排序、挑选、最小值和次小值求和、频数更新、字符移动、编码值更新及编码长度更新8步。其中前4步按顺序完成,然后同时完成后4步。总循环次数由字符种类数控制。

排序操作功能是将每个节点池的频数从小到大进行排序,本文借鉴了参考文献[5]中的方法,硬件实现时通过构建比较器阵列将每两个数两两比较,再通过加法器对每个字符频数的比较结果求和。对一个字符频数,若它小于另一个字符的频数,则相应结果为0,否则为1。那么通过指定字符频数与其他字符频数的比较结果之和可以得知它的频数在所有频数中的位置。

挑选操作是将排序操作中比较结果为0和1对应的字符频数选出,它们代表最小频数和次小频数,挑选操作同时挑选出这两个频数对应的字符池ID。硬件实现时构建多个比较器,将比较结果之和与0和1比较,再通过多路复用器从多个频数和字符池ID中准确挑选出所需的值。例如在图2(b)中,挑选出的两个频数为15和20,它们对应字符池ID为1和2。

接下来的最小值和次小值求和操作就是将挑选操作挑选出的最小频数和次小频数求和,然后输出。此步骤硬件实现时需要一个多位加法器。例如在图2(b)中,求和值为15+20=35。

频数更新操作指根据挑选操作挑选出的结果进行字符池频数的更新。按照本文约定方法,将最小频数对应字符池的频数更新成无效值,无效值应大于所有可能的频数,它的目的是避免此字符池的频数被接下来的循环挑选操作挑选出。本文将次小频数对应字符池的频数以求和操作的加法结果替代。例如图2(c)中1号字符池频数变成100,2号字符池频数变成35。

字符移动操作指将特定字符从一个字符池移动到另一个字符池中。按照本文约定方法,将最小频数对应字符池的所有字符移动到次小频数对应字符池中。例如将图2(c)和图2(b)对比可发现1号字符池的字符“0”和“1”被移动到了2号字符池中。

编码值、编码长度更新操作中,按本文约定方法,将最小频数对应字符池的所有字符编码值左移1位并在最后一位补0,长度加1。将次小频数对应字符池的所有字符编码值左移1位并在最后一位补1,长度加1。将图2(c)和图2(b)对比可看出,字符“0”的编码值从0变成00,“1”编码值从1变成10,“2”编码值从无变成1。

输出模块负责从FIFO中读取出原始数据、从编码表中获取编码值,再通过并串转换以一位数据口首先输出各字符编码值,再输出字符串编码结果。

本文使用vivado对顶层模块进行综合实现,通过实现后仿真验证 结果正确性。

图3展示了模块输入时序。本文测试时以huf_in_start高电平脉冲标志数据输入开始,实际数据以4为并口输入,测试字符范围为“0”至“9”。

图4展示了模块输出时序。通过huf_out_start高电平脉冲表明输出开始。首先输出各字符编码序列,包含4bit编码长度和实际编码值,然后输出原始字符串的编码值。huf_out_end高电平脉冲表明输出结束。

图5为vivado控制台输出,它展示了各字符编码值以及原始字符和testbench进行的解码字符比较,说明模块正常运行。

本文提出了一种新的在硬件上实现哈夫曼编码的方法,利用本文的字符池数据结构,对每次输入的数据实时生成哈夫曼编码表,从平均码长角度保证了编码的最优,同时避免了生成完整的哈夫曼树,减少了资源占用,并避免了遍历哈夫曼树所需的额外操作,实现方便快捷。

[1]邓丽娟,田金文,柳健,等.哈夫曼编码器IP核的设计与实现[J].微电子学与计算机,2005(02):9-12.

本文来源于《电子产品世界》2017年第12期第40页,欢迎您写论文时引用,并注明出处。

鸭脖体育钱取不出来

作者 / 黄传 黄尚川 刘旭阳 北京航空航天大学 电子信息工程学院(北京 100191)

*第一届(2016-2017)全国大学生集成电路创新创业大赛全国总决赛FPGA设计方向获奖作品

Huffman编码是一种可变字长的无损压缩编码。根据字符出现的概率得到的可变字长编码表是Huffman编码的核心。概率低的字符使用较短的编码,概率高的字符使用的长的编码。

Huffman编码的具体方法是将序列中的信源符号先按出现的频次排序,把两个最小的频次相加,作为新的频次和剩余的频次重新排序,再把最小的两个频次相加,再重新排序,直到最后变成序列的总长度。每次挑出的最小两个频次所对应的信源符号或信源符号集构成二叉树的左右两支,对这左右两支赋予“0”和“1”的权重。符号的编码从树的根部开始一直到达符号所在的叶节点, 将路线”按最低位到最高位的顺序排好,就是该符号的哈夫曼编码。

算法核心思想就是利用哈夫曼编码过程中需要合并频次最小的两个符号集并且每次合并符号集不相交的特点,先用“独热码”对符号进行预编码(信源符号“0”用0000000001编码,信源符号“1”用0000000010编码…),在合并符号集时对两符号集的编码进行抑或,使新符号集的编码能反映符号集中的元素。比如一个符号集的编码是0000010011,按照之前的规定,这个符号集就含有“0”,“1”,“4”这三个信源符号。这样做的好处就是能通过对检测符号集编码中“1”的位置得到符号集中元素,从而在对符号的哈夫曼编码过程转化为对一个个符号集整体编码。

注意到每个符号集被合并时都会将参与合并的两个符号集的预编码相异或,并将结果作为新符号集的预编码。并行化处理就体现在这排序和编码可以同时进行。

在每次参与合并的两个符号集上都带有其相应的预编码,预编码不为0的位体现了这个符号集包含的信源符号。在每次排序完成后,将0和1分别赋予这两个符号集内包含的元素,
更多精彩尽在这里,详情点击:https://pnwfx.net/,弗赖堡队便可以在排序完成后立即得到所有元素的码字。

对于码字长度最小方差问题,对几个符号集频次相同的情况,优先合并符号集中所包含符号数量少的两个符号集。算法选择的下图中第二种算法,码长方差最小。

1)Receiver:统计频次信息,并控制shift register缓存这些信息,统计完成后输出频次信息;

2)Sorter:根据频次信息进行9次排序,每次排序输出相应的数据到code_gen;

功能:统计各个符号出现的频次,并控制移位寄存器保存输入序列,统计完成后,在输出端口串行输出信息。

频次的统计使用简单的寄存器操作即可完成,具体不赘述。在统计过程中,使能移位寄存器信号为高,统计完成后,valid信号产生高电平脉冲,示意排序器开始工作,同时在输出端将各个符号出现的频次按时钟节拍依次送入排序器。

为了便于描述,我们将排序器的操作对象定义为“节点”。一个“节点”中包含有一组待编码的符号,“节点”的频次为这些符号的频次之和。

该排序器的功能是输出具有两个最小频次的节点信息。data_0表示最小频次对应的节点信息,data_1表示次小频次对应的节点信息。

初始时,每个节点中仅有一个符号。排序器每次将具有最小频次的两个节点的信息输出(为data_0和data_1),然后将这两个节点合并成一个新的节点。如表3所示,对于5个节点进行排序的例子可以说明该排序器的工作原理。

第一次输出频率最小的两个符号的data,即A和E对应的data,分别为00001和10000;然后这两组符号被合并为同一个节点,即有表4结果。

类似上一次,第二次输出分别为10001和00010,然后这两组符号被合并,即有表5结果。

类似上一步,第三次输出分别为10011和01000,仍然将它们合并,即有表6结果。

则第四次输出为00100和11011。这也是最后一次输出。所以输出结果如表7所示。

类似地,对于此项目中10个符号的情况,只要用10位二进制数来表示相应的节点信息即可。

在本工程中,根据设计需求,可以算出,每个字符的编码位数最长可能为9位,最短为1位。所以存储编码表的寄存器应该至少有9位,每一位的可能状态有三种:“0”,“1”,“-”,分别表示“该位编码为0”、“该位编码为1”和“该位没有存储编码信息”。因此,我们使用两个比特来表示一位编码。

编码是根据data_0和data_1生成的,初始时,所有位都被置为“-”,然后根据data_0和data_1进行操作。对于data_0中的每一个符号,为其增加一位编码“0”;对于data_0中的每一个符号,为其增加一位编码“1”。表8为图1中的数据生成编码的过程。

输出格式:在output_start置高电平后、output_done置高电平前,output_data端为有效的输出数据。这些数据包含了霍夫曼编码表,以及对输入数据进行编码后的结果。

哈夫曼编码表按顺序存放了0~9的霍夫曼编码。对于某特定的符号,其哈夫曼编码表示为:该符号的的码字长度(长度为4比特),紧接着是该符号的码字。

先通过MATLAB程序产生用来测试电路的256个数据,这些数据根据一个概率向量p来生成,再利用Vivado仿真工具加载数据到电路输入端,并把电路输出的有效数据输出到文件中。

利用MATLAB对输出数据进行解码并和原始数据进行比对(编码正确性测试),还利用MATLAB内置的哈夫曼编码函数计算平均码长与电路得出的平均码长进行对比(平均码长测试)。下表是在不同概率向量p下得到的测试结果如表9所示。

对于不同的输入序列有不同的编码长度,所以电路的Total Cycle是不确定的。但是从start到output_start的周期间隔是确定的,为272个时钟周期,如下图所示。

在选择目标器件为xc7a100tcsg324-1进行综合、布线之后,资源消耗情况如表10所示。

yabo2010

霍夫曼编码压缩算法,是数据压缩中经典的一种算法。这是一种根据文本字符出现的频率,重新对字符进行编码,频率越高的词,编码越短,从而达到数据压缩的效果。

假设我们有这样的一段数据需要进行编码“beep boop beer!”。这段字符通过ASCII编码后的结果为62 65 65 70 20 62 6F 6F 70 20 62 65 65 72 21 (十六进制),总共有十五个字节。

下面我们需要把这个队列,转换成霍夫曼二叉树,这是一个带有权重的二叉树,在队列中每个字符出现的次数,标识这个字符的权重,霍夫曼二叉树始终保证权重高的在越高的地方。下面来介绍,二叉树是如何演变的。

我们从最左边开始,取两个元素来构造一个二叉树(第一个元素是左结点,第二个是右结点),并把这两个元素的权重相加,得到新的空元素。

同理,我们继续取最左边两个元素,进行权重相加(2+2=4),相加结果变大,需要对权重进行重新排序。

这里,我们把这个树的左边分支用0编码,右边分支用1,这样我们就可以遍历这棵二叉树获取每个字符的编码,例如:b的编码是 00,p的编码是101, r的编码是1000。我们可以发现出现次数越多的字符会越在上层,它的编码也越短,次数少的字符,编码越长。

利用这个编码表我们对字符串“beep boop beer!”重新进行编码,得到:0011 1110 1011 0001 0010 1010 1100 1111 1000 1001。共计40位二进制,而之前没重新编码时,是15字节共120位,这样看来压缩比例还是比较客观的。

更多精彩尽在这里,详情点击:https://pnwfx.net/,弗赖堡队