# Linux 核心專題: 錯誤更正碼原理和應用
> 執行人: MuChengChen
> [解說錄影](https://youtu.be/GN8GIPBnLaM)
## TODO: 閱讀教材和去年報告，理解 ECC 原理
> 研讀 [錯誤更正碼介紹和實作考量](https://hackmd.io/@sysprog/r1wrjOp6a) 和 [2024 年報告](https://hackmd.io/@sysprog/HkxFLnvL0) (含解說錄影和問答)，紀錄學習過程中的疑惑，嘗試排除後，將 ECC 原理和考量整理在本頁
先簡介 3 種易混淆的編碼種類 :
>根據 Todd K. Moon (2005). 《Error Correction Coding Mathematical Methods and Algorithms》Chapter 1.2
* 錯誤更正碼 (Error correction code) : 根據接收到的數位資料，「修正」因透過通訊通道傳輸而可能引入的數位資料錯誤。
* 錯誤偵測碼 (Error detection code) : 根據接收到的數位資料「偵測」錯誤。
* 錯誤控制碼 (Error control code) : 錯誤更正碼與錯誤偵測碼合稱為錯誤控制碼。錯誤控制碼能夠決定一個通訊系統是正常運作還是功能失常。
>根據 中央研究院數學研究所 〈[錯誤更正碼簡介](chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://www.math.sinica.edu.tw/media/pdf/d184/18404.pdf)〉Chapter 1
錯誤更正碼的基本構想是讓資料在傳輸前先經過編碼器 (Encoder) 進行編碼，編碼出來的資料除了原始資料外也包含了多餘的資料 (redundancy)，使得資料存在某種數學的結構，傳輸經過通道 (Channel) 後有可能原始資料或多餘的資料會出錯，此時可以再經由解碼器 (Decoder) 依據資料中包含的數學結構將錯誤的資料修正。
### Single–Error Correcting (SEC) Code
SEC 是錯誤更正碼的一種，可以修正一個位元的錯誤。以下說明 Hamming (7, 4) Code 如何修正錯誤以及其數學運算。
- Hamming Code 的特性，當 $m \geq 3$ 時 :
- Code length : $n = 2^m-1$
- Number of information symbols : $k = 2^m-m-1$
- Number of parity-check symbols : $n-k = m$
- Error-correcting capability : $t = 1$(當最小漢明距離等於3時)
首先，由於在此的每個元素都是在 $S = \{0,1\}$ 集合中，因此 $+$、$-$ 與 $\times$ 都是指二進位制單一位元的運算。而元素和元素間 $+$ 、 $-$ 和 $\newcommand*\xor{\oplus}$ (XOR) 的運算結果相等，因此三者可以互換。
原本的資料為 $d1d2d3d4$，在經過 Hamming (7, 4) Code 編碼後資料變為 $d1d2d3d4p1p2p3$，也就是 Hamming (7, 4) Code 的 code word
其中
$p1$,$p2$,$p3$ 為奇偶校驗碼 (Parity bit)，目的是將集合內(圈內) 1 的個數保持為偶數，因此
$$
\left\{
\begin{array}{c}
p1 \newcommand*\xor{\oplus} d1 \newcommand*\xor{\oplus} d2 \newcommand*\xor{\oplus} d4 = 0\\
p2 \newcommand*\xor{\oplus} d1 \newcommand*\xor{\oplus} d3 \newcommand*\xor{\oplus} d4 = 0\\
p3 \newcommand*\xor{\oplus} d2 \newcommand*\xor{\oplus} d3 \newcommand*\xor{\oplus} d4 = 0\\
\end{array}
\right.
$$
由於 $\newcommand*\xor{\oplus}$ 可以和 $+$ 互換，因此可以列出
$$
\left\{
\begin{array}{c}
d1 + d2 + d4 + p1 = 0 \\
d1 + d3 + d4 + p2 = 0 \\
d2 + d3 + d4 + p3 = 0 \\
\end{array}
\right.
$$
而我們就可以依照上面的規則列出
| d1 | d2 | d3 | d4 | p1 | p2 | p3 |
| --- | --- |:---:| --- | --- | --- |:---:|
| 1 | 1 | 0 | 1 | <font color="#f00">1</font> | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | <font color="#f00">1</font> | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | <font color="#f00">1</font> |
此時就產生了 Hamming (7, 4) Code 的奇偶校驗矩陣 (Parity-check matrix) $H$ :
$$
H = \begin{pmatrix}
1 & 1 & 0 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 1 & 0 & 1 & 0 \\
0 & 1 & 1 & 1 & 0 & 0 & 1\\
\end{pmatrix}
$$
奇偶校驗矩陣的定義為 $Hc^T = 0$，$c$ 為此編碼規則中的 code word 向量。因此若傳輸的 code word 完全正確，則
$$
\begin{pmatrix}
1 & 1 & 0 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 1 & 0 & 1 & 0 \\
0 & 1 & 1 & 1 & 0 & 0 & 1\\
\end{pmatrix}\begin{pmatrix} d1 \\ d2 \\ d3 \\ d4 \\ p1 \\ p2 \\ p3 \end{pmatrix} = \begin{pmatrix} 0\\0\\0 \end{pmatrix}
$$
那 $H$ 如何偵測 code word 出現錯誤呢?
若我們將正確的 code word 向量設為 $c$，錯誤的 code word 向量設為 $e$，則
$$
H(c + e)^T = Hc^T + He^T = 0 + He^T = He^T
$$
$He^T$ 就會是錯誤 code word 的 Syndrome，再比對 $H$ 矩陣第幾行和 $He^T$ 一樣就可以知道 $e$ 向量是第幾個位元出錯，進而翻轉該位元進行修正。
我們可以理解為由於出錯的位元在運算上述三條規則時必然出錯，出錯的規則必定是該位元有參與運算的規則，且出錯時結果必為 1，由此我們就可以定位該位元是第幾個位元。
- 例子:
設傳輸正確的 code word 向量為 $c=\begin{pmatrix} 0 & 0 & 1 & 0 & 0 & 1 & 1 \end{pmatrix}$，傳輸錯誤的 code word 向量為 $e=\begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$
$$
H(c + e)^T = \begin{pmatrix}
1 & 1 & 0 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 1 & 0 & 1 & 0 \\
0 & 1 & 1 & 1 & 0 & 0 & 1\\\end{pmatrix}(\begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix} + \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}) = (\begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}+\begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix})
$$
可以看到 $\begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}$ 和 $H$ 矩陣第二行一樣，由此可以得知 $e$ 向量第二位元出錯，將第二位元翻轉後再驗算一次
$$
\begin{pmatrix}
1 & 1 & 0 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 1 & 0 & 1 & 0 \\
0 & 1 & 1 & 1 & 0 & 0 & 1\\\end{pmatrix}\begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}
$$
可以發現 $e$ 向量成功修正成正確的 code word
然而經過上面的推算可以知道，若是 code word 有兩個位元出錯則無法經由奇偶校驗矩陣定位兩個出錯位元的位置，因此 Hamming (7, 4) Code 只能修正一個位元的錯誤
再來我們可以將
$$
\left\{
\begin{array}{c}
p1 \newcommand*\xor{\oplus} d1 \newcommand*\xor{\oplus} d2 \newcommand*\xor{\oplus} d4 = 0\\
p2 \newcommand*\xor{\oplus} d1 \newcommand*\xor{\oplus} d3 \newcommand*\xor{\oplus} d4 = 0\\
p3 \newcommand*\xor{\oplus} d2 \newcommand*\xor{\oplus} d3 \newcommand*\xor{\oplus} d4 = 0\\
\end{array}
\right.
$$
推導成
$$
\left\{
\begin{array}{c}
p1 = d1 \newcommand*\xor{\oplus} d2 \newcommand*\xor{\oplus} d4\\
p2 = d1 \newcommand*\xor{\oplus} d3 \newcommand*\xor{\oplus} d4\\
p3 = d2 \newcommand*\xor{\oplus} d3 \newcommand*\xor{\oplus} d4\\
\end{array}
\right.
$$
因此我們可以藉由傳來的資料進行奇偶校驗碼的推算
- 例子:
當傳輸進來的資料是 $1001$
經過 $p1 = 1 \newcommand*\xor{\oplus} 0 \newcommand*\xor{\oplus} 1 = 0$ ， $p2 = 1 \newcommand*\xor{\oplus} 0 \newcommand*\xor{\oplus} 1 = 0$ ， $p3 = 0 \newcommand*\xor{\oplus} 0 \newcommand*\xor{\oplus} 1 = 1$ 的編碼後資料變為 $1001001$
而我們就可以依照上面的規則列出
| <font color="#008000">要計算的位元</font><br><font color="#007FF">每列代表的位元</font>| <font color="#008000">d1</font> | <font color="#008000">d2</font> | <font color="#008000">d3</font> | <font color="#008000">d4</font> | <font color="#008000">p1</font> | <font color="#008000">p2</font> | <font color="#008000">p3</font> |
|:---:| --------------------------- | --------------------------- | --------------------------- | --------------------------- | --- | --- |:---:|
| <font color="#007FF">d1</font> | <font color="#f00">1</font> | 0 | 0 | 0 | 1 | 1 | 0 |
| <font color="#007FF">d2</font> | 0 | <font color="#f00">1</font> | 0 | 0 | 1 | 0 | 1 |
| <font color="#007FF">d3</font> | 0 | 0 | <font color="#f00">1</font> | 0 | 0 | 1 | 1 |
| <font color="#007FF">d4</font> | 0 | 0 | 0 | <font color="#f00">1</font> | 1 | 1 | 1 |
此時就產生了 Hamming (7, 4) Code 的生成矩陣 G :
$$
G = \begin{pmatrix}
1 & 0 & 0 & 0 & 1 & 1 & 0 \\
0 & 1 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 & 0 & 1 & 1\\
0 & 0 & 0 & 1 & 1 & 1 & 1\\
\end{pmatrix}
$$
我們可以利用生成矩陣將資料編碼
$$
\begin{pmatrix} d1&d2&d3&d4 \end{pmatrix}\begin{pmatrix}
1 & 0 & 0 & 0 & 1 & 1 & 0 \\
0 & 1 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 & 0 & 1 & 1\\
0 & 0 & 0 & 1 & 1 & 1 & 1\\
\end{pmatrix} = \begin{pmatrix} d1&d2&d3&d4&p1&p2&p3 \end{pmatrix}
$$
- 例子 :
當有一資料為 $1010$
$$
\begin{pmatrix} 1 & 0 & 1 & 0 \end{pmatrix}\begin{pmatrix}
1 & 0 & 0 & 0 & 1 & 1 & 0 \\
0 & 1 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 & 0 & 1 & 1\\
0 & 0 & 0 & 1 & 1 & 1 & 1\\
\end{pmatrix} = \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{pmatrix}
$$
$1010101$ 為編碼過後的資料，也就是 code word
再來提一下編位元率 (Code rate)，編位元率是指資料中非冗餘資料的比例，以 Hamming (7, 4) Code 而言 編位元率 = $\dfrac{4}{7}$ = $57.14\%$
#### 漢明距離 (Hamming distance) 和 漢明權重 (Hamming weight)
漢明距離的定義為「兩個等長符號字串之間對應位置上符號不同的位置數」
- 例子 :
$1010101$ 和 $0010011$ 的漢明距離為 3
漢明權重的定義為「符號字串與該符號表中的零符號不同的符號數」，也可以視為符號字串與相等長度全零符號字串間的漢明距離
- 例子 :
$1010101$ 的漢明權重為 4，$1010101$ 和 $0000000$ 的漢明距離也為 4
接下來說明如何計算一個編碼系統 $C$ 的最小距離
假設 $C$ 為 linear block code，$v$ 和 $u$ 為此編碼系統中任意兩個編碼向量，$d(v,u)$ 表示 $v$ 和 $u$ 的漢明距離，$w(v+u)$ 表示 $v+u$ 的漢明權重，$d_{min}$ 為 $C$ 的最小距離，則
$$
\begin{aligned}
d_{min} &= min \{d(v,u):v,u \in C, v \neq u \}\\
&= min \{d(v-u,u-u):v,u \in C, v \neq u \}\\
&= min \{d(v-u,0):v,u \in C, v \neq u \}\\
&= min \{w(v-u):v,u \in C, v \neq u \}\\
&= min \{w(v+u):v,u \in C, v \neq u \}\\
&= min \{w(x):x \in C, x \neq 0 \}\\
&\equiv w_{min}
\end{aligned}
$$
- 例子:
以 Hamming (7, 4) Code 為例，我們可以發現若是不為 $0000000$ 的 code word 漢明權重必定大於等於 3，如設 $d1,d2,d3,d4$ 任一位元為 $1$，則查看生成矩陣 $G$ 可以發現每一列 $1$ 的總和均為 3 個，因此 Hamming (7, 4) Code 的最小權重為 3，依照上面最小距離的公式推導就可以得知 Hamming (7, 4) Code 的最小距離也為 3。
以下舉簡單的例子，查看漢明距離和可偵測錯誤數量與可修正錯誤數量之間的關係。設 $v$ 和 $u$ 為兩個 code word
| 距離 $d(v,u)$ | 視覺化 code word 距離 (X 為不屬於 code word 系統中的編碼) | 可偵測錯誤種類數量 | 可修正錯誤種類數量 |
|:----:|:---------------------------------------------------:|:--------------:|:--------------:|
| 1 | $v$-$u$ | 0 | 0 |
| 2 | $v$-X-$u$ | 1 | 0 |
| 3 | $v$-<font color="#f00">X</font>-<font color="#007FFF">X</font>-$u$ | 2 | 1 |
| 4 | $v$-<font color="#f00">X</font>-X-<font color="#007FFF">X</font>-$u$ | 3 | 1 |
| 5 | $v$-<font color="#f00">X</font>-<font color="#f00">X</font>-<font color="#007FFF">X</font>-<font color="#007FFF">X</font>-$u$ | 4 | 2 |
| 6 | $v$-<font color="#f00">X</font>-<font color="#f00">X</font>-X-<font color="#007FFF">X</font>-<font color="#007FFF">X</font>-$u$ | 5 | 2 |
由於 <font color="#f00">X</font> 較靠近 $v$，因此若是錯誤碼落在 <font color="#f00">X</font> 則可以修正為 $v$ ，反之若錯誤碼落在 <font color="#007FFF">X</font> 則可以修正為 $u$，但若是錯誤碼落在 X 則因為和 $u$ 與 $v$ 的距離一樣故無法修正。另外只要錯誤碼落在 <font color="#f00">X</font> , <font color="#007FFF">X</font> 或 X 都可以偵測到錯誤。從例子中可以發現可偵測錯誤種類數量為 $d-1$ ，可修正錯誤種類數量為 $\lfloor \dfrac{d-1}{2} \rfloor$。通則為若是一個 block code 的最小距離為 $d_{min}$，則可偵測錯誤種類數量為 $d_{min}-1$，可修正錯誤種類數量為 $\lfloor \dfrac{d_{min}-1}{2} \rfloor$。
### Reed–Solomon error correcting code
#### 先備知識 : 群 (Group)
>參考 [〈大學基礎代數〉](chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://math.ntnu.edu.tw/~li/algebra-html/chap1.pdf) 李華介 著
一個集合 $G$ 若元素間有一個運算 $*$ 符合下列性質則稱為一個 群 (group) :
1. 封閉性：若 $a,b \in G$ 則 $a*b \in G$
2. 結合性：若 $a,b,c \in G$ 則 $(a*b)*c=a*(b*c)$
3. 單位元素：在 $G$ 中存在一個元素 $e$ 使得 $G$ 中所有元素 $g$ 都有 $g*e=e*g=g$，我們稱 $e$ 為 identity
4. 反元素：對 $G$ 任一元素 $g$ 都可在 $G$ 中找到某一元素 $g'$ 使得 $g*g'=g'*g = e$，我們稱 $g'$ 為 $g$ 的 inverse
阿貝爾群 (Abelian group) 又稱 交換群 (Commutative group) 定義 :
- 若 $G$ 是一個 群 且對任意的 $a,b \in G$ 都有 $a*b=b*a$ ，則稱 $G$ 為一個阿貝爾群
另外若 $G$ 是一個 群 且只有有限多個元素，則稱 $G$ 為一個 finite group；若 $G$ 中元素的個數為 n，則我們稱 $G$ 是一個 order n 的 群，通常用 $|G|=n$ 表示。
群 的性質:
1. 若 $G$ 是一個 群，則 $G$ 中只有唯一的元素會符合 identity 的性質
2. 若 $G$ 是一個 群，給定 $G$ 中任一元素 $a$ ，則在 $G$ 中只有唯一的元素 $b$ 會符合 $a*b=b*a=e$
3. 若 $G$ 是一個 群，給定 $G$ 中任意元素 $a$ 和 $b$ ，則方程式 $a*x=b$ 在 $G$ 中有解且其解唯一，同理，方程式 $y*a=b$ 在 $G$ 中也有唯一解
4. 若 $G$ 是一個 群，給定 $G$ 中任意元素 $a$ 和 $b$ ，則 $(a^{-1})^{-1}=a$ 且 $(a*b)^{-1}=b^{-1}*a^{-1}$
#### 先備知識 : 環 (Ring)
>參考 [〈大學基礎代數〉](chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://math.ntnu.edu.tw/~li/algebra-html/chap1.pdf) 李華介 著
環 (Ring) 的結構比 群 豐富， 環 必須有兩種運算。
一個集合 $R$ 中如果有兩種運算 (以 $+$ (加法) 和 $\times$ (乘法) 表示) 且符合以下性質，則稱之為一個 環 :
1. 對任意的 $a,b \in R$ 皆有 $a+b \in R$
2. 對任意的 $a,b,c \in R$ 皆有 $(a+b)+c=a+(b+c)$
3. 在 $R$ 中存在一元素定之為 $0$ 滿足對任意的 $a \in R$ 皆有 $a+0=0+a=a$
4. 給定 $R$ 中任一元素 $a$，在 $R$ 中皆存在一元素 $b$ 滿足 $a+b=b+a=0$
5. 對任意的 $a,b \in R$ 皆有 $a+b=b+a$
6. 對任意的 $a,b \in R$ 皆有 $a \times b \in R$
7. 對任意的 $a,b,c \in R$ 皆有 $(a \times b) \times c=a \times (b \times c)$
8. 對任意的 $a,b,c \in R$ 皆有 $a \times (b+c)=a \times b+a \times c$ 且 $(b+c) \times a=b \times a+c \times a$
環 的性質 :
1. 假設 $R$ 是一個 環 ，則 :
(1) 對任意的 $a \in R$，$-(-a)=a$
(2) 若 $a,b \in R$ 則存在一個唯一的 $c \in R$ 滿足 $a+c=b$
2. 假設 $R$ 是一個 環 且 $0$ 是其加法的 identity，則對任意的 $a \in R$ 皆有 $a \times 0=0 \times a=0$
3. 假設 $R$ 是一個 環 ，則對任意的 $a,b \in R$ 皆有 $a*(-b)=(-a)*b=-(a*b)$
4. 假設 $R$ 是一個 環 且 $a,b \in R$ 則 $(-a) \times (-b)=a \times b$
5. 令 $R$ 是一個 環 ，若 $a \neq 0$ 是 $R$ 中的一個元素且在 $R$ 中存在 $b \neq 0$ 使得 $a \times b=0$ 或 $b \times a=0$，則稱 $a$ 是 $R$ 的一個 zero-devisor
6. 當 $a \in R$ 不是 環 $R$ 中的 zero-devisor 時，若 $a \times b=a \times c$ 或 $b \times a=c \times a$，則 $b=c$
7. 如果 $R$ 是一個 環 且 $R$ 中沒有 zero-divisor，則稱 $R$ 是一個 domain。如果 $R$ 是一個 commutative ring with $1$ 且是一個 domain，則稱之為一個 integral domain
8. 若 $R$ 是一個 ring with $1$ ，如果 $a \in R$ 且存在 $b \in R$ 使得 $a \times b=b \times a=1$，則稱 $a$ 是 $R$ 的一個 unit
9. 若 $R$ 是一個 ring with 1 且 $a \in R$ 是一個 uint，則
(1) $a$ 絕對不會是 $0$，也不會是 $R$ 中的一個 zero-divisor
(2) 對任意的 $b \in R$，方程式 $a \times x=b$ 和 $y \times a=b$ 在 $R$ 中都會有唯一的解
10. 若 $R$ 是一個 ring with 1 且 $R$ 中非 $0$ 的元素都是 unit，則稱 $R$ 是一個 division ring。若 $R$ 是一個 commutative ring 且是一個 division ring，則稱 $R$ 是一個 <font color="#007FFF">體(field)</font>
#### 先備知識 : 體 (Field)
>參考 [〈大學基礎代數〉](chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://math.ntnu.edu.tw/~li/algebra-html/chap1.pdf) 李華介 著
若 $F$ 是一個 體 (field) ，則 $F$ 中的 $+$ (加法) 和 $\times$ (乘法) 必須滿足以下環的性質
>一個集合 $R$ 中如果有兩種運算 (以 $+$ (加法) 和 $\times$ (乘法) 表示) 且符合以下性質，則稱之為一個 環 :
1. 對任意的 $a,b \in R$ 皆有 $a+b \in R$
2. 對任意的 $a,b,c \in R$ 皆有 $(a+b)+c=a+(b+c)$
3. 在 $R$ 中存在一元素定之為 $0$ 滿足對任意的 $a \in R$ 皆有 $a+0=0+a=a$
4. 給定 $R$ 中任一元素 $a$，在 $R$ 中皆存在一元素 $b$ 滿足 $a+b=b+a=0$
5. 對任意的 $a,b \in R$ 皆有 $a+b=b+a$
6. 對任意的 $a,b \in R$ 皆有 $a \times b \in R$
7. 對任意的 $a,b,c \in R$ 皆有 $(a \times b) \times c=a \times (b \times c)$
8. 對任意的 $a,b,c \in R$ 皆有 $a \times (b+c)=a \times b+a \times c$ 且 $(b+c) \times a=b \times a+c \times a$
還必須額外滿足 :
1. 對任意 $a,b \in F$ 皆滿足 $a \times b=b \times a$，要求 $F$ 是一個 commutative ring with 1
2. 存在 $1 \in F$ 使得對任意 $a \in F$ 皆滿足 $a \times 1=1 \times a=a$，要求 $F$ 是一個 commutative ring with 1
3. 對任意 $a \in F$ 且 $a \neq 0$，皆存在 $a^{-1} \in F$ 使得 $a \times a^{-1}=a^{-1} \times a=1$，要求 $F$ 中不為 $0$ 的元素都是 unit
體 的性質 :
1. 若 $F$ 是一個 體，則 $F$ 是一個 integral domain
2. 假設 $F$ 是一個 體，令 $F^*=F \setminus \{0\}$ 表示 $F$ 中不為 $0$ 的元素所成的集合，則 $F^*$ 在乘法的運算之下是一個 阿貝爾群
3. 假設 $F$ 是一個 體 且 $S \subseteq F$ 。如果對任意 $a,b \in S$，其中 $b \neq 0$ 皆有 $a-b \in S$ 且 $a \times b^{-1} \in S$，則 $S$ 是 $F$ 的 subfield
4. 假設 $F$ 是一個 體 ，則對 $F$ 下面兩種情況之一會發生:
(1) 對任意 $n \in \mathbb{N}$ 且 $a \in F \setminus \{0\}$ 皆有 $na \neq 0$
(2) 存在一個 prime $p \in \mathbb{N}$ 使得對任意的 $a \in F$ 皆有 $pa=0$
5. 假設 $F$ 是一個 體，若對任意的 $n \in \mathbb{N}$ 且 $a \in F \setminus \{0\}$ 皆有 $na \neq 0$，則稱 $F$ 的 特徵 (characteristic) 是 $0$，記為 $char(F)=0$。反之若存在 $p \in \mathbb{N}$ 是 $\mathbb{Z}$ 中的 質數 使得對任意的 $a \in F$ 皆有 $pa=0$，則稱 $F$ 的 特徵 是 $p$，記為 $char(F)=p$
- 註記 : 若存在正整數 $n$ 使得 $0 = 1 + 1 + \dots + 1$ （n個1），那麼這樣的 $n$ 中最小的一個稱為這個體的 特徵 (characteristic)，特徵要麼是一個質數 $p$，要麼是 $0$ （表示這樣的 $n$ 不存在）。此時 $F$ 中最小的子體分別是 有理數體 $\mathbb{Q}$ 或有限體 $\mathbb {F}_{p}$，稱之為 $F$ 的素體。
6. 若 $F$ 是一個 <font color="#007FFF">有限體 (finite field)</font>，則存在一 質數 $p \in \mathbb{N}$ 使得 $char(F)=p$
7. 假設 $F$ 是一個 體 且 $char(F)=p \neq 0$，則對任意 $a,b \in F$
$$
(a+b)^{p^n}=a^{p^n}+b^{p^n}\ 和\ (a-b)^{p^n}=a^{p^n}-b^{p^n},\forall n \in \mathbb{N}
$$
8. 假設 $F$ 是一個 體 且 $char(F)=p \neq 0$，則對任意 $f(x)=a_{m}x^m+ \dots +a_{0} \in F[x]$，會有
$$
(f(x))^{p^n}=a_{m}^{p^n}x^{mp^n}+ \dots +a_{0}^{p^n} ,\forall n \in \mathbb{N}
$$
特別當 $a \in F$ 時，會有
$$
(x-a)^{p^n}=x^{p^n}+a^{p^n},\forall n \in \mathbb{N}
$$
#### 先備知識 : 伽羅瓦體 (Galois field) 或 有限體 (finite field)
>參考 [〈大學基礎代數〉](chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://math.ntnu.edu.tw/~li/algebra-html/chap1.pdf) 李華介 著
若 $F$ 是一個 有限體 (finite field) ，則 $F$ 的元素個數 (通常用 $|F|$ 表示)是有限多個，因此 F 的 特徵 一定是一個質數 $p$ 。
有限體 的性質 :
1. 假設 $F$ 是一個 有限體 且 $char(F)=p$，則 $F$ 中存在一個 子域 (subfield) $\mathbb{F}_{p}$ ，其中 $|\mathbb{F}_{p}|=p$ 且和 $\mathbb{Z}/(p)$ 同構 (isomorphic) ，而且 $F$ 是 $\mathbb{F}_{p}$ 的一個 finite extension。若 $[F:\mathbb{F}_{p}]=k$ ，則 $|F|=p^k$
2. 假設 $F$ 是一個 有限體 且 $|F|=p^k$ 。令 $f(x)=x^{p^k}-x$，則對任意 $a \in F$ 皆符合 $f(a)=0$ 且 $f(x)$ split linear factor in $F$ 。事實上有
$$
x^{p^k}-x=\prod_{a \in F} (x-a)
$$
3. 假設 $F$ 是一個 有限體 ，則 $F^*=F \setminus \{0\}$ 看成是一個乘法的 群 時是一個 循環群 (cyclic group)
4. 假設 $F$ 是一個 有限體 且 $|F|=p^k$ ，則存在 $a \in F$ 滿足 $\mathbb{F}_{p}(a)=F$ 且 $a$ over $\mathbb{F}_{p}$ 的 degree 為 $k$
5. 給定任一質數 $p$ 以及 $k \in \mathbb{N}$，一定存在一個 有限體 $F$ 滿足 $|F|=p^k$
6. 假設 $\mathbb{F}_{p}$ 是一個有 $p$ 個元素的 有限體，則對任意 $k \in \mathbb{N}$ ，皆存在 $g(x) \in \mathbb{F}_{p}[x]$ 在 $\mathbb{F}_{p}[x]$ 中是 不可約的 (irreducible) ，且 $deg(g(x))=k$
7. 假設 $\mathbb{F}_{p}$ 是一個有 $p$ 個元素的 有限體 且 $g(x) \in \mathbb{F}_{p}[x]$ 在 $\mathbb{F}_{p}[x]$ 中是 不可約的，若 $deg(g(x))=k$ ，則在 $\mathbb{F}_{p}[x]$ 中 $g(x)|x^{p^k}-x$
8. 假設 $K$ 和 $L$ 都是 有限體 且 $|K|=|L|$ ，則 $K$ 和 $L$ 之間存在一個 環同構 (ring isomorphism)，也就是說 $K \simeq L$ as rings
- 例子 :
假設 $G𝐹(p)$ 是一個 有限體，則 $G𝐹(7) \equiv \mathbb{Z}_{7}$，以下是 $G𝐹(7)$ 加法和乘法的表格
加法 : $(a+b)$ $mod(7)$
| <font color="#007FFF">**+**</font> | <font color="#C19A6B">0</font> | <font color="#C19A6B">1</font> | <font color="#C19A6B">2</font> | <font color="#C19A6B">3</font> | <font color="#C19A6B">4</font> | <font color="#C19A6B">5</font> | <font color="#C19A6B">6</font> |
| --- |:---:| --- | --- | --- | --- | --- |:---:|
| <font color="#C19A6B">**0**</font> | ==0== | 1 | 2 | 3 | 4 | 5 | 6 |
| <font color="#C19A6B">**1**</font> | 1 | 2 | 3 | 4 | 5 | 6 | ==0== |
| <font color="#C19A6B">**2**</font> | 2 | 3 | 4 | 5 | 6 | ==0== | 1 |
| <font color="#C19A6B">**3**</font> | 3 | 4 | 5 | 6 | ==0== | 1 | 2 |
| <font color="#C19A6B">**4**</font> | 4 | 5 | 6 | ==0== | 1 | 2 | 3 |
| <font color="#C19A6B">**5**</font> | 5 | 6 | ==0== | 1 | 2 | 3 | 4 |
| <font color="#C19A6B">**6**</font> | 6 | ==0== | 1 | 2 | 3 | 4 | 5 |
乘法 : $(a \times b)$ $mod(7)$
| <font color="#007FFF">**$\times$**</font> | <font color="#C19A6B">0</font> | <font color="#C19A6B">1</font> | <font color="#C19A6B">2</font> | <font color="#C19A6B">3</font> | <font color="#C19A6B">4</font> | <font color="#C19A6B">5</font> | <font color="#C19A6B">6</font> |
| --- |:---:| --- | --- | --- | --- | --- |:---:|
| <font color="#C19A6B">**0**</font> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <font color="#C19A6B">**1**</font> | 0 | ==1== | 2 | 3 | 4 | 5 | 6 |
| <font color="#C19A6B">**2**</font> | 0 | 2 | 4 | 6 | ==1== | 3 | 5 |
| <font color="#C19A6B">**3**</font> | 0 | 3 | 6 | 2 | 5 | ==1== | 4 |
| <font color="#C19A6B">**4**</font> | 0 | 4 | ==1== | 5 | 2 | 6 | 3 |
| <font color="#C19A6B">**5**</font> | 0 | 5 | 3 | ==1== | 6 | 4 | 2 |
| <font color="#C19A6B">**6**</font> | 0 | 6 | 5 | 4 | 3 | 2 | ==1== |
依照上面的表可以知道元素之間的對應 :
| <font color="#007FFF">$a$</font> | <font color="#007FFF">$-a$</font> | <font color="#007FFF">$a^{-1}$</font> |
| ---------------------------------- |:---------------------------------:| ------------------------------------- |
| <font color="#C19A6B">**0**</font> | 0 | - |
| <font color="#C19A6B">**1**</font> | 6 | 1 |
| <font color="#C19A6B">**2**</font> | 5 | 4 |
| <font color="#C19A6B">**3**</font> | 4 | 5 |
| <font color="#C19A6B">**4**</font> | 3 | 2 |
| <font color="#C19A6B">**5**</font> | 2 | 3 |
| <font color="#C19A6B">**6**</font> | 1 | 6 |
>參考 [〈finite field〉](https://web.ntnu.edu.tw/~algo/FiniteField.html)
若是將 有限體 應用在 錯誤更正碼，因為電腦採用的是二進位，所以常會以 $GF(2^n)$ 表示，有限體的質數設為 $2$。因此，由於當模數是質數 $p$，係數的範圍就是 $0$ 到 $p-1$，所以當 $GF(2^n)$ 的模數是 $2$，係數範圍是 $0$ 到 $1$；由於當模數是質式（ $n$ 次餘數多項式），次方範圍就是 $0$ 到 $n-1$，所以當 $GF(2^n)$ 模數是質式（ $n$ 次餘數多項式），次方範圍就是 $0$ 到 $n-1$ 。另外，在 $GF(2^n)$ 的情況下， 正號 等於 負號 ， 加法 等於 減法 等於 $\newcommand*\xor{\oplus}$ (XOR) 。
關於 $GF(2^n)$ 的 質式 (Irreducible Polynomials) 可以參考 [此表](https://www.ece.unb.ca/tervo/ee4253/polyprime.shtml)，當我們在 $GF(2^n)$ 中運算時都需要取模，而取模所使用的除式就是 $GF(2^n)$ 的質式。
- 例子 :
舉 $G𝐹(2^3)$ 為例
$G𝐹(2^3)$ 的質式 為 $x^3+x+1$ ，若是以二進位制表示為 $1011$ ，可以對應為 $1x^3+0x^2+1x+1$ 。
加法 : $(a+b)$ $mod(x^3+x+1)$ ($a$ 和 $b$ 為對應的多項式)
| <font color="#007FFF">**+**</font> | <font color="#C19A6B">0 (000)</font> | <font color="#C19A6B">1 (001)</font> | <font color="#C19A6B">2 (010)</font> | <font color="#C19A6B">3 (011)</font> | <font color="#C19A6B">4 (100)</font> | <font color="#C19A6B">5 (101)</font> | <font color="#C19A6B">6 (110)</font> | <font color="#C19A6B">7 (111)</font> |
|:----------------------------------------:|:------------------------------------:|:------------------------------------:|:------------------------------------:|:------------------------------------:|:------------------------------------:|:------------------------------------:|:------------------------------------:|:------------------------------------:|
| <font color="#C19A6B">**0 (000)**</font> | ==0== | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| <font color="#C19A6B">**1 (001)**</font> | 1 | ==0== | 3 | 2 | 5 | 4 | 7 | 6 |
| <font color="#C19A6B">**2 (010)**</font> | 2 | 3 | ==0== | 1 | 6 | 7 | 4 | 5 |
| <font color="#C19A6B">**3 (011)**</font> | 3 | 2 | 1 | ==0== | 7 | 6 | 5 | 4 |
| <font color="#C19A6B">**4 (100)**</font> | 4 | 5 | 6 | 7 | ==0== | 1 | 2 | 3 |
| <font color="#C19A6B">**5 (101)**</font> | 5 | 4 | 7 | 6 | 1 | ==0== | 3 | 2 |
| <font color="#C19A6B">**6 (110)**</font> | 6 | 7 | 4 | 5 | 2 | 3 | ==0== | 1 |
| <font color="#C19A6B">**7 <br> (111)**</font> | 7 | 6 | 5 | 4 | 3 | 2 | 1 | ==0== |
以 $(2_{10} + 5_{10})$ $mod(x^3+x+1)$ 為例，
$(2_{10} + 5_{10})$ $mod(x^3+x+1)$
$=(010_{2} + 101_{2})$ $mod(x^3+x+1)$
$=(x + (x^2+1))$ $mod(x^3+x+1)$
$=(x^2+x+1)$ $mod(x^3+x+1)$
$=(x^2+x+1)$
$=111_{2}$
$=7_{10}$
再來由於 加法 等於 減法 等於 $\newcommand*\xor{\oplus}$ ，因此相同數字 相加 等於 相減 等於 多項式係數轉換成二進位制再相互 $\newcommand*\xor{\oplus}$，結果為 $0$
乘法 : $(a \times b)$ $mod(x^3+x+1)$ ($a$ 和 $b$ 為對應的多項式)
| <font color="#007FFF">**$\times$**</font> | <font color="#C19A6B">0 (000)</font> | <font color="#C19A6B">1 (001)</font> | <font color="#C19A6B">2 (010)</font> | <font color="#C19A6B">3 (011)</font> | <font color="#C19A6B">4 (100)</font> | <font color="#C19A6B">5 (101)</font> | <font color="#C19A6B">6 (110)</font> | <font color="#C19A6B">7 (111)</font> |
|:----------------------------------------:|:------------------------------------:|:------------------------------------:|:------------------------------------:|:------------------------------------:|:------------------------------------:|:------------------------------------:|:------------------------------------:|:------------------------------------:|
| <font color="#C19A6B">**0 (000)**</font> | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <font color="#C19A6B">**1 (001)**</font> | 0 | ==1== | 2 | 3 | 4 | 5 | 6 | 7 |
| <font color="#C19A6B">**2 (010)**</font> | 0 | 2 | 4 | 6 | 3 | ==1== | 7 | 5 |
| <font color="#C19A6B">**3 (011)**</font> | 0 | 3 | 6 | 5 | 7 | 4 | ==1== | 2 |
| <font color="#C19A6B">**4 (100)**</font> | 0 | 4 | 3 | 7 | 6 | 2 | 5 | ==1== |
| <font color="#C19A6B">**5 (101)**</font> | 0 | 5 | ==1== | 4 | 2 | 7 | 3 | 6 |
| <font color="#C19A6B">**6 (110)**</font> | 0 | 6 | 7 | ==1== | 5 | 3 | 2 | 4 |
| <font color="#C19A6B">**7 <br> (111)**</font> | 0 | 7 | 5 | 2 | ==1== | 6 | 4 | 3 |
以 $(2_{10} \times 5_{10})$ $mod(x^3+x+1)$ 為例，
$(2_{10} \times 5_{10})$ $mod(x^3+x+1)$
$=(010_{2} \times 101_{2})$ $mod(x^3+x+1)$
$=(x \times (x^2+1))$ $mod(x^3+x+1)$
$=(x^3+x)$ $mod(x^3+x+1)$
$=-1$
$=1_{2}$
$=1_{10}$
依照上面的表可以知道元素之間的對應 :
| <font color="#007FFF">$a$</font> | <font color="#007FFF">$-a$</font> | <font color="#007FFF">$a^{-1}$</font> |
| ---------------------------------- |:---------------------------------:|:-------------------------------------:|
| <font color="#C19A6B">**0**</font> | 0 | - |
| <font color="#C19A6B">**1**</font> | 1 | 1 |
| <font color="#C19A6B">**2**</font> | 2 | 5 |
| <font color="#C19A6B">**3**</font> | 3 | 6 |
| <font color="#C19A6B">**4**</font> | 4 | 7 |
| <font color="#C19A6B">**5**</font> | 5 | 2 |
| <font color="#C19A6B">**6**</font> | 6 | 3 |
| <font color="#C19A6B">**7**</font> | 7 | 4 |
另外我們也可以利用下面的轉換表使得運算更為簡單
| <font color="#007FFF">word</font> | <font color="#007FFF">$x^i$ $mod$ $p(x)$</font> |
| ------------------------------------ |:-----------------------------------------------:|
| <font color="#C19A6B">**001**</font> | $1$ |
| <font color="#C19A6B">**010**</font> | $x$ |
| <font color="#C19A6B">**100**</font> | $x^2$ |
| <font color="#C19A6B">**011**</font> | $x^3 \equiv x+1$ |
| <font color="#C19A6B">**110**</font> | $x^4 \equiv x^2+x$ |
| <font color="#C19A6B">**111**</font> | $x^5 \equiv x^2+x+1$ |
| <font color="#C19A6B">**101**</font> | $x^6 \equiv x^2+1$ |
以 $(3_{10} \times 4_{10})$ $mod(x^3+x+1)$ 為例，
$(3_{10} \times 4_{10})$ $mod(x^3+x+1)$
$=(011_{2} \times 100_{2})$ $mod(x^3+x+1)$
$=((x+1) \times x^2)$ $mod(x^3+x+1)$
$\equiv (x^3 \times x^2)$ $mod(x^3+x+1)$
$=x^5$ $mod(x^3+x+1)$
$\equiv (x^2+x+1)$ $mod(x^3+x+1)$
$=111_{2}$
$=7_{10}$
因此我們也可以寫成
| | |
|:----------------------------------------------------:|:---------:|
| <font color="#C19A6B">**$\alpha$**</font> | $z$ |
| <font color="#C19A6B">**$\alpha^2$**</font> | $z^2$ |
| <font color="#C19A6B">**$\alpha^3$**</font> | $z+1$ |
| <font color="#C19A6B">**$\alpha^4$**</font> | $z^2+z$ |
| <font color="#C19A6B">**$\alpha^5$**</font> | $z^2+z+1$ |
| <font color="#C19A6B">**$\alpha^6$**</font> | $z^2+1$ |
| <font color="#C19A6B">**$\alpha^7=\alpha^0$**</font> | $1$ |
在解多項式根的時候可以以上表作為轉換
#### Reed–Solomon error correcting code 介紹
>根據 [<里德所羅門碼之運算分析>](https://ir.lib.nycu.edu.tw/bitstream/11536/47106/2/362702.pdf) 國立交通大學 林詩倩 著
Reed–Solomon code 為一 線性區塊碼 (linear block code)，是非二元 BCH 碼(nonbinary BCH codes) 的一種特例。
$(n,k,t)$ Reed–Solomon code 表示將長度為 $k$ 的訊息符號元序列編碼成長度為 $n$ 的 code word 符號元序列，最多可改正 $t$ 個錯誤符號元，而其中每一個訊息符號元及碼字符號元皆為 $GF(2^m)$ 中的元素，而奇偶查核符號元個數為 $n-k$ 個，且需滿足 $n−k = 2t$ 的條件。由此得知，每個符號元都包含了 $m$ 個位元訊息，故此特性使它可有效的更正 叢集錯誤 (burst errors) ，因為無論一個符號元中有多少個位元發生錯誤，都僅表示為一個符號元發生錯誤。
#### Reed–Solomon code 編碼
若傳輸的訊息為 $m=[m_0,m_1,\dots,m_{k-1}]$ ，則訊息多項式 $p(x)$ 為
$$
p(x)=m_0+m_1x+m_2x^2+\dots+m_{k-1}x^{k-1},m_{i,0 \leq i \leq k-1} \in GF(2^m)
$$
此為非系統化編碼，解碼較困難故較少被拿來做應用
系統化編碼的過程分為以下三個步驟 :
1. 將訊息多項式 $p(x)$ 乘上 $x^{n-k}$
$$
x^{n-k}p(x)= m_0 x^{n-k}+m_1x^{n-k+1}+\dots+m_{k-1}x^{n-1}
$$
2. 將 $x^{n-k}p(x)$ 除以 生成多項式 $g(x)$ 以得到 奇偶查核多項式 $b(x)$
- 生成多項式:
$$
\begin{aligned}
g(x) &= (x- \alpha^i)(x- \alpha^{i+1})\dots(x- \alpha^{i+n-k-1})\\ &= g_0+g_1 x+\dots+g_{n-k-1}x^{n-k-1}+x^{n-k}\\ &= g_0+g_1 x+\dots+g_{2t-1}x^{2t-1}+x^{2t},g_{i,0 \leq i \leq 2t-1} \in GF(2^m)
\end{aligned}
$$
狹義來說， $i=1$，然而在 CD、QR codes 和 DVB-T 中使用 $i=0$
接下來運算 $b(x)$
$$
\begin{aligned}
x^{n-k}p(x)=a(x)g(x)+b(x)\\
b(x)+x^{n-k}p(x)=a(x)g(x)\\
\end{aligned}
$$
(由於在 $GF(2^m)$ 中 加號 等於 減號，因此 $-b(x)$ 變為 $+b(x)$)
其中 $a(x)$ 和 $b(x)$ 分別為商式和餘式，
而 $b(x)=b_0+b_1x+\dots+b_{n-k-1}x^{n-k-1},b_{i,0 \leq i \leq n-k-1} \in GF(2^m)$ 。
3. 將 $b(x)$ 和 $x^{n-k}p(x)$ 相加，得到 code word 多項式 $c(x)$
$$
\begin{aligned}
c(x) &= b(x)+x^{n-k}p(x)\\
&= b_0+b_1x+\dots+b_{n-k-1}x^{n-k-1}+
m_0+m_1x+m_2x^2+\dots+m_{k-1}x^{k-1}
\end{aligned}
$$
因此， code word 為 $(b_0,b_1,\dots,b_{n-k-1},m_0,m_1,\dots,m_{k-1})$ 。
由於 code word 多項式含有 $g(x)$ 的因式，因此若接收端收到的訊號發生錯誤，則接收的訊號多項式必不含 $g(x)$ 的因式。
#### Reed–Solomon code 解碼
以下為 Reed–Solomon code 的解碼流程圖
假設接收到的訊號多項式為 $r(x)$ :
$$
r(x)=r_0+r_1x+\dots+r_{n-1}x^{n-1},r_{i,0 \leq i \leq n-1} \in GF(2^m)
$$
而經過通道傳輸後有可能受到雜訊的干擾，因此訊號包含了傳送的資訊與雜訊，可以表示為 $r(x)=c(x)+e(x)$ ，並假設錯誤多項式為
$$
\begin{aligned}
e(x) &=r(x)-c(x)\\
&=e_0+e_1x+\dots+e_{n-1}x^{n-1},e_{i,0 \leq i \leq n-1} \in GF(2^m)
\end{aligned}
$$
若 $e(x)=0$ 則接收訊號為正確的。
#### Syndrome
由於傳送 訊號多項式 $c(x)$ 是藉由 生成多項式 $g(x)$ 進行編碼，因此若 $r(x)=c(x)$ ，則 $r(x)$ 必定含有 $g(x)$ 的因式，也就是可以被 $g(x)$ 整除，所以 $g(x)$ 的根必為 $r(x)$ 的根，即 徵狀值 (Syndrome) 都為 $0$ 。反之，則表示 $c(x)$ 在傳輸過程中受到雜訊干擾而導致錯誤，即有非零徵狀值出現。
計算 徵狀值 是將 $g(x)$ 所有的根 $\alpha,\alpha^2,\dots,\alpha^{2t}$ 代入 $r(x)$ 中，因此定義 徵狀值 為
$$
S_i=r(\alpha^i)=c(\alpha^i)+e(\alpha^i)=e(\alpha^i),1 \leq i \leq 2t,S_{i,1 \leq i \leq 2t} \in GF(2^m)
$$
可以更正 $t$ 個錯誤的 Reed–Solomon code 會產生 $2t$ 個 徵狀值，我們必須算出所有 $2t$ 個徵狀值來判斷訊號有無錯誤，並可藉此訊息加以更正錯誤。只要其中任一 $S_i \neq 0,1 \leq i \leq 2t$ 就代表接收訊號錯誤。
假設 $e(x)$ 包含了 $v$ 個錯誤符號元，則
$$
e(x)=e_{j_1}x^{j_1}+e_{j_2}x^{j_2}+\dots+e_{j_v}x^{j_v},0 \leq j_1 < j_2 < \dots < j_v \leq n-1
$$
其中 $x^{j_1},x^{j_2},\dots,x^{j_v}$ 為錯誤位置，$e_{j_1},e_{j_2},\dots,e_{j_v}$ 為錯誤的值。
因此我們可以列出
$$
\begin{aligned} &S_1=e_{j_1}\alpha^{j_1}+e_{j_2}\alpha^{j_2}+\dots+e_{j_v}\alpha^{j_v}\\
&S_2=e_{j_1}\alpha^{2j_1}+e_{j_2}\alpha^{2j_2}+\dots+e_{j_v}\alpha^{2j_v}\\
&\vdots\\
&S_{2t}=e_{j_1}\alpha^{2tj_1}+e_{j_2}\alpha^{2tj_2}+\dots+e_{j_v}\alpha^{2tj_v}\\
\end{aligned}
$$
我們需要解出上面的式子才能從中找出符號元的錯誤位置和其對應之錯誤值。
最後，徵狀值的多項式表示式為
$$
\begin{aligned}
S(x)&=S_1+S_2x+ \dots +S_{2t}x^{2t-1}+S_{2t+1}x^{2t}+\dots\\
&=\sum\limits_{j=1}^\infty S_jx^{j-1}
\end{aligned}
$$
#### Berlekamp-Massey 演算法
Berlekamp-Massey 演算法主要是透過疊代的方式來找錯誤位置多項式。
令 $\beta_i \triangleq \alpha^{j_i},\delta_i \triangleq e_{j_i}, 1 \leq i \leq v,$
$$
\begin{aligned}
&S_1=\delta_1 \beta_1+ \delta_2 \beta_2+ \dots + \delta_v \beta_v\\
&S_2=\delta_1 \beta_1^2+ \delta_2 \beta_2^2+ \dots + \delta_v \beta_v^2\\
&\vdots\\
&S_{2t}=\delta_1 \beta_1^{2t}+ \delta_2 \beta_2^{2t}+ \dots + \delta_v \beta_v^{2t}\\
\end{aligned}
$$
$S_i,1 \leq i \leq 2t$ 為已知的徵狀值，$\delta_1 \beta_1^n+ \delta_2 \beta_2^n+ \dots + \delta_v \beta_v^n,1 \leq n \leq 2t$ 中的錯誤值 $\delta_i$ 和錯誤變數 $\beta_i$ 是需要求的未知變數。
錯誤位置多項式的定義為
$$
\begin{aligned}
\sigma(x)&=(1-\beta_1x)(1-\beta_2x) \dots (1-\beta_vx)\\
&=\sigma_0+\sigma_1x+\sigma_2x^2+\dots+\sigma_vx^v
\end{aligned}
$$
其中
$$
\begin{aligned}
&\sigma_0=1\\
&\sigma_1=-(\beta_1+\beta_2+\dots+\beta_v)\\
&\sigma_2=\beta_1\beta_2+\beta_2\beta_3+\dots+\beta_{v-1}\beta_v\\
&\vdots\\
&\sigma_v=(-1)^v\beta_1\beta_2+\dots+\beta_{v-1}
\end{aligned}
$$
因此可以得到 $\sigma_i$ 與 徵狀值 $S_i$ 的關係式
$$
S_{i+v}+\sigma_1S_{i+v-1}+\dots+\sigma_vS_i=0,i=1,\dots,2t-v
$$
此關係式即為廣義牛頓恆等式，而我們的目標就是要找出可以滿足上述關係式之最小階數多項式 $\sigma(x)$，這也代表我們找到的錯誤樣本是錯誤個數最少的。
Berlekamp-Massey 演算法根據上述關係式提出可以解決錯誤發生的個數為未知數的問題，其採用反覆疊代的方式，從滿足 $\{S_1\}$ 的 $\sigma(x)$ 找起，再找滿足 $\{S_1,S_2\}$ 的 $\sigma(x)$，不斷疊代直到 $\sigma(x)$ 滿足所有 $\{S_1,S_2,\dots,S_{\mu}\}$ 為止，因此為了滿足 $2t$ 個徵狀值，要經過 $2t$ 次的疊代。對於最多可更正 $t$ 個錯誤的 Reed–Solomon code 來說，必須滿足 $v\leq t$ 。若 $v>t$ ，則無法正確有效解碼。
假設第 $\mu$ 次疊代滿足 $\{S_1,S_2,\dots,S_{\mu}\}$ 的錯誤多項式為 $\sigma^{(\mu)}(x)$，$L_{\mu}$ 為 $\sigma^{(\mu)}(x)$ 的階數，則此次 $\sigma_i$ 與 徵狀值 $S_i$ 的關係式為
$$ S_{j+L_{\mu}}+\sigma_1^{(\mu)}S_{j+L_{\mu}-1}+\dots+\sigma_{L_{\mu}}^{(\mu)}S_j=0,j=1,\dots,\mu-L_{\mu}
$$
再來檢驗 $\sigma^{(\mu)}(x)$ 是否可以滿足下一個徵狀值 $S_{\mu+1}$ 時產生 差異值 (discrepancy) ，差異值的定義為
$$ d_{\mu}=S_{\mu+1}+\sigma_1^{(\mu)}S_{\mu}+\dots+\sigma_{L_{\mu}}^{(\mu)}S_{\mu+1-L_{\mu}}
$$
若 $d_{\mu}=0$，則不需修改錯誤位置多項式，繼續檢查下個徵狀值，故
$$
\begin{aligned}
&\sigma^{(\mu+1)}(x)=\sigma^{(\mu)}(x)\\
&L_{\mu+1}=L_{\mu}
\end{aligned}
$$
若 $d_{\mu}\neq 0$，則需要修改錯誤位置多項式來滿足 $\{S_1,S_2,\dots,S_{\mu+1}\}$ 。我們需要藉由先前找到的 $\sigma^{(\rho)}(x)$ 來作為輔助修正多項式，其中 $d_{\rho} \neq 0$ 且 $\rho-L_{\rho}$ 為最大值，$\rho$ 亦可選擇為當下錯誤位置多項式最後一次改變階數的前一次疊代，因此 $\sigma^{(\mu+1)}(x)$ 修正為
$$
\sigma^{(\mu+1)}(x)=\sigma^{(\mu)}(x)-d_{\mu}d_{\rho}^{-1}x^{(\mu-\rho)}\sigma^{(\rho)}(x)
$$
其階數改變為
$$
L_{\mu+1}=max(L_{\mu},L_{\rho}+\mu-\rho)
$$
經過 $2t$ 次疊代後，得到 $\sigma(x)=\sigma^{(2t)}(x)$，就是我們要的錯誤位置多項式，其中階數 $L=L_{2t}$ 即表示錯誤個數 $v$。
#### Chien Search 演算法
在 錯誤位置多項式 $\sigma(x)=(1-\beta_1x)(1-\beta_2x) \dots (1-\beta_vx)$ 中可以得知若解出錯誤位置多項式的根，其反元素就可以找到錯誤位置。我們無法直接從 $\sigma (x)$ 分解出因式來得到所有的 $\beta$ 值，因此需要利用 Chien Search 演算法，將 $GF(2^m)$ 中的所有元素逐一代入 $\sigma (x)$ ，若可以使 $\sigma (x)=0$，則表示此元素是 $\sigma (x)=0$ 的根。而 $\sigma (x)=0$ 的根之反元素就是 $\beta$，$\beta_{i,1\leq i \leq v} \in GF(2^m)$，又 $\beta_i \triangleq \alpha^{j_i}$，因此 $j_i$ 代表其錯誤位置。
#### Forney 演算法
利用 Chien Search 演算法 找到錯誤位置後，就可以從錯誤位置多項式
$$
\begin{aligned}
&S_1=\delta_1 \beta_1+ \delta_2 \beta_2+ \dots + \delta_v \beta_v\\
&S_2=\delta_1 \beta_1^2+ \delta_2 \beta_2^2+ \dots + \delta_v \beta_v^2\\
&\vdots\\
&S_{2t}=\delta_1 \beta_1^{2t}+ \delta_2 \beta_2^{2t}+ \dots + \delta_v \beta_v^{2t}\\
\end{aligned}
$$
中解出每個錯誤位置 $\beta_i$ 相對應的錯誤值 $\delta_i$ 。 Forney 演算法 利用了錯誤位置多項式 $\sigma(x)$ 與徵狀值多項式 $S(x)$ 的關係，經由數學推導找出錯誤值計算方程式，因此可以免於解上述錯誤位置多項式的聯立方程式的運算。
首先，關鍵方程式 (key equation) 定義為
$$
\Omega(x)=\sigma(x)S(x) \mod\ x^{2t}
$$
又從徵狀值的多項式 $S(x)=\sum\limits_{j=1}^\infty S_jx^{j-1}$ 和上述的錯誤位置多項式可以得知
$$
S(x)=\sum\limits_{l=1}^v \dfrac{\delta_l \beta_l}{1-\beta_lx}
$$
因此可以從 $\sigma(x)=(1-\beta_1x)(1-\beta_2x) \dots (1-\beta_vx)$ 、關鍵方程式 和 $S(x)=\sum\limits_{l=1}^v \dfrac{\delta_l \beta_l}{1-\beta_lx}$ 推得
$$
\Omega(x)\triangleq \sum\limits_{l=1}^v\delta_l\beta_l\prod_{i=1,i \neq l}^v(1-\beta_ix)
$$
再將 $\beta_k$ 的反元素 $\beta_k^{-1}$ 代進上述式子得到
$$
\Omega(\beta_k^{-1})=\delta_k\beta_k\prod_{i=1,i \neq k}^v(1-\beta_i \beta_k^{-1})
$$
接著將 $\sigma(x)$ 微分
$$
\sigma'(x)=-\sum\limits_{l=1}^v\beta_l\prod_{i=1,i \neq k}^v(1-\beta_ix)
$$
且將 $\beta_k^{-1}$ 代進上述式子得到
$$
\sigma'(\beta_k^{-1})=-\beta_k\prod_{i=1,i \neq k}^v(1-\beta_i\beta_k^{-1})
$$
我們可以利用 $\Omega(x)$ 和 $\sigma(x)$ 來求得錯誤值。而由 $\Omega(\beta_k^{-1})=\delta_k\beta_k\prod_{i=1,i \neq k}^v(1-\beta_i \beta_k^{-1})$ 和 $\sigma'(\beta_k^{-1})=-\beta_k\prod_{i=1,i \neq k}^v(1-\beta_i\beta_k^{-1})$ 可以計算出 錯誤位置 $\beta_k$ 相對應的錯誤值 $\delta_k$ 為
$$
\delta_k=\dfrac{-\Omega(\beta_k^{-1})}{\sigma'(\beta_k^{-1})},\delta_{k,1 \leq k \leq v} \in GF(2^m)
$$
當我們有了錯誤位置和相對應的錯誤值後，就可以更正錯誤資訊了。
## TODO: 探討 Linux 核心應用 ECC 的案例
> 從 Linux 核心原始程式碼中找出 ECC 的應用案例，予以解說和分析，應當包含記憶體存取和電腦網路領域，舉出至少三個案例解說
### 案例一 : NAND Error-correction Code
> 根據 Frans Meulenbroeks 所寫的 [〈NAND Error-correction Code〉](https://docs.kernel.org/driver-api/mtd/nand_ecc.html)
以下解說 [linux/drivers/mtd/nand/ecc-sw-hamming.c](https://github.com/torvalds/linux/blob/master/drivers/mtd/nand/ecc-sw-hamming.c)
此程式使用 hamming code 偵測和校正 256 位元組 (byte) 資料區塊中的 1 位元錯誤
資料與 ECC code 的整體排列以下圖表示
訂 `invparity` 表，若 256 位元組中第 n 位元所含的 1 的數量為偶數，則標為 `1`
，奇數則標為 `0` 。如第 2 位元組為 `00000010` 有 1 個 1，因此標為 `0` 。
```c
static const char invparity[256] = {
1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1
};
```
訂 `bitsperbyte` 表，標示 256 位元組中第 n 位元組所含的 1 的數量。如第 2 位元組為 `00000010` 有 1 個 1，因此標為 `1` 。
```c
static const char bitsperbyte[256] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
};
```
訂 `addressbits` 表，用來濾出 syndrome bits 中錯誤位元所在的位址以及位元
```c
static const char addressbits[256] = {
0x00, 0x00, 0x01, 0x01, 0x00, 0x00, 0x01, 0x01,
0x02, 0x02, 0x03, 0x03, 0x02, 0x02, 0x03, 0x03,
0x00, 0x00, 0x01, 0x01, 0x00, 0x00, 0x01, 0x01,
0x02, 0x02, 0x03, 0x03, 0x02, 0x02, 0x03, 0x03,
0x04, 0x04, 0x05, 0x05, 0x04, 0x04, 0x05, 0x05,
0x06, 0x06, 0x07, 0x07, 0x06, 0x06, 0x07, 0x07,
0x04, 0x04, 0x05, 0x05, 0x04, 0x04, 0x05, 0x05,
0x06, 0x06, 0x07, 0x07, 0x06, 0x06, 0x07, 0x07,
0x00, 0x00, 0x01, 0x01, 0x00, 0x00, 0x01, 0x01,
0x02, 0x02, 0x03, 0x03, 0x02, 0x02, 0x03, 0x03,
0x00, 0x00, 0x01, 0x01, 0x00, 0x00, 0x01, 0x01,
0x02, 0x02, 0x03, 0x03, 0x02, 0x02, 0x03, 0x03,
0x04, 0x04, 0x05, 0x05, 0x04, 0x04, 0x05, 0x05,
0x06, 0x06, 0x07, 0x07, 0x06, 0x06, 0x07, 0x07,
0x04, 0x04, 0x05, 0x05, 0x04, 0x04, 0x05, 0x05,
0x06, 0x06, 0x07, 0x07, 0x06, 0x06, 0x07, 0x07,
0x08, 0x08, 0x09, 0x09, 0x08, 0x08, 0x09, 0x09,
0x0a, 0x0a, 0x0b, 0x0b, 0x0a, 0x0a, 0x0b, 0x0b,
0x08, 0x08, 0x09, 0x09, 0x08, 0x08, 0x09, 0x09,
0x0a, 0x0a, 0x0b, 0x0b, 0x0a, 0x0a, 0x0b, 0x0b,
0x0c, 0x0c, 0x0d, 0x0d, 0x0c, 0x0c, 0x0d, 0x0d,
0x0e, 0x0e, 0x0f, 0x0f, 0x0e, 0x0e, 0x0f, 0x0f,
0x0c, 0x0c, 0x0d, 0x0d, 0x0c, 0x0c, 0x0d, 0x0d,
0x0e, 0x0e, 0x0f, 0x0f, 0x0e, 0x0e, 0x0f, 0x0f,
0x08, 0x08, 0x09, 0x09, 0x08, 0x08, 0x09, 0x09,
0x0a, 0x0a, 0x0b, 0x0b, 0x0a, 0x0a, 0x0b, 0x0b,
0x08, 0x08, 0x09, 0x09, 0x08, 0x08, 0x09, 0x09,
0x0a, 0x0a, 0x0b, 0x0b, 0x0a, 0x0a, 0x0b, 0x0b,
0x0c, 0x0c, 0x0d, 0x0d, 0x0c, 0x0c, 0x0d, 0x0d,
0x0e, 0x0e, 0x0f, 0x0f, 0x0e, 0x0e, 0x0f, 0x0f,
0x0c, 0x0c, 0x0d, 0x0d, 0x0c, 0x0c, 0x0d, 0x0d,
0x0e, 0x0e, 0x0f, 0x0f, 0x0e, 0x0e, 0x0f, 0x0f
};
```
接下來為 hamming code 的計算，函式為 `ecc_sw_hamming_calculate`
先解釋 `rpX` :
- `rp0` 是所有偶數位元組（0、2、4、6、... 252、254）的奇偶校驗碼
- `rp1` 是所有奇數位元組（1、3、5、7、... 253、255）的奇偶校驗碼
- `rp2` 是所有位元組 0、1、4、5、8、9、... 的奇偶校驗（因此處理兩個位元組，然後跳過兩個位元組）。
- `rp3` 則涵蓋 `rp2` 未涵蓋的部分（位元組 2、3、6、7、10、11、...）
- 對 `rp4` 而言，規則是覆蓋 4 個位元組，跳過 4 個位元組，覆蓋 4 個位元組，跳過 4 個位元組，以此類推。因此 `rp4` 會計算位元組 0、1、2、3、8、9、10、11、16、... 的奇偶校驗。
- 而 `rp5` 則覆蓋另一半，所以位元組 4、5、6、7、12、13、14、15、20、...。
- `rp6` 每次覆蓋 8 個位元組然後跳過 8 個位元組，以此類推
- `rp7` 每次跳過 8 個位元組然後覆蓋 8 個位元組，以此類推
- `rp8` 每次覆蓋 16 個位元組然後跳過 16 個位元組，以此類推
- `rp9` 每次跳過 16 個位元組然後覆蓋 16 個位元組，以此類推
- `rp10` 每次覆蓋 32 個位元組然後跳過 32 個位元組，以此類推
- `rp11` 每次跳過 32 個位元組然後覆蓋 32 個位元組，以此類推
- `rp12` 每次覆蓋 64 個位元組然後跳過 64 個位元組，以此類推
- `rp13` 每次跳過 64 個位元組然後覆蓋 64 個位元組，以此類推
- `rp14` 每次覆蓋 128 個位元組然後跳過 128 個位元組，以此類推
- `rp15` 每次跳過 128 個位元組然後覆蓋 128 個位元組，以此類推
- `rp16` 每次覆蓋 256 個位元組然後跳過 256 個位元組，以此類推
- `rp17` 每次跳過 256 個位元組然後覆蓋 256 個位元組，以此類推
`*bp` 為 32 bits，因此可以排列 4 個位元組，因此 256 個位元組可以以 64 個 `*bp` 表示 。
由於 `rp4` 以上都是以 4 個位元組的倍數為一組進行計算，因此利用 loop unrolling 的技巧，每次疊代 16 個 `*bp` 並計算 `rp4` 、 `rp6` 、 `rp8` 、 `rp10` 、 `rp12` 、 `rp14` 、 `rp16` 、 `par` ，`temppar` 是 XOR 每次疊代的 16 個 `*bp` ， `par` 則是 XOR 全部的 `*bp` 。
```c
for (i = 0; i < eccsize_mult << 2; i++) {
cur = *bp++;
tmppar = cur;
rp4 ^= cur;
cur = *bp++;
tmppar ^= cur;
rp6 ^= tmppar;
cur = *bp++;
tmppar ^= cur;
rp4 ^= cur;
cur = *bp++;
tmppar ^= cur;
rp8 ^= tmppar;
cur = *bp++;
tmppar ^= cur;
rp4 ^= cur;
rp6 ^= cur;
cur = *bp++;
tmppar ^= cur;
rp6 ^= cur;
cur = *bp++;
tmppar ^= cur;
rp4 ^= cur;
cur = *bp++;
tmppar ^= cur;
rp10 ^= tmppar;
cur = *bp++;
tmppar ^= cur;
rp4 ^= cur;
rp6 ^= cur;
rp8 ^= cur;
cur = *bp++;
tmppar ^= cur;
rp6 ^= cur;
rp8 ^= cur;
cur = *bp++;
tmppar ^= cur;
rp4 ^= cur;
rp8 ^= cur;
cur = *bp++;
tmppar ^= cur;
rp8 ^= cur;
cur = *bp++;
tmppar ^= cur;
rp4 ^= cur;
rp6 ^= cur;
cur = *bp++;
tmppar ^= cur;
rp6 ^= cur;
cur = *bp++;
tmppar ^= cur;
rp4 ^= cur;
cur = *bp++;
tmppar ^= cur;
par ^= tmppar;
if ((i & 0x1) == 0)
rp12 ^= tmppar;
if ((i & 0x2) == 0)
rp14 ^= tmppar;
if (eccsize_mult == 2 && (i & 0x4) == 0)
rp16 ^= tmppar;
}
```
由於 `rp4` 、 `rp6` 、 `rp8` 、 `rp10` 、 `rp12` 、 `rp14` 、 `rp16` 為 32 位元，因此要轉換為 1 個位元組也就是 8 位元。這裡的做法為先將高位的 2 個位元組和低位的 2 個位元組 XOR ，再將 XOR 的結果的最低位位元組和第 2 低位位元組 XOR，完成所有位元組的 XOR 並合併成一個位元組，最後 `&=0xff` 取此位元組
```c
rp4 ^= (rp4 >> 16);
rp4 ^= (rp4 >> 8);
rp4 &= 0xff;
rp6 ^= (rp6 >> 16);
rp6 ^= (rp6 >> 8);
rp6 &= 0xff;
rp8 ^= (rp8 >> 16);
rp8 ^= (rp8 >> 8);
rp8 &= 0xff;
rp10 ^= (rp10 >> 16);
rp10 ^= (rp10 >> 8);
rp10 &= 0xff;
rp12 ^= (rp12 >> 16);
rp12 ^= (rp12 >> 8);
rp12 &= 0xff;
rp14 ^= (rp14 >> 16);
rp14 ^= (rp14 >> 8);
rp14 &= 0xff;
if (eccsize_mult == 2) {
rp16 ^= (rp16 >> 16);
rp16 ^= (rp16 >> 8);
rp16 &= 0xff;
}
```
這裡是取 `rp0` 、 `rp1` 、 `rp2` 、 `rp3`，若是系統為 little endian 則 `par` 的排列為 `rp3 rp3 rp2 rp2` 以及 `rp1 rp0 rp1 rp0`，big endian 則 `par` 的排列為 `rp2 rp2 rp3 rp3` 以及 `rp0 rp1 rp0 rp1`，因此在此依照不同的排列方式摺疊 (`rp0` XOR `rp0`，`rp1` XOR `rp1`，以此類推，最後取出一個位元組)
```c
#ifdef __BIG_ENDIAN
rp2 = (par >> 16);
rp2 ^= (rp2 >> 8);
rp2 &= 0xff;
rp3 = par & 0xffff;
rp3 ^= (rp3 >> 8);
rp3 &= 0xff;
#else
rp3 = (par >> 16);
rp3 ^= (rp3 >> 8);
rp3 &= 0xff;
rp2 = par & 0xffff;
rp2 ^= (rp2 >> 8);
rp2 &= 0xff;
#endif
/* reduce par to 16 bits then calculate rp1 and rp0 */
par ^= (par >> 16);
#ifdef __BIG_ENDIAN
rp0 = (par >> 8) & 0xff;
rp1 = (par & 0xff);
#else
rp1 = (par >> 8) & 0xff;
rp0 = (par & 0xff);
#endif
```
再來將 `par` 摺疊成一個位元組並且取出此位元組
```c
par ^= (par >> 8);
par &= 0xff;
```
再來計算 `rp5` 、 `rp7` 、 `rp9` 、 `rp11` 、 `rp13` 、 `rp15` ，由於 `par=rp4 ^ rp5 = rp6 ^ rp7 =...` 且有交換律，因此可以寫成 `rp5=par^rp4`，`rp7=par^rp6` 等等。
```c
rp5 = (par ^ rp4) & 0xff;
rp7 = (par ^ rp6) & 0xff;
rp9 = (par ^ rp8) & 0xff;
rp11 = (par ^ rp10) & 0xff;
rp13 = (par ^ rp12) & 0xff;
rp15 = (par ^ rp14) & 0xff;
if (eccsize_mult == 2)
rp17 = (par ^ rp16) & 0xff;
```
再來使用 `invparity` 表找出 `rpX` 所代表的位置的數字再依照以下圖中的排列生成 ECC code，cpX 則是可以直接從 `par` 中濾出
```c
if (sm_order) {
code[0] = (invparity[rp7] << 7) | (invparity[rp6] << 6) |
(invparity[rp5] << 5) | (invparity[rp4] << 4) |
(invparity[rp3] << 3) | (invparity[rp2] << 2) |
(invparity[rp1] << 1) | (invparity[rp0]);
code[1] = (invparity[rp15] << 7) | (invparity[rp14] << 6) |
(invparity[rp13] << 5) | (invparity[rp12] << 4) |
(invparity[rp11] << 3) | (invparity[rp10] << 2) |
(invparity[rp9] << 1) | (invparity[rp8]);
} else {
code[1] = (invparity[rp7] << 7) | (invparity[rp6] << 6) |
(invparity[rp5] << 5) | (invparity[rp4] << 4) |
(invparity[rp3] << 3) | (invparity[rp2] << 2) |
(invparity[rp1] << 1) | (invparity[rp0]);
code[0] = (invparity[rp15] << 7) | (invparity[rp14] << 6) |
(invparity[rp13] << 5) | (invparity[rp12] << 4) |
(invparity[rp11] << 3) | (invparity[rp10] << 2) |
(invparity[rp9] << 1) | (invparity[rp8]);
}
if (eccsize_mult == 1)
code[2] =
(invparity[par & 0xf0] << 7) |
(invparity[par & 0x0f] << 6) |
(invparity[par & 0xcc] << 5) |
(invparity[par & 0x33] << 4) |
(invparity[par & 0xaa] << 3) |
(invparity[par & 0x55] << 2) |
3;
else
code[2] =
(invparity[par & 0xf0] << 7) |
(invparity[par & 0x0f] << 6) |
(invparity[par & 0xcc] << 5) |
(invparity[par & 0x33] << 4) |
(invparity[par & 0xaa] << 3) |
(invparity[par & 0x55] << 2) |
(invparity[rp17] << 1) |
(invparity[rp16] << 0);
```
接下來為 hamming code 的校正，函式為 `ecc_sw_hamming_correct`
- `read_ecc[0~2]` 為從硬體實際讀取出來的奇偶校驗碼，排列成 3 個位元組
- `calc_ecc[0~2]` 為在 `ecc_sw_hamming_calculate` 算出的奇偶校驗碼，排列成 3 個位元組
利用 `read_ecc[X]^calc_ecc[X]` 可以校驗出錯誤的奇偶校驗位元，該位元為 1，也就是 Syndrome
```c
if (sm_order) {
b0 = read_ecc[0] ^ calc_ecc[0];
b1 = read_ecc[1] ^ calc_ecc[1];
} else {
b0 = read_ecc[1] ^ calc_ecc[1];
b1 = read_ecc[0] ^ calc_ecc[0];
}
b2 = read_ecc[2] ^ calc_ecc[2];
```
若 Syndrome 都為 0，則沒有錯誤
```c
if ((b0 | b1 | b2) == 0)
return 0;
```
若 Syndrome 不為 0 且 `b0` 、 `b1` 和 `b2` 為交錯的位元，如 `0b01010101` 或 `0b10101010` (但當 step_size 為 256 時 `b2` 不檢查最低位)，則視為資料中含有單一位元錯誤，可以校正。
`addressbits[b0]` 可以定位第 n 個位元組有錯的 n 的 0~3 位元，`addressbits[b1]` 則是 n 的 4~7 位元，`addressbits[b2]` 則是 n 的 8~11 位元 (若是 step_size 大於或等於 512)。
`addressbits[b2 >> 2]` 則是定位第 n 個位元組的第 x 位元有錯，最後翻轉該位元。
```c
if ((((b0 ^ (b0 >> 1)) & 0x55) == 0x55) &&
(((b1 ^ (b1 >> 1)) & 0x55) == 0x55) &&
((eccsize_mult == 1 && ((b2 ^ (b2 >> 1)) & 0x54) == 0x54) ||
(eccsize_mult == 2 && ((b2 ^ (b2 >> 1)) & 0x55) == 0x55))) {
if (eccsize_mult == 1)
byte_addr = (addressbits[b1] << 4) + addressbits[b0];
else
byte_addr = (addressbits[b2 & 0x3] << 8) +
(addressbits[b1] << 4) + addressbits[b0];
bit_addr = addressbits[b2 >> 2];
/* flip the bit */
buf[byte_addr] ^= (1 << bit_addr);
return 1;
}
```
若 `b0` 、 `b1` 和 `b2` 的 1 的數量加總為 1 表示是奇偶校驗碼本身有錯，故不做任何的處置
```c
if ((bitsperbyte[b0] + bitsperbyte[b1] + bitsperbyte[b2]) == 1)
return 1;
```
## TODO: 運用 librs 撰寫 Linux 核心模組
> 擴充 [2024 年報告](https://hackmd.io/@sysprog/HkxFLnvL0)，撰寫可運作的 Linux 核心模組，附上對應的測試案例
Sign in with Wallet
Connect another wallet