TY - JOUR
T1 - Memory effects can make the transmission capability of a communication channel uncomputable
AU - Elkouss, David
AU - Pérez-García, David
PY - 2018
Y1 - 2018
N2 - Most communication channels are subjected to noise. One of the goals of information theory is to add redundancy in the transmission of information so that the information is transmitted reliably and the amount of information transmitted through the channel is as large as possible. The maximum rate at which reliable transmission is possible is called the capacity. If the channel does not keep memory of its past, the capacity is given by a simple optimization problem and can be efficiently computed. The situation of channels with memory is less clear. Here we show that for channels with memory the capacity cannot be computed to within precision 1/5. Our result holds even if we consider one of the simplest families of such channels - information-stable finite state machine channels - restrict the input and output of the channel to 4 and 1 bit respectively and allow 6 bits of memory.
AB - Most communication channels are subjected to noise. One of the goals of information theory is to add redundancy in the transmission of information so that the information is transmitted reliably and the amount of information transmitted through the channel is as large as possible. The maximum rate at which reliable transmission is possible is called the capacity. If the channel does not keep memory of its past, the capacity is given by a simple optimization problem and can be efficiently computed. The situation of channels with memory is less clear. Here we show that for channels with memory the capacity cannot be computed to within precision 1/5. Our result holds even if we consider one of the simplest families of such channels - information-stable finite state machine channels - restrict the input and output of the channel to 4 and 1 bit respectively and allow 6 bits of memory.
KW - Computer science
KW - Information theory and computation
KW - OA-Fund TU Delft
UR - http://resolver.tudelft.nl/uuid:28f67ee5-1b87-4d9a-8dc8-6e5c5274585a
UR - http://www.scopus.com/inward/record.url?scp=85044462752&partnerID=8YFLogxK
U2 - 10.1038/s41467-018-03428-0
DO - 10.1038/s41467-018-03428-0
M3 - Article
AN - SCOPUS:85044462752
SN - 2041-1723
VL - 9
SP - 1
EP - 5
JO - Nature Communications
JF - Nature Communications
IS - 1
M1 - 1149
ER -