Simple Finite-Length Achievability and Converse Bounds for Deletion and Insertion Channels
IEEE Transactions on Communications · 2026 · 74 · 7716-7729
DOI: 10.1109/tcomm.2026.3681706 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Communications, 2026. Verfasst von Ruslan Morozov und 1 weiteren Autor:innen. Die Arbeit nennt 27 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: European Research Council.
Abstract (Originalsprache)
We develop upper bounds on code size for an independent and identically distributed deletion and insertion channels for a given code length and target frame error probability. The bounds are obtained as a variation of a general converse bound, which, though available for any channel, is inefficient and not easily computable without a good reference distribution over the output alphabet. We obtain a reference output distribution for a general finite-input finite-output channel and provide a simple formula for the converse bound on the capacity employing this distribution. We then evaluate the bound for the deletion channel with a finite block length, and show that the resulting upper bound on the code size is tighter than that for a binary erasure channel, which is the only alternative converse bound for the finite-length setting. We also provide similar results for the insertion channel. Furthermore, we present a simple algorithm for computing an achievability bound for a general discrete-input discrete-output channel. Although the algorithm has exponential complexity, it is useful for comparison purposes.
Förderung
- European Research Council
Zitieren
APA
Morozov, R., & Duman, T. M. (2026). Simple Finite-Length Achievability and Converse Bounds for Deletion and Insertion Channels. IEEE Transactions on Communications, 74, 7716-7729. https://doi.org/10.1109/tcomm.2026.3681706
Vancouver
Morozov R, Duman TM. Simple Finite-Length Achievability and Converse Bounds for Deletion and Insertion Channels. IEEE Transactions on Communications. 2026;74:7716-7729. doi:10.1109/tcomm.2026.3681706
BibTeX
@article{Morozov2026,
author = {Morozov, Ruslan and Duman, Tolga M.},
title = {Simple Finite-Length Achievability and Converse Bounds for Deletion and Insertion Channels},
journal = {IEEE Transactions on Communications},
year = {2026},
volume = {74},
pages = {7716--7729},
doi = {10.1109/tcomm.2026.3681706}
}
EUVIMED