Weak variable-length source coding

Given a general source X={Xⁿ}_n=1^∞ , source coding is characterized by a pair (φ_n, ψ_n) of encoder φ_n, and decoder ψ_n , together with the probability of error ε_n≡Pr{ψ_n(φ_n(Xⁿ ))≠Xⁿ}. If the length of the encoder output φ _n(Xⁿ) is fixed, then it is called fixed-length source coding, while if the length of the encoder output φ_n (Xⁿ) is variable, then it is called variable-length source coding. Usually, in the context of fixed-length source coding the probability of error ε_n is required to asymptotically vanish (i.e., lim_n→∞ε_n=0), whereas in the context of variable-length source coding the probability of error ε_n is required to be exactly zero (i.e., ε_n =0∀n=1, 2, ...). In contrast to these, we consider the problem of variable-length source coding with asymptotically vanishing probability of error (i.e., lim_n→∞ε_n =0), and establish several fundamental theorems on this new subject