2024/06/21 by Lugaoze Feng, Baoji Wang, Feng, Lugaoze +9
Computer Science · Engineering · #Coding theory and cryptography #FOS: Computer and information sciences #Information Theory (cs.IT) #Wireless Communication Security Techniques #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2406.15031
openalex publication_date 2024/06/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The noisy permutation channel is a useful abstraction introduced by Makur for point-to-point communication networks and biological storage. While the asymptotic capacity results exist for this model, the characterization of the second-order asymptotics is not available. Therefore, we analyze the converse bounds for the noisy permutation channel in the finite blocklength regime. To do this, we present a modified minimax meta-converse for noisy permutation channels by symbol relaxation. To derive the second-order asymptotics of the converse bound, we propose a way to use divergence covering in analysis. It enables the observation of the second-order asymptotics and the strong converse via Berry-Esseen type bounds. These two conclusions hold for noisy permutation channels with strictly positive matrices (entry-wise). In addition, we obtain computable bounds for the noisy permutation channel with the binary symmetric channel (BSC), including the original computable converse bound based on the modified minimax meta-converse, the asymptotic expansion derived from our subset covering technique, and the ε-capacity result. We find that a smaller crossover probability provides a higher upper bound for a fixed finite blocklength, although the ε-capacity is agnostic to the BSC parameter. Finally, numerical results show that the normal approximation shows remarkable precision, and our new converse bound is stronger than previous bounds.