PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii


Volume 25, Number 4, October–December, 1989
Back to contents page

CONTENTS                   Powered by MathJax

 

Asymptotically Optimal Codes Correcting Memory Defects of Fixed Multiplicity
I.I. Dumer
pp. 259–265

Abstract—An asymptotically optimal class of codes of length $n\to\infty$ is proposed for correction of $t=\mathrm{const}$ defects. The length-$n$ code can be constructed in time $O(\log_2n)$, and its coding and decoding requires order of $n$ operations.

 

Quasiperfect Linear Binary Codes with Distance 4 and Complete Caps in Projective Geometry
A. A. Davydov and L. M. Tombak
pp. 265–275

Abstract—We prove that if a linear binary code with distance $d=4$ is quasiperfect (i.e., has a covering radius $2$) and the code length is $N\ge 2^{r-2}+2$, where $r$ is the number of check symbols, then the check matrix is symmetric in the following sense: the matrix columns may be partitioned into $N/2$ pairs so that the sum of the columns in each pair is constant. As a corollary, we derive all possible values of the length $N$ of a binary linear quasiperfect code with $d=4$ for $N\ge 2^{r-2}+1$ and construct all such nonequivalent codes for $N>2^{r-2}+2^{r-6}$. The results are extended to complete caps in the projective geometry $\operatorname{PG}(r-1,2)$.

 

$E$-Optimal Coding Rates of a Randomly Varying Source with Side Information at the Decoder
E. A. Haroutunian and R. Sh. Maroutian
pp. 276–284

Abstract—Upper and lower bounds are constructed on optimal code rates as a function of the given error exponent $E$ for a randomly varying source with an informed decoder. The following two cases are considered: (1) state information is delivered to the decoder coded at a given rate; (2) an accuracy criterion is specified for the reconstruction of coded messages, and the source states are completely known at the decoder.

 

Prediction of Stochastic Sequences
V. G. Vovk
pp. 285–296

Abstract—The following problem is considered: given the sequence $\omega_0\omega_1\dots\omega_{n-1}$, where $\omega_i\in\{0,1\}$, estimate the probability that $\omega_n=1$. It is assumed that the generating mechanism of the sequence $\omega_0\omega_1\dots\strut$ is sufficiently simple. Optimality of the estimators is investigated.

 

Upper Bound on the Capacity of a Packet Random Multiple Access System with Errors
B. S. Tsybakov and N. B. Likhanov
pp. 297–308

Abstract—We consider a random multiple access system with Poisson input and ternary feedback. An empty window and successful transmission may be erroneously interpreted as a collision. An upper bound is derived on the capacity of the system as a function of error probability.

 

Conflict Resolution in a Multiple Access Channel
L. S. Khasin
pp. 308–312

Abstract—Nonadaptive conflict-resolution algorithms for a multiple access channel are considered. A worst-case lower bound on the algorithm time is obtained, which coincides (up to a constant multiplier) with a well-known upper bound. A constructive technique for the design of nonadaptive algorithms is proposed. If the conflict multiplicity is fixed and the number of transmitting stations n tends to infinity, then an algorithm with minimal (up to a constant multiplier) worst-case time is constructed in almost linear time $O(n\log_2^3n)$.

 

Monotonicity Properties of Structurally Complex Switching Systems with Losses
G. I. Falin
pp. 313–321

Abstract—The paper describes some methods for obtaining stochastic bounds of structurally complex systems with losses. Semi-Markov models of partially accessible systems are considered in detail. The proposed bounds are simple for numerical calculations and sufficiently accurate in the medium and high traffic case.

 

Asymptotic Behavior of the Stationary Distribution for a Closed Queueing System
A. L. Stolyar
pp. 321–331

Abstract—We consider a closed queueing system consisting of $M$ identical servers with fixed unit service time. The number of customers is fixed and equal to $N$. Each served customer is instantaneously routed with equal probability to one of $M$ servers in the system (or is enqueued if the server is busy). An asymptotic result is proved for the stationary distribution of the queueing process as $N,M\to\infty$, $N/M\to\nu=\mathrm{const}$, and also a result on deterministic approximation of the process on a finite time interval.

 

Recursive Fourier Transform using Convolutions
Yu. I. Gagarin
pp. 332–334

Abstract—A new convolution-based fast transform algorithm is proposed with recursively updated coefficients.

 

Construction of Signature Codes and the Coin Weighing Problem
S. S. Martirosian and G. G. Khachatrian
pp. 334–335

Abstract—A recursive method is proposed for constructing signature codes of prescribed length.

 

Block Codes from Convolution Codes
B. D. Kudryashov and T. G. Zakharova
pp. 336–339

Abstract—An ensemble of linear codes obtained by truncation of convolution codes is considered. Bounds on decoding complexity are derived.

 

Likelihood Equations for Estimation of Parameters Determining the Covariance Matrix of Gaussian Sequences
E. G. Zhilyakov
pp. 340–343

Abstract—We prove a theorem which makes it possible to construct likelihood equations for the estimation of parameters determining the covariance matrix of one-dimensional Gaussian sequences. Relationships are derived for the Fisher information matrix and the probability density function of the estimators.

 

First-Approximation Stability for Discrete-Time Stochastic Systems
V. A. Lazarev
pp. 343–346

Abstract—We prove that for first-approximation stability of the trajectories of a nonlinear discrete-time Markov chain it is sufficient that the linearized system be asymptotically stable in probability, and some positive-order moment of the difference between the right-hand sides of the nonlinear and the linearized systems be small in a certain sense.

 

INDEX
pp. 347–353