[發明專利]利用共享ZMODD提取ESOP乘積項間公因子的可逆電路綜合方法

有效

• 申請號: 201810725176.1
• 申請日: 2018-07-04
• 公開（公告）號: CN108920837B
• 公開（公告）日: 2023-04-07
• 發明（設計）人: 卜登立
• 申請（專利權）人: 卜登立
• 主分類號: G06F30/30
• 分類號: G06F30/30
• 代理公司: 北京市盛峰律師事務所 11337
• 代理人: 于國富

本發明公開一種利用共享ZMODD提取ESOP乘積項間公因子的可逆電路綜合方法，屬于可逆電路綜合與設計技術領域；該方法主要包括以下步驟：使用共享ZMODD表示多輸出函數的ESOP，由共享ZMODD采取迭代方式提取ESOP乘積項間的公因子，根據提取公因子的結果，進行可逆電路綜合。本發明通過共享ZMODD來表示ESOP立方體集合，借助現有變量排序技術Sifting技術對共享ZMODD進行變量排序，根據輸入變量結點的共享來提取立方體間的公因子，可以提取數量大于2的立方體間的公因子，同時也可以做到盡可能地提取多個立方體間的最大公因子，從而在量子成本與量子位數之間進行權衡，并降低綜合所得可逆電路的量子成本。

技術領域

本發明涉及可逆電路綜合與設計技術領域，尤其涉及一種利用共享ZMODD提取ESOP乘積項間公因子的可逆電路綜合方法。

背景技術

可逆電路是采用信息無損計算模式的電路形式，可以實現理論上的近似零功耗。由于量子計算的固有可逆性，使得可逆電路成為量子計算機的基本部件以及量子電路模型的核心部分。降低可逆電路的量子成本有助于降低量子電路實現的計算復雜度，減少可逆電路的量子位數則有助于降低量子電路實現的硬件復雜度。

積之異或和(ESOP，Exclusive-Sum-Of-Products)，是函數基于“與-異或”運算的邏輯表示，即由異或運算連接一組乘積項的表示形式，常采用立方體集合表示。零抑制多輸出決策圖(ZMODD，Zero-suppressed?Multiple-Output?Decision?Diagram)，是立方體特別是多輸出立方體的一種圖形表示，如果將一個ESOP立方體表示為一個ZMODD，那么ESOP立方體集合則可以表示為共享ZMODD。

由于ESOP的乘積項可以直接映射為一個多控制線的可逆邏輯門，因此常被用來作為一種表示模型進行可逆電路的綜合。為降低由ESOP綜合所得可逆電路的量子成本，現有基于ESOP的可逆電路綜合方法常采用立方體表示并通過立方體分解來提取乘積項間的公因子，由于立方體表示難以直接體現乘積項間的結構相似性，因此不利于乘積項間公因子的提取，不利于降低綜合所得可逆電路的量子成本。

Lukac?M等采用的ESOP立方體分解方法僅提取乘積項間文字數為2的公因子。該文方法一是沒有對立方體的輸入部分進行變量排序，因此不能很好地提取多個乘積項間的公因子，盡管該文方法可以在一定程度上降低由ESOP綜合所得可逆電路的量子成本，但是相對而言量子成本仍然較高；二是沒有提取乘積項間的最大公因子，導致綜合所得可逆電路的量子位數較多。(Lukac?M?et?al，2011)

Parlapalli?S?P等采用的ESOP立方體分解方法僅提取2個立方體間的公因子，盡管可以做到提取2個乘積項間的最大公因子，使得綜合所得可逆電路的量子位數較少，但是由于沒有提取數量大于2的立方體間的公因子，導致綜合所得可逆電路的量子成本較高。(Parlapalli?S?P?et?al，2017)

綜上所述，目前基于ESOP立方體分解的可逆電路綜合方法一是綜合所得可逆電路的量子成本較高，二是沒有綜合考慮量子成本與量子位數，在量子成本和量子位數之間進行權衡，因此亟待找到一種新的可逆電路綜合方法，能夠在量子成本和量子位數之間進行權衡，并降低綜合所得可逆電路的量子成本。

參考文獻：

Lukac?M,Kameyama?M,Perkowski?M,Kerntopf?P.Decomposition?of?reversiblelogic?function?based?on?cube-reordering[J].FACTA?UNIVERSITATIS(NIS),2011,24(3):403-422.