2 霍夫曼编码算法 
---熵编码规定，任何给定的一系列数据，如果每个数据符号出现的概率已知的话，就可以采用更有效率的方式来编码。霍夫曼编码的基本思想就是：给出现概率越高的数据符号编成越短的码字，给出现概率越低的数据符号编成越长的码字。
---下面举一个具体的例子来说明霍夫曼编码是如何在无损压缩的前提下实现消除数据冗余的，详见“表1”中陈列的数据样本和编码。由表中可以看出，对于同样的信息源，霍夫曼编码有效地减小了数据冗余，使输出码字的平均码长最短，与信源熵值最接近，编码方法最佳。
---在应用霍夫曼编码的场合，在信息接收端需要霍夫曼解码器来回复初始码字。设计霍夫曼解码器的主要问题在于霍夫曼码的变长特性。

3 霍夫曼解码器的硬件结构研究
3.1比特串结构的霍夫曼解码器
---

最简单的霍夫曼解码器结构就是对输入的数据流按位进行解码，也就是比特串方式的解码器。采用Moore型状态机，可以很容易的设计出比特串方式的解码器。假设给定任何一组霍夫曼码，解码器的有限状态机可以通过如下方法建立：把每个结点（0或1）看作不同的状态，把下一时刻的输入看作向下一个状态跳转的条件。按照这样的做法，“表1”中的霍夫曼码的解码器的状态机可以构建如图1所示。
---虽然比特串方式的解码器有它的优点，设计难度小，消耗的硬件资源少，如图1此例中只需要3个触发器就可以了。但它的缺点也很明显：由于输入的码字长度的不同，解码所需要的时钟周期数也各不相同，这在解码过程中会引起比特率的不连续，从而需要额外的硬件来解决这个问题。另外，由于较长的解码时间也使比特串方式的霍夫曼解码器不适合应用在要求实时解码条件的系统中。
---此种结构的另一个问题是，当霍夫曼码树改变时不得不修改整个设计。一个更好选择就是采用并行结构的霍夫曼解码器来加快解码时间。

3.2并行结构的霍夫曼解码器
---

采用并行技术设计的解码器的优点就是解码可以在每个时钟周期内进行，不受码长的影响，硬件复杂度的提高换来了解码速度的加快。如图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”得到的值才是缓冲器中下一个未解码数据的位置。解码器重复以上过程，直到所有比特流中的数据全部解完。
---从上面的例子可以看出，不管码字的长短，各个码字解码所需要的时钟周期是相同的，而且解码的时间相对也比较短，比较适合要求实时解码的环境。而且当霍夫曼的码表改变的时候，只需要修改查找表中的数据就可以了，在通用性方面也比较方便。

4 霍夫曼解码器在MP3解码器中的应用
---

作为一种重要音频数据的压缩算法，mp3算法以其优秀的压缩能力和较高品质的音质获得了较高的评价。在mp3的压缩算法中，霍夫曼编码的初始数据是DCT变换输出的音频频率线经过量化后的值。在mp3解码的过程中，霍夫曼解码器的作用是接受mp3比特流中的主数据，输出576条初始频率线。mp3的霍夫曼编码分为三个区域：Big－values，Count1,Rzero。Big－values区包含着出现频率最低的DCT系数，用最高的精确度来编码，为了进一步增强霍夫曼编码的精确度，将Big－values区再划分成三个区域，每个区域有32个码表可供选择;Count1区包含着出现频率中等的DCT系数，这个区中每四个值编码为一个码字，一共有2个码表供这个区域选择;Rzero区包含的是出现频率最高的频率值，全部被编码为0，不需要传输。在设计mp3解码器的霍夫曼解码器部分的时候，除了采用上述的平行结构，还要考虑上述三个区的起始边界，以及补零的问题。霍夫曼码字的三个区的起始边界信息和码表选择信息可以在mp3比特流数据的帧头和侧信息中找到;在解完Big－values和Count1两个区中的数据后，解码器还应该自动补0，直到解出576个频率值为止。MP3解码器中的霍夫曼解码器的状态机设计如图3所示。


5 结论
---我们以“ISO/IEC 11172-3”标准中的“霍夫曼码表6”为例进行验证最终仿真后输出波形如图4所示，“data_in”是数据输入端，“code_x” 和“code_y”是最终输出的码字，“valid”是有效信号，当“valid”为高电平时输出码字有效。
---通过实际地运行，并行结构的解码器很好地达到了mp3解码的要求。也可以方便的进行修改以满足各种应用环境的解码需求。另外经过验证此设计是可综合的，电路的关键路径是Shifter -> Look-up Table -> Accumulator -> Shifter，如果想达到更高的时钟频率可以进一步采用pipelining等结构对此关键路径进行优化。

参考文献
1 李平著. 电子设计自动化快速入门教程. 北京, 高等教育出版社, 2003.7
2 精英科技著. 视频压缩与音频编码技术. 北京，中国电力出版社，2001.6
3 ISO/IEC 11172-3:1993，Information technology - Coding of moving pictures and associated audio for digital storage media at up to about 1.5Mbit/s,1993