---
title:
image:
description:
tags: NCKU Class , 進階電腦系統理論與實作 , 2020q3
---
# 2020q3 Homework4 (quiz4)
contributed by < `TsenEN` >
> [題目](https://hackmd.io/@sysprog/2020-quiz4)
> [作業要求](https://hackmd.io/@sysprog/r1z0WPWLD)
## [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance)
由 [Richard Hamming](https://en.wikipedia.org/wiki/Richard_Hamming) 這位偉大的數學家所提出，因為其特性，被廣泛運用在編碼理論中的字元比較，例如：在兩個等長字串中，它測量將一個字符串轉換為另一個字符串所需的最小替換數，換句話說他可以作為字符最小編輯數的一個指標。
### Properties
在固定 n 長度下，Hamming distance 是長度 n 的單字集合(又稱為 [Hamming space](https://en.wikipedia.org/wiki/Hamming_space))上的一個 [metric](https://en.wikipedia.org/wiki/Metric_(mathematics))。
#### metric
metric 跟數學上的度量沒有關係！它又可以稱為 distance function ，所以它其實是個函數，是定義集合中每對點元素之間的距離之函數。
具有 metric 的集合稱為 metric space。
##### Definition
Metric 在 X 集合上是個函數，又稱為距離函數，但通常我們會稱為距離(距離是數學規範出來後在某定義域在函數上轉換後出來的數值(值域)，在我們生活中普遍利用的距離就是 cm、m、km)
X 集合為函數
:::info
wiki 寫說 $\forall x,y,z\in X$，所以 xyz 皆是 X 這個函數所轉換出來的數字，這意味著 xyz 屬於X這個函數的值域(codomain)，這其實也交代了今天要算距離時使用的數值或許會是某函數所轉換出來的值，並且因為要算距離所以兩個數值屬於的空間一定要一樣，所以下面才會寫 $X$ x $X$。
:::
$d : X$ x $X \to [0, \infty)$
因為是距離所以最少就是 0，也因此會往正無限大所延伸(這是定義所以毋庸置疑)。
$\forall x,y,z\in X，$d$ 滿足下面三個公理：
這邊先簡要說明，要證明的話，需要複習一下離散數學。
1. 反身性
$\displaystyle d(x,y)=0\Leftrightarrow x=y$
自己跟自己距離一定為 0。
2. 對稱性
$\displaystyle d(x,y)=d(y,x)$
你到我的距離=我到你的距離。
3. 三角不等式
$\displaystyle d(x,y)\leq d(x,z)+d(z,y)$
因為滿足我到你為最短距離的，因為不存在一條路徑會比我小。
## 測驗 1
Hamming distance 有個特性是相鄰兩碼必定差 1 bit ，[leetcode 461. Hamming Distance](https://leetcode.com/problems/hamming-distance/)，要我們計算距離相當於計算他們差幾碼，所以我們利用 `XOR` 奇同位特性搭之前 H3-quiz3 所提及的 `__builtin_popcount` 即可達成要求。
| ＸＯＲ | x | y | x^y |
| ------ | --- | --- | --- |
| | 0 | 0 | 0 |
| | 0 | 1 | 1 |
| | 1 | 0 | 1 |
| | 1 | 1 | 0 |
==OP = `(c) ^`==
```c
int hammingDistance(int x, int y) {
return __builtin_popcount(x ^ y);
}
```
## 延伸問題 1-1
:::success
解釋上述程式碼運作原理，並舉出不使用 gcc extension 的 C99 實作程式碼
:::
理解了 Hamming Distence 特性，我們知道==兩個字串不同位元的個數等於他們的距離==，所以只需要做簡單 XOR 後，利用 gcc extension 的 __builtin_popcount 來計算 1 的個數，即可知道相差距離！
所以我們可以如果不利用 popcount ，我們要開始想如何做到在 O(1) 的時間就完成計數？
想法一：
大家應該都學過如何 10 進制如何轉 2 進制，整數部份一直 mod 2 ，取出餘數就可以得到 2 進制，而小數部份就是一直乘 2，取整數部份為數值。下圖來自[進制轉換 (二進制、八進制、十進制、十六進制)](https://notfalse.net/17/positional-numeral-systems-conversion)
<img style = "display:block; margin:auto;" src="https://i.imgur.com/YsTUSMs.png"></img>
<img style = "display:block; margin:auto;" src="https://i.imgur.com/18iZ0tq.png"></img>
所以可以看到在計算過程就可以得知 1 的部份！
```c
int hamming_distance(unsigned x, unsigned y){
int dist = 0;
if(x==y)
return 0;
for (unsigned val = x ^ y;val >1 ;val = val / 2){
if(val % 2 == 1)
dist ++;
}
dist ++;
// Return the number of differing bits
return dist;
}
```
所以我們利用轉換 2 進制過程，mod 2 餘數為 1 的時候做計數即可達到這個效果！但是對計算機系統有概念的都知道，只要跟除法有關係的操作，在背後都是很費時也很浪費記憶體，所以如果能避免除法，就盡量避免！
所以我們再想想有沒有別的方式！
想法二：
其實有個很簡單 bitwise 的操作，無需除法，只需要簡單減法跟 XOR 即可以達成目的。
```c=
int hamming_distance(unsigned x, unsigned y){
int dist = 0;
// The ^ operators sets to 1 only the bits that are different
for (unsigned val = x ^ y; val > 0; ++dist)
{
// We then count the bit set to 1 using the Peter Wegner way
val = val & (val - 1); // Set to zero val's lowest-order 1
}
// Return the number of differing bits
return dist;
}
```
演算的過程 `val = val & (val - 1);` 這條是精華！，這樣的操作可以每次取出字串最後一個 1 。
1010 ^ (1010-1) = 1000
1000 ^ (1000-1) = 0000
## 延伸問題 1-2
:::success
[LeetCode 477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/submissions/)
:::
暴力法：O(n^2^)
```c=
int totalHammingDistance(int* nums, int numsSize){
int total = 0;
int i,j = 0;
for(i;i<numsSize;i++){
for(j = i + 1;j<numsSize;j++){
total += __builtin_popcount(nums[i] ^ nums[j]);
}
}
return total;
}
```
最直覺的做法，$\binom{n}{2}$，n = |numsSize|，但是這太直觀也很暴力可能會 Time Limit Exceeded 。
Bitwise：
首先我們列幾個數字來觀察
| Number | b3| b2| b1| b0 |
| ------ | --|--|--|--|--- |
| 4 | 0|1|0|0 |
| 14 | 1|1|1|0 |
| 2 | 0|0|1|0 |
| 3 | 0|0|1|1 |
我們知道 Hamming Distance 的特性會對應到數字 Binary bits 的差異，譬如 14 跟 4 有兩個 bits 不同，那距離就為 2 ，那我們一次比 4 個，注意到大家的 `b1` 只有 4 是 0 其他數字是 1 ，這代表著 4 的 `b1` 跟大家 XOR 會使 `total distance += 3`，再注意 `b2` 發現 4、14 為 1 其他為 0，這意味著當某位是 1 的就會去找是 0 的配對所以這樣會出現 2x2 種情況！
好所以我們就是要逐位去檢查 0、1 的個數並相乘起來再加總就是我們要計算的 Total Hamming Distance.
| bits | zeros | ones | pairs |
| ---- | ---------- | ---------- | ----- |
| b0 | {4、14、2} | {3} | 3 |
| b1 | {4} | {14、2、3} | 3 |
| b2 | {4、14} | {2、3} | 4 |
| b3 | {4、2、3} | {14} | 3 |
```c=
int totalHammingDistance(int* nums, int numsSize){
if (numsSize < 2)
return 0;
int total = 0;
int i,j,cont= 0;
unsigned int mask = 1;
for(i;i<32;i++){
cont = 0;
for(j = 0;j<numsSize;j++){
if(nums[j] & mask)
cont++;
}
total += (numsSize - cont) * cont;//(numsSize - cont) = 0 的個數
mask <<= 1;
}
return total;
}
```
<img src = "https://i.imgur.com/SL7C4fb.jpg"></img>
<img src = "https://i.imgur.com/zln7ncl.jpg"></img>
## 延伸問題 1-3
:::success
研讀[錯誤更正碼簡介](https://w3.math.sinica.edu.tw/math_media/d184/18404.pdf)及[抽象代數的實務應用](https://www.math.sinica.edu.tw/www/file_upload/summer/crypt2017/data/2017/%E4%B8%8A%E8%AA%B2%E8%AC%9B%E7%BE%A9/[20170710][%E6%8A%BD%E8%B1%A1%E4%BB%A3%E6%95%B8%E7%9A%84%E5%AF%A6%E5%8B%99%E6%87%89%E7%94%A8].pdf)，摘錄其中 Hamming Distance 和 Hamming Weight 的描述並重新闡述，舉出實際的 C 程式碼來解說
* 搭配閱讀 [Hamming codes, Part I](https://www.youtube.com/watch?v=X8jsijhllIA&t=135) 及 [Hamming codes, Part II](https://www.youtube.com/watch?v=b3NxrZOu_CE&t=7s)，你可適度摘錄影片中的素材，但應當清楚標註來源
:::
#### The Hamming Single Error Corrcetion Code (ECC)
這是一個應用在計算機科學上非常廣泛的技術，也是先前提到 [Richard Hamming](https://en.wikipedia.org/wiki/Richard_Hamming) 可以獲得 1968 圖靈獎不可或缺的元素之一。
ECC 應用非常廣泛，只要跟通訊有關，就少不了它，因為當我們資料傳遞時難免會受到雜訊影響，假設這是一串編碼的其中一部分 `1101` 結果被干擾成 `1111` ，原本編碼的意思是，維尼要跟唐老鴨說：『我們結束這無聊的戰爭吧！』，改成：『我要用核彈轟爆你！』，這假設可能誇張了一點但只是想表述 ECC 多重要！
<img style = "display:block; margin:auto;" src="https://i.imgur.com/s5Efhti.jpg"></img>
ECC 也被利用在 EEC Memory 或是 RAID(Redundant Array of Independent Disks) 作為資料糾錯或是恢復的演算法。
### [Hamming codes, Part I](https://www.youtube.com/watch?v=X8jsijhllIA&t=135)
[Hamming codes, Part I 翻譯](https://hackmd.io/@TsenEN/HkJ31g0av)
我覺得影片有句說得很好:「After all, storing data is the thing as sending a message, just from the past to the future instead of from one place to another.」充分表示當資料在傳輸的時候，是會出現錯誤的。
#### 簡單的資料維護
$Q :$ 在沒有任何的基礎下，請問最簡單的資料維護方式是？
$A :$ 這答案應該會是大部分人想到的，複製兩份一模一樣的資料(這樣總共三份資料)，每次檢查佔 $\frac{2}{3}$ 的部份則為正確的資料。
```graphviz
digraph structs {
T [label="error" color=Blue, fontcolor=Red, fontsize=24, shape=box]
node [shape=record];
struct1 [label="<f0> Original File|{b0|0}|{b1|1}|{b2|1}|{b3|1}|{b4|0}|{b5|1}|{<f6>b6|0}|{b7|0}|{b8|0}|{b9|0}|{b10|0}|{b11|1}|{b12|1}|{b13|0}|{b14|1}|{b15|0}", fontsize=24];
T->struct1:f6;
}
```
```graphviz
digraph structs {
node [shape=record];
struct1 [label="<f0> Copy 1 |{b0|0}|{b1|1}|{b2|1}|{b3|1}|{b4|0}|{b5|1}|{b6|1}|{b7|0}|{b8|0}|{b9|0}|{b10|0}|{b11|1}|{b12|1}|{b13|0}|{b14|1}|{b15|0}", fontsize=24];
}
```
```graphviz
digraph structs {
node [shape=record];
struct1 [label="<f0> Copy 2 |{b0|0}|{b1|1}|{b2|1}|{b3|1}|{b4|0}|{b5|1}|{b6|1}|{b7|0}|{b8|0}|{b9|0}|{b10|0}|{b11|1}|{b12|1}|{b13|0}|{b14|1}|{b15|0}", fontsize=24];
}
```
假設今天 `b6` 在原始資料產生了反轉 `1 -> 0` 而當檢查到 `b6` 時會發現 `b6 = 1` 佔了 $\frac{2}{3}$ 機率，此時電腦就會知道 `b6` 發生了反轉，這時就可以將 `b6` 修正成 1。
但是上述方式存在兩個大問題：
1. 這樣複製資料來維護的方式非常浪費記憶體資源（Redundancy），稍微想一下會知道記憶體實際使用率只有 33.3％ 其他 66.7% 都是複製一樣的資料，在以前的年代記憶體空間非常的珍貴，這樣做基本上不是那麼聰明也不實用。
```graphviz
digraph structs {
node [shape=record];
struct1 [label="{Original File |33.3%}|{Redundancy |66.7%}"];
}
```
2. 如果今天在同一個位元上發生有兩份資料發生了反轉，則資料仍然是錯誤的。假設錯誤仍在 `b6` ，但是不僅 Original File 反轉了，Copy1 也反轉了，這樣 `b6 = 0`就佔了 $\frac{2}{3}$ 的機率，則資料仍然是錯誤的，因為原始資料為 1。
但這樣的方式並非都是缺點，也是有優點的，但這要有前提：
假設今天資料反轉永遠都只有 Original File 會發生，其他複製出來的資料永遠都是正確的
1. 永遠可以知道反轉的資料位置，並且可以修正它。
2. 可以發生超過一個位元反轉後，資料仍可以修正。
這意思是假設今天 `b6 b9 b10 b11` 都發生反轉了，但是因為有複製兩筆相同的資料來做驗證，所以可以知道前述反轉的位置（`b6 b9 b10 b11`），並且可以修正反轉位。
所以綜合前述，如果我們可以發明一個演算法，這個演算法滿足以下好處：
a. 不僅不佔記憶體空間。
b. 可以知道反轉位置。
c. 可以修正反轉位。
d. 如果發生超過一個位元反轉後，但是仍可以知道錯誤位置，並且還可以修正。
這要看起來不怎麼過分，但是實際上要滿足上述 4 點其實是要花點心思的。而接下來要說到的演算法（ECC）可以滿足上述前 3 點(a,b,c)，並且雖然無法完全滿足 d 但可以知道至少超過一位元有反轉。
所以這邊要先說一下他的賣點，不然就沒有意義看下去了。就好像我要賣你東西但是我無法滿足你的需求那麼你也不會想買了！
假設今天你是 256 bits 的資料，利用先前的方式，要產生 256 * 3 bits，非常浪費！而 ECC 只需要==利用 256 bits 中的 8 bits 作為 Redundancy== 就可以滿足上述前 3 點(a,b,c)，如果利用 9 bits ，則可以知道是否有超過一位元反轉。
所以只利用了 $\frac{9}{256}$ = 3.5% 作為 Redundancy !!!!!你看看那個 66.7% 這怎麼比？？？
```graphviz
digraph structs {
node [shape=record];
struct1 [label="{Original File |96.5%}|{Redundancy |3.5%}"];
}
```
夠吸引了吧！？怎麼有人可以想到這樣的事情？然後還長那麼帥？
<img style = "display:block; margin:auto;" src="https://i.imgur.com/DTs17JI.jpg"></img>
年輕時候的 Richard Hamming | University of Illinois
開始說明 Hamming 整體想法以前，要先有個基礎建設，沒有一種演算法可以在發生任何錯誤下都可以完整地恢復原本訊息。如果有那應該是薩滿?
以下討論的基礎建設是：｢如果有反轉位(資料錯誤的位置)，則只會有一個。
#### Parity Check
深入 ECC 以前需先學習 Parity Check (奇偶驗證)，假設現在有 16 bits ，並且 `bit 0` 這個位置將其保留並且它作為 `bit 1 ~ bit 15` 的 1 總數為偶數的驗證碼 (b0 = parity bit)，如果 `bit 1 ~ bit 15` 1 總數為偶數 (even) 則 `bit 0` 為 0，反之奇數 (odd) 則為 1，這樣做的目的是確保送過去接收端時，接收者可以接收到的 1 個數都是 even，當接收者檢查字串中 1 的數量如果是 odd 則這段字串在被送到接收者手中前就被雜訊所干擾。
```graphviz
digraph structs {
node [shape=record];
struct1 [label="<f0> Original File|{{b0|0}|{b4|0}|{b8|0}|{b12|1}}|{{b1|0}|{b5|1}|{b9|0}|{b13|0}}|{{b2|0}|{b6|0}|{b10|0}|{b14|1}}|{{b3|0}|{b7|1}|{b11|0}|{b15|0}}}", fontsize=12];
}
```
以上字串為傳輸正確的範例，`bit 0 = 0`，且`bit 1 ~ bit 15` 1 總數個數為 even 。
```graphviz
digraph structs {
node [shape=record];
struct1 [label="<f0> Original File|{{b0|0}|{b4|0}|{b8|0}|{b12|1}}|{{b1|0}| {b5|1}|{b9|1}|{b13|0}}|{{b2|0}|{b6|0}|{b10|0}|{b14|1}}|{{b3|0}|{b7|1}|{b11|0}|{b15|0}}}", fontsize=12];
}
```
以上字串為傳輸失敗的範例，`bit 0 = 0`，且`bit 1 ~ bit 15` 1 總數個數為 odd。接收者可以知道這串訊息是有錯誤的。但是不知道錯在哪裡！
當然如果一次翻轉兩位，勢必又會回到 even，但是這樣檢查的方式啟發了 Hamming 。
#### Use parity check to check 4 question
所以 Hamming 利用剛才所提及的 parity check 做出了華麗的操作，只須對字串做出 4 個詢問方式，則可以知道錯誤位在哪！
#### $Q1$
第一個 parity check 是檢查整個字串的 odd bits (橘色部分)，並且利用 `b1` 作為 parity bit ，來檢查在 odd 位置 1 的總數是否為 even，如果 b3、b5、b7、b9、b11、b13、b15，1 總數為 even，則 `b1 = 0`，反之 `b1 = 1`。
```graphviz
digraph structs {
node [shape=record];
struct0 [label="{{b0|}|{b4|}|{b8|}|{b12|}}}", fontsize=12 ,fillcolor="#E3E3E3" , style=filled];
struct1 [label="{{b1|}| {b5|}|{b9|}|{b13|}}}", fontsize=12 ,fillcolor="#FFD78C" , style=filled];
struct2 [label="{{b2|}|{b6|}|{b10|}|{b14|}}", fontsize=12 ,fillcolor="#E3E3E3" , style=filled];
struct3 [label="{{b3|}|{b7|}|{b11|}|{b15|}}", fontsize=12 ,fillcolor="#FFD78C" , style=filled];
}
```
以下為例
```graphviz
digraph structs {
node [shape=record];
struct0 [label="{{b0|}|{b4|}|{b8|}|{b12|}}}", fontsize=12 ,fillcolor="#E3E3E3" , style=filled];
struct1 [label="{{b1|1}| {b5|0}|{b9|1}|{b13|1}}}", fontsize=12 ,fillcolor="#FFD78C" , style=filled];
struct2 [label="{{b2|}|{b6|}|{b10|}|{b14|}}", fontsize=12 ,fillcolor="#E3E3E3" , style=filled];
struct3 [label="{{b3|1}|{b7|1}|{b11|1}|{b15|0}}", fontsize=12 ,fillcolor="#FFD78C" , style=filled];
}
```
上圖可以得知這橘色區塊是沒有問題，這代表這整段字串沒有錯又或者錯誤位置在 even bits 。
#### $Q2$
第二個 parity check 是檢查整個字串的橘色部分，並且利用 `b2` 作為 parity bit ，來檢查在 odd 位置 1 的總數是否為 even，如果 b3、b6、b7、b10、b11、b14、b15，1 總數為 even，則 `b2 = 0`，反之 `b2 = 1`。
```graphviz
digraph structs {
node [shape=record];
struct0 [label="{{b0|}|{b4|}|{b8|}|{b12|}}}", fontsize=12 ,fillcolor="#E3E3E3" , style=filled];
struct1 [label="{{b1|}| {b5|}|{b9|}|{b13|}}}", fontsize=12 ,fillcolor="#E3E3E3" , style=filled];
struct2 [label="{{b2|}|{b6|}|{b10|}|{b14|}}", fontsize=12 ,fillcolor="#FFD78C" , style=filled];
struct3 [label="{{b3|}|{b7|}|{b11|}|{b15|}}", fontsize=12 ,fillcolor="#FFD78C" , style=filled];
}
```
以下為例
```graphviz
digraph structs {
node [shape=record];
struct0 [label="{{b0|}|{b4|}|{b8|}|{b12|}}}", fontsize=12 ,fillcolor="#E3E3E3" , style=filled];
struct1 [label="{{b1|}| {b5|}|{b9|}|{b13|}}}", fontsize=12 ,fillcolor="#E3E3E3" , style=filled];
struct2 [label="{{b2|0}|{b6|1}|{b10|0}|{b14|0}}", fontsize=12 ,fillcolor="#FFD78C" , style=filled];
struct3 [label="{{b3|1}|{b7|1}|{b11|1}|{b15|0}}", fontsize=12 ,fillcolor="#FFD78C" , style=filled];
}
```
上圖可以得知這橘色區塊是沒有問題，這代表這整段字串沒有錯又或者錯誤位置在灰色的位置。
到這邊先思考一下這樣可以有甚麼用意？
假設今天 $Q1$ 檢查沒有問題，$Q2$ 卻檢查錯誤，以下圖為例
```graphviz
digraph structs {
check0[shape=plaintext,fontcolor=blue]
check1[shape=plaintext,fontcolor=blue]
check2[shape=plaintext,fontcolor=red]
check3[shape=plaintext,fontcolor=blue]
node [shape=record];
struct0 [label="{{b0|}|{b4|}|{b8|}|{b12|}}}", fontsize=12 ,fillcolor="#E3E3E3" , style=filled];
struct1 [label="{{b1|1}| {b5|0}|{b9|1}|{b13|1}}}", fontsize=12 ,fillcolor="#FFD78C" , style=filled];
struct2 [label="{{b2|0}|{b6|1}|{b10|0}|{b14|1}}", fontsize=12 ,fillcolor="#FFD78C" , style=filled];
struct3 [label="{{b3|1}|{b7|1}|{b11|1}|{b15|0}}", fontsize=12 ,fillcolor="#FFD78C" , style=filled];
check0->struct0;
check1->struct1;
check2->struct2;
check3->struct3;
}
```
這邊要注意剛剛說到的基礎建設(前提)，==如果這個字串有錯，那只會有一個==。
為了方便解說，我們將每一行都上編號，分別以那行的起頭命名為 check no. 。
所以當 $Q1$ 檢查沒有錯誤的時候，表示 check1 跟 check3 那兩行一定沒有錯，而 $Q2$ 檢查有錯誤的時候表示 check2 跟 check3 其中某一行出錯，而剛剛 $Q1$ 保證 check3 沒有錯，這表示一定是 check2 那行出了錯誤(以紅色表示)。
好所以我們可以推廣出真值表，以 0 表示沒錯 1 表示出錯，這邊假設字串一定有一個錯誤。
| Q1 | Q2 | 錯誤行 |
| ------------ | -------------- | -------------- |
|0|0|check0|
|0|1|check2|
|1|0|check1|
|1|1|check3|
所以這邊 $Q3$ $Q4$ 也運用相同道理來處理出錯列，所以當出錯行跟出錯列已經都鎖定出來，那麼是不是就可以知道真正的錯誤位在哪裡!並且還可以修正回來。
### [錯誤更正碼簡介](https://w3.math.sinica.edu.tw/math_media/d184/18404.pdf)
#### Single–Error Correcting(SEC) Codes
<img style = "width:400px;height:270px;" src="https://i.imgur.com/dolMGcP.jpg"></img>
這篇也運用到 Parity Check ，在同一個圓中 1 的個數一定是偶數，所以當在圖3.3a 檢查到 B 的時候會知道 B 出錯了，而因為 A、C 確定沒錯所以在 B 裡面的 `2,1,4` 區塊不會有錯誤，故此可以知道 `6` 號區塊出錯了。其他的情形, 都只是對稱而已, 所以這個碼可以改一個錯, 我們就稱做 single–error correcting (SEC)。 這個碼有一個術語叫做 (7, 4) Hamming code, 為什麼叫(7, 4)? 就是全部長度是 7，只有 4 個 bits 是原來要傳的資料, 所以叫 (7, 4)。
但是這樣的方式只能錯一修一，錯二就沒了
<img style = "width:400px;height:270px;" src="https://i.imgur.com/crUVbl3.jpg"></img>
按照剛剛的驗證方式去修正圖3.4 會去修正到 `4` 這個正確的區塊，其他位置錯兩個同樣會修正到正確的區塊，所以如果要改兩個或兩個以上的錯，會需要更好的演算法。
#### (7, 4) Hamming Code 的數學結構
文中提到一個代數結構，意思是想表明矩陣內的數值非 0 即 1。
<img style = "width:300px;height:200px;" src="https://i.imgur.com/VR3S18c.png"></img>
我們將每個區塊對應成 $x_1 x_2...x_7$
因為我們要使每個區塊 1 的個數為偶數可以定義以下數學式：
$$
\left\{
\begin{array}{c}
x_1+x_2+x_3+x_5=0 \\
x_1+x_2+x_4+x_6=0 \\
x_1+x_3+x_4+x_7=0
\end{array}
\right.
$$
$$
x_i \in \{0,1\}, \ i \in \{ 0,1,2,3,4,5,6,7\}
$$
這邊要思考為何等於 0，這邊因為代數結構的特性，所以以 A 來說，A 涵蓋區塊 `1,2,3,5` ， $x_1$ $x_2$ $x_3$ $x_5$ 因為一定要等於 0，所以出現 1 的個數會是偶數！
我們將上面數學式轉換成線性方程式 (linear equations)
$$
H =
\begin{pmatrix}
1 & 1 & 1 & 0 & 1 & 0 & 0 \\
1 & 1 & 0 & 1 & 0 & 1 & 0 \\
1 & 0 & 1 & 1 & 0 & 0 & 1 \\
\end{pmatrix}
$$
令 C 代表所有 codewords 所構成的集合，白話說就是加密過後字串，而因為任意屬於 $C$ 的向量(1x7) transpose 後(7x1)去右乘 $H$ 都可以使其成為一個3x1的 $\vec 0$，因此我們得出下列數學式。
$$
C:1\times7,
\forall \vec x \in C,
\because H \cdot \vec x^T = \vec 0,
\therefore C^T\in ker(H)
$$
Ker(H)這邊需要參考 [Kernel (algebra)](https://en.wikipedia.org/wiki/Kernel_(algebra))，簡單來說這裡面任一個向量都可以滿足右乘 $H$ 使其為 $\vec 0$。
:::warning
文中有提到 ***“因此整個 $C$ 就是矩陣 $H$ 的 null space(Ker)”*** ，我覺得怪怪的，因為他自己有說 ***“$\vec x$ 是 row vector”***，這意思是 $\vec x$ 的 size 是 $1\times7$，這跟 $H$ 根本無法做到左乘右乘(學過線性代數的應該都知道)，只有 ranspose 後 $\vec x^T$ 變成 7x1 才能右乘，所以我上面才寫 ***"$C^T\in ker(H)$"***。
:::
再來說明這段 “***它的 dimension 就等於7減掉這個矩陣的 rank 3, 也就是4***”
這邊運用到一些線代的基礎概念
$H:m \times n$ , m = 列 , n = 行
***1. $Rank(H)$ $\le$ $min \{m,n\}$***
要理解這行要知道一件事 ***$row\ rank\ of\ H\ =\ column\ rank\ of\ H$***，中文來說是 [$H$ 的行空間會等於 $H$ 的列空間](https://zh.wikipedia.org/wiki/%E8%A1%8C%E7%A9%BA%E9%97%B4%E4%B8%8E%E5%88%97%E7%A9%BA%E9%97%B4)。
$dim(RS(H))$ = $H$ 的列空間
$dim(CS(H))$ = $H$ 的行空間
$dim(RS(H)) = dim(CS(H)) = Rank(H)$
***2. $H$ 列獨立 $in \ F^{1 \times n}$ :left_right_arrow: $dim(RS(H)) = m$ :left_right_arrow: $Rank(H) = m$ :left_right_arrow: $H$ 具右反矩陣 :left_right_arrow: $dim(CS(H)) = m$ :left_right_arrow: $H$ 行生成 $in \ F^{m \times１}$***
所我們先做簡單的列運算([高斯消去法](https://ccjou.wordpress.com/2013/02/20/%E9%AB%98%E6%96%AF%E6%B6%88%E5%8E%BB%E6%B3%95/))來證明列獨立
$$
H =
\begin{pmatrix}
1 & 1 & 1 & 0 & 1 & 0 & 0 \\
1 & 1 & 0 & 1 & 0 & 1 & 0 \\
1 & 0 & 1 & 1 & 0 & 0 & 1 \\
\end{pmatrix}
$$
第一列乘 -1 跟第二列相加 = $r_{12}^{-1}$
$$
H =
\begin{pmatrix}
1 & 1 & 1 & 0 & 1 & 0 & 0 \\
0 & 0 & -1 & 1 & -1 & 1 & 0 \\
1 & 0 & 1 & 1 & 0 & 0 & 1 \\
\end{pmatrix}
$$
第一列乘 -1 跟第三列相加 = $r_{13}^{-1}$
$$
H =
\begin{pmatrix}
1 & 1 & 1 & 0 & 1 & 0 & 0 \\
0 & 0 & -1 & 1 & -1 & 1 & 0 \\
0 & -1 & 0 & 1 & -1 & 0 & 1 \\
\end{pmatrix}
$$
好做到這邊就已經知道列獨立，因為符合梯形矩陣([row echelon form](https://zh.wikipedia.org/wiki/%E9%98%B6%E6%A2%AF%E5%BD%A2%E7%9F%A9%E9%98%B5))的性質，故此我們結合第一點得到 $dim(RS(H)) = dim(CS(H)) =Rank(H) = m = 3$
***3. [Rank–nullity theorem](https://en.wikipedia.org/wiki/Rank%E2%80%93nullity_theorem)***
${\displaystyle \operatorname {Rank} (T):=\dim(\operatorname {Image} (T))} \ and \ {\displaystyle \operatorname {Nullity} (T):=\dim(\operatorname {Ker} (T)).}$
所以我們得到：
$Rank(H) + Nullity(H) = n = 7$
所以我們可以知道 $dim(ker(H)) = Nullity(H) =dim(C^T) = 7- Rank(H) = 4$
好所以這邊很驚奇喔，別看小看這個 $4$，還記得我們一直提到$Nullity(H) =dim(C^T)$，我們可以將它[基底](https://zh.wikipedia.org/wiki/%E5%9F%BA_(%E7%B7%9A%E6%80%A7%E4%BB%A3%E6%95%B8))列出來，這邊以列向量條列出來。
$$
\displaystyle Basis=
\left\{\begin{bmatrix} 1\\ 0\\ 0\\ 0 \end{bmatrix},\begin{bmatrix} 0\\ 1\\ 0\\ 0 \end{bmatrix},\begin{bmatrix} 0\\ 0\\ 1\\ 0 \end{bmatrix},\begin{bmatrix} 0\\ 0\\ 0\\ 1 \end{bmatrix}\right\}
$$
基底可以隨便列，只要確保[線性獨立](https://ccjou.wordpress.com/2013/11/19/%E7%B7%9A%E6%80%A7%E7%8D%A8%E7%AB%8B%E5%90%91%E9%87%8F%E9%9B%86%E7%9A%84%E5%88%A4%E5%AE%9A%E8%88%87%E7%AE%97%E6%B3%95/)就好，每個空間都會有基底，基底就是作為整個空間生成的基本，利用基底做任何的線性組合，即可變成這個空間任意一個向量。
例如我可以生成出 1011
$$
\left\{1\begin{bmatrix} 1\\ 0\\ 0\\ 0 \end{bmatrix}+ 0\begin{bmatrix} 0\\ 1\\ 0\\ 0 \end{bmatrix}+ 1\begin{bmatrix} 0\\ 0\\ 1\\ 0 \end{bmatrix}+ 1\begin{bmatrix} 0\\ 0\\ 0\\ 1 \end{bmatrix}\right\} = \begin{bmatrix} 1\\ 0\\ 1\\ 1 \end{bmatrix}
$$
好這是什麼意思？這代表給 4bits 的字串，$2^4 = 16$(非0即1) ，==0~15 的二進制表示式，都可以被生成出對應的 7bits codeword(另外 3bits 會對映生成)。==
#### Hamming Distance & Hamming Weight
:::info
這邊有幾個資料可以參考
- [CSC 310: Information Theory|University of Toronto, Fall 2011](http://www.cs.toronto.edu/~radford/csc310/week11.pdf)
- [錯誤控制編碼: 碼率與最小漢明距離](https://www.youtube.com/watch?v=bPpohhwJ0Pk)
:::
我們舉些實例：假設今天只傳 two bits
```graphviz
digraph structs {
node [shape=record];
struct1 [label="{{b1|b0}|{0|0}|{0|1}|{1|0}|{1|1}}", fontsize=12];
}
```
我們令 $C1 = \{00,01\}$ 作為傳輸資料，所以在傳輸資料時資料可能反轉成 00、01、10、11，如果說今天傳輸 00，資料反轉成 10 ，那我們肯定知道這資料有錯，並且我們可能會猜是 00 ，因為這呼應[錯誤更正碼簡介](https://w3.math.sinica.edu.tw/math_media/d184/18404.pdf)文中提到"在一般的情況下會錯的機率比較小，不會錯的機率比較大，所以就統計上來說，找一個錯的個數最少的向量，表示它可能的機率最大"(我們也非常相信現在抗雜訊技術非常成熟:smile:)。
那如果今天 00 :arrow_right: 01，這樣接受者並不會懷疑資訊錯誤，所以==這樣選擇並沒有偵錯能力==。這邊注意 $Hamming\ distance$ :arrow_right: $d_H (00,01) = 1$
那我們選擇 $C2 = \{00,11\}$ 作為傳輸資料，傳輸資料時資料可能反轉成 00、01、10、11，我們這樣選擇有個好處，如果今天只反轉一位 00 :arrow_right: 01 或 00 :arrow_right: 10 或 11 :arrow_right: 10 或 11 :arrow_right: 01，==我們擁有了偵錯能力，但是我們沒有修正能力，因為我們不知道錯在哪裡！== 並且當我們收到 10 ，我們不知原本資料是 00 還是 11，這是因為修正距離一樣都只差 1 bit。這邊注意 $Hamming\ distance$ :arrow_right: $d_H (00,11) = 2$
然後我們先畫個圖，這邊是想表示上面敘述"修正距離一樣都只差 1 bit"故此產生==交集==，這就是為什麼修正不會去原因。
<img style = "width:300px;height:200px;" src="https://i.imgur.com/nKr1tip.jpg"></img>
所以我們只能擴充多的 bits
```graphviz
digraph structs {
node [shape=record];
struct1 [label="{{b2|b1|b0}|{0|0|0}|{0|0|1}|{0|1|0}|{0|1|1}|{1|0|0}|{1|0|1}|{1|1|0}|{1|1|1}}", fontsize=12];
}
```
我們選擇 $C3 = \{000,111\}$ 作為傳輸資料，因此傳輸過程可能產生反轉
000 :arrow_right: 001 , 111 :arrow_right: 011
000 :arrow_right: 010 , 111 :arrow_right: 101
000 :arrow_right: 100 , 111 :arrow_right: 110
上面列出了反轉 1 bit 的可能性，但是各位有沒有發現這樣的錯法永遠都可以修正回去。
這邊一樣注意$Hamming\ distance$ :arrow_right: $d_H (000,111) = 3$，接著我們先看圖
<img style = "width:400px;height:200px;" src="https://i.imgur.com/3xSh8XI.png"></img>
<img style = "width:400px;height:200px;" src="https://i.imgur.com/zLt2gjq.jpg"></img>
感覺到了嗎？因為他們錯誤的資料並沒有交集所以才可以達成修正功能。
因此文中才會提到
1. 這兩個球不能碰在一起, 假如碰在一起, 那會有一點與 x 的距離小於等於 t，距離 x′ 也小於等於 t，這時候就不知道要把它改成 x，或者是x′。
2. 所以這兩球的距離至少是 1，交集是空集合，x 和 x′ 的距離至少要是 $t + 1 + t =2t + 1$
所以我們得到一個 minimum distance 公式，t 表示錯誤的 bit 數，d 表示最短距離。
$$
d = 2t+1 \\
t = \lfloor \frac {d-1}2 \rfloor \\
$$
而這個 d 跟 $minimum\ distance$ 有關係，所以文中先利用 $Hamming\ distance$ 跟 $Hamming\ weight$ 推導出 $minimum\ distance$ 跟$minimum\ weight$ 這兩個空間是相等的，再由 $minimum\ weight$ 來敘述 $d_{min} = w_{min} = 3$。
而由公式我們可以知道 $t=1$ 所以上面 $C3$ 能處理接受的反轉位只有 1，故此我的可以知道上面提到的 $H$ 他的容錯能力只有 1。
## 用 C 實作 Error Correcting Code (Bonus)
:::info
看了這麼多想睡著的理論，相信大家都想動手寫寫 code 了！但是這邊還是容我多說幾句。
動手前，建議不要硬寫，特別是像我這種新手，或許寫得出來功能，但寫出來的 code 讓了解計算機系統的人看到可能會想把它丟進垃圾桶了。這句話的意思是，我們人類最厲害的是什麼？是模仿，我們應該先去看看高手如何寫 Code，看看他們為什麼要這樣寫，並把他們的技巧複製過來。
<img style = "width:400px;height:300px;" src= "https://i.imgur.com/H0R9635.jpg"></img>
沒錯拉，當個拷貝忍者卡卡西拉！但是當你不了解背後的理論，你是無法真正理解為什麼他們要這樣寫，並且你也無法修改他們的 code，所以再動手前，還是要多閱讀。
:::
如果我們看完了 [Hamming codes, Part I](https://www.youtube.com/watch?v=X8jsijhllIA&t=135) ，就馬上開始寫，你可能會寫出將資料切成一塊一塊的 code，來去 parity check，這樣的方式不僅沒效率，也很浪費記憶體空間。
看看 [Hamming codes, Part II](https://www.youtube.com/watch?v=b3NxrZOu_CE&t=7s)，會有啟發。
先舉一例：
```graphviz
digraph structs {
node [shape=plaintext]
struct3 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="9">
<TR>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">1</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b1</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b2</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">1</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b3</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">1</TD>
</TR>
<TR>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b4</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b5</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">1</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b6</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">1</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b7</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
</TR>
<TR>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b8</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b9</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b10</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b11</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">1</TD>
</TR>
<TR>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b12</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b13</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b14</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">1</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b15</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
</TR>
</TABLE>>];
}
```
開始 $Q1$、$Q2$、$Q3$、$Q4$ 依序確認，並且我們令 $Qx$ 得到 odd = 1，even = 0。
$Q1 = 1$
```graphviz
digraph structs {
node [shape=plaintext]
struct3 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="9">
<TR>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">1</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b1</TD>
<TD COLSPAN="1" BGCOLOR="bisque">0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b2</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">1</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b3</TD>
<TD COLSPAN="1" BGCOLOR="bisque">1</TD>
</TR>
<TR>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b4</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b5</TD>
<TD COLSPAN="1" BGCOLOR="bisque">1</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b6</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">1</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b7</TD>
<TD COLSPAN="1" BGCOLOR="bisque">0</TD>
</TR>
<TR>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b8</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b9</TD>
<TD COLSPAN="1" BGCOLOR="bisque">0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b10</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b11</TD>
<TD COLSPAN="1" BGCOLOR="bisque">1</TD>
</TR>
<TR>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b12</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b13</TD>
<TD COLSPAN="1" BGCOLOR="bisque">0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b14</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">1</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b15</TD>
<TD COLSPAN="1" BGCOLOR="bisque">0</TD>
</TR>
</TABLE>>];
}
```
$Q2 = 1$
```graphviz
digraph structs {
node [shape=plaintext]
struct3 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="9">
<TR>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">1</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b1</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b2</TD>
<TD COLSPAN="1" BGCOLOR="bisque">1</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b3</TD>
<TD COLSPAN="1" BGCOLOR="bisque">1</TD>
</TR>
<TR>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b4</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b5</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">1</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b6</TD>
<TD COLSPAN="1" BGCOLOR="bisque">1</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b7</TD>
<TD COLSPAN="1" BGCOLOR="bisque">0</TD>
</TR>
<TR>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b8</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b9</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b10</TD>
<TD COLSPAN="1" BGCOLOR="bisque">0</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b11</TD>
<TD COLSPAN="1" BGCOLOR="bisque">1</TD>
</TR>
<TR>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b12</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b13</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b14</TD>
<TD COLSPAN="1" BGCOLOR="bisque">1</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b15</TD>
<TD COLSPAN="1" BGCOLOR="bisque">0</TD>
</TR>
</TABLE>>];
}
```
$Q3 = 1$
```graphviz
digraph structs {
node [shape=plaintext]
struct3 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="9">
<TR>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">1</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b1</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b2</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">1</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b3</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">1</TD>
</TR>
<TR>
<TD COLSPAN="1" BGCOLOR="bisque">b4</TD>
<TD COLSPAN="1" BGCOLOR="bisque">0</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b5</TD>
<TD COLSPAN="1" BGCOLOR="bisque">1</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b6</TD>
<TD COLSPAN="1" BGCOLOR="bisque">1</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b7</TD>
<TD COLSPAN="1" BGCOLOR="bisque">0</TD>
</TR>
<TR>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b8</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b9</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b10</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b11</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">1</TD>
</TR>
<TR>
<TD COLSPAN="1" BGCOLOR="bisque">b12</TD>
<TD COLSPAN="1" BGCOLOR="bisque">0</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b13</TD>
<TD COLSPAN="1" BGCOLOR="bisque">0</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b14</TD>
<TD COLSPAN="1" BGCOLOR="bisque">1</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b15</TD>
<TD COLSPAN="1" BGCOLOR="bisque">0</TD>
</TR>
</TABLE>>];
}
```
$Q4 = 0$
```graphviz
digraph structs {
node [shape=plaintext]
struct3 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="9">
<TR>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">1</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b1</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b2</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">1</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b3</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">1</TD>
</TR>
<TR>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b4</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b5</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">1</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b6</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">1</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">b7</TD>
<TD COLSPAN="1" BGCOLOR="#E3E3E3">0</TD>
</TR>
<TR>
<TD COLSPAN="1" BGCOLOR="bisque">b8</TD>
<TD COLSPAN="1" BGCOLOR="bisque">0</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b9</TD>
<TD COLSPAN="1" BGCOLOR="bisque">0</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b10</TD>
<TD COLSPAN="1" BGCOLOR="bisque">0</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b11</TD>
<TD COLSPAN="1" BGCOLOR="bisque">1</TD>
</TR>
<TR>
<TD COLSPAN="1" BGCOLOR="bisque">b12</TD>
<TD COLSPAN="1" BGCOLOR="bisque">0</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b13</TD>
<TD COLSPAN="1" BGCOLOR="bisque">0</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b14</TD>
<TD COLSPAN="1" BGCOLOR="bisque">1</TD>
<TD COLSPAN="1" BGCOLOR="bisque">b15</TD>
<TD COLSPAN="1" BGCOLOR="bisque">0</TD>
</TR>
</TABLE>>];
}
```
並且我們將 $Q4\ Q3\ Q2\ Q1$ = 0111 = 7 ，這意思是 `b7` 這個位置反轉了。
好這個是解答，阿為什麼它可以這樣？
先想想為什麼上面 parity bit 是在 1、2、4、8？
我們將 $Q1$ 的數字 1、3、5 ... 轉成 2 進位你會發現他檢查了所有 xxx1 的數字（ｘ= don't care = 0/1），那 $Q2$ 呢？你會發現他檢查了所有 xx1x 的數字，依此類推 $Q3$ = x1xx、$Q4$ = 1xxx。
然後你把 1、2、4、8 轉成 2 進制，0001、0010、0100、1000，你發現什麼了嗎？ 1、2、4、8 的 2 進制，竟然是 $Q4\ Q3\ Q2\ Q1$ 的基底，換個角度想好了 1、2、4、8 是獨立集合，他們沒有交集，而所有數字都是由他們所組合出來，譬如 7 是由 0001 + 0010 + 0100 所組成的，而因為 1、2、4、8 無法相互生成所以只能由他們作為 parity bit。
$Q4\ Q3\ Q2\ Q1$ 就是在檢查 xxx1、xx1x、x1xx、1xxx，那個位置出現錯誤的 bit，所以組合起來就可以知道錯誤位置。
<img src="https://i.imgur.com/UU5cs5R.jpg"></img>
再來我們要怎麼做 $Q4\ Q3\ Q2\ Q1$ ？更白話來說我們如何做出偶數驗證？其實只要一個 $XOR$ 就解決了！
<img src="https://i.imgur.com/SO43wtK.jpg"></img>
可以看到 $XOR$ 可以檢驗出奇數 1 的位置，我們現在套用 $XOR$ 到上面的例子。
我們將資料為 1 的位置依照 $Q1\ Q2\ Q3\ Q4$ 依序 $XOR$
$Q1$
`b3,b5,b11`
| 位置 | | | | |
| ----- | --- | --- |--- |--- |
|b3|0|0|1|1|
|b5|0|1|0|1|
|b11|1|0|1|1|
|XOR||||
|result|1|1|0|1|
$Q2$
`b2,b3,b6,b11,b14`
| 位置 | | | | |
| ----- | --- | --- |--- |--- |
|b2|0|0|1|0|
|b3|0|0|1|1|
|b6|0|1|1|0|
|b11|1|0|1|1|
|b14|1|1|1|0|
|XOR||||
|result|0|0|1|0|
$Q3$
`b5,b6,b14`
| 位置 | | | | |
| ----- | --- | --- |--- |--- |
|b5|0|1|0|1|
|b6|0|1|1|0|
|b14|1|1|1|0|
|XOR||||
|result|1|1|0|1|
$Q4$
`b11,b14`
| 位置 | | | | |
| ----- | --- | --- |--- |--- |
|b11|1|0|1|1|
|b14|1|1|1|0|
|XOR||||
|result|0|1|0|1|
1101
0010
1101
0101
Sign in with Wallet
Connect another wallet