Prikladnaya Diskretnaya Matematika
General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Prikl. Diskr. Mat.:

Personal entry:
Save password
Forgotten password?

Prikl. Diskr. Mat., 2020, Number 47, Pages 30–56 (Mi pdm693)  

This article is cited in 1 scientific paper (total in 1 paper)

Applied Coding Theory

Theoretically effective asymptotically optimal universal coding of partially defined sources

L. A. Sholomov

Federal Research Center “Computer Science and Control” of RAS, Moscow, Russia

Abstract: Let $A_0=\{a_i: i\in M\}$ be a finite alphabet of basic symbols, $A=\{a_T: T\in\mathcal{T}\}$, $\mathcal{T}\subseteq 2^M$, — an alphabet of underdetermined symbols. Any symbol $a_i$, $i\in T$, is considered to be a specification of the symbol $a_T$. The symbol $a_M$, denoted by $*$, is called indefinite. An underdetermined source $X$ generates symbols $a_T\in A$ independently with probabilities $p_T$. The entropy of the source $X$ is the quantity
$$ \mathcal{H}(X)= \min_Q(-\textstyle\sum\limits_{T\in\mathcal{T}} p_T\log\sum\limits_{i\in T}q_i), $$
where the minimum is taken over the set of probability vectors $Q=(q_i, i\in M)$, $\log x=\log_2x$. For source $X$, we consider separable block coding with a block length of $n$. Encoding $K$ of underdetermined words $v\in A^n$ should ensure that the code $K(v)$ of word $v$ allow one to recover some specification of $v$. Coding is universal if it is independent of the probabilities $p_T$, $T\in\mathcal{T}$. Characteristic of coding quality is average code length
$$ \bar l^{(n)}=\frac{1}{n}\textstyle\sum\limits_{v\in A^n}p(v)|K(v)|, $$
where $p(v)=p_{T_1}\ldots p_{T_n}$ is the probability of the appearance of the word $v=a_{T_1}\ldots a_{T_n}$ at the source output, $|K(v)|$ is the codeword length for $v$. Earlier, the author established that for arbitrary source $X$ and for any block coding method, the inequality $\bar l^{(n)}\ge\mathcal{H}(X)$ holds, and that there is universal block coding, for which $\bar l^{(n)}\le\mathcal{H}(X)+O(\dfrac{\log n}{n})$. The upper bound here is obtained by random coding which only establishes existence of the estimation, but does not provide an appropriate algorithm. Important for applications are issues of complexity of procedures. Coding method considered theoretically effective if the complexities of coding and decoding are estimated by a some polynomial of the size $n$ of problem. This paper presents a polynomial coding method for underdetermined sources whose alphabet has the form $A=A_0\cup\{*\}=\{a_0, a_1,\ldots,a_{m-1},*\}$. Such sources are called partially defined. For them, entropy can be explicitly expressed:
$$ \mathcal{H}(P)=(1-p_*)\log(1-p_*)-\textstyle\sum\limits_{i=0}^{m-1}p_i\log p_i. $$
The main content of the paper is the proof of the following result. For a partially defined source $X$, there is an universal method of block coding that provides an estimate of the average length of the code
$$ \bar l^{(n)}\le\mathcal{H}(P) + O(\frac{\log \log n}{\log^{1/2}n}) $$
and allows you to encode and decode using RAM-programs with complexity O$(n^2)$. An analogue of this result is also valid for other types of undetermined sources whose entropy is explicitly representable.

Keywords: underdetermined source, partially defined source, universal coding, polynomial method, source entropy, quasientropy of a word, frequency class, combinatorial entropy, representative set.


Full text: PDF file (824 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.728

Citation: L. A. Sholomov, “Theoretically effective asymptotically optimal universal coding of partially defined sources”, Prikl. Diskr. Mat., 2020, no. 47, 30–56

Citation in format AMSBIB
\by L.~A.~Sholomov
\paper Theoretically effective asymptotically optimal universal coding of partially defined sources
\jour Prikl. Diskr. Mat.
\yr 2020
\issue 47
\pages 30--56

Linking options:

    SHARE: FaceBook Twitter Livejournal

    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. L. A. Sholomov, “Polinomialnoe asimptoticheski optimalnoe kodirovanie nedoopredelennykh bernullievskikh istochnikov obschego vida”, Probl. peredachi inform., 56:4 (2020), 81–96  mathnet  crossref
  • Прикладная дискретная математика
    Number of views:
    This page:74
    Full text:17

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021