動機
文章很好懂,紀錄一下 同時把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的逆矩陣求解