CAJ | 학술논문

三值可逆逻辑综合是可逆逻辑综合的延伸和扩展．为了简化可逆网络，提高三值可逆逻辑门的通用性，对现有三值可逆控制门控制位的生效值扩展为0、1和2．在此基础上提出了基于最小混乱度原则的三值可逆逻辑综合算法．该算法根据三值可逆函数计算其对应真值表中每个变量的相对混乱度和绝对混乱度，以最小混乱度原则选取三值可逆逻辑门，直至真值表中的每个变量的混乱度为零，得到三值可逆网络．该算法的时间复杂度为 O（n2×3n ），空间复杂度为 O（n ×3n）．实验结果表明，与现有已知算法对比，平均门数更少．
삼치가역라집종합시가역라집종합적연신화확전．위료간화가역망락，제고삼치가역라집문적통용성，대현유삼치가역공제문공제위적생효치확전위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 exist-ing ternary reversible controlled gates can be extended to any of 0 ,1 and 2 .And on the basis of that ,a ternary reversible logic syn-thesis 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 × 3 n ) ,and its space complexity is O ( n × 3 n ) . The experimental results show that the average number of gates is less than the existing algorithms as known .