# 基礎邏輯電路（下）
[TOC]
歡迎你點入本篇文章，會促成我想做這篇的原因，主要是因為在上計概時，突然浮現很多靈感，跟一大堆的問題（~~教授，為什麼要講的這麼淺白呢？我想知道更多啊啊！~~），為了一次解決我所有的困惑，於是製作本篇文章。
若文章有任何疑點及錯誤的地方歡迎提出。
本篇文章主要作為個人學習用途，撰筆形式概要以筆記形式撰筆。另外本篇文章以入門為導向，若需詳細閱讀相關學門，請搜尋「數位系統導論」或「數位系統設計」。
## Sum of Products（SOP） Form
先做 AND 運算，再做 OR 運算。
如： $(A \cdot B) + (C \cdot D) + \cdots$
主要是用 $+$ 號連接多項 Products，下圖可能會比較清晰一點。
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 Source：[File:Half Adder.svg - 維基百科，自由的百科全書](https://zh.m.wikipedia.org/zh-tw/File:Half_Adder.svg)
而這個電路可以用一個正方形寫 HA，再加上兩個輸出簡單表示：
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 Source：[Full Adder - GeeksforGeeks](https://www.geeksforgeeks.org/digital-logic/full-adder-in-digital-logic/)
FA 也可以畫成這樣：
用兩個 HA 也可以實現 FA：
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)
Sign in with Wallet
Connect another wallet