PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii


Volume 11, Number 3, July–September, 1975
Back to contents page

CONTENTS                   Powered by MathJax

 

Nonexistence of Perfect Codes for Some Composite Alphabets
L. A. Bassalygo, V. A. Zinoviev, V. K. Leont'ev, and N. I. Fel'dman
pp. 181–189

Abstract—It is known [V. A. Zinoviev and V. K. Leont'ev, Probl. Control Inf. Theory, 1973, vol. 2, no. 2, pp. 123–132; A. Tietäväinen, SIAM J. Appl. Math., 1973, vol. 24, no. 1, pp. 88–96] that if the cardinality of an alphabet $q$ is a power of a prime number, then nontrivial perfect codes other than the Hamming and Golay codes do not exist. A natural assumption is that this is true for composite $q$. In this paper it is shown that there do not exist nontrivial perfect codes over an alphabet of $q=2^{\alpha}3^{\beta}$ ($\alpha,\beta\ge l$) symbols that correct $t\ge 2$ errors. The question remains an open one for $t=1$. The only known result in this case [S. W. Golomb and E. S. Posner, IEEE Trans. Inf. Theory, 1964, vol. 10, no. 1, pp. 196–208] is that a perfect single-error-correcting code does not exist for $q=6$ and $n=7$.

 

An Upper Bound on the Volume of $q$-ary Codes
V. R. Sidorenko
pp. 190–194

Abstract—An analog of Sidel'nikov's lemma [Probl. Inf. Trans., 1974, vol. 10, no. 2, pp. 124–131] is obtained for $q$-ary codes with a specified vector composition. Upper bounds are obtained for the volume of codes with a specified vector composition and for arbitrary codes. An upper bound is obtained for the exponent of the volume of an arbitrary $q$-ary code that is uniformly superior to the Elias bound.

 

Defect and Error Correction
B. S. Tsybakov
pp. 195–202

Abstract—Memory devices with defective storage cells and random errors are considered. It is assumed that the locations of defective cells are known for entry of information and are unknown for readout. Codes that correct distortions resulting from defective cells and random errors are investigated.

 

Parameter Estimation for a Discontinuous Signal in White Gaussian Noise
I. A. Ibragimov and R. Z. Khas'minskii
pp. 203–212

Abstract—It is shown that for a discontinuous and quasidiscontinuous signal $S(t-\theta)$ the quadratic risk of the estimate of the parameter $\theta$ in white Gaussian noise of spectral density $\varepsilon^2$ is proportional to $\varepsilon^4$ when $\varepsilon\to 0$. The minimum attainable coefficient for $\varepsilon^4$ is found, as well as estimates for which this minimum is attained. It is shown that the maximum-likelihood estimate in this sense is inferior to the optimum one by roughly a factor of $1.3$ when $\varepsilon\to 0$. The limiting distributions of the estimates are also found; they are non-Gaussian but general for all $S(t)$ with discontinuities of the first kind. The only parameter that appears in these distributions is the number $r^2$, this being equal to the sum of squares of the discontinuities of $S(t-\theta)$ in the observation interval.

 

On One Problem of Observation Control
M. V. Burnashev and K. Sh. Zigangirov
pp. 213–220

Abstract—The problem of estimating an unknown parameter $\theta\in[0,1]$ by a confidence interval is considered. If points $x, y\in[0,1]$ are chosen as observation points, then the device in question indicates whether the estimated parameter belongs to the segment $[x,y]$ or not, but it has an error probability $p$. An observation strategy with a fixed number of observations is set up and investigated. An asymptotically optimal observation strategy is designed for the problem with a random number of observations.

 

Discriminant Analysis of Normal Populations with Different Covariation Matrices
L. G. Malinovskii
pp. 221–226

Abstract—The author examines a hypothesis regarding the structure of two normal populations and the links between this hypothesis and a procedure that makes it possible, as the paper, shows, to evaluate the parameters of the hypothesis. It is shown that if the populations are represented by large samples, the separating surface constructed in accordance with the hypothesis will possess smaller sampling errors than in the case of the widely employed hypothesis $\mathbf M_1\ne\mathbf M_2$, $\mathbf{\Sigma}_1\ne\mathbf{\Sigma}_2$.

 

Behavior of Finite Automata under Three Types of Responses of a Stationary Stochastic Medium
E. I. Pal'tsev
pp. 227–232

Abstract—The article analyzes some cases of the behavior of finite automata in stationary stochastic media under three types of responses of the medium. The medium reacts to each action of the automata either by rewarding it, by penalizing it, or by being indifferent. It is shown that the purposefulness of the forms of behavior of finite automata depends on the structure of the medium. Conditions are obtained such that the choice of a given form of behavior (active or passive) is most purposeful. Asymptotic optimality of the automata in question is analyzed.

 

Determination of Hamiltonian Cycles of a Graph
V. V. Kiryukhin and D. V. Polonskii
pp. 233–234

Abstract—A simple algorithm for finding all Hamiltonian cycles of a graph is proposed.

 

Theorem on Optimal Limited-Access Circuits in the Limit of Low Load Intensity
M. A. Shneps
pp. 235–240

Abstract—A theorem is proved to the effect that when the load intensity tends to zero, an optimal limited-access circuit should contain the maximum number of search steps with activation or switch-in of individual lines, and if, for given circuit parameters a search step is created that activates not only individual lines, it should have uniform activation of lines.

 

Indexed Grammars and Wijngaarden Grammars
A. N. Maslov
pp. 241–248

Abstract—The paper considers the relationships between the generative capacity of indexed grammars and Wijngaarden grammars.

 

Characterizations of Error Clustering at the Output of Convolutional Decoders
V. A. Artem'ev, V. I. Kireichenko, and Ya. D. Khatskelevich
pp. 249–252

Abstract—Experimentally obtained characteristics of error grouping at the output of a Viterbi convolutional decoder are given. These characteristics are used to estimate the error probability in an information word.

 

Representation of Fisher Information in Terms of Distribution Moments
S. M. Fintushal
pp. 253–255

Abstract—It is shown that, under fairly general conditions, the polynomial Pitman bounds for the shift parameter are asymptotically effective. The Fisher information is estimated in terms of a rational function of the moments.

 

Field Processing Algorithm That Uses Linear Channel Estimates
V. A. Soifer
pp. 256–258

Abstract—An algorithm is created for processing a spatial-temporal field containing a discrete message. It is shown that an algorithm that uses linear channel estimates is similar to the Bayesian algorithm for processing a Gaussian field in Gaussian noise.

 

On Some Multidimensional Systems of Automata Related to Percolation Problems
L. G. Mityushin
pp. 259–261

Abstract—The article considers the asymptotic behavior with respect to $n$ of the critical parameter value for some percolation problems on an $n$-dimensional lattice and the associated systems of automata.