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.

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.

A threshold gate is a linear combination of input variables with integer coefficients (weights). It outputs 1 if the sum is positive. The maximum absolute value of the coefficients of a threshold gate is called its weight. A degree-d perceptron is a Boolean circuit of depth 2 with a threshold gate at the top and any Boolean elements of fan-in at most d at the bottom level. The weight of a perceptron is the weight of its threshold gate.For any constant d ≥ 2 independent of the number of input variables n, we construct a degree-d perceptron that requires weights of at least $$ n^{\Omega (n^d )} $$ ; i.e., the weight of any degree-d perceptron that computes the same Boolean function must be at least $$ n^{\Omega (n^d )} $$ . This bound is tight: any degree-d perceptron is equivalent to a degree-d perceptron of weight $$ n^{O(n^d )} $$ . For the case of threshold gates (i.e., d = 1), the result was proved by Håstad in [2]; we use Håstad’s technique.

The subspace metric is an object of active research in network coding. Nevertheless, little is known on codes over this metric. In the present paper, several classes of codes over subspace metric are defined and investigated, including codes with distance 2, codes with the maximal distance, and constant-distance constant-dimension codes. Also, Gilbert-type bounds are presented.

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.

We consider regular block and convolutional LDPC codes determined by paritycheck matrices with rows of a fixed weight and columns of weight 2. Such codes can be described by graphs, and the minimum distance of a code coincides with the girth of the corresponding graph. We consider a description of such codes in the form of tail-biting convolutional codes. Long codes are constructed from short ones using the “voltage graph” method. On this way we construct new codes, find a compact description for many known optimal codes, and thus simplify the coding for such codes. We obtain an asymptotic lower bound on the girth of the corresponding graphs. We also present tables of codes.

We consider partitions of finite abelian groups. We introduce the concept of Fourier-invariant pairs and demonstrate that this concept is equivalent to the concept of an association scheme in an abelian group. It follows that Fourier-invariant pairs of partitions might be viewed as a very natural approach to abelian association schemes.

We consider a realistic model of a wireless network where nodes are dispatched in an infinite map with uniform distribution. Signals decay with distance according to attenuation factor alpha. At any time we assume that the distribution of emitters is lambda per square unit area. From an explicit formula of the Laplace transform of a received signal, we derive an explicit formula for the information rate received by an access point at a random position, which is alpha/2(log 2)(-1) per Hertz. We generalize to network maps of any dimension.

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.

We consider a retrial queueing system with batch arrival of customers. Unlike standard batch arrival, where a whole batch enters the system simultaneously, we assume that customers of a batch (session) arrive one by one in exponentially distributed time intervals. Service time is exponentially distributed. The batch arrival flow is MAP. The number of customers in a session is geometrically distributed. The number of sessions that can enter the system simultaneously is a control parameter. We analyze the joint probability distribution of the number of sessions and customers in the system using the techniques of multidimensional asymptotically quasi-Toeplitz Markov chains.

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.

A transformation of Steiner quadruple systems S(υ, 4, 3) is introduced. For a given system, it allows to construct new systems of the same order, which can be nonisomorphic to the given one. The structure of Steiner systems S(υ, 4, 3) is considered. There are two different types of such systems, namely, induced and singular systems. Induced systems of 2-rank r can be constructed by the introduced transformation of Steiner systems of 2-rank r − 1 or less. A sufficient condition for a Steiner system S(υ, 4, 3) to be induced is obtained.

We obtain some upper and lower bounds for the maximum of mutual information of several random variables via variational distance between the joint distribution of these random variables and the product of its marginal distributions. In this connection, some properties of variational distance between probability distributions of this type are derived. We show that in some special cases estimates of the maximum of mutual information obtained here are optimal or asymptotically optimal. Some results of this paper generalize the corresponding results of [1–3] to the multivariate case.

The discrete Walsh transform is a linear transform defined by a Walsh matrix. Three ways to construct Walsh matrices are known, which differ by the sequence order of rows and correspond to the Paley, Walsh, and Hadamard enumerations. We propose a new enumeration of Walsh matrices and study its properties. The new enumeration is constructed as a linear rearrangement; we obtain an eigenvector basis for it and propose a convenient-to-generate fast implementation algorithm; the new enumeration possesses certain symmetry properties, which make it similar to the discrete Fourier transform.

We apply the theory of products of random matrices to the analysis of multi-user communication channels similar to the Wyner model, which are characterized by short-range intra-cell broadcasting. We study fluctuations of the per-cell sum-rate capacity in the non-ergodic regime and provide results of the type of the central limit theorem (CLT) and large deviations (LD). Our results show that CLT fluctuations of the per-cell sum-rate C m are of order $$ 1/\sqrt m $$ , where m is the number of cells, whereas they are of order 1/m in classical random matrix theory. We also show an LD regime of the form P(|C m − C| > ɛ) ≤ e −mα with α = α(ɛ) > 0 and C = $$ \mathop {\lim }\limits_{m \to \infty } $$ C m , as opposed to the rate $$ e^{ - m^2 \alpha } $$ in classical random matrix theory.

We generalize the method for computing the number of errors correctable by a low-density parity-check (LDPC) code in a binary symmetric channel, which was proposed by V.V. Zyablov and M.S. Pinsker in 1975. This method is for the first time applied for computing the fraction of guaranteed correctable erasures for an LDPC code with a given constituent code used in an erasure channel. Unlike previously known combinatorial methods for computing the fraction of correctable erasures, this method is based on the theory of generating functions, which allows us to obtain more precise results and unify the computation method for various constituent codes of a regular LDPC code. We also show that there exist an LDPC code with a given constituent code which, when decoded with a low-complexity iterative algorithm, is capable of correcting any erasure pattern with a number of erasures that grows linearly with the code length. The number of decoding iterations, required to correct the erasures, is a logarithmic function of the code length. We make comparative analysis of various numerical results obtained by various computation methods for certain parameters of an LDPC code with a constituent single-parity-check or Hamming code.

Two codes C (1) and C (2) are said to be weakly isometric if there exists a mapping J: C (1) -> 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 a parts per thousand yen 2(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.

We consider properties of the matrix of a real quadratic form that takes a constant value on a sufficiently large set of vertices of a multidimensional cube centered at the origin given that the corresponding quadric does not separate vertices of the cube. In particular, we show that the number of connected components of the graph of the matrix of such a quadratic form does not change when one edge of the graph is deleted.

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.

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.