PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii


Volume 30, Number 3, July–September, 1994
Back to contents page

CONTENTS                   Powered by MathJax

 

Measures Separated in $L_1$ Metrics and ID-Codes
M. V. Burnashev and S. Verdú
pp. 191–201

Abstract—A geometrical approach to ID-codes, based on their equivalence to some natural notions from mathematical statistics, is described. This not only enlarges the available analytical apparatus, but also enables us to strengthen some known results.

 

Lower Estimates of the Probability to Distinct Subsets of Unit Cube
I. B. Oshkin and G. V. Proskurin
pp. 202–208

Abstract—The structure of binary-cube partitions which minimize the probability of correctly finding a subset by its distorted representatives is studied.

 

Some New NP-Complete Coding Problems
A. Barg
pp. 209–214

Abstract—We prove the NP-completeness of the basic decision problems for ternary linear codes. In particular, we prove that finding out whether a ternary linear code contains a vector of weight equal to the code length is NP-complete. In addition, we prove the hardness of minimum distance decoding for linear product codes with nontrivial factors.

 

A New Class of High-Rate Orthogonalizable Convolutional Codes
A. E. Gheer
pp. 215–223

Abstract—We propose a new class of high-speed orthogonalizable convolutional codes (CC) with relative code rate $R=(n-1)/n$. These codes are substantially shorter than the optimal self-orthogonal CC, have limited error propagation, and are transparent for the phase ambiguity in a phase-shift keying channel.

 

Binary Weight Spectrum of the Extended $[2^m,5]$ Reed–Solomon Code and its Dual Code
E. Kolev and N. Manev
pp. 224–231

Abstract—We consider the extended $[2^m,5]$ Reed–Solomon code over $\operatorname{GF}(2^m)$ and its binary image determined by the choice of a basis $\beta_1,\beta_2,\ldots,\beta_m$ over $\operatorname{GF}(2)$. The weight spectrum of the binary image for a certain class of bases is computed.

 

Theory of Fuzzy Sets as a Theory of Uncertainty and Decision-Making Problems in Fuzzy Experiments
P. V. Golubtsov
pp. 232–250

Abstract—This paper develops a fuzzy-theoretic approach to uncertainty and decision-making problems. It is an alternative to the probabilistic approach though it is very similar to the latter. The paper examines fuzzy analogs of the main probabilistic concepts such as joint distribution, conditional distribution, independence, etc., and the role of these concepts in the construction of optimal strategies for fuzzy decision problems. It is shown that this approach makes it entirely possible to use the rich conceptual experience of mathematical statistics in the new context. In particular, the fuzzy variant of the Bayes principle derived in the paper plays the same role in fuzzy decision-making problems as its probabilistic prototype in the theory of statistical games. To illustrate the developed approach fuzzy point estimation problems are studied. Finally, the relation between Bayes and minimax approaches is discussed. It is demonstrated that the minimax approach is a particular case of the Bayes approach within the framework of fuzzy theories.

 

Implemented Optimal Algorithm of Passive Stochastic Approximation with Averaging along a Trajectory
A. V. Nazin and P. S. Shcherbakov
pp. 251–259

Abstract—The problem of finding a root of a regression equation is considered in passive stochastic approximation. An implemented (adaptive) version is proposed for the asymptotically optimal algorithm with averaging investigated earlier by the authors. This is based on the estimation of unknown parameters of the problem which are required when calculating the optimal value for the bandwidth. Convergence with probability 1 and in the mean square is proved for the estimates, as well as their optimality in terms of asymptotic normality.

 

Evolution of a Random String: Stabilization Laws
V. A. Malyshev
pp. 260–274

Abstract—A discrete time homogeneous Markov chain is considered the states of which are sequences (strings) $ \alpha =x_{n} \ldots x_{1}$ of $r$ symbols; the transition probabilities depend only on the $d$ leftmost symbols, and $ \alpha $ can jump only to $ \beta =y_{m} \ldots y_{1}$ such that $|n-m| \leq d$ and $x_{i}=y_{i}$ for all $i=1, \ldots ,n-d$. We prove various stabilization laws for the left end of the string. For a queueing theory, this means that a LIFO queue with $r$ types of customers and with batch arrivals and batch services is considered. This constitutes the first step of the new probabilistic approach to communication networks with several customer types.

 

Binary Processes of Self-Assembling with Volumetric Interactions
M. L. Tai
pp. 275–282

Abstract—We study the binary process of self-assembling of ordered components, which are able to store and transmit information, in the presence of volumetric interactions. We have found a description of the process, which uses the hierarchy of its components and links and enables us to determine the behavior of the concentrations of the links as $t\rightarrow \infty$. The stability of equilibrium is proved for the binary process of self-assembly in the absence of volumetric interactions. A simple class of volumetric interactions, which causes instability of the equilibrium even with self-assembly of four elements, is discovered.

 

Single-Line Queue with Finite Source and Repeated Calls
V. I. Dragieva
pp. 283–289

Abstract—A single-line queue with a finite source and repeated calls is considered. Some of its basic characteristics were studied earlier. In this paper the study of these characteristics is continued. Numerical data are obtained and a comparison with the characteristics of the corresponding model with an infinite number of sources is made.