FEC 前向差錯(cuò)恢復(fù)編碼
FEC 是一種前向差錯(cuò)恢復(fù)編碼技術(shù)，是通過(guò)對(duì)原生信息序列進(jìn)行編碼生成監(jiān)督碼，這些監(jiān)督碼作為冗余信息序列與原生信息序列一起被傳輸，當(dāng)原生信息序列發(fā)生錯(cuò)誤或丟失，可通過(guò)冗余信息序列以一定能力恢復(fù)原生信息序列。
對(duì)于生成的冗余數(shù)據(jù)，我們希望生成數(shù)據(jù)大小范圍與原生數(shù)據(jù)一致，以免使用更多冗余來(lái)表示，比如在計(jì)算機(jī)中，以一個(gè)字節(jié)單位的數(shù)據(jù)來(lái)生成的編碼數(shù)據(jù)我們不希望是個(gè)兩個(gè)字節(jié)或更大數(shù)據(jù)。因此，編碼通常利用了有限域的數(shù)學(xué)方法，在有限域中進(jìn)行四則運(yùn)算，使得編碼后的數(shù)據(jù)還是在一樣的大小范圍內(nèi)。
伽羅瓦域（galois field）
域是一個(gè)可以在其上進(jìn)行加法、減法、乘法和除法運(yùn)算而結(jié)果不會(huì)超出域的集合。如果域F只包含有限個(gè)元素，則稱其為有限域。有限域亦稱伽羅瓦域（galois field），它是伽羅瓦(Galois,E.)于18世紀(jì)30年代研究代數(shù)方程根式求解問(wèn)題時(shí)引出的。
伽羅瓦域的階（元素個(gè)數(shù)）必為素?cái)?shù)的冪，即有限域的階可表示為pn（p是素?cái)?shù)、n是正整數(shù)），記為GF(pn)。計(jì)算機(jī)應(yīng)用一般取 p=2 來(lái)計(jì)算二進(jìn)制運(yùn)算。
GF(pn) 中有 pn個(gè)元素，除了 0，1 之外的元素由本原多項(xiàng)式 P(x)生成。本原多項(xiàng)式（primitive polynomial）是一個(gè)不可約多項(xiàng)式，不能夠進(jìn)行因子分解，它 只能整除x2n?1+1 , 而不能整除其他xJ?1+1, 其中 J<(2n?1) 。當(dāng)一個(gè)域上的本原多項(xiàng)式確定了，這個(gè)域上的運(yùn)算也就確定了。本原多項(xiàng)式一般通過(guò)查表可得，同一個(gè)域往往有多個(gè)本原多項(xiàng)式。通過(guò)將域中的元素化為多項(xiàng)式形式，可以將域上的乘法運(yùn)算轉(zhuǎn)化為普通的多項(xiàng)式乘法再模本原多項(xiàng)式。
GF(pn) 中元素加法和乘法單位元分別是 0和1，對(duì)于域中的乘法，當(dāng)p為素?cái)?shù)時(shí)，才能保證集合中的所有的元素都有乘法逆元(0除外)。
通過(guò)本原多項(xiàng)式生成元素
例 GF(24), 其本原多項(xiàng)式 P(x)=x4+x+1, 令 GF(24)的元素為 0、1、a1、a2、……、a14 , 則ai 生成的多項(xiàng)式為 ximod(P(x)) , 如下表：
| 元素 |
多項(xiàng)式 |
對(duì)應(yīng)數(shù)值 |
| 0 |
0modP(x)=0 |
0000 (0) |
| 1 |
1modP(x)=1 |
0001 (1) |
| a1 |
x1modP(x)=x |
0010 (2) |
| a2 |
x2modP(x)=x2 |
0100 (4) |
| a3 |
x3modP(x)=x3 |
1000 (8) |
| a4 |
x4modP(x)=x+1 |
0011 (3) |
| a5 |
x5modP(x)=x2+x |
0110 (6) |
| a6 |
x6modP(x)=x3+x2 |
1100 (12) |
| a7 |
x7modP(x)=x3+x+1 |
1011 (11) |
| a8 |
x8modP(x)=x2+1 |
0101 (5) |
| a9 |
x9modP(x)=x3+x |
1010 (10) |
| a10 |
x10modP(x)=x2+x+1 |
0111 (7) |
| a11 |
x11modP(x)=x3+x2+x |
1110 (14) |
| a12 |
x12modP(x)=x3+x2+x+1 |
0010 (15) |
| a13 |
x13modP(x)=x3+x2+1 |
1101 (13) |
| a14 |
x14modP(x)=x3+1 |
1001 (9) |
上面例子建立GF中元素與數(shù)值一一對(duì)應(yīng)關(guān)系。
上述可以看出，GF 的元素其實(shí)就是二進(jìn)制多項(xiàng)式構(gòu)成的循環(huán)碼，由循環(huán)碼的特性，定義GF中元素的四則運(yùn)算，保證了運(yùn)算后的結(jié)果還是域的中元素。例如，加法 a4+a9=(0011)xor(1010)=(1001)=a14 , 即元素的加法是對(duì)應(yīng)數(shù)值的異或結(jié)果對(duì)應(yīng)的元素；a4?a9=a((4+9)mod15)=a13 , 即元素相乘為其冪值相加求模對(duì)應(yīng)的元素。
設(shè)數(shù)值 y,u,v,z, 元素ai,aj,a((i+j)mod(n?1)),a((i?j)mod(n?1))分別為y,u,v,z在GF(2n)中對(duì)應(yīng)的元素，為則GF中四則運(yùn)算為：
加減法：數(shù)值異或 k⊕l
乘法：k?l?a((i+j)mod(n?1))?v
除法：k/l?a((i?j)mod(n?1))?z
常用本原多項(xiàng)式：
| n |
本原多項(xiàng)式 |
| 4 |
x4+x+1 |
| 8 |
x8+x4+x3+x2+1 |
| 16 |
x16+x12+x3+x+1 |
| 32 |
x32+x22+x2+x+1 |
| 64 |
x64+x4+x3+x+1 |
為了乘除法計(jì)算方便，一般將數(shù)值與元素對(duì)應(yīng)關(guān)系列表。計(jì)算時(shí)，將數(shù)值根據(jù)表轉(zhuǎn)為對(duì)應(yīng)各自的元素乘法，得到結(jié)果元素，再根據(jù)表轉(zhuǎn)為對(duì)應(yīng)的數(shù)值。
RS編碼丟包恢復(fù)
通過(guò)使用多項(xiàng)式對(duì)應(yīng)的GF來(lái)實(shí)現(xiàn)對(duì)非二進(jìn)制數(shù)據(jù)運(yùn)算并進(jìn)行變換其實(shí)就是RS編碼技術(shù)。RS(Reed-Solomon)碼是一類糾錯(cuò)能力很強(qiáng)的特殊的非二進(jìn)制BCH碼。
對(duì)于簡(jiǎn)單普通抗丟技術(shù)，增加冗余是對(duì)原生數(shù)據(jù)一份復(fù)制，也就是增加數(shù)據(jù)的一倍冗余來(lái)恢復(fù)對(duì)應(yīng)的一個(gè)數(shù)據(jù)。這種恢復(fù)性能非常低。而RS編碼變換則能實(shí)現(xiàn)高效抗丟。
例如，有四個(gè)數(shù)據(jù) a b c d被傳輸 ， 則通過(guò)變換得到e=f(a,b,c,d)，這時(shí)若a b c d 中有一個(gè)丟失，如a丟失，那么可以通過(guò)逆變換a=fH(b,c,d,e)恢復(fù)。也就是通過(guò)增加四分之一的冗余，來(lái)抵抗一個(gè)包的丟失，但這種抵抗是任何一個(gè)數(shù)據(jù)。而如果要抗所有數(shù)據(jù)丟失，那么需要增加一倍的冗余，即四個(gè)原生數(shù)據(jù)變換到四個(gè)冗余數(shù)據(jù)。
RS編碼
F?D=C, 變換中涉及到的四則運(yùn)算都在GF中進(jìn)行，D是原生數(shù)據(jù)，C是監(jiān)督數(shù)據(jù)（冗余數(shù)據(jù)）, F是一個(gè)線性無(wú)關(guān)矩陣（變換方程組系數(shù)），其實(shí)現(xiàn)有范德蒙矩陣（vandermode）和柯西矩陣。范德蒙矩陣實(shí)現(xiàn)比較方便，可以構(gòu)建任意 n*n 的非奇異可逆矩陣,其形式如下：
??????????111?11222?2n?11332?3n?1?????1nn2?nn?1??????????
例如，選取子范德蒙矩陣對(duì) a b c d ，變換為 e f g h ：
?????111112481416641864256??????????abcd?????=?????efgh?????
RS恢復(fù)
如果在n個(gè)原生數(shù)據(jù) D 中丟失m個(gè)數(shù)據(jù)Dm，那么可以從冗余數(shù)據(jù)C中任意m個(gè)數(shù)據(jù)Cm 和原生未丟失數(shù)據(jù)Dn?m 通過(guò)F對(duì)應(yīng)的子矩陣進(jìn)行逆變換求解計(jì)算出丟失的Dm。
例如，a b d 丟失， 我們?nèi)稳∪哂鄶?shù)據(jù)中的 e g h 和為丟失的c來(lái)恢復(fù) :
?????11114811664164256??????????abcd?????=?????egh?????
上面先將f 對(duì)應(yīng)的矩陣F那一行系數(shù)去掉，接著將c 對(duì)應(yīng)矩陣F那一列系數(shù)與c相乘，移位到等式右邊與 e g h 分別相加：
?????111148164256??????????abd?????=?????e+cg+16ch+64c?????
整理為：
???111148164256??????abd???=???e+cg+16ch+64c???
則逆變換可得 a b d:
???abd???=???111148164256???H???e+cg+16ch+64c???
RS編碼通常將每n個(gè)原生數(shù)據(jù)為一組，通過(guò)n*n 的范德蒙矩陣換成一組n個(gè)冗余數(shù)據(jù)，如果丟失m個(gè)，那么任意的m個(gè)冗余便可用來(lái)逆變換恢復(fù)原生數(shù)據(jù)，最多可恢復(fù)連續(xù)n個(gè)丟失包，其中任意的冗余數(shù)據(jù)就能來(lái)用恢復(fù)這一點(diǎn)是普通的增加冗余的本質(zhì)區(qū)別，因?yàn)槿哂鄶?shù)據(jù)也會(huì)丟失，如果任意就能恢復(fù)那么恢復(fù)能力也就更強(qiáng); RS變化中涉及的運(yùn)算是在定義在GF中的，這使的不因?yàn)閿?shù)據(jù)表示的大小而增加冗余開(kāi)銷 。
信道丟包恢復(fù)技術(shù)
在網(wǎng)絡(luò)通信傳輸場(chǎng)景，數(shù)據(jù)通常以包形式被連續(xù)傳輸，為了抗丟包，可以采用FEC技術(shù)生成冗余數(shù)據(jù)包，來(lái)恢復(fù)丟包， 將上述例子中數(shù)據(jù)用數(shù)據(jù)換成數(shù)據(jù)包，是一樣邏輯。通常將原生數(shù)據(jù)包分組，生成一組檢驗(yàn)包（冗余包），將檢驗(yàn)包作為下一組的冗余， 例如：
a0b0c0d0a1e0b1f0c1g0d1h0
上述中，每4個(gè)包 a b c d 為一組，生成的檢驗(yàn)包e f g h分別做為下一組包傳輸，這樣就可以前一組的丟包情況（丟少個(gè)），當(dāng)收到下一組的就可以通過(guò)冗余包恢復(fù)。對(duì)于實(shí)時(shí)傳輸情況，這樣為了等待冗余包，勢(shì)必造成延遲， 分組大小對(duì)應(yīng)著延遲大小，犧牲時(shí)效性保證可靠性。
參考文獻(xiàn)
[1] James S. Plank. Erasure Codes For Storage Application.
https://web.eecs./~plank/plank/papers/FAST-2005.pdf
[2] James S. Plank. A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems
https://web.eecs./~plank/plank/papers/CS-96-332.pdf
[3] Reed-Solomon Codes.
https://www.cs./courses/spring10/cps296.3/rs_scribe.pdf
|
