摘要
三值可逆逻辑综合是可逆逻辑综合的延伸和扩展.为了简化可逆网络,提高三值可逆逻辑门的通用性,对现有三值可逆控制门控制位的生效值扩展为0、1和2.在此基础上提出了基于最小混乱度原则的三值可逆逻辑综合算法.该算法根据三值可逆函数计算其对应真值表中每个变量的相对混乱度和绝对混乱度,以最小混乱度原则选取三值可逆逻辑门,直至真值表中的每个变量的混乱度为零,得到三值可逆网络.该算法的时间复杂度为O(n2×3n),空间复杂度为O(n×3n).实验结果表明,与现有已知算法对比,平均门数更少.
Ternary reversible logic synthesis is the extension and expansion of reversible logic synthesis.In order to simplify the reversible network and improve the generality of ternary reversible logic gate,the effective value of controlling bits of the existing ternary reversible controlled gates can be extended to any of 0,1 and 2.And on the basis of that,a ternary reversible logic synthesis algorithm with minimum chaos degree is proposed.The algorithm is used to compute the relative chaos degree and absolute chaos degree of each variable in truth table under ternary logic system,according to the reversible function.As one reversible logic gate is selected,the principle of minimal chaos degree in ternary reversible logic synthesis should be followed until the relative chaos degree and absolute chaos degree of each variable in truth table decrease to 0,which means the synthesis has been finished,and the reversible network can be derived.The time complexity for the algorithm is O（n2×3n）,and its space complexity is O（n×3n）.The experimental results show that the average number of gates is less than the existing algorithms as known.
出处
《电子学报》
EI
CAS
CSCD
北大核心
2013年第7期1352-1357,共6页
Acta Electronica Sinica
基金
国家自然科学基金(No.60873069)
关键词
三值可逆逻辑门
三值可逆逻辑综合
混乱度
ternary reversible logic gate
ternary reversible logic synthesis
chaos degree
