列表化簡(jiǎn)邏輯函數(shù)技術(shù)
加入技術(shù)交流群
1、概述
本文引用地址：http://www.ex-cimer.com/article/149507.htm在設(shè)計(jì)邏輯電路圖時(shí)，由真值表直接得到的函數(shù)往往比較復(fù)雜。代數(shù)法和卡諾圖法等方法對(duì)于變量數(shù)目較多的邏輯函數(shù)則效果不佳，本文介紹一種可以化簡(jiǎn)復(fù)雜邏輯函數(shù)的方法──表格法，該方法可以對(duì)變量數(shù)目較多的邏輯函數(shù)也可以進(jìn)行化簡(jiǎn)。
2、原理
在介紹化減法之前，先說(shuō)明三個(gè)概念：
蘊(yùn)涵項(xiàng)──在函數(shù)的任何積之和式中，每個(gè)乘積項(xiàng)稱為該函數(shù)的蘊(yùn)涵項(xiàng)。對(duì)應(yīng)于卡諾圖中的任一標(biāo)1單元(最小項(xiàng))以及2m個(gè)相鄰單元所形成的圈都是函數(shù)的蘊(yùn)涵項(xiàng)。
素項(xiàng)──若函數(shù)的一個(gè)蘊(yùn)涵項(xiàng)不是該函數(shù)中其它蘊(yùn)涵項(xiàng)的一個(gè)子集，則此蘊(yùn)涵項(xiàng)稱為素蘊(yùn)涵項(xiàng)，簡(jiǎn)稱素項(xiàng)。
實(shí)質(zhì)素項(xiàng)──若函數(shù)的一個(gè)素項(xiàng)所包含的某一最小項(xiàng)，不包括在該函數(shù)的其它任何素項(xiàng)中則此素項(xiàng)稱為實(shí)質(zhì)素蘊(yùn)涵項(xiàng)，簡(jiǎn)稱實(shí)質(zhì)素項(xiàng)。
列表化簡(jiǎn)法的基本原理是利用邏輯函數(shù)的最小項(xiàng)，通過(guò)對(duì)相鄰最小項(xiàng)的合并，消去多余變量因子，獲得邏輯函數(shù)的最簡(jiǎn)式的。列表化簡(jiǎn)法的思路是先找出給定函數(shù)F的全部素項(xiàng)，然后找出其中的實(shí)質(zhì)素項(xiàng)；若實(shí)質(zhì)素項(xiàng)不能覆蓋F的所有最小項(xiàng)，則進(jìn)一步找出所需素項(xiàng)，以構(gòu)成F的最簡(jiǎn)素項(xiàng)集。
下面用列表化簡(jiǎn)法將下列函數(shù)化簡(jiǎn)為最簡(jiǎn)與或表達(dá)式。
F(A,B,C,D)＝Σ(0,3,4,5,6,7,8,10,11)
3、建立素項(xiàng)表
首先，找出給定函數(shù)的全部素項(xiàng)。
(1)先將每個(gè)最小項(xiàng)所對(duì)應(yīng)的二進(jìn)制數(shù)按其“1”的個(gè)數(shù)分組得表1；
表1 最小項(xiàng)
組號(hào) | 項(xiàng)號(hào) | 二進(jìn)制數(shù) |
0 | 0 | 0000 |
1 | 4 8 | 0100 1000 |
2 | 3 5 6 10 | 0011 0101 0110 1010 |
3 | 7 11 | 0111 1011 |
(2)將表1中的相鄰兩個(gè)組之間二進(jìn)制數(shù)進(jìn)行比較、合并得到一次化簡(jiǎn)結(jié)果，稱為一次乘積項(xiàng)，其項(xiàng)號(hào)記為i(j－i)，其中i為最小項(xiàng)中的小項(xiàng)號(hào)，j為最小項(xiàng)中的大項(xiàng)號(hào)，得表2；
表2 一次乘積項(xiàng)
組號(hào) | 項(xiàng)號(hào) | 二進(jìn)制數(shù) |
0 | a0(4) b0(8) | 0-00 -000 |
1 | 4(1) 4(2) c8(2) | 010- 01-0 10-0 |
2 | d3(4) e3(8) 5(2) 6(1) f10(1) | 0-11 -011 01-1 011- 101- |
(3)再將表2中的相鄰兩組內(nèi)的二進(jìn)制數(shù)進(jìn)行比較、合并、便得到第二次化簡(jiǎn)結(jié)果，稱為二次乘積項(xiàng)，其項(xiàng)號(hào)記為i(n,m)，其中i為兩個(gè)一次乘積項(xiàng)中的小項(xiàng)號(hào)，n為原最小項(xiàng)的項(xiàng)號(hào)差，m為一次乘積項(xiàng)的項(xiàng)號(hào)差，得表3；
表3 二次乘積項(xiàng)
組號(hào) | 項(xiàng)號(hào) | 二進(jìn)制數(shù) |
1 | g4(1,2) 4(2,1) | 01-- 01-- |
不能與其它一次乘積項(xiàng)合并的一次乘積項(xiàng)是素項(xiàng)，分別以a,b,c,d,e,f記之，不能合并的二次乘積項(xiàng)也是素項(xiàng)，以g記之。
4、實(shí)質(zhì)素項(xiàng)
建立實(shí)質(zhì)素項(xiàng)產(chǎn)生表，找出實(shí)質(zhì)素項(xiàng)。
先用×標(biāo)出每個(gè)素項(xiàng)覆蓋最小項(xiàng)的情況，再找出實(shí)質(zhì)最小項(xiàng)5、6，在×上標(biāo)括號(hào)以示區(qū)別，可找出對(duì)應(yīng)實(shí)質(zhì)素項(xiàng)g，在其前標(biāo)*，最后一行用“V”標(biāo)出實(shí)質(zhì)素項(xiàng)覆蓋最小項(xiàng)的情況，可看出還有最小項(xiàng)0、3、8、10、11未被覆蓋。如表4所示。
表4實(shí)質(zhì)素項(xiàng)產(chǎn)生式
最小項(xiàng) 素項(xiàng) | 0 | 3 | 4 | 5 | 6 | 7 | 8 | 10 | 11 |
a0(4) | X | X | |||||||
b0(8) | X | X | |||||||
c8(2) | X | X | |||||||
d3(4) | X | X | |||||||
e3(8) | X | X | |||||||
f10(1) | X | X | |||||||
*g4(1,2) | X | X | X | X | |||||
覆蓋情況 | V | V | V | V |
5、素項(xiàng)產(chǎn)生式
第三步：建立所需素項(xiàng)產(chǎn)生表，找出所需素項(xiàng)，所需素項(xiàng)集應(yīng)覆蓋所有未被實(shí)質(zhì)素項(xiàng)覆蓋的最小項(xiàng)，得表5。再用行列消去法來(lái)找，選優(yōu)勢(shì)行b0(8)，e3(8)，劃去劣勢(shì)行a0(4)及d3(4)得表6，再選最小項(xiàng)為0、3的劣勢(shì)列，劃去最小項(xiàng)為8，11的優(yōu)勢(shì)列，得表7。找出新的實(shí)質(zhì)素項(xiàng)b，e，取該兩項(xiàng)作為所需素項(xiàng)后，尚有最小項(xiàng)10未被覆蓋，可選取c或f求得所需素項(xiàng)集為(b,e,c)或(b,e,f)，
表5
最小項(xiàng) 素項(xiàng) | 0 | 3 | 8 | 10 | 11 |
a0(4) | Ｘ | ||||
b0(8) | Ｘ | Ｘ | |||
c8(2) | Ｘ | Ｘ | |||
d3(4) | Ｘ | ||||
e3(8) | Ｘ | Ｘ | |||
f10(1) | Ｘ | Ｘ |
評(píng)論