An algorithm for computing the capacity of arbitrary discrete memoryless channels
IEEE Transactions on Information Theory · 1972 · 849 citations · 4 references
EngineeringChannel Capacity EstimationMonotonic ConvergenceIterative MethodMulti-terminal Information TheoryComputer ArchitectureComputer EngineeringComputational ComplexityChannel CodingComputer ScienceChannel EstimationChannel ModelChannel CharacterizationSignal ProcessingLower Bounds
A systematic and iterative method for computing the capacity of arbitrary discrete memoryless channels is presented. The algorithm uses only logarithms, exponentials, and elementary arithmetic, and derives inequalities that bound the capacity. It converges monotonically to capacity, with approximation error decreasing at least inversely with the number of iterations and, in some cases, exponentially.
A systematic and iterative method of computing the capacity of arbitrary discrete memoryless channels is presented. The algorithm is very simple and involves only logarithms and exponentials in addition to elementary arithmetical operations. It has also the property of monotonic convergence to the capacity. In general, the approximation error is at least inversely proportional to the number of iterations; in certain circumstances, it is exponentially decreasing. Finally, a few inequalities that give upper and lower bounds on the capacity are derived.
4
A Mathematical Theory of Communication
Claude E. Shannon · Bell System Technical Journal · 1948
78.4K citations
Information theory and statistics
Journal of the Franklin Institute · 1959
7.2K citations
Saburo Muroga · Journal of the Physical Society of Japan · 1953
70 citations
On the capacity of a discrete, constant channel
Bernd Meister, W. Oettli · Information and Control · 1967
39 citations