基于图编码的组合逻辑电路的自动合成方法

摘要

本发明涉及一种基于“图”编码的组合逻辑电路的自动合成方法。其方案是：用“有向图”表示组合逻辑电路，设定组合逻辑电路的真值表和最大循环次数，随机产生N个个体形成种群P，评估种群P中所有个体的性能，选亲和力高的n个个体形成临时种群P_S，对临时种群P_S克隆形成克隆种群P_C，对克隆种群P_C修改形成变异种群P_M，评估变异种群P_M，选出m个亲和力高的个体形成重选种群P_R，替换种群P中亲和力低的个体形成次新种群P_N，随机产生d个新个体替换次新种群P_N中亲和力低的个体形成新种群P_T；对新种群P_T按种群P的评估方法进行评估，依此循环，直到最大循环次数为止。本发明具有高效自动生成任意组合逻辑电路和编码效率高的特点。

主权项

1、一种基于“图”编码的组合逻辑电路的自动合成方法，其特征在于该组合逻辑电路的自动合成步骤为：第一步：用“有向图”表示组合逻辑电路，“图”G记作(V，E)，V是“图”的顶点的集合，E是“图”的边的集合；第二步：设定目标组合逻辑电路的真值表和最大循环次数；第三步：模板组合逻辑电路是由一个两输入一输出的逻辑门、两个输入端子和一个输出端子组成的组合逻辑单元；种群中任意一个个体是一个组合逻辑电路的“图”编码形式，个体是在模板组合逻辑电路的基础上随机产生；个体产生的过程是：向模板组合逻辑电路中随机添加新顶点，添加新顶点的个数和位置是随机的；在随机添加的新顶点和模板组合逻辑电路中的顶点之间添加有向边，直到该“图”满足规定的输入输出顶点数且不含环状结构为止；个体产生的过程重复进行N次，N个不同的个体表示N个不同的组合逻辑电路，从而形成种群P；第四步：评估种群P中所有个体所表示的组合逻辑电路的性能，即每个个体亲和力的计算，每个个体的亲和力等于它的功能亲和力与性能亲和力的和：Affinity＝F_V+P_V(1)式(1)中：F_v是个体的功能亲和力；P_v是个体的性能亲和力；功能亲和力F_v的计算公式为：$F_v=\underset{i=0}{\overset{2^M}{\Sigma }}\underset{j=0}{\overset{N}{\Sigma }}f{v}_{\mathrm{ij}}/(2^M·N)---\left(2\right)$式(2)中：M是组合逻辑电路输入的个数；N是组合逻辑电路输出的个数；fv_ij的定义如下：式(3)中：f_j(x_i)表示当输入为真值表的第i行时组合逻辑电路第j个输出端子的值；x_i是真值表第i个变量；P_ij表示真值表第i行第j个输出值；性能亲和力P_v的计算公式为：式(4)中：r表示组合逻辑电路的逻辑门数；第五步：将种群P中的N个个体按照亲和力的大小降序排列，亲和力高的n(n＜N)个个体被选中，形成临时种群P_S，临时种群P_S中的个体同样按照亲和力的大小降序排列；第六步：临时种群P_S被克隆，克隆后的个体形成克隆种群P_C，克隆种群P_C中第i个个体被克隆的份数与第i个个体的亲和力成正比：N_i＝round(β*n/i)(5)式(5)中：N_i是第i个个体被克隆的份数；β是克隆因子；n是临时种群P_S中的个体数；i是该个体在临时种群P_S中的序号；round是四舍五入取整函数；第七步：克隆种群P_C中的个体被随机选中进行变异操作，个体被选中的条件如下：if rand(1)＜R_M(6)式(6)中：R_M是变异的概率，0＜R_M≤1；rand(1)随机产生一个0～1范围内的实数；选中的个体被随机选中的操作算子所修改，选中的操作算子为以下待选的操作算子中的全部或部分：a、添加边操作算子；b、删除边操作算子；c、修改边操作算子；d、添加顶点操作算子；e、删除顶点操作算子；f、串联操作算子；g、反串联操作算子；选中的操作算子的个数由下式决定：N_o＝RAND(L) (7)式(7)中：L是操作算子类型的总数；RAND(x)返回一个整数r∈[0，x-1]；对克隆种群P_C中的个体修改后，形成变异种群P_M，克隆种群P_C和变异种群P_M中的个体数目相同；第八步：评估变异种群P_M中的个体，评估的过程与第四步相同；第九步：将评估后的变异种群P_M中的个体首先按照亲和力的大小降序排列，然后从中选出m(m＜N)个亲和力高的个体形成重选种群P_R，若重选种群P_R中的个体亲和力高于种群P中的个体亲和力，则种群P中的亲和力低的个体将被替换，形成次新种群P_N；第十步：按照第三步所述的产生新个体的过程，随机产生d(d＜N)个新个体，再替换次新种群P_N中d个亲和力低的个体，形成新种群P_T，然后对新种群P_T按照第四步所述的过程进行评估；重复执行上述步骤中的第五步～第十步，依此循环，直到达到最大的循环次数；以上步骤执行完最大循环次数以后称为一次合成实验，重复上述合成实验M次，最后自动合成出一个满足真值表要求的个体的“图”编码和对应的组合逻辑电路。