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

David Elkouss () and David Pérez-García
Additional contact information
David Elkouss: Delft University of Technology
David Pérez-García: Universidad Complutense de Madrid

Nature Communications, 2018, vol. 9, issue 1, 1-5

Abstract: Abstract 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.

Date: 2018
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.nature.com/articles/s41467-018-03428-0 Abstract (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nat:natcom:v:9:y:2018:i:1:d:10.1038_s41467-018-03428-0

Ordering information: This journal article can be ordered from
https://www.nature.com/ncomms/

DOI: 10.1038/s41467-018-03428-0

Access Statistics for this article

Nature Communications is currently edited by Nathalie Le Bot, Enda Bergin and Fiona Gillespie

More articles in Nature Communications from Nature
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().