On Universal Decoding over Discrete Additive Channels by Noise Guessing

We study universal decoding over unknown discrete additive channels. Aiming at low-complexity decoders, we study variants of noise-guessing decoders that use estimators for the probability of a noise sequence when the actual channel law is unknown. A deterministic version produces noise sequences in a fixed order, and a new randomised version draws them at random, until finding one that, subtracted from the received sequence, results in a valid codeword. In all cases, we give sufficient conditions on the family of parametric channels for the decoding strategies to be random-coding universal, and derive upper bounds for their complexity. We give examples of common families of channels in which these conditions are satisfied, and a numerical example illustrates the proposed method’s performance.