A New Lower Bound for Noisy Permutation Channels via Divergence Packing

Noisy permutation channels are applied in modeling biological storage systems and communication networks. For noisy permutation channels with strictly positive and full-rank square matrices, new achievability bounds are given in this paper, which are tighter than existing bounds. To derive this bound, we use the ϵ-packing with Kullback-Leibler divergence as a distance and introduce a novel way to illustrate the overlapping relationship of error events. This new bound shows analytically that for such a matrix <i>W</i>, the logarithm of the achievable code size with a given block <i>n</i> and error probability ϵ is closely approximated by ℓlogn-Φ-1(ϵ/G)+logV(W), where ℓ=rank(W)-1, G=2ℓ+12, and V(W) is a characteristic of the channel referred to as channel volume ratio. Our numerical results show that the new achievability bound significantly improves the lower bound of channel coding. Additionally, the Gaussian approximation can replace the complex computations of the new achievability bound over a wide range of relevant parameters.