error detection

error detection

「錯誤偵測」。判斷資料是否損毀變異。

channel

天有不測風雲,人有旦夕禍福。

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

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

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

encode / decode

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

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

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

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

checksum

以指數指標偵測錯誤

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

資料:時今
筆劃:14

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

checksum

以雜湊值偵測錯誤。

編碼:資料代入雜湊函數,得到雜湊值,添在資料尾端。

偵測:資料代入雜湊函數,得到雜湊值,檢查是否相符。

仿照字串搜尋「Karp–Rabin algorithm」。

Luhn algorithm

Hill code

雜湊函數是一次函數。

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

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

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

仿照「Hill cipher」。

Damm algorithm

cyclic redundancy check

以餘數偵測錯誤

資料視作被除數,自行挑選除數,求得餘數,添在資料尾端。

parity check:除數是2。
cyclic redundancy check:除數是自訂數字。

parity check

奇偶檢查。計算資料有幾個位元1。資料尾端添上一個位元,偶數添0、奇數添1,使得碼有偶數個位元1。

編碼:資料所有位元XOR(求和、模2),得到一個位元(稱作parity),添在資料尾端。

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)

偵測:碼所有位元XOR,等於0則對,等於1則錯。

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) ✖

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

UVa 541

cyclic redundancy check(CRC)

資料視作餘數多項式。係數模2。

11100010 ←—→ x⁷ + x⁶ + x⁵ + x (mod 2)

事先約定一個除數。

11000101 ←—→ x⁷ + x⁶ + x² + 1 (mod 2)

編碼:資料尾端補零(向左移位),數量是除數長度減一,以便置放餘數。

11100010 ---> 111000100010111
111000100000000 ÷ 11000101 ≡ 10111011 ... 0010111 (mod 2)

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

111000100010111 ÷ 11000101 ≡ 0 (mod 2) ✔

錯誤位元數量,少於除數長度,則保證正確偵測錯誤。

UVa 128

erasure correction

erasure correction

「抹消更正」。已知損毀變異的地方,嘗試修復資料。

checksum

以指數指標修復錯誤

我不確定是否有這種東西。

關鍵字可能是homomorphic hashing。

cyclic redundancy check

以餘數修復錯誤

看看損毀變異的地方,應該改成多少數字,才能整除。

parity check

更正:碼所有正確位元XOR,得到一個位元,作為損毀位元。

00110001 ---> 10110001
0+1+1+0+0+0+1 ≡ 1 (mod 2) 
10101001 ---> 10101001
1+0+1+0+1+0+1 ≡ 0 (mod 2)

損毀位元數量,少於2個,則保證正確修復錯誤。

cyclic redundancy check(CRC)

更正:化作一次方程組求解。

損毀位元數量,少於除數長度,則保證正確修復錯誤。

raptor code

fountain code

Luby transform code

tornado code

raptor code

Reed–Solomon code

以多項式內插修復錯誤

函數。N個輸入,作為資料。N個輸出,作為碼。

多項式函數。N個輸入,作為資料。N個輸出,作為碼。

多項式函數。N個係數,作為資料。N個輸出,作為碼。

編碼:多項式求值。指定N個輸入,計算N個輸出。

解碼:多項式內插。N個輸入、N個輸出,計算N個係數。

追加K個輸入,用來容錯。計算N+K個輸出,作為碼。

解碼:尚未損毀變異的地方,挑出N個輸出,輔以N個輸入,實施多項式內插,得到N個係數,成功還原資料。

錯誤數量小於等於K個,則保證正確修復錯誤。

unisolvence theorem

多項式函數:考慮N-1次多項式,總共N個係數。

唯一解定理:隨意選定N個輸入(不可重複)。N個係數、N個輸出,形成一對一轉換!

詳情請見本站文件「polynomial interpolation」。

finite field

實數改成有限體,唯一解定理依然成立。【尚待確認】

電腦採用二進位,有限體適合採用GF(2ⁿ)。

如此一來,係數、輸入、輸出,都是二元碼了。

詳情請見本站文件「finite field」。

generator

輸入設定成原元素g的各種次方:g⁰ g¹ g² ... gᴺ⁺ᴷ⁻¹。

如此一來,只需事先約定一個數字g,就能求得N+K個輸入,同時確保輸入不重複。

如此一來,編碼就是傅立葉轉換了。

詳情請見本站文件「Fourier transform」。

Reed–Solomon code原始版本

資料視作係數。事先約定N+K個輸入,代入多項式,求得N+K個輸出,作為碼。

缺點是資料產生變換。無人使用此方法。

Reed–Solomon code現行版本

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