Sharp Analytical Capacity Upper Bounds for Sticky and Related Channels. Cheraghchi, M. & Ribeiro, J. In Proceedings of the 56th Annual Allerton Conference on Communication, Control, and Computing, pages 1104–1111, 2018. Extended version in IEEE Transactions on Information Theory.Link Paper doi abstract bibtex We study natural examples of binary channels with synchronization errors. These include the duplication channel, which independently outputs a given bit once or twice, and geometric channels that repeat a given bit according to a geometric rule, with or without the possibility of bit deletion. We apply the general framework of Cheraghchi (STOC 2018) to obtain sharp analytical upper bounds on the capacity of these channels. Previously, upper bounds were known via numerical computations involving the computation of finite approximations of the channels by a computer and then using the obtained numerical results to upper bound the actual capacity. While leading to sharp numerical results, further progress on the full understanding of the channel capacity inherently remains elusive using such methods. Our results can be regarded as a major step towards a complete understanding of the capacity curves. Quantitatively, our upper bounds sharply approach, and in some cases surpass, the bounds that were previously only known by purely numerical methods. Among our results, we notably give a completely analytical proof that, when the number of repetitions per bit is geometric (supported on $\{0,1,2,ṡ\}$) with mean growing to infinity, the channel capacity remains substantially bounded away from $1$.
@INPROCEEDINGS{ref:conf:CR18,
author = {Mahdi Cheraghchi and Jo\~{a}o Ribeiro},
title = {Sharp Analytical Capacity Upper Bounds for Sticky
and Related Channels},
year = 2018,
booktitle = {Proceedings of the 56th {Annual Allerton Conference
on Communication, Control, and Computing}},
pages = {1104--1111},
note = {Extended version in {IEEE Transactions on
Information Theory}.},
doi = {10.1109/ALLERTON.2018.8636009},
url_Link = {https://ieeexplore.ieee.org/document/8636009},
url_Paper = {https://arxiv.org/abs/1903.09992},
abstract = {We study natural examples of binary channels with
synchronization errors. These include the
duplication channel, which independently outputs a
given bit once or twice, and geometric channels that
repeat a given bit according to a geometric rule,
with or without the possibility of bit deletion. We
apply the general framework of Cheraghchi (STOC
2018) to obtain sharp analytical upper bounds on the
capacity of these channels. Previously, upper
bounds were known via numerical computations
involving the computation of finite approximations
of the channels by a computer and then using the
obtained numerical results to upper bound the actual
capacity. While leading to sharp numerical results,
further progress on the full understanding of the
channel capacity inherently remains elusive using
such methods. Our results can be regarded as a major
step towards a complete understanding of the
capacity curves. Quantitatively, our upper bounds
sharply approach, and in some cases surpass, the
bounds that were previously only known by purely
numerical methods. Among our results, we notably
give a completely analytical proof that, when the
number of repetitions per bit is geometric
(supported on $\{0,1,2,\dots\}$) with mean growing
to infinity, the channel capacity remains
substantially bounded away from $1$. }
}
Downloads: 0
{"_id":"FJkMRPikN5oFKLg7m","bibbaseid":"cheraghchi-ribeiro-sharpanalyticalcapacityupperboundsforstickyandrelatedchannels-2018","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.","Ribeiro, J."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Mahdi"],"propositions":[],"lastnames":["Cheraghchi"],"suffixes":[]},{"firstnames":["João"],"propositions":[],"lastnames":["Ribeiro"],"suffixes":[]}],"title":"Sharp Analytical Capacity Upper Bounds for Sticky and Related Channels","year":"2018","booktitle":"Proceedings of the 56th Annual Allerton Conference on Communication, Control, and Computing","pages":"1104–1111","note":"Extended version in IEEE Transactions on Information Theory.","doi":"10.1109/ALLERTON.2018.8636009","url_link":"https://ieeexplore.ieee.org/document/8636009","url_paper":"https://arxiv.org/abs/1903.09992","abstract":"We study natural examples of binary channels with synchronization errors. These include the duplication channel, which independently outputs a given bit once or twice, and geometric channels that repeat a given bit according to a geometric rule, with or without the possibility of bit deletion. We apply the general framework of Cheraghchi (STOC 2018) to obtain sharp analytical upper bounds on the capacity of these channels. Previously, upper bounds were known via numerical computations involving the computation of finite approximations of the channels by a computer and then using the obtained numerical results to upper bound the actual capacity. While leading to sharp numerical results, further progress on the full understanding of the channel capacity inherently remains elusive using such methods. Our results can be regarded as a major step towards a complete understanding of the capacity curves. Quantitatively, our upper bounds sharply approach, and in some cases surpass, the bounds that were previously only known by purely numerical methods. Among our results, we notably give a completely analytical proof that, when the number of repetitions per bit is geometric (supported on $\\{0,1,2,ṡ\\}$) with mean growing to infinity, the channel capacity remains substantially bounded away from $1$. ","bibtex":"@INPROCEEDINGS{ref:conf:CR18,\n author =\t {Mahdi Cheraghchi and Jo\\~{a}o Ribeiro},\n title =\t {Sharp Analytical Capacity Upper Bounds for Sticky\n and Related Channels},\n year =\t 2018,\n booktitle =\t {Proceedings of the 56th {Annual Allerton Conference\n on Communication, Control, and Computing}},\n pages =\t {1104--1111},\n note =\t {Extended version in {IEEE Transactions on\n Information Theory}.},\n doi =\t\t {10.1109/ALLERTON.2018.8636009},\n url_Link =\t {https://ieeexplore.ieee.org/document/8636009},\n url_Paper =\t {https://arxiv.org/abs/1903.09992},\n abstract =\t {We study natural examples of binary channels with\n synchronization errors. These include the\n duplication channel, which independently outputs a\n given bit once or twice, and geometric channels that\n repeat a given bit according to a geometric rule,\n with or without the possibility of bit deletion. We\n apply the general framework of Cheraghchi (STOC\n 2018) to obtain sharp analytical upper bounds on the\n capacity of these channels. Previously, upper\n bounds were known via numerical computations\n involving the computation of finite approximations\n of the channels by a computer and then using the\n obtained numerical results to upper bound the actual\n capacity. While leading to sharp numerical results,\n further progress on the full understanding of the\n channel capacity inherently remains elusive using\n such methods. Our results can be regarded as a major\n step towards a complete understanding of the\n capacity curves. Quantitatively, our upper bounds\n sharply approach, and in some cases surpass, the\n bounds that were previously only known by purely\n numerical methods. Among our results, we notably\n give a completely analytical proof that, when the\n number of repetitions per bit is geometric\n (supported on $\\{0,1,2,\\dots\\}$) with mean growing\n to infinity, the channel capacity remains\n substantially bounded away from $1$. }\n}\n\n","author_short":["Cheraghchi, M.","Ribeiro, J."],"key":"ref:conf:CR18","id":"ref:conf:CR18","bibbaseid":"cheraghchi-ribeiro-sharpanalyticalcapacityupperboundsforstickyandrelatedchannels-2018","role":"author","urls":{" link":"https://ieeexplore.ieee.org/document/8636009"," paper":"https://arxiv.org/abs/1903.09992"},"metadata":{"authorlinks":{"cheraghchi, m":"https://mahdi.ch/"}}},"bibtype":"inproceedings","biburl":"http://mahdi.ch/writings/cheraghchi.bib","creationDate":"2020-05-28T19:49:18.638Z","downloads":1,"keywords":[],"search_terms":["sharp","analytical","capacity","upper","bounds","sticky","related","channels","cheraghchi","ribeiro"],"title":"Sharp Analytical Capacity Upper Bounds for Sticky and Related Channels","year":2018,"dataSources":["YZqdBBx6FeYmvQE6D"]}