
HP Labs Technical Reports
Click here for full text:
Guessing Subject to Distortion
Merhav, Neri; Arikan, Erdal
HPL9648
Keyword(s): ratedistortion theory, fidelity criterion, source coding, guessing, source coding error exponent, side information
Abstract: We investigate the problem of guessing a random vector X within distortion level D. Our aim is to characterize the best attainable performance in the sense of minimizing, in some probabilistic sense, the number of required guesses G(X) until the error falls below D. The underlying motivation is that G(X) is the number of candidate code words to be examined by a ratedistortion block encoder until a satisfactory code word is found. In particular, for memoryless sources, we provide a singleletter characterization of the least achievable exponential growth rate of the pth moment of G(X) as the dimension of the random vector X grows without bound. In this context, we propose an asymptotically optimal guessing scheme that is universal both w.r.t the information source and the value of p. We then study some properties of the exponent functuion E(D,p) along with its relation to the source coding error exponent. Finally, we provide extensions of our main results to the Gaussian case, guessing with side information, and nonmemoryless sources.
Back to Index
