Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding

Computer Science – Information Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Conference version appears at STOC 2012

Scientific paper

We give a new construction of algebraic codes which are efficiently list decodable from a fraction $1-R-\eps$ of adversarial errors where $R$ is the rate of the code, for any desired positive constant $\eps$. The worst-case list size output by the algorithm is $O(1/\eps)$, matching the existential bound for random codes up to constant factors. Further, the alphabet size of the codes is a constant depending only on $\eps$ - it can be made $\exp(\tilde{O}(1/\eps^2))$ which is not much worse than the lower bound of $\exp(\Omega(1/\eps))$. The parameters we achieve are thus quite close to the existential bounds in all three aspects - error-correction radius, alphabet size, and list-size - simultaneously. Our code construction is Monte Carlo and has the claimed list decoding property with high probability. Once the code is (efficiently) sampled, the encoding/decoding algorithms are deterministic with a running time $O_\eps(N^c)$ for an absolute constant $c$, where $N$ is the code's block length. Our construction is based on a linear-algebraic approach to list decoding folded codes from towers of function fields, and combining it with a special form of subspace-evasive sets. Instantiating this with the explicit "asymptotically good" Garcia-Stichtenoth tower of function fields yields the above parameters. To illustrate the method in a simpler setting, we also present a construction based on Hermitian function fields, which offers similar guarantees with a list and alphabet size polylogarithmic in the block length $N$. Along the way, we shed light on how to use automorphisms of certain function fields to enable list decoding of the folded version of the associated algebraic-geometric codes.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-33248

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.