TY - GEN

T1 - Approximation theory of output statistics

AU - Han, Te Sun

AU - Verdu, Sergio

PY - 1993/1/1

Y1 - 1993/1/1

N2 - Given a channel and an input process we study the minimum randomness of those input processes whose output statistics approximate the original output statistics with arbitrary accuracy. We introduce the notion of resolvability of a channel, defined as the number of random bits required per channel use in order to generate an input that achieves arbitrarily accurate approximation of the output statistics for any given input process. We obtain a general formula for resolvability which holds regardless of the channel memory structure. We show that, for most channels, resolvability is equal to Shannon capacity. By-products of our analysis are a general formula for the minimum achievable (fixed-length) source coding rate of any finite-alphabet source, and a strong converse of the identification coding theorem, which holds for any channel that satisfies the strong converse of the channel coding theorem.

AB - Given a channel and an input process we study the minimum randomness of those input processes whose output statistics approximate the original output statistics with arbitrary accuracy. We introduce the notion of resolvability of a channel, defined as the number of random bits required per channel use in order to generate an input that achieves arbitrarily accurate approximation of the output statistics for any given input process. We obtain a general formula for resolvability which holds regardless of the channel memory structure. We show that, for most channels, resolvability is equal to Shannon capacity. By-products of our analysis are a general formula for the minimum achievable (fixed-length) source coding rate of any finite-alphabet source, and a strong converse of the identification coding theorem, which holds for any channel that satisfies the strong converse of the channel coding theorem.

UR - http://www.scopus.com/inward/record.url?scp=0027297485&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027297485&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0027297485

SN - 0780308786

T3 - Proceedings of the 1993 IEEE International Symposium on Information Theory

BT - Proceedings of the 1993 IEEE International Symposium on Information Theory

PB - Publ by IEEE

T2 - Proceedings of the 1993 IEEE International Symposium on Information Theory

Y2 - 17 January 1993 through 22 January 1993

ER -