一种JPEG霍夫曼解码电路及其解码方法

摘要

本发明公开一种JPEG霍夫曼解码电路及其解码方法，在JPEG文件头霍夫曼标记解码阶段，包括如下步骤：步骤1.根据不同长度下的霍夫曼码字个数建立霍夫曼最小码字表，所述最小码字表中16个码字的位宽分别为1位，2位，3位，4位，5位，6位，7位，8位，8位，8位，8位，8位，8位，8位，8位，8位；步骤2.根据不同长度下的霍夫曼码字个数建立霍夫曼最小码字地址表；步骤3.根据16个并行的小于比较器的比较结果，计算出当前霍夫曼码字的长度，并根据最小码字地址表得到游程编码值并计算出解码数据，其中16个小于比较器的位宽分别是1位，2位，3位，4位，5位，6位，7位，8位，8位，8位，8位，8位，8位，8位，8位，8位。

说明书

技术领域

本发明涉及一种JPEG霍夫曼解码电路及其解码方法。

背景技术

霍夫曼编码是一种常用的基于概率统计的无损压缩技术，它用较长的 比特对出现概率较高的码字进行编码，用较短的比特对出现概率较低的码 字进行编码，从而达到了非常接近理论极限的压缩比。

传统的霍夫曼解码通常是通过逐位比较来实现，该方法首先需要根据编 码信息重构出用于解码的霍夫曼码表，该码表需要占用较大的存储空间， JPEG标准中示例的典型码表长度约为4Kbit。其次，采用逐位比较的方法 通常需要多个时钟周期来解码一个码字，这种方法大大限制了解码速率。

与本发明最接近的现有技术为公开号CN 101017574A的专利申请，该专 利公开了一种适于JPEG码流的霍夫曼解码方法，该方法根据JPEG码流中 的码字个数建立最小码字表和最小码字地址表，然后在霍夫曼解码阶段将 输入码流与最小码字表进行并行比较，得到码字长度之后再根据最小码字 地址表解码出当前霍夫曼码字的地址，最后得到对应的霍夫曼码字。

但是由于JPEG码流中霍夫曼码字长度最长为16位，上述方法中的最小 码字表位宽为16位，另外输入码流与最小码字表进行比较时，需要用16 个长度分别为1，2，3，...，15，16的比较器才能解码出当前码字长度， 这就会造成解码速度降低，同时增加芯片的硬件成本。

在专用集成电路设计中，解码速度和芯片成本都是设计者必须考虑的 重要因素，应该采用高速低成本的霍夫曼解码算法来降低硬件资源的消耗。

发明内容

由于现有技术存在上述问题，本发明提出一种JPEG霍夫曼解码电路及 其解码方法，其可有效解决现有技术存在的问题。

为了实现上述目的，本发明提供一种JPEG霍夫曼解码方法，在JPEG 文件头霍夫曼标记解码阶段，包括如下步骤：

步骤1.根据不同长度下的霍夫曼码字个数建立霍夫曼最小码字表，所 述最小码字表中16个码字的位宽分别为1位，2位，3位，4位，5位，6 位，7位，8位，8位，8位，8位，8位，8位，8位，8位，8位；

步骤2.根据不同长度下的霍夫曼码字个数建立霍夫曼最小码字地址 表；

步骤3.根据16个并行的小于比较器的比较结果，计算出当前霍夫曼 码字的长度，并根据最小码字地址表得到游程编码值并计算出解码数据， 其中16个小于比较器的位宽分别是1位，2位，3位，4位，5位，6位，7 位，8位，8位，8位，8位，8位，8位，8位，8位，8位。

进一步地，步骤1包括如下步骤：

步骤1A，从长度为1的最小码字开始，如果当前长度下对应的码字个数 为0，则该长度下的最小码字值等于0，如果下一个长度下对应的码字个数 为0则重复执行过程1A，如果下一个长度下对应的码字个数不为0则执行 步骤1B；

步骤1B，通过以下公式计算出当前长度下对应的最小码字值：

其中，MinCode(i)是当前长度为i时的最小码字值，Num(i)是长度为i 的码字个数；

如果从下一个长度开始到长度为16所对应的码字个数全部为0则执行 1C，否则重复执行过程1B。

步骤1C，从当前长度开始到长度为16的最小码字全部等于255，即8 位全1。

进一步地，步骤2通过以下公式计算不同长度下的霍夫曼最小码字地 址表

其中，MinAddr(i)是长度为i时的霍夫曼最小码字地址表，Num(i)是长 度为i的码字个数。

进一步地，步骤3包括如下步骤：

步骤3A，在前8个小于比较器中，有效输入码流为前n位数据，将有效 输入码流值与当前长度为n时的最小码字值进行比较，如果有效输入码流 前值小于当前长度为n时的最小码字值，则比较器输出结果为0，否则比较 器输出结果为1，其中1≤n≤8；

步骤3B，在后8个小于比较器中，首先根据输入码流判断出该码字是 否可能为长码字，即码字长度是否大于8，如果当前输入码字肯定不是长码 字，比较器输出结果直接为0；如果可能是长码字，，有效输入码流为舍弃 前n-8位之后接下来的8位数据，然后将8位有效输入码流值与当前长度 为n时的8位最小码字值进行比较，如果8位有效输入码流值小于当前长 度为n时的8位最小码字值，则比较器输出结果为0，否则比较器输出结果 为1，其中9≤n≤16；

步骤3C，通过以下公式将所有比较结果相加得到最终的码字长度 CodeLen：

$\mathrm{CodeLen}=\underset{n=1}{\overset{16}{\Sigma }}\mathrm{Comp}\left(n\right)$1≤n≤16，其中Comp(n)为比较器输出结果；

步骤3D，根据当前解码出的码字长度通过以下公式计算得到该长度下 的最小码字地址min_adress：min_adress＝MinAddr(CodeLen)，其中 是长度为CodeLen的霍夫曼最小码字地址，

根据当前解码出的码字长度通过以下公式计算得到该长度下的最小码 字值min_code_value＝MinCode(CodeLen)，其中 MinCode(CodeLen)是长度为CodeLen的最小码字值；

根据有效输入码流、最小码字值以及最小码字地址通过以下公式计算 出当前码字在霍夫曼码表中的地址值symbol_adress：

symbol_adress＝ValidData(CodeLen)+min_code_value-min_address，其中 长度为CodeLen的有效输入码流；

最后根据symbol_adress查找霍夫曼码字表就可以得到当前码字对应的 游程编码值。

其中，步骤3B中判断是否可能为长码字包括如下步骤：如果输入码流 的最高位为1，则该输入码流可能是长度为9的长码字，如果输入码流的最 高2位全为1，则该输入码流可能是长度为10的长码字，以此类推，如果 输入码流的最高8位全为1，则该输入码流可能是长度为16的长码字。

同时，本发明还公开了一种JPEG霍夫曼解码电路，包括根据不同长度 下的霍夫曼码字个数建立霍夫曼最小码字表的最小码字表模块；根据不同 长度下的霍夫曼码字个数建立霍夫曼最小码字地址表的最小码字地址表模 块；存储霍夫曼码字表的霍夫曼码字表模块；包含多个比较器的比较器阵 列模块；其中比较器阵列模块中各比较器的输入端与有效输入码流和当前 最小码字值相连，输出端分别与第一加法器的输入端相连；移位寄存器的 输入端分别与输入码流及第一加法器输出端相连，输出端与第二加法器的 输入端相连；最小码字表模块的输入端与第一加法器的输出端相连，输出 端与减法器的输入端相连；最小码字地址表模块的输入端与第一加法器的 输出端相连，输出端与减法器的输入端相连；减法器的输出端与第二加法 器的输入端相连；第二加法器的输出端与霍夫曼码字表模块相连。

进一步地，比较器阵列模块还包括8个与门，8个与门的输入端依次分 别与第九至第十六比较器的输出端及当前有效输入码流是否可能为长度9 至16的长码字相连，输出端与第一加法器的输入端相连，其中当前有效输 入码流如果为1表示可能为长码字，如果为0表示不可能为长码字。

现有技术所提供的JPEG霍夫曼解码方法需要位宽分别为1位，2位，3 位，4位，5位，6位，7位，8位，9位，10位，11位，12位，13位，14 位，15位，16位的霍夫曼最小码字表和16个位宽分别为1位，2位，3位， 4位，5位，6位，7位，8位，9位，10位，11位，12位，13位，14位， 15位，16位的数据比较器才能对当前霍夫曼码字进行解码，而本发明所提 供的JPEG霍夫曼解码电路及其解码方法只需要位宽分别为1位，2位，3 位，4位，5位，6位，7位，8位，8位，8位，8位，8位，8位，8位，8 位，8位的霍夫曼最小码字表和16个位宽分别为1位，2位，3位，4位， 5位，6位，7位，8位，8位，8位，8位，8位，8位，8位，8位，8位 的数据比较器就能对当前霍夫曼码字进行解码，这样可以大量节省最小码 字表寄存器资源和比较器资源，在高速解码的同时有效地降低了硬件资源 的消耗。

附图说明

图1是本发明JPEG霍夫曼解码的电路图；

图2是本发明最小码字表计算流程图；

图3是本发明最小码字地址表计算流程图；

图4是本发明码字长度计算示意图。

具体实施方式

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

如图1所示，本发明公开了一种JPEG霍夫曼解码电路。该电路包括根 据不同长度下的霍夫曼码字个数建立霍夫曼最小码字表的最小码字表模 块；根据不同长度下的霍夫曼码字个数建立霍夫曼最小码字地址表的最小 码字地址表模块；存储霍夫曼码字表的霍夫曼码字表模块；包含多个比较 器的比较器阵列模块。

其中，比较器阵列模块中各比较器的输入端与有效输入码流和当前最 小码字值相连，输出端分别与第一加法器的输入端相连；移位寄存器的输 入端分别与输入码流及第一加法器输出端相连，输出端与第二加法器的输 入端相连；最小码字表模块的输入端与第一加法器的输出端相连，输出端 与减法器的输入端相连；最小码字地址表模块的输入端与第一加法器的输 出端相连，输出端与减法器的输入端相连；减法器的输出端与第二加法器 的输入端相连；第二加法器的输出端与霍夫曼码字表模块相连。

此外，比较器阵列模块还包括8个与门，8个与门的输入端依次分别与 第九至第十六比较器的输出端及当前有效输入码流是否可能为长度9至16 的长码字(long_code_9至long_code_15)相连，输出端与第一加法器的 输入端相连，其中当前有效输入码流如果为1表示可能为长码字，如果为0 表示不可能为长码字。

如图1所示，码流输入数据中截取的有效输入数据分别同时输入到16 个比较器的一端，与对应的最小码字进行比较，其中，第九个比较器到第 十六个比较器的最终输出结果只有在当前有效输入数据可能为长码字时才 有效，该部分功能通过将比较器结果和长码字标志相与来实现，十六个比 较器的最终输出结果之和就是当前霍夫曼码字的长度，根据当前码字长度 通过数据移位器截取当前输入码流数据中的对应长度下的霍夫曼码字，同 时根据当前码字长度从最小码字表中查找出当前长度下的最小码字，将从 当前输入码流数据中截取的对应长度下的霍夫曼码字与对应的最小码字相 减并加上当前有效输入码流就可以得到霍夫曼码字表的索引地址，根据该 地址值即可取出当前霍夫曼码字对应的游程编码值。

根据上述电路设计，本发明还公开了一种JPEG霍夫曼解码方法。

首先，执行步骤1.在JPEG文件头霍夫曼标记解码阶段根据不同长度 下的霍夫曼码字个数建立的霍夫曼最小码字表，该最小码字表中前8个码 字的位宽分别为1位，2位，3位，4位，5位，6位，7位，8位，后8个 码字的位宽全部为8位；

假设JPEG文件头霍夫曼标记段中长度为i的码字个数为Num(i)，其中 1≤i≤16。如图2所示，对应的霍夫曼最小码字表通过如下过程计算：

步骤1A，从长度为1的最小码字开始，如果当前长度下对应的码字个数 为0，则该长度下的最小码字值MinCode(1)等于0，如果下一个长度下对应的 码字个数为0则重复执行过程1A)，如果下一个长度下对应的码字个数不为 0，则执行1B)；

步骤1B，通过以下公式计算出当前长度下对应的最小码字值

如果从下一个长度开始到长度为16所对应的码字个数全部为0，即 Num(i)到Num(16)全为0则执行1C)，否则重复执行过程1B)。其中，公式中 MinCode(1)始终等于0是由JPEG霍夫曼编码性质决定的；

步骤1C，从当前长度开始到长度为16的最小码字即MinCode(i)至 MinCode(16-i)全部等于255，即8位全1；

上述计算过程中得到的MinCode(1)～MinCode(16)的位宽分别为1位，2 位，3位，4位，5位，6位，7位，8位，8位，8位，8位，8位，8位，8 位，8位，8位。

需要说明的是，由于JPEG码流中霍夫曼编码的特性，可以证明当码字 长度大于8时，高于该码字第8位的所有比特位全为1，所以在解码计算码 字长度大于8的最小码字的时候只需要保存其低8位即可，下面简要介绍 上述霍夫曼码字特性的证明过程：

码字长度为l的最小码字可以通过以下二进制小数公式来计算：

$\underset{i=1}{\overset{l-1}{\Sigma }}{n}_i·2^{-i}$(公式一)

其中n_i是码字长度为i的码字个数。

在该二进制小数最低有效位补零(如有需要)以使得该二进制小数的 小数部分的位数等于码字长度，那么该二进制小数的小数部分就是与之对 应的霍夫曼码字串。JPEG压缩标准中使用的霍夫曼码字的长度为1～16位， 根据克拉夫特不等式，可以得到整个二进制霍夫曼码字树的总和等于1：

$\underset{i=1}{\overset{16}{\Sigma }}{n}_i·2^{-i}=\underset{i=1}{\overset{8}{\Sigma }}{n}_i·2^{-i}+\underset{i=9}{\overset{16}{\Sigma }}{n}_i·2^{-i}=1$

其中n_i是码字长度为i的码字个数。

同时又因为

$2^{-9}\underset{i=9}{\overset{16}{\Sigma }}{n}_i>\underset{i=9}{\overset{16}{\Sigma }}{n}_i·2^{-i}$

所以

$\underset{i=1}{\overset{8}{\Sigma }}{n}_i·2^{-i}+2^{-9}\underset{i=9}{\overset{16}{\Sigma }}{n}_i>\underset{i=1}{\overset{8}{\Sigma }}{n}_i·2^{-i}+\underset{i=9}{\overset{16}{\Sigma }}{n}_i·2^{-i}=1$

即

$\underset{i=1}{\overset{8}{\Sigma }}{n}_i·2^{-i}>1-2^{-9}\underset{i=9}{\overset{16}{\Sigma }}{n}_i$

对于JPEG压缩标准中任何一张霍夫曼码表来说：

$\underset{i=9}{\overset{16}{\Sigma }}{n}_i<256$

所以

$2^{-9}\underset{i=9}{\overset{16}{\Sigma }}{n}_i<0.5$

即

$1-2^{-9}\underset{i=9}{\overset{16}{\Sigma }}{n}_i>0.5$

所以

$\underset{i=1}{\overset{8}{\Sigma }}{n}_i·2^{-i}>1-2^{-9}\underset{i=9}{\overset{16}{\Sigma }}{n}_i>0.5$

结合公式一，从上式可以看出9位长度下最小码字的最高位肯定为1， 对于长度更长的码字，可以通过相同的方法证明出高于该码字第8位的所 有比特位全为1。

如图3所示，接着执行步骤2.在计算霍夫曼最小码字表的同时通过以 下公式计算不同长度下的霍夫曼最小码字地址表；

下表给出了真实的JPEG码流中AC分量码字个数表，同时也给出了本具 体实施例中步骤1和步骤2的计算结果；

  码字长度   码字个数   最小码字(二进制)   最小码字地址   1   0   0   0   2   2   00   0   3   1   100   2   4   3   1010   3   5   3   11010   6   6   2   111010   9   7   4   1111000   11   8   3   11111000   15

  9   5   11110110   18   10   5   11110110   23   11   4   11110110   28   12   4   11110000   32   13   0   11110100   36   14   0   11100000   36   15   1   11000000   36   16   125   10000010   37

如图4所示，接着执行步骤3.在JPEG图像霍夫曼解码阶段根据16个 并行的小于比较器的比较结果，计算出当前霍夫曼码字的长度，并根据最 小码字地址表得到游程编码值(RUN/SIZE)。

假设霍夫曼解码过程中当前16位输入码流为16’b1111111000111001， 则具体计算过程为：

假设16个比较器的比较结果为Comp(n)，并且将小于比较器中与输入码 流连接的输入端数据称为有效输入码流ValidData(n)，其中1≤n≤16，

步骤3A，在前8个比较器中，ValidData(n)为输入码流前n位，将 ValidData(n)与MinCode(n)进行比较，如果ValidData(n)小于MinCode(n)，比较结 果Comp(n)＝0，否则输出Comp(n)＝1，其中1≤n≤8；

步骤3B，在后8个比较器中，首先根据输入码流判断出该码字是否可 能为长码字(码字长度是否大于8)，如果输入码流的最高位为1，则该输 入码流可能是长度为9的长码字，如果输入码流的最高2位全为1，则该输 入码流可能是长度为10的长码字，以此类推，如果输入码流的最高8位全 为1，则该输入码流可能是长度为16的长码字。

如果当前输入码字不是长码字，比较器输出结果直接为0；如果是长码 字，舍弃输入码流高(n-8)位，ValidData(n)为输入码流中接下来的8位数据， 将ValidData(n)与MinCode(n)进行比较，如果ValidData(n)小于MinCode(n)，比较 结果Comp(n)＝0，否则输出Comp(n)＝1，其中9≤n≤16，在本具体实施例中 下表给出了计算结果：

步骤3C，通过以下公式将所有比较结果相加得到最终的码字长度 CodeLen

$\mathrm{CodeLen}=\underset{n=1}{\overset{16}{\Sigma }}\mathrm{Comp}\left(n\right)$1≤n≤16

从上表中可以看出，本实施例中CodeLen＝10。

步骤3D，根据当前解码出的码字长度通过以下公式计算得到该长度下 的最小码字地址min_adress：

min_adress＝MinAddr(CodeLen)＝MinAddr(10)＝23；

根据当前解码出的码字长度通过以下公式计算得到该长度下的最小码 字值min_code_value：

min_code_value＝MinCode(CodeLen)＝MinCode(10)＝8′b11110110；

根据有效输入码流、最小码字值以及最小码字地址通过以下公式计算 出当前码字在霍夫曼码表中的地址值symbol_adress：

symbol_adress＝ValidData(CodeLen)+min_code_value-min_address

             ＝8′b11111000-8′b11110110+23＝25；

最后根据symbol_adress查找霍夫曼码字表就可以得到当前码字对应的 游程编码值。

虽然上述优选的实施例详尽地说明了本发明的方法，但是需要说明的 是，本发明不限于上文优选的实施例。本领域的技术人员应当意识到在不 脱离本发明技术方案所给出的技术特征和范围的情况下，对技术特征所作 的增加、以本领域一些同样内容的替换，均应属本发明的保护范围。