第 6 章 數位邏輯

學習目標 看完本章, 您應該學會以下主題： 布林代數、布林函數和真值表 AND、OR 和 NOT 等 3 種邏輯運算 布林代數的基本定理 常見的邏輯閘

前言 數位邏輯 (Digital Logic) 泛指在分析或設計數位電路時, 所應瞭解的理論與運算, 而這些理論與運算是以布林代數為數學基礎, 並涉及布林函數、真值表和邏輯閘等等, 本章將依序介紹這些主題與相關的概念。

6-1 布林代數 在 1854 年英國數學家喬治•布耳 (George Boole) 發表關於邏輯運算的代數理論, 世人為了紀念他的卓越貢獻, 便將這門代數學稱為布林代數 (Boolean Algebra)。而布林函數則是布林代數的核心, 因此我們首先來認識布林函數。

6-1-1 布林函數的定義 凡是由以下元素所組成的代數運算式, 即稱為布林函數 (Boolean Function) ： 二元變數 (Binary Variable)：『二元』意味著此種變數只有 0 或 1 兩種值, 不允許為其它值。通常用 W、X、Y、Z 或 A、B、C、D 代表二元變數。 二元常數 (Binary Constant)：代表固定不變的數字, 同樣也只能是 0 或 1。

6-1-1 布林函數的定義 括弧和等號：包括 (、)、〔、〕、｛、｝和 ＝ 等符號。 邏輯運算符號 (Logical Operator)：最基本的邏輯運算為 AND、OR 和 NOT 等 3 種, 所有的邏輯運算都可以用這 3 種來表示, 詳細的說明請見後文。 典型的布林函數表示方式如下：

6-1-1 布林函數的定義 等號左邊的 F(X,Y) 意味著『布林函數 F 的值與 X、Y 兩個變數有關係』, 至於到底是什麼關係呢？看看等號的右邊就知道了：『X + Y』, 其中『+』是運算符號 (Operator), 又稱為運算子；參與運算的 X 和 Y 則稱為運算元 (Operand) 。

6-1-1 布林函數的定義 至於括弧的使用時機, 則是為了指明運算的優先順序, 舉例而言： 代表先執行括弧內的運算 X + Y, 所得的結果再和 Z 運算。如果去除括弧, 成為：

6-1-1 布林函數的定義 那麼意思就不同了！變成是先執行 Y 和 Z 的運算, 所得的結果再與 X 運算。關於比較詳細的運算說明請見後文。

6-1-2 邏輯運算符號 在組成布林函數的元素中, 『二元變數』、『常數』、『括弧』和『等號』都很容易理解, 唯有第 4 項的『邏輯運算符號』對讀者而言可能是初次接觸, 因此我們要特別說明。基本的邏輯運算符號區分為以下 3 種：

6-1-2 邏輯運算符號 AND AND 運算的特性是『所有運算元都為 1 時, 結果才會是 1, 否則結果一律是0』。通常以實心原點『•』代表 AND 運算符號, 假設 X 和 Y 經過 AND 運算的結果等於 Z, 則記為：

6-1-2 邏輯運算符號 讀作『Z 等於 X AND Y』, 不過大多數人會省略『•』, 直接記為『Z = XY』。只有在 X = Y = 1 時, Z 才是 1；在其它情形, Z 都是 0。若以布林函數來表示 Z = X•Y, 則記為：

6-1-2 邏輯運算符號 以生活實例來比喻, AND 運算就像是串聯兩個開關的電燈系統, 如下圖： 只有在兩個開關都接通 (On) 時, 燈泡才會亮；假如有任一個開關沒接通, 燈泡就不會亮。

6-1-2 邏輯運算符號 OR OR 運算特性是『只要任一個運算元為 1 時, 結果就會是 1, 所有運算元皆為 0 時, 結果才會是 0』。通常以加號『＋』代表 OR 運算符號, 假設 X 和 Y經過 OR 運算的結果等於 Z, 則記為：

6-1-2 邏輯運算符號 讀作『Z 等於 X OR Y』, 在 X 或 Y 其中任一個為 1 時, Z 就等於 1；若 X =Y = 0, 則 Z 便是 0。以布林函數來表示 Z = X + Y, 則記為： 以生活實例來比喻, OR 就像是並聯兩個開關的電燈系統, 如下圖：

6-1-2 邏輯運算符號 只要兩個開關之中的任一個為接通 (On) , 燈泡就會點亮；除非兩個開關都沒接通, 燈泡才不會點亮。

6-1-2 邏輯運算符號 NOT NOT 運算的特性是『若原本是 1, 則運算後為 0；若原本是 0, 則運算後為 1』, 簡單說就是把 0 變 1、1 變 0。通常以加上『′』或『—』代表 NOT 運算, 假設 X 經由 NOT 運算後的結果等於 Y, 則記為：

6-1-2 邏輯運算符號 讀作『Y 等於 NOT X』。若以布林函數來表示, 則記為：

邏輯運算的特色 大家在小學時都學過加、減、乘、除四則運算, 現在遇到了邏輯運算, 是否發現這兩者間的差異呢？ 邏輯運算所處理的對象不是 0 就是 1 , 不可能冒出其它整數或是諸如 2.5、9.8 的小數。而且這種 0 與 1 應該說是『邏輯 0』和『邏輯 1』, 它們代表兩種狀態 (State) , 而不是數量, 不應被當成阿拉伯數字的 0 與 1, 拿來比較大小或做四則運算。

邏輯運算的特色 因此, 在邏輯運算的世界裡, 沒有所謂的『0 小於 1』、『1 大於 0』或『1 加 1 等於 2』這種觀念。 雖然在前面介紹的 AND 和 OR 運算中出現『F(X,Y) = X + Y』、『F(X,Y) = XY』函數, 但是讀者千萬不要視為『數量的關係式』, 因為它們真正代表的是『狀態的關係式』。

6-1-3 真值表 認識了布林函數之後, 接著要來瞭解何謂真值表 (Truth Table) 。若我們將布林函數中每個變數的可能值都列出來, 並記下相對應的函數值, 如此所得的表格便是真值表。舉例而言： 布林函數 F(X,Y) = X＋Y 當 X = 0、Y = 0 時, F(X,Y) = 0； 當 X = 0、Y = 1 時, F(X,Y) = 1； 當 X = 1、Y = 0 時, F(X,Y) = 1； 當 X = 1、Y = 1 時, F(X,Y) = 1。

6-1-3 真值表 將上面 4 列轉換為真值表如下：

6-1-3 真值表 依此類推, 我們就可以寫出布林函數 F(X,Y,Z) = X＋Y＋Z 的真值表如下：

6-1-3 真值表 也就是說, 從布林函數可以推算出真值表；反過來講, 根據真值表也能推導出布林函數。布林函數與真值表其實是一體的兩面！ 對於一個有 N 個變數的布林函數, 可以推算出有 N+1 欄、2n+1 列的真值表, 如下圖：

6-1-3 真值表

0 與 1 在數位電路上所代表的意義 在數位電路中, 通常是以電壓的高低代表 0 與 1 兩種狀態, 高電壓代表 1, 低電壓代表 0, 這種設計稱為『正邏輯』 (Positive Logic) ；然而, 也可以用低電壓代表 1, 高電壓代表 0, 這種設計稱為『負邏輯』 (Negative Logic) 。採用負邏輯設計時必須特別註明, 否則一般人會搞不清楚。

0 與 1 在數位電路上所代表的意義 不同特性的電子元件, 對於高電壓和低電壓有不同的判定標準。以TTL(Transistor Transistor Logic, 電晶體-電晶體-邏輯) 元件為例, 將 2 ~ 5 伏特視為高電壓；0~ 0.8 伏特視為低電壓。至於 0.8 ~ 2 伏特之間則視為不穩定狀態, 又稱為轉態 (Transition) 。 轉態期間的訊號既不為 0、也不為 1, 而是無效訊號。必須等到其電壓進入高電壓範圍或低電壓範圍時, 才當成有效訊號, 而這也是電子元件會造成延遲 (Delay) 的原因之一。

0 與 1 在數位電路上所代表的意義

6-1-4 布林代數的基本定理 在實務應用上, 愈簡單的布林函數, 代表愈簡單的邏輯電路, 也意味著可以用較少的邏輯元件來製造, 如此便能節省成本。 當我們根據真值表推導出來的布林函數, 未必是最簡單的形式, 或許還可以利用一些基本定理來簡化。這些基本定理又被稱為『恆等式』或『公理』, 但是無論用那個名稱, 其內容和觀念都是相同的。

6-1-4 布林代數的基本定理 交換律 (Commutative Law ) 結合律 (Associative Law) X＋Y = Y＋X X•Y = Y•X 結合律 (Associative Law) (X＋Y)＋Z = X＋(Y＋Z) (X•Y)•Z = X•(Y•Z) 分配律 (Distributive Law) X•(Y＋Z) = (X•Y)＋(X•Z) X＋(Y•Z) = (X＋Y)•(X＋Z)

6-1-4 布林代數的基本定理 吸收律 ( Absorption Law) 狄摩根定理 (DeMorgan Theorem ) X＋XY = X X•(X＋Y) = X 狄摩根定理 (DeMorgan Theorem )

6-1-4 布林代數的基本定理 吸收律 ( Absorption Law) 狄摩根定理 (DeMorgan Theorem ) 其它定理 X＋XY = X X•(X＋Y) = X 狄摩根定理 (DeMorgan Theorem ) 其它定理 X ＋X = X X•X = X

6-1-4 布林代數的基本定理 X＋0 = X X•0 = 0 X＋1 = 1 X•1 = X 若要證明上述的定理, 最簡單的就是列出等號兩邊運算式的真值表, 就能看出其相等性。不過, 即使不列出真值表, 仍可利用其它定理來證明某一個定理為真。

6-1-4 布林代數的基本定理 假設我們要證明吸收律 X•(X＋Y) = X 為真, 其方式如下：

『二元運算符號』和『一元運算符號』 AND 和 OR 這兩種運算符號稱為『二元運算符號』 (Binary Operator) , 因為它們都需要有兩個運算元 (Operand) 才能動作, 例如：X＋Y 與 X•Y, 簡而言之, 就是『一個巴掌拍不響, 兩個巴掌才拍得響』。 但是 NOT 就不同了, 它只需要一個運算元即可動作, 例如：X, 因此稱為『一元運算符號』 (Unitary Operator) 。

『二元運算符號』和『一元運算符號』 在沒有任何括弧的布林運算式中, 一元運算符號的優先順序高於二元運算符號, 例如： 應該先算出Y的值, 再和 X 做 OR 運算。

隨堂練習 1.請列出布林函數 F(X,Y,Z) = X•Y＋ 的真值表。 2.請用真值表證明狄摩根定理 。 2.請用真值表證明狄摩根定理 。 3.請化簡布林函數 F(X,Y) = XY＋ 。 4.請證明布林函數 (提示： )

6-2 常見的邏輯閘 所謂的邏輯閘 (Logic Gate) 就是執行邏輯運算的數位電路, 也是數位邏輯的基礎, 如果看不懂邏輯閘, 就等於沒學過數位邏輯。若要將先前推導的布林函數化為具體的元件或產品, 就必須利用邏輯閘將電路圖畫出來。

6-2-1 AND 閘 AND 閘 (AND Gate) 是執行 AND 運算的數位電路。可接受兩個 (含) 以上的輸入, 但是只產生一個輸出, 唯有全部的輸入皆為 1, 輸出才會是 1；否則輸出都是 0。 AND 閘的邏輯符號、布林函數和真值表如下所示：

6-2-1 AND 閘 AND 閘的邏輯符號、布林函數和真值表如下所示：

6-2-2 OR 閘 OR 閘 (OR Gate) 是執行 OR 運算的數位電路。可接受兩個 (含) 以上的輸入, 但是只產生一個輸出, 唯有全部的輸入皆為 0, 輸出才會是 0；否則輸出都是 1。

6-2-2 OR 閘 OR 閘的邏輯符號、布林函數和真值表如下：

6-2-3 NOT 閘 NOT 閘 (NOT Gate) 是執行 NOT 運算的數位電路。只接受一個輸入, 產生一個輸出, 輸入與輸出的邏輯狀態必定相反。若輸入是 1, 則輸出是 0；若輸入是 0, 則輸出是 1 。因為這種特性, NOT 閘也被稱為反相器 (Inverter) 。

6-2-3 NOT 閘 NOT閘的邏輯符號、布林函數和真值表如下所示：

6-2-4 XOR 閘 XOR 閘 (XOR Gate) 是執行 XOR 運算的數位電路, 所謂的 XOR 運算, 以兩個輸入為例, 可以說是『同性相斥』, 當兩個輸入訊號相同時, 輸出便是 0；否則輸出便是 1 。通常用 ⊕ 代表 XOR 運算符號。 XOR 閘可接受兩個 (含) 以上的輸入, 但是只產生一個輸出, 若有奇數個輸入為 1, 輸出才會是 1；否則輸出都是 0。

6-2-4 XOR 閘 XOR 閘的邏輯符號、布林函數和真值表如下 (以兩個輸入為例) ：

6-2-4 XOR 閘 XOR 運算特色是『與同一個二元常數做兩次 XOR 之後, 即恢復原值』。舉例說明如下：

6-2-5 NAND 閘 NAND 閘 (NAND Gate) 是執行 NAND 運算的數位電路, 所謂的 NAND 代表 NOT 運算加上 AND 運算, 也就是先執行 AND 運算, 再將所得的結果做NOT 運算。 由於 AND 閘必須在所有輸入皆為 1, 輸出才為 1, 而 NAND 又將這個輸出再做一次 NOT 運算, 所以我們可以推導出 NAND 閘唯有在所有輸入皆為 1 時, 輸出才為 0；否則輸出一律是 1, 其邏輯符號、布林函數與真值表如下：

6-2-5 NAND 閘

6-2-5 NAND 閘 因為只要利用 NAND 閘, 我們就可以模擬出 AND、OR 和 NOT 三種邏輯閘, 所以 NAND 閘又被稱為萬用邏輯閘 (Universal Gate) , 以下列出其模擬方式：

6-2-5 NAND 閘

6-2-6 NOR 閘 NOR 閘 (NOR Gate) 是執行 NOR 運算的數位電路, 所謂 NOR (NOTOR) 運算, 就是先執行 OR 運算, 再將所得的結果做 NOT 運算。 由於 OR 閘必須在所有輸入皆為 0, 輸出才為 0, 而 NOR 又將這個輸出再做一次 NOT 運算, 所以我們可以推導出 NOR 閘唯有在所有輸入皆為 0 時, 輸出才為 1；否則輸出一律是 0, 其邏輯符號、布林函數與真值表如下：

6-2-6 NOR 閘

6-2-6 NOR 閘 如同 NAND 閘, 我們用 NOR 閘就可以模擬出 AND、OR 和 NOT 三種邏輯閘, 所以 NOR 閘也被視為萬用邏輯閘, 以下列出其模擬方式：

6-2-6 NOR 閘

隨堂練習 1.請寫出 AND 閘的邏輯符號、布林函數和真值表。 2.請寫出 XOR 閘的邏輯符號、布林函數和真值表。 3.請寫出 NOR 閘的邏輯符號、布林函數和真值表。 4.請寫出 NAND 閘的邏輯符號、布林函數和真值表。

特別企劃－IC 設計流程與方法 IC 設計流程 第 1 章介紹電腦的演進, 提到第 3 代電腦 (1964〜1970) 是積體電路 (以下簡稱 IC, Integrated Circuit) 電腦, 所謂的積體電路就是將多個電子_"_響踆#_閔元件及其電路, 製作在微小的晶片上。套用本章所學的邏輯閘觀念, 第 1 章介紹過的 VLSI (超大型積體電路, Very Large-Scale Integration), 其內的邏輯閘數量都在十萬以上。

特別企劃－IC 設計流程與方法 IC 設計流程 對於中小型的 IC, 邏輯閘數量少, 構成 IC 的元件也不多, 或許還可以用手工的方式, 在紙上畫一畫完成設計, 但對於 CPU、GPU 等各種複雜的 IC, 其內的邏輯閘、元件數量動輒以百萬計, 因此 IC 設計已發展為高度分工, 且有各種輔助工具可使用。台灣的 IC 設計規模約佔全球 20%, 股票上市公司中不乏高知名度的 IC 設計廠商, 例如聯發科技、威盛等等。 58

特別企劃－IC 設計流程與方法 IC 設計流程 59

特別企劃－IC 設計流程與方法 IC 設計流程 60

特別企劃－IC 設計流程與方法 IC 設計流程 在 CPU 產品規格上看到的 45nm、65nm (奈米) 等就是指其製程規格, 例如 45nm 指的是 IC 內部的特徵尺寸 (Feature Size), 也就是內部電路寬度的二分之一, 或是閘的長度。愈小的尺寸代表較先進的製程, 因為如此可在同樣面積的 IC 上放置更多的元件 (功能提昇)、或是在相同尺寸晶圓上切割出更多的 IC (成本降低)。 61

特別企劃－IC 設計 流程與方法 IC 設計流程 邏輯設計：規格定好後, 就可開始設計產品。這個階段主要是利用硬體描述語言 (Hardware description language) 來描述硬體的行為、電路的設計, 硬體描述語言類似於一般的電腦程式語言 (參見第 14 章), 例如目前常見的 Verilog 及 VHDL 分別是由 C 和 Ada 程式語言發展而來的。 62

特別企劃－IC 設計流程與方法 IC 設計流程 63

特別企劃－IC 設計流程與方法 IC 設計流程 電路設計：以硬體描述語言描述的電路設計, 經過檢查並確認符合當初的規格需求, 就可以開始著手畫出實際的電路圖。目前硬體描述語言也具備電路合成功能, 可快速產生所需的電路。 電路模擬：設計好的電路需進一步測試、驗證, 如果等 IC 生產出來才發現問題將形成重大的損失。 64

特別企劃－IC 設計流程與方法 IC 設計流程 此階段可使用 SPICE (Simulation Program with Integrated Circuit Emphasis) 之類的軟體進行模擬, 此外，目前硬體描述語言也具備模擬功能, 可幫助檢查設計的功能是否能正常運作。 65

特別企劃－IC 設計流程與方法 IC 設計流程 66

特別企劃－IC 設計流程與方法 IC 設計流程 佈局設計：模擬確認電路的功能, 就需產生實際的電路佈局 (Layout), 準備交給晶圓廠 (例如一般人耳熟能詳的台積電、聯電) 生產。 此時必須依據 IC 的實體規格, 將元件、電路一一安置到適當的位置, 完成的佈局也需再做檢查與確認。 67

特別企劃－IC 設計流程與方法 IC 設計流程 例如 DRC (Design Rule Check) 是檢查電路有無違反晶圓廠提供的硬體參數、LVS (Layout versus schematic) 則是比對佈局是否與之前設計的電路相符、ERC (Electrical Rule Check) 則檢查電路的電氣特性, 例如有無短路的情況等。 68

特別企劃－IC 設計流程與方法 IC 設計流程 通過重重的檢查、模擬與確認後, 需將最後的 IC 佈局輸出成業界標準的 GDS II (Graphic Database System) 檔案格式, 交給廠商製作光罩、生產晶圓、切割成晶粒, 接著進行 IC 的封裝 (將晶粒以塑膠或其它材質包裝起來) 與測試, 最後生產出來的就是 IC 成品。 69

特別企劃－IC 設計流程與方法 IC 設計流程 台灣的封測 (封裝與測試) 產業和晶圓代工一樣, 市佔率都是世界首位, 知名的封測廠商如日月光、矽品等。 70

特別企劃－IC 設計流程與方法 IC 設計方法 一個 IC 是由無到有的全新設計, 將上述的流程全部走完一遍, 稱為 Full-Custom 設計, 此種設計會得到最佳化的產品, 但設計成本也最高。 有的 IC 設計為了簡化設計過程、縮短時間, 會採用 Cell-Based 的設計。Cell 是指已事先設計好的 IC 電路單元 (例如編碼器、RAM 等等), 然後利用類似堆積木的方式, 將所需用到的 Cell 組合起來實現所需的 IC 功能。 71

特別企劃－IC 設計流程與方法 IC 設計方法 此種設計隨可縮短設計時間、降低成本, 但產品效能會較 Full-Custom 設計來得差。 Cell-Based 的設計雖然簡化了一些設計過程, 但加上後續佈局、生產、封裝等製造過程, 從設計到產品上市要好幾個月, 而且對一些產量較少的特定功能 IC (ASIC, Application-Specific IC), 所需成本仍太高。 72

特別企劃－IC 設計流程與方法 IC 設計方法 因而又有一種更快速的設計方式, 稱為 Gate-Array IC 設計, Gate-Array IC 是內部已經做好大量邏輯閘的『半成品』 IC, 設計者依需求, 只要以不同的電路將現有的邏輯閘連在一起, 就能設計出具備特定功能的 IC。 73

特別企劃－IC 設計流程與方法 IC 設計方法 74

特別企劃－IC 設計流程與方法 IC 設計方法 另一種在既有 IC 上進行設計的方式稱為 PLD (Programmable Logical Device, 可程式化邏輯元件) IC 設計。不過『可程式化』IC 並不像 Gate-Array 是半成品, 而是已經完成的 IC 商品, 但其內部也是包含大量邏輯閘、Macrocell (已完成特定功能的邏輯單元。 75

特別企劃－IC 設計流程與方法 IC 設計方法 例如算術邏輯單元 ALU、暫存器) 等, 且可由客戶依需要規劃其內部元件的電路繞線, 所以只要做不同的規劃, 就能實現不同功能的 IC 成品 (所以稱為『可程式化』)。 76

特別企劃－IC 設計流程與方法 IC 設計方法 77