A translation of Problemy Peredachi Informatsii

Volume 20, Number 1, January–March, 1984
Back to contents page

CONTENTS                   Powered by MathJax


On Shortening of Codes
V. A. Zinov'ev and S. N. Litsyn
pp. 1–7

Abstract—The authors obtain some new bounds for the dual distance of generalized concatenated codes and BCH codes. The use of these bounds in the existing code-shortening arrangements leads to a number of new codes with optimal parameters. A new construction is proposed for shortening arbitrary (linear and nonlinear) codes. Application of this construction to existing codes yields a large number of codes with optimal known parameters.


Minimum Possible Block Length of a Linear Binary Code for Some Distances
S. M. Dodunekov and N. L. Manev
pp. 8–14

Abstract—Linear binary codes are considered. It is shown that if $d=2^{k-1}-2^{k-i-1}-2^i$ or $2^{k-1}-2^{k-i-1}-2^i-2$ and $k\geq2i+2$, the minimum possible block length of a code of dimension $k$ with code distance $d$ is $1+\sum\limits^{k-1}_{j=0}\biggl\lceil\displaystyle\frac d{2^j}\biggr\rceil$.


Choice of Coding System for Error Protection of Storage Devices
Yu. L. Sagalovich and N. S. Shcherbakov
pp. 14–20

Abstract—The authors describe a method of choosing a noise-stable coding system for protecting storage devices from independent errors of both the storage bits themselves and of parallel coders and decoders. It is shown that there is a substantial difference from the choice of coding system intended for a communications channel. Preference is given to systems with one-step majority decoding. The method is illustrated using 12 coding systems, for which detailed parameters of the principal code, encoder, and decoder parameters are given.


Multidimensional Signals for a Continuous Channel
V. V. Ginzburg
pp. 20–34

Abstract—For channels with an additive signal distance, the author proposes constructions of multidimensional signals described by an ensemble of codes. The constructions are suitable for a continuous channel with white noise, for which a number of specific signal systems are constructed.


Modular Curves and Codes with Polynomial Construction Complexity
S. G. Vlǎduţ, G. L. Katsman, and M. A. Tsfasman
pp. 35–42

Abstract—The authors construct and analyze linear $q$-ary codes that arise from modular Drinfeld, and the associated binary codes. All these codes have polynomial complexity of construction and “good” asymptotic parameters: $q$-ary codes for $q=p^{2m}\ge 49$ lie above the Varshamov–Gilbert bound on some segment, while binary codes lie above the Blokh–Zyablov bound everywhere.


On Minimax Estimation of Regression
G. K. Golubev
pp. 42–49

Abstract—In the problem of minimax estimation of regression, for special classes of the function $\Sigma_T$ the author finds the minimax quadratic risk and constructs estimates on which it is attained.


Median Filtering of Random Processes
L. I. Piterbarg
pp. 49–55

Abstract—The author proposes a model of median filtering of continuous processes. The problem of correcting the statistical characteristics of the signal being processed in the case of a narrow filter window is examined for certain Gaussian processes. The property of robustness of the procedure is considered.


On the Lower Bound for the Number of States of Deterministic Intelligent Automata
A. N. Boiko
pp. 56–63

Abstract—The article examines the problem of estimating the complexity of deterministic Moore automata that are intelligent in homogeneous Markov media (HMM). The measure of complexity of the automaton is determined as the number of its internal states. A lower bound $N\geq 2k$ is established for the number of states of automata that are intelligent in HMM; this bound improves the earlier bound $N\gt k$ (here $k$ is the number of controls). A lower bound $N\geq k^{3/2}$ is established for the number of states of automata that are intelligent in HMM, for the case in which any of their states is taken as the initial one.


Stability of Asynchronous ALOHA System
B. S. Tsybakov and V. L. Bakirov
pp. 63–72

Abstract—The authors consider a pure ALOHA system involving random multiple access of packets to a shared channel with feedback. A new mathematical model of the system is proposed; it is free from a number of the restrictive assumptions that were made in [N. Abramson, IEEE Trans. Commun., 1977, vol. 25, no. 1, pp. 117–128; L. Kleinrock, Queuing Systems, Vol. 2, Wiley, New York, 1976; M.J. Ferguson, Proc. 4th Data Commun. Symp., Quebec, Canada, 1975, pp. 5.20–5.25; D. Sant, IEEE Trans. Commun., 1980, vol. 28, no. 8, pp. 1422–1425]. The stability conditions for a pure ALOHA system are obtained. The transmission rate is optimized in the case of single stations.


Discrete-Time Single-Server System with Requests of Several Types
G. P. Basharin and V. A. Efimushkin
pp. 73–80

Abstract—The authors analyze a discrete-time single-server $\mathrm{Geom}_k|\mathrm{Geom}_k|1|R|f_0$ queuing system (QS) with several types of incoming requests. The time intervals between arrivals and the servicing durations are independent and distributed geometrically (the discrete analog of the exponential distribution). Scalar and matrix relations are obtained for the distribution of the stationary state probabilities of the Markov chain describing the QS. It is shown that, as the discretization unit $h$ tends to zero, the solution for an $M_k|M_k|1|R|f_0$ QS is obtained. A numerical example is given.


(available in Russian only)


Comparision of Decoding Comlexity for Truncated Convolutional Codes and Block Codes
V. V. Zyablov and S. A. Shavgulidze
pp. 105–109 (Russian issue)

Abstract—We compare the complexity of maximum likelihood decoding of truncated convolutional codes with that of best known block codes.