PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii


Volume 40, Number 1, January–March, 2004
Back to contents page

CONTENTS                   Powered by MathJax

 

Mark Semenovich Pinsker. In Memoriam
pp. 1–4

 

On Multifold MDS and Perfect Codes That Are Not Splittable into Onefold Codes
D. S. Krotov and V. N. Potapov
pp. 5–12

Abstract—The union of $\ell$ disjoint MDS (or perfect) codes with distance $2$ (respectively, $3$) is always an $\ell$-fold MDS (perfect) code. The converse is shown to be incorrect. Moreover, if $k$ is a multiple of $4$ and $n+1\ge 16$ is a power of two, then a $k/2$-fold $k$-ary MDS code of length $m\ge 3$ and an $(n+1)/8$-fold perfect code of length $n$ exist from which no MDS (perfect) code can be isolated.

 

New Minimum Distance Bounds for Linear Codes over $\operatorname{\it GF}(9)$
R. Daskalov, E. Metodieva, and P. Hristov
pp. 13–24

Abstract—Thirty-one new linear codes over $\operatorname{\it GF}(9)$ are constructed, and the nonexistence of thirty codes is proved.

 

Binary Perfect Codes of Length $15$ by the Generalized Concatenated Construction
V. A. Zinoviev and D. V. Zinoviev
pp. 25–36

Abstract—We enumerate binary nonlinear perfect codes of length $15$ obtained by the generalized concatenated (GC) construction. There are $15$ different types of such codes. They are defined by pairs of MDS codes $A_i\colon(4,2,64)_4$. For every pair we give the number of nonequivalent codes of this type. In total, there are $777$ nonequivalent binary perfect codes of length $15$ obtained by the GC construction. This number includes the Hamming code (of rank $11$), $18$ Vasil'ev codes (of rank $12$), and $758$ codes of rank $13$.

 

Construction of Perfect $q$-ary Codes by Sequential Switchings of $\widetilde{\alpha}$-Components
A. V. Los'
pp. 37–43

Abstract—We suggest a construction of perfect $q$-ary codes using sequential switchings of special-type components of the Hamming code. The construction yields a lower bound on the number of different $q$-ary codes.

 

On Optimal Detectors in Multiuser Detection Problems
M. V. Burnashev
pp. 44–52

Abstract—The paper is a supplement to [1: M.V. Burnashev, Probl. Inf. Trans., 2003, vol. 39, no. 2, pp. 191–206]. Conditions under which asymptotically optimal detectors are linear are found. It is shown also that if, in contrast to [1], we consider not the Bayesian but minimax statement of the problem with unknown coefficients, then optimal detectors are linear (moreover, nonasymptotically). A geometrical meaning of Theorem 1 from [1] is explained, and it is shown that the theorem follows from some general results [M.V. Burnashev, Teor. Veroyatn. Primen., 1979, vol. 24, no. 1, pp. 106–118; Math. Notes, 1982, vol. 32, no. 4, pp. 549–555] on hypotheses testing. It is also shown that some results of [R. Lupas and S. Verdú, IEEE Trans. Inf. Theory, 1989, vol. 35, no. 1, pp. 123–136] follow from [1, Theorem 1].

 

The Method of Risk Envelope in Estimation of Linear Functionals
G. K. Golubev
pp. 53–65

Abstract—The problem of estimating a linear functional in a linear Gaussian model is considered. For the estimation, the class of projection estimators is used. The problem is to choose the optimal estimate from this class on the basis of observations. The solution of this problem is based on the principle of risk envelope minimization.

 

“Book Stack” as a New Statistical Test for Random Numbers
B. Ya. Ryabko and A. I. Pestunov
pp. 66–71

Abstract—A new statistical test is proposed for testing the hypothesis $H_0$ that symbols of an alphabet are generated with equal probabilities against the alternative hypothesis $H_1$, the negation of $H_0$. The new method is applied to testing generators of pseudorandom numbers. It is experimentally demonstrated that the method makes it possible to detect deviations from randomness for many generators which “withstand” previously known statistical tests.

 

On Indication of External Factors by Circuits of Functional Elements
V. V. Tarasov
pp. 72–77

Abstract—We consider functions $f(x_1,\ldots,x_n, z_1,\ldots,z_m)$ of $k$-valued logic, where $x_1,\ldots,x_n$ are ordinary $k$-valued variables and $z_1,\ldots,z_m$ are improper $k$-valued variables indicating external factors. An algorithm is presented for designing a circuit of $k$-valued functional elements, which realizes a $k$-valued indicator $z$, $z\in\{z_1,\ldots,z_m\}$.

 

Local Diffusion Approximation of the State Changing Process of an Unstable Random Access Network in a Neighborhood of the Asymptotic Mean
P. I. Kotsyuruba and A. A. Nazarov
pp. 78–89

Abstract—A mathematical non-Markovian model of an unstable random access network is investigated by the asymptotic analysis method. A random process is constructed which approximates the values of deviations of the normalized number of messages from the asymptotic mean. This process is shown to be Gaussian; explicit expressions for its drift coefficients, diffusion, and other characteristics are obtained.

 

Optimal Universal Coding with Respect to the Maximal Individual Relative Redundancy Criterion
Yu. M. Shtarkov, Tj. J. Tjalkens, and F. M. J. Willems
pp. 90–101

Abstract—Advantages of the relative redundancy criterion are discussed. Two types of universal (with respect to this criterion) codes are proposed. It is proved that, for the set of binary memoryless sources, variable-to-fixed length codes are more efficient than fixed-to-variable length codes if the number of encoded messages is the same.