Simple Finite-Length Achievability and Converse Bounds for the Deletion Channel and the Insertion Channel
Provides tighter finite-length converse bounds for deletion/insertion channels, which are important for coding theory but the improvement is incremental.
The authors develop tighter upper bounds on code size for finite-length deletion and insertion channels, improving over the binary erasure channel bound. They also provide a simple algorithm for achievability bounds, though with exponential complexity.
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.