基于蘊(yùn)涵法的求解多變量邏輯函數(shù)本原蘊(yùn)涵項(xiàng)的程序流程

王波 徐州師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 221116

基于蘊(yùn)涵法的求解多變量邏輯函數(shù)本原蘊(yùn)涵項(xiàng)的程序流程

王波 徐州師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 221116

基于邏輯函數(shù)蘊(yùn)涵化簡(jiǎn)法的基本理論，構(gòu)造比較合并數(shù)組，設(shè)計(jì)求解多變量邏輯函數(shù)本原蘊(yùn)涵項(xiàng)的結(jié)構(gòu)化程序流程，使邏輯函數(shù)的化簡(jiǎn)工作在降低了復(fù)雜度的同時(shí)提高了可靠性。

蘊(yùn)涵化簡(jiǎn)法；本原蘊(yùn)涵項(xiàng)；邏輯相鄰項(xiàng)；結(jié)構(gòu)化流程

引言

通過(guò)化簡(jiǎn)實(shí)現(xiàn)邏輯函數(shù)的最小化是數(shù)字邏輯系統(tǒng)設(shè)計(jì)過(guò)程中非常重要的一個(gè)步驟，但諸如公式法、卡諾圖法等常用的化簡(jiǎn)方法僅適用于簡(jiǎn)單的邏輯函數(shù)，對(duì)于復(fù)雜的多變量（5變量以上）邏輯函數(shù)的化簡(jiǎn)則可使用蘊(yùn)涵化簡(jiǎn)法。

蘊(yùn)涵法又叫制表法，是由奎恩（Quine）提出，并經(jīng)由麥克拉斯基（McCluskey）改進(jìn)和完善的一種邏輯函數(shù)系統(tǒng)化簡(jiǎn)法，故又稱為Q－M化簡(jiǎn)法。雖然與卡諾圖法一樣也是以公式為基本理論依據(jù)，但蘊(yùn)涵法又有著化簡(jiǎn)步驟規(guī)律性強(qiáng)的優(yōu)點(diǎn)，應(yīng)用于多變量邏輯函數(shù)的化簡(jiǎn)，雖然工作量大，但操作可以按部就班地進(jìn)行，適合于計(jì)算機(jī)處理[1]。

上述特點(diǎn)，在蘊(yùn)涵法化簡(jiǎn)邏輯函數(shù)的第一個(gè)步驟即求本原蘊(yùn)涵項(xiàng)的過(guò)程中表現(xiàn)得尤為突出。所謂本原蘊(yùn)涵項(xiàng)就是不含多余變量的乘積項(xiàng)，即其已不能再通過(guò)同其它乘積項(xiàng)合并而減少變量了[2]。本文以5變量邏輯函數(shù)為例，應(yīng)用蘊(yùn)涵法進(jìn)行計(jì)算機(jī)輔助設(shè)計(jì)，給出求解多變量邏輯函數(shù)本原蘊(yùn)涵項(xiàng)的結(jié)構(gòu)化程序流程。

1.程序流程

1.1 初始化

初始化操作除了定義程序運(yùn)行所需的多個(gè)相關(guān)變量外，最主要的工作就是定義如下兩個(gè)數(shù)組。

1.1.1 二維數(shù)組m[3][212]

m數(shù)組的每個(gè)數(shù)組元素為一個(gè)字節(jié)，同一列的三個(gè)數(shù)組元素構(gòu)成一個(gè)數(shù)據(jù)單元，數(shù)組元素的列號(hào)即為數(shù)據(jù)單元的序號(hào)，如圖1所示，數(shù)據(jù)單元是存儲(chǔ)邏輯函數(shù)標(biāo)準(zhǔn)與或式中包含的最小項(xiàng)或操作過(guò)程中產(chǎn)生的一般乘積項(xiàng)的基本單位。

數(shù)據(jù)單元中標(biāo)記“×”的位沒(méi)有定義（用“0”填充），其余位根據(jù)不同的存儲(chǔ)對(duì)象有著不同的定義和使用方法。

（1）存儲(chǔ)最小項(xiàng)

按照使最小項(xiàng)、數(shù)據(jù)單元的序號(hào)對(duì)應(yīng)相等的方法，將邏輯函數(shù)包含的最小項(xiàng)mi存儲(chǔ)于m數(shù)組的第i（=0～31）個(gè)數(shù)據(jù)單元并由輸入程序作相應(yīng)設(shè)置。

1）m[2][i].7位為“1”，表示邏輯函數(shù)包含最小項(xiàng)mi，此時(shí)，數(shù)據(jù)單元的其它各位定義如下。

①m[2][i].6位為“0”，表示mi尚未被消去任何變量，一旦mi參與化簡(jiǎn)，此位將被置“1”；

②m[0][i].4～m[0][i].0位組存儲(chǔ)mi的序號(hào)i對(duì)應(yīng)的5位二進(jìn)制數(shù)，其中“1”對(duì)應(yīng)mi中的原變量，而“0”對(duì)應(yīng)反變量；

③m[1][i].4～m[1][i].0位組存儲(chǔ)5個(gè)連續(xù)的二進(jìn)制“1”表示mi包含所有邏輯變量；

④m[2][i].2～m[2][i].0位組用于存儲(chǔ)3位二進(jìn)制值，表示位組m[0][i].4～m[0][i]. 0中“1”的個(gè)數(shù)，即mi中原變量的個(gè)數(shù)。

圖1（a）為一個(gè)特例，描述最小項(xiàng)m2尚未參與化簡(jiǎn)合并時(shí)的存儲(chǔ)狀態(tài)。

2）m[2][i].7位為“0”表示邏輯函數(shù)不包含最小項(xiàng)mi，此數(shù)據(jù)單元的其它位皆不被定義使用。

（2）存儲(chǔ)一般乘積項(xiàng)

在求解本原蘊(yùn)涵項(xiàng)過(guò)程中，一般會(huì)產(chǎn)生被消去若干個(gè)變量的一般乘積項(xiàng)，它們將被依次存儲(chǔ)于m數(shù)組中序號(hào)大于或等于32的數(shù)據(jù)單元中,除以下兩點(diǎn)外，各數(shù)據(jù)位取“0”、“1”狀態(tài)的含義與存儲(chǔ)最小項(xiàng)時(shí)基本相同。

1）一個(gè)一般乘積項(xiàng)在m數(shù)組中的具體存儲(chǔ)位置由被處理的邏輯函數(shù)的結(jié)構(gòu)決定；

2）m[1][i].4～m[1][i].0位組中的某位為“0”，表明其對(duì)應(yīng)的變量已被從乘積項(xiàng)中消去，其在m[0][i].4～m[0][i].0位組中對(duì)應(yīng)位的狀態(tài)也失去意義。

圖1（b）為另一個(gè)特例，描述了一個(gè)一般乘積項(xiàng)的存儲(chǔ)狀態(tài)，此一般乘積項(xiàng)由邏輯函數(shù)F（在后文的實(shí)現(xiàn)實(shí)例部分中詳細(xì)說(shuō)明）包含的兩個(gè)最小項(xiàng)m9、m11合并得到，其所在數(shù)據(jù)單元的序號(hào)為36，尚需進(jìn)一步化簡(jiǎn)。

（3）m數(shù)組中數(shù)據(jù)單元數(shù)目的定義問(wèn)題

對(duì)于m數(shù)組，實(shí)際所需的數(shù)據(jù)單元的數(shù)目由被處理的邏輯函數(shù)決定，隨邏輯函數(shù)包含的最小項(xiàng)數(shù)目及最小項(xiàng)分布情況不同而變化。在此，對(duì)5變量邏輯函數(shù)，設(shè)定數(shù)據(jù)單元的個(gè)數(shù)為212，即m數(shù)組的列號(hào)范圍為0～211,這是一個(gè)存儲(chǔ)單元數(shù)目極端大的選擇，對(duì)應(yīng)邏輯函數(shù)的標(biāo)準(zhǔn)與或式中共包含31個(gè)最小項(xiàng)的情況。

1.1.2 二維比較合并數(shù)組comp[6][10]

為了比較、合并邏輯相鄰的最小項(xiàng)，根據(jù)蘊(yùn)涵法理論定義6行10列的二維字節(jié)數(shù)組comp，并依據(jù)表1（最小項(xiàng)比較合并表）的結(jié)構(gòu)和內(nèi)容將comp數(shù)組初始化，comp數(shù)組具有如下特征。

（1）內(nèi)容非“-1”的數(shù)組元素共32個(gè)，分別對(duì)應(yīng)被處理邏輯函數(shù)可能包含的序號(hào)為0～31的32個(gè)最小項(xiàng)，而內(nèi)容為“-1”的數(shù)組元素不對(duì)應(yīng)最小項(xiàng)。每行的第一個(gè)內(nèi)容為“-1”的數(shù)組元素用于控制某一輪尋找、比較與合并最小項(xiàng)的循環(huán)過(guò)程的結(jié)束。

（2）同一行數(shù)組元素對(duì)應(yīng)的最小項(xiàng)擁有相同個(gè)數(shù)的原變量，并且原變量的個(gè)數(shù)等于行號(hào)。

（3）某行一個(gè)數(shù)組元素對(duì)應(yīng)的最小項(xiàng)與相鄰上一行另一個(gè)數(shù)組元素對(duì)應(yīng)的最小項(xiàng)相比較，原變量個(gè)數(shù)多1，如果這種關(guān)系是由于邏輯函數(shù)的同一個(gè)變量在兩個(gè)最小項(xiàng)中分別取原、反變量狀態(tài)引起的，則相應(yīng)的兩個(gè)最小項(xiàng)即為一對(duì)邏輯相鄰項(xiàng)。

1.2 邏輯函數(shù)輸入

輸入程序依據(jù)前述要求設(shè)置m數(shù)組的相關(guān)數(shù)組元素。特別地，對(duì)于邏輯函數(shù)包含所有最小項(xiàng)（邏輯函數(shù)值恒為1）和邏輯函數(shù)不包含任何最小項(xiàng)（邏輯函數(shù)值恒為0）兩種情況要在輸入流程中直接進(jìn)行處理說(shuō)明，而不必進(jìn)入后續(xù)的求解本原蘊(yùn)涵項(xiàng)流程。

1.3 求解本原蘊(yùn)涵項(xiàng)流程

求解本原蘊(yùn)涵項(xiàng)操作的程序流程結(jié)構(gòu)為一個(gè)整體，為描述方便，將其分為主體和子模塊兩個(gè)部分。

1.3.1 主體部分

圖2以N-S圖的形式給出主體部分的結(jié)構(gòu)化流程。

這一部分的核心流程是一個(gè)嚴(yán)格遵循蘊(yùn)涵法基本步驟設(shè)計(jì)的，分別以i1、j1和k1為外、中和內(nèi)層循環(huán)控制變量的三重嵌套循環(huán)結(jié)構(gòu)。借助于comp數(shù)組為主要的控制依托，通過(guò)此循環(huán)結(jié)構(gòu)正常運(yùn)行，可實(shí)現(xiàn)主體部分的基本功能，即進(jìn)行邏輯相鄰最小項(xiàng)的尋找、比較與合并操作，得到因消去一個(gè)變量而擁有4個(gè)變量的所有一般乘積項(xiàng)，并依次存儲(chǔ)于m數(shù)組中相應(yīng)位置的數(shù)據(jù)單元中。

當(dāng)?shù)玫降?變量一般乘積項(xiàng)的個(gè)數(shù)大于或等于2時(shí)，求解本原蘊(yùn)涵項(xiàng)的操作過(guò)程就需要繼續(xù)進(jìn)行，流程進(jìn)而由此部分結(jié)束處的二重嵌套選擇結(jié)構(gòu)的最左端分支進(jìn)入子模塊部分，否則，本原蘊(yùn)涵項(xiàng)已經(jīng)求出，整個(gè)流程結(jié)束。

1.3.2 子模塊部分

圖3以N-S圖的形式給出子模塊部分的結(jié)構(gòu)化流程。

子模塊部分實(shí)現(xiàn)的功能是：針對(duì)主體部分求得的兩個(gè)或兩個(gè)以上的4變量一般乘積項(xiàng)，繼續(xù)進(jìn)行邏輯相鄰的一般乘積項(xiàng)的尋找、比較與合并操作。

這一部分程序流程整體上為一個(gè)四重嵌套的循環(huán)結(jié)構(gòu)。以r為循環(huán)控制變量的外層循環(huán)最多可能執(zhí)行3次，先后求得可能存在的由3、2或1個(gè)邏輯變量組成的一般乘積項(xiàng)；i2、j2控制中間兩層循環(huán)，實(shí)施求解這些一般乘積項(xiàng)的具體操作；而k2控制的最內(nèi)層循環(huán)則用于防止同一個(gè)一般乘積項(xiàng)在m數(shù)組中的重復(fù)存儲(chǔ)。

1.4 本原蘊(yùn)涵項(xiàng)的輸出

上述相關(guān)流程執(zhí)行完畢后，化簡(jiǎn)得到的所有本原蘊(yùn)涵項(xiàng)都被存儲(chǔ)在m數(shù)組中，假設(shè)某個(gè)本原蘊(yùn)涵項(xiàng)所在數(shù)據(jù)單元的序號(hào)為i，則有：

（1）i的范圍為0～PointEnd；

（2）m[2][i].7～m[2][i].6位組的內(nèi)容為“10”（此為本原蘊(yùn)涵項(xiàng)的標(biāo)志）；

（3）m[1][i].4～m[1][i].0位組中內(nèi)容為“1”的位對(duì)應(yīng)的變量被保留在本原蘊(yùn)涵項(xiàng)中；

（4）本原蘊(yùn)涵項(xiàng)中一個(gè)被保留變量的原、反狀態(tài)由m[0][i].4～m[0][i].0位組中此變量對(duì)應(yīng)位的取值確定，“1”對(duì)應(yīng)原變量，“0”對(duì)應(yīng)反變量。

根據(jù)上述特征，可設(shè)計(jì)相應(yīng)的程序流程對(duì)所有本原蘊(yùn)涵項(xiàng)進(jìn)行依次輸出。

2.實(shí)現(xiàn)實(shí)例

用蘊(yùn)涵法化簡(jiǎn)邏輯函數(shù)F（A、B、C、D、E）=∑m（0,2,4,6,9,11,13,15,17, 21,25,27,29,31），求全部本原蘊(yùn)涵項(xiàng)[3]。用C語(yǔ)言實(shí)現(xiàn)上述流程，程序運(yùn)行的結(jié)果是在m數(shù)組中得到3個(gè)存儲(chǔ)著本原蘊(yùn)涵項(xiàng)的數(shù)據(jù)單元，它們是：

①m[0][51]=00000000、m[1][51]=00011001、m[2][51]=1000000；

②m[0][55]=00010001、m[1][55]=00010011、m[2][55]=1000010；

③m[0][59]=00001001、m[1][59]=00001001、m[2][59]=1000010。

3.結(jié)束語(yǔ)

本文介紹的求解多變量邏輯函數(shù)本原蘊(yùn)涵項(xiàng)的方法嚴(yán)格遵循蘊(yùn)涵法理論，設(shè)計(jì)的程序流程清晰、準(zhǔn)確，符合結(jié)構(gòu)化標(biāo)準(zhǔn)，用C、VB等高級(jí)編程工具很容易實(shí)現(xiàn)。對(duì)于6變量以上的邏輯函數(shù)，也僅僅需要對(duì)m數(shù)組的列數(shù)、comp數(shù)組的結(jié)構(gòu)和內(nèi)容及部分循環(huán)結(jié)構(gòu)的循環(huán)次數(shù)進(jìn)行簡(jiǎn)單的修改即可。實(shí)踐表明，通過(guò)上述流程對(duì)邏輯函數(shù)進(jìn)行處理的結(jié)果，與用公式法、卡諾圖法等手工方法進(jìn)行處理的結(jié)果完全一致，但在提高可靠性、減小復(fù)雜度和降低工作成本等方面優(yōu)點(diǎn)是明顯的。

[1]朱勇，高曉清，曾西洋．?dāng)?shù)字邏輯第一版．北京：中國(guó)鐵道出版社．2007；49

[2，3]韓振振，李亞伯．?dāng)?shù)字電路邏輯設(shè)計(jì)[M]．第一版．大連：大連理工大學(xué)出版社．1987；105－116

10.3969/j.issn.1001-8972.2010.24.014

王波，男，漢族，現(xiàn)任教于徐州師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，主要研究方向：數(shù)字系統(tǒng)設(shè)計(jì)，單片機(jī)及嵌入式系統(tǒng)。