In this paper, we propose a novel state-space model to represent the behavior of sum-product algorithm (SPA) in the vicinity of a trapping set (TS) of a low-density parity-check (LDPC) code over the additive white Gaussian noise (AWGN) channel in the error floor region. The proposed model takes into account the non-linear behavior of SPA and dynamically adjusts the operating point of the model in accordance to the statistical properties of TS messages. This is in contrast to the existing linear state-space models which linearly approximate such behavior at around the operating point of zero. Simulation results are provided to demonstrate the higher accuracy of the proposed model in estimating the error floor of LDPC codes compared to the linear state-space model.

In this paper, a probabilistic analysis of the cycle distribution of protograph-based spatially coupled low-density parity-check (SC LDPC) codes is presented. In particular, we derive the probability that cycles of specific, but arbitrary, length are broken as a result of spatial coupling with a random spreading matrix in a general edge spreading process. Our results show that the probability of existence of cycles in SC codes is O(1/m), where m is the code memory. This result is independent of the cycle length.

In this paper, we propose a novel state-space model to represent the behavior of sum-product algorithm (SPA) in the vicinity of a trapping set (TS) of a low-density parity-check (LDPC) code over the additive white Gaussian noise (AWGN) channel in the error floor region. The proposed model takes into account the non-linear behavior of SPA in the initial iterations using a quadratic approximation, and dynamically adjusts the operating point of the model in accordance to the statistical properties of TS messages. This is in contrast to the existing linear state-space models which linearly approximate the non-linear behavior of SPA at around the operating point of zero in all iterations. Simulation results are provided to demonstrate the higher accuracy of the proposed model in estimating the error floor of LDPC codes compared to the linear state-space model. We also make connections to the semi-analytical code-dependent technique proposed by Richardson for the error floor estimation of LDPC codes, and demonstrate that the proposed state-space model not only is a fully-analytical code-independent counterpart to that method, but also has less complexity and, in some cases, more accuracy.

In this article, we design finite-length irregular protograph-based quasi-cyclic (QC) low-density parity-check (LDPC) codes with good waterfall performance and low error floor. To achieve a low error floor, we eliminate a targeted set of dominant elementary trapping sets (ETS) £ in the Tanner graph of the code. For a given rate and girth, the codes are designed to be free of the largest set of problematic ETSs for a given block length, or to have the shortest block length while a given set of ETSs is avoided. The design is based on a search algorithm that identifies whether any instance of any structure within £ exists in the Tanner graph of the constructed code or not. The search algorithm performs this task with minimal complexity, making it feasible to construct practical codes by running the search algorithm a large number of times. Simulation results are provided to demonstrate the superior performance of designed codes compared to similar state-of-the-art irregular QC-LDPC codes.

In this paper, we propose a design technique for the construction of variable-regular time-invariant spatially-coupled low-density parity-check (SC-LDPC) codes with small constraint length and low error floor. The proposed technique reduces the error floor by imposing simple constraints on the short cycles in the code's Tanner graph, which in turn, result in the elimination of the most dominant trapping sets of the code. In some cases, we also derive lower bounds on the syndrome former memory for satisfying such constraints. The designed codes are superior to the state-of-the-art in terms of error floor performance and/or decoding complexity and latency.

One of the key weaknesses of low-density parity-check (LDPC) codes is the error floor that they typically exhibit at high signal-to-noise ratios (SNRs). Such an error floor is usually attributed to problematic structures known as trapping sets (TSs). The overwhelming majority of existing error floor estimation schemes consider the case of binary phase shift keying (BPSK) signalling. Unfortunately, these schemes are not readily extensible to estimate the error floor of high order LDPC coded modulation systems considered herein. To provide such a scheme, in this work, we use mean-shift importance sampling (MS-IS) to develop a novel error floor estimation methodology for high-order pulse amplitude modulation (PAM) and quadrature amplitude modulation (QAM) LDPC coded systems. First, a computationally efficient graphical-based approach is used to identify the TSs of a given LDPC code. Subsequently, a novel analytical approach is devised to identify the TSs that are likely to have a higher contribution in the error floor. These TSs are referred to as potentially dominant TSs (PDTSs). Finally, a new methodology for categorizing the PDTSs into equivalence classes is developed. A representative PDTS of each equivalence class is chosen and an MS-IS framework is devised to obtain the error rate corresponding to each equivalence class. To arrive at the desired MS-IS scheme, we develop an algorithm that invokes the geometry of the constellation to determine the MS value. In contrast with the conventional MS-IS method used in BPSK signalling, in the proposed MS-IS scheme, the MS value is a variable that is determined based on the TS and the transmitted codeword. The computational complexity of the three main steps of our methodology, viz. extracting the PDTSs, determining the MS values, and applying the MS-IS scheme, depends merely on the size of the constellation and the structure of the code, but not on the SNR. Numerical simulations confirm the efficacy and accuracy of the proposed technique at different SNRs.

Alternating direction method of multipliers (ADMM) is an efficient implementation of linear programming (LP) decoding for low-density parity-check (LDPC) codes. By adding penalty terms to the objective function of the LP decoding model, ADMM variable node (VN) penalized decoding can suppress the non-integral solutions and improve the frame error rate (FER) performance in the low signal-to-noise ratio (SNR) region. In this paper, we propose a novel ADMM check node (CN) penalized decoding algorithm. Codeword solutions which satisfy all parity-check equations will have smaller penalty values than non-codeword solutions, including the non-integral solutions. We discuss the required properties of CN-penalty functions, propose a few functions that satisfy those properties, and study their performance/complexity trade-offs. We also investigate the convergence properties of the proposed algorithm and prove that its performance is independent of the transmitted codeword. Using Monte Carlo simulations and instanton analysis, we then demonstrate that the proposed CN-penalized decoder outperforms ADMM VN penalized decoders in both waterfall and error floor regions. This comes at the expense of some increase in the decoding complexity.

In this paper, we analyze the error floor of quasi-cyclic (QC) low-density parity-check (LDPC) codes decoded by the sum-product algorithm (SPA) with row layered message-passing scheduling. For this, we develop a linear state-space model of trapping sets (TSs) which incorporates the layered nature of scheduling. We demonstrate that the contribution of each TS to the error floor is not only a function of the topology of the TS, but also depends on the row layers in which different check nodes of the TS are located. This information, referred to as TS layer profile (TSLP), plays an important role in the harmfulness of a TS. As a result, the harmfulness of a TS in particular, and the error floor of the code in general, can significantly change by changing the order in which the information of different layers, corresponding to different row blocks of the parity-check matrix, is updated. We also study the problem of finding a layer ordering that minimizes the error floor, and obtain row layered decoders with error floor significantly lower than that of their flooding counterparts. As part of our analysis, we make connections between the parameters of the state-space model for a row layered schedule and those of the flooding schedule. Simulation results are presented to show the accuracy of analytical error floor estimates.

In this paper, we propose a new technique, based on the so-called breadth-first search algorithm, to count the short cycles of a bipartite graph. For a general bipartite graph with |V| nodes and girth g, our technique has a time complexity of O(|V|2Δ) to count g-cycles and (g + 2)-cycles, and a time complexity of O(|V|2Δ2) to count (g + 4)-cycles, where Δ is the maximum node degree in the graph. Moreover, for bi-regular bipartite graphs, the latter complexity is further reduced to O(|V|2Δ). Compared to the fastest known algorithm, which has a complexity O(g|V|2Δ2), the proposed method always has a lower complexity for counting g-cycles and (g + 2)-cycles. It also has a lower complexity for counting (g + 4)-cycles in bi-regular graphs and in scenarios where g is increased with the size of the graph. Related to the problem of counting short cycles, we also demonstrate, using a long-standing conjecture, that there is no algorithm with time complexity less than O(|V|2-2/1±i ) that can determine whether a given sparse bipartite graph has a cycle of length 4i. An important application of the results presented here is to count the short cycles of Tanner graphs of low-density parity-check (LDPC) codes.

The linear state-space model is a well-known code-independent method to estimate the contribution of a trapping set (TS) structure to the error floor of low-density parity-check (LDPC) codes. In this paper, we provide an in-depth analysis of this method by incorporating a more accurate model for the incoming messages to the TS structure that takes into account the randomness and the correlation among such messages. Based on this analysis, we demonstrate that both randomness and correlation result in the over-estimation of the failure probability of the TS. We then propose an alternate code-independent technique for the error floor estimation of iterative LDPC decoders that can accurately estimate the contribution of different TS structures in the error floor. Compared to the linear state-space model, the proposed method is not only more accurate, but also more general, in that, it is applicable to any saturating iterative message-passing decoder, symmetrically quantized or unquantized, over any memoryless binary-input output-symmetric channel. The proposed technique can be viewed as the local application of importance sampling (IS) to the message-passing algorithm over the subgraph induced by the TS in the code's Tanner graph. In the message-passing process, to account for the effect of the rest of the Tanner graph, density evolution along with a simple correlation model is used to generate the messages coming into the TS from the rest of the Tanner graph. Extensive simulations demonstrate that the proposed technique can accurately estimate the error floor of LDPC codes over both additive white Gaussian noise (AWGN) channel and binary symmetric channel (BSC), for a variety of iterative decoding algorithms and quantization schemes.

We propose a systematic design of protograph-based quasi-cyclic (QC) low-density parity-check (LDPC) codes with low error floor. We first characterize the trapping sets of such codes and demonstrate, using edge coloring techniques, that the QC structure of the code eliminates some of the trapping set structures that can exist in a code with the same degree distribution and girth but lacking the QC structure. Based on this characterization, our design aims at eliminating a targeted collection of trapping sets. Considering the parent/child relationship between the trapping sets in the collection, we search for and eliminate those trapping sets that are in the collection but are not a child of any other trapping set in the collection. An efficient layered algorithm is designed for the search of these targeted trapping sets. Compared to the existing codes in the literature, the designed codes are superior in the sense that they are free of the same collection of trapping sets while having a smaller block length, or a larger collection of trapping sets while having the same block length. In addition, the efficiency of the search algorithm makes it possible to design codes with larger degrees which are free of trapping sets within larger ranges compared to the state-of-the-art.

The problem of finding bipartite (Tanner) graphs with given degree sequences that have large girth and few short cycles is of great interest in many applications including construction of good low-density parity-check (LDPC) codes. In this paper, we prove that for given integers α, β, and -y, and degree sequences π and π', the problem of determining whether there exists a simple bipartite graph with degree sequences (π, π') that has at most α (β and -y) cycles of length four (six and eight, respectively) is NP-complete. This is proved by a two-step polynomial-time reduction from the 3-Partition Problem. On the other hand, using connections to linear hypergraphs, we prove that given the degree sequence π, a polynomial time algorithm can be devised to determine whether there exists a bipartite graph whose degree sequence on one side of the bipartition is π and has a girth of at least six. In addition to these complexity results, we devise a quasi-polynomial time algorithm that can construct a bipartite graph with given (irregular) degree sequences and a girth that increases logarithmically with the size of the graph. Compared to the well-known progressive-edge-growth (PEG) algorithm, the proposed method, in some cases, results in Tanner graphs with larger girth, particularly for scenarios where the degree sequences of the graph are strictly enforced.

Counting short cycles in bipartite graphs is a fundamental problem of interest in many fields including the analysis and design of low-density parity-check (LDPC) codes. There are two computational approaches to count short cycles (with length smaller than 2g, where g is the girth of the graph) in bipartite graphs. The first approach is applicable to a general (irregular) bipartite graph, and uses the spectrum {ηi} of the directed edge matrix of the graph to compute the multiplicity Nkof k-cycles with kk= Σiηik/(2k). This approach has a computational complexity O(|E|3), where |E| is number of edges in the graph. The second approach is only applicable to bi-regular bipartite graphs, and uses the spectrum {λi} of the adjacency matrix (graph spectrum) and the degree sequences of the graph to compute Nk. The complexity of this approach is O(|V|3), where |V| is number of nodes in the graph. This complexity is less than that of the first approach, but the equations involved in the computations of the second approach are complex and tedious, particularly for k ≥ g+6. In fact, the computational complexity of the equations increases exponentially with k. In this paper, we establish an analytical relationship between the two spectra {ηi} and {λi} for bi-regular bipartite graphs. Through this relationship, the former spectrum can be derived from the latter through simple equations with computational complexity constant in k. This allows the computation of Nkusing Nk= Σiηik/(2k) but with a complexity of O(|V|3) rather than O(|E|3).

The problem of finding bipartite (Tanner) graphs with given degree sequences that have large girth and few short cycles is of great interest in many applications including construction of good low-density parity-check (LDPC) codes. In this paper, we prove that for a given set of integers α, β, and γ, and degree sequences π and π', the problem of determining whether there exists a simple bipartite graph with degree sequences (π, π') that has at most α (β and γ) cycles of length four (six and eight, respectively) is NP-complete. This is proved by a two-step polynomial-time reduction from the 3-Partition Problem. On the other hand, using connections to linear hypergraphs, we prove that given the degree sequence π, a polynomial time algorithm can be devised to determine whether there exists a bipartite graph whose degree sequence on one side of the bipartition is π and has a girth of at least six.

Counting short cycles in bipartite graphs is a fundamental problem of interest in many fields including the analysis and design of low-density parity-check (LDPC) codes. There are two computational approaches to count short cycles (with length smaller than 2g, where g is the girth of the graph) in bipartite graphs. The first approach is applicable to a general (irregular) bipartite graph, and uses the spectrum {ηi} of the directed edge matrix of the graph to compute the multiplicity Nk of k-cycles with kk=Σiηik/(2k). This approach has a computational complexity O(|E|3), where |E| is number of edges in the graph. The second approach is only applicable to bi-regular bipartite graphs, and uses the spectrum {λi} of the adjacency matrix (graph spectrum) and the degree sequences of the graph to compute Nk. The complexity of this approach is O(|V|3), where |V| is number of nodes in the graph. This complexity is less than that of the first approach, but the equations involved in the computations of the second approach are very tedious, particularly for k ≥ g + 6. In this paper, we establish an analytical relationship between the two spectra {ηi} and {λi} for bi-regular bipartite graphs. Through this relationship, the former spectrum can be derived from the latter through simple equations. This allows the computation of Nkusing Nk= Σiηik/(2k) but with a complexity of O(|V|3) rather than O(|E|3).

This paper presents a novel log-likelihood ratio (LLR) calculation for high order coded modulation schemes over an additive white Gaussian noise channel at the presence of residual phase noise (RPN). Residual phase noise is known to significantly degrade the error rate performance of such systems, particularly at lower error rates, resulting in an early error floor. To model RPN, we consider the commonly used pilot symbol assisted modulation schemes for carrier recovery. We derive the exact formula for the calculation of LLR for such systems. To simplify the implementation, we also derive an approximation of LLR which reduces the complexity significantly with almost no loss in performance. The simulation results are presented for coded modulation schemes based on quadrature amplitude modulations and low-density parity-check codes. The simulations demonstrate significant performance improvement in the error rate as a result of using the new LLR calculation instead of the conventional calculation of LLR which ignores the RPN.

The performance of low-density parity-check (LDPC) codes in the error floor region is closely related to some substructures of the code's Tanner graph, collectively referred to as trapping sets (TSs). In this paper, we study the asymptotic average number of different types of trapping sets such as elementary TSs (ETS), leafless ETSs (LETS), absorbing sets (ABS), elementary ABSs (EABS), and stopping sets (SS), in random variable-regular and irregular LDPC code ensembles. We demonstrate that, regardless of the type of the TS, as the code's length tends to infinity, the average number of a given structure tends to infinity, to a positive constant, or to zero, if the structure contains no cycle, only one cycle, or more than one cycle, respectively. For the case where the structure contains a single cycle, we derive the asymptotic expected multiplicity of the structure by counting the average number of its constituent cycles and all the possible ways that the structure can be constructed from the cycle. This, in general, involves computing the expected number of cycles of a certain length with a certain given combination of node degrees, or computing the expected number of cycles of a certain length expanded to the desired structure by the connection of trees to its nodes. The asymptotic results obtained in this work, which are independent of the block length and only depend on the code's degree distributions, are shown to be accurate even for finite-length codes.

Cages, defined as regular graphs with minimum number of nodes for a given girth, are well-studied in graph theory. Trapping sets are graphical structures responsible for error floor of low-density parity-check (LDPC) codes, and are well investigated in coding theory. In this paper, we make connections between cages and trapping sets. In particular, starting from a cage (or a modified cage), we construct a trapping set in multiple steps. Based on the connection between cages and trapping sets, we then use the available results in graph theory on cages and derive tight upper bounds on the size of the smallest trapping sets for variable-regular LDPC codes with a given variable degree and girth. The derived upper bounds in many cases meet the best known lower bounds and thus provide the actual size of the smallest trapping sets. Considering that non-zero codewords are a special case of trapping sets, we also derive tight upper bounds on the minimum weight of such codewords, i.e., the minimum distance, of variable-regular LDPC codes as a function of variable degree and girth.

Counting short cycles in bipartite graphs is a fundamental problem of interest in the analysis and design of low-density parity-check codes. The vast majority of research in this area is focused on algorithmic techniques. Most recently, Blake and Lin proposed a computational technique to count the number of cycles of length g in a bi-regular bipartite graph, where g is the girth of the graph. The information required for the computation is the node degree and the multiplicity of the nodes on both sides of the partition, as well as the eigenvalues of the adjacency matrix of the graph (graph spectrum). In this paper, the result of Blake and Lin is extended to compute the number of cycles of length g+2, ... , 2g-2, for bi-regular bipartite graphs, as well as the number of 4-cycles and 6-cycles in irregular and half-regular bipartite graphs, with g ≥ 4 and g ≥ 6, respectively.

Leafless elementary trapping sets (LETSs) are known to be the problematic structures in the error floor region of low-density parity-check (LDPC) codes over the additive white Gaussian (AWGN) channel under iterative decoding algorithms. While problems involving the general category of trapping sets, and the subcategory of elementary trapping sets (ETSs), have been shown to be NP-hard, similar results for LETSs, which are a subset of ETSs are not available. In this paper, we prove that for a general LDPC code, finding a LETS of a given size a with minimum number of odd-degree check nodes b is NP-hard to approximate within any approximation factor. We also prove that finding the minimum size a of a LETS with a given b is NP-hard to approximate within any approximation factor. Similar results are proved for elementary absorbing sets, a popular subcategory of LETSs.

Leafless elementary trapping sets (LETSs) are known to be the problematic structures in the error floor region of low-density parity-check (LDPC) codes over the additive white Gaussian (AWGN) channel under iterative decoding algorithms. While problems involving the general category of trapping sets, and the subcategory of elementary trapping sets (ETSs), have been shown to be NP-hard, similar results for LETSs, which are a subset of ETSs, are not available. In this paper, we prove that, for a general LDPC code, finding a LETS of a given size α with minimum number of unsatisfied check nodes b is NP-hard to approximate with any guaranteed precision. We also prove that finding the minimum size a of a LETS with a given b is NP-hard to approximate. Similar results are proved for elementary absorbing sets, a popular subcategory of LETSs.

The performance of low-density parity-check (LDPC) codes in the error floor region is closely related to some substructures of the code's Tanner graph, collectively referred to as trapping sets (TSs). In this paper, we study the asymptotic average number of different types of trapping sets such as elementary TSs (ETS), leafless ETSs (LETS), absorbing sets (ABS), elementary ABSs (EABS), and stopping sets (SS), in random variable-regular and irregular LDPC code ensembles. We demonstrate that, regardless of the type of the TS, as the code's length tends to infinity, the average number of a given structure tends to infinity, to a positive constant, or to zero, if the structure contains no cycle, only one cycle, or more than one cycle, respectively. For the case where the structure contains a single cycle, we obtain an estimate of the expected number of the structure through the available approximations for the average number of the constituent cycle. These estimates, which are independent of the block length and only depend on the code's degree distributions, are shown to be accurate even for finite-length codes.

In this paper, we propose a characterization for nonelementary trapping sets (NETSs) of low-density parity-check (LDPC) codes. The characterization is based on viewing a NETS as a hierarchy of embedded graphs starting from an ETS. The characterization corresponds to an efficient search algorithm that under certain conditions is exhaustive. As an application of the proposed characterization/search, we obtain lower and upper bounds on the stopping distance smin of LDPC codes. We examine a large number of regular and irregular LDPC codes, and demonstrate the efficiency and versatility of our technique in finding lower and upper bounds on, and in many cases the exact value of, smin. Finding smin, or establishing search-based lower or upper bounds, for many of the examined codes are out of the reach of any existing algorithm.

In this paper, we study the cycle distribution of random low-density parity-check (LDPC) codes, randomly constructed protograph-based LDPC codes, and random quasicyclic (QC) LDPC codes. We prove that for a random bipartite graph, with a given (irregular) degree distribution, the distributions of cycles of different length tend to independent Poisson distributions, as the size of the graph tends to infinity. We derive asymptotic upper and lower bounds on the expected values of the Poisson distributions that are independent of the size of the graph, and only depend on the degree distribution and the cycle length. For a random lift of a bi-regular protograph, we prove that the asymptotic cycle distributions are essentially the same as those of random bipartite graphs as long as the degree distributions are identical. For random QC-LDPC codes, however, we show that the cycle distribution can be quite different from the other two categories. In particular, depending on the protograph and the value of c, the expected number of cycles of length c, in this case, can be either 8(N) or 8(1), where N is the lifting degree (code length). We also provide numerical results that match our theoretical derivations. Our results provide a theoretical foundation for emperical results that were reported in the literature but were not well-justified. They can also be used for the analysis and design of LDPC codes and associated algorithms that are based on cycles.

In this paper, we propose a characterization of elementary trapping sets (ETSs) for irregular low-density paritycheck (LDPC) codes. These sets are known to be the main culprits in the error floor region of such codes. The characterization of ETSs for irregular codes has been known to be a challenging problem due to the large variety of nonisomorphic ETS structures that can exist within the Tanner graph of these codes. This is a direct consequence of the variety of the degrees of the variable nodes that can participate in such structures. The proposed characterization is based on a hierarchical graphical representation of ETSs, starting from simple cycles of the graph, or from single variable nodes, and involves three simple expansion techniques: degree-one tree (dot), path, and lollipop, thus, the terminology dpl characterization. A similar dpl characterization was proposed in an earlier work by the authors for the leafless ETSs of variable-regular LDPC codes. The present paper generalizes the prior work to codes with a variety of variable node degrees and to ETSs that are not leafless. The proposed dpl characterization corresponds to an efficient search algorithm that, for a given irregular LDPC code, can find all the instances of (a, b) ETSs with size a and with the number of unsatisfied check nodes b within any range of interest a amax and b bmax, exhaustively. Although branch-&-bound exhaustive search algorithms for finding ETSs of irregular LDPC codes exist, to the best of our knowledge, the proposed search algorithm is the first of its kind, in that, it is devised based on a characterization of ETSs that makes the search process efficient. For a constant degree distribution and range of search, the worst-case complexity of the proposed dpl algorithm increases linearly with the block length n. The average complexity, excluding the search for the input simple cycles, is constant in n. Extensive simulation results are presented to show the versatility of the search algorithm, and to demonstrate that, compared to the literature, significant improvement in search speed can be obtained.

In this paper, we propose a characterization of elementary trapping sets (ETSs) for irregular low-density parity-check (LDPC) codes. These sets are known to be the main culprits in the error floor region of such codes. The proposed characterization is based on a hierarchical graphical representation of ETSs, starting from simple cycles of the graph, or from single variable nodes, and involves three simple expansion techniques: depth-one tree (dot), path and lollipop, thus, the terminology dpl characterization. The proposed dpl characterization corresponds to an efficient search algorithm, that, for a given irregular LDPC code, can find all the instances of (a, b) ETSs with size a and with the number of unsatisfied check nodes b, within any range of interest a ≤ amaxand b ≤ bmax, exhaustively. Simulation results are presented to show the versatility of the search algorithm, and to demonstrate that, compared to the literature, significant improvement in search speed can be obtained.

In this paper, we propose new constructions for regular girth-8 quasi-cyclic low-density parity-check (QC-LDPC) codes based on circulant permutation matrices (CPM). The constructions assume symmetries in the structure of the parity-check matrix and employ a greedy exhaustive search algorithm to find the permutation shifts of the CPMs. As a result of symmetries, the new codes have a more compact representation compared with their counterparts. In majority of cases, also, they achieve the girth 8 at a shorter block length for the same degree distribution (code rate). Deterministic (explicit) constructions are also presented to expand the proposed parity-check matrices to larger block lengths and higher rates. The proposed long high-rate codes are often substantially shorter than regular girth-8 QC-LDPC codes of similar rate in the literature. Simulation results demonstrate that the proposed symmetric codes have competitive performance in comparison with similar existing QC-LDPC codes that lack symmetry.

In this paper, we propose an efficient exhaustive search algorithm for elementary trapping sets (ETS) of variable-regular low-density parity-check (LDPC) codes. Recently, Karimi and Banihashemi proposed a characterization of ETSs, which was based on viewing an ETS as a layered superset (LSS) of a short cycle in the code's Tanner graph. A notable advantage of LSS characterization is that it corresponds to a simple LSS-based search algorithm (expansion technique) that starts from short cycles of the graph and finds the ETSs with LSS structure efficiently. Compared to the LSS-based search, which is based on a single LSS expansion technique, the new search algorithm involves two additional expansion techniques. The introduction of the new techniques results in significant improvements in search efficiency compared to the LSS-based search. We prove that using the three expansion techniques, each and every ETS structure can be obtained starting from a simple cycle. We also provide extensive simulation results that show, compared to the LSS-based search, up to three orders of magnitude improvement in search speed and memory requirements can be achieved.

In this paper, we propose a number of weighting/reweighting schemes to improve the performance of the so-called approximate message passing (AMP) algorithm of Donoho et al. We consider the application of AMP for the recovery of sparse signals from an under-determined system of linear equations, and variants of AMP for the recovery of block sparse signals. The proposed schemes for block sparse signals cover both cases of known and unknown block borders. Simulation results, both in noiseless and noisy scenarios, show significant performance improvement over the standard AMP algorithm and a considerably better performance/complexity trade-off compared to other state-of-the-art recovery algorithms.

In this paper, we propose a new characterization and an efficient exhaustive search algorithm for elementary trapping sets (ETS) of variable-regular low-density parity-check (LDPC) codes. Recently, Karimi and Banihashemi proposed a characterization of ETSs, which was based on viewing an ETS as a layered superset (LSS) of a short cycle in the code's Tanner graph. Compared to the LSS-based characterization, which is based on a single LSS expansion technique, the new characterization involves two additional expansion techniques. The introduction of the new techniques mitigates two problems that LSS-based characterization/search suffers from: (1) exhaustiveness: not every ETS structure is an LSS of a cycle, (2) search efficiency: LSS-based search algorithm often requires the enumeration of cycles with length much larger than the girth of the graph, where the multiplicity of such cycles increases rapidly with their length. We prove that using the three expansion techniques, any ETS structure can be obtained starting from a simple cycle, no matter how large the size of the structure a or the number of its unsatisfied check nodes b are, i.e., the characterization is exhaustive. We also demonstrate that for the proposed characterization to exhaustively cover all the ETS structures within the (a, b) classes with a ≤ amax, b ≤ bmax, for any value of amaxand bmax, the maximum length of the required cycles is minimal. The proposed characterization corresponds to a provably efficient search algorithm, significantly more efficient than the LSS-based search.

In this paper, we propose a new characterization for leafless elementary trapping sets (LETSs) of variable-regular lowdensity parity-check codes. Recently, Karimi and Banihashemi proposed a characterization of LETSs, which was based on viewing an LETS as a layered superset (LSS) of a short cycle in the code's Tanner graph. A notable advantage of LSS characterization is that it corresponds to a simple LSS-based search algorithm (expansion technique) that starts from short cycles of the graph and finds the LETSs with LSS structure efficiently. Compared with the LSS-based characterization of Karimi and Banihashemi, which is based on a single LSS expansion technique, the new characterization involves two additional expansion techniques. The introduction of the new techniques mitigates two problems that LSS-based characterization/search suffers from: 1) exhaustiveness: not every LETS structure is an LSS of a cycle and 2) search efficiency: LSS-based search algorithm often requires the enumeration of cycles with length much larger than the girth of the graph, where the multiplicity of such cycles increases rapidly with their length. We prove that using the three expansion techniques, any LETS structure can be obtained starting from a simple cycle, no matter how large the size of the structure a or the number of its unsatisfied check nodes b are, i.e., the characterization is exhaustive. We also demonstrate that for the proposed characterization/search to exhaustively cover all the LETS structures within the (a, b) classes with a amax and b bmax, for any value of amax and bmax, the length of the short cycles required to be enumerated is less than that of the LSS-based characterization/search. We, in fact, show that such a length for the proposed search algorithm is minimal. We also prove that the three expansion techniques, proposed here, are the only expansions needed for characterization of LETS structures starting from simple cycles in the graph, if one requires each and every intermediate sub-structure to be a LETS as well. Extensive simulation results are provided to show that, compared with LSS-based search, significant improvement in search speed and memory requirements can be achieved.

In this paper, we study the cycle structure of quasi-cyclic (QC) low-density parity-check (LDPC) codes with the goal of obtaining the shortest code with a given degree distribution and girth. We focus on QC-LDPC codes, whose Tanner graphs are cyclic liftings of fully connected base graphs of size 3 × n, n ≥ 4, and obtain minimal lifting degrees that result in girths 6 and 8. This is performed through an efficient exhaustive search, and as a result, we also find all the possible non-isomorphic codes with the same minimum block length, girth, and degree distribution. The exhaustive search, which is ordinarily a formidable task, is made possible by pruning the search space of many codes that are isomorphic to those previously examined in the search process. Many of the pruning techniques proposed in this paper are also applicable to QC-LDPC codes with base graphs other than the 3 × n fully connected ones discussed here, as well as to codes with a larger girth. To further demonstrate the effectiveness of the pruning techniques, we use them to search for QC-LDPC codes with girths 10 and 12, and find a number of such codes that have a shorter block length compared with the best known similar codes in the literature. In addition, motivated by the exhaustive search results, we tighten the lower bound on the block length of QC-LDPC codes of girth 6 constructed from fully connected 3 × n base graphs, and construct codes that achieve the lower bound for an arbitrary value of n ≥ 4.

Wideband spectrum sensing is a significant challenge in cognitive radios (CRs) due to requiring very high-speed analog-to-digital converters (ADCs), operating at or above the Nyquist rate. Here, we propose a very low-complexity zero-block detection scheme that can detect a large fraction of spectrum holes from the sub-Nyquist samples, even when the undersampling ratio is very small. The scheme is based on a block sparse sensing matrix, which is implemented through the design of a novel analog- to-information converter (AIC). The proposed scheme identifies some measurements as being zero and then verifies the sub-channels associated with them as being vacant. Analytical and simulation results are presented that demonstrate the effectiveness of the proposed method in reliable detection of spectrum holes with complexity much lower than existing schemes. This work also introduces a new paradigm in compressed sensing where one is interested in reliable detection of (some of the) zero blocks rather than the recovery of the whole block sparse signal.

In this paper, we propose solutions for the minimum-energy broadcasting problem for cross networks, where N nodes are located on two perpendicular lines. Our solutions consist of an algorithm which finds the optimal assignment in polynomial time, a near-optimal algorithm with less complexity (O(N)), and a distributed algorithm with complexity O(1) that gives acceptable results. To the best of our knowledge, this is the first study presenting an optimal solution for the minimum-energy broadcasting problem for a 2-D network (with cross configuration). We compare our algorithms with the broadcast incremental power (BIP) algorithm, one of the most commonly used methods for solving this problem with complexity O(N2). The results show that while the proposed optimal algorithm finds the best solution, our near-optimal algorithm performs better than BIP in all cases, and the distributed algorithm performs close to it. The performance of our non-optimal algorithms tend to be closer to the optimal solution for larger networks. We prove that all the algorithms perform the same in the asymptotic regime.

In this paper, we study the hop-count properties of one-dimensional wireless ad-hoc networks, where the nodes are placed independently and identically according to a Poisson distribution with an arbitrary density function. We derive exact equations to calculate the probability mass function of the number of hops needed for a node located at an arbitrary location in the network to receive a message from the source (located at one end of the linear network). Based on the derived formulas, we then propose localization methods. Through simulations, we show that our best proposed localization method not only has a competitive performance for a range-free method, but also outperforms range-based methods with a local distance measurement error of 10% or more. An important feature of our methods is that they are applicable to arbitrary densities. This is unlike the existing methods that are limited only to the case of uniform node densities. Moreover, the hop-count equations derived in this work can be used in analyzing other aspects of broadcasting protocols such as location verification, quality of service, and delay.

A low-complexity scheme for the reliable detection of zero blocks in a block sparse signal is proposed. The scheme is based on the application of verification based (VB) recovery algorithms in compressed sensing to block sparse signals, and is described in the context of wideband spectrum sensing (WSS). To apply VB algorithms to WSS, we devise a block sparse sensing matrix by designing a novel analog-to-information converter (AIC). The AIC, the sensing matrix and the VB algorithms are then optimized such that the largest number of zero blocks for a given number of measurements can be detected. This work introduces a new paradigm in the recovery of block sparse signals, where one is interested in partial detection of the complement of the support set, reliably, rather than the full recovery of the signal or its support. The analysis and simulations demonstrate significant improvement in performance/complexity over the existing block sparse recovery schemes within this new framework. An important application of the results would be in cognitive radios with limited computational resources.

In this paper, we study the hop-count properties of one-dimensional wireless ad-hoc networks, where the nodes are placed independently and identically according to a Poisson distribution with an arbitrary density function. We derive exact equations to calculate the probability mass function of two hop-count random variables: the number of hops needed for a node located at an arbitrary location in the network to receive a message from a node located at one end of the linear network, and the number of hops needed for a node located at one end of the network to receive a message from a node at an arbitrary location. Based on the derived formulas, we then propose localization and location verification methods. Through simulations, we show that our proposed localization method not only has a competitive performance for a range-free method, but also outperforms range-based methods with a local distance measurement error of 10% or more. Furthermore, the proposed location verification protocol is shown to have better results compared to the existing verification systems that also use the hop-count information. An important feature of our methods is that they are applicable to arbitrary densities. This is unlike the existing methods that are limited only to the case of uniform node densities. Using simulations, we also evaluate the proposed schemes in the presence of Rician fading and show that their performance is rather robust with respect to the change in the fading parameter. Moreover, the hop-count equations derived in this work can be used in analyzing other aspects of broadcasting protocols such as quality of service and delay.

In the above paper, there are some erroneous entries in Tables I, III, IV, VII, and X, which are corrected here. Moreover, for the proper application of the definition of layered superset (LSS) property to all the results of Tables I –VII in the above-mentioned paper, the LSS definition needs to be extended as described here.

In this work, we consider the problem of designing efficient feedback-based scheduling policies for chunked codes (CC) over single-path (line) networks with stochastic (queuing) delay. The state of the art in such policies are random push (RP) and local-rarest-first (LRF), which outperform the original policy of CC, namely the uniformly-at-random policy, in terms of the expected throughput even without any knowledge about the delay model. To our knowledge, however, this work is the first attempt to discover how much better one policy can do in an ideal case with perfect feedback when the model of delay is perfectly known. Towards this goal, we propose a new policy, referred to as transmitted-innovation-maximizer (TIM), based on the expected number of innovative packet transmissions at each transmitting node of the network by the next transmission time given the feedback information from the receiving node about the received packets. Our simulations show that TIM provides significantly larger (tighter) lower bounds on the maximum expected throughput (compared to the tightest existing bounds provided by LRF and RP), and thus it can be considered as the newest benchmark in this emerging line of research.

In this paper, we study the graphical structure of elementary trapping sets (ETSs) of variable-regular low-density parity-check (LDPC) codes. ETSs are known to be the main cause of error floor in LDPC coding schemes. For the set of LDPC codes with a given variable node degree dl and girth g, we identify all the nonisomorphic structures of an arbitrary class of (a, b) ETSs, where a is the number of variable nodes and b is the number of odd-degree check nodes in the induced subgraph of the ETS. This paper leads to a simple characterization of dominant classes of ETSs (those with relatively small values of a and b) based on short cycles in the Tanner graph of the code. For such classes of ETSs, we prove that any set S in the class is a layered superset (LSS) of a short cycle, where the term layered is used to indicate that there is a nested sequence of ETSs that starts from the cycle and grows, one variable node at a time, to generate S. This characterization corresponds to a simple search algorithm that starts from the short cycles of the graph and finds all the ETSs with LSS property in a guaranteed fashion. Specific results on the structure of ETSs are presented for dl= 3, 4, 5, 6, g = 6, 8, and a, b ≤ 10 in this paper. The results of this paper can be used for the error floor analysis and for the design of LDPC codes with low error floors.

A message-passing algorithm for counting short cycles in a graph is presented. For bipartite graphs, which are of particular interest in coding, the algorithm is capable of counting cycles of length g, g+2, ..., 2g-2, where g is the girth of the graph. For a general (non-bipartite) graph, cycles of length g, g+1, ..., 2g-1 can be counted. The algorithm is based on performing integer additions and subtractions in the nodes of the graph and passing extrinsic messages to adjacent nodes. The complexity of the proposed algorithm grows as O(g |E|2), where |E| is the number of edges in the graph. For sparse graphs, the proposed algorithm significantly outperforms the existing algorithms, tailored for counting em short cycles, in terms of computational complexity and memory requirements. We also discuss a more generic and basic approach of counting short cycles which is based on matrix multiplication, and provide a message-passing interpretation for such an approach. We then demonstrate that an efficient implementation of the matrix multiplication approach has essentially the same complexity as the proposed message-passing algorithm.

This paper describes a combinatorial approach to estimate the error rate performance of low-density parity-check (LDPC) codes decoded by (quantized) soft-decision iterative decoding algorithms. The method is based on efficient enumeration of input vectors with small distances to a reference vector whose elements are selected to be the most reliable values from the input alphabet. Several techniques, including modified cycle enumeration, and the efficient derivation of problematic inputs for finer quantizers from those of coarser ones are employed to reduce the complexity of the enumeration. The error rate estimate is derived by testing the input vectors of small distances followed by estimating the contribution of larger distance vectors. We demonstrate by a number of examples that the proposed method provides accurate estimates of error rate with computational complexity much lower than that of Monte Carlo simulations, especially at the error floor region.

In this paper, we study the relationships between the girth of the Tanner graph of a quasi-cyclic (QC) protograph low-density parity-check (LDPC) code, the lifting degree, and the size and the structure of the base graph. As a result, for a given base graph, we derive a lower bound on the lifting degree as a necessary condition for the lifted graph to have a certain girth. This also provides an upper bound on the girth of the family of graphs lifted from a given base graph with a given lifting degree. The upper bounds derived here, which are applicable to both regular and irregular base graphs with no parallel edges, are in some cases more general and in some other cases tighter than the existing bounds. The results presented in this work can be used to design cyclic liftings with relatively small degree and relatively large girth. As an example, we present new QC protograph LDPC code constructions with girth 8 using fully connected base graphs. These constructions provide upper bounds on the lifting degree required for achieving girth 8 using fully connected base graphs.

A major task in cognitive radios (CRs) is spectrum sensing. In a wide-band regime, this is a challenging task requiring very high-speed analog-to-digital converters (ADCs), operating at or above the Nyquist rate. Compressed sensing is recognized as an effective technique to significantly reduce the sampling rate in wideband spectrum sensing, taking advantage of the sparsity of the spectrum. The recovery of the spectrum from the samples at sub-Nyquist rates is usually achieved through the so-called ℓ1-norm minimization. A more effective recovery technique for block sparse signals, called ℓ2/ℓ1-norm minimization, can be used as a replacement for ℓ1-norm minimization to reduce the sampling rate and consequently simplify the implementation of ADCs even further. In this paper, we propose two iterative ℓ2/ ℓ1-norm minimization algorithms for the recovery of block sparse spectrums. Similar to the standard ℓ2/ℓ1-norm minimization, the proposed algorithms require the side information about the boundaries of the spectral blocks. We evaluate the performance of the proposed algorithms both in the absence and in the presence of noise, and demonstrate that for both cases, the proposed algorithms significantly outperform the existing ℓ1-minimization-based and standard ℓ2/ℓ1minimization recovery algorithms. The improvement in performance comes at a small cost in complexity increase.

In this paper, we present a probabilistic analysis of iterative node-based verification-based (NB-VB) recovery algorithms over irregular graphs in the context of compressed sensing. Verification-based algorithms are particularly interesting due to their low complexity (linear in the signal dimension n). The analysis predicts the average fraction of unverified signal elements at each iteration ℓ where the average is taken over the ensembles of input signals and sensing matrices. The analysis is asymptotic (n → ∞) and is similar in nature to the well-known density evolution technique commonly used to analyze iterative decoding algorithms. Compared to the existing technique for the analysis of NB-VB algorithms, which is based on numerically solving a large system of coupled differential equations, the proposed method is much simpler and more accurate. This allows us to design irregular sensing graphs for such recovery algorithms. The designed irregular graphs outperform the corresponding regular graphs substantially. For example, for the same recovery complexity per iteration, we design irregular graphs that can recover up to about 40% more non-zero signal elements compared to the regular graphs. Simulation results are also provided which demonstrate that the proposed asymptotic analysis matches the performance of recovery algorithms for large but finite values of n.

In this paper, we study the coding delay and the average coding delay of random linear network codes (dense codes) over line networks with deterministic regular and Poisson transmission schedules. We consider both lossless networks and networks with Bernoulli losses. The upper bounds derived in this paper, which are in some cases more general, and in some other cases tighter, than the existing bounds, provide a more clear picture of the speed of convergence of dense codes to the min-cut capacity of line networks.

In this paper, we study the relationships between the girth of the Tanner graph of a quasi cyclic (QC) protograph low-density parity-check (LDPC) code, on one hand, and the lifting degree and the size and the structure of the base graph, on the other hand. As a result, for a given base graph and a given lifting degree, we derive an upper bound on the girth of the resulting lifted graphs (codes). The upper bounds derived here are generally tighter than the existing bounds. The results presented in this work can be used to select an appropriate lifting degree for a given base graph, in order to have a desired girth, or to provide some insight in designing good base graphs, or to properly select the base graph's edge permutations.

We propose a technique to design finite-length irregular low-density parity-check (LDPC) codes over the binary-input additive white Gaussian noise (AWGN) channel with good performance in both the waterfall and the error floor region. The design process starts from a protograph which embodies a desirable degree distribution. This protograph is then lifted cyclically to a certain block length of interest. The lift is designed carefully to maximize the components of the approximate cycle extrinsic message degree (ACE) spectrum of the code's Tanner graph in a greedy fashion. As a consequence, the designed code would perform well in the error floor region. Moreover, the proposed construction results in quasi-cyclic codes which are attractive in practice due to simple encoder and decoder implementation. Simulation results are provided to demonstrate the effectiveness of the proposed construction in comparison with similar existing constructions.

A new approach for the approximation of the channel log-likelihood ratio (LLR) for wireless channels based on Taylor series is proposed. The approximation is applied to uncorrelated flat fading channels with unknown channel state information at the receiver. It is shown that the proposed approximation greatly simplifies the calculation of channel LLRs, and yet provides results almost identical to those based on the exact calculation of channel LLRs. The results are obtained in the context of bit-interleaved coded modulation (BICM) schemes with low-density parity-check (LDPC) codes, and include threshold calculations and error rate performance of finite-length codes. Compared to the existing approximations, the proposed method is either significantly less complex, or considerably more accurate.

Density evolution is often used to determine the performance of an ensemble of low-density parity-check (LDPC) codes under iterative message-passing algorithms. Conventional density evolution techniques over memoryless channels are based on the assumption that messages at iteration \ell are only a function of the messages at iteration \ell -1 and possibly the channel output. This assumption is valid for many algorithms such as standard belief propagation (BP) and min-sum (MS) algorithms. However, there are other important iterative algorithms such as successive relaxation (SR) versions of BP and MS, and differential decoding with binary message passing (DD-BMP) algorithm of Mobini et al., for which this assumption is not valid. The reason is the introduction of memory in these algorithms. In this work, we propose a model for iterative decoding algorithms with memory which covers SR and DD-BMP algorithms as special cases. Based on this model, we derive a Bayesian network for iterative algorithms with memory over memoryless channels and use this representation to analyze the performance of the algorithms using density evolution. The density evolution technique is developed based on truncating the memory of the decoding process and approximating it with a finite order Markov process, and can be implemented efficiently. As an example, we apply our technique to analyze the performance of DD-BMP on regular LDPC code ensembles, and make a number of interesting observations with regard to the performance/complexity tradeoff of DD-BMP in comparison with BP and MS algorithms. The model presented in this paper is based on certain simplifying assumptions about the memory structure of iterative algorithms such as the existence of memory only at the output of variable nodes in the code's Tanner graph rather than at both outputs of variable and check nodes. The Bayesian network framework introduced here however, can still be used to analyze the more general scenarios.

In this paper, we present a new approach for the analysis of iterative node-based verification-based (NB-VB) recovery algorithms in the context of compressed sensing. These algorithms are particularly interesting due to their low complexity (linear in the signal dimensionn). The asymptotic analysis predicts the fraction of unverified signal elements at each iterationlin the asymptotic regime wheren→∞. The analysis is similar in nature to the well-known density evolution technique commonly used to analyze iterative decoding algorithms. To perform the analysis, a message-passing interpretation of NB-VB algorithms is provided. This interpretation lacks the extrinsic nature of standard message-passing algorithms to which density evolution is usually applied. This requires a number of nontrivial modifications in the analysis. The analysis tracks the average performance of the recovery algorithms over the ensembles of input signals and sensing matrices as a function ofl. Concentration results are devised to demonstrate that the performance of the recovery algorithms applied to any choice of the input signal over any realization of the sensing matrix follows the deterministic results of the analysis closely. Simulation results are also provided which demonstrate that the proposed asymptotic analysis matches the performance of recovery algorithms for large but finite values ofn. Compared to the existing technique for the analysis of NB-VB algorithms, which is based on numerically solving a large system of coupled differential equations, the proposed method is more accurate and simpler to implement.

This paper presents an efficient algorithm for finding the dominant trapping sets of a low-density parity-check (LDPC) code. The algorithm can be used to estimate the error floor of LDPC codes or as a tool to design LDPC codes with low error floors. For regular codes, the algorithm is initiated with a set of short cycles as the input. For irregular codes, in addition to short cycles, variable nodes with low degree and cycles with low approximate cycle extrinsic message degree (ACE) are also used as the initial inputs. The initial inputs are then expanded recursively to dominant trapping sets of increasing size. At the core of the algorithm lies the analysis of the graphical structure of dominant trapping sets and the relationship of such structures to short cycles, low-degree variable nodes, and cycles with low ACE. The algorithm is universal in the sense that it can be used for an arbitrary graph and that it can be tailored to find a variety of graphical objects, such as absorbing sets and Zyablov-Pinsker trapping sets, known to dominate the performance of LDPC codes in the error floor region over different channels and for different iterative decoding algorithms. Simulation results on several LDPC codes demonstrate the accuracy and efficiency of the proposed algorithm. In particular, the algorithm is significantly faster than the existing search algorithms for dominant trapping sets.

A new approach for the approximation of the channel log-likelihood ratio (LLR) for wireless channels based on Taylor series is proposed. The approximation is applied to the uncorrelated flat Rayleigh fading channel with unknown channel state information at the receiver. It is shown that the proposed approximation greatly simplifies the calculation of channel LLRs, and yet provides results almost identical to those based on the exact calculation of channel LLRs. The results are obtained in the context of bit-interleaved coded modulation (BICM) schemes with low-density parity-check (LDPC) codes, and include threshold calculations and error rate performance of finite-length codes. Compared to the existing approximations, the proposed method is either significantly less complex, or considerably more accurate.

In this paper, the problem of MIMO signal detection based on the belief propagation (BP) algorithm has been addressed in the presence of channel and noise uncertainties at the receiver. We propose a robust detection approach that works on the basis of message passing algorithm on the best tree approximation of the posterior distribution of the received signal. Our approach to make the detector robust is to formulate a worst-case detector design as a min-max optimization problem with imperfect channel and noise knowledge at the receiver.

We propose a technique to design finite-length irregular low-density parity-check (LDPC) codes over the binary-input additive white Gaussian noise (AWGN) channel with good performance in both the waterfall and the error floor region. The design process starts from a protograph which embodies a desirable degree distribution. This protograph is then lifted cyclically to a certain block length of interest. The lift is designed carefully to satisfy a certain approximate cycle extrinsic message degree (ACE) spectrum. The target ACE spectrum is one with extremal properties, implying a good error floor performance for the designed code. The proposed construction results in quasi-cyclic codes which are attractive in practice due to simple encoder and decoder implementation. Simulation results are provided to demonstrate the effectiveness of the proposed construction in comparison with similar existing constructions.

In this paper, we present a new approach for the analysis of iterative node-based verification-based (NB-VB) recovery algorithms in the context of compressive sensing. These algorithms are particularly interesting due to their low complexity (linear in the signal dimension n). The asymptotic analysis predicts the fraction of unverified signal elements at each iteration ℓ in the asymptotic regime where n → ∞. The analysis is similar in nature to the well-known density evolution technique commonly used to analyze iterative decoding algorithms. To perform the analysis, a message-passing interpretation of NB-VB algorithms is provided. This interpretation lacks the extrinsic nature of standard message-passing algorithms to which density evolution is usually applied. This requires a number of non-trivial modifications in the analysis. The analysis tracks the average performance of the recovery algorithms over the ensembles of input signals and sensing matrices as a function of ℓ. Concentration results are devised to demonstrate that the performance of the recovery algorithms applied to any choice of the input signal over any realization of the sensing matrix follows the deterministic results of the analysis closely. Simulation results are also provided which demonstrate that the proposed asymptotic analysis matches the performance of recovery algorithms for large but finite values of n. Compared to the existing technique for the analysis of NB-VB algorithms, which is based on numerically solving a large system of coupled differential equations, the proposed method is much simpler and more accurate.

To lower the complexity of network codes over packet line networks with arbitrary schedules, chunked codes (CC) and overlapped chunked codes (OCC) were proposed in earlier works. These codes have been previously analyzed for relatively large chunks. In this paper, we prove that for smaller chunks, CC and OCC asymptotically approach the capacity with an arbitrarily small but non-zero constant gap. We also show that unlike the case for large chunks, the larger is the overlap size, the better would be the tradeoff between the speed of convergence and the message or packet error rate. This implies that OCC are superior to CC for shorter chunks. Simulations consistent with the theoretical results are also presented, suggesting great potential for the application of OCC for multimedia transmission over packet networks.

This paper presents an efficient algorithm for finding the dominant trapping sets of irregular low-density parity-check (LDPC) codes. The algorithm can be used to estimate the error floor of irregular LDPC codes or to be part of the apparatus to design irregular LDPC codes with low error floors. The algorithm is initiated with a set of short cycles, variable nodes with low degree, and cycles with low approximate cycle extrinsic message degree (ACE), as the input. The input structures are then expanded recursively to dominant trapping sets of increasing size. The algorithm is devised based on the careful inspection of the graphical structure of dominant trapping sets and the relationship of such structures to short cycles, low-degree variable nodes and cycles with low ACE. In particular, the important role of degree-2 variable nodes in the structure of dominant trapping sets is discussed. Simulation results on several LDPC codes demonstrate the accuracy and efficiency of the proposed algorithm. In particular, the algorithm is significantly faster than the existing search algorithms for dominant trapping sets.

In this paper, we investigate the problem of network coding and media scheduling in wireless multihop networks. Unique characteristics of the wireless media, such as omnidirectional transmissions and destructive interference, as well as having one transceiver per wireless node, imply new code design constraints for wireless networks. Here, we formulate a linear program to solve the joint scheduling and network coding problem. Using our formulation, we demonstrate that for a large percentage of randomly generated wireless networks, the optimal scheduling time shares are unequal. All the existing network code design algorithms are based on equal scheduling time shares or the considered joint optimization problems do not have sufficient information for scheduling flows during unequal time shares. Therefore, we provide these statistics to emphasize the importance of enabling the code design algorithms to include unequal time shares. Our simulations further show that the network throughput can be significantly improved if the network code is properly designed to incorporate unequal time shares.

A systematic construction of capacity achieving low-density parity-check (LDPC) code ensemble sequences over the Binary Erasure Channel (BEC) has been proposed by Saeedi et al. based on a method, here referred to as Successive Maximization (SM). In SM, the fraction of degree-i nodes are successively maximized starting from i = 2 with the constraint that the ensemble remains convergent over the channel. In this paper, we propose SM to design universally capacity approaching rate-compatible LDPC code ensemble sequences over the general class of Binary-Input Output-Symmetric Memoryless (BIOSM) channels. This is achieved by first generalizing the SM method to other BIOSM channels to design a sequence of capacity approaching ensembles called the parent sequence. The SM principle is then applied to each ensemble within the parent sequence, this time to design rate-compatible puncturing schemes. As part of our results, we extend the stability condition which was previously derived for degree-2 variable nodes to other variable node degrees as well as to the case of rate-compatible codes. Consequently, we prove that using the SM principle, one is able to design universally capacity achieving rate-compatible LDPC code ensemble sequences over the BEC. Unlike the previous results in the literature, the proposed SM approach is naturally extendable to other BIOSM channels. The performance of the rate-compatible schemes designed based on our method is comparable to those designed by optimization.

Cyclic liftings are proposed to lower the error floor of low-density parity-check (LDPC) codes. The liftings are designed to eliminate dominant trapping sets of the base code by removing the short cycles which are part of the trapping sets. We derive a necessary and sufficient condition for the cyclic permutations assigned to the edges of a cycle ξ of lengthl(ξ) in the base graph such that the inverse image of ξ in the lifted graph consists of only cycles of length strictly larger thanl(ξ). The proposed method is universal in the sense that it can be applied to any LDPC code over any channel and for any iterative decoding algorithm. It also preserves important properties of the base code such as degree distributions, and in some cases, the code rate. The constructed codes are quasi-cyclic and thus attractive from a practical point of view. The proposed method is applied to both structured and random codes over the binary symmetric channel (BSC). The error floor improves consistently by increasing the lifting degree, and the results show significant improvements in the error floor compared to the base code, a random code of the same degree distribution and block length, and a random lifting of the same degree. Similar improvements are also observed when the codes designed for the BSC are applied to the additive white Gaussian noise (AWGN) channel.

A new approach for the approximation of the channel log-likelihood ratio (LLR) for wireless channels based on Taylor series is proposed. The approximation is applied to the uncorrelated flat Rayleigh fading channel with unknown channel side information at the receiver. It is shown that the proposed approximation greatly simplifies the calculation of channel LLRs, and yet provides results almost identical to those based on the exact calculation of channel LLRs. The results are obtained in the context of iterative decoding of low-density parity-check (LDPC) codes and include threshold calculations and error rate performance of finite-length codes. Compared to the existing approximations, the proposed method is either significantly less complex, or considerably more accurate.

Cyclic liftings are proposed to lower the error floor of low-density parity-check (LDPC) codes. The liftings are designed to eliminate dominant trapping sets of the base code by removing the short cycles which form the trapping sets. We derive a necessary and sufficient condition for the cyclic permutations assigned to the edges of a cycle c of length ℓ(c) in the base graph such that the inverse image of c in the lifted graph consists of only cycles of length strictly larger than ℓ(c). The proposed method is universal in the sense that it can be applied to any LDPC code over any channel and for any iterative decoding algorithm. It also preserves important properties of the base code such as degree distributions. The proposed method is applied to both structured and random codes over the binary symmetric channel (BSC). The error floor improves consistently by increasing the lifting degree, and the results show significant improvements in the error floor compared to the base code, a random code of the same degree distribution and block length, and a random lifting of the same degree. Similar improvements are also observed when the codes designed for the BSC are applied to the additive white Gaussian noise (AWGN) channel.

We propose a systematic method to design irregular low-density parity-check (LDPC) codes for binary erasure channels (BEC). Compared to the existing methods, which are based on the application of asymptotic analysis tools such as density evolution or Extrinsic Information Transfer (EXIT) charts in an optimization process, the proposed method is much simpler and faster. Through a number of examples, we demonstrate that the codes designed by the proposed method perform very closely to the best codes designed by optimization. An important property of the proposed designs is the flexibility to select the number of constituent variable node degrees P. The proposed designs include existing systematic designs as a special case with P = N - 1, where N is the maximum variable node degree. Compared to the existing systematic designs, for a given rate and a given ¿ > 0, the designed ensembles can have a threshold in ¿-neighborhood of the capacity upper bound with smaller values of P and N. They can also achieve the capacity of the BEC as N, and correspondingly P and the maximum check node degree tend to infinity.

Existing design methods for irregular Low-Density Parity-Check (LDPC) codes over the additive white Gaussian noise channel are based on using asymptotic analysis tools such as density evolution in an optimization process. Such a process is computationally expensive particularly when a large number of constituent variable node degrees are involved in the design. In this paper, we propose a systematic approach for the design of irregular LDPC codes. The proposed method, which is based on a pre-computed upper bound on the fraction of edges connected to variable nodes of degree 3, is considerably less complex than the conventional optimization approach. Through a number of examples, we demonstrate that using our method, ensembles with performance very close to those devised based on optimization, can be designed. In addition to having very good performance, the number of constituent variable node degrees in the designed ensembles is only three or four. This, in some cases, is much smaller than the corresponding number for optimization-based designs with similar performance.

In this paper, new sequences$(\lambda ^{n},\rho ^{n})$of capacity achieving low-density parity-check (LDPC) code ensembles over the binary erasure channel (BEC) is introduced. These sequences include the existing sequences by Shokrollahias a special case. For a fixed code rate$R$, in the set of proposed sequences, Shokrollahi's sequences are superior to the rest of the set in that for any given value of$n$, their threshold is closer to the capacity upper bound$1- R$. For any given$\delta $,$0 < \delta < 1-R$, however, there are infinitely many sequences in the set that are superior to Shokrollahi's sequences in that for each of them, there exists an integer number$n_{0}$, such that for any$n > n_{0}$, the sequence$(\lambda ^{n},\rho ^{n})$requires a smaller maximum variable node degree as well as a smaller number of constituent variable node degrees to achieve a threshold within$\delta $-neighborhood of the capacity upper bound$1-R$. Moreover, it is proven that the check-regular subset of the proposed sequences are asymptotically quasi-optimal, i.e., their decoding complexity increases only logarithmically with the relative increase of the threshold. A stronger result on asymptotic optimality of some of the proposed sequences is also established.

An efficient rate allocation algorithm for the progressive transmission of multiple images over time-varying noisy channels is proposed. The algorithm is initiated by the distortion optimal solution for the first image and searches for the optimal rate-allocation for each subsequent image in the neighborhood of the solution for the previous image. Given the initial solution, the algorithm is linear-time in the number of transmitted packets per image and its rate allocation solution for each image can achieve a performance equal or very close to the distortion optimal solution for that image. Our simulations for the transmission of images, encoded by embedded source coders, over the binary symmetric channel (BSC) show that with very low complexity the proposed algorithm successfully adapts the channel code rates to the changes of the channel parameter.

An efficient policy allocation algorithm for the transmission of embedded bit streams over noisy channels with feedback is proposed. The transmission is based on the type-II Hybrid ARQ/FEC protocol and uses a nested sequence C of channel codes to protect the packets. There are also constraints on the total bit budget and on the allowed number of retransmissions per packet. The allocation algorithm assigns different protection policies, each policy being a subset of C, to different packets to maximize the average number of correctly received source bits. We study the performance and the complexity of the proposed scheme through the transmission of images encoded by JPEG2000 over mobile channels with correlated Rayleigh fading. We demonstrate by simulations that the proposed multiple-policy scheme provides significant improvements over a purely FEC scheme with no feedback and also the existing fixed-policy (equal error protection) schemes. Our results show that feedback is particularly helpful for poor channel conditions and that the proposed scheme is very robust against changes in the channel signal-to-noise ratio (SNR) and the mobile speed.

In this paper, we propose a binary message-passing algorithm for decoding low-density parity-check (LDPC) codes. The algorithm substantially improves the performance of purely hard-decision iterative algorithms with a small increase in the memory requirements and the computational complexity. We associate a reliability value to each nonzero element of the code's parity-check matrix, and differentially modify this value in each iteration based on the sum of the extrinsic binary messages from the check nodes. For the tested random and finitegeometry LDPC codes, the proposed algorithm can perform as close as about 1 dB and 0.5 dB to belief propagation (BP) at the error rates of interest, respectively. This is while, unlike BP, the algorithm does not require the estimation of channel signal to noise ratio. Low memory and computational requirements and binary message-passing make the proposed algorithm attractive for high-speed low-power applications.

An efficient policy allocation algorithm for the transmission of embedded bit streams over noisy channels with feedback is proposed. The transmission is based on the type-II hybrid ARQ/FEC protocol and uses a nested sequence C of channel codes to protect the packets. There are also constraints on the total bit budget and on the allowed number of retransmissions per packet. The allocation algorithm assigns different protection policies, each policy being a subset of C, to different packets to maximize the average number of correctly received source bits. We study the performance and the complexity of the proposed scheme through the transmission of images encoded by JPEG2000 over mobile channels with correlated Rayleigh fading. We demonstrate by simulations that the proposed multiple-policy scheme provides significant improvements over a purely FEC scheme with no feedback and also the existing fixed-policy schemes. Our results show that feedback is particularly helpful for poor channel conditions and that the proposed scheme is very robust against changes in the channel signal-to-noise ratio (SNR) and the mobile speed.

Belief propagation (BP) algorithm for decoding low-density parity-check (LDPC) codes over a binary input additive white Gaussian noise (BIAWGN) channel requires the knowledge of the signal-to-noise ratio (SNR) at the receiver to achieve its ultimate performance. An erroneous estimation or the absence of a perfect knowledge of the SNR at the decoder is referred to as "SNR mismatch". SNR mismatch can significantly degrade the performance of LDPC codes decoded by the BP algorithm. In this paper, using extrinsic information transfer (EXIT) charts, we design irregular LDPC codes that perform better (have a lower SNR threshold) in the presence of mismatch compared to the conventionally designed irregular LDPC codes that are optimized for zero mismatch. Considering that min-sum (MS) algorithm is the limit of BP with infinite SNR over-estimation, the EXIT functions generated in this work can also be used for the efficient analysis and design of LDPC codes under the MS algorithm.

The performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms can be accurately estimated if the weight J and the number |EJ| of the smallest error patterns that cannot be corrected by the decoder are known. To obtain J and |EJ|, one would need to perform the direct enumeration of error patterns with weight i les J. The complexity of enumeration increases exponentially with J, essentially as nJ, where n is the code block length. This limits the application of direct enumeration to codes with small n and J. In this letter, we approximate J and |EJ| by enumerating and testing the error patterns that are subsets of short cycles in the code's Tanner graph. This reduces the computational complexity by several orders of magnitude compared to direct enumeration, making it possible to estimate the error rates for almost any practical LDPC code. To obtain the error rate estimates, we propose an algorithm that progressively improves the estimates as larger cycles are enumerated. Through a number of examples, we demonstrate that the proposed method can accurately estimate both the bit error rate (BER) and the frame error rate (FER) of regular and irregular LDPC codes decoded by a variety of hard-decision iterative decoding algorithms.

The application of successive relaxation (SR) to the fixed-point problem associated with the iterative decoding of low-density parity-check (LDPC) codes was proposed by Hemati et al.. The simulation results presented by Hemati et al. for the SR version of belief propagation (BP) in the likelihood ratio (LR) domain and that of min-sum (MS) in the log-likelihood ratio (LLR) domain are based on the assumption of all-zero codeword transmission. This assumption however results in erroneous error rates when SR is applied in the LR domain. Here, we correct the simulation results reported by Hemati et al. for SR-BP in the LR domain. Furthermore, we investigate the performance of SR-BP and SR-MS in the LLR and LR domains, respectively. The results for a binary input additive white Gaussian noise (BIAWGN) channel show that for both BP and MS, the application of SR in the two domains of LR and LLR results in different error correcting performance. In particular, for the tested codes, it is shown that among the four algorithms, SR-MS-LLR has the best performance. It outperforms standard MS and BP by up to about 0.6 dB and 0.3 dB, respectively, offering an attractive solution in terms of performance/complexity tradeoff.

In this paper, we introduce new sequences (lambdan, rhon) of capacity achieving low-density parity-check (LDPC) code ensembles over the binary erasure channel (BEC). These sequences include the existing sequences by Shokrollahi as a special case. For a fixed code rate R, in the set of proposed sequences, Shokrollahipsilas sequences are superior to the rest of the set in that for any given value of n, their threshold is closer to the capacity upper bound 1 - R. For any given delta, 00, such that for any n > n0, the sequence (lambdan, rhon) requires a smaller maximum variable node degree as well as a smaller number of constituent variable node degrees to achieve a threshold within delta-neighborhood of the capacity upper bound 1 - R. Moreover, we prove that the check-regular subset of the proposed sequences are asymptotically quasi-optimal, i.e., their decoding complexity per iteration increases only logarithmically with the relative increase of the threshold. A stronger result on asymptotic optimality of some of the proposed sequences is also established.

This paper describes a combinatorial approach to estimate the error rate performance of low-density parity-check (LDPC) codes decoded by (quantized) soft-decision iterative decoding algorithms. The method is based on efficient enumeration of input vectors with small distances to a reference vector whose elements are selected to be the most reliable values from the input alphabet. Several techniques, including modified cycle enumeration, are employed to reduce the complexity of the enumeration. The error rate estimate is derived by testing the input vectors of small distances and estimating the contribution of larger distance vectors. We demonstrate by a number of examples that the proposed method provides accurate estimates of error rate with computational complexity much lower than that of Monte Carlo simulations, especially at the error floor region.

We propose a distortion optimal rate allocation algorithm for robust transmission of embedded bitstreams over noisy channels. The algorithm is based on the backward application of a Viterbi-like algorithm to a search trellis, and can be applied to both scenarios of fixed and variable channel packet length problems, referred to as FPP and VPP, respectively. For the VPP, the complexity of the algorithm is comparable to the well-known dynamic programming approach of Chande and Farvardin. For the FPP, where no low-complexity algorithm is known, the complexity of the proposed algorithm is O(N/sup 2/), where N is the number of transmitted packets.

In this paper, a globally distortion optimal solution is proposed for FPP. The method, which is applicable to any source with arbitrary distortion-rate characteristics, has quadratic complexity in N, where N is the number of transmitted packets. It is based on constructing a search trellis in which trellis levels represent the number of packets, trellis states at a given level i embody the possible source rates corresponding to i packets, and edges represent different code rates. Such a trellis, starts from a single root state and spreads out in N levels. We prove that the backward application of a Viterbi-like algorithm to this trellis starting from the final states and working towards the root results in a survivor path that provides us with the distortion optimal rate allocation solution. The proposed method can also be applied to VPP, providing an alternative to the algorithm of V. Chande and N. Farvardin (2000) with comparable complexity

In this paper, we propose a binary message-passing algorithm for decoding low-density parity-check (LDPC) codes. The algorithm substantially improves the performance of purely hard-decision iterative algorithms with a small increase in the memory requirements and the computational complexity. We associate a reliability value to each nonzero element of the code's parity-check matrix, and differentially modify this value in each iteration based on the sum of the extrinsic binary messages from the check nodes. For the tested random and finite-geometry LDPC codes, the proposed algorithm can achieve performance as close as 1.3 dB and 0.7 dB to that of belief propagation (BP) at the error rates of interest, respectively. This is while, unlike BP, the algorithm does not require the estimation of channel signal to noise ratio. Low memory and computational requirements and binary message-passing make the proposed algorithm attractive for high-speed low-power applications.

We propose a deterministic method to design irregular Low-Density Parity-Check (LDPC) codes for binary erasure channels. Compared to the existing methods, which are based on the application of asymptomatic analysis tools such as density evolution or Extrinsic Information Transfer (EXIT) charts in an optimization process, the proposed method is much simpler and faster. Through a number of examples, we demonstrate that the codes designed by the proposed method perform very closely to the best codes designed by optimization. It can also be proved that, the proposed code ensembles are capacity-achieving and are thus asymptotically optimal.

The performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms can be accurately estimated if the weight J and the number |Ej| of the smallest error patterns that cannot be corrected by the decoder are known. To obtain J and |Ej|, one would need to perform the direct enumeration of error patterns with weight i les J. The complexity of enumeration increases exponentially with J, essentially as nJ, where n is the code block length. In this paper, we approximate J and |Ej| by enumerating and testing the error patterns that are subsets of short cycles in the code's Tanner graph. This reduces the computational complexity by several orders of magnitude compared to direct enumeration, making it possible to estimate the error rates for almost any practical LDPC code. To obtain the error rate estimates, we propose an algorithm that progressively improves the estimates as larger cycles are enumerated. Through a number of examples, we demonstrate that the proposed method can accurately estimate both the bit error rate (BER) and the frame error rate (FER) of regular and irregular LDPC codes decoded by a variety of hard-decision iterative decoding algorithms.

This letter is concerned with the implementation of iterative decoding algorithms in analog integrated circuits. We study the convergence speed and the throughput of analog decoders for low-density parity-check codes, and show that they depend on the code, the decoding algorithm, the signal-to-noise ratio, and the average time constant of the analog circuit interconnections. However, they are not a function of the variance of the time constants. The analysis presented here can be used for selecting suitable codes and decoding algorithms for analog decoding. Furthermore, it can be used to estimate the throughput of an analog decoder, if the average time constant of the analog circuit is known

In this paper, we investigate the performance of the belief propagation (BP) algorithm for decoding low-density parity-check codes over the additive white Gaussian noise channel when there is an incorrect estimate of the channel signal-to-noise ratio (SNR) (referred to as "SNR mismatch") at the decoder. At the extremes for over- and underestimation of SNR, the performance of BP tends to that of min-sum algorithm and the channel bit-error rate, respectively. Our results for regular codes indicate that the sensitivity to mismatch increases by increasing the variable-node degree and by decreasing the check-node degree. The effect of variable-node degree, however, appears to be more profound, such that at a given rate, the codes with the smallest variable and check degrees are more robust against SNR mismatch. For irregular codes, by comparing the thresholds of a few ensembles, we demonstrate that the ensemble which performs better in the absence of mismatch can perform worse in the presence of it. To obtain our asymptotic results, we propose a computationally efficient method based on the Gaussian approximation of density evolution in the presence of SNR mismatch. We also show that the asymptotic results are consistent with simulation results for codes with finite block lengths

A method for estimating the performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms on binary symmetric channels (BSCs) is proposed. Based on the enumeration of the smallest weight error patterns that cannot be all corrected by the decoder, this method estimates both the frame error rate (FER) and the bit error rate (BER) of a given LDPC code with very good precision for all crossover probabilities of practical interest. Through a number of examples, we show that the proposed method can be effectively applied to both regular and irregular LDPC codes and to a variety of hard-decision iterative decoding algorithms. Compared with the conventional Monte Carlo simulation, the proposed method has a much smaller computational complexity, particularly for lower error rates.

Time-invariant hybrid (HscrTI) decoding of irregular low-density parity-check (LDPC) codes is studied. Focusing on HscrTIalgorithms with majority-based (MB) binary message-passing constituents, we use density evolution (DE) and finite-length simulation to analyze the performance and the convergence properties of these algorithms over (memoryless) binary symmetric channels. To apply DE, we generalize degree distributions to have the irregularity of both the code and the decoding algorithm embedded in them. A tight upper bound on the threshold of MB HscrTIalgorithms is derived, and it is proven that the asymptotic error probability for these algorithms tends to zero, at least exponentially, with the number of iterations. We devise optimal MB HscrTIalgorithms for irregular LDPC codes, and show that these algorithms outperform Gallager's algorithm A applied to optimized irregular LDPC codes. We also show that compared to switch-type algorithms, such as Gallager's algorithm B, where a comparable improvement is obtained by switching between different MB algorithms, MB HscrTIalgorithms are more robust and can better cope with unknown channel conditions, and thus can be practically more attractive.

In this paper, we propose a combined source/channel coding scheme for transmission of images over fading channels. The proposed scheme employs rate-compatible low-density parity-check (RC-LDPC) codes along with embedded image coders such as JPEG2000 (JP2K) and set partitioning in hierarchical trees (SPIHT). The assignment of channel coding rates to source packets is performed by a fast trellis-based algorithm. Simulation results for the expected peak signal-to-noise ratio (PSNR) of reconstructed images, which are within 1dB of the capacity upper bound over a wide range of channel signal-to-noise ratios (SNR), show considerable improvement compared to existing results under similar conditions. We also investigate the sensitivity of the proposed scheme in the presence of channel estimation error at the transmitter and demonstrate that under most conditions our scheme is more robust compared to existing schemes.

Conventional iterative decoding with flooding or parallel schedule can be formulated as a fixed-point problem solved iteratively by a successive substitution (SS) method. In this paper, we investigate the dynamics of a continuous-time (asynchronous) analog implementation of iterative decoding, and show that it can be approximated as the application of the well-known successive relaxation (SR) method for solving the fixed-point problem. We observe that SR with the optimal relaxation factor can considerably improve the error-rate performance of iterative decoding for short low-density parity-check (LDPC) codes, compared with SS. Our simulation results for the application of SR to belief propagation (sum-product) and min-sum algorithms demonstrate improvements of up to about 0.7 dB over the standard SS for randomly constructed LDPC codes. The improvement in performance increases with the maximum number of iterations, and by accordingly reducing the relaxation factor. The asymptotic result, corresponding to an infinite maximum number of iterations and infinitesimal relaxation factor, represents the steady-state performance of analog iterative decoding. This means that under ideal circumstances, continuous-time (asynchronous) analog decoders can outperform their discrete-time (synchronous) digital counterparts by a large margin. Our results also indicate that with the assumption of a truncated Gaussian distribution for the random delays among computational modules, the error-rate performance of the analog decoder, particularly in steady state, is rather independent of the variance of the distribution. The proposed simple model for analog decoding, and the associated performance curves, can be used as an "ideal analog decoder" benchmark for performance evaluation of analog decoding circuits.

In this letter, we consider the interleaver design in bit-interleaved coded modulation (BICM) with low-density parity-check (LDPC) codes. The design paradigm is to provide more coding protection through iterative decoding to bits that are less protected by modulation (and are thus less reliable at the output of the demodulator). The design is carried out by an ad hoc search algorithm over the column permutations of the parity-check matrix. Our simulations show that the proposed reliability-based coded modulation scheme can improve the error-rate performance of conventional BICM schemes based on regular LDPC codes by a few tenths of a decibel, with no added complexity.

We propose a fast trellis-based rate-allocation algorithm for robust transmission of progressively coded images over noisy channels. The algorithm, which is an improved version of a similar algorithm by Banister et al., is based on the application of the Viterbi algorithm to a search trellis. This trellis is a substantially trimmed version of the one used by Banister et al.. The proposed algorithm is applied to images encoded by the set partitioning in hierarchical trees and the Joint Photographers Expert Group 2000 for transmission over binary symmetric channels. For different total bit budgets and channel parameters, speed-up factors of up to about three orders of magnitude are achieved.

In this paper, we propose a combined source/channel coding scheme for transmission of images over fading channels. The proposed scheme employs rate-compatible low-density parity-check codes along with embedded image coders such as JPEG2000 and set partitioning in hierarchical trees (SPIHT). The assignment of channel coding rates to source packets is performed by a fast trellis-based algorithm. We examine the performance of the proposed scheme over correlated and uncorrelated Rayleigh flat-fading channels with and without side information. Simulation results for the expected peak signal-to-noise ratio of reconstructed images, which are within 1 dB of the capacity upper bound over a wide range of channel signal-to-noise ratios, show considerable improvement compared to existing results under similar conditions. We also study the sensitivity of the proposed scheme in the presence of channel estimation error at the transmitter and demonstrate that under most conditions our scheme is more robust compared to existing schemes.

Low-density parity-check codes (LDPC) can have an impressive performance under iterative decoding algorithms. In this paper we introduce a method to construct high coding gain lattices with low decoding complexity based on LDPC codes. To construct such lattices we apply Construction D', due to Bos, Conway, and Sloane, to a set of parity checks defining a family of nested LDPC codes. For the decoding algorithm, we generalize the application of max-sum algorithm to the Tanner graph of lattices. Bounds on the decoding complexity are derived and our analysis shows that using LDPC codes results in low decoding complexity for the proposed lattices. The progressive edge growth (PEG) algorithm is then extended to construct a class of nested regular LDPC codes which are in turn used to generate low density parity check lattices. Using this approach, a class of two-level lattices is constructed. The performance of this class improves when the dimension increases and is within 3 dB of the Shannon limit for error probabilities of about 10-6. This is while the decoding complexity is still quite manageable even for dimensions of a few thousands

Summary form only given. The fast trellis-based rate-allocation algorithm, which is an improved version of a similar algorithm presented by B.A. Banister et al. (see IEEE Sig. Process. Lett., vol.9, no.4, p.117-19, 2002), is based on the application of the Viterbi algorithm to a search trellis. The proposed algorithm is applied to images progressively encoded by set partitioning in hierarchical trees (SPIHT) and JPEG-2000 for transmission over noisy binary symmetric channels. For different total bit budgets and channel parameters, speed-up factors of up to about three orders of magnitude are achieved.

Current-mode circuits are presented for implementing analog min-sum (MS) iterative decoders. Proposed circuits are devised based on current mirrors. Therefore, in any fabrication technology that accurate current mirrors can be designed, analog MS decoders can be implemented. The functionality of the proposed modules was verified by implementing an analog MS decoder for a (32,8,10) regular LDPC code in 0.18-mum CMOS technology. In low signal to noise ratios when the circuit imperfections are dominated by the noise of the channel, the measured error correcting performance of this chip in steady-state condition surpasses that of the conventional MS decoder, and is close to the performance predicted by the earlier work on the dynamics of the continuous-time analog decoding by Hemati and Banihashemi, ISIT2004. At a throughput of 24 Mb/s, loss in the coding gain compared to the conventional MS decoder at BER of 10-3is about 0.3 dB. To the best of our knowledge, this decoder has the highest throughput and the lowest power/speed ratio among the reported analog CMOS iterative decoders

Time-invariant hybrid (HTI) decoding of irregular low-density parity-check (LDPC) codes is studied. Focusing on HTIalgorithms with majority-based (MB) binary message-passing constituents, we use density evolution and finite-length simulation to analyze the performance and the convergence properties of these algorithms. Tight upper bounds on the threshold of MB HTIalgorithms are derived, and it is proven that the asymptotic error probability for these algorithms tends to zero at least exponentially with the number of iterations. We devise optimal MB HTIalgorithms for irregular LDPC codes, and show that these algorithms outperform Gallager's algorithm A applied to optimized irregular LDPC codes. We also show that compared to switch-type algorithms, such as Gallager's algorithm B, where a comparable improvement is obtained by switching between different MB algorithms, MB HTIalgorithms are more robust, and can better cope with unknown channel conditions, and thus can be practically more attractive

The effects of clipping and quantization on the performance of the min-sum algorithm for the decoding of low-density parity-check (LDPC) codes at short and intermediate block lengths are studied. It is shown that in many cases, only four quantization bits suffice to obtain close to ideal performance over a wide range of signal-to-noise ratios. Moreover, we propose modifications to the min-sum algorithm that improve the performance by a few tenths of a decibel with just a small increase in decoding complexity. A quantized version of these modified algorithms is also studied. It is shown that, when optimized, modified quantized min-sum algorithms perform very close to, and in some cases even slightly outperform, the ideal belief-propagation algorithm at observed error rates.

Conventional iterative decoding with flooding or parallel schedule can be formulated as a fixed-point problem solved iteratively by the successive substitution (SS) method. In this work, we investigate the dynamics of continuous-time asynchronous analog implementation of iterative decoding, and show that it can be approximated as the application of the well-known successive overrelaxation (SOR) method for solving the fixed-point problem. We observe that SOR with the optimal relaxation factor can considerably improve the performance of iterative decoding for short low-density parity-check (LDPC) codes compared to SS. Our simulation results for the application of SOR to belief propagation (sum-product) and min-sum algorithms demonstrate improvements of up to about 0.7 dB over the standard SS for randomly constructed LDPC codes. The improvement in performance increases with the maximum number of iterations and by accordingly reducing the relaxation factor. The asymptotic result, corresponding to infinite maximum number of iterations and infinitesimal relaxation factor represents the performance of analog continuous-time asynchronous iterative decoding. This means that under ideal circumstances continuous-time asynchronous analog decoders can outperform their discrete-time synchronous digital counterparts by a large margin. The proposed model for analog decoding, and the associated performance curves, can be used as an "ideal analog decoder" benchmark for performance evaluation of analog decoding circuits.

The progressive-edge-growth (PEG) algorithm (X.-Y. Hu et al., 2001; 2002) is known to construct low-density parity-check codes at finite block lengths with very good performance. We propose a very simple modification to the PEG construction for irregular codes, which considerably improves the performance at high signal-to-noise ratios (SNR) with no sacrifice in low-SNR performance.

The use of multiple antennas at the BS (base station) allows significant improvements on the spectral efficiency of wireless communication systems by increasing the number of simultaneous users in a given cell. We introduce a new iterative multiuser detection scheme for systems requiring high-rate transmission in severe time-dispersive channels. We consider the use of single-carrier modulation combined with frequency-domain equalization techniques, which are known to be excellent candidates for severe time-dispersive channels. The BS employs multiple antennas and consists of an iterative LST (layered space-time) receiver combined with frequency-domain equalization techniques. Our performance results show that the proposed receiver structure has excellent performance, which can be very close to the matched filter bound, even for severe time-dispersive channels and in the presence of strongly interfering channels.

A reliability-based message-passing schedule for iterative decoding of low-density parity-check codes is proposed. Simulation results for bit-flipping algorithms (with binary messages) show that reliability-based schedule can provide considerable improvement in performance and decoding speed over the so-called flooding (parallel) schedule as well as the existing graph-based schedules. The cost associated with this improvement is negligible and is equivalent to having a 2-bit representation for initial messages, instead of the standard 1-bit for hard-decision algorithms, only at the first iteration (all the exchanged messages are still binary).

This paper deals with the problem of devising an efficient framework for constructing rate-compatible low-density parity-check (RC-LDPC) codes. We present a deterministic framework for constructing a family of linear-time encodable RC-LDPC codes from a mother code using puncturing and extending. Application of the proposed construction to a type-II hybrid ARQ scheme with information block length k=1024 and code rates 8/19 to 8/10, using an optimized irregular mother code of rate 8/13, results in a throughput which is only about 0.7dB away from Shannon limit. This outperforms existing similar schemes based on turbo codes and LDPC codes by up to 0.5dB.

Hybrid decoding is to combine different iterative decoding algorithms with the aim of improving error performance or decoding complexity. In this work, we introduce "time-invariant" hybrid (HTI) algorithms, and show that for regular low-density parity-check codes and binary message-passing algorithms, HTIalgorithms perform remarkably better than their constituent algorithms. We also show that compared to "switch-type" hybrid algorithms, such as Gallager's algorithm B, where a comparable improvement is obtained by switching between different iterative decoding algorithms, HTIalgorithms are far less sensitive to channel conditions and thus can be practically more attractive.

Iterative decoding with flooding schedule can be formulated as a fixed-point problem solved iteratively by successive substitution (88) method. In this work, we model continuous-time analog (asynchronous) iterative decoding by a first-order differential equation, and show that it can be approximated as the application of the well-known successive over relaxation (SOR) method for solving the fixed-point problem. Simulation results for belief propagation (sum-product) and min-sum algorithms confirm that SOR, which is in general superior to the simpler 88 method, can considerably improve the performance of iterative decoding for short codes. The improvement in performance increases with the maximum number of iterations and by reducing the step size in SOR, and the asymptotic result, corresponding to infinite maximum number of iterations and infinitesimal step size represents the performance of continuous-time analog iterative decoding. This means that under ideal circumstances continuous-time analog decoders can outperform their discrete-time digital counterparts by a large margin. Moreover, the results obtained by the proposed model are surprisingly close to the results of circuit simulation of a min-sum analog decoder presented in [S. Hemati et al., 2003]. Our work also suggests a general framework for improving iterative decoding algorithms on graphs with cycles, even for synchronous digital implementations.

A reliability-based message-passing schedule for iterative decoding of low-density parity-check codes is proposed. Simulation results for bit-flipping algorithms (with binary messages) show that a reliability-based schedule can provide considerable improvement in performance and decoding speed over the so-called flooding (parallel) schedule, as well as the existing graph-based schedules. The cost associated with this improvement is negligible and is equivalent to having a two-bit representation for initial messages, instead of the standard one bit for hard-decision algorithms, only at the first iteration (all the exchanged messages are still binary).

We study a wide range of graph-based message-passing schedules for iterative decoding of low-density parity-check (LDPC) codes. Using the Tanner graph (TG) of the code and for different nodes and edges of the graph, we relate the first iteration in which the corresponding messages deviate from their optimal value (corresponding to a cycle-free graph) to the girths and the lengths of the shortest closed walks in the graph. Using this result, we propose schedules, which are designed based on the distribution of girths and closed walks in the TG of the code, and categorize them as node based versus edge based, unidirectional versus bidirectional, and deterministic versus probabilistic. These schedules, in some cases, outperform the previously known schedules, and in other cases, provide less complex alternatives with more or less the same performance. The performance/complexity tradeoff and the best choice of schedule appear to depend not only on the girth and closed-walk distributions of the TG, but also on the iterative decoding algorithm and channel characteristics. We examine the application of schedules to belief propagation (sum-product) over additive white Gaussian noise (AWGN) and Rayleigh fading channels, min-sum (max-sum) over an AWGN channel, and Gallager's algorithm A over a binary symmetric channel.

This work presents a detailed study of a family of binary message-passing decoding algorithms for low-density parity-check (LDPC) codes, referred to as "majority-based algorithms." Both Gallager's algorithm A (G/sub A/) and the standard majority decoding algorithm belong to this family. These algorithms, which are, in fact, the building blocks of Gallager's algorithm B (G/sub B/), work based on a generalized majority-decision rule and are particularly attractive for their remarkably simple implementation. We investigate the dynamics of these algorithms using density evolution and compute their (noise) threshold values for regular LDPC codes over the binary symmetric channel. For certain ensembles of codes and certain orders of majority-based algorithms, we show that the threshold value can be characterized as the smallest positive root of a polynomial, and thus can be determined analytically. We also study the convergence properties of majority-based algorithms, including their (convergence) speed. Our analysis shows that the stand-alone version of some of these algorithms provides significantly better performance and/or convergence speed compared with G/sub A/. In particular, it is shown that for channel parameters below threshold, while for G/sub A/ the error probability converges to zero exponentially with iteration number, this convergence for other majority-based algorithms is super-exponential.

In this paper, a novel current-mode approach is proposed for implementing basic building blocks of an analog iterative decoder. The decoder is based on the so-called min-sum algorithm (also referred to as max-sum or max-product) and can be used to decode powerful coding schemes such as low-density parity-check (LDPC) codes and turbo codes. The proposed circuits can be implemented by standard CMOS technology, which means lower fabrication cost and/or simpler design compared to previously reported analog iterative decoders that are based on BiCMOS or sub-threshold CMOS technology. To demonstrate the functionality of the proposed design, simulation results based on TSMC 0.18mm CMOS technology for a (7,4) Hamming code are also presented.

This paper is concerned with the implementation issues of the so-called min-sum algorithm (also referred to as max-sum or max-product) for the decoding of low-density parity-check (LDPC) codes. The effects of clipping threshold and the number of quantization bits on the performance of the min-sum algorithm at short and intermediate block lengths are studied. It is shown that min-sum is robust against quantization effects, and in many cases, only four quantization bits suffices to obtain close to ideal performance. We also propose modifications to the min-sum algorithm that improve the performance by a few tenths of a dB with just a small increase in decoding complexity.

The best known practical algorithm for the decoding of low-density parity-check (LDPC) codes is the iterative sum-product or belief propagation algorithm, operating on a Tanner graph (TG) of the code. Conventionally, in each iteration, all the symbol nodes and subsequently all the check nodes in the TG pass new messages to their neighbors (the so-called "flooding schedule"). We propose a new message-passing schedule, called "probabilistic schedule". Unlike flooding, the probabilistic schedule operation is based on the structure of the TG, and probabilistically balances the frequency at which different symbol nodes update their outgoing messages in accordance with their girths. Our results show that, particularly for short block lengths, the new schedule offers a much better performance/complexity trade-off. For a particular example of a (1268, 456) code, at no cost in complexity, the probabilistic schedule not only decreases both the bit and message error rates by an order of magnitude, but also reduces the number of undetected errors considerably. This work shows the importance of scheduling in the performance of iterative decoding algorithms and suggests that a schedule which matches the structure of the TG can substantially improve the performance/complexity trade-off in the decoding of short LDPC codes.

For a given block length and given degree sequences of the underlying Tanner graph (TG), the ensemble of short low-density parity-check (LDPC) codes can have considerable variation in performance. We present an efficient heuristic method to find good LDPC codes based on what we define as the girth distribution of the TG. This method can be used effectively to design short codes for applications where delay and complexity are of major concern.

We develop a Tanner graph (TG) construction for an Abelian group block code L with arbitrary alphabets at different coordinates, an important application of which is the representation of the label code of a lattice. The construction is based on the modular linear constraints imposed on the code symbols by a set of generators for the dual code L*. As a necessary step toward the construction of a TG for L we devise an efficient algorithm for finding a generating set for L*. In the process, we develop a construction for lattices based on an arbitrary Abelian group block code, called generalized Construction A (GCA), and explore relationships among a group code, its GCA lattice, and their duals. We also study the problem of finding low-complexity TGs for Abelian group block codes and lattices; and derive tight lower bounds on the label-code complexity of lattices. It is shown that for many important lattices, the minimal label codes which achieve the lower bounds cannot be supported by cycle-free Tanner graphs.

Trellis complexity of root lattices A/sub n/, D/sub n/, E/sub n/, and their duals is investigated. Using N, the number of distinct paths in a trellis, as the measure of trellis complexity for lattices, a trellis is called minimal if it minimizes N. It is proved that the previously discovered trellis diagrams of some of the above lattices (D/sub n/, n odd, A/sub n/, 4/spl les/n/spl les/9, A/sub 4/*, A/sub 5/*, A/sub 6/*, A/sub 9/*, E/sub 6/, E/sub 6/*, and E/sub 7/*) are minimal. We also obtain minimal trellises for A/sub 7/* and A/sub 8/*. It is known that the complexity N of any trellis of an n-dimensional lattice with coding gain /spl gamma/ satisfies N/spl ges//spl gamma//sup n/2/. Here, this lower bound is improved for many of the root lattices and their duals. For A/sub n/ and A/sub n/* lattices, we also propose simple constructions for low-complexity trellises in an arbitrary dimension n, and derive tight upper bounds on the complexity of the constructed trellises. In some dimensions, the constructed trellises are minimal, while for some other values of n they have lower complexity than previously known trellises.

This paper presents results on trellis complexity and low-complexity trellis diagrams of lattices. We establish constructive upper bounds on the trellis complexity of lattices. These bounds both improve and generalize the similar results of Tarokh and Vardy (see ibid., vol.43, p.1294-1300, 1997). We also construct trellis diagrams with minimum number of paths for some important lattices. Such trellises are called minimal. The constructed trellises, which are novel in many cases, can be employed to efficiently decode the lattices via the Viterbi algorithm. In particular, a general structure for minimal trellis diagrams of D/sub n/ lattices is obtained. This structure corresponds to a new code formula for D/sub n/. Moreover, we develop some important duality results which are used in both deriving the upper bounds, and finding the minimal trellises. All the discussions are based on a universal approach to the construction and analysis of trellis diagrams of lattices using their bases.

Upper and lower bounds are derived for the decoding complexity of a general lattice L. The bounds are in terms of the dimension n and the coding gain /spl gamma/ of L, and are obtained based on a decoding algorithm which is an improved version of Kannan's (1983) method. The latter is currently the fastest known method for the decoding of a general lattice. For the decoding of a point x, the proposed algorithm recursively searches inside an, n-dimensional rectangular parallelepiped (cube), centered at x, with its edges along the Gram-Schmidt vectors of a proper basis of L. We call algorithms of this type recursive cube search (RCS) algorithms. It is shown that Kannan's algorithm also belongs to this category. The complexity of RCS algorithms is measured in terms of the number of lattice points that need to be examined before a decision is made. To tighten the upper bound on the complexity, we select a lattice basis which is reduced in the sense of Korkin-Zolotarev (1873). It is shown that for any selected basis, the decoding complexity (using RCS algorithms) of any sequence of lattices with possible application in communications (/spl gamma//spl ges/1) grows at least exponentially with n and /spl gamma/. It is observed that the densest lattices, and almost all of the lattices used in communications, e.g., Barnes-Wall lattices and the Leech lattice, have equal successive minima (ESM). For the decoding complexity of ESM lattices, a tighter upper bound and a stronger lower bound result are derived.