只使用NAND或NOR Gate實現邏輯函數

作者 : Max Maxfield,EEWeb

這篇文章分為三個部分,解讀某個學生在EDN姐妹媒體EEWeb論壇上所提出的一個問題,這個難題的其核心是:他的老師提出了一個布林方程式,要求他創建相應的真值表,然後再告訴他要進行卡諾圖最簡化;最後要他必須只使用NAND Gate或只使用NOR Gate來實現這個電路…

這篇文章分為三個部分,解讀某個學生在EDN姐妹媒體EEWeb論壇上所提出的一個問題,這個難題的其核心是:他的老師提出了一個布林方程式(Boolean Equation),要求他創建相應的真值表,然後再告訴他要進行卡諾圖(Karnaugh map)最簡化;最後要他必須只使用反及閘(NAND Gate)或只使用反或閘(NOR Gate)來實現這個電路。 因此,一開始要做的就是考慮為什麼首先要提出這種問題。接下來就是更詳細地研究這個學生的特定問題,並將其轉換成最初的AND-OR解決方案。然後,就是考慮將基於AND-OR電路轉換為與NAND-NOR對應電路的一般概念。最後,就是用所學的知識來解決這個學生的最初問題。 為什麼只使用NAND Gate或NOR Gate? 那麼,為什麼老師都會要求他的學生只使用NAND Gate或只使用NOR Gate來實現布林方程式?(請注意,我特地不說「只使用NAND或NOR Gate」,因為這有可能被理解成可以使用NAND和NOR Gate,而不使用AND和OR Gate。) 儘管學生可能對此感到驚訝,但不一定就說明老師是個不成功的人,他生活中唯一的樂趣就是去折磨學生。話雖這麼說,但回想起我自己還是一名學生的日子,最好不要實際排除這種可能的動機。 我不由自主地想到老師給學生出這個作業可能有以下原因: 1.提出一個用AND或OR Gate (以乘積的和或和的乘積形式)描述的電路,然後要求學生將其轉換成只使用NAND Gate、只使用NOR Gate,或者使用NAND Gate和NOR Gate組合的另一種表現形式,是確保讓學生瞭解各種邏輯閘如何工作的好方法,它還有助於確保讓學生瞭解DeMorgan轉換之類的內容。 2.如果你想使用簡單的邏輯元件——例如包含六個NOT Gate或四個2輸入AND、OR、NAND或NOR Gate的雙列直插(DIL)封裝積體電路(IC)——來設計印刷電路板(PCB),而你可能正好沒有AND Gate之類的東西,但是碰巧有一個NAND Gate和一個NOT Gate備用(或者可能是一個OR和三個NOT Gate),那麼在這種情況下,你對邏輯閘的理解就可能節省一天的時間。 3.最簡單的邏輯閘是NOT。假設我們在討論CMOS電路,那麼一個NOT Gate需要兩個電晶體。NAND和NOR Gate會複雜一些,其每種包含四個電晶體。然後是AND和ORGate,這兩種邏輯閘每種包含六個電晶體。也就是說,如果使用NAND或NOR Gate代替AND或OR Gate,那麼所使用的電晶體數量可以減少三分之一。 4.關於上一點,AND Gate實際上是由一個NAND Gate後接一個NOT Gate構成(同樣,ORGate是由一個NORGate後接一個NOTGate所組成)。除了使用4 + 2 = 6個電晶體外,這還說明AND Gate (和OR Gate)具有兩級延遲。因此,如果可以使用NAND Gate取代AND Gate (或用NOR Gate取代OR Gate),所得到的電路會運作得更快。 5.順便稍微說一句,本文所討論的所有內容在我的書《Bebop to the Boolean Boogie》中都有詳細描述。 實際上,現在已很少有人在閘級(gate-level)進行設計。取而代之的是以較高的抽象層級攻克設計,然後使用邏輯綜合引擎產生相對應的閘級等效設計,這也說明上述第2點到第4點不再像以前那樣重要。 你可以爭辯說,第1點也是如此,但我不太同意。我的想法是,它類似於使用計算器進行運算的概念。如果你有一個計算器,那你實際上就不需要知道如何對整數、實數和浮點數進行加減乘除運算,但是,如果你掌握了這類知識,那麼當你計算器的電池沒電時,它就可以派上用場。同樣,儘管你可能不需要每天處理布林結構,但是在需要時知道如何處理就會非常方便。 思考問題 所以,以下是那位學生提供給我的資料。他首先說,老師向班級展示了以下方程式: 那位學生還告訴我,他已經使用這個方程式產生了圖1所示的真值表,但是從這時起,他遇到麻煩因而無法往下進行了。 圖1 學生創建的真值表。 好吧,我不得不告訴他,我對他遇到的問題一點都不感到驚訝,因為在他的方程式裡有六個乘積,每個乘積在他的真值表的輸出列中都應該有一個對應的1,但是實際上,他的真值表的輸出列中只有五個1。 我對這個情況進行了反覆思考,並認為潛在的問題是他缺乏對基本原理的理解。還有一點是,如果有一個學生感到困惑,那麼就很可能不止他一個人。最後但同樣重要的是,我記得剛開始時有點困惑不解,所以我會花一點時間逐步解決這個問題(如果你感到無聊,請隨時跳過;或者,你也可以隨時試著發現我可能導入任何故意的錯誤,以便瞭解你是否有集中精力)。 我要做的第一件事就是在方程式中對乘積進行編號,以便可以對我們所處的位置和所做的事進行追蹤(若我們是來真的,那麼就不必費心對乘積進行編號): 下一步是創建真值表。可以從以標準二進位計數表示的所有輸入組合開始,如圖2中的(a)所示;然後將與六個乘積相對應的六個1加起來,如(b)到(g)所示;最後把任何剩餘的輸出「空位」都填入0,如(h)所示。 圖2 創建真值表的過程。 這裡要注意的重點是,將方程式轉換為真值表確實一點也不困難。話雖如此,但無論誰這樣做,都必須瞭解這個過程背後的基本邏輯。再看一下這個方程式,其本質可以這樣來表達:「如果第一個乘積(第一個AND函數)為真,則輸出為真(邏輯1),或者如果第二乘積為真,則輸出為真,或者如果第三乘積為真……」。這就是為什麼可以在與每個乘積相對應的輸出列中簡單地填寫1——如果這些乘積中的任何一項為真,則輸出為真(1),否則輸出為假(0)。 下一步是創建卡諾圖。首先是創建網格本身。由於總共有三個輸入,因此可以使用兩種方法(選項)來做這一步,如圖3所示。 圖3 創建卡諾圖的兩種方法。 選擇使用哪種方案都沒有關係。這兩種情況下答案都是相同的(如果不是,那就確實有問題)。這裡本文使用方案1,這種方法我比較喜歡,如果有任何學生正在閱讀本文,我建議你在這步驟完成後從此處開始,自己使用卡諾圖方案2進行重做,以便確保你真正瞭解這個過程。 查看卡諾圖方案1,觀察「AB」所處的位置。右側是與AB輸入相關的0和1的四種組合:「00」、「01」、「11」和「10」。請務必注意,這四種組合是以格雷碼(Gray code)形式進行排列,這樣就可以讓我們從一個值移到相鄰值時,只會有單個位元發生變化(圖4)。這是卡諾圖運作的關鍵。 圖4 二進位碼與格雷碼對比。 在二進位碼中,當從01過渡到10時,會有兩個位元發生變化。相比之下,如果查看格雷碼(01至11)中的相應轉換,則只有單個位元發生變化。 此外,請注意二進位碼的最後一行。如果要從這一行轉而過渡到第一行(11到00),那麼就會再次有兩位元發生變化。但是,如果查看格雷碼中的相應行(10到00),則會再次看到只有一位元發生變化。 好了,現在來填充卡諾圖。這一步是向方程式中的乘積所對應的每個方框中填入1。這裡再次依照圖5所示的步驟逐步填寫(圓圈中的小數字1到6與初始方程式中的乘積相對應)。 圖5 逐步填充卡諾圖。 這裡需要注意的另一點是,不需要真值表即可填充卡諾圖。這裡要做的只是照著方程式一項一項來,對每個乘積在對應的卡諾圖「方框」中填入1。 下一步是使用卡諾圖來化簡邏輯運算式。從圖5所得的最終卡諾圖(f)中可立即看出,可以將其簡化為三個項。如往常一樣,我們一次一次地完成每一步。 觀察圖6中用紅色圈出的兩個1,我們知道,這兩種情況下的輸出均為1。對於這兩個框中的每個框都有A = 0、C = 1,因此這兩個值很重要。但是,這兩個框中有一個是B = 0,另一個則是B = 1。這就是說,只要A = 0、C = 1,那麼就可不在乎B是0還是1。 圖6 用卡諾圖化簡邏輯運算式(第一步)。 接下來看一下圖7中用紅色圈出的第二組兩個1。對於這兩個框中的每個框都有A = 1、C = 0,因此這兩個值很重要。但是,這兩個框中也是有一個是B = 0,另一個是B = 1。這就表示,只要A = 1、C = 0,那麼就可不在乎B是0還是1。 圖7 用卡諾圖化簡邏輯運算式(第二步)。 最後但同樣重要的是,以下來看圖8中用紅色圈出的一組四個1(卡諾圖的技巧之一是可以將相同的1用作多個組的一部分)。 圖8 用卡諾圖化簡邏輯運算式(第三步)。 在這種情況下,這四個框中有兩個框是A = 0,另外兩個框則是A = 1,這就是說,我們可不在乎A是0還是1。類似地,這四個框中有兩個框是C = 0,另外兩個框是C = 1,因此我們就可不在乎C是0還是1。實際上,對於所有這四個框而言,唯一恆定的輸入是B,它始終為1。 這樣,就可以使用卡諾圖最簡化的運算式來編寫最佳化的乘積和方程,如下所示: 由此就可以使用NOT Gate、AND Gate和OR Gate輕鬆繪製相應的閘級原理圖,如圖9所示。 圖9 用AND、OR、NOT Gate實現的邏輯運算式的閘級原理圖。 至此,我知道你會跟我說我們沒有使用!B訊號(這裡使用「!」字 元來表示B的NOT,因為在文本裡在字母上畫一條橫線有點難),但我們將在不久的將來使用它。說到這,未來比你想像的要近。這是我們必須考慮的重點,因為那位令人討厭的老師他所出的作業是只使用NAND Gate或NOR Gate來展示最終電路。 使用NAND或NOR Gate實現NOT Gate 讓我們從容易的開始,先解決本例中的三個NOT Gate。首先我們先回憶五種常見基本閘的真值表,如圖10所示。 圖10 五種常見基本邏輯閘及其真值表。 也就是說,如果將NAND Gate的輸入綁(連接)在一起,那麼得到的功能就是NOT Gate。如果將NOR Gate的輸入綁在一起,那麼得到的結果也相同。也就是說,圖11中的三個部分功能相同。 圖11 NOT Gate的NAND和NOR Gate等效。 對AND、OR、NAND和NOR Gate進行DeMorgan轉換 Augustus DeMorgan (1806~1871年)是George Boole的同輩,他在符號邏輯領域做出了重大貢獻,尤其是我們現在用的一組規則—DeMorgan轉換。 為了對布林方程式進行DeMorgan轉換,需要依以下步驟進行: 1.將所有的AND運算子換成OR運算子,反之亦然; 2.將所有的輸入變數反轉,也可將任何0換成1,反之亦然; 3.將整個函數反轉; 4.減少任何多次反轉。 一般而言,我們傾向於對多項式進行DeMorgan轉換,但是也可以對單個閘進行轉換,這樣就得到圖12所示的結論。 圖12 AND、OR、NAND和NOR Gate的DeMorgan轉換。 我不瞭解你,所以沒辦法解釋為什麼會這樣,但是在查看了圖12中的DeMorgan轉換後,我感覺很滿意,並且感覺在(邏輯)世界中一切都是對的。 只用NAND Gate表示電路 老實說,現在我們已奠定了基礎,這個部分非常容易。讓我們回憶使用NOT Gate、AND Gate和OR Gate實現的電路是什麼樣的(圖13)。 圖13 對圖9所示原理圖進行顏色編碼。 我對它們進行了顏色編碼,以便讓我們清楚瞭解自己在做什麼。以下就做出決定,我們只希望使用NAND Gate。因此,使用前面討論的所有內容,就可以將NOT Gate、OR Gate和AND Gate換成NAND Gate。 和往常一樣,一步步來做。首先從左邊用粉紅色表示的三個NOT Gate開始。我們知道,可以將這三個閘中的每一個換成一個2輸入NAND Gate(它們的輸入綁在一起),所以這裡沒有問題(圖14)。 圖14 NOT Gate的NAND Gate等效。 接下來來研究電路右側用綠色表示的3輸入OR Gate。根據DeMorgan轉換,我們知道,可以用一個3輸入NAND Gate (其輸入帶有NOT Gate)來代替它,如圖15所示。 圖15 3輸入OR Gate的NOT Gate加NAND Gate等效。 當然,可以將這三個NOT Gate中的每一個再次用一個2輸入NAND Gate來替換,如圖16所示。 圖16 3輸入OR Gate的4 輸入NAND Gate等效。 因此,現在只需要考慮電路中間兩個用藍色表示的AND Gate了。當然,DeMorgan轉換在這裡幫不上忙,因為ANDGate的等效電路是將NOR Gate的所有輸入都加上NOTGate,但這個作業不允許我們使用NOR Gate。 有時,我們傾向於使事情變得比所需要的更複雜。在這種情況下,要做的就是記住,AND Gate實際上是由NAND Gate後接一個NOT Gate形成(同樣,OR Gate是由NORGate後接一個NOT Gate所組成)。也就是說,可以像圖17這樣來替換AND Gate。 圖17 AND Gate是由NAND Gate加NOT Gate所構成。 當然,由於作業要求只使用NAND Gate,因此必須將NOT Gate替換成其等效的2輸入NAND Gate,如圖18所示。 圖18 將圖17中的NOT Gate再次用等效的NAND Gate替換。 現在,萬事大吉了。因此,如果把上述所有轉換結合起來,那麼只使用NAND Gate的實現就如圖19所示。 圖19 將圖13中的AND、OR、NOT Gate全部用等效的NAND Gate替換。 雖然圖19中的電路可以執行所需的功能,但是這裡有幾個邏輯閘浪費了,因為如圖20中用紅色框框出的部分所示,有兩個地方出現了NOT Gate接NOT Gate的情況(當然都是用NAND Gate實現)。 圖20 圖19中有兩處NAND Gate浪費。 每當以非函數形式出現偶數次反轉時,都可以用一條簡單的線來代替它們。因此,稍作修改就得到圖21所示的最終電路。 圖21 布林方程式最終NAND Gate實現。 如果NOT Gate、NAND Gate和NOR Gate分別等於一級延遲,AND Gate和OR Gate分別等於兩級延遲,那麼在最初的NOT Gate、AND Gate和OR Gate電路實現中,最壞情況的輸入到輸出路徑就等於1 + 2 + 2 = 5級延遲。相比之下,經過最佳化的只使用NAND Gate的實現則僅會發生最多1 + 1 + 1 = 3級延遲。 再說一次,如果有任何學生正在閱讀本文,只是為了確保你能100%掌握以上所有內容,建議你用以上的討論為基礎,創建只使用NOR Gate實現的基礎。在此期間,歡迎提出任何意見和問題,也希望能有更多有經驗的讀者願意分享任何相關的提示與技巧。 (參考原文:Implementing Logic Functions Using Only NAND or NOR Gates,by Max Maxfield) 本文同步刊登於EDN Taiwan 2021年1月號數位版雜誌                
活動簡介

人工智慧(AI)無所不在。這一波AI浪潮正重塑並徹底改變科技產業甚至整個世界的未來。如何有效利用AI協助設計與開發?如何透過AI從設計、製造到生產創造增強的體驗?如何以AI作為轉型與變革的力量?打造綠色永續未來?AI面對的風險和影響又是什麼?

AI⁺ 技術論壇聚焦人工智慧/機器學習(AI/ML)技術,涵蓋從雲端到邊緣、從硬體到軟體、從演算法到架構的AI/ML技術相關基礎設施之設計、應用與部署,協助您全面掌握AI最新技術趨勢與創新,接軌AI生態系佈局,讓機器學習更快速、更經濟、更聰明也更有效率。

贊助廠商

發表評論