第十七章数位逻辑简介

1、第十七章 數位邏輯簡介計算機概論編輯小組計算機概論p17-2大綱v布林函數與布林代數v邏輯閘v邏輯簡化v組合電路v記憶裝置計算機概論p17-317.1 布林函數與布林代數v布林函數4一個布林函數 (Boolean function) 是指由下列元素所形成的代數運算式：二元變數、常數、邏輯運算符號、括號以及等號。n(1) 二元變數 (Binary variables) ：通常以英文字母A、B、C、D、W、X、Y、Z來代表。其變數值只可能是0或1。n(2) 常數 (Constants) ：指的是0或1。n(3) 邏輯運算符號：AND、OR、NOT等。n(4) 括號：(、)、等。n(5) 等號：。計

2、算機概論p17-44三種基本運算(1) AND 運算 通常用 “ ” 或 “ * ” 或 “ ” 來表式AND運算。(2) OR 運算 通常用 “ + ” 來表式OR運算。(3) NOT 運算 通常在二元變數上方加上 “，” 或 “”來表式NOT運算。 NOT可將0變成1或1變成0，所以又稱NOT為互補 (Complement) 運算。計算機概論p17-5v真值表4一個布林函數，其所牽涉的二元變數之變數值與相對應之函數值的關係可利用所謂的真值表 (Truth Tables) ；呈現出來。n一個真值表是由n+1欄 (columns) ，及最多2n列 (rows) 所構成。4給定一個真值表，我們亦

3、可推導出相對應的布林函數。計算機概論p17-6計算機概論p17-7v布林代數4布林代數(Boolean Algebra)是作用在布林函數的一種代數運算，布林代數所牽涉到變數皆為二元變數而其使用到的運算符號為前所述之邏輯運算：AND、OR及NOT。A. 恆等式計算機概論p17-8計算機概論p17-9B. 代數運算n靈活運用上述的基本恆等式，我們可做些簡易的代數運算。n範例計算機概論p17-10計算機概論p17-1117.2 邏輯閘v若欲實現AND、OR、NOT，及布林函數，就必需依靠能夠處理二元邏輯運算的數位電路，而這些電路稱之為邏輯閘 (Logic Gates) 。v通常一個邏輯閘具有一個或數

4、個輸入訊號及一個輸出訊號，而這些輸入、輸出訊號皆為二元常數或二元變數。計算機概論p17-12v AND閘4AND閘是具有兩個或兩個以上的輸入及一個輸出的邏輯電路，當所有的輸入訊號皆為1時，輸出訊號才等於1；否則，其輸出訊號為0。4具兩個輸入訊號的AND閘的邏輯符號、布林函數與真值表：計算機概論p17-13v OR閘4OR閘是具有兩個或兩個以上的輸入及一個輸出的邏輯電路，當有任何一個輸入訊號等於1時，其輸出訊號使等於1；只有當所有輸入訊號皆為0時，其輸出訊號才等於0。4具兩個輸入訊號的OR閘的邏輯符號、布林函數與真值表：計算機概論p17-14v NOT閘4NOT閘是具有一個輸入訊號及一個輸出訊號

5、的邏輯電路。4NOT閘的輸出訊號正好與輸入訊號相反，故NOT閘又稱為反相器 (Inverter) 。4具兩個輸入訊號的NOT閘的邏輯符號、布林函數與真值表：計算機概論p17-15v AND、OR與NOT三種邏輯閘的時序圖計算機概論p17-16v NAND 閘4 NAND閘是具有兩個或兩個以上的輸入及一個輸出的邏輯電路，當所有輸入訊號皆為1時，其輸出訊號才等於0；否則，其輸出訊號為1。4顧名思義，NAND的意思是NOT-AND。4具兩個輸入訊號的NAND閘的邏輯符號、布林函數與真值表：計算機概論p17-17v NOR閘4 NOR閘是具有兩個或兩個以上的輸入及一個輸出的邏輯電路，當所有輸入訊號皆為

6、0時，其輸出訊號才等於1；否則，其輸出訊號為0。4顧名思義，NOR的意思是NOT-OR。易言之，將輸入訊號先做OR之後，才做NOT的動作。4具兩個輸入訊號的NOR閘的邏輯符號、布林函數與真值表：計算機概論p17-18v Exclusive-OR 閘 (或簡稱XOR閘) 4 Exclusive-OR (或XOR) 閘是具有兩個或兩個以上的輸入及一個輸出的邏輯電路，當有奇數個輸入訊號為1時其輸出訊號才等於1；否則，其輸出訊號為0。故XOR閘的布林函數稱為奇函數 (odd function) 。4具兩個輸入訊號的XOR閘的邏輯符號、布林函數與真值表：計算機概論p17-194XOR的特性 (1) AB

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

8、ms)v標準形式 (Standard Forms)A. 積項之和(Sum of Product Terms)B. 和項之積(Product of Sum Terms)。在標準形式中看不到括號，只有AND，OR及NOT三種運算能存在布林函數中。計算機概論p17-22A. 積項之和 (Sum of Product Terms)v積項(Product Terms)：利用AND將二元變數串起來所成的一個單位。例如前述的AB，CD，CE皆是積項。v最小項(Minterms)：它是一個特別的積項，在這積項中所有的二元變數皆要出現一次，其出現之方式為二元變數本身或其補數方式。例如ABCD，ABCD 等皆是最

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

10、項。4若一個布林函數含有n個二元變數，則我們可找出 2n 個不同的最大項。計算機概論p17-264以圖表示最大項的意義n任何一個布林函數皆可表成最大項之積(Product of Maxterms)計算機概論p17-27計算機概論p17-2817.3.2 利用卡諾圖做邏輯簡化v邏輯簡化 (Logic Minimization) 的目的在降低硬體成本，回想任何布林函數皆可表示成標準形式，在此為易於了解起見，將以積項之和為例來討論邏輯簡化。v給定一個布林函數將其表成積項之和的標準形式後，所謂邏輯簡化乃是要達成下列兩項目的：4減少積項的個數，則可減少AND閘的個數，同時減少OR閘的fan-in數目。4

11、減少每個積項中變數的個數，則可減少AND閘的fan-in數。其中又比前者重要，因為可直接減少邏輯閘的數目以降低成本。計算機概論p17-29A. 兩個變數的卡諾圖v卡諾圖是一個二維矩陣，其元素的個數正好等於最小項的個數，經過適當的安排，每個最小項正好有一個位置可放。v2個變數的情況，會有4個最小項，故卡諾圖會有4個元素 (位置)4縱軸表示X，橫軸表示Y，X與Y分別可以是0或1。4四個最小項分別為 XY (m0) ， XY (m1) ，XY (m2) 及XY (m3) ，將X、Y的值與最小項相對應，我們便找最小項的位置計算機概論p17-30計算機概論p17-31B. 三個變數的卡諾圖v三個變數可有

12、8個不同的最小項，故其卡諾圖含有8個位置，每個位置對應一個最小項。v卡諾圖計算機概論p17-32C. 四個變數的卡諾圖v四個變數可有16個不同的最小項，故其卡諾圖含有16個位置，每個位置對應一個最小項。v卡諾圖計算機概論p17-33D. 無所謂的情況 (Dont care condition)v無所謂的情況4有些布林函數對於某些特定的輸入值，並不在乎其函數輸出值為0或1，換句話說，其函數值到底是0還是1，均無所謂。4這些無所謂的輸入組合皆可展開成最小項的形式，我們特別將其在卡諾圖所對應的位置，記成“X”，即該位置的值可以為1也可以為0。4我們將無所謂的輸入組合表示成一個 dont care 函

13、數，例如D(W,X,Y,Z)= ，表示最小項m10，m11，m14，m15為無所謂情況其值可為0或1。m(,)10111415計算機概論p17-34計算機概論p17-3517.3.3 和項之積的簡化v注意事項(1) 先簡化F ，並以積項之和方式表達 ，所謂 F，指的是F的卡諾圖中“0”的部分，要合併之。(2) 將(1)所得到的積項之和取補數 ( F)=F。如此，得到一個簡化的和項之積的F函數。計算機概論p17-36計算機概論p17-3717.4 組合電路v組合電路 (Combinational Circuits) 是由許多邏輯閘所組成，它的輸出值直接由輸入訊號決定，通常可用布林函數來表示組合電

14、路。v方塊圖4包含n個輸入變數，方框中的邏輯閘及m個輸出變數。4其實每個輸出變數就代表一個布林函數。4這種輸入與輸出的關係，我們可用真值表完全描述出來。計算機概論p17-38v常用的組合電路4半加器、全加器、n位元並加器、加減法器、解碼器、及多工器。計算機概論p17-39A. 加法器v半加器 (Half-Adder)4半加器可將兩個一位元 (1-bit) 的二進值 (Binary digits) 相加，得到和 (sum) 及進位 (carry) 。4考慮下列4種情況：n0+0=0 ，進位及和皆為0n0+1=1 ，進位為0，和為1n1+0=1 ，進位為0，和為1n1+1=10 ，其中1是進位，0

15、是和。計算機概論p17-404假設這二個數分別以X及Y (X，Y都二元變數) ，根據上述4種情況，寫出其真值表如下，輸出變數S代表和，C代表進位：4布林函數C及S計算機概論p17-414半加器的電路圖v全加器 (Full-Adders)4將三個一位元的二進值 (binary digits) 相加，其結果最小是十進位的0，最大相當於十進位的3，3用二進位來表示就是(11)2，因此解釋為和及進位都等於1， XYCS計算機概論p17-424全加器的真值表4布林函數C及S 計算機概論p17-434全加器的電路圖n一個全加法是由兩個半加器及一個OR閘所組合而成 所以我們可利用半加器來組成一個全加器 H.

16、A. 表示半加器 XYCSZH.AH.AXYZCS計算機概論p17-44B. 解碼器(Decoders) v解碼器是一種將n個輸入的二進位碼轉換成最多有2n條輸出的組合電路。v當一個n位元的二進碼輸入解碼器，則只有唯一的一條輸出線其訊號為“1”，其它的皆為0。計算機概論p17-45計算機概論p17-46計算機概論p17-47C. 多工器 (Multiplexers) v多工器是根據選擇訊號線的指示，讓眾多輸入訊號中的其中一條跑到輸出端的一個組合電路。 v多工器永遠只有一條輸出訊號線，若它有2n條輸入訊號線，則需要有n條選擇線，以決定讓那個輸入訊號跑到輸出端，通常簡記作2n-to-1條線的多工器

17、，或2n*1多工器 (MUX) 。 計算機概論p17-48S0S1D0D1D2D3Y計算機概論p17-4917.5 記憶裝置v可程式邏輯陣列 (PLA) 4一個PLA是由一組輸入變數及其相對應的補數 (例X及) 所形成的兩階段邏輯電路。n第一階段是由AND閘所組成的陣列，可產生所需的積項。n第二階段是由OR閘所組成的陣列，可依需要將特定的積項OR起來，以產生某特定輸出 (或布林函數) 。圖1.2計算機概論p17-504PAL方塊圖v唯讀記憶體 (ROM) 4唯讀記憶體 (Read Only Memory) 也是一種結構化的邏輯電路可利用實現或製作一堆邏輯函數。4功能和PLA類似，但卻以記憶體稱

18、之乃因ROM具有位址功能 (Location) 來幫助讀取存在其中的內容。 4通常存於ROM的內容，在ROM製作時就已固定，無法改變。若欲改變其內容，則需另一種可程式的ROM，稱為PROM。計算機概論p17-514PROM買來時內容是空的，使用者可利用PROM程式器，將特定內容燒進去。一但將內容燒進去後，PROM的內容就無法改變。若想改變其內容，則要利用另一種可插拭的PROM，稱為EPROM。4一個唯讀記憶體，不論是ROM、PROM、EPROM、或EEPROM，皆由一組位址輸入線及一組輸出線所構成。4ROM可有多少個不同的位置取決於輸入位址線的項目，若有n條輸入線，則ROM包函2n不同的位置；至於每個位置可放多少位元的資料，則取決於輸出線的項目，若輸出線有m條，則表示每個位置可放m-bit的資料。4PLA及ROM皆為組合電路，任何燒在其中的內容不因電源中段兒消失，故其具有非揮發性 (non-volatile) ，能確保資料不流失。計算機概論p17-52v暫存器4暫存器是由循序電路所組成的儲存裝置，它由一組記憶元件 (memory element) 所構成，每個記憶元件可儲存一個位元 (bit) 。4一個n位元的暫存器具有n個記憶元件，並可儲存任何n位元的二進資訊。通常用於暫存器的記憶元件為正反器 (Flip-Flops)