2024/12/15 by Sarkar, Abhishek, Dey, Bikash Kumar
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2412.11091
We study message identification over the noisy permutation channel. For discrete memoryless channels (DMCs), the number of identifiable messages grows doubly exponentially, and the maximum second-order exponent is same as the Shannon capacity of the DMC. We consider a q-ary noisy permutation channel where the transmitted vector is first permuted by a permutation chosen uniformly at random, and then passed through a DMC with strictly positive entries in its transition probability matrix U. In an earlier work, we showed that over q-ary noiseless permutation channel, 2^cn nq-1 messages can be identified if cn→ 0, and a strong converse holds for 2^cn nq-1 messages if cn→ ∞. For the q-ary noisy permutation channel, we show that message sizes growing as 2^Rn ( (n)/(log n))(r-1)/2, where r be the rank of U, are identifiable for any Rn→ 0. We also prove a strong converse result showing that for any sequence of identification codes with 2^(Rn n(q-1)/2(log n)1+((q-1)(q-2))/(2)), messages, where Rn → ∞, the sum of Type-I and Type-II error probabilities approaches at least 1 as n→ ∞. Our converse proof uses the idea of channel resolvability. We propose a novel deterministic quantization scheme for quantization of a distribution over the set of all compositions/types by an M-type input distribution when the distortion is measured on the output distribution in total variation distance. This plays a key role in the converse proof. We have also studied identification with deterministic encoder and decoder, and proved tight achievability, weak converse, and strong converse.