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

陳澤華馬 賀

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

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

陳澤華*馬 賀

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

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

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

1 引言

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

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

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

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

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

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

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

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

3 多輸入多輸出真值表快速并行約簡(jiǎn)算法

3.1 符號(hào)定義

3.2 算法描述

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

3.3 計(jì)算實(shí)例

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

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

表1 基于粒計(jì)算的多輸入多輸出真值表快速并行約簡(jiǎn)算法

圖1 七段字形顯示

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

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

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

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

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

可得

表3 ω1=的計(jì)算過(guò)程

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

表4 ω2=的計(jì)算過(guò)程

4 算法分析

4.1 算法正確性證明

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

等價(jià)性證明保證了本文算法的正確性。

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

4.3 無(wú)關(guān)項(xiàng)的處理

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

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

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

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

真值表化簡(jiǎn)是數(shù)字邏輯電路分析和設(shè)計(jì)中的重要問(wèn)題，本文將等價(jià)關(guān)系的粒計(jì)算模型應(yīng)用于m輸入n輸出真值表化簡(jiǎn)，一方面豐富了粒計(jì)算理論研究，另一方面為數(shù)字邏輯電路的分析與設(shè)計(jì)提供了新思路。如何將二元關(guān)系的粒計(jì)算模型［17］推廣到時(shí)序邏輯電路中的狀態(tài)轉(zhuǎn)移表（圖）的化簡(jiǎ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］ 邊計(jì)年， 薛宏熙， 蘇明， 等. 數(shù)字系統(tǒng)設(shè)計(jì)自動(dòng)化［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］. 計(jì)算機(jī)學(xué)報(bào)， 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ì)算的增量式知識(shí)獲取方法［J］. 電子與信息學(xué)報(bào)， 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］ 陳澤華， 張?jiān)＃?謝剛. 基于粒計(jì)算的最簡(jiǎn)決策規(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］ 陳澤華， 曹長(zhǎng)青， 謝剛. 基于粒矩陣的多變量真值表快速約簡(jiǎn)算法［J］. 模式識(shí)別與人工智能， 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年生，副教授，主要研究方向?yàn)榱Ｓ?jì)算、智能信息處理與智能控制.

馬 賀： 女，1989年生，碩士生，研究方向?yàn)榱Ｓ?jì)算、組合邏輯優(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改回

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

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