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}$.
| Identifer | oai:union.ndltd.org:METU/oai:etd.lib.metu.edu.tr:http://etd.lib.metu.edu.tr/upload/12613621/index.pdf |
| Date | 01 September 2011 |
| Creators | Yayla, Oguz |
| Contributors | Ozbudak, Ferruh |
| Publisher | METU |
| Source Sets | Middle East Technical Univ. |
| Language | English |
| Detected Language | English |
| Type | Ph.D. Thesis |
| Format | text/pdf |
| Rights | To liberate the content for METU campus |
Page generated in 0.0017 seconds