---
title: "計算機 (Computer)"
path: "計算機 Computer"
---

{%hackmd @RintarouTW/About %}

# 計算機 (Computer)

從數學的觀點上看，現代極其複雜的電腦，根本原理其實和算盤差異不大。
真正的差別在於「開關速度」。

在半導體與真空管之前的工業革命時代 則以機械式齒輪 (Gear) 來做計算，甚至紡織機可被視為現代電腦的前身。

二進位的電腦，也可以說是一堆「開關」所組成的狀態機（從一個狀態到另一個狀態），這也是 Turing 高度抽象思考後的結論，即 Turing machine (圖靈機)。

二進位藉由「兩種不同的狀態」來儲存所對應的資訊（0 & 1），當人們只用 0 & 1 來解釋電腦時，其實也已經是抽象化到數學層次後的描述。實際上所謂的邏輯閘，就和每個人家裡的電燈開關一樣，差異是由高低電壓變化決定開或關（電流通或不通），再以電路設計（真正的邏輯所在之處）進行二元邏輯運算 (AND/OR/NOT/etc...)。

## 邏輯閘 (Logic Gate)

<center><img src="https://i.imgur.com/3iPWSIa.png" style="width:70%"/></center>

Gate (閘) 說穿了就是開關，如 Water Gate (水閘門)。其實就字面意義上來說，Logic Gate 本來就是指由開關組合而成的邏輯，開關的動作變化是為了完成邏輯。至於開關是什麼東西做的，何種型式，根本沒有關係，只要是能完成相同的邏輯皆可被稱為 Logic Gate 才是。

### 難道用水閘門也能計算？

是的，只要一個水閘門控制的水路能夠控制另一個水閘門的開關，經過適當的設計就能組合成 AND/OR/NOT 的邏輯運算水路，只是速度慢而已。

在工業革命之前，水鐘就是一種利用水力(與齒輪)的運算迴路。

> 題外話:Valve (閥門) 1920 Nikola Tesla Valve (Water, Air, A fluidic diode) Fluid Dynamics
(我猜連 Steam 的 Valve 八成也是特斯拉的信眾之一)

理論上，只要一個開關能控制另一個開關，就能實作出二元運算迴路來。

### 真空管時代

Vacuum Tube (真空管) 1873，只看過沒摸過的東西，僅知皮毛不敢妄言。

### 半導體時代 (Semi-Condoctor)

介於導體與絕緣體之間的半導體，就是一種人造開關，目的和真空管一樣，本身能被電壓控制開或關，而其開或關則又能控制另一電路上的開或關，只要能夠完成這個最基本的要求即可以被組合成邏輯閘，最後再由邏輯閘組合成運算單元（如加法器），再一層層組合成更複雜的模組。

### 二極體

<iframe width="560" height="315" src="https://www.youtube.com/embed/Fwj_d3uO5g8" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

Diode (二極體) 1874, 單向導通, 1899 Patent, 整流橋接 (如交流轉直流)
LED - Light Emitting Diode (發光二極體)
Photodiode (光電二極體) 光發電 (太陽能板)、測光器 (紅外線遙控)
1887
1905 愛因斯坦 (Photoelectric Effect) 光電效應論文, 1921 諾貝爾獎

### 三極體/電晶體

三極體 (Transistor) 1907, 由基極控制的開關 (Emitter, Collector, Base) 或放大器

MOSFET (Metal-Oxide-Semiconductor Field-Effect Transistor) 場效電晶體
PMOS (P Channel - NPN) P型
NMOS (N Channel - PNP) N型
CMOS (Complementary MOS - PMOS + NMOS)

### 積體電路 IC (Integrated Circuit)

> 雖然不知為何翻成積體二字，明明 Intergrated 是整合之意，積非成是，已見怪不怪了。

電路設計，正如之前所言，真正形成邏輯的地方在於電路，而其根本則是大家小學就學過的串聯與並聯。

串聯：皆通方能通
並聯：皆斷方才斷

就是如此單純的兩個基本概念即可組合成 AND/OR/NOT 的基本邏輯閘：

>（此處僅為概念性的論述，而非實際實作方式-NAND/NOR。）

#### AND Gate

| Input1 | Input2 | Output |
| ------ | ------ | ------ |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |

要完成 AND Gate，只需將兩輸入串聯即可。

#### OR Gate

| Input1 | Input2 | Output |
| ------ | ------ | ------ |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |

要完成 OR Gate，只需將兩輸入並聯即可。

#### NOT Gate

| Input | Output |
| ----- | ------ |
| 0 | 1 |
| 1 | 0 |

輸入控制的電路與輸出電路同時並聯在一起，當輸入控制的電路斷路之時，電流只能往輸出電路走，即輸入 0 輸出 1。
當輸入控制的電路為通路時，也只需要加一電阻在輸出電路上，造成比輸入控制的電路需要更高的電位，即可完成輸入 1 輸出 0。

## 加法器 (Adder)

### 半加器 (Half Adder)

<center><img src="https://i.imgur.com/6fPGEFp.png" style="width:30%;filter:invert(0.8)"/></center>

<center>此圖來自維基百科</center>

半加法器不考慮第三個輸入(即前一位的進位)，只能計算一個位元的加總和進位。既然有半加法器，自然有全加法器，也可以由兩個半加器組成起來完成，一樣由簡入繁。

#### Sum bit (合位元)

大概沒人這麼翻，我自己倒是挺滿意叫「合位元」的。

| Input1 | Input2 | Output |
| ------ | ------ | ------ |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

其實就是所謂的 Exclusive OR (XOR Gate)，當兩個輸入值不同時才會是真。透過兩組相反開關分別並聯在輸出電路上，兩輸入電路各控制一組相反開關，於是只有兩輸入值不同時，輸出電路才會導通。

用文字說明很難達意，倒不如看繼電器電路更容易理解。

如下圖 A, B 為輸入， Y 為輸出。
<center><img src="https://i.imgur.com/mF6PafR.png" style="width:30%;filter:invert(.8)"/></center>

<center>此圖來自維基百科</center>

#### Carry bit (進位元)

一樣沒人這麼翻，與合位元相對，進位元也不難理解。

再加上 Carry bit 輸出，一個 AND Gate 就能搞定。

| Input1 | Input2 | Output |
| ------ | ------ | ------ |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |

### 全加器 (Full Adder)

考慮到前一位元的進位元，於是需要三個輸入 Input1, Input2 和 CarryIn，輸出則仍是合位元和進位元兩個。

| Input1 | Input2 | Carry In | Sum | Carry Out |
| ------ | ------ | -------- | --- | --------- |
| 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 |

Sum 可以由兩個半加器來串聯，Input1 和 Input2 做為第一個半加器的輸入，而輸出的合位元則可接到第二個半加器的輸入一，再加上 CarryIn 做為第二個半加器的輸入二。

$$
\begin{cases}
HA1_{Sum} = {In_1}\ XOR\ {In_2}\\
HA2_{Sum} = HA1_{Sum}\ XOR\ C_{in}
\end{cases}
$$

做完就會發現，其實這根本就是

$$Sum = In_1\ XOR\ In_2\ XOR\ C_{in}$$

也就是三個輸入裡有偶數個 1 就會是 0，有奇數個 1 就會是 1，其實大部分人在寫真值表時也是以此邏輯在運算，只不過多數人不自覺而已。

Carry 部分也很簡單，就是三個輸入裡若有兩個為 1，就要進位，排列組合就只有三種情況，只要符合其中一種就輸出 1。

$$三個輸入
\begin{cases}
In_1\ AND\ In_2\\
In_1\ AND\ C_{in}\\
In_2\ AND\ C_{in}
\end{cases}
$$

再把他們都 OR 起來即可。

$$Carry = (In_1\ AND\ In_2)\ OR\ (In_1\ AND\ C_{in})\ OR\ (In_2\ AND\ C_{in})$$

寫是寫完了，但這種表達式又長又累，這也就是為什麼邏輯電路設計裡有一組符號來做 $AND/OR/NOT/XOR$ 等等的表達與運算規則，其實這些邏輯本質不管硬體還是軟體都是一樣的。

## 邏輯運算符號 (Logic Operator)

| Operator | Logical | C Language (bit operation) | Hardware |
| -------- | --------- | -------------------------- | -------------------- |
| AND | $\land$ | & | $\cdot$ |
| OR | $\lor$ | \| | $+$ |
| NOT | $\lnot$ | ~ | $A'$/ $\overline{A}$ |
| XOR | $\veebar$ | ^ | $\oplus$ |

更多可參考
https://en.wikipedia.org/wiki/List_of_logic_symbols
https://en.wikipedia.org/wiki/Logical_connective

全加器重新用 Logic Operator 表達

$$
\begin{cases}
Sum &= In_1\ \oplus\ In_2\ \oplus\ C_{in}\\
Carry &= In_1\ \cdot\ In_2\ +\ In_1\ \cdot\ C_{in}\ +\ In_2\ \cdot\ C_{in}
\end{cases}
$$

真的清爽美多了～

## 補數減法

有了加法器，也需要再重新專門設計減法器？其實減法可以透過補數與加法器來完成。

$$
A - B = A + (N-B) - N
$$

N 是指 N 進位，(N - B) 就是 B 的補數。

以 10 進位為例，

$$
8 - 3 = 8 + (10 - 3) - 10
= 5
$$

### 補數的直覺理解

光從數學式上很輕易可以證明是對的，但我們有什麼直覺的方式來理解補數呢？

<img src="https://i.imgur.com/ADCz1e8.png" style="filter:invert(.9)"/>

其實只要把 N 進位想成一杯刻了 N 個刻度的水杯，今天有兩杯水，一杯水位在刻度 A，一杯則在刻度 B，想要知道刻度 (A - B) 的水位差，但只能透過加法來完成，只要同時在 A, B 兩杯水中一起加水，直到 B 加滿了，A 這杯水滿出來的部分，就是 (A - B) 的水位差。

用以上的對於水位的描述，也更能幫助理解硬體中所謂的溢位 (overflow) 是何意義。

### 為什麼用補數?

一般人習慣十進制會感覺補數好像更麻煩了，但二進位的補數卻很簡單，比如 101001 的補數就是 0 變 1, 1 變 0，每個位元都反過來就可以得到一的補數 (01110)，對硬體而言實作起來快速又簡單，複雜度更低。而真正二的補數則是把得到的一的補數再加 1 即可。

## 算術邏輯單元 (Arithmetic Logic Unit)

到目前為止，實作了加法和減法，當然也有乘法器，不過我更想講的是整個計算機的架構與原理的概念，而不是針對某一項深入研究。

總之我們把加減乘除(含浮點運算) 統稱為「算術邏輯單元」，簡稱為 ALU。
就是 CPU 裡執行基本四則運算的單元，而 CPU 裡除了 ALU 外，還有 Control Unit，即控制整個輸入、輸出，錯誤時該怎麼辦，有中斷時又該如何等等的控制系統。

## 控制單元 (Control Unit)

所謂的程式，包含組合語言，最終也都得轉換成二進位存放在記憶體裡，CPU 只能透過 MMU (Memory Management Unit) 存取記憶體裡的資料，而資料就分成兩種，一種是指令集，另一種則是指令集指定要處理的真正需要運算的資料，這些資料則會被 CPU 載入到資料暫存器 (Data Registers) 中，讓 ALU 來做真正計算的工作。

> 此處並未細述 Instruction Fetch/Decode/Execution 等 pipeline，而是簡單以執行二字替代。

### 指令集 (Instruction Set)

二進位的 Instrusction 則稱為 Operation Code (簡稱 opcode)

程式被組譯成指令集，本身就是告訴控制單元，接下來該做些什麼事。當然現代 CPU 已非常複雜，絕非三言兩語可以概述，但總得來說概念上是如此。

## 記憶體管理單元 (Memory Management Unit)

主要就是在控管記憶體，由 Virtual Address 對應到 Physical Address，反之亦然。大家在大學時學的計組裡常提到的 Segmatation/Paging 基本上就是這個單元在負責的，實作上，這部分更多的是寫 BIOS/BootLoader/bootstrap 的人才會碰到的東西(即開機)，一旦啟始完成後(到至少能夠執行 C Runtime 後)，連 kernel 本身也不會沒事去動它。

> 當年玩 LinuxBIOS 這部分的記憶有點久遠了，也不知現在是否依然如此。
不行不行，得回歸正傳，若是再鑽進去，又要變成另一大篇了。

## SRAM (Static Random Access Memory)

記憶體種類太多了，SRAM 也是記憶體裡的一種，之所以在此提出就是因為它與 Flash 類的記憶體有著很不一樣的運作方式，CPU 就是存取 SRAM 裡的資料，因為 SRAM 才夠快(作為 DRAM 與 CPU 之間的 Cache 當然也就比 DRAM 要快才可以)，至於 Flash 裡的資料其實都是先搬到 DRAM 再到 SRAM 裡後再處理的。

為什麼稱之為 Random?

實際上在 RAM 出現之前，電腦是以磁帶 (跟傳統錄音帶一樣) 做為記憶體，所有程式與資料都是存在磁帶上，只能照順序(一維前進或後退) 讀寫運作，更貼近原本 Turing Machine 的描述，而不像 RAM 一般可以任意指定記憶體位置讀寫資料。

所以相對於傳統無法任意更改記憶體位置的系統來說，Random Access Memory 就是可以任意讀寫記憶體的意思。

## 暫存器 (Register)

對於 ALU/CU 來說，真正的資料輸入與輸出都是暫存器 (Register)，之後才會搬到 (S)RAM 裡。

CPU 裡對於記憶體暫存器的運作模型正是 Segment 為主，分作 Code(or Text) Segment/Data Segment/Stack Segment/Heap Segment，一個 Execution Context 就必須把這些暫存器裡的值都儲存下來後才能做 Context Switch 的動作。

若有寫過組語的人，對這些暫存器都不陌生才是。早年 286 - 586 時代，記憶體仍是很寶貴的資源 (用 MB 為單位計算的)，而隨便一個程式都會塞滿記憶體，所以如何有效分配與使用記憶體與 swapping 是非常影響效能的事，Segmentation/Paging 機制就是為此而設計。

不過如今隨隨便便連 Embeded 系統的記憶體都是 GB 起跳，Segmentation 就不重要了，大多 kernel 都會將各 Text/Data/Stack Segment Registers 都定成相同的，也就是全都在一個 Segment 裡了。

## Endian

分為 Little Endian 與 Big Endian 兩種，比如說

> 0xB3B2B1B0

在我們的表達式裡這是一個 32 位元 16 進位的數字(值)，但存放在記憶體中時，Little Endian 系統會以 "B0 B1 B2 B3" 連續四個 Byte 來存放，也就是以 least significant byte(LSB) first 為原則，記憶體位置也是由低 (Low) 到高 (High)。

而 Big Endian 則相反，以 most significant bye(MSB) first 為原則，會以 "B3 B2 B1 B0" 來存放在記憶體中，也就跟我們定義書寫 "0xB3B2B1B0" 時的順序一致；一般網路硬體的處理器多半都是 Big Endian 為主，因為網路傳輸時 packet 是以我們定義的方式傳送的，也就是會先傳 MSB，packet header 也是位於 MSB 裡，越早處理 header 越好，因為後面大部分 payload 的資料可以依照 header 裡的指定長度照搬即可，不用處理。

至於儲存在檔案之中的資料，也會指定是以何種 Endian 資料格式，這部分各種 File Format Specification 都會詳述，除非你要自己 Hack 也不難確定到底是何種 Endian，資料在不同的 Endian 系統中運作時是需要轉換的，不過現在寫的程式都很高階，很少人會自己去寫 (file or stream) parser ，寫 driver 或是寫 graphic library (不同 pixel format 轉換) 的人還是要注意處理 Endian 的問題。

:::info
Big-Endians/Little-Endians 原出自 1726 格列弗遊記 (Gulliver's Travels)，意指要打開一顆蛋時，應從大的一端或小的一端開始。1980 年，IEEE 借此意喻。
https://www.ling.upenn.edu/courses/Spring_2003/ling538/Lecnotes/ADfn1.htm
:::

###### tags: `computer` `gate` `logic` `endian`