閆心怡，溫 馨，陳澤華+

1.太原理工大學 電氣與動力工程學院，太原 030024

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

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

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

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

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

1 預備知識

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

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

定義2（最小項表達式）真值表中對應所有邏輯函數(shù)值為1 的最小項之和，稱為最小項表達式。

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

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

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

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

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

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

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

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

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

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

式中元素：

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

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

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

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

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

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

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

2.1 算法描述

算法1基于粒分辨矩陣的真值表約簡算法

輸入：真值表。

輸出：最小布爾邏輯表達式。

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

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

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

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

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

步驟6否則，不記錄。

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

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

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

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

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

2.2 實例說明

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

例2對于圖2 邏輯電路圖，其函數(shù)式為Y=。可以將圖1 轉(zhuǎn)化為如表1 所示真值表，對于有3 個邏輯輸入的邏輯電路，其對應的真值表有8 行數(shù)據(jù)。

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

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

Table 1 Truth table表1 真值表

本例以邏輯輸出Y為例說明本文算法的運算過程，如表1 所示，可知：

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

同理可得：

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

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

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

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

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

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

Fig.3 Karnaugh map reduction diagram圖3 卡諾圖化簡示意圖

3 算法分析

K-map 方法使用簡單直觀，但是圖形表示難以描述5 個以上的輸入變量；Q-M 算法使得K-map 方法易于在計算機上實現(xiàn)。對于含有m個輸入的真值表，|A|=m,|U|=2m，Q-M 算法的時間復雜度為O(|U|×3|A|)，即O(2m×3m)。在粒矩陣法（granular matrix reduction algorithm，GMRA）[15]中，用粒度計算和矩陣來區(qū)分真值表中的所有“1”，將邏輯化簡問題轉(zhuǎn)化為布爾矩陣運算的問題，算法的時間復雜度為O(|U|2×|A|×2|A|)，即O(m×23m)。文獻[17]提出的變粒度真值表約簡算法（variable granularity reduction algorithm，VGRA），隨著真值表的輸入邏輯變量的粒度變化，通過引入標記矩陣和啟發(fā)式算子，對大規(guī)模真值表進行知識約簡，其算法復雜度為O(|U|×|A|×2|A|)，即O(m×22m)。文獻[18]將MIMO（multiple input multiple output）真值表轉(zhuǎn)化為決策形式背景，將真值表的約簡問題轉(zhuǎn)化為決策形式背景的最簡規(guī)則提取過程，提出一種基于FCA（formal concept analysis）的MIMO 真值表并行約簡算法，其算法的復雜度為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ī)?？梢钥吹?，矩陣復雜度大大下降。生成本文提出的粒分辨矩陣C的計算復雜度O(p×q)，決策規(guī)則的計算復雜度為O(q)，規(guī)則提取過程的計算復雜度為O(p)，故整個算法復雜度為O(p2×q2)，在最壞情況下也遠小于O(22m-1)。各算法復雜度對比如表3 所示。

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

Table 3 Complexity comparison表3 復雜度對比

4 結(jié)束語

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

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

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