Approximate simulation of communication channels with refined accuracy
Fine asymptotics for approximate simulation of symmetric channels
Information Theory
Summary
This paper looks at how well we can simulate communication channels with some allowed error and how big the codebook (set of codes) needs to be. The authors focus on a specific type of channel called Gallager-symmetric channels and improve previous estimates by adding finer detail called third-order terms. They find that the exact improvement depends on the channel type, with different behaviors for singular and nonsingular channels. Interestingly, the nature of this difference is reversed from what is known in channel coding.
What this means in practice
- •For communication system designers: Precisely estimate the minimum codebook size needed for approximate channel simulation under strict error constraints in symmetric channels.
- •For coding algorithm developers: Develop more accurate coding strategies by incorporating third-order asymptotic refinements to handle different channel types effectively.
A theory result. No direct application yet.
Authors
Valentinian Lungu, Aaron B. Wagner, Ioannis Kontoyiannis
Abstract
We study the approximate channel simulation problem in the normal approximation regime. Our starting point is the fact established by Cao et al.~\cite{Cao_channel_simulation}, that the minimal codebook size $M_ε^*(W)$ for a fixed error tolerance $ε>0$ is closely related to the $ε$-smooth channel max-information, $I_{\max}^ε(W)$. Using this, we refine earlier large-blocklength approximations to $M_ε^*(W^{\otimes n})$ for discrete memoryless channels. Specifically, we provide tight third-order expansions for Gallager-symmetric channels and demonstrate that the third-order term is channel-dependent. As in corresponding channel coding expansions, we identify a substantial rate gap between singular and nonsingular channels. Notably, the direction of this gap is reversed relative to channel coding: The third-order term is $-\frac{1}{2}\log n$ for singular channels but $O(\log\log n)$ for nonsingular channels.