摘要
在可逆逻辑函数综合中,分类可以使模块重复使用。把布尔函数NP-N等价的概念推广到可逆逻辑函数中,得到了可逆逻辑函数NP-NP等价的概念;把最小项数为4的3元布尔函数根据辅因子的码值向量分成5类,并计算出了这5类布尔函数的固定极Reed-Muller(FPRM)展开式;把可逆逻辑函数的辅因子码值向量排序后是否相同作为可逆逻辑函数是否NP-NP等价的初步判定,当它们相同时,两个可逆逻辑函数NP-NP等价当且仅当它们的各个对应的输出分量有相同的变量映射,否则它们不是NP-NP等价的。运用这个方法可以判定任意的两个3阶可逆逻辑函数是否NP-NP等价。
In reversible logic synthesis, the templates can be used repeatedly through classification. Extending the defini-tion of NP-N equivalence for Boolean functions to the reversible logic functions, the definition of NP-NP equivalence for reversible logic functions can be given. Divide all 3-varible Boolean functions in which everyone of them has exactly four minterms into five classes by their cofactor weight vectors, and calculate the fixed polarity Reed-Muller Form of each class. By comparing the sorted cofactor weight vectors, whether the reversible logic functions are NP-NP equivalent can be judged preliminarily. When the sorted cofactor weight vectors are identical, the reversible logic functions should be judged as NP-NP equivalence if and only if their every corresponding output which is Boolean function has the same vari-able mappings. Otherwise, the reversible logic functions are not NP-NP equivalent. Thus, whether two 3-bit reversible logic functions are NP-NP equivalent can be judged by this method.
出处
《计算机科学》
CSCD
北大核心
2013年第10期218-220,256,共4页
Computer Science
基金
国家自然科学基金项目(61272175)
高等学校博士学科点专项科研基金(20090185110006)
四川省教育厅重点项目(2011ZA173)资助
关键词
量子电路综合
FPRM展开式
可逆逻辑函数
NP-NP等价
等价判定
Synthesis of quantum circuit, Fixed polarity reed-muller form, Reversible logic function, NP-NP equivalence,Equivalence judgment