Capacity achieving codes from randomness conductors. Cheraghchi, M. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), pages 2639–2643, 2009. 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
{"_id":"kMt42yzrawknrCYK6","bibbaseid":"cheraghchi-capacityachievingcodesfromrandomnessconductors-2009","authorIDs":["2n8MNophuzbeevTa8","3NEcSaujokmJYSDaa","3tFWxWs2qWeYAZx9a","4QNcMTdRiWr2gs8Sk","5KoQWR3vSjnsoZNz5","5i4QHRc5LGio8Mf5u","62bYDgAFwCxaQ4Q9T","685mTysGDdQJKGxEE","6sX76eTffL7p76peN","8NLx3B3FAvaK54hSK","9NZpjMJLG7dNWroGm","9aD4MPX9ELhsyJmaR","9aFgrqcc4j28kZn8n","A9wAgP7TPK9tw28qY","BJ6h7zrsT3L89RKSg","BWL9E9QxvrST7y7ym","Cht4qGZ9eYAvPygNC","D3NMRJpac7Z2oFz7x","EiL6Xv4GTWGB97B8H","F3Y934eNyTeEJsg6E","FDEj5Zwdm28pFcAnB","FJdyLy2TL3v973ge8","GxccwstJJuJ4rg7Dq","H4D7r27RcPALT5DCs","HP7szFXWBWFXXZhdA","HRX7xsd7ZkTNvr67D","Hj3KN5PTNMST8hD3b","JEvEPvDBYNNXgGBnp","JYpde2ppjXLva6cre","KFgC2dZG7jXYAgZ3T","NRg9mmaSB55QqzNnH","NWCEkq6XqRBCiGmMe","NpGaG45evixRFDMiF","NyDiXeBc7cuxdWrqh","P6pva6vpPZCz6ndh9","Py2jfYGNZKNt7nxL6","Q6E9aDkYPcbhngLMx","QYrXKExv3BPABZGyA","QupQWsidagmv2nu8Z","SGZ2YignSm7njeTxy","SSuyWxzudqBDgAosw","THz3CmRmH3zZ9Xfud","TTEBJzPHwrY4d2Qfi","Wzr7kB4bxMDqceidA","YedfCw6zcDLoWAWFL","YtTEuSL9GJ8pkKcZw","Z3w2d32WjDczZMeGo","aduB2YE7dcNtbHnAN","c8gPvTXFPd9NazgEw","d6HAadRZAtz97Y2so","dTBDNYCcYKNNdhqaR","ezDt3Lb3Q6Sbo2rfX","fXtxgjbjZswBmF45i","ftBpmnKRHoB2muB8u","gKxHau44e8gnmxs6v","hM29eSWZbASnmDdFf","hw7Q4GHDAHkLTAyeB","i6Ns5rSW8R3ifxeHg","jJcoL4QWRkJQ59LfW","kKvRZ55rH7sfbubS2","kdfqsAMqCFDhpuW3S","koPTGcsAkwhGbkAYe","manxWg6Q3ZC5vW4JE","pwN2yYKo5DdSDaZGs","qpSgMrJ8WQNupjbXX","sD5Wq95oeSzqGF9kn","uSGLWGoXjyDyozeEy","wCcpScxkvg5RkcmWm","xKz7kx4eXbnkHeNXP","xeiij9YsbXBbMjciP","yGxZz3yuu6krMRxgK","yjJrpKY5QmDe8SXvm","zaR6PwJ7aC9xWBpiy"],"author_short":["Cheraghchi, M."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Mahdi"],"propositions":[],"lastnames":["Cheraghchi"],"suffixes":[]}],"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","bibtex":"@INPROCEEDINGS{ref:conf:Che09:capacity,\n author =\t {Mahdi Cheraghchi},\n booktitle =\t {Proceedings of the {IEEE International Symposium on\n Information Theory (ISIT)}},\n title =\t {Capacity achieving codes from randomness conductors},\n year =\t 2009,\n pages =\t {2639--2643},\n doi =\t\t {10.1109/ISIT.2009.5205931},\n url_Link =\n {https://ieeexplore.ieee.org/abstract/document/5205931},\n url_Paper =\t {https://arxiv.org/abs/0901.1866},\n abstract =\t {We establish a general framework for construction of\n small ensembles of capacity achieving linear codes\n for a wide range of (not necessarily memoryless)\n discrete symmetric channels, and in particular, the\n binary erasure and symmetric channels. The main\n tool used in our constructions is the notion of\n randomness extractors and lossless condensers that\n are regarded as central tools in theoretical\n computer science. Same as random codes, the\n resulting ensembles preserve their capacity\n achieving properties under any change of basis.\n Using known explicit constructions of condensers, we\n obtain specific ensembles whose size is as small as\n polynomial in the block length. By applying our\n construction to Justesen's concatenation scheme\n (Justesen, 1972) we obtain explicit capacity\n achieving codes for BEC (resp., BSC) with almost\n linear time encoding and almost linear time (resp.,\n quadratic time) decoding and exponentially small\n error probability. },\n keywords =\t {Capacity achieving codes, Randomness extractors,\n Lossless condensers, Code ensembles, Concatenated\n codes}\n}\n\n","author_short":["Cheraghchi, M."],"key":"ref:conf:Che09:capacity","id":"ref:conf:Che09:capacity","bibbaseid":"cheraghchi-capacityachievingcodesfromrandomnessconductors-2009","role":"author","urls":{" link":"https://ieeexplore.ieee.org/abstract/document/5205931"," paper":"https://arxiv.org/abs/0901.1866"},"keyword":["Capacity achieving codes","Randomness extractors","Lossless condensers","Code ensembles","Concatenated codes"],"metadata":{"authorlinks":{"cheraghchi, m":"https://mahdi.ch/"}}},"bibtype":"inproceedings","biburl":"http://mahdi.ch/writings/cheraghchi.bib","creationDate":"2020-05-29T01:55:30.863Z","downloads":4,"keywords":["capacity achieving codes","randomness extractors","lossless condensers","code ensembles","concatenated codes"],"search_terms":["capacity","achieving","codes","randomness","conductors","cheraghchi"],"title":"Capacity achieving codes from randomness conductors","year":2009,"dataSources":["YZqdBBx6FeYmvQE6D"]}