[發明專利]一種三值FPRM電路面積與功耗最佳極性搜索方法

有效

• 申請號: 201510552955.2
• 申請日: 2015-09-01
• 公開（公告）號: CN105205534B
• 公開（公告）日: 2017-09-29
• 發明（設計）人: 汪鵬君;厲康平;張會紅
• 申請（專利權）人: 寧波大學
• 主分類號: G06N3/12
• 分類號: G06N3/12;G06F17/30
• 代理公司: 寧波奧圣專利代理事務所(普通合伙)33226
• 代理人: 方小惠

技術領域

本發明涉及一種三值FPRM電路最佳極性搜索方法，尤其是涉及一種三值FPRM電路面積與功耗最佳極性搜索方法。

背景技術

多值邏輯電路單線攜帶信息能力強，能有效提高空間或時間的利用率，減少數字系統的連線，節省電路面積與成本。任意三值邏輯函數均可以用布爾邏輯和Reed-Muller(RM)邏輯來表示。與傳統的布爾邏輯電路相比，基于RM邏輯的電路具有以下三個方面的優勢：首先，在某些功能電路(算通信電路、奇偶校驗電路、運算電路等)中，用RM邏輯表示的電路在功耗、面積和速度等方面體現出了巨大的優勢；其次，用RM邏輯表示的電路可測性強；最后，用RM邏輯表示的電路結構更加緊湊。固定極性(Fixed-polarity Reed-Muller,FPRM)是RM邏輯常用表達方式。在三值FPRM邏輯函數中，n變量函數有3ⁿ個固定極性，對應3ⁿ個不同的三值FPRM表達式，其表達式的簡單與復雜程度由極性決定。由此可知，極性對三值FPRM電路的功耗、面積等性能產生很大的影響。

三值FPRM電路的功耗和面積屬于兩個獨立的性能指標，其功耗較小時面積不一定較小，面積較小時功耗也不一定較小。目前，三值FPRM電路的面積優化方法主要是通過找到最佳極性來實現面積優化。對較小規模的三值FPRM電路進行面積優化時，通常使用窮舉法遍歷表示該三值FPRM電路的RM邏輯函數的每個極性來搜索最佳極性；對較大規模三值FPRM電路的面積進行優化時，由于極性與變量存在指數關系使得搜索空間急劇增加，窮舉法很難在有限的時間內得到優化結果，目前最新的研究是采用整體退火遺傳算法在大規模三值FPRM電路面積優化時進行最佳極性搜索，從而得到最小面積，然而其極性搜索結果存在改進空間，難以找到最佳極性。而在FPRM電路的功耗優化方面，國內外專家學者的研究仍停留二值電路領域，對三值FPRM電路耗優化技術未進行研究。

人口遷移算法(Population Migration Algorithm，PMA)是以人口遷移規律為依據的一種新的全局優化搜索算法，主要模擬人口跟隨經濟中心轉移以及人口由于壓力增大而擴散的機制。人口遷移算法是一種全局優化的仿生算法，將目標函數的選擇空間模擬成人類的生存空間，將目標函數值模擬成某個地域的吸引力，利用人口流動、遷移和擴散行為搜索可行解，通過個體的流動、遷移和擴散行為找到局部最優解，最后比較多個局部最優解得到全局最優解。

遺傳算法通過選擇、交叉和變異三個操作模擬種群進化過程。首先，隨機產生初代種群，根據適應度函數計算每個個體的適應度值，按適應度值的大小評價個體的好壞。其次，通過選擇操作挑選出適應能力較強的個體。最后，通過對挑選出的個體進行交叉和變異操作，產生子代，形成新的種群。選擇操作能淘汰掉種群中適應能力較差的個體，選出優秀的個體。交叉操作隨機選擇兩個個體，將父代個體的部分結構進行替換，產生新的個體。選擇和交叉操作能保留種群中優秀的個體，避免了優秀個體的丟失。變異操作模擬基因突變現象，以極小的概率改變個體的某些基因，增加種群多樣性，能使算法避免陷入局部最優解。

鑒此，結合人口遷移算法和遺傳算法，設計一種三值FPRM電路面積與功耗最佳極性搜索方法具有重要意義。

發明內容

本發明所要解決的技術問題是提供一種三值FPRM電路面積與功耗最佳極性搜索方法。該方法可以找到面積與功耗最佳極性，同時優化三值FPRM電路的面積與功耗性能，提高三值FPRM電路的綜合性能。

本發明解決上述技術問題所采用的技術方案為：一種三值FPRM電路面積與功耗最佳極性搜索方法，包括以下步驟：

①構建人口遷移遺傳算法，人口遷移遺傳算法通過將遺傳算法融合到人口遷移算法中得到：在人口遷移算法中發生人口流動時加入遺傳算法的交叉操作和變異操作，在人口遷移算法中發生人口遷移時加入遺傳算法的交叉操作和變異操作；由此實現遺傳算法和人口遷移算法的融合；

②建立三值FPRM電路的面積估計模型和功耗估計模型：

②-1將三值FPRM電路用三值FPRM邏輯函數的表達式表示為：