[toc]

# Chapter 1
## Digital System

- Boolean Algebra, 表示邏輯運算, 如 `A AND B = AB`
- Logic Gates, 如 `AND, OR, NOT`
- 組合邏輯, 沒有記憶功能, 輸出依賴當前輸入
- 時序邏輯, 有記憶功能, 如 counter, register

## Number Base Conversions

### r-base to Decimal

假設是n位整數, m位小數
整數部分: 每個數字乘上 `r^n` ~ `r^0` 次
小數部分: 每個數字乘上 `r^-1` ~ `r^-m` 次


### Decimal to r-base

整數部分: num / r, 直到num=0為止, 反著取餘數
小數部分: num * r, 直到num=0為止, 正著取整數

- code

int num;
string s;
while(num) {
   s = to_string(num % r) + s;
   num /= r;
}
cout << s << "\n";

- to binary
- to octal

### Octal To Hex
octal -> binary
binary -> hex

## Complements of Numbers

(number N, in base r, having n digits)

### radix complement
r's complement = `r^n - N`

每個數字用(r-1)減掉, + 1

- 十進位(10補數) (每位數: 用9減掉, + 1)
- 二進位(2補數) (每位數: NOT, + 1)


### diminished radix complement
(r-1)'s complement = `(r^n - 1) - N`

每個數字用(r-1)減掉

- 十進位(9補數) (每位數: 用9減掉) (`k = 9 - k`)
- 二進位(1補數) (每位數: NOT) (`k = 1 - k`)


### 補數相減
如果要計算`M - N` in base r

先算 `K` = `M + N的r補數` = `M + (r^n - N)`
- 如果 M >= N, r^n 可以省略
ex.
M = 725, N = 316, r = 10
N的10補數 = 10^3 - 316 = 684
M + N的10補數 = 725 + 684 = 1409, 捨去r^n (進位的1)

- 如果 M < N, 取r補數, 再加負號
ex.
M = 316, N = 725, r = 10
N的10補數 = 10^3 - 725 = 275
M + N的10補數 = 316 + 275 = 591,
取10補數 = 409, 加上負號 = -409

### 二補數減法 vs 一補數減法

如果一補數減法時, 有end carry, 要加1。
ex. X = 1010100, Y = 1000011

- 2's
X - Y -> X + Y的2補數 = 1010100 + 0111101 = 10010001, 捨棄 = 0010001
Y - X -> Y + X的2補數 = 1000011 + 0101100 = 1101111, 取負2's -> -0010001
- 1's
X - Y -> X + Y的1補數 = 1010100 + 0111100 = 10010000, **把end carry加回** = 0010001
Y - X -> Y + X的1補數 = 1000011 + 0101011 = 1101110, 取負1's -> -0010001

### 二補數加法
如果要計算`x + y` in base 2
先算`x + y的2補數` = `x + (2^n - y)`

- 如果 x > y, 2^n 可以省略
`x + (2^n - y) = 2^n + (x - y)` -> `x - y`

- 如果 x = y, 0
`x + (2^n - y) = 2^n + (x - y)` -> `x - y` -> `0`

- 如果 x < y, 為 `-(y-x)`
`x + (2^n -y) = 2^n - (y - x)` -> 就是了

### Signed Binary Numbers
最大位表示正負號

#### 二補數變號
取一次二補數
ex. 6 (0110) -> -6 (1001 + 1 = 1010)

#### 加法

- signed magnitude:
- 同號: 兩數的數值部分: 加起來, 正負號部分: 用原本的正負號
- 異號: 兩數的數值部分: 大數-小數, 正負號部分: 用大數的號

- 2's complement:
兩數binary直接加起來, 進位捨棄

#### 減法
- 2's complement:
(+-A) - (+B) = (+-A) + (-B)
(+-A) - (-B) = (+-A) + (+B)

### Binary Codes

#### BCD
把每位數用0000 ~ 1001 表示。

k位數的decimal需要4k bits的BCD

ex.

185 = 0001 1000 0101

# Chapter 2

## Algebraic Properties

### Axioms of algebra

- Commutative Law
a + b = b + a, a x b = b x a

- Associative Law
(a + b) + c = a + (b + c)
(a x b) x c = a x (b x c)

### Equivalent relation

- Reflexive
For any element a, it satisfies a = a.

- Symmetric
if a = b then b = a must also hold.

- Transitive
if a = b and b = c then a = c must also hold.
## Boolean Algebra

(a) Element 0 is an identity element with respect to +;
x + 0 = 0 + x = x.
(b) Element 1 is an identity element with respect to •;
x • 1 = 1 • x = x.

## Two-valued Boolean Algebra

### Binary Operator

- AND
F = x * y

| x | y | F |
| - | - | - |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |

- OR
F = x + y

| x | y | F |
| - | - | - |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |

## Unary Operator

- NOT
F = x'

| x | F |
| - | - |
| 0 | 1 |
| 1 | 0 |

## Basic Theores and Properties of Boolean Algebra
- Idempotent Law
`x + x = x`
`x * x = x`
- Domination Law
`x + 1 = 1`
`x * 0 = 0`
- Involution Law
`(x')' = x`
- Associativity Law
`x + (y + z) = (x + y) + z`
`x(yz) = (xy)z`
- DeMorgan's Theorem
`(x+y)' = x'y'`
`(xy)' = x' + y'`
- Absorption Law
`x + xy = x`
`x(x + y) = x`
- Identity Law
`x + 0 = x`
`x * 1 = x`
- Complement Law
`x + x' = 1`
`x * x' = 0`
- Commutative Law
`x + y = y + x`
`xy = yx`
- Distribution Law
`x(y + z) = xy + xz`
`x + yz = (x+y)(x+z)`

### Operator Priority
- Parentheses: ()
- NOT
- AND
- OR

## Boolean Functions
是一個代數式, formed with:
- Binary variables
- Binary operators: AND and OR
- Unary operator: NOT
- Parentheses: ()

ex.
`F = x + y' z`

可以用真值表表示, 有2^n row。(n個binary var)
有無限個代數式能表示一個Boolean Function, 能找到最簡的 (cost)
任何Boolean function都可以用AND, OR, NOT表示

### Literal (字面量)

Ex.
`F = x'y'z + x'yz + xy'`

- 8 literals
- 1 OR term
- 3 AND term

### complement

The complement of any function F is F'

Ex.
`F = x'y'z + x'yz + xy'`
`F' = (x'y'z + x'yz + xy')' = (x + y + z')(x + y' + z')(x' + y)`

### Algebraic Manipulation
- Minimize the numbers of literaals and terms
- No specific rules to guarantee the optimal results.

## Canonical and Standard Form

### Minterm, Maxterm

- Minterm (mi)
`AND`
ex. `x, y` , minterms are `x'y'`, `x'y`, `xy'`, `xy`

- Maxterm (Mi)
`OR`
ex. `x, y` , maxterms are `x + y`, `x + y'`, `x' + y`, `x' + y'`

Mi = mi'

| x | y | z | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |

### Canonical Form (正規形式)

SOM = POM

#### Sum of Minterm (SOM) (積之和)

取1

`F = x'y'z + xy'z' + x'y'z'`
`= m1 + m4 + m7`
= ∑m (1, 4, 7)

#### Product of Maxterm (POM) (和之積)

取0

`F' = (x + y + z)(x + y' + z)(x + y' + z')(x' + y + z')(x' + y' + z)`
`= M0 * M2 * M3 * M5 * M6`
= ∏M (0, 2, 3, 5, 6)

### Standard Forms

#### Sum of Products (SOP)
- 每個項目都是AND組合
- 多個AND之間用OR連接

ex. `F = y' + zy+ x'yz'`

#### Product of Sums (POS)
- 每個項目都是OR組合
- 多個OR之間用AND連接

ex. `F = x(y' + z)(x' + y + z' + w)`

## Other Logic Operations

n binary variables
- 2^n rows in the truth table
- 2^2^n functions


NAND 與 NOR 容易實現, 比XOR, XNOR更容易用於硬體設計

AND, OR 可擴展多個輸入

任何布林函數都 可以用NAND或NOR實現

- AND
`F = x * y`

| x | y | F |
| - | - | - |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |

- OR
`F = x + y`

| x | y | F |
| - | - | - |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |

- NOT
`F = x'`

| x | F |
| - | - |
| 0 | 1 |
| 1 | 0 |

- Buffer
`F = x`

| x | F |
| - | - |
| 0 | 0 |
| 1 | 1 |

- NAND
`F = (xy)'`

| x | y | F |
| - | - | - |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

- NOR
`F = (x + y)'`

| x | y | F |
| - | - | - |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |

- XOR
`F = xy' + x'y = x ⊕ y`

| x | y | F |
| - | - | - |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

- XNOR
`F = xy + x'y' = (x ⊕ y)'`

| x | y | F |
| - | - | - |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |

# Chapter 3

一個Function的truth table是unique, 但是algebra expression不unique

最簡的表達式: 最少terms, 越少literals越好。

## K-Map

### Merging Minterm
如果說某兩行, 有個值與輸出無關
範例: m1, m3

m1: 001 x'y'z, m3: 011 x'yz
因此, m1 + m3 = x'y'z + x'yz = x'z(y' + y) = x'z

| x | y | z | F | m |
|---|---|---|---|---
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | m1
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | m3
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |

### Two-Variable Map
### Three-Variable Map

### Four-Variable Map

### Implicants

F 是 n 個變數的 Boolean Function

P 是 乘積項

如果使P得到1的所有組合，F也等於1, 則P是F的蘊含項

- 特性:
- 涵蓋一個或多個1
- 每個minterm都是一個implicant

### Prime Implicants (PI)

- 特性:
- 不能再擴大的implicant (最大可能群組) (符合2的次方)

### Essential Prime Implicants (EPI)

- 特性:
- 是Prime Implicant
- 他圈的某些Minterms不被其他Prime Implicants覆蓋
- 非選不可的Prime Implicant

Ex. F(A,B,C,D) = ∑ (0,2,3,5,7,8,9,10,11,13,15)


1. 找PI
圈起來的都是PI (CD, B'C, AD, AB', BD, B'D')
2. 找EPI
綠色的是EPI (BD, B'D')

3. 選所有EPI
有: BD, B'D'
4. 選最少的PI, 用於覆蓋未被EPI覆蓋的minterm
至少要: B'C + AB' (不唯一)

所以得到F = BD + B'D' + B'C + AB'

## Product of Sums Simplification


1.
用 SOP 表示 F'
然後F = (F')'

F' = m0 + m1 = A'B'C'D' + A'B'C'D = A'B'C'
F = (F')' = (A'B'C')' = A + B = C

2. 用Maxterms

F = (F')' = (m0 + m1)' = M0M1 = (A+B+C+D)(A+B+C+D')=A+B+C

#### k-map
0: 用SOP表示F'
1: 套用Demorgan, F = (F')' (POS)

ex. F = ∑(0,1,2,5,8,9,10)

選0, F' = AB + CD + BD'
F = (F')' = (A'+B')(C'+D')(B'+D)

ex.

- In SOM (選1):
F = m1 + m3 + m4 + m6 = ∑(1,3,4,6)
- In POM (選0):
F' = m0 + m2 + m5 + m7
F = (F')' = M0M2M5M7 = ∏(0,2,5,7)

ex.

- In SOM (選1):
F = ∑(1,3,4,6) = m1 + m3 + m4 + m6 = x'z + xz' (SOP)
- In POM (選0):
F' = ∑(0,2,5,7) = m0 + m2 + m5 + m7 = xz + x'z'
F = (F')' = (x'+z')(x+z) (POS)
## Don't Care Conditions
可以是0,1的

ex.

F(w,x,y,z) = ∑(1,3,7,11,15)
d(w,x,y,z) = ∑(0,2,5)

-> F可以是 ∑(0,1,2,3,7,11,15), 或是 ∑(1,3,5,7,11,15)

(方便化簡)

# 期末

## 3-7 Other Two-level Implementations
AND/NAND/OR/OR 有16種two level form (2^4)

這八種能退化至一個operation
AND-AND -> AND
OR-OR -> OR
AND-NAND -> NAND
OR-NOR -> NOR
NAND-NOR -> AND
NOR-NAND -> OR
NAND-OR -> NAND
NOR-AND -> NOR

這八種不行
AND-OR (SOP)
NAND-NAND (SOP)
OR-AND (POS)
NOR-NOR (POS)
AND-NOR/NAND-AND (AOI)
OR-NAND/NOR-OR (OAI)

#### 建立方法
- AND-OR
F = x'y'z' + xyz' (SOP of 1's)

- NAND-NAND (拿AND-OR 外demorgan)
F = ((x'y'z')' (xyz')')'

- OR-NAND (拿NAND-NAND 內demorgan)
F = ((x+y+z)(x'+y'+z))'

- NOR-OR (拿OR-NAND 外demorgan)
F = (x+y+z)' + (x'+y'+z)'

---

- OR-AND
F' = x'y + xy' + z (SOP of 0's)
F = (F')' = (x + y')(x' + y)z'

- NOR-NOR (拿OR-AND 外demorgan)
F = ((x+y’)’ + (x’+y)’ + z)’

- AND-NOR (F'的NOT)
F = (F')' = (x'y + xy' +ｚ)’　（AND-NOR)

- NAND-AND (拿AND-NOR 外demorgan)
F = (x’y)’(xy’)’(z)’

## XOR

x ⊕ y (XOR)
= xy'+x'y (AND-OR-NOT)
= ((xy)’x)’ ((xy)’y)’)’ (NAND)

(x ⊕ y)' (XNOR)
= xy + x'y'

### Odd and Even Function

Odd : F = A⊕B⊕C
Even: F = (A⊕B⊕C)'

### Parity Generation

even-parity:
讓資料跟P 1的數量是偶數

#### Parity Bit
P = x⊕y⊕z

#### Parity Check
C = P ⊕ P

C = 1 -> odd number of 1's bit error
C = 0 -> correct or an even number of 1's bit error


# Chapter 4 - Combination Logic

## Combination circuits

ex. Adders, subtracters, comparators, decoders, encoders, multiplexers

## Analysis of Combinational Circuits x

## Design Procedure x

## Binary Adder-Subtractor

### 半加器 (Binary Half Adder)

將兩個一位元二進制數相加

0 + 0 = 00
0 + 1 = 01
1 + 0 = 01
1 + 1 = 10

S (和)
S = x’y + xy’ = x ⊕ y
C (進位)
C = xy



### 全加器 (Binary Full Adder)

將兩個一位元二進制數相加，並根據接收到的低位進位訊號，輸出和、進位輸出

x, y: two significant bits
cin: 低位進位

S = x ⊕ y ⊕ cin
C = x y + y cin + cin x



#### 用 Half Adder 實作 Full Adder

S = x ⊕ y ⊕ cin
C = z(x ⊕ y) + xy


### 行波進位加法器 (Ripple Carry Adder)

一堆 FA 串一起


### 前瞻進位加法器 (Carry Lookahead Adder) x

### Binary Adder/Subtractors

M=0 : addition
M=1 : subtraction

#### Overflow

兩個正數相加 -> 負數 (超出整數範圍)
兩個負數相加 -> 正數 (超出富庶範圍

V = 1 : overflow
V = 0 : overflow


## 十進位加法器 (Decimal Adder) x

## 乘法器 (Binary Multiplier) x

## Magnitude Comparartor x

## Decoders

n input variables -> 2^n outputs


- 1 to 2 line decoder

D0 = x'
D1 = x

- 2 to 4 line decoder

b0 = a1' a0'
b1 = a1' a0
b2 = a1 a0'
b2 = a1 a0

### Enabling

允許訊號傳遞 (用AND)

EN = 0 -> out = 0
EN = 1 -> out = in

out = in * EN

| EN | in | out |
| -------- | -------- | -------- |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |

## Encoders
inverse function of a decoder


z = D1 + D3 + D5 + D7
y = D2 + D3 + D6 + D7
x = D4 + D5 + D6 + D7

### Priority Encoder (x)

## 多工器 (Multiplexers)

從多個input中，選取一個input，直接輸出

ex. 4 to 1 multiplexer

function table:

boolean expression:
Y = s0' s1' I0 + s0 s1' I1 + s0' s1 I2 + s0 s1 I3

circuit diagram:

MUX = Decoder + OR

### Boolean Function Implementatiton

Ex. F = Sigma(1,2,6,7)

有兩種做法
1. n 個 select input ， 2^n 個 data input
2. n-1 個 select input ， 剩的變數為 data input

select input: x, y
data input: z



## Three-state gates

三種輸出:
0, 1, high-impedance


### 用Three-state gates 實作多工器

# Chapter 5 - Synchronous Sequential Logic

## Latches

### NOR

S R -> Q
0 0 -> Keep
1 0 -> 1
0 1 -> 0
1 1 -> invalid


### NAND

S R -> Q
1 1 -> Keep
0 1 -> 1
1 0 -> 0
0 0 -> Invalid


### D Latch

En D -> Q
0 X -> No Change
1 0 -> 0
1 1 -> 1


## Flip Flops

### 負緣觸發 D 型觸發器 (Negative Edge-Triggered D flip-flop)

clk D -> Q（下一狀態）
0 X -> No Change
1 0 -> 0
1 1 -> 1


### 正緣觸發 D 型觸發器 (Positive Edge Triggered D flip-flop)


clk D -> Q（下一狀態）
0 X -> No Change
1 0 -> 0
1 1 -> 1