分辨矩陣在邏輯優(yōu)化中的應(yīng)用

閆心怡，溫 馨，陳澤華+

1.太原理工大學(xué) 電氣與動(dòng)力工程學(xué)院，太原 030024

2.太原理工大學(xué) 大數(shù)據(jù)學(xué)院，太原 030024

組合邏輯電路[1]由門(mén)電路組成，門(mén)之間的相互連接形成了邏輯網(wǎng)絡(luò)。邏輯網(wǎng)絡(luò)可由布爾函數(shù)或真值表來(lái)描述。通過(guò)化簡(jiǎn)布爾函數(shù)或真值表，可以減少邏輯網(wǎng)絡(luò)的復(fù)雜性，從而提高電路的可靠性并降低系統(tǒng)功耗。K-map（Karnaugh map）[1]是典型的圖形表示的布爾函數(shù)化簡(jiǎn)方法，當(dāng)輸入變量超過(guò)5 時(shí)其圖形難以理解。Q-M（Quine-McCluskey algorithms）[1]方法更便于計(jì)算機(jī)計(jì)算，但是Q-M 算法的運(yùn)行時(shí)間隨變量數(shù)量呈指數(shù)增長(zhǎng)。隨著電路規(guī)模不斷擴(kuò)大，數(shù)據(jù)挖掘理論的迅速發(fā)展，從知識(shí)工程角度重新考慮邏輯電路優(yōu)化，是一種新的思路。

經(jīng)典粗糙集理論由Pawlak 提出，除了通過(guò)定義上、下近似完成知識(shí)的近似表達(dá)，還可以基于等價(jià)關(guān)系處理信息系統(tǒng)，在保證信息不減的前提下實(shí)現(xiàn)知識(shí)約簡(jiǎn)或規(guī)則提取。

Skowron 教授提出的不可分辨矩陣[2-3]是信息系統(tǒng)屬性約簡(jiǎn)和規(guī)則提取的經(jīng)典方法，在此基礎(chǔ)上衍生出很多相關(guān)改進(jìn)算法[4-11]，有學(xué)者將其與覆蓋[6]、模糊粗糙集[7]啟發(fā)式算子聯(lián)系起來(lái)構(gòu)建新的辨識(shí)矩陣，使之能夠?qū)σ恢?、不一致系統(tǒng)進(jìn)行更為有效的屬性約簡(jiǎn)和規(guī)則提取。近年來(lái)，學(xué)者將分辨矩陣和形式概念分析[12-14]結(jié)合起來(lái)，基于分辨矩陣的方法也在形式概念分析中發(fā)展起來(lái)。

在邏輯電路的分析與設(shè)計(jì)中，真值表用來(lái)表征數(shù)字邏輯電路輸入與輸出之間的邏輯關(guān)系，真值表約簡(jiǎn)是邏輯優(yōu)化的理論基礎(chǔ)。本文將真值表看作邏輯信息系統(tǒng)（logic information system，LIS）[15]，在傳統(tǒng)分辨矩陣基礎(chǔ)上構(gòu)造了粒分辨矩陣，與多粒度形式概念分析的類(lèi)屬性塊方法[16]中一樣，試圖尋找決策蘊(yùn)含與不同屬性組合之間的關(guān)系，但是不同的是本文通過(guò)定義信息粒來(lái)分析屬性與決策間的關(guān)系，將邏輯電路化簡(jiǎn)轉(zhuǎn)化為基于粒分辨矩陣的LIS 最簡(jiǎn)規(guī)則發(fā)現(xiàn)問(wèn)題。該方法避免了傳統(tǒng)分辨矩陣中大量的矩陣元素計(jì)算問(wèn)題，同時(shí)證明了該方法與傳統(tǒng)卡諾圖約簡(jiǎn)的等價(jià)性。

1 預(yù)備知識(shí)

數(shù)字電路可以用布爾函數(shù)以及真值表進(jìn)行表示。它們處理的是“0”“1”信號(hào)。

定義1（真值表）真值表是表征邏輯事件輸入和輸出之間全部可能狀態(tài)的表格，它對(duì)所有可能的邏輯輸入定義了對(duì)應(yīng)的邏輯輸出，用邏輯關(guān)系的表格形式表示。真值表的輸入包括了全部n個(gè)變量的乘積項(xiàng)（每個(gè)變量只以原變量或反變量的形式出現(xiàn)一次），稱為最小項(xiàng)。n個(gè)輸入變量的真值表包含2n個(gè)最小項(xiàng)，用表示。

定義2（最小項(xiàng)表達(dá)式）真值表中對(duì)應(yīng)所有邏輯函數(shù)值為1 的最小項(xiàng)之和，稱為最小項(xiàng)表達(dá)式。

定義3（最簡(jiǎn)邏輯函數(shù)表達(dá)）化簡(jiǎn)后的真值表中所有邏輯函數(shù)值為1 的條件屬性乘積項(xiàng)的組合稱為最簡(jiǎn)邏輯函數(shù)表達(dá)式。

定義4[15]（邏輯信息系統(tǒng)）定義LIS=(U,R,V,f)為一個(gè)邏輯信息系統(tǒng)，其中U為論域，|U|表示論域元素個(gè)數(shù)，R=A?Y為屬性集，A={A1,A2,…,Am}表示邏輯信息系統(tǒng)的輸入變量（條件屬性），|A|表示條件屬性的個(gè)數(shù)，Y={Y1,Y2,…,Yn}表示邏輯信息系統(tǒng)的輸出變量（決策屬性），|Y|表示決策屬性的個(gè)數(shù)。V={0,1} 是屬性值的值域，f:U×R→V是一個(gè)信息函數(shù)，它指定U中每一個(gè)對(duì)象的屬性值。

真值表是一個(gè)邏輯信息系統(tǒng)，它的每一行代表一條邏輯規(guī)則。

特殊地，當(dāng)n=1 時(shí)，這是一個(gè)多輸入單輸出邏輯信息系統(tǒng)。

從邏輯信息系統(tǒng)的角度研究真值表，可以將數(shù)字邏輯電路中的邏輯優(yōu)化問(wèn)題轉(zhuǎn)化為信息系統(tǒng)最簡(jiǎn)單規(guī)則發(fā)現(xiàn)問(wèn)題。

定義5（信息粒）邏輯信息系統(tǒng)中的任意邏輯輸入變量Ai∈A可以導(dǎo)出論域U的一個(gè)劃分：

式中，fAi(u)=0 表示在屬性Ai論域下具有屬性值0 的論域元素u。同樣的表示在屬性Ai下論域中具有屬性值1 的論域元素u?？梢缘玫接奢斎胱兞緼i推導(dǎo)出的等價(jià)類(lèi)劃分，本文將該等價(jià)類(lèi)劃分定義為信息粒。由邏輯輸入屬性Ai∈A推導(dǎo)出的所有信息粒構(gòu)成了一個(gè)信息粒集（information granular set，IGS）。

定義6（決策類(lèi)劃分）對(duì)于任何邏輯輸出屬性Yi，其屬性值也將在整個(gè)論域中劃分。定義U0=，表示輸出屬性Yi中所有屬性值為“0”的論域元素。相應(yīng)地，，表示輸出屬性Yi中所有屬性值為“1”的論域元素。

顯然地，U0?U1=U，U0?U1=?。

定義7（粒分辨矩陣）本文利用等價(jià)類(lèi)定義信息粒，進(jìn)而構(gòu)成粒分辨矩陣。對(duì)于多輸入單輸出信息系統(tǒng)，定義粒分辨矩陣：

式中元素：

式中，cij表示信息粒集合中能夠區(qū)分元素ui∈U1與元素uj∈U0的信息粒，X表示信息粒集合中的任一元素。同時(shí)p=|U1|表示輸出屬性Yi中所有屬性值為“1”的論域元素個(gè)數(shù)。q=|U0|表示輸出屬性Yi中所有屬性值為“0”的論域元素個(gè)數(shù)。

定義8（決策規(guī)則）組織粒分辨矩陣中的元素cij，定義決策規(guī)則：

式中，ri包含所有能區(qū)分ui∈U1與uj∈U0中的所有元素，DR即為能區(qū)分等價(jià)類(lèi)U0和U1的最簡(jiǎn)規(guī)則集，dr作為其中的一條規(guī)則。

定義9（啟發(fā)式信息）在最簡(jiǎn)規(guī)則基礎(chǔ)上提出啟發(fā)式信息：

式中，|dr|表示規(guī)則的信息粒組合的個(gè)數(shù)。

2 粒分辨矩陣的邏輯表達(dá)式優(yōu)化算法

根據(jù)第1 章的相關(guān)內(nèi)容，本文針對(duì)真值表提出了一種基于粒分辨矩陣的約簡(jiǎn)算法。

2.1 算法描述

算法1基于粒分辨矩陣的真值表約簡(jiǎn)算法

輸入：真值表。

輸出：最小布爾邏輯表達(dá)式。

步驟1計(jì)算U0和U1，初始化MBE=?，計(jì)算信息粒。

步驟2計(jì)算邏輯輸出的粒分辨矩陣C。

步驟3根據(jù)粒分辨矩陣元素cij組織決策規(guī)則，計(jì)算每條規(guī)則的啟發(fā)式信息He。

步驟4對(duì)He由大到小排序，判斷每條規(guī)則是否存在新識(shí)別的論域元素。

步驟5若存在，將該條規(guī)則記錄到MBE中；同時(shí)判斷是否覆蓋U1集合中的所有元素，若覆蓋跳到步驟7，否則返回步驟4，繼續(xù)計(jì)算下一條規(guī)則。

步驟6否則，不記錄。

步驟7輸出最小布爾邏輯表達(dá)式MBE，結(jié)束。

可以證明本文所提算法與K-map方法的等價(jià)性：

對(duì)一個(gè)n行真值表，設(shè)有r個(gè)最小項(xiàng)F輸出變量值1 且Fi為其中一個(gè)最小項(xiàng)（0 ≤i≤r），則有n-r個(gè)最小項(xiàng)G輸出變量值0 且Gj為其中一個(gè)最小項(xiàng)（0 ≤j≤n-r）。

設(shè)Fi與Gj不同的輸入變量為X1,X2,…,Xs，則在卡諾圖中可以形成s組互補(bǔ)的包圍圈，其中任一組包圍圈中的均包含最小項(xiàng)Fi在卡諾圖中的“1”，而不包含Gj，因此這s組包圍圈互相為“或”關(guān)系。同理，若使得Fi與n-r個(gè)輸出變量值為0 的最小項(xiàng)G都區(qū)分出來(lái)，則需Fi與n-r個(gè)最小項(xiàng)形成的包圍圈互相為“與”關(guān)系。

粒分辨矩陣中，行為真值表中輸出為1 的最小項(xiàng)Fi，列為輸出為0的最小項(xiàng)Gj。矩陣元素cij為Fi與Gj不同的邏輯輸入變量，cij中任一變量均可區(qū)分Fi與Gj，故cij中，各變量為“或”關(guān)系，cij=X1∨X2∨…∨Xs，cij和Fi所在s組包圍圈對(duì)應(yīng)。同理，若欲得到Fi與所有輸出變量值為0 的最小項(xiàng)G都不同的邏輯輸入變量，需n-r個(gè)cij為相“與”關(guān)系，即ci1∧ci2∧…∧cir。由上述分析可知，粒分辨矩陣方法與卡諾圖方法原理相同，故粒分辨矩陣方法等價(jià)于卡諾圖方法。

2.2 實(shí)例說(shuō)明

邏輯電路與邏輯表達(dá)式是可以轉(zhuǎn)化為真值表來(lái)表示的，本文將通過(guò)例2 來(lái)說(shuō)明算法1 的實(shí)施過(guò)程。

例2對(duì)于圖2 邏輯電路圖，其函數(shù)式為Y=?？梢詫D1 轉(zhuǎn)化為如表1 所示真值表，對(duì)于有3 個(gè)邏輯輸入的邏輯電路，其對(duì)應(yīng)的真值表有8 行數(shù)據(jù)。

Fig.1 Complementary encirclement diagram圖1 包圍圈示意圖

Fig.2 Logic circuit diagram圖2 邏輯電路圖

Table 1 Truth table表1 真值表

本例以邏輯輸出Y為例說(shuō)明本文算法的運(yùn)算過(guò)程，如表1 所示，可知：

論域U={0,1,2,3,4,5,6,7}，邏輯輸入屬性為A={A,B,C}，邏輯輸出屬性為Y，根據(jù)定義4 可以得到：

同理可得：

構(gòu)造粒分辨矩陣：

同理可得矩陣中的其他元素，得到如上矩陣計(jì)算結(jié)果。

根據(jù)定義8 計(jì)算決策規(guī)則可得：

最后根據(jù)式（4）可以得到：

Table 2 Heuristic information表2 啟發(fā)式信息

根據(jù)文獻(xiàn)[1]中的卡諾圖化簡(jiǎn)方法首先得到圖3，由圖可知卡諾圖化簡(jiǎn)結(jié)果為。對(duì)比兩種方法的結(jié)果可知，本文算法所得結(jié)果與卡諾圖化簡(jiǎn)結(jié)果一致。

Fig.3 Karnaugh map reduction diagram圖3 卡諾圖化簡(jiǎn)示意圖

3 算法分析

K-map 方法使用簡(jiǎn)單直觀，但是圖形表示難以描述5 個(gè)以上的輸入變量；Q-M 算法使得K-map 方法易于在計(jì)算機(jī)上實(shí)現(xiàn)。對(duì)于含有m個(gè)輸入的真值表，|A|=m,|U|=2m，Q-M 算法的時(shí)間復(fù)雜度為O(|U|×3|A|)，即O(2m×3m)。在粒矩陣法（granular matrix reduction algorithm，GMRA）[15]中，用粒度計(jì)算和矩陣來(lái)區(qū)分真值表中的所有“1”，將邏輯化簡(jiǎn)問(wèn)題轉(zhuǎn)化為布爾矩陣運(yùn)算的問(wèn)題，算法的時(shí)間復(fù)雜度為O(|U|2×|A|×2|A|)，即O(m×23m)。文獻(xiàn)[17]提出的變粒度真值表約簡(jiǎn)算法（variable granularity reduction algorithm，VGRA），隨著真值表的輸入邏輯變量的粒度變化，通過(guò)引入標(biāo)記矩陣和啟發(fā)式算子，對(duì)大規(guī)模真值表進(jìn)行知識(shí)約簡(jiǎn)，其算法復(fù)雜度為O(|U|×|A|×2|A|)，即O(m×22m)。文獻(xiàn)[18]將MIMO（multiple input multiple output）真值表轉(zhuǎn)化為決策形式背景，將真值表的約簡(jiǎn)問(wèn)題轉(zhuǎn)化為決策形式背景的最簡(jiǎn)規(guī)則提取過(guò)程，提出一種基于FCA（formal concept analysis）的MIMO 真值表并行約簡(jiǎn)算法，其算法的復(fù)雜度為O(|U|×|A|)+O(|U|2×|A|2lb(|U|×|A|))，即O(m×2m)+O(22m×m3×lbm)。

本文算法中，粒分辨矩陣C=[cij]的規(guī)模為p×q，其中p+q=2m，而經(jīng)典分辨矩陣的規(guī)模為2m×2m。從矩陣的規(guī)?？梢钥吹?，矩陣復(fù)雜度大大下降。生成本文提出的粒分辨矩陣C的計(jì)算復(fù)雜度O(p×q)，決策規(guī)則的計(jì)算復(fù)雜度為O(q)，規(guī)則提取過(guò)程的計(jì)算復(fù)雜度為O(p)，故整個(gè)算法復(fù)雜度為O(p2×q2)，在最壞情況下也遠(yuǎn)小于O(22m-1)。各算法復(fù)雜度對(duì)比如表3 所示。

GMRA 算法復(fù)雜度以指數(shù)8 為底，Q-M 算法復(fù)雜度則以指數(shù)6 為底，VGRA 算法復(fù)雜度以指數(shù)4 為底。本文提出的GMD 算法，在傳統(tǒng)分辨矩陣的基礎(chǔ)上，簡(jiǎn)化了矩陣的規(guī)模，避免了大量矩陣元素的計(jì)算，同時(shí)利用啟發(fā)因子的優(yōu)勢(shì)，加快算法收斂速度。較Q-M 算法以及其他算法在計(jì)算復(fù)雜度上具有明顯的優(yōu)勢(shì)。

Table 3 Complexity comparison表3 復(fù)雜度對(duì)比

4 結(jié)束語(yǔ)

本文將分辨矩陣應(yīng)用到邏輯優(yōu)化中，提出了一種獲取最小布爾表達(dá)式的方法。構(gòu)造粒分辨矩陣區(qū)分真值表中的所有“1”，本文從理論證明和實(shí)例分析的角度，說(shuō)明了算法的正確性和有效性。

本文的創(chuàng)新之處在于：（1）粒分辨矩陣與傳統(tǒng)的分辨矩陣不同，它既不是方陣也不對(duì)稱，大大減少了矩陣規(guī)模。（2）矩陣的元素由信息粒度（等價(jià)類(lèi)代替屬性）表示，而非將屬性作為基本元素。（3）證明了本文算法與卡諾圖法的等價(jià)性。（4）以覆蓋真值表中所有的輸出“1”為終止條件，簡(jiǎn)便運(yùn)算同時(shí)避免了規(guī)則的冗余。

在下一步的研究工作中，可以繼續(xù)將該方法擴(kuò)展到多輸出邏輯信息系統(tǒng)中。雖然從算法復(fù)雜度的角度來(lái)看，本文算法比以往算法的復(fù)雜度有所下降，但是依舊以指數(shù)形式增長(zhǎng)。在以后的工作中可以探索并行計(jì)算方式，并能夠?qū)⑾嚓P(guān)成果和概念研究融合起來(lái)。另外本文方法還暫未推廣至普通的信息系統(tǒng)中，方法仍需要繼續(xù)改進(jìn)擴(kuò)展，這也是未來(lái)努力需要解決的問(wèn)題。