第三章 布林代數及數位邏輯

第三章 教學目的 了解布林邏輯和數位計算機電路的關係. 學習如何設計簡單的邏輯電路. 了解數位電路如何協同運作形成複雜的電腦系統.

3.1 簡介 在19世紀後期,, George Boole 提出人類的思考可以透過數學式子來表達, 這激怒了當時的哲學家和數學家. 誰膽敢說人類的思維能用布林方程式來表示及操作? 電腦, 如我們今日所知, 就是用布林的思考定律所製造出來的. John Atanasoff 和 Claude Shannon 是第一個發現這個關聯的.

3.1 簡介 在20世紀的中期, 電腦被稱為 “思考機器” 以及 “電子大腦” 很多人都很怕電腦. 現在, 我們很少會去想電子數位電腦和人類邏輯之間的關係. 電腦已經自然的成為我們生活的一部份了. 然而還是有很多人很怕它們. 在這一章中, 你將學習到構成電腦的簡單基本要件.

3.2 布林代數 布林代數是一種用來處理只有二個值的數學系統. 布林表示式可用布林變數的運算式來表示. 在正規邏輯來說, 這二個值為 “true” 和 “false.” 在數位邏輯來說, 這個值是 “on” 和 “off,” 1 和 0, 或說 “high” 和 “low.” 布林表示式可用布林變數的運算式來表示. 一般的布林運算包含AND, OR, 和 NOT.

3.2 布林代數 布林運算子可以用真值表來描術. 布林運算子AND 和 OR的真值表如右所示. AND 又稱為布林積. OR 又稱為布林和.

NOT 通常以在變數上加一橫槓來表示. 有時是在右上角用一丿 ( ‘ ) 或是在前面加上. 3.2 布林代數 布林NOT的真值表如右所示. NOT 通常以在變數上加一橫槓來表示. 有時是在右上角用一丿 ( ‘ ) 或是在前面加上.

3.2 布林代數 布林函數包括了: 產生的值也是 {0,1}. 至少一個布林變數, 至少一個布林運算子, 以及 至少一個0或1的輸入. 現在可以了解為什麼二元數字系統在數位系統會這麼方便了.

3.2 布林代數 下面布林函數的真值表如右所示: 為了更容易來求出此布林函數的值, 我們在真值表中多加了幾行, 用來記錄函數的部份值.

3.2 布林代數 在一般的算術運算中, 布林運算有些先後順序性. NOT 最優先, 再來是 AND, 接著是 OR. 這就是我們為何要在表中加入多餘的部份.

3.2 布林代數 數位電腦包含了實現布林函數的電路. 布林含數越簡單, 所產生的電路就越小. 越簡單的電路做起來就越便宜, 功率消耗也小, 速度也快. 因為這樣, 我們會試著將布林函數化成最簡的形式. 有一些布林特性能幫我們完成這樣的工作.

3.2 布林代數 大多數的布林性質有AND (product) 和 OR (sum) 的形式. 我們會同時列出. 第一個要介紹的很直覺的特性:

3.2 布林代數 第二組特性是在代數中非常易見的:

3.2 布林代數 最後一組要介紹的最有用. 如果你學過集合理論或正規邏輯, 你對這些定律一定不會陌生.

3.2 布林代數 我們可以利用介紹過的布林性質來簡化下列函數:

有時候, 用函數的補數來製作電路會比直接製作來得經濟 (結果的相反值). 3.2 布林代數 有時候, 用函數的補數來製作電路會比直接製作來得經濟 (結果的相反值). DeMorgan’s 定律可以很容易的找出布林函數的補數. DeMorgan’s 定律告訴我們:

3.2 布林代數 的補數為: DeMorgan’s 定律可以擴充為很多變數. 將每個變數取補數, 然後將AND改成OR, 將OR換成AND. 所以, 函數的補數為: 的補數為:

3.2 布林代數 透過我們簡化布林表示式的練習可知, 同一個布林函數會有很多不同的表示法. 這些 “同義” 的形式都是邏輯等效 (logically equivalent). 邏輯等效就是有相同的真值表. 為了避免這種情況, 設計人員會用標準的型式來表示布林函數.

3.2 布林代數 布林函數有二種標準型式: 積之和 (sum-of-products)以及和之積 (product-of-sums). 布林積就是 AND運算, 布林和就是 OR 運算. 在積之和型式中, 互相AND的變數, 最後用 OR串起來. 例如: 在和之積型式中, 互相OR的變數, 最後用AND串起來: For example:

3.2 布林代數 利用真值表, 我們可以很容易的把函數化成積之和. 我們只看表中會產生1的部份. 利用真值表, 我們將會產生1的結果列出. 每一個部份再用OR串起來.

3.2 布林代數 函數的積之和型式為: 我們看到這並不是最簡的型式. 我們的目的只是要寫成一個標準的型式.

3.3 邏輯閘 我們剛介紹了布林函數的抽象術語. 這一節我們來看看當布林函數在數位電腦電路中時, 是以閘的型式存在. 閘是一個電子裝置, 它的輸出結果是視其輸入而定的. 事實上, 閘是由1或6個電晶體所組成, 但是數位設計人員把它視為是單一裝置. 積體電路內包含了很多閘, 其用來達成某種目的.

3.3 邏輯閘 三種最簡單的閘AND, OR, 和 NOT. 它們直接對應到相對的布林函數, 可由真值表得知.

3.3 邏輯閘 另一種常用的閘是互斥OR (XOR)閘. 當輸入的值不相同時, XOR 的輸出為 true. XOR有特殊的表示符號 .

3.3 邏輯閘 NAND和NOR 是非常重要的閘. 它們的符號和真值表如右所示.

3.3 邏輯閘 NAND和NOR 被稱為通用閘 (universal gates) 因為它們製造成本低, 而且我們可以只用NAND或NOR閘來構成所有的布林函數.

3.3 邏輯閘 閘可以擁有多個輸入及超過一個的輸出. 第二個輸出可以是補數. 我們等一下會介紹的更清楚.

3.4 數位元件 最主要的是, 我們可以透過將閘組合在一起來構成布林函數. 下面的電路就是布林函數 的實體: 下面的電路就是布林函數 的實體: 我們將布林表示式簡化, 所以我們的電路變得較為簡單.

當我們輸入值時, 組合邏輯會馬上產生相對應的輸出. 3.5 組合電路 我們設計了一個實現下列布林函數的電路: 這是一個組合邏輯電路. 當我們輸入值時, 組合邏輯會馬上產生相對應的輸出. 在後面的小節中, 我們會看到還有別種情況.

3.5 組合電路 組合邏輯電路有很多有用的裝置. 這之中最簡單的就是半加器( half adder), 它求出二個位元的和. 我們可以仔細檢查半加器的真值表(如右), 來獲取設計半加器的靈感.

3.5 組合電路 如我們所見, 和可以透過XOR產生, 進位則可以用AND求得.

我們可以將半加器改成全加器, 這只要多加一個進位處理的位元即可. 3.5 組合電路 我們可以將半加器改成全加器, 這只要多加一個進位處理的位元即可. 全加器的真值表如右所示.

3.5 組合電路 我們如何將下面的半加器變成全加器呢?

3.5 組合電路 下圖就是一個全加器.

3.5 組合電路 就像我們用半加器組成一個全加器一般,我們也可以將全加器串接起來. 進位位元會從一個加法器波動傳遞到下一個加法器; 因此, 這種組態就稱為漣波進位加法器. 今日系統都用比較有效率的加法器了.

一個有n 個輸入的記位址解碼器可以選擇2n 位置的其中一個. 3.5 組合電路 解碼器是另一個重要的組合電路. 它們通常用來選擇記憶體位置. 一個有n 個輸入的記位址解碼器可以選擇2n 位置的其中一個. 這是解碼器的方塊圖.

3.5 組合電路 這是一個 2-to-4 解碼器的內部. 如果 x = 0 且 y = 1, 那一條輸出線會被致能呢?

3.5 組合電路 多工器做的事和解碼器恰恰相反. 多工器會從數個輸入中選一個來輸出. 它是藉由多工器的控制線來選擇的. 如果有n 個輸入的話, 那就要有 log2n 的控制線. 這是多工器的方塊圖.

3.5 組合電路 這是一個 4-to-1 多工器的內部. 如果 S0 = 1 且 S1 = 0, 那一個輸入會被傳到輸出呢?

當我們接受一組輸入要馬上得到其布林函數的輸出時, 組合邏輯是不錯的選擇. 3.6 循序電路 當我們接受一組輸入要馬上得到其布林函數的輸出時, 組合邏輯是不錯的選擇. 但是有時候, 我們的輸出會需要考慮到目前的狀態和輸入. 這種電路需要 “記住”目前的狀態. 循序邏輯電路就是這樣的電路.

3.6 循序電路 就像它的名稱一樣, 循序邏輯電路需要某些事件點的發生來排序. 狀態的改變是經由時脈來控制. 時脈會產生如下的電波. “時脈” 是一個特殊的電路, 它透過一個電路來傳送電脈衝信號. 時脈會產生如下的電波.

只有在時脈變動(clock ticks)發生時, 循序電路中的狀態才會改變. 3.6 循序電路 只有在時脈變動(clock ticks)發生時, 循序電路中的狀態才會改變. 狀態改變可以發生在上昇邊緣, 下降邊緣或是時脈到達它最高電壓時.

3.6 循序電路 狀態在上昇邊緣或下降邊緣改變的電路稱為邊緣觸發(edge-triggered). 位階觸發電路(Level-triggered circuits) 會在時脈電壓到達最高或最低時才改變狀態.

3.6 循序電路 循序電路靠回授(feedback)來保留狀態值. 在數位電路中, 回授是透過將輸出接回輸入來達成. 以下是一個最簡單的例子. 如果 Q 是 0, 那電路就會是0, 如果是 1, 就會是 1. 為什麼?

你可以藉由觀察SR正反器來了解回授的意義. 3.6 循序電路 你可以藉由觀察SR正反器來了解回授的意義. “SR” 表示 set/reset. SR正反器的內部入下圖所示, 右邊是其方塊圖.

3.6 循序電路 SR正反器的行為可以用特徵表來描述. Q(t) 表是時間 t 時的輸出值. Q(t+1) 則是下一個時脈過後Q的值.

3.6 循序電路 事實上, SR 正反器有三個輸入 : S, R, 和它目前的輸出Q. 因此, 其真值表如右所示.

3.6 循序電路 如果我們能保證SR正反器的輸入不會同時為1, 那我們就不會有不穩定的現像出現. 但這是不一定的. • 修改過的正反器稱為 JK 正反器, 方塊圖如右. - “JK” 是為紀念發明人 Jack Kilby.

3.6 循序電路 右邊可看出SR 正反器是怎麼變成, JK正反器的. 右邊的特徵表可看出所有的輸入狀態都是穩定的.

另一個SR 正反器的變形是D型正反器, 方塊圖和特徵表入下所示. 3.6 循序電路 另一個SR 正反器的變形是D型正反器, 方塊圖和特徵表入下所示. 你可能注意到D型正反器的輸出在時脈改變時會維持一樣. 只有當D值改變時輸出才會跟著改變.

3.6 循序電路 D型正反器是電腦記憶體的最基本元件. 下一張投影片我們會介紹要如何將這些電路兜成暫存器.

3.6 循序電路 右邊是一個 4-bit的暫存器. 它是由 D 型正反器所構成. 通常會用下方這個方塊圖來表示. 書中有比較大的記憶體範例可供參考.

3.6 循序電路 另一個循序電路的範例是二進制計數器. 低位元會在每次時脈改變時轉態. 每次從 0 變 1時, 下一個位元就轉態, 以次類推.

3.7 設計電路 我們以二種觀點來討論數位電路: 數位分析和數位合成. 數位分析是一種探究電路輸入和輸出關係的方法. 數位合成是用真值表的值來產生邏輯圖. 數位系統設計人員必需謹記, 實體電路會有輸入到輸出之間的傳輸延遲, 它包含了輸出達道正確且穩定的所需時間.

3.7 設計電路 數位設計人員仰賴特殊的軟體來產生有效的電路. 當然, 軟體實際上是一群演算法的集合, 它也可以用硬體形式出現. 所以, 軟體是建構優良硬體的驅使者. 當然, 軟體實際上是一群演算法的集合, 它也可以用硬體形式出現. 記得我們介紹軟硬體等效原理.

3.7 設計電路 當我們要製作一個簡單, 特別的演算法, 而且要求它的執行速度越快越好, 那硬體的實作方式會比較適合. 當我們要製作一個簡單, 特別的演算法, 而且要求它的執行速度越快越好, 那硬體的實作方式會比較適合. 這就是嵌入式系統(embedded systems)背後的概念,它是一個小型的特殊用途電腦. 我們到處都可以發現它的蹤跡. 嵌入式系統需要特殊的程式設計, 這需要了解數位電路的動作才行, 你在本章已經學到一些基本的觀念了.

結論 電腦就是布林邏輯的實體. 布林函數可以完全由真值表來表示. 邏輯閘是實現布林運算的小電路. 基本的閘有 AND, OR, 和 NOT. XOR 在同位元檢查和加法器中非常有用. NOR, 和NAND是通用閘

結論 電腦電路是由組合邏輯和循序邏輯所構成. 組合電路會隨著輸入改變而馬上改變輸出. 循序電路需要時脈來控制狀態的改變. 基本的循序電路是正反器: SR, JK, 和 D 型正反器是三種最重要的基本元件.

End of Chapter 3