第十七章數(shù)位邏輯簡介

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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