Repository logo
  • Log In
    Log in via Symplectic to deposit your publication(s).
Repository logo
  • Communities & Collections
  • Research Outputs
  • Statistics
  • Log In
    Log in via Symplectic to deposit your publication(s).
  1. Home
  2. Faculty of Engineering
  3. Faculty of Engineering
  4. Capacity achieving codes from randomness conductors
 
  • Details
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
URI
http://hdl.handle.net/10044/1/63178
DOI
https://www.dx.doi.org/10.1109/ISIT.2009.5205931
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
About
Spiral Depositing with Spiral Publishing with Spiral Symplectic
Contact us
Open access team Report an issue
Other Services
Scholarly Communications Library Services
logo

Imperial College London

South Kensington Campus

London SW7 2AZ, UK

tel: +44 (0)20 7589 5111

Accessibility Modern slavery statement Cookie Policy

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science

  • Cookie settings
  • Privacy policy
  • End User Agreement
  • Send Feedback