Capacity achieving codes from randomness conductors
File(s)0901.1866v2.pdf (637.57 KB)
Accepted version
Author(s)
Cheraghchi, Mahdi
Type
Conference Paper
Abstract
We give a general framework for construction of small ensembles of capacity achieving linear codes for a wide range of (not necessarily memoryless) discrete symmetric channels, and in particular, the binary erasure and symmetric channels. The main tool used in our constructions is the notion of randomness extractors and lossless condensers that are regarded as central tools in theoretical computer science. Same as random codes, the resulting ensembles preserve their capacity achieving properties under any change of basis. Our methods can potentially lead to polynomial-sized ensembles; however, using known explicit constructions of randomness conductors we obtain specific ensembles whose size is as small as quasipolynomial in the block length. By applying our construction to Justesen's concatenation scheme (Justesen, 1972) we obtain explicit capacity achieving codes for BEC (resp., BSC) with almost linear time encoding and almost linear time (resp., quadratic time) decoding and exponentially small error probability. The explicit code for BEC is defined and capacity achieving for every block length.
Date Issued
2009-08-18
Date Acceptance
2009-06-28
Citation
2009 IEEE International Symposium on Information Theory, 2009, pp.2639-2643
ISBN
9781424443123
ISSN
2157-8095
Publisher
IEEE
Start Page
2639
End Page
2643
Journal / Book Title
2009 IEEE International Symposium on Information Theory
Copyright Statement
© 2009 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Identifier
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000280141401244&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
Source
IEEE International Symposium on Information Theory (ISIT 2009)
Subjects
Science & Technology
Technology
Engineering, Electrical & Electronic
Engineering
EXTRACTORS
ERROR
Publication Status
Published
Start Date
2009-06-28
Finish Date
2009-07-03
Coverage Spatial
Seoul, South Korea
Date Publish Online
2009-08-18