霍夫曼解码器的设计及在MP3解码中的应用

　　1. 引言

　　---在多媒体数据的压缩中，一项广泛应用的编码技术就是熵编码。作为重要的熵编码，霍夫曼编码可以通过消除统计的冗余数据来达到无损压缩的目的。本论文主要讨论霍夫曼(HUFFMAN)解码的硬件实现方法及MP3解码中霍夫曼解码器的设计。

　　2 霍夫曼编码算法

　　---熵编码规定，任何给定的一系列数据，如果每个数据符号出现的概率已知的话，就可以采用更有效率的方式来编码。霍夫曼编码的基本思想就是：给出现概率越高的数据符号编成越短的码字，给出现概率越低的数据符号编成越长的码字。

　　---下面举一个具体的例子来说明霍夫曼编码是如何在无损压缩的前提下实现消除数据冗余的，详见“表1”中陈列的数据样本和编码。由表中可以看出，对于同样的信息源，霍夫曼编码有效地减小了数据冗余，使输出码字的平均码长最短，与信源熵值最接近，编码方法最佳。

　　---在应用霍夫曼编码的场合，在信息接收端需要霍夫曼解码器来回复初始码字。设计霍夫曼解码器的主要问题在于霍夫曼码的变长特性。

　　3 霍夫曼解码器的硬件结构研究

　　3.1比特串结构的霍夫曼解码器

　　---最简单的霍夫曼解码器结构就是对输入的数据流按位进行解码，也就是比特串方式的解码器。采用Moore型状态机，可以很容易的设计出比特串方式的解码器。假设给定任何一组霍夫曼码，解码器的有限状态机可以通过如下方法建立：把每个结点(0或1)看作不同的状态，把下一时刻的输入看作向下一个状态跳转的条件。按照这样的做法，“表1”中的霍夫曼码的解码器的状态机可以构建如图1所示。

　　---虽然比特串方式的解码器有它的优点，设计难度小，消耗的硬件资源少，如图1此例中只需要3个触发器就可以了。但它的缺点也很明显：由于输入的码字长度的不同，解码所需要的时钟周期数也各不相同，这在解码过程中会引起比特率的不连续，从而需要额外的硬件来解决这个问题。另外，由于较长的解码时间也使比特串方式的霍夫曼解码器不适合应用在要求实时解码条件的系统中。

　　---此种结构的另一个问题是，当霍夫曼码树改变时不得不修改整个设计。一个更好选择就是采用并行结构的霍夫曼解码器来加快解码时间。

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

　　---采用并行技术设计的解码器的优点就是解码可以在每个时钟周期内进行，不受码长的影响，硬件复杂度的提高换来了解码速度的加快。如图2采用并行技术设计的解码器的基本思想就是，采用查找表(LUT)把霍夫曼码字保存起来，通过把待解码字与查找表中码字的比较匹配，来实现解码的目的。这种结构比特流输入到解码器的长度是固定的，比如说8位。8位的数据输入长度有可能包含多于一个码字的数据，这样需要一个缓冲器来保存输入数据流。缓冲器可以用桶型移位寄存器来实现，应用缓冲器的另外一个目的就是能保证在一个码字解完以后，可以移位到正确的位置。缓冲器中的码字解完以后，开始从比特流中接收新的码字，重复上面的过程，因此，解完缓冲器中的可能码字需要多于一个时钟周期的时间。此外，为了使查找表中的数据