基于粒子群优化算法的RM电路最佳极性搜索.doc

编号： 本科毕业设计（论文） 题目：（中文）基于粒子群优化算法的RM电路最佳极 性搜索 （英文）Particle swarm optimization algorithm based on RM circuit searching the be best polarity 学 院 专 业 班 级 学 号 姓名 指导教师 职称 完成日期 宁波大学信息科学与工程学院本科毕业设计诚 信 承 诺我谨在此承诺：本人所写的毕业论文基于粒子群优化算法的RM电路最佳极性搜索均系本人独立完成，没有抄袭行为，凡涉及其他作者的观点和材料，均作了注释，若有不实，后果由本人承担。 承诺人（签名）： 摘要【摘要】低功耗设计技术是是当前集成电路逻辑层综合设计和优化的一项重要内容。通过结合粒子群优化算法进行RM电路最佳极性的搜索。本文通过对离散粒子群优化算法、XNOR/OR逻辑表达式、信号概率传递算法和利用快速列表法的极性转换算法的研究，提出了一种基于XNOR/OR逻辑的低功耗最佳极性搜索算法。首先，根据混合极性XNOR/OR展开式的特点，改进快速列表技术并将其应用于混合极性XNOR/OR展开式的转换；然后，通过离散二值PSO算法和机率转换法则，得到离散三值粒子群优化（Discrete Ternary Particle Swarm Optimization, DTPSO）算法，并将DTPSO应用于MPRM电路的最佳极性搜索中，实现混合极性XNOR/OR电路功耗和面积最小化；最后，通过实验验证该算法具有更快的收敛速度和更好的寻优效率。【关键词】 RM逻辑；粒子群优化算法；极性搜索；低功耗。Particle swarm optimization algorithm based on RM circuit searching the be best polarity Abstract【ABSTRACT】 Low-power integrated circuit design technology is the logical layer of the current integrated design and optimization is an important content.By combining particle swarm optimization algorithm to search the best polarity RM circuit.Based on the discrete particle swarm optimization, XNOR / OR logic expressions, the probability of passing the signal list of algorithms and the use of rapid methods of polarity algorithm is proposed based on XNOR / OR logic polarity of the best low-power search algorithm.First, according to the mixed polarity of XNOR / OR expansions characteristics, improved technology and apply it to the list quickly mixed polarity XNOR / OR expansions of the conversion;Then, with discrete binary PSO algorithm and the probability of conversion rules, proposed three-valued discrete particle swarm optimization (Discrete Ternary Particle Swarm Optimization, DTPSO) algorithm, and DTPSO used MPRM search the best polarity circuit to achieve the mixed polarity XNOR / OR circuit to minimize power and area;Finally, experimental verification of the algorithm has faster convergence speed and better optimization efficiency.【KEYWORDS】 RM Logic; Particle Swarm Optimization; Polarity Searching;Low Power.目录摘要IIAbstractIII1绪论11.1选题背景和意义11.2课题的基本内容11.2.1研究对象11.2.2拟解决的问题22 Reed-Muller电路的逻辑展开式32.1 固定极性RM展开式32.1.1 XNOR/OR展开式32.1.2 XOR/AND展开式32.2 混合极性RM展开式32.2.1 XNOR/OR展开式32.2.2 XOR/AND展开式43 粒子群优化算法63.1 基本的粒子群算法63.1.1 粒子群算法63.1.2 粒子群算法的原理63.1.3 粒子群算法的流程73.2 改进的粒子群算法（离散三值粒子群优化（TPSO）算法 ）74 XNOR/OR电路的混合极性转换94.1 基于快速列表法混合极性转换95 基于PSO的XNOR/OR电路低功耗最佳极性搜索115.1 XNOR/OR电路功耗优化115.1.1 基于信号概率传递的CMOS电路功耗模型115.2 多输入OR门低功耗优化125.3 多输入XNOR门低功耗优化135.3.1 动态逻辑的多输入XNOR门低功耗优化145.3.2 静态逻辑的多输入XNOR门低功耗优化155.4 TPSO算法在混合极性XNOR/OR电路上的应用175.4.1 编码和适应度函数175.4.2 速度和位置更新185.4.3 算法描述185.4.4 实验结果及分析206 总结236.1 论文结论236.2 展望23参考文献24致谢25附录26241 绪论1.1选题背景和意义随着社会的发展，现代社会中发展最快的产业是信息产业。随着国民经济的增长和人民生活水平的不断提高，越来越多的电子产品被开发。而在各种电子产品中起着重要作用的是集成电路。迎来电子科技的飞速进步，让集成电路运行起来的工作效率是也越来越速度，然而我们的集成电路的集成度要求也是越来越高，这引起了我们工作的电路的功耗飞速递增和集成电路集成面积的递增。随着电路功耗的递增，让各种电子产品在工作的时候，遇到各种各样的问题，例如：电子产品中的集成电路芯片因为工作的速度引起芯片的产生太多热量容易让芯片的使用年限缩短和造成它们工作的效率，也会让集成电路的集成成为问题，并且影响电路的封装问题。面积的增加，是制作集成电路的成本增加。这些原因让减少功耗和减小集成电路的面积成为集成电路设计中除了工作的快慢和可测试性之外需要考虑的又两个重要设计参数。 集成电路优化设计大多基于AND/OR/NOT运算的Boolean逻辑，而基于XNOR/OR或XOR/AND运算的RM（Reed-Muller）逻辑优化技术尚未成熟。与传统布尔逻辑为一定基础的表示的电路相比较，用Reed-Muller逻辑来表示的部分电路，如算术电路、奇偶校验电路、通信电路等在电路的功耗、面积和速度以及可测试性等方面表现出了相当的优势1。因此，建立快速有效的RM电路逻辑综合优化方法是对目前以Boolean逻辑为主的电路设计方法的补充和完善。随着智能算法应用的日益广泛，人们渐渐的用各种智能算法的思想来解决此问题。粒子群优化(ParticleSwarmOptimization,PSO)算法就是众多优化算法的一种，其具有操作原理简单、收敛速度快、在解决多目标问题时优化性能良好、有很强的全局搜索能力等特点，并且在解决一些实际问题时展示了其优越性。利用粒子群算法解决RM（Reed-Muller）电路的极性搜索是解决该问题的其中一种方法，随着对这个问题的不断改进和优化将会更好的解决RM（Reed-Muller）电路的优化。 综上所述，本文涉及到低功耗和面积的一个重要方面，就是实现基于粒子群优化算法的RM电路低功耗和面积最佳极性搜索。这是个很具有方向性的课题，所以，其中的应用前景和科学意义是不可限量的。本文是从功耗和面积这两方面来考虑的。1.2课题的基本内容1.2.1研究对象本课题主要研究RM逻辑电路最佳极性搜索，并基于粒子群优化算法来解决功耗最低和面积最小的问题。主要任务是利用粒子群优化算法进行RM逻辑电路最佳极性搜索，实现功耗和面积最优。在这过程中通过对基本的粒子群算法的学习，再结合几率转换法则，得到离散三值粒子群优化算法，首先采用C语言对基本的算法进行实现，在此基础上来实现离散三值粒子群优化算法来对RM电路最佳极性的搜索，并实现功耗和面积最优。具体工作包括以下几点：（） 熟悉掌握粒子群算法的基本理论，并利用测试函数尝试在编好的程序上实现该算法。（） 查阅资料，掌握RM逻辑电路的应用及展开式的求解，由于一个XNOR/OR展开式对应于一个XNOR/OR电路，因此可以从该XNOR/OR展开式来估计相应XNOR/OR电路的功耗和面积。（） 对RM电路功耗面积分析，建立数学模型，得到适应度函数。（） 编写粒子群算法，极性转换，面积，功耗的程序，通过测试函数运行程序并对其进行分析。1.2.2拟解决的问题通过对离散PSO算法的研究，提出混合极性XNOR/OR电路的功耗优化算法。1) 根据混合极性XNOR/OR展开式的特点，改进快速列表技术并将其应用于混合极性XNOR/OR展开式的转换；2) 根据结合离散二值PSO算法和几率转换法则，得到离散三值粒子群优化算法（DiscreteTernaryParticleSwarmOptimization,DTPSO），并将DTPSO应用于MPRM电路的最佳极性搜索中，实现混合极性XNOR/OR电路功耗和面积最小化；3) 根据信号概率传递算法的功耗优化模型，针对多输入XNOR门和OR门，进行低功耗的优化。4) 通过实验验证该算法具有更快的收敛速度和更好的寻优效率。2 Reed-Muller电路的逻辑展开式 对于基于XNOR/OR或XOR/AND运算Reed-Muller电路的逻辑展开式，固定极性Reed-Muller（fixed polarity Reed-Muller, FPRM）和混合极性Reed-Muller（mixed polarity Reed-Muller, MPRM）是两种重要的RM逻辑表达式。不管是固定极性还是混合极性，都是存在XNOR/OR或XOR/AND运算。2.1 固定极性RM展开式2.1.1 XNOR/OR展开式 任何XNOR/OR逻辑展开式都可以表示成2：= (2.1)其中，下标i的二进制形式可表示为；表示XNOR操作；，表示Si项是否在表达式中出现；Si为OR项，可表示为（其中）： (2.2) 对于一个固定极性，每个变量在式(2.1)中只能以原变量或反变量的形式出现：如pj为0则相应的变量为原变量，否则为它的反变量的形式。因此n变量的逻辑函数具有2n个固定极性，与之对应的有2n个XNOR/OR逻辑表达式。2.1.2 XOR/AND展开式任何 XOR/AND逻辑函数都可以表示为3： (2.3)其中，下标i的二进制形式可表示为；表示XOR操作；，表示项是否在表达式中出现；为AND项，可表示为（其中）： (2.4)对于一个固定极性，每个变量在式(2.3)中只能以原变量或反变量的形式出现：如pj为0则相应的变量为原变量，否则为它的反变量的形式。因此n变量的逻辑函数具有2n个固定极性，与之对应的有2n个RM表达式。2.2 混合极性RM展开式 2.2.1 XNOR/OR展开式 任何逻辑函数都可以用 XNOR/OR展开式来表示，n个输入变量逻辑函数f: XnX可用最大项展开式表示为12: (2.5) n个输入变量的MPRM有3n个不同的极性，对应3n个不同的混合极性XNOR/OR展开式，则极性P下混合极性XNOR/OR展开式可表示为 (2.6)其中，下标i的二进制形式可表示为；为同或运算；P为极性，其三进制数表示形式为pn-1pn-2p0；，表示Si项是否在表达式中出现；Si为或项，可用符号表示为。混合极性XNOR/OR展开式中的变量以原变量或反变量的形式出现，也可以同时以原变量和反变量的形式出现，其出现形式与极性P有关。图2.1为Si中的出现形式与pk和ik的关系，0kn-1，其中表示的原变量，表示的反变量。若对应的极性为pk，当pk=0时，以原变量出现；当pk=1时，以反变量出现；当pk=2时，的原变量和反变量同时出现。图2.1 与ik和pk的关系 2.2.2 XOR/AND展开式 逻辑函数基也可以用AND/XOR运算的RM逻辑函数表示。根据XNOR/OR展开式 ，可以知道任一n个输入变量逻辑函数f: XnX用最小项表达式表示为12： （2.7） 其中，为XOR运算；fk为第k个输出变量，k = 0, 1, , n-1；ai,k为最小项系数，表示mi是否在第k个最小项表达式中出现；最小项mi用符号表示为；下标i用二进制数表示形式为in-1in-2i0。mi中与i中ik有如下关系：当ik=0时，；当ik=1时，0kn-1。同理，n个输入变量的MPRM有3n个不同的极性，对应3n个不同的XOR/AND混合极性展开式，此逻辑函数用P极性的MPRM表达式表示成： （2.8） 其中，为XOR运算；极性P用三进制数表示为pn-1pn-2p0；与项Mi用符号表示为；bi,k为MPRM系数。Mi中与pk和ik有如下关系：当pk=0时，以原变量出现；当pk=1时，以反变量出现；当pk=2时，的原变量和反变量。具体可通过查找如图2.2确定。图2.2 与ik和pk的关系3 粒子群优化算法3.1 基本的粒子群算法 粒子群算法(Particle Swarm Optimization, PSO) 是由Eberhart博士和kennedy博士提出的，是通过模拟鸟群和鱼群寻找食物的行为而发展起来的，一种基于群体协作的随机搜索算法。它是群体智能搜索方法的一种，在各类群体可以起到全局优化的效果。和其他的智能算法一样，PSO算法也是根据群体的运动，而不同的是它没有其它演化算法中的演化算子（如遗传算法中的交叉、变异算子），而是将群体中的每一个个体看成是一种没有质量、没有体积的微粒（点）。每个微粒在搜索空间以一定的速度飞行13。每个微粒的速度根据自身的经验与群体的经验进行调节，表现为每个粒子均向自身较好位置和群体中最好微粒的位置靠近。每个微粒的位置即可视为问题空间的一个潜在解。3.1.1 粒子群算法 粒子群算法将每个个体看作为D维空间中的一个没有体积和重量的粒子，在搜索空间中以一定速度的飞行，并根据对自身和集体飞行经验的综合分析来动态调整速度。其中，每一个粒子都有一个被优化函数决定的适应度值，粒子的位置代表优化问题在搜索空间的可行解，飞行速度代表着粒子的搜索方向和步长5。3.1.2 粒子群算法的原理 假设一个由M个粒子组成的群体在D维的搜索空间以一定的速度飞行。粒子i在t时刻的状态属性设置如下(, )： 位置： ，分别代表搜索空间的下限和上限；速度： ，、分别代表最小和最大速度；个体最优位置：；全局最优位置：；则粒子在t+1时刻的位置通过下式来更新得到： (3.1) (3.2)其中，c1和c2为学习因子，分别代表了自我调整能力和向种群最优粒子的学习能力，r1和r2为0，1范围内的随机数，w为惯性权重。公式（3.1)主要通过三部分来计算更新粒子的速度：第一部分为记忆项，表示上次速度大小和方向的影响，相当于对粒子起初的运动速度乘一个惯性权重值进行提升速度，表示粒子对当前自身运动状态的信任，依据自身的速度进行惯性运动；第二部分为认知项，是从当前位置引向粒子自己最好的位置，表示粒子自身的动作是根据自己的经验；第三部分为社会项，表示从当前的点引向种群的最好位置，反映粒子间的协同合作和知识的共享。3.1.3 粒子群算法的流程第一步：随即产生每个粒子的位置和速度并初始化；第二步：计算出每个粒子曾到过的最优位置（适应值）；第三步：将每个粒子到过的最优位置的适应值与所经历过的最好位置的最优位置进行 比较，若较好，就将该位置当作当前的最好位置； 第四步：对每个粒子，将在个体上的最优位置的适应值与种群中最好位置的适应值进行比较，若较好，就让这个位置成为当前的全局最好位置；第五步：根据公式（3.1）和公式（3.2）更新粒子的速度和位置；第六步：如未达到最大的迭代次数或者还有没有达到一定的适应值，则返回第二步。开始随即产生的位置和速度初始化粒子群求粒子群曾到过的最优位置求每个粒子曾到过的最优位置用公式（3.1）（3.2）更新速度和位置达到最大进化代数结束图3.1 PSO算法流程框图3.2 改进的粒子群算法（离散三值粒子群优化（TPSO）算法 ） 通过对XNOR/OR电路逻辑展开式的深入理解，根据其展开式的特点，结合几率转换法则，从而得出离散三值粒子群优化（TPSO）算法 。根据混合极性XNOR/OR电路展开式的特点，结合几率法则6，提出了离散三值PSO算法，该算法采用三进制编码形式，0,1,2的取值服从正态分布,其与PSO最重要的区别就是粒子的运动方程，TPSO的粒子运动方程如下: (3.3) (3.4) (3.5) (3.6)速度公式形式保持不变,位置公式完全改变了，其中集合数R为3，、和只能取0、1或2，被约束在0,2之间，为权值，round()对括号内的数值进行四舍五入，其返回值为整数。速度不再是位置的步长，而是决定位置的一种概率，通过sigmoid函数和服从标准正态分布的随机数来约束位置，选中位置的概率与该位置离的距离成反比，并可以证明概率之和为1，即：。4 XNOR/OR电路的混合极性转换4.1 基于快速列表法混合极性转换 在XNOR/OR逻辑函数f: XnX中对应有2n个XNOR/OR逻辑展开式，对应的系数下标为02n-1，它的最大项展开式的下标为02n-1。对于混合极性XNOR/OR逻辑函数f: XnX中对应有3n个XNOR/OR逻辑展开式，对应的系数下标为03n-1，它的最大项展开式下标为03n-1。XNOR/OR电路混合极性转换就是在已经知道的最大项展开式的情况下求取某一极性的下的下标值，根据下标值来写出混合极性下的最大项展开式。根据快速列表技术在固定极性转换上的思想9，将固定极性电路极性转换的原则用于混合极性XNOR/OR电路的极性转换，从而提高极性转换速度。其基本转换过程表述如下：第一步：将布尔函数中的所有最大项以二进制形式表示； 第二步：将所要求的极性转换成三进制形式，并与最大项中对应极性为1的位进行异或操作，得到新项，若极性位为0或2时，则不操作；第三步：当极性位为0或1时，选择i个位为1的新项，以这些位为无关项，再产生所有2i-1个新项，并更新索引表中的项数，若极性位为2时，则保持不变；第四步：重复步骤第三步，直至操作完所有新项；第五步：索引表中项数为奇数的项即为所求的XNOR/OR项。例：三变量Boolean函数，现将此最大项展开式转换成极性22下MPRM展开式。 图4.1产生新的最大项 图4.2 索引图第一步：将布尔函数每个最大项以二进制表示，010,100,101。第二步：将极性22转化成三进制211，再将最大项的二进制与211进行异或操作得到新的最大项，如图4.1中第一列所示；第三步：产生所有新项如图4.1中第二列所示，并建立索引图，如图4.2所示。第四步，索引表中项数为奇数的项就是要求的XNOR/OR项的项数，因此，极性22下的混合极性的XNOR/OR展开式： (4.1)5 基于PSO的XNOR/OR电路低功耗最佳极性搜索5.1 XNOR/OR电路功耗优化 在XNOR/OR电路最佳极性搜索的同时，也必须要进行优化XNOR/OR电路的功耗。一般的XNOR/OR电路都是多输入的门电路，也要对单个XNOR/OR电路进行功耗的优化。在XNOR/OR电路的逻辑展开式的基础上，通过信号概率传递算法对多输入的XNOR/OR电路进行低功耗的分解，能有效的降低电路的功耗。5.1.1 基于信号概率传递的CMOS电路功耗模型 XNOR/OR电路的逻辑展开式都可以表示为： (5.1)从公式得知，XNOR/OR电路完全由多输入OR门和多输入XNOR门组成，所以OR门和XNOR门也是影响电路的功耗和面积的重要原因。但是为了降低功耗大小，减小面积大小，需要将多输入的OR门和多输入的XNOR门分解为一系列的二输入的OR门和二输入的XNOR门，因此，XNOR/OR电路的功耗和面积实际上是由二输入的OR门和二输入的XNOR门引起的。 CMOS电路的功耗主要有动态功耗组成7，动态功耗主要由电路内部节点负载电容充放电产生。对于电路都是由门电路组成的，所以电路的动态功耗为： (5.2)其中，Vdd 是供应电压，fclk 是时钟频率，是门j的输出负载电容，是门j在任何的一个时钟周期里“0”跳变到“1”和“1”跳变到“0”，在此过程中，门j的平均跳变次数为门j的开关活动性。基于低功耗的组合逻辑中，往往可以通过开关活动性来控制的。所以，在低功耗的组合的逻辑中，为了降低电路的功耗，一般是通过减小电路的开关活动性，而开关活动性又是通过电路的输入和输出信号的概率来计算的。 若在一个时间段中，一个信号出现高电平的时间段和该总的时间段之商，叫做该信号的输出信号概率，记作P(m)，则根据文献8中的信号概率传递算法，分别可以得到图5.1(a)所示的二输入OR门和图5.1(b)所示的二输入XNOR门的输出信号概率。二输入OR门： (5.3)二输入XNOR门： (5.4) (a) (b)图5.1 二输入OR门和二输入XNOR门: (a)二输入OR门 (b)二输入XNOR门 开关活动性的具体计算，与电路实现方式（动态逻辑或静态逻辑）有关10。 动态逻辑电路常通过采用的工作方式是预先充电然后求出信号概率，在预先准备的时间段将输出预先充电到“1”或者预先放电到“0”。在预先放电到“0”的过程，因为电路在输出的时候会发生电平从“1”到“0”的跳变，都会出现一个预先放电到“0”的阶段。在预先充电到“1”的过程，因为电路在输出的时候会发生电平从“0”到“1”的跳变，都会出现一个预先充电到高电平的过程。所以如果输出信号概率为p(g)，则开关活动性如公式（5.5）所示： (5.5) 静态逻辑电路能保持良好的稳定输出情况主要由稳定的输入信号让MOS晶体管导通或者截止状态所决定。如果输出信号概率为P(g)，发生跳变之后的信号概率为，现在考虑两个连续的时钟周期中的输出信号概率P(g)、与开关活动性的关系。如果考虑这两个连续时钟周期中的信号是互不相干的，所以发生“0”到“1”跳变的概率为P(g)，发生“1”到“0”跳变的概率为P(g)，这两个是相等。根据这个可以得到静态逻辑电路的开关活动性如公式（5.6）所示： (5.6)5.2 多输入OR门低功耗优化由于OR门输出信号的概率随着输入的增加而增加，所以对其的分解过程采用Huffman算法，可以得到较好的结果。在一定的条件下，Min-Huffman算法和Max-Huffman算法这两种算法可以解决加权组合方程的分解。若所有输入的信号概率小于等于0.5，Min-Huffman算法能够由于求解低功耗分解问题。Min-Huffman算法：将所有输入变量的信号概率按大小排列；将最小的两个信号概率的变量结合，并将结合后得到的概率代替这两个信号概率；若信号概率个数大于1个，返回第步，不然的话算法结束。若所有输入的信号概率大于等于0.5，Max-Huffman算法能够由于求解低功耗分解问题。Max-Huffman算法：将所有输入变量的信号概率按大小排列；将最小的两个信号概率的变量结合，并将结合后得到的概率代替这两个信号概率；若信号概率个数大于1个，返回第步，不然的话算法结束。 例：图5.2为5输入OR门用 Huffman算法对其进行低功耗分解后的二输入OR门电路，其中pr(a)=0.4、pr(b)=0.4、pr(c)=0.6、pr(d)=0.84和pr(e)=0.95。通过把信号概率排序，将最小的两个信号概率可以根据二输入OR门概率传递公式（5.3）进行计算，得到图5.3。图5.2 5输入OR门 图5.3 分解后二输入OR门5.3 多输入XNOR门低功耗优化 多输入XNOR门的低功耗分解比较繁琐，由于多输入XNOR门在综合情况下，往往总是要被分解为一系列的二输入XNOR门。所以为了使这些所组成树型结构的二输入XNOR门的开关活动性最低，必须在低功耗综合时应合理安排和组合多输入XNOR门的这些输入信号概率。根据公式（5.4），二输入XNOR门的输出信号概率函数为： (5.7) 对g(m,n)求偏导： , （5.8)图5.4 函数g(m,n)的变量和因变量的关系可见函数g(m,n)的变量和因变量的关系，在固定n的情况下：当0n0.5，0m0.5时，g(m,n)随m的递增而单调递减，且它的值一直大于0.5；当0n0.5，0.5m1时，g(m,n)也随m的递增而单调递增，但它的值一直小于0.5；当n=0.5(或m=0.5)时，g(m,n)一直保持不变且它的值为0.5；当0.5n1，0m0.5时，g(m,n) 随n的递增而单调递减，且它的值一直小于0.5；当0.5n1，0.5m1时，g(m,n)也随n的递增而单调递增，但它的值一直大于0.5。由于m与n完全对称，当固定m，变化n时，g(m,n)一样可以有上述的特点，所以在固定m的情况下：当0m0.5，0n0.5时，g(m,n)随n的递增而单调递减，而且它的值一直大于0.5；当0m0.5，0.5n1时，g(m,n)也随n的递增而单调递减，但它的值一直小于0.5；当m=0.5(或n=0.5)时，g(m,n)一直不变，而且它的值为0.5；当0.5m1，0n0.5时，g(m,n) 随n的递增而单调递增，且它的值一直小于0.5；当0.5m1，0.5n1时，g(m,n)也随n的递增而单调递增，但它的值一直大于0.5。故二输入XNOR门信号概率的输出值的大小有可能出现的情况可以用图5.5来表示。(a) (b)(c) (d)图5.5 动态逻辑多输入XNOR门低功耗分解(a) 多输入XNOR门 (b) 情况(1) (c) 情况(2) (d) 情况(3)5.3.1 动态逻辑的多输入XNOR门低功耗优化 由公式（5.2）得知，要实现低功耗，应该尽量减小各个门电路开关活动性。由公式（5.5）可知，动态逻辑电路的开关活动性与信号输出的概率成一定的比例。因此，动态逻辑电路的低功耗分解应主要来使电路的输出信号概率越小越好。根据以上对二输入XNOR门概率函数的深入理解，多输入XNOR门在动态逻辑时分解成一系列二输入XNOR门的过程如下：（1） 如果多输入XNOR门的所有输入信号概率都小于0.5，因为g(m,n)随m（或者n）的增加而减小，而且任何的两个信号进行组合时输出的信号概率都是小于0.5，只有当取概率值最大的两个信号进行综合时，可以使得输出信号概率最小，从而开关活动性最小；（2）如果多输入XNOR门的所有输入信号概率都大于0.5，因为g(m,n)随m(或者n)的增加而增加，而且任何两个信号进行组合所输出的信号概率都是大于0.5，只有当取概率值最小的两个信号进行组合时，可以使得输出信号概率最小，从而开关活动性最小；（3）如果多输入XNOR门的输入信号中概率大于0.5，等于0.5，小于0.5的情况都存在，当有两个信号等于0.5（m=0.5，n=0.5）时，因为g(m,n)的值则为0.5，所以信号概率的值为0.5的信号要在其他信号组合后再进行组合。如果所选的两个输入信号概率都小于0.5，其输出信号概率值大于0.5。如果所选的两个输入信号概率都大于0.5，其输出的信号概率值也是大于0.5。如果所选的信号概率一个大于0.5，一个小于0.5，那么其输出的信号概率值是小于0.5.因此要使输出信号概率越小越好，一般要取一个信号概率值小于0.5，而另外一个信号概率值大于0.5的信号。因为上文已得到当0m0.5，0.5n1时，m取值固定，则g(m,n)随n的增加而减小；n取值固定，则g(m,n) 随m的增加而增加，因此要使输出信号概率值达到最小，m应取在0m0.5之间输入信号概率的最小值，n应取在0.5n1之间输入信号概率的最大值。因为m、n在输出信号概率函数中输出特性是完全对称，所以当0n0.5，0.5m1时，要使输出信号概率值达到最小，n应取在0n0.5之间输入信号概率的最小值，m应取在0.5m1之间输入信号概率的最大值。 图5.5分别给出了上述三种输入信号概率情况下，三输入XNOR门在动态逻辑下的低功耗分解过程。5.3.2 静态逻辑的多输入XNOR门低功耗优化 与动态逻辑多输入XNOR门低功耗优化相似，多输入XNOR门在静态逻辑中的低功耗优化也与降低开关活动性相关的问题。由公式(5.6)可知，静态逻辑电路开关活动性的计算曲线是一条开口向下的抛物线，它的对称轴是P(m)=1/2。因此，要使其信号概率值最小，应让她的输出信号概率越接近0或者1越好。因此，根据二输入XNOR门的变量和因变量信号概率值的大小进行分析，多输入XNOR门在静态逻辑时分解成一系列二输入XNOR门的过程可归纳如下：（1）如果多输入XNOR门的所有输入信号概率都大于0.5。由上文的讨论可知，因为g(m,n)随m（或n）的增加而严格增加，而且任何两个信号概率进行组合后输出的信号概率值大于0.5。所以，只有当每次都取信号概率值最大的两个信号进行组合，其输出的概率值最接近于1，使开关活动最小。（2）多输入XNOR门的输入信号中存在概率值大于0.5的信号，概率值小于0.5的信号，概率值等于0.5的情况。当有两个信号等于0.5（m=0.5，n=0.5）时，因为g(m,n)的值则为0.5，所以信号概率的值为0.5的信号要在其他信号组合后再进行组合。如果所选的两个输入信号概率都小于0.5，其输出信号概率值大于0.5。如果所选的两个输入信号概率都大于0.5，其输出的信号概率值也是大于0.5。在此种情况下，若所取信号的概率值都小于0.5，将信号进行组合其输出的信号概率大于0.5。若所取信号的概率值都大于0.5，将信号进行组合其输出的信号概率也是大于0.5。所以当所有的信号概率值小于0.5和大于0.5的时候，信号输出的概率值更有机会达到接近1的max；若所取信号的概率值一个大于0.5，另外一个小于0.5，将信号进行组合其输出的信号概率值小于0.5，所以该输出信号概率值更有机会达到接近0的min。因为在静态逻辑电路中，信号的输出概率越靠近0或1将都会是让开关活动性达到最小的机会越大，所以让电路的功耗越小，必须要根据这两种情况来判断的，从而得到更好的信号输出概率。（3）多输入XNOR门的所有输入信号概率都小于0.5，因为所有输入概率值小于0.5时，函数g(m,n)随m（或n）的递增而单调递减，而且任何两个信号进行组合后其输出的信号概率值大于0.5，当第一次组合时，应该让两个信号概率值的最小信号进行结合，输出概率必最接近于1，这时开关活动性为最小。但因为出现了一个大于0.5的信号概率值，接下来开始的组合要和情况（2）中信号的概率值有大于0.5和概率小于0.5完的全相同。为了要电路的功耗越低越好的话，则当有信号组合时都需要判断输入概率值和组合的情况是属于哪一种及其结果。从上述分析可见：情况（1）的组合过程比起其他情况要简单的多了，通过用霍夫曼算法就可以使信号输出概率值达到最小；而情况（2）、（3）则相当复杂（每次组合都需要判断输入概率值和组合的结果）因此从降低运算复杂度出发，此组合过程需要改进。XNOR门的工作特点是当输入的变量都为高电平或都是低电平时它的输出为“1”，当输入的变量既有高电平它的输出为“0”。所以，只要改变输入信号中的一个信号，输出就会发生由“0”到“1”或由“1”到“0”的变化；如果同时改变两个输入信号，输出就不会发生变化。对应于XNOR门的工作特点，它输出信号的概率也有相似的特点10：若其中一个输入信号概率P(g)，给这个输入信号取补概率，那么输出信号概率为原来输出信号概率的补概率；若两个输入信号概率都取它们概率的补，那么输出信号概率就不发生变化。而静态逻辑电路的开关活动性如公式（5.6）所示：Es=2P(g)1P(g)，相当于原来信号的开关活动性和它将信号概率取补之后的开关活动性是相同的。所以，对于XNOR门来说，在静态逻辑中，如果将输入信号概率取补之后就不会影响开关活动性。因此，可以将输入信号中概率小于0.5的值全都取成1的补，使情况（2）、（3）转换为情况（1），让它变成简单的组合过程。图5.6给出了三输入XNOR门在静态逻辑下的低功耗分解过程。通过静态逻辑的分析可以计算出(a)中的概率是0.51，通过信号概率的求补，再计算出概率为0.49,如（c）图所示。(a) (b) (c) 图5.6 静态逻辑多输入XNOR门低功耗分解： (a) 多输入XNOR门 (b)概率取补 (c) 分解结果5.4 TPSO算法在混合极性XNOR/OR电路上的应用 混合极性XNOR/OR电路极性它仅仅只是一个数值，无法体现出一个电路功耗和面积的好与差。由于电路的功耗和面积在极性的方向上是无规则的。一般的计算方法是不能适用的。在基本的粒子群优化算法中，提出了离散二值的粒子群，在本文中，通过几率转换法则，根据离散二值，得到离散三值的粒子群优化算法，并将此算法应用在混合极性XNOR/OR电路的功耗和面积的优化上。5.4.1 编码和适应度函数 在TPSO算法中所要优化的变量就是XNOR/OR电路的极性，实现极性的最优。而极性仅仅只是个数值，不能直接反映电路好与差的程度。XNOR/OR电路的繁简是由极性决定的，XNOR/OR电路对应的是XNOR门和OR门，所以用XNOR门和OR门来反映电路的好与差。因此，在某种极性下XNOR/OR电路的功耗和面积的大小分别由XNOR门和OR门的开关活动性和XNOR和OR门的项数和所决定的。根据对多输入XNOR门和OR门低功耗分解后得到的开关活动性以及对多输入XNOR门和OR门分解后得到的二输入OR门和二输入XNOR门的项数和得出适应度函数。算法中用到的适应度函数如公式所示： （5.8）其中,和分别表示二输入OR门和XNOR门的项数，表示在该极性下的XNOR/OR电路总的开关活动性。由于求出来的适应值比较小，所以将其扩大100。5.4.2 速度和位置更新 根据TPSO算法运动方程公式(3.3)、公式(3.4）、公式（3.5）和公式（3.6）更新每一个粒子的速度和位置，得到新粒子，并对速度进行限制，通过迭代得到个体最优，将各个粒子的个体置于群体里再次更新，得到全体最优。5.4.3 算法描述通过以上的分析，离散三值PSO算法和电路信号概率的传递，基于快速列表法的XNOR/OR电路的混合极性转换，与其他的极性转换相比，可以加快极性搜索的速度。该算法的主要思想是：（1）先读入PLA格式测试电路，再初始化粒子群的位置、速度，适应度值；（2）进入TPSO算法，通过对每个粒子的速度和位置的迭代更新得到下一代的粒子群，并通过调用基于基于快速列表法的混合极性转换子函数得到XNOR/OR的逻辑展开式，计算出XNOR门和OR门的个数，从而调用功耗的子函数，OR门利用霍夫曼算法将信号概率排序通过二输入OR门计算出OR门的开关活动性，XNOR门通过上文所提到的多输入XNOR门低功耗优化，分解成二输入XNOR门来实现计算出XNOR门的开关活动性；（3）得到适应度函数中的各个参数，进行局部优化和全局的优化，若达到最大的迭代次数，就会输出最优的适应值。不然的话，则继续迭代。上述的算法流程如图5.7所示：图5.7 算法流程图上述算法过程的程序伪代码如图5.8所示：/Generation_Size: 遗传代数/Population_Size: 种群大小/F_Population: 父代群体 /F_Fitness: 父代群体适应度 /Z _Population: 子代群体 /Z_Fitness: 子代群体适应度Begin Algorithm: Read_Benchmark(); /读入MCNC标准电路 Chushihua_Populatio