Memory effects can make the transmission capability of a communication channel uncomputable

Memory effects can make the transmission capability of a communication channel uncomputable

Elkouss Coronas, D. (TU Delft Quantum Information and Software; TU Delft QuTech Advanced Research Centre)
Pérez-García, David (Universidad Complutense de Madrid; Instituto de Ciencias Matemáticas (ICMAT))

2018

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.

Computer science
Information theory and computation
OA-Fund TU Delft

http://resolver.tudelft.nl/uuid:28f67ee5-1b87-4d9a-8dc8-6e5c5274585a

https://doi.org/10.1038/s41467-018-03428-0

2041-1723

Nature Communications, 9 (1), 1-5

Institutional Repository

journal article

© 2018 D. Elkouss Coronas, David Pérez-García