A New Lower Bound for Noisy Permutation Channels via Divergence Packing

Area of Science:

• Information Theory
• Coding Theory
• Applied Mathematics

Background:

• Noisy permutation channels are crucial for modeling biological storage and communication systems.
• Existing achievability bounds for these channels require improvement for practical applications.

Purpose of the Study:

• To derive new, tighter achievability bounds for noisy permutation channels with specific matrix properties.
• To provide an analytical expression for the achievable code size and explore computational approximations.

Main Methods:

• Utilized ϵ-packing with Kullback-Leibler divergence as a distance metric.
• Introduced a novel method to visualize the overlap of error events.
• Derived an analytical bound involving the channel matrix rank and a new 'channel volume ratio' characteristic.

Main Results:

• Established new, tighter achievability bounds for noisy permutation channels.
• The new bound is analytically expressed as log(code size) ≈ ℓlogn - Φ⁻¹(ϵ/G) + logV(W).
• Numerical results demonstrate significant improvement over existing lower bounds for channel coding.

Conclusions:

• The novel achievability bound offers a substantial enhancement for channel coding performance.
• A Gaussian approximation provides a computationally efficient alternative for complex calculations.
• The findings are applicable to systems employing noisy permutation channels, including biological storage and communication networks.