[發明專利]一種基于貪婪算法的同或/或電路的分解方法

有效

• 申請號: 201210389864.8
• 申請日: 2012-10-15
• 公開（公告）號: CN102915392A
• 公開（公告）日: 2013-02-06
• 發明（設計）人: 張會紅;汪鵬君
• 申請（專利權）人: 寧波大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 寧波奧圣專利代理事務所(普通合伙) 33226
• 代理人: 程曉明

技術領域

本發明涉及一種邏輯門電路的低功耗分解技術，尤其是涉及一種基于貪婪算法的同或/或電路的分解方法。

背景技術

隨著集成電路的發展，功耗已成為集成電路設計中的關鍵性限制因素。以低功耗為目標的里德穆勒(RM)電路極性優化已引起了廣泛關注。其中，多輸入門分解是影響RM電路功耗的關鍵性環節之一，不同的分解方法將使電路具有不同的功耗。因此，研究RM電路的低功耗分解具有現實意義。

目前，對于同或/或電路，其多輸入或門由于輸出信號的概率隨著輸入信號的概率而增大，一般采用霍夫曼算法進行分解；而同或/或電路中的多輸入同或門目前主要采用隨機順序分解方法或者分類分解方法(分類分解方法見P.Wang,J.Lu,J.Xu,et?al.Power?optimization?algorithm?based?on?XNOR/OR?logic[J]..2009,26(1):138-144.[汪鵬君，陸金剛，徐建.基于XNOR/OR邏輯的功耗優化算法.電子科學學刊（英文版）.2009,26(1):138-144]）。隨機順序分解方法按照隨機順序將待分解的多輸入同或門分解為一系列二輸入同或門，沒有進行優化組合，其低功耗分解效果較差；而分類分解方法中將待分解的多輸入同或門分為三種情況：待分解的多輸入同或門的所有輸入信號的概率均大于0.5、待分解的多輸入同或門的所有輸入信號的概率均小于0.5和待分解的多輸入同或門同時包含概率大于0.5、等于0.5和小于0.5的輸入信號，通過將輸入信號分為三類，不同的類別采取不同的分解算法，其相對于隨機順序分解方法低功耗效果較好。但是由于分類分解方法中對于一個或多個輸入信號的概率為0.5的多輸入同或門往往留待最后考慮，因此無法保證低功耗分解的最優性。

發明內容

本發明所要解決的技術問題是提供一種可以通用于同或門和或門的低功耗分解，低功耗分解效果好的基于貪婪算法的同或/或電路的分解方法，

本發明解決上述技術問題所采用的技術方案為：一種基于貪婪算法的同或/或電路的分解方法，首先導入或讀入同或/或電路表達式，將多輸入同或/或門的分解問題轉換為最小二叉樹搜索問題，然后采用貪婪算法分解同或/或電路中的多輸入或門，再在多輸入或門分解的基礎上采用貪婪算法分解同或/或電路中的多輸入同或門，具體包括以下步驟：

①讀入同或/或電路表達式n為函數f(x₁,x₂,…,x_i…,x_n)的變量數，(x₁,x₂,…,x_i…,x_n)為函數f(x₁,x₂,…,x_i…,x_n)的n個輸入變量，i為正整數，且1≤i≤n，S_k項代表同或/或電路中的某個或門，且d_k為或項系數，且d_k∈{0,1}，當d_k=0時，表示S_k項在同或/或電路表達式中出現，當d_k=1時，表示S_k項不在同或/或電路表達式中出現，⊙∏表示同或操作，k為S_k項序號，k用二進制形式表示為k₁k₂…k_j…k_n，j為正整數，且1≤j≤n，當k_j＝0時，當k_j＝1時，S_k項代表的或門的輸入變量x_i的數量為m，m=Σj=1n(1-kj);]]>