|
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
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:
-
W. Szpankowski, “On Asymptotics of Certain Recurrences Arising in Universal Coding”, Problems Inform. Transmission, 34:2 (1998), 142–146
-
Yu. M. Shtar'kov, “Aim Functions and Sequential Estimation of the Source Model for Universal Coding”, Problems Inform. Transmission, 35:3 (1999), 275–285
-
Szpankowski, W, “Asymptotic average redundancy of Huffman (and other) block codes”, IEEE Transactions on Information Theory, 46:7 (2000), 2434
-
Yu. M. Shtar'kov, “Joint Matrix Universal Coding of Sequences of Independent Symbols”, Problems Inform. Transmission, 38:2 (2002), 154–165
-
Drmota, M, “Generalized Shannon code minimizes the maximal redundancy”, Latin 2002: Theoretical Informatics, 2286 (2002), 306
-
Flajolet, P, “Analytic variations on redundancy rates of renewal processes”, IEEE Transactions on Information Theory, 48:11 (2002), 2911
-
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
-
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
-
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
-
Drmota, M, “Precise minimax redundancy and regret”, IEEE Transactions on Information Theory, 50:11 (2004), 2686
-
Orlitsky, A, “Speaking of infinity”, IEEE Transactions on Information Theory, 50:10 (2004), 2215
-
Jacquet, P, “Markov types and minimax redundancy for Markov sources”, IEEE Transactions on Information Theory, 50:7 (2004), 1393
-
Orlitsky, A, “Universal compression of memoryless sources over unknown alphabets”, IEEE Transactions on Information Theory, 50:7 (2004), 1469
-
Meron, E, “Fiftite-memory universal prediction of individual sequences”, IEEE Transactions on Information Theory, 50:7 (2004), 1506
-
Jevtic, N, “A lower bound on compression of unknown alphabets”, Theoretical Computer Science, 332:1–3 (2005), 293
-
Dhulipala, AK, “Universal compression of Markov and related sources over arbitrary alphabets”, IEEE Transactions on Information Theory, 52:9 (2006), 4182
-
Boucheron, S, “Coding on Countably Infinite Alphabets”, IEEE Transactions on Information Theory, 55:1 (2009), 358
-
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
-
Szpankowski W., Weinberger M.J., “Minimax Pointwise Redundancy for Memoryless Models Over Large Alphabets”, IEEE Trans. Inf. Theory, 58:7 (2012), 4094–4104
-
Yu. M. Shtarkov, “Individual redundancy of adaptive and weighted source coding”, Problems Inform. Transmission, 49:4 (2013), 391–395
-
Yu. M. Shtarkov, “Universal coding algorithm for a family of context Markov sources”, Problems Inform. Transmission, 50:3 (2014), 285–291
-
B. D. Kudryashov, A. V. Porov, “Universal coding for memoryless sources with countably infinite alphabets”, Problems Inform. Transmission, 50:4 (2014), 390–399
-
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
|
Number of views: |
This page: | 1165 | Full text: | 450 | First page: | 3 |
|