一种基于Huffman解码的方法和装置

摘要

本发明公开了一种基于Huffman解码的方法和装置，该装置包括数据缓存器，一个或多个层解码器，判定器以及码表查找单元，其中，数据缓存器用于接收外部输入的数据流以准备待解码数据，同时接收所述判定器输出的偏置量SD以准备下一次的待解码数据；一个或多个层解码器LD1～LDn，用于分别接收待解码数据的各层码字，同时根据配置表对每层码字进行解码，从而计算得出各层的偏移量offset1～offsetn；判定器，用于接收各层解码器输出的偏移量，并进行优先级判断，选择层数最低并且输出为合理值的偏移量作为最终偏移量offset，同时将偏置量SD设置为该层数；码表查找单元，用于接收最终偏移量offset，并对码表进行查找，获取该最终偏移量对应位置的数据，该数据即为解码后的数据。

说明书

技术领域

本发明涉及图形图像处理和数据压缩的技术领域，具体涉及一种改进的基于Huffman解码的方法和装置。

背景技术

随着图像相关应用越来越多的应用，图像在计算机处理中占比越来越高，而由于图像本身就具有数据量大和运算量大的特点，尤其是当前虚拟现实，深度学习技术的越来越多的使用，图像和类图像数据的传输本身就成为了计算瓶颈，所以压缩算法在这个过程中就显得尤为重要。

而根据香农定理，Huffman编码在无损编码中，能够接近理论上的压缩极限，在数据处理的硬件系统中，加入Huffman编码就成为了能够减少数据传输量，降低带宽压力的一个普遍的选择。但是传统的Huffman编解码在硬件实现过程中，由于需要对每个编码后的数值进行比较，要么整个比较的数目过大，难以进行硬件实现，要么采用少量的运算单元但是会造成硬件逻辑过于复杂，硬件的总体性能低下。

发明内容

鉴于上述问题，本发明提供了一种克服上述问题或者至少部分地解决上述问题的一种基于Huffman解码的方法和装置。

为了解决上述问题，本发明实施例还提供了一种基于Huffman编解码的装置，包括：该装置包括数据缓存器，一个或多个层解码器，判定器以及码表查找单元。

其中，所述数据缓存器，用于接收外部输入的数据流以准备待解码数据，同时接收所述判定器输出的偏置量SD以准备下一次的待解码数据；

所述一个或多个层解码器LD1～LDn，用于分别接收待解码数据的各层码字，同时根据配置表对每层码字进行解码，从而计算得出各层的偏移量offset1～offsetn，其中，每层表示每个不同的码字长度；

所述判定器，用于接收各层解码器输出的偏移量offset1～offsetn，并进行优先级判断，选择层数最低并且输出为合理值的偏移量作为最终偏移量offset输出至所述码表查表单元，同时将偏置量SD设置为该层数。

所述码表查找单元，用于接收最终偏移量offset，并对码表进行查找，获取该最终偏移量对应位置的数据，该数据即为解码后的数据。

本发明实施例还提供了一种基于Huffman解码的方法，该方法包括如下步骤：

(1)接收外部输入的待解码数据；

(2)分别接收待解码数据的各层码字，同时根据配置表对每层码字进行解码，从而计算得出各层的偏移量offset1～offsetn，其中，每层表示每个不同的码字长度；

(3)接收各层的偏移量offset1～offsetn，并进行优先级判断，选择层数最低并且输出为合理值的偏移量作为最终偏移量offset，同时将偏置量SD设置为所述层数进行反馈；

(4)接收所述最终偏移量offset，并对码表进行查找，获取所述最终偏移量offset对应位置的数据，该数据即为解码后的数据；

(5)根据所述偏置量SD准备下一次的待解码数据，直至数据流全部解码完 成。

本发明中的一种基于Huffman编解码的方法和装置主要被应用于ASIC设计领域，与现有技术相比，本发明包括以下优点：

本发明通过采用一个或多个层解码器LD1～LDn对每层码字同时进行并行解码，再结合优先级判断，能够低成本、低功耗、高效率的实现对解码的加速。

本发明通过设置不同的配置表方式，极大的减少了运算过程，能够进一步提升性能。

本发明通过在优先级判断完成后直接进行偏置量SD的反馈，可以将解码过程提前一个硬件时钟周期，进一步提高了整个系统的运行速度。

本发明所采用的基于Huffman编解码的方法和装置在提高解码效率的同时，更加适合硬件的实现，能够取得成本低、并行度高以及计算速度快的有益技术效果。

附图说明

图1是本发明实施例中一建立好的正则Huffman树的示意图；

图2是本发明实施例的一种基于Huffman解码的装置示意图；

图3是根据本发明实施例的一种基于Huffman解码的方法的流程图。

具体实施方式

为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。

参照图1，为本发明实施例中一建立好的正则Huffman树的示意图。正则Huffman树在某一个层级上生成的编码完全是连续的，而任何一个普通的Huffman树，都可以直接转换成为正则Huffman树，仅仅改变每个数据的码字， 而码字的长度不会改变，也不会影响最终的压缩率。基于该Huffman树可以生成每个数据的码字和存储位置信息，参见表1。其中，码字为二进制数字。

表1每个数据的码字和存储位置信息

码字位置Z数据00f1001c1012e1103d11104a11115b

由此可见，通过偏移量offset即可找到数据的存储位置Z，进而找到对应的数据，如上表所示，Z[0]＝f，Z[4]＝a。

而实际上，位置的确定是根据层数(即码字长度)递增的原则和码字本身的大小，由小到大进行排序。因此，在实际使用过程中，码表只需顺序存储数据，也就是说，码字、位置信息与数据之间的对应关系被隐含在该码表中，此时，位置信息即为码表的偏移量offset，通过该偏移量offset可以直接查找码表进而获取解码数据。

由表1可以看出，图1所示的正则Huffman树根据层数(即码字长度)可以被分为三组：

第一组G1：0(a)

第二组G2：0b100(c)，0b101(e)，0b110(d)

第三组G3：0b1110(a)，0b1111(b)

根据该组码字代表的具体数值，每一组都包括一最小值min[G]和一最大值max[G]，同时，使用每一组的最小值和其码字所在的存储位置可以得到每一组 中的偏移参数C[G]，具体计算过程如下：

如第一组的最小值为0，数据的存储位置为0，则偏移参数C[1]为：

C[1]＝0-0＝0

第二组的最小值为4，数据存储位置从1开始，则偏移参数C[2]为：

C[2]＝1-4＝-3

上述过程可以直接得到一用于计算位置Z的配置表，如表2所示。

表2配置表

码字长度组(G)最小值(min)最大值(max)偏移参数(C)110003246-3431415-10

在表2所示的配置表中，码字长度与组G是为了更好的对解码过程进行说明，而在实际使用过程中，配置表只需要存储最小值min，最大值max和偏移参数C。

上述码表与配置表的设置方式，都在缩减存储量的同时，进一步简化了索引过程，降低了硬件成本。

上述配置表的设置使得本发明的基于Huffman的解码已经在很大程度上实现了对硬件的友好，但在硬件设计中，存储变量相对还是比较消耗资源的，而与或非这种位级别的操作消耗比变量的存储以及比较、加减等运算单元要节省硬件逻辑资源，而且运算速度也要快很多。

因此，为了使解码过程中使用的硬件资源更小，在实现更低功耗的同时，进一步提高运行频率，作为一优选实施例，本发明在配置表中进一步地引入了一计算掩码M，在每个层解码器中，掩码M是根据最小值min和最大值max中变 化的bit来决定的，如图1所示的正则Huffman数的第二层，最高位始终为1，其生成的码字实质上变化的仅为后两位，即0b00～0b10，那么对应的掩码就是0b11，也就是3。而最大值max和最小值min也会根据掩码M做对应的调整，改进后的配置表如表3所示。

表3改进后的配置表

其中，由于图1所示的正则Huffman树未包含码字长度为2的数据，因此表3中的x表示该组不运算。

通过该配置表即可完成Huffman的解码。各组解码同时进行，而当有一组比较成功后，之后的比较结果就可以不再被使用。

参照图2，为本发明实施例的一种基于Huffman解码的装置的示意图，该装置包括数据缓存器，一个或多个层解码器，判定器以及码表查找单元。

其中，数据缓存器，用于接收外部输入的数据流以准备待解码数据，同时还用于接收判定器输出的偏置量SD以准备下一次的待解码数据。

一个或多个层解码器，用于分别接收待解码数据的各层码字，同时根据配置表对每层码字进行解码，从而计算得出各层的偏移量offset1～offsetn。其中，每层表示每个不同的码字长度。

更进一步的，每一个层解码器LD1～LDn仅接收一种码字长度并对其进行解码。而层解码器的总个数由待解码数据的最长的码字长度来决定，并且可以根 据需要在设计中进行扩展。此处，为了便于说明，每个层解码器的序号n表示该层解码器LDn能够接收的码字长度。

判定器，用于接收各层解码器输出的偏移量offset1～offsetn，并进行优先级判断，选择层数最低并且输出为合理值的偏移量作为最终偏移量offset输出至码表查表单元，同时将偏置量SD设置为该层数。

码表查找单元，用于接收最终偏移量offset，并对码表进行查找，获取该最终偏移量对应位置的数据，该数据即为解码后的数据。

作为一优选实施例，可以选取表2的配置表进行解码，此时当单个层解码器LDn的输入值为X时，比较X是否落在该层的最小值min和最大值max之间，如果落在其中，则以X加该层的偏移参数C作为该层解码器LDn的输出值offsetn，否则输出一特定标记。

作为另一优选实施例，还可以选取表3中包含掩码M的配置表进行解码，此时当单个层解码器LDn的输入值为X时，首先输入值X与掩码M进行与(&)操作，得到一中间值X1，比较X1是否落在该层的最小值min和最大值max之间，如果落在其中，则以X1加该层的偏移参数C作为该层解码器LDn的输出值offsetn，否则输出一特定标记。

下面将以数据流为0b1000100，数据缓存器准备的待解码数据的最大长度为4，选取表3配置表为例，对该装置的解码过程作进一步的解释说明。

根据最大长度需设计四个层解码器LD1，LD2，LD3和LD4。数据缓存器每次均准备4位数据，其第一次准备的数据为0b1000。

各层解码器LD1，LD2，LD3和LD4分别接收数据缓存器输出的各层码字，即首位数据“1”输入层解码器LD1，前两位数据“10”输入层解码器LD2，前 三位数据“100”输入层解码器LD3，四位数据“1000”输入层解码器LD4。

假定配置表仍为表3所示，首先各层解码器将其输入与该层解码器的掩码M分别进行与(&)操作，每层的层解码器操作如下：

LD1：M&0b1＝1&0b1＝1，

LD2：M&0b10＝0&0b10＝0，

LD3：M&0b100＝3&0b100＝0，

LD4：M&0b1000＝1&0b1000＝0，

通过表3所示的配置表可知，层解码器LD1和LD2的操作结果均未落在其最大值max和最小值min的区间内，因此层解码器LD1和LD2的输出为NULL(其中，NULL可以为任意一个可以被判断为不合理的值)；而层解码器LD3和LD4的操作结果均落在了其最大值max和最小值min区间内，因此层解码器LD3的输出值offset3＝0+C＝1，层解码器LD4的输出值offset4＝0+C＝5。

判定器接收各层解码器LD1，LD2，LD3和LD4输出的偏移量offset1～offset4，选择层数最低并且输出为合理值的层解码器LD3的输出值1作为最终偏移量offset输出至码表查表单元，同时将偏置量SD设置为层数3。

码表查找单元对码表进行查找，获取解码后的数据为c，即最终偏移量offset对应位置的数据。

至此，完成了第一次解码过程。然后数据缓存器接收偏置量SD，其中SD值为3，将其中待解码数据的前三位移出，并进一步从数据流中补充三位数据以作为下一次待解码数据。

最终得到数据流0b1000100解码后数据为cfc。

由上述过程还可以看出，判定器在得到结果后会直接将偏置量SD反馈回数 据缓存器，这样比在获取最终结果时才生成偏置量要提前一个硬件时钟(cycle)以进行运算，进一步提高了整个系统的运行速度。

参照图3，为根据本发明实施例的改进哈夫曼解码方法的流程图。

(1)接收外部输入的待解码数据。

(2)分别接收待解码数据的各层码字，同时根据配置表对每层码字进行解码，从而计算得出各层的偏移量offset1～offsetn。其中，每层表示每个不同的码字长度。

(3)接收各层的偏移量offset1～offsetn，并进行优先级判断，选择层数最低并且输出为合理值的偏移量作为最终偏移量offset，同时将偏置量SD设置为该层数进行反馈。

(4)接收最终偏移量offset，并对码表进行查找，获取该最终偏移量对应位置的数据，该数据即为解码后的数据。

(5)根据偏置量SD准备下一次的待解码数据，直至数据流全部解码完成。

作为一优选实施例，可以选取表2的配置表进行解码，此时当所述码字为X时，比较X是否落在该层的最小值min和最大值max之间，如果落在其中，则以X加该层的偏移参数C作为该层的偏移量offsetn输出，否则输出一特定标记。

作为另一优选实施例，还可以选取表3中包含掩码M的配置表进行解码，此时当所述码字为X时，首先输入值X与掩码M进行与(&)操作，得到一中间值X1，比较X1是否落在该层的最小值min和最大值max之间，如果落在其中，则以X1加该层的偏移参数C作为该层的偏移量offsetn输出，否则输出一特定标记。

此外，作为另一优选实施例，在步骤(3)中，所述优先级判断完成后，直接将偏置量SD反馈以准备下一次的待解码数据，这样进一步提高了整个系统的运行速度。

以上对本发明所提供的一种可扩展智能图像处理加速装置和加速方法进行了详细介绍，上述记载中应用了具体示例对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本发明的限制，本领域技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。