  We consider the topic of universal decoding with a decoder that does not have
direct access to the codebook, but only to noisy versions of the various
randomly generated codewords, a problem motivated by biometrical identification
systems. Both the source that generates the original (clean) codewords, and the
channel that corrupts them in generating the noisy codewords, as well as the
main channel for communicating the messages, are all modeled by non-unifilar,
finite-state systems (hidden Markov models). As in previous works on universal
decoding, here too, the average error probability of our proposed universal
decoder is shown to be as small as that of the optimal maximum likelihood (ML)
decoder, up to a multiplicative factorthat is a sub-exponential function of the
block length. It therefore has the same error exponent, whenever the ML decoder
has a positive error exponent. The universal decoding metric is based on
Lempel-Ziv (LZ) incremental parsing of each noisy codeword jointly with the
given channel output vector, but this metric is somewhat different from the one
proposed in earlier works on universal decoding for finite-state channels, by
Ziv (1985) and by Lapidoth and Ziv (1998). The reason for the difference is
that here, unlike in those earlier works, the probability distribution that
governs the (noisy) codewords is, in general, not uniform across its support.
This non-uniformity of the codeword distribution also makes our derivation more
challenging. Another reason for the more challenging analysis is the fact that
the effective induced channel between the noisy codeword of the transmitted
message and the main channel output is not a finite-state channel in general.
