PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Two-Way Communication Complexity of Sum-Type Functions For One Processor to Be Informed
Rudolf Ahlswede and Ning Cai
pp. 1–10

Abstract—The asymmetric two-way communication complexity of a function is a measure of the minimal amount of information required to be communicated between two parties in order for one of them to compute the value of the function at the inputs supplied by the parties. We provide rather sharp lower bounds for this quantity in terms of the rank of a certain matrix transform of the function. For several sum-type functions, such as the Hamming, Lee, or Taxi metrics, they are even tight. We emphasize that for this class of functions the familiar  log rank  of the function tables gives, in general, a poor lower bound.

Estimating the Mutual Interference of Two Sources in a Multiple Access Channel
V. A. Yakovlev
pp. 11–26

Abstract—A communication system with two independent sources and two receivers that are pairwise connected by channels that are called basic channels is investigated. A third (adversary) receiver is connected to both sources via a multiple access channel. A theorem that establishes the relation between the rate of information transmission via the basic channels and the equivocation of information in the multiple access channel is proved.

On the Divisibility of Discrete Sources with an Additive Single-Letter Distortion Measure
V. N. Koshelev
p. 27–43

Abstract—Hierarchical ε-nets for discrete metric spaces as well as hierarchical multilevel codes for discrete memoryless sources are considered. A divisibility problem is formulated. The divisibility means that in each level of the hierarchy, the total amount of the information necessary to pass from an achieved distortion level to a smaller one asymptotically coincides with the corresponding increment of the ε-entropy of the space or the rate-distortion function of the source. Conditions under which a ternary equiprobable source with the balanced distortion measure is divisible are found.

Decoding Reed–Solomon Codes Beyond $(d-1)/2$ and Zeros of Multivariate Polynomials
V. M. Sidelnikov
pp. 44–59

Abstract—Let ${\bf e}$ be an error vector of weight $t$ and let ${\bf b}$ be its syndrome. In this work we consider a symmetric polynomial $O(y_1,\ldots,y_r,{\bf b})$ from $F_q[y_1,\ldots,y_r]$ of degree $t-r+1$, where $r=2t-d+2$, which has the following property: if $\Omega$ is the set of error locations with syndrome ${\bf b}$, then any $r$-element subset $\Omega'$ of the set $\Omega$ is a zero of $O(y_1,\ldots,y_r,{\bf b})$. The converse is also true, namely, the zeros of $O(y_1,\ldots,y_r,{\bf b})$ determine all the locations of errors of weight $t$ whose syndrome equals ${\bf b}$, i.e., decoding and finding zeros of $O(y_1,\ldots,y_r,{\bf b})$ that lie in a prescribed set are equivalent problems. Based on these properties, we suggest a decoding algorithm of Reed--Solomon codes for $t\gt(d-1)/2$. A large part of the paper is devoted to the study of a nontrivial class of symmetric polynomials in $r$ variables formed by the polynomials $O(y_1,\ldots,y_r,{\bf b})$.

Transmission of Constant Weight Binary Sequences with Convolutional Codes and Maximum Likelihood Decoding
V. B. Balakirskii
pp. 60–71

Abstract—We study the performance of a communication system that uses linear convolutional codes for the transmission of binary sequences of fixed Hamming weight over the binary symmetric channel. The transmission method that we consider is the straightforward encoding of messages transmitted. We suggest a maximum likelihood decoding algorithm of received sequences. It is shown that this algorithm provides a more efficient tradeoff between the decoder implementation complexity and the decoding error probability than the performance of the two-stage encoding.

Optimization of Closed Queueing Networks with Several Classes of Messages
A. I. Gerasimov
pp. 72–81

Abstract—We consider the problem of optimizing closed queueing networks with several classes of messages. The research is based on our previous results concerning normalizing constants. An example of optimization is given.

Kernels of Jackson Type and Their Application to Designing Low-Pass Filters
V. G. Alekseev
pp. 82–87

Abstract—A sequence of linear digital low-pass filters is proposed on the basis of expansion in a Fourier series of the kernel of Jackson type $J_{3,n}(\mu)$ proportional to the cube of the Fejer kernel. In addition, exact formulas for the kernels of Jackson type $J_{l,n}(\mu)$, $l=4,5,6$, each being proportional to the $l$-th degree of the Fejer kernel, are obtained.

Variance of Statistical Parameter Estimates of a Semimarkov Process with a Finite State Space
E. I. Shkolny
pp. 87–92

Abstract—We consider statistical estimates of parameter of a generalized semi-Markov process with a finite state space. The estimates take the form of a ratio of two accumulative processes in time $t$. It is shown that the estimates are asymptotically unbiased, consistent, and asymptotically normal as $t\to\infty$. Formulas for the variance of the estimates are obtained.

Sixth Joint Swedish–Russian International Workshop on Information Theory
pp. 93–94