一种基于随机计算的离散余弦变换实现方法及系统

摘要

本发明公开了一种基于随机计算的离散余弦变换实现方法及系统，其中，该方法包括：将图像变换单元(TU)与离散余弦变换(DCT)系数映射为预设范围内的小数，再将小数转化为随机序列；将所述随机序列转化为随机计算域序列，并利用随机计算乘法器与随机计算加法器进行计算；将计算结果转化为二进制补码形式，从而实现离散余弦变换。通过采用本发明公开的方法及系统，可以大大的减少硬件消耗的同时提高系统的工作时钟频率。

说明书

技术领域

本发明涉及数字图像压缩或视频压缩技术领域，尤其涉及一种基于随机计算的离散余弦变换实现方法及系统。 

背景技术

离散余弦变换(DCT)因具有接近理想的去相关的性能而广泛用于图像和视频编码标准中。 

目前，主流图像和视频编码标准均是基于块的编码架构，这就意味着DCT的实现也要以变换块(TU)为基本单元。图像处理中通常采用8×8大小的块，而视频处理中则相对较灵活，比如4×4～8×8(H.264)，4×4～32×32(H.265)。硬件电路中，若直接实现浮点或定点的DCT运算，会带来较多硬件消耗和无法容忍的关键路径延时。所以，DCT硬件实现方面的改进有两个方向：一是减少硬件消耗，比如寻找快速算法和乘法器的替代方案，二是采用并行和流水线架构以增加吞吐量和时钟频率。 

但是，目前的DCT实现即使融合快速算法(比如部分蝶形运算)和无乘法器结构，也同时会带来繁琐的移位和加法运算，而且流水线结构势必也会引入更多的硬件消耗。所以，DCT硬件电路实现的面积和时钟频率仍需进一步改善。 

发明内容

本发明的目的是提供一种基于随机计算的离散余弦变换实现方法及系统，大大的减少了硬件消耗。 

本发明的目的是通过以下技术方案实现的： 

一种基于随机计算的离散余弦变换实现方法，该方法包括： 

将图像变换单元TU与离散余弦变换DCT系数映射为预设范围内的小数，再将小数转化为随机序列； 

将所述随机序列转化为随机计算域序列，并利用随机计算乘法器与随机计算加法器进行计算； 

将计算结果转化为二进制补码形式，从而实现离散余弦变换。 

进一步的，所述将图像变换单元TU与离散余弦变换DCT系数映射为预设范围内的小数，再将小数转化为随机序列包括： 

将TU中的数据和DCT变换系数转化为[0,1]或[-1,1]区间中的小数，再通过基于ROM的二进制权重随机序列生成器产生对应于TU和DCT变换系数的随机序列，并对所述随机序列进行不同位数的循环移位。 

进一步的，所述将TU中的数据和DCT变换系数转化为[0,1]或[-1,1]区间中的小数，再通过基于ROM的二进制权重随机序列生成器产生对应于TU和DCT变换系数的随机序列，并对所述随机序列进行不同位数的循环移位，包括： 

整数到小数的映射：TU的数据包括预测后的残差数据R，若TU数据的位宽为B，残差数据R的变化范围为[-2^B+1,2^B-1]，则残差数据R的1/N为伸缩扩展后的数据，其中，N为扩展因子，N＝2^B；对DCT变换系数矩阵T进行伸缩变换，表示为T*2/N； 

小数的处理：将步骤整数到小数的映射获得的数据x进行双线双极性处理，包括将数据x分为数据部分x_data和符号部分x_sign，表示为： 

$\left(\begin{array}{c}{x}_{\mathrm{data}}=\left|x\right|,x_{\mathrm{sign}}=0;(x\ge 0)\\ x_{\mathrm{data}}=\left|x\right|,x_{\mathrm{sign}}=1;(x<0)\end{array},;\right)$

小数到随机序列的映射，包括：权重二进制比特流的产生和随机序列的合成：其中，权重二进制比特流是由LFSR线性反馈移位寄存器及逻辑门组合产生，通过本级寄存器的输出与前面所有级输出取反后相与产生，相互之间1的位置交替出现，并且每一串权重比特流ω_i中1的概率是2^-(B-i)，(i＝0,1,2…B-1)，i是权重比特流号；将数据部分x_data写成B位二进制小数的形式，则有x_data＝.x_B-1x_B-2…x₀，通过X_data＝x₀ω₀+x₁ω₁+…+x_B-1ω_B-1，x_data表征为比特流X_data的形式，式中的加法和乘法对应逻辑运算的或和与运算。 

进一步的，该方法还包括：将预先生成的权重比特流分段存储在多个ROM中实现并行计算，具体的：对于数据位宽为B的随机运算，ROM中需要存储B串权重比特流，若每串比特流分为L段，则硬件实现需要L个位宽为B，深度为2^B/L的ROM。 

进一步的，所述基于随机计算理论将所述随机序列进行转化，并利用随机计算乘法器与随机计算加法器进行计算包括： 

将所述随机序列进行转化包括：将进行双线极性处理的随机序列转化为双线随机计算域序列；其中，所述双线随机计算域序列表示为U，D序列，用于表征在区间[-1,1]内 的数据x，具体的：由式子x＝P(U＝1)-P(D＝1)表征数据x，其中定义： 

$\left(\begin{array}{c}P(U=1)=\left|x\right|,P(D=1)=0;(x_{\mathrm{sign}}=0)\\ P(D=1)=\left|x\right|,P(U=1)=0;(x_{\mathrm{sign}}=1)\end{array},;\right)$

利用随机计算乘法器进行计算包括：将输入的含有数据和符号序列的双线随机序列进行计算，表示为： 

X_data＝X_data1∩X_data2； 

X_sign＝X_sign1⊕X_sign2； 

其中，X_data1、X_data2与X_signi、X_sign2分别表示数据和符号的序列； 

所述随机计算加法器包括2选1选择器组成的缩放加法器，加法计算表示为： 

x₁+x₂＝P(U₁＝1)+P(U₂＝1)-[P(D₁＝1)+P(D₂＝1)]＝P(U＝1)-P(D＝1)。 

进一步的，所述将计算结果转化为二进制补码形式包括： 

利用UP-DOWN计数器，将U序列接入计数加法端，D序列接入计数减法端，时钟上升沿触发计数更新，最后输出二进制补码形式的计数结果。 

进一步的，该方法还包括：利用有符号的计数器替代UP-DOWN计数器与随机计算加法器；其实现步骤包括： 

首先来自随机计算乘法器的L段随机序列进入L输入的1位并行加法器，并行加法器的输出结果进入2选1选择器；若所述随机计算乘法器的输出序列符号为正，则选择器输出并行加法器结果；否则，选择器输出算术取反后的结果；选择器的结果进入有符号的并行累加器，每个时钟周期累加器更新一次，运算周期结束输出最终的累加值。 

一种实现离散余弦变换实现方法的系统，该系统包括： 

数据映射单元，用于将图像变换单元TU与离散余弦DCT变换系数映射为预设范围内的小数，再将小数转化为随机序列； 

随机计算核单元，用于将所述随机序列转化为随机计算域序列，并利用随机计算乘法器与随机计算加法器进行计算 

结果转换单元，用于将计算结果转化为二进制补码形式，从而实现离散余弦变换。 

由上述本发明提供的技术方案可以看出，通过基于随机计算理论将算术运算转换为简单的逻辑运算，能够有效的简化硬件实现并提高电路工作时钟频率；另外，通过采用基于只读存储器(ROM)的并行结构，还可有效的提高了DCT系统的吞吐量。 

附图说明

为了更清楚地说明本发明实施例的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域的普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他附图。 

图1为本发明实施例一提供的一种基于随机计算的离散余弦变换实现方法的流程图； 

图2为本发明实施例一提供的一种基于随机计算的离散余弦变换实现方法的流程框图； 

图3为本发明实施例一提供的权重比特流的产生过程的示意图； 

图4为本发明实施例一提供的基于ROM的随机序列合成过程的示意图 

图5a为本发明实施例一提供的将随机序列进行转化的示意图； 

图5b为本发明实施例一提供的利用随机计算乘法器进行计算的示意图； 

图5c为本发明实施例一提供的利用随机计算加法器进行计算的示意图； 

图6为本发明实施例一提供的有符号的并行计数器结构示意图； 

图7为本发明实施例二提供的一种离散余弦变换实现系统的示意图。 

具体实施方式

下面结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明的保护范围。 

随机计算的理论源于20世纪60年代，由于低复杂度和高容错率性能，广泛应用于模糊控制和神经网络研究领域。近年来，随机计算开始在低密度校验码(LDPC)编解码和数字图像处理领域崭露头角。 

随机计算的低复杂度和高容错率可以用接下来的例子来说明。参与随机计算的数据首先应转化到[0,1]的范围，然后用一串随机比特流代表这个值。比如一个小数0.5，我们可以用“0101111000110010”这串比特流代替，其中“1”在这串比特流中所占的比重为0.5。在表示0.5这个数的比特流中，每一位都有相同的权重(1/16)，因此，其中一位出 错会带来1/16的误差。而在传统的二进制补码的数据表示形式中，如果错误发生在高位，将会带来巨大的错误。所以，随机计算在容错率方面比传统的二进制补码形式的表示方法更有优势。另外，随机计算同时具有简单的电路实现。假如采用随机计算理论计算1/2和1/4的相乘结果，首先分别用相互独立的比特流A:0101111000110010和B:0001000101010000代表1/2和1/4，然后两串比特流经过与门即A∩B结果为0001000000010000，其中“1”的比率为1/8，也即1/2和1/4相乘的结果。如果要计算两个在[0,1]区间的小数加法，要采用缩放加法才能使最后结果能以比特流形式表示，缩放加法可以采用选择器实现。比如与上例相同的两串比特流A和B，2选1选择器的选择信号使用比特流sel:1001000010111101，sel中“1”的比率为1/2。A和B经过选择器后的输出比特流为0101111000010010，其中“1”的比率为3/8，也即(1/2+1/4)/2。因此，随机计算可以用简单的逻辑运算实现算术乘法和加法运算。 

本发明实施例中，对TU数据进行常规DCT是两个矩阵相乘的形式。本发明采用随机计算的理论实现了常规的4点的DCT运算。一个DCT运算结果的产生包括4次乘法和3次加法运算，本发明采用并行架构在一个运算周期可以产生4个运算结果，提高了系统的吞吐率。 

实施例一 

图1为本发明实施例一提供的一种基于随机计算的离散余弦变换实现方法的流程图。如图1所示，该方法主要包括如下步骤： 

步骤11、将图像变换单元(TU)与离散余弦变换(DCT)系数映射为预设范围内的小数，再将小数转化为随机序列。 

为便于理解本发明，具体的实现流程还可参见附图2所示的框图。 

本步骤具体来说，是将TU中的数据和DCT变换系数转化为[0,1]或[-1,1]区间中的小数，再通过二进制权重生成器产生对应于TU和DCT变换系数的随机序列，并对所述随机序列进行不同位数的循环移位用以降低相关性；可以分为如下三个步骤来实现： 

1)整数到小数的映射：TU的数据包括预测后的残差数据R，若TU数据的位宽为B，残差数据R的变化范围为[-2^B+1,2^B-1]，则残差数据R的1/N为伸缩扩展后的数据，其中，N为扩展因子，N＝2^B； 

本发明基于最新的高效视频编码标准(HEVC)的整数DCT变换核，其中4点的整数DCT变换系数矩阵T如下式所示： 

$T=\left(\begin{array}{cccc}64& 64& 64& 64\\ 83& 36& -36& -83\\ 64& 64& -64& -64\\ 36& -83& 83& -36\end{array}\right);$

它是在保证正交性的前提对精确DCT变换系数的伸缩和取整的结果。本发明实施例在保证精确DCT变换系数正交性和归一性的基础上对T进行伸缩变换，也即T*2/N。为使得参与随机计算的表征TU数据和DCT变换系数比特流长度一致，这里取B＝8。 

2)小数的处理：TU数据和DCT变换系数经过步骤1)后的扩展数据x属于区间[-1,1]，包括两种处理方式，一种为单线双极性的处理，也即将数据x经过(x+1)/2映射到[0,1]的范围；另一种为双线双极性处理，即将数据x分为数据部分x_data和符号部分x_sign，表示为： 

$\left(\begin{array}{c}{x}_{\mathrm{data}}=\left|x\right|,x_{\mathrm{sign}}=0;(x\ge 0)\\ x_{\mathrm{data}}=\left|x\right|,x_{\mathrm{sign}}=1;(x<0)\end{array},;\right)$

由于单线双极性的映射会使得结果转换单元变的复杂甚至无法实现，并且会增加计算误差，因此，本发明采用双线双极性的映射方式。 

3)小数到随机序列的映射，包括：权重二进制比特流的产生和随机序列的合成。 

为产生表征[0,1]范围的随机序列，传统的随机序列生成器是由伪随机噪声生成器(PRNG)和比较器构成，伪随机噪声生成器一般由线性反馈移位寄存器(LFSR)实现。传统的随机序列生成器应用广泛，但存在固有的波动误差和较大的并行实现难度。 

相比于传统的方法，基于权重二进制的生成器(WBG)具有更高的精度和并行实现的灵活性。如图3所示，权重二进制比特流是由LFSR线性反馈移位寄存器及逻辑门组合产生，通过本级寄存器的输出与前面所有级输出取反后相与产生，相互之间1的位置交替出现，并且每一串权重比特流ω_i中1的概率是2^-(B-i)，(i＝0,1,2…B-1)，i是权重比特流号；将数据部分x_data写成B位二进制小数的形式，则有x_data＝.x_B-1x_B-2…x₀，通过X_data＝x₀ω₀+x₁ω₁+…+x_B-1ω_B-1，x_data表征为比特流X_data的形式，式中的加法和乘法对应逻辑运算的或和与运算。 

进一步的，本发明采用基于WBG的随机序列生成方式；将预先生成的权重比特流分段存储在多个ROM中实现并行计算，也即图2中的MWBG。如图4所示，为比特流X中的其中一段X_i的产生电路图，W_i即为第i个ROM，x为步骤数据部分x_data的二进制补码表示形式。对于数据位宽为B的随机运算，ROM中需要存储B串权重比特流，若每串比特流分为 L段，则硬件实现需要L个位宽为B，深度为2^B/L的ROM。这样，L个ROM可以同时读取数据参与并行运算。值得注意的是，相互运算的并行数据串形式上是不同循环移位量的数据，以减少相关性，具体实现是交错运算数据映射单元的输出数据。 

步骤12、将所述随机序列转化为随机计算域序列，并利用随机计算乘法器与随机计算加法器进行计算。 

如图5a所示，将所述随机序列进行转化包括：将数据和符号分离形式的随机序列转化为双线随机计算域序列；其中，U，D序列即为双线随机计算域序列，用于表征在区间[-1,1]内的数据x，X_data与X_sign为表示数据x的绝对值和x的符号的序列。具体的：由式子x＝P(U＝1)-P(D＝1)表征数据x，其中定义： 

$\left(\begin{array}{c}P(U=1)=\left|x\right|,P(D=1)=0;(x_{\mathrm{sign}}=0)\\ P(D=1)=\left|x\right|,P(U=1)=0;(x_{\mathrm{sign}}=1)\end{array},;\right)$

如图5b所示，利用随机计算乘法器进行计算包括：将输入的数据和符号序列的双线随机序列进行计算，表示为： 

X_data＝X_data1∩X_data2； 

X_sign＝X_sign1⊕X_sign2； 

其中，X_data1、X_data2与X_signi、X_sign2分别表示数据和符号的序列； 

如图5c所示，所述随机计算加法器包括2选1选择器组成的缩放加法器，输入U、D序列和选择器的选择信号sel，输出同样为表征结果的U、D序列。加法计算表示为： 

x₁+x₂＝P(U₁＝1)+P(U₂＝1)-[P(D₁＝1)+P(D₂＝1)]＝P(U＝1)-P(D＝1)。 

其中U₁和D₁序列用来表征小数x₁，U₂和D₂序列用来表征小数x₂，U和D为随机加法器输出序列，用来表征伸缩加法器输出结果。 

步骤13、将计算结果转化为二进制补码形式，从而实现离散余弦变换。 

本步骤将核心计算单元产生的比特流结果转化为传统的二进制补码形式，从而方便后续的量化实现。要对双极性双线性随机计算的结果转换，本发明采用加减计数器(UP-DOWN计数器)实现。将U序列接入计数加法端，D序列接入计数减法端，时钟上升沿触发计数更新，最后输出二进制补码形式的计数结果。 

实验结果表明，随机加法器计算误差是整个系统计算误差的主要来源，我们进一步用有符号的并行计数器取代随机计算加法器与UP-DOWN计数器，从而大大提高了计算精 度。 

图6是有符号的并行计数器结构，首先L段随机序列(比如来自随机计算乘法器的序列X_I₁，X_I₂…X_I_L)进入L输入的1位并行加法器(可以采用传统并行加法器)，所述并行加法器的输出结果进入2选1选择器；若所述随机计算乘法器的输出序列符号为正(X_sign＝0)，则选择器输出并行加法器结果；否则(X_sign＝1)，选择器输出算术取反后的结果。选择器的结果进入有符号的并行累加器，每个时钟周期累加器更新一次，运算周期结束输出最终的累加值。 

本发明实施例通过基于随机计算理论将算术运算转换为简单的逻辑运算，能够有效的简化硬件实现并提高电路工作时钟频率；另外，通过采用基于ROM的并行结构，还可有效的提高了DCT系统的吞吐量。 

本发明相比于传统的DCT，硬件消耗降低50％以上。表1是对传统的4点整数DCT和基于随机计算的4点整数DCT FPGA实现的综合的结果对比(采用Xilinx ISE13.3XST综合工具)，其中寄存器(#Slice Registers)和查找表触发器对(#LUT-FF pairs)的数量均低于传统实现，而所需查找表数(#Slice LUTs)更是低于传统实现的50％。 

本发明相比于传统的DCT实现，关键路径延时少，具有更高的工作时钟频率，如表1Max.Freq.项所示。传统的实现采用了三级流水线结构，而基于随机计算的实现没有采用流水线结构。但本发明综合后的时钟频率是传统的两倍。 

实施例二 

图7为本发明实施例二提供的一种离散余弦变换实现系统的示意图。如图7所示，该系统主要包括： 

数据映射单元71，用于将图像变换单元TU与离散余弦变换DCT系数映射为预设范围内的小数，再将小数转化为随机序列； 

随机计算核单元72，用于将所述随机序列进行转化，并利用随机计算乘法器与随机 计算加法器进行计算； 

结果转换单元73，用于将计算结果转化为二进制补码形式，从而实现离散余弦变换。 

需要说明的是，上述系统中包含的各个功能模块所实现的功能的具体实现方式在前面的各个实施例中已经有详细描述，故在这里不再赘述。 

所属领域的技术人员可以清楚地了解到，为描述的方便和简洁，仅以上述各功能模块的划分进行举例说明，实际应用中，可以根据需要而将上述功能分配由不同的功能模块完成，即将系统的内部结构划分成不同的功能模块，以完成以上描述的全部或者部分功能。 

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明披露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应该以权利要求书的保护范围为准。