---
title: Karnaugh-Map 和 Quine McCluskey|第五週
tags: 數位系統與實驗
---

## Karnaugh-Map

因為有視覺化的圖形，比較適合人腦；通常適用 2~5 個變數，再往上就超出可以視覺化的部分了

## Quine McCluskey

雖然沒有了視覺化的圖形，但是這樣就可以有條理的列出每個階段的步驟，反而沒有了 Karnaugh-Map 在 6 個變數以上很難呈現的困擾
也因為這個特性很適合用來寫出演算法

## 重要點

- Karnaugh-Map：相鄰的兩格只能有一個 bit 是不一樣的
- Quine McCluskey：每次要合併時只能有一個 bit 是不一樣的

---

# Karnaugh-Map 步驟

## 1. 畫出卡諾圖

:::warning
注意，畫的時候，相鄰兩格一次只能有 1 個 bit 不一樣
:::

### 這是 4 個變數的卡諾圖


### 這是 3 個變數的卡諾圖


### 這是 2 個變數的卡諾圖


### 這是 5 個變數的卡諾圖


這個很像是在原本的四個變數之上多疊一層樓

## 2.將你的式子中的會等於 1 和 0 的都填上去

這裡以 4 個變數舉例

假如我們的式子是

| Term | A | B | C | D | F(A,B,C,D) |
|:--------:|:---:|:---:|:---:|:---:|:----------:|
| $M_{0}$ | 0 | 0 | 0 | 0 | 0 |
| $m_{1}$ | 0 | 0 | 0 | 1 | 1 |
| $M_{2}$ | 0 | 0 | 1 | 0 | 0 |
| $m_{3}$ | 0 | 0 | 1 | 1 | 1 |
| $m_{4}$ | 0 | 1 | 0 | 0 | 1 |
| $m_{5}$ | 0 | 1 | 0 | 1 | 1 |
| $M_{6}$ | 0 | 1 | 1 | 0 | 0 |
| $M_{7}$ | 0 | 1 | 1 | 1 | 0 |
| $M_{8}$ | 1 | 0 | 0 | 0 | 0 |
| $M_{9}$ | 1 | 0 | 0 | 1 | 0 |
| $m_{10}$ | 1 | 0 | 1 | 0 | 1 |
| $M_{11}$ | 1 | 0 | 1 | 1 | 0 |
| $m_{12}$ | 1 | 1 | 0 | 0 | 1 |
| $m_{13}$ | 1 | 1 | 0 | 1 | 1 |
| $M_{14}$ | 1 | 1 | 1 | 0 | 0 |
| $M_{15}$ | 1 | 1 | 1 | 1 | 0 |

可以知道

$$
F(A,B,C,D)=\sum m(1,3,4,5,10,12,13)=\prod M(0,2,6,7,8,9,11,14,15)
$$

然後將上面的情況填進去


## 3.開始圈 1 或 0

:::warning
1. 圈的時候，一定要圈最大的；並且每次只能圈 2 的整數次方個
- 像是 1,2,4,8 個...
2. 所有的 1 或 0 都要圈到
3. 讓圈圈的總數是最小的
- 所以要先評估，哪些 1 或 0 是只會被 1 個圈圈包住
- 那麼該圈圈就一定要圈，優先把它圈起來
4. 如果有 DC ，請視情況將他視為 1 或 0，只要能夠讓你圈越大、圈越少就好
:::

### SOP

:::success
SOP 要把 1 圈起來
:::


:::warning
- 上圖中，橘色的就是圈最大、圈最少的結果
- 但是綠色的圈圈，**就是多餘的**；上面只是為了示範用才圈他
:::

### POS

:::success
POS 要把 0 圈起來
:::


:::warning
圈的時候要注意一些事情
1. 整個圖是「循環的」，也就是說右邊邊界，跟左邊邊界是相鄰的；上下邊界亦然
- 所以圖中，最左上角那格，跟最左下角那格是相鄰的
- 所以要把那兩個相鄰的 0 給他圈起來
- 圖中最右上角那格跟最左上角那格也是同理，屬於相鄰的格子，要圈起來
:::

## 4.將圈起來的內容寫下來

### SOP

從結果可以知道，我們圈了 3 個地方

1. 中間四個被圈起來的，看看哪個變數同時出現 0 跟 1，就把它刪掉
- 可以知道是 A 跟 D
- 所以那個圈圈得出的式子就是 $BC'$
- 0 代表 $'$ 1 代表沒有 $'$
2. 左邊兩個圈起來的，看看哪個變數同時出現 0 跟 1，就把它刪掉
- 可以知道只有 C
- 所以那個圈圈得出的式子就是 $A'B'D$
3. 右下角那孤獨的 1，就直接把他寫起來
- 因此就是 $AB'CD'$

最後，將結果 OR 起來，就會得到

$$
BC'+A'B'D+AB'CD'
$$

### POS

從結果可以知道，我們圈了 4 個地方，寫起來的方法跟剛剛 SOP 一樣

1. 中間四個被圈起來的
- $BC$
3. 左上跟右上角被圈起來的
- $B'C'D'$
5. 左上跟左下角被圈起來的
- $A'B'D'$
7. 右邊兩個被圈起來
- $AB'D$

一樣，將結果 OR 起來，就會得到

$$
BC+B'C'D'+A'B'D'+AB'D
$$

而 POS 最不一樣的步驟是，將上面的整個式子取反，並使用迪摩根化簡

$$
(BC+B'C'D'+A'B'D'+AB'D)'\\
=(BC)'(B'C'D')'(A'B'D')'(AB'D)'\\
=(B'+C')(B+C+D)(A+B+D)(A'+B+D')
$$

## 原理

### SOP

會去看哪個變數同時有 1 跟 0，然後把它刪掉，是因為如果把它寫出來，其實就長得像：

$$
AB+AB'=A(B+B')=A
$$

利用了分配律，這就是為甚麼可以消掉的原因

### POS

為了方便說明，例子改成 2 個變數

假如有某個邏輯式子是這樣

$$
F(A,B)=\sum m(0,1)
$$

1. 我們知道由 minterm 組成的 SOP 是標準的 SOP，所以他是可以化簡成最簡單的 SOP
>其實這裡很明顯就是 $F(A,B)=A'$

2. 我們也知道同個式子除了用上面的標準 SOP 表示，也可以由標準 POS 表示，也就是 maxterm

$$
F(A,B)=\prod M(2,3)
$$

3. 這個標準的 POS 一定可以化簡成最簡單的 POS

4. 回顧之前 minterm 跟 maxterm 是互補的關係，也就是說

$$
m_{i}=M_{i}'
$$

5. 此時回想我們圈 0 到底做了甚麼
- 把 0 給圈起來，其實就是在圈 Maxterm 對應的那些組別，像上面例子中的 2 跟 3
- 但是由於當初建立卡諾圖的時候，是根據 minterm 的情況建立的
- 也就是說 0 對應的是 $'$ 1 對應的是沒有 $'$
- 所以我們圈起來化簡後的結果就是 $\sum m(2,3)$ 化簡的結果

6. 所以我們藉由圈 0 得到了 $\sum m(2,3)$ 的化簡結果，但本質上跟 $\sum m(2,3)$ 是等價的，所以可以藉由互補關係，給他取反，得到 $\prod M(2,3)$ 的最簡結果

:::warning
那直接取反得到的真的是最簡結果嗎？底下藉由直接圈出 POS 來說明為甚麼是最簡結果
:::

## 直接圈 POS

此時回顧之前提到的「不直覺的分配律」

$$
(A+B)(A+B')=A+BB'=A
$$

上面這件事告訴我們，如果 Maxterm 之間如果有個變數同時有 1 跟 0，那他就可以消掉，像是

$$
(A+B+C+D')(A+B+C+D)=A+B+C+DD'=A+B+C
$$

所以其實我們也可以不用採取取反的方式，直接用卡諾圖圈出我們要的 SOP


這裡就直接以上面圈好的為例子，可以注意到，為了換成以 POS 為主，所以將 bit 整個取反了(綠色)

所以接下來做的事情就跟原本 SOP 一樣，看誰有 0 跟 1 ，就把他刪掉

1. 中間四個被圈起來的
- $B'+C'$
3. 左上跟右上角被圈起來的
- $B+C+C$
5. 左上跟左下角被圈起來的
- $A+B+D$
7. 右邊兩個被圈起來
- $A'+B+D'$

接下來全部 OR 起來就是我們要的最簡 POS 了

:::warning
此時應該會注意到，「圈起來」跟「刪掉」這兩個步驟，不管是先以 SOP 的角度然後再取反，還是直接取 POS，我們圈起來的，還有刪掉的變數都是相同的，所以兩者都是最簡的結果
:::

---

## Prime Implicant

就是不能再長大的框框

:::warning
可以使用 MQ 有系統的找出所有 PI
:::

## Non Prime Implicant

就是還可以再長大的框框

**而一個最簡式子，一定只包含 PI**


## Essential PI

就是如果你要圈 1 或 0 的時候，有人只能被圈到 1 次，則包含那個 1 或 0 的圈圈就是 EPI
一定要優先把 EPI 圈起來，這樣就可以筆記好規劃要圈誰

## Two level Logic

是在講像 SOP 這種，一堆變數先經過 AND ，然後再一起 OR 起來的樣子，很像經過兩層結構

## 講義 POS 範例


---

# Quine McCluskey

## 例子

| Term | A | B | C | D | F(A,B,C,D) |
|:--------:|:---:|:---:|:---:|:---:|:----------:|
| $m_{0}$ | 0 | 0 | 0 | 0 | 1 |
| $m_{1}$ | 0 | 0 | 0 | 1 | 1 |
| $m_{2}$ | 0 | 0 | 1 | 0 | 1 |
| $M_{3}$ | 0 | 0 | 1 | 1 | 0 |
| $M_{4}$ | 0 | 1 | 0 | 0 | 0 |
| $m_{5}$ | 0 | 1 | 0 | 1 | 1 |
| $m_{6}$ | 0 | 1 | 1 | 0 | 1 |
| $m_{7}$ | 0 | 1 | 1 | 1 | 1 |
| $m_{8}$ | 1 | 0 | 0 | 0 | 1 |
| $m_{9}$ | 1 | 0 | 0 | 1 | 1 |
| $m_{10}$ | 1 | 0 | 1 | 0 | 1 |
| $M_{11}$ | 1 | 0 | 1 | 1 | 0 |
| $M_{12}$ | 1 | 1 | 0 | 0 | 0 |
| $M_{13}$ | 1 | 1 | 0 | 1 | 0 |
| $m_{14}$ | 1 | 1 | 1 | 0 | 1 |
| $M_{15}$ | 1 | 1 | 1 | 1 | 0 |

好的我知道看上面那個會看到眼花

$$
F(A,B,C,D)=\sum m(0,1,2,5,6,7,8,9,10,14)=\prod M(3,4,11,12,13,15)
$$

## 1.分區

先把 minterm 是 1 的列蒐集起來，並且依照該 minterm 有 1 的個數，分成小區塊
下面是四個變數的例子，所以分成四個區塊，也就是有 0 個 1，1 個 1，2 個 1 ...


## 2.合併

其實上圖就有在做合併的動作。

1. 所謂的合併，就是看哪些組別他們只有一個 bit 不一樣，那就可以把這兩個併起來
- 所謂的只有 1 個 bit 不一樣，就是該 bit 一個人是 1 另一個是 0
- 併起來之後用「底線 _ 」標記這個位置
- 但是不能因為那個位置可以是 0 或 1，就以為他可以拿來跟別人合併
- 反而是兩組要合併時，該 bit 都要是「底線 _ 」才可以合併
3. 由於先前已經分好組別了，所以可以知道 0 個 1 的 跟 2 個 1 的一定不可能合併在一起
4. 有合併的，就移到新的表格，並標記誰跟誰合併，還有合併的樣子，如上圖
5. 如果有無法合併的組別，就把他做記號標起來
- 但是上圖因為都可以合併，所以看不到記號

## 3.持續合併

沒錯，要一直合併，直到沒有組別可以合併下去


1. 上圖中，兩兩個一組的組別中，只有 (1,5),(5,7),(6,7) 這三組無法合併下去變成四個一組，所以用紅色標起來
2. 由於到了四個一組，所以有可能合併起來後會有重複的，像上面畫紅線的就是重複的組別
3. 最後一樣檢查看看能不能繼續合併
- 可以的話就是要重複持續合併的步驟，然後持續把不能合併的記錄下來

而這個例子到這裡就不能再繼續合併了

:::warning
這個合併的過程，其實就是卡諾圖在畫圈圈的過程，但是 QM 的不是一次畫最大圈，而是慢慢由小圈圈變成大圈圈
:::

## 4.列出來找 EPI

上面逐漸把圈圈長好長滿的結果，就是要去除掉不用圈的


在卡諾圖中，上面可以發現深色框的就是只被圈到一次的 1，所以包含他的圈圈就是 EPI


上面就是依照我們結果畫出的表格

1. 左半邊就是我們無法再往下合併的各個大小圈圈，記得順便紀錄他的 bit 狀況
2. 右半邊就是組成那些圈圈需要的 Minterm
- 所以不用全部列出來
3. 深色的框框，也就是 9 號跟 14 號，就是我們只被圈到一次的 1
- 所以 (0,1,8,9),(2,6,10,14)這兩組就是 EPI，是一定要圈的圈圈

## 5.去除掉不需要的圈圈

有了優先需要的圈的組別後，代表該組別的 minterm 都會被圈到
所以如果有其他小圈圈是由這個組別的 Minterm 組成，代表該圈圈就是重複的
也就是下圖中間那條圈圈



1. EPI 所擁有的 Minterm 分別是 橘色線的和綠色線的
2. 畫掉後會剩下 5 跟 7 這兩個 Minterm，而正好就有組別是 5 跟 7 組成的
3. 所以可以知道，這一步跟卡諾圖一樣，圈圈要畫越少越好

## 6.列出結果

上面總共需要三個圈圈，把這三個圈圈的 bit 情況寫出來

$$
F(A,B,C,D)=m(0,1,8,9)+m(2,6,10,14)+m(5,7)\\
= B'C'+CD'+A'BD
$$

## 跟卡諾圖對應


---

## 用卡諾圖解釋 Consensus


之前學的其他的定理也都可以用卡諾圖解釋