The concept and existence of sphere-bound-achieving and capacity-achieving lattices has been explained on AWGN channels by Forney. LDPC lattices, introduced by Sadeghi, perform very well under iterative decoding algorithm. In this work, we focus on an ensemble of regular LDPC lattices. We produce and investigate an ensemble of LDPC lattices with known properties. It is shown that these lattices are sphere-bound-achieving and capacity-achieving. As byproducts we find the minimum distance, coding gain, kissing number and an upper bound for probability of error for this special ensemble of regular LDPC lattices.The concept and existence of sphere-bound-achieving and capacity-achieving lattices has been explained on AWGN channels by Forney. LDPC lattices, introduced by Sadeghi, perform very well under iterative decoding algorithm. In this work, we focus on an ensemble of regular LDPC lattices. We produce and investigate an ensemble of LDPC lattices with known properties. It is shown that these lattices are sphere-bound-achieving and capacity-achieving. As byproducts we find the minimum distance, coding gain, kissing number and an upper bound for probability of error for this special ensemble of regular LDPC lattices.

Apr 10, 20100 citations

Performance of low-density parity-check codes with linear minimum distance

Hossein Pishro-Nik, Faramarz Fekri

This correspondence studies the performance of the iterative decoding of low-density parity-check (LDPC) code ensembles that have linear typical minimum distance and stopping set size. We first obtain a lower bound on the achievable rates of these ensembles over memoryless binary-input output-symmetric channels. We improve this bound for the binary erasure channel. We also introduce a method to construct the codes meeting the lower bound for the binary erasure channel. Then, we give upper bounds on the rate of LDPC codes with linear minimum distance when their right degree distribution is fixed. We compare these bounds to the previously derived upper bounds on the rate when there is no restriction on the code ensemble.This correspondence studies the performance of the iterative decoding of low-density parity-check (LDPC) code ensembles that have linear typical minimum distance and stopping set size. We first obtain a lower bound on the achievable rates of these ensembles over memoryless binary-input output-symmetric channels. We improve this bound for the binary erasure channel. We also introduce a method to construct the codes meeting the lower bound for the binary erasure channel. Then, we give upper bounds on the rate of LDPC codes with linear minimum distance when their right degree distribution is fixed. We compare these bounds to the previously derived upper bounds on the rate when there is no restriction on the code ensemble.

IEEE Transactions on Information TheoryDec 28, 200513 citations

New sequences of capacity achieving LDPC code ensembles over the binary erasure channel

Hamid Saeedi, Amir H. Banihashemi

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.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.

IEEE International Symposium on Information Theory (ISIT)Jul 1, 20088 citations

Low-Density Parity-Check Lattices: Construction and Decoding Analysis

Mohammad‐Reza Sadeghi, Amir H. Banihashemi, Daniel Panario

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 thousandsLow-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

IEEE Transactions on Information TheorySep 29, 200695 citations

Performance Study of a Class of Irregular Near Capacity Achieving LDPC Codes

F. Vatta, Alessandro Soranzo, Massimiliano Comisso +2 more

This paper investigates the performance of a class of irregular low-density parity-check (LDPC) codes through a recently published low complexity upper bound on their beliefpropagation decoding thresholds. Moreover, their performance analysis is carried out through a recently published algorithmic method, presented in Babich et al. 2017 paper. In particular, the class considered is characterized by variable node degree distributions $\lambda(x)$ of minimum degree $i_1 \gt 2$ : being, in this case, $\lambda^{'} (0)=\lambda_2=0$ , this is useful to design LDPC codes presenting a linear minimum distance growth with the block length with probability 1, as shown in Di et al.’s 2006 paper. These codes unfortunately cannot reach capacity under iterative decoding, since the achievement of capacity requires $\lambda_2 \neq 0$ . However, in this latter case, the block error probability might converge to a constant, as shown in the aforementioned paper.This paper investigates the performance of a class of irregular low-density parity-check (LDPC) codes through a recently published low complexity upper bound on their beliefpropagation decoding thresholds. Moreover, their performance analysis is carried out through a recently published algorithmic method, presented in Babich et al. 2017 paper. In particular, the class considered is characterized by variable node degree distributions $\lambda(x)$ of minimum degree $i_1 \gt 2$: being, in this case, $\lambda^{'} (0)=\lambda_2=0$, this is useful to design LDPC codes presenting a linear minimum distance growth with the block length with probability 1, as shown in Di et al.’s 2006 paper. These codes unfortunately cannot reach capacity under iterative decoding, since the achievement of capacity requires $\lambda_2 \neq 0$. However, in this latter case, the block error probability might converge to a constant, as shown in the aforementioned paper.

Journal of Communications Software and SystemsJan 1, 20210 citations

New Sequences of Capacity Achieving LDPC Code Ensembles Over the Binary Erasure Channel

Hamid Saeedi, Amir H. Banihashemi

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.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.

IEEE Transactions on Information TheoryNov 30, 201020 citations

\lambda(x)

of minimum degree

i_1 \gt 2

: being, in this case,

\lambda^{'} (0)=\lambda_2=0

, this is useful to design LDPC codes presenting a linear minimum distance growth with the block length with probability 1, as shown in Di et al.’s 2006 paper. These codes unfortunately cannot reach capacity under iterative decoding, since the achievement of capacity requires

\lambda_2 \neq 0

. However, in this latter case, the block error probability might converge to a constant, as shown in the aforementioned paper.

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.