HP Labs Technical Reports

Hierarchical Guessing with a Fidelity Criterion

Merhav, Neri; Roth, Ron M.; Arikan, Erdal

HPL-97-09

Keyword(s): rate-distortion theory; successive refinement; guessing; source coding; error exponent

Abstract: In an earlier paper, we studied the problem of guessing a random vector X within distortion D, and characterized the best attainable exponent E(D,rho) of the rho-th moment of the number of required guesses G(X) until the guessing error falls below D. In this paper, we extend these results to a multi-stage, hierarchical guessing model, which allows for a faster search of a codeword vector at the encoder of a rate-distortion codebook. In the two-stage case of this model, if the target distortion level is D (sub 2), the guesser first makes guesses, directs the subsequent guesses w.r.t. (a higher) distortion level D (sub 1), and then, upon his/her first success, directs the subsequent guesses to distortion D (sub 2). As in the above mentioned earlier paper, we provide a single-letter characterization of the best attainable guessing exponent, which relies heavily on well-known results on the successive refinement problem. We also relate this guessing exponent function to the source coding error exponent function of the two-step coding process.

Back to Index