陳澤華馬 賀

（太原理工大學(xué)信息工程學(xué)院 太原 030024）

基于粒矩陣的多輸入多輸出真值表快速并行約簡算法

陳澤華*馬 賀

（太原理工大學(xué)信息工程學(xué)院 太原 030024）

真值表是表征邏輯輸入與輸出之間因果關(guān)系的重要工具，真值表約簡在數(shù)字邏輯電路的分析與設(shè)計中具有重要意義。該文將真值表看作邏輯信息系統(tǒng)，將真值表約簡轉(zhuǎn)化為邏輯信息系統(tǒng)的最簡規(guī)則獲取。采用粒計算分層?；乃枷?，在不同粒度下，利用粒矩陣的知識表示形式、粒矩陣中的啟發(fā)式知識以及粒矩陣運(yùn)算，設(shè)計了多輸入多輸出真值表快速并行約簡算法。以發(fā)光二極管七段數(shù)字顯示器為例進(jìn)行了算法說明，通過數(shù)學(xué)證明和算法復(fù)雜性分析證明了算法的正確性和有效性。

數(shù)字邏輯電路；真值表；粒度；粒矩陣；并行約簡；粒計算

1 引言

真值表約簡在數(shù)字邏輯電路分析與設(shè)計中具有重要作用。經(jīng)典方法有卡諾圖法、公式法、Q-M及其改進(jìn)算法以及立方體算法等［17］-。當(dāng)輸入變量增大時，前3種方法算法復(fù)雜度比較高，不利于程序?qū)崿F(xiàn)，而且不能對多個輸出進(jìn)行并行處理。立方體算法［2］相對簡單，可以處理多輸出，本質(zhì)依然依靠邏輯代數(shù)運(yùn)算規(guī)律。目前，真值表約簡算法被內(nèi)嵌在國外的電子設(shè)計自動化軟件中，工程師們不再需要自行設(shè)計約簡算法。因此，國內(nèi)外對真值表的約簡問題研究成果仍然停留在十幾年前。

粒計算［8］求解復(fù)雜問題的思想和方法受到關(guān)注，基于粒計算的信息系統(tǒng)知識處理方法得到快速發(fā)展［915］-。文獻(xiàn)［16］將真值表看作邏輯信息系統(tǒng)，從知識工程角度分析真值表，將真值表看作等價關(guān)系的粒計算模型，通過分層?；?、矩陣運(yùn)算，將傳統(tǒng)的真值表化簡過程轉(zhuǎn)化為基于粒矩陣運(yùn)算的邏輯信息系統(tǒng)的最簡規(guī)則提取過程。

本文進(jìn)一步優(yōu)化了文獻(xiàn)［16］中的粒矩陣運(yùn)算，通過定理1減少了矩陣的存儲規(guī)模、提高了算法的搜索效率，并將其擴(kuò)展為多輸入多輸出（M IMO）真值表快速并行約簡算法。本文以發(fā)光二極管七段數(shù)字顯示器為例，詳述了算法步驟。最后通過數(shù)學(xué)推導(dǎo)，證明了本文算法與傳統(tǒng)卡諾圖約簡算法的等價性。通過理論分析，探討了算法的復(fù)雜性和有效性。

2 預(yù)備知識

定義1 真值表、最小項表達(dá)式、最簡邏輯函數(shù)表達(dá)式［1-3］：真值表是表征邏輯事件輸入和輸出之間全部可能狀態(tài)的表格，是邏輯因果關(guān)系的表格表示。當(dāng)一個真值表同時有多個輸出時，稱為多輸出真值表。真值表中全部m個輸入變量的乘積項（每個變量只以原變量或反變量的形式出現(xiàn)一次）稱為最小項。真值表中所有邏輯函數(shù)值為1的最小項之和稱為最小項表達(dá)式。簡化后的真值表中所有輸出值為1的輸入變量乘積項的和稱為最簡邏輯函數(shù)表達(dá)式。

注：在下文中用黑體 Xi表示矩陣或向量，用Xi表示等價關(guān)系或等價類。

矩陣X表示輸入變量組合A'導(dǎo)出的等價類集合，矩陣Y0由全部n個輸出的“0”輸出向量構(gòu)成。矩陣Cs×n（下文簡稱C ）反映了所有等價類Xi與Yj1之間的包含關(guān)系，稱為矩陣X與Y的粒邏輯關(guān)系矩陣。·表示集合的勢。

下面通過定理1說明粒邏輯關(guān)系矩陣所表達(dá)的信息與含義：

3 多輸入多輸出真值表快速并行約簡算法

3.1 符號定義

3.2 算法描述

區(qū)別于傳統(tǒng)的任何一種算法，基于粒計算的多輸入多輸出（m輸入n輸出）真值表快速并行約簡算法的主要思想是：從知識工程的角度，從粗到細(xì)，在不同粒度空間下對邏輯信息系統(tǒng)進(jìn)行約簡，約簡的本質(zhì)是借用代數(shù)規(guī)則和統(tǒng)計規(guī)律為啟發(fā)式信息，通過粒矩陣運(yùn)算，用最少的輸入變量和變量值快速辨識出所有輸出屬性中所有的屬性值1。算法描述如表1所示。

3.3 計算實例

例1 數(shù)字顯示譯碼器［3］

發(fā)光二極管七段數(shù)字顯示器通常采用七段（a， b，c， d， e， f， g）字形顯示，如圖1所示。表2給出一種七段譯碼器的功能表，它接收8421BCD碼，輸出邏輯值為1時，對應(yīng)的字段點亮，輸出為0時，對應(yīng)的字段熄滅。顯示的字形圖如圖2所示。

表1 基于粒計算的多輸入多輸出真值表快速并行約簡算法

圖1 七段字形顯示

圖2 十進(jìn)制數(shù)字

（1）設(shè)置初始值ω=1，此時粒度最粗。下文用i表示Ai，可以得到

表2 七段譯碼器的邏輯信息系統(tǒng)

根據(jù)He的大小對Xω=1進(jìn)行排序，見表3，其中灰色規(guī)則表示重復(fù)識別的規(guī)則，不做記錄。此時ob ja=｛3，4，7，8，9，10｝， ob jb=｛1，2，3，4，9，10｝，均未完全區(qū)分輸出中的1，繼續(xù)計算。

（2）在細(xì)粒度ω=2上繼續(xù)計算：

可得

表3 ω1=的計算過程

計算并根據(jù)He的大小對Xω=2進(jìn)行排序，見表4。表4中灰色的規(guī)則表示其分辨出來的行已經(jīng)被包含在ob j中，不做記錄。由于本次計算至Xω=2中的前3個 Xi就已經(jīng)完成了運(yùn)算。因此表4只列出了這3個 Xi。

表4 ω2=的計算過程

4 算法分析

4.1 算法正確性證明

在單輸出情況下，本算法與卡諾圖約簡算法等價。證明如下：

等價性證明保證了本文算法的正確性。

4.2 算法復(fù)雜性分析

4.3 無關(guān)項的處理

當(dāng)真值表含有無關(guān)項時，應(yīng)用卡諾圖法、Q-M算法和立方體算法時，無關(guān)項通常被假設(shè)為1參與運(yùn)算，最后需要驗證無關(guān)項是否構(gòu)成冗余項，如果是則刪除，否則留下得到最終結(jié)果。將真值表當(dāng)作LIS進(jìn)行處理，不需要對無關(guān)項的輸出做任何假設(shè)，通過設(shè)定粒度，會自動按需將無關(guān)項放入卡諾圖法對應(yīng)的大圈中，化簡結(jié)果不受影響。

5 結(jié)束語

Q-M算法及其改進(jìn)算法本質(zhì)是卡諾圖方法的擴(kuò)展。立方體方法本質(zhì)依據(jù)邏輯運(yùn)算規(guī)則［2］。本文提出的基于粒矩陣的真值表快速并行約簡算法，本質(zhì)上是從信息處理角度在不同粒度空間下實現(xiàn)邏輯規(guī)則的并行約簡，在思路上與傳統(tǒng)方法不同，在算法上還有進(jìn)一步優(yōu)化的空間。

本文創(chuàng)新之處在于：（1）將真值表當(dāng)作邏輯信息系統(tǒng)，在不同的粒度空間，通過定義粒矩陣及其基本運(yùn)算，并行實現(xiàn)邏輯規(guī)則化簡；（2）利用二值邏輯特性，將文獻(xiàn)［16］中尋找矩陣中的NE（i）=1轉(zhuǎn)變?yōu)閷ふ襝ij=0，減小了相關(guān)的數(shù)值比較和搜索，并將輸出矩陣規(guī)模減半，從而降低了算法的空間復(fù)雜度和時間復(fù)雜度；（3）通過矩陣運(yùn)算并設(shè)置啟發(fā)式算子和終止條件，并行得到所有輸出的邏輯化簡，提高了計算效率；（4）不需要單獨考慮無關(guān)項；（5）證明了本文算法與經(jīng)典的卡諾約簡方法是等價的。以上幾點決定了本文算法的快速性和可靠性。

真值表化簡是數(shù)字邏輯電路分析和設(shè)計中的重要問題，本文將等價關(guān)系的粒計算模型應(yīng)用于m輸入n輸出真值表化簡，一方面豐富了粒計算理論研究，另一方面為數(shù)字邏輯電路的分析與設(shè)計提供了新思路。如何將二元關(guān)系的粒計算模型［17］推廣到時序邏輯電路中的狀態(tài)轉(zhuǎn)移表（圖）的化簡是我們正在進(jìn)行的工作。

［1］ 閻石. 數(shù)字電子技術(shù)基礎(chǔ)［M］. 第5版， 北京: 高教出版社，2006: 29-54.Yan Shi. Fundamentals of Digital Electronics［M］. 5th Edition，Beijing: Higher Education Press， 2006: 29-54.

［2］ 邊計年， 薛宏熙， 蘇明， 等. 數(shù)字系統(tǒng)設(shè)計自動化［M］. 第2版北京: 清華大學(xué)出版社， 2005: 221-226. Bian Ji-nian， Xue Hong-xi， Su M ing， et al.. Design Automation for Digital Systems［M］。 2nd Edition， Beijing: Tsinghua University Press， 2005: 221-226.

［3］ 劉寶琴. 數(shù)字電路與系統(tǒng)［M］. 第2版， 北京: 清華大學(xué)出版社，2007: 39-56. Liu Bao-qin. D igital Circu its and System s［M］. 2nd Ed ition，Beijing: Tsinghua University Press， 2007: 39-56.

［4］ Cepek O， Kucera P， and Kurik S. Boolean functions w ith long prime im plicants［J］. Information Processing Letters， 2013，113（19-21）: 698-703.

［5］ Dusa A. A m athem atical app roach to the boolean m in im ization p rob lem［OL］. http://www.com passs.org/ wpseries/Dusa2007a.pdf， 2010.

［6］ Altun M and Marc D. Riedel: lattice-based computation of Boolean functions［OL］. http://www.m riedel.ece.umn.edu/ w iki/images/7/7b/A ltun_Riedel_Lattice-Based_Com putat ion_of_Boolean_Functions.pd f， 2010.

［7］ Hemaspaandra E and Schnoor H. M inimization for generalized Boolean formulas［OL］. http://arxiv.org/pdf/ 1104.2312.pd f， 2011.

［8］ Zadeh L A. Some reflections on soft com puting， granular com puting and their roles in the conception， design and utilization of information/intelligent system s［J］. Soft Com puting， 1998（2）: 23-25.

［9］ 苗奪謙， 徐菲菲， 姚一豫. 粒計算的集合論描述［J］. 計算機(jī)學(xué)報， 2012， 35（2）: 351-363. M iao Duo-qian， Xu Fei-fei， and Yao Yi-yu. Set-theoretic formulation of granular com puting［J］. Chinese Journal of Computers， 2012， 35（2）: 351-363.

［10］ 張清華， 幸禹可， 周玉華. 基于粒計算的增量式知識獲取方法［J］. 電子與信息學(xué)報， 2011， 33（2）: 435-441. Zhang Qing-hua， Xing Yu-ke， and Zhou Yu-hua. The incremental know ledge acquisition algorithm based on granular com puting［J］. Journal of Electronics & Information Technology， 2011， 33（2）: 435-441.

［11］ Qian Yu-hua， Hu Zhang， Sang Yan-li， et al.. M ultigranulation decision-theoretic rough sets［J］. In ternational Journal of Approximate Reasoning， 2014， 55（1）: 225-237.

［12］ Yang Xi-bei， Qian Yu-hua， and Yang Jing-yu. On characterizing hierarchies of granulation structures via distances［J］. Fundamenta Informaticae， 2013， 123（3）: 365-380.

［13］ M in Fan， Hu Qing-hua， and Zhu W. Feature selection w ith test cost constraint［J］. International Journal of Approximate Reasoning， 2014， 55（1）: 167-179.

［14］ Qian Jin， M iao Duo-qian， Zhang Ze-hua， et al.. Parallel attribute reduction algorithm s using M apReduce［J］. Inform ation Science， 2014， 279（20）: 671-690.

［15］ 陳澤華， 張裕， 謝剛. 基于粒計算的最簡決策規(guī)則挖掘算法［J］.控制與決策， 2015， 30（1）: 143-148. Chen Ze-hua， Zhang Yu， and Xie Gang. A m ining algorithm for concise decision rules based on granular com puting［J］. Contro l and Decision， 2015， 30（1）: 143-148.

［16］ 陳澤華， 曹長青， 謝剛. 基于粒矩陣的多變量真值表快速約簡算法［J］. 模式識別與人工智能， 2013， 26（8）: 745-750. Chen Ze-hua， Cao Chang-qing， and Xie Gang. G ranular matrix based rapid reduction algorithm for multivariab le truth table［J］. Pattern Recognition and Artificial Intelligence，2013， 26（8）: 745-750.

［17］ Chen Ze-hua， Lin T Y， and Xie Gang. Know ledge approximations in binary relation: granular com puting approach［J］. International Journal of Intelligent System， 2013，28（9）: 843-864.

陳澤華： 女，1974年生，副教授，主要研究方向為粒計算、智能信息處理與智能控制.

馬 賀： 女，1989年生，碩士生，研究方向為粒計算、組合邏輯優(yōu)化.

Granu lar M atrix Based Rapid Parallel Reduction A lgorithm for M IMO Truth Table

Chen Ze-hua Ma He
（College of Information Engineering， Taiyuan University of Technology， Taiyuan 030024， China）

Truth table is an im portant tool to represent the logic causal relationships between inputs and outputs. The reduction of the truth tab le is of great significance in analysis and design of digital logic circuit. In this paper，the M IMO tru th tab le is considered as a Logical In form ation System （LIS）， and the traditional tru th table reduction issue is converted into the m inimal ru le discovery of LIS. Granular Com puting （GrC） method is then introduced. Firstly， the logical in formation system is hierarchically granu lated. Secondly， the Granu lar Matrix（GrM） is defined and operated to represent the know ledge in different granularity， together with heuristic in formation hidden in the matrix， the rapid parallel reduction algorithm for the M IMO truth tab le is proposed. Light-Em itting Diode （LED） digital disp lay is app lied to illustrate the com puting process. The mathematical proof and the com p lexity analysis proves the efficiency and valid ity of the p roposed algorithm.

Digital logic circuit； Truth tab le； Granularity； Granu lar M atrix （GrM）； Parallel reduction； Granu lar Com puting （GrC）

TN79； TP181

： A

：1009-5896（2015）05-1260-06

10.11999/JEIT141129

2014-09-01收到，2015-01-16改回

國家自然科學(xué)基金（61402319）和山西省回國留學(xué)人員科研資助項目（2013-031）資助課題

*通信作者：陳澤華 zehuachen@163.com