故事是這樣子的，最近因為工作的關係，頻繁接觸到了錯誤更正碼 (ECC) 中的 Reed-Solomon code 里德-所羅門編碼或是雷德-所羅門編碼（下稱 RS 碼），在學習的過程中，我發現了這篇 Tomverbeure 所寫的 Reed-Solomon Error Correcting Codes from the Bottom Up 十分詳盡，而且切入簡單又好理解，讓我看完立馬看懂相關的程式碼，值得推廣給大家，在徵得作者同意 就透過 AI 整理並翻譯了這篇文。

Reed-Solomon 是一種錯誤更正碼，在 Turbo 與 LDPC 碼出現前，是 1960 年代開發出來非常重要的錯誤更正碼。例如航海家號在傳送影像 時就使用了 RS 編碼，早年設備如音樂光碟 CD 、DVD、藍光的資料都有使用 RS 編碼，現代設計如 QR code 與 RAID 6 上也使用 RS code。

多項式

先來複習一下多項式，一個多項式寫為 $f(x) = c_0 + c_1x + c_2x^2 + … + c_nx^n$

可以對多項式進行加法、減法、乘法或除法運算，以下是簡單的例子，定義 f(x) 和 g(x) 如下：

$$ \begin{aligned} f(x) &= 3 + 2x + 5x^2 - 4x^3 \\ g(x) &= 7x - x^2 \end{aligned} $$

加法與減法的方式，是將相同 x 次方的係數相加或相減：

$$ \begin{aligned} f(x) + g(x) &= (3 + 0) + (2 + 7)x + (5 - 1)x^2 + (-4 + 0)x^3 \\ &= 3 + 9x + 4x^2 - 4x^3 \end{aligned} $$

你可以將多項式彼此相乘：

$$ \begin{aligned} f(x)g(x) &= (3 + 2x + 5x^2 - 4x^3)(7x - x^2) \\ &= (3 + 2x + 5x^2 - 4x^3) \cdot 7x + (3 + 2x + 5x^2 - 4x^3)(-x^2) \\ &= 3 \cdot 7x + 2x \cdot 7x + 5x^2 \cdot 7x - 4x^3 \cdot 7x \\ &\quad + 3 \cdot (-x^2) + 2x \cdot (-x^2) + 5x^2 \cdot (-x^2) - 4x^3 \cdot (-x^2) \\ &= 21x + 14x^2 + 35x^3 - 28x^4 \\ &\quad - 3x^2 - 2x^3 - 5x^4 + 4x^5 \\ &= 21x + 11x^2 + 33x^3 - 33x^4 + 4x^5 \end{aligned} $$

你也可以使用長除法（對但我 latex 打不出來就算了）來進行多項式除法：

$$ \begin{aligned} \frac{f(x)}{g(x)} &= \frac{-4x^3 + 5x^2 + 2x + 3}{-x^2 + 7x} \\ &= 4x + 23 + \frac{-159x + 3}{-x^2 + 7x} \end{aligned} $$

求解多項式

如果是 n-1 維的多項式，則需要 n 個點

將 n 個點代入方程式之後，就能組出一個矩陣運算，以 $ f(x) = 2 - 2x - 3x^{2}+x^{3} $ 為例，在 x = -1, 0, 1, 2 分別計算其結果，得到四個點

Evaluate function

那麼給定 (-1, 0), (0, 2), (1, -2), (2, -6) 這四個點，我們就能把它們代入 f(x)，得到四條方程式： $$ \begin{aligned} c_0 - c_1 + c_2 - c_3 &= 0 \\ c_0 &= 2 \\ c_0 + c_1 + c_2 + c_3 &= -2 \\ c_0 + 2c_1 + 4c_2 + 8c_3 &= -6 \end{aligned} $$

便可以使用高斯消去法，求得 c0, c1, c2, c3 為 (2,-2,-3,1)。
當然，使用高斯消去法（Gaussian elimination）來求出 f(x) 並不是最有效率的方法，因為它需要的運算量為 O(n^3)。 使用 Lagrange polynomial 可以用 O(n^2)的運算量達成一樣的目的。

我們可以選用其他四個 (x,y) 座標點，可以求得完全一樣的方程式。

名詞定義：

以下介紹編碼理論中會出現的一些名詞：

Symbol 符號

符號是最小的資訊單位。
在許多編碼方法中，一個符號就是一個 bit，只有兩種可能的值；但也可以如下 RS 碼所用的以 byte 為單位。

message 訊息

需要被編碼、由符號組成的內容，例如 “AveMujica”。

message word 訊息字/訊息組

Reed–Solomon 碼是一種區塊編碼（block coding）演算法，訊息會被分割成多個訊息組， 並且編碼演算法會對每一個訊息字獨立進行處理，而不依賴之前的訊息字。
RS 碼中通常使用 m 代表訊息，以 k 代表訊息字的長度，例如以 k = 3 處理 “AveMujica” 就會被切割成 ( Ave) ( Muj) ( ica )

alphabet 字母

字母是一個符號可以被指派的所有可能值的完整集合，一般用 q 表示可能的字母數量，當符號是 bit 的時候 q=2；符號為所有大小寫字母和空白時 q = 26 + 26 + 1 = 53。
因為幾乎所有編碼演算法都需要能對符號進行數學運算，例如加法、減法、乘法與除法， 因此幾乎不會使用 q = 53 這樣的字母。
在實務上，大多數編碼演算法的字母表是由二進位數值所組成的序列；8-bit 很常見，但也不是只有 8 bit。
相反地，這類字母表上的運算是定義在伽羅瓦體（Galois field）上進行。 叫它8-bit 整數會有點怪怪的，因為底層的運算完全不一樣。

code word 編碼字

編碼字是把訊息字送進編碼器之後吐出來的結果，一般用 n 代表編碼字的長度。

例如我們將上述 k = 3 編碼為 n = 5，得到新的 code ( AveXX ) ( MujYY ) (icaZZ )
其中的 XX, YY, ZZ 就是加上去的內容，用來作為錯誤檢測與更正。

systematic code 系統編碼

如上面的例子，如果本來的訊息是 AveMujica，編碼很的訊息也含有 AveMujica 那麼就是系統編碼。

Reed–Solomon 編碼：透過多項式求值

Reed–Solomon 編碼最早由 Irving S. Reed 與 Gustave Solomon 提出，他們發表了一篇標題相當低調而且短小的論文 Polynomial Codes over Certain Finite Fields。

語錄：數學論文跟課本就是愈短愈難讀 注意力驚人

前一章說明了，三次多項式可以由 4 個數字決定，可以是四個係數 (C0, C1, C2, C3) ，或是在四個不同的 x 值上求值的結果。
當我們知道係數後，就可以在超過 4 個 x 值上計算該多項式，額外的點對於求解多項式來說是多餘的， 但這正是我們想要的冗餘資訊，讓我們在傳輸過程中資料損壞時，仍能還原原始訊息。

這就是 Reed–Solomon 編碼的核心概念：

透過在比必要更多的 x 值上對多項式求值，來產生冗餘資訊。

假設我要設計一個通訊協定，用來傳送一串數字並加入冗餘，使訊息在部分損壞後仍可復原，可以這樣做：

協定規格

編碼端與解碼端先約定以下參數（與訊息內容無關）：

  • 約定一個字母表（alphabet）
  • 約定訊息字（message word）的長度 k
  • 約定編碼字（code word）的長度 n，n 與 k 的差距越大，冗餘越多，可修正的錯誤也越多
  • 約定如何將訊息字轉換成多項式 p(x)，原始論文中是直接把訊息當作係數，但後面會看到這不一定是最佳做法
  • 約定要在哪些 x 值上計算 p(x)
  • 約定編碼字是將 p(x) 在這些 x 值上求值的結果

套用到實際例子

設定如下：

  • 字母表：整數
  • 訊息長度 k = 4
  • 想要 2 個冗餘符號，編碼字長度 n = 6
  • 多項式在以下 x 值計算：-1, 0, 1, 2, 3, 4（x 的數量與編碼字長度相同）

編碼（Encoder）

給定訊息：(2, -2, -3, 1)

  1. 建立多項式 $p(x) = 2 - 2x - 3x^2 + x^3$ （直接把訊息當作係數）
  2. 在 6 個 x 值上求值：(-1, 0) (0, 2) (1, -2) (2, -6) (3, -4) (4, 10)
  3. 編碼字為： (0, 2, -2, -6, -4, 10)

解碼（Decoder）

解碼端會這樣做：

  1. 接收 6 個編碼字符號若無錯誤，則為：(0, 2, -2, -6, -4, 10)。
  2. 任選其中 4 個點，對應其 x 值，例如選中間 4 個：(0, 2) (1, -2) (2, -6) (3, -4)
  3. 用這 4 個點反推出多項式 p(x) 的係數可得到 (2, -2, -3, 1) 即是原始訊息！

解碼器其實只用 4 個點就能還原訊息，那多傳的 2 個是幹嘛？
這兩個符號就是冗餘，解碼器會利用這些額外符號來：

  • 檢查資料是否被破壞（錯誤偵測）
  • 修正錯誤的數值（錯誤更正）

冗餘正是讓系統具備抗錯能力的核心。

Reed–Solomon 簡單錯誤更正解碼

在討論解碼之前，我們先來看需要多少冗餘符號才能進行錯誤更正：

若要修正最多 s 個符號錯誤，至少需要 2s 個冗餘。

在前面的例子中，我們加入了 2 個冗餘符號，因此可以修正 1 個錯誤。

原始 Reed–Solomon 論文提出的解碼方法

原始論文 Polynomial Codes over Certain Finite Fields 提出以下演算法：

  1. 從收到的 n 個編碼字符號中，從中選出所有 k 個的組合
  2. 對每一組組合，計算對應的多項式係數，統計每一組係數出現的次數
  3. 若錯誤數不超過 s，出現次數最多的係數組，即為原始多項式的係數

套用到範例，接收資料（含錯誤）收到的編碼字為 (0, 2, -2, 1, -4, 10)

注意：第四個值應該是 -6，但變成了 1，表示發生了錯誤。

對應到 x 值 (−1,0) (0,2) (1,-2) (2,1) (3,−4) (4,10)
C6取4 總共有 15 種組合，每組對應的多項式係數與其解如下：

   ((-1, 0), (0, 2), (1, -2), (2, 1)) -> {c0: 2, c1: -19/6, c2: -3, c3: 13/6}
** ((-1, 0), (0, 2), (1, -2), (3, -4)) -> {c0: 2, c1: -2, c2: -3, c3: 1}
** ((-1, 0), (0, 2), (1, -2), (4, 10)) -> {c0: 2, c1: -2, c2: -3, c3: 1}
   ((-1, 0), (0, 2), (2, 1), (3, -4)) -> {c0: 2, c1: 3/2, c2: -2/3, c3: -1/6}
   ((-1, 0), (0, 2), (2, 1), (4, 10)) -> {c0: 2, c1: 1/3, c2: -5/4, c3: 5/12}
** ((-1, 0), (0, 2), (3, -4), (4, 10)) -> {c0: 2, c1: -2, c2: -3, c3: 1}
   ((-1, 0), (1, -2), (2, 1), (3, -4)) -> {c0: -5, c1: 1/3, c2: 4, c3: -4/3}
   ((-1, 0), (1, -2), (2, 1), (4, 10)) -> {c0: -8/3, c1: -5/6, c2: 5/3, c3: -1/6}
** ((-1, 0), (1, -2), (3, -4), (4, 10)) -> {c0: 2, c1: -2, c2: -3, c3: 1}
   ((-1, 0), (2, 1), (3, -4), (4, 10)) -> {c0: 16, c1: 23/6, c2: -10, c3: 13/6}
   ((0, 2), (1, -2), (2, 1), (3, -4)) -> {c0: 2, c1: -25/2, c2: 11, c3: -5/2}
   ((0, 2), (1, -2), (2, 1), (4, 10)) -> {c0: 2, c1: -9, c2: 23/4, c3: -3/4}
** ((0, 2), (1, -2), (3, -4), (4, 10)) -> {c0: 2, c1: -2, c2: -3, c3: 1}
   ((0, 2), (2, 1), (3, -4), (4, 10)) -> {c0: 2, c1: 19, c2: -61/4, c3: 11/4}
   ((1, -2), (2, 1), (3, -4), (4, 10)) -> {c0: -40, c1: 129/2, c2: -31, c3: 9/2}

解方程式之統計結果，係數：(2, -2, -3, 1) 出現了 5 次（不知道原作者是不是用手算的，最後一組答案算錯，這裡打錯變 6 次），而其他結果都各不相同，因此它是最可能的正確解。
也確實是原始訊息的係數。

背後原因也很好理解，四個正確的點就能定出正確的多項式；從五個正確點中能取出四種組合，其他的則都會得到不一樣的結果。

為什麼這個方法不實用？

即使在這個小例子中 n=6, k=4 也需要計算： $$ \binom{6}{4} = \frac{6!}{4!2!} = 15 $$ 次多項式。

真實系統的情況，常見參數為： n=255, k=223 組合數為： $$ \begin{aligned} \binom{255}{223} &= \frac{255!}{223!32!} \\ &= 50,964,019,775,576,912,153,703,782,274,307,996,667,625 \\ &\approx 5E+40 \\ \end{aligned} $$

因此實際應用中會使用更高效的演算法，例如：

這篇文章只講編碼都很簡單，相信我編碼學難的都在解碼器。

如何改成系統編碼？

讓我們先回顧之前的編碼器是如何運作的：

  1. 將訊息符號作為多項式 p(x) 的係數。
  2. 將多項式 p(x) 在 n 個固定的 x 上救值。
  3. 編碼字即為這 n 個 p(x) 的值。

這種編碼方式可以正常運作，但是編碼字中的所有符號都與原始訊息字不同。
(2,-2,−3,1) 被編碼為 (0, 2, -2, -6, -4, 10)。

如果我們能夠讓編碼後的編碼字保留原始訊息，並在後面附加一些冗餘符號，會不會更好呢？
也就是將 (2,-2,-3,1) 編碼為 (2, -2, -3, 1, a, b)

優點之一是：額外的兩個碼只為了確認有沒有發生錯誤，沒有錯誤就不用解碼，可以直接取用傳來的訊息。
修改為系統編碼也很容易，訊息不再是 p(x) 的係數，而是p(x) 在某些點的取值。

編碼器：

  1. 訊息字 $(m_0,m_1,\ldots,m_{k-1})$ 視為多項式 p(x) 在某些已知 x 值上的函數值。
  2. 透過這些點 $(x_i, m_i)$ 求出多項式 p(x) 的係數。
  3. 將 p(x) 在額外的 (n-k) 個 x 值上進行評估，產生冗餘符號。
  4. 最終編碼字為：訊息字 + 冗餘符號。

用同樣的例子來試試看，訊息：(2, -2, -3, 1)
現在我們將其視為多項式 p(x) 在以下 x 值的結果：x = (-1,0,1,2)
因此得到點：(-1,2) (0,-2) (1,-3) (2,1)

接著，我們需要根據這些點來建構多項式 $p(x)$ 得到：

$$ p(x) = -2 - \frac{17}{6}x + \frac{3}{2}x^2 + \frac{1}{3}x^3 $$

這裡的係數出現了分數，而不是整數。這是為什麼在實務上不會使用整數，會改用例如 Galois Field 等其他數學工具來實作來做 Reed–Solomon 編碼的一個原因。

接著，用這個方程式在額外的兩個點取值：

p(3) = 12
p(4) = 32

因此，編碼字為 (2,-2,-3,1,12,32)，解碼器與之前完全相同

將編碼字表示為多項式係數

在前面介紹的兩種編碼方法中，編碼字是由某個多項式 p(x) 的取值結果所組成。還有另一種 Reed–Solomon 編碼方式，是讓編碼字直接由多項式的係數組成。
因為這是最常見的的 RS 碼，所以我們也需要提一下。這裡會多一點點億點點數學推導，但後面的例子會幫助釐清概念。

一個訊息字包含 k 個符號，而我們需要 n 個符號來形成編碼字。 使用多項式的係數來表示編碼，那我們需要構造一個 (n-1) 次的多項式 s(x)。

我們希望 s(x) 具有以下兩個性質：

  1. 其中有 k 個係數與訊息字 $(m_0,m_1,\ldots,m_{k-1})$ 相同，形成系統編碼。
  2. 當 s(x) 在 (n-k) 個特定的 x 值上求值時，其結果為 0。

以下是一種構造符合這些性質的多項式的方法：

  1. 建立多項式 p(x)，其係數為 $(m_0,m_1,\ldots,m_{k-1})$（與之前相同）。
  2. 建立所謂的生成多項式（generator polynomial）$g(x) = (x - x_0)(x - x_1)\cdots(x - x_{n-k-1})$

$(x_0, x_1, \ldots, x_{n-k-1})$ 是協定的參數，共有 (n-k) 個值，對應冗餘的數量。

$g(x)$ 展開後為： $$ g(x) = g_0 + g_1 x + \cdots + g_{n-k} x^{n-k} $$ 其次數為 (n-k)，且最高次項係數 $g_{n-k} = 1$。

計算多項式 $p(x)x^{n-k}$ 除以 g(x) 的商式與餘式： $$ p(x)x^{n-k} = q(x)g(x) + r(x) $$ 其中 $q(x)$ 是商，$r(x)$ 是餘式，因為 g(x) 最高項為 (n-k) 次，因此 r(x) 的最高項是 (n-k-1) 次。

定義我們要的多項式 $s(x) = p(x)x^{n-k} - r(x)$

讓我們檢查這樣構造的結果：

性質一：s(x) 的 k 個係數為 $(m_0,\ldots,m_{k-1})$

$p(x)$ 的次數為 $(k-1)$，乘上 $x^{n-k}$ 後得到： $$ m_0 x^{n-k} + m_1 x^{n-k+1} + \cdots + m_{k-1} x^{n-1} $$

其最高次為 (n-1)，第一個非零項為 $x^{n-k}$，也就是說從常數項到 $x^{n-k-1}$ 都是 0，因此

  1. $r(x)$ 涵蓋 $x^0$ 到 $x^{n-k-1}$
  2. $p(x)x^{n-k}$ 涵蓋 $x^{n-k}$ 到 $x^{n-1}$
  3. => $p(x)x^{n-k}$ 跟 $r(x)$ 的係數沒有重疊。
  4. => s(x) 在 $x^{n-k}$ 到 $x^{n-1}$ 的係數就是 p(x) 的係數，也就是 $(m_0, m_1, \ldots, m_{k-1})$

滿足了第一個我們想要的性質：系統編碼。

性質二：s(x) 在 (n-k) 個特定的 x 值上被評估時，其結果為 0

根據定義 $s(x)=p(x)x^{n-k}-r(x) = q(x)g(x)$

因為 g(x) 的關係，代入所有冗餘 x 值時，都會得到 0。

這樣兩個性質有什麼好處呢？這就得看 decoder 了。

Decoder 會把接收到的 code word 當成多項式 $s’(x)$ 的係數，每一組 $s’(x_i)$ 都稱為一個 syndrome。
利用 s(x) 的性質，只要沒發生傳輸錯誤，把冗餘的 x 值代入檢查結果是否為 0 即可，如果 syndrome 不等於 0，代表有傳輸錯誤。

此時定義兩者的差值為 error polynomial：e(x) 使得 $s’(x)=s(x)+e(x)$

同樣都是 $(n-1)$ 次多項式，有 (n-k) 個係數可構造 (n-k) 條方程式。

展開後可寫成：

$$ \begin{aligned} e_0 + e_1x_0 + e_2x_0^2 + \cdots + e_{n-1}x_0^{n-1} &= s_0 \\ e_0 + e_1x_1 + e_2x_1^2 + \cdots + e_{n-1}x_1^{n-1} &= s_1 \\ \vdots \\ e_0 + e_1x_{n-k-1} + e_2x_{n-k-1}^2 + \cdots + e_{n-1}x_{n-k-1}^{n-1} &= s_{n-k-1} \end{aligned} $$

但若錯誤數量不超過 $\frac{n-k}{2}$ 就能進行修正。

編碼器範例

訊息：(2,-2,-3,1) 對應成多項式：$p(x)=2 - 2x -3x^2+x^3$

選定兩個冗餘的位置：

$$ x_0=1 \newline x_1=2 $$

作為 generator polynomial 的根： $$ g(x)=(x-1)(x-2)=x^2-3x+2 $$

接著將 $p(x)x^2$ 除以 g(x)

$$ \begin{aligned} \frac{x^5 - 3x^4 - 2x^3 + 2x^2}{x^2-3x+2} &= (x^3-4x-10)(x^2-3x+2)+(-22x+20) \end{aligned} $$

其中餘式 $r(x)=(-22x+20)$

因此編碼的結果為： $$ \begin{aligned} s(x) &= p(x)x^2-r(x) \\ &= (2x^2-2x^3-3x^4+x^5) - (-22x+20) \end{aligned} $$

編碼結果為：(2,-2,-3,1,22,-20)

可以嘗試看看，上式代入 x=1, 2 都會得到 0。

解碼器範例

因為有 2 個 redundant symbols，所以最多只能修正 1 個錯誤，最簡單的方法，是逐一嘗試所有可能的錯誤位置並解聯立方程式。

假設收到的 code word 為 (2,-2,-1,1,22,-20) 第三個符號從 -3 變成 -1。

因此收到的多項式：

$$ s’(x)=(2x^2-2x^3-x^4+x^5)-(-22x+20) $$

x = 1, 2 代入後得到 syndrome：

$$ \begin{aligned} s’(1) &= 2 \\ s’(2) &= 32 \end{aligned} $$

syndrome 不為 0，因此發生了錯誤。

嘗試 s0

先假設 $s_0$ 錯誤，其餘皆正確，則：

$$ s(x) = (s_0x^2 - 2x^3 - x^4 + x^5) - (-22x+20) $$

分別代入 x=1 與 x=2：

$$ \begin{aligned} x=1 &\implies s_0 -2 - 1 + 1 + 22 - 20=0 \\ &\implies s_0 = 0 \\ x=2 &\implies 4s_0-16-16+32+44-20=0 \\ &\implies s_0 = -6 \end{aligned} $$

兩個結果矛盾，因此 $s_0$ 不是錯誤位置。

嘗試 s2

對所有係數重複同樣步驟，只有 $s_2$ 會得到一致結果。

$$ \begin{aligned} s(x) &= (2x^2 - 2x^3 - s_2x^4 + x^5) - (-22x+20) \\ x=1 &\implies 2-2-s_2+1+22-20 = 0 \\ &\implies s_2=3 \\ x=2 &\implies 8-16-16s_2+32+44-20=0 \\ &\implies s_2=3 \end{aligned} $$

兩個結果一致，因此 $s_2$ 確實是錯誤的係數。

修正後的 code word 為： $$ (2,-2,-3,1,22,-20) $$ message word 即為前 4 個符號。

多項式除法的硬體實作

以係數作為編碼字 Reed–Solomon code 編碼方式，是你在實際應用中最常看到的方法，也看到它使用了多項式除法。 那麼，要如何在硬體中實作它呢？

一般多項式除法的流程如下： 以被除式（dividend）作為初始餘數（remainder）。 從餘數中減去除式（divisor）的倍數，使得餘數中最高次的 x 項係數變成 0。 這個倍數會成為商（quotient）的一部分，而減法後剩下的內容則成為新的餘數。 重複前一步，直到餘數中最高次的非零係數，其對應的 xxx 次方低於除式的次方為止。

Long Division 1

硬體的設計技巧在於，不要把整個被除數載進記憶體，不用管被除式的低次項， 需要的時候再把他們加到結果內，只需要一個跟除數一樣長的佇列來放餘式。
每進行一個步驟，餘式最高項一定歸零（仔細觀察下圖，加過被除式係數就會得到商式的係數）， 將該數從佇列中移除，更新後的餘式往前進一格，從尾端加入下一個係數。

Long Division 2

上述的除法器很容易就能以下列的電路進行實作：

Hardware Divider

p(x) 的係數由高位到低位從左下依序輸入。
輸入後與當前餘式 r(x) 最高位相加，乘 -1 得到這輪 generator g(x) 要相乘的數字。
餘式最高位在減去相乘結果後一定是 0 因此隨後就丟掉了。
中間的乘法運算單元放了目前的 generator 係數負責乘法。

輸入完 p(x) 之後，force_zero 設定讓輸入改為 0，輸出就會開始吐出餘式的各項。

編碼器的硬體實作

Hardware Encoder

與一般 polynomial divider 硬體相比，唯一的差別是多了一個 output multiplexer，可以讓輸入直接繞送到輸出，因為 s(x) 的高位項即 $p(x)x^{n-k}$ 無須計算，直接輸出即可。

如果搜尋 reed solomon encoder 的硬體圖，會看到大量類似的架構。
只有一點不同：你幾乎不會看到：-1 乘法器。因為在 Galois field 的數學中，加法與減法是一樣的。

結論與後記

這就是 Reed–Solomon code 的入門介紹。

還有許多內容尚未討論，例如：

  • Galois field 數學
  • Galois field 硬體邏輯
  • 解碼演算法

希望這份整理對你而言，能像對我自己一樣有幫助，我個人是覺得超級有幫助，看完這篇本來看不懂的程式碼瞬間通透 ，但另一方面也很後悔為什麼要翻這篇，在 AI 時代做翻譯感覺真的有點蠢，明明大家瀏覽器點一下就能看到中文了。
而且這篇滿滿的 latex，又是分數又是長除法的，真的是會累死人，雖然這年頭有 AI 可以幫忙，但檢查這堆 latex 語法還是異常的累人呀。

參考資料

首先，這篇文本身就是翻譯文，所以這篇一定要列為參考資料之首

  1. Reed-Solomon Error Correcting Codes from the Bottom Up

  2. 針對這篇文章，我寫了一份 python script 來幫我計算（不然現在用筆算都會出錯，想當年高中大學解方程組甚至可以心算…），這個 script 也有留在 github gist 上供大家參考。

剩下是原作者最出的參考資料，擇其還未失效的附上：

  1. NASA Tutorial on Reed-Solomon error correction coding

  2. Wiki: Reed–Solomon error correction