RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Probl. Peredachi Inf.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Probl. Peredachi Inf., 1987, Volume 23, Issue 3, Pages 3–17 (Mi ppi811)  

This article is cited in 23 scientific papers (total in 23 papers)

Coding Theory

Universal Sequential Coding of Single Messages

Yu. M. Shtar'kov


Abstract: We define coding redundancy of single messages. A coding method is proposed which ensures a uniform bound on this redundancy for all messages on the output of a source with unknown statistical properties. Using the same criterion, we investigate the possibilities of sequential coding of messages, including messages on the output of a source with unknown statistical properties. Upper bounds on redundancy are obtained for memoryless sources, Markov chains, and various sets of Markov sources.

Full text: PDF file (1760 kB)

English version:
Problems of Information Transmission, 1987, 23:3, 175–186

Bibliographic databases:

UDC: 621.391.15
Received: 26.06.1985

Citation: Yu. M. Shtar'kov, “Universal Sequential Coding of Single Messages”, Probl. Peredachi Inf., 23:3 (1987), 3–17; Problems Inform. Transmission, 23:3 (1987), 175–186

Citation in format AMSBIB
\Bibitem{Sht87}
\by Yu.~M.~Shtar'kov
\paper Universal Sequential Coding of Single Messages
\jour Probl. Peredachi Inf.
\yr 1987
\vol 23
\issue 3
\pages 3--17
\mathnet{http://mi.mathnet.ru/ppi811}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=914346}
\zmath{https://zbmath.org/?q=an:0668.94005}
\transl
\jour Problems Inform. Transmission
\yr 1987
\vol 23
\issue 3
\pages 175--186


Linking options:
  • http://mi.mathnet.ru/eng/ppi811
  • http://mi.mathnet.ru/eng/ppi/v23/i3/p3

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. W. Szpankowski, “On Asymptotics of Certain Recurrences Arising in Universal Coding”, Problems Inform. Transmission, 34:2 (1998), 142–146  mathnet  mathscinet  zmath
    2. Yu. M. Shtar'kov, “Aim Functions and Sequential Estimation of the Source Model for Universal Coding”, Problems Inform. Transmission, 35:3 (1999), 275–285  mathnet  mathscinet  zmath
    3. Szpankowski, W, “Asymptotic average redundancy of Huffman (and other) block codes”, IEEE Transactions on Information Theory, 46:7 (2000), 2434  crossref  isi
    4. Yu. M. Shtar'kov, “Joint Matrix Universal Coding of Sequences of Independent Symbols”, Problems Inform. Transmission, 38:2 (2002), 154–165  mathnet  crossref  mathscinet  zmath
    5. Drmota, M, “Generalized Shannon code minimizes the maximal redundancy”, Latin 2002: Theoretical Informatics, 2286 (2002), 306  crossref  isi
    6. Flajolet, P, “Analytic variations on redundancy rates of renewal processes”, IEEE Transactions on Information Theory, 48:11 (2002), 2911  crossref  isi
    7. Drmota M., Hwang H.K., Szpankowski W., “Precise average redundancy of an idealized arithmetic coding”, Dcc 2002: Data Compression Conference, Proceedings, IEEE Data Compression Conference, 2002, 222–231  isi
    8. Jacquet P., Szpankowski W., “A combinatorial problem arising in information theory: Precise minimax redundancy for Markov sources”, Mathematics and Computer Science II - Algorithms, Trees, Combinatorics and Probabilities, Trends in Mathematics, 2002, 311–328  isi
    9. Yu. M. Shtar'kov, Tj. J. Tjalkens, F. M. J. Willems, “Optimal Universal Coding by the Maximum Individual Redundancy Criterion”, Problems Inform. Transmission, 40:1 (2004), 90–101  mathnet  crossref  mathscinet  zmath
    10. Drmota, M, “Precise minimax redundancy and regret”, IEEE Transactions on Information Theory, 50:11 (2004), 2686  crossref  isi
    11. Orlitsky, A, “Speaking of infinity”, IEEE Transactions on Information Theory, 50:10 (2004), 2215  crossref  isi
    12. Jacquet, P, “Markov types and minimax redundancy for Markov sources”, IEEE Transactions on Information Theory, 50:7 (2004), 1393  crossref  isi
    13. Orlitsky, A, “Universal compression of memoryless sources over unknown alphabets”, IEEE Transactions on Information Theory, 50:7 (2004), 1469  crossref  isi
    14. Meron, E, “Fiftite-memory universal prediction of individual sequences”, IEEE Transactions on Information Theory, 50:7 (2004), 1506  crossref  isi
    15. Jevtic, N, “A lower bound on compression of unknown alphabets”, Theoretical Computer Science, 332:1–3 (2005), 293  crossref  isi
    16. Dhulipala, AK, “Universal compression of Markov and related sources over arbitrary alphabets”, IEEE Transactions on Information Theory, 52:9 (2006), 4182  crossref  isi
    17. Boucheron, S, “Coding on Countably Infinite Alphabets”, IEEE Transactions on Information Theory, 55:1 (2009), 358  crossref  isi
    18. Szpankowski W., Weinberger M.J., “Minimax Redundancy for Large Alphabets”, 2010 IEEE International Symposium on Information Theory, IEEE International Symposium on Information Theory, 2010, 1488–1492  isi
    19. Szpankowski W., Weinberger M.J., “Minimax Pointwise Redundancy for Memoryless Models Over Large Alphabets”, IEEE Trans. Inf. Theory, 58:7 (2012), 4094–4104  crossref  isi
    20. Yu. M. Shtarkov, “Individual redundancy of adaptive and weighted source coding”, Problems Inform. Transmission, 49:4 (2013), 391–395  mathnet  crossref  isi
    21. Yu. M. Shtarkov, “Universal coding algorithm for a family of context Markov sources”, Problems Inform. Transmission, 50:3 (2014), 285–291  mathnet  crossref  isi
    22. B. D. Kudryashov, A. V. Porov, “Universal coding for memoryless sources with countably infinite alphabets”, Problems Inform. Transmission, 50:4 (2014), 390–399  mathnet  crossref  isi  elib
    23. Acharya J., Jafarpour A., Orlitsky A., Suresh A.T., “Poissonization and Universal Compression of Envelope Classes”, 2014 IEEE International Symposium on Information Theory (Isit), IEEE International Symposium on Information Theory, IEEE, 2014, 1872–1876, ISBN: 978-1-4799-5186-4  isi
  • Проблемы передачи информации Problems of Information Transmission
    Number of views:
    This page:1165
    Full text:450
    First page:3

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2017