霍夫曼解碼器的設計及在MP3解碼中的應用

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

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

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

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


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