[發明專利]通用可逆比較交換器

有效

• 申請號: 201310730155.6
• 申請日: 2013-12-26
• 公開（公告）號: CN103684368A
• 公開（公告）日: 2014-03-26
• 發明（設計）人: 徐明強;朱小社;杜江;何金鳳;徐海
• 申請（專利權）人: 南通紡織職業技術學院
• 主分類號: H03K5/22
• 分類號: H03K5/22
• 代理公司: 南京正聯知識產權代理有限公司 32243
• 代理人: 王素琴

技術領域

本發明使用了NOT門、CNOT門、Toffoli門、4-Toffoli門和Fredkin門這五種常用的基本可逆邏輯門，將這些可逆門進行級聯，構造出一種基于可逆邏輯的通用可逆比較交換器的級聯電路。?

背景技術

傳統計算機運用不可逆技術，運算過程中存在信息位丟失，根據Landauer原理，一個信息位的丟失將會導致kTln2(約為3*10^-21J，其中k為Boltzmann常量，T為當前熱力學溫度)能耗的損失。隨著集成電路的工藝水平和集成度不斷提高，集成電路中的芯片功能將會受到量子效應干擾，同時芯片的散熱問題無法從根本上解決，也將抑制傳統硅芯片技術的發展。?

可逆計算是一種新的計算模型，他通過恢復和重新利用丟失的數據來避免電路中的邏輯能耗的損失。從某種意義上講，計算的過程就是對數值按照一定的規則進行轉換演算。與傳統的不可逆計算不同，可逆計算在整個計算的過程中都是可逆的，即由計算中的任何一步中間結果可以反演算回它的前一步或者最初狀態，而在一般情況下，不可逆計算無法做到這一點。Bennett提出并證明了可逆計算在邏輯上是可行的。可逆電路的設計是實現可逆計算的重要步驟，而可逆門是實現可逆電路的基本運算單元，?Toffoli和Fredkin等人提出了幾種實現可逆計算的邏輯門，這使得對可逆邏輯部件的設計與實現成為了可能。對于可逆電路的設計，學者們投入了極大的熱情，多種不同功能的可逆電路，如可逆加法器、可逆乘法器、可逆除法器等相繼提出并設計完成。這些可逆邏輯部件的設計對可逆計算機的發展和實現具有巨大的理論意義指導和實踐支撐。?

發明內容

本發明的目的是提供一種通用可逆比較交換器，用可逆邏輯電路來解決兩個二進制數的數值比較。輸出比較結果并輸出這兩個二進制數，當第一個數在數值上比第二個數要小時，交換輸出這兩個二進制數。?

本發明通過以下的技術方案實現的：?

一種通用可逆比較交換器，由n個一位可逆完全比較器和n個Fredkin門級聯構造而成，該通用可逆比較交換器分別由n個常量輸入0、1個常量輸入1、2個常量輸入0，兩個n位二進制數A_i(n-1),?A_i(n-2)，…，A_i0和B_i(n-1),?B_i(n-2)，…，B_i0所組成,共3n+3個輸入;與之對應的輸出是n個垃圾輸出、O_A=B、O_A>B?、O_A<B，和兩個n位二進制數A_o(n-1),?A_o(n-2)，…，A_o0和B_o(n-1),?B_o(n-2)，…，B_o0。構成該通用可逆比較交換器的級聯電路的第一個器件為第一塊一位可逆完全比較器，第一塊一位可逆完全比較器的輸入I_A=B、I_A>B和I_A<B分別設置為1、0和0；第二個器件為第二塊一位可逆完全比較器,?第二塊一位可逆完全比較器的輸入I_A=B、I_A>B和I_A<B分別為第一塊一位可逆完全比較器的輸出O_A=B、O_A>B和O_A<B，依此類推第n-1個器件為第n-1塊一位可逆完全比較器，,第n-1塊一位可逆完全比較器的輸入I_A=B、I_A>B和I_A<B分別為第n-2塊一位可逆完全比較器的輸出O_A=B、O_A>B和O_A<B；第n個器件為第n塊一位可逆完全比較器，第n塊一位可逆完全比較器的輸入I_A=B、I_A>B和I_A<B分別為第n-1塊一位可逆完全比較器的輸出O_A=B、O_A>B和O_A<B。之后的n個Fredkin門的控制位都為第n塊一位可逆完全比較器的輸出O_A<B，目標位分別是第一塊一位可逆完全比較器的輸出A_o(n-1)和輸出B_o(n-1)，第二塊一位可逆完全比較器的輸出A_o(n-2)和輸出B_o(n-2)，依次類推，第n個Fredkin門的目標位是第n塊一位可逆完全比較器的輸出A_o0和輸出B_o0。