CN101493760A - 一种高速除法器及其实现高速除法运算的方法 - Google Patents

Abstract

本发明提供了一种高速除法器，包括编码转换模块、符号位判决模块、非零bit位搜索模块、倒数值查表模块、修正调节模块和乘法处理模块，所述编码转换模块与符号位判决模块、非零bit位搜索模块、倒数值查表模块、修正调节模块和乘法处理模块依次连接，编码转换模块、符号位判决模块还分别与乘法处理模块相连接，乘法处理模块的输出端输出除法运算的结果。本发明高速除法器为一种运算精度可控的高速除法器，既可以根据实际应用要求任意设定相应运算精度，而且，本发明高速除法器可以应用在高速数学运算处理中，而且运算时间短，处理延时小，结构简单，可行性好。

Description

一种高速除法器及其实现高速除法运算的方法

技术领域

本发明涉及通信、电子技术领域的数字信号处理领域，具体涉及一种高速除法器及其实现高速除法运算的方法。

背景技术

在数字信号处理领域，除法运算是一个必不可少的处理。尤其是涉及到自适应信号处理，经常会遇到归一化或矩阵运算等处理，而这些都必须通过除法运算才得以实现。随着移动通信技术的发展，以及数字信号处理技术的不断进步，在如今的通信、电子设备中，越来越多的运用了基于信号处理技术实现的子系统或模块，因此，很多算法运算，如加法、减法、乘法和除法运算，都必须在硬件电路上实现，通过固定的硬件电路或是采用一定的算法，结合已有的一些硬件电路，而扩展实现应有的功能。对于加法、减法处理，硬件电路都是完全支持的；对于乘法运算，很多硬件电路是通过查找表(LUT)来实现的，一些特殊的器件，还嵌入了专门的乘法处理模块，如可编程逻辑器件厂商开发的高性能FPGA芯片，都具有专门的DSP模块，可以实现高速的乘法运算。加法、减法、乘法运算在实际应用中，都比较容易实现。但对于除法运算，硬件电路都是不具备专门的除法模块的，基本都是通过一定的算法，在现有的硬件电路资源情况下，通过组合不同资源得以实现除法处理。

在专利公开号为CN1423189A的中国申请专利“一种除法器”中，采用移位加减法的处理方式实现除法器，也是通过利用相应算法，控制硬件电路中固有的加法和减法资源，而得以实现除法处理。该除法器的优点在于运算较为精确，但处理的时钟周期较长，如一个简单的32bit除16bit的运算，需要16个时钟周期。在数字信号处理中，处理时钟周期的拉长，会引入额外的处理延时，给系统带来不利的映像。

在专利公开号为CN1979411A的中国专利公开了“一种高速除法器的实现方法与装置”，其整体处理结构图如图1所示，该高速除法器的实现装置由预处理模块、查找表模块、插值拟合模块、乘法器和后处理模块依次连接组成，预处理模块主要是将输入的除数和被除数都转换为无符号数，并记录商的符号；查找表模块主要是将区间[A，B]内依据等分或不等分的间隔分成N段，然后计算出各分隔点的对应倒数，做成表格；插值拟合模块主要采用插值的方法得到其余各点处倒数值的估算；乘法器主要是实现乘法运算，得到商的中间结果；后处理模块是对上述步骤中的数进行扩大或缩小K倍，得到最后的商。该方法避免了常规乘法器结构中的多次移位运算和减法操作，结构简单，可行性好、运算速度比较快，大大减少了除法运算的时钟周期。但该发明的运算精度受限，只比较适合对运算速度要求较高，而对运算精度要求不是很高的场合。

发明内容

本发明的目的在于克服上述现有技术的缺点和不足，提供一种高速除法器，本发明高速除法器为一种运算精度可控的高速除法器，即可以根据实际应用要求任意设定相应运算精度，而且，本发明高速除法器可以应用在高速数学运算处理中，而且运算时间短，处理延时小，结构简单，可行性好。

本发明的目的还在于提供上述高速除法器实现高速除法运算的方法。

本发明目的通过下述技术方案实现：一种高速除法器，包括编码转换模块、符号位判决模块、非零bit位搜索模块、倒数值查表模块、修正调节模块和乘法处理模块，所述编码转换模块与符号位判决模块、非零bit位搜索模块、倒数值查表模块、修正调节模块和乘法处理模块依次连接，编码转换模块、符号位判决模块还分别与乘法处理模块相连接，乘法处理模块的输出端输出除法运算的结果。

利用上述高速除法器实现高速除法运算的方法，包括下述步骤：

(1)编码转换模块对除数和被除数分别进行码制转换处理，即将非二进制补码的除数、被除数分别转换为二进制补码编码的除数、被除数；

(2)符号位判决模块对二进制补码编码的除数进行分部分解处理，确定分部分解处理后的二进制补码编码的除数的符号位，作为最后商的正负的参考准则；同时，对二进制补码编码的除数进行绝对化处理，以利于进行相应的搜索和查表等处理；

(3)非零bit位搜索模块从最高bit位开始搜索绝对化处理后的除数的第一个非零bit位，同时记录该非零bit位，并从该非零bit位开始扩展N bit的数；

(4)倒数值查表模块根据上述非零bit位，并结合扩展N bit的数，组成一个数，将该数作为倒数值查表模块中的查找表的地址，查询该地址，获得该地址对应的倒数值；

(5)修正调节模块对步骤(4)所述的倒数值进行修正调节处理，即对该倒数值进行相应的不同倍数的放大处理；

(6)乘法处理模块将输入数据，即输入的被除数与修正调节模块输入的倒数值进行乘法运算处理，并将乘法运算处理后的数值与步骤(2)所述除数的符号位结合起来，输出最后的商；也即，由于二进制补码编码的除数已经经过符号位判决模块分部分解处理和绝对化处理，因此，乘法运算处理后的数值不能简单作为高速除法器的最后结果，需要结合除数的符号位才能确定；当除数为正数的时候，乘法运算处理后的数值即为高速除法器的商；当除法为负数的时候，乘法运算处理后的数值的相反数才是高速除法器的商。

上述方法中，步骤(4)所述的倒数值查表模块根据上述非零bit位，并结合扩展N bit的数，组成一个数，将该数作为倒数值查表模块中的查找表的地址，查询该地址，获得该地址对应的倒数值；该倒数值的运算精度可以通过在步骤(3)中扩大或减少N的数值来提高或降低查找表的深度来控制，进而控制高速除法器的运算精度；也可以通过扩大或减少查找表的宽度，以加大或减少查找表中数据的位宽来控制，进而控制高速除法器的运算精度；也还可以将扩大或减少N的数值、扩大或减少查找表的宽度这两种处理方式结合起来，也即将提高或降低查找表的深度和以加大或减少查找表中数据的位宽结合起来，更好地控制该倒数值的运算精度，进而更好地控制高速除法器的运算精度。

上述方法中，步骤(6)所述乘法处理模块进行乘法运算处理的运算精度，可以通过控制乘法处理模块输入数据和输出的商的位宽来控制。

上述方法中，步骤(6)所述的乘法处理模块可以通过LUT、加法或是通过专用乘法模块实现。对于乘法运算，很多硬件电路是通过LUT实现，一些特殊的器件，还嵌入了专门的乘法处理模块，在实际应用中，都比较容易实现。

本发明的基本原理如下：为了获得除法运算后的结果 $\mathrm{Quotient}=\frac{\mathrm{Dividend}}{\mathrm{Divisor}},$ 将其除法运算转化为乘法运算，也即：

其中，abs(Divisor)表示Divisor的绝对值。由上式可知，为了实现除法运算，计算

的时候，先将Divisor进行分部分解处理，得到Divisor的符号位，再对Divisor进行绝对化处理得到abs(Divisor)，

通过对abs(Divisor)进行搜索、控制和查找表(具体操作如步骤(4)、(5)和(6))来获得。然后将和Dividend进行乘法运算，进而将乘法运算结果与步骤(2)所述Divisor的符号位结合起来，最后得到的结果即为商Quotient。

其中，倒数值

的运算精度可以通过查找表的深度和宽度来精确控制，该倒数值的运算精度也直接影响到商Quotient的精确度。乘法运算处理可以通过LUT、加法模块或是通过专用乘法模块实现。

本发明相对于现有技术具有以下优点：

(1)本发明的除法运算的精度可以根据要求任意控制和调整可以满足多种应用场合的要求；

(2)本发明避免了常规的移位、加减法运算，也避免近似拟合的处理思路，而直接采用查表和乘法的处理，大大减少了除法运算的时钟周期，简化了设计，适合硬件电路实现；

(3)本发明的除法运算基于乘法结构，确保高速除法器可以工作在高速时钟频率下，因此，适合高速数字信号处理场合；

(4)本发明一种高速除法器的结构简单，可行性好，易于设计和实现。

附图说明

图1是专利公开号CN1979411A的中国专利“一种高速除法器的实现方法与装置”的结构图；

图2是本发明一种高速除法器的结构示意图；

图3是本发明中的非零bit位搜索算法模块的工作流程图；

图4是本发明中修正调节模块对倒数值的修正调节处理的示意图

具体实施方式

下面结合实施例及附图，对本发明作进一步地详细说明，但本发明的实施方式不限于此。

实施例

本发明的基本原理如下：为了获得除法运算后的结果 $\mathrm{Quotient}=\frac{\mathrm{Dividend}}{\mathrm{Divisor}},$ 将其除法运算转化为乘法运算，也即：

其中，abs(Divisor)表示Divisor的绝对值。由上式可知，为了实现除法运算，计算

的时候，先将Divisor进行分部分解处理，得到Divisor的符号位，再对Divisor进行绝对化处理得到abs(Divisor)，

通过对abs(Divisor)进行搜索、控制和查找表(具体操作如步骤(4)、(5)和(6))来获得。然后将

和Dividend进行乘法运算，进而将乘法运算结果与步骤(2)所述Divisor的符号位结合起来(即进行乘法运算)，最后得到的结果即为商Quotient。

其中，倒数值

的运算精度可以通过查找表的深度和宽度来精确控制，该倒数值的运算精度也直接影响到商Quotient的精确度。乘法运算处理可以通过LUT、加法模块或是通过专用乘法模块实现。

图2所示为本发明的具体结构，一种高速除法器包括编码转换模块、符号位判决模块、非零bit位搜索模块、倒数值查表模块、修正调节模块和乘法处理模块，所述编码转换模块与符号位判决模块、非零bit位搜索模块、倒数值查表模块、修正调节模块和乘法处理模块依次连接，编码转换模块、符号位判决模块还分别与乘法处理模块相连接，乘法处理模块的输出端输出除法运算的结果。

利用上述高速除法器实现高速除法运算的方法，包括下述步骤：

(1)编码转换模块对特定数值(包括除数和被除数)分别进行码制转换处理，即将非二进制补码的除数、被除数分别转换为二进制补码编码的除数、被除数；由于编码的方式很多，有偏移码、二进制补码、二进制无极性码、1的补码等，在本发明中，编码转换模块将非二进制补码的数值转换为二进制补码编码的数值，以便于后续的运算处理；二进制补码的编码方式，对于数学运算非常有利，便于数字信号处理和运算，本发明的乘法运算处理也是基于二进制补码的编码方式的；

(2)根据如下处理“(Divisor的符号位)

”，可知，要计算出

的值，先要进行Divisor的符号位分离处理；因此，所述符号位判决模块对二进制补码编码的除数进行分部分解处理，确定分部分解处理后的二进制补码编码的除数的符号位即除数的正负情况，作为最后商的正负的参考准则；同时，对二进制补码编码的除数进行绝对化处理，以利于进行相应的搜索和查表等处理；

(3)所述非零bit位搜索模块是本发明中的一个重要组成部分，它主要确定了本发明中的除法运算的运算精度；由于经过绝对值化处理后的除数，已经转变为一个无符号数，其直接表现就是除数对应的倒数已经是一个非负数，因此，通过二进制码表示，其最高bit位已经是一个0；非零bit位搜索模块从最高bit位开始搜索绝对化处理后的除数的第一个非零bit位，同时记录该非零bit位，并从该非零bit位开始，扩展N bit的数作为步骤(4)中的查找表的深度参考，显然，N越大，相应的查找表深度越深，倒数值的运算精度也越高，这样就可以通过控制查找表的深度，来控制倒数值的运算精度，进而控制整个除法运算的精度；

图3是本发明中的非零bit位搜索算法模块的工作流程图。对于M bit的一个数，由于本发明中的符号位判决模块已经对除数进行了绝对值化处理，因此，对于M bit的数，其最高bit位是为0的，因此，从第M-1bit位开始搜索，直至搜索到第一个非零bit位，记录该bit位所对应的位置，便于后续的修正调节处理，搜索到第一个非零bit位之后，再扩展N bit的数。

(4)倒数值查表模块根据上述非零bit位，并结合扩展N bit的数，组成一个N+1bit的数，将该数作为倒数值查表模块中的查找表的地址，查询该地址，获得该地址对应的倒数值；因此，查找表中的数据要根据每个数A，在地址A存放对应的

数值，这样，以使得查表运算简单、容易控制和实现；

(5)修正调节模块对步骤(4)所述的倒数值进行修正调节处理，即对该倒数值进行相应的不同倍数的放大处理；由于对于不同的数A和B，其非零bit位的起始点是不同的，但其对应扩展的N bit数值是完全一样的，这样，直接查表后的数值，对于A和B来说都是一样的，显然，这个时候的数值是不对应于

和

因此，需要进行相应的修正调节处理，才能获得对应的

和

图4是修正调节模块对倒数值的修正调节处理的示意图。如图所示，对于同为11bit的A和B两个数，各自找到第一个非零bit位之后，同时扩展4bit，也即结合非零bit位，组成一个5bit的数值，由图可知，对于A和B来说，5bit数同为“10111”，因此，如果以“10111”作为查找表地址，得到对应的倒数值C，如果不加以修正处理，A和B得到的倒数值都为C，显然，这个结果是不正确的。因此，要结合A和B对应的非零bit位的起始点，对查表后得到的C值进行修正，也即进行不同倍数的放大处理，分别得到D和E，而修正后的D和E分别对应A和B的正确倒数值。具体的放大倍数，根据非零bit位的起始点，进行确定即可。

(6)乘法处理模块将输入数据，即输入的被除数与修正调节模块输入的倒数值进行乘法运算处理，并将乘法运算处理后的数值与步骤(2)所述除数的符号位结合起来，输出最后的商；也即，由于二进制补码编码的除数已经经过符号位判决模块分部分解处理和绝对化处理，因此，乘法运算处理后的数值不能简单作为高速除法器的最后结果，需要结合除数的符号位才能确定；当除数为正数的时候，乘法运算处理后的数值即为高速除法器的商；当除法为负数的时候，乘法运算处理后的数值的相反数才是高速除法器的商。

上述方法中，步骤(4)所述的倒数值查表模块根据上述非零bit位，并结合扩展N bit的数，组成一个数，将该数作为倒数值查表模块中的查找表的地址，查询该地址，获得该地址对应的倒数值；该倒数值的运算精度可以通过在步骤(3)中扩大或减少N的数值来提高或降低查找表的深度来控制，进而控制高速除法器的运算精度；也可以通过扩大或减少查找表的宽度，以加大或减少查找表中数据的位宽来控制，进而控制高速除法器的运算精度；也还可以将扩大或减少N的数值、扩大或减少查找表的宽度这两种处理方式结合起来，也即将提高或降低查找表的深度和以加大或减少查找表中数据的位宽结合起来，更好地控制该倒数值的运算精度，进而更好地控制高速除法器的运算精度。

上述方法中，步骤(6)所述乘法处理模块进行乘法运算处理的运算精度，可以通过控制乘法处理模块输入数据和输出的商的位宽来控制。

上述方法中，步骤(6)所述的乘法处理模块可以通过LUT、加法或是通过专用乘法模块实现。对于乘法运算，很多硬件电路是通过LUT实现，一些特殊的器件，还嵌入了专门的乘法处理模块，在实际应用中，都比较容易实现。

由上述方法可知，本发明除法运算的精度，主要受控于倒数值的运算精度以及乘法处理模块的运算精度，对于倒数值的运算精度，可以通过控制查找表的深度和宽带来实现对运算精度的控制，而乘法处理模块的运算精度，也可以通过控制乘法处理模块的位宽来控制，因此，本发明的除法运算的精度，可以根据需求，任意控制。

上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受上述实施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。

Claims (7)

1、一种高速除法器，其特征在于：包括编码转换模块、符号位判决模块、非零bit位搜索模块、倒数值查表模块、修正调节模块和乘法处理模块，所述编码转换模块与符号位判决模块、非零bit位搜索模块、倒数值查表模块、修正调节模块和乘法处理模块依次连接，编码转换模块、符号位判决模块还分别与乘法处理模块相连接。

2、一种利用权利要求1所述一种高速除法器实现高速除法运算的方法，其特征在于，包括下述步骤：

(1)编码转换模块对除数和被除数分别进行码制转换处理，即将非二进制补码的除数、被除数分别转换为二进制补码编码的除数、被除数；

(2)符号位判决模块对二进制补码编码的除数进行分部分解处理，确定分部分解处理后的二进制补码编码的除数的符号位，作为最后商的正负的参考准则；同时，对二进制补码编码的除数进行绝对化处理；

(3)非零bit位搜索模块从最高bit位开始搜索绝对化处理后的除数的第一个非零bit位，同时记录该非零bit位，并从该非零bit位开始扩展N bit的数；

(4)倒数值查表模块根据上述非零bit位，并结合扩展N bit的数，组成一个数，将该数作为倒数值查表模块中的查找表的地址，查询该地址，获得该地址对应的倒数值；

(5)修正调节模块对步骤(4)所述的倒数值进行修正调节处理，即对该倒数值进行相应的不同倍数的放大处理；

(6)乘法处理模块将输入数据，即输入的被除数与修正调节模块输入的倒数值进行乘法运算处理，并将乘法运算处理后的数值与步骤(2)所述除数的符号位结合起来，输出最后的商。

3、根据权利要求2所述的一种高速除法运算的方法，其特征在于：步骤(4)所述的倒数值的运算精度通过提高或降低查找表的深度来控制，查找表的深度通过在步骤(3)中扩大或减少N的数值来提高或降低。

4、根据权利要求2所述的一种高速除法运算的方法，其特征在于：步骤(4)所述的倒数值的运算精度通过加大或减少查找表中数据的位宽来控制，查找表中数据的位宽通过扩大或减少查找表的宽度来扩大或减少。

5、根据权利要求2所述的一种高速除法运算的方法，其特征在于：步骤(4)所述的倒数值的运算精度通过提高或降低查找表的深度与加大或减少查找表中数据的位宽相结合的方式来控制，其中，查找表的深度通过在步骤(3)扩大或减少N的数值来提高或降低，查找表中数据的位宽通过扩大或减少查找表的宽度来扩大或减少。

6、根据权利要求2所述的一种高速除法运算的方法，其特征在于：步骤(6)所述乘法处理模块进行乘法运算处理的运算精度通过控制乘法处理模块输入数据和输出的商的位宽来控制。

7、根据权利要求2所述的一种高速除法运算的方法，其特征在于：步骤(6)所述的乘法处理模块通过LUT、加法模块或专用乘法模块实现。

Images