基礎邏輯電路（下）

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

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

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

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

為什麼需要 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 - 維基百科，自由的百科全書

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

Image Source：The Elements of Computing Systems: 02-Combinational Chips | by Anuj Yadav | Medium

半加器的缺點

唯一缺點就是不能做到前級進位運算，像是十進位的 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

FA 也可以畫成這樣：

用兩個 HA 也可以實現 FA：

Image Source：Full Adder - GeeksforGeeks

總結

一、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

Logical Expression in SOP and POS Form

Difference between SOP and POS in Digital Logic - GeeksforGeeks

Half Adder · Nand2tetris-Homework

Half Adder - GeeksforGeeks

Full Adder - GeeksforGeeks

加法器 - 維基百科，自由的百科全書

加法器如何工作？ |类型和功能解释 | 台灣 聯想

Full Adder · Nand2tetris-Homework