TY - GEN
T1 - Turing Meets Shannon
T2 - 2021 IEEE International Conference on Communications, ICC 2021
AU - Boche, Holger
AU - Schaefer, Rafael F.
AU - Poor, H. Vincent
N1 - Funding Information:
This work of H. Boche was supported in part by the German Federal Ministry of Education and Research (BMBF) within the national initiative for “Post Shannon Communication (NewCom)” under Grant 16KIS1003K and in part by the German Research Foundation (DFG) within the Gottfried Wilhelm Leibniz Prize under Grant BO 1734/20-1 and within Germany’s Excellence Strategy EXC-2092 – 390781972 and EXC-2111 – 390814868. This work of R. F. Schaefer was supported in part by the BMBF within NewCom under Grant 16KIS1004 and in part by the DFG under Grant SCHA 1944/6-1. This work of H. V. Poor was supported by the U.S. National Science Foundation under Grants CCF-0939370 and CCF-1908308.
Publisher Copyright:
© 2021 IEEE.
PY - 2021/6
Y1 - 2021/6
N2 - Proving a capacity result usually involves two parts: achievability and converse which establish matching lower and upper bounds on the capacity. For achievability, only the existence of good (capacity-achieving) codes is usually shown. Although the existence of such optimal codes is known, constructing such capacity-achieving codes has been open for a long time. Recently, significant progress has been made and optimal code constructions have been found including for example polar codes. A crucial observation is that all these constructions are done for a fixed and given channel and this paper addresses the question whether or not it is possible to find universal algorithms that can construct optimal codes for a whole class of channels. For this purpose, the concept of Turing machines is used which provides the fundamental performance limits of digital computers. It is shown that there exists no universal Turing machine that takes the channel from the class of interest as an input and outputs optimal codes. Finally, implications on channel-aware transmission schemes are discussed.
AB - Proving a capacity result usually involves two parts: achievability and converse which establish matching lower and upper bounds on the capacity. For achievability, only the existence of good (capacity-achieving) codes is usually shown. Although the existence of such optimal codes is known, constructing such capacity-achieving codes has been open for a long time. Recently, significant progress has been made and optimal code constructions have been found including for example polar codes. A crucial observation is that all these constructions are done for a fixed and given channel and this paper addresses the question whether or not it is possible to find universal algorithms that can construct optimal codes for a whole class of channels. For this purpose, the concept of Turing machines is used which provides the fundamental performance limits of digital computers. It is shown that there exists no universal Turing machine that takes the channel from the class of interest as an input and outputs optimal codes. Finally, implications on channel-aware transmission schemes are discussed.
UR - http://www.scopus.com/inward/record.url?scp=85108273937&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85108273937&partnerID=8YFLogxK
U2 - 10.1109/ICC42927.2021.9500750
DO - 10.1109/ICC42927.2021.9500750
M3 - Conference contribution
AN - SCOPUS:85108273937
T3 - IEEE International Conference on Communications
BT - ICC 2021 - IEEE International Conference on Communications, Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 14 June 2021 through 23 June 2021
ER -