Capacity achieving codes from randomness conductors. Cheraghchi, M. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), pages 2639–2643, 2009.
Capacity achieving codes from randomness conductors [link]Link  Capacity achieving codes from randomness conductors [link]Paper  doi  abstract   bibtex   
We establish 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. Using known explicit constructions of condensers, we obtain specific ensembles whose size is as small as polynomial 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.
@INPROCEEDINGS{ref:conf:Che09:capacity,
  author =	 {Mahdi Cheraghchi},
  booktitle =	 {Proceedings of the {IEEE International Symposium on
                  Information Theory (ISIT)}},
  title =	 {Capacity achieving codes from randomness conductors},
  year =	 2009,
  pages =	 {2639--2643},
  doi =		 {10.1109/ISIT.2009.5205931},
  url_Link =
                  {https://ieeexplore.ieee.org/abstract/document/5205931},
  url_Paper =	 {https://arxiv.org/abs/0901.1866},
  abstract =	 {We establish 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.
                  Using known explicit constructions of condensers, we
                  obtain specific ensembles whose size is as small as
                  polynomial 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.  },
  keywords =	 {Capacity achieving codes, Randomness extractors,
                  Lossless condensers, Code ensembles, Concatenated
                  codes}
}

Downloads: 0