Error Correction

Error Detection / Error Correction

「錯誤偵測」和「錯誤更正」。偵測較簡單,更正較複雜。

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

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

Channel

天有不測風雲,人有旦夕禍福。資料損毀變異怎麼辦?

電腦世界當中,資料通常是經過傳輸而損毀。於是數學家想像有一個「通道」,宛如函數,一筆資料經過通道得到一筆資料,可能不變,可能出錯。

數學家引入機率的概念、引入遞增法化整為零的概念,令每一個位元有固定機率出錯。現實生活有著千奇百怪的出錯原因;數學家便設計了各式各樣的通道,儘量符合現實情況。

以下文章不談通道,讓事情單純一點!

Encode / Decode

不像壓縮與加密特別訂立新名詞,更正直接沿用舊名詞。

「編碼」是資料變碼。「解碼」是碼變資料。碼經過「通道」將有一定機率損毀變異。

「編碼」是補強資料。「解碼」是復原資料。

         encode
0010001 -------> 001000100100010010001
                           ↓ channel
0010001 <------- 001100110100010010000
         decode
    (detect/correct)

Repetition Code

以重複備份偵測錯誤、更正錯誤

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

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

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

前面假設備份資料絕對沒問題。如果備份資料可能有問題呢?

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

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

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

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

如果需要更細膩的結論,可以引入機率:設定毀損機率、計算修復機率。

Repetition Code

00110001 ---> 001100010011000100110001

電腦世界也有類似的演算法:原始資料重複數次。

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

電腦以位元為單位。針對一個特定位元,只要所有對應的位元,正確比錯誤多,即可正確地偵測錯誤、更正錯誤。

此演算法相當耗費記憶體空間、耗費處理時間。因此有人研發更好的演算法。

如果需要更細膩的結論,可以引入「通道」:設定毀損機率、計算修復機率。

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

Hadamard Code

以最短距離來偵測錯誤、更正錯誤

資料長度為N個位元。一共2ᴺ種資料。

碼長度為N+K個位元。N+K維空間,挑選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]      

碼之間的距離越遠,容忍越多錯誤!令碼的兩兩距離皆大於等於d,中點為分野,當d是偶數、奇數,即便錯d/2、(d-1)/2個位元,仍可正確偵測;即便錯d/2-1、(d-1)/2個位元,仍可完全修復。如果錯太多,就誤判了。

挑選2ᴺ個點座標,只要令兩兩距離大於等於d,就能容忍將近d/2個錯誤位元,正確偵測、完全修復!

增加碼長度(空間維度),得拉開兩兩距離、增加d、調整d、調整容忍程度。代價是碼變長,耗費記憶體空間、耗費處理時間。

編碼:建立表格,2^N種資料對應到2^N個點座標。
解碼:窮舉2^N個點座標,找到Hamming距離最小者。

Hadamard Code

利用「Hadamard Matrix」,N個向量當作碼,兩兩距離皆大於等於N/2。證明交給讀者。

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]

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

引入線性組合的概念,找到這些向量的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]

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

矩陣 | 碼  | 基底 | 資料 | 碼  | 兩兩   | 偵測 | 更正 | 編碼率
大小 | 數量 | 向量 | 長度 | 長度 | 距離   | 錯誤 | 錯誤 | 資料與碼的比例
-----|------|------|------|------|--------|------|------|---------------
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

實務上N都很小,因此不必研發特別的解碼演算法。解碼採用試誤法,簡單而迅速。

編碼:預先建立所有碼的basis。資料經過線性組合得到碼。
解碼:窮舉所有資料並且求得碼,找到Hamming距離最小者。
   一旦發現Hamming距離小於N/2,即可立即結束,推定為正解。

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

Reed-Muller Code

http://homepages.math.uic.edu/~leon/mcs425-s08/handouts/Hadamard_codes.pdf

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

Hill Code

以指數指標偵測錯誤

設立指數指標,判斷指數指標是否一致。

資料:時今
筆劃:14

資料:時令
筆劃不同,發現錯誤

Checksum

https://en.wikipedia.org/wiki/Checksum

仿照字串搜尋「Karp-Rabin Algorithm」,資料視作數列,以雜湊值偵測錯誤。

Hill Code

仿照「Hill Cipher」。雜湊函數是線性函數。

資料長度n。挑選n個權重,形成1個加權平均數。挑選m組權重,形成m個加權平均數,併成雜湊值。雜湊值長度m。

一種方便的設置:挑選一組權重a₁ a₂ ... aₙ。權重分別1次方、2次方、...、m次方,得到m組權重。

一種方便的設置:建立大矩陣,從中挑選一個m×n子矩陣。

Damm Algorithm

https://en.wikipedia.org/wiki/Damm_algorithm

Hamming Code

以前後文偵測錯誤、更正錯誤

最簡單的方法:原始資料直接重複好幾次。更聰明的方法:補充說明,依照前後文推敲正文。

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

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

Parity Check

電腦世界當中,由於物理電子電機已臻化境,網路線傳輸、無線傳輸、USB傳輸、燒錄光碟、讀取光碟,資料毀損機率極低,只需容忍很少的錯誤位元。因此有人研發容忍程度極低、卻非常節省空間時間的演算法。接下來介紹僅容忍一個錯誤位元的演算法,只能偵測錯誤,無法更正錯誤。

00110001 ---> 001100011
0+0+1+1+0+0+0+1 = 1 (mod 2)

10101001 ---> 101010010
1+0+1+0+1+0+0+1 = 0 (mod 2)
001100011 ✔
0+0+1+1+0+0+0+1+1 = 0 (mod 2)

101011010 ✖
1+0+1+0+1+1+0+1+0 = 1 (mod 2)
編碼:資料所有位元xor(先求和、再模二),
   得到一個位元(稱作parity),添在資料尾端。
偵測:碼所有位元xor,等於0則對,等於1則錯。

錯零個位元、錯一個位元,保證正確偵測錯誤;錯兩個位元以上,不保證正確偵測錯誤。無法更正錯誤。

最後附上一個益智問題:

陣列裡放入 1 到 100 的正整數,但是少了一個。請找出少了哪一個?
使用 Counting Sort ,時間複雜度極低,但是空間複雜度極高。
有沒有更節省記憶體的方法呢?

UVa 541

Hamming Code:編碼

接下來介紹僅容忍一個錯誤位元的演算法,可以更正錯誤。

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

寫成代數式子:

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

範例:

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

Hamming Code:所有的碼

從屬關係改成平等關係。

{ 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

Hamming Code:碼的兩兩距離

一、碼=解。

                [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個位元,仍可完全修復。

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

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

Hamming Code:解碼

試誤法是窮舉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的向量,則錯誤;錯誤位元編號即是向量編號。

硬體設備已經內建Hamming Code的電路,其實沒有必要用程式語言實作。

Hamming Code:其他性質

畫成圖論的二分圖(Bipartite Graph)。

畫成集合論的文氏圖(Venn Diagram)。

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

                [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(LDPC 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

表示成二分圖。

解碼。自由設計之後,缺乏數學性質。求最佳解是NP-hard問題,只好求近似解。其中一種演算法:Belief Propagation Decoding,採用Iterative Method,用二分圖的一側算出另一側,兩側交替計算,直到收斂為止。有興趣的讀者請自行研究。

LDPC Code是當前「資料與碼的比例」最高的演算法,節省空間與時間,非常實用!例如無線通訊Wi-Fi (IEEE 802.11)、WiMAX (IEEE 802.16)就有使用。

由於硬體設備已經內建LDPC Code的電路,其實沒有必要用程式語言實作。

Reed-Solomon Code(Under Construction!)

以餘數偵測錯誤、更正錯誤

資料視作被除數,再挑選一個除數,求得餘數,作為parity。

方便起見,資料視作二進位數字,每個位數模2,只有0和1,如此一來餘數也只有0和1。

數學術語是GF(2ⁿ),n是二進位數字長度。請見本站文件「Finite Field」。

GF(2ⁿ)當中,每個位數獨立運作,不存在進位借位。每個位數只有0和1,加法等同減法、又等同XOR。

GF(2ⁿ)當中,二進位數字可以改寫成餘數多項式,模數是2。

Cyclic Redundancy Check(CRC)

資料看作餘數多項式,係數模二。

11100010 ⟷ x⁷ + x⁶ + x⁵ + x (mod 2)

事先約定一個除數。

11000101 ⟷ x⁷ + x⁶ + x² + 1 (mod 2)

編碼:資料尾端補零,數量是除數長度減一,以便置放餘數。實施長除法。餘數當作parity,添在原始資料尾端。

111000100000000 ÷ 11000101 = 10111011 ... 0010111 (mod 2)

11100010 ---> 111000100010111
111000100000000
11000101        1
--------------- 
 01001110       
 00000000       0
--------------- 
  10011100      
  11000101      1
--------------- 
   10110010     
   11000101     1
--------------- 
    11101110    
    11000101    1
--------------- 
     01010110   
     00000000   0
--------------- 
      10101100  
      11000101  1
--------------- 
       11010010 
       11000101 1
--------------- 
        0010111

偵測:碼除以除數。整除即正確,不整除即錯誤。

111000100010111 ÷ 11000101 = 0 ✔

UVa 128

Reed-Solomon Code(RS Code)

過時的老方法。解碼演算法相當複雜,我沒有完全弄懂。

實作細節請見恩智浦、德州儀器的技術報告。

https://www.nxp.com/docs/en/application-note/AN2407.pdf

https://www.ti.com/litv/pdf/spra686

理論概述請見英國廣播公司的技術報告、課程講義、維基百科。

https://www.bbc.co.uk/rd/publications/whitepaper031

https://www.cse.iitk.ac.in/users/manindra/CS681/index.html

https://en.wikipedia.org/wiki/Reed–Solomon_error_correction

歷史典故請見維基百科。

https://en.bitcoinwiki.org/wiki/Berlekamp–Welch_algorithm

Reed-Solomon Code:編碼

多項式函數的唯一解定理:N個係數、N個函數值,當x皆相異,是一對一轉換!

方法一、資料視作係數:事先約定N+K個x值,代入多項式,求得N+K個函數值,作為碼。

方法二、資料視作函數值:事先約定N+K個x值。前N個用來求得內插多項式;後K個用來求得K個函數值,作為parity。

x值習慣設定成α¹ α² ... αᴺ⁺ᴷ,α是原根。如此一來只需約定一個數字α,除此之外又能確保x皆相異。

方法一的缺點是資料轉換了、無法識別了。大家採用方法二。

Reed-Solomon Code:所有的碼

以方法一為例。

[(α¹)⁰ (α¹)¹ (α¹)² (α¹)³ ]        [x₀]
[(α²)⁰ (α²)¹ (α²)² (α²)³ ]        [x₁]
[(α³)⁰ (α³)¹ (α³)² (α³)³ ] [v₀]   [x₂]
[(α⁴)⁰ (α⁴)¹ (α⁴)² (α⁴)³ ] [v₁] = [x₃]
[(α⁵)⁰ (α⁵)¹ (α⁵)² (α⁵)³ ] [v₂]   [x₄]
[(α⁶)⁰ (α⁶)¹ (α⁶)² (α⁶)³ ] [v₃]   [x₅]
[(α⁷)⁰ (α⁷)¹ (α⁷)² (α⁷)³ ]        [x₆]
            G               v   =  x

Reed-Solomon Code:碼的兩兩距離

K+1。

Reed-Solomon Code:解碼

四個步驟。兩種error locator polynomial。

https://en.wikipedia.org/wiki/Vieta's_formulas

Bose-Chaudhuri-Hochquenghem Code(BCH Code)

http://www.seanerikoconnor.freeservers.com/Mathematics/AbstractAlgebra/PrimitivePolynomials/theory.html

被發現跟Reed-Solomon Code等價。

g(x) = (x-α¹)(x-α²)(x-α³)...(x-αᴷ),α是原根。(甚至可以改成從任意次方值開始遞增。)

g(x)的所有倍率,s⋅g(x),即是所有碼。

s⋅g(x)代入α¹ α² ... αᴷ都是零。

                                            [x₀]
                                            [x₁]
[(α¹)¹ (α¹)² (α¹)³ (α¹)⁴ (α¹)⁵ (α¹)⁶ (α¹)⁷] [x₂]   [0]
[(α²)¹ (α²)² (α²)³ (α²)⁴ (α²)⁵ (α²)⁶ (α²)⁷] [x₃] = [0]
[(α³)¹ (α³)² (α³)³ (α³)⁴ (α³)⁵ (α³)⁶ (α³)⁷] [x₄]   [0]
                                            [x₅]
                                            [x₆]
                    H                        x   =  0

Algebraic Geometry Code

Algebraic Geometric Code(Goppa Code)

專著《Error Correction Coding: Mathematical Methods and Algorithms》

Turbo Code(Under Construction!)

Convolution Code

「卷積碼」。資料視作數列,以多個濾波器編碼。

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

解碼,即是找到最好的路徑,Viterbi Algorithm。有人把動態規劃的過程圖,叫做Trellis Diagram。

Turbo Code

專著《Error Correction Coding: Mathematical Methods and Algorithms》

Polar Code

Polar Code

專著《Error Correction Coding: Mathematical Methods and Algorithms》

Type of Error Correcting Code(Under Construction!)

Maximum Distance Separable Code

「最大距離分離碼」。合法的碼,q進位,長度N,最小距離d,數量等於qᴺ⁻ᵈ⁺¹。

https://en.wikipedia.org/wiki/Singleton_bound

例如RS Code。

Systematic Code

「系統碼」。添加Parity的碼。

例如Hamming Code、RS Code。

Polynomial Code

「多項式碼」。合法的碼,都是某個多項式的各種倍率。

例如RS Code。

Linear Code

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

一種構造方式:線性方程組的kernel(根集合)。parity check matrix。

一種構造方式:線性方程組的image(函數值集合)。generator matrix。

例如Hamming Code、RS Code。

Cyclic Code

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

一種構造方式:線性循環碼。

令g(x)整除(xᴺ-1)。g(x)的所有倍率,s⋅g(x),即是所有碼。

例如CRC、RS Code。

Block Code

「區塊碼」。資料分段編碼。

例如Hamming Code、RS Code。

Erasure Correction

Erasure Correction

「抹消更正」。

Fountain Code

Fountain Code

http://en.wikipedia.org/wiki/Fountain_code

https://en.wikipedia.org/wiki/Luby_transform_code

Tornado Code

Tornado Code

https://en.wikipedia.org/wiki/Tornado_code

https://en.wikipedia.org/wiki/Raptor_code