Codes for Identification via Channels: Tutorial for Communications Generalists

Identification via channels (ID) is a communication problem in which a receiver tries to discern whether a received message matches a previously selected message. With identification, the receiver tries to answer the yes-no question “Is this my message?"; whereas, with message transmission, the receiver tries to answer the question “What message is this?", which has many possible answers. Information and coding theory show that for identification, specialized codes can achieve efficiency gains of an exponential order compared to full transmission of messages. This tutorial gives an introduction to identification via channels and to codes for identification via channels, for communication generalists with an interest in this traction-gaining topic. Specifically, a receiver can identify a message reliably from a received noisy-ID codeword. A noisy-ID codeword can be constructed by concatenating a linear block code that mitigates channel distortion with a noiseless-ID codeword that encodes a message efficiently for reliable identification. Noiseless-ID codes can be implemented as tagging codes or constant-weight codes that both guarantee low collision probabilities due to the distance properties of their underlying linear codes, such as Reed-Solomon codes, Reed-Muller codes, or random linear codes. We revisit and explain the close relationship between noiseless-ID codes and universal hash functions. ID is a ubiquitous communication problem and is relevant to all scenarios where two parties aim to determine whether two pieces of data are exactly identical. Specific non-cryptographic use cases include determining data integrity and state consistency in digital twins. While existing comprehensive tutorial treatments of ID are targeted at an information theory readership, we provide the first comprehensive ID tutorial targeted at a generalist readership without an information theory background by explaining the abstract ID concepts from basic principles with extensive illustrations and examples.