Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Open Access Guideline
Open Access Guideline
Postgraduate Thesis Guideline
Postgraduate Thesis Guideline
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
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
194
views
0
downloads
Cite This
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
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
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.