# 數位邏輯
## 費曼學習法，教學文
### Preface
#### 如何自學:

1. 讀Objectives 知道要學什麼
2. 讀內文，寫Study Guide確定學會了
3. 寫後面的Problems
4. 再讀一次Objectives 確定是否讀通

這應該比雜誌厚1000倍吧...
恐怖的英文閱讀量

### 1.1 Digital Systems and Switching Circuits

在學習**Logic Design**前，我們先了解Logic Design在全部設計電路位在哪個地方。

電路是一團給電線走的路，藉由設計電路使我們可以控制電子的行為，達成特定的目的。至於電路的輸出，可以將電路分成digital跟analog。

**digital**的值是不連續的(現今是兩個state，不一定要數字，只要是被限制只能以state表示都行)，**analog**則是連續的(例如0.1, 0.2, 0.3, .. 4.7, 4.8, .. 0.1與0.2又可以分成0.11, 0.12 ...)。

相較於類比，**數位**比較準確，因為處理誤差的方式不同。**類比**的訊號如果有誤差，會原封不動地記錄起來，而**數位**的訊號如果有誤差，還是會調整成那些規定的符號。

Digital Circuits可分為三個層級，由低到高分別為**Circuit Design**, **Logic Design**, 和 **System Design**
**Circuit Design** 是研究用基本電子元件(電晶體、電阻等等)組合電路，**Logic Design**則是用基本邏輯閘搭建電路，**System Design**則是將系統分解成子系統並研究每個子系統在整個系統扮演什麼角色。

現在的Digital Circuit可以視為**Switching Circuit**，也就是一個有一堆開關在裡面的電路。
Switching Circuit有兩種: **Combinational Circuit** 跟 **Sequential Ciricuit**。
**Combinational Circuits**的輸出跟當下的輸入有關，而**Sequential Circuits**的輸出除了跟當下的輸入有關，也跟以前的輸入有關(有memory在電路中)。

現今的Digital Circuits都是以兩個state做運算，剛剛好符合boolean(true, false)跟binary(0, 1)，因此在學logic design前，需要先學會**布林運算**與**二進位**。

### 1.2 Number Systems and Conversion
#### 進位制

在了解**二進位**是什麼前，我們先了解什麼是**進位制**。

進位制是一個表示數字的方法，古時候的人們發明了九個數字，分別為0, 1, 2, 3, 4, 5, 6, 7, 8, 9。0表示沒有，1~9表示有的數量。但是只有十個數字只能表示十種數量，只要一超過9就無法表示了，因此，**進位制**就誕生了!當數到九，再也沒有符號可以表示時，我們在右邊寫一個1，而將9歸0，以10表示十，依此類推，19個下一個數字是20，99的下一個數字是100，109的下一個數字是110，當現有的符號不能再表示時，我們將左邊一位加一，這個就叫**進位制**。因為我們從時開始沒有表示的符號，因此叫**十進位制**。

當然，除了經典的**十進位制**之外，如果從八開始沒有表示的符號(只有0, 1, 2, 3, 4, 5, 6, 7)，我們叫**八進位制**，如果從二開始沒有表示的符號(只有0, 1)，我們叫他**二進位**。

那你可能會說，有沒有大於十的進位制?當然有，只是因為阿拉伯數子只有十個，因此我們須借用其他的符號表示，我們常用英文字母，例如**十六進位**，由零數到十五分別為0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E。

知道了進位制，接下來利用剛剛講述的規則用另一種角度看。至於為何要這樣，除了看起來比較專業之外，我們可以在其中看到更多奇怪的特性。

#### 另一個角度

首先，我們先觀察十進位的數字。我們先看一個數字: 
我們知道，這就是一個很基本的五，寫成數學式也是長的一樣: 
接下來，我們來看一個更難的數字: 
左邊的1是怎麼跑出來的呢？我們知道，左邊有一個1，是因為右邊已經沒有符號可以表示這個值了，因此需要在右邊的左邊再放置一個符號，每次自己超過可以表示的數量時，左邊就加一。因此，左邊這一個1不是表示一，因為他是因為右邊無法表示十，因此要表示十時，需要把9歸零，並在左邊加1。也就是說，這裡的1表示十，而13表示十加三，也就是十三。寫成數學式長這樣:
那呢，我們知道2是因為放3的位置無法承受大於十的數字，因此每次要表示十的時候，放2的位置都要加一。因此，我們知道123的2不是二，而是二十。至於1呢?1的存在是因為放2的位置承受不了大於十的數量，因此每當放2的位置每次要顯示十的時候，就會在左邊加一。放2的位置如果是9的話是九十，放十的話是一百，因此，這裡的1代表100。將其轉成數學式:
你會發現，因為每個位置最多只能放到九，只要一到十，自動會加一，因此每個位置的左邊每加一，就等於那個位置加十。我們可以把123改寫成這樣：
2563可以寫成: 
小數點也可以用這種方式表示歐，例如0.245呢可以寫成:
你會發現，這些式子都有10在裡面，這是**十進位**表示法的影子歐，有沒有覺得更了解**十進位**了?

#### 二進位

假設有一天，全世界的人都忘記2, 3, 4, 5, 6, 7, 8, 9這些數字的，只剩下0跟1，要如何表示各種數量呢？我們可以用之前提到觀念，每當某個位置要表示二的時侯，進一位(左邊位址加一)。例如，1的存在是因為放0的位置不能承受二，所以這裡的1表示二，換另一個角度看則長這樣。
難一點: 
最左邊的1的存在是因為其右邊承受不住2所導致的結果，而在中間的2存在是因為最右邊承受不住2，因此這裡的1是表示四(二乘二)，換個角度想則是這樣:
感覺是不是似曾相識?那二進位的呢?
沒錯就是
那小數呢，也是一樣的道理：
至於其他進位呢，只要把2全部改成你想要的進位制就可以了，請大家自己練習看看吧。

#### 轉換進位制

很好，終於打到這裡了。接下來，就是轉換進位制了，這也是考試會考的地方了。我們現在常用的進位制為**十進位制**，那如果要把數字的概念應用在現今的Digital Circuit上的話，那你必須學會如何將**十進位**轉成**二進位**跟將**二進位**轉成**十進位**。

##### 十進位轉成二進位

從"另一個角度"跟"二進位"，我們知道如何以另一個角度看待**二進位**數字跟**十進位**數字(是那個有一堆乘法和加法的超多餘式子歐)。接著，我們來利用它吧。
我們的目標是把一個**十進位**的式子表示成**二進位**的式子。~~如果你有去高中，並且上課沒睡覺，高一應該有學過餘數定理吧。是不是很像其中一題呢?~~(我都快忘了你們應該已經沒有記憶了吧)，總之列一個式子，我以把**十進位**9換成**二進位**為例:
只要求出a, b, c, d的值，就是九轉換成**二進位**的值摟。
至於要怎麼快速的求出值呢?先觀察等號右邊的式子:
我們把他除以2試試:
疑，我們把最靠近小數點的d弄出來了。接下來把d省略，再除一次2:
這次是c跑出來了，再除一次2:
再除一次2:
我們發現，藉由不斷的除以二，並求的其餘數，我們可以從最靠近小數點的數字，一個一個慢慢地算出來。
這次我們來對9動刀!
跟前面對照，我們可以知道:
記得先除所得到的餘數是最靠近小數點的值歐
但是你知道，小數點右邊也是有可能有東西的，例如: 
那這個怎麼辦呢?我們先用另一個角度看看他。根據上面，我們知道小數可以寫成這樣:
乘以2，我們會發現:
發現到什麼了嗎，我們發現當乘以2後，整數部分居然是最靠近小數點的值(這裡為a)。

> (為何只有a會顯現出來呢，是因為a, b, c, d等等只能是0跟1，因為那是二進位用另一個角度看，b, c, ...即使都是1，也沒辦法大於等於1)

我們把a拿掉，再乘一次2:
疑，離小數點第二個值，b，出現在正數部份了。
依此類推，後面也是不斷的乘以2，就可以求出欲求值的二進位了。

> 有時候是永遠除不完的歐，有可能有循環，~~這時候記得求到小數第三位就行了~~(
> 我算的辛辛苦苦結果答案直接求到小數第三位就停了 :( )

用剛剛的概念，解0.625的**二進位**表示吧。
記得先乘出來的數是靠近小數點的歐
那你可能問：那怎麼辦?

拆成整數的跟小數的，分開算，最後再把它整合起來。

##### 二進位轉成十進位

至於如何將**二進位**轉成**十進位**?

這個嗎，還記得**二進位**如何從另一個角度看嗎，例如:
把右邊爆開不就是你要的答案了?

##### 十進位轉其他進位制 與 其他進位制轉十進位

這個嗎，我打累了，把"**十進位**轉**二進位**"跟"**二進位**轉**十進位**"裡面所有的二換成你要的進位制，例如**八進位制**就把全部的二改成八，就行了。如果你們有問題，留言給我，我再打。

##### 其他進位制 轉 其他進位制

先轉成十進位再轉過去，其實有其他方法，但是很麻煩，跟傳換成十進位的方法一樣，只是計算的時候需要用你轉換前or轉換後的進位制之規則。

### 1.3 Binary Arithmetic

這邊講述如何用二進位做加減乘除，說實在，跟十進位一模一樣，只是你只有0跟1，導致你需要進位的時間跟十進位不一樣。
加法:
0+0=0
0+1=1
1+0=1
1+1=0 進位1

減法:
0-0=0
0-1= 這你需要跟左邊一位借
1-0=1
1-1=0

乘法:
0\*0=0
0\*1=0
1\*0=0
1\*1=1

除法:
0/0=0
0/1=0
1/0=沒定義
1/1=1

我來做幾道題目好了，你就會知道這有多簡單了。
如果還是不會的話，可以使用留言功能歐。
{%youtube DgfnJGQMRJI %}(啊我一開始放錯了XD)

### 1.4 Representation of Negative Numbers

#### 負數的表示法
在1.2跟1.3的時候，我們知道如何用二進位表示整數與小數。今天我們要了解如何用二進位表示負數。在這邊，我們只考慮整數。至於小數與分數等等，因為這本書沒有特別去講，所以呢？我也沒有辦法告訴你們。

負數其實就是在一個整數前面，加一個負號。簡單來說，如果我們可以在二進位最左邊加一個位元來表示正與符號不就可以表示負數了嗎？這種表示方式我們就叫做 **sign and magnitude**。用這個表示法之前，我們要先定義，這個數字要用幾個位元表示。假設是8個位元的話，最左邊的那個位元要用來表示正負號，而右邊的剩下7個位元則是來表示，它的大小。

我們習慣最左邊的位元，0為正號，1為負號。

這種表示方式我們就叫做 **sign and magnitude**。sign是指正負號，magnitude是指大小。

但是呢？這種表示法有一個缺點。在設計數位邏輯電路的時候呢，會不好設計。因為符號與大小需要分開處理，因此有人用**補數**來表示負數。補數有分兩種，一種是**基數的補數**，第二種是**減基數的補數**。
詳細部分可以自己去參考維基百科。

因為這邊我們使用了進位制是二進位，因此只有二的補數(**基數的補數**)與一的補數(**減基數的補數**)。
至於如何使用補數來表示負數呢？

轉換成**2的補數**:
公式、邏輯解、快速解、權重解 (影片)
轉換成**1的補數**:
公式、邏輯解 (影片)

記得要使用這些表示法之前，我們要先定義，這個數字要用幾個位元表示。
至於哪一種比較好呢？我們可以先把零附近的給列出來:
你會發現零這個數字，一的補數居然有兩種表示法，分別是1111跟0000
一個數字有兩種表示法會使設計電路的時候會有問題，因此這3種表示法二的補數最常用。

#### 值域

我們在前面提到，如果要表示負數的話，需要先定義，要用幾個位元表示，這樣表示負數的位元才不會亂跑，但這也會限制能呈現數字的多寡。現在我們就來探討這些表示法，在 n 個位元的時候呢，可以表示的數字。

##### sign and magnitude (符號與大小)

假設位元數有8個，因為最左邊要拿來表示正負號，因此表示大小的有7個位元。而7個位元最小呢是全部都是0，最大則是全部都是1，1111111在十進位是127。再加上正負號，我們的表示的數為-127到127。注意零有+0跟-0兩種表示法。現在不管多少個位元，你應該用這種方法，知道它的**值域**。

##### 1's complement (一的補數)

假設位元數有8個，一樣最左邊要拿來表示正負號。因為如果最左邊是一的話代表負數，且把正變成負，或是把負變成正，只需要把零變成一，一變成零就行了，所以最小值是10000000 (負的1111111)(-127)，最大值是01111111 (正1111111))(127)。值域跟 **sign and magnitude** 一樣。注意跟**sign and magnitude**一樣零有+0跟-0兩種表示法。

##### 2's complement (二的補數)

一樣，假設位元數有8個，最左邊也是拿來表示正負號。相較於**一的補數**，**二的補數**呢其實就是一的補數加1。因此要把負號(-127 ~ -0)對應的二進位全部再加上1(-128 ~ -1)。把正數與負號合併起來，就得到**值域**了(-128 ~ 127)。你也可以利用權重概念，先把最小的湊出來，再把最大的湊出來，就可以得到**值域**了。

#### 這些表示法的運算

基本上運算方式跟二進位的運算方式是一樣的，只是對待carry方式不一樣。二的補數是直接把 carry 忽略，而一的補數呢？則是在 carry 的時候呢除了把carry忽略還要再額外加一。

小心有時候算出來的答案不一定是正確的答案，因為每種表示法都有其**值域**，如果真的結果超出**值域**，算出來的答案會是錯的，稱為**overflow**。只有正加正或負加負的時候會發生 **overflow**。正加負或負加正的時候不會發生，因為加數與被加數也是被束縛在**值域**裡面(-128 + 1與127 + -1答案都沒有在-128 ~ 127的外面)

至於如何快速檢查有沒有發生 **overflow**，如果正加正得到答案是負的，或是負加負得到答案是正的，一定是 **overflow**。

至於如何用數位邏輯電路來檢查是不是 **overflow**，如果 carry 進最左邊一位跟 carry 出最左邊一位是不一樣的，那就是 **overflow**。


### 1.5 Binary Codes

在前面幾節，我們已經瞭解二進位相關的知識，我們知道二進位呢是電路所需要的數字表示法，但是呢輸入跟輸出的裝置，除了要讓機器看懂，要讓人們容易閱讀。因此需一種表示法，是由零跟一所組成的，而且也有十進位的成分在裡面，方便人們閱讀。我們現在所說的 **binary code** 就是為了滿足這個所需，至於他如何運作的呢？不是像我們前面學的把十進位轉成二進位，跟二進位轉成十進位，當成是一個數量來做轉換，而是逐字將一個數字把它轉換成由零跟一所表示的字串。假設有個數字，它是921，前面，我們會把921視為一個數量，並且用數量的概念把它轉換成二進位。但現在呢？我們要把921拆成'9', '2', '1'三個符號，再把每一個數字符號呢轉換成相對應的由零跟一所組成的字串，最後再把這些字串合併在一起，得到我們要的最後的結果。

接下來，我們要介紹一些把0到9十個符號，轉成由零跟一組成的字串的方法，這些方法我們叫做**binary code**。


**binary code**有非常非常多種(有興趣看這個 https://en.wikipedia.org/wiki/List_of_binary_codes )，這邊我們只舉四種，分別是**8-4-2-1**, **6-3-1-1**, **excess-3**, **2-out-of-5**, **gray code**。

**8-4-2-1**跟**6-3-1-1**都是以權重來做編碼。至於他是如何編碼的？看下面的影片。
(影片放置區)

**excess-3** 是把**8-4-2-1**的編碼，再加上3，目的是讓每一個位元出現1的機率都一樣。

**2-out-of-5**以五個位元來表示一個阿拉伯數字。這5個位元一定是兩個1和三個0所組成。這種編碼在除錯上會非常的容易，因為如果這5個位元不是有兩個1三個0所組成的，就代表有問題。

至於 **gray code**, 從表中，我們可以看到，每一個數字，他的上面跟下面只會有一個位元是不同的。

上面介紹的是專門放阿拉伯數字的編碼系統，當然，除了阿拉伯數字，還有的其他的符號。這個時候，我們就要介紹鼎鼎有名的**ASCII**，他以7個位元表示128個常見的符號。至於他怎麼排的呢？就是把先把所有的符號列出來，然後再給他們編碼。


如果你不喜歡這些編碼系統，你也可以自己造一個!只是功能性好不好，我就不知道了 :)

### 2.1 Introduction (Boolean Algebra)

我來練習錄影片，打字效率太糟了
記得"代數"是 algebra 不是 algrebra
{%youtube QFQFa64P0wA %}

---

如果有問題的地方，可以把字選起來，並使用留言功能，感謝你們。

## 學習表
### 前言
- [x] Preface
### Introduction: Number Systems and Conversion
- [x] 1.1
- [x] 1.2
- [x] 1.3
- [x] 1.4
- [x] 1.5
### Boolean Algrebra
- [x] 2.1
- [ ] 2.2
- [ ] 2.3
- [ ] 2.4
- [ ] 2.5
- [ ] 2.6
- [ ] 2.7
- [ ] 2.8
### Boolean Algrebra (Continued)
- [ ] 3.1
- [ ] 3.2
- [ ] 3.3
- [ ] 3.4
- [ ] 3.5
### Applications of Boolean Algrebra, Minterm and Maxterm Expansions
- [ ] 4.1
- [ ] 4.2
- [ ] 4.3
- [ ] 4.4
- [ ] 4.5
- [ ] 4.6
- [ ] 4.7
### Karnaugh Maps
- [ ] 5.1
- [ ] 5.2
- [ ] 5.3
- [ ] 5.4
- [ ] 5.5
- [ ] 5.6
- [ ] 5.7
### Quine-McCluskey
- [ ] 6.1
- [ ] 6.2
- [ ] 6.3
- [ ] 6.4
- [ ] 6.5
- [ ] 6.6
### Multi_Level Gate Circuits NAND and NOR Gates
- [ ] 7.1
- [ ] 7.2
- [ ] 7.3
- [ ] 7.4
- [ ] 7.5
- [ ] 7.6
- [ ] 7.7
### Combinational Circuit Design and Simulation Using Gates
- [ ] 8.1
- [ ] 8.2
- [ ] 8.3
- [ ] 8.4
- [ ] 8.5
### Multiplexer, Decoders, and Programmable Logic Devices
- [ ] 9.1
- [ ] 9.2
- [ ] 9.3
- [ ] 9.4
- [ ] 9.5
- [ ] 9.6
- [ ] 9.7
- [ ] 9.8
### Introduction to VHDL
- [ ] 10.1
- [ ] 10.2
- [ ] 10.3
- [ ] 10.4
- [ ] 10.5
- [ ] 10.6
- [ ] 10.7
- [ ] 10.8
- [ ] 10.9
### Latches and Flip-Flops
- [ ] 11.1
- [ ] 11.2
- [ ] 11.3
- [ ] 11.4
- [ ] 11.5
- [ ] 11.6
- [ ] 11.7
- [ ] 11.8
- [ ] 11.9
- [ ] 11.10
### Registers and Counters
- [ ] 12.1
- [ ] 12.2
- [ ] 12.3
- [ ] 12.4
- [ ] 12.5
- [ ] 12.6
### Analysis of Clocked Sequential Circuits
- [ ] 13.1
- [ ] 13.2
- [ ] 13.3
- [ ] 13.4
### Derivation of State Graphs and Tables
- [ ] 14.1
- [ ] 14.2
- [ ] 14.3
- [ ] 14.4
- [ ] 14.5
- [ ] 14.6
### Reduction of State Tables State Assignment
- [ ] 15.1
- [ ] 15.2
- [ ] 15.3
- [ ] 15.4
- [ ] 15.5
- [ ] 15.6
- [ ] 15.7
- [ ] 15.8
- [ ] 15.9
### Sequential Logic Design
- [ ] 16.1
- [ ] 16.2
- [ ] 16.3
- [ ] 16.4
- [ ] 16.5
- [ ] 16.6
- [ ] 16.7
- [ ] 16.8
### VHDL for Sequential Logic
- [ ] 17.1
- [ ] 17.2
- [ ] 17.3
- [ ] 17.4
- [ ] 17.5
- [ ] 17.6
### Circuits for Arithmetic Operations
- [ ] 18.1
- [ ] 18.2
- [ ] 18.3
### State Machines Design with SM Charts
- [ ] 19.1
- [ ] 19.2
- [ ] 19.3
### VHDL for Digital System Design
- [ ] 20.1
- [ ] 20.2
- [ ] 20.3
- [ ] 20.4
- [ ] 20.5

預估學習時間: 128天