李金燦

（華南農(nóng)業(yè)大學(xué)珠江學(xué)院，廣東 廣州 510900）

卡諾圖在數(shù)字電子技術(shù)課程中的應(yīng)用

李金燦

（華南農(nóng)業(yè)大學(xué)珠江學(xué)院，廣東 廣州 510900）

卡諾圖是數(shù)字電子技術(shù)課程一項(xiàng)重要的圖形工具，它在邏輯函數(shù)化簡(jiǎn)方面要優(yōu)于公式法.它能快速驗(yàn)證實(shí)驗(yàn)數(shù)據(jù)的準(zhǔn)確性，為數(shù)據(jù)選擇器實(shí)現(xiàn)邏輯函數(shù)提供直觀的降維卡諾圖，其次態(tài)卡諾圖在時(shí)序邏輯電路設(shè)計(jì)中可以起到重要的橋梁作用.

卡諾圖化簡(jiǎn)；降維卡諾圖；次態(tài)卡諾圖

1 引言

數(shù)字電子技術(shù)課程作為電氣電子類專業(yè)一門重要的專業(yè)基礎(chǔ)課，其教學(xué)目標(biāo)是讓學(xué)生通過(guò)系統(tǒng)的學(xué)習(xí)，能掌握基本原理，認(rèn)識(shí)常用的邏輯芯片，并能設(shè)計(jì)出滿足要求的邏輯電路.而卡諾圖在整門課程中的地位是非常重要的，它典型用于邏輯函數(shù)的化簡(jiǎn)，亦可用于快速驗(yàn)證實(shí)驗(yàn)結(jié)果，還可用于組合邏輯電路如數(shù)據(jù)選擇器的設(shè)計(jì)，及時(shí)序邏輯電路的設(shè)計(jì)[1].本文將通過(guò)實(shí)際的例子來(lái)敘述卡諾圖在這幾方面的應(yīng)用.

2 卡諾圖的應(yīng)用

卡諾圖（Karnaugh map）是由美國(guó)貝爾實(shí)驗(yàn)室電信工程師莫里斯·卡諾（Maurice Karnaugh）在1953年根據(jù)維奇圖（Veitch diagram）改進(jìn)而得到，在數(shù)字邏輯、故障診斷等許多領(lǐng)域廣泛應(yīng)用[2].卡諾圖是邏輯函數(shù)一種用圖形表示的描述方法，它可以與真值表、邏輯代數(shù)式、邏輯圖、波形圖等其它描述方法相互轉(zhuǎn)換.

2.1 卡諾圖在邏輯函數(shù)化簡(jiǎn)的應(yīng)用

為減少邏輯電路使用的門電路數(shù)量或門輸入端，需對(duì)邏輯函數(shù)進(jìn)行化簡(jiǎn)，化簡(jiǎn)方法有公式法和圖形法即卡諾圖法.公式法化簡(jiǎn)比較快速，但需對(duì)常用公式非常熟悉.且某些邏輯函數(shù)在化簡(jiǎn)過(guò)程中，不能直觀的判斷結(jié)果是否為最簡(jiǎn).而使用卡諾圖化簡(jiǎn)[3]，則可以直接得到最簡(jiǎn)結(jié)果.其缺點(diǎn)是對(duì)于變量個(gè)數(shù)超過(guò)4個(gè)的函數(shù)，卡諾圖方格數(shù)將急劇增多，難以繪制.

要使用卡諾圖快速化簡(jiǎn)邏輯函數(shù)，必須掌握邏輯函數(shù)的卡諾圖填入、畫“卡諾圈”和與項(xiàng)求解.邏輯函數(shù)可分為標(biāo)準(zhǔn)和非標(biāo)準(zhǔn)與或式，對(duì)于標(biāo)準(zhǔn)式，可直接在卡諾圖中相應(yīng)的最小項(xiàng)方格填“1”即可.但對(duì)于非標(biāo)準(zhǔn)式，則需通過(guò)找出“交集方格”填“1”.如化簡(jiǎn)函數(shù)，該函數(shù)屬于非標(biāo)準(zhǔn)式，要找出函數(shù)中每個(gè)“與項(xiàng)”的公共部分.因變量A、B負(fù)責(zé)卡諾圖的行，變量C、D負(fù)責(zé)卡諾圖的列，以為例，只需令“A=0，C=0”，“A=0”可找出第1、2行，“C=0”可找出第1、2列，它們交集為m0、m1、m4、m5，在相應(yīng)的最小項(xiàng)方格填“1”即可.其它“與項(xiàng)”按相應(yīng)的方法填入，如圖1所示.

圖1 卡諾圖填入

接下來(lái)需畫“卡諾圈”，即將卡諾圖中所有為“1”的小方格用最少的圈數(shù)圈完.其合并規(guī)律有3個(gè)，（1）2個(gè)相鄰的小方格可以合并，消去1個(gè)變量；（2）4個(gè)相鄰的小方格可以合并，消去2個(gè)變量；（3）8個(gè)相鄰的小方格可以合并，消去3個(gè)變量.這里涉及“相鄰”的概念，是指“幾何相鄰”，包括相接、相對(duì)、相重合.在畫圈時(shí)一般按“8個(gè)1→4個(gè)1→2個(gè)1→1個(gè)1”的順序，畫完后需對(duì)“卡諾圈”進(jìn)行檢驗(yàn)是否成立，其方法是檢查圈內(nèi)是否至少有一個(gè)從未被其它圈圈過(guò)的“1”.畫完“卡諾圈”的卡諾圖如圖2所示：

圖2 卡諾圈

最后將每個(gè)“卡諾圈”對(duì)應(yīng)的“與項(xiàng)”寫出再進(jìn)行“相或”即可得到函數(shù)的最簡(jiǎn)與或式.大部分圖書資料并沒(méi)有將“與項(xiàng)”的獲得方法寫出，只是列舉一些常見(jiàn)的“卡諾圈”及結(jié)果.作者根據(jù)多年的教學(xué)經(jīng)驗(yàn)，歸納出方便快捷的方法：行看左邊AB，列看上方CD；卡諾圖內(nèi)所有的“1”對(duì)應(yīng)的變量取值不同，則將該變量去掉；對(duì)應(yīng)的變量取值相同則保留該變量，變量取值為“1”時(shí)保留為原變量，為“0”時(shí)保留為反變量.

以卡諾圖中“8個(gè)1”的卡諾圈為例，先看左邊，上面“4個(gè)1”對(duì)應(yīng)變量A取值為0，而下面“4個(gè)1”對(duì)應(yīng)變量A取值為1，取值不同，去掉變量A；上下“4個(gè)1”對(duì)應(yīng)變量B均取值為0，保留為反變量B.再看上方，4列“2個(gè)1”對(duì)應(yīng)的變量C、D的取值均不相同，所以去掉變量C、D.該卡諾圈對(duì)應(yīng)的與項(xiàng)是，與“8個(gè)相鄰小方格合并消去3個(gè)變量”的化簡(jiǎn)規(guī)律是一致的.按同樣的方法可以寫出其它2個(gè)卡諾圈對(duì)應(yīng)的與項(xiàng)是和，函數(shù)的化簡(jiǎn)結(jié)果為

2.2 卡諾圖在實(shí)驗(yàn)過(guò)程中的應(yīng)用

數(shù)字電子技術(shù)是一門對(duì)動(dòng)手能力要求很高的課程，在理論課堂教學(xué)外，還需配套進(jìn)行驗(yàn)證性和綜合性實(shí)驗(yàn).學(xué)生在實(shí)驗(yàn)過(guò)程中，往往只會(huì)按實(shí)驗(yàn)指導(dǎo)書給出的步驟搭建邏輯電路，并根據(jù)實(shí)驗(yàn)箱的顯示狀態(tài)記錄實(shí)驗(yàn)數(shù)據(jù)，但對(duì)數(shù)據(jù)的正確性不能快速判斷.

現(xiàn)以邏輯函數(shù)F（A，B，C，D）=ABC+ACD+BCD為例，要求用合適的邏輯芯片實(shí)現(xiàn)，并根據(jù)實(shí)驗(yàn)結(jié)果列出真值表進(jìn)行驗(yàn)證.若直接對(duì)該函數(shù)式進(jìn)行實(shí)現(xiàn)，需要2片三輸入端或四輸入端的與門和1片三輸入端的或門.但若將函數(shù)式轉(zhuǎn)換成與非-與非形式，即則只需使用2片三輸入端或四輸入端的與非門.搭建好電路便能很快得到該函數(shù)的真值表，學(xué)生一般會(huì)將16種的取值可能一一代入原函數(shù)進(jìn)行驗(yàn)證，驗(yàn)證時(shí)間過(guò)長(zhǎng).若能巧妙使用卡諾圖，便可快速驗(yàn)證.先將函數(shù)填入到卡諾圖中，如圖3所示：

圖3 驗(yàn)證函數(shù)卡諾圖

從卡諾圖中立刻可以看出，當(dāng)變量ABCD的取值組合為0111、1011、1110和1111這4種組合時(shí)，函數(shù)輸出值為1，其余取值組合輸出均為0.

2.3 卡諾圖的降維應(yīng)用

一般將卡諾圖的變量數(shù)稱為維數(shù)，如果把某些變量也作為卡諾圖小方格的值，則會(huì)減少卡諾圖的維數(shù)，這種卡諾圖稱為降維卡諾圖[4].在使用數(shù)據(jù)選擇器（MUX）實(shí)現(xiàn)組合邏輯函數(shù)時(shí)，教材一般只會(huì)介紹公式法，亦即拼湊法.拼湊法的關(guān)鍵是要分別列出數(shù)據(jù)選擇器的輸出端表達(dá)式和待求函數(shù)的標(biāo)準(zhǔn)與或式，然后將待求函數(shù)拼成與數(shù)據(jù)選擇器輸出表達(dá)的樣式，通過(guò)對(duì)比，得出數(shù)據(jù)選擇器地址輸入端和數(shù)據(jù)輸入端的值.當(dāng)待求函數(shù)變量數(shù)是2-3個(gè)時(shí)，拼湊的過(guò)程不會(huì)很復(fù)雜，但若變量是4個(gè)時(shí)，則會(huì)變得很繁瑣，對(duì)比過(guò)程容易出錯(cuò).此時(shí)若引入圖形法即降維卡諾圖將會(huì)大大減少工作量.降維卡諾圖一般適用于數(shù)據(jù)選擇器地址端數(shù)少于待求函數(shù)變量數(shù)的情況.下面舉例說(shuō)明卡諾圖如何降維，以及如何應(yīng)用于函數(shù)實(shí)現(xiàn)過(guò)程.

現(xiàn)使用八選一數(shù)據(jù)選擇器74LS151來(lái)實(shí)現(xiàn)函數(shù)F（A，B，C，D）=∑m（0，1，5，6，7，9，12，13，14），因74LS151的地址端只有3個(gè)，而函數(shù)變量數(shù)有4個(gè)，所以需對(duì)函數(shù)降維.首先畫出函數(shù)的卡諾圖，如圖4所示：

一般默認(rèn)降變量“D”，可以先畫出三變量“A,B,C”的空白卡諾圖，根據(jù)原卡諾圖的小方格取值即函數(shù)值來(lái)確定其值.降維可分成四種情況：

（1）當(dāng)ABC取值為000時(shí)，當(dāng)D=0，F(xiàn)=1；當(dāng)D=1，F(xiàn)=1，不論D取值為0還是1，F(xiàn)都為1，所以在三變量卡諾圖m0對(duì)應(yīng)小方格填“1”.

（2）當(dāng)ABC取值為001時(shí)，當(dāng)D=0，F(xiàn)=0；當(dāng)D=1，F(xiàn)=0，不論D取值為0還是1，F(xiàn)都為0，所以在三變量卡諾圖m1對(duì)應(yīng)小方格填“0”.

（3）當(dāng)ABC取值為010時(shí)，當(dāng)D=0，F(xiàn)=0；當(dāng)D=1，F(xiàn)=1，F(xiàn)的取值與D的取值相同，所以在三變量卡諾圖m2對(duì)應(yīng)小方格填“D”.

（4）當(dāng)ABC取值為111時(shí)，當(dāng)D=0，F(xiàn)=1；當(dāng)D=1，F(xiàn)=0，F(xiàn)的取值與D的取值相反，所以在三變量卡諾圖m7對(duì)應(yīng)小方格填“”.

圖4 函數(shù)卡諾圖

最后得函數(shù)的降維卡諾圖，如圖5所示.再將74LS151輸出信號(hào)的卡諾圖畫出，如圖6所示，通過(guò)兩卡諾圖對(duì)比，可以快速得出74LS151地址輸入端A2A1A0和數(shù)據(jù)輸入端D7-D0的值，之后便可畫出74LS151的連線圖，實(shí)現(xiàn)待求函數(shù).

圖5 降維卡諾圖

圖6 數(shù)據(jù)選擇器卡諾圖

2.4 次態(tài)卡諾圖的應(yīng)用

次態(tài)卡諾圖是指卡諾圖小方格填入的數(shù)據(jù)不是一個(gè)函數(shù)值，而是當(dāng)前狀態(tài)的下一個(gè)狀態(tài)，一般是一組二進(jìn)制數(shù).在進(jìn)行時(shí)序邏輯電路設(shè)計(jì)，需根據(jù)給定的條件，如狀態(tài)轉(zhuǎn)移圖求解狀態(tài)方程，此時(shí)需引入次態(tài)卡諾圖，之后再將其拆分成各觸發(fā)次態(tài)卡諾圖來(lái)求解[5].現(xiàn)以設(shè)計(jì)一個(gè)同步六進(jìn)制加法計(jì)數(shù)器為例，首先根據(jù)其計(jì)數(shù)規(guī)則，采用3個(gè)觸發(fā)器實(shí)現(xiàn)，畫出相應(yīng)的狀態(tài)轉(zhuǎn)移圖，如圖7所示：

圖7 狀態(tài)轉(zhuǎn)移圖

設(shè)圖中狀態(tài)圈內(nèi)二進(jìn)制數(shù)組合對(duì)應(yīng)Q2Q1Q0狀態(tài)，按箭頭指向可以清晰的看出某一狀態(tài)在輸入信號(hào)作用下的下一個(gè)狀態(tài)，即次態(tài)，可用次態(tài)卡諾圖表示，如圖8所示：

圖8 次態(tài)卡諾圖

將次態(tài)卡諾圖中8個(gè)小方格中的二進(jìn)制數(shù)組合分別取左、中、右各1個(gè)數(shù)字構(gòu)成三個(gè)新的卡諾圖，化簡(jiǎn)可得次態(tài)的表達(dá)式.再根據(jù)所選用觸發(fā)器的類型，變換狀態(tài)方程的形式，通過(guò)對(duì)比法可以求出觸發(fā)器的驅(qū)動(dòng)方程.

3 結(jié)語(yǔ)

上面敘述的4種情況基本是卡諾圖在數(shù)字電子技術(shù)課程的全部應(yīng)用，通過(guò)實(shí)例分析，可以快速掌握各種卡諾圖應(yīng)用的使用場(chǎng)合及方法.熟練使用卡諾圖可加深對(duì)課程的理解，亦可加快邏輯電路的設(shè)計(jì)進(jìn)度.

〔1〕余孟嘗.數(shù)字電子技術(shù)基礎(chǔ)簡(jiǎn)明教程[M].北京:高等教育出版社,2006.

〔2〕王芳.基于數(shù)字電路中卡諾圖的應(yīng)用研究[J].山西電子技術(shù),2008(06):22-24.

〔3〕葉騰,朱桂英.卡諾圖化簡(jiǎn)數(shù)學(xué)新方法[J].河北科技大學(xué)學(xué)報(bào),2012,33(03):202-206.

〔4〕郝卜,張陽(yáng),柴毅哲，等.降維卡諾圖在邏輯函數(shù)設(shè)計(jì)中的應(yīng)用[J].降維卡諾圖在邏輯函數(shù)設(shè)計(jì)中的應(yīng)用,2012,25(04):33-36.

〔5〕任駿原.基于次態(tài)卡諾圖的J、K激勵(lì)函數(shù)最小化方法及時(shí)序邏輯電路自啟動(dòng)設(shè)計(jì)[J].浙江大學(xué)學(xué)報(bào)(理學(xué)版),2010,37(4):425-427.

G642

A

1673-260X（2017）08-0212-03

2017-05-06

2014年廣東省質(zhì)量工程項(xiàng)目《從化供電局校外實(shí)踐教學(xué)基地建設(shè)》（4720）；北方國(guó)際大學(xué)聯(lián)盟第四期教育教學(xué)研究項(xiàng)目《EDA仿真軟件在數(shù)字電子技術(shù)課程教學(xué)中的應(yīng)用研究》（20140408002）