CN100542047C - 一种指数Golomb编码的编码方法和装置 - Google Patents

Abstract

本发明公开了一种指数Golomb编码的编码方法和装置，编码时，将待编码的数据CodeNum和编码的阶数k输入编码装置，可以对通信数据进行k阶编码。本发明采用了纯组合逻辑电路求解以2为底的对数的技术，进而求出码字长度CodeLength和编码码字CodeWord的值，从而对输入数据进行实时的k阶哥伦布编码。编码过程实时性强、硬件资源消耗少，取得了编码速度快的效果。

Description

一种指数Golomb编码的编码方法和装置

技术领域

本发明属于通信领域，涉及一种编码器方法和装置，具体涉及一种指数Golomb编码的方法和装置。

背景技术

在通信领域中，为了减少通信传输的数据量，在数据发送端通常要对通信数据进行信源编码。指数Golomb编码是通信领域中经常用到的一种编码方法，在国际视频标准H.264和空间通信CCSDS等标准中都有应用。

指数Golomb编码是一种变长编码算法。变长码采用不同长度比特位的码字来表示数据，对常用的数据采用较短的码字，对不常用的数据采用较长的码字。这样做的好处是提高了存储的效率，降低了传输时对网络带宽的占用。与定长码相比，变长码提高了编码效率。

指数Golomb编码构成如下：对待编码数据CodeNum，设定编码指数阶数k，编码码字为：[M比特的0][1][M+k比特的INFO]，即由M个比特的0加上一个比特的1再加上信息位INFO，其中M和INFO的计算方法为：

M＝log₂(CodeNum/2^k+1)，INFO＝CodeNum-(2^M-1)×2^k，

根据定义，可以得到计算编码码字CodeWord和码字长度CodeLength的方法。对一个k阶的Golomb编码，编码计算公式如下：

CodeWord＝CodeNum+2^k，CodeLength＝2×log₂(CodeNum/2^k+1)+k+1

其中CodeNum表示待编码的数据。

在硬件实现编码的时候，出现了对数运算，通常采用查表的方法，将LUT固化到rom当中，即将待编码的数据作为地址线，编码结果CodeWord和CodeLength放到地址线对应的位置，这样简化了逻辑运算，但是构造的码表需要消耗大量的存储空间，且当编码的阶数k不相同的时候，码表不能重用。

发明内容

本发明的目的在于，提供了一种指数Golomb编码的编码方法和装置，可以对通信数据进行k阶编码。本发明采用了纯组合逻辑电路求解以2为底的对数的技术，进而求出CodeLength和CodeWord的值，从而对输入数据进行实时的k阶指数Golomb编码，使编码实时性强、硬件资源消耗少。

一种指数Golomb编码的编码方法，其特征在于，本方法包括下面几个步骤：

步骤1：数据输入初始化：将待编码的数据CodeNum和编码的阶数k分别输入到两个寄存器中；

步骤2：将待编码的数据CodeNum向右移动k位之后的数据和数值1输入到加法器中，输出数据为CodeNum1。运算表达式如下式所示：

CodeNum1＝(CodeNum＞＞k)+1

步骤3：将CodeNum1输入数据逆序器，得到输出CodeNumAnti，数据逆序器作用为将输出的对应比特位数据与输入的对应比特位数据调换；

步骤4：将CodeNumAnti输入到对数求解单元，求出CodeNumAnti的补码然后与本身的CodeNumAnti做一个逻辑与的运算，采用组合逻辑电路实现。输出数据为OneHotAnti，且OneHotAnti只含有CodeNumAnti最右边、即最低位的1，其余数据位均为0。组合逻辑电路的逻辑表达式如下：

OneHotAnti＝CodeNumAnti&(CodeNumAnti+1)

其中，CodeNumAnti表示对CodeNumAnti按位取反。

步骤5：将OneHotAnti输入到一个数据逆序器，输出为OneHot。

步骤6：将OneHot输入通用的2ⁿ-n编码器，得到输出M。

步骤7：将输出的M左移一位，得到结果与1+k相加，即得到Golomb编码的码字长度：

CodeLength＝(M＜＜1)+1+k，

实现过程可用乘法器和加法器实现。

步骤8：将CodeNum和k输入到运算逻辑电路中，得到编码码字CodeWord；运算的逻辑表达式如下式所示：

CodeWord＝CodeNum+(1＜＜k)，

实现过程可用加法器和n-2ⁿ译码器实现。

一种指数Golomb编码的编码装置，包括：通用2ⁿ-n编码器，其特征在于，还包括：输入数据处理单元、输出数据处理单元和对数求解单元。

输入数据处理单元将从寄存器取出的待编码数据CodeNum和编码阶数k进行处理，得出求对数运算的真数CodeNumAnti并输入到对数求解单元中，经过对数求解单元求以2为底的对数求解，并逆序输出，得到中间结果OneHot，并输入到通用2ⁿ-n编码器，得到输出M；M与待编码数据CodeNum和编码阶数k输入到输出数据处理单元中，得到编码的码字CodeWord和码字长度CodeLength。

所述编码器中输入数据处理单元，包括信号线、数据逆序器和一个通用加法器；从寄存器中取出待编码的数据CodeNum和编码的阶数k；信号线将输入的CodeNum对应位置连接，输出右移k位之后的数据，并与1在加法器中相加，结果作为数据逆序器的输入；数据逆序器中电路信号线将输入和输出数据高低比特位逆序连接，得到该模块的输出CodeNumAnti。

所述对数求解单元，用来析出输入数据最低比特位的1，对数求解单元的输出为OneHotAnti；该单元由一逻辑电路和一数据逆序器组成；逻辑电路将输入本单元的CodeNumAnti作为真数取以2为底的对数OneHotAnti；数据逆序器中电路信号线将输入和输出数据高低比特位逆序连接，得到逻辑电路输出信号OneHotAnti的逆序输出OneHot。

所述逻辑电路由非门、与门和一加法器连接而成，非门与输入端信号连接，非门的输出与信号1作为加法器的输入端，加法器的输出与输入信号再经过与门后的输出信号作为逻辑电路的输出。

所述输出数据计算单元，通过逻辑电路计算码字长度CodeLength和编码码字CodeWord；CodeWord由n-2ⁿ译码器和加法器组合的逻辑电路计算得到，将从寄存器取出的编码阶数k信号输入到n-2ⁿ译码器，再将其与从寄存器取出的待编码数据CodeNum输入到加法器，即可以得到编码码字CodeWord；CodeLength通过乘法器和加法器组成的逻辑电路计算得出。

本发明的优点在于：

(1)对数求解的过程中，可以实时的计算出输入数据的以2为底的对数的整数部分。不需进行查表，节省大量的存储空间；也不需要进行循环的移位比较运算，节省了运算时间。

(2)本发明可以适合于k阶哥伦布编码，将k作为一个参数输入到电路中，编码出结果。不同的阶数可以用相同的逻辑电路，无需查表法那样构造不同的码表，以至于消耗过多的空间和时间资源。

附图说明

图1为本发明一种指数Golomb编码的编码装置的模块结构图

图2为本发明一种指数Golomb编码的编码方法的系统流程图

图3为本发明0阶Golomb编码计算待求对数数据CodeNum1的电路原理图

图4为本发明一种指数Golomb编码的编码装置计算OneHot的电路原理图

图5为本发明0阶Golomb编码计算码字CodeWord的电路原理图

图6为本发明0阶Golomb编码计算码字长度CodeLength的电路原理图

图7为本发明2阶Golomb编码计算待求对数数据CodeNum1的电路原理图

图8为本发明2阶Golomb编码计算码字CodeWord的电路原理图

图9为本发明2阶Golomb编码计算码字长度CodeLength的电路原理图

具体实施方式

下面将结合附图和实施例对本发明作进一步的详细说明。

一种指数Golomb编码的编码方法，本方法包括下面几个步骤，如图2所示：

(1)数据输入初始化：将待编码的数据CodeNum和编码的阶数k分别输入到两个寄存器中；

(2)分别从寄存器中将待编码的数据CodeNum和编码的阶数k取出到输入数据处理单元中，将待编码的数据CodeNum向右移动k位之后的数据和数值为1的高电平信号输入到通用加法器中，输出数据为CodeNum1。运算表达式如(1)式所示。

CodeNum1＝(CodeNum＞＞k)+1               (1)

其中的移位运算可以直接用信号线将输入和输出数据的对应比特位连接起来，假设移位结果为TempShift，如(2)所示：

TempShift＝CodeNum＞＞k                 (2)

具体方法，将TempShift[i]与CodeNum[i+k]相连(0≤i≤(n-k)，n表示CodeNum的总比特数，TempShift[i]表示TempShift的第i比特，CodeNum[i+k]表示CodeNum的第i+k比特)，TempShift的高位补0。然后将TempShift与1输入到加法器，输出为CodeNum1，完成(1)的计算。

(3)将CodeNum1输入数据逆序器Anti，得到输出CodeNumAnti，数据逆序器Anti中，用信号线将将输出的对应比特位数据与输入的对应比特位数据调换，即将两者的高低位反向连接：CodeNum1的最低位与CodeNumAnti的最高位相连，CodeNum1的次低位与CodeNumAnti的次高位相连，直至CodeNum1的最高位与CodeNumAnti的最低位相连。

(4)将CodeNumAnti输入到对数求解单元，求出CodeNumAnti的补码然后与本身的CodeNumAnti做一个逻辑与的运算，采用组合逻辑电路实现，逻辑电路由非门、与门和一加法器连接而成，非门与输入端信号连接，非门的输出与信号1作为加法器的输入端，加法器的输出与输入信号再经过与门后的输出信号作为逻辑电路的输出。

输出为析出CodeNumAnti最右边、即最低位1之后的数据OneHotAnti，组合逻辑电路的逻辑表达式如下：

OneHotAnti＝CodeNumAnti&(CodeNumAnti+1)                          (3)

CodeNumAnti的补码与本身的CodeNumAnti做一个逻辑与的运算，即可以析出CodeNumAnti最低位1。得到的结果是指含有一位1或全0的数据。当CodeNumAnti为0时，输出数据为全0、不含1。

(5)将OneHotAnti输入到数据逆序器中，输出数据为OneHot。该逆序器同步骤(2)中逆序数据做法相同，用信号线将将输出的对应比特位数据与输入的对应比特位数据调换。

(6)编码计算M，将OneHot输入通用的2ⁿ-n编码器，得到编码结果，输出数据为M。这里的2ⁿ-n编码器可以用通用的8-3编码器组合实现，组合实现方法为业界通用方法。

(7)计算码字长度，从寄存器中取出编码阶数k至输出数据处理单元中，并将(6)中得到的M做如下的处理：

CodeLength＝(M＜＜1)+1+k                              (4)

将输出的M通过乘法器与信号量2相乘，使M左移一位，也可以将电路退化为若干连接的信号线，将输入的M和输出对应的比特位连接起来实现，得到结果在加法器中与1+k相加，即得到Golomb编码的码字长度CodeLength。

(8)计算编码结果CodeWord，将从寄存器取出的待编码数据CodeNum和k输入到计算CodeWord逻辑电路中可以得到编码结果CodeWord，逻辑表达式如(5)所示：

CodeWord＝CodeNum+(1＜＜k)                                     (5)

(1＜＜k)可以用一个n-2ⁿ译码器实现，k作为译码器的输入，输出就是(1＜＜k)。将(1＜＜k)和CodeNum输入到一个加法器，即可以完成(5)的逻辑功能。

一种指数Golomb编码的编码装置，包括：通用2ⁿ-n编码器、通用n-2ⁿ译码器、输入数据处理单元、对数求解单元和输出数据处理单元。

如图1所示，输入数据处理单元将信号将从寄存器取出的待编码数据CodeNum和编码阶数k进行信号处理，得出求对数运算的真数CodeNumAnti并输入到对数求解单元中，经过对数求解单元求以2为底的对数求解，并逆序输出，得到中间结果OneHot，并输入到通用2ⁿ-n编码器，得到输出M；M与待编码数据CodeNum和编码阶数k输入到输出数据处理单元中，得到编码的码字CodeWord和码字长度CodeLength。

所述编码器中输入数据处理单元，包括信号线、数据逆序器和一个通用加法器；从寄存器中取出待编码的数据CodeNum和编码的阶数k；信号线将输入的CodeNum与对应的比特位连接实现移位运算，输出移位后右移k位之后的数据，并与1在加法器中相加，结果作为数据逆序器的输入；数据逆序器中电路信号线将输入和输出数据高低比特位逆序连接，得到该模块的输出CodeNumAnti，作为求对数运算的真数。

所述对数求解单元，用来析出输入数据最低比特位的1，对数求解单元的输出为OneHotAnti。由一逻辑电路和一数据逆序器组成；逻辑电路将输入本单元的CodeNumAnti作为真数，并取以2为底的对数OneHotAnti；数据逆序器中电路信号线将输入和输出数据高低比特位逆序连接，即输入数据最高比特与输出数据最低比特连接，输入数据次高比特与输出数据次高比特连接，直至得到逻辑电路输出信号OneHotAnti的逆序输出OneHot。

如图4所示，所述逻辑电路由非门、与门和一加法器连接而成，非门与输入端信号连接，非门的输出与信号1作为加法器的输入端，这样就完成了求补码的运算；加法器的输出与输入信号再经过与门后的输出信号作为逻辑电路的输出。

所述输出数据处理单元，通过逻辑电路计算出码字以及码字长度；输出数据处理单元由乘法器、n-2ⁿ译码器和加法器混合连接而成；从寄存器取出的编码阶数k信号在加法器中与1相加输出到加法器中，并与所述2ⁿ-n编码器的输出M与信号量2经过乘法器后，即M左移一位的结果在另一加法器中相加，输出信号为码字长度CodeLength；对于编码的码字，可以将从寄存器取出的编码阶数k信号输入到一个n-2ⁿ译码器，将高电平信号1左移k位输出，输出即为2^k，再将其与从寄存器取出的待编码数据CodeNum输入到一加法器，即可以得到编码码字CodeWord。

实施例1：

本实施实例以k＝0为例，即0阶Golomb编码，说明本发明的应用

输入数据处理单元，由输入的数据CodeNum得到待求对数数据CodeNum1。此时k＝0，公式(1)退化为：

CodeNum1＝CodeNum+1                                    (6)

具体可以由通用加法器实现，逻辑电路图如图3所示。

得到CodeNum1之后，将CodeNum1输入逆序器，输出为CodeNumAnti；即将CodeNum1高低位逆序输出，用信号线将将输出的对应比特位数据与输入的对应比特位数据调换，CodeNum1的最低位与CodeNumAnti的最高位相连，CodeNum1的次低位与CodeNumAnti的次高位相连，直至CodeNum1的最高位与CodeNumAnti的最低位相连。将处理结果CodeNumAnti输出给对数求解单元。

对数求解单元，将CodeNumAnti通过(7)式所表示运算电路，即可以析出最低比特位的1。

OneHotAnti＝CodeNumAnti&(CodeNumAnti+1)                         (7)

具体实现逻辑电路如图4所示。(7)式得到的是CodeNumAnti的对数的整数部分，要得到CodeNum1的对数整数部分，需要将OneHotAnti高低位逆序，得到OneHot。具体做法也是用逆序器中的信号线高低位直接反向连接，将输出的对应比特位数据与输入的对应比特位数据调换即可。

2ⁿ-n编码器单元，输入为OneHot，输出为M，具体可以用通用的8-3编码器组合实现。

输出数据处理单元，计算出码字CodeWord和码字长度CodeLength。其中编码码字CodeWord由(8)式得到：

CodeWord＝CodeNum+1                                            (8)

具体逻辑电路由一个加法器实现，如图5所示，n-2ⁿ译码器对从寄存器取出的编码阶数0进行编码，将编码的结果与从寄存器取出的待编码数据CodeNum输入到加法器，得到码字CodeWord。

而码字长度由(9)式得到：

CodeLength＝(M＜＜1)+1                                   (9)

具体逻辑电路如图6所示，2ⁿ-n编码器的输出M与信号量2经过乘法器后所得输出在加法器中与高电平信号量1相加，信号M移位也可以用电路信号线直接连接，即CodeLength的第0位连接到表示1的高电平，CodeLength的第i位与M的第i-1位相连。

实施例2：

本实施实例以k＝2为例，即2阶Golomb编码。

输入数据处理单元，由输入的数据CodeNum得到待求对数数据CodeNum1，CodeNum总共有n个比特。此时k＝2，公式(1)变为：

CodeNum1＝(CodeNum＞＞2)+1                              (10)

其中，移位运算只需要对应的比特位用信号线连接即可，加法由通用加法器实现，逻辑电路图如图7所示。其中CodeNum[n:2]表示，CodeNum的第n到第2位。

得到CodeNum1之后，将CodeNum1输入逆序器，即将CodeNum1高低位反过来，将输出的对应比特位数据与输入的对应比特位数据调换即可。将结果CodeNumAnti输出给对数求解单元。

对数求解单元，2ⁿ-n编码器单元，与0阶Golomb编码装置相同。

输出数据处理单元，计算出码字CodeWord和码字长度CodeLength。其中，码字由(11)式得到：

CodeLength＝(M＜＜1)+3                                    (11)

具体逻辑电路如图8所示，2ⁿ-n编码器的输出M与信号量2经过乘法器后所得输出在加法器中与高电平信号量1相加，信号M移位也可以用电路信号线直接连接，即CodeLength的第0位连接到表示1的高电平，CodeLength的第i位与M的第i-1位相连。

而码字长度由(12)式得到：

CodeWord＝CodeNum+(1＜＜2)                                (12)

具体逻辑电路如图9所示，n-2ⁿ译码器对从寄存器取出的编码阶数2进行编码，将编码的结果2²与从寄存器取出的待编码数据CodeNum输入到加法器，得到码字CodeWord。

Claims (3)

1、一种指数Golomb编码的编码方法，其特征在于，本方法包括下面几个步骤：

步骤一：数据输入初始化：将待编码的数据CodeNum和编码的阶数k分别输入到两个寄存器中；

步骤二：将待编码的数据CodeNum向右移动k位之后的数据和数值1输入到加法器中，输出数据为CodeNum1；运算表达式如下式所示：

CodeNum1＝(CodeNum＞＞k)+1；

步骤三：将CodeNum1输入数据逆序器，得到输出CodeNumAnti，数据逆序器将输出的对应比特位数据与输入的对应比特位数据调换；

步骤四：将CodeNumAnti输入到对数求解单元，求出CodeNumAnti的补码然后与本身的CodeNumAnti做一个逻辑与的运算，采用组合逻辑电路实现，输出为析出CodeNumAnti最右边，即最低位1之后的数据OneHotAnti，组合逻辑电路的逻辑表达式如下：

OneHotAnti＝CodeNumAnti&(CodeNumAnti+1)；

步骤五：将OneHotAnti输入到一个数据逆序器，输出为OneHot；

步骤六：将OneHot输入通用的2ⁿ-n编码器，得到输出M；

步骤七：将输出的M左移一位，得到结果与1+k相加，即得到Golomb编码的码字长度：

CodeLength＝(M＜＜1)+1+k，

实现过程可用乘法器和加法器实现；

步骤八：将CodeNum和k输入到运算逻辑电路中，得到编码码字CodeWord；运算的逻辑表达式如下式所示：

CodeWord＝CodeNum+(1＜＜k)，

实现过程用加法器和n-2ⁿ译码器实现。

2、一种应用于权利要求1所述一种指数Golomb编码的编码方法的装置，包括：通用2ⁿ-n编码器，其特征在于，还包括：输入数据处理单元，对数求解单元和输出数据处理单元；

输入数据处理单元将从寄存器取出的待编码数据CodeNum和编码阶数k进行处理，得出求对数运算的真数CodeNumAnti并输入到对数求解单元中，经过对数求解单元求以2为底的对数求解，并逆序输出，得到中间结果OneHot，并输入到通用2ⁿ-n编码器，得到输出M，M与待编码数据CodeNum、高电平信号1、对数求解单元的结果OneHot和编码阶数k输入到输出数据处理单元中，得到编码的码字CodeWord和码字长度CodeLength；

所述输入数据处理单元，包括信号线、数据逆序器和一个通用加法器，从寄存器中取出待编码的数据CodeNum和编码的阶数k，信号线将输入的CodeNum与对应的比特位连接实现移位运算，输出移位后右移k位之后的数据，并与1在加法器中相加，结果作为数据逆序器的输入，数据逆序器中电路信号线将输入和输出数据高低比特位反向连接，得到该模块的输出CodeNumAnti；

所述对数求解单元，用来析出输入数据最低比特位的1，该单元输出为信号OneHotAnti，由一逻辑电路和一数据逆序器组成，逻辑电路将输入本单元的CodeNumAnti作为真数取以2为底的对数OneHotAnti，数据逆序器中电路信号线将输入和输出数据高低比特位反向连接，得到逻辑电路输出信号OneHotAnti的逆序输出OneHot；

所述输出数据处理单元中计算得到的码字CodeWord是由n-2ⁿ译码器和加法器组合的逻辑电路计算得到的，具体计算过程为：n-2ⁿ译码器对从寄存器取出编码阶数k信号进行计算，即将高电平信号1左移k位输出，再将计算结果与从寄存器取出的待编码数据CodeNum输入到加法器，即得到编码码字CodeWord；

所述输出数据处理单元中得到的码字长度CodeLength通过乘法器和加法器组成的逻辑电路计算得出，具体过程为：从寄存器取出的编码阶数k信号在加法器中与1相加输出到加法器中，并与2ⁿ-n编码器的输出M与信号量2经过乘法器后，即M左移一位的结果在另一加法器中相加，输出信号为码字长度CodeLength。

3、根据权利要求2所述的一种应用于权利要求1所述一种指数Golomb编码的编码方法的装置，其特征在于：所述逻辑电路由非门、与门和加法器连接而成，非门与输入端信号连接，非门的输出与信号1作为加法器的输入端，得到输入信号的补码；加法器的输出与输入信号再经过与门后的输出信号作为逻辑电路的输出。

Images