计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2013年
10期
32-38
,共7页
程学云%管致锦%张海豹%丁卫平
程學雲%管緻錦%張海豹%丁衛平
정학운%관치금%장해표%정위평
可逆逻辑综合%可逆函数%Toffoli门%可逆电路优化
可逆邏輯綜閤%可逆函數%Toffoli門%可逆電路優化
가역라집종합%가역함수%Toffoli문%가역전로우화
Reversible logic synthesis%Reversible function%Toffoli gate%Optimization of reversible circuit
可逆电路的优化是可逆逻辑综合的关键问题之一.为了解决可逆Toffoli电路优化问题中算法复杂度高和电路规模可扩充性差的问题,分析归纳了相邻Toffoli门的关系,提出并证明了可逆Toffoli电路中子序列的移动和化简规则,并基于这些规则给出了可逆Toffoli电路的优化算法.根据移动规则对可逆电路进行正向和反向扫描,寻找满足化简规则的子序列进行优化,直到可逆电路不发生变化为止.该优化算法与可逆电路的输入线数无关,无需存储额外信息,适用于各种不同类型的Toffoli电路合成方法,算法复杂度为O(s3),优于通常使用的模板优化的复杂度O(n!t2s3).在具体实例和国际认可的所有3变量可逆函数上的验证结果表明,该优化算法能有效地减少可逆电路的门数和控制位数,降低可逆电路的代价.
可逆電路的優化是可逆邏輯綜閤的關鍵問題之一.為瞭解決可逆Toffoli電路優化問題中算法複雜度高和電路規模可擴充性差的問題,分析歸納瞭相鄰Toffoli門的關繫,提齣併證明瞭可逆Toffoli電路中子序列的移動和化簡規則,併基于這些規則給齣瞭可逆Toffoli電路的優化算法.根據移動規則對可逆電路進行正嚮和反嚮掃描,尋找滿足化簡規則的子序列進行優化,直到可逆電路不髮生變化為止.該優化算法與可逆電路的輸入線數無關,無需存儲額外信息,適用于各種不同類型的Toffoli電路閤成方法,算法複雜度為O(s3),優于通常使用的模闆優化的複雜度O(n!t2s3).在具體實例和國際認可的所有3變量可逆函數上的驗證結果錶明,該優化算法能有效地減少可逆電路的門數和控製位數,降低可逆電路的代價.
가역전로적우화시가역라집종합적관건문제지일.위료해결가역Toffoli전로우화문제중산법복잡도고화전로규모가확충성차적문제,분석귀납료상린Toffoli문적관계,제출병증명료가역Toffoli전로중자서렬적이동화화간규칙,병기우저사규칙급출료가역Toffoli전로적우화산법.근거이동규칙대가역전로진행정향화반향소묘,심조만족화간규칙적자서렬진행우화,직도가역전로불발생변화위지.해우화산법여가역전로적수입선수무관,무수존저액외신식,괄용우각충불동류형적Toffoli전로합성방법,산법복잡도위O(s3),우우통상사용적모판우화적복잡도O(n!t2s3).재구체실례화국제인가적소유3변량가역함수상적험증결과표명,해우화산법능유효지감소가역전로적문수화공제위수,강저가역전로적대개.
