Linux 核心專題: 錯誤更正碼 (ECC) 介紹和實作考量

執行人: allenliao666
解說影片

Reviewed by `Petakuo`

在阿貝爾群及半群結合律的例子中皆多打了"("，且應該先將兩者的答案寫出來再說他們相等，順序有點反了。

已修正，感謝 review !

Reviewed by `hugo0406`

由於我們假設 code word 發生錯誤的機率很小，因此只有一個位元錯誤的機率會遠大於兩個位元都錯的機率，所以我們會傾向選擇比較少的位元錯誤的那個 code word 。

針對 code word 錯誤機率的假設是基於甚麼作為根據呢?與在 Single–Error Correcting (SEC) 檢測出錯誤的情況有關係嗎?

我這段的論述倒果為因，應該先提到位元錯誤率再推廣到 code word ，已更新內文，感謝提醒! Code word 和 SEC 都是用額外加入確認位元的方式保障資料的正確性，因此兩者檢測錯誤的方法相同。兩者間的差異在於修正錯誤的能力。 SEC 僅能檢測1個位元的錯誤，若錯誤的位元超過1個，則 SEC 無法修正錯誤；反之，常見的 Reed Solomon Code 的 code word 為255位元，因此可修正16位元的錯誤。

Reviewed by `yinghuaxia`

diskonchip 是由 M-systems 開發的嵌入式儲存設備，作為嵌入式系統的存儲解決方案，其中就會使用 ECC 增加安全性。diskonchip.c 為 diskonchip 的 Interface ，在舊的程式碼中使用 ECC 實作確保資料安全，後來 RS API 的維護者 Thomas Gleixner 使用 RS API 取代舊的程式碼。

此段落中提到的舊程式碼是指舊版本的 Linux 核心程式碼嗎？想請問 RS API 的優勢為何才得以讓他取代舊的程式碼?

任務簡介

Error-Correcting Codes(ECC) 廣泛用於通訊傳輸，補正因為資料損壞、雜訊所導致的錯誤。本任務探討 ECC 原理，並分析 Linux 核心內部對於 ECC 的處理機制。

TODO: 研讀 Error-Correcting Codes 並紀錄問題

強化數學基礎的討論，若發現 Error-Correcting Codes 陳述有誤，著手修正

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

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

Single–Error Correcting (SEC) Codes

code word (中間有空白) 保留原文，不翻譯為「碼字」

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

x

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

x \in {0, 1}^{4}

。把

x

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

c \in {0, 1}^{7}

，

c

被稱為 code word，即傳輸或是保存時使用的格式。將前述行為寫成數學式為

f : {0, 1}^{4} \to {0, 1}^{7}

以矩陣乘法表示即為

c = G x, G = (\begin{matrix} 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{matrix})

這裡用到的

G

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

x

編碼為

c

，而

c

所組成的向量空間

C

為

{0, 1}^{7}

的子空間。令

H

為

G

的行向量總成的集合，

C

為以

H

為基底生成的子空間，即

C = C o l u m n - s p a n (H) = {G x : 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}

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

以 Graphviz 或向量繪圖描述語言重新繪製

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

c

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

p_{2}

從0變成1，故收信方收到錯誤 code word

\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{matrix} 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{matrix}

改寫成矩陣如下：

H = (\begin{matrix} 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{matrix})

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

H

，

H c = 0

，

\forall c \in C

。

C

為

H

的解集合，即為

H

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

H

的維度為 7 ，且

H

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

C

的維度即為 4 。因此

| C | = 2^{4} = 16

。

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

S

確認收到的 code word 是否有誤。假設 code word

c

在傳遞過程發生錯誤

e

，收信方收到有錯的 code word

\tilde{c} = c + e

。

S

檢驗 code word 的方法是把

H

乘

\tilde{c}

，若 code word 無誤，

S

則會是零矩陣；反之則

S

為非零矩陣。把上述想法寫成數學式

H \tilde{c} = H c + H e

。因為

H x = 0

，所以

H \tilde{c} = H e

，可以使用

S

把

e

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

e

後就可修正

c

。舉例來說，

c

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

e

為 0000010 ，則

\tilde{c}

為 0111011 。

S = H \tilde{c} = (\begin{matrix} 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{matrix}) (\begin{matrix} 0 \\ 1 \\ 1 \\ 1 \\ 0 \\ 1 \\ 1 \end{matrix}) = (\begin{matrix} 0 \\ 1 \\ 0 \end{matrix})

因為

S

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

S^{T} = (\begin{matrix} 0 & 1 & 0 \end{matrix})

和

H

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

e

最有可能為 0000010 ，因為他錯的位元數最少。

據 BER calculation 的附錄，位元錯誤率（Bits Error Rate，BER）至多為10%上下，並且會隨著訊號雜訊比(Signal-to-noise ratio，SNR)的上升而降低。因此只有一個位元錯誤的機率會遠大於兩個位元都錯的機率。

在判斷錯誤 code word 應該被修正為哪一個正確 code word 時，雖然我們無法得知錯誤位元的總量，但基於上述 BER 的觀點，我們會傾向選擇錯誤位元比較少的 code word 為正確 code word 。因此我們就可以還原

c

的值了！由於

H

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

S

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

S^{T}

為

(\begin{matrix} 1 & 1 & 1 \end{matrix})

。

Hamming Distance & Hamming Weight

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

首先定義 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

中任兩個相異 code word 的 Hamming Distance 之最小值:

d_{m i n} (C) = min H_{d} (x, y) x, y \in C, x \neq y

還有定義

C

的 minimum weight，即

C

中不為 0 的 code word 之 Hamming Distance 的最小值:

w_{m i n} (C) = min H_{w} (x), x \in C, x \neq 0

由於

C

是

H

的 kernel space ，所以

C

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

C

中 code word 執行 XOR 運算後，仍存在於

C

。因此可以推論

d_{m i n} (C) = w_{m i n} (C)

。
以 (7, 4) Hamming Code 為例，他的 minimum distance 等於 3 。因為

C

為

H

的行組合，且

H

行獨立，表示若要使

H c = 0

，

c

至少有 3 個以上 1 。

為什麼我們會需要知道

C

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

⌊ t / 2 ⌋

位元的錯誤，想法如下:
若把

C

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

⌊ t / 2 ⌋

畫出圓形，在該圓形範圍內的錯誤 code word 將會被修正為該圓心的 code word 。因此必須保證每個圓形之間不能重疊，不然錯誤 code word 若在兩圓交疊處，會不知道應該修正為哪個正確 code word 。故兩圓心間的距離至少為

⌊ t / 2 ⌋ + ⌊ t / 2 ⌋ + 1

即為 minimum distance

t

。

Galois Field 有限體

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

定義

令

(F, +, \times)

為一有限體，則

(F, +, \times)

為阿貝爾環 (Abelian ring) 且

(F - {0}, \times)

為群，兩者分別具有以下性質，這裡提到的加法和乘法都是模數運算。

阿貝爾環

若

(F, +, \times)

為阿貝爾環表示

(F, +)

為阿貝爾群(交換群)、

(F, \times)

為半群(semigroup) 且 × 對＋符合分配律。

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

(Z_{p}, +), p \in P, a, b \in Z_{p}

即為一阿貝爾群，接著以

(Z_{7}, +), a = 3, b = 5

為例：

封閉性：

3 + 5 = 8 \equiv 1 (\mod 7)

結合律：

((3 + 5) + 1) = 9 = (3 + (5 + 1)) \equiv 2 (\mod 7)

具單位元素：

3 + 0 = 0 + 3 = 3 (\mod 7)

具反元素：

3 + 4 = 4 + 3 = 0 (\mod 7)

交換律：

3 + 2 = 2 + 3 = 5 (\mod 7)

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

(Z_{p}, \times), p \in P, a, b \in Z_{p}

，同樣以

(Z_{7}, +), a = 3, b = 5

為例：

封閉性：

3 \times 5 = 15 \equiv 1 (\mod 7)

結合律：

((3 \times 5) \times 2) = 30 = (3 \times (5 \times 2)) \equiv 2 (\mod 7)

最後是

(Z_{p}, +, \times), p \in P

中 × 對＋的分配律：

(3 + 5) \times 2 = 8 \times 2 = 16 = 3 \times 2 + 5 \times 2 \equiv 2 (\mod 7)

經過上面的舉例可知

(Z_{7}, +, \times)

為有限體，其實

(Z_{p}, +, \times), p \in P

皆屬於有限體，即只要

p

為質數，在

Z_{p}

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

(Z_{4}, +, \times)

為例，發現2的乘法反元素並不存在，即

2 \times X \equiv 1 (\mod 4)

，

X

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

(Z_{7}, +, \times)

中每個元素的乘法反元素都存在，其對應關係如下

2 \times 4 \equiv 3 \times 5 \equiv 6 \times 6 \equiv 1 (\mod 7)

。

通常把有限體記為

G F (P^{E})

，其中

P

為質數；

E

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

P

取模，且有限體的大小為

P^{E}

。例如 RS Code 建構在

G F (2^{8})

上，即 RS Code 的加法和乘法都要對2取模，且

G F (2^{8})

的元素個素共 256 個。

Reed Solomon Code

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

G F (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

的最高次項被記做

d e g (P)

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

R [X]

，稱為

R

上的多項式環。
在有限體

G F (2^{m})

中的元素共有

2^{m}

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

m - 1

，因此這些元素可以表示

2^{8}

個字串。例如

X^{7} + X^{5} + X + 1

表示 10100011。
需要注意的是，因為

G F (2^{8})

上的運算要模2，因此加減法等同 XOR 。例如

(X^{7} + X^{5} + X + 1) + (X^{5} + X^{2}) = X^{7} + 2 X^{5} + X^{2} + X + 1

= X^{7} + X^{2} + X + 1

。乘法的運算可以視為位元移動後再 XOR ，例如

(X^{7} + X^{5}) * (X^{2} + 1) = X^{9} + 2 X^{7} + X^{5}

= X^{9} + X^{5}

。因為現在的最高次項超過 7 了，因此需要

P

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

d e g

為

m

。本例以

(X^{8} + X^{4} + X^{3} + X^{2} + 1)

作為質式，因此前面的乘法結果為

X^{4} + X^{3} + X

。

Preliminaries

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

Z_{5}

為例，3 就是本原元，因為把

3^{0}

到

3^{3}

寫成集合

{1, 3, 4, 2}

就是

Z_{5}

中的所有元素。
此外，我們令傳輸資料的長度為

k, 1 \leq k < | 2^{8} |

；並加入

m

個錯誤修正碼，

1 \leq m < | 2^{8} | - k

，可修正最多

⌊ m / 2 ⌋

個錯誤， 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 \leq i \leq k - 1

為有限體中的元素。我們的目標就是透過映射

ρ : u (x) \to s (x)

把資料編碼成 code word

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 。經過編碼的 code word 如下:

s (x) = u (x) x^{m} - [(u (x) x^{m}) \mod g (x)]

可以發現

d e g (s (x)) = n - 1

，且

s (x)

必定整除於

g (x)

，因此正確傳輸的 code word 在解碼時應為零多項式。其中

x^{m}

到

x^{m + k - 1}

共 k 項的係數和

u (x)

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

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

的

d e g

最高為

m - 1

，故不會影響到要傳輸的資料 (

s (x)

的前 k 項係數)。

Decoding

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

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

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

{α^{0}, α^{1}, . . . α^{m - 1}}

(即生成多項式的因式)代入收到的 RS Code 即可，若得到的校驗子多項式不為 0 ，表示 code word 錯誤。

發現 code word 有誤後，為了找到錯誤的位置，我們需要計算錯誤位置多項式。

得到錯誤位置多項式後，我們可以使用 Chien search 演算法加速尋找錯誤的位置 (即錯誤位置多項式的根)。因為 RS Code 可以同時解決錯誤和擦除(erase, 可以理解為已知其位置的錯誤)，兩者的差異在於一個位元發生錯誤需要兩個額外的位元才能修正；但一個位元發生擦除時僅需一個額外位元即可改正。綜上所述，我們為了同時處理錯誤和擦除，必須防止擦除干擾錯誤定位。因此我們藉由計算 Forney 校驗碼實現。

最後我們用 Forney 校驗碼即可知道所有不正確的位置並修正他們的值。

TODO: 研究 Linux 核心關於錯誤修正的案例 (ECC)，並撰寫獨立的 LKM

Linux kernel module (LKM, for Linux v6.8) (比照第六次作業)，說明 RS API 的使用案例和用法
舉出 Linux 核心內部 ECC 的應用案例並解說

Linux 核心的 RS API

Linux 核心 Reed Solomon (RS) API 主要定義在 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 表示

α^{p r i m}

。若不使用 gffunc 的狀況下，則 Linux 把

α

預設為 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 取餘的值。因為

n n = (1 ≪ m m) - 1

，故為梅森數，可以對該運算最佳化如下，舉例來說，令 nn = 3， mm = 4，則

x \mod 3

可以改寫為

(x / 4) + (x % 4)

。相關細節請參考Mersenne Numbers: Mod 3, Mod 7, Mod (

2^{𝑖} - 1

) 。此外，梅森數應也可以2024 年第 4 週測驗二的方式實作。

`encode_rs8`

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

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

接著用多項式長除法把 data 陣列除以 gen 陣列，也就是前面提到的把傳遞資料除以生成多項式後，剩下的餘式存在 par 陣列中。與數學模型中不同的點在於，數學模型會把餘式扣除，使 code word 可以整除於生成多項式。但在 Linux 的實作則是把傳遞資料和餘式分別存放在 data 和 par 陣列中。

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`

int decode_rs8(struct rs_control *rsc, 
                uint8_t *data, 
                uint16_t *par, 
                int len,
                uint16_t *s, 
                int no_eras, 
                int *eras_pos, 
                uint16_t invmsk,
                uint16_t *corr)

s: 解碼時會先計算校驗子多項式，再根據校驗子多項式找出發生錯誤的位。有些硬體支援計算叫晏子多項式，因此在這裡可以直接作為引數。

enum {
	RS_DECODE_LAMBDA,
	RS_DECODE_SYN,
	RS_DECODE_B,
	RS_DECODE_T,
	RS_DECODE_OMEGA,
	RS_DECODE_ROOT,
	RS_DECODE_REG,
	RS_DECODE_LOC,
	RS_DECODE_NUM_BUFFERS
};
...
    /*
     * The decoder buffers are in the rs control struct. They are
     * arrays sized [nroots + 1]
     */
    uint16_t *lambda = rsc->buffers + RS_DECODE_LAMBDA * (nroots + 1);
    uint16_t *syn = rsc->buffers + RS_DECODE_SYN * (nroots + 1);
    uint16_t *b = rsc->buffers + RS_DECODE_B * (nroots + 1);
    uint16_t *t = rsc->buffers + RS_DECODE_T * (nroots + 1);
    uint16_t *omega = rsc->buffers + RS_DECODE_OMEGA * (nroots + 1);
    uint16_t *root = rsc->buffers + RS_DECODE_ROOT * (nroots + 1);
    uint16_t *reg = rsc->buffers + RS_DECODE_REG * (nroots + 1);
    uint16_t *loc = rsc->buffers + RS_DECODE_LOC * (nroots + 1);
    
    /* Check length parameter for validity */
    pad = nn - nroots - len;
    BUG_ON(pad < 0 || pad >= nn - nroots);

在初始化 rs_control 結構時預留的 buffers 現在派上用場。這些 buffers 會各自紀錄解碼所需的各種多項式。

接下來正式進入解碼程序，以下對應到前述 Decoding 的部分：

    /* Does the caller provide the syndrome ? */
    if (s != NULL) {
        for (i = 0; i < nroots; i++) {
            /* The syndrome is in index form,
             * so nn represents zero
             */
            if (s[i] != nn)
                goto decode;
        }

        /* syndrome is zero, no errors to correct  */
        return 0;
    }

首先，若 caller 提供校驗子多項式，我們可以省下計算的成本，反之，則我們使用下列程式碼計算之：

    /* form the syndromes; i.e., evaluate data(x) at roots of
     * g(x) */
    for (i = 0; i < nroots; i++)
        syn[i] = (((uint16_t) data[0]) ^ invmsk) & msk;

    for (j = 1; j < len; j++) {
        for (i = 0; i < nroots; i++) {
            if (syn[i] == 0) {
                syn[i] = (((uint16_t) data[j]) ^
                      invmsk) & msk;
            } else {
                syn[i] = ((((uint16_t) data[j]) ^
                       invmsk) & msk) ^
                    alpha_to[rs_modnn(rs, index_of[syn[i]] +
                               (fcr + i) * prim)];
            }
        }
    }
    
     for (j = 0; j < nroots; j++) {
        for (i = 0; i < nroots; i++) {
            if (syn[i] == 0) {
                syn[i] = ((uint16_t) par[j]) & msk;
            } else {
                syn[i] = (((uint16_t) par[j]) & msk) ^
                    alpha_to[rs_modnn(rs, index_of[syn[i]] +
                               (fcr+i)*prim)];
            }
        }
    }
    s = syn;

    /* Convert syndromes to index form, checking for nonzero condition */
    syn_error = 0;
    for (i = 0; i < nroots; i++) {
        syn_error |= s[i];
        s[i] = index_of[s[i]];
    }
    
    if (!syn_error) {
        /* if syndrome is zero, data[] is a codeword and there are no
         * errors to correct. So return data[] unmodified
         */
        return 0;
    }

校驗子多項式的計算方式就是把 code word (即 data 和 par 陣列)以 nroot 個本源元代入，並檢查是否為零，若為零，表示訊息正確；反之，則進入錯誤修正流程，最後把結果轉換為指數形式以方便計算。

decode:
    memset(&lambda[1], 0, nroots * sizeof(lambda[0]));
    lambda[0] = 1;

    if (no_eras > 0) {
        /* Init lambda to be the erasure locator polynomial */
        lambda[1] = alpha_to[rs_modnn(rs,
                    prim * (nn - 1 - (eras_pos[0] + pad)))];
        for (i = 1; i < no_eras; i++) {
            u = rs_modnn(rs, prim * (nn - 1 - (eras_pos[i] + pad)));
            for (j = i + 1; j > 0; j--) {
                tmp = index_of[lambda[j - 1]];
                if (tmp != nn) {
                    lambda[j] ^=
                        alpha_to[rs_modnn(rs, u + tmp)];
                }
            }
        }
    }

    for (i = 0; i < nroots + 1; i++)
        b[i] = index_of[lambda[i]];

若擦除存在，我們需要先計算擦除位置多項式

Λ (x)

。此外，使用

Λ (x)

初始化 b 陣列，其對應 Berlekamp-Massey algorithm 中的 B(x)。

/*
 * Begin Berlekamp-Massey algorithm to determine error+erasure
 * locator polynomial
 */
r = no_eras;
el = no_eras;
while (++r <= nroots) {	/* r is the step number */
    /* Compute discrepancy at the r-th step in poly-form */
    discr_r = 0;
    for (i = 0; i < r; i++) {
        if ((lambda[i] != 0) && (s[r - i - 1] != nn)) {
            discr_r ^=
                alpha_to[rs_modnn(rs,
                          index_of[lambda[i]] +
                          s[r - i - 1])];
        }
    }
    discr_r = index_of[discr_r];	/* Index form */
   ...

接著使用 Berlekamp-Massey algorithm 計算錯誤定位多項式。迴圈會進行 nroots- no_eras次，迴圈內計算每一步的差異(discrepancy)，差異的值為

\sum_{i = 0}^{r} Λ_{i} S_{r - i - 1}

...
if (discr_r == nn) {
    /* 2 lines below: B(x) <-- x*B(x) */
    memmove (&b[1], b, nroots * sizeof (b[0]));
    b[0] = nn;
} else {
    /* 7 lines below: T(x) <-- lambda(x)-discr_r*x*b(x) */
    t[0] = lambda[0];
    for (i = 0; i < nroots; i++) {
        if (b[i] != nn) {
            t[i + 1] = lambda[i + 1] ^
                alpha_to[rs_modnn(rs, discr_r +
                          b[i])];
        } else
            t[i + 1] = lambda[i + 1];
    }
    if (2 * el <= r + no_eras - 1) {
        el = r + no_eras - el;
        /*
         * 2 lines below: B(x) <-- inv(discr_r) *
         * lambda(x)
         */
        for (i = 0; i <= nroots; i++) {
            b[i] = (lambda[i] == 0) ? nn :
                rs_modnn(rs, index_of[lambda[i]]
                     - discr_r + nn);
        }
    } else {
        /* 2 lines below: B(x) <-- x*B(x) */
        memmove(&b[1], b, nroots * sizeof(b[0]));
        b[0] = nn;
    }
    memcpy(lambda, t, (nroots + 1) * sizeof(t[0]));
}
}

discr_r == nn 表示原求的 discrepancy d 為 0
- 此時
  $B (x) ⟸ x * B (x)$
- 然後前進到下個 iteration
如果 discrepancy 不為 0:
- $Λ^{'} (x) ⟸ Λ (x) - d \times x \times B (x)$
- 可以看到程式中的 t 就是
  $Λ (x) - d \times x \times B (x)$ 的暫存空間
  $Λ^{'} (x)$
每個 iteration 中的 r + no_eras 表示目前是第幾個 iteration (從 1 開始數)
el 的用途是用來判斷某些 iteration 中需要額外的調整 B(x)，在條件滿足的 el 下：
- $e l ⟸$ 現在的 iteration 數量
  $- e l$
- 此時
  $B (x) ⟸ d^{- 1} Λ (x)$
- 除此之外
  $B (x) ⟸ x * B (x)$
最後，
$Λ (x) ⟸ Λ^{'} (x)$ ，然後進入下一個 iteration

/* Convert lambda to index form and compute deg(lambda(x)) */
deg_lambda = 0;
for (i = 0; i < nroots + 1; i++) {
    lambda[i] = index_of[lambda[i]];
    if (lambda[i] != nn)
        deg_lambda = i;
}

if (deg_lambda == 0) {
    /*
     * deg(lambda) is zero even though the syndrome is non-zero
     * => uncorrectable error detected
     */
    return -EBADMSG;
}

最後會得到擦除/錯誤位置多項式

Λ (x)

，表示我們終於找出所有不正確的位置了！接著我們把

Λ (x)

轉換為對數形式，並確認其階數，若 deg_lambda 為零，但校驗子多項式非零，表示擦除和錯誤的總數超過 RS 的容忍範圍，因此無法修正。

/* Find roots of error+erasure locator polynomial by Chien search */
memcpy(&reg[1], &lambda[1], nroots * sizeof(reg[0]));
count = 0;		/* Number of roots of lambda(x) */
for (i = 1, k = iprim - 1; i <= nn; i++, k = rs_modnn(rs, k + iprim)) {
    q = 1;		/* lambda[0] is always 0 */
    for (j = deg_lambda; j > 0; j--) {
        if (reg[j] != nn) {
            reg[j] = rs_modnn(rs, reg[j] + j);
            q ^= alpha_to[reg[j]];
        }
    }
    if (q != 0)
        continue;	/* Not a root */

    if (k < pad) {
        /* Impossible error location. Uncorrectable error. */
        return -EBADMSG;
    }

    /* store root (index-form) and error location number */
    root[count] = i;
    loc[count] = k;
    /* If we've already found max possible roots,
     * abort the search to save time
     */
    if (++count == deg_lambda)
        break;
}

使用 Chien search 對

Λ (x)

求根，若

α^{{f r c}^{i}}

為根，表示 len(msg) - 1 - i (LSB 往左數 i 位)為錯誤發生的位元。

    if (deg_lambda != count) {
        /*
         * deg(lambda) unequal to number of roots => uncorrectable
         * error detected
         */
        return -EBADMSG;
    }
    /*
     * Compute err+eras evaluator poly omega(x) = s(x)*lambda(x) (modulo
     * x**nroots). in index form. Also find deg(omega).
     */
    deg_omega = deg_lambda - 1;
    for (i = 0; i <= deg_omega; i++) {
        tmp = 0;
        for (j = i; j >= 0; j--) {
            if ((s[i - j] != nn) && (lambda[j] != nn))
                tmp ^=
                    alpha_to[rs_modnn(rs, s[i - j] + lambda[j])];
        }
        omega[i] = index_of[tmp];
    }

若找到的根數量和

Λ

的階數不一致，表示錯誤無法被修正。
接下來要計算 error / evaluator polynomial

Ω (x) = S (x) * Λ (x) m o d x^{n r o o t s}

，且存成 index form

    /*
     * Compute error values in poly-form. num1 = omega(inv(X(l))), num2 =
     * inv(X(l))**(fcr-1) and den = lambda_pr(inv(X(l))) all in poly-form
     * Note: we reuse the buffer for b to store the correction pattern
     */
    num_corrected = 0;
    for (j = count - 1; j >= 0; j--) {
        num1 = 0;
        for (i = deg_omega; i >= 0; i--) {
            if (omega[i] != nn)
                num1 ^= alpha_to[rs_modnn(rs, omega[i] +
                            i * root[j])];
        }

        if (num1 == 0) {
            /* Nothing to correct at this position */
            b[j] = 0;
            continue;
        }

        num2 = alpha_to[rs_modnn(rs, root[j] * (fcr - 1) + nn)];
        den = 0;

        /* lambda[i+1] for i even is the formal derivative
         * lambda_pr of lambda[i] */
        for (i = min(deg_lambda, nroots - 1) & ~1; i >= 0; i -= 2) {
            if (lambda[i + 1] != nn) {
                den ^= alpha_to[rs_modnn(rs, lambda[i + 1] +
                               i * root[j])];
            }
        }

        b[j] = alpha_to[rs_modnn(rs, index_of[num1] +
                           index_of[num2] +
                           nn - index_of[den])];
        num_corrected++;
    }

Forney algorithm

    /*
     * We compute the syndrome of the 'error' and check that it matches
     * the syndrome of the received word
     */
    for (i = 0; i < nroots; i++) {
        tmp = 0;
        for (j = 0; j < count; j++) {
            if (b[j] == 0)
                continue;

            k = (fcr + i) * prim * (nn-loc[j]-1);
            tmp ^= alpha_to[rs_modnn(rs, index_of[b[j]] + k)];
        }

        if (tmp != alpha_to[s[i]])
            return -EBADMSG;
    }

經過前面的步驟後，這裡我們會得到誤差多項式 e(x)(重用 b 來保存係數)

$e (x) = e_{0} + e_{1} x + . . . + e_{n - 1} x^{(n - 1)}$
理論上，我們前面得到的 syndromes
$S_{i}$ 應該要等於
$e (β^{i})$ ，這裡再做額外的檢查以確保正確性

    /*
     * Store the error correction pattern, if a
     * correction buffer is available
     */
    if (corr && eras_pos) {
        j = 0;
        for (i = 0; i < count; i++) {
            if (b[i]) {
                corr[j] = b[i];
                eras_pos[j++] = loc[i] - pad;
            }
        }
    } else if (data && par) {
        /* Apply error to data and parity */
        for (i = 0; i < count; i++) {
            if (loc[i] < (nn - nroots))
                data[loc[i] - pad] ^= b[i];
            else
                par[loc[i] - pad - len] ^= b[i];
        }
    }

    return  num_corrected;

如果 input 是 corr 和 eras_pos 的話，就把該誤差多項式填入 corr 並把有錯的位置填入 eras_pos，當成回傳
如果是 input 是 data 和 par 的話，那就是看誤差項的位置在 data 還是 par，並且將結果修正回去

Linux 核心內部 ECC 的應用案例

diskonchip.c

diskonchip 是由 M-systems 開發的嵌入式儲存設備，作為嵌入式系統的存儲解決方案，其中就會使用 ECC 增加安全性。diskonchip.c 為 diskonchip 的 Interface ，在舊的程式碼中使用 ECC 實作確保資料安全，後來 RS API 的維護者 Thomas Gleixner 使用 RS API 取代舊的程式碼。

ram_core.c

ram_core.c 位於 Linux 的檔案系統目錄下，主要用於 Linux kernel 的持久性儲存。ram_core.c 主要透過 ram_internal.h 中定義的 persistent_ram_zone 結構去使用 RS API 的編/解碼函式。

撰寫核心模組測試 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

核心模組

commit ac1f86d

在核心模組中，首先引入相關標頭檔及設定模組參數:

#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/rslib.h>

MODULE_LICENSE("GPL");
MODULE_AUTHOR("allenliao666");
MODULE_DESCRIPTION("A Reed-Solomon Test module");

在 rsdrv_init 函式中，首先初始化 rs_control 結構，並配置記憶體給 parity 陣列 (需手動配置)，再呼叫 encode_rs8 把餘式存在 parity 陣列:

struct rs_control *rs;
uint8_t data[223];
uint16_t parity[32];
int no_error;
int i;

//initialize a rs_control structure
rs = init_rs(8, 0x11d, 0, 1, 32);
if(!rs) {
    printk(KERN_ERR "Failed to initialize rs_control structure\n");
return -ENOMEM;
}
memset(parity, 0, sizeof(parity));
encode_rs8(rs, data, 223, parity, 0);

在解碼時呼叫 decode_rs8 ，其回傳值為發生錯誤的數量，若該數量超過可以修正的上限，就會回報解碼失敗:

//decode codewords 
no_error = decode_rs8(rs, data, parity, 223, NULL, 0,NULL, 0, NULL);
if (no_error < 0) {
    printk(KERN_ERR "Failed to decode Reed-Solomon data\n");
} else {
    printk(KERN_INFO "Number of erroes:%d\n", no_error);
    printk(KERN_INFO "Decode codewords successfully\n");
}

參考資料

Yan-Jie

2024/06/25 10:13:06

這裡用到的被稱為生成矩陣(Generator matrix)，他的功能就是把編碼為，而所組成的向量空間為的子空間，為行生成的子空間，即，可歸納為。

你的 G 定義不明確，前述第一個 G 是一映射現在是做生成矩陣再下段 span(G) 此處 span(set) 中放的要是集合。藉由集合中的元素線性組合生成，是 span 的意思，不應該為矩陣 (Edited)

chihenliu

2024/06/26 09:43:51

SEC 、 Galois Field 和 Reed Solomon code (RS Code)

可以介紹linear block code和convolution code的差異因為您是先介紹SEC code，R-S code也是BCH code的一種形式感覺可以稍微講解BCH code的數學概念因為對於BCH code來說 RS-code 是其的 Subset 都屬於cyclic code的一種(也就是有限體)

2024/06/26 09:47:52

於 Error Correction Coding_ Mathematical Methods and Algorithms 此書中介紹SEC code中有提及 binary symmetric channel (BSC)及Gaussian model channel 進而引入Hamming distance及Hamming weight的概念能否解講詳細一些

2024/06/26 09:54:58

上述矩陣為奇偶檢驗矩陣(Parity check matirx) ，，。為的解集合，即為的 null space (kernel space) 。據秩—零化度定理 https://zh.wikipedia.org/zh-tw/%E7%A7%A9%E2%80%94%E9%9B%B6%E5%8C%96%E5%BA%A6%E5%AE%9A%E7%90%86，的維度為 7 ，且的三條方程式線性獨立，故秩(rank) 為 3 ，的維度即為 4 。因此。

奇偶校驗矩陣對於codeword向量應該會有H^T c=0

2024/06/26 10:49:29

模術運算

模數運算

allenliao666

2024/07/03 04:43:59

感謝已修正