數位系統導論 - 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

演算法效率與Big oh

要討論一個演算法的效率，可以從空間複雜度和時間複雜度兩方面來分析。

關於空間複雜度，指的是演算法所占用的儲存空間，可以考慮為固定空間與變動空間的總和。固定空間指的是程式用來儲存指令、變數、常數及結構等等所耗費的空間。而可變空間則涉及了程式的輸入大小，或者遞歸呼叫等等所要占用的空間，需要視解決的問題而更動。一般而言，程式所需的全部空間S(P) ＝Sp(I) + c，前者為變動空間，後者c為一常數，屬於固定空間。


關於時間複雜度，考慮的是演算法執行完成要花費多少時間，包括了編譯和執行時間，不過一個程式編譯後能執行多次而不需重新編譯，因此，我們真正關心的是程式的執行時間。至於如何得知執行時間？基本上有兩個方法，一是利用計時程式來幫助我們，例如引入<time.h>，不過這會因硬體設備產生偏差，二是土法煉鋼，計算出程式需要多少個步驟完成，但這又讓我們面臨一個新問題，如何定義一個步驟？
我們先暫且假設一個步驟等同於一個指令，意思是t++這種簡單的指令與t=t+3*a+4*b+5*c這種複雜的計算都為一個步驟，現在。我們已經能藉由一個變數來對一個程式記數，例如：


step告訴我們這個程式共花了103個步驟，如果將50改為一個自由輸入的變數n，那麼步驟總數即為2n＋3次。

題外話，你可能會很好奇為何int i沒有被列入step，因為從系統的角度來看，宣告一個變數只是在編譯時建立一個空間，並不會產生什麼對應的程式碼，除非在宣告時有分配一個值給變數。

不過還記得嗎？先前我們對步驟的定義一點也不精確，即便一行一行的慢慢數，也未必有助於估計效率。換句話說，既然從一開始就是估計，結果也是夠用就好，那麼夠用又是指什麼程度呢？如果從極限的角度出發，在n極大時，2n+3的3影響微乎其微，一兆與一兆零三元相差無幾，進一步而言，an^2+b與cn+d，我們不必精確知道常數a、b、c、d，代表什麼，因為函數的成長趨勢告訴我們，在n突破某個值後，前者所耗費的時間必定會超越後者。當然，不排除在n不夠大時考量效率會做出錯誤判斷，但通常我們在意的往往是相當大的輸入，而不是拘泥幾微秒的差距。

---

Big O notation


談時間複雜度，總是不能忘記他的老跟班Big-Oh，它是一個漸進符號，至於為什麼用Ｏ，有人說是代表Order，有人說是形容你看到它的表情。總之，Ｏ能夠描述函數漸進的趨勢，他的快樂夥伴還有Ω (omega)跟Θ(theta)，不過目前先介紹他們的老大。

1.Big-Oh定義：

f(n) = O(g(n))：存在常數Ｃ、Ｍ，對於所有大於Ｍ的輸入Ｎ，使得f(n)不大於Ｃ*g(n)

簡單來說，f(n)的成長速度不會超過g(n)，頂多跟他一樣快而已。
以上文舉例：f(n) = 2n+3，g(n)=n，則當N大於3時，f(n)不大於3*g(n)，我們便可以說f(n) = Ｏ(n)
再舉一個比較常見的例子：當N>5時，10n²+10 < 11n²，因此10n² +10 = O(n²)

「看，很簡單吧」。「我們在這裡沒有什麼錯誤，只有快樂的意外。」

g(n)怎麼來的？怎麼突然蹦出一個3？4不行嗎？4也是符合答案啊，教科書就這麼討厭4嗎？如果要亂入的話，我也能讓g(n)=99n，這樣我Ｎ＝1的時候也對呀，而且我答案還是f(n) = O(99n)耶。更傷心的是，它還舉了滿滿一頁的例子來嘲諷我，不禁令我回想起童年中那顆超級爆炸頭。

首先，範例就真的只是個範例，他沒有要你求任何東西。先回顧一下定義，f(n)的成長速度不會超過g(n)，換句話說，當n非常非常大的時候，f(n)一定會比g(n)矮，那如果我們把g(n)整形成g'(n)：

g'(n) = g(n)+1，f(n)會不會比g'(n)矮？會

g'(n) = g(n)+2，f(n)會不會比g'(n)矮？當然會

g'(n) = g(n)+2，f(n)會不會比g'(n)矮？肯定會

我們能一直＋＋＋＋＋出各式各樣的g'(n)，當然，g'(n)=2g(n)也是個可行的辦法，定義告訴我們：只要g(n)在座標軸的右端比f(n)高就成了，別去在乎他高了多少。照這樣看來，g(n)會有很多種可能囉？就定義上來看，沒錯，如果符合定義，我們就能舉出各式各樣的答案。

但是，這樣會導致一個問題，答案多樣性，它是生物多樣性的好朋友，常見於作業、考卷讓學生被當掉。
比方說 f(n)=123n+456，那我能說g(n)=n，g(n)＝n²，或者像g(n)=e^n2+5n+8這種奇葩函數，只要能找到適合Ｃ和Ｍ，都算是個解。為了解決這個問題，我們希望g(n)越小越好，如此它才最接近，也最能夠描述逼近的趨勢，所以當f(n)=123n+456n時，我們預期g(n)＝n，而不是n²，儘管這個答案是正確的。

說了這麼多，那要怎麼去預期？

最直觀地去想，找影響趨勢最大的就對啦，我們考慮的是極限，所以攻略目標是一個函式裡，極限值最大的那個，從成長趨勢的大原則說起，

多重指數函數 >  階乘 > 指數函數 > 多項式函數 > 對數函數 > 常函數