PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

Volume 23, Number 3, July–September, 1987
Back to contents page

CONTENTS

Universal Sequential Coding of Single Messages
Yu. M. Shtar'kov
pp. 175–186

Abstract—We define coding redundancy of single messages. A coding method is proposed which ensures a uniform bound on this redundancy for all messages on the output of a source with unknown statistical properties. Using the same criterion, we investigate the possibilities of sequential coding of messages, including messages on the output of a source with unknown statistical properties. Upper bounds on redundancy are obtained for memoryless sources, Markov chains, and various sets of Markov sources.

Modulation/Coding System for a Gaussian Channel
V. V. Zyablov and S. L. Portnoy
pp. 187–193

Abstract—We consider a modulation/coding system for a memoryless Gaussian channel. As in some known systems, the inner stage uses phase modulation or amplitude/phase modulation signals, and the outer stage uses binary error-correcting codes. The system partitions the given signal set into subsets with mapping of subsets by Gray code. Various finite-dimensional modulation/coding systems have been constructed, showing substantial coding-rate gains with known systems. The asymptotic properties of the system are also examined.

Nonparametric Estimation of Functionals of the Derivatives of a Signal Observed in White Gaussian Noise
A. S. Nemirovskii and R. Z. Khas'minskii
pp. 194–203

Abstract—We consider the estimation of an integral functional of the signal $S$ and its derivatives up to order $p_m$ when the observable quantity is the result of transmission of $S$ through a communication channel with white Gaussian noise of low intensity $\varepsilon^2$. Nonparametric estimators of $S$ and $S^{(k)}$ in this case are known to have variance $\Delta^2\gg\varepsilon^2$. Yet a differentiable functional $F$ often may be estimated asymptotically efficiently with $\Delta^2\asymp\varepsilon^2$. We obtain nearly necessary conditions on the a priori known smoothness of the signal $\beta$, the smoothness of the derivative of the functional $\gamma$ and $p_m$ that ensure asymptotically (for $\varepsilon \to 0$) efficient estimation of $F$. The form of this estimator is given.

Optimal Detection of Random-Length Signals
A. G. Tartakovskii
pp. 203–210

Abstract—We consider the problem of detection of a random-length signal by observations in discrete and continuous time. Algorithms are proposed to generate the likelihood ratio averaged over the signal length distribution, and these algorithms are incorporated in an optimal detection system. Sufficient statistics are determined for the sequential detection problem.

Symmetry Properties of High-Order Spectral Densities of Stationary and Periodic-Nonstationary Stochastic Processes
V. G. Alekseev
pp. 210–215

Abstract—We investigate the symmetry properties of spectral densities of orders $\nu=\overline{2,6}$ of a periodic-nonstationary stochastic process $\xi(t)$, $T\in\mathbb R$. In parallel, we describe the symmetry properties of the high-order spectral densities of stationary stochastic processes in discrete and continuous time.

Analysis of Overflow in Circuit Switching Networks
G. P. Basharin and B. E. Kurenkov
pp. 216–223

Abstract—We examine analytical methods for the investigation of partially available stepwise activation systems with and without pulling. For partially available systems without pulling, a new approximate method is proposed, generalizing Hayward's method from one to several overflow streams and suitable for calculation of the individual lost call probabilities. The results may be applied to calculation and optimization of circuit switching networks. Some numerical examples are given.

Upper Bound on the Capacity of a Random Multiple-Access System
B. S. Tsybakov and N. B. Likhanov
pp. 224–236

Abstract—An upper bound $C\le 0.568$ is obtained for the capacity $C$ of a random multiple-access system. This is an improvement on the best of the known bounds proved by Tszan and Berger [Probl. Peredachi Inf., 1985, vol. 21, no. 4, pp. 83–87].

Obstacles to Partitioning a Graph into Trees
V. P. Polesskii
pp. 236–249

Abstract—We formulate a class of combinatorial problems about the trees of a graph, which arise in connection with algorithms processing group requests to transmit information in a network. The problem of polar packing of reciprocal trees is solved. A conjecture of minimal partitioning of a graph into trees is stated and justified. A lower bound is established on the number of trees into which a graph can be partitioned. A technique for partitioning a graph into trees is developed. This tech-technique is applied to prove the conjecture for one class of graphs.

BRIEF COMMUNICATIONS
(available in Russian only)

A Method of Approximation of a Functional Dependence from Expert Evaluations
V. G. Gitis
pp. 94–100 (Russian issue)

Abstract—We present a method for reconstructing a function from observations where function values at sample points are evaluated by experts according to some rate scale. A statistical model of the function parameter estimation is introduced and statistical properties of estimates are analyzed. An example is considered.

On Primitive Polynomials
I. E. Shparlinskii
pp. 100–103 (Russian issue)

Abstract—We prove the existence of primitive polynomials of degree $n$ over the field $\operatorname{\it GF}(2)$ with at most $n/4+o(n)$ nonzero coefficients.