卡諾圖的化簡

1.認識 minterm & maxterm

Minterm   :  由輸入或輸入的補數構成的   AND
    比如有兩個輸入x,y，那minterm = xy , x’y, xy’ ,x’y’
Maxterm ： 由輸入或輸入的補數構成的    Or
    比如有兩個輸入x,y，那maxterm = x + y, x’+y , x+y’ , x’+y’

->考慮DeMorgan’s theorem
    (A + B + C)’ = A’B’C’
    (ABC)’ = A’ + B’ + C’

可以進行Minterm與Maxterm之間的轉換：
    e.g. x’y’z’ = m0 = x + y + z =M0
再比如說有一個電路
    F = x’y’z’ + xy’z’ + xyz = m1 + m4 + m7，
    F’ = x’y’z’ + x’yz +x’yz’ +xy’z +xyz’ =m0 + m2 +m3 +m5 +m6
    F’’ = (x+y+z)(x+y’+z)(x+y’+z’)(x’yz’)(x’y’z)
所以說F可表達成兩個形式

    1.  5個 minterm    or   在一起 （ＳＯＰ）sum of product形式
    2.  5個 Maxterm  and 在一起 （ＰＯＳ）product of sum形式


那有了Minterm跟Maxterm有什麼好處呢？

    若電路F表示為 x’y’z + xyz +xyz’
    上述的F稱為 canonical form，因為它有三個輸入，而且每項都有3個變數，實際上F可化簡為x’y’z +xy，但這樣就非 canonical form
    那表示成canonical form又有什麼好處？就是真值表定可表達成canonical form，比如說：
        x=0,y=0,z=1，可以寫作x’y’z
        x=0,y=1,z=1，可以寫作x’yz
        x=1,y=1,z=0，可以寫作xyz’
    所以只要有真值表，任何電路總能表達成canoncial form（ＳＯＰ或ＰＯＳ），但是這個形式有個致命的缺點，就是他的變數很多，這間接導致了成本增加。

於是，我們需要簡化的技巧

Gate-level minimization

2.Karnaugh Map

    1.按照格雷碼填入電路輸入 e.g(00 , 01, 11, 10)
    2.圈1 or 圈 0 ，以1,2,4,8,16,32...2的次方為個數去圈，儘量多圈讓化簡達到最大效果
    3.圖視為連通的
    4.持續的圈0 or 圈1，直到所有的0或1都被圈到
    5.圈1得到化簡的F (SOP形式)，圈0得化簡的F' (SOP形式)，需再做一次迪摩根得F(POS形式)
   
0或1可以重複圈，但是一定要完全圈完其中一種
注意：如果一個項的變數個數跟輸入不同，比如說輸入有w,x,y,z，但F中有一項為wxy’，即缺少了z項，那麼我們就要把wxy’z與wxy’z都視為1

卡諾圖的消去原理：(x' + x) = 1