Concepedia

An algorithm for computing the capacity of arbitrary discrete memoryless channels

S. Arimoto

IEEE Transactions on Information Theory · 1972 · 849 citations · 4 references

Concepts

TL;DR

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.

Abstract

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.

References

4