主权项 |
1.一种用于数字电路设计的固定极性转换方法,其特征在于首先读入包含无关项的布尔逻辑函数的SOP展开式;然后利用快速列表技术分别建立最小项索引表和无关项索引表;最后搜索最优无关项取舍,选择合适的无关项写入FPRM函数式,得到与项最少的FPRM展开式;具体过程如下:①读入布尔电路,将布尔电路用包含无关项的布尔逻辑函数的SOP展开式表示为:<maths num="0001"><![CDATA[<math><mrow><mi>f</mi><mrow><mo>(</mo><msub><mi>x</mi><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>x</mi><mrow><mi>n</mi><mo>-</mo><mn>2</mn></mrow></msub><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><msub><mi>x</mi><mi>c</mi></msub><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><msub><mi>x</mi><mn>0</mn></msub><mo>)</mo></mrow><mo>=</mo><munderover><mi>Σ</mi><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><msup><mn>2</mn><mi>n</mi></msup><mo>-</mo><mn>1</mn></mrow></munderover><msub><mi>a</mi><mi>i</mi></msub><msub><mi>m</mi><mi>i</mi></msub><mo>+</mo><munderover><mi>Σ</mi><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><msup><mn>2</mn><mi>n</mi></msup><mo>-</mo><mn>1</mn></mrow></munderover><msub><mi>d</mi><mi>i</mi></msub><msub><mi>m</mi><mi>i</mi></msub><mo>,</mo></mrow></math>]]></maths>其中∑为或运算符,n为函数f(x<sub>n-1</sub>,x<sub>n-2</sub>,...,x<sub>c</sub>,...,x<sub>0</sub>)的输入变量数,(x<sub>n-1</sub>,x<sub>n-2</sub>,...,x<sub>c</sub>,...,x<sub>0</sub>)为函数f(x<sub>n-1</sub>,x<sub>n-2</sub>,...,x<sub>c</sub>,...,x<sub>0</sub>)的n个输入变量,m<sub>i</sub>代表最小项,m<sub>i</sub>用符号表示为<img file="FDA00002440318900012.GIF" wi="389" he="48" />i为最小项序数,且0≤i≤2<sup>n</sup>-1,i用二进制形式表示为i<sub>n-1</sub> i<sub>n-2</sub>...i<sub>c</sub>...i<sub>0</sub>,c为正整数且0≤c≤n-1,<img file="FDA00002440318900013.GIF" wi="34" he="44" />与i<sub>c</sub>有如下关系:当i<sub>c</sub>=0时,<img file="FDA00002440318900014.GIF" wi="157" he="48" />当i<sub>c</sub>=1时,<img file="FDA00002440318900015.GIF" wi="159" he="48" />a<sub>i</sub>为最小项系数且a<sub>i</sub>∈{0,1},当a<sub>i</sub>=0时表示m<sub>i</sub>不在SOP展开式中出现,当a<sub>i</sub>=1时表示m<sub>i</sub>在SOP展开式中出现,d<sub>i</sub>为无关项系数且d<sub>i</sub>∈{0,1},当d<sub>i</sub>=0时表示m<sub>i</sub>不属于无关项,当d<sub>i</sub>=1时表示m<sub>i</sub>属于无关项;布尔逻辑函数的SOP展开式中包含k个无关项,分别记为d<sub>k-1</sub>、d<sub>k-2</sub>、…、d<sub>j</sub>…、d<sub>0</sub>,用W代表无关项取舍,表示各无关项是否写入逻辑函数的SOP展开式,W用k位的二进制形式表示为w<sub>k-1</sub> w<sub>k-2</sub>…w<sub>j</sub>…w<sub>0</sub>,其中,w<sub>j</sub>=0表示所对应的无关项dj不写入SOP展开式,w<sub>j</sub>=1表示所对应的无关项d<sub>j</sub>写入SOP展开式;将包含无关项的布尔逻辑函数的SOP展开式转换为FPRM函数式,FPRM函数式表示为<maths num="0002"><![CDATA[<math><mrow><msup><mi>f</mi><mi>p</mi></msup><mrow><mo>(</mo><msub><mi>x</mi><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>x</mi><mrow><mi>n</mi><mo>-</mo><mn>2</mn></mrow></msub><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><msub><mi>x</mi><mi>c</mi></msub><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><msub><mi>x</mi><mn>0</mn></msub><mo>)</mo></mrow><mo>=</mo><mo>⊕</mo><munderover><mi>Σ</mi><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><msup><mn>2</mn><mi>n</mi></msup><mo>-</mo><mn>1</mn></mrow></munderover><msub><mi>b</mi><mi>i</mi></msub><msub><mi>π</mi><mi>i</mi></msub></mrow></math>]]></maths>其中p为变量极性,p用二进制数表示为p<sub>n-1</sub> p<sub>n-2</sub>...p<sub>c</sub>...p<sub>0</sub>,代表n个变量在FPRM展开式中的出现方式;<img file="FDA00002440318900017.GIF" wi="74" he="48" />为XOR运算;π<sub>i</sub>为FPRM展开式中的与项,b<sub>i</sub>∈{0,1},当b<sub>i</sub>=0时表示π<sub>i</sub>不写入FPRM展开式,当b<sub>i</sub>=1时表示π<sub>i</sub>写入FPRM展开式;②采用快速列表技术将SOP展开式中所有的最小项转换为其相应的与项,并将所有的最小项所产生的与项保存到最小项索引表中,得到最小项索引表;③采用快速列表技术将SOP展开式中所有的无关项转换为其相应的与项,并将所有的无关项所产生的与项保存到无关项索引表中,得到无关项索引表;④结合无关项索引表与最小项索引表搜索最优无关项取舍,选择合适的无关项写入FPRM函数式,得到与项最少的FPRM展开式。 |