arXiv:1404.5507 · IEEE International Symposium on Information Theory (ISIT)

Strong converse and second-order asymptotics of channel resolvability

Shun Watanabe, Masahito Hayashi

Published Jun 1, 2014• 36 citations

Abstract

We study the problem of channel resolvability for fixed i.i.d. input distributions and discrete memoryless channels (DMCs), and derive the strong converse theorem for any DMCs that are not necessarily full rank. We also derive the optimal second-order rate under a condition. Furthermore, under the condition that a DMC has the unique capacity achieving input distribution, we derive the optimal second-order rate of channel resolvability for the worst input distribution.

DOI: 10.1109/isit.2014.6875160

Related papers

Variable-Length Channel Resolvability for Discrete Memoryless Sources and Channels

Hideki Yagi, Te Sun Han

The problem of channel resolvability, where a given output probability distribution over a channel is approximated by encoding uniform random number as a channel input, is addressed. The channel resolvability has recently been generalized to the variable-length setting, where the variable-length uniform random number instead of the fixed-length one is encoded. Though the optimum resolvability rate can be reduced compared with the fixed-length resolvability, it is not yet clear how much resolvability rate can be saved even when the given source and channel are stationary and memoryless. Given a stationary memoryless source and a discrete memoryless channel, this paper establishes a single-letter formula for the variable-length resolvability under the variational distance as an approximation measure. When the channel is a full-rank discrete memoryless channel, the established formula reduces to a further simpler formula characterized by the mutual information between the source and the channel. The established formula also recovers a known formula for the variable-length source resolvability.

IEEE International Symposium on Information Theory (ISIT)Jun 1, 20180 citations

Separation of random number generation and resolvability

Karthik Visweswariah, Sanjeev R. Kulkarni, Sergio Verdú

We consider the problem of determining when a given source can be used to approximate the output due to any input to a given channel. We provide achievability and converse results for a general source and channel. For the special case of a full-rank discrete memoryless channel we give a stronger converse result than we can give for a general channel.

IEEE Transactions on Information TheoryJan 1, 200012 citations

Covert Capacity-Key Tradeoff Over Discrete Memoryless Networks

Abdelaziz Bounhar, Mireille Sarkiss, Michèle Wigger

This paper characterizes the covert capacity-key tradeoffs for discrete memoryless channels (DMC) and discrete memoryless multiple-access channels (DMMAC). The focus is on channels where communication rates are measured as the number of transmitted bits divided by the square-root of the blocklength and by the square-root of the covertness constraint. Previous results had determined the largest achievable covert rates for these channels, as well as the minimum key rates required to achieve these largest covert rates. In this work, we additionally determine the minimum key rates required at reduced covert rates. Stated differently, we determine the set of all covert rates that are achievable for a given set of key rates. This is termed thecovert capacity-key tradeoff. Our results on the covert capacity-key tradeoffs over DMCs and DMMACs show that for small key rates and when the adversary observes the inputs through a better channel than the legitimate receiver, binary signalling at all transmitters is optimal even for larger input alphabets and the capacity-key tradeoff grows linearly. Moreover, in this regime the covert capacity-key tradeoff of DMMACs is square implying that each of the transmitters can simultaneously achieve its own largest covert rate depending only on its own available key rate, irrespective of the other transmitter. For larger key rates or when the adversary is not uniformly stronger than the legitimate receiver over all inputs, the covert capacity-key tradeoff region of DMMACs is non-square and a tradeoff arises between the rates of the various transmitters.

IEEE Journal on Selected Areas in Information TheoryJan 1, 20260 citations

Resolvability of Classical-Quantum Channels

Masahito Hayashi, Hao–Chung Cheng, Li Gao

Channel resolvability concerns the minimum resolution for approximating the channel output. We study the resolvability of classical-quantum channels in two settings, for the channel output generated from the worst input, and from the fixed independent and identically distributed (i.i.d.) input. The direct part of the worst-input setting is derived from sequential hypothesis testing as it involves non-i.i.d. inputs. The strong converse of the worst-input setting is obtained via the connection to identification codes. For the fixed-input setting, while the direct part follows from the known quantum soft covering result, we exploit the recent alternative quantum Sanov theorem to prove the strong converse.

arXiv:2410.16704IEEE Transactions on Information TheoryMay 15, 20256 citations

Approximation Theory of Output Statistics

Te Sun Han, S. Verdu

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.

IEEE International Symposium on Information Theory (ISIT)Aug 24, 20051 citation

Exact Second-Order Asymptotics for Covert Communication over DMCs with Variational Distance Constraints

Qiaosheng Zhang, Lin Zhou, Xuelong Li

We determine the exact second-order asymptotics of covert communication over binary-input discrete memoryless channels when covertness is measured by variational distance. Previous work by Tahmasbi and Bloch [IEEE Trans. Inf. Theory, Apr. 2019] characterized the first-order asymptotics and derived achievability and converse bounds on the second-order term, but these bounds do not match. The gap arises from an additional penalty of order n^{1/4} in the achievability bound. We show that this penalty can be removed through a sharper analysis of the distribution of the warden's output induced by pulse-position modulation. Specifically, we express the variational distance through the Bhattacharyya coefficient of two distributions and the expectation of a continuous function of the log-likelihood ratio. Because the resulting expectation involves a continuous function rather than the probability of a likelihood-ratio event, an analysis of the characteristic function combined with a Gaussian smoothing argument reduces the approximation error from O(n^{-1/4}) (derived from the Berry--Esseen bound in prior work) to O(n^{-1/2}). With this better controlled approximation error, we manage to derive a matching achievability result to the existing converse result, thus establishing the exact second-order asymptotics.

arXiv:2609.24675Sep 21, 20260 citations