2 霍夫曼編碼算法
---熵編碼規(guī)定，任何給定的一系列數(shù)據(jù)，如果每個(gè)數(shù)據(jù)符號(hào)出現(xiàn)的概率已知的話，就可以采用更有效率的方式來(lái)編碼?；舴蚵幋a的基本思想就是：給出現(xiàn)概率越高的數(shù)據(jù)符號(hào)編成越短的碼字，給出現(xiàn)概率越低的數(shù)據(jù)符號(hào)編成越長(zhǎng)的碼字。
---下面舉一個(gè)具體的例子來(lái)說(shuō)明霍夫曼編碼是如何在無(wú)損壓縮的前提下實(shí)現(xiàn)消除數(shù)據(jù)冗余的，詳見“表1”中陳列的數(shù)據(jù)樣本和編碼。由表中可以看出，對(duì)于同樣的信息源，霍夫曼編碼有效地減小了數(shù)據(jù)冗余，使輸出碼字的平均碼長(zhǎng)最短，與信源熵值最接近，編碼方法最佳。
---在應(yīng)用霍夫曼編碼的場(chǎng)合，在信息接收端需要霍夫曼解碼器來(lái)回復(fù)初始碼字。設(shè)計(jì)霍夫曼解碼器的主要問(wèn)題在于霍夫曼碼的變長(zhǎng)特性。

3 霍夫曼解碼器的硬件結(jié)構(gòu)研究
3.1比特串結(jié)構(gòu)的霍夫曼解碼器
---最簡(jiǎn)單的霍夫曼解碼器結(jié)構(gòu)就是對(duì)輸入的數(shù)據(jù)流按位進(jìn)行解碼，也就是比特串方式的解碼器。采用Moore型狀態(tài)機(jī)，可以很容易的設(shè)計(jì)出比特串方式的解碼器。假設(shè)給定任何一組霍夫曼碼，解碼器的有限狀態(tài)機(jī)可以通過(guò)如下方法建立：把每個(gè)結(jié)點(diǎn)（0或1）看作不同的狀態(tài)，把下一時(shí)刻的輸入看作向下一個(gè)狀態(tài)跳轉(zhuǎn)的條件。按照這樣的做法，“表1”中的霍夫曼碼的解碼器的狀態(tài)機(jī)可以構(gòu)建如圖1所示。
---雖然比特串方式的解碼器有它的優(yōu)點(diǎn)，設(shè)計(jì)難度小，消耗的硬件資源少，如圖1此例中只需要3個(gè)觸發(fā)器就可以了。但它的缺點(diǎn)也很明顯：由于輸入的碼字長(zhǎng)度的不同，解碼所需要的時(shí)鐘周期數(shù)也各不相同，這在解碼過(guò)程中會(huì)引起比特率的不連續(xù)，從而需要額外的硬件來(lái)解決這個(gè)問(wèn)題。另外，由于較長(zhǎng)的解碼時(shí)間也使比特串方式的霍夫曼解碼器不適合應(yīng)用在要求實(shí)時(shí)解碼條件的系統(tǒng)中。
---此種結(jié)構(gòu)的另一個(gè)問(wèn)題是，當(dāng)霍夫曼碼樹改變時(shí)不得不修改整個(gè)設(shè)計(jì)。一個(gè)更好選擇就是采用并行結(jié)構(gòu)的霍夫曼解碼器來(lái)加快解碼時(shí)間。

3.2并行結(jié)構(gòu)的霍夫曼解碼器
---采用并行技術(shù)設(shè)計(jì)的解碼器的優(yōu)點(diǎn)就是解碼可以在每個(gè)時(shí)鐘周期內(nèi)進(jìn)行，不受碼長(zhǎng)的影響，硬件復(fù)雜度的提高換來(lái)了解碼速度的加快。如圖2采用并行技術(shù)設(shè)計(jì)的解碼器的基本思想就是，采用查找表（LUT）把霍夫曼碼字保存起來(lái)，通過(guò)把待解碼字與查找表中碼字的比較匹配，來(lái)實(shí)現(xiàn)解碼的目的。這種結(jié)構(gòu)比特流輸入到解碼器的長(zhǎng)度是固定的，比如說(shuō)8位。8位的數(shù)據(jù)輸入長(zhǎng)度有可能包含多于一個(gè)碼字的數(shù)據(jù)，這樣需要一個(gè)緩沖器來(lái)保存輸入數(shù)據(jù)流。緩沖器可以用桶型移位寄存器來(lái)實(shí)現(xiàn)，應(yīng)用緩沖器的另外一個(gè)目的就是能保證在一個(gè)碼字解完以后，可以移位到正確的位置。緩沖器中的碼字解完以后，開始從比特流中接收新的碼字，重復(fù)上面的過(guò)程，因此，解完緩沖器中的可能碼字需要多于一個(gè)時(shí)鐘周期的時(shí)間。此外，為了使查找表中的數(shù)據(jù)
---與輸入碼字匹配，還需要保存每個(gè)對(duì)應(yīng)碼長(zhǎng)的值，這樣，一個(gè)碼字解完后，查找表同時(shí)把碼長(zhǎng)的值輸入到一個(gè)累加器。累加器的作用有兩個(gè)：一是指出緩沖器中下一個(gè)待解碼字的位置，這一步是通過(guò)累加前幾次碼字的長(zhǎng)度來(lái)計(jì)算的；二是當(dāng)所有碼字解完以后通知緩沖器從比特流接收新的碼字。查找表的結(jié)構(gòu)由數(shù)據(jù)指針和存儲(chǔ)器組成，存儲(chǔ)器中預(yù)先存儲(chǔ)著解碼時(shí)要使用的霍夫曼碼表。
---以“表1”的碼表為例，假設(shè)第一個(gè)輸入的數(shù)據(jù)流由八位組成：“00100110”。開始解碼的第一個(gè)周期累加器的值為“0”，解碼的碼字為“00”（A），碼長(zhǎng)為“2”。第二個(gè)周期，累加器的值為第一周期解碼的碼長(zhǎng)“2”，累加器控制緩沖器移位2位，這樣，解碼的碼字為“10”（D），碼長(zhǎng)為“2”。第三個(gè)周期，累加器的值為前兩個(gè)周期解碼的碼長(zhǎng)的和“4”，累加器控制緩沖器移位4位，解碼的碼字為“011”（C），碼長(zhǎng)為“3”。第四個(gè)周期，累加器的值為“7”，緩沖器中還剩一位數(shù)據(jù)。累加器控制緩沖器將前七位移出，輸入新的比特流。算上上次解碼剩下的一位“0”，假設(shè)第二個(gè)輸入的8位數(shù)據(jù)是“10010101”，這樣，下一個(gè)被解出的碼字是“01001”（E）。第五個(gè)時(shí)鐘周期，累加器的值為“12”，已經(jīng)大于緩沖器的8位容量，因此用累加器的值減去“8”得到的值才是緩沖器中下一個(gè)未解碼數(shù)據(jù)的位置。解碼器重復(fù)以上過(guò)程，直到所有比特流中的數(shù)據(jù)全部解完。
---從上面的例子可以看出，不管碼字的長(zhǎng)短，各個(gè)碼字解碼所需要的時(shí)鐘周期是相同的，而且解碼的時(shí)間相對(duì)也比較短，比較適合要求實(shí)時(shí)解碼的環(huán)境。而且當(dāng)霍夫曼的碼表改變的時(shí)候，只需要修改查找表中的數(shù)據(jù)就可以了，在通用性方面也比較方便。

4 霍夫曼解碼器在MP3解碼器中的應(yīng)用
---作為一種重要音頻數(shù)據(jù)的壓縮算法，mp3算法以其優(yōu)秀的壓縮能力和較高品質(zhì)的音質(zhì)獲得了較高的評(píng)價(jià)。在mp3的壓縮算法中，霍夫曼編碼的初始數(shù)據(jù)是DCT變換輸出的音頻頻率線經(jīng)過(guò)量化后的值。在mp3解碼的過(guò)程中，霍夫曼解碼器的作用是接受mp3比特流中的主數(shù)據(jù)，輸出576條初始頻率線。mp3的霍夫曼編碼分為三個(gè)區(qū)域：Big－values，Count1,Rzero。Big－values區(qū)包含著出現(xiàn)頻率最低的DCT系數(shù)，用最高的精確度來(lái)編碼，為了進(jìn)一步增強(qiáng)霍夫曼編碼的精確度，將Big－values區(qū)再劃分成三個(gè)區(qū)域，每個(gè)區(qū)域有32個(gè)碼表可供選擇；Count1區(qū)包含著出現(xiàn)頻率中等的DCT系數(shù)，這個(gè)區(qū)中每四個(gè)值編碼為一個(gè)碼字，一共有2個(gè)碼表供這個(gè)區(qū)域選擇；Rzero區(qū)包含的是出現(xiàn)頻率最高的頻率值，全部被編碼為0，不需要傳輸。在設(shè)計(jì)mp3解碼器的霍夫曼解碼器部分的時(shí)候，除了采用上述的平行結(jié)構(gòu)，還要考慮上述三個(gè)區(qū)的起始邊界，以及補(bǔ)零的問(wèn)題。霍夫曼碼字的三個(gè)區(qū)的起始邊界信息和碼表選擇信息可以在mp3比特流數(shù)據(jù)的幀頭和側(cè)信息中找到；在解完Big－values和Count1兩個(gè)區(qū)中的數(shù)據(jù)后，解碼器還應(yīng)該自動(dòng)補(bǔ)0，直到解出576個(gè)頻率值為止。MP3解碼器中的霍夫曼解碼器的狀態(tài)機(jī)設(shè)計(jì)如圖3所示。


5 結(jié)論
---我們以“ISO/IEC 11172-3”標(biāo)準(zhǔn)中的“霍夫曼碼表6”為例進(jìn)行驗(yàn)證最終仿真后輸出波形如圖4所示，“data_in”是數(shù)據(jù)輸入端，“code_x” 和“code_y”是最終輸出的碼字，“valid”是有效信號(hào)，當(dāng)“valid”為高電平時(shí)輸出碼字有效。
---通過(guò)實(shí)際地運(yùn)行，并行結(jié)構(gòu)的解碼器很好地達(dá)到了mp3解碼的要求。也可以方便的進(jìn)行修改以滿足各種應(yīng)用環(huán)境的解碼需求。另外經(jīng)過(guò)驗(yàn)證此設(shè)計(jì)是可綜合的，電路的關(guān)鍵路徑是Shifter -> Look-up Table -> Accumulator -> Shifter，如果想達(dá)到更高的時(shí)鐘頻率可以進(jìn)一步采用pipelining等結(jié)構(gòu)對(duì)此關(guān)鍵路徑進(jìn)行優(yōu)化。