On decoding interleaved Reed-solomon codes

Abstract

Bleichenbacher-Kiayias-Yung olasılıksal eşzamanlı polinom geriçatılması algoritması polinomların dereceleri farklı olduğu durumlara genelleştirilmiştir. Ayrıca, olasılığın ar/-tı/-rı/-la/-bi/-le/-ce/-ği de gözlemlenmiştir. Belirgin şekliyle, $/F$ sonlu bir cisimi için, $p_l(z_i) = y_{i,l}$ $i /in I$, $I=t$ ve $l /in [r]$ polinom değerleri verildiğinde, dereceleri sırasıyla $k_1,k_2,/ldots,k_r$ olan $p_1,/ldots, p_r /in /F[x]$ polinomlarını en azından $1 - (n - t)//F$ olasılığı ve en çok $O((nr)^3)$ hesaplama karmaşıklığında eşzamanlı geriçatan olasılıksal bir algoritma sunulmuştur. Bu algoritmanın kullanımıyla geçmeli Reed-Solomon kodları için olasılıksal çözümleyici sunulmuştur. Bu çözümleyici, bigi oranı $R$ olan $/F$ üzerinde tanımlı $r$ geçmeli Reed-Solomon kodları $/frac{r}{r+1}(1 - R)$ yığılma hata oranına kadar olasılıksal çözümleyebilir. O/-la/-sı/-lık/-sal geçmeli Reed-Solomon kod çözümleyicisi kullanıldığında verilen bir Reed-Solomon kodu RS$(n;k)$ $R' = /frac{(k-1)(r+1)+2}{2n}$ için $/frac{r}{r+1}(1 - R')$ hata oranına kadar çözümlenebileceği ispatlanmıştır. Benzer şekilde, bir $/F_{q^2}$ sonlu cismi için, bilgi oranı $R$ olan ve $/F_{q^{2q}}$ üzerinde tanımlı $q$-katlı Hermityan kodlarının $/frac{q}{q+1}(1 - R)$ hata oranına kadar olasılıksal çözümlenebileceği istalanmıştır. Diğer taraftan, alt/-kod/-la/-rı/-nın en az aralıkları farklı olduğunda bile geçmeli kodların, altkodlarının en küçük liste çözümleme çapına kadar çözümlenebileceği gösterilmiştir. Diğer bir ifadeyle, en az aralıkları farklı olabilen $C_1,/ldots, C_b$ kodlarının geçirilmesi ile oluşan $C$ kodunu, $C_1,/ldots, C_b$ kodlarının en küçük liste çözümleme çapına kadar, $C_1,/ldots, C_b$ kodlarının en büyük liste boyutunun polinom katı liste büyüklüğünde ve bu büyüklük ve $b$ sabitinin bir polinom katı zamanda çözebilen bir algoritma sunulmuştur. Bu algoritmanın kullanımıyla tanımlandığı cisim büyüküğü $q$ olan ve herhangibir $h$ doğal sayısı için $qh$-katlı Hermityan kodlarını listeleme yöntemiyle çözümleyebilen yeni bir algoritma sunulmuştur. Bu algoritma, $qh$-katlı Hermityan kodlarını, Guruswami-Sudan algoritmasından daha iyi bir çapa kadar, $/F_{q^2}$ üzerinde tanımlı $h$-katlı Reed-Solomon kodlarının liste büyüklüğünün polinom katı hesap karmaşıklığında ve liste büyüklüğünde çözümler.

Probabilistic simultaneous polynomial reconstruction algorithm of Bleichenbacher-Kiayias-Yung is extended to the polynomials whose degrees are allowed to be distinct. Furthermore, it is observed that probability of the algorithm can be increased. Specifically, for a finite field $/F$, we present a probabilistic algorithm which can recover polynomials $p_1,/ldots, p_r /in /F[x]$ of degree less than $k_1,k_2,/ldots,k_r$, respectively with given field evaluations $p_l(z_i) = y_{i,l}$ for all $i /in I$, $I=t$ and $l /in [r]$ with probability at least $1 - (n - t)//F$ and with time complexity at most $O((nr)^3)$. Next, by using this algorithm, we present a probabilistic decoder for interleaved Reed-Solomon codes. It is observed that interleaved Reed-Solomon codes over $/F$ with rate $R$ can be decoded up to burst error rate $/frac{r}{r+1}(1 - R)$ probabilistically for an interleaving parameter $r$. It is proved that a Reed-Solomon code RS$(n;k)$ can be decoded up to error rate $/frac{r}{r+1}(1 - R')$ for $R' = /frac{(k-1)(r+1)+2}{2n}$ when probabilistic interleaved Reed-Solomon decoders are applied. Similarly, for a finite field $/F_{q^2}$, it is proved that $q$-folded Hermitian codes over $/F_{q^{2q}}$ with rate $R$ can be decoded up to error rate $/frac{q}{q+1}(1 - R)$ probabilistically. On the other hand, it is observed that interleaved codes whose subcodes would have different minimum distances can be list decodable up to radius of minimum of list decoding radiuses of subcodes. Specifically, we present a list decoding algorithm for $C$, which is interleaving of $C_1,/ldots, C_b$ whose minimum distances would be different, decoding up to radius of minimum of list decoding radiuses of $C_1,/ldots, C_b$ with list size polynomial in the maximum of list sizes of $C_1,/ldots, C_b$ and with time complexity polynomial in list size of $C$ and $b$. Next, by using this list decoding algorithm for interleaved codes, we obtained new list decoding algorithm for $qh$-folded Hermitian codes for $q$ standing for field size the code defined and $h$ is any positive integer. The decoding algorithm list decodes $qh$-folded Hermitian codes for radius that is generally better than radius of Guruswami-Sudan algorithm, with time complexity and list size polynomial in list size of $h$-folded Reed-Solomon codes defined over $/F_{q^2}$.