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

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

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

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

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

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

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

參考文獻(xiàn)[1]HashemianR.DirectHuffmancodinganddecodingusingthetableofcode-lengthsInformationTechnology：CodingandComputing[ComputerandCommunications]，2003WatkinsonJohn，TheMPE