CHANNEL CAPACITY FOR A GIVEN DECODING METRIC

For discrete memoryless channels {W : X --> Y}, we consider decoders, possibly suboptimal, which minimize metric defined additively by a given function d(x, y) greater than or equal to 0. The largest rate achievable by codes with such a decoder is called the d-capacity C-d(W). The choice d(x, y) = 0 if and only if (iff) W(y/x) > 0 makes C-d(W) equal to the ''zero undetected error'' or ''erasures-only'' capacity C-eo(W). The graph-theoretic concepts of Shannon capacity and Sperner capacity are also special cases of d-capacity, viz. for a noiseless channel with a suitable {0, 1}-valued function d. We show that the lower bound on d-capacity given previously by Csiszar and Korner and Hui, is not tight in general, but C-d(W) > 0 iff this bound is positive. The ''product space'' improvement of the lower bound is considered, and a ''product space characterization'' of C-eo(W) is obtained. We also determine the erasures-only (e.o.) capacity of a deterministic arbitrarily varying channel defined by a bipartite graph, and show that it equals capacity. We conclude with a list of challenging open problems.