PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Information Rates in Stationary Gaussian Channels in Weak Signal Transmission
M. S. Pinsker and V. V. Prelov
pp. 291–298

Abstract—Let $N=\{N_i\}$ and $Z=\{Z_i\}$ be arbitrary independent discrete-time stationary processes. If $N$ is a regular Gaussian process and $Z$ is a process with completely positive entropy, we prove that the information rate $\bar I(Z;N+\theta Z)=\bar I(\bar Z;N+\theta\bar Z)+o(\theta^2)$, $\theta\to 0$, where $\bar Z=\{\bar Z_i\}$ is a Gaussian stationary process with the same autocorrelation function as $Z$. As a corollary, some generalizations of the results of [1, 2] concerning the sensitivities of the channel capacity and the $\varepsilon$-entropy are obtained, which allow one to omit the regularity assumption of $Z$ (in the case of the $\varepsilon$-entropy we can also omit the assumption of regularity of $N$ and remove all previous conditions on the spectral densities of $N$ and $Z$).

Constant-Weight Codes Correcting One Known Error
V. S. Lebedev
pp. 299–302

Abstract—We introduce the concept of constant weight codes correcting known errors. An exact value of the efficiency of a code of weight one is derived when there is one error in the binary channel. An upper bound for the weight $w\gt1$ is derived.

A New Construction of Partial Unit Memory Codes Based on Reed–Solomon Codes
U. K. Sorger
pp. 303–306

Abstract—In this paper we describe a novel construction of (P)UM codes based on RS codes. These codes attain a higher increase of the extended row distance $\alpha$ with the same free distance as the codes derived from the original construction. The basic idea is to allow dependent rows in the generator matrices. These dependent rows are then organized in a special way. The codes that we construct have the following parameters: length $N$, rate $N- d_\infty /2$, free distance $d_\infty$, and $\alpha \geq d_\infty/8$. The construction is easily generalized. Moreover, these codes can be decoded up to half this designed extended row distance.

Asymptotically Optimal Codes Correcting Multiple Localized Bursts
P. Larsson
pp. 307–309

Abstract—We consider codes correcting localized errors. It is assumed that the errors occur in the form of multiple bursts. A code construction is given which asymptotically meets the trivial upper bound.

Key Distribution System Based on Exponential Representations of Linear Group $\operatorname{\it GL}_n({\Bbb F}_p)$
V. M. Sidelnikov
pp. 310–316

Abstract—The first key distribution system was suggested by Diffie and Hellman [IEEE Trans. Inf. Theory, 22, 472–492 (1976)] (see also K. S. McCurley [Proc. Symp. Appl. Math, 42, 49–74 (1989)]). In Sidelnikov et al., [Doklady RAN, 332, No. 5, 566–567 (1993)] (see also Sec. 1 of the present paper) a new construction technique was proposed for a key distribution by means of a noncommutative group $G$. In this paper we study a particular case, where ideas of Diffie and Hellman and Sidelnikov et al. are united. Namely, we consider systems based on the group $\operatorname{\it GL}_n({\Bbb F}_p)$ represented by means of an auxiliary cyclic group $U$ of order $p$. One can take, for instance, a group of ${\Bbb F}_q$-points of an elliptic curve for $U$.

We treat in detail the case where $U=\left\langle \eta\right\rangle $ is the subgroup of order $p$ in the multiplicative group of an auxiliary field ${\Bbb F}_q$, $p\mid q-1$, and $G$ is the group of affine transformations of the field ${\Bbb F}_p$, $G\lt\operatorname{\it GL}_2({\Bbb F}_p)$. In this case the problem of determination of the common key ${\bf u}_{XY}$ for users $X$ and $Y$ is equivalent from the computational point of view to the following one: evaluate the element $\eta^{xy/z}$ as soon as $\eta^{x}$, $\eta^{y}$, $\eta^{z}$ are known. The latter problem does not presumably reduce to several Diffie–Hellman problems, i.e., to evaluation of the element $f=\eta^{xy}$ for $\eta^{x}$, $f=\eta^{y}$ known.

In the system constructed by using the group $G\lt\operatorname{\it GL}_2({\Bbb F}_p)$, there arise several new parameters not involved in Diffie–Hellman-type systems. In particular, a new private key arises for the whole system such that it is presumably impossible to determine the key ${\bf u}_{XY}$ without its knowledge.

In Sec. 4 we present a new way of evaluating numeral signatures of messages.

Asymptotic Efficiency in Estimation of a Convex Set
A. P. Korostelev and A. B. Tsybakov
pp. 317–327

Abstract—Consider the problem of estimating a closed convex set $G$ on the plane, given a sample from the uniform distribution on this set. We assume that $G$ belongs either to the class of all closed convex subsets of a fixed circle with Lebesgue measure separated from $0$, or to a smaller class of all convex sets with smooth boundaries having curvature radius $\geq R_{0}$. We study the asymptotics of the minimax risk over these classes, assuming that the distance between the estimator and the true set is measured in the Hausdorff metric. We show that the asymptotics of the risks are different for these classes, namely, $O((n/(\log n))^{-1/2})$ and $O((n/(\log n))^{-2/3}),$ respectively. Moreover, for the class of smooth convex sets $G$ we obtain a sharp evaluation of the minimax risk, with the ratio of lower and upper bounds $\approx 0.96.$

Fast-Service Polling Systems with Intensive Input Flows and Constant Switch Times
F. I. Karpelevich and A. Ya. Kreinin
pp. 328–340

Abstract—A queuing system is considered with a single server which serves $N$ queues in cyclic order. Fast customer arrivals and fast service are assumed as well as a finite time for the server to switch from one queue to the next. The process in $N$-dimensional space is studied with the value at any time instant being the queue lengths at that instant. This process is proved to coincide asymptotically with some nonrandom function taking values in $N$-dimensional space.

Average Packet Output Time For Conflict with Multiplicity 3 and Ternary Feedback
B. S. Tsybakov
pp. 341–356

Abstract—In problems of multiple access packet communications networks, one is required to analyze packet conflicts to find ways of resolving them. We find that in order to give a successful transmission to any given packet participating in a conflict of multiplicity 3, it is necessary and sufficient to use 3.53 (up to the three written digits) slots on average. Here we assume that after each slot, a feedback gives knowledge of whether it was an empty, successful, or conflict slot but does not tell the conflict multiplicity in the case of conflict.

Packet Delay Caused by Stack-Algorithm for Overcritical Income Flow
N. D. Vvedenskaya, P. Jacquet, and B. S. Tsybakov
pp. 357–369

Abstract—Multi-access of packets to a channel is considered. A stack algorithm is used in case of a conflict. It is assumed that the flow rate of arriving packets is overcritical and therefore not all packets are transmitted with finite delay. We present the conditional mean delay of a packet under the condition that the delay is finite, and we also present the outcome flow intensity.

The Number of Forms for Two-Dimensional Images
S. I. Stasevich
pp. 370–373

Abstract—In this paper, forms for gray-level images are investigated. These forms are defined by the decomposition of an $(N\times M)$-dimensional rectangle belonging to a two-dimensional integer grid into non-overlapping connected domains with boundaries passing along the grid edges. An expression for the number $L(M;N)$ of possible forms is derived as the sum of elements of a matrix raised to a power, for which a recursive relation is written. Then an estimate for the rate of exponential increase of the quantity $L(M;N)$ for $M\rightarrow\infty$, $N\rightarrow\infty$ is obtained.

Letter to the Editor (N. P. Zabotina)
p. 374