數位系統導論 - Binary System

#1.數位是什麼？而為什麼要數位？

先回答第一個問題，資料可以用兩種方法來表示，即是類比與數位，兩者最大的區別在於數值連不連續，其中類比是連續的，而數位是離散的。用一條1~5的數線來看，類比資料可以是其中任何一個點，比如1.3、0.1884251，但是數位資料可能只代表了整數點1,2,3,4,5，而在1跟2、2與3、3與4、4與5之間不容許其他任何值存在，只能透夠近似的方式把3.23之類的居中值分配給最接近的點。

而為何要數位呢？正如先前的例子，我們可以發現類比資料是無窮無盡的，比如1與2之間切半得1/2，再切1/4，可以這樣無窮的切下去，但是我們的硬體則是有限的，所以必須把類比資料數位化，方便電腦進行處理。

而多數的數位系統會用兩個離散值來表示狀態，比如

• 0 or 1
• True or False
• High or Low
• On or Off

#2.進位制表示法

2-1

一個N進位的數字1234.5678而言，可以寫作(1234.5678)_N
而他用十進位的值為：1*10³+2*10²+3*10¹+4*10⁰+5*10^-1+6*10^-2+7*10^-3+8*10^-4

十進位轉R進制：

• 整數部分：不斷除R，除完後取商繼續除，直到不能除為止，取餘數排列(除越多次者越高位)
• 小數部分：不斷乘R，乘完後取積繼續乘，直到小數化為整數，(乘最多次為最小小數位數)

2-2
二進位轉八進位：由右往左數，三個(2的三次=8)為一組
e.g. : 10101011 -> 10101011 ->  253
 
二進位轉八進位：由右往左數，四個(2的三次=16)為一組
e.g. : 10101011 -> 10101011 ->  AB

#3.

Signed Magnitude representation

• 第一位用來表示正負e.g. 000 = 0,101= -1
• 容易在運算在溢位

1's Complement representation

• 負數表示法：原值0與1互換
• e.g. 1011000 0100111
• 缺點是存在兩個0 (111與000)

• 1補數的減法 
• 所有的減法都透過與其補數相加達成
• e.g. a - b = a+(-b)
• 相加如果有在最高位元有進位，要將進位值補到最末位元
• 反之，沒有進位則代表真正答案為負，要再取一次原結果的一補數

2's Complement representation

• 表示法：取一補數再+1
• e.g.1011000 取一補數 0100111之後加一得 0101000

•  2補數的減法
• 所有的減法都透過與其補數相加達成
• e.g. a-b = a+(-b)
• 相加如果有在最高位元有進位，直接捨棄進位得答案
• 反之，沒有進位則代表真正答案為負，要再取一次原結果的二補數

---

1.Binary Code

• 每個bit可代表兩個情形(0&1)，則n bits代表了2^n種情形
• e.g. 10進位的數字0~9要區別可以使用4個位元(16種) 

Binary Code 表示法

• BCD 8421
• 2421
• Excess - 3 =BCD + 3
• 84 -2 -1
• 以上每個數字都代表著一個位元
• 比如數字4
• 8421 : 0100 = 8*0+4*1+2*0+1*0
• 2421 : 0100 = 2*0+4*1+2*0+1*0
• Excess -3 : 0111 : BCD+3 = 0100 + 3 = 0111
• 84-2-1: 0100 = 8*0+4*1+2*0+1*0

2.BCD

• 185 = (0001 1000 0101)BCD
• (a3,a2,a1,a0)BCD = 8a3+4a2+2a1+1a0
• BCD編碼並不是self-complementing code，這使得BCD雖然是最直覺的編碼方式，但在某些情形仍需要其他三種補足
• Self Compleementing

3.Gray Code

• 優勢：確保一次只有一個位元改變，使得充放電(可以想做0與1之間的轉換)較少也較省功耗

 設計數位系統必須考慮三樣要素：cost,speed,power，必須要在三者間求得平衡

4.ASCII Character Code

• American Standard Code for Information Interchange
• 運用7個組合表示128種字元

5.Unicode

• 2bytes

6.Error Detection/Correction Code

• 傳遞的過程可能發生Error
• 除了要偵測錯誤，還要把錯誤更正回來
• 使用方法 ： Even parity 與 Odd parity
• Even parity : 將原字元插入1，使其共有偶數個1
• 比如說 : 000插入0 （變為000-0，末位為parity），以維持0個（偶數個）1，001則要插入1，來維持2個（偶數個）1
• Odd parity :將原字元插入1，使其共有奇數個1
• 透過此法，能夠得知位元上的錯誤，比如說在傳送中將001-1誤傳為011-1，在Even parity的保護下，我們知道總共只能有偶數個1，從而得知傳送發生錯誤
• 但是，如果錯了很多個bits，parity bit就不太可行了

---

Binary Storage & Register

• Binary Cell

• 2 stable states,1-bit information(0 or1)

•  Register 暫存器

• 是一組binary cell
• 暫存需要處理或output的資料
• 暫存的資料可能有不同的編譯方式，例如01000001可能表示A or 65 or ......
• 其實暫存器就是由一堆邏輯閘構成的電路
• 暫存器是最快但容量最小的記憶體，位於最高的記憶體階層
• 依據暫存器的大小，可將處理器分為32bits與64bits

簡介資料結構與演算法

1.演算法

演算法是指令構成的集合，遵循這些指令能讓程式完成任務。通常演算法包會包含5個原則。

1. 有0~多個輸入資料
2. 至少要有一個結果
3. 每一個指令都要明確不含糊
4. 每一個指令都要是可行的
5. 在有限的步驟後便會結束，不會產生無窮迴圈

第五點也是一個程式跟演算法最大的不同，例如作業系統，除非系統當機，否則它將一直處於等待迴路中，直到有工作來臨。

1-1.以Selectioon sort為例

（ 這個for loop的目的是要找第i小的數字 ） 

for(i=0;i<n;i++){
Examine list[i] to list[i-1] and suppose that the smallist integer at list[min];
Intercange list[i] and list[min]
假設最小值出現於index min中，找到list[min]時，將list[i]與list[min]互換
}

1-2.以Binary Search為例

1. Given a sorted array list with n>=1 distinct integers, figure out if an integer seachnum is in list or not
2. 因為是排序過的陣列，所以利用中位數來進行搜尋，大則往後，小則往前，借此二分(binary)

while (there more integers to check)
{
 middle = (left+right)/2
 if(searchnum < list[middle]
    right  = middle -1;
 else if (search num == list[middle])
    return middle;
 else left = middle +1;
}

1-3.表示方法：

我們常常透過流程圖與虛擬碼來陳述一個演算法的步驟。值得一提的是虛擬碼，他介於口語與程式語法間，既能兼顧設計邏輯又可簡便表達演算法的內容。

2.Recursive Algorithm

• Direct recursion: 自己呼叫自己
• Indirect recursion: A呼叫B,B再呼叫A 

用於在問題本身是遞迴呼叫時（如階乘，費波那契）Recursive 最重要的是要決定跳出條件，以免造成Stack Overflow

3.Data Abstration

3-1簡介Data type

• Data type definition : A data type is a collection of objects and a set of operations that act on those object.
• e.g. int and arithmetic operations
• 程式語言內附的Data type稱為Predefined的Data type，使用者自行定義的則稱User-defined types ，但不是所有程式語言都會讓使用者創造User-defined data type
•  不論是哪一種類型的Data type，Data type都是由Object與Operation構成
• 就資料安全的角度來看，直接外露object給使用者是相當危險的，所以須透過operation處理

3-2 ADT

Definition: An abstract data type is a data type whose specification of the objects an the operations on the objects is separated from the representation of the objects and the implementation of the operations.

• 外漏給使用者看的只有specification，而specification並不一定要完成
• 抽象就是取出事物普遍性的本質，隱藏不必要的細節，只保留了目標必要的信息
• Catagories of function of a data type
• 建構式
• Transformers
• Observers/Reporters