PROBLEMS OF INFORMATION TRANSMISSION

A translation of *Problemy Peredachi Informatsii*

Volume 33, Number 3, July–September, 1997

Back to contents page

**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