EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Statistics of the Compression Ratio of a Variable-to-Variable Code: Exact Moments and Asymptotic Behavior

Neri Merhav

Entropy · 10.08.2026 · 28 (8) · 898

DOI: 10.3390/e28080898 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Entropy, online erschienen am 10.08.2026. Verfasst von Neri Merhav. Beteiligte Einrichtung: The Viterbi Faculty of Electrical and Computer Engineering, Technion-Israel Institute of Technology, Technion City, Haifa 3200003, Israel. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 27 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A variable-to-variable (V2V) length code parses a source sequence into phrases of variable length and maps each phrase to a binary codeword of, generally, a different random length. After encoding n phrases, the realized compression ratio Rn=Λn/Σn—total codeword length over total source-symbol count—is the finite-sample counterpart of the code’s asymptotic rate ρ, to which it converges only as n→∞. This paper first derives exact formulas for all integer moments of Rn for a given discrete memoryless source (DMS). Specifically, we obtain a closed-form formula for every moment E{Rnk} as a one-dimensional integral involving only single-phrase moment generating functions of the pair (L,l)—the phrase length, in source symbols, and codeword length, in bits. From these moments we derive an Edgeworth approximation to the cumulative distribution function (CDF) of Rn that is substantially more accurate than the central limit theorem (CLT) approximation. Using the Laplace method of integration, we also derive explicit closed-form formulas for the bias constant C=limn→∞n(E{Rn}−ρ) and for the variance constant limn→∞n·Var{Rn}. The analysis extends to Markov sources via state-indexed matrices with a redundancy formula obtained in closed form. On the coding-theoretic side, we cast V2V length codes as finite-state encoders and apply a generalized Kraft inequality for a compression-rate lower bound, and give a structural decomposition of the bias coefficient that separates cleanly across variable-to-fixed (V2F) length codes, fixed-to-variable (F2V) length codes, and V2V length codes. Applied to the Khodak code of Bugeaud, Drmota, and Szpankowski, this decomposition shows that its improved performance is reflected in its smaller bias constant.

Schlagwörter

Stichwörter der Autor:innen

Edgeworth expansionMarkov sourcescompression ratioexact momentsfinite-length analysislarge deviationssource codingvariable-to-variable codes

Autor:innen und Institutionen

  • The Viterbi Faculty of Electrical and Computer Engineering, Technion-Israel Institute of Technology, Technion City, Haifa 3200003, Israel.

Zitieren

APA

Merhav, N. (2026). Statistics of the Compression Ratio of a Variable-to-Variable Code: Exact Moments and Asymptotic Behavior. Entropy, 28(8), 898. https://doi.org/10.3390/e28080898

Vancouver

Merhav N. Statistics of the Compression Ratio of a Variable-to-Variable Code: Exact Moments and Asymptotic Behavior. Entropy. 2026;28(8):898. doi:10.3390/e28080898

BibTeX
@article{Merhav2026,
  author = {Merhav, Neri},
  title = {Statistics of the Compression Ratio of a Variable-to-Variable Code: Exact Moments and Asymptotic Behavior},
  journal = {Entropy},
  year = {2026},
  volume = {28},
  number = {8},
  pages = {898},
  doi = {10.3390/e28080898}
}
Kostenlos starten →