Asymptotic bounds on the decoding error probability for two ensembles of LDPC codes
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.
Non-orthogonal multiple access schemes are of great interest for next generation wireless systems, as such schemes allow to reduce the total number of resources (frequencies or time slots) in comparison to orthogonal transmission (TDMA, FDMA, CDMA). In this paper we consider an iterative LDPC-based joint decoding scheme suggested in . We investigate the most difficult and important problem where all the users have the same power constraint and the same rate. For the case of 2 users we use a known scheme and analyze it by means of simulations. We found the optimal relation between the number of inner and outer iterations. We further extend the scheme for the case of any number of users and investigated the cases of 3 and 4 users by means of simulations. Finally, we showed, that considered non-orthogonal transmission scheme is more efficient (for 2 and 3 users), than orthogonal transmission.
A modification of the decoding q-ary Sum Product Algorithm (q-SPA) was proposed for the nonbinary codes with small check density based on the permutation matrices. The algorithm described has a vector realization and operates over the vectors defined on the field GF(q), rather than over individual symbols. Under certain code parameters, this approach enables significant speedup of modeling.
This paper deals with the error exponent of the regular graph-based binary low-density parity-check (LDPC) codes under the maximum likelihood (ML) decoding algorithm in the binary symmetric channel (BSC). Unlike other papers where error exponents are considered for the case when the length of LDPC codes tends to infinity (asymptotic analysis) we considered the finite length case (finite length analysis). In this paper we describe the method of deriving the lower bound on the error exponent for regular graph- based LDPC code with finite length under ML decoding and analyze the dependency of the error exponent on various LDPC code parameters. The numerical results, obtained for the considered lower bound, are represented and analyzed at the end of the paper.
Methods for constructing a mapping of the elements of a multiplicative group of a Galois field onto a symmetric group of permutation matrices are proposed. A technique minimizing the order of the symmetric group is suggested. The results are used for constructing an ensemble of low-density parity-check codes. The obtained code constructions are tested on an iterative belief propagation (sum-product) decoding algorithm on transmission of a code word through a binary channel with an additive Gaussian white noise.
We study the following computational problem: for which values of k, the majority of n bits MAJn can be computed with a depth two formula whose each gate computes a majority function of at most k bits? The corresponding computational model is denoted by MAJk o MAJk. We observe that the minimum value of k for which there exists a MAJk o MAJk circuit that has high correlation with the majority of n bits is equal to Θ(n1/2). We then show that for a randomized MAJk o MAJk circuit computing the majority of n input bits with high probability for every input, the minimum value of k is equal to n2/3+o(1). We show a worst case lower bound: if a MAJk o MAJk circuit computes the majority of n bits correctly on all inputs, then k ≥ n13/19+o(1). This lower bound exceeds the optimal value for randomized circuits and thus is unreachable for pure randomized techniques. For depth 3 circuits we show that a circuit with k = O(n2/3) can compute MAJn correctly on all inputs.
The preemptive single machine scheduling problem of minimizing the total weighted completion time with equal processing times and arbitrary release dates is one of the four single machine scheduling problems with an open computational complexity status. In this paper we present lower and upper bounds for the exact solution of this problem based on the assignment problem. We also investigate properties of these bounds and worst-case behavior.
We consider certain spaces of functions on the circle, which naturally appear in harmonic analysis, and superposition operators on these spaces. We study the following question: which functions have the property that each their superposition with a homeomorphism of the circle belongs to a given space? We also study the multidimensional case.
We consider the spaces of functions on the m-dimensional torus, whose Fourier transform is p -summable. We obtain estimates for the norms of the exponential functions deformed by a C1 -smooth phase. The results generalize to the multidimensional case the one-dimensional results obtained by the author earlier in “Quantitative estimates in the Beurling—Helson theorem”, Sbornik: Mathematics, 201:12 (2010), 1811 – 1836.
We consider the spaces of function on the circle whose Fourier transform is p-summable. We obtain estimates for the norms of exponential functions deformed by a C1 -smooth phase.
For a class of optimal control problems and Hamiltonian systems generated by these problems in the space l 2, we prove the existence of extremals with a countable number of switchings on a finite time interval. The optimal synthesis that we construct in the space l 2 forms a fiber bundle with piecewise smooth two-dimensional fibers consisting of extremals with a countable number of switchings over an infinite-dimensional basis of singular extremals.
The problem of minimizing the root mean square deviation of a uniform string with clamped ends from an equilibrium position is investigated. It is assumed that the initial conditions are specified and the ends of the string are clamped. The Fourier method is used, which enables the control problem with a partial differential equation to be reduced to a control problem with a denumerable system of ordinary differential equations. For the optimal control problem in the l2 space obtained, it is proved that the optimal synthesis contains singular trajectories and chattering trajectories. For the initial problem of the optimal control of the vibrations of a string it is also proved that there is a unique solution for which the optimal control has a denumerable number of switchings in a finite time interval.
This proceedings publication is a compilation of selected contributions from the “Third International Conference on the Dynamics of Information Systems” which took place at the University of Florida, Gainesville, February 16–18, 2011. The purpose of this conference was to bring together scientists and engineers from industry, government, and academia in order to exchange new discoveries and results in a broad range of topics relevant to the theory and practice of dynamics of information systems. Dynamics of Information Systems: Mathematical Foundation presents state-of-the art research and is intended for graduate students and researchers interested in some of the most recent discoveries in information theory and dynamical systems. Scientists in other disciplines may also benefit from the applications of new developments to their own area of study.
In this paper, we construct a new distribution corresponding to a real noble gas as well as the equation of state for it.