# 數系 ： Chapter 3
###### tags: `Digital system`

## 一 . 電路簡化
### (一) . 電路的基本概念和簡化 ： review
1. 電路的表達 ：
- 真值表。
- 電路圖。
- 布林代數。
2. 電路化簡的方法 ：
- 布林代數的代數性質。
- K-map algorithm。
3. K-map algorithm :
- 表示方法 ：
- 以row和col組成的2維陣列。
- 相連的一個空格為一個minterm且相差一個1bit。
- 使用方法 ：
- 1或2或4或8個一次合併 : 觀察圈內變數可為0或1者，消除。
- 沒有鄰居的先選 ： 計算鄰居數，注意，可以跨越邊界者。
- 所有的minterm都包覆即成功。
4. 精簡電路 ：
- 精簡的定義 ： 最小化的輸入和邏輯閘。
- 最簡的路徑非唯一 ： 常見的方式
- SOP : sum of product。
- POS : product of sum。

### (二) . 兩個變數的K-map

1. Minterm位置 ：
2. 合併方法 ：
- step 1 : 相鄰的兩個位置圈在一起，直到所有的1都被圈到。
- step 2 : 將相鄰的圈圈用or相連。
3. 例一 ：
- 下面電路 ： 紅圈or黃圈的時候，為Ｔ。
- 紅圈 ： $(x'y)+(xy)= (x+x')y = y$ ($x$可以是0或1，代表$x$可以忽略)
- 黃圈 ： $(xy')+(xy)= x(y+y') = x$ ($y$可以是0或1，代表$y$可以忽略)
- 電路 ： $f =x+y$


### (三) . 三個變數的K-map
1. Minterm位置 ：
2. 合併方式 ：
- step 1 : 相鄰的兩個位置圈在一起，直到所有的1都被圈到。
- step 2 : 將相鄰的圈圈用or相連。

3. 例一 ：
- 上排圈圈 ： $(x'yz)+(x'yz')=x'y'$ ($z$可以是0或1，代表$z$可以忽略)
- 下排圈圈 ： $(xy'z)+(xy'z')=xy'$ ($z$可以是0或1，代表$z$可以忽略)
- 整體 ： $(x'y')+(xy')=y'(x+x')=y'$

4. 例二 ：
- Point 1 : **可以越過邊界化簡**。
- Point 2 : **至少每一個1都必須被圈入**。
- 越過邊界的正方形 ：$(x'y'z')+(x'yz')+(xy'z')+(xyz')=z'$。
- 第二排的長方形 ： $(xy'z')+(xy'z)=xy'$。
- 整體 ：$z'+xy'$。

5. 例三 ：
- Point 1 : **不要多圈**。
- Point 2 : **由鄰居最少的開始**。
- $m4圈m6$ : m4鄰居最少，由他開始圈。
- $(xy'z')+(xyz')=xz'$。
- $m3圈m7$ : 既然m4圈了m6，m7就先不考慮先圈他，除非沒得圈。
- $(x'yz)+(xyz)=yz$
- 整體 ： $(xz')+(yz)$

### (四) . 四個變數的K-map
1. Minterm位置 :
2. 合併方式 ：
- step 1 : 相鄰的兩個位置圈在一起，直到所有的1都被圈到。
- step 2 : 將相鄰的圈圈用or相連。
3. 例一 ：
- Point : 四個變數的卡諾圖，善用多個變數，並且**用觀察的，不用慢慢算**。
- 藍圈 ： $z、x、w$可以是0或1，可以忽略，但圈中$y$必為$y'$。
- 綠圈 ： $x、y$可以是0或1，可以忽略，但圈中$w、z$必為$w'、z'$。
- 紅圈 ： $w、y$可以是0或1，可以忽略，但圈中$x、z$必為$x、z'$。
- 整體 ： $y'+w'z'+x'z'$

4. 例二 ：
- Point 1 : 轉換圖。下面只有給部分的電路，**為了滿足minterm，所以我們在沒有包含得之中填上0或1**。
- $A'B'C'=A'B'C'D+A'B'C'D'$。
- $B'C'D'=AB'C'D'+A'B'C'D'$。
- $AB'C'=AB'C'D+AB'C'D'$。
- Point 2 : 保證先**由最少的開始**，**每次圈的圈確保最大化(2或4或8)**。
- 可以知道 ： 0110為鄰居最少的minterm，先圈起來，且保證此圈是最大的。
- 所以，0110先包含0010，再安排其他的minterm的圈圈。
- 因此，我們先圈紅圈，在圈藍圈。

### (五) . K-map方法 : 整理
1. 使用步驟 ：
- step 1 : 由變數的數量畫出卡諾圖。
- step 2 : 由下列的原則圈起卡諾圖的元素。
2. 使用原則 ：
- 由最少鄰居的minterm開始。
- 每次的圈要保持最大化 ： 2或4或8。
- 圈到包起所有的minterm在作化簡。
3. 化簡方法 ：
- 善用布林方程 ： $x+x'=1$。
- 觀察圈內的minterm，若，同變數可以出現0或1，則代表可以省去。

4. 例 ： 示範畫圈
- 先找 ： 鄰居最少的，即0000或0101，所以先圈出藍圈。
- 接下來，想辦法圈出可以包含其它三者的圈。

### (六) . POS的最簡
- 上面的方法都是求出SOP的，那如果要求出POS的話，我們可以用下列方法。
1. 對$F'$做卡諾圖，即改圈1變成圈0。
2. 再用迪摩根定理 ： $(F')'＝F$。
3. 此時的$F$即為POS
4. 例子 ：

### (七) . Don't Care input
1. 定義 ： **不可能發生的輸入**。
2. 卡諾圖操作 ： 可以是**視為0或1**，在卡諾圖上記為大寫$X$。
3. 運用 ： 可以幫助我們更精簡我們的電路。
- 若沒有使用don't care ： 只能簡化成$yz+w'x'z$。

## 二 . NAND和NOR的實作
### (一) . 基本概念
1. 起因 ： 因為and和or閘的花費十分的貴，且deley的時間比較久。

### (二) . NAND實作
1. NAND特性 ： 任何的閘都可以用NAD實作。
- AND : 可以用NAND加上一個not。
- OR : 可以用NAND加上兩個not。
。

2. NAND轉換成Invert-OR : 轉化SOP。
- 由圖一可以知道 ： NAND可以用Invert-OR實作。
- 由圖二知道 ： 可以延伸SOP，讓and變成NAND，讓OR變成Invert-OR再用NAND實作。
- 轉換重點 ： 在電路兩端加入兩個not，不會改變電路輸出，但可以使我們可以改成NAND電路。
- 結論 ： 所以，所有電路求完SOP後，都可以用NAND實作。

3. 轉換方法 ： 將and接OR的閘，在and前面加入not，在OR後面加入not，可以使剛剛好and和or都轉為NAND。

4. 例子 ： 多個level的NAND轉換
- 找出and和or的相連。
- 在and前面，or後面加入not實作。

### (三) . NOR的實作
1. NOR特性 ： 任何的閘都可以用NAD實作。
- OR : 可以用NOR加上一個not 。
- AND : 兩個not，在加上一個OR。
2. NOR轉換成Invert-AND : 轉換POS。
- 由圖一可以知道 ： NOR可以用Invert-AND實作。
- 由圖二知道 ： 可以延伸POS，讓OR變成NOR，讓AND變成Invert-AND再用NOR實作。
- 轉換重點 ： 在電路兩端加入兩個not，不會改變電路輸出，但可以使我們可以改成NOR電路。
- 結論 ： 所以，所有電路求完POS後，都可以用NOR實作。

## 三 . XOR
### (一) . 基本性質和實作
1. XOR和NXOR可以用and或or表示 ：
- XOR : $x'y+xy'$。
- NXOR : $xy+x'y'$
。
2. XOR和NXOR的實作 ：
- 用SOP的方式實作XOR : 可以再換為NAND實作

### (二) . Parity
1. XOR 可以應用在even parity的產生和偵測。
- even parity : 用來測試傳輸資料是否有錯誤。
2. Parity generator : 產生1個bit的0或1使整串資料的1的個數為偶數。
- 真值表 ： 使1個個數為偶數。
- 布林函數 ： 用XOR的運算特徵。
3. Parity check : 檢查字串是否滿足even parity的特性。
- 真值表 ： 下面的資料包含對跟錯的資料，即全部的結果。