PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Claude Elwood Shannon
pp. 87–90

Codes Derived from Binary Goppa Codes
P. Loidreau
pp. 91–99

Abstract—We present a new family of binary codes derived from the family of classical Goppa codes. We generalize properties of Goppa codes to this family, including bounds on the dimension and minimum distance and construction of a polynomial-time algorithm of decoding up to the designed distance. Asymptotically, these codes have the same parameters as Goppa codes.

Frank Signal and Its Generalizations
V. N. Malozemov, S. M. Masharsky, and K. Yu. Tsvetkov
pp. 100–107

Abstract—Based on the Frank signal, we construct two infinite sets of signals whose cyclic or $n$-adic shifts form orthogonal bases. Such bases can efficiently be employed in designing CDMA broadband communication systems where the basis signals are used as information carriers.

Nonrobustness Property of the Individual Ergodic Theorem
V. V. V'yugin
pp. 108–119

Abstract—Main laws of probability theory, when applied to individual sequences, have a “robustness” property under small violations of randomness. For example, the law of large numbers for the symmetric Bernoulli scheme holds for a sequence where the randomness deficiency of its initial fragment of length $n$ grows as $o(n)$. The law of iterated logarithm holds if the randomness deficiency grows as $o(\log\log n)$. We prove that Birkhoff's individual ergodic theorem is nonrobust in this sense. If the randomness deficiency grows arbitrarily slowly on initial fragments of an infinite sequence, this theorem can be violated. An analogous nonrobustness property holds for the Shannon–McMillan–Breiman theorem.

Large Deviation Principle for Markov Chains in Continuous Time
A. de La Fortelle
pp. 120–139

Abstract—Let $Y_t$ be a homogeneous nonexplosive Markov process with generator $R$ defined on a denumerable state space $E$ (not necessarily ergodic). We introduce the \emph{empirical generator} $G_t$ of $Y_t$ and prove the Ruelle–Lanford property, which implies the weak LDP. In a fairly broad setting, we show how to perform almost all classical operations (e.g., contraction) on the weak LDP under suitable assumptions, whence Sanov’s theorem follows.

Untying of Clutter-Family Supports and Its Role in the Monotone-Structure Reliability Theory
V. P. Polesskii
pp. 140–154

Abstract—We suggest a transformation of supports of a clutter family. It is a natural generalization of the untying transformation of a one-clutter support previously introduced by the author. We show that the new transformation does not decrease the reliability of the corresponding clutter sum. We give new bounds for the clutter-sum reliability. We demonstrate that the untying transformation of clutter-family supports and the factor transformation introduced by McDiarmid provide a combinatorial basis for the monotone-structure reliability theory.

Estimation of Performance of the Hopfield Randomized Memory
B. V. Kryzhanovskii, V. N. Koshelev, and A. B. Fonarev
pp. 155–164

Abstract—We study the recognition capability of a Hopfield network, i.e., a neural network where interaction of nodes is determined by the Hebb transform. We present a formally rigorous derivation of an upper bound on the error probability for recognition of randomized objects. It is based on the standard technique of estimating large deviations by the Chebyshev–Chernov method.

Ergodicity of Band Graph Markov Chains and Their Application to Problems of the Analysis of Existence of a Stationary Regime in a Dynamic Random Multiple Access Communication Network
A. A. Nazarov and S. L. Shokhor
pp. 165–171

Abstract—A concept of the class of band graph Markov chains is introduced. Simple ergodicity criteria for this class of stochastic processes are found. We show how these criteria can be applied to prove the existence of a stationary operation regime in a dynamic access communication network with conflict warning.

Using Literal and Grammatical Statistics for Authorship Attribution
O. V. Kukushkina, A. A. Polikarpov, and D. V. Khmelev
pp. 172–184

Abstract—Markov chains are used as a formal mathematical model for sequences of elements of a text. This model is applied for authorship attribution of texts. As elements of a text, we consider sequences of letters or sequences of grammatical classes of words. It turns out that the frequencies of occurrences of letter pairs and pairs of grammatical classes in a Russian text are rather stable characteristics of an author and, apparently, they could be used in disputed authorship attribution. A comparison of results for various modifications of the method using both letters and grammatical classes is given. Experimental research involves 385 texts of 82 writers. In the Appendix, the research of D.V. Khmelev is described, where data compression algorithms are applied to authorship attribution.

Fridrikh Izrailevich Karpelevich. In Memoriam
pp. 185–186