On the calculation of the minimax-converse of the channel coding problem
On the calculation of the minimax-converse of the channel coding problem
复制标题
信道编码问题极小极大逆的计算
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
M. Feder
中科院分区：
文献类型：
--
作者：
Nir Elkayam;M. Feder
针对一般信道编码问题[1]，提出了一种极小极大逆算法。这款匡威有两种口味。第一种风格通常用于分析错误概率不消失的编码问题，并在给定错误概率的情况下给出编码率的上界。第二种方法固定了错误率，并提供了错误概率的下限。这两个逆都是一个适当的二元假设检验问题的最小-最大优化问题。在[2]中研究了第一逆的性质，证明了一个鞍点。极大极小解也可以与随机编码结合使用，以实现“最佳”[3]编码性能。本文研究了第二种形式的性质，即速率固定时的性质。证明了鞍点解的充分必要条件。此外，还提出了一种鞍点的计算算法，从而给出了鞍点的界。在DMC情况下，算法在多项式时间内运行。
A minimax-converse has been suggested for the general channel coding problem [1]. This converse comes in two flavors. The first flavor is generally used for the analysis of the coding problem with non-vanishing error probability and provides an upper bound on the rate given the error probability. The second flavor fixes the rate and provides a lower bound on the error probability. Both converses are given as a min-max optimization problem of an appropriate binary hypothesis testing problem. The properties of the first converse were studies in [2] and a saddle point was proved. The minimax solution can also be used in conjunction with random coding to achieve “optimal” [3] coding performance. In this paper we study the properties of the second form, i.e. when the rate is fixed. Necessary and sufficient conditions on the saddle point solution are proved. Moreover, an algorithm for the computation of the saddle point, and hence the bound, is developed. In the DMC case, the algorithm runs in a polynomial time.