2.1 Huffman解码的实现
Huffman解码是解码过程中重要的一环。传统的哈夫曼解码需要逐位查找哈夫曼表,进行比较判断,由于查找过程需要大量的移位及循环。这样的解码效率非常低。针对这种情况,充分考虑到ATmegal28的存储容量的限制,在读文件头时,软件事先构造出不同码长下的哈夫曼码字的最小值表和最大值表如表1所示,最小值在哈夫曼表中的索引以及哈夫曼树各叶子结点对应的编码表。
在解码的时候,读取1串二进制数据,分别与各码长下的最大值和最小值进行比较,如果在哈夫曼表中没有该码长的码字,说明该比特数据不是完整的Huff_man编码,接着读取下一个比特数据加在前面的比特数据组成的新的码字,然后再在最小值表和最大值表中进行查找,直至找到确切的码字。最后把该码字减去同一码长下最小值,加上此最小值在哈夫曼表中的索引即可得到该码字在编码表中的位置。
2.2 IDCT变换的实现
将8×8块中的颜色分量单元的64个值逐一乘以对应的量化表内位置相同的系数,然后再将64个数据进行Z字型的重新排列,进行IDCT变换。IDCT的运算量很大,其中要进行大量的浮点乘法和加法运算,因而在解码过程中IDCT所占时间最多。采用行列分解法先将二维IDCT分解成一维8点的IDCT,对于一维8点IDCT采用Loeffler的快速算法。图2为Loef—fler算法的流程图,Loeffler算法运算因子的解释如图3 所示。
直接对旋转因子进行计算需要4次乘法和2次加法,这样1次8个点的一维IDCT变换总共需要14次乘法和26次加法。可以对旋转因子进行变形如式(1)所示:
从而1次旋转因子计算只需要3次乘和3次加。进而进行1次一维IDCT只需11次乘和29次加。因为乘法运算的代价高于加法运算,所以这种变形是有益的。完成一次二维的IDCT运算总共要进行16次的8点一维IDCT运算。由于ATmegal28在速度方面的限制,在IDCT运算过程中把浮点操作改进为整形运算,并且把的值扩大211倍存储起来,为IDCT运算做准备。