Multiple object Identification coding

Hirosuke Yamamoto and Masashi Ueda

IEEE Transactions on Information Theory, Vol. 61, No.8, pp.4269-4276, August 2015

In the case of ordinary identification coding, a code is devised to identify a single object among $N$ objects. But, in this paper, we consider a coding problem to identify $K$ objects at once among $N$ objects in the both cases that $K$ objects are ranked or not ranked. By combining Moulin-Koetter scheme with the $\varepsilon$-almost strongly universal class of hash functions used in Kurosawa-Yoshida scheme, an efficient and explicit coding scheme is proposed for $K$-multiple object identification ($K$- MOID) coding. Furthermore, it is shown that the $K$-MOID capacity $C_K$ -MOID , which is the maximum achievable coding rate in the $K$-MOID coding, is equal to the ordinary channel capacity, and the proposed scheme can attain $C_K$-MOID.

Index Terms : Identification coding, channel coding, multiple objects, passive feedback, common randomness.

Final submission version (PDF) (168 Kbytes)
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

DOI: 10.1109/TIT.2015.2441058