On-The-Fly Stochastic Codebook Re-generation for Sources with Memory

摘要

This paper proposes a generalized stochastic mechanism for codebook generation in lossy coding settings for sources with memory. Earlier work has shown that the rate-distortion bound can be asymptotically achieved for discrete memoryless sources by a "natural type selection" (NTS) algorithm. In iteration n, the distribution that is most likely to produce the types of a sequence of K codewords of finite length ℓ that "d-match" a respective sequence of K source words of length ℓ, (i.e., which satisfy the distortion constraint), is used to regenerate the codebook for iteration n+1. The resulting sequence of codebook generating distributions converges to the optimal distribution Q^{* that achieves the rate-distortion bound for the memoryless source, asymptotically in ℓ, K, and n. This work generalizes the NTS algorithm to account for sources with memory. The algorithm encodes mℓ-length source words consisting of ℓ vectors (or super-symbols) of length m. We show that for finite m and ℓ, the sequence of codebook reproduction distributions Q0,m,ℓ, Q1,m,ℓ, …(each computed after observing a sequence of K d-match events) converges to the optimal achievable distribution $Q_{m,ell }^{st}$ (within a set of achievable distributions determined by m and ℓ), asymptotically in K and n. It is further shown that $Q_{m,ell }^{st}$ converges to the optimal reproduction distribution Q∗ that achieves the rate-distortion bound for sources with memory, asymptotically in m and ℓ.}