Identification based on random coding

Abstract

Ahlswede and Dueck showed possibility to identify with high probability one out of $M$ messages by transmitting $1/C\log \log M$ bits only, where $C$ is the channel capacity. It is known that this identification can be based on error-correcting codes. We propose an identification procedure based on random codes that achieves channel capacity. Then we show that this procedure can be simplified using pseudo-random generators.