PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

On Convergence Properties of Shannon Entropy
F. J. Piera and P. Parada
pp. 75–94

Abstract—Convergence properties of Shannon entropy are studied. In the differential setting, it is known that weak convergence of probability measures (convergence in distribution) is not sufficient for convergence of the associated differential entropies. In that direction, an interesting example is introduced and discussed in light of new general results provided here for the desired differential entropy convergence, which take into account both compactly and uncompactly supported densities. Convergence of differential entropy is also characterized in terms of the Kullback–Liebler discriminant for densities with fairly general supports, and it is shown that convergence in variation of probability measures guarantees such convergence under an appropriate boundedness condition on the densities involved. Results for the discrete setting are also provided, allowing for infinitely supported probability measures, by taking advantage of the equivalence between weak convergence and convergence in variation in that setting.

Low-Complexity Error Correction of Hamming-Code-Based LDPC Codes
V. A. Zyablov, R. Johannesson, and M. Lončar
pp. 95–109

Abstract—Ensembles of binary random LDPC block codes constructed using Hamming codes as constituent codes are studied for communicating over the binary symmetric channel. These ensembles are known to contain codes that asymptotically almost meet the Gilbert–Varshamov bound. It is shown that in these ensembles there exist codes which can correct a number of errors that grows linearly with the code length, when decoded with a low-complexity iterative decoder, which requires a number of iterations that is a logarithmic function of the code length. The results are supported by numerical examples, for various choices of the code parameters.

A Method for Proving Nonexistence of Spherical Designs of Odd Strength and Odd Cardinality
S. Boumova, P. Boyvalenkov, and M. Stoyanova
pp. 110–123

Abstract—We combine polynomial techniques with some geometric arguments to obtain restrictions of the structure of spherical designs with fixed odd strength and odd cardinality. Our bounds for the extreme inner products of such designs allow us to prove nonexistence results in many cases. Applications are shown for 7-designs.

DNA Codes for Additive Stem Similarity
A. G. D'yachkov and A.N. Voronina
pp. 124–144

Abstract—We study two new concepts of combinatorial coding theory: additive stem similarity and additive stem distance between $q$-ary sequences. For $q=4$, the additive stem similarity is applied to describe a mathematical model of thermodynamic similarity, which reflects the “hybridization potential” of two DNA sequences. Codes based on the additive stem distance are called DNA codes. We develop methods to prove upper and lower bounds on the rate of DNA codes analogous to the well-known Plotkin upper bound and random coding lower bound (the Gilbert–Varshamov bound). These methods take into account both the “Markovian” character of the additive stem distance and the structure of a DNA code specified by its invariance under the Watson–Crick transformation. In particular, our lower bound is established with the help of an ensemble of random codes where distribution of independent codewords is defined by a stationary Markov chain.

On Weak Isometries of Preparata Codes
I. Yu. Mogil'nykh
pp. 145–150

Abstract—Two codes $C_1$ and $C_2$ are said to be weakly isometric if there exists a mapping $J\colon C_1\to C_2$ such that for all $x,y$ in $C_1$ the equality $d(x,y)=d$ holds if and only if $d(J(x),J(y))=d$, where $d$ is the code distance of $C_1$. We prove that Preparata codes of length $n\ge2^{12}$ are weakly isometric if and only if the codes are equivalent. A similar result is proved for punctured Preparata codes of length at least $2^{10}-1$.

Local and Interweight Spectra of Completely Regular Codes and of Perfect Colorings
A. Yu. Vasil'eva
pp. 151–157

Abstract—We introduce notions of local and interweight spectra of an arbitrary coloring of a Boolean cube, which generalize the notion of a weight spectrum. The main objects of our research are colorings that are called perfect. We establish an interrelation of local spectra of such a coloring in two orthogonal faces of a Boolean cube and study properties of the interweight spectrum. Based on this, we prove a new metric property of perfect colorings, namely, their strong distance invariance. As a consequence, we obtain an analogous property of an arbitrary completely regular code, which, together with his neighborhoods, forms a perfect coloring.

Exact Formulas for Computation of Reception Characteristics of a Signal with Unknown Appearance and Disappearance Times
A. P. Trifonov and Yu. E. Korchagin
pp. 158–167

Abstract—We consider the performance of the maximum-likelihood algorithm for detection and measurement of appearance and disappearance times of an arbitrary waveform signal observed against additive white Gaussian noise. We find exact expressions for detection error probabilities and densities of estimated appearance and disappearance times.

On Complete One-Way Functions
A. A. Kozhevnikov and S. I. Nikolenko
pp. 168–183

Abstract—Complete constructions play an important role in theoretical computer science. However, in cryptography complete constructions have so far been either absent or purely theoretical. In 2003, L.A. Levin presented the idea of a combinatorial complete one-way function. In this paper, we present two new one-way functions based on semi-Thue string rewriting systems and a version of the Post correspondence problem. We also present the properties of a combinatorial problem that allow a complete one-way function to be based on this problem. The paper also gives an alternative proof of Levin's result.

Asymptotically Optimal Perfect Steganographic Systems
B. Ya. Ryabko and D. B. Ryabko
pp. 184–190

Abstract—In 1998 C. Cachin proposed an information-theoretic approach to steganography. In particular, in the framework of this approach, so-called perfectly secure stegosystems were defined, where messages that carry and do not carry hidden information are statistically indistinguishable. There was also described a universal steganographic system, for which this property holds only asymptotically, as the message length grows, while encoding and decoding complexity increases exponentially. (By definition, a system is universal if it is also applicable in the case where probabilistic characteristics of messages used to transmit hidden information are not known completely.)

In the present paper we propose a universal steganographic system where messages that carry and do not carry hidden information are statistically indistinguishable, while transmission rate of “hidden” information approaches the limit, the Shannon entropy of the source used to “embed” the hidden information.

Remark on “On Error-free Filtering of Finite-State Singular Processes under Dependent Distortions” Published in Probl. Peredachi Inf., 2007, no. 4
V. V. Prelov and E. C. van der Meulen
p. 191

The authors thank S.A. Pirogov for finding an error in the proof of the main theorem of our paper “On Error-free Filtering of Finite-State Singular Processes under Dependent Distortions” (Probl. Peredachi Inf., 2007, vol. 43, no. 4, pp. 271–279). The statement of the theorem remains valid (even without additional assumption on finiteness of the number of values of a completely singular process $X$) if $Y$ is an output process of a stationary memoryless channels whose input signal is $X$. However, in the general case, where $Y$ is absolutely regular with respect to $X$, the question of validity of the theorem statement remains open.