嵌入式MP3解碼器中Huffman算法的硬件加速

嵌入式MP3解碼器中Huffman算法的硬件加速

摘要Huffman解碼是MP3解碼流程中的一個重要部分，其運算量在整個流程中占有相當比重，其算法實現(xiàn)的優(yōu)劣直接關系到MP3的實時解碼。傳統(tǒng)的Huffman解碼多采用軟件實現(xiàn)，從而增大了CPU的負擔。本文介紹一種Huffman解碼的硬件加速方案，并對Huffman碼表進行了改進，而MP3解碼器已在Altera的FPGA上進行驗證，結果表明在實時解碼的前提下，節(jié)約了CPU資源，并可顯著降低CPU的工作頻率。關鍵字MP3；Huffman編碼；硬件加速；實時解碼

1引言Huffman編碼是一種無損的、可變長熵編碼，其理論依據(jù)是使各個符號的概率均勻化，即出現(xiàn)概率大的符號編成短碼，出現(xiàn)概率小的編成長碼。在MPEG1_III中，根據(jù)音頻數(shù)據(jù)的統(tǒng)計特性建有34張碼表，為了實現(xiàn)最優(yōu)的編碼，編碼器會根據(jù)當前處理的數(shù)據(jù)類型來選擇碼表進行編碼。由于是對頻域量化值進行編碼，一般大值主要集中在低頻部分，而零值則集中于高頻部分，所以各個頻段可以靈活選擇編碼效率更高的Huffman表。按照MPEG1_III標準，從零到Nyquist采樣頻率范圍上的量化值被分成bigvalue，count1，zero三個區(qū)域，對于bigvalue區(qū)和count1區(qū)采用不同的編碼方案。為提高編碼效率，在bigvalue區(qū)每兩個絕對量化值轉換為一個Huffman碼字；count1區(qū)4個絕對量化值轉換為一個Huffman字；zero區(qū)的量化值全為零，從而不需編碼和傳輸。另外為了進一步提高bigvalue區(qū)的編碼效率，將其細分為region0，region1，region2三個區(qū)域，允許每個區(qū)域選擇不同的碼表。

2Huffman解碼算法分析經(jīng)過分析，Huffman硬件加速實現(xiàn)的難點在于Huffman碼表的設計，碼表效率的高低直接決定了Huffman硬件解碼的速度。本設計采用分步查表法進行Huffman解碼，其主要思路是在碼表中加入索引來指明下一次查表的碼表位置，這樣查表工作就被分為若干次完成，每次讀入固定的比特數(shù)，如命中則輸出解碼值，否則根據(jù)當前位置的索引值去碼表中進行下一步搜索，圖1為所示步驟。這樣，只需增加少量存儲碼表空間就可以實現(xiàn)快速查找，一次讀入的比特數(shù)越多查找速度就越快。在對查表速度和存儲空間進行權衡后，對于MPEG1_III協(xié)議中的表1，表2及表3采用3bit的搜索步長，其它表采用4bit；同時也改進協(xié)議中的Huffman碼表以適應分步查表法。Huffman碼表的每一項都由碼字和碼表構成，且碼表中的每一項都按照輸入碼字的順序進行排列。下面以count1區(qū)的tableA為例加以說明。圖1分步查表法圖2為MPEG1_III協(xié)議中的tableA，圖3為根據(jù)分步查表法特點，將協(xié)議中的tableA調(diào)整后的新碼表。當輸入的碼字為0100時，它在碼表中對應的位置為地址0100。這樣排列可以很方便地根據(jù)輸入的碼字進行地址映射，減少了計算映射的邏輯單元。如果一次查表未能命中，則根據(jù)碼表中給出的跳轉地址進行二次查表。調(diào)整后的新碼表比原先有所增大，其目的是當輸入固定比特長度的碼字都可以在表中直接查找到，而不需額外的計算。在查表得到解碼

結果的同時也可讀出碼長，這樣也節(jié)省了額外的計算單元。圖2MPEG1_III協(xié)議中的tableA圖3tableA調(diào)整后的新碼表

3Huffman解碼器的硬件實現(xiàn)整個MP3解碼系統(tǒng)采用Altera公司的FPGA實現(xiàn)，其中的Huffman解碼器的硬件結構如圖4所示。Huffman解碼模塊與CPU之間的數(shù)據(jù)傳輸通過Wishbone總線進行。在解碼的時候CPU取出碼字以及相應的碼表號傳給Huffman硬件加速器，在完成解碼后將解碼值以及碼長傳送給CPU。Huffman碼表存儲在ROM中，Huffman解碼的過程也就是在計算ROM的地址。經(jīng)過對碼表的統(tǒng)計，在bigvalue區(qū)，總的碼表長度位2147，最大的x，y值都為15。在count1區(qū)，總的碼表長度為44，解碼值為0或1。在所有碼表中，最大的碼長為19bits，所以ROM的位寬為13bits，深度為2191。ROM的地址由基址和偏移地址兩部分構成。基址對應的是每個碼表在ROM中的起始地址，被固化在解碼器內(nèi)的基址寄存器中，可以根據(jù)碼流中指明的碼表序號進行輸出。偏移地址是根據(jù)實際輸入的碼字計算得到的解碼值在每個碼表中的相對地址，由于Huffman碼表是根據(jù)碼字進行排列的，所以偏移地址只要通過輸入的碼字進行簡單計算就可以得到。最后，將基址和偏移地址相加就得到了實際解碼值在ROM中所對應的地址。本設計對分步查表法進行了優(yōu)化，多次查表要多次讀取ROM而影響了速度，所以將多次查表在計算偏移地址的時候?qū)崿F(xiàn)。偏移地址計算單元可根據(jù)輸入的碼字和碼表進行計算，首先讀入4bit的碼字，如果一次命中則輸出偏移地址，否則將下面的若干比特輸入控制碼字寄存器，具體的比特數(shù)要根據(jù)選用的碼表來決定，這樣在查找若干次后就可以得到查表所需要的偏移地址。協(xié)議中規(guī)定的最長的Huffman碼字為19bit，因此最多只需進行5次迭代，與軟件實現(xiàn)所消耗的時鐘周期相比，有很大改進。圖4Huffman解碼器的硬件結構4結束語本文所提出的Huffman解碼的硬件加速方案，采用分步查表的方法，不僅可以做到MP3的實時解碼，而且經(jīng)過實際驗證，與Huffman解碼的軟件實現(xiàn)相比，減少了CPU的運算量，CPU的主頻可由原來的18M降至13M左右。本設計思想為相關領域的Huffman解碼電路提供了更有效的解決方法。

參考文獻[1]HashemianR.DirectHuffmancodinganddecodingusingthetableofcode-lengthsInformationTechnology：CodingandComputing[ComputerandCommunications]，2003WatkinsonJohn，TheMPE