ＰＮＧ的硬件解碼加速設計

鄭天翼　黃世震　韋　明

摘 要：討論PNG圖像解碼的硬件實現方法，針對PNG文件的圖像數據使用的LZ77和Huffman兩種無損壓縮算法，提出一種補充碼表的方法實現快速的硬件解碼，并采用較優的軟硬件協調機制，在節省功耗的前提下實現PNG硬件解碼的加速設計。該設計經Modelsim 6.3仿真測試和Matlab工具比較驗證，證明可以完全無失真地恢復PNG圖像。

關鍵詞：LZ77；Huffman；軟硬件協調；PNG硬件解碼

中圖分類號：TP391 文獻標識碼：B 文章編號：1004－373X(2009)04－182－03

Hardware Design for Accelerating PNG Decode

ZHENG Tianyi,HUANG Shizhen,WEI Ming

(Fujian Key Laboratory of Microelectronic & Integrated Circuit,College of Physics and Information Engineering,Fuzhou University,Fuzhou,350002,China)

Abstract：This paper discusses a hardware accelerated implementation for PNG image decoding within LZ77 and Huffman compression algorithm without any distortion,this design adopts complete patch－tree table to achieve fast hardware decode,cooperate hardware and software to accelerate hardware decode with less power consume under the test of Modelsim 6.3 and Matlab tools,the results show this design can recover PNG image without any distortion.

Keywords：LZ77;Huffman;cooperating of software and hardware;PNG hardware decode

0 引 言

PNG(Portable Network Graphic Format)是流式網絡圖形格式的簡稱，是一種位圖文件(Bitmap File)存儲格式［1］。PNG文件采用壓縮率高的LZ77和Huffman兩種無損壓縮算法，支持網絡彩色圖像傳輸，支持Alpha通道、定義透明區域和多重透明，逐步細化地顯示圖片［2］。

PNG壓縮的核心算法是采用Zip壓縮算法［3］，該算法的特點就是先利用LZ77算法進行短語式重復的壓縮得到未匹配的字節和匹配長度、距離的組合值，然后再根據Huffman算法進行單字節重復的壓縮最終得到壓縮碼流。PNG解碼的原理也就是壓縮的反過程，那么解碼時可根據碼表信息和壓縮碼流還原出原始圖像數據。

PNG文件的解碼通常由軟件完成，軟件解碼實現方式靈活，但相對硬件解碼而言，軟件解碼速度慢，能量消耗大，不利于移動設備的低功耗設計優化。為此，這里討論了PNG圖像的硬件解碼實現方法，其應用對象是手機專用芯片，對低功耗和解碼速度都有較高的要求，并解決了PNG解碼的快速查表、軟硬件協調和硬件加速等實現方法，而硬件加速解碼功能的主要作用是減少CPU的負擔，極大加快PNG圖片顯示速度，并在一定程度上減少了功耗，延長了手機的待機時間，具有很大研究與開發的實際價值。

1 PNG圖像解碼原理的介紹

1.1 LZ77算法介紹

LZ77 算法可以稱為“滑動窗口壓縮”［4］，該算法將一個虛擬的，可以跟隨壓縮進程滑動的窗口作為術語字典；要壓縮的字符串若在窗口中出現，則輸出匹配長度和距離的組合信息，來替換前面出現的相同字符串,且要求最小匹配的字符串為3個字節，這樣可以保證壓縮后的數據量小于原始數據。

例如窗口的大小為15個字符，剛剛編碼過的15個字符為：byhelloeveryone，即將編碼的字符為:hellotoeveryonehi。可以發現有些字符串前面已經出現過，則用()起來的字符串表示滑動窗口中已出現過的匹配串：(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規范的Deflate原則建立的，具有以下特點：

(1) 左邊的葉子編碼為0，右邊的為1；

(2) 編碼必須滿足“前綴編碼”的要求，即較短的編碼不能是較長編碼的前綴，這保證了碼的惟一性；

(3) 每一層葉子的節點頻率按從小到大排列，而同樣頻率的節點按字符值從小到大排列，這點也是PNG采用的Zip算法對Huffman算法的一種改進。因此，解碼時首先要提取出壓縮流中的碼表信息建立出Huffman樹，其中每個葉結點應包含有碼長和字符值信息，并把最終生成的碼表保存在RAM中供給Huffman解碼模塊查表還原出圖像原始數據。

2 PNG解碼的軟硬件協調機制

整個PNG硬件解碼過程都是由軟件來調度的，在硬件解碼中若校驗到圖片數據出錯或解碼完成時，則PNG硬件模塊通過配置專門的寄存器給軟件檢查做中斷處理；當軟件檢測到這個寄存器信號使能時就產生中斷，就能即使關閉PNG硬件解碼模塊，在數據有誤的情況下節省了硬件解碼的功耗。

解碼前后數據的搬運機制是通過公用的AVI模塊(相當于FIFO實現輸入輸出數據的緩存)實現了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 nm的工藝庫，在100 MHz的頻率下對PNG解碼核心模塊用DC進行綜合，結果如表1所示。(其中面積大小和功耗不包括RAM的面積和讀寫RAM的功耗)

6 結 語

這里討論了PNG解碼加速的硬件實現方法。其中分析了LZ77和Huffman兩種算法的硬件解碼原理，以及采用補滿Huffman樹的機制實現快速查表解碼，并運用較優的軟硬件協調機制，在節省功耗前的前提下實現PNG硬件解碼加速。

參 考 文 獻

［1］Brown C W,Shepherd B J.Graphic File Formats Reference and Guide.Manning Publications Co.,1995.

［2］Roelofs G.News and History of the Png Development Group.http://www.cdrom.com/pub/png/pngnews.html.

［3］李章晶,鄭國勤.針對無線通信領域的圖像壓縮的研究.計算機工程與設計,2006,27(23):4 471－4 474.

［4］Scott N R.Computer Number Systems and Arithmetic.New Jersey:Prentice Hall,Englewood Cliffs,1985.

［5］陶鈞,王暉,張軍,等.三維小波視頻編碼的可伸縮性研究.小型微型計算機系統,2005,26(2):285－288.

［6］Kakadiaris C.A Convex Penalty Method for Optical Human Motion Tracking.International Multimedia Conference.New York:ACM,2003:1－10.

［7］Zhang Z M.Independent Motion Detection Directly from Compressed Surveillance Video.International Multimedia Conference.New York:ACM,2003.

［8］Peleg A,Weiser U.MMX Technology Extension to the Intel Architecture.IEEE Micro.,1996,16(4):42－50.

［9］Deutch P,Gailly J －L,Adler M.GZip.http://www.gzip.org,2008.

作者簡介

鄭天翼 男，1983年出生，福建福州人，碩士研究生。主要從事數字信號處理與集成電路設計的研究。

黃世震 男，1968年出生，福建福州人，副教授。福建省ICC副主任，主持省部級重點科研項目多項。主要從事集成電路設計的研究。

韋 明 男，1979年出生，陜西西安人。主要從事數字集成電路設計的研究。