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

有效

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

1.一種基于貪婪算法的同或/或電路的分解方法，其特征在于首先引入同或/或電路表達式，將多輸入同或/或門的分解問題轉換為最小二叉樹搜索問題，然后采用貪婪算法分解同或/或電路中的多輸入或門，再在多輸入或門分解的基礎上采用貪婪算法分解同或/或電路中的多輸入同或門，具體包括以下步驟：

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

②定義S_k項代表的或門的開關活動性為SA_OR_S_k，將S_k項代表的或門的輸入變量x_i定義為最小二叉樹搜索問題中的樹，樹的數(shù)量為m，將S_k項代表的或門分解得到的二輸入或門的開關活動性定義為兩棵樹間的距離，每個輸入變量x_i的輸入概率P(x_i)作為其對應樹的概率，記在該樹的樹根，S_k項代表的或門的輸出概率記為P(S_k)；

③采用貪婪算法分解同或/或電路中的多輸入或門，得到S_k項代表的或門的開關活動性SA_OR_S_k和S_k項代表的或門的輸出概率P(S_k)；

④將所有或門的開關活動性累加，得到同或/或電路中所有或門的總開關活動性，同或/或電路中或門的數(shù)量為q,，其中SA_OR表示同或/或電路中所有或門的總開關活動性，將所有或門的輸出概率P(S_k)記入一個長度為q的數(shù)組中，將該數(shù)組作為同或/或電路中同或門輸入變量的輸入概率；

⑤采用貪婪算法分解同或/或電路中的多輸入同或門，得到同或/或電路中所有同或門的總開關活動性SA_XNOR；

⑥將同或/或電路中所有或門的總開關活動性SA_OR和同或/或電路中所有同或門的總開關活動性SA_XNOR相加，得到同或/或電路的總開關活動性SA_total，SA_total=Σk=1qSA_OR_Sk+SA_XNOR.]]>