Finite-Blocklength Analysis for Noisy Permutation Channels
2026-05-25 • Information Theory
Information Theory
AI summaryⓘ
The authors study communication channels where the possible outputs form a shape that can be smaller or simpler than usual. They improve how to send messages by carefully placing them on a geometric structure and decoding by projecting received signals onto this shape, breaking down errors into simpler parts. Their method gives a better lower bound for how well messages can be sent, and they also provide a strong upper bound on performance that depends on the shape's dimension and the message length. Overall, they extend known results to more general and complex channel scenarios.
finite-blocklength boundsnoisy permutation channelsoutput polytopediscrete memoryless channel (DMC)achievability boundstrong converseaffine coordinatesKullback–Leibler divergenceGaussian approximationmeta-converse
Authors
Lugaoze Feng, Guocheng Lv, Xunan Li., Ye Jin
Abstract
We study finite-blocklength bounds for noisy permutation channels whose reachable output polytope may be lower-dimensional than the output simplex. Existing Gaussian achievability analyses focus on strictly positive full-rank square DMC transition matrices. The capacity result for arbitrary strictly positive DMCs is established through a weak converse, while available strong converse bounds in the lower-dimensional setting can scale with the dimension of the output simplex rather than with that of the reachable output polytope. On the achievability side, messages are placed on a simplex lattice in affine coordinates, and decoding is performed by projecting the empirical output distribution onto the reachable affine hull followed by Euclidean nearest-neighbor decoding. Writing $d$ for the affine dimension of the reachable output polytope, a geometric reduction converts decoding errors into $d(d+1)$ one-dimensional transfer events, yielding a refined Gaussian achievability lower bound based on averaged local coordinate variances and a relative volume ratio. On the converse side, a modified meta-converse, a Kullback--Leibler divergence covering, and a local binary-testing bound yield a strong converse whose blocklength-dependent term is $d\log\sqrt n$, up to a bounded additive remainder.