PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

A Fast Method for Full Randomization of Messages
B. Ya. Ryabko and A. N. Fionov
pp. 191–201

Abstract—We consider the problem of homophonic coding (or full randomization) of source messages that arises in cryptography when provably secure secret-key systems are to be constructed. For the known methods of homophonic coding, the encoder and decoder memory grows exponentially as the redundancy $r$, which is defined as the difference between the average codeword length and the source entropy, tends to zero. We propose a method of homophonic coding for which the memory and the computing time grow, respectively, as $O(1/r)$ and $O(\log^21/r\log\log 1/r)$ as $r\to 0$.

Construction of Perfect Binary Codes by Sequential Shifts of $\alpha$-Components
S. V. Avgustinovich and F. I. Solov'eva
pp. 202–207

Abstract—We propose the construction of perfect binary codes by sequential shifts of special-kind components of the Hamming code. The construction yields a new lower estimate on the number of nonequivalent perfect binary codes. Some known constructions of perfect binary codes are particular cases of this one.

A Metric for Codes over Residue Class Rings
I. Constantinescu and W. Heise
pp. 208–213

Abstract—The Lee weight function $w\colon{\Bbb Z}_4 \rightarrow {\Bbb N}_0,\ 0 \mapsto 0,\ 1,3 \mapsto 1,\ 2 \mapsto 2$ used by Calderbank et al. ( IEEE Trans. Inf. Theory, IT-40, No. 2, 301–319 (1994)) for the representation of some nonlinear binary codes as linear codes over ${\Bbb Z}_4$ is generalized to the residue class ring ${\Bbb Z}_m$ of integers with an arbitrary modulus $m$. This generalized weight is a unique function having certain homogeneity properties, which are desirable for coding-theoretic purposes.

Decoding of Codes on an Elliptic Curve with Number of Errors Greater than Half the Designed Code Distance
A. Yu. Serebryakov
pp. 214–223

Abstract—The problem of decoding algebraic-geometric codes over an elliptic curve is considered, where the number of errors may exceed half the designed code distance (in particular, it may exceed half the minimum distance as well). This problem can be reduced to that of finding zeroes of a multivariate polynomial. A syndrome probabilistic decoding algorithm of depth $t$ is constructed.

Information Processing in the Class of Functions with Finite Spectrum
Yu. G. Bulychev and I. V. Burlai
pp. 224–232

Abstract—Problems of approximation, interpolation, and differentiation of information messages in the class of functions with finite spectrum are considered, and corresponding estimates of the errors brought about are obtained. Mathematical aspects of the optimal processing of information in the class of functions with finite spectrum, as well as problems of differentiation of messages given on a nonuniform interpolation grid, are considered.

Clutter Untyings, Correlation Inequalities, and Bounds for Combinatorial Reliability
V. P. Polesskii
pp. 233–250

Abstract—We consider the clutter approach to the theory of reliability of stochastic binary systems. We propose the clutter untying transformations that are special inversions to one of the factor clutter transformations introduced by McDiarmid. We show that the untying transformations underlie the correlation inequalities conceptually related with the ideas of Esary and Proshan that are basic for the theory of reliability of stochastic binary systems. We give new proofs for these correlation inequalities (and characterize the statistical independence of monotone events in terms of the supports of their clutters), using only the untying transformation and not invoking (which is the practice now) the FKG-inequality for distributive lattices. As to stochastic binary system reliability itself, we show that the untying transformations generate a class of new bounds for this reliability, which are tighter than the classical Esary–Proshan bounds. One of these bounds is formulated in terms of a clutter and an antiblocking set for this clutter.

On the Matrix Apparatus for Elementary Markov Fields
V. N. Koshelev and S. I. Stasevich
pp. 251–267

Abstract—We derive matrix expressions for the number of realizations of a binary field defined on edges of a rectangular lattice, in the nodes of which a certain interaction matrix is defined. Lattices of planar and cylindrical modifications are considered; upper and lower bounds on the information rate of a field for a given interaction model are discussed.

Queueing Networks with Several Demand Types, Immediate Service, and Node Bypassing by Demands
A. V. Krylenko
pp. 268–276

Abstract—We consider open networks with several demand types. Demands arrive at a node with probability depending on the node state and demand type and displace the demands being served. The displaced demands are queued at the same node or are moved instantly to another node according to a route matrix or leave the system. It is proved that the stationary distribution depends only on the mean service time and not on the type of its distribution.

Generalized Ideal Secret-Sharing Schemes and Matroids
G. R. Blakley and G. A. Kabatianski
pp. 277–284

Abstract—An axiomatic approach to secret-sharing schemes is proposed. This approach enables us to give a unified and more general proof of previously known results on the relationship between such schemes and matroids.

On the Development of Fundamental Research on Informational Interaction in Nature and Society
Academician N. A. Kuznetsov
pp. 285–286