
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_{m1},*\}$. Such sources are called partially defined. For them, entropy can be explicitly expressed: $$ \mathcal{H}(P)=(1p_*)\log(1p_*)\textstyle\sum\limits_{i=0}^{m1}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 RAMprograms 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.
DOI:
https://doi.org/10.17223/20710410/47/4
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
\Bibitem{Sho20}
\by L.~A.~Sholomov
\paper Theoretically effective asymptotically optimal universal coding of partially defined sources
\jour Prikl. Diskr. Mat.
\yr 2020
\issue 47
\pages 3056
\mathnet{http://mi.mathnet.ru/pdm693}
\crossref{https://doi.org/10.17223/20710410/47/4}
Linking options:
http://mi.mathnet.ru/eng/pdm693 http://mi.mathnet.ru/eng/pdm/y2020/i1/p30
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:

L. A. Sholomov, “Polinomialnoe asimptoticheski optimalnoe kodirovanie nedoopredelennykh bernullievskikh istochnikov obschego vida”, Probl. peredachi inform., 56:4 (2020), 81–96

Number of views: 
This page:  74  Full text:  17  References:  4 
