 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Prikl. Diskr. Mat.: Year: Volume: Issue: Page: Find

 Personal entry: Login: Password: Save password Enter Forgotten password? Register

 Prikl. Diskr. Mat., 2020, Number 47, Pages 30–56 (Mi pdm693)  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.

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 30--56 \mathnet{http://mi.mathnet.ru/pdm693} \crossref{https://doi.org/10.17223/20710410/47/4} 

• http://mi.mathnet.ru/eng/pdm693
• http://mi.mathnet.ru/eng/pdm/y2020/i1/p30

 SHARE:      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  •  Contact us: math-net2021_09 [at] mi-ras ru Terms of Use Registration to the website Logotypes © Steklov Mathematical Institute RAS, 2021