Variable-Length Compression Allowing Errors

Article, Preprint OPEN
Kostina, Victoria; Polyanskiy, Yury; Verdú, Sergio;
(2015)

This paper studies the fundamental limits of the minimum average length of lossless and lossy variable-length compression, allowing a nonzero error probability $\epsilon$, for lossless compression. We give non-asymptotic bounds on the minimum average length in terms of ... View more
  • References (28)
    28 references, page 1 of 3

    [1] W. Szpankowski and S. Verdu´, “Minimum expected length of fixed-to-variable lossless compression without prefix constraints: memoryless sources,” IEEE Transactions on Information Theory, vol. 57, no. 7, pp. 4017-4025, 2011.

    [2] S. Verdu´ and I. Kontoyiannis, “Optimal lossless data compression: Non-asymptotics and asymptotics,” IEEE Transactions on Information Theory, vol. 60, no. 2, pp. 777-795, Feb. 2014.

    [3] N. Alon and A. Orlitsky, “A lower bound on the expected length of one-to-one codes,” IEEE Transactions on Information Theory, vol. 40, no. 5, pp. 1670-1672, 1994.

    [4] A. D. Wyner, “An upper bound on the entropy series,” Inf. Contr., vol. 20, no. 2, pp. 176-181, 1972.

    [5] T. S. Han, “Weak variable-length source coding,” IEEE Transactions on Information Theory, vol. 46, no. 4, pp. 1217-1226, 2000.

    [6] --, Information spectrum methods in information theory. Springer, Berlin, 2003.

    [7] H. Koga and H. Yamamoto, “Asymptotic properties on codeword lengths of an optimal fixed-to-variable code for general sources,” IEEE Transactions on Information Theory, vol. 51, no. 4, pp. 1546-1555, April 2005.

    [8] A. Kimura and T. Uyematsu, “Weak variable-length Slepian-Wolf coding with linked encoders for mixed sources,” IEEE Transactions on Information Theory, vol. 50, no. 1, pp. 183-193, 2004.

    [9] Y. Polyanskiy, H. V. Poor, and S. Verdu´, “Feedback in the non-asymptotic regime,” IEEE Transactions on Information Theory, vol. 57, no. 8, pp. 4903-4925, 2011.

    [10] H. Koga, “Source coding using families of universal hash functions,” IEEE Transactions on Information Theory, vol. 53, no. 9, pp. 3226-3233, Sep. 2007.

  • Related Organizations (1)
    Purdue University
    United States
    73%
  • Metrics
Share - Bookmark