用于完成乘法运算的方法、系统和设备的制作方法.docx

用于完成乘法运算的方法、系统和设备的制作方法专利名称：用于完成乘法运算的方法、系统和设备的制作方法技术领域：本发明涉及一种用于以流水线方式完成一个乘法运算和另一个乘法运算的方法，其中，在完成所述一个乘法运算之前开始所述另一个乘法运算，将所述乘法运算分成至少第一子运算和第二子运算，在一个流水线级执行每个所述第一和第二子运算本发明也涉及一种用于以流水线方式完成一个乘法运算和另一个乘法运算的设备，该设备包括用于将乘法运算分成至少第一子运算和第二子运算的装置，将每一个所述第一和第二子运算设置成在一个流水线级内执行本发明也涉及一种包含用于以流水线方式完成一个乘法运算和另一个乘法运算的装置的无线终端，其包括用于将该乘法运算分成至少第一子运算和第二子运算的装置，将每个所述第一和第二子运算设置成在一个流水线级中执行本发明进一步涉及一种用于以流水线方式完成一个乘法运算和另一个乘法运算的系统，该系统包括用于将该乘法运算分成至少第一子运算和第二子运算的装置，将每个所述第一和第二子运算设置成在一个流水线级中执行背景技术： 存在着许多其中需要乘法和/或相乘累加(MAC)运算的应用作为一个非限制性的例子，如数字信号滤波应用、视频/图像处理应用等等这样的许多信号处理应用就是其中实现了实时乘法运算的应用。

其中需要向量和/或矩阵运算的其他应用也利用了乘法和/或MAC运算通常将乘法运算实现为求和及逐位移位运算由于两个操作数间的一次乘法运算需要许多次求和及移位运算以计算乘法结果，因此这种乘法运算是资源需求作业尤其是视频/图像处理算法是不得不实时实现的巨大量计算因此，高速性能已经成为发展用于不同视频/图像处理算法或者子作业的并行专门化结构(加速器)中的推动力一个现有技术的视频/图像处理系统包括几个这种加速器(如绝对差求和(SAD)，余弦变换等等)，其中每个由大量的硬件元件组成，然而，随着移动通信系统的发展，该影响系统成本的硬件领域以及功率/能量消耗成为了与高速性能同等重要的性能对于满足所有这些准则的一种方法是进一步现代化数字信号处理器(DSP)并降低专用加速器的数目虽然在这个领域存在着一些改进，但是所开发的系统仍然不能总是满足高速及功率消耗的需要用于视频及图像处理及其他信号处理作业的现有技术体系通常以传统乘法器结构为基础已经开发出了用于实现乘法和/或相乘累加运算的许多乘法方法以及相当多种类的设备在下文中，仅考虑两个操作数(被乘数及乘数)均未知的情况的乘法方法及通用乘法器结构、存在于二进制补码运算的两个定点带符号整数乘法以及所谓的以T为基数的(radix-T)方法。

分别地将n位(包括符号)乘数a的二进制补码表示描述成a~=an-1an-2···a1a0,]]>以及将m位(包括符号)被乘数x的补码表示表示成x~=xm-1xm-2···x1x0.]]>a和 之间的关系(以及x和 之间的类似关系)如下a=-an-12n-1+Σr=0n-2ar2r,x=-xm-12m-1+Σl=0m-2xl2l.···(1)]]>在radix-T并行乘法方法中，根据以下公式而获得乘积y＝a·x的二进制补码y~=Σr=0nradix-T-1(Arx)2rtradix-T···(2)]]>在以下两个主要步骤中步骤1.产生部分乘积(PP)Ar·x，r＝0，...，nradix-T-1以便等式(2)有效。

步骤2.并行相加所有的部分乘积，将第r个部分乘积Ar·x，r＝0，...，nradix-T-1预先向左移位rtradix-T个位置radix-T MAC单元以类似的方式进行运算，不同之处在于在步骤2将另一个数(累加项)与部分乘积加在一起现在更详细地考虑步骤1取决于怎样定义和获得数字Ar·x，r＝0，...，nradix-T-1可以导出不同的乘法方法接着，事实上由乘数a的表示而指定数字Ar·x，r＝0，...，nradix-T-1的选择最简单的乘法方法是radix-2方法，其利用了等式(1)左侧给出的a的基本二进制补码表示在这个情况中，通过下述公式而获得乘积的二进制补码y~=Σr=0nradix-2-1(Arx)2rtradix-2=Σr=0n-2(arx)2r-(an-1x)2n-1,···(3)]]>即，nradix-2＝n，以及由Ar＝ar，其中r＝0，...，n-2以及An-1＝-an-1，其中r＝n-1而定义了部分乘积Ar·x，r＝0，...，n-1可利用乘数 和被乘数 的每个二进制补码位之间的两输入端AND门阵列而简单地(并且通常地)形成这些部分乘积。

在第二步的累加之前Ar·x，r＝0，...，n-1的值乘以2r(即向左移动r位)应当注意的是在这个方法中，与其他部分乘积不同的方式来处理有时也称作是校正因数的该部分乘积An-1·x在另一个radix-2乘法方法中，根据将该乘数的二进制补码位 作Booth重编码成冗余带符号数字，由此避免了部分乘积的不均匀性现在由下述公式而给出该乘积y~=Σr=0nradix-2-1(Arx)2r=Σr=0n-1(-ar+ar-1)x2r,a-1=0···(4)]]>即如前所述，nradix-2＝n，但是部分乘积Ar·x，r＝0，...，n-1现在全部由Ar＝-ar+ar-1而定义与前述方法类似，在第二步将其相加之前将Ar·x，r＝0，...，n-1的值乘以2r在这个方案中，在0，±x之间选择部分乘积这些值(0和x)中的两个是可容易地利用的，而得到-x需要对 的位求反并加1通常，在其中对部分乘积进行求和的步骤2中完成加1不管是否采用Booth重编码或非编码方法，在radix-2乘法方法中共有nradix-2＝n个部分乘积要被求和。

为了降低部分乘积的数目并因此而降低第二级的延迟(累加部分乘积)，已经开发了基于改进Booth算法(MBA)的radix-4方法MBA可能是最普及的乘法方法，并且正在被广泛地研究和最佳化在MBA中通过nradix-4＝n/2个部分乘积的和y~=Σr=0nradix-4-1(Arx)22r=Σr=0n/2-1([-2a2r+1+a2r+a2r-1]x)22r,···(5)]]>a-1=0而获得乘积的二进制补码，其中根据乘数 的二进制补码表示的三个连续位a2r+1、a2r、a2r-1(a-1＝0)而选定Ar∈{-2，-1，0，1，2}，r＝0，1，...，n/2-1的值在步骤2相加之前用22r来乘以该部分乘积(即硬件向左移动2r位)Ar·x，r＝0，...，n/2-1为了简化以下公式，在其中存在象n/k这样的项的每种情况中，假定n是k的整数倍由于可根据任意数目的位(重复最高有效位)而对二进制补码数求补码，因而这是一个有效的假定图1呈现了通常的改进Booth算法101有n/2个Booth编-解码行，其中每行包含一个Booth编码器102和m+1个Booth解码器103，所述编码器和解码器可以两个为一组。

每个Booth编码器102分析乘数 的二进制补码的三个连续位，包括一位重叠，并向相应的行解码器103输出q个信号在一些最近的现有技术设计中，q的值＝3根据这q个信号，解码器行在其输入端形成具有被乘数的位 的部分乘积(Arx)∈{0，±x，±2x}由于是通过硬件移位形成了2x，因而x的非负倍数可容易地获得通过将x的相应正倍数的位求反并接着加1而形成x的负倍数，这通常在步骤2中完成例如，美国专利US6173304描述了一种实现Booth编码器和解码器的这种系统在radix-2方法中可以比在改进Booth算法中更容易得到部分乘积，但是当采用改进Booth算法时将部分乘积的数目减小到n/2其导致了在速度性能、面积及功率消耗中的显著优势为了进一步减小部分乘积的数目，将Booth编码进一步扩展到多位(以任意T为基数)重编码现在给出该乘积的通用方程y~=Σr=0nradix-T-1(Arx)2rt=Σr=0n/t-1([-atr+t-12t-1+Σi=0t-2atr+i2i+atr-1]x)2tr···(6)]]>a-1＝0，T=2t=2tradix-T.]]>即，存在着nradix-T＝n/t个部分乘积(T＝2t)并且根据来自可能的部分乘积Ax(A的范围在-2t-1到2t-1之间)列表中的乘数 的t+1个连续位而选择每个部分乘积。

可通过两个(对于T＝8，16)或更多个(T＞16)2的x次幂的加法，以及可能地通过将位求反并加1而相对容易地形成每个可能的部分乘积(步骤2)例如，在radix-8重编码的情况中，可能的部分乘积的列表是0，±x，±2x，±3x，±4x除3x可通过一次加法3x＝x+2x而获得之外这个列表中的所有非负倍数均可容易的得到如前所述，可通过求反加1的方法而得到负的倍数在radix-16重编码的情况中，可能的部分乘积的列表是0，±x，±2x，±3x，...，±8x，所有这些均可通过实现三个独立的加法/减法以便得到3x＝x+2x，5x＝x+4x，7x＝-x+8x而可以得到可通过将3x向左移一位而得到可能的部分乘积6x然而，对于更高基数的情况，一些可能的部分乘积(如11x和13x)不能在一次加法/减法中得到图2呈现了现有技术的radix-T(T≥8)多位Booth重编码(基数高于4)乘法器的通用结构201这个结构包括用于计算可能的部分乘积的列表0，±x，±2x，...，±Tx的加法器阵列202、用于根据乘数位而选择n/t个部分乘积的选择模块203、和用于将所选择的部分乘积求和的求和模块204最后加法器205从由求和模块204中所产生的和S以及进位C项而形成乘积 典型的现有技术基数高于4乘法器的加法器阵列包括与包含在可能的部分乘积列表中的x的正奇数倍数一样多的加法器(在T＝8的情况中是1，在T＝16的情况中是3等等)。

通常，由于形成该可能的部分乘积列表是这种乘法器相当费时间的部分，因而采用快速-超前进位(CLA)加法器在专利US5875125中，提出了一种可用在radix-8乘法器中的专门的x+2x加法器值得注意的是也提出了混合的radix-4/radix-8乘法器，例如在美国专利号4965762中，然而，其主要对其中串行产生并累加可能的部分乘积的迭代(非并行)乘法器有用美国专利号5646877描述了一种乘法器结构，其中对于任意基数的可能的部分乘积均是作为加法器阵列内3x及x移位方案的和或差而得到的，该阵列包括一个用于产生3x的x+2x加法器、两个移位器和一个加法器/减法器典型现有技术以高于4为基数的乘法器的选择模块203包括n/t个radix-T Booth编码器和相等数目的解码器行根据由该解码器行所形成的相应部分乘积，每个编码器分析乘数的相应(t+1)个字节组并输出多个控制信号例如，在专利US6240438中给出了对如何将radix-TBoot。