Improved probabilistic decoding of interleaved Reed–Solomon codes and folded Hermitian codes

Probabilistic simultaneous polynomial reconstruction algorithm of Bleichenbacher, Kiayias, and Yung is extended to the polynomials whose degrees are allowed to be distinct. Specifically, for a finite field FF, positive integers n, r, t   and distinct elements z1,z2,…,zn∈Fz1,z2,…,zn∈F, we present a probabilistic algorithm which can recover polynomials p1,p2,…,pr∈F[x]p1,p2,…,pr∈F[x] of degree less than k1,k2,…,krk1,k2,…,kr respectively for a given instance 〈yi,1,…,yi,r〉i=1n satisfying pl(zi)=yi,lpl(zi)=yi,l for all l∈{1,2,…,r}l∈{1,2,…,r} and for all i∈I⊂{1,2,…,n}i∈I⊂{1,2,…,n} such that |I|=t|I|=t with probability at least 1−n−t|F| and with time complexity at most O(rn4)O(rn4) if t⩾max{k1,k2,…,kr,n+∑j=1rkjr+1}. Next, by using this algorithm, we present a probabilistic decoder for interleaved Reed–Solomon codes. It is observed that interleaved Reed–Solomon codes over FF with rate R   can be decoded up to burst error rate rr+1(1−R) probabilistically for an interleaving parameter r. Then, it is proved that q  -folded Hermitian codes over Fq2qFq2q with rate R   can be decoded up to error rate qq+1(1−R) probabilistically.