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

Date

2014-02-06

Author

Özbudak, Ferruh

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

203
views

0
downloads

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 F, positive integers n, r, t and distinct elements z(1), z(2), ... , z(n) is an element of F, we present a probabilistic algorithm which can recover polynomials p(1), p(2), p(r) is an element of F[x] of degree less than k(1), k(2), ... , k(r) respectively for a given instance < y(i), (1, ... ,) y(i,r)>(n)(i=1) satisfying p(i)(z(i)) = y(i,l) for all I is an element of {1,2, ... , r} and for all i is an element of I subset of {1,2, ... , n} such that vertical bar I vertical bar = t with probability at least 1 - n-t/vertical bar F vertical bar and with time complexity at most 0(rn(4)) if t >= max{k(1), k(2), ... , k(r), n+Sigma(r)(j=1)k(j)/r+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 F with rate R can be decoded up to burst error rate r/r+1 (1 - R) probabilistically for an interleaving parameter r. Then, it is proved that q-folded Hermitian codes over F-q2q with rate R can be decoded up to error rate q/q+1 (1 - R) probabilistically.

Subject Keywords

Theoretical Computer Science, General Computer Science

URI

https://hdl.handle.net/11511/47531

Journal

THEORETICAL COMPUTER SCIENCE

DOI

https://doi.org/10.1016/j.tcs.2013.10.025

Collections

Department of Mathematics, Article

Suggestions

OpenMETU
Core

A note on divisor class groups of degree zero of algebraic function fields over finite fields Özbudak, Ferruh (Elsevier BV, 2003-01-01) We give tight upper bounds on the number of degree one places of an algebraic function field over a finite field in terms of the exponent of a natural subgroup of the divisor class group of degree zero.. (C) 2002 Elsevier Science (USA). All rights reserved.
Invariant subspaces for positive operators acting on a Banach space with Markushevich basis Ercan, Z; Onal, S (Springer Science and Business Media LLC, 2004-06-01) We introduce 'weak quasinilpotence' for operators. Then, by substituting 'Markushevich basis' and 'weak quasinilpotence at a nonzero vector' for 'Schauder basis' and 'quasinilpotence at a nonzero vector', respectively, we answer a question on the invariant subspaces of positive operators in [ 3].
On ideals generated by positive operators Alpay, S; Uyar, A (Springer Science and Business Media LLC, 2003-06-01) Algebra structure of principle ideals of order bounded operators is studied.
A note on b-weakly compact operators Alpay, Safak; Altin, Birol (Springer Science and Business Media LLC, 2007-11-01) We consider a continuous operator T : E -> X where E is a Banach lattice and X is a Banach space. We characterize the b-weak compactness of T in terms of its mapping properties.
On decoding interleaved reed-solomon codes Yayla, Oğuz; Özbudak, Ferruh; Department of Cryptography (2011) 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$, $

Citation Formats

F. Özbudak, “Improved probabilistic decoding of interleaved Reed-Solomon codes and folded Hermitian codes,” THEORETICAL COMPUTER SCIENCE, pp. 111–123, 2014, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/47531.