數位邏輯與實習 Week 5 邏輯閘層次的最小化 曾建勳
三變數卡諾圖 三變數卡諾圖: 三個變數共有2 =8個全及項(全或項)卡諾圖中包含8個方格 必須以葛雷碼的順序排列如下: 規則：相鄰的行只有一個位元變化 有撇號與沒有撇號的相鄰方格即可化簡 例如： m5 與m7 便可化簡: m5+ m7 = xy'z + xyz = xz (y'+y) = xz 3 (y’+y)Z
三變數卡諾圖 例題 3-1: F(x,y,z) = ∑(2,3,4,5) 相對的全及項方格內填上1 找出倆倆可能相鄰的方格(垂直或水平方向 皆為1) 化簡： 組1: x’y 組2: xy’ 結果： F = x‘y + xy’ y(z+z’)=y y’(z’+z)=y’
三變數卡諾圖 例題 3-2: F(x,y,z) = ∑(3,4,6,7) = yz+ xz‘ 相對的全及項方格內填上1 找出倆倆可能相鄰的方格(皆為1) 化簡： 組1: yz 組2: xz’ 結果： F(x,y,z) = = yz+ xz‘ (x’+x)yz=yz
三變數卡諾圖 可以合併在一起的相鄰方格數必須是2的乘羃： Ex.4個相鄰方格數:方格0, 2, 4與6 或者方格1, 3, 5與7 m0+m2+m4+m6 = x'y'z'+x'yz'+xy'z'+xyz' = x'z'(y'+y) +xz'(y'+y)= x'z' + xz‘ = z' m1+m3+m5+m7 = x'y'z+x'yz+xy'z+xyz=z =x'z(y'+y) + xz(y'+y)=x'z + xz = z
三變數卡諾圖 例題 3-3： F(x,y,z) = ∑(0,2,4,5,6) F = z'+ xy'
三變數卡諾圖 例題 3-4： 已知布林函數 F = A‘C + A’B + AB‘C + BC（及項和） (a)將函數表示成全及項的和。F=Σ(1,2,3,5,7)=m1+m3+m2+m5+m7 (b)求出函數之最簡積項和表示式。
四變數卡諾圖
四變數卡諾圖 相鄰方格的合併 簡化過程 由四變數卡諾圖即可很容易地直接觀察得到： 圖(a) 部分有16個方格，每一個方格分別代表16個全及項中的一個。 3 (16/2=8=2 ) 2 (16/4=4=2 ) 1 (16/8=2=2 )
四變數卡諾圖 例題 3-5: F(w,x,y,z) = S (0,1,2,4,5,6,8,9,12,13,14) 組1: m0, m0, m4, m5,m12, m13,, m8, m7 組2: m2, m6, m0, m4 組3: m6, m14, m4, m12 結果: F = y'+w'z'+xz'
四變數卡諾圖 例題 3-6:化簡布林函數 F = ABC + BCD + ABCD + ABC 全及項的和: 例題 3-6:化簡布林函數 F = ABC + BCD + ABCD + ABC 全及項的和: =Σ(0,1,2,6,8,9,10) 組1: m0, m1, m8, m9 B’C’ 組2: m0, m2 A’B’D’ 組3: m8, m10 AB’D’ 組4: m2, m6 A’CD’ 結果: F=B’C’+A’B’D’+AB’D’+A’CD’ =B’C’+(A’+A)B’D’+A’CD’ =B’C’ + B’D’ + A’CD’ Σ(0,2,8,10)
四變數卡諾圖 在卡諾圖中選擇相鄰的方格時，我們必須確認： 在合併方格時函數所有的全及項全都包含到； 表示式中的項數必須為最少i.e.方格數的選取以2的冪次方由大至小。 沒任何多餘的項 (亦即全及項均已由其他項所包含)。 所謂質含項 (prime implicant) 就是在卡諾圖中可以合併的最大可能相鄰的方格所得到的積項。 單一一個1(沒有其他1與其相鄰）是質含項 2個相鄰的1（在1組4個相鄰的方格中）是質含項 4個相鄰的1（在1組8個相鄰的方格中）是質含項 假如在一個方格的一個全及項只被一個質含項所包含，則此質含項即稱為基本質含項 (essential prime implicant)。
四變數卡諾圖 考慮 F(A,B,C,D)=Σ(0,2,3,5,7,8,9,10,11,13,15) 簡化的表示式可能並非為唯一 F = BD+B'D'+CD+AD = BD+B'D'+CD+AB = BD+B'D'+B'C+AD = BD+B'D'+B'C+AB' m0, m5 (m3,m9,m11)