| 主权项 |
1.一种基于贪婪算法的同或/或电路的分解方法，其特征在于首先引入同或/或电路表达式，将多输入同或/或门的分解问题转换为最小二叉树搜索问题，然后采用贪婪算法分解同或/或电路中的多输入或门，再在多输入或门分解的基础上采用贪婪算法分解同或/或电路中的多输入同或门，具体包括以下步骤：①读入同或/或电路表达式<img file="FDA00002255334600011.GIF" wi="777" he="109" />n为函数f(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>i</sub>…,x<sub>n</sub>)的变量数，(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>i</sub>…,x<sub>n</sub>)为函数f(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>i</sub>…,x<sub>n</sub>)的n个输入变量，i为正整数，且1≤i≤n，S<sub>k</sub>项代表同或/或电路中的某个或门，且<img file="FDA00002255334600012.GIF" wi="568" he="46" />d<sub>k</sub>为或项系数，且d<sub>k</sub>∈{0,1}，当d<sub>k</sub>=0时，表示S<sub>k</sub>项在同或/或电路表达式中出现，当d<sub>k</sub>=1时，表示S<sub>k</sub>项不在同或/或电路表达式中出现，⊙∏表示同或操作，k为S<sub>k</sub>项序号，k用二进制形式表示为k<sub>1</sub>k<sub>2</sub>…k<sub>j</sub>…k<sub>n</sub>，j为正整数，且1≤j≤n，当k<sub>j</sub>＝0时，<img file="FDA00002255334600013.GIF" wi="143" he="44" />当k<sub>j</sub>＝1时，<img file="FDA00002255334600014.GIF" wi="133" he="43" />S<sub>k</sub>项代表的或门的输入变量x<sub>i</sub>的数量为m，<maths num="0001"><![CDATA[<math><mrow><mi>m</mi><mo>=</mo><munderover><mi>Σ</mi><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mrow><mo>(</mo><mn>1</mn><mo>+</mo><msub><mi>k</mi><mi>j</mi></msub><mo>)</mo></mrow><mo>;</mo></mrow></math>]]></maths>②定义S<sub>k</sub>项代表的或门的开关活动性为SA_OR_S<sub>k</sub>，将S<sub>k</sub>项代表的或门的输入变量x<sub>i</sub>定义为最小二叉树搜索问题中的树，树的数量为m，将S<sub>k</sub>项代表的或门分解得到的二输入或门的开关活动性定义为两棵树间的距离，每个输入变量x<sub>i</sub>的输入概率P(x<sub>i</sub>)作为其对应树的概率，记在该树的树根，S<sub>k</sub>项代表的或门的输出概率记为P(S<sub>k</sub>)；③采用贪婪算法分解同或/或电路中的多输入或门，得到S<sub>k</sub>项代表的或门的开关活动性SA_OR_S<sub>k</sub>和S<sub>k</sub>项代表的或门的输出概率P(S<sub>k</sub>)；④将所有或门的开关活动性累加，得到同或/或电路中所有或门的总开关活动性，同或/或电路中或门的数量为q,，其中<img file="FDA00002255334600016.GIF" wi="293" he="114" />SA_OR表示同或/或电路中所有或门的总开关活动性，<img file="FDA00002255334600017.GIF" wi="508" he="115" />将所有或门的输出概率P(S<sub>k</sub>)记入一个长度为q的数组中，将该数组作为同或/或电路中同或门输入变量的输入概率；⑤采用贪婪算法分解同或/或电路中的多输入同或门，得到同或/或电路中所有同或门的总开关活动性SA_XNOR；⑥将同或/或电路中所有或门的总开关活动性SA_OR和同或/或电路中所有同或门的总开关活动性SA_XNOR相加，得到同或/或电路的总开关活动性SA_total，<maths num="0002"><![CDATA[<math><mrow><mi>SA</mi><mo>_</mo><mi>total</mi><mo>=</mo><munderover><mi>Σ</mi><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>q</mi></munderover><mi>SA</mi><mo>_</mo><mi>OR</mi><mo>_</mo><msub><mi>S</mi><mi>k</mi></msub><mo>+</mo><mi>SA</mi><mo>_</mo><mi>XNOR</mi><mo>.</mo></mrow></math>]]></maths> |
