Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with soft-decision decoding:
TR97-046 | 3rd October 1997
Alexander Barg

Complexity Issues in Coding Theory

This is a research-expository paper. It deals with
complexity issues in the theory of linear block codes. The main
emphasis is on the theoretical performance limits of the
best known codes. Therefore, the main subject of the paper are
families of asymptotically good codes, i.e., codes whose rate and
relative ... more >>>

TR08-036 | 14th March 2008
Venkatesan Guruswami, Atri Rudra

Soft decoding, dual BCH codes, and better list-decodable eps-biased codes

We construct binary linear codes that are efficiently list-decodable
up to a fraction $(1/2-\eps)$ of errors. The codes encode $k$ bits
into $n = {\rm poly}(k/\eps)$ bits and are constructible and
list-decodable in time polynomial in $k$ and $1/\eps$ (in
particular, in our results $\eps$ need ... more >>>

ISSN 1433-8092 | Imprint