Design of Improved Quasi-Cyclic Protograph-Based Raptor-Like LDPC Codes for Short Block-Lengths
Sudarsan V. S. Ranganathan Dariush Divsalar Richard D. Wesel






















Design of Improved Quasi-Cyclic Protograph-Based Raptor-Like LDPC Codes for Short Block-LengthsResearch is supported in part by National Science Foundation (NSF) grant CCF-1618272. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the NSF. Research was carried out in part at the Jet Propulsion Laboratory (JPL), California Institute of Technology, under a contract with NASA. This work used computational and storage services associated with the Hoffman2 Shared Cluster provided by UCLA Institute for Digital Research and Education's Research Technology Group.
    Sudarsan V. S. Ranganathan1, 
Dariush Divsalar2, and
Richard D. Wesel1
1Department of Electrical Engineering, 
University of California, Los Angeles, Los Angeles, California 90095

2Jet Propulsion Laboratory, California Institute of Technology, Pasadena, California 91109
Email: sudarsanvsr@ucla.edu, Dariush.Divsalar@jpl.nasa.gov, wesel@ucla.edu

    Received: date / Accepted: date
============================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================










Protograph-based Raptor-like low-density parity-check codes (PBRL codes) are a recently proposed family of easily encodable and decodable rate-compatible LDPC (RC-LDPC) codes. These codes have an excellent iterative decoding threshold and performance across all design rates. PBRL codes designed thus far, for both long and short block-lengths, have been based on optimizing the iterative decoding threshold of the protograph of the RC code family at various design rates. 

In this work, we propose a design method to obtain better quasi-cyclic (QC) RC-LDPC codes with PBRL structure for short block-lengths (of a few hundred bits). We achieve this by maximizing an upper bound on the minimum distance of any QC-LDPC code that can be obtained from the protograph of a PBRL ensemble. The obtained codes outperform the original PBRL codes at short block-lengths by significantly improving the error floor behavior at all design rates. Furthermore, we identify a reduction in complexity of the design procedure, facilitated by the general structure of a PBRL ensemble. 





















§ INTRODUCTION AND BACKGROUND


Protograph-based low-density parity-check (LDPC) codes <cit.>, <cit.> are a class of codes amenable to tractable analysis and design procedures. Protograph quasi-cyclic LDPC (QC-LDPC) codes <cit.>, a class of protograph codes, have parity-check matrices composed of circulant permutation matrices (CPMs) and permit very low complexity decoder implementations <cit.>.

The presence of CPMs in protograph QC-LDPC codes enables us to understand how the connections in the protograph affect the girth and minimum distance of such codes. Fossorier <cit.>, Karimi and Banihashemi <cit.>, and others analyze the girth of a protograph QC-LDPC code by examining the protograph of the code. More pertinent to this paper are <cit.> and <cit.>. Smarandache and Vontobel <cit.> derive an upper bound on the minimum distance of any QC-LDPC code that can be obtained from a protograph. Butler and Siegel <cit.> extend the results of <cit.> to QC-LDPC codes based on punctured protographs.

Protograph-based Raptor-like LDPC codes (PBRL codes) are a class of easily encodable rate-compatible (RC) LDPC code families proposed by Chen, Vakilinia et al. in <cit.>. PBRL code families have an excellent iterative decoding threshold <cit.>, <cit.> and performance across all rates for which they are designed. In <cit.>, the authors design PBRL protographs for long and short block-lengths by optimizing the iterative decoding threshold of the protograph at each rate. They show that PBRL QC-LDPC code families can outperform other RC-LDPC codes in the literature, both at short (≈ 1000 information bits) and long (≈ 16000 information bits) block-lengths.

This paper considers the design of RC-LDPC codes for very short block-lengths (≈ 200 information bits). While the iterative decoding threshold is the correct design metric to use for code design at long block-lengths, minimum distance is more important at short block-lengths. 

One contribution of this paper is a new PBRL design approach. Given a set of design rates, we design protographs for PBRL ensembles by maximizing, at each rate, the upper bounds on the minimum distance that were derived in <cit.> and <cit.>. The resulting PBRL QC-LDPC code families outperform the ones designed by optimizing the iterative decoding threshold at each rate. The complexity of computing the aforementioned upper bounds increases quickly with the size of the protographs. A second contribution of this paper is to leverage the structure of PBRL protographs to identify a significant reduction in the complexity of the design procedure. 

The paper is organized as follows: Section <ref> provides the design procedure, derives the reduction that is possible in the computational complexity of the design procedure, and discusses design examples. Section <ref> shows simulation results. Section <ref> concludes the paper. 




§ DESIGNING PBRL ENSEMBLES BY MAXIMIZING AN UPPER BOUND ON THE MINIMUM DISTANCE


A PBRL ensemble is defined by its protomatrix P that has the following general form:

    P = [ P_𝖧𝖱𝖢     0; P_𝖨𝖱𝖢     I ]_n_c × n_v

Here, 0 and I refer to the all-zeros and identity matrices of appropriate size. The highest-rate code (𝖧𝖱𝖢) of the rate-compatible protomatrix is represented by P_𝖧𝖱𝖢, which is of size n_c_H× n_v_H. The variable nodes of the protomatrix containing the identity matrix in (<ref>) represent the incremental redundancy symbols of P. Some variable nodes of a protomatrix could also be punctured. The design rate is R ≜(n_v-n_c)/n_t for a protomatrix with n_c check nodes, n_v variable nodes, and n_t of the n_v variable nodes that are transmitted.

A protomatrix is lifted (see <cit.>, <cit.>) to obtain an LDPC code of block-length that is a multiple of n_t. The use of circulant permutation matrices while lifting yields QC-LDPC codes, which are practical and are the subject of this paper. 



 §.§ Design Method


The design of a PBRL protomatrix consists of two steps: First, we choose the 𝖧𝖱𝖢 part, P_𝖧𝖱𝖢, as a protomatrix by itself. Then, we obtain the 𝖨𝖱𝖢 part, P_𝖨𝖱𝖢, one row at a time. In the original work on PBRL codes by Chen, Vakilinia et al. <cit.>, the authors first choose an 𝖧𝖱𝖢 part with a degree distribution and an acceptable iterative decoding threshold. Then they design each row of P_𝖨𝖱𝖢 successively to optimize the iterative decoding threshold of the protomatrix up to that rate while designing the row, keeping all previously obtained rows fixed. The best known families of RC-LDPC codes at both short and long block-lengths are the PBRL codes as designed with the heuristics proposed by Chen, Vakilinia et al. in <cit.>. 

At short block-lengths, minimum distance can be more important than the iterative decoding threshold as a criterion to use while designing LDPC codes. A key feature of QC-LDPC codes based on protomatrices is that the minimum distance of any such code obtained from a protomatrix is upper bounded by a constant that depends only on the protomatrix. In order to state the upper bounds, which were derived in earlier works, we need the definition of the permanent of a square matrix.



Denote the set {1, 2, …, ℓ} by [ℓ]. The permanent of an ℓ×ℓ square matrix A with elements a_i,j, i ∈ [ℓ], j ∈ [ℓ] over some commutative ring is defined as

    𝗉𝖾𝗋𝗆 (A) = ∑_σ∏_1 ≤ j ≤ℓ a_j, σ(j) = ∑_σ∏_1 ≤ j ≤ℓ a_σ(j), j,

where σ refers to a permutation and the summation is over all permutations of [ℓ]. The permanent, although it looks deceptively similar to the determinant, is harder to compute than the determinant <cit.>. While the arithmetic complexity of computing the determinant is O(ℓ^3), the most efficient algorithm known to compute the permanent of any square matrix, due to Ryser <cit.>, is of complexity Θ(ℓ· 2^ℓ). 




Let a protomatrix P with a positive design rate and no punctured variable nodes be of size n_c × n_v. If S ⊆[n_v], denote by P_S the sub-matrix of P formed by the columns indexed by elements of S. Then, any QC-LDPC code 𝒞 obtained from the protomatrix P has a minimum distance d_min(𝒞) that is upper bounded as

    d_min(𝒞) ≤S ⊆ [n_v], |S| = n_c + 1min^∗∑_i ∈ S𝗉𝖾𝗋𝗆(P_S ∖ i),

where |·| refers to the cardinality of a set, S ∖ i is shorthand for S ∖{i}, and min^∗ returns the smallest non-zero value in a set of non-negative values with at least one positive value or +∞ if the set is {0}. Note that permanents computed from sub-matrices of a protomatrix are always non-negative.




Let a punctured protomatrix P with a positive design rate less than 1 be of size n_c × n_v. Let the set of punctured variable nodes, a subset of [n_v], be denoted 𝒫. Denote any punctured QC-LDPC code that can be obtained from P by 𝒞' and the unpunctured version of the code 𝒞' by 𝒞. Then, provided that 𝒞 and 𝒞' have the same number of codewords in their codebooks (dimensionality), 𝒞' has a minimum distance d_min(𝒞') that is upper bounded as

    d_min(𝒞') ≤S ⊆ [n_v], |S| = n_c + 1min^∗∑_i ∈ S ∖𝒫𝗉𝖾𝗋𝗆(P_S ∖ i).



With Theorems <ref> and <ref> in hand, we propose the following PBRL ensemble search procedure:


  * Choose an 𝖧𝖱𝖢 matrix of size n_c_H× n_v_H with a desired degree distribution and complexity constraint. A common complexity constraint is to limit the weight of each column in the protomatrix.

  * 𝖨𝖱𝖢 design: Select the next row of the protomatrix from a set of candidate rows to maximize the upper bound on the minimum distance via Theorem <ref> or <ref> (depending upon whether there are punctured nodes or not). If there are multiple candidates with the best upper bound, then select one at random.

  * Go to Step 2) if another row of 𝖨𝖱𝖢 is required. Otherwise, terminate the search procedure. 


It is not known, in general, whether the upper bounds of (<ref>) or (<ref>) are achievable. But our design procedure yields better RC QC-LDPC code families at short block-lengths than the design based on optimizing the iterative decoding thresholds. 

For a punctured protomatrix, care must be taken to ensure that not too many variable nodes are punctured. Otherwise, the dimensionality requirement in Theorem <ref> may be violated. 



 §.§ Lowering the Complexity of the Design Procedure


In this subsection, we leverage the general structure of the protomatrix of a PBRL ensemble in (<ref>) to reduce the complexity of computing the upper bounds in (<ref>) or (<ref>). 

Assume that we have a PBRL protomatrix of size n_c × n_v with an 𝖧𝖱𝖢 part that is of size n_c_H× n_v_H. Assume also that the protomatrix has no punctured variable nodes[We consider the case when the protomatrix has punctured variable nodes in the Appendix.]. With these assumptions, computation of the upper bound for the protomatrix as given in (<ref>) requires computing n_vn_c + 1·(n_c + 1) permanents, each of size n_c × n_c. The complexity of Ryser's algorithm to compute the required permanents increases quickly while constructing the 𝖨𝖱𝖢 part of a PBRL ensemble. Our following result leads to a significant reduction in both the number of permanents that need to be computed and the size of each permanent to be computed.




Let a PBRL protomatrix P of size n_c × n_v with no punctured variable nodes have a positive design rate, i.e. n_v > n_c. Let the 𝖧𝖱𝖢 part be of size n_c_H× n_v_H. Assume that the upper bound in (<ref>) for P is a positive integer. Then, the same upper bound can be obtained with at most n_v_Hn_c_H + 1·(n_c + 1) permanents, each of size at most (n_c_H + 1) ×(n_c_H + 1). 


Before we provide the proof, we comment on the reduction in complexity of computing (<ref>). The complexity of computing each permanent would now depend only on the number of check nodes in the 𝖧𝖱𝖢 part, n_c_H. Also, the dominating factor in the expression for number of permanents to be computed is the binomial coefficient, which again would now depend only on the size of the 𝖧𝖱𝖢 part, n_c_H× n_v_H, and not on the size of the entire protomatrix. 


Let us first consider the case when S ⊆[n_v], |S| = n_c + 1 contains the last n_v - n_v_H columns, i.e. the columns that comprise the incremental redundancy variable nodes of the protomatrix and have an identity matrix of size (n_v - n_v_H) ×(n_v - n_v_H). Note that n_v - n_v_H = n_c - n_c_H. The n_c + 1 chosen columns form a sub-matrix with structure that can be written as:

    P_S = [c_1 c_2 ⋯ c_n_c_H+1 | P_𝖨𝖱],

where c_i are the columns chosen from the initial n_v_H columns of P and P_𝖨𝖱 has the following structure:

    P_𝖨𝖱 = [ 0; I ]_{n_c ×(n_v - n_v_H)}

Because each column in P_𝖨𝖱 contains only a single 1, the complexity of computing each of the n_c + 1 required permanents is at most the size of computing the permanent of an (n_c_H+1) ×(n_c_H+1) sub-matrix (when the removed column is from P_𝖨𝖱). When the removed column is not from P_𝖨𝖱, the complexity is the size of computing the permanent of an n_c_H× n_c_H sub-matrix since the product is zero for permutations that select elements not in the 𝖧𝖱𝖢 rows of c_i, 1 ≤ i ≤ n_c_H+1. Furthermore, there are n_v_Hn_c_H + 1 sets S ⊆[n_v] of size n_c + 1 that contain P_𝖨𝖱.

Now let us consider the general set S of n_c+1 columns in [n_v]. First, let us assume that

    ∑_i ∈ S𝗉𝖾𝗋𝗆(P_S ∖ i) > 0,

which implies that at least one of the n_c + 1 permanents is positive. Denote by P' one such n_c × n_c sub-matrix of P_S with a positive permanent. There exists a permutation denoted σ^* that has a positive product in (<ref>) when computed for the matrix P'. Assume the following definition of a permanent:

    𝗉𝖾𝗋𝗆(P') = ∑_σ∏_1 ≤ j ≤ n_c p'_σ(j), j,

where p'_i,j denotes the entries of P'. Consider all columns indexed by j ∈[n_c] such that σ^*(j) > n_c_H. There are n_c - n_c_H = n_v - n_v_H such columns. Replace all these columns by the columns of the sub-matrix P_𝖨𝖱 (whenever possible), in the following manner: Replace column j whose σ^*(j) = j' > n_c_H with the column in P_𝖨𝖱 whose only non-zero element, 1, is present in row j', unless the column from P_𝖨𝖱 is already in the set S of n_c + 1 columns under consideration. Call the newly obtained matrix P'_1. The sub-matrix P'_1 has a permanent that is positive and is at most the value of the permanent of P' due to the following reasons: Permutation σ^* yields a positive product with P'_1 because the replacements (whenever possible) only lead to non-zero entries at locations (σ^*(j),j): σ^*(j) > n_c_H. Furthermore, each permutation σ that yields a positive product ∏_i ∈σ p'_σ(j),j in P' (including σ^*) yields a product with P'_1 that is upper bounded by the product computed with P'. 

Let us denote the matrix [c_1  c_2  c_3 ⋯ c_n_c_H+1 |  P_𝖨𝖱] by P”, where c_1, c_2, …, c_n_c_H+1 are the columns in P_S chosen from the first n_v_H columns of the protomatrix P and were either in P' and not replaced to obtain P'_1 or was not in P'. Let us denote by S” the columns of P that lead to P”. It is now straight-forward to see from the composition of the matrices P_S and P_S” that 

    ∑_i ∈ S𝗉𝖾𝗋𝗆(P_S ∖ i) ≥∑_i ∈ S”𝗉𝖾𝗋𝗆(P_S”∖ i) > 0.


We now consider the final case of the general set of n_c + 1 columns whose n_c + 1 permanents sum to zero. Recall that the statement of the theorem assumes that P has a positive upper bound in (<ref>). Therefore, we may ignore such a case unless those columns contain P_𝖨𝖱, in which case we would compute the sum of n_c + 1 permanents according to the complexity as shown already.

This completes the proof as the above shows it suffices to consider subsets S that always contain the columns of P_𝖨𝖱.


The requirement that the protomatrix have a finite upper bound on its minimum distance (as assumed in Theorem <ref> and its counterpart in the Appendix for a protomatrix with punctured variable nodes) can be satisfied while designing every row of the 𝖨𝖱𝖢 part via the following observation:




Let a PBRL protomatrix P of size n_c × n_v with a positive design rate have an 𝖧𝖱𝖢 part of size n_c_H× n_v_H. Let the 𝖧𝖱𝖢 part, as a protomatrix by itself, have a positive and finite upper bound d_𝖧𝖱𝖢 as computed using (<ref>) or (<ref>). Then the upper bounds for each new row i=n_c_H+1,n_c_H+2,…, n_c added to obtain P, irrespective of the chosen candidates for the rows, are non-decreasing and are lower bounded by d_𝖧𝖱𝖢.


Let us consider the design of the first row of the 𝖨𝖱𝖢 part and assume that the protomatrix has no punctured columns. Assume that there is no non-zero integer in the new (n_c_H+1)^th row except the required 1 from the P_𝖨𝖱 part at entry (n_c_H+1, n_v_H +1 ). For any set of n_c_H +2 columns S that does not include the (n_v_H+1)^th column, the sum of the n_c_H +2 permanents is zero. For any other set that includes the (n_v_H+1)^th column, the sum of the permanents is equal to one of the sums of n_c_H+1 permanents computed to find the upper bound for the 𝖧𝖱𝖢 part. Now, if the new row is designed to have non-zero entries in the columns not in P_𝖨𝖱, the upper bound can only increase or remain the same. 

Similar arguments follow if the protomatrix has punctured columns. This completes the proof as the above arguments can then be successively applied to each new row.










 §.§ Design Examples


In this subsection we design PBRL protomatrices according to the new design method we have proposed. We assume the following 𝖧𝖱𝖢 matrix for all our designs:

    [ 2 1 2 1 2 1 2 1; 1 2 1 2 1 2 1 2 ]

We consider both a punctured and an unpunctured version of the matrix in (<ref>) in our examples. The punctured version has the first variable node punctured. Hence the design rate we start with is either 6/8 (unpunctured) or 6/7 (punctured). 

Because of Lemma <ref>, choosing an 𝖧𝖱𝖢 with a non-zero and finite upper bound (<ref>) or (<ref>) is sufficient to then use our results on reducing the complexity of search procedure to design the n_c × n_v protomatrix P. The 𝖧𝖱𝖢 matrix in (<ref>) has an upper bound of 12 when none of its variable nodes are punctured and an upper bound of 8 when its first column is punctured. 



We constrain the last n_c - n_c_H rows of the protomatrix to have a weight of exactly 4 and do not allow any non-zero integer other than 1. These constraints facilitate good performance at short block-lengths because limiting both the density and the number of multiple edges in the protograph helps the resulting LDPC codes have good girth and avoid having too many short cycles. Explicit constraints are necessary because increasing the value of any element at any position of a protomatrix with a finite upper bound of (<ref>) or (<ref>) either results in an increase in the upper bound or the upper bound stays the same. 




Our design method, which maximizes an upper bound on code minimum distance, does not depend upon the channel over which we deploy the codes. For designing codes for comparison according to the original design method that involves computing iterative decoding thresholds, we assume the binary-input additive white Gaussian noise channel (BI-AWGNC). The threshold values computed in this work are the result of at least 1000 iterations of the reciprocal channel approximation method to computing thresholds (see <cit.>). 






  §.§.§ Unpunctured design
 We design two unpunctured ensembles using the 𝖧𝖱𝖢 matrix given in (<ref>) with the design constraints in Remark <ref>. The design rates we consider decrease from 6/8 to 6/15. The first ensemble, P_1, is obtained using the new permanent bound design (PBD) method proposed in this paper. For comparison, the second ensemble, P_2, is designed by optimizing the iterative decoding thresholds (referred to as “threshold-based” in results) over BI-AWGNC.
The 𝖨𝖱𝖢 parts of P_1 and P_2 that we obtained are:

    P_1,𝖨𝖱𝖢 = [ 1 1 1 0 0 0 0 0; 0 0 0 1 1 1 0 0; 1 0 0 0 0 0 1 1; 0 1 1 1 0 0 0 0; 1 0 0 0 1 1 0 0; 1 0 1 0 0 0 0 1; 0 1 0 1 0 0 1 0 ],
    P_2,𝖨𝖱𝖢 = [ 1 1 1 0 0 0 0 0; 0 0 0 1 1 1 0 0; 1 0 0 0 0 0 1 1; 0 0 1 0 1 0 1 0; 1 0 0 1 1 0 0 0; 1 0 1 0 0 1 0 0; 1 0 1 0 0 0 1 0 ]




  §.§.§ Punctured design
 Similarly, we design two punctured ensembles using the 𝖧𝖱𝖢 matrix in (<ref>) via the design constraints in Remark <ref>. The first variable node is punctured[A punctured variable node improves the iterative decoding threshold (see <cit.> and <cit.>). Also, following the observations of <cit.> we constrain every row of P_𝖨𝖱𝖢 to connect to the punctured variable node in our punctured designs.], and the design rates decrease from 6/7 to 6/15. The resulting ensembles are called P_3 (PBD) and P_4 (threshold-based). 
Their 𝖨𝖱𝖢 parts are

    P_3,𝖨𝖱𝖢= [ 1 1 1 0 0 0 0 0; 1 0 0 1 0 0 1 0; 1 0 0 0 1 0 0 1; 1 0 1 0 0 1 0 0; 1 1 0 1 0 0 0 0; 1 0 0 0 1 1 0 0; 1 0 0 0 1 0 0 1; 1 1 0 0 1 0 0 0 ],P_4,𝖨𝖱𝖢= 
    [ 1 0 1 0 1 0 0 0; 1 0 1 0 0 0 1 0; 1 1 0 0 1 0 0 0; 1 0 0 1 0 0 1 0; 1 0 0 0 1 1 0 0; 1 0 0 0 0 0 1 1; 1 0 0 1 1 0 0 0; 1 1 0 0 0 0 1 0 ]



  §.§.§ Unconstrained design via original PBRL design method
 For further comparison, we design an ensemble, called P_5, using the same 𝖧𝖱𝖢 matrix with its first variable node punctured according to the original PBRL design method. The design rates decrease from 6/7 to 6/15. For this ensemble we only have the following restriction in the 𝖨𝖱𝖢 part: We do not permit any integer greater than 1.
The design yielded the following 𝖨𝖱𝖢 part:

    P_5,𝖨𝖱𝖢 =
    [ 1 0 1 0 1 0 0 0; 1 0 1 0 1 0 1 0; 1 1 1 0 1 0 1 0; 1 1 1 0 1 0 1 0; 1 1 1 0 1 0 1 0; 1 0 1 1 1 0 0 0; 1 1 1 0 1 0 1 0; 1 0 1 1 0 0 0 0 ]




We now compare the five ensembles P_i, i ∈ [5] according to two metrics. Fig. <ref> shows the upper bound on the minimum distance obtained at each rate for the five ensembles. P_1, the unpunctured, constrained ensemble obtained via the new PBD method, has the best upper bound at almost every rate. At the other end of the spectrum, P_5, the unconstrained, punctured ensemble designed to optimize the threshold at each rate, has the worst upper bound at every rate. 

The iterative decoding thresholds at each rate (over BI-AWGNC) for all five ensembles are shown in Fig. <ref>. As expected, ensemble P_5 has the best threshold at each rate. But surprisingly, both the unpunctured and punctured constrained ensembles obtained via the new PBD method, P_1 and P_3, have almost the same threshold at each rate as their counterpart ensembles, P_2 and P_4, which were obtained by optimizing the iterative decoding threshold at each rate. 




§ SIMULATION RESULTS






This section presents simulation results of carefully designed RC code families from each of the five ensembles. Codes simulated in this section are all quasi-cyclic. Lifting was performed for the n_c × n_v protomatrix of the lowest rate 6/15 using the circulant-PEG (C-PEG) algorithm combined with the ACE algorithm of Tian et al. <cit.>. The lifting factor used is 33, which resulted in k=198 information bits for all code families. The resulting girth of all code families, at the lowest rate, is 6. Simulation results shown were obtained using a maximum of 100 iterations of full-precision, flooding, LLR-domain belief propagation over BI-AWGNC. At least 100 errors were collected for each frame error rate (FER) point in any simulated E_b/N_0 vs. FER graph.



The FER of all five codes are shown in Figs. <ref> and <ref>. The QC-LDPC code family obtained from ensemble P_3 outperforms all the other codes at FERs 10^-4, 10^-5, and 10^-6 and at all rates (even at rates 6/12 and 6/13, which are omitted as the results are similar to the ones shown here). This ensemble has the advantages of a good, if not the best, threshold due to the punctured variable node (Fig. <ref>) and a good upper bound on the minimum distance at all rates (Fig. <ref>). The code family from the ensemble P_1, which has the best minimum distance upper bound at all rates, performs well at lower rates but not at higher rates. 


The gap to BI-AWGNC capacity at FER of 10^-6 is shown in Fig. <ref>. The code family of ensemble P_3 achieves the best performance at all design rates. The performance of this code is about 1.5 dB away at all rates from the refined normal approximation of <cit.>.




§ CONCLUSION


This paper proposed a new method to design PBRL QC-LDPC codes for short block-lengths. The metric used in the design is an upper bound on the minimum distance of any QC-LDPC code that can be obtained from a protomatrix. By maximizing this upper bound at each design rate of the rate-compatible family of codes, the paper obtained a significant improvement in the error floor region over PBRL codes designed according to the original method of optimizing the iterative decoding threshold. Furthermore, the paper identified a key reduction that is possible in the complexity of the newly proposed design procedure. 



IEEEtran




[Reduction in Complexity of Design Procedure for PBRL Protomatrices With Punctured Nodes]

Theorem <ref> provides a considerable reduction in the complexity of the new design procedure to obtain PBRL ensembles with no punctured variable nodes. This appendix explores the case when a protomatrix has punctured variable nodes. 

Let a PBRL protomatrix P of size n_c × n_v with n_p punctured variable nodes have a positive design rate less than 1, i.e. n_v > n_c and n_t = n_v - n_p > n_v - n_c. Let the 𝖧𝖱𝖢 part be of size n_c_H× n_v_H. Let the set of punctured variable nodes be denoted 𝒫. Assume that the upper bound in (<ref>) for P is a positive integer. 

Now, if S ⊆[n_v], |S| = n_c + 1, S ∩𝒫 = ϕ, and S does not contain all the columns of P_𝖨𝖱, then the arguments in Theorem <ref> for ignoring such a set S while computing the upper bound for the protomatrix still hold. Similarly, if S includes P_𝖨𝖱 and any subset of columns from the first n_v_H columns of P, the computational complexity arguments for computing the sum of at most n_c + 1 permanents for such a set of columns hold the same way as observed in Theorem <ref>. 

Now consider the case when S ⊆[n_v], |S| = n_c + 1, S does not contain all the columns of P_𝖨𝖱, and S ∩𝒫ϕ. Let the number of punctured columns in S be n_S_p. The sum

    ∑_i ∈ S ∖𝒫𝗉𝖾𝗋𝗆(P_S ∖ i)

has n_c + 1 - n_S_p permanents that need to be computed, all of size at most n_c × n_c. Every n_c × n_c sub-matrix whose permanent is computed for this sum contains all the n_S_p columns that are punctured. The strategy of replacing n_v - n_v_H columns of a sub-matrix whose permanent is non-zero in (<ref>) by all the columns in P_𝖨𝖱 does not necessarily yield a new summation that is smaller than the summation computed for the columns in S according to (<ref>). We give an example to illustrate this. 

Let us consider the following PBRL protomatrix whose first column is punctured:

    [ 1 1 2 1 2 1 0; 0 2 1 2 1 2 0; 1 1 0 0 0 0 1 ]

Let S={1,2,3,4}, the first four columns of the protomatrix. The sum in (<ref>) for this set has three terms in it and is equal to 17. The permanent of the 3 × 3 sub-matrix comprised of columns 1, 3, 4 is equal to 5. If we follow the same replacement strategy as in Theorem <ref>, we need to replace column 1 by the only incremental redundancy variable node, i.e. column 7. The new set of columns {2, 3, 4, 7} has no column that is punctured and the summation in (<ref>), which now has four terms, is now equal to 19. 

Therefore, we observe that when a PBRL protomatrix has n_p punctured variable nodes and a finite upper bound in (<ref>), the complexity of computing the bound can be reduced the following way: 


  * Consider all sets of n_c + 1 columns that contain P_𝖨𝖱. For such a set we need to compute at most n_c + 1 permanents, each of size at most (n_c_H + 1) ×(n_c_H + 1). There are n_v_Hn_c_H + 1 such sets.

  * Consider all sets of n_c + 1 columns that contain i ≥ 1 punctured variable nodes, and not all columns or no column of P_𝖨𝖱. Compute the summation of the n_c + 1 - i permanents, each of size at most n_c × n_c (if there are columns of P_𝖨𝖱 then the complexity of computing the permanent would decrease). There are

    ∑_i=1^n_p∑_j=0^n_v - n_v_H - 1n_pin_v_H - n_pn_c + 1 - i - jn_v - n_v_Hj

such sets that need to be considered, where the binomial coefficient nk is assumed to be 0 if k ∉{0,1,…,n}. 





