PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Optimal Rank Algorithms for Detecting Signals in Noise
A. F. Kushnir and B. R. Levin
pp. 1–12

Abstract—Methods are discussed for constructing rank algorithms for detecting signals in noise which ensure the least probability of false alarm when the noise distribution is changed. It is pointed out that under certain restrictions asymptotically optimal rank algorithms can be constructed for which the probability of detecting signals in a large sample space is close to the theoretical maximum.

Noise Immunity of the Optimal Coherent Reception of Frequency Spaced Signals in a Multipath Channel
M. A. Bykhovskii
pp. 13–21

Abstract—An analysis is made of a system of signal reception which measures the frequency characteristic of a multipath communication channel and uses the information obtained for optimal reception of frequency -spaced signals. It is established that the system under consideration and the “Rake” system [R. Price and P.E. Green, Proc. IRE, 1958, vol. 46, no. 3, pp. 555–570] possess the same noise immunity. At low information transmission rates the system with frequency-spaced signals has a number of practical advantages.

Coherent Spaced Reception in the Presence of Concentrated Interference
I. S. Andronov
pp. 22–28

Abstract—Decision rules and error probabilities are deduced for coherent spaced reception in the presence of fluctuation and concentrated interference in the form of slowly varying normal quasi-harmonic oscillations. It is proved that the use of an optimal decision circuit can virtually eliminate the effect of concentrated interference on the fidelity of reception.

Information Transmission Over a Binary Symmetrical Channel with Noiseless Feedback (Random Transmission Time)
K. Sh. Zigangirov
pp. 29–36

Abstract—This paper considers problems of transmitting information over a binary symmetrical channel without memory, but with feedback, in the form of finite and infinite sequences of independent and equiprobable binary symbols. The probability of correct decoding is determined. The transmission time is random.

The Relation Between Redundancy Coding and the Reliability of Information from a Source
R. E. Krichevskii
pp. 37–45

Abstract—This paper concerns a source generating independent letters with certain constant but unknown probabilities. These probabilities are discussed on the basis of an analysis of statistical data using Bayes’ rule. An asymptotic formula is found for the average redundancy of optimal coding which can be used by the statistical data.

On a Parallel Machine
Yu. P. Ofman
pp. 46–48

Abstract—In this paper we consider the structure and the instruction system of a parallel computer with several arithmetic units.

Methods of Introducing Redundancy for Raising the Reliability of a Finite Automaton
Yu. L. Sagalovich
pp. 49–57

Abstract—Various methods of introducing redundancy into a finite automaton for the purpose of raising its reliability are considered. The method of hammock-form circuits of Moore and Shannon is compared with the method of minimal bracket forms. We also compare the latter with the combinational method of symmetric lattices, which arises naturally in the noise-immune coding of the automaton states in connection with hammock-form circuits. Conditions are found under which one method is preferable to the other.

Some Variants of the Problem of Synchronization of Automata
V. I. Varshavskii, V. B. Marakhovskii, and V. A. Peschanskii
pp. 58–68

Abstract—Certain variations of the firing-squad synchronization problem posed by J. Myhill [E.F. Moore, The Firing Squad Synchronization Problem, in Sequential Machines, Reading, Mass., Addison-Wesley, 1964, pp. 213–214] are considered. The synchronization problem is solved for the case when the starting signal is given to an arbitrary automaton in the chain. It is shown that in this case the chain is synchronized within the time $2n-2-a_{\min}$, where $n$ is the length of the chain, and $a_{\min}$ is the minimum distance from the first automaton to the end of the chain. The obtained solution is a modification of the solution obtained by Levenshtein for the Myhill problem [Probl. Peredachi Inf., 1965, vol. 1, no. 4, pp. 20–32]; each of the automata has ten internal states. The existence of a solution is shown for the case when the objects to be synchronized have different firing times.

Regulation of Numbers in a Population of Dividing Cells
N. B. Vasil'ev, L. V. Levina, A. M. Leontovich, and I. I. Pyatetskii-Shapiro
pp. 69–75

Abstract—A study is made of the question of how long it is possible to keep within given limits the numbers of a population consisting of identical cells each of which lives for a finite time, makes the decision “to divide into two” or “to die” independently of the others, and makes this decision with some delay in time. “Feedback” consists of the fact that the probability of either decision depends on the state of the population as a whole at the time of the decision (the total number of cells present, their ages, etc.). Results are given of the computer simulation of some “natural” regulating mechanisms of this type.

The Computation on a Computer of the Channel Capacity of a Line with Symbol Drop-Out
N. D. Vvedenskaya and R. L. Dobrushin
pp. 76–79

Abstract—The channel capacity for the simplest model of a line with symbol drop-out is computed by the Monte Carlo method. The algorithm by which the channel capacity can be computed to within a few per cent is described.

The Limiting Form of the Bayesian Estimate of Regression Coefficients
F. G. Levit
pp. 79–82

Abstract—The limiting form of the Bayesian estimate of regression coefficients is presented in [B.R. Levin and Yu.S. Shinakov, Probl. Peredachi Inf., 1967, vol. 3, no. 1, pp. 27–34] for an unrestricted increase in the signal/noise ratio. In this note the existence of such a limiting form is proved for more general assumptions about the a priori distribution.

A Nonstationary Queueing Problem for a System with an Infinite Number of Channels for a Group Arrival of Requests
L. M. Abol'nikov
pp. 82–85

Abstract—A study is made of the nonstationary mode of functioning of a system with an infinite number of channels for requests arriving in groups (a group of requests of size $S$ arrives with probability $a_s$, $s= 1,2,3,\ldots\strut$). The instants of arrival of the groups have a Poisson distribution with the variable parameter $\lambda(t)$, an arbitrary differentiate function of $t$, and the serving time is exponentially distributed with parameter $\mu$. In these conditions the generating function $\Phi(t,x)$ of the probabilities of some particular number of requests to be served remaining in the system is found in explicit form, and also the function $p_0(t)$. The remaining $p_k(t)$ are defined recursively. The average number of channels $M(t)$ which are in service at the instant $t$ is found.