動機

文章很好懂,紀錄一下 同時把6.824沒說到的補完

把遺失資料當成未知數

a + b + c = sum(a,b,c)

這樣可以冗餘一個資料(未知數)

2個的話? 要2個方程式

3個? 要3個方程式

但係數不能隨便選吧? 亂選不一定能求解

所以有了Vandermonde matrix,他保證有解

空間是有限的: Galois-Field

也就是說所有數字都只會出現在一定的範圍,同時還有4則運算的性質

所以可以用它表現方程式,但怎麼用程式表現

GF(2): xor 以及 &

如果限制只有0與1的Galois-Field,會發現+與*就是xor與&

GF(2)的多項式: 邁向高維

係數放GF(2),剩下就是一般的多項式

這樣只要項目變多,能表現的數目也會越多 $a_1x^8+a_2x^7+….+a_7x+a_8$

像上面的式子可以表現$2^8$個東西 就是一個byte

再來就是要取餘數(餘數要是質數),不然會超過!!

所以選下面的式子 $x^8+x^4+x^3+x^2+1$

EC的實現方式

用GF(2)的多項式表示資料 用Vandermonde matrix求回復資料 需要回復時用Vandermonde matrix的逆矩陣求解

Ref

Erasure-Code-擦除码-2-实现篇 Erasure-Code-擦除码-1-原理篇