2024期末專案(暫定)

contributed by < allenliao666 >

研讀 Error-Correcting Codes (ECC)

研讀錯誤更正碼簡介

原連結掛掉，新連結如上！

當我們需要傳遞或儲存資料時，可能會發生錯誤或是資料遺失。這時就需要 Error-Correcting Codes (ECC) 把不正確的資料修正回來，所謂 ECC 就是在在資料發生缺漏時，我們可以透過數學架構，去猜出一個最可能性最高的答案。 ECC 的實作為將原有的資料加入額外的校驗碼後經由是先建構的數學規則組成碼字，碼字在面對可容忍數量的錯誤時可以發現錯誤的位置並更正，以下介紹 SEC 、 Galois Field 和 Reed Solomon code (RS Code)， Linux kernel 中與 ECC 相關的程式碼。

為什麼我們需要了解 Galois Field 呢?因為 Galois Field 具有一些特別的性質，讓我們更容易在上面使用 RS Code 作為編解碼器(Codec)。

Single–Error Correcting(SEC) Codes

最簡單的 ECC 就是 SEC ，顧名思義 SEC 可以發現並修正單一位元的錯誤。以下舉 (7,4) Hamming code 為例。首先定義如下，

$x$ 是我們要傳送的4位元資料，

$x\in \{0,1{\}}^4$ 。把

$x$ 經過編碼(encode)後，會得到

$c\in \{0,1{\}}^7$ ， $c 被稱為碼字(codeword)，就是在傳輸或是保存時使用的格式。將前述行為寫成數學式為

$$G:\{0,1{\}}^4\to \{0,1{\}}^7$$ 以矩陣乘法表示即為

$$c=Gx,G=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\\ 1& 1& 0& 1\\ 1& 0& 1& 1\\ 0& 1& 1& 1\end{array}\right)$$
這裡用到的

$G$ 被稱為生成矩陣(Generator matrix)，他的功能就是把

$x$ 編碼為

$c$ ，而

$c$ 所組成的向量空間

$C$ 為

$\{0,1{\}}^7$ 的子空間，

$C$ 為

$G$ 行生成的子空間，即

$C=Column-span(G)=\{Gx:x\in F^k\}$ ，可歸納為

$c\in C\subseteq \{0,1{\}}^7$。

$c$ 的二進位格式為

$d_1...d_4{p}_1...p_3，$其中

$d_1$ 到

$d_4$ 為我們要傳遞的資料(前述的

$x$)，

$p_1,p_2,p_3$ 是用來檢測並修正錯誤的奇偶校驗碼，對應如下圖

圖中3個集合兩兩相交，資料位於集合相交處，每個集合各有一個奇偶校驗碼。 Hamming code 規定每個集合中1的數量皆為偶數。若發出的碼字

$c$ 為0111001，但在傳遞過程中發生錯誤，導致

$p_2$ 從0變成1，故收信方收到錯誤碼字

$\tilde{c}$ 0111011。收信方會逐一比對每個集合中1的數量是否符合規定，因此就會發現

$p_2$ 的值應更正為0。舉個例子，若

$d_4$ 發生錯誤，則會導致三個集合1的數量都是奇數。

(7, 4) Hamming Code 的數學結構

接下來用數學的觀點解釋上述的例子，首先先定義 Hamming Code 上的運算，包含加法和乘法。此處的加法和乘法皆為模二運算，加法的規則等同互斥或( exclusive or , XOR)；乘法的規則即一般的乘法後 mod 2。把上圖轉換為方程式，考慮集合

$S=\{0,1\},x_i\in S,i=1,2,...,7$ 。令

$x_1,...,x_4$ 對應到

$d_1,...,d_4$ 且

$x_5,x_6,x_7$ 對應到

$p_1,p_2,p_3$。可以寫成下列方程式:

$$\{\begin{array}{c}{x}_1+x_2+x_4+x_5=0\\ x_1+x_3+x_4+x_6=0\\ x_2+x_3+x_4+x_7=0\end{array}$$

改寫成矩陣如下：

$$H=\left(\begin{array}{ccccccc}1& 1& 0& 1& 1& 0& 0\\ 1& 0& 1& 1& 0& 1& 0\\ 0& 1& 1& 1& 0& 0& 1\end{array}\right)$$

上述矩陣為奇偶檢驗矩陣(Parity check matirx)

$H$，

$Hc=0$ ，

$\mathrm{\forall }c\in C$。

$C$ 為

$H$ 的解集合，即為

$H$ 的 null space (kernel space) 。據秩—零化度定理，

$H$ 的維度為 7 ，且

$H$ 的三條方程式線性獨立，故秩(rank) 為 3 ，

$C$ 的維度即為 4 。因此

$|C|=2^4=16$ 。

討論完編碼的規則後，在解碼時我們需要校驗子(Syndrome)

$S$ 確認收到的碼字是否有誤。假設碼字

$c$ 在傳遞過程發生錯誤

$e$ ，收信方收到有錯的碼字

$\tilde{c}=c+e$ 。

$S$ 檢驗碼字的方法就是把

$H$ 乘

$\tilde{c}$ ，若碼字無誤，

$S$ 會是零矩陣；若碼字有誤則

$S$ 非零矩陣。寫成數學式

$H\tilde{c}=Hc+He$ 。因為

$Hx=0$ ，所以

$H\tilde{c}=He$ ，因此可以使用

$S$ 把

$e$ 給反推出來。然而有可能會產生多組解，通常我們會選擇錯的位元數最少的向量，因為一般情況下發生錯誤的機率較正確的機率低，所以錯的位元數最少的向量的機率最大，得到

$e$ 後我們就可修正

$c$ 。舉例來說，

$c$ 為 0111001 ，第六位元發生錯誤，故

$e$ 為 0000010 ， 則

$\tilde{c}$ 為 0111011 。

$$S=H\tilde{c}=\left(\begin{array}{ccccccc}1& 1& 0& 1& 1& 0& 0\\ 1& 0& 1& 1& 0& 1& 0\\ 0& 1& 1& 1& 0& 0& 1\end{array}\right)\left(\begin{array}{c}0\\ 1\\ 1\\ 1\\ 0\\ 1\\ 1\end{array}\right)=\left(\begin{array}{c}0\\ 1\\ 0\end{array}\right)$$

因為

$S$ 非零矩陣，故一定有某個位元發生錯誤，我們發現

$S^T=(\begin{array}{ccc}0& 1& 0\end{array})$ 和

$H$ 的第六行相同，故可以反推

$e$ 最有可能為 0000010 ，因為他錯的位元數最少。由於我們假設碼字發生錯誤的機率很小，因此有一個位元錯誤的機率會遠大於兩個位元錯誤，所以我們會傾向比較少的位元錯誤。經過修正錯誤後，就能還原

$c$ 的值了！由於

$H$ 行獨立，因此錯誤的位元位置不同，生成的

$S$ 就會不同，例如錯誤發生在第四位元，則

$S^T$ 為

$(\begin{array}{ccc}1& 1& 1\end{array})$ 。

Hamming Distance & Hamming Weight

藉由上述例子我們理解 (7, 4) Hamming Code 的編解碼規則，接下來從數學的角度討論碼字的長度和錯誤修正能力的關聯。

首先定義 Hamming Distance 為兩個向量間相異位元數量；Hamming Weight 為向量非零的位元數。舉例來說

$x$ 為 0001011 ，

$y$ 為 1101010 ，則

$H_w(x)=3$,

$H_w(y)=4$,

$H_d(x,y)=3$ 。可以發現

$H_d(x,y)=H_w(x\oplus y)$ ，也就是兩者的 Hamming Distance 等同

$x$ 先和

$y$ 做 XOR 再取 Hamming Weight 。
接著定義

$C$ 的 minimum distance 為

$C$ 中任兩個相異碼字的 Hamming Distance 之最小值:

$$d_{min}(C)=min{H}_d(x,y)x,y\in C,x\ne y$$ 還有定義

$C$ 的 minimum weight，即

$C$ 中不為 0 的碼字之 Hamming Distance 的最小值:

$$w_{min}(C)=min{H}_w(x),x\in C,x\ne 0$$由於

$C$ 是

$H$ 的 kernel space ，所以

$C$ 是一個線性空間，故具有封閉性，

$C$ 中碼字 XOR 後，仍存在於

$C$ 。因此可以推論

$d_{min}(C)=w_{min}(C)$ 。
以 (7, 4) Hamming Code 為例，他的 minimum distance 等於 3 。因為

$C$ 為

$H$ 的行組合，且

$H$ 行獨立，表示若要使

$Hc=0$ ，

$c$ 至少有 3 個以上 1 。

為什麼我們會需要知道

$C$ 的 minimum distance 呢？因為 minimum distance 的大小決定碼字可以修正多少位元的錯誤。若 minimum distance 為 t ，則可以修復

$\lfloor t/2\rfloor$ 位元的錯誤，想法如下:
若把

$C$ 想像為一個平面，所有碼字分布在上面(包括正確和有誤的碼字)，以每個正確的碼字為圓心，以半徑

$\lfloor t/2\rfloor$ 畫出圓形，在這範圍內的錯誤碼字將會被修正為該圓心的碼字。因此必須保證每個圓形之間不能重疊，不然錯誤碼字若在兩圓交疊處，會不知道應該修正為哪個正確碼字才對。故兩圓心間的距離至少為

$\lfloor t/2\rfloor +\lfloor t/2\rfloor +1$，即為 minimum distance

$t$ 。

Reed Solomon Code

Reed Solomon Code (RS Code)運用前面章節提到的，以加入多餘位元的方式去對抗傳遞過程中可能發生的資訊錯誤。因此 RS Code 被廣泛運用在硬碟、快閃記憶體等領域。 RS Code 需建構在有限體上，常使用

$GF(2^8)$ 。

Polynomials over finite field

給定一個環

$R$ 以及一個未知數

$X$，則可建構多項式

$P$ 如下：

$$P=a_0+a_{1}X+...+a_{n-1}{X}^{n-1}+a_n{X}^n$$ 其中

$a_0,...,a_n$ 為

$R$ 的元素，

$P$ 的最高次項被記做

$deg(P)$ 。且兩多項式的和、差與積仍是多項式，因此多項式也會組成環

$R[X]$ ，稱為

$R$ 上的多項式環。
在有限體

$GF(2^m)$ 中的元素共有

$2^m$ 個二進位多項式(多項式的係數只會是 0 或 1)，且任一多項式的最高項次不超過

$m-1$ ，因此這些元素可以表示

$2^8$ 個字串。例如

$X^7+X^5+X+1$ 表示 10100011。
需要注意的是，因為

$GF(2^8)$ 上的運算要模2，因此加減法等同 XOR 。例如

$(X^7+X^5+X+1)+(X^5+X^2)=X^7+2X^5+X^2+X+1$

$=X^7+X^2+X+1$ 。乘法的運算可以視為位元移動後再 XOR ，例如

$(X^7+X^5)\ast (X^2+1)=X^9+2X^7+X^5$

$=X^9+X^5$ 。因為現在的最高次項超過 7 了，因此需要

$P$ 對質式(irreducible polynomial) 取模。所謂質式指一個多項式不能再被分解成其他多項式的乘積，而且他的

$deg$ 為

$m$ 。本例以

$(X^8+X^4+X^3+X^2+1)$ 作為質式，因此前面的乘法結果為

$X^4+X^3+X$ 。

Preliminaries

在編碼之前，我們要先找到有限體的本原元/生成元 (primitive element / generator)，上述兩者意思相同，即找到一個有限體中的元素，可以藉由改變次方而生成所有元素，舉

${\mathbb{Z}}_5$ 為例，3 就是本原元，因為把

$3^0$ 到

$3^3$ 寫成集合

$\{1,3,4,2\}$ 就是

${\mathbb{Z}}_5$ 中的所有元素。
此外，我們令傳輸資料的長度為

$k,1\le k<|2^8|$ ；並加入

$m$ 個錯誤修正碼，

$1\le m<|2^8|-k$ ，可修正最多

$\lfloor m/2\rfloor$ 個錯誤， RS Code 由上述兩者組成，總長度

$n=k+m<2^8$ 。

Encoding

RS Code 的編碼過程非常簡單，首先定義資料多項式(message polynomial):

$$u(x)=\sum _{i=0}^{k-1}{u}_i{x}^i=u_0+u_{1}x+...+u_{k-1}{x}^{k-1}$$共 k 項，其中

$u_i,0\le i\le k-1$ 為有限體中的元素。我們的目標就是透過映射

$\rho :u(x)\to s(x)$ 把資料編碼成碼字

$s(x)$ 。因此我們需要生成多項式(generator polynomial):

$$g(x)=\prod _{i=0}^{m-1}(x-a^i)=(x-a^0)(x-a^1)...(x-a^{m-1})$$ 該式為 m 次多項式，且最高項係數為 1 。經過編碼的碼字如下:

$$s(x)=u(x)x^m-[(u(x)x^m)\mathrm{mod}g(x)]$$可以發現

$deg(s(x))=n-1$ ，且

$s(x)$ 必定整除於

$g(x)$ ，因此正確傳輸的碼字在解碼時應為零多項式。其中

$x^m$ 到

$x^{m+k-1}$ 共 k 項的係數和

$u(x)$ 相同，等同我們把資料記錄在前 k 項係數。此外

$[(u(x)x^m)\mathrm{mod}g(x)]$ 的

$deg$ 最高為

$m-1$ ，故不會影響到要傳輸的資料 (

$s(x)$ 的前 k 項係數)。

Decoding

RS Code 有很多解碼方式，以下介紹 Linux kernel 中 linux/lib/reed_solomon 使用的 Berlekamp-Massey 演算法，分為下列五個步驟:

1. 計算校驗子多項式 (Syndromes polynomial)
2. 計算錯誤位置多項式 (Error locator polynomial)
3. 計算評估多項式 (Evaluator polynomial)
4. 計算梯度多項式 (Magnitude polynomial)
5. 修復受損資料

如同先前 SEC Code 章節談過的，校驗子矩陣若為零矩陣表示資料無誤。因為 RS Code 是多項式形式，所以需要校驗子多項式協助判斷資料的正確性。建構校驗子多項式的方式很簡單，只要把編碼時使用的本原元

$\{{\alpha }^0,{\alpha }^1,...{\alpha }^{m-1}\}$ (即生成多項式的因式)代入收到的 RS Code 即可，若得到的校驗子多項式不為 0 ，表示碼字錯誤。
為了找到錯誤的位置，因此需要計算錯誤位置多項式。

使用 Chien search

Galois Field 有限體

又被稱為伽羅瓦體，顧名思義， Galois Field 即為一個包含有限多個元素的代數結構，在這個結構中的加法和乘法具有下列提到的性質。

定義

令

$(F,+,\times )$ 為一有限體，則

$(F,+,\times )$ 為阿貝爾環 (Abelian ring) 且

$(F-\{0\},\times )$ 為群，兩者分別具有以下性質，這裡提到的加法和乘法都是模術運算。

阿貝爾環

若

$(F,+,\times )$ 為阿貝爾環表示

$(F,+)$ 為阿貝爾群(交換群)、

$(F,\times )$ 為半群(semigroup) 且 × 對 ＋ 符合分配律。

阿貝爾群為具有交換律的群，即群具下列前四項性質，阿貝爾群則是五項性質都有，

$({\mathbb{Z}}_p,+),p\in \mathbb{P},a,b\in {\mathbb{Z}}_p$ 即為一阿貝爾群，接著以

$({\mathbb{Z}}_7,+),a=3,b=5$ 為例：

封閉性：

$3+5=8\equiv 1(\mathrm{mod}7)$

結合律：

$(3+5)+1=(3+(5+1)=9\equiv 2(\mathrm{mod}7)$

具單位元素：

$3+0=0+3=3(\mathrm{mod}7)$

具反元素：

$3+4=4+3=0(\mathrm{mod}7)$

交換律：

$3+2=2+3=5(\mathrm{mod}7)$

半群則僅具有封閉性和結合律，例如

$({\mathbb{Z}}_p,\times ),p\in \mathbb{P},a,b\in {\mathbb{Z}}_p$ ，同樣以

$({\mathbb{Z}}_7,+),a=3,b=5$ 為例：

封閉性：

$3\times 5=15\equiv 1(\mathrm{mod}7)$

結合律：

$(3\times 5)\times 2=(3\times (5\times 2)=30\equiv 2(\mathrm{mod}7)$

最後是

$({\mathbb{Z}}_p,+,\times ),p\in \mathbb{P}$ 中 × 對 ＋ 的分配律：

$(3+5)\times 2=8\times 2=16=3\times 2+5\times 2\equiv 2(\mathrm{mod}7)$

經過上面的舉例可知

$({\mathbb{Z}}_7,+,\times )$ 為有限體，其實

$({\mathbb{Z}}_p,+,\times ),p\in \mathbb{P}$ 皆屬於有限體，即只要

$p$ 為質數，在

${\mathbb{Z}}_p$ 上的模數加法和乘法都符合上述性質。那為什麼在合數為模的運算就不是有限體呢？舉

$({\mathbb{Z}}_4,+,\times )$ 為例，發現2的乘法反元素不存在，即

$2\times X\equiv 1mod4$ ，

$X$ 不存在，只要是合數的因數，他的乘法反元素就不存在。與之相反，

$({\mathbb{Z}}_7,+,\times )$ 中每個元素的乘法反元素都存在，其對應關係如下

$2\times 4\equiv 3\times 5\equiv 6\times 6\equiv 1mod7$ 。

我們經常把有限體記為

$GF(P^E)$ ，其中

$P$ 為質數；

$E$ 為正整數，表示在該有限體上的運算要對

$P$ 取模，且有限體的大小為

$P^E$ 。 例如 RS Code 建構在

$GF(2^8)$ 上，即 RS Code 的加法和乘法都要對2取模，且

$GF(2^8)$ 的元素個素共256個。

Linux Kernel 中的 RS Code

Linux kernel 中有關 RS Code 的程式碼主要出現在 linux/lib/reed_solomon 和 linux/include/linux/rslib.h 。以下的解說參考主要維護者 Thomas Gleixner 寫的 Reed-Solomon Library Programming Interface 。

init_rs

init_rs 用於初始化 rs_control 結構，該結構包括一個指向 rs_codec 結構的指標和 buffers 陣列， buffers 陣列在解碼時會派上用場。

Linux 提供兩種初始化 rs_control 的函式，分別是init_rs 和 init_rs_non_canonical ，兩者間的差別在於第二個引數。init_rs 使用本原多項式(primitive polynomial)； init_rs_non_canonical 則使用 gffunc 生成一個體:

static inline struct rs_control *init_rs(int symsize, int gfpoly, int fcr,
					 int prim, int nroots)
{
	return init_rs_gfp(symsize, gfpoly, fcr, prim, nroots, GFP_KERNEL);
}

struct rs_control *init_rs_non_canonical(int symsize, int (*func)(int),
					 int fcr, int prim, int nroots);

需要注意的是 prim 表示

${\alpha }^{prim}$ 。若不使用 gffunc 的狀況下，則 Linux 把

$\alpha$ 預設為 2。舉例來說，若 prim = 1，則生成元為 2。
init_rs 會呼叫 lib/reed_solomon/reed_solomon.c 中的 init_rs_gfp ，之後 init_rs_gfp 再呼叫 init_rs_internal :

struct rs_control *init_rs_gfp(int symsize, int gfpoly, int fcr, int prim,
			       int nroots, gfp_t gfp)
{
	return init_rs_internal(symsize, gfpoly, NULL, fcr, prim, nroots, gfp);
}
EXPORT_SYMBOL_GPL(init_rs_gfp);

static struct rs_control *init_rs_internal(int symsize, int gfpoly,
					   int (*gffunc)(int), int fcr,
					   int prim, int nroots, gfp_t gfp)

在 init_rs_internal 中首先檢查引數是否合理:

if (symsize < 1)
    return NULL;
if (fcr < 0 || fcr >= (1<<symsize))
    return NULL;
if (prim <= 0 || prim >= (1<<symsize))
    return NULL;
if (nroots < 0 || nroots >= (1<<symsize))
    return NULL;

/*
 * The decoder needs buffers in each control struct instance to avoid variable size or 
 * large fixed size allocations on stack. Size the buffers to arrays of [nroots + 1].
 */
bsize = sizeof(uint16_t) * RS_DECODE_NUM_BUFFERS * (nroots + 1);
rs = kzalloc(sizeof(*rs) + bsize, gfp);
if (!rs)
    return NULL;

為了避免解碼時使用過多記憶體資源，因此需要分配 buffer 給 rs_control ， RS_DECODE_NUM_BUFFERS = 8，在解碼時這些 buffer 會派上用場。

list_for_each(tmp, &codec_list) {
    struct rs_codec *cd = list_entry(tmp, struct rs_codec, list);
    if (symsize != cd->mm)
        continue;
    if (gfpoly != cd->gfpoly)
        continue;
    if (gffunc != cd->gffunc)
        continue;
    if (fcr != cd->fcr)
        continue;
    if (prim != cd->prim)
        continue;
    if (nroots != cd->nroots)
        continue;
    /* We have a matching one already */
    cd->users++;
    rs->codec = cd;
    goto out;
}

接著走訪 codec_list 尋找是否已經有相同的 rs_codec 結構，若是存在，則指向該 rs_codec 即可，若不存在則呼叫 codec_init 新增一個 rs_codec 結構。

codec_init 中，有一段程式碼使用 alpha_to 和 index_of 陣列建立生成多項式如下:

/* Form RS code generator polynomial from its roots */
rs->genpoly[0] = 1;
for (i = 0, root = fcr * prim; i < nroots; i++, root += prim) {
    rs->genpoly[i + 1] = 1;
    /* Multiply rs->genpoly[] by  @**(root + x) */
    for (j = i; j > 0; j--) {
        if (rs->genpoly[j] != 0) {
            rs->genpoly[j] = rs->genpoly[j -1] ^
                rs->alpha_to[rs_modnn(rs, rs->index_of[rs->genpoly[j]] + root)];
        } else
            rs->genpoly[j] = rs->genpoly[j - 1];
    }
    /* rs->genpoly[0] can never be zero */
    rs->genpoly[0] =
        rs->alpha_to[rs_modnn(rs,rs->index_of[rs->genpoly[0]] + root)];
}

rs_modnn

static inline int rs_modnn(struct rs_codec *rs, int x)
{
	while (x >= rs->nn) {
		x -= rs->nn;
		x = (x >> rs->mm) + (x & rs->nn);
	}
	return x;
}

rs_modnn 用於計算對 nn 取餘的值。因為 nn = (1<<mm)-1 ，故為梅森數，可以對該運算最佳化如下，舉例來說，令 nn = 3， mm = 4，則

$x\mathrm{mod}3$ 可以改寫為

$(x/4)+(x\mathrm{\%}4)$ 。相關細節請參考Mersenne Numbers: Mod 3, Mod 7, Mod (

$2^{𝑖}–1$) 。此外，梅森數應也可以2024q1 第 4 週測驗二的方式實作。

encode_rs8

首先檢查輸入的引數是否合理:

pad = nn - nroots - len;
if (pad < 0 || pad >= nn)
    return -ERANGE;

for (i = 0; i < len; i++) {
    fb = index_of[((((uint16_t) data[i])^invmsk) & msk) ^ par[0]];
    /* feedback term is non-zero */
    if (fb != nn) {
        for (j = 1; j < nroots; j++) {
            par[j] ^= alpha_to[rs_modnn(rs, fb +
                         genpoly[nroots - j])];
        }
    }
    /* Shift */
    memmove(&par[0], &par[1], sizeof(uint16_t) * (nroots - 1));
    if (fb != nn) {
        par[nroots - 1] = alpha_to[rs_modnn(rs,
                            fb + genpoly[0])];
    } else {
        par[nroots - 1] = 0;
    }
}
return 0;

decode_rs8

撰寫核心模組測試 Reed-Solomon API

前置作業

首先參考作業六中針對 Linux 核心模組的內容，核心模組定義為視核心需要可以動態掛載和卸載的程式碼，使核心無須重新開機即可使用所需功能。

在實作核心模組前，我們必須先檢查 Kernel 是否編譯相關的 Reed-Solomon 模組:

$ grep REED_SOLOMON /boot/config-$(uname -r)
CONFIG_REED_SOLOMON=m
CONFIG_REED_SOLOMON_ENC8=y
CONFIG_REED_SOLOMON_DEC8=y
CONFIG_REED_SOLOMON_DEC16=y

發現 CONFIG_REED_SOLOMON=m ，因此手動加載 Reed-Solomon 模組，並檢查是否掛載成功:

$ sudo modprobe reed_solomon
$ lsmod | grep reed_solomon
reed_solomon           28672  0

核心模組