PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Codes in the Vandermonde $\mathcal{F}$-Metric and Their Application
E. M. Gabidulin and V. A. Obernikhin
pp. 159–169

Abstract$\mathcal{F}$-metrics are metrics based on projective sets. In this paper, construction of optimal codes for a special $\mathcal{F}$-metric associated with a generalized Vandermonde matrix is given. Encoding and fast decoding algorithms are described. A public-key cryptosystem is considered as an example of a possible application of codes constructed.

On a Geometric Generalization of Entropy
V. A. Leus
pp. 170–177

Abstract—A new approach to the notion of a probability space is proposed. A stochastically measurable space is equipped with a geometric structure by introducing distances between elementary events. The probabilistic proximity space (in the discrete case) is used to generalize the notion of entropy. Entropy thus geometrized is shown to preserve all the former properties and also to acquire a previously unknown useful quality. This opens new possibilities in the area of information disciplines.

To the Metrical Rigidity of Binary Codes
S. V. Avgustinovich and F. I. Solov'eva
pp. 178–183

Abstract—A code $C$ in the $n$-dimensional metric space $E^n$ over $\operatorname{\it GF}(2)$ is called metrically rigid if each isometry $I\colon C\to E^n$ can be extended to an isometry of the whole space $E^n$. For $n$ large enough, metrical rigidity of any length-$n$ binary code that contains a $2$-$(n,k,\lambda)$-design is proved. The class of such codes includes, for instance, all families of uniformly packed codes of large enough lengths that satisfy the condition $d-\rho\ge2$, where $d$ is the code distance and $\rho$ is the covering radius.

New Quasi-cyclic Degenerate Linear Codes over $\operatorname{\it GF}(8)$
R. Daskalov and P. Hristov
pp. 184–190

Abstract—Let $[n,k,d]_q$ code be a linear code of length $n$, dimension $k$, and minimum Hamming distance $d$ over $\operatorname{\it GF}(q)$. One of the most important problems in coding theory is to construct codes with best possible minimum distances. Recently, quasi-cyclic (QC) codes were proved to contain many such codes. In this paper, twenty-five new codes over $\operatorname{\it GF}(8)$ are constructed, which improve the best known lower bounds on minimum distance.

On Optimal Linear Detectors, Asymptotic Efficiency, and Some CDMA Problems
M. V. Burnashev
pp. 191–206

Abstract—Necessary and sufficient conditions for a linear detector to be asymptotically optimal are given. In particular, it is shown that finding the asymptotically best linear detector and the largest asymptotic efficiency is a standard problem of convex analysis in Euclidean space, namely, finding the distance from a point to a convex set. As examples, decorrelating and conventional detectors are considered. In the case of randomly chosen CDMA signals, we show that, under certain conditions, the decorrelating detector is with high probability asymptotically optimal. This allows us to find the largest asymptotic efficiency of linear detectors for randomly chosen CDMA signals.

Adaptive $\chi^2$ Test for Discriminating between Close Hypotheses with a Large Number of Classes and Its Application to Some Cryptography Problems
B. Ya. Ryabko, V. S. Stognienko, and Yu. I. Shokin
pp. 207–215

Abstract—The main problem considered consists in testing the hypothesis $H_0$ that letters of an alphabet $A=\{a_1, a_2,\ldots,a_k\}$ are generated with equal probabilities $1/k$ against the alternative complex hypothesis $H_1$, the negation of $H_0$. In many applications, in particular, those connected with cryptography, $k$ is large, but possible deviations from the uniform distribution are small. Therefore, application of Pearson's $\chi^2$ test, which is one of the most wide-spread and efficient tests, requires samples of a very large size, certainly exceeding $k$. We propose a so-called adaptive $\chi^2$ test, whose power can be considerably higher than that of the traditional method in the case described. This conclusion is based on the theoretical analysis of the proposed criterion for some classes of alternatives as well as on experimental results related to discriminating between enciphered Russian texts and random sequences.

On Optimal Signal–Filter Pairs
V. N. Malozemov and K. Yu. Tsvetkov
pp. 216–226

Abstract—We extend the notion of an optimal signal–filter pair to the case where $n$-convolution is used instead of cyclic convolution. We construct $n$-optimal $n$-adic signals for all $n=2,3,\ldots\strut$.

Boolean Functions with Improper Parameters
V. V. Tarasov
pp. 227–230

Abstract—In this paper, Boolean functions $f(x_1,\ldots,x_n, z_1,\ldots,z_m)$ are considered, where $x_1,\ldots,x_n$ are ordinary Boolean variables and $z_1,\ldots,z_m$ are improper Boolean parameters, i.e., indicators of external factors. Algorithms for designing a circuit of functional elements that realizes an indicator $z\in\{z_1,\ldots,z_m\}$ are presented.