一种快速霍夫曼解码算法和其软硬件实现.pdf

维普资讯 第4l卷 第 2期 复 旦 学 报 (自然科学版) Vo1．41No．2 2002年 4月 Journal0fFudanUniversity(NaturalScience) Apr．2002 文章编号 ：0427—7104{2002)020165(15 一 种快速霍夫曼解码算法及其软硬件实现 董培良．俞 日龙，廖天康，俞承芳，刘 峰，洪志 良 (矍 =I(学 电了工程系 ，上海 200433) 摘 要 ：由于霍夫曼算法产生的码字长度不固定 ．使得霍夫曼解码过程 的效率较低 ．为克服这一缺点，提 出了一 种新的懈码算法 ，使 占码流 中大部分的短码字能迅速解码 ．从而提高整体的运行效率 该算法分别在软件 (TI公 司的TMS320C54x系列 DSP的i[编程序)和硬件(jPEG 图像解压电路 中的霍夫曼解码模块)上实现 ．通过鬻试 表明，在增加 了为数不多的资源情况lF．此解码算法此传统方法太大提高了执行效率． 关t词 ：霍走曼编码 {解码 ；数字信号处理器；JPEG 中圈分类号：TN91121 文献标识码 ：A 霍夫曼编码”是一种基于概率统计的无损压缩技术，其算法简单 ，具有非常接近理论极限的压缩比， 一 直被广泛地应用于各种压缩场台 一 过去对霍夫曼算法改进和扩展的研究主要都集 中在编码的策略 上 ；现在，随着一些应用场合 中对解码速度的要求越来越高．解码策略的研究也逐渐引起 了人们的注意 霍夫曼算法是变长编码．压缩后产生的码字长度不固定 传统的解码方法必须逐位读人码流，先判断码 字长度，再进行解码，效率相对较低．本文提出了一种新的解码算法 ．能一次性读人多位码流，使绝大部分码 字一次性地读人并立即解码 ；即使是不能立即完成解码的码字，也比传统方式要节约大量的判断时间． 1 关于解码算法 的研究 对于一个有 m 个符号的压缩对象，其解码所需 的时间代价 西 ：∑C．， 1 其中C。是第 i个符号在解码时所花的时间代价．对于软件解码的情况 ，G 指对此符号解码所需的指令周 期时间；对于硬件解码的情况 ，C．指对此符号解码所需 的时钟周期数 常见的解码算法 有一个共同点．即必须一位一位地读入码流 ，读人后需进行一系列的判断，以决 定是输出一个符号 ，还是继续读人下一位码流．其时间代价 Cost1=∑(Cbt+C0)= ( +c0)， I= 【 其中C 表示读人每一位后进行判断的时间代价； 表示第 i个码宇的长度 (比特数)；C。是修正量，表示 读人码字的最后一位时，系筑输 出解码结果所需的时问代价 ：T是所有码字的平均码长． 与编码过程 (不考虑码表的产生过程)相比，解码过程要复杂得多，所需时间也多 其原 因在于上式 中 项太大 要提高解码效率，必颁将此项变小 ，甚至消去． 本文提 出的快速算法，目标就是希望能将解码过程变得象编码一样 ，可以一次性地读人若干位码流 ， 立即确定位于最前面一个码字的码长，并对其进行解码 设每次从码流中读出最前面的N 位数据 只要最前面的那个码字长度不大于 N ，则此次读人 的数据 就足够对该码字进行解码 为了能一次性得到解码结果，就需要建立一组查找表．该查找表的长度为2 ，其 收稿 日期 ：2001．04—26 作者简介 ：董培照 t‘976一)．男，硕士研究生 ；通讯联系人俞承芳教授 维普资讯 166 复 旦 学 报 (自然科学版) 第 41卷