---
tags: 必修們
---
# 數位系統
:::spoiler 傳送門
[TOC]
:::
:::info
Exercise:
Problem 2.2
Problem 2.3
Problem 2.4
Problem 2.17
Problem 2.19
Problem 2.22

Honework:
Problem 1.5,1.16,1.33
Problem 2.2,2.22
Problem 3.5(a)(b),3.9(a)(b),3.13(a),3.19(a)
:::

## Intro
- 數位系統流程圖
- 數位與類比訊號

## Complement
- 十進制小數轉換

- 補數
- **r補數為 r-1補數+1**
ex:95621的9補數為4378,10補數為4379
- M-N補數算法
- **STEP1.取N的r補數**
- **STEP2.將M加上N的r補數,如果多出一個進位，表示M>=N，去掉最大的位數即為結果**
- **STEP3.沒有多出進位，表示M<N，將結果扣掉$r^n$即為結果**
- 這麼做可以用加法取代減法

- 二進制正負數表示方式

- **對一個負數取2補數，就會出現他的大小**
ex:1001 -> 0111 -> -7 , 1000 -> 1000 -> -8

- 二進制M-N算法
- **記得正數要在前面補零**

- 補數的缺點:overflow
- overflow rule:兩個正數相加變成負數,兩個負數相加變成正數，正負數相加不會產生overflow

## 編碼們
### BCD code

**10~15是用不到的**
- 185的BCD碼 ->0001 1000 0101


- BCD加法
- 相加後多大於1001，就再加上6(0110)，便可順利進位

### Gray code
- 每次加1只會有一個位數不一樣->適合當計數器

- 編碼規則
**基本概念:鏡射，上半部補零，下半部補一**

### ASCII code

- **實際上只會用到右邊七位，最左的那位是用來偵錯用的**
偵錯方式:利用偶同位，只要變成奇同位就是有產生位元錯誤。

## Binary logic

- 三種基本邏輯運算


## Error Detection and Correction

- **Distance: 有幾個位元不一樣**

相鄰的只會有一個位元不同

- 偵測錯誤的代價: 需要多用**一個位元**變成偶同位或是奇同位
- 修正錯誤的條件: **只有一個位元發生錯誤且距離要大於等於三才可以修正**

- Hamming codes

**m位個同位位元，可以編出$2^m-1$長度的Hamming code，其中有$2^m-1-m$個位元可以存資料**

- 假設有3個同位位元，便可以產生長度為7個code，可以存放4個位元的資料，往右邊數$第2^0,2^1,2^2個$位元會是同位位元

- 選擇$2^0,2^1,2^2$當同位位元，是因為這三個數字可以組合成$(2^3-1)$以內的所有數字

- 使用方法: 將每個同位位元和對應的資料位元檢查是否偶同位，將發生奇同位的位置加起來就是發生錯誤的位數

若每個同位位元1,2,4都和對應的資料位元發生奇同位，那就是第1+2+4個位元發生錯誤。


## Chap. 2 Boolean Algebra and Logic Gates
### Basic Theorems & Properties
- 分配率
列出所有可能性(真值表)，即可證明OR Gate & AND Gate皆==存在分配率==

- 定理們(考試會給)

**用Postulate證明$x+x = x$**
\begin{split}
x+x &= (x+x)\cdot 1\\
&= (x+x)(x+x')\\
&= x+x\cdot x'\\
&= x+0\\
&= x
\end{split}

**證明吸收律**
\begin{split}
x + xy &= x1 + xy\\
&=x(1+y)\\
&=x1\\
&=x\\
&\end{split}

- 迪摩根
- not(a and b) = not a or not b
- not( a or b) = not a and not b

### Boolean Function
不同的Boolean Function可能會有相同的結果(可化簡)
- 運算優先權
1. 括號
2. NOT
3. AND
4. OR

### Algebraic Manipulation

- 定義最小化Boolean expression
- 變數數量越少越好
- OR|AND Gate 越少越好

**e.g.**
利用定理靠經驗化簡，以下確實有化簡，==但不保證最簡==(詳情請見第三章內容補充包)
- $x(x'+y)=xx'+xy=0+xy=xy$
- $x+x'y=(x+x')(x+y)=1(x+y)=x+y$

利用吸收率，生出==臨時變數==化簡

Distance只有一個的時候，可以==藉由結合率減少變數==
- $x'y'z+x'yz=x'z(y'+y)=x'z$

利用吸收率，生出一個與原本的項距離差一的新元素，再行化簡

### Complement of a Function

- 三變數的DeMorgan
\begin{split}
(A+B+C)' &= (A+X)'\\
&= A'X'\\
&= A'(B+C)'\\
&= A'B'C'
\end{split}
- N變數：規則一樣 刮號裡分開，AND, OR互換


- 參考算法

### Canonical and Standard Forms

- minterm & maxterm(Canonical form)
- minterm : 所有 term 皆為 AND gate (standard product)
- maxterm : 所有 term 皆為 OR gate (standard sum)
- 上述兩者皆有$2^n$種狀況(每個變數都有 primed 或 unprimed 兩種)
- [Extra Reading](https://www.allaboutcircuits.com/textbook/digital/chpt-8/minterm-maxterm-solution/)
- minterm 例子
- maxterm 例子

- 順序(照二進制排)，minterm 零對應有 prime 一對應沒有 prime ， maxterm 則是與 minterm 相反

**e.g.**
- $f_1 = x'+y'+xyz=m_1+m_4+m_7$
- $f_2 = x'yz+xy'z+xyz'+xyz=m_3+m_5+m_6+m_7$

- 任何Boolean function都可以表示成maxterm或是minterm且**表示方法唯一**

- 將minterm轉換為maxterm

- 一個一個代太遜了，直接用公理及定理生出來
- 作法一: 缺甚麼就就補甚麼(利用$(x+x')=1$)
- 作法二(較簡單的方法):
**Solve: $F = x+y'z$**

1. 分成 $x$ 及 $y'z$前後兩項
2. 先看$x$，$x$沒有prime，所以鎖定x值為1，把剩下的y，z所有狀況填上去，產生100,101,110,111。
3. $y'z$也用一樣的方式，鎖定y值為0,z值為1，產生101,001。
4. 將上面產生的做聯集，得到答案。

- Product of maxterms
可以將Sum of minterms反轉得到，也可以利用$(xx')=0$得到

- 真值表和Canonical表可以互相轉換

**e.g.**
$F(A,B,C) = \Sigma(1,4,5,6,7)$
$F'(A,B,C) = \Sigma(0,2,3)$
根據DeMorgan(minterm為maxterm補集): $F(A,B,C) = \Pi(0,2,3)$

### Standard Form
形式為下列兩種
1. 積項的和 $F_1=y'+xy+x'yz'$
2. 和項的積 $F_1=x(y'+z)(x'+y+z)$

### Other Logic Operations

- n個變數可以產生$2^n$種結果($2^n$rows in the truth table)
- n個變數可以有$2^{2^n}$種邏輯運算(functions)
- $F_0$為$F_{15}$反相，$F_1$為$F_{14}$反相，以此類推
- 特別介紹XOR,Equivalence
- XOR: 相同為0，不同為1
- Equivalence: 相同為1，不同為0

### Digital Logic gates
- **NAND及NOR並不具有結合率**
- NAND可以利用積項的和化簡省電晶體，NOR則是利用和項的積
- N輸入的XOR GATE，奇數個1會輸出1，偶數個1則會輸出0(可以連結到之前的漢明碼處理)
- 各種Gate

### Gate Implementations(死人電子學)
- 先有NOR,NAND才有OR,AND
- NOR,NAND共有四個電晶體，OR,AND則是再加上invert的兩個電晶體，共六個電晶體

## Chap. 3 Gate-Level Minimization

### Map method
- 兩變數的Karnaugh圖，distance都是相差1
>相鄰的1開始合併，只下值相等的變數

### Three-variable Map
- 三變數的Karnaugh圖
>為了保持相鄰距離為1，順序採用Gray code


**Example:**

- 在兩端也算相鄰，因此也可以化簡

- 試著找到可以合併最多次的方法，這樣才是最簡

- 面積為2,4,8的長方形可以合併在一起，4可以砍掉兩個變數，8則可以砍掉三個變數

- 重疊的話也可以重複使用

### Four-variable Map

- 找2,4,8,16個1相鄰(只能為長方形，從16個1開始找)，2個1相鄰可消掉1個變數，4個則是消掉2個變數，以此類推

**Example:**
- 尋找順序:16個1相鄰->8個1相鄰->4個1相鄰->2個1相鄰

- **四個角落皆為1也算是4個1相鄰**

- Prime Implicants
>定義: 這個長方形框框沒有被更大的長方形包圍住
- Essential
>定義: 長方形(必須要是prime Implicant)包圍住的所有1中，有其中一個1只有被這個長方形框住(若沒有這個長方形框框就沒辦法cover全部的1)

- Karnaugh圖簡化並不一定是唯一的，怎麼選擇最後非Essential的框框來cover住剩下的1，會決定最後出現的答案(但都是對的)

### Five-variable Map

- 用兩個4變數的圖去組成5變數的圖
>兩個圖中同位置的相鄰(例如7和23相鄰,3和19相鄰，兩個編號都會差16)，其他就和四變數的圖相同


**Example:**

### Six-variable Map

- 四個4變數的圖組成6變數的圖
>太噁心了，這不會考XD

- 每個位置都有6個位置和它相鄰(10和2,8,11,14,26,40相鄰)

## Product of Sums Simplification

- 利用Karnaugh圖來找和項的積
>方法很簡單，直接拿圖上的0來化簡(DeMorgan's theorem)


## Don't-Care Conditions


- 有時候會有可以填1也可以填0的狀況，這時候就填入可以幫助畫簡的數值

### 速記表 : 2 level 的計算過程們

| 2 level | 計算過程 |
|:-------:|:-----------------------------------------------------:|
| SOP | 框 1，化簡 |
| OAI | 框 1，化簡，再整個取 complement，最後最外面括號加 not |
| POS | 框 0，化簡，再整個取 complement |
| AOI | 框 0，化簡，最後最外面括號加 not (不要用迪摩根) |

## Chap. 4 Combinational Logic
### 概念

- 電路都是從起點直接流到終點，不會有feedback的狀況，也可以用karnaugh map化簡
- Sequential circuits 有==回饋==的資訊


單個最簡，合起來不一定是最簡
1. 多利用 de morgan 換成 NOR / NAND
2. 重複利用中途的計算解果


### BCD TO EXCESS-3

>因為是BCD，所以會有Don't care condition



>化簡後會碰到一個問題，每個輸出都是最簡，但是組合後不保證為最簡，因此還需要改變一下化簡的結果，找出各個輸出的共通點(需要的電晶體較少但Delay會比較長)


### Adder-Substractor

- Half adder
- ==only== single bit add
- S = x ⊕ y
- C = x and y



- Full adder
- ==multi== bits add
- S = x ⊕ y ⊕ z
- C = xy and yz and xz
>若產生(棋盤格狀)錯開的Karnaugh map，此種狀況無法化簡，直接用sum of product會用到太多電晶體，
>因此考慮xor or xnor，在最左上角的位置是1的話為exclusive-nor，反則exclusive-or


>x xor y的結果也可以給C做使用


- 可能碰到的問題

>如果使用 ripple carry adder 來設計全加器，delay時間會隨著位元數而增加，因為要等前面算完

- 解決方案：look ahead adder，直接用 2n bit 的 input 組合算出 n bit 的結果（快，但很肥）

### Carry-look Ahead Adder

- carry propagate: $P_i=A_i \oplus B_i$
- carry generate: $G_i=A_iB_i$
- sum : $P_i \oplus C_i$
- carry : $C_{i+1}=G_i+P_iC_i$(A,B都是1或是AB其中有一個1且carry為1的時候會進位)



### Subtractor

>A-B其實就是A再加上B的2補數

實作上要新增一個減法 flag as M，在其中一組 input 之前加 xor(B ⊕ M)，然後 assign $C_0$ = M（+1的動作），簡單來說，M=1會做減法，反之則做加法


- 可能遇到的問題 - overflow

>經過觀察，發現4位元減法器$C_3,C_4$不相同時，會overflow
- detect n bit oveflow : $C_{n-1} \oplus C_{n}$

### Decinal Adder

>把兩個BCD碼加在一起

- 若要把兩個4bit的BCD加在一起，你會需要9個input、5個output，這樣幾乎不可能化簡，因此就直接用上面的binary Adder，再轉回BCD(大於等於10的直接加6)
- 大於等於10的狀況：$K + Z_8Z_4 + Z_8Z_2$



### Binary Multiplier

>先利用AND gate產生部分乘積，再將這些數字加總

- AND閘及半加器即可實作2 bits * 2 bits乘法器

- m bits* n bits會需要m+n個bit輸出，n-1個加法器，每個加法器為m-bit adder，下圖為4 bits* 3 bits乘法器

### Magnitude Comparator

>輸入很多，沒辦法Karnaugh map化簡

- 從最左邊的bit開始比，一樣的話就比下一個bit

**先對A和B的每個bit做xnor**，接著做下圖的操作