Hierarchical Guessing with a Fidelity Criterion

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

HP Development Company

关键词: rate-distortion theory;    successive refinement;    guessing;    source coding;    error exponent;   

RP-ID  :  HPL-97-09

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

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.