PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

On the Reliability Function for a Quantum Communication Channel
M. V. Burnashev and A. S. Holevo
pp. 97–107

Abstract—Using random coding methods, lower estimates for the reliability function of a quantum channel with pure states are obtained. As a consequence, these estimates yield an alternative proof of a formula for the capacity of the channel. At zero rate, the precise value of the reliability function is found.

On Linear Programming Bounds for Codes in Polynomial Metric Spaces
P. Boyvalenkov and D. Danev
pp. 108–120

Abstract—We describe a general approach for studying the possibilities for improvements of the best known universal linear programming bounds on the cardinality and the minimum distance of codes in a polynomial metric space ${\cal M}$ (finite or infinite). We introduce functions $P_j({\cal M},s)$ having the property that $P_j({\cal M},s)\lt 0$ for some $j$ if and only if the universal linear programming bound $(1)$ can be improved by linear programming. A formula for $P_j({\cal M},s)$ depending on the zonal spherical functions (corresponding to ${\cal M}$) and $s$ is given. Applications in different polynomial metric spaces are considered with special emphasis on the Euclidean spheres and the binary Hamming space. Methods for obtaining new bounds (when $P_j({\cal M},s)\lt 0$ for some $j$) on the size of codes and the code distance are presented. An algorithm for computer calculations of $P_j({\cal M},s)$ is described.

Codes of the Reed–Muller Type on a Finite Abelian Group
O. A. Logachev and V. V. Yashchenko
pp. 121–133

Abstract—Codes of the Reed–Muller type are introduced with the help of certain sets of complex-valued functions on a finite Abelian group. In the case of an elementary Abelian 2-group, these are ordinary binary Reed–Muller codes. For codes of the Reed–Muller type, some of the algebraic properties well known for standard Reed–Muller codes are proved.

Construction of Efficient Literal Codes for Vocabulary Methods of Data Compression
E. I. Sitnyakovskaya
pp. 134–141

Abstract—We investigate how the efficiency of vocabulary methods of data compression depends on the literal codes they utilize. Known codesets and new ones based on them have been tested experimentally. As a result, best codes have been found, using which in the vocabulary methods makes it possible to achieve a compression rate close to the lower bound for the average codeword length.

On Asymptotics of Certain Recurrences Arising in Universal Coding
W. Szpankowski
pp. 142–146

Abstract—Ramanujan's $Q$-function, the Lambert $W$-function, and the so-called “tree function” $T(z)$ defined implicitly by the equation $T(z)=ze^{T(z)}$ have found applications in hashing, the birthday paradox problem, random mappings, caching, memory conflicts, and so forth. Recently, several novel applications of these functions to information theory problems such as linear coding and universal portfolios were brought to light. In this paper, we study them in the context of another information theory problem, namely, universal coding which was recently investigated by [Yu. M. Shtarkov et al., Probl. Inf. Trans., 31, No. 2, 114–127 (1995)]. We provide asymptotic expansions of certain recurrences studied there which describe the optimal redundancy of universal codes. Our methodology falls under the so-called analytical information theory, which was recently applied to a variety of problems of information theory.

On the Dissipation of Energy upon Classical Measurement and on the Relation Between Information and Entropy
L. I. Rozonoer
pp. 147–149

Abstract—We establish an inequality between the relative precision of a measurement and the dissipation of energy. Brillouin's principle of negentropy is discussed.

Nonlinear Filtering with Fractional Brownian Motion
M. L. Kleptsyna, P. E. Kloeden, and V. V. Anh
pp. 150–160

Abstract—A Kalman-type system of integral equations is obtained for a nonlinear filtering problem in which the noise generating the signal is a fractional Brownian motion with long-range dependence and the observational process appears in functional form in both the signal and observation equations.

Fast Wavelet Transform for Discrete Periodic Signals and Patterns
V. N. Malozemov, A. B. Pevnyi, and A. A. Tretyakov
pp. 161–168

Abstract—A simple wavelet transform for discrete periodic signals and patterns is constructed, which is different from the Haar transform. Computational formulas of decomposition and reconstruction are obtained.

Using Bases of Finite Functions in Problems of Filtering of a Priori Uncertain Time-Dependent Processes on Stochastic Spatial Fractals
V. V. Khutortsev
pp. 169–179

Abstract—We consider questions related to solving the problem of spatially differential filtering of a priori uncertain time-dependent processes on stochastic spatial manifolds (fractals), using bases of finite functions.

Large Queueing System where Messages are Transmitted via Several Routes
N. D. Vvedenskaya
pp. 180–189

Abstract—Let a system with $N$ servers be fed by a Poisson flow of rate $\lambda N$. Upon its arrival, a message is split into $n$ packets and each packet is sent to a randomly selected server independently of all other packets. The packet service time is distributed exponentially with mean $1$. It is shown that if $\rho=\lambda n <1$, then in the limit, as $N \to \infty$, the queue-length distribution at the servers tends to the queue-length distribution in an $M/M/1$ system with the input flow rate $\rho$. This permits one to conclude that if such a method of message transmission is used as the values of $\rho$ are small, the coding may speed up the delivery of messages. The case where a packet is formed by $M$ mini-packets and a mini-packet service time is distributed exponentially with mean $\displaystyle{1\over M}$ is also briefly considered. As $M\to \infty$, the waiting-time distribution in such a system tends to the waiting-time distribution in the $M/D/1$ system.

Engset Formulas for Nonhomogeneous Non-Markov Queueing Systems and Their Application in Communication Networks
A. A. Nazarov
pp. 190–196

Abstract—We consider a closed waiting-free queueing system (QS) with arbitrary distribution functions for the generating and servicing times of arrivals. The stationary probability distribution for the states of the system is found. Its various applications to communication networks are studied. In particular, Erlang problems are solved for different-type arrivals and for those that require a random number of servers in open systems. A channel-switching network is considered.

On Key and Message Equivocation in Secrecy Systems
Yu. M. Shtarkov, T. Johansson, and B. J. M. Smeets
pp. 197–206

Abstract—Two methods (including randomization) are studied for increasing the uncertainty concerning $n\geq 1$ transmitted messages and an applied key. Furthermore, it is shown that encryptions which perform equally well for $n=1$ may perform differently when $n\gt1$.