PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Bounds on the Probability of Undetected Error
V. I. Levenshtein
pp. 1–12

Abstract—New upper and lower bounds are obtained for the probability of undetected error for block codes in a binary symmetrical channel (BSC). These bounds improve the available bounds by a factor that increases exponentially with the block length $n$, provided that the transmission rate is fixed and does not exceed the capacity of the BSC. The resultant bounds are used to select the parameters of a quasioptimal code for transmission over a BSC with instantaneous and noiseless feedback.

Error Probability in a Channel with Fading and Signallike Noise
V. I. Korzhik and L. N. Smirnov
pp. 13–17

Abstract—It is shown that for a channel without fading there always exists an additive Gaussian noise for which the error probability for optimum reception of multifrequency signals is uniquely determined by the ratio of signal power to noise power and, when there is fading and arbitrary Gaussian noise in the channel, the error probability can be made arbitrarily small when the number of harmonic components of the signals is increased; this is accounted for by the random nature of the signal under fading.

On a Problem of Separate Coding of Two Dependent Sources
V. N. Koshelev
pp. 18–22

Abstract—The random-coding procedure is employed to solve the Slepian–Wolf problem of compression of information produced by two dependent sources. An upper bound for the error probability is determined and a general formula for an arbitrary finite number of sources is given.

Codes Associated with Divisors
V. D. Goppa
pp. 22–27

Abstract—The author introduces the concept of a linear code associated with a divisor on a field of algebraic functions. The volume (cardinality) and weight of such codes are evaluated by means of the Riemann–Roch theorem. Cyclic codes and $(L,g)$-codes are particular cases of the codes in question.

On Minimax Training of Signal Discrimination
V. A. Korado
pp. 27–41

Abstract—The article considers optimization of training and self-training of decision-making under conditions of a priori indeterminancy with a finite training-sample size and a minimax criterion. A solution is given for the problem of synthesizing locally minimax decision rules for discriminating between two constant signals with unknown amplitudes against a background of Gaussian noise with unknown variance when there are classified and unclassified training samples.

On Recursive Estimates of Probability Density and Regression Line
V. M. Buldakov and G. M. Koshkin
pp. 41–48

Abstract—Recursive estimates for the probability density and regression line are set up on the basis of nonparametric probability-density estimates of the Rosenblatt–Parzen type [Ann. Math. Stat., 33, No. 3, 1065–1076 (1965); 27, No. 3, 832–835 (1956)]; their asymptotic properties (as $n\to\infty$) are investigated, and, in particular, it is shown that they are asymptotically normal; results of statistical simulation of ordinary and recursive estimates of the regression line are given.

Lower Bound on the Risk for Spectral Density Estimates
A. M. Samarov
pp. 48–52

Abstract—The problem of estimating the spectral density of a stationary Gaussian random sequence is considered. A minimax lower bound on the risk for the spectral density estimates is obtained that is exact in order of magnitude as the number of observations increases.

Rates of Interaction Propagation in One-Dimensional Automaton Networks
G. A. Gal'perin
pp. 52–58

Abstract—This paper is a continuation of the author’s article “One-dimensional automaton networks with monotonic local interaction.” The author determines the values that the left and right rates $L_{a,b}$, $R_{a,b}$ ($0\le a,b\le n$) can assume, and also gives a way of computing them with a complexity corresponding to reality.

Lower Bound for the Redundancy of Self-correcting Arrangements of Unreliable Functional Elements
R. L. Dobrushin and S. I. Ortyukov
pp. 59–65

Abstract—Arrangements of unreliable functional elements are considered. It is assumed that all the elements misfunction independently of one another with probability $\varepsilon$. The redundancy of a self-correction arrangement that realizes some function is understood to mean the ratio of the number of elements (complexity) of a self-correcting arrangement of unreliable elements to the complexity of the arrangement of reliable elements that realizes the same function. It is shown that, for some functions, the redundancy of the self-correcting arrangements that realize them increases no more slowly than the logarithm of the complexity of the reliable-element arrangement.

Single-Line Queueing System with Absolute Priorities and a Limited Number of Interruptions
D. G. Mikhalev
pp. 65–69

Abstract—The article considers a single-line queueing system with many incoming flows that have absolute priority relative to one another. Only a restricted number of interruptions of low-priority requests by high-priority requests are permitted. Once the limiting number of interruptions is exceeded, an interrupted request leaves the system.

Analysis of a Queueing System with a Hyperexponential Input Flow
V. A. Popov, M. L. Litvinov, and A. L. Litvinov
pp. 70–73

Abstract—A queueing system with an arbitrarily distributed servicing time and second-order hyperexponential input flow is investigated. It is possible to approximate, with an adequate degree of accuracy, the input flows for which the coefficient of variation is greater than unity. Operating characteristics in the steady state are obtained.

New Bound for the Number of Signals in Binary Codes with Asymmetrical Error Correction
I. Ya. Gol'dbaum
pp. 74–76

Abstract—A new upper bound is obtained for the volume of binary codes that are capable of correcting from $1$ to $r$ errors of the form $1\to 0$. The bound is obtained as the approximate solution of a dual linear programming problem.

Optimum Queue Formation in Multichannel Queueing Systems with Indirect Observations
A. A. Nazarov
pp. 76–79

Abstract—The article considers a two-line queueing system with one incoming flow and a distributing device whose mode of operation is determined by indirect observations of the states of the system and whose task is to optimally allocate requests among servicing devices.

Note on the Article “Data Transmission over a Discrete Channel with Feedback. Random Transmission Time”
M. V. Burnashev
p. 80

Yu. L. Sagalovich. State Assignment and Reliability of Automata
Reviewed by O. P. Kuznetsov
pp. 81–82