今天碼哥給大家?guī)硪环N數(shù)據(jù)備份與修復(fù)的技術(shù)——里德所羅門編碼。
里德所羅門編碼可是應(yīng)用場(chǎng)景很多，例如我們耳熟能詳?shù)腞AID（磁盤陣列），又例如在UDP傳輸中降低丟包導(dǎo)致的數(shù)據(jù)缺失的情況等等。
什么是里德所羅門編碼
這里，先要介紹一種糾錯(cuò)方法——極大距離可分法（MDS）。這是一種很常見的糾錯(cuò)方法，它將原始數(shù)據(jù)分成等長(zhǎng)的N份，并根據(jù)這N份數(shù)據(jù)生成M個(gè)冗余的校驗(yàn)數(shù)據(jù)。此時(shí)，M+N塊數(shù)據(jù)中任意M塊數(shù)據(jù)損失，也可以通過剩余N塊數(shù)據(jù)經(jīng)過計(jì)算來恢復(fù)原始數(shù)據(jù)。
里德所羅門糾錯(cuò)算法就是經(jīng)典的MDS算法。
里德所羅門編碼的理論基礎(chǔ)
- 范德蒙矩陣
- 有限域算法
- 伽羅華域
這里我們那先不過多解釋，大家先對(duì)矩陣型形式混個(gè)臉熟，至于伽羅華域我們后面會(huì)說到。
里德所羅門編碼的原理
在開始前，我們不得不引入一個(gè)數(shù)學(xué)問題——插值問題。
在一些工程實(shí)踐中，某些變量間是存在函數(shù)關(guān)系的，但通常不能用公式表示，只能用實(shí)驗(yàn)觀測(cè)得到y(tǒng)=f(x)，即一系列xi在函數(shù)上的值。有些公式非常復(fù)雜，計(jì)算其完整公式并不劃算，因此我們希望用另一個(gè)函數(shù)p(x)來嘗試逼近f(x)。
此時(shí)，假設(shè)在二維空間中有n個(gè)點(diǎn)，(x1, y1), (x2, y2), …, (xn, yn)，希望得到一個(gè)多項(xiàng)式的解：
這個(gè)多項(xiàng)式可以滿足我們的當(dāng)前條件：
實(shí)際上，可以推演如下：
可以看到矩陣A即為范德蒙矩陣，而如果每個(gè)點(diǎn)的x值互不相同，那么范德蒙矩陣的行列式值必不為零（略過證明），那么矩陣A就存在逆矩陣。
由此，我們那可以看到，通過對(duì)插值問題的討論，我們發(fā)現(xiàn)了一種數(shù)據(jù)恢復(fù)方式，即：
矩陣A * 矩陣B = 矩陣Y
矩陣A的你矩陣 * 矩陣Y = 矩陣B
下面，我們來說一下在里德所羅門編碼中如何進(jìn)行的編解碼的。
例如，我有兩段數(shù)據(jù)：
data = [
[1,2,3,4],
[5,6,7,8]
]
下面是構(gòu)建系數(shù)矩陣A，A的構(gòu)建方式是，上方為一單位矩陣，下方是范德蒙矩陣，且：
- 單位矩陣的行數(shù)與數(shù)據(jù)矩陣的行數(shù)一致，本例中為兩行。
- 范德蒙矩陣的行數(shù)與冗余數(shù)據(jù)個(gè)數(shù)保持一致，本例中為一行。并且每行中的ai為前一行的值加1，首行的a1為1。
那么構(gòu)建出的系數(shù)矩陣A為：
A = [
[1, 0],
[0, 1],
[1, 1]
]
編碼即為矩陣乘法，得到的結(jié)果為：
result = data * A = [
[1,2,3,4],
[5,6,7,8],
[6,8,10,12]
]
可以看到，前兩行與原始數(shù)據(jù)一樣，最后一行則是冗余數(shù)據(jù)。
下面，我們來模擬解碼過程，假設(shè)我們丟失了第二個(gè)數(shù)據(jù)[5,6,7,8]，那么恢復(fù)過程如下：
首先，構(gòu)建系數(shù)矩陣A'：
A' = [
[1, 0],
[1, 1]
]
可以看到，我們跳過了[0, 1]，是因?yàn)樵撔袑?duì)應(yīng)的數(shù)據(jù)丟失了，因此構(gòu)建時(shí)也要相應(yīng)去掉。
然后我們要對(duì)A'求逆，得到A''：
A'' = [
[1, 0],
[-1, 1]
]
最后，利用矩陣乘法恢復(fù)原始數(shù)據(jù)：
data = A'' * B = [
[1,2,3,4],
[5,6,7,8]
]
到此，似乎已經(jīng)完成了數(shù)據(jù)丟失后的恢復(fù)，但細(xì)心的讀者可能發(fā)現(xiàn)了，在計(jì)算逆矩陣的時(shí)候可能會(huì)存在小數(shù)，會(huì)造成精度損失，因此，恢復(fù)后的數(shù)據(jù)會(huì)和原始數(shù)據(jù)不一致。
這就是我們接下來要介紹的，數(shù)域的作用。
伽羅華域
為了避免矩陣運(yùn)算中出現(xiàn)小數(shù)導(dǎo)致的精度損失，我們要將整個(gè)矩陣運(yùn)算從實(shí)數(shù)域遷移到伽羅華域中。
伽羅華域是一種有限數(shù)域，其值范圍為[0, 2^8-1]，即0~255。
那么如何進(jìn)行遷移呢？答案很簡(jiǎn)單，我們將矩陣中用到的加減乘除四則運(yùn)算進(jìn)行一些變換。
在伽羅華域中：
- 加法 a + b：被轉(zhuǎn)換為實(shí)數(shù)域內(nèi)的異或運(yùn)算，即 a ^ b。
- 減法 a - b：同樣是異或運(yùn)算 a ^ b。
- 乘法 a * b：ilog((log(a)+log(b))%255)，其中ilog為反對(duì)數(shù)運(yùn)算，log為對(duì)數(shù)運(yùn)算。伽羅華域上的對(duì)數(shù)與反對(duì)數(shù)運(yùn)算結(jié)果在網(wǎng)上是有歸納總結(jié)的，可以直接查表獲取，因此運(yùn)算速度會(huì)非常快。
- 除法 a / b：如果a小于b，則結(jié)果為 c = ilog(255 - log(a) - log(b))；否則，c = ilog(log(a) - log(b))。
由于本篇為純理論類文章，涉及較多數(shù)學(xué)概念，如有紕漏還望告知，感謝您的觀看！
