# 數系 : Chapter 4
###### tags: `Digital system`

## 一 . 基本概念
### (一) . 組合電路、循序電路
1. 組合電路(Combinational logic circuits) :
- 定義 : 只能和input有關，輸出output。
- function： 是一個input集合mapping到output的關係。
2. 循序電路(Sequential logic circuits) :
- 定義 : 只能和input和集中儲存的bit或feeback有關，輸出output。
- function： 是一個input和儲存bit集合mapping到output的關係。

3. 常見的組合電路 :
- 常見的組合電路型態如下 ： 可以有 $2^n$ 種input。
- 常見的組合電路 ： 加法器、減法器、乘法器、解碼器、加密器。
4. 分析一個組合電路 ：
- step 1 : 拿到真值表。

### (二) . 設計一個組合電路
1. 前置 ：
- step 1 : 決定問題的定義。
- step 2 : 問題的輸出輸入。
- step 3 : 將問題的輸出輸入加上變數代號。
2. 電路形成與簡化 ：
- step 1 : 畫出真值表。
- step 2 : 將k-map化簡真值表。
- step 3 : 用NADN、NOR優化電路。

### (三) . 範例 ： BDC轉Excess-3
1. 前置 ： 重點為取得真值表，當然要先觀察是否符合組合電路的特性。
2. K-map : 將『每一個output』都畫成一個個k-map。
- 每一個k-map形成個解就是最佳解。
- 並將每一個解合成一個電路。



## 二 .加法器

### (一) . 半加器
#### 1. 功用 ： 輸入為2個bit的相加，輸出包含進位carry。
- 定義輸出入 ： $x、y$ 為輸入；$c、s$ 為輸出。
- 真值表 ： 如下，由兩個k-map化簡。


#### 2. 電路 ：
- step 1 : 先找出sum of product。
- step 2 : 在用k-map化簡。
- 註 ： 其實這邊看一下就知道一個是and一個是xor。


### (二) . 全加器
#### 1. 功用 ： 輸入為3個bit的相加包含進位carray，輸出為兩位的bit。
- 定義輸出入 ： $x、y、z$ 為輸入，$z$為上一位的進位；$c、s$ 為輸出。
- 真值表 ： 如下，由兩個k-map化簡。

#### 2. 電路 ：
- 法一 ： 視為全新的電路。再用一次新的k-map化簡。
- 法二 ： 用兩個半加器相加。先加x和y，再將x加y的s和z相加，注意多一個or閘。


若x=1, y=1 , z=1 時 ：  
   1 ->x      0  -> s of x+y
+) 1 ->y   +) 1  -> z
----        -----
  10         01

### (三) . 4bit加法器
#### 1. 功用 ： 4個bits和一個carry的相加。
#### 2. 電路 ：
- 不能再用一般一個位的二進位相加減。
- 因為輸入太多，k-map化簡不易。
#### 3. Ripple carry : 將多個全加器相連，形成一個多bit的相加。


#### 4. Carry Propagation ： 多個全加器相連下，相加會等上一個位的進位，造成delay。
- 雖然exclusive-or的延遲最長，但因為可以於有輸入的時候就加入，因此，比進位的延遲來說較短。
- 對每一位的進位，都有兩個邏輯閘(進位)的延遲 : $n$個bit的相加，要等$2n$個加法器的delay。


#### 5. Carry lookhead優化 :
- 方法 ： 將每一個進位的關係直接爆開，使其值只和輸入的三個為數有關。
- 可以再有輸入的時候，就直接算出進位值，不用等到上一個位算完。
- 如下圖 ： 可以有輸入的時候，就直接計算出全部的進位。

### (四) . 加減器
#### 1. 功用 ： 因為二補數加減可以用同一個方式，此則為實作。
#### 2. 電路 ：
- step 1 : 若為減，取減數的二補數(M為1時)。
- 取二補數方式 ： $not$整個數後，加一($C_0=M=1$)。
- 取二補數實作 ： $XOR$的性質，即$X(xor)0=X$和$X(xor)1=X'$。
- step 2 : 為二補數相加，得解即為二補數的形式。
- 正數方面 ： 二補數和sign形式一樣。
- 負數方面 ： 二補數和sign形式不一樣，所以取二補後，答案為二補形式。

## 三 . 乘法器
### (一) . 乘法器一
#### 1. 功用 ： 將2-bit乘2-bit的二進位進行乘法。
#### 2. 分析二進位乘法 ： 展開分析
- 二進位相成的邏輯，就是and二數。
- 乘法可以分析為先and在or。

#### 3. 電路 ：
- step 1 : 先取乘法公式中需要的各項。
- step 2 : 相加各項，用兩個半加器形成的3bit相加。


### (二) . 乘法器二
#### 1. 功用 ： 將4-bit乘3-bit的二進位進行乘法。
#### 2. 分析二進位乘法 ： 展開分析
- 二進位相成的邏輯，就是and二數。
- 乘法可以分析為先and在or。

#### 3. 電路 ：
- step 1 : 先取乘法公式中需要的各項。
- step 2 : 相加各項，用兩個半加器形成的3bit相加。


### (三) . 比較器一
#### 1. 功用 ： 比較兩串二進位是否一樣，是大於或小於。
#### 2. 分析 ： 分析兩個字串，
- 若字串是 ： $A_0A_1A_2A_3$、$B_0B_1B_2B_3$。
- 全等下 ： $A_0=B_0$ 且 $A_1=B_1$ 且 $A_2=B_2$ 且 $A_3=B_3$。
- 意思 ：
- 設$x_i=A_iB_i+A_i'B_i'$ ： 即若$A_i=B_i=1\ or \ 0$時。
- 也可以視$x_i$為$x_i=A_i\ (xor)\ B_i$。
- 大於下 ： $A_3B_3'+x_3A_2B_2'+x3x2A_1B_1'+x_3x_2x_1A_0B_0'$。
- 意思 ：
- 小於下 ： $A_3'B_3+x_3A_2'B_2+x3x2A_1'B_1+x_3x_2x_1A_0'B_0$。
- 意思 ：

#### 3. 電路 ：

## 四 . 解碼器
### (一) . 3轉8Decoder
#### 1. 功用 ： 將$3\ bit$轉乘$8\ bit$的電路。
- n個輸入有$2^n$個輸出。
- 輸出的只有一個1。
#### 2. 分析 ： 由真值表(圖需要記憶一下，什麼minterm是$D_n$為1)
- 真值表 ： 不用使用k-map化簡，因為變數太多，需要大量時間空間。
#### 3.電路 ：
- 用 $sum\ of\ product$去思考。
- 因為and閘在全為1下，才可以為1。
- 所以，每個用not連接後，在分八個，可以變成8不同的狀況。


### (二) . enable電路
#### 1. 功用 ： 可以決定組合電路是否進行
- 利用 ： and閘只要有一個0就為0的特性。
- 結果 ： 全部電路都連上一個enable，使得
- enable為0時，整個電路都沒有輸出。
- enable為1時，整個電路才可能有輸出。

#### 2. 電路 ：
- 加入enable後 ：當期為0時，整個電路都會輸出0，無法加密。
- 真值表要特別標註enable為非啟動時的情況為$don't care$。
- $enable$為0為啟動 ： active-low。
- $enable$為1為啟動 ： active-high。


### (三) . 4轉16Decoder
#### 1. 功用 ： 將$4\ bit$轉乘$16\ bit$的電路。
#### 2. 分析 ： 用真值表
- 若用真值表分析，會太花時間。
- 可以視為3轉8加入一個enable。
- 3轉8decoder在enable為0時。
- 3轉8decoder在enable為1時。
#### 3. 電路 ： 為2個decoder。

### (四) . minterm generator
#### 1. 概念 ： decoder對應唯一的minterm
- 由decoder的真值表，我們可以知道。
- 唯一的minterm都有一個唯一的解碼。
- 所以代表每一個decoder的輸出，都代表唯一的minterm。
- 如下 ： 當$D_n$為1時，都可以對應到唯一的minterm。

#### 2. 應用 ： 可以用decoder實作full adder
- 由真值表分析 ：
- S : 為1、2、4、7的sum。
- C : 為3、5、6、7的sum。

## 五 . 編碼器
### (一) . encoder
#### 1. 功用 ： 為把decoder的功能翻轉回去
- 限制 ： 一次只有1個為1輸入。
- 不合法 ： 當輸入為2個1時，會有不可預期的結果。
#### 2. 分析 ： 考慮輸入的情況
- 設計 ： 只先考慮合法輸入的情況，不處理有多個1時的輸入。
- don't care : 所有非法的輸入。

#### 3. 電路 ：
- 直觀邏輯 : 考慮『什麼輸入的時候會為1』。
- 由真值表可以看到，在不同$D_n$為1時才會造成不同的$x、y、z$為1。


## 三 . 選擇器、buffer和gate
### (一) . 選擇器
#### 1. 功用 ： 在兩個輸入之間選擇一個為輸出。
#### 2. 分析 ：
- 真值表 ： 注意選擇器通常除了一個enable bit外，通常會多一個select bit，為選擇哪一個輸入為輸出。
- 注意 ： 通常不用管輸入，因為selcet bit決定了整個輸出。
#### 3. 電路
- 用and的特性為選擇器。
- 用or為最後總輸出。

### (二) . 1個位元的4選1選擇器
#### 1. 功用 ： 在4個1bit的輸入之間選擇一個為輸出。
#### 2. 分析 ：
- 真值表 ： 似前面那個電路，可以只考慮select的可能性。
- 注意 ： $n$個select可以決定$2^n$個輸入中選一個。

#### 3. 電路
- 有兩個select可以決定$2^2$個輸入中選一個輸出。

### (三) . 4個位元的2選1選擇器
#### 1. 功用 ： 在2個4bit的輸入之間選擇一個為輸出。
- 並且加入enable。
#### 2. 分析 ：
- 真值表 ： 似之前的電路，可以只考慮select的可能性。
- 注意 ： 有enalbe時，要標記enable為off狀態時，輸入為$don't care$。
- enable也有active-high active-low之分。

#### 3. 電路

### (四) . Buffer
#### 1. 功用 ：
- 增加電路fan-out的數量。
- 可以用兩個not實作。
#### 2.實作
- 若有一個and閘fan-out為2。
- 但需要驅動4個電路。
- 可以先接上兩個fan-out為2的buffer。