Treffer: Rectangular Algorithm for Computing the Capacity of Arbitrary Discrete Memoryless Channels.

In information theory, the channel capacity is defined as the maximum of the transmission rate at which information can be conveyed reliably over a noisy channel. This paper presents a new algorithm for computing the capacity of discrete memoryless channels. The problem of determining the capacity is a concave programming. Thus it can be computed by solving a system of nonlinear equations termed the Kuhn-Tucker equations. Newton's method often is used to solve nonlinear equations. However, it does not have global convergence and may not converge when the starting point is not close to the solution. A globally convergent algorithm using simplicial subdivision has been proposed for the capacity evaluation, but it is very slow and cannot be applied to large-scale problems. In this paper, the Kuhn-Tucker equations are transformed into a system of equations with separable mappings by introducing auxiliary variables. This system of equations can be solved by a homotopy method using rectangular subdivision, which is much more efficient than the simplicial-type algorithm. Moreover, the proposed algorithm has quadratic convergence, so it converges rapidly similarly to Newton's method. The global convergence of the proposed algorithm is also proved herein. By numerical examples, it is shown that the proposed algorithm is more efficient than the well-known Arimoto algorithm. [ABSTRACT FROM AUTHOR]