---
title: 計算機編碼
description: 從數學的觀點去解釋編碼的原理
---

# 解讀計算機編碼

:::success
對於數字的加減運算，人腦可以快速的在腦中辨識符號並快速算出結果。但是電腦只認得`0`和`1`，卻不曉得+和-在數學上的意義是甚麼。於是我們引進了補數的概念，來表達二進位系統中的正負數。但是為何二補數廣泛應用?背後的設計考量是甚麼?本篇筆記會嘗試使用淺顯的數學觀點去解釋編碼的原理，並用圖像幫助記憶。
:::

## Part1 : 直觀的編碼設計有甚麼問題?

我們知道實數有正和負兩種符號，但是電腦只認得`0`和`1`，沒有用來表示正負號的方式。那麼一個直觀的解決方式就是挪用最高有效位元(most significant bit i,e, MSB)來表示正負號，在[big-endian](https://en.wikipedia.org/wiki/Endianness)的表示法中，MSB就是最左邊的位元，負數的MSB為`1`，正數的MSB為`0`。以下用`8`個位元二進位數的來舉例:
> 35~10~ = 00100011~2~
> -35~10~ = 10100011~2~

承上，如果使用8個位元來表示數字，因為需要保留一個位元來表示正負號，所以這個直觀的編碼方式能表達的範圍為:
> -(2^7^ - 1) = -127, -126, -125, ... -0, +0, ..., +125, +126, +(2^7^ - 1) = +127

上述的編碼方式雖然直觀並實際用於太空技術當中，但是因為以下的兩個缺點，導致被棄用:
1. 電路複雜
* 從前述運算法可見，「符號與值」的正負號位元不能直接參與運算，必須要單獨的硬體線路來確定正負號符號位元;
* 受限於額外的正負號位元，加法和減法需要各自的硬體電路才能實作：加法運算會產生「進位」(carry)，減法運算需要「借位」(borrow)，這兩種運算對應的硬體電路差異很大，需要額外的電路才可把加法器改造為減法器;
2. 0的表示不唯一
* 這種表示法導致有兩種方式表示0:
* ==0==0000000 (+0)
* ==1==0000000 (−0)
* 這實際增加數位電路的複雜性和設計難度，中央處理器也為此須執行兩次比較，才能確認運算結果是否為0;

## Part2 : 簡單回顧一補數(ones' complement)和二補數(two's complement)的計算

### 一補數
負數的二進位表示法為其絕對值二進位逐個位元做反轉，這樣的設計稱為一補數(ones' complement)，可以有效簡化加減法的運算，以下用兩個例子來說明一補數的運算規則，一樣都是`8`個位元的二進位數運算。

graph TD;
一補數-->將正數以二進位表示;
一補數-->將負數取絕對值以二進位表示再把每個位元翻轉;
將正數以二進位表示-->將兩數做正常的二進位加法;
將負數取絕對值以二進位表示再把每個位元翻轉-->將兩數做正常的二進位加法;
將兩數做正常的二進位加法-->若最高位有進位則把1加回LSB
將兩數做正常的二進位加法-->檢查MSB
若最高位有進位則把1加回LSB-->檢查MSB
檢查MSB-->1的話代表為負數
檢查MSB-->0的話代表為正數

          二進位     十進位                   
      0010 0011        35               
    +)1110 1010       -21             
    ............     ....             
    1)0000 1101        13  <-- 錯誤答案  
    +)        1       + 1  <-- 加上進位
    ............     ....
      0000 1110        14  <-- 正確答案
      
         二進位     十進位
     0001 0101        21
   +)1101 1100       -35
   ............     ....
     1111 0001       -14  <--  MSB為1，故為負數，把所有位元翻轉加上負號即可
   ............     ....
    -0000 1110       -14

### 二補數
負數的二進位表示法和一補數類似，差別只在翻轉位元後再加上一，這樣的設計稱為二補數。

graph TD;
二補數-->將正數以二進位表示;
二補數-->將負數取絕對值以二進位表示再把每個位元翻轉加一;
將正數以二進位表示-->將兩數做正常的二進位加法;
將負數取絕對值以二進位表示再把每個位元翻轉加一-->將兩數做正常的二進位加法;
將兩數做正常的二進位加法-->若最高位有進位則直接捨棄
將兩數做正常的二進位加法-->檢查MSB
若最高位有進位則直接捨棄-->檢查MSB
檢查MSB-->1的話代表為負數
檢查MSB-->0的話代表為正數

          二進位     十進位                   
      0010 0011        35               
    +)1110 1011       -21             
    ............     ....             
    1)0000 1110        13  <-- 捨棄進位即為正確答案 
    
      
         二進位     十進位
     0001 0101        21
   +)1101 1101       -35
   ............     ....
     1111 0010       -14  <--  MSB為1，故為負數
   ............     ....
    -0000 1101       -14  <-- 再取一次二補數
   +)        1
   ...........
    -0000 1110            

在這邊簡單複習計算機概論的內容，但是不知道大家會不會有以下的疑問:
1. 為甚麼一補數和二補數是這樣設計的?
2. 為甚麼是這樣做加減法運算?
3. 出現溢位(overflow)要怎麼處理?

接下來的章節將會為大家(我?)解答以上的問題~

## Part3 : 編碼背後的數學原理

在解釋以上問題之前，先讓我們回顧一些基礎的數學概念:

### 阿貝爾群

先來定義甚麼是"群"，數學中的群是由我們定義的二元運算的集合。這裡的二元運算是加法"+"，為了讓我們的集合G成為群，我們必須定義加法運算使之滿足以下4個特性:

1. 封閉性: 若`a`和`b`皆為集合`G`的元素，則`a+b`也為集合`G`的元素
2. 結合律: `(a+b)+c = a+(b+c)`
3. 存在唯一單位元素`0`，使得`a+0 = 0+a = a`
4. 每個集合`G`中的元素都有唯一的反元素，也就是說對於任意`a`而言，存在唯一的`b`使得`a+b = 0`

如果多加上這個條件

5. 交換律: `a+b = b+a`

那這個群就被稱為阿貝爾群。

定義完後，這邊就衍伸出一個問題，那就是電腦只能處理有限值域的運算，因此如果每次超過電腦可以處理的範圍(也就是溢位)都要報錯，那麼想要讓電腦自動化執行就難以實現。因此人們利用接下來要介紹的數學概念也就是"**模除運算**"來讓電腦可以在有限的值域進行計算，並在溢位發生時能得出"自圓其說並看似正確的結果"。

### 模除運算(modular arithmetic)

假設現在電腦使用三個位元進行加法和乘法運算，那在不考慮正負號的情況下，可以表達的數值範圍為`0~7`，而`7+1`的結果不會是`8`，因為會發生溢位(overflow)，所以`7+1`的結果用三個位元的表示法會是`000`，用同餘(congruence mode, 符號 ≡)表示即為:
$7 + 1 \equiv 0 \pmod{8}$
從上述的結果來看，同餘的特性告訴我們，允許溢位的加法滿足交換律、結合律等數學性質。為了滿足計算機中的加法我們需要實現一個阿貝爾群。然而根據上面提到的阿貝爾群的性質，單純加法顯然無法滿足上述條件，因此我們需要引入同餘的特性讓電腦無論做多少次操作，其結果仍落在該群當中。

好了，在我們有了上面兩個數學概念後，我們可以來思考為甚麼計算機要這樣編碼。

## Part4 計算機為何如此編碼(二補數)

### 二補數編碼

假設現在電腦可用來表示的位元數為8，那麼這個位元組可以表示從`0000 0000`到`1111 1111`共256個數值。在十進位和二進位當中`0`都是一樣，所以我們將`0`編碼為`0000 0000`。考慮編碼負數的情況，先從`-1`開始，因為`-1`加上`1`的結果為`0`，而`1`的二進位編碼為`0000 0001`。根據上面阿貝爾群的性質，要想讓`x + 0000 0001`的結果為`0000 0000`，那麼`x`的值必為`1111 1111`， 因為可以利用同餘的性質將溢位的`1`捨去。因此`-1`的編碼為`1111 1111`。那麼`-2`也是同等道理，`-2 + 1 = 1`，因此`-2`的編碼為`1111 1110`，以此類推，我們可以一路推到`1000 0000`。那現在問題來了`1000 0000`究竟是正數還是負數呢?如果大家還記得二補數的結論，會知道MSB=`1`的話為負數，而此數是最小的負數。

但是沒關係，我們依然可以用數學推論出`1000 0000`為負數。假設存在比`1000 0000`的負數`x`，則`x + 1 = 1000 0000`，這樣的話`x = 0111 1111`。先當作此數是比`1000 0000`還要小`1`的負數，我們轉頭去看看正數的編碼。從`0000 0000`開始推論，`1`的編碼為`0000 0001`，`2`的編碼是`0000 0010`。以此類推，我們也可以一路推到`0111 1111`這個數。根據前面的假設，`0111 1111`是負數，利用阿貝爾群的性質，`0111 1111`和它的反元素`1000 0001`相加為`0000 0000`，但是`1000 0001`是我們前面推論出的負數，那麼`0111 1111`必為正數且與前面的假設矛盾，所以`1000 0000`是最小的負數。我們可以將編碼的結果用一個圓環來表示(為了作圖方便，僅用4個位元):


根據上面的圖我們可以發現最大的正數`0111`加`1`之後是`1000`也就是最小的負數。計算機加法的結果會自動用 $2^4-1 = 15$ 做模除運算，而這個模除基本上就是透過自動捨去溢位來達成。在這邊我們可以注意到，這裡討論的是編碼，不涉及正負號，具體是有號還是無號，就看電腦指令的解釋，`1000` 可以是有號的`-8`，也可是無號的`8`，同樣`1111` 可以是有號的`-1`，也可以是無號的`15`。

### 推論二補數規則

假設位元數為 $k$，那麼以下規則成立:
$A + \neg A = 2^k - 1$

雙邊各加`1`並同時取 $\pmod{2^k}$
$A + \neg A + 1 \equiv 0 \pmod{2^k}$

根據阿貝爾群的性質，我們知道 $-A$ 是 $A$ 的反元素，所以
$-A \equiv \neg A + 1$

根據上面的推論，我們解釋了為甚麼二補數是一補數加`1`~

## Part5 圖像化解釋一補數和二補數之間的關係

以下一樣用4個位元做討論，我們先觀察下圖(AOS=axis of symmetry)，綠色的線是一補數對軸，紅色的是二補數對稱軸:
我們可以很輕易的驗證說一補數的做法為反轉所有位元，例如`0001 -> 1110`。同樣也可以看到二補數的作法為先一補數再加`1`，例如`0001 -> 1110 + 0001`。更仔細觀察，可以發現一補數對稱軸和二補數對稱軸相差`0.5`，所以對稱後剛好數值差`1`。透過圖像觀察法，我們可以更直觀理解為甚麼二補數是一補數加`1`。

## Part6 回答上述提到的三個問題

1. 為甚麼一補數和二補數是這樣設計的?
2. 為甚麼是這樣做加減法運算?
3. 出現溢位(overflow)要怎麼處理?

針對問題1和2，上面各個part都已解答。至於問題3，我們可以重新檢視這張圖
對於二補數而言，因為0的表示法只有`0000`一種，所以模除運算是取$\pmod {16}$，所以因為進位而造成溢位的`1`可以直接被捨去。至於一補數的部分，因為`0`的表示法有兩種，分別是`0000`和`1111`，所以模除運算是取$\pmod{15}$，因此如果要把因為進位而造成溢位的`1`去掉，就要再加上`0001`才符合$\pmod{15}$。

## 後記

本篇筆記主要是解釋計算機編碼的數學原理，至於背後涉及的bitwise operation以及資訊安全方面的考量會陸續整理出筆記。

參考資料
[sysprog 解讀計算機編碼](https://hackmd.io/vOjbtew3Tn2aA0uDrmUL4Q)