PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Error Exponents for Multi-Keyhole MIMO Channels
J. Xue, T. Ratnarajah, and C. Zhong
pp. 1–19

Abstract—Along with the channel capacity, the error exponent is one of the most important information-theoretic measures of reliability, because it sets ultimate bounds on the performance of communication systems employing codes of finite complexity. In this paper, we derive closed-form expressions for the Gallager random coding and expurgated error exponents for multi-keyhole multiple-input multiple-output (MIMO) channels, which provide insights into a fundamental tradeoff between the communication reliability and information rate. We investigate the effect of keyholes on the error exponents and cutoff rate. Moreover, without an extensive Monte-Carlo simulation we can easily compute the codeword length necessary to achieve a predefined error probability at a given rate, which quantifies the effects of the number of antennas, channel coherence time, and the number of keyholes. In addition, we derive exact closed-form expressions for the ergodic capacity and cutoff rate based on the easily computable Meijer $G$-function. Finally, we extend our study to Rayleigh-product MIMO channels and keyhole MIMO channels.

Codes for a Generalized Wire-Tap Channel Model
Yu. V. Kosolapov
pp. 20–24

Abstract—We consider a model of a wire-tap channel generalizing some previously known models. It is assumed that in a channel between two legal parties there can be errors, and an adversary is possible to observe both a part of a code vector and a part of the corresponding information vector.

Fractional Matchings in Hypergraphs
V. M. Blinovsky
pp. 25–30

Abstract—We find an exact formula for the minimum number of edges in a hypergraph which guarantees a fractional matching of cardinality $s$ in the case where $sn$ is an integer.

Phase Transitions in the One-Dimensional Coulomb Medium
V. A. Malyshev
pp. 31–36

Abstract—A Coulomb medium is a system of $N$ charged particles of equal charge on an interval with nearest-neighbor Coulomb interaction and constant external electric field. We show that, asymptotically as $N\to\infty$, stable configurations have four possible phases of the particle density depending on the external field, which is assumed to be a function of $N$. Moreover, we find these phases explicitly.

Generating Operator for Discrete Chrestenson Functions
M. S. Bespalov
pp. 37–48

Abstract—We study the structure and properties of and a construction algorithm for a cyclic operator whose orbit consists of discrete Chrestenson functions arranged as columns of the matrix of a Kronecker power of the discrete Fourier transform. We analyze possibilities for extending the results to the case of discrete Vilenkin functions.

Distributed Communication Complexity of Spanning Tree Construction
M. N. Vyalyi and I. M. Khuziev
pp. 49–65

Abstract—We consider the problem of constructing a spanning tree in a synchronized network with an unknown topology. We give lower and upper bounds on the complexity of protocols for spanning tree constriction in various settings: for deterministic and probabilistic protocols, networks with distinguishable nodes, and anonymous networks. We present suboptimal protocols for which the multiplicative gap from the lower bound can be an arbitrarily slowly growing function of the number of vertices in the network.

Activity Maxima in Some Models of Information Networks with Random Weights and Heavy Tails
A. V. Lebedev
pp. 66–74

Abstract—We consider models of information networks described by random graphs and hypergraphs where each node has a random information activity with distribution having a heavy (regularly varying) tail. We derive sufficient conditions under which the maximum of the aggregate activities (over a node and its neighbors or over communities) asymptotically grows in the same way as the maximum of individual activities and the Fréchet limit law holds for them.

A New Method for Ensuring Anonymity and Security in Network Coding
O. V. Trushina and E. M. Gabidulin
pp. 75–81

Abstract—We propose a method for providing anonymity and security of data transmission in networks with network coding with multiple sources and receivers. An external passive adversary is assumed to be present in the network. It is required to organize message transmission in such a manner that the adversary cannot trace a message route. The proposed method is a modification of a secure transmission scheme based on coset coding. We show that using an additional operation at relaying nodes enables to remove statistical dependence between incoming and outgoing messages of the relaying nodes. This makes tracing message routes impossible. An overlay network between a source and a receiver must be constructed due to restrictions on routes between the source and receiver: the minimum cut between two successive nodes must be not less than the number of packets in the encoded source message.

The Vernam Cipher Is Robust to Small Deviations from Randomness
B. Ya. Ryabko
pp. 82–86

Abstract—The Vernam cipher, or one-time pad, plays an important role in cryptography because it is perfectly secure. In this cipher a key is a sequence of equiprobable independently generated symbols. We show that under small disturbance of these properties the obtained cipher is close to the Vernam cipher in the case where the enciphered plaintext and the key are generated by stationary ergodic sources.