PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Combinatorial Entropy of Images
J. Justesen and Yu. M. Shtarkov
pp. 1–8

Abstract—The definition of combinatorial entropy of images with deterministic restrictions on the values of brightness in elements of a two-dimensional lattice is given, which has an information-theoretic meaning of a lower bound of the coding rate of a combinatorial source. It is proved that this value exists for an arbitrary set of stationary deterministic restrictions.

On the Asymptotic Capacity of a Multiple-Access Channel
L. Wilhelmsson and K. Sh. Zigangirov
pp. 9–16

Abstract—The asymptotic capacity for the memoryless $T$-user $q$-ary noiseless channel is studied under the condition that $T\to \infty$ and $q\to \infty$. Both coordinated and uncoordinated transmission are considered. It is shown that for both cases the maximum capacity is achieved for $T = q \ln 2$. For the coordinated case, the total capacity for $T$ users is found to be $C_T \simeq q$, while for the uncoordinated case, $C_T \simeq q \ln 2$.

Multialphabet Weighting Universal Coding of Context Tree Sources
Yu. M. Shtarkov, Tj. J. Tjalkens, and F. M. J. Willems
pp. 17–28

Abstract—An algorithm of weighting universal coding of $M$-ary sources $(M\geq 2)$ with contexts of variable length is proposed. The estimates of its basic characteristics are derived. A modification of the algorithm is considered, which allows one to adapt to an unknown number of letters generated in each state.

On One Finite Matrix Group and Codes on Euclidean Spheres
V. M. Sidelnikov
pp. 29–44

Abstract—Starting from a finite group of orthogonal $2^n \times 2^n$ and $2p^n \times 2p^n$ matrices over the field of real numbers, we construct new orbit codes on a Euclidean sphere. Some of these codes have more than twice as many points as codes with the same code distance obtained by the standard procedure from second-order Reed–Muller codes.

Codes for the $m$-Metric
M. Yu. Rosenbloom and M. A. Tsfasman
pp. 45–52

Abstract—We introduce a new series of metrics on ${\Bbb F}_q^n$ generalizing the usual Hamming metric. We give some upper and lower bounds for the parameters of codes in these metrics, as well as simple constructions, including the algebraic geometry one.

Code-Generating Factorizations of the $n$-Dimensional Unit Cube and of Perfect Binary Codes
Yu. L. Vasil'ev and F. I. Solov'eva
pp. 53–61

Abstract—In the paper, an approach to constructing and studying perfect binary codes with distance 3 is introduced. This approach is to study their modifications, i.e., perfect codes with the same projection along a given coordinate, and is based on studying corresponding connection structures over an $n$-cube and their factorizations, which are called code-generating. Basic properties of the notions mentioned are presented. Examples of their application to the construction of rather extensive classes of perfect codes are given.

On the Propagation Criterion for Boolean Functions and on Bent Functions
V. V. Yashchenko
pp. 62–71

Abstract—We consider the parameters of a Boolean function that characterize its position relative to the first-order Reed–Muller code $R(1,n)$. We establish simple criteria of a given vector being, for a given Boolean function, unessential, a linear structure, or belonging to $\operatorname{PC}(f)$. We find conditions under which the set $\operatorname{PC}(f)$ contains some linear subspace (without zero). We show that the greater the dimension of the subspace, the more distant such functions are from $R(1,n)$. We obtain a new description of the class of bent functions most remote from $R(1,n)$.

The Euler Characteristic of the Minimal Code Trellis is Maximum
V. R. Sidorenko
pp. 72–77

Abstract—A class of separable block codes is defined. The class includes group and linear codes. A code trellis is called the minimal trellis if it has the minimum number of vertices $|V|$ (the order of code symbols is fixed). We show that the minimal trellis of a separable code minimizes the edge count $|E|$ and maximizes the Euler characteristic $|V|-|E|$. Thus, the Viterbi decoding complexity of a separable code is minimum when it is implemented on the minimal code trellis, since the Viterbi decoding algorithm requires $|E|$ additions and $|E|-|V|+1$ comparisons.

Asymptotically Efficient Signal Estimation in $L_2$ under General Loss Functions
A. B. Tsybakov
pp. 78–88

Abstract—The problem of nonparametric signal estimation in Gaussian white noise is considered. Asymptotics of the minimax $L_2$-risk on ellipsoids is obtained under nonquadratic loss functions.

On Realizability in the Algebra of Unreliable Generalized Contacts
V. V. Tarasov
pp. 89–93

Abstract—Fundamental problems of realizability of arbitrarily reliable contacts using unreliable ones are considered.