Diskretnyi Analiz i Issledovanie Operatsii
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Guidelines for authors Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Diskretn. Anal. Issled. Oper.: Year: Volume: Issue: Page: Find

 Diskretn. Anal. Issled. Oper., Ser. 1, 1997, Volume 4, Issue 2, Pages 51–74 (Mi da393)

An efficient method for the randomization of messages based on arithmetic coding

A. N. Fionov

Siberian Academy of Telecommunications and Informatics

Abstract: We consider the problem of complete randomization of messages. This problem arises in cryptology during the construction of unconditionally stable codes with a secret key. One of the basic parameters of any randomization method is redundancy $r$, defined as the difference between the average length of a code word and the entropy for a source symbol. To obtain an arbitrarily low redundancy using the method from earlier papers of B. Ya. Ryabko and Fionov requires $O(1/r)$ memory and $O(\log^2(1/r)\log\log (1/r))$ coding and decoding time. In this paper we present a method for which the memory and time are defined as $O(\log(1/r))$ and $O(\log(1/r)\log\log(1/r)\log\log\log(1/r))$, respectively, as $r\to 0$. This method, however, uses subtantially more random symbols than the well-known methods.

Full text: PDF file (2257 kB)

Bibliographic databases:
UDC: 519.68

Citation: A. N. Fionov, “An efficient method for the randomization of messages based on arithmetic coding”, Diskretn. Anal. Issled. Oper., Ser. 1, 4:2 (1997), 51–74

Citation in format AMSBIB
\Bibitem{Fio97} \by A.~N.~Fionov \paper An efficient method for the randomization of messages based on arithmetic coding \jour Diskretn. Anal. Issled. Oper., Ser.~1 \yr 1997 \vol 4 \issue 2 \pages 51--74 \mathnet{http://mi.mathnet.ru/da393} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=1490448} \zmath{https://zbmath.org/?q=an:0930.94017}