第十七章 數位邏輯簡介 計算機概論編輯小組

大綱 布林函數與布林代數 邏輯閘 邏輯簡化 組合電路 記憶裝置 計算機概論

17.1 布林函數與布林代數 布林函數 一個布林函數 (Boolean function) 是指由下列元素所形成的代數運算式：二元變數、常數、邏輯運算符號、括號以及等號。 (1) 二元變數 (Binary variables) ：通常以英文字母A、B、C、D、W、X、Y、Z來代表。其變數值只可能是0或1。 (2) 常數 (Constants) ：指的是0或1。 (3) 邏輯運算符號：AND、OR、NOT等。 (4) 括號：(、)、[、]、{、}等。 (5) 等號：＝。 計算機概論

三種基本運算 (1) AND 運算 (2) OR 運算 (3) NOT 運算 NOT可將0變成1或1變成0，所以又稱NOT為互補 (Complement) 運算。 計算機概論

真值表 一個布林函數，其所牽涉的二元變數之變數值與相對應之函數值的關係可利用所謂的真值表 (Truth Tables) ；呈現出來。 一個真值表是由n+1欄 (columns) ，及最多2n列 (rows) 所構成。 給定一個真值表，我們亦可推導出相對應的布林函數。 計算機概論

計算機概論

布林代數 布林代數(Boolean Algebra)是作用在布林函數的一種代數運算，布林代數所牽涉到變數皆為二元變數．而其使用到的運算符號為前所述之邏輯運算：AND、OR及NOT。 A. 恆等式 計算機概論

計算機概論

靈活運用上述的基本恆等式，我們可做些簡易的代數運算。 範例 B. 代數運算 靈活運用上述的基本恆等式，我們可做些簡易的代數運算。 範例 計算機概論

計算機概論

17.2 邏輯閘 若欲實現AND、OR、NOT，及布林函數，就必需依靠「能夠處理二元邏輯運算的數位電路」，而這些電路稱之為邏輯閘 (Logic Gates) 。 通常一個邏輯閘具有一個或數個輸入訊號及一個輸出訊號，而這些輸入、輸出訊號皆為二元常數或二元變數。 計算機概論

AND閘 AND閘是具有兩個或兩個以上的輸入及一個輸出的邏輯電路，當所有的輸入訊號皆為1時，輸出訊號才等於1；否則，其輸出訊號為0。 計算機概論

OR閘 OR閘是具有兩個或兩個以上的輸入及一個輸出的邏輯電路，當有任何一個輸入訊號等於1時，其輸出訊號使等於1；只有當所有輸入訊號皆為0時，其輸出訊號才等於0。 具兩個輸入訊號的OR閘的邏輯符號、布林函數與真值表： 計算機概論

NOT閘 NOT閘是具有一個輸入訊號及一個輸出訊號的邏輯電路。 NOT閘的輸出訊號正好與輸入訊號相反，故NOT閘又稱為反相器 (Inverter) 。 具兩個輸入訊號的NOT閘的邏輯符號、布林函數與真值表： 計算機概論

AND、OR與NOT三種邏輯閘的時序圖 計算機概論

NAND 閘 NAND閘是具有兩個或兩個以上的輸入及一個輸出的邏輯電路，當所有輸入訊號皆為1時，其輸出訊號才等於0；否則，其輸出訊號為1。 顧名思義，NAND的意思是NOT-AND。 具兩個輸入訊號的NAND閘的邏輯符號、布林函數與真值表： 計算機概論

NOR閘 NOR閘是具有兩個或兩個以上的輸入及一個輸出的邏輯電路，當所有輸入訊號皆為0時，其輸出訊號才等於1；否則，其輸出訊號為0。 顧名思義，NOR的意思是NOT-OR。易言之，將輸入訊號先做OR之後，才做NOT的動作。 具兩個輸入訊號的NOR閘的邏輯符號、布林函數與真值表： 計算機概論

Exclusive-OR 閘 (或簡稱XOR閘) Exclusive-OR (或XOR) 閘是具有兩個或兩個以上的輸入及一個輸出的邏輯電路，當有奇數個輸入訊號為1時﹐其輸出訊號才等於1；否則，其輸出訊號為0。故XOR閘的布林函數稱為奇函數 (odd function) 。 具兩個輸入訊號的XOR閘的邏輯符號、布林函數與真值表： 計算機概論

XOR的特性 計算機概論

17.3 邏輯簡化 邏輯簡化乃是透過某些程序 (例如布林代數運算或卡諾圖等) 將布林函數做簡化，使得用來製作該布林函數的邏輯閘數目減少，進而降低成本。 標準形式 (Standard Forms) A. 積項之和(Sum of Product Terms) B. 和項之積(Product of Sum Terms)。在標準形式中看不到括號，只有AND，OR及NOT三種運算能存在布林函數中。 計算機概論

17.3.1 標準形式 (Standard Forms) 標準形式 (Standard Forms) A. 積項之和(Sum of Product Terms) B. 和項之積(Product of Sum Terms)。在標準形式中看不到括號，只有AND，OR及NOT三種運算能存在布林函數中。 計算機概論

A. 積項之和 (Sum of Product Terms) 積項(Product Terms)：利用AND將二元變數串起來所成的一個單位。例如前述的AB，CD，CE皆是積項。 最小項(Minterms)：它是一個特別的積項，在這積項中所有的二元變數皆要出現一次，其出現之方式為二元變數本身或其補數方式。例如ABCD，ABCD 等皆是最小項。 若一個布林函數含有n個二元變數，則我們可以找出2n個不同最小項 計算機概論

任何一個布林函數皆可表示成最小項之和(Sum of Minterms) 以圖表示最小項的意義 任何一個布林函數皆可表示成最小項之和(Sum of Minterms) 計算機概論

計算機概論

B. 和項之積(Product of Sum Terms) 和項(Sum Terms)：利用OR將二元變數串起來所成的一個單位。例如A+B，A+C ，A+B+C 等皆是和項。 最大項(Maxterms)：它是一個特別的和項，在這和項中所有的二元變數皆要出現一次，其出現的方式為二元變數本身或以其補數方式。 例如A+B+C+D，A+B +C+D， A+B +C+D皆是最大項。 若一個布林函數含有n個二元變數，則我們可找出 2n 個不同的最大項。 計算機概論

任何一個布林函數皆可表成最大項之積(Product of Maxterms) 以圖表示最大項的意義 任何一個布林函數皆可表成最大項之積(Product of Maxterms) 計算機概論

計算機概論

17.3.2 利用卡諾圖做邏輯簡化 邏輯簡化 (Logic Minimization) 的目的在降低硬體成本，回想任何布林函數皆可表示成標準形式，在此為易於了解起見，將以積項之和為例來討論邏輯簡化。 給定一個布林函數將其表成積項之和的標準形式後，所謂邏輯簡化乃是要達成下列兩項目的： 減少積項的個數，則可減少AND閘的個數，同時減少OR閘的fan-in數目。 減少每個積項中變數的個數，則可減少AND閘的fan-in數。其中又比前者重要，因為可直接減少邏輯閘的數目以降低成本。 計算機概論

A. 兩個變數的卡諾圖 卡諾圖是一個二維矩陣，其元素的個數正好等於最小項的個數，經過適當的安排，每個最小項正好有一個位置可放。 2個變數的情況，會有4個最小項，故卡諾圖會有4個元素 (位置) 縱軸表示X，橫軸表示Y，X與Y分別可以是0或1。 四個最小項分別為 XY (m0) ， XY (m1) ，XY (m2) 及XY (m3) ，將X、Y的值與最小項相對應，我們便找最小項的位置 計算機概論

計算機概論

B. 三個變數的卡諾圖 三個變數可有8個不同的最小項，故其卡諾圖含有8個位置，每個位置對應一個最小項。 卡諾圖 計算機概論

C. 四個變數的卡諾圖 四個變數可有16個不同的最小項，故其卡諾圖含有16個位置，每個位置對應一個最小項。 卡諾圖 計算機概論

D. 無所謂的情況 (Don¢t care condition) 有些布林函數對於某些特定的輸入值，並不在乎其函數輸出值為0或1，換句話說，其函數值到底是0還是1，均無所謂。 這些無所謂的輸入組合皆可展開成最小項的形式，我們特別將其在卡諾圖所對應的位置，記成“X”，即該位置的值可以為1也可以為0。 我們將無所謂的輸入組合表示成一個 don’t care 函數，例如D(W,X,Y,Z)= ，表示最小項m10，m11，m14，m15為無所謂情況其值可為0或1。 計算機概論

計算機概論

17.3.3 和項之積的簡化 注意事項 (1) 先簡化F ，並以積項之和方式表達 ，所謂 F，指的是F的卡諾圖中“0”的部分，要合併之。 計算機概論

計算機概論

17.4 組合電路 組合電路 (Combinational Circuits) 是由許多邏輯閘所組成，它的輸出值直接由輸入訊號決定，通常可用布林函數來表示組合電路。 方塊圖 包含n個輸入變數，方框中的邏輯閘及m個輸出變數。 其實每個輸出變數就代表一個布林函數。 這種輸入與輸出的關係，我們可用真值表完全描述出來。 計算機概論

常用的組合電路 半加器、全加器、n位元並加器、加減法器、解碼器、及多工器。 計算機概論

A. 加法器 半加器 (Half-Adder) 半加器可將兩個一位元 (1-bit) 的二進值 (Binary digits) 相加，得到和 (sum) 及進位 (carry) 。 考慮下列4種情況： 0+0=0 ，進位及和皆為0 0+1=1 ，進位為0，和為1 1+0=1 ，進位為0，和為1 1+1=10 ，其中1是進位，0是和。 計算機概論

假設這二個數分別以X及Y (X，Y都二元變數) ，根據上述4種情況，寫出其真值表如下，輸出變數S代表和，C代表進位： 布林函數C及S 計算機概論

全加器 (Full-Adders) 半加器的電路圖 將三個一位元的二進值 (binary digits) 相加，其結果最小是十進位的0，最大相當於十進位的3，3用二進位來表示就是(11)2，因此解釋為和及進位都等於1， 計算機概論

全加器的真值表 布林函數C及S 計算機概論

一個全加法是由兩個半加器及一個OR閘所組合而成 全加器的電路圖 一個全加法是由兩個半加器及一個OR閘所組合而成 所以我們可利用半加器來組成一個全加器 H.A. 表示半加器 計算機概論

B. 解碼器(Decoders) 解碼器是一種將n個輸入的二進位碼轉換成最多有2n條輸出的組合電路。 計算機概論

計算機概論

計算機概論

C. 多工器 (Multiplexers) 多工器是根據選擇訊號線的指示，讓眾多輸入訊號中的其中一條跑到輸出端的一個組合電路。 多工器永遠只有一條輸出訊號線，若它有2n條輸入訊號線，則需要有n條選擇線，以決定讓那個輸入訊號跑到輸出端，通常簡記作2n-to-1條線的多工器，或2n*1多工器 (MUX) 。 計算機概論

計算機概論

17.5 記憶裝置 可程式邏輯陣列 (PLA) 一個PLA是由一組輸入變數及其相對應的補數 (例X及) 所形成的兩階段邏輯電路。 17.5 記憶裝置 可程式邏輯陣列 (PLA) 一個PLA是由一組輸入變數及其相對應的補數 (例X及) 所形成的兩階段邏輯電路。 第一階段是由AND閘所組成的陣列，可產生所需的積項。 第二階段是由OR閘所組成的陣列，可依需要將特定的積項OR起來，以產生某特定輸出 (或布林函數) 。 圖1.2 計算機概論

PAL方塊圖 唯讀記憶體 (ROM) 唯讀記憶體 (Read Only Memory) 也是一種結構化的邏輯電路可利用實現或製作一堆邏輯函數。 功能和PLA類似，但卻以記憶體稱之乃因ROM具有位址功能 (Location) 來幫助讀取存在其中的內容。 通常存於ROM的內容，在ROM製作時就已固定，無法改變。若欲改變其內容，則需另一種可程式的ROM，稱為PROM。 計算機概論

一個唯讀記憶體，不論是ROM、PROM、EPROM、或EEPROM，皆由一組位址輸入線及一組輸出線所構成。 PROM買來時內容是空的，使用者可利用PROM程式器，將特定內容燒進去。一但將內容燒進去後，PROM的內容就無法改變。若想改變其內容，則要利用另一種可插拭的PROM，稱為EPROM。 一個唯讀記憶體，不論是ROM、PROM、EPROM、或EEPROM，皆由一組位址輸入線及一組輸出線所構成。 ROM可有多少個不同的位置取決於輸入位址線的項目，若有n條輸入線，則ROM包函2n不同的位置；至於每個位置可放多少位元的資料，則取決於輸出線的項目，若輸出線有m條，則表示每個位置可放m-bit的資料。 PLA及ROM皆為組合電路，任何燒在其中的內容不因電源中段兒消失，故其具有非揮發性 (non-volatile) ，能確保資料不流失。 計算機概論

暫存器 暫存器是由循序電路所組成的儲存裝置，它由一組記憶元件 (memory element) 所構成，每個記憶元件可儲存一個位元 (bit) 。 一個n位元的暫存器具有n個記憶元件，並可儲存任何n位元的二進資訊。通常用於暫存器的記憶元件為正反器 (Flip-Flops) 。透過時間脈衝 (clock pulse) 可適當控制n個正反器，以利n位元資料進入 (load) 暫存器或釋放出來。 我們可將若干個暫存器組成所謂的暫存器組 (register files) 計算機概論

隨機存取記憶體 (RAM) RAM是屬於揮發性 (volatile) 的儲存裝置，通常若電源中斷，則存在其中的內容全部流失。它得特性是允許使用者隨時更改任一位置的內容，故它用來當做電腦的主記憶體 (Main Memory) 。 隨機存取記憶體 (RAM) 可分為靜態的 (SRAM，Static RAM) 及動態的 (DRAM，Dynamic RAM) 兩種。 這兩種主要不同在於所使用的儲存元件不同。 SRAM利用正反器來當作儲存一位元 (1bit) 的元件， DRAM則利用電容器來當作儲存一位元 (1bit) 的元件。 由於正反器所佔面積較電容器大，故通常SRAM較佔空間。但因電容器會漏電，故DRAM需定期重新充電，以免儲存的內容亂掉。 SRAM常用來當做快取記憶體 (Cache) 而 DRAM則充當主記憶體 計算機概論

SRAM與 DRAM在存取速度與單位價格的比較： 各種記憶裝置依其可讀寫性、可擦拭性、揮發性及寫入資料方式的比較： 計算機概論