---
# System prepended metadata

title: 課程｜計算機概論
tags: [課程]

---

# 計算機概論

## 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
    
    