PNG的硬件解码加速设计

0 引 言 
    PNG(Portable Network Graphic Format)是流式网络图形格式的简称，是一种位图文件(Bitmap File)存储格式。PNG文件采用压缩率高的LZ77和Huffman两种无损压缩算法，支持网络彩色图像传输，支持Alpha通道、定义透明区域和多重透明，逐步细化地显示图片。
    PNG压缩的核心算法是采用Zip压缩算法，该算法的特点就是先利用LZ77算法进行短语式重复的压缩得到未匹配的字节和匹配长度、距离的组合值，然后再根据Huffman算法进行单字节重复的压缩最终得到压缩码流。PNG解码的原理也就是压缩的反过程，那么解码时可根据码表信息和压缩码流还原出原始图像数据。
    PNG文件的解码通常由软件完成，软件解码实现方式灵活，但相对硬件解码而言，软件解码速度慢，能量消耗大，不利于移动设备的低功耗设计优化。为此，这里讨论了PNG图像的硬件解码实现方法，其应用对象是手机专用芯片，对低功耗和解码速度都有较高的要求，并解决了PNG解码的快速查表、软硬件协调和硬件加速等实现方法，而硬件加速解码功能的主要作用是减少CPU的负担，极大加快PNG图片显示速度，并在一定程度上减少了功耗，延长了手机的待机时间，具有很大研究与开发的实际价值。

1 PNG图像解码原理的介绍
1．1 LZ77算法介绍
    LZ77算法可以称为“滑动窗口压缩”，该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为术语字典；要压缩的字符串若在窗口中出现，则输出匹配长度和距离的组合信息，来替换前面出现的相同字符串，且要求最小匹配的字符串为3个字节，这样可以保证压缩后的数据量小于原始数据。
    例如窗口的大小为15个字符，冈0刚编码过的15个字符为：byhelloeveryone，即将编码的字符为：helloto—e、，eryonehi。可以发现有些字符串前面已经出现过，则用()起来的字符串表示滑动窗口中已出现过的匹配串：(hello)to(everyone)hi。
    以上这些原始信息，可利用LZ77算法用匹配长度和距离的组合信息来替换有匹配的字符串，若碰到未匹配的字节则直接输出，压缩后的内容为：(5，13)to(8，15)hi。在LZ77解压缩时，只要维护好滑动窗口，随着压缩信息的不断输入，可根据匹配的组合信息从窗口中找到相应的匹配字符串作为输出，即可还原出原始数据。
1．2 Huffman算法介绍
    Huffman算法属于编码式压缩，利用各个单字节所使用频率不一样的特点，使定长编码转变为变长的编码，给频率高的字节更短的编码，使用频率低的字节更长的编码，起到无损压缩的效果。这样，经过LZ77压缩后的未匹配的字节和匹配的组合信息可以进一步地进行Huffman压缩，从而得到很高的压缩效率。
    例如，对于一组元素的字符值为s={a，b，c，d，e，f}，其对应的出现频率为P={10，2，2，2，2，9}。图1是根据以上信息建立的Huffman树。各元素出现频率和元素值如图1所示，编码后的各个元素长度分别为L一{1，3，3，3，3，2}，可见编码后储存这些字符值所需的空间极大地减少了。

    这棵Huffman树是根据PNG规范的Dellate原则建立的，具有以下特点：
    (1)左边的叶子编码为0，右边的为1；
    (2)编码必须满足“前缀编码”的要求，即较短的编码不能是较长编码的前缀，这保证了码的惟一性；
    (3)每一层叶子的节点频率按从小到大排列，而同样频率的节点按字符值从小到大排列，这点也是PNG采用的zip算法对Huffman算法的一种改进。因此，解码时首先要提取出压缩流中的码表信息建立出Huffman树，其中每个叶结点应包含有码长和字符值信息，并把最终生成的码表保存在RAM中供给Huff_man解码模块查表还原出图像原始数据。

2 PNG解码的软硬件协调机制
    整个PNG硬件解码过程都是由软件来调度的，在硬件解码中若校验到图片数据出错或解码完成时，则PNG硬件模块通过配置专门的寄存器给软件检查做中断处理；当软件检测到这个寄存器信号使能时就产生中断，就能即使关闭PNG硬件解码模块，在数据有误的情况下节省了硬件解码的功耗。
    解码前后数据的搬运机制是通过公用的AVI模块(相当于FIF0实现输入输出数据的缓存)实现了PNG数据的搬运：解码前，软件通过调配AVI模块从内存中搬取压缩数据给PNG硬件模块做解码；解码后的数据经过Resize模块缩放后又可以利用AVI搬运给VGA做显示，这种较优的软件调配机制，解决了该设计的软硬件协调问题，可以在节省功耗的前提下实现高效率的解码，具体的软件硬件协调原理如图2所示。

3 PNG解码的总体硬件结构
    PNG硬件解码加速的整体结构主要由Bytesshift字符容器、PNG头信息处理模块、Inflate table建Huffman表模块、Inflate fast快速解码模块、Lz77寻找匹配串模块、Filter反滤波反交织模块和Resize放大缩小模块7大模块组成。具体PNG解码的硬件流程图如图3所示。

    如图3可见，PNG解码的基本流程为：通过AVI模块从总线上搬取压缩数据到Bytesshift字符容器进行缓存，并转换为压缩比特流；通过PNG头信息处理模块保留下文件的头信息，通过控制Inflate table模块读取码长信息来建立Huffman表，并对压缩数据进行解码；解码后的数据经过Filter模块进行反滤波和反交织等处理，然后发给Resize模块做放大缩小处理后，并通过AVI模块将最终解码后的数据传输出去。其中，解码核心模块和Filter模块通过采用了数据的流水线处理方式，也极大地提高了．PNG的解码效率。

4 PNG核心解码模块的硬件结构
    由于编码长度可变和编码长度不统一，解码时若按位比较来查找Huffman表会消耗很多时间，且PNG数据流中Huffman编码的最长码长为9。因此，为了实现快速查表解码，本算法中将码长小于9的Huffman树的叶结点作为父结点来扩展到9层，即扩展出来的叶结点信息都同父结点一样，每次用固定的9比特压缩数据作为地址去查表。这样可以保证在每一个时钟内都可以查找到相应的字符值，就可以极大地提高硬件解码的效率。以前面的Huffman树为例子(如图4所示)，简单地将第4层以内的叶结点补充到第4层，即把整个Huffman二叉树补满，则在第4层的子叶结点的长度和字符信息都同父结点一样。

    这种扩展Huffman树的方法，可以实现迅速查找Huffman表，得到相应的字符值和匹配的组合信息值，对解出匹配的组合信息值，则根据LZ77原则还原出解码数据作为输出。
    该设计中的硬件解码核心模块可参考图5。这种硬件结构的优点是利用扩展码表的方法实现快速解码。核心解码的基本流程为：每次用固定的9 b压缩数据作为地址去查表，查出包含有码长和字符信息的叶结点，并根据码长信息从字符容器模块移出使用过的压缩数据，并等待新进的压缩数据与字符容器剩余的压缩数据组成新的9 b数据作为查表地址。在下一个时钟重复查表的过程，以此方式反复查表直至Huffman解码结束。

5 仿真和综合结果
    经Modelsim 6．3仿真提取出解码后数据，在Matlab工具中进行对原图显示与该设计解码后提取出的图像数据进行对比，比较结果完全一致，并且在验证平台上比较其对应的原始图像数据也完全吻合，因此，该硬件设计能够完全不失真的恢复PNG图像数据。
    在设计中，使用台积电90 nlTl的工艺库，在100 MHz的频率下对PNG解码核心模块用DC进行综合，结果如表1所示。(其中面积大小和功耗不包括RAM的面积和读写RAM的功耗)

6 结 语
    这里讨论了PNG解码加速的硬件实现方法。其中分析了LZ77和Huffman两种算法的硬件解码原理，以及采用补满Huffman树的机制实现快速查表解码，并运用较优的软硬件协调机制，在节省功耗前的前提下实现PNG硬件解码加速。