---
# System prepended metadata

title: 基礎邏輯電路（下）
tags: [電腦雜談, 計算機概論, 電腦]

---

# 基礎邏輯電路（下）

[TOC]

歡迎你點入本篇文章，會促成我想做這篇的原因，主要是因為在上計概時，突然浮現很多靈感，跟一大堆的問題（~~教授，為什麼要講的這麼淺白呢？我想知道更多啊啊！~~），為了一次解決我所有的困惑，於是製作本篇文章。

若文章有任何疑點及錯誤的地方歡迎提出。

本篇文章主要作為個人學習用途，撰筆形式概要以筆記形式撰筆。另外本篇文章以入門為導向，若需詳細閱讀相關學門，請搜尋「數位系統導論」或「數位系統設計」。

## Sum of Products（SOP） Form

先做 AND 運算，再做 OR 運算。

如： $(A \cdot B) + (C \cdot D) + \cdots$

主要是用 $+$ 號連接多項 Products，下圖可能會比較清晰一點。

![image](https://hackmd.io/_uploads/By8gDmYple.png)

Image Source：[What is Sum Of Product (SOP) Form? - GeeksforGeeks](https://www.geeksforgeeks.org/digital-logic/what-is-sum-of-product-sop-form/)

為什麼需要 SOP？因為可以從真值表直接算出布林運算式，接著進一步簡化可畫出電路圖，這是一種蠻好的方式。

### 最小項（Minterm）

最小項是構成 SOP 的基本單位，是一個 AND 項（積項），具有以下特點：

1. 包含所有輸入變數：每個變數都必須出現。
2. 每個變數只出現一次：可為原變數或補數形式。
3. 只用 AND 運算：所有變數用 $\cdot$ 連接。

對於 $n$ 個變數的布林函數，共有 $2^n$ 個最小項。

而最小項的命名規則如下：

最小項用小寫字母 m（最小項的縮寫）加下標來表示，下標號碼由二進位轉十進位而來：

- 變數為 $1$ 時，用原變數（對應二進位 1）。
- 變數為 $0$ 時，用補數（加橫線，對應二進位 0）。

呃什麼意思呢？？接下來做個舉例：

設三變數 $A, B, C$ ，這樣共有 $2^3 = 8$ 個最小項。

| 編號 | 二進位 | A    | B   | C   |  最小項運算式   | 符號 |
| ---- | ------ | ---- | --- | --- | --- | ------------ |
| 0 | 000 | 0 | 0 | 0 | $\overline{ABC}$ | $m_0$ |
| 1 | 001 | 0 | 0 | 1 | $\overline{AB}C$ | $m_1$ |
| 2 | 010 | 0 | 1 | 0 | $\overline{A}B\overline{C}$ | $m_2$ |
| 3 | 011 | 0 | 1 | 1 | $\overline{A}BC$ | $m_3$ |
| 4 | 100 | 1 | 0 | 0 | $A\overline{BC}$ | $m_4$ |
| 5 | 101 | 1 | 0 | 1 | $A\overline{B}C$ | $m_5$ |
| 6 | 110 | 1 | 1 | 0 | $AB\overline{C}$ | $m_6$ |
| 7 | 111 | 1 | 1 | 1 | $ABC$ | $m_7$ |

所謂的最小項就是那些 $\overline{ABC}$ 、 $\overline{AB}C$ 等等，而 $m_0$ 以及 $m_1$ 所代表的意義跟 $\overline{ABC}$ 、 $\overline{AB}C$ 是一樣的。

也就是說 $m_0 = \overline{ABC}$ 、 $m_1 = \overline{AB}C$ 。

### SOP 實際範例

有一個真值表長以下這樣，求出其布林運算式。

| A | B | C | F |
| :-- | :-- | :-- | :-- |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |

可以利用最小項 + SOP 的方法，由於是 SOP，所以只要看輸出的 F 為 1 的項目就好了，其他 0 的不用看。

然後就可以得到 $F = \overline{AB}C + \overline{A}BC + A\overline{B}C + ABC$

接著可以進一步化簡，會發現大家都有共同因式叫做 C，先把他提出來： $F = C(\overline{AB} + \overline{A}B + A\overline{B} + AB)$ 。

提出來後，可以觀察一下 $\overline{AB} + \overline{A}B$ 跟 $A\overline{B} + AB$ ，會發現前一組的有共同因式 $\overline{A}$ ，後一組的有共同因式 $A$ ，所以也可以共同提出來變成： $F = C[\overline{A}(\overline{B} + B) + A(\overline{B} + B)]$ 。

這邊用到之前學過的定律， $\overline{B} + B = 1$ ，因此又會得到 $F = C(\overline{A} + A)$ 。

然後裡面也是這樣的定律，最後化簡完得到 $F = C$ 。（ $C \cdot 1 = C$ ）

## Product of sums（POS） Form

跟 SOP 相反，先做 OR 再做 AND，如： $(A + B) \cdot (C + D) \cdot (E + F) \cdots$

SOP 的基本單位叫做最小項，那 POS 的就叫做最大項（Maxterm），就直接進入例子來看 POS 了。

設有以下簡單的真值表，兩變數 $A, B$ ：

| A | B | F |
| -------- | -------- | -------- |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

如果是 SOP 的話，只要看 1 的去做就好，會變成： $F = \overline{A}B + A\overline{B}$

但換成 POS 的話，是要看 0 的情形去算，變成： $F = (A + B) \cdot (\overline{A} + \overline{B})$ 。

POS 後面為 $\overline{A} + \overline{B}$ 的原因是因為笛摩根定理，如果照著前面想法寫成 $\overline{A + B}$ 的話就會錯囉，因為 POS 裡面要是 OR 運算先。

## 加法器（Adder）

顧名思義，就是執行加法運算的數位電路部件，是構成電子計算機核心微處理器中算術邏輯單元（ALU）的基礎。在電子系統中，加法器主要負責計算地址、索引等數據，也是其他硬體（例如二進位數的乘法器）的重要組成部分。

加法器有兩種，一個是半加器（Half adder），一個是全加器（Full adder）。

### 半加器（HA：Half adder）

半加器習慣簡稱為 HA，他是最基本的數位加法電路，專門處理兩個一位元二進位數（如十進位的個位數相加）的相加運算。

HA 有兩個輸入端（「被加數 $A$ 」和「加數 $B$ 」）以及兩個輸出端：和（Sum, $S$ ）與進位（Carry, $C$ ）。這兩個一位元二進制數的和用十進制表示即等於 $2C + S$ 。

而這個 $C$ 呢，也可以表示成 $C_o$ ，下面的 $o$ 表示 out 的意思。

因為 HA 只有兩個輸入端，所以真值表的可能輸出結果也就對應到四個輸出，以下是 HA 的真值表：

| A | B | C | S |
| :-- | :-- | :-- | :-- |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |

先來看 S 的部分是怎麼得出來的，這邊用條列式的步驟看會比較清楚：

1. $A = 0, B = 0,$ $S = A + B = 0 + 0 = 0$
2. $A = 0, B = 1,$ $S = A + B = 0 + 1 = 1$
3. $A = 1, B = 0,$ $S = A + B = 1 + 0 = 1$
4. $A = 1, B = 1,$ $S = A + B = 1 + 1 = 10$

由於真值表的輸出只能表示一個位元，因此最後的 $S = (10)_2$ 的 1 被省略掉了，但這也表示一件事情，那就是他進位了，所以最後要在 C 的地方寫上 1，表示 S 已經進一位。

這邊可以用布林代數式簡單表示出 S 跟 C：

- $S = A \oplus B$
- $C = A \cdot B$

然後透過這個布林代數式我們可以得出以下電路：

![image](https://hackmd.io/_uploads/B17MWB56eg.png)

Image Source：[File:Half Adder.svg - 維基百科，自由的百科全書](https://zh.m.wikipedia.org/zh-tw/File:Half_Adder.svg)

而這個電路可以用一個正方形寫 HA，再加上兩個輸出簡單表示：

![image](https://hackmd.io/_uploads/Sk0u-S9pxg.png)

Image Source：[The Elements of Computing Systems: 02-Combinational Chips | by Anuj Yadav | Medium](https://medium.com/@yadavanuj/the-elements-of-computing-systems-02-combinational-chips-d389210dc9d0)

#### 半加器的缺點

唯一缺點就是不能做到前級進位運算，像是十進位的 19 + 23，會先算個位數 9 + 3 = 12，將 2 寫下然後 1 進位到十進位，而 1 為前級進位。在多位元的加法器中，每一位元都需要考慮前一位元的進位，不然加法結果就錯了。

整理一下：半加器像是只能十進位的個位數相加，不能做到兩位數以上相加。

那要怎麼解決這個問題呢？這時候就請出我們的全加器了。

### 全加器（FA：Full Adder）

全加器（Full Adder）是數位電路中用來執行三個一位元二進位數相加的組合邏輯電路。

他在半加器的基礎上多了一個輸入，所以總共是三個輸入：

- 兩加數（A、B）
- 前一位元的進位數（ $C_{in}$ ）

輸出一樣維持兩個：

- 和（Sum, $S$ ）
- 進位（Carry, $C_{out}$ ）

全加器的真值表如下所示：

| $A$ | $B$ | $C_i$ | $S$ | $C_o$ |
| :-- | :-- | :-- | :-- | :-- |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |

註：該真值表的輸入排列方式是以二進位不斷加一、進位得到的。

真值表最後的 $S = A + B + C_i = (11)_2$ 因為只看最右邊的 $1$ ，所以真值表這邊 $S = 1$ ，而同時也有進位，所以 $C_o = 1$ 。

然後這要怎麼轉成布林代數式呢？只要用到前面學到的 SOP 技巧即可。

- $S = \overline{AB}C_i + \overline{A}B\overline{C_i} + A\overline{BC_i} + ABC_i$
- $C_o = \overline{A}BC_i + A\overline{B}C_i + AB\overline{C_i} + ABC_i$

上述兩式都可以繼續化簡，以下是 $S$ 的化簡詳細步驟：

觀察一下可以提出 $C_i$ 跟 $\overline{C_i}$ ，變成 $S = C_i(\overline{AB} + AB) + \overline{C}(\overline{A}B + A\overline{B})$ 。

前面括號裡面的叫做 A XNOR B，後面的叫做 A XOR B，所以可以進一步寫成： $S = C_i(\overline{A \oplus B}) + \overline{C_i}(A \oplus B)$ 。

這邊設一個變數叫做 X，令 $X = A \oplus B$ ，代入原式可得到 $S = C_i \overline{X} + \overline{C_i}X$ ，可看到這就是 XOR 的定義了，再改成 XOR 符號： $S = X \oplus C_i$ 。

最後將 X 展開就會得到我們想要的精簡過後的結果了： $S = A \oplus B \oplus C_i$
 
以下為 $C_o$ 的化簡詳細步驟：

看到 $C_i$ ，可以跟 $\overline{A}BC_i + A\overline{B}C_i$ 配，因此提出 $C_i$ ，注意這邊不要也把後面的 $ABC_i$ 牽扯進去了，會算得很麻煩。

ok 首先得到這樣的式子： $C_o = C_i(\overline{A}B + A\overline{B}) + AB\overline{C_i} + ABC_i$ 。

之後後面可以提出 AB，變成 $C_o = C_i(\overline{A}B + A\overline{B}) + AB(\overline{C_i} + C_i)$ 。

觀察一下可以發現前面的是 A XOR B，後面抵銷變成 1，最後得到最精簡的式子： $C_o = C_i(A \oplus B) + AB$

最後的最後，讓我來列出兩個式子的最終結果：

- $S = A \oplus B \oplus C_i$
- $C_o = C_i(A \oplus B) + AB$

以下就是 $S, C_o$ 的電路畫法：

![image](https://hackmd.io/_uploads/HJhOHdqpxx.png)

Image Source：[Full Adder - GeeksforGeeks](https://www.geeksforgeeks.org/digital-logic/full-adder-in-digital-logic/)

FA 也可以畫成這樣：

![image](https://hackmd.io/_uploads/B1RgU_q6xe.png)

用兩個 HA 也可以實現 FA：

![image](https://hackmd.io/_uploads/BJMmLO9Tex.png)

Image Source：[Full Adder - GeeksforGeeks](https://www.geeksforgeeks.org/digital-logic/full-adder-in-digital-logic/)

## 總結

### 一、Sum of Products（SOP）

SOP（乘積之和）是一種布林函數表示法。

定義是先進行 AND，再進行 OR。

形式：$(A \cdot B) + (C \cdot D) + \cdots$

為何使用 SOP？可由真值表直接導出布林運算式，再經化簡後可轉換為邏輯電路，是數位設計的基礎流程之一。

SOP 在實作時看輸出是 1 的，0 的不用看。

#### 最小項（Minterm）

最小項是 SOP 的基本構成單位，具以下特性：

1. 包含所有輸入變數。
2. 每個變數僅出現一次（原變數或補數形式）。
3. 僅使用 AND 運算。

對於 $n$ 個變數，共有 $2^n$ 個最小項。

命名方式： $m_i$，下標 $i$ 由變數真值的二進位轉十進位得來。

### 二、Product of Sums（POS）

定義：POS（和之積）為 SOP 的相反形式，也就是先進行 OR，再進行 AND。

形式：$(A + B) \cdot (C + D) \cdot (E + F) \cdots$

反之，SOP 有最小項，那 POS 就會是最大項，同樣把兩者原理顛倒就好。

POS 在實作時看輸出是 0 的，1 的不用看。

注意：POS 內部必須是 OR 運算，若誤寫成 $\overline{A+B}$ 則違反定義，所以要做 POS 記得寫成 $\overline{A} + \overline{B}$

### 三、半加器（HA：Half Adder）

功能：對兩個一位元二進位數 $A$、$B$ 相加。

輸入： A, B
輸出：和（Sum, S）、進位（Carry, C 或 $C_o$）

真值表：

|  A  |  B  |  C  |  S  |
| :-: | :-: | :-: | :-: |
|  0  |  0  |  0  |  0  |
|  0  |  1  |  0  |  1  |
|  1  |  0  |  0  |  1  |
|  1  |  1  |  1  |  0  |

布林代數式：

- $S = A \oplus B$
- $C = A \cdot B$

缺點：

1. 無法處理前級進位（Carry-in），
2. 僅適用於一位元加法。

### 四、全加器（FA：Full Adder）

功能：可處理三個輸入（含前一位的進位）。

輸入：A, B, $C_i$ （前級進位）
輸出：S（和）、 $C_o$（進位）

真值表：

|  A  |  B  | $C_i$ |  S  | $C_o$ |
| :-: | :-: | :---: | :-: | :---: |
|  0  |  0  |   0   |  0  |   0   |
|  0  |  0  |   1   |  1  |   0   |
|  0  |  1  |   0   |  1  |   0   |
|  0  |  1  |   1   |  0  |   1   |
|  1  |  0  |   0   |  1  |   0   |
|  1  |  0  |   1   |  0  |   1   |
|  1  |  1  |   0   |  0  |   1   |
|  1  |  1  |   1   |  1  |   1   |

布林代數式（已化簡，由 SOP 做過來的）：

- $S = A \oplus B \oplus C_i$
- $C_o = C_i(A \oplus B) + AB$

電路結構：可由兩個半加器 + 一個 OR 閘組成。

### 五、總表

| 類別      | 運算順序     | 基本單位         | 典型形式                               | 應用              |
| ------- | -------- | ------------ | ---------------------------------- | --------------- |
| **SOP** | AND → OR | 最小項（Minterm） | $(A \cdot B) + (C \cdot D)$        | 從真值表得出輸出為 1 的條件 |
| **POS** | OR → AND | 最大項（Maxterm） | $(A + B) \cdot (\overline{C} + D)$ | 從真值表得出輸出為 0 的條件 |
| **HA**  | 二輸入加法    | 無前級進位        | $S=A⊕B$, $C=AB$                    | 單位元加法           |
| **FA**  | 三輸入加法    | 含前級進位        | $S=A⊕B⊕C_i$, $C_o=AB+C_i(A⊕B)$     | 多位元加法基礎元件       |

## 參考資料

[Chapter2-數位邏輯-Digital Logical | PinJin's Blog](https://pingjing0628.github.io/2021/04/01/Chapter2-%E6%95%B8%E4%BD%8D%E9%82%8F%E8%BC%AF-Digital-Logical/)

[Logical Expression in SOP and POS Form](https://www.tutorialspoint.com/digital-electronics/logical-expression-in-sop-and-pos-form.htm)

[Difference between SOP and POS in Digital Logic - GeeksforGeeks](https://www.geeksforgeeks.org/digital-logic/difference-between-sop-and-pos-in-digital-logic/)

[Half Adder · Nand2tetris-Homework](https://tomorrow0w0.gitbooks.io/nand2tetris-homework/content/chapter2/HalfAdder.html)

[Half Adder - GeeksforGeeks](https://www.geeksforgeeks.org/digital-logic/half-adder-in-digital-logic/)

[Full Adder - GeeksforGeeks](https://www.geeksforgeeks.org/digital-logic/full-adder-in-digital-logic/)

[加法器 - 維基百科，自由的百科全書](https://zh.wikipedia.org/zh-tw/%E5%8A%A0%E6%B3%95%E5%99%A8)

[加法器如何工作？ |类型和功能解释 | 台灣 聯想](https://www.lenovo.com/tw/zh/glossary/adder/)

[Full Adder · Nand2tetris-Homework](https://tomorrow0w0.gitbooks.io/nand2tetris-homework/content/chapter2/FullAdder.html)

