Learning Objectives
- 說明相鄰格子為什麼可以合併，以及卡諾圖為什麼用格雷碼排列
- 在 2 到 4 變數的卡諾圖上圈出最簡的乘積相加式
- 利用隨意項讓式子更短，並說明這樣做的代價
- 把化簡結果接成電路，比較閘的數量與延遲
同一個功能，閘越少越好
三位評審表決，至少兩位同意才通過。把同意記成 1，從真值表直接寫最小項相加，會得到：
Y = A′·B·C + A·B′·C + A·B·C′ + A·B·C
4 個乘積、12 個文字（literal，一個變數或它的反相算一個文字）。可是這個功能只需要 A·B + B·C + A·C：3 個乘積、6 個文字。每少一個文字，就少一條線接進閘裡；每少一個閘，晶片面積就小一點、耗電少一點，訊號要經過的層數也可能變少。
化簡靠的是一條規則：
A·B + A·B′ = A·(B + B′) = A·1 = A
兩個乘積只差一個變數的反相時，可以合併，那個變數會消失。 意思很直白：不管 B 是什麼結果都一樣，那 B 就不重要。
難處在於怎麼找出這些配對。項目一多，靠代數改寫容易漏掉，也不知道什麼時候算寫完了。
把真值表排成一張圖
卡諾圖（Karnaugh map）把真值表換個排法，讓「只差一個變數」變成「在圖上相鄰」，用眼睛就能找到可以合併的項目。Edward Veitch 在 1952 年發表用圖表化簡真值函數的方法，Maurice Karnaugh 在 1953 年的論文裡重新安排了這張圖，成為今天通用的形式。
3 個變數的卡諾圖長這樣，格子裡的數字是最小項的編號（把 ABC 當成二進位，m5 就是 A＝1、B＝0、C＝1）：
A＼BC 00 01 11 10
0 m0 m1 m3 m2
1 m4 m5 m7 m6
注意欄的順序是 00 01 11 10，不是 00 01 10 11。這是格雷碼（Gray code）：相鄰兩個只差一個位元。如果照二進位順序排，01 和 10 會成為鄰居，但它們差了兩個位元，兩格圈在一起也消不掉變數。
最左邊的 00 和最右邊的 10 也只差一個位元，所以卡諾圖的左右邊緣是相連的，上下邊緣也一樣。想像把紙捲起來接成一個圈。
確認格雷碼的相鄰關係
用程式檢查四個位置的相鄰關係，包括最後一個接回第一個的那一對，再和二進位順序比較。
圈選的規則與背後的理由
| 規則 | 理由 |
|---|---|
| 圈內只能有 1（或等一下會講的 d） | 圈到 0，那一格的輸入就會輸出 1，功能錯了 |
| 大小只能是 1、2、4、8、16 格 | 每對折一次消掉一個變數，3 格不可能剛好對折 |
| 形狀是矩形，邊緣可以環繞 | 只有這樣圈裡的格子才兩兩配對 |
| 所有的 1 都要被圈到 | 沒圈到的列會輸出 0 |
| 圈越大越好 | 每放大一倍少一個文字 |
| 圈越少越好 | 每多一圈多一個乘積，也多一個閘 |
讀出乘積項的方法：看圈裡的格子，值有變化的變數消失，值固定的變數留下，固定是 1 就直接寫，固定是 0 就加反相。在 4 個變數的圖上，2 格留 3 個文字、4 格留 2 個、8 格留 1 個、16 格全部消失，式子就是 1。
每個不能再放大的圈叫做質蘊涵項（prime implicant）。最簡的式子一定由它們組成，但不一定全部都要用，所以「永遠先圈最大的」並不保險。比較可靠的順序是：先找只有一種最大圈包得住的 1，那個圈一定要選（叫做必要質蘊涵項），剩下的再用最少的圈補齊。
下面第二題就是這個陷阱。第三題則有不只一種最簡答案，這是正常的。
隨意項：不會出現的輸入
有些輸入在實際使用時根本不會出現，它們的輸出是什麼都無所謂，這些列叫做隨意項（don't care），圖上寫成 d。
典型的例子是用 4 個位元表示一個十進位數字（BCD，binary-coded decimal），再點亮七段顯示器。4 個位元能表示 0～15，但數字只到 9，所以 10～15 是隨意項。
aaa
f b
ggg
e c
ddd
看最上面那一橫 a。以常見的字形，數字 0、2、3、5、6、7、8、9 要亮，1 和 4 不亮。
隨意項的用法是：對你有利時當成 1 圈進去，否則當成 0 不理它。圈裡可以有 d，只包 d 的圈沒有意義。下面的練習先假裝沒有隨意項，再加上去，比較兩個結果。
化簡結果接回電路
回到一開始的表決電路。下面第一個電路是不化簡的版本，第二個由你接。兩個真值表應該完全相同，差別在閘的數量與訊號要經過的層數。
SOP 接成電路的方式固定：每個乘積一個 AND，全部接到一個 OR，需要反相的變數加 NOT。這叫兩層邏輯（two-level logic），AND 一層、OR 一層，不算反相器。
用窮舉確認化簡沒有改變功能
卡諾圖是手工方法，圈錯了不會有人提醒你。變數不多的時候，窮舉每一種輸入是最可靠的檢查。
變數再多就換工具
卡諾圖適合 4 個變數以內。5、6 個變數要疊成好幾張圖，不同層之間也算相鄰，用眼睛已經不好找；更多變數就沒辦法了。
電腦用的方法有兩類。Quine-McCluskey 方法（Quine 1952 年提出，McCluskey 1956 年擴充）把乘積項列成表，兩兩比較合併，保證找到最簡結果，但執行時間隨變數數量指數成長。ESPRESSO（Brayton 等人在 1980 年代開發）是啟發式方法：不保證是最簡，但速度快很多，結果通常很接近。保證最好與來得及算完，在這裡是要取捨的。
另外要知道卡諾圖的範圍：它找的是兩層 SOP 裡最簡的。例如剛才 a 段的 A + C + B·D + B′·D′，其中 B·D + B′·D′ 就是 XNOR，所以可以接成 1 個 XNOR 加 1 個 OR3，只要 2 個閘。多層電路可能比最簡的兩層 SOP 更省，真實的合成工具會考慮這些，也會考慮延遲與面積的平衡。
確認一下
卡諾圖的欄為什麼排成 00 01 11 10？
4 變數的卡諾圖上，一個 8 格的圈化簡後是什麼樣子？
同學圈了一個包到 0 的 4 格圈，因為這樣文字比較少。結果會怎樣？
一個隨意項 d 被圈進某個圈裡，對這個電路的意思是？
為什麼「永遠先圈最大的」不一定得到最簡答案？
重點整理
A·B + A·B′ = A：只差一個變數的兩項可以合併。卡諾圖用格雷碼排列，讓這些項在圖上相鄰，邊緣也相連。- 圈只能是 1、2、4、8、16 格的矩形，不能包到 0。值有變化的變數消失，固定的留下。
- 最簡答案由質蘊涵項組成，但不一定全用，也可能不只一種；先選必要質蘊涵項。
- 隨意項對你有利就當 1。硬體不知道它「不該出現」，所以要確認真的不會出現。
- 變數多時改用 Quine-McCluskey 或 ESPRESSO；兩層 SOP 的最簡不一定是整體最省的電路。
下一課看兩種到處都用得到的組合電路：多工器與解碼器。