卡諾圖

維基百科,自由的百科全書
跳轉到: 導覽搜尋

卡諾圖真值表的變形,它可以將有n個變數的邏輯函數2^n個最小項組織在給定的長方形表格中,同時為相鄰最小項(相鄰與項)運用鄰接律化簡提供了直觀的圖形工具。但是,如果需要處理的邏輯函數的自變數較多,那麼卡諾圖的行列數將迅速增加,使圖形更加複雜;此外,卡諾圖的圖形化表示方法不適合直接用於演算法的設計,因此計算機輔助工程工具一般不會使用卡諾圖來進行邏輯函數的優化。[1]:189

卡諾圖是貝爾實驗室的電信工程師,莫里斯·卡諾英語Maurice Karnaugh在1953年發明的。

變數卡諾圖[編輯]

  • 表示各最小項的2^n(n-變數數)個小格,排列呈矩形。
  • 小格按「循環碼」 排列,保證最小項間「幾何相鄰」與「邏輯相鄰性」的統一。(幾何相鄰有「內相鄰」 「外相鄰」和「中心對稱」)

Kanuo1.jpg

函數卡諾圖[編輯]

把函數包含的所有最小項,以「1」填入變數卡諾圖對應編號的小格內。

Kanuo2.jpg 99

用卡諾圖化簡邏輯函數的步驟[編輯]

  • 如果表達式為最小項表達式,則可直接填入卡諾圖
  • 如表達式不是最小項表達式,但是「與—或表達式」,可將其先化成最小項表達式,再填入卡諾圖。也可直接填入。
  • 合併相鄰的最小項,即根據下述原則畫圈
    • 盡量畫大圈,但每個圈內只能含有2^n(n=0,1,2,3……)個相鄰項。要特別注意對邊相鄰性和四角相鄰性。
    • 圈的個數盡量少。
    • 卡諾圖中所有取值為1的方格均要被圈過,即不能漏下取值為1的最小項。
    • 在新畫的包圍圈中至少要含有1個未被圈過的1方格,否則該包圍圈是多餘的。
  • 寫出化簡後的表達式。每一個圈寫一個最簡與項,規則是,取值為l的變數用原變數表示,取值為0的變數用反變數表示,將這些變數相與。然後將所有與項進行邏輯加,即得最簡與—或表達式。

在進行化簡時,如果用圖中真值為0的項更方便,可以用他們來處理,方法和真值取1時一樣,只是結果要再做一次求反。

Kanuo3.jpg

引用[編輯]

  1. ^ Stephen Brown, Zvonko Vranesic. Fundamentals of Digital Logic with Verilog Design. McGraw-Hill Education. ISBN 0-07-283878-7.