PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Bounds on the Average Error Probability for a Code Ensemble with Fixed Composition
A. G. D'yachkov
pp. 255–259

Abstract—The author obtains the logarithmic asymptotic form of the average error probability over a code ensemble with fixed composition [R.M. Fano, Transmission of Information: A Statistical Theory of Communications, New York, MIT Press, 1961] for the case of decoding by a list of fixed length $L\ge 1$, for a discrete memoryless channel. The exponent of the error probability is represented in an analytic form analogous to that of the exponent of the spherical packing bound for codes with fixed composition introduced by E.A. Haroutunian in [Probl. Peredachi Inf., 1968, vol. 4, no. 4, pp. 37–48]. In the particular case $L=1$, corresponding to classical decoding this exponent coincides with the exponent of the upper bound proved by Fano.

Codes for an Adder Channel with Multiple Correlated Sources
V. N. Dyn'kin and A. P. Kurdyukov
pp. 260–265

Abstract—The article proposes a method of constructing codes for a transmission system incorporating three sources, two coders, a decoder, and a ternary adder channel. The transmission rate is estimated, and computational procedures that implement the coding and decoding algorithm are given.

Data Compression by Means of a “Book Stack”
B. Ya. Ryabko
pp. 265–269

Abstract—The article proposes a method of coding sources with finite memory, whose statistics are unknown. Unlike existing methods, it results in reduced redundancy in the case in which the source memory is larger than that of the coder and decoder.

Sampling Theorem for Random Processes and Fields
B. Kh. Barladian
pp. 270–281

Abstract—A generalization of the sampling theorem is obtained for random processes and fields with arbitrary spectral measures and sets on which the process or field is defined.

Estimation of the Drift Parameter of the Unobservable Component of Partially Observable Random Processes
S. Ya. Makhno
pp. 282–285

Abstract—The article considers the problem of estimating a parameter that appears in the drift of an unobservable process. An estimate is constructed for this parameter, and, under certain assumptions, it is shown that the estimate is consistent and asymptotically normal; the bias and standard deviation are determined.

On Uniform Convergence of Estimates of Multivariate Probability Density
V. G. Alekseev
pp. 286–289

Abstract—Statistical estimates of Rosenblatt–Parzen type for a multivariate probability density are considered. It is assumed that the probability density being estimated is a sufficiently smooth function. The use of this assumption makes it possible to construct estimates for a multivariate probability density that displace a high rate of uniform decrease of the estimation error with increasing sample size.

There Exist Reliable Circuits, Optimal with Respect to Order of Number of Elements, of Unreliable Functional Elements
A. P. Goryashko
pp. 290–296

Abstract—Assume that $\varphi_{\delta}^s(x_1,\ldots,x_k)$ is a Boolean function whose value is $0$ on binary combinations with weight $0,1,\ldots,]s-\delta k[$ and $1$ on binary combinations with weight $]s+\delta k[,\ldots,k-1,k$. On the remaining combinations the function $\varphi_{\delta}^s(x_1,\ldots,x_k)$ is not defined. It is shown that there exists a synthesis method that makes it possible to reliably implement, in a circuit of unreliable elements (with error probability $\varepsilon$ for each element $\le\varepsilon(\delta))$, any function $\varphi_{\delta}^s(x_1,\ldots,x_k)$ such that the number of elements of the resultant circuit does not exceed $c(\delta)k$, where $c(\delta)$ is independent of $k$.

Stochastic Model of Self-Assembly of Graphs
M. L. Tai
pp. 297–304

Abstract—The article proposes a statistical description of processes of self-assembly of graphs with cycles, loops, and multiple edges. For controlled Markov processes of self-assembly of trees with $n$ different vertices, an iterative representation of the state of the process is obtained in quadratures of the solution of a system of differential equations with $n-1$ unknowns. A spatial assumption is introduced, on the basis of which an iterative representation in quadratures is obtained for the state of the process of self-assembly of graphs with cycles, loops, and multiple edges.

Random Multiple Packet Access: Part-and-Try Algorithm
B. S. Tsybakov and V. A. Mikhailov
pp. 305–317

Abstract—The authors propose and investigate a new algorithm for random multiple access of packets to a channel with feedback. It is called a part-and-try algorithm and affords the possibility of translation at a rate $0.4877$ packets per unit time for finite delay.

On Almost-Decomposable Markov Chains and Their Applications
Ya. A. Kogan and G. G. Torosyan
pp. 317–322

Abstract—New results regarding the asymptotic behavior of stationary distributions of almost-decomposable Markov chains are presented. Models of behavior of programs and multiple-access systems of ALOHA type are considered as examples.

Integral Equilibrium Relations of Non-Full-Access Systems with Repeated Calls, and Their Applications
S. N. Stepanov
pp. 323–327

Abstract—Integral equilibrium relations are derived that link together the principal probability characteristics of non-full-access systems with repeated calls. The relations can be used to indirectly determine the values of the probability characteristics of the model whose measurement entails some difficulties.

INDEX
pp. 331–334

Asymptotically Optimal Batch Rearrangeable and Nonrearrangeable Switching Circuits
L. A. Bassalygo and M. S. Pinsker
pp. 94–98 (Russian issue)

Abstract—Unlike single switching circuits, where pairwise (single) connections of sites are established only, batch switching circuits allow one to establish connections between sites and groups of sites. We show how the former circuits can be used for constructing the latter ones, without a significant increase in the number of switching nodes.

Convolutional Codes as Subspaces of $GF(q)^w$
L. Staiger
pp. 99–101 (Russian issue)

Abstract—We give necessary and sufficient conditions for a subset of $GF(q)^w$ to form a convolutional code.

Integral Reception Procedures for Some Nonbinary Codes
V. V. Ginsburg
pp. 102–107 (Russian issue)

Abstract—We propose integral reception procedures for nonbinary codes with one parity-check equation and a system of divided parity-check equations.