论文简报
cs.IT 2605.25699v1 必读

Finite-Blocklength Analysis for Noisy Permutation Channels

Lugaoze Feng, Guocheng Lv, Xunan Li., Ye Jin

发布日期：2026-05-25 10:57 相关性：1.0000 价值：0.8300 分类：cs.IT
arXiv 摘要 PDF 原文 网页正文

摘要

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.

相关性判断

high
相关方向
information_theory coding_theory communications
判断依据

Directly about finite-blocklength bounds, achievability/converse, and strong converse for noisy permutation channels in cs.IT, with explicit coding-theoretic and communications relevance.

价值判断

High relevance to cs.IT finite-blocklength analysis with both achievability and converse contributions. Addresses a specific gap for lower-dimensional reachable output polytopes and improves scaling from output-simplex dimension to affine dimension d. Structure evidence indicates substantial technical machinery: lattice construction, projection decoding, KL covering, modified meta-converse, and Gaussian approximation.

核心问题与主要方法

核心问题

Finite-blocklength bounds for noisy permutation channels when the reachable output polytope is lower-dimensional

场景：Finite-alphabet DMC followed by a random uniform permutation block; analysis is on the affine hull of the reachable output polytope with affine dimension d

主要方法

Constructs messages as simplex-lattice points in K_W=T^{-1}(P_W), so each message corresponds to a reachable output distribution q_u=T(u). Decoder maps the empirical output distribution through projection onto aff(P_W) and affine coordinates H=T^{-1} o Pi_A, then applies Euclidean nearest-neighbor decoding with ties counted as errors. Voronoi error reduction decomposes any competing lattice difference into zero-sum elementary transfers e_i-e_j, turning arbitrary nearest-neighbor errors into a union over d(d+1) one-dimensional transfer events. Achievability combines the transfer-event union bound with uniform Berry-Esseen approximation and Riemann-sum convergence over the lattice to obtain an averaged local-variance Gaussian coefficient. Converse uses a KL covering of the reachable polytope whose logarithmic size is controlled by affine dimension d and relative volume ratio lambda_W^*, then plugs it into a modified meta-converse plus a local binary-testing estimate.

关键贡献与后续阅读

关键贡献

Extends finite-blocklength noisy permutation channel analysis to cases where the reachable output polytope is lower-dimensional than the output simplex. Provides an affine-hull simplex-lattice achievability construction with a coordinate projection plus Euclidean nearest-neighbor decoder. Proves an error-reduction lemma showing nearest-neighbor errors can be controlled by d(d+1) elementary one-dimensional transfer events. Derives a refined Gaussian achievability lower bound using averaged local coordinate variances and the relative volume ratio lambda_W^*. Establishes a bounded-remainder fixed-error strong converse whose blocklength-dependent term scales with affine dimension d as d log sqrt(n), not the ambient output-simplex dimension. Connects achievability and converse to conclude epsilon-capacity scaling C_epsilon=d/2 for fixed epsilon in (0,1), under the stated assumptions.

研究启发

How tight is the bounded O_{W,epsilon}(1) converse remainder in concrete channels, and can it be made computable enough for finite-blocklength comparison? Does the minimum-volume reference simplex S_W^* have a practical construction or stable numerical procedure for general reachable polytopes? How sensitive is the refined Gaussian coefficient c_epsilon to the chosen affine coordinate representation and to boundary regions of K_W? Can the strict positivity assumption on W be weakened while preserving the local testing and uniform variance arguments?

限制与不确定性

Assessment is based on abstract and structure analysis only, not a full proof check. Impact may be niche because the setting is noisy permutation channels with finite alphabets and strictly positive DMCs. Some constants and bounded remainders appear not fully explicit from the provided evidence.

参考文献

27 条
  1. [1] J. H. Conway and N. J. A. Sloane (2013) Sphere packings, lattices and groups . Springer . Cited by: § III-C .
  2. [2] I. Csiszar and Z. Talata (2006-03) Context tree estimation for not necessarily finite memory processes, via BIC and MDL . IEEE Transactions on Information Theory 52 ( 3 ), pp. 1007–1016 . External Links: Document Cited by: § IV-A .
  3. [3] H. Davenport (1951) On a principle of lipschitz . Journal of the London Mathematical Society 1 ( 3 ), pp. 179–183 . Cited by: § III-A .
  4. [4] W. Feller (1971) An introduction to probability theory and its applications, vol. ii . 2nd edition , Wiley , New York, NY, USA . Cited by: §V .
  5. [5] L. Feng, X. Li, G. Lv, and Y. Jin (2025-06) New channel coding lower bounds for noisy permutation channels . In Proceedings of the IEEE International Symposium on Information Theory (ISIT) , Ann Arbor, MI, USA , pp. 1–6 . Cited by: §I , §I , § III-C , § VI-A , § VI-A , Remark 1 , Remark 5 .
  6. [6] L. Feng, G. Lv, X. Li, and Y. Jin (2025) A new lower bound for noisy permutation channels via divergence packing . Entropy 27 ( 11 ), pp. 1101 . External Links: Document Cited by: §I , §I .
  7. [7] L. Feng, B. Wang, G. Lv, X. Li, L. Wang, and Y. Jin (2025-09) New upper bounds for noisy permutation channels . IEEE Transactions on Communications 73 ( 9 ), pp. 7478–7492 . External Links: Document Cited by: §I , §I , § IV-C , §IV , § VI-A .
  8. [8] R. Heckel, I. Shomorony, K. Ramchandran, and D. N. C. Tse (2017-06) Fundamental limits of DNA storage systems . In Proc. IEEE Int. Symp. Inf. Theory (ISIT) , Aachen, Germany , pp. 3130–3134 . External Links: Document Cited by: §I .
  9. [9] H. M. Kiah, G. J. Puleo, and O. Milenkovic (2016) Codes for dna sequence profiles . IEEE Transactions on Information Theory 62 ( 6 ), pp. 3125–3146 . Cited by: §I .
  10. [10] M. Kovacevic and V. Y. F. Tan (2018-07) Codes in the space of multisets—coding for permutation channels with impairments . IEEE Transactions on Information Theory 64 ( 7 ), pp. 5156–5169 . External Links: Document Cited by: §I .
  11. [11] M. Kovačević and D. Vukobratović (2013-04) Subset codes for packet networks . IEEE Communications Letters 17 ( 4 ), pp. 729–732 . External Links: Document Cited by: §I .
  12. [12] M. Kovačević and D. Vukobratović (2015-04) Perfect codes in the discrete simplex . Designs, Codes and Cryptography 75 ( 1 ), pp. 81–95 . External Links: Document Cited by: §I .
  13. [13] W. Lu and A. Makur (2024) On permutation capacity regions of multiple-access channels . In 2024 IEEE International Symposium on Information Theory (ISIT) , pp. 3142–3147 . Cited by: §I .
  14. [14] W. Lu and A. Makur (2024) Permutation capacity region of adder multiple-access channels . IEEE Transactions on Information Theory 70 ( 7 ), pp. 4693–4720 . Cited by: §I .
  15. [15] J. MacLaren Walsh, S. Weber, and C. Wa Maina (2009-12) Optimal rate–delay tradeoffs and delay mitigating codes for multipath routed and network coded networks . IEEE Transactions on Information Theory 55 ( 12 ), pp. 5491–5510 . External Links: Document Cited by: §I , §I .
  16. [16] A. Makur (2020-06) Bounds on permutation channel capacity . In Proceedings of the IEEE International Symposium on Information Theory (ISIT) , Los Angeles, CA, USA , pp. 2026–2031 . External Links: Document Cited by: §I .
  17. [17] A. Makur (2020-11) Coding theorems for noisy permutation channels . IEEE Transactions on Information Theory 66 ( 11 ), pp. 6723–6748 . External Links: Document Cited by: §I , § III-D .
  18. [18] Y. Polyanskiy, H. V. Poor, and S. Verdú (2010-05) Channel coding rate in the finite blocklength regime . IEEE Transactions on Information Theory 56 ( 5 ), pp. 2307–2359 . External Links: Document Cited by: §IV .
  19. [19] Y. Polyanskiy (2013-05) Saddle point in the minimax converse for channel coding . IEEE Transactions on Information Theory 59 ( 5 ), pp. 2576–2595 . External Links: Document Cited by: §IV .
  20. [20] R. Schneider (1993) Convex bodies: the brunn–minkowski theory . Cambridge university press . Cited by: § IV-A .
  21. [21] J. Tang and Y. Polyanskiy (2023-07) Capacity of noisy permutation channels . IEEE Transactions on Information Theory 69 ( 7 ), pp. 4145–4162 . External Links: Document Cited by: §I , §I , § IV-C .
  22. [22] J. Tang (2021) Divergence covering . Ph.D. Thesis , Massachusetts Institute of Technology , Cambridge, MA, USA . Cited by: §IV , Remark 2 .
  23. [23] M. Tomamichel and V. Y. F. Tan (2013-11) A tight upper bound for the third-order asymptotics for most discrete memoryless channels . IEEE Transactions on Information Theory 59 ( 11 ), pp. 7041–7051 . External Links: Document Cited by: §IV .
  24. [24] L. Wang, R. Colbeck, and R. Renner (2009-06) Simple channel coding bounds . In Proceedings of the IEEE International Symposium on Information Theory (ISIT) , Seoul, South Korea , pp. 1804–1808 . External Links: Document Cited by: §IV .
  25. [25] Y. Yang and A. Barron (1999) Information-theoretic determination of minimax rates of convergence . The Annals of Statistics 27 ( 5 ), pp. 1564–1599 . External Links: Document Cited by: §IV .
  26. [26] S. M. H. T. Yazdi, H. M. Kiah, E. Garcia-Ruiz, J. Ma, H. Zhao, and O. Milenkovic (2015-09) DNA-Based Storage: Trends and Methods . IEEE Transactions on Molecular, Biological and Multi-Scale Communications 1 ( 3 ), pp. 230–248 ( en ). External Links: ISSN 2372-2061, 2332-7804 , Document Cited by: §I .
  27. [27] R. Zamir (2014) Lattice coding for signals and networks: a structured coding approach to quantization, modulation, and multiuser information theory . Cambridge University Press . Cited by: § III-C .

底部评论

0 条根评论，可继续回复叠楼

0/2000