Error Correction

Error Correction

「錯誤更正」。找出損毀變異的地方,並且嘗試修復。

偵測較簡單,更正較複雜。兩者的應用場景有所不同。

有些時候,我們只需要偵測,不需要更正。例如網路傳輸,如果發現出錯了,麻煩對方馬上重傳一次就好。例如身份證字號,最後一碼是驗證碼,一方面避免卡號連續、一方面避免行政人員輸入錯誤;如果輸入錯誤,重新輸入就好。

有些時候,我們必須要更正。例如CD光碟片,時間久了染料變質了,資料不正確,就必須更正資料。例如火星探勘太空船發送到地球的訊息,由於距離太遠了,重傳太花時間,必須直接更正。

Repetition Code

以重複備份更正錯誤

資料損毀變異怎麼辦?製作備份,有備無患。

原始資料:時今
備份資料:時令

發現錯別字「今」,應該改成「令」。

備份資料資料也損毀變異怎麼辦?那就製作多個備份。

時今 時令 時令
發現錯別字「今」,應該改成「令」。

時令 時今 時今 時令
無法確定錯別字。

時令 時今 時令 時今 時今 時今
錯別字誤判為「令」。

只要正確資料過半,就能正確更正。然而無論多少備份,仍有機會毀損達半,無法更正。我們只能多建立備份,避免憾事發生。

Repetition Code

00110001 ---> 001100010011000100110001

電腦以位元為單位。針對一個特定位元,只要所有對應的位元,正確位元過半,就能正確更正。

此演算法有兩種觀點:備份資料放在原始資料尾端(主從、狹觀)、各份資料相互支援(平等、宏觀)。

編碼:資料重複N-1次(一共N份),變成碼。
解碼:針對每個位元,找到所有對應位元(一共N個)。過半者,推定為正解。

Hadamard Code

以最短距離更正錯誤

資料長度:N個位元。總共2ᴺ種資料。

碼長度:N+K個位元。總共2ᴺ⁺ᴷ種情形,從中挑選2ᴺ個碼。

自由設定資料與碼的對應方式。

偵測:給定一個待測碼,從2ᴺ個碼之中,找到相同的碼。找不到就表示有錯誤。

更正:給定一個待測碼,從2ᴺ個碼之中,找到差異最小(距離最近)的碼。更正成它。

差異(距離):相異位元的數目。專業術語是Hamming Distance。

N=5 example:
          [0]   [0]                   [1]   [0]      
hamming   [1]   [1]         hamming   [1]   [0]      
distance( [1] , [0] ) = 2   distance( [1] , [0] ) = 5
          [1]   [0]                   [1]   [0]      
          [1]   [1]                   [1]   [0]      

          [1]   [1]                   [1]   [0]      
hamming   [1]   [1]         hamming   [1]   [0]      
distance( [0] , [0] ) = 0   distance( [0] , [1] ) = 5
          [1]   [1]                   [0]   [1]      
          [1]   [1]                   [0]   [1]      

碼之間的距離越遠,就能容忍越多錯誤!

挑選2ᴺ個碼,令碼的兩兩距離皆大於等於d。

偵測能耐:相差d-1個位元,仍可正確偵測。

更正能耐:中點為分野,分開討論d是偶數、奇數,相差d/2-1、(d-1)/2個位元,仍可正確更正。通常簡單寫成⌊(d-1)/2⌋。

編碼:建立表格,2ᴺ種資料對應到2ᴺ個碼。

解碼:窮舉2ᴺ個碼,找到Hamming距離最小者。

所有的碼

利用「Hadamard Matrix」,N個向量當作碼。

HN = [HN/2 HN/2]
     [HN/2 HN/2]

H₂     H₄         H₈
[0 0]  [0 0 0 0]  [0 0 0 0 0 0 0 0]
[0 1]  [0 1 0 1]  [0 1 0 1 0 1 0 1]
       [0 0 1 1]  [0 0 1 1 0 0 1 1]
       [0 1 1 0]  [0 1 1 0 0 1 1 0]
                  [0 0 0 0 1 1 1 1]
                  [0 1 0 1 1 0 1 0]
                  [0 0 1 1 1 1 0 0]
                  [0 1 1 0 1 0 0 1]

擴充成2N個碼。原本數值反轉即得。

H₂         H₄                 H₈
[0 0|1 1]  [0 0 0 0|1 1 1 1]  [0 0 0 0 0 0 0 0|1 1 1 1 1 1 1 1]
[0 1|1 0]  [0 1 0 1|1 0 1 0]  [0 1 0 1 0 1 0 1|1 0 1 0 1 0 1 0]
           [0 0 1 1|1 1 0 0]  [0 0 1 1 0 0 1 1|1 1 0 0 1 1 0 0]
           [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 0 0 0 1 1 1 1|1 1 1 1 0 0 0 0]
                              [0 1 0 1 1 0 1 0|1 0 1 0 0 1 0 1]
                              [0 0 1 1 1 1 0 0|1 1 0 0 0 0 1 1]
                              [0 1 1 0 1 0 0 1|1 0 0 1 0 1 1 0]

碼的兩兩距離

碼的兩兩距離皆大於等於N/2。證明省略。

編碼

碼長度、碼數量皆已確認!那麼資料長度呢?

引入線性組合的概念,找到這些向量的basis。基底向量的個數,設定成資料長度;一筆資料套用線性組合求得對應的碼!

H₂     H₄       H₈
basis  basis    basis       (H₄ example)
[1 1]  [1 1 1]  [1 1 1 1]        encode              encode      
[1 0]  [1 1 0]  [1 1 1 0]   101 -------> 0101   111 -------> 1001
       [1 0 1]  [1 1 0 1]   [1 1 1] [1]   [0]   [1 1 1] [1]   [1]
       [1 0 0]  [1 1 0 0]   [1 1 0] [0] = [1]   [1 1 0] [1] = [0]
                [1 0 1 1]   [1 0 1] [1]   [0]   [1 0 1] [1]   [0]
                [1 0 1 0]   [1 0 0]       [1]   [1 0 0]       [1]
                [1 0 0 1]
                [1 0 0 0]

解碼

編碼:預先建立所有碼的basis。資料經過線性組合得到碼。

解碼:窮舉所有資料並且求得碼,找到Hamming距離最小的碼。一旦發現Hamming距離小於N/2,即可立即結束,推定為正解。

編碼率

資料長度呈線性成長,碼長度卻呈指數成長,付出代價極大!

矩陣 | 碼  | 基底 | 資料 | 碼  | 兩兩   | 偵測 | 更正 | 編碼率
大小 | 數量 | 向量 | 長度 | 長度 | 距離   | 錯誤 | 錯誤 | 資料與碼的比例
-----|------|------|------|------|--------|------|------|---------------
N=2  | 4 種 | 2個  | 2    | 2    | 至少1  | 0    | 0    | 2/2(毫無功能)
N=4  | 8 種 | 3個  | 3    | 4    | 至少2  | 1    | 0    | 3/4(只能偵測)
N=8  | 16種 | 4個  | 4    | 8    | 至少4  | 2    | 1    | 4/8
N=16 | 32種 | 5個  | 5    | 16   | 至少8  | 4    | 3    | 5/16
N=32 | 64種 | 6個  | 6    | 32   | 至少16 | 8    | 7    | 6/32

由於付出代價極大,實務上不採用此演算法。

延伸閱讀:Maximum Distance Separable Code

「最大距離分離碼」。2進位碼,長度N,最小距離d,數量2ᴺ⁻ᵈ⁺¹。數量撐到最大。

一個編碼演算法,並非最大距離分離碼,則表示編碼演算法仍有改進空間。也許還可以擴充一些碼、也許還可以增加一點距離。Hadamard Code顯然不是最大距離分離碼。

Reed–Muller Code

Reed–Muller Code

以Hadamard Code的基底向量作為素材,兩兩內積(甚至三三內積、四四內積),構造更複雜的基底向量。

由於付出代價極大,實務上不採用此演算法。

Hamming Code

以前後文更正錯誤

最簡單的方法:原始資料直接重複好幾次。

更聰明的方法:補充說明,依照前後文推敲正文。

資料:好人氣
不知是否有錯別字。

資料:好人氣青空萬里
發現錯別字「人」,應該改成「天」。
發現錯別字「青」,不過沒關係。

編碼

僅容忍一個錯誤位元。

三個parity。這是經過精心設計的,有很強的數學性質。

寫成代數式子:

{ x₄ = x₀ + x₁ + x₂
{ x₅ = x₀ + x₁ + x₃
{ x₆ = x₀ + x₂ + x₃

加法的意義:

數字:餘數 (mod 2)  	數字:Boolean
加法:餘數加法      	加法:XOR
(左右等價。教科書習慣採用左邊。)

範例:

0123  encode  0123456
—————————————————————
0000 -------> 0000000
1111 -------> 1111111
0011 -------> 0011110
1010 -------> 1010010

所有的碼

從屬關係改成平等關係。

{ x₀ + x₁ + x₂ + x₄ = 0
{ x₀ + x₁ + x₃ + x₅ = 0
{ x₀ + x₂ + x₃ + x₆ = 0

所有解就是所有碼。

                [x₀]
                [x₁]
[1 1 1 0 1 0 0] [x₂]   [0]
[1 1 0 1 0 1 0] [x₃] = [0]
[1 0 1 1 0 0 1] [x₄]   [0]
                [x₅]
                [x₆]
       H         x   =  0

運算符號的意義。

數字:餘數 (mod 2)  	數字:Boolean
加法:餘數加法      	加法:XOR
倍率:餘數乘法      	倍率:AND
(左右等價。教科書習慣採用左邊。)

碼的兩兩距離

一、碼=解。

                [0]        |                 [1]         
                [0]        |                 [0]         
[1 1 1 0 1 0 0] [1]   [0]  | [1 1 1 0 1 0 0] [1]   [0]   
[1 1 0 1 0 1 0] [1] = [0]  | [1 1 0 1 0 1 0] [0] = [0]   
[1 0 1 1 0 0 1] [1]   [0]  | [1 0 1 1 0 0 1] [0]   [0]   
                [1]        |                 [1]         
                [0]        |                 [0]         
       H         x   =  0  |        H         x   =  0   

二、兩個碼的距離=兩個碼相加後有幾個1。

          [0]   [1]           [0]   [1]              [0]   [1]  
          [0]   [0]     how   [0]   [0]              [0]   [0]  
hamming   [1]   [1]     many  [1]   [1]     hamming  [1]   [1]  
distance( [1] , [0] ) = 1s? ( [1] + [0] ) = weight ( [1] + [0] )
          [1]   [0]           [1]   [0]              [1]   [0]  
          [1]   [1]           [1]   [1]              [1]   [1]  
          [0]   [0]           [0]   [0]              [0]   [0]  

三、矩陣運算的線性、模數運算的封閉性:兩個解相加=某一個解!所有解兩兩相加=所有解(剔除零向量)!所有解的兩兩距離=所有解(剔除零向量)數1。

[0]   [1]   [1]
[0]   [0]   [0]
[1]   [1]   [0]
[1] + [0] = [1]  會是 Hx=0 的某一個解
[1]   [0]   [1]
[1]   [1]   [0]
[0]   [0]   [0]

四、矩陣運算的線性組合:一個解數1=1所對應的矩陣向量,相加等於零向量。

                [0]
   ↓   ↓   ↓    [1]←
[1 1 1 0 1 0 0] [0]    [0]
[1 1 0 1 0 1 0] [1]← = [0]
[1 0 1 1 0 0 1] [0]    [0]
                [1]←
                [0]
       H         x   =  0

有兩個解(碼)距離為3。
有一個解恰有三個1。
矩陣H有三個向量相加是零向量。

五、採用試誤法,嘗試各種距離。採用反證法,證明各種距離不成立。運用矩陣向量,判斷碼的距離。

有兩個碼(解)距離為0:碼皆相異,顯然不成立。
有兩個碼(解)距離為1:某一個解僅有一個1,某一個矩陣向量是零向量。
            但是矩陣沒有零向量。不成立。
有兩個碼(解)距離為2:某一個解僅有兩個1,某兩個矩陣向量相加等於零向量。
            但是矩陣向量兩兩相加都不是零向量。不成立。
有兩個碼(解)距離為3:仿前。確實有三個向量相加是零向量。成立。

故碼的兩兩距離皆大於等於3。錯1個位元,仍可完全更正。

六、碼的兩兩距離大於等於d=矩陣向量沒有零向量、兩兩相加沒有零向量、三三相加沒有零向量、……、d-1 d-1相加沒有零向量,而d d相加可得零向量。

也就是說,仔細設計parity式子,得以調整容忍程度。

解碼

試誤法是窮舉2ᴺ種資料可能性,N是資料長度。以下介紹更快的演算法。

x是正確的碼。x+e是毀損的碼,e是誤差。
Hx = 0                    前面談過
H(x+e) = Hx + He = He     H(x+e)和He的結果恰好一樣

因為只容許一個錯誤位元,
所以e只能是這8個向量的其中一種:
[0] [1] [0] [0] [0] [0] [0] [0]
[0] [0] [1] [0] [0] [0] [0] [0]
[0] [0] [0] [1] [0] [0] [0] [0]
[0] [0] [0] [0] [1] [0] [0] [0]
[0] [0] [0] [0] [0] [1] [0] [0]
[0] [0] [0] [0] [0] [0] [1] [0]
[0] [0] [0] [0] [0] [0] [0] [1]
 0   e₀  e₁  e₂  e₃  e₄  e₅  e₆
至於其他情況,無法保證正確更正,不討論。

預先計算He,代入8種可能性。
H0  He₀ He₁ He₂ He₃ He₄ He₅ He₆
[0] [1] [1] [1] [0] [1] [0] [0]
[0] [1] [1] [0] [1] [0] [1] [0]
[0] [1] [0] [1] [1] [0] [0] [1]
以線性組合的觀點來看,其實就是H的各個向量。

解碼。給定一個碼x+e,計算H(x+e) = He。判斷He是H0 He₀ ... He₆當中哪一個,反推e是多少,反推錯誤位元。

(example 1)

      encode           channel           decode
1111 -------> 1111111 --------> 1110111 -------> ?

                [1]                  [0]
                [1]                  [0]
[1 1 1 0 1 0 0] [1]   [0]            [0]
[1 1 0 1 0 1 0] [0] = [1]   =>   e = [1]   =>   bit x₃ is wrong.
[1 0 1 1 0 0 1] [1]   [1]            [0]
                [1]                  [0]
                [1]                  [0]
       H       (x+e)= He₃

(example 2)

      encode           channel           decode
1111 -------> 1111111 --------> 1111110 -------> ?

                [1]                  [0]
                [1]                  [0]
[1 1 1 0 1 0 0] [1]   [0]            [0]
[1 1 0 1 0 1 0] [1] = [0]   =>   e = [0]   =>   bit x₆ is wrong.
[1 0 1 1 0 0 1] [1]   [1]            [0]
                [1]                  [0]
                [0]                  [1]
       H       (x+e)= He₆

(example 3)

      encode           channel           decode
1111 -------> 1111111 --------> 1111111 -------> ?

                [1]                  [0]
                [1]                  [0]
[1 1 1 0 1 0 0] [1]   [0]            [0]
[1 1 0 1 0 1 0] [1] = [0]   =>   e = [0]   =>   all right!
[1 0 1 1 0 0 1] [1]   [0]            [0]
                [1]                  [0]
                [1]                  [0]
       H       (x+e)= H0
編碼:三個parity式子。
   分別計算parity,添在資料尾端。
解碼:三個parity式子,形成矩陣H。
   碼代入H。若為0,則正確。
   若對應到H的向量,則錯誤;錯誤位元編號即是向量編號。

調動位元順序

調動位元順序、調動矩陣直條順序,讓矩陣橫條逐步右挪。更好編碼。

                [x₀]        |                 [x₄]      
                [x₁]        | row right shift [x₅]      
[1 1 1 0 1 0 0] [x₂]   [0]  | [1 0 1 1 1 0 0] [x₂]   [0]
[1 1 0 1 0 1 0] [x₃] = [0]  | [0 1 0 1 1 1 0] [x₁] = [0]
[1 0 1 1 0 0 1] [x₄]   [0]  | [0 0 1 0 1 1 1] [x₀]   [0]
                [x₅]        |                 [x₃]      
                [x₆]        |                 [x₆]      
0123  encode  0123456       | 0123  encode  4521036
—————————————————————       | —————————————————————
0000 -------> 0000000       | 0000 -------> 0000000
1111 -------> 1111111       | 1111 -------> 1111111
0011 -------> 0011110       | 0011 -------> 1110010
1010 -------> 1010010       | 1010 -------> 0110100

調動位元順序、調動矩陣直條順序,讓直條由小到大。更好解碼。

                [x₀]        |  lexico order   [x₆]      
                [x₁]        |  ------------>  [x₅]      
[1 1 1 0 1 0 0] [x₂]   [0]  | [0 0 0 1 1 1 1] [x₃]   [0]
[1 1 0 1 0 1 0] [x₃] = [0]  | [0 1 1 0 0 1 1] [x₄] = [0]
[1 0 1 1 0 0 1] [x₄]   [0]  | [1 0 1 0 1 0 1] [x₂]   [0]
                [x₅]        |                 [x₁]      
                [x₆]        |                 [x₀]      

編碼率

推廣位元數量、推廣矩陣邊長。碼的兩兩距離依然皆大於等於3,依然只容許一個錯誤位元。

資料長度呈指數成長,parity數量僅呈線性成長,代價銳減!

3 x 2³-1       4 x 2⁴-1       5 x 2⁵-1
[0 0 0     1]  [0 0 0     1]  [0 0 0     1]
[0 1 1 ... 1]  [0 0 0     1]  [0 0 0     1]
[1 0 1     1]  [0 1 1 ... 1]  [0 0 0 ... 1]
               [1 0 1     1]  [0 1 1     1]
                              [1 0 1     1]

追加一個位元

7bit補足為8bit = 1byte,補入Parity Check。更好儲存。

x₄ = x₀ + x₁ + x₂     | x₄ = x₀ + x₁ + x₂
x₅ = x₀ + x₁ + x₃     | x₅ = x₀ + x₁ + x₃
x₆ = x₀ + x₂ + x₃     | x₆ = x₀ + x₂ + x₃
                      | x₇ = x₀ + x₁ + x₂ + x₃ + x₄ + x₅ + x₆
0123  encode  0123456 | 0123  encode  01234567
————————————————————— | ——————————————————————
0000 -------> 0000000 | 0000 -------> 00000000
1111 -------> 1111111 | 1111 -------> 11111111
0011 -------> 0011110 | 0011 -------> 00111100
1010 -------> 1010010 | 1010 -------> 10100101

Low-density Parity-check Code

編碼

自由設計parity,令矩陣稀疏。

{ x₀ + x₁ + x₂ + x₃ + x₅ + x₇ + x₉ = 0
{ x₀ + x₂ + x₃ + x₆ + x₇ + x₈ + x₉ = 0
{ x₁ + x₃ + x₇ = 0
{ x₀ + x₄ + x₆ + x₇ + x₈ + x₉ = 0
{ x₂ + x₃ + x₄ + x₆ + x₈ = 0

所有的碼

所有解就是所有碼。

                      [x₀]
                      [x₁]
[1 1 1 1 0 1 0 1 0 1] [x₂]   [0]
[1 0 1 1 0 0 1 1 1 1] [x₃]   [0]
[0 1 0 1 0 0 0 1 0 0] [x₄] = [0]
[1 0 0 0 1 0 1 1 1 1] [x₅]   [0]
[0 0 1 1 1 0 1 0 1 0] [x₆]   [0]
                      [x₇]
                      [x₈]
                      [x₉]
          H            x   =  0

所有的碼(Tanner Graph)

表示成二分圖。有人叫做Tanner Graph。

解碼(Belief Propagation Decoding)

自由設計parity,各種數學性質蕩然無存。

解碼,求最佳解是NP-hard問題,只好改求近似解。

其中一種演算法:Belief Propagation,貪心法,用二分圖的一側算出另一側,兩側交替計算,直到收斂為止。

編碼率

當今世上的演算法之中,LDPC Code編碼率最高。節省空間與時間,非常實用!

應用

無線通訊Wi-Fi (IEEE 802.11)、WiMAX (IEEE 802.16)、5G NR (3GPP 38.212)。電視訊號DVB-S2、DVB-T2、DVB-C2。電腦硬碟SSD。快閃記憶體NAND。

最後講個八卦

因為parity沒有規律,所以找不到簡潔的數學性質,所以找不到精確的解碼演算法。以貪心法強行解碼,實在有夠低能。這導致LDPC Code一出現就被打入冷宮。

直到三十年以後,大家才漸漸察覺,自由自在的parity,可以突破編碼率瓶頸。直到五十年之後,LDPC Code才正式晉升主角,全面取代Turbo Code。

Convolutional Code

講義

Convolutional Code

「卷積碼」。Hamming Code是線性函數,自訂parity位置。Convolutional Code是線性遞迴函數,同一組parity不斷移位。

複製貼上,乃是人性。優點是容易設計電路。格子是變數。

另一種繪圖風格。格子是暫存器。

編碼(Trellis Diagram)

引入「Markov Chain」的概念,畫成狀態轉移圖。

或者畫成狀態分層圖。有人叫做Trellis Diagram。

編碼,即是走出一條路徑。起點必須是00。

解碼(Viterbi Algorithm)

將誤差大小填在邊上。誤差是Hamming Distance。

解碼,即是找到誤差總和最小的路徑。起點必須是00。

演算法是動態規劃。逐層計算。

Convolutional Code名稱由來

資料視作數列,以許多個線性濾波器進行編碼。

線性濾波器=多項式乘法=數列卷積。

請見本站文件「Filter」。

Convolutional Code其他設計

一個queue。

兩個queue。

循環。Recursive Systematic Convolutional Code。

最後講個八卦

Viterbi Algorithm和PageRank同是傳奇。以一個演算法作為起點,建立一間公司,開拓一種產業,創造一個時代。

若你不熟悉高通、只熟悉谷歌,主要原因是台灣實施媒體管制。在台灣,IBM、Intel、Qualcomm的聲名遠不如微軟、谷歌、蘋果,主要原因是後者的待人用事方式,跟黨一拍即合。

Turbo Code

編碼

「渦輪碼」。Recursive Systematic Convolutional Code,並聯兩份編碼器。第二份編碼器,其輸入經過重新排列。

重新排列資料,拷貝原本parity,藉以追加一組全新parity。

複製貼上,乃是人性。優點是容易設計電路。

解碼

我沒有弄懂。

Interleaver

重新排列。下圖是四個橫條,也有人用兩個橫條。

                                   write
input                            ———————————→
1 2 3 4 5 6 7 8 ... 16        r |  1  2  3  4
                              e |  5  6  7  8
output                        a |  9 10 11 12
1 5 9 13 2 6 10 14 ... 16     d ↓ 13 14 15 16

編碼率

線性遞迴函數、重新排列資料,都是為了輕鬆拷貝parity。然而這麼做並未帶來任何好處。parity的位置受到侷限,碼的兩兩距離難以縮短。

應用

已被LDPC Code取代。

Linear Cyclic Code

專著

《Coding Theory and Cryptography: The Essentials》

Linear Code

「線性碼」。合法的碼,任意倍率、任意相加,仍是合法的碼。

linear code | linear combination of codes is also code.
0000000     | 1000111 + 0100110 = 1100001
1000111     | 1000111 + 0100110 + 0010101 = 1110100
0100110     | 1000111 ⋅ 2 + 0100110 ⋅ 5 + 0010101 ⋅ 7 = 0110011
0010101     |         :
1100001     |         :
1110100     |         :
   :        |
0110011     |

運算符號的意義。

數字:餘數 (mod 2)  	數字:Boolean
加法:餘數加法      	加法:XOR
倍率:餘數乘法      	倍率:AND
(左右等價。教科書習慣採用左邊。)
(mod 2的情況下,倍率其實只有0和1。)

數學性質:Generator Matrix

generator   data   code
matrix      word   word
[ 1 0 0 0 ]        [c₀]
[ 0 1 0 0 ] [w₀]   [c₁]
[ 0 0 1 0 ] [w₁]   [c₂]
[ 0 0 0 1 ] [w₂] = [c₃]
[ 1 1 1 0 ] [w₃]   [c₄]
[ 1 1 0 1 ]        [c₅]
[ 1 0 1 1 ]        [c₆]
     G       w   =  c

線性碼=線性函數的輸出集合(image)。

Generator Matrix用來編碼。

直條:資料視作權重,各種加權總和得到各種碼。

橫條:從資料之中挑出特定欄位,相加後得到碼的特定欄位。

數學性質:Parity-check Matrix

parity-check    code   zeros
matrix          word
                [c₀]
                [c₁]
[1 1 1 0 1 0 0] [c₂]   [0]
[1 1 0 1 0 1 0] [c₃] = [0]
[1 0 1 1 0 0 1] [c₄]   [0]
                [c₅]
                [c₆]
       H         c   =  0

線性碼=線性函數的根集合(kernel)。

Parity-check Matrix用來偵測或者更正。

橫條:從資料之中挑出特定欄位,做一次parity檢查。

直條:用來判斷碼的兩兩距離。詳情請見Hamming Code。

顯然Hamming Code、LDPC code、Convolutional Code、Turbo Code都是一種Linear Code。

數學性質:Systematic Code

「系統碼」。資料後端添加parity形成碼。

碼的前段是資料,碼的後段是parity。彼此不相間。

系統碼很容易從碼之中擷取資料,無須複雜的計算過程。

systematic code       | non-systematic code
0000 -------> 0000000 | 0000 -------> 0000000
1111 -------> 1111111 | 1111 -------> 1111111
0011 -------> 0011110 | 0011 -------> 1110010
1010 -------> 1010010 | 1010 -------> 0110100

換句話說,Generator Matrix的上段是恆等矩陣I,Parity-check Matrix的右段是恆等矩陣I。

generator     parity-check
matrix        matrix
[ 1 0 0 0 ]
[ 0 1 0 0 ]
[ 0 0 1 0 ]
[ 0 0 0 1 ]   [ 1 1 1 0 | 1 0 0 ]
[—————————]   [ 1 1 0 1 | 0 1 0 ]
[ 1 1 1 0 ]   [ 1 0 1 1 | 0 0 1 ]
[ 1 1 0 1 ]
[ 1 0 1 1 ]
     G                 H

Generator Matrix與Parity-check Matrix的數學公式。

    [ I ]
G = [———]   H = [ -A | I ]   HG = 0
    [ A ]

Generator Matrix調動橫條順序,Parity-check Matrix調動直條順序,即得系統碼。詳情請見Hamming Code。

數學性質:Dual Code

線性碼、其「對偶碼」,各種配對的點積皆是零(互相垂直)。

linear code | dual code | dot product is zero
0000000     | 0000000   | 1000111 ∙ 0000000 = 0
1000111     | 1101010   | 1000111 ∙ 1101010 = 0
0100110     | 1011001   | 1000111 ∙ 1011001 = 0
0010101     |    :      | 0100110 ∙ 1101010 = 0
1100001     |    :      |         :
1110100     |           |         :
   :        |           |

換句話說,一組線性碼,對調其Parity-check Matrix和Generator Matrix,得到其對偶碼。即是「線性代數基本定理」。

Cyclic Code

「循環碼」。合法的碼,循環移位,仍是合法的碼。

cyclic code
0011010
0001101
1000110
0100011
1010001
1101000
0110100

循環碼=多項式。移位=乘x。循環移位=乘x減xᴺ加1。

最高位元可能是0,無數可減,改成「乘x模(xᴺ-1)」。

位元是餘數,改成「乘x (mod 2)xᴺ+1 (mod 2)」。

【註:高位數可以自由設定成左端或右端。此處是右端。】

0123456
———————
0011010 ---> x² + x³ + x⁵
0001101 ---> x³ + x⁴ + x⁶
1000110 ---> 1  + x⁴ + x⁵
0100011 ---> x  + x⁵ + x⁶
   :              :

線性碼變成矩陣運算,循環碼變成多項式運算。問題變成經典數學領域,容易分析問題、容易設計演算法。

Linear Cyclic Code

「線性循環碼」。既是線性碼、又是循環碼。

一、首先考慮循環碼。循環移位任意次數,都是碼。

xⁱg(x) (mod xᴺ+1)【方便起見省略(mod 2)】

二、追加考慮線性碼。任意倍率、任意相加,都是碼。

∑ wᵢxⁱg(x) (mod xᴺ+1)

三、提出g(x),再將∑ wᵢxⁱ改寫成w(x)。任意倍式,都是碼。

g(x)w(x) (mod xᴺ+1)

四、g(x)必須整除xᴺ+1,才會形成線性循環碼。

帶餘除法得到xᴺ+1 ≡ g(x)q(x) + r(x)。

xᴺ+1是碼,g(x)q(x)是碼,兩者相減而得的r(x)必須是碼。

因此r(x)恰是g(x)的某個倍數。顯然r(x) ≡ 0。得證。

五、xᴺ+1任選一個因式當作g(x),都能形成線性循環碼。

數學性質:xᴺ+1 (mod 2)質因式分解

 N | factorization of xᴺ + 1 (mod 2)
———+————————————————————————————————————
 1 | 1 + x
 3 | (1 + x)(1 + x + x²)
 5 | (1 + x)(1 + x + x² + x³ + x⁴)
 7 | (1 + x)(1 + x + x³)(1 + x² + x³)
 9 | (1 + x)(1 + x + x²)(1 + x³ + x⁶)
11 | (1 + x)(1 + x + x² + ... + x¹⁰)
13 | (1 + x)(1 + x + x² + ... + x¹²)
15 | (1 + x)(1 + x + x²)(1 + x + x² + x³ + x⁴)
   | (1 + x + x⁴)(1 + x³ + x⁴)
17 | (1 + x)(1 + x + x² + x⁴ + x⁶ + x⁷ + x⁸)
   | (1 + x³ + x⁴ + x⁵ + x⁸)
19 | (1 + x)(1 + x + x² + ... + x¹⁸)
21 | (1 + x)(1 + x + x²)(1 + x² + x³)(1 + x + x³)
   | (1 + x² + x⁴ + x⁵ + x⁶)(1 + x + x² + x⁴ + x⁶)
23 | (1 + x)(1 + x + x⁵ + x⁶ + x⁷ + x⁹ + x¹¹)
   | (1 + x² + x⁴ + x⁵ + x⁶ + x¹⁰ + x¹¹)
25 | (1 + x)(1 + x + x² + x³ + x⁴)(1 + x⁵ + x¹⁰ + x¹⁵ + x²⁰)
27 | (1 + x)(1 + x + x²)(1 + x³ + x⁶)(1 + x⁹ + x¹⁸)
29 | (1 + x)(1 + x + x² + ... + x²⁸)
31 | (1 + x)(1 + x² + x⁵)(1 + x³ + x⁵)
   | (1 + x + x² + x³ + x⁵)(1 + x + x² + x⁴ + x⁵)
   | (1 + x + x³ + x⁴ + x⁵)(1 + x² + x³ + x⁴ + x⁵)

偶數次方則是套用x² + y² ≡ (x + y)² (mod 2)。

隨便抓幾個質因式,相乘之後得到因式。

數學性質:Generator Polynomial

Generator Polynomial用來編碼。

資料w(x),碼w(x)g(x)。

乘上g(x)可以想成是追加parity。

parity長度是deg(g),碼長度是N,資料長度是N - deg(g) = deg(w) + 1。當N是定值,若parity越長,則資料越短。

數學性質:Generator Matrix

直條是g(x) x¹g(x) x²g(x) ...。

碼是g(x) x¹g(x) x²g(x) ...的線性組合。

                                     [c₀]
                                     [c₁]
[  ╷      ╷      ╷      ╷   ] [w₀]   [c₂]
[x⁰g(x) x¹g(x) x²g(x) x³g(x)] [w₁] = [c₃]
[  ╵      ╵      ╵      ╵   ] [w₂]   [c₄]
                              [w₃]   [c₅]
                                     [c₆]
              G                w   =  c
[ g₀          ]        [c₀]
[ g₁ g₀       ] [w₀]   [c₁]
[ g₂ g₁ g₀    ] [w₁]   [c₂]
[ g₃ g₂ g₁ g₀ ] [w₂] = [c₃]   G的空白欄位是0
[    g₃ g₂ g₁ ] [w₃]   [c₄]   g(x) = g₀ + g₁x + g₂x² + g₃x³
[       g₃ g₂ ]        [c₅]
[          g₃ ]        [c₆]
       G         w   =  c

數學性質:Parity-check Polynomial

Parity-check Polynomial用來偵測或者更正。

h(x) = (xᴺ+1) / g(x)。

數學性質:Parity-check Matrix

橫條是h(x) = (xᴺ+1) / g(x)頭尾顛倒。

parity是rev(h(x)) x¹rev(h(x)) x²rev(h(x))...的各項。

                    [c₀]
                    [c₁]
[ — x⁰rev(h(x)) — ] [c₂]   [0]
[ — x¹rev(h(x)) — ] [c₃] = [0]
[ — x²rev(h(x)) — ] [c₄]   [0]
                    [c₅]
                    [c₆]
         H           c   =  0
                         [c₀]
                         [c₁]
[ h₄ h₃ h₂ h₁ h₀       ] [c₂]   [0]
[    h₄ h₃ h₂ h₁ h₀    ] [c₃] = [0]   H的空白欄位是0
[       h₄ h₃ h₂ h₁ h₀ ] [c₄]   [0]
                         [c₅]
                         [c₆]
           H              c   =  0
page 13-14
https://web.ntpu.edu.tw/~yshan/cyclic_code.pdf

數學性質:Systematic Code

Reed–Solomon Code(BCH View)

專著

《Coding Theory: Algorithms, Architectures and Applications》

Linear Cyclic Code引入Finite Field

請見本站文件「Finite Field」。

基本單元從GF(2)改成GF(2ʳ)。基本單元從1 bit改成r bits。

數學性質:有限體元素

一個有限體元素(GF(2ʳ))=一段二元碼(長度r)。

GF(2³)
element | binary
————————+———————
α₀      | 000
α₁      | 001
α₂      | 010
α₃      | 011
α₄      | 100
α₅      | 101
α₆      | 110
α₇      | 111

數學性質:有限體加法

有限體的本質是餘數多項式的餘數系統。

係數的模數是任意質數。指定一個質數(此處必須是2),以便進行有限體加法運算。

【註:高位數可以自由設定成左端或右端。此處是左端。】

GF(2³)
element | polynomial | binary
————————+————————————+———————
α₀      | 0          | 000
α₁      | 1          | 001
α₂      | x          | 010
α₃      | x + 1      | 011
α₄      | x²         | 100
α₅      | x² + 1     | 101
α₆      | x² + x     | 110
α₇      | x² + x + 1 | 111
  α₁ + α₅
≡ (1) + (x² + 1)
≡ x² + 2 
≡ x²              remember (mod 2)
≡ α₄

數學性質:有限體乘法

有限體的本質是餘數多項式的餘數系統。

整體的模式是任意質式(r次方)。指定一個質式(r次方),以便進行有限體乘法運算。

GF(2³), irreducible polynomial is x³ + x + 1 (mod 2).

element | polynomial | binary
————————+————————————+———————
α₀      | 0          | 000   
α₁      | 1          | 001   
α₂      | x          | 010   
α₃      | x + 1      | 011   
α₄      | x²         | 100   
α₅      | x² + 1     | 101   
α₆      | x² + x     | 110   
α₇      | x² + x + 1 | 111   
  α₂ × α₆
≡ (x) × (x² + x) 
≡ x³ + x²      
≡ x² + x + 1      remember (mod x³ + x + 1) and (mod 2)
≡ α₇

數學性質:利用生成元,構造有限體元素。

構造有限體元素,可以利用生成元。生成元的各種次方,得到每個有限體元素(除了0)。有限體乘法變得簡單。

GF(2³), irreducible polynomial is x³ + x + 1 (mod 2).
generator is x + 1 (mod 2).

element | polynomial            | binary
————————+———————————————————————+———————
g¹      | (x + 1)¹ ≡ x + 1      | 011
g²      | (x + 1)² ≡ x² + 1     | 101
g³      | (x + 1)³ ≡ x²         | 100
g⁴      | (x + 1)⁴ ≡ x² + x + 1 | 111
g⁵      | (x + 1)⁵ ≡ x          | 010
g⁶      | (x + 1)⁶ ≡ x² + x     | 110
g⁷ ≡ g⁰ | (x + 1)⁷ ≡ 1          | 001

數學性質:利用生成元x (mod 2),構造有限體元素。

整體的模式是任意質式(r次方)。質式可以是原多項式,使得x (mod 2)是生成元。有限體乘法變得更簡單。

GF(2³), irreducible polynomial is x³ + x + 1 (mod 2).
                                (primitive polynomial)
generator is x (mod 2).

element | polynomial      | binary
————————+—————————————————+———————
g¹      | x¹ ≡ x          | 010
g²      | x² ≡ x²         | 100
g³      | x³ ≡ x + 1      | 011
g⁴      | x⁴ ≡ x² + x     | 110
g⁵      | x⁵ ≡ x² + x + 1 | 111
g⁶      | x⁶ ≡ x² + 1     | 101
g⁷ ≡ g⁰ | x⁷ ≡ 1          | 001

數學性質:x^(2ʳ-1) - 1質因式分解

xᴺ - 1任選一個因式當作g(x),都能形成線性循環碼。

有限體恰巧有一道數學公式:x^(2ʳ-1) - 1質因式分解。

x^2ʳ     - x ≡ (x-0)(x-α₁)(x-α₂)...(x-α2ʳ-1)
x^(2ʳ-1) - 1 ≡      (x-α₁)(x-α₂)...(x-α2ʳ-1)
where GF(2ʳ) = { 0, α₁, α₂, ..., α2ʳ-1 }

每一個有限體元素恰好都出現一次(除了0)。

大家令N = 2ʳ-1。隨便抓幾個因式,都能當作g(x)。爽!

g(x) = (x-α₁)(x-α₃)(x-α₆)...

數學性質:x^(2ʳ-1) - 1質因式分解

事先找到生成元g,數學公式改寫如下。

x^2ʳ     - x ≡ (x-0)(x-g¹)(x-g²)...(x-g^(2ʳ-1))
x^(2ʳ-1) - 1 ≡      (x-g¹)(x-g²)...(x-g^(2ʳ-1))
where GF(2ʳ) = { 0, g¹, g², ..., g^(2ʳ-1) }

生成元g、多項式g(x),兩者代表不同事物。生成元x (mod 2)、多項式變數x,兩者代表不同事物。數學符號恰好一樣而已。

g(x) = (x-g⁰)(x-g³)(x-g⁴)...

數學性質:Generator Matrix

如舊。g(x)每增一項,w(x)則減一項。

碼有2ʳ-1個元素。parity每追加2個元素(2r個位元),資料則減少2個元素(2r個位元)。

[ g₀             ]        [c₀]
[ g₁ g₀          ] [w₀]   [c₁]
[ g₂ g₁ g₀       ] [w₁]   [c₂]
[    g₂ g₁ g₀    ] [w₂] = [c₃]   G的空白欄位是0
[       g₂ g₁ g₀ ] [w₃]   [c₄]   g(x) = g₀ + g₁x + g₂x²
[          g₂ g₁ ] [w₄]   [c₅]
[             g₂ ]        [c₆]
        G           w   =  c

實際範例。

g(x) = (x - g¹)(x - g²)
     = x² - (g¹ + g²)x + g³
     = g⁰x² + g⁴x + g³

dataword: 0,g⁰,g²,g³,0           隨便設定
codeword: 0,g³,g⁰,g⁰,g⁶,g³,0     手工計算,可能算錯

[ g³             ]        [0 ]
[ g⁴ g³          ] [0 ]   [g³]
[ g⁰ g⁴ g³       ] [g⁰]   [g⁰]
[    g⁰ g⁴ g³    ] [g²] = [g⁰]   G的空白欄位是0
[       g⁰ g⁴ g³ ] [g³]   [g⁶]
[          g⁰ g³ ] [0 ]   [g³]
[             g⁰ ]        [0 ]
        G           w   =  c
g(x) = (x - g¹)(x - g²)
     = x² - (g¹ + g²)x + g³
     = g⁰x² + g⁴x + g³
     = 001x² + 110x + 011

dataword: 000,001,100,011,000           請自行去掉逗點
codeword: 000,011,001,001,101,011,000

[ 011                 ]         [000]
[ 110 011             ] [000]   [011]
[ 001 110 011         ] [001]   [001]
[     001 110 011     ] [100] = [001]   G的空白欄位是000
[         001 110 011 ] [011]   [101]
[             001 110 ] [000]   [011]
[                 001 ]         [000]
           G              w   =   c

順帶一提,乘上x,不再是位移一個位元了,而是位移r個位元。「循環移位」的概念不太一樣了。

數學性質:Parity-check Matrix

如舊。

                         [c₀]
                         [c₁]
[ h₅ h₄ h₃ h₂ h₁ h₀    ] [c₂]   [0]
[    h₅ h₄ h₃ h₂ h₁ h₀ ] [c₃] = [0]   H的空白欄位是0
                         [c₄]
                         [c₅]
                         [c₆]
           H              c   =  0

實際範例就不給了。總之差不多。

數學性質:Annihilator Matrix
【尚無正式名稱。目前大家稱作Parity-check Matrix。】

g(x)只有一次方質因式,恰好擁有特殊數學性質。

首先簡單一點,令g(x) = (x-α)。

碼變成多項式c(x)。所有碼都是(x-α)的倍數。所有碼都有因式(x-α)。所有碼都有根α。所有碼滿足c(α) = 0。c(α) = c₀α⁰ + c₁α¹ + c₂α² + ... = 0。改寫成矩陣乘法,矩陣只有一個橫條。

                         [c₀]
                         [c₁]
                         [c₂]
[ α⁰ α¹ α² α³ α⁴ α⁵ α⁶ ] [c₃] = [0]
                         [c₄]
                         [c₅]
                         [c₆]
           A              c   =  0

令g(x) = (x-α₁)(x-α₂)...。

所有碼滿足c(α₁) = 0且c(α₂) = 0且...。追加橫條即可。

                                [c₀]
                                [c₁]
[ α₁⁰ α₁¹ α₁² α₁³ α₁⁴ α₁⁵ α₁⁶ ] [c₂]   [0]
[ α₂⁰ α₂¹ α₂² α₂³ α₂⁴ α₂⁵ α₂⁶ ] [c₃] = [0]
[  :   :   :   :   :   :   :  ] [c₄]   [:]
                                [c₅]
                                [c₆]
               A                 c   =  0

Annihilator Matrix與Parity-check Matrix完全等價,高斯消去法結果一致。【尚待確認】

Reed–Solomon Code

生成多項式g(x),設定t個根:生成元α = g的連續次方。

g(x) = (x-α⁰)(x-α¹)(x-α²)...(x-αᵗ⁻¹)

大家習慣從0次方開始。其實也可以從任意次方值開始。

g(x) = (x-αⁱ)(x-αⁱ⁺¹)...(x-αⁱ⁺ᴷ⁻¹)

α是生成元,確保每一種次方都是相異元素。

採用連續次方,原因是容易設計演算法、電路。

編碼

資料w(x),碼c(x) = w(x)g(x)。

乘上g(x)可以想成是追加parity。

所有的碼

窮舉w(x),那麼c(x) = w(x)g(x)即是所有碼。

c(x) = w(x)g(x)代入α⁰ α¹ α² ... αᵗ⁻¹都是零。

碼的兩兩距離

仿照Hamming Code,證明碼的兩兩距離皆大於等於t+1。

利用Annihilator Matrix得到所有碼。Annihilator Matrix恰是Vandermonde Matrix的子矩陣,其determinant有數學公式。

                                              [c₀]
[ (α⁰)⁰ (α⁰)¹ (α⁰)² (α⁰)³ (α⁰)⁴ (α⁰)⁵ (α⁰)⁶ ] [c₁]   [0]
[ (α¹)⁰ (α¹)¹ (α¹)² (α¹)³ (α¹)⁴ (α¹)⁵ (α¹)⁶ ] [c₂] = [0]
[ (α²)⁰ (α²)¹ (α²)² (α²)³ (α²)⁴ (α²)⁵ (α²)⁶ ] [c₃]   [0]
[   :                                  :    ] [c₄]   [:]
[(αᵗ⁻¹)⁰             ...             (αᵗ⁻¹)⁶] [c₅]   [0]
                                              [c₆]
                      A                        c   =  0

符號一覽表

r = length of binary presentation of finite field
q = alphabet size = 2^r
n = codeword length = q-1
k = dataword length = message length
t = syndrome number = root number of g(x) = n-k = m
d = minimum codeword distance = t+1
ν = error number ≤ ⌊(d-1)/2⌋ = ⌊t/2⌋

解碼(Peterson–Gorenstein–Zierler Decoder)

1. get t symdromes from codeword.
   (speedup: Horner's Rule O(nt) )
   (speedup: Multipoint Evaluation O(𝓜(n) + 𝓜(t)logt) )
2. get minimal polynomial of t syndromes.
   aka error locator polynomial with minimum errors.
   (speedup: Berlekamp–Massey Algorithm O(tν) )
   (speedup: Brent–Gustavson–Yun Algorithm O(𝓜(t)logν) )
3. find ν error locators from minimal polynomial Λ(x)
   by evaluating Λ(α-0) ... Λ(α-(n-1)) and taking the zeros.
   (speedup: Chien Search O(νn) )
   (speedup: Multipoint Evaluation O(𝓜(ν) + 𝓜(n)logn) )
4. find ν error magnitudes from ν error locators and t syndromes.
   (speedup: Forney Algorithm)
5. codeword -= error

實務上n t ν很小,導致每個步驟的第一個演算法優於第二個演算法。雖然時間複雜度較高,但是過程較短,況且可以平行計算。

設計Error Locator Polynomial,展開得到係數:根總和、根兩兩乘積和、根三三乘積和、……。形成Newton's Identity

實作細節請見恩智浦、德州儀器、英國廣播公司的技術報告。

解碼(FFT Decoder)

1. get t syndromes by n-point FFT of codeword.
   O(nlogn)
2. get minimal polynomial of t symdromes.
   O(tν)
3. get remaining (n-t) syndromes from minimal polynomial.
   O((n-t)ν)
4. get error by n-point IFFT of n syndromes.
   O(nlogn)
5. codeword -= error.
   O(n)

各個步驟所使用的運算:正向數論轉換、線性遞迴函數內插、線性遞迴函數求值、逆向數論轉換、多項式減法。演算法請見本站文件「Number Theoretic Transform」「Polynomial (Recurrence)」。

幹古

Reed–Solomon Code學習門檻很高。

舉例來說,知名的最短路徑演算法Dijkstra's Algorithm約有三階階梯:圖論元件(點、邊、權重、陣列或串列)、貪心策略(最短路徑開頭截下一段還是最短路徑)、紀錄路徑長度(陣列或堆積)。

相比之下,Reed–Solomon Code少說也有十階階梯。

本站收錄上千種演算法,相當變態。其中Reed–Solomon Code學習門檻位居第一,簡直變態到不行。因此我決定特地撰文介紹Reed–Solomon Code的先備知識,方便大家理解什麼是變態

Reed–Solomon Code的數字系統,不是整數,也不是餘數,而是「有限體」。「有限體運算」可以改寫成「餘數多項式運算」。「餘數多項式運算」是「餘數運算」和「多項式運算」兩者併用。餘數運算源自「整數運算」與「因數」與「質數」。多項式運算源自「數列運算」與「生成函數」。

電腦採用二進位。有限體習慣採用GF(2ⁿ)。「餘數多項式運算」習慣簡化成「位元運算」。

構造有限體元素,使用了「有限體的原多項式」,源自「餘數的原根(單位圓的單位根的次方循環)」,又源自「群的生成元」。

Reed–Solomon Code發展自Hamming Code和BCH Code。Hamming Code是一種Parity-check Code,等價於Linear Code,需要「線性代數」的知識。BCH Code同時是Linear Code和Cyclic Code,後者需要「位元」和「多項式」的知識。

Reed–Solomon Code原理是「多項式內插」。因此Annihilator Matrix恰是「內插矩陣Vandermonde Matrix」。x值設定成同一個數字的每一種次方,而且x值是有限體。因此Annihilator Matrix同時也是「傅立葉矩陣Fourier Matrix」。

Reed–Solomon Code編碼與解碼,包含「多項式的加減乘除、多點求值、最大公因數」、「線性遞迴函數的求值、內插」、「數列的數論轉換」。順帶一提,這些運算可以表示成「多項式形式」或「矩陣形式」,而教科書習慣採用「矩陣形式」。

我講完了。來個結語。雖然Reed–Solomon Code少說也有十階階梯,但是現實世界的事物更加複雜。比方來說,機車零件約一百種、汽車零件約一千種,維修製造車輛可是複雜多了。便利商店貨品品項至少一千種、大賣場至少一萬種,貨品進銷存可是複雜多了。十階階梯在現實世界只是小玩意兒,無非是熟不熟悉而已,不必自己嚇自己。所謂變態,其實只不過是這麼一回事。

編碼率

每追加2個元素(2r個位元),只能額外修正1個元素(r個位元)。

應用

雖然Reed–Solomon Code已經不敵後起之秀,諸如LDPC Code和Turbo Code,但是現今仍然可以見到實際應用,主要都是古代流傳至今的重要發明:光碟CD/DVD/BD、條碼QR Code、電話線上網ADSL/VDSL。

Bose–Chaudhuri–Hocquenghem Code

專著

《Error Correction Coding: Mathematical Methods and Algorithms》

Linear Cyclic Code引入Subfield

資料與碼的基本單元,改回GF(2),也就是1 bit。

Generator Polynomial,係數改回GF(2),變數仍是GF(2ʳ)。

目的是降低編碼率。

數學性質:x^(2ʳ-1) - 1質因式分解

數學公式不復存在。只能自行計算質因式了。

係數與變數不一致的多項式,其質因式(包含指定的根α)稱作最小多項式。

生成多項式,本來是質因式g(x) = (x-α),現在是最小多項式g(x) = mα(x)。

生成多項式,本來是質因式連乘積g(x) = (x-α₁)(x-α₂)...,現在是最小多項式的最小公倍式g(x) = lcm(mα₁(x), mα₂(x), ...)。

數學性質:Minimal Polynomial

請見本站文件「Finite Field」。

最小多項式是質因式,且包含指定的根α,根是GF(2ʳ)。

最小多項式通常需要額外補充其他的根,使得所有質因式展開之後,係數恰是GF(2)。

數學性質:Frobenius Endomorphism

係數是GF(2)的情況下,最小多項式,任意一個根,其平方也是根。

給定的根,不斷平方,就能找到每個根。

mα(x) = (x-α)(x-α²)(x-α⁴)(x-α⁸)...,直到根重覆之前。

數學性質:Minimal Polynomial演算法

GF(2⁴), irreducible polynomial is x⁴ + x + 1 (mod 2).
                                (primitive polynomial)
generator is x (mod 2).

element  | polynomial            | binary
—————————+———————————————————————+———————
g¹       | x¹  ≡ x               | 0010
g²       | x²  ≡ x²              | 0100
g³       | x³  ≡ x³              | 1000
g⁴       | x⁴  ≡ x + 1           | 0011
g⁵       | x⁵  ≡ x² + x          | 0110
g⁶       | x⁶  ≡ x³ + x²         | 1100
g⁷       | x⁷  ≡ x³ + x + 1      | 1011
g⁸       | x⁸  ≡ x² + 1          | 0101
g⁹       | x⁹  ≡ x³ + x          | 1010
g¹⁰      | x¹⁰ ≡ x² + x + 1      | 0111
g¹¹      | x¹¹ ≡ x³ + x² + x     | 1110
g¹²      | x¹² ≡ x³ + x² + x + 1 | 1111
g¹³      | x¹³ ≡ x³ + x² + 1     | 1101
g¹⁴      | x¹⁴ ≡ x³ + 1          | 1001
g¹⁵ ≡ g⁰ | x¹⁵ ≡ 1               | 0001

最小多項式的根,只有一種演算法:

給定的根,不斷平方,直到根重複。

find mg⁵(x)
g⁵   = 0110
g¹⁰  = 0111
g²⁰  = g⁵
=> mg⁵(x) = mg¹⁰(x) = (x - g⁵)(x - g¹⁰)
=> deg( mg⁵ ) = 2

最小多項式的係數,有兩種演算法:

一、質因式展開。時間複雜度是指數時間。

二、一次方程組求解。時間複雜度是多項式時間。

實務上根數量極少,時間複雜度缺乏討論意義。

assume mg⁵(x) = a₀ + a₁x + a₂x²
find a₀, a₁, a₂

mg⁵(g⁵) = 0
a₀   + a₁g⁵ + a₂g¹⁰ = 0
a₀g⁰ + a₁g⁵ + a₂g¹⁰ = 0
a₀0001 + a₁0110 + a₂0111 = 0000

{ 0a₀ + 0a₁ + 0a₂ = 0
{ 0a₀ + 1a₁ + 1a₂ = 0
{ 0a₀ + 1a₁ + 1a₂ = 0
{ 1a₀ + 0a₁ + 1a₂ = 0
=> a₀ = 1, a₁ = 1, a₂ = 1
=> mg⁵(x) = x² + x + 1

數學性質:Generator Matrix

矩陣元素、輸入、輸出,通通改回GF(2)。

GF(2)                           GF(2)  GF(2)
                                       [c₀]
                                       [c₁]
[   ╷      ╷      ╷      ╷    ] [w₀]   [c₂]
[ x⁰g(x) x¹g(x) x²g(x) x³g(x) ] [w₁] = [c₃]
[   ╵      ╵      ╵      ╵    ] [w₂]   [c₄]
                                [w₃]   [c₅]
                                       [c₆]
               G                 w   =  c

數學性質:Parity-check Matrix

只有輸入改回GF(2)。

GF(2ʳ)              GF(2)  GF(2ʳ)
                    [c₀]
                    [c₁]
[ — x⁰rev(h(x)) — ] [c₂]   [0]
[ — x¹rev(h(x)) — ] [c₃] = [0]
[ — x²rev(h(x)) — ] [c₄]   [0]
                    [c₅]
                    [c₆]
         H           c   =  0

數學性質:Annihilator Matrix
【尚無正式名稱。目前大家稱作Parity-check Matrix。】

只有輸入改回GF(2)。

g(x) = mα(x)

GF(2ʳ)                   GF(2)  GF(2ʳ)
                         [c₀]
                         [c₁]
                         [c₂]
[ α⁰ α¹ α² α³ α⁴ α⁵ α⁶ ] [c₃] = [0]
                         [c₄]
                         [c₅]
                         [c₆]
           A              c   =  0

g(x) = lcm( mα₁(x), mα₂(x), ... )

GF(2ʳ)                          GF(2)  GF(2ʳ)
                                [c₀]
                                [c₁]
[ α₁⁰ α₁¹ α₁² α₁³ α₁⁴ α₁⁵ α₁⁶ ] [c₂]   [0]
[ α₂⁰ α₂¹ α₂² α₂³ α₂⁴ α₂⁵ α₂⁶ ] [c₃] = [0]
[  :   :   :   :   :   :   :  ] [c₄]   [:]
                                [c₅]
                                [c₆]
               A                 c   =  0

Annihilator Matrix與Parity-check Matrix不再等價!

Annihilator Matrix的橫條數量,多於Parity-check Matrix的橫條數量。parity數量過剩!

當然啦,我們可以硬是將Annihilator Matrix作為Parity-check Matrix。g(x)就不再是原先那樣了,這套碼也不再是循環碼了。

Cyclic Hamming Code

生成多項式,設定1個根:生成元α = g。

g(x) = mα(x)

Annihilator Matrix恰好可以作為Parity-check Matrix。

GF(2ʳ)                   GF(2)  GF(2ʳ)
                         [c₀]
                         [c₁]
                         [c₂]
[ α⁰ α¹ α² α³ α⁴ α⁵ α⁶ ] [c₃] = [0]
                         [c₄]
                         [c₅]
                         [c₆]
           H              c   =  0

GF(2ʳ)直向展開成GF(2)。

GF(2)                    GF(2)  GF(2)
                         [c₀]
                         [c₁]
[ ╷  ╷  ╷  ╷  ╷  ╷  ╷  ] [c₂]   [╷]
[ α⁰ α¹ α² α³ α⁴ α⁵ α⁶ ] [c₃] = [0]
[ ╵  ╵  ╵  ╵  ╵  ╵  ╵  ] [c₄]   [╵]
                         [c₅]
                         [c₆]
           H              c   =  0

填入實際數值。

【註:高位數可以自由設定成上端或下端。此處是下端。】

GF(2)             GF(2)  GF(2)
                  [c₀]
                  [c₁]
[ 1 0 0 1 0 1 1 ] [c₂]   [0]
[ 0 1 0 1 1 1 0 ] [c₃] = [0]
[ 0 0 1 0 1 1 1 ] [c₄]   [0]
                  [c₅]
                  [c₆]
        H          c   =  0

Bose–Chaudhuri–Hocquenghem Code(BCH Code)

生成多項式g(x),設定2t個根:生成元α = g的連續次方。

g(x) = lcm( mα¹(x), mα²(x), mα³(x), ..., mα²ᵗ(x) )

根據Frobenius Endomorphism,偶數次方的最小多項式是重複的。捨棄偶數次方,保留奇數次方。剩下t個根。

g(x) = lcm( mα¹(x), mα³(x), mα⁵(x), ..., mα²ᵗ⁻¹(x) )

大家習慣從1次方開始。其實也可以從任意奇數次方值開始。

g(x) = lcm( mαⁱ(x), mαⁱ⁺²(x), ..., mαⁱ⁺²ᵗ⁻²(x) )

採用連續次方,原因是容易設計演算法、電路。

編碼

資料w(x),碼c(x) = w(x)g(x)。

乘上g(x)可以想成是追加parity。

所有的碼

窮舉w(x),那麼c(x) = w(x)g(x)即是所有碼。

c(x) = w(x)g(x)代入α¹ α² α³ ... α²ᵗ都是零。

碼的兩兩距離(BCH Bound)

如舊。證明碼的兩兩距離皆大於等於t+1。

GF(2)                                         GF(2)  GF(2)
[  ╷     ╷     ╷     ╷     ╷     ╷     ╷    ] [c₀]   [╷]
[ (α¹)⁰ (α¹)¹ (α¹)² (α¹)³ (α¹)⁴ (α¹)⁵ (α¹)⁶ ] [c₁]   [0]
[  ╵     ╵     ╵     ╵     ╵     ╵     ╵    ] [c₂]   [╵]
[  ╷     ╷     ╷     ╷     ╷     ╷     ╷    ] [c₃] = [╷]
[ (α²)⁰ (α²)¹ (α²)² (α²)³ (α²)⁴ (α²)⁵ (α²)⁶ ] [c₄]   [0]
[  ╵     ╵     ╵     ╵     ╵     ╵     ╵    ] [c₅]   [╵]
[  :     :     :     :     :     :     :    ] [c₆]   [:]
                     A                         c   =  0

根據Frobenius Endomorphism,刪除偶數次方。然並卵。

GF(2)                                         GF(2)  GF(2)
[  ╷     ╷     ╷     ╷     ╷     ╷     ╷    ] [c₀]   [╷]
[ (α¹)⁰ (α¹)¹ (α¹)² (α¹)³ (α¹)⁴ (α¹)⁵ (α¹)⁶ ] [c₁]   [0]
[  ╵     ╵     ╵     ╵     ╵     ╵     ╵    ] [c₂]   [╵]
[  ╷     ╷     ╷     ╷     ╷     ╷     ╷    ] [c₃] = [╷]
[ (α³)⁰ (α³)¹ (α³)² (α³)³ (α³)⁴ (α³)⁵ (α³)⁶ ] [c₄]   [0]
[  ╵     ╵     ╵     ╵     ╵     ╵     ╵    ] [c₅]   [╵]
[  :     :     :     :     :     :     :    ] [c₆]   [:]
                     A                         c   =  0

解碼(Peterson–Gorenstein–Zierler Decoder)

如舊。

編碼率

優於Reed–Solomon Code,劣於LDPC Code和Turbo Code。

應用

曾經用於電視訊號DVB-S1、DVB-T1、DVB-C1。仍然用於快閃記憶體NAND Flash。

Goppa Code

專著

《Error Correcting Codes and Finite Fields》

Linear Cyclic Code引入Elliptic Curve

有限體推廣成橢圓曲線。

Goppa Code(Algebraic Geometric Code)

目前沒有實際用處。而我也不打算弄懂。

應用

目前沒人使用的加密演算法McEliece Encryption,其原理包含了錯誤更正、使用了Generator Matrix。有人建議使用Goppa Code,而這是它唯一一次登場。

Reed–Solomon Code(Original View)

澄清聲明

這個版本與上個版本恰是Dual Code。有鑑於此,儘管原理完全不同,但是名稱保持相同。以致大家稱呼它的時候,還得加上「原著觀點」或「BCH觀點」。

編碼

資料視作輸出。事先約定N+K個輸入。前N個用來求得內插多項式;後K個用來求得K個輸出,作為parity。

輸入是原元素g的各種次方:g⁰ g¹ g² ... gᴺ⁺ᴷ⁻¹。事先約定一個數字g,就能求得N+K個輸入。同時也確保輸入不重複,確保內插多項式有唯一解。

碼的兩兩距離

抹消更正:已知損毀位置,計算損毀數值。追加K個parity能夠容忍K個錯誤數字。

錯誤更正:同時計算損毀位置暨損毀數值。不再保證追加K個parity能夠容忍K個錯誤數字。必須另闢蹊徑。

我們可以仿照Hamming Code,將所有的碼改寫成所有的解,以矩陣向量判斷碼的兩兩距離。很不幸的,我不會證明。

我只知道結論:碼長是N+K個數字,錯⌊(N+K)/2⌋個數字,仍可完全更正。【尚待確認】

解碼(Berlekamp–Welch Decoder)

n = codeword length
k = message length
t = parity number = root number of E(x) = n-k
d = minimum codeword distance = t+1
e = error number ≤ ⌊(d-1)/2⌋ = ⌊t/2⌋
1. assume there exists e errors in codeword (b₀b₁...bₙ₋₁).

   { bᵢ ≠ F(gⁱ)   if i is the error position
   { bᵢ = F(gⁱ)   if i is the correct position

2. revoke all error positions by E(gⁱ).

   bᵢ E(gⁱ) = F(gⁱ) E(gⁱ)   for i = 0 ... n-1

3. discrete indicator function E(gⁱ).

   E(gⁱ) = { 0   if bᵢ ≠ F(gⁱ)
           { 1   if bᵢ = F(gⁱ)     note: E(gⁱ) need not be 1

4. continuous polynomial function E(x) with degree e.

   E(x) = (x - gp₁)(x - gp₂)...(x - gpₑ)

   where p₁ ... pₑ are unknown error positions.

5. let Q(x) = F(x) E(x) is unknown polynomial function
                           with degree (k+e).
   bᵢ E(gⁱ) = Q(gⁱ)

6. solve linear equations.

   if solution is not unique, then e-- and try again.
   if e decreases to 0, then exit. (no error is detected.)

7. verify the solution.

   if Q(x) is not divided by E(x), then fail.

時間複雜度O(enn(k+2e)) = O(en³)。

解碼(Gao's Decoder)

時間複雜度O(𝓜(e)loge) = O(elog²e)。

Polar Code

專著

《Error Correction Coding: Mathematical Methods and Algorithms》

Polar Code

最後講個八卦

企業界制定5G標準,其中Huawei公司強勢支持Polar Code,使得Polar Code異軍突起,最終成為標準的一小部分。這是Polar Code唯一一個實際應用。

背後動機應該是「Taiwan Can Help」、「讓世界看見台灣」、「護國神山」、「矽盾」諸如此類的理由。