Third-order coding rate for universal compression of Markov sources
Nematollah Iri, Oliver Kosut · 2015
We consider the universal source coding problem for first-order stationary, irreducible and aperiodic Markov sources for short blocklengths. Achievability is derived based on the previously introduced algorithm for universal compression of memoryless sources in the finite blocklengths, the Type Size Code, which encodes strings based on type class size. We derive the third-order asymptotic coding rate of the Type Size code for this model class. We also present a converse on the third-order coding rate for the general class of fixed-to-variable codes and show the optimality of Type Size codes for such Markov sources.