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

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

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

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


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