CN1561478A - 用于有效的混和精度dsp的分割乘法器 - Google Patents

Abstract

给出了一种方法和结构，可利用该方法和结构来获得用于乘法资源有效的子字并行。在一个优选实施例中给出了一个双二元补码乘法器，这样n位操作数B可以被分割，并且该操作数B的每一部分并行地与另一操作数A相乘。其中间乘积和补偿向量在加法器中组合，以校正来自该乘法器的二元补码子积的任何错误负号，处理分割操作数B的最低有效位或者较低的p位，或者说B[p－1：0]，其中p＝n/2。补偿向量C是使用简单电路从A和B操作数中获得的。该技术可以被轻易扩展到3个或者更多个并行乘法器，在其上可分割n位操作数D，并且并行地与操作数A相乘。以和双二元补码乘法器实施例相似的方式，补偿向量C’可以从操作数D和A中相似地获得。

Description

用于有效的混和精度DSP的分割乘法器

技术领域

本发明涉及数字信号处理器(“DSP”)，并且更具体地涉及在数字信号处理ASIC实施方案中优化乘法运算。

发明背景

众所周知，对于混和了信号处理变量的定点精度的算法实施方案来说，可编程数字信号处理系统在资源和功耗方面的效率都很低。这种低效是因为需要使运算精度不同的所有共享硬件都适应最大的精度而造成的。换而言之，共享的硬件必须支持最大的必要精度。因而，当使用这种硬件来执行精度要求较低的运算时，会导致低效。

在固定的ASIC实施方案中，经常使精度最小化，以便提高硬件效率。最普遍的例子是用于数字地面电视接收(“ATSC8-VSB”)应用之残留边带的判决反馈均衡器，其中数据运算数是由4位判决符号组成的。对于该均衡器的前馈部分使用完全的12位软符号精度。前馈均衡器通常由16位系数的64个前向抽头组成，而反馈均衡器通常由16位系数的128个抽头组成。因此，当在ASIC的硬件中进行优化时，反馈计算需要128个4×16的乘法，而前馈计算需要64个12×16的乘法。因而需要映射到不同乘法器。然而，如果均衡器被映射到共享硬件的可编程系统，则需要把包括128个4×16乘法在内的所有运算都映射到同一12×16乘法器，因为它是唯一可用的乘法器。后一种情形将引入128个映射实例，而这比固定的ASIC中的映射实例多三倍，在每个反馈乘法运算期间，实际上浪费了可用硬件中的三分之二。

理论上，为了弥补这样的低效率，在某种程度上可以利用算术和存储资源中的子字并行来弥补这种低效映射。子字并行允许并行地提取多个操作数并对之运算，并且取决于可用的并行算术资源。例如，如果共享硬件被设计成用于实施12×16个乘法，则很容易将其改成同时实现3个并行的4×16乘法。或者，对于涉及一个全精度12位字的完全的12×16乘法，将该字分割到3个4×16乘法器上，并组合它们的中间结果。然而，在本例中，如果字被组合到一个全精度运算中，则算数资源应当可以被组合成一个全精度运算。尽管对于存储器和诸如加法器的简单单元来说，对于资源精度的分割和组合都非常简单，但是对于二元补码乘法器(two’s complement multiplier)来说却十分困难。诸如Booth或者Baugh-Wooley的标准的双补码乘法器把出现在最左边(MSB)的非零比特或符号、位置解释为表示一个负数。因此，在两个或者三个二元补码乘法器中的宽操作数分布(如图2中的结构所示)无法产生正确乘积。

因而，在本领域中所需要的是一种能够使用共享硬件来有效地实现不同精度的二元补码乘法的装置。

进一步，还需要一种装置，用于在二元补码乘法中，当把较大操作数映射到多个较小的并行乘法器上时能够获得正确结果。

发明概述

本发明寻求通过提出一种用于实现二元补码乘法分割的方法和结构来弥补现有技术的上述缺陷。因而，利用本发明所提供的方法和结构，就可以获得用于乘法资源的有效的子字并行程度。

在优选实施例中提出了一种双二元补码乘法器，这样可以分割n比特操作数B，并且操作数B的每一部分并行地同另一操作数A相乘。在一个加法器中将中间乘积与补偿向量组合，以便校正来自该乘法器的二元补码子积的任何错误负号，处理分割操作数B的最低有效的p位或者较低的p位，或者B[p-1：0]，其中p＝n/2。该补偿向量C是利用简单电路从A和B操作数中获得的。

本发明的技术很容易扩展到3个或者多个并行乘法器，在这些乘法器上分割n位操作数D，并使其并行地和操作数A相乘。以类似于双二元补码乘法器实施例的方式从D和A操作数中获得补偿向量C’。

附图简介

图1示出了并行运算并且共享一个操作数的两个m乘p的二元补码乘法器；

图2将一个操作数分配到两个m乘p的双补码乘法器中并且在输出加法器中组合子积；

图3示出了依照本发明优选实施例对图2的传统结构的改进；

图4更详细地示出了图3的系统；以及

图5示出了依照本发明用户获得补偿向量的示例电路。

优选实施例详述

本发明讨论了用于实现分割二元补码乘法器的方法，以便为乘法资源提供有效的子字并行程度。作为示例，希望双乘法器的配置可以实现如图1所示的较低精度的两个并行运算。并且希望这些相同的乘法器能够支持一个全精度运算，如图2中所示。

对于以上讨论的VSB DFE实例，三个4×16乘法器阵列可以提供3个同时的乘法，或者一个12×16的乘法。因此，这种分割乘法器是实现资源和功耗有效的共享硬件的可编程资源的重要工具。

以下将就两个单独的二元补码乘法器的情形来讨论分割乘法器的实现方法。参照图1，两个m乘p的二元补码乘法器101和102使用单个共享的m位系数A来实现并行乘法，并行地将A同B和C相乘，产生B×A的乘积P1和C×A的乘积P0。这种乘法可用于以上讨论的情形中的两个较低精度的乘法。

图2示例了在两个乘法器上分割更高精度乘法的情形。图2示出了试图将单个n位操作数分布于两个相同的m×p乘法器201和202上，然后在输出加法器203中组合子积，从而组成乘积。在所描述的情形中，因为操作数B的第p-1位被解释为更低阶乘法器201中的二元补码符号位，因此不能得到正确的乘积。

正确的方法是如图3中所示的那样地、在两个乘法器上分割操作数B。在图3中，通过把补偿向量310和两个乘法子积320以及321一起添加到最终的乘积相加中来获得正确结果。该补偿向量是使用简单电路而从操作数A和B中获得的。在图5中描述了一个这样的电路例子。以下将就两个和三个乘法器的情形来解释操作数A和B以及补偿向量C之间的解析关系，并且也可以按照希望而容易地从这种情形扩展到更多的乘法器。

补偿向量可以用如下的方式添加到乘积上：(1)子积组合加法器之后的附加加法器(未示出)；(2)子积组合加法器303中的附加端口(图3所示的实施方式)；或者(3)每一个二元补码乘法器面板的一个附加行(未示出)。

进而，分割乘法器可以被实施为两个独立的二元补码乘法器面板(panel)，其具有单个分割加法器用以形成最终的结果。通过利用任意一种所述的设计选择，在此所示的分割乘法器结构都不会产生明显的门延时损失。

对于VSB DFE中所期望的3到1乘法器情形，如下所述地类似得出，由于两个乘法器的情形可以确定用于将这3个二元补码乘法器合并为一个组合乘法器所需的补偿向量。为了示例的目的，接下来描述用于将两个单独的乘法器合并为一个而获得补偿向量的方式。

在双补码格式中的操作数被表示如下：

$A=-a_{m-1}{2}^{m-1}+\underset{i=0}{\overset{m-i}{\mathrm{\Σ}}}{a}_i{2}^i$

等式1

注意最高有效位(符号)是负值。

m乘n个乘数a_m和b_n的乘积被表示为：

$P_{\mathrm{ab}}=[-a_{m-1}{2}^{m-1}+\underset{i=0}{\overset{m-2}{\mathrm{\Σ}}}{a}_i{2}^i]\×[-b_{n-1}{2}^{n-1}+\underset{j=0}{\overset{n-2}{\mathrm{\Σ}}}{b}_j{2}^j]$

$=a_{m-1}{b}_{n-1}{2}^{m+n-2}-a_{m-1}\underset{j=0}{\overset{n-2}{\mathrm{\Σ}}}{b}_j{2}^{m+j-1}-b_{n-1}\underset{i=0}{\overset{m-2}{\mathrm{\Σ}}}{a}_i{2}^{m+i-1}+\underset{i=0}{\overset{m-2}{\mathrm{\Σ}}}\underset{j=0}{\overset{n-2}{\mathrm{\Σ}}}{a}_i{b}_j{2}^{i+j}$

$=\left(1\right)+\left(2\right)+\left(3\right)+\left(4\right)$

等式2

下面解释分割的n位乘数B，低阶乘法器中的双m乘p的补码乘法器将该段的最高有效位解释为符号位，如下：

$B=-b_{n-1}{2}^{n-1}+\underset{j=p}{\overset{n-2}{\mathrm{\Σ}}}{b}_j{2}^j+\underset{k=0}{\overset{p-1}{\mathrm{\Σ}}}{b}_k{2}^k\⇒-b_{n-1}{2}^{n-1}+\underset{j=p}{\overset{n-2}{\mathrm{\Σ}}}{b}_j{2}^j-b_{p-1}{2}^{p-1}+\underset{k=0}{\overset{p-2}{\mathrm{\Σ}}}{b}_k{2}^k$

等式3

用3来置换2得到等式4，如下：

$P_{\mathrm{ab}}^{\′}=[-a_{m-1}{2}^{m-1}+\underset{i=0}{\overset{m-2}{\mathrm{\Σ}}}{a}_i{2}^i]\×[-b_{n-1}{2}^{n-1}+\underset{j=p}{\overset{n-2}{\mathrm{\Σ}}}{b}_j{2}^j-b_{p-1}{2}^{p-1}+\underset{k=0}{\overset{p-2}{\mathrm{\Σ}}}{b}_k{2}^k]$

$=a_{m-1}{b}_{n-1}{2}^{m+n-2}$

$-a_{m-1}\{\underset{j=p}{\overset{n-2}{\mathrm{\Σ}}}{b}_j{2}^{m+j-1}-b_{p-1}{2}^{m+p-2}+\underset{j=0}{\overset{p-2}{\mathrm{\Σ}}}{b}_k{2}^{m+j-1}\}$

$-b_{n-1}\underset{i=0}{\overset{m-2}{\mathrm{\Σ}}}{a}_i{2}^{n+i-1}$

$+\underset{i=0}{\overset{m-2}{\mathrm{\Σ}}}\underset{j=p}{\overset{n-2}{\mathrm{\Σ}}}{a}_i{b}_j{2}^{i+j}+\underset{i=0}{\overset{m-2}{\mathrm{\Σ}}}\underset{j=0}{\overset{p-2}{\mathrm{\Σ}}}{a}_i{b}_j{2}^{i+j}-b_{p-1}\underset{i=0}{\overset{m-2}{\mathrm{\Σ}}}{a}_i{2}^{p+i-1}$

等式4

比较4与2，可以得到补偿项，如等式5中所示：

$P_{\mathrm{ab}}^{\′}=\left(1\right)+\left(3\right)$

$+\left(2\right)+2a_{m-1}{b}_{p-1}{2}^{m+p-2}$

$+\left(4\right)-2b_{p-1}\underset{i=0}{\overset{m-2}{\mathrm{\Σ}}}{a}_i{2}^{p+i-1}$

$=P_{\mathrm{ab}}+a_{m-1}{b}_{p-1}{2}^{m+p-1}-b_{p-1}\underset{i=0}{\overset{m-2}{\mathrm{\Σ}}}{a}_i{2}^{p+i}$

$=P_{\mathrm{ab}}-\mathrm{compensation}$

等式5

其中的compensation(补偿)由等式6给出。

$\mathrm{compensation}=b_{p-1}[-a_{m-1}{2}^{m+p-1}+\underset{i=0}{\overset{m-2}{\mathrm{\Σ}}}{a}_i{2}^{p+i}]$

等式6

如果乘数B的MSB(b_p-1)等于0，则只是简单地等于0，或者说如果b_p-1＝0，则compensation＝0。

使用正项来替换6中的负项可以获得

$-a_{m-1}{2}^{m+p-1}=a_{m-1}\{\left(\underset{m+p}{\overset{m+n-2}{\mathrm{\Σ}}}{2}^i\right)+0*2^{m+p-1}+\left(\underset{0}{\overset{m+p-2}{\mathrm{\Σ}}}{2}^i\right)+1\}.$

$=a_{m-1}\left(\underset{m+p-1}{\overset{m+1-2}{\mathrm{\Σ}}}{2}^i\right)$

等式7

最后，补偿向量是符号扩展的A乘数，左移p位(子乘法器的宽度)，如等式8所示。补偿向量只是被施加到非零的错误符号b_p-1。因而，必须使用硬件对p-1位置上的非零位进行简单检查。如果该位是1，则补偿向量被添加到最终的加法器。

$P_{\mathrm{ab}}=P_{\mathrm{ab}}^{\′}+b_{p-1}\{a_{m-1}\underset{m+p-1}{\overset{m+n-2}{\mathrm{\Σ}}}{2}^i+\underset{0}{\overset{m+p-2}{\mathrm{\Σ}}}{a}_i{2}^{p+i}\}$

等式8

图4因而示出了本发明完整的两个加法器的实施方式，示出了(如前)两个乘法器401和402以及加法器。乘数B被分割到两个乘法器401和402上，在加法器403中，中间乘积411和412被加在一起获得正确的乘积450。如上所述，如果乘数B的第p-1位是0，则补偿向量也是0。

接下来，为了完整起见，给出了3个操作数情形下的补偿向量的取得方式。

$B=-b_{n-1}{2}^{n-1}+\underset{j=p}{\overset{n-2}{\mathrm{\Σ}}}{b}_j{2}^j+\underset{k=0}{\overset{p-1}{\mathrm{\Σ}}}{b}_k{2}^k+\underset{l=0}{\overset{q-1}{\mathrm{\Σ}}}{b}_l{2}^l$

$\⇒-b_{n-1}{2}^{n-1}+\underset{j=p}{\overset{n-2}{\mathrm{\Σ}}}{b}_j{2}^j-b_{p-1}{2}^{p-1}+\underset{k=0}{\overset{p-2}{\mathrm{\Σ}}}{b}_k{2}^k-b_{q-1}{2}^{q-1}+\underset{l=0}{\overset{q-2}{\mathrm{\Σ}}}{b}_l{2}^l$

等式9

使用和2路分割取得相似的方式，用以上的等式1乘以等式9来获得扩展乘积。比较该等式的12项得到合并的乘法器(等式2)，以获得：

$P_{\mathrm{ab}}^{\′}=\left(1\right)+\left(3\right)$

$+\left(2\right)+2a_{m-1}{b}_{p-1}{2}^{m+p-2}+2a_{m-1}{b}_{q-1}{2}^{m+q-2}$

$+\left(4\right)-2b_{p-1}\underset{i=0}{\overset{m-2}{\mathrm{\Σ}}}{a}_i{2}^{p+i-1}-2b_{q-1}\underset{i=0}{\overset{m-2}{\mathrm{\Σ}}}{a}_i{2}^{q+i-1}$

$=P_{\mathrm{ab}}+a_{m-1}{b}_{p-1}{2}^{m+p-1}-b_{p-1}\underset{i=0}{\overset{m-2}{\mathrm{\Σ}}}{a}_i{2}^{p+i}+a_{m-1}{b}_{q-1}{2}^{m+q-1}-b_{q-1}\underset{i=0}{\overset{m-2}{\mathrm{\Σ}}}{a}_i{2}^{q+i}$

$=P_{\mathrm{ab}}-\mathrm{compensation}\left(p\right)-\mathrm{compensation}\left(q\right)$

等式10

其中对于每个补偿项：

$\mathrm{compensation}\left(x\right)=b_{x-1}[-a_{m-1}{2}^{m+x-1}+\underset{i=0}{\overset{m-2}{\mathrm{\Σ}}}{a}_i{2}^{x+i}]$

$=b_{x-1}\{a_{m-1}\underset{m+x-1}{\overset{m+n-2}{\mathrm{\Σ}}}{2}^i+\underset{0}{\overset{m+x-2}{\mathrm{\Σ}}}{a}_i{2}^{x+i}\}$

$=b_{x-1}{2}^x\mathrm{sext}\left(A\right)$

等式11

一般来说，为了为每个操作数在二元补码乘法器面板中引入分割，我们必须增加一个校正项(等式11)到来自每一个面板的部分和的相加中。该校正项只是正交于该分割的乘数(操作数不被分割)，经过符号扩展、在分割的操作数中与错误符号位相乘，然后移位，使得校正值的LSB被添加到由面板的上半部分所引入的部分和中。这种分割可以被分别沿每个操作数引入，从而允许乘法器的任意划分。操作数的每个分割都需要一个补偿向量，以用于校正最后乘积。

一般来说，沿着一个轴，对于乘法器的每个划分都有一个补偿向量。例如，如果每个乘数被分割一次(构成4个面板的乘法器)，则需要两个补偿向量。

尽管以上描述了本发明的优选实施例，但是本领域技术人员可以利用各种修改和变化，诸如，将本发明扩展为在许多乘法器上分割乘数，因而允许在同样的共享硬件中以各种级别的精度来实现乘法。此外，也可以很容易地实现把补偿向量加到最终加法器中的该示例方法的变体的使用。这些修改被预定由附加的权利要求所覆盖。

Claims (16)

1.一种利用子字并行来实现二元补码乘法的方法，包括：

在多个乘法器(401，402)之间分割第一操作数B，并且将它们中的每一个与第二乘数A相乘；以及

把中间乘积(411，412)和补偿向量(410)相加(403)以获得最终乘积。

2.权利要求1的方法，其中乘法器(401，402)具有相等的宽度。

3.权利要求2的方法，其中补偿向量(410)是：

零，其前提是如果没有错误符号位被引入到该分割操作数B的给定片断的MSB；以及

符号扩展的第二乘数A，其左移了该较低分割乘法器(410)的宽度。

4.权利要求1的方法，其中补偿向量按照以下方式之一添加：

不同于中间乘积相加的其他加法；

与中间乘积相加(403)同时；或者

与并行乘法同时。

5.权利要求1-4中任意一个的方法，该方法被用于在相同的共享硬件上实施不同精度的乘法。

6.权利要求5的方法，其中乘法器(401，402)的数目是2或者3。

7. 一种能够实现多精度二元补码乘法的集成电路，包括：

两个子乘法器(401，402)；

加法器(403)，以及

用于产生补偿向量的电路(图5)。

8.权利要求7的电路，还附加包括一个用于测试子乘法器的乘数的MSB中的非零符号位的电路。

9.权利要求8的电路，其中附加的电路控制补偿向量的值。

10.权利要求7-9中任意一个的电路，其中补偿向量(410)通过以下方式之一添加：

不同于中间乘积加法器的附加加法器；

中间乘积加法器(403)中的附加端口；或者

在二元补码乘法面板中的附加行。

11.一种能够实现多精度二元补码乘法的集成电路，包括：

N个子乘法器(401，402)；

加法器(403)；以及

用于产生补偿向量的电路(图5)。

12.权利要求11的电路，还附加包括用于测试每个子乘法器(401)的一个乘数的MSB中的非零符号位的电路。

13.权利要求12的电路，其中附加的电路控制补偿向量的值。

14.权利要求11-13中任意一个的电路，其中补偿向量通过以下方式之一添加：

不同于中间乘积加法器的附加加法器；

中间乘积加法器(403)中的附加端口；或者

在二元补码乘法面板中的附加行。

15.权利要求14的电路，其中沿一个轴对于该乘法器的每一分区都有一个补偿向量(410)。

16.权利要求5的方法，其中沿一个轴对于该乘法器的每一分区都有一个补偿向量(410)。

Images