# 計算機概論
## Overall View
* 從what到how do computer works。
* what是指知道如何透過高階層的指令，讓電腦做我們想做的事情。
* how是指知道電腦接受指令，軟體硬體怎麼配合做那些事情，也就是知道電腦底層在做的事情。
* 資工系的學生和外系差在知道how，知道底層memory,硬體如何運作，所以設計方法解決問題可能會更有效率。
## Coding
* 最底層是透過0跟1來儲存，可以減低大部分noise。如Morse code及Braille都是binary code。
* Morse code是透過長和短訊號來表示字元
* Braille是盲人點字系統，共有六個點透過凸和平來表示。
*
* 二進位來儲存非常方便，十進位是因為手指數目然後成為慣用，要熟悉兩個的轉換。 2^10 = k(千) , 2^20 = m(百萬) , 2^30 = G(十億)。
* 16進位是2進位的簡化版本，**可以把4個bit變成1個digit**。而1個byte=8個bit。
(32進位把5個bit變成1個digit不方便使用，且一個digit要有32種可能不好記憶)
*
* Unsigned Number
直接儲存，每個bit代表2的某個次方。
* Signed Number(看成是一種protocol，端看編碼系統規定如何)
* Sign+Magnitude：直觀，但有兩個0，且不行加法。
第一個bit代表正負號，剩下的bit就是unsigned number的值。
* 2’s Complement：
* 不會有重複數字
* 可直接加法，減法可用加法處理
* 第一個為signed bit
* 可以用MSB extend使bit數變多
正數：剩下的bit就是unsigned number的值。
負數：正負數之間關係為，取complement再加1(或是說$2^N$-x = -x)。
* 2's complement中 **-a 的表示法整理**
* 1.先把a表示出來，接著對所有bit取complement，接著加1。
* 2.不考慮signed bit，直接把2^n^-a這個正數寫出來
* 3.先把a表示出來，從右到左找第一個1，把此1左邊所有bit取complement
* Character sets(也可看成一種protocol)
* ASCII
* ANSI
* Unicode
* 實數 IEEE
## Logic
* 1.Boolean Algebra布林代數
* Boolean variables： 0 or 1
* Boolean Operation： and(乘), or(加), not(^--^)
* NOT>AND>OR
* 2.Define a function
* 1.Description，透過文字、自然語言去描述。
* 2.Algebraic form，透過代數去描述。
* 3.Enumeration，透過窮舉所有可能。
* 因為Boolean Function的variable只有0,1比較單純，可以透過窮舉去證明function，一般general的例子比較不容易達到。
* 3.Truth Table
* 用窮舉方式來表達Boolean Function。
* 一或多個Input, 一個Output。
* Number of Functions
* N input ->2^N^ rows -> 2\^2\^N functions
* Demorgan Law
* NOT(xy)=NOT(x)+NOT(y)
* NOT(x+y)=NOT(x)NOT(y)
* 給定任意F可以用來得到F'。
* Bubble Pushing
* Demorgan Law的應用
* 可以把AND gate轉成OR gate加上三個not
* 可以把OR gate轉成AND gate加上三個not
* 轉換的過程就像是在擠泡泡一樣
* Sum-Of-Product
* 系統性的，把任何Boolean Function，用且只用And,Or,Not表達。
* 1.先列出該Boolean Function的Truth Table。
* 2.對函數值是1的部分，用and term去表達，把所有input串起來。
* 3.把所有and term的結果or起來。
* Product-Of-Sum
* 系統性的，把任何Boolean Function，用且只用And,Or,Not表達。
* 1.先列出該Boolean Function的Truth Table。
* 2.對函數值是0的部分，用or term去表達，把所有input串起來。
* 3.把所有or term的結果and起來。
|x|y|Truth|
|-|-|-|
|0|0|0|
|0|1|0|
|1|0|1|
|1|1|1|
f = x~y + xy
f'= (~x+y)(~x+~y)
f = (x+y)(x+~y)
f'= ~x~y + ~xy
* 兩種方式比較及互相轉換
* 因為列出function的Truth Table之後，一個是關注0的部分，一個是關注1的部分，因此可以決定怎麼表達比較簡潔。
* f 和 f' 之間的轉換，可以直接透過demorgan's law，而且若一者為sop則另一者為pos。
* f 的sop和pos之間的轉換，通常要透過Truth Table，然後關注另外一部分。
* Universality
* 最基本的邏輯閘gate，可以組合出任何組合電路(Truth Table中的任何一種function)。
* {And, Or, Not}
* product of sum
* sum of product
* {And, Not}
* a|b = \~(\~a&~b)
* {Or, Not}
* a&b = \~(\~a|~b)
* {Nor}
* ~a = a nor a
* a|b = \~(a nor b)
* a&b = \~(\~a|~b)
* {NAND}
* ~a = a nand a
* a&b = \~(a nand b)
* a|b = \~(\~a&~b)
* 4.Digital System
* Analog：signal是連續的
* Digital：signal為0或1
* Accuracy and reliability.
* Staggeringly fast and cheap.
* 5.Controlled Switch 電磁開關(Relay)
* 透過電流驅動磁力影響另一條的電流
* Not：一個switch本身就是
* Nor：兩個switch串聯起來
* Or：兩個switch串聯起來，再加output取相反
* And：把兩個input先取相反，再把兩個switch串聯起來
* NAND：兩個switch並連起來
* **Principle of Information Hiding**
* 大部分的時候，我們不會在意電路內部怎麼設計的，我們只需要知道這個電路的，功能、input、output，然後可以正確地拿來使用就可以。
* Multiway Gate：也可以用2-input的類似形式，擴充到n-input。
* 6.Boolean Function to Circuit
* 運用sum of product技巧，可以只用and,or,not和wire去描述任何boolean function
* 1.用boolean variable去表示input及output
* 2.**列出function的truth table**
* 3.列出sum of product表示的boolean expression
* 4.直接把expression轉成circuit
* 7.Optimal Circuit
* 如果考慮**空間**：可能越少gate越好
* 如果考慮**時間**：可能length越短越好
* 也可能考慮：設計時間短，不容易犯錯，容易擴展
* 8.Hierachy Design
* 因為要達到時間越短或空間越少，的設計成本，可能太高了。
* 關鍵是：用**小部分兜成大部分**。
* 2bit or -> 4bit or
* 2bit and -> 4bit and
* 2bit xor -> 4bit xor
* 1bit 加法 -> 多bit 加法
* 9.Karnaugh Map(K map)
* 簡化電路方法，目標為使用更少的gate實現相同功能。
* 同樣可以選擇要關注0的部分或是1的部分。
*
* 一般的形式，可以用在2~4的變數情況，超過5個變數則要使用電腦輔助。
* 詳細的操作方法略，總之希望把某些bit的判斷省略。
*
* 之前有提到product of sum和sum of product，兩種電路實作起來的gate數是不一樣多的。
* 所以可以推測得知，Kmap的簡化電路，把大部分重複之處的地方刪除，但不能保證留下來的gate是最少的或最佳的。(化簡後仍可選擇用POS或SOP實作。)
* 10.Mux,Dmux
* Mux的功用是，依照selector的值，決定要把input的哪一部分傳給Output
* DMux的功用是，依照selector的值，決定要把input傳給Output的哪一部分，而Output其他部分為0
## ALU
* 1.**1-bit half adder**
* input：x, y
* output：sum, carry
*
* sum = x xor y
* carry = x & y
|x|y|sum|carry|
|-|-|-|-|
|0|0|0|0|
|0|1|1|0|
|1|0|1|0|
|1|1|0|1|
* 2.**1-bit full adder**
* input：x, y, Cin
* output：S, Cout
*
* sum = xor(x, y, Cin) = odd(x, y, Cin)
* carry = maj(x, y, Cin)
*
|x|y|Cin|Sum|Cout|
|-|-|-|-|-|
|0|0|0|0|0|
|0|0|1|1|0|
|0|1|0|1|0|
|0|1|1|0|1|
|1|0|0|1|0|
|1|0|1|0|1|
|1|1|0|0|1|
|1|1|1|1|1|
* 3.任意bit加法器都可以製作出。
* 也許會考慮用truth table然後用sum of proudct製作出電路，但4bit加法器就有2^9^=256列，128bit加法器就有2^257^列，在實務上是做不到的。
*
* 但可以考慮用hierachy的概念，用小元件組合成大元件。
* 兩個1-bit加法器，可構造成2-bit加法器。
* 兩個2-bit加法器，可構造成4bit加法器。
* ...，可構造出任意bit加法器。
* 4.減法一：**1-bit subtractor**
* input：x, y, bin(上一位有沒有像我借位)
* output：d, bout(我需不需要像下一位借位)
|x|y|bin|d|bout|
|-|-|-|-|-|
|0|0|0|0|0|
|0|0|1|1|1|
|0|1|0|1|1|
|0|1|1|0|1|
|1|0|0|1|0|
|1|0|1|0|0|
|1|1|0|0|0|
|1|1|1|1|1|
* 5.減法二：利用加法器做減法
* x-y = x+(-y) = x + (~y+1)
* 重複利用已經有的加法器
* input：x, ~y
* Cin=1
* 6.Shifter：
* input：x0\~x3,s0\~s3
* output：z0\~z3
* z0\~z3是x0\~x3經過向左shift之後得結果，shift的位數根據s0\~s3的哪一個bit是1來決定(保證只有一個是1)
*
* z0 = s0‧x0 + s1‧0 + s2‧0 + s3‧0
* z1 = s0‧x1 + s1‧x0 + s2‧0 + s3‧0
* z2 = s0‧x2 + s1‧x1 + s2‧x0 + s3‧0
* z3 = s0‧x3 + s1‧x2 + s2‧x1 + s3‧x0
* 根據這個關係是就可以做出對應的電路
* 7.N-bit Decoder
* 以上一個shifter例子來說，用s0\~s3來控制shift的位數，是很方便來實作shifter的電路，但
* 使用者不一定正確的輸入讓s0\~s3只有一個bit是1
* 這樣浪費硬體成本，2^4^->4種(其實只要2bit就夠了)
* Decoder的目的是，把二進位的數字轉換成特定一bit為1的形式。
* Input：N bit二進位數字
* Output：2^N^ bit 資料
* 在input數字的位置的bit為1，其他位置的bit為0
* 可以輕易地由sum of product 實作。
* 8.N-bit Encoder
* Encoder的目的是，把一串資料，挑出bit為1的位置，用二進位的數字表達。
* Input：2^N^ bit 資料
* Output：N bit二進位數字
* 挑出bit為1的位置
* 可以輕易地由and, or實作。
* 9. 1 HOT OR
* 處理有很多種運算，然後根據哪一條線是on起來選擇特定的那一個運算
* 方法就是
* 先把各個bit，選擇的線和運算的結果線and起來
* (因為選擇線只有一條會on，所以and起來後只有一條非0)
* 最後再把所有結果or起來
* 當然也有別種實作方法，但這樣很簡潔易懂
* 10.ALU(Arithmetic logic unit)
* CPU的執行單元
* 支援以下運算
* 加法和減法
* And
* Xor
* 左移和右移
* 11.Toy ALU
* Input：A[16], B[16], select[3], subtract, shift direction
* Output：Out[16]
*
|sel|2|1|0|
|-|-|-|-|
|加減|0|0|0|
|and|0|0|1|
|xor|0|1|0|
|位移|0|1|1|
|out=B|1|0|0|
* 電路會先把各種運算結果製造出來，最後再根據sel用one hot or選擇所要的作為Out。
* 12.Hack ALU
* Input：x[16], y[16], zx, nx, zy, ny, f, no
* Output：Out[16], zr, ng
*
* zx和nx，先後決定要不要把x設為零，要不要把x設為~x。
* zy和ny，同理。
* f = 1 表示 out = x+y，0則是x&y。
* zr表示out是否為0，ng表示out是否為負數。
|zx|nx|zy|ny|f|no|out|
|-|-|-|-|-|-|-|
|1||1||1||0|
|1|1|1|1|1|1|1|
|1|1|1||1||-1|
|||1||1||x|
|1||||1||y|
|||1||1|1|!x|
|1||||1|1|!y|
|||1|1|1|1|-x|
|1|1|||1|1|-y|
||1|1|1|1|1|x+1|
|1|1||1|1|1|y+1|
|||1|1|1||x-1|
|1|1|||1||y-1|
|||||1||x+y|
||1|||1|1|x-y|
||||1|1|1|y-x|
|||||||x&y|
||1||1||1|x\|y|
## Sequential Logic
* 1.Combinational circuits和Sequential circuits
* 理論上combinational circuit就可以組裝成一台電腦了，但是用到的硬體可能是exponential成長的，而且不能記憶之前的狀態。
* Sequential 電路，把Output接回來當作下一round的input。
* 因此有記憶的功能，或是說他有state概念。
* 需要有clock的幫忙
* 2.Flip-Flop
* 可以記憶一個bit的電路
* **是register、memory、counter的基本元件**
* 3.S-R flip flop
|S|R|Q~t~|
|-|-|-|
|0|0|Q~t-1~|
|0|1|0|
|1|0|1|
|1|1|X|
或是 Q=S+(~R)Q
|S|R|Q~t-1~|Q~t~|
|-|-|-|-|
|0|0|0|0|
|0|0|1|1|
|0|1|0|0|
|0|1|1|0|
|1|0|0|1|
|1|0|1|1|
|1|1|0|X|
|1|1|1|X|
* 電路和truth table可以互轉，雖然在sequential中比較複雜但仍然可以。
* SR flip-flop可以由兩個NOR實作
* SR flip-flop可以由電磁開關實作
* 但要注意到delay問題
* 4.D flip-flop
|Q~t~|
|-|
|Q~t-1~|
|Q~t-1~|Q~t~|
|-|-|
|0|0|
|1|1|
* 5.Clock
* 另外的裝置，用來處理delay問題
* 可以分成positive edge trigger或是negative edge trigger
* 只有在trigger的瞬間可以把訊號傳出去
* Clock用來控制電路的一致性，所有的sequential logic都會和clock相連。
* 以頻率為單位，代表一秒內有幾個cycle
* clocked SR flip flop
* input為 S,R,Clock
* output為 Q
* 在clock為1的瞬間Q會去判斷S或R的值
*
* 內部實際上是用Clock和S、R互相AND起來
* clocked D flip flop
* 直接透過clocked SR flip flop就可以實作
* input為 D, clock
* output為 Q
* 在clock為1的瞬間Q會等於D的值
*
* 實作方式是把D接到S，~D接到R
* 6.Register暫存器
* 把clock和write接起來，稱為enable write
* D flip-flop把clock位置input接入enable write，本身就是1bit的暫存器
* 同樣方式把D flip-flop串接起來就直接形成了n bit的暫存器
* 7.Register file暫存器堆
* 提供n register，每個bit是k bit
*
* 透過addr來identify我要存取哪一個暫存器
* 透過w來決定要不要從input寫入16bit。
*
* 實作方法為
* 把addr先decode之後，n個register中每個的clock input就是colck和w和addr一起AND起來，只有在這三條線都是1的時候才會更改到register的值
* 最後再用multiplexer根據addr決定要output哪一個register的值
* 8.k-wide-n-to-1-multiplexer
* k wide表示每個input有幾bit，n表示有幾種input選擇
* 先處理1-wide-n-to-1-multiplexer，透過truth table把sel對應的值和input AND起來，再把所有可能OR起來就得到。
* 只要把input每個bit用一個1-wide-n-to-1-multiplexer處理即可得到k-wide-n-to-1-multiplexer。
* 9.Memory
* 簡易的memory component包含
* Register
* Main Memory
* Program Counter
* 可以用register file方式實作memory，但是這樣製作成本會很高，真實世界的memory都是用DRAM來達到，而且位置會離CPU很遠。
* Toy Machine中
* Word ： 16bit
* Memory address ： 8bit (256個memory)
* Register name ： 4bit (16個register)
*
* program counter (PC)：存8bit的記憶體位置
* instruction register (IR)：存16bit的instruction
* 10.Memory Bank
* n個register，每個k bit
* 透過input address來指出要access哪一個register，並且output該register的值
* 透過w決定是否要更改該register
* Toy Machine中
* 256-by-16 main memory
* 16-by-16 register
## Toy Machine Programming
* 1.Introduction
* General-purpose，理論上能夠做到任何一台電腦能做到的功能
* 只是說會受到memory和time的限制
* 范紐曼型架構，也就是code和data會放在相同位置，這種電腦稱為**儲存程式電腦**。
* 2.Toy Machine 包含
* Switches
* Light
* Memory ： 256 by 16 bits
* Program counter ： 8 bits
* Registers ： 16 by 16 bits
* Arithmetic-logic unit(ALU)
* Standard input, standard output
* 3.Program and Data
* Program是由多行instruction組成，儲存在記憶體，每一行就是16bit通常是從10開始儲存。
* Data是由16-bit word組成，通常存在memory前面00到0f。
* program counter(PC)會記錄現在要執行哪一行instruction，一開始會initial成10。然後每次會把該行instruction讀到instruction register(IR)裡面執行。
* 4.Instruction( Machine Code如何表達)
<table>
<tr>
<td>-</td>
<td>15</td>
<td>14</td>
<td>13</td>
<td>12</td>
<td>11</td>
<td>10</td>
<td>9</td>
<td>8</td>
<td>7</td>
<td>6</td>
<td>5</td>
<td>4</td>
<td>3</td>
<td>2</td>
<td>1</td>
<td>0</td>
</tr>
<tr>
<td>Fmt1</td>
<td colspan="4">op code</td>
<td colspan="4">dest d</td>
<td colspan="4">source s</td>
<td colspan="4">source t</td>
</tr>
<tr>
<td>Fmt2</td>
<td colspan="4">op code</td>
<td colspan="4">dest d</td>
<td colspan="8">addr</td>
</tr>
</table>
op|FMT|Instruction
-|-|-
0|1| halt
1|1| add
2|1| subtract
3|1| and
4|1| xor
5|1| shift left
6|1| shift right
7|2| load address
8|2| load
9|2| store
A|1| load indirect
B|1| store indirect
C|2| branch zero
D|2| branch positive
E|1| jump register
F|2| jump and link
* 5.一些常見指令寫法
* LOAD和STORE
* 70XX，直接讀constant XX到R0
* 80XX，把mem[XX]的值，讀到R0
* A00Y，把mem[RY]的值，讀到R0
*
* 90XX，把R0的值，寫入mem[xx]
* B00Y，把R0的值，寫入mem[RY]
* 第FF的memory位置為stdin、stdout位置，可以和使用者互動。
* 9xFF：從stdout寫
* 8xFF：從stdin讀
* JUMP
* C0XX：直接跳到YY位置
* E和F是一組的
* FFXX：跳到XX位置，並把return address存在RF
* EF00：跳到RF所存的return address位置
* 70XX：把constant XX 讀到R0裡
* 0000：停止，確保程式不會執行預期外code
* 1AB0：A = B+0，有move效果
* 1000：No operation，有時候會需要。
* 6.加法
```clike=
// C = A + B
10: 8A00 RA ← mem[00]
11: 8B01 RB ← mem[01]
12: 1CAB RC ← RA + RB
13: 9CFF mem[FF] ← RC
14: 0000 halt
```
* 7.乘法
* 可以用連加法來實作，但是loop可能會跑太多次
* 可以用shift來實作，
```clike=
14: CA18 if (RA == 0) pc ← 18
15: 1CCB RC ← RC + RB
16: 2AA1 RA ← RA - R1
17: C014 pc ← 14
18: 9CFF mem[FF] ← RC
19: 0000 halt
// a存在RA，b存在RB，c存在RC
int c = 0;
while (a != 0) {
c = c + b;
a = a - 1;
}
```
* 下面的例子，因為要處理>=的情況，所以只能用do while形式來寫
```clike=
15: 2221 R2 ← R2 - R1 //i--
16: 53A2 R3 ← RA << R2 //a<<i
17: 64B2 R4 ← RB >> R2 //b>>i
18: 3441 R4 ← R4 & R1 //(b>>i) & 1
19: C41B if (R4 == 0) goto 1B
1A: 1CC3 RC ← RC + R3 // c + (a<<i)
1B: D215 if (R2 > 0) goto 15
1C: 9CFF mem[FF] ← RC
1D: 0000 halt
// i 初始成16，R1永遠是1
int c = 0;
for (int i= 15; i >=0; i--)
if (((b >>i) & 1) ==1)
c = c + (a << i);
```
* 8.其他例子
* Fibonacci
```clike=
12: 9AFF print RA
13: 1AAB RA ← RA + RB
14: 2BAB RB ← RA - RB
15: C012 goto 12
16: 0000 halt
//b初始成0，a初始成1
//b' = a ;
//a' = a+b ;
```
*
* read and sum
```clike=
11: 8AFF read RA
12: CA15 if (RA == 0) pc ← 15
13: 1CCA RC ← RC + RA
14: C011 pc ← 11
15: 9CFF write RC
16: 0000 halt
//sum存在RC裡，初始成0
//程式直到讀到0000才停下來
```
*
* Reverse
```clike=
//讀到0000為止，存在mem RA之後連續位置
13: 8CFF read RC
14: CC19 if (RC == 0) goto 19
15: 16AB R6 ← RA + RB
16: BC06 mem[R6] ← RC
17: 1BB1 RB ← RB + R1
18: C013 goto 13
//從讀到的最後位置開始，印出直到RA位置
19: CB20 if (RB == 0) goto 20
1A: 16AB R6 ← RA + RB
1B: 2661 R6 ← R6 – R1
1C: AC06 RC ← mem[R6]
1D: 9CFF write RC
1E: 2BB1 RB ← RB – R1
1F: C019 goto 19
20: 0000 halt
```
* 9.Buffer overrun
* 當程式設計不當，使得array明明宣告固定size，使用者卻可以更改到更大的size時
* 使用者可能可以巧妙設計，讓原程式執行使用者輸入的指令
* 此時程式就lose control
* 許多viruses and worms都用此種技巧
## Toy Machine Architecture
* 1.複習現在有的元件
* ALU
* 兩個16 bit INPUT，一個16bit OUTPUT
* 功能為：由3+2bit來控制
* Add/subtract,
* and,
* xor,
* shift left/right,
* copy input 2
* k wide n to 1 Multiplexer
* 把n to 1的1 bit multiplexer重複k bit。
* Flip Flop
* SR flip flop可以組裝成D flip flop
* Register
* 把DFF再加上write enable控制
* Register file
* 多個register一起記憶，在透過multiplexer決定要對哪一個register操作。
* 這裡的register file提供**dual read**，也就是可以一次讀出兩個直給ALU使用，因為指令常常會需要。
* Memory
* 可以直接用register實做
* Clock
* positive edge trigger
* on: fetch phase
* off: execute phase
* 2.如何建構processor
* Develop instruction set architecture (ISA)
決定要有那些指令，每個指令的規格、形式為何
* Determine major components
決定完成這些功能需要使用那些元件
* Determine datapath requirements
看看data在這些元件的先後順序，適時使用memory和multiplexer
* Analyze how to implement each instruction
設計control讓元件達到正確功能
* 3.4bit Counter 的architecture
input|semantic|
-|-|-
00|c=0|
01|c=in|
10|c=c+1|
11|c=c-1|
* 4.Stack 的architecture
W|OP|operation
-|-|-
0|0|read
0|1|top
1|0|push
1|1|pop
Sign in with Wallet
Connect another wallet