Optimal erasure codes Erasure code

1 optimal erasure codes

1.1 parity check
1.2 polynomial oversampling

1.2.1 example: err-mail (k = 2)
1.2.2 general case
1.2.3 real world implementation

optimal erasure codes

optimal erasure codes have property k out of n code word symbols sufficient recover original message (i.e., have optimal reception efficiency). optimal erasure codes maximum distance separable codes (mds codes).

optimal codes costly (in terms of memory usage, cpu time, or both) when n large. except simple schemes, practical solutions have quadratic encoding , decoding complexity. in 2014, lin et al. gave approach



o
(
n
log
⁡
n
)


{\displaystyle o(n\log n)}

operations.

parity check

parity check special case n = k + 1. set of k values



{

v

i



}

1
≤
i
≤
k




{\displaystyle \{v_{i}\}_{1\leq i\leq k}}

, checksum computed , appended k source values:

v

k
+
1


=
−

∑

i
=
1


k



v

i


.


{\displaystyle v_{k+1}=-\sum _{i=1}^{k}v_{i}.}

the set of k + 1 values



{

v

i



}

1
≤
i
≤
k
+
1




{\displaystyle \{v_{i}\}_{1\leq i\leq k+1}}

consistent regard checksum. if 1 of these values,




v

e




{\displaystyle v_{e}}

, erased, can recovered summing remaining variables:

v

e


=
−

∑

i
=
1
,
i
≠
e


k
+
1



v

i


.


{\displaystyle v_{e}=-\sum _{i=1,i\neq e}^{k+1}v_{i}.}



polynomial oversampling
example: err-mail (k = 2)

in simple case k = 2, redundancy symbols may created sampling different points along line between 2 original symbols. pictured simple example, called err-mail:

alice wants send telephone number (555629) bob using err-mail. err-mail works e-mail, except

instead of asking bob acknowledge messages sends, alice devises following scheme.

bob knows form of f(k)



f
(
i
)
=
a
+
(
b
−
a
)
(
i
−
1
)


{\displaystyle f(i)=a+(b-a)(i-1)}

, , b 2 parts of telephone number. suppose bob receives d=777 , e=851 .

bob can reconstruct alice s phone number computing values of , b values (f(4) , f(5)) has received. bob can perform procedure using 2 err-mails, erasure code in example has rate of 40%.

note alice cannot encode telephone number in 1 err-mail, because contains 6 characters, , maximum length of 1 err-mail message 5 characters. if sent phone number in pieces, asking bob acknowledge receipt of each piece, @ least 4 messages have sent anyway (two alice, , 2 acknowledgments bob). erasure code in example, requires 5 messages, quite economical.

this example little bit contrived. generic erasure codes work on data set, need other f(i) given.

general case

the linear construction above can generalized polynomial interpolation. additionally, points computed on finite field.

first choose finite field f order of @ least n, power of 2. sender numbers data symbols 0 k − 1 , sends them. constructs (lagrange) polynomial p(x) of order k such p(i) equal data symbol i. sends p(k), ..., p(n − 1). receiver can use polynomial interpolation recover lost packets, provided receives k symbols successfully. if order of f less 2, b number of bits in symbol, multiple polynomials can used.

the sender can construct symbols k n − 1 on fly , i.e., distribute workload evenly between transmission of symbols. if receiver wants calculations on fly , can construct new polynomial q, such q(i) = p(i) if symbol < k received , q(i) = 0 when symbol < k not received. let r(i) = p(i) − q(i). firstly know r(i) = 0 if symbol < k has been received successfully. secondly, if symbol ≥k has been received successfully, r(i) = p(i) − q(i) can calculated. have enough data points construct r , evaluate find lost packets. both sender , receiver require o(n (n − k)) operations , o(n − k) space operating on fly .

real world implementation

this process implemented reed–solomon codes, code words constructed on finite field using vandermonde matrix.