A computation algorithm of the capacity of discrete memoryless channel with the input size larger than the output size

摘要

Computation of the channel capacity for the discrete memoryless channel is considered when the input size J being larger than the output size K. In this case the Arimoto-Brahut algorithm requires considerable iterations. However, the capacity is achieved by an input distribution which is supported on the set with the size at most K. Thus we propose a new algorithm in which the original capacity computation problem is separated into the one of smaller input size and the search problem of the support set. For the former problem we can employ Nakagawa-Kanaya algorithm to avoid long iterations and for the latter we rely on the computational geometry. We implement our algorithm and compare the running time with the Arimoto-Brahut algorithm and show the effectiveness for the channel of small output size.