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

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

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

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


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