常系数乘法器的进化生成

《常系数乘法器的进化生成》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、25常系数乘法器的进化生成Graph-BasedEvolutionaryDesignofHigh-SpeedConstant~CoefficientMultipliers巫庆邮电学院温平川殷茜（車庆630065）»S：文章提出了一种十分有效的墓于图进化的优化技术，并成功地廉央了16•比特常系数乘宏器的设计问题。实驶结果充分表明，在大部分情形下•通过进化技术自动生成的乘法器的性能胜过使用常规的计算算术算法设计的乘法器。这项研究同时也充分表明，我们提出的慕于图的进化技术舵够有效地简化和加速计算算术电路的设什过程。关績洞：进化计算.算术电路,数字信号处理•电子

2、设计自动化如何将要解决的问的解有效地编码成一个染1引言目前.电子电路的设计是一件费时、复杂的工作C设计人员通常需要掌握许多有关电路设计方面的规范。而且•每设计一个电路时、设计人员还要经过设计、测试、调试等多道程序的反复c一般地说,设计的产品质量与设计人员的知识经验有着密切关系。为了简化和加速电路的设计过程，最近，一些研究人员利用进化技术探讨电子电路设计的可能性。例如:在文献［1］中，Miller等人成功使用遗传算法荻得了满意的算术电路c这项研究后来被称为“进化硬件”3和。它的突出优点在于能够获得超过常规设计空间意想不到的解。高速数字乘法器是数字信号处理芯

3、片里基本电路元件。然而、乘法器与加法器相比，由于存在大量部分积的求和而导致信号处理延迟。特别对于实时信号处理•这种延迟是不能接受的。因此•设计高速有效的乘法器是当前电路设计的人员最关心的话题之一。目前.有许多常见方法来设计并改进由简单移位器(shifter)和加法器(adder)构成并采用CSD(CanonicSigned-Digit)数字表示的乘法器(八"。例如,BoothsH法、或使用快速的加法器F'SAfFinalStageAdders)©最近.在文献⑻中、Higuchi等人提出通过SW(Signed-Weight)3-2Counter和Shift

4、er来构造CSD乘法器。这似乎是目前设计高速常系数乘法器的最佳途径。本文采用基于图的进化技术成功地设计16-比特的由SW3-2Counter和Shifter作为基本元件的CSD乘法器、并对基于卄算算法设计的同样由SW3-2Counter和Shifter构造的CSD乘法器进行了比校。收稿日期:2001-03-12基金项目；恵庆市科委应用基础基金资助项目2问题编码色体是实现进化计算的关键话题之一。目前，在进化硬件领域，存在许多不同的编码方案(―山。例如:在文献【11中.描述了一个算术电路进化设计编码方案，但是，这种方法是以门级器件(例如：与门、或门、非门等等

5、)作为基本元器件来进化电路C采用这种编码方案,Miller等人完成了对2-比特和3-比特乘法器的设计•但没有给出16-比特或更复杂的乘法器。我们以Higuchi提岀SW-Counter和Shifter作为基本元器件来构造16-比特的乘法器。显然,Miller等人的基于门级元件编码方案对解决我们的问题不太适用。因此■我们提出了进化图生成EGG(EvolutionaryGraphGeneration)方法。在这种方法中、一个电路图G被定义成G=(N(G).D(O)形式＜这里N(G)是结点集合・D(G)是有向边集合c在结点集合里、主要有两种不同的结点，即功能结

6、点和输人/输出结点c每一个结点有一个自己的功能名称和输入/输出端子c我们假定每一个有向边必须连接一个结点的输出端子与另一个结点的辙入端子，并且每一个输入/输出端子有且仅只有一个有向边相连实际上.我们可以把这样一个电路图看成一个基于CSD数字表示的乘法器的数据流图。有向边表示数据的相关性。结点表示一个抬定的算术操作。因此.结点本身起初不含有电路细节。只有当所有输入操作数的性质确定后，电路图才能被转换成比特级电路元件集合。所以，电路图中结点的实际含义依赖于数据流图的整个结构。例如:图1(a)表示了一个3-input,2-input,counter结点。符号

7、

8、MSD:ISD］表示活性数字的范围。这里MSD(theMostSignificantactiveDigit)是最多有意义的活性数字，LSD(theLeastSignificantactiveDigit)是最少有意义的活性数字。每一个结点有一个生成对应的比特级电路规则C表1表示了这个3-2counter规范c使用这个规则，图13)可以被•转换成图1(b)描述的电路图c为更好理無这一点.图2(a)给岀了一个完整的数据流图•假定有4-bit无符号二进制数到输人结点.这个电路图可以转换成图2(b)形式c表丨3-2counter结点的位操作输人号码位操作04>1W

9、ire2HA(HalfAdder)3FA(FullAdder)20一a®>-JV