嵌入式MP3解码器中Huffman算法的硬件加速

嵌入式MP3解码器中Huffman算法的硬件加速

摘要Huffman解码是MP3解码流程中的一个重要部分，其运算量在整个流程中占有相当比重，其算法实现的优劣直接关系到MP3的实时解码。传统的Huffman解码多采用软件实现，从而增大了CPU的负担。本文介绍一种Huffman解码的硬件加速方案，并对Huffman码表进行了改进，而MP3解码器已在Altera的FPGA上进行验证，结果表明在实时解码的前提下，节约了CPU资源，并可显着降低CPU的工作频率。关键字MP3；Huffman编码；硬件加速；实时解码

1引言Huffman编码是一种无损的、可变长熵编码，其理论依据是使各个符号的概率均匀化，即出现概率大的符号编成短码，出现概率小的编成长码。在MPEG1_III中，根据音频数据的统计特性建有34张码表，为了实现最优的编码，编码器会根据当前处理的数据类型来选择码表进行编码。由于是对频域量化值进行编码，一般大值主要集中在低频部分，而零值则集中于高频部分，所以各个频段可以灵活选择编码效率更高的Huffman表。按照MPEG1_III标准，从零到Nyquist采样频率范围上的量化值被分成bigvalue，count1，zero三个区域，对于bigvalue区和count1区采用不同的编码方案。为提高编码效率，在bigvalue区每两个绝对量化值转换为一个Huffman码字；count1区4个绝对量化值转换为一个Huffman字；zero区的量化值全为零，从而不需编码和传输。另外为了进一步提高bigvalue区的编码效率，将其细分为region0，region1，region2三个区域，允许每个区域选择不同的码表。

2Huffman解码算法分析经过分析，Huffman硬件加速实现的难点在于Huffman码表的设计，码表效率的高低直接决定了Huffman硬件解码的速度。本设计采用分步查表法进行Huffman解码，其主要思路是在码表中加入索引来指明下一次查表的码表位置，这样查表工作就被分为若干次完成，每次读入固定的比特数，如命中则输出解码值，否则根据当前位置的索引值去码表中进行下一步搜索，图1为所示步骤。这样，只需增加少量存储码表空间就可以实现快速查找，一次读入的比特数越多查找速度就越快。在对查表速度和存储空间进行权衡后，对于MPEG1_III协议中的表1，表2及表3采用3bit的搜索步长，其它表采用4bit；同时也改进协议中的Huffman码表以适应分步查表法。Huffman码表的每一项都由码字和码表构成，且码表中的每一项都按照输入码字的顺序进行排列。下面以count1区的tableA为例加以说明。图1分步查表法图2为MPEG1_III协议中的tableA，图3为根据分步查表法特点，将协议中的tableA调整后的新码表。当输入的码字为0100时，它在码表中对应的位置为地址0100。这样排列可以很方便地根据输入的码字进行地址映射，减少了计算映射的逻辑单元。如果一次查表未能命中，则根据码表中给出的跳转地址进行二次查表。调整后的新码表比原先有所增大，其目的是当输入固定比特长度的码字都可以在表中直接查找到，而不需额外的计算。在查表得到解码

结果的同时也可读出码长，这样也节省了额外的计算单元。图2MPEG1_III协议中的tableA图3tableA调整后的新码表

3Huffman解码器的硬件实现整个MP3解码系统采用Altera公司的FPGA实现，其中的Huffman解码器的硬件结构如图4所示。Huffman解码模块与CPU之间的数据传输通过Wishbone总线进行。在解码的时候CPU取出码字以及相应的码表号传给Huffman硬件加速器，在完成解码后将解码值以及码长传送给CPU。Huffman码表存储在ROM中，Huffman解码的过程也就是在计算ROM的地址。经过对码表的统计，在bigvalue区，总的码表长度位2147，最大的x，y值都为15。在count1区，总的码表长度为44，解码值为0或1。在所有码表中，最大的码长为19bits，所以ROM的位宽为13bits，深度为2191。ROM的地址由基址和偏移地址两部分构成。基址对应的是每个码表在ROM中的起始地址，被固化在解码器内的基址寄存器中，可以根据码流中指明的码表序号进行输出。偏移地址是根据实际输入的码字计算得到的解码值在每个码表中的相对地址，由于Huffman码表是根据码字进行排列的，所以偏移地址只要通过输入的码字进行简单计算就可以得到。最后，将基址和偏移地址相加就得到了实际解码值在ROM中所对应的地址。本设计对分步查表法进行了优化，多次查表要多次读取ROM而影响了速度，所以将多次查表在计算偏移地址的时候实现。偏移地址计算单元可根据输入的码字和码表进行计算，首先读入4bit的码字，如果一次命中则输出偏移地址，否则将下面的若干比特输入控制码字寄存器，具体的比特数要根据选用的码表来决定，这样在查找若干次后就可以得到查表所需要的偏移地址。协议中规定的最长的Huffman码字为19bit，因此最多只需进行5次迭代，与软件实现所消耗的时钟周期相比，有很大改进。图4Huffman解码器的硬件结构4结束语本文所提出的Huffman解码的硬件加速方案，采用分步查表的方法，不仅可以做到MP3的实时解码，而且经过实际验证，与Huffman解码的软件实现相比，减少了CPU的运算量，CPU的主频可由原来的18M降至13M左右。本设计思想为相关领域的Huffman解码电路提供了更有效的解决方法。

参考文献[1]HashemianR.DirectHuffmancodinganddecodingusingthetableofcode-lengthsInformationTechnology：CodingandComputing[ComputerandCommunications]，2003WatkinsonJohn，TheMPE