A new method for estimating the number of errors guaranteed to be corrected by a low-density parity-check code is proposed. The method is obtained by analyzing edges with special properties of an appropriate Tanner graph. In this paper we consider binary LDPC codes with constituent single-parity-check and Hamming codes and an iterative decoding algorithm. Numerical results obtained for the proposed lower bound exceed similar results for the best previously known lower bounds.

Two ensembles of low-density parity-check (LDPC) codes with low-complexity decoding algorithms are considered. The first ensemble consists of generalized LDPC codes, and the second consists of concatenated codes with an outer LDPC code. Error exponent lower bounds for these ensembles under the corresponding low-complexity decoding algorithms are compared. A modification of the decoding algorithm of a generalized LDPC code with a special construction is proposed. The error exponent lower bound for the modified decoding algorithm is obtained. Finally, numerical results for the considered error exponent lower bounds are presented and analyzed.

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.

We consider leader election and spanning tree construction problems in a synchronous network. Protocols are designed under the assumption that nodes in the network have identifiers but the size of an identifier is unlimited. We present fast protocols with runtime *O*(*D*log *L*+*L*), where *L* is the size of the minimal identifier and *D* is the network diameter.

The operation of Minkowski addition of geometric figures has a discrete analog, addition of subsets of a Boolean cube viewed as a vector space over the two-element field. Subsets of the Boolean cube (or multivariable Boolean functions) form a monoid with respect to this operation. This monoid is of interest in classical discrete analysis as well as in a number of problems related to information theory. We consider several complexity aspects of this monoid, namely structural, algorithmic, and algebraic.

We study the asymptotic behavior of probabilities of first-order properties for random uniform hypergraphs. In 1990, J. Spencer introduced the notion of a spectrum for graph properties and proved the existence of a first-order property with an infinite spectrum. In this paper we give a definition of a spectrum for properties of uniform hypergraphs and establish an almost tight bound for the minimum quantifier depth of a first-order formula with infinite spectrum.

This paper addresses the problem of constructing a multiple access sys- tem for a disjunctive vector channel, similar to multiuser channel without intensity information, as described in Chang S.C., Wolf J.K. On the T-User M-Frequency Noiseless Multiple-Access Channels with and without Intensity Information // IEEE Trans. Inform. Theory. 1981. V. 27. No 1. P. 41-48.. To solve this problem a signal-code construction based on the q-ary codes is proposed. It is shown that the proposed signal-code con- struction allows to obtain the asymptotic value of the total relative rate arbitrarily close to ln 2.

We propose an elementary solution to the apartment rent division problem. This problem belongs to the class of problems of “fair division,” but differs from its standard setting by “heterogeneity,” i.e., the presence of both a conventional continuous component and a discrete one, a fixed set of rooms. A combinatorial-topological approach to solving this problem in a finite number of steps (each of which requires a survey of all participants), actively used in the literature, allows to obtain an approximate decision only. We propose a fundamentally different setting, based on a priori estimates of each room by the participants and allowing, in principle, to consider various optimization tasks as well. Our approach is particularly relevant in the case of a large number of participants. We also note that the proposed approach allows to find a solution in a number of cases where the combinatorial-topological approach does not work.

Original Russian Text © M.L. Blank, 2016, published in Problemy Peredachi Informatsii, 2016, Vol. 52, No. 3, pp. 108–116.

The research was carried out at the Institute for Information Transmission Problems of the Russian Academy of Sciences at the expense of the Russian Science Foundation, project no. 14-50-00150.

We study zero-one laws for random distance graph with vertices in {−1, 0, 1} *^n* depending on a set of parameters. We give some conditions under which sequences of random distance graphs obey or do not obey the zero-one law.

An algorithm for generating parity-check matrices of regular low-density paritycheck codes based on permutation matrices and Steiner triple systems S(v, 3, 2), v = 2m − 1, is proposed. Estimations of the rate, minimum distance, and girth for obtained code constructions are presented. Results of simulation of the obtained code constructions for an iterative “belief propagation” (Sum-Product) decoding algorithm applied in the case of transmission over a binary channel with additive Gaussian white noise and BPSK modulation are presented.

The paper discusses generalized error locating (GEL) codes over the same alpha- bet for both component codes. The algorithm for computing upper bound on decoding error probability under known input symbol error rate and code parameters. Is is used for construct- ing the algorithm of code parameters selection that maximizes code rate for given construction and input and output error probabilities. The lower bound on on decoding error probability is given. The examples of wrong decoding probability versus input symbol error rate are given and their behavior is described.

We consider regular realizability problems, which consist in verifying whether the intersection of a regular language which is the problem input and a fixed language (filter) which is a parameter of the problem is nonempty. We study the algorithmic complexity of regular realizability problems for context-free filters. This characteristic is consistent with the rational dominance relation of CF languages. However, as we prove, it is more rough. We also give examples of both P-complete and NL-complete regular realizability problems for CF filters. Furthermore, we give an example of a subclass of CF languages for filters of which the regular realizability problems can have an intermediate complexity. These are languages with polynomially bounded rational indices.

We prove equivalence of using the modulus metric and Euclidean metric in solving the soft decoding problem for a memoryless discrete channel with binary input and *Q*-ary output. For such a channel, we give an example of a construction of binary codes correcting *t *binary errors in the Hamming metric. The constructed codes correct errors at the output of a demodulator with *Q *quantization errors as (*t*+1)(*Q−*1)*−*1 errors in the modulus metric. The obtained codes are shown to have polynomial decoding complexity.