Non-Uniformly Coupled LDPC Codes: Better Thresholds, Smaller Rate-loss, and Less Complexity
Laurent Schmalen Vahid Aref Fanny Jardel





Non-Uniformly Coupled LDPC Codes: Better Thresholds, Smaller Rate-loss, and Less Complexity
    Laurent Schmalen, 
Vahid Aref, and
Fanny Jardel


Nokia Bell Labs, Stuttgart, Germany. (e-mail: {})
    
=======================================================================================================




We consider spatially coupled low-density parity-check codes with finite smoothing parameters. A finite smoothing parameter is important for designing practical codes that are decoded using low-complexity windowed decoders. 
By optimizing the amount of coupling between spatial positions, we show that we can construct codes with excellent thresholds and small rate loss, even with the lowest possible smoothing parameter and large variable node degrees, which are required for low error floors. 
We also establish that the decoding convergence speed is faster with non-uniformly coupled codes, which we verify by density evolution of windowed decoding with a finite number of  iterations. We also show that by only slightly increasing the smoothing parameter,  practical codes with potentially low error floors and thresholds close to capacity can be constructed. Finally, we give some indications on protograph designs.




§ INTRODUCTION


The work of L. Schmalen was supported by the German Government in the frame of the CELTIC+/BMBF project SENDATE-TANDEM.
Low-density parity-check (LDPC) codes are widely used due to their outstanding performance under low-complexity belief propagation (BP) decoding.  
However, an error probability exceeding that of maximum-a-posteriori (MAP) decoding has to be tolerated with (sub-optimal) low-complexity BP decoding. 
A few years ago, it has been empirically observed that the BP performance of 
some protograph-based, spatially coupled (SC) LDPC ensembles (also termed convolutional LDPC codes) can improve towards the MAP performance of the underlying LDPC ensemble <cit.>. Around the same time, 
this threshold saturation phenomenon has been proven rigorously in <cit.> for a newly introduced, randomly coupled SC-LDPC ensemble.
 In particular, the BP threshold of that SC-LDPC ensemble tends towards its MAP threshold on any binary memoryless symmetric channel (BMS). 

SC-LDPC ensembles are characterized by two parameters: the replication factor L, which denotes the number of copies of LDPC codes to be places along a spatial dimension, and the smoothing parameter w. This latter parameter indicates that each edge of the graph is allowed to connect to w neighboring spatial positions (for details, see <cit.> and Sec. <ref>).
The proof of threshold saturation was given in the context of uniform spatial coupling and requires both L→∞ and w→∞. This poses a serious disadvantage for realizing practical codes, as relatively large structures are required to build efficient codes.

In practice, the main challenges for implementing SC-LDPC codes are the rate-loss due to termination and the decoding complexity. The rate-loss, which scales with w, can be made arbitrarily small by increasing L, however, a large L can worsen the finite-length performance of SC-LDPC codes <cit.>. Known approaches to mitigate the rate-loss (e.g., <cit.>) often introduce extra structure at the boundaries, which is usually undesired. Therefore, we would like to keep the rate-loss as small as possible for a fixed, but small L. Additionally, the decoding complexity can be managed by employing windowed decoding (WD) <cit.>, however, the window length and complexity scale with the smoothing parameter w. For both reasons, w should be as small as possible, ideally w∈{2,3}, to keep the rate-loss and complexity small, e.g., in high-speed optical communications <cit.>.

In this paper, we construct code ensembles that have excellent thresholds for small w, that have smaller rate-loss than SC-LDPC ensembles and can be decoded with less complexity by maximizing the speed of the decoding wave. We achieve these properties by generalizing the uniformly coupled SC-LDPC codes of <cit.> to allow for non-uniform coupling. It was already recognized in <cit.> that non-uniform protographs can lead to improved thresholds in some circumstances by sacrificing a one-sided converge of the chain, which is not problematic when using WD. A very particular, exponential coupling was used in <cit.> to guarantee anytime reliability.

We extend non-uniform coupling to randomly coupled SC-LDPC ensembles and protograph-based ensembles. We analyze their performance under message passing with and without windowed decoding. We show that we can achieve excellent close-to-capacity thresholds by optimizing the coupling, for small w and large d_v, which is required for codes with low error floors. Furthermore, we introduce a new multi-type-based non-uniform coupling that further improves the thresholds without increasing w. We find that the rate-loss is decreased by non-uniform coupling as well. We finally show that the decoding speed, which is an indicator of the complexity, can be increased by non-uniform coupling.


 


§ SPATIALLY COUPLED LDPC CODES


We briefly describe two construction types of 
non-uniformly coupled LDPC codes: the random ensemble and the protograph-based ensemble. The former is easier to analyze and exhibits
the general advantages of non-uniform coupling 
while the latter is more of practical interest.



 §.§ The Random (d_v,d_c,ν,L,M) Ensemble


We now briefly review how to sample a code from a random, non-uniformly coupled (d_v,d_c,ν,L,M) SC-LDPC ensemble with regular degree distributions.
We first lay out a set of positions indexed from z=1 to L on a spatial dimension. 
At each spatial position (SP) z, there are M variable nodes (VNs) and Md_v/d_c check nodes (CNs), 
where Md_v/d_c∈ℕ and d_v and d_c denote the variable and check node degrees, respectively.
The non-uniformly coupled structure is based on the smoothing distribution
ν=[ν_0,…,ν_w-1] where ν_i>0, 
∑_iν_i=1 and w>1 denotes the smoothing (coupling) width.
The special case of ν_i=1/w leads to the usual, well-known spatial coupling with the uniform smoothing distribution <cit.>.

For termination, we additionally consider w-1 sets of Md_v/d_c CNs in SPs L+1,…,L+w-1. Every CN is assigned with d_c “sockets” and imposes an even parity constraint on its d_c neighboring VNs. 
Each VN in SP z is connected to d_v CNs in SPs z,…,z+w-1 as follows: 
For each of the d_v edges of this VN, an SP z^'∈{z,…,z+w-1} is randomly selected according to
the distribution ν, and then, the edge is uniformly connected to any free socket of the Md_v sockets arising from the CNs in that SP z^'.
This graph represents the code with n=LM code bits, distributed over L SPs. Because of additional CNs in SPs L+1,…,L+w-1, but also because of potentially unconnected CNs in SPs 1,…,w-1, the design rate is slightly decreased to r = 1-d_v/d_c-1/LΔ where

    Δ=d_v/d_c(w-1-∑_k=0^w-2[ (∑_i=0^kν_i)^d_c+ (∑_i=k+1^w-1ν_i)^d_c])

which increases linearly with w. 

In the limit of M, the asymptotic performance of this ensemble on a binary erasure channel (BEC) can be analyzed using density evolution, with

    x_z^(t+1) = (1-∑_i=0^w-1ν_i(1-∑_j=0^w-1ν_j x_z+i-j^(t))^d_c-1)^d_v-1

where  denotes the channel erasure probability and x_z^(t) the average erasure probability of the outgoing messages from VNs in SP z at iteration t. The messages are initialized as x_z^(0) =, if z∈[1,L] and x_z^(0) = 0 otherwise. For ν_i=1/w, (<ref>) becomes the known 
DE equation for SC-LDPC codes with uniform coupling <cit.>.



 §.§ Protograph-based SC-LDPC Ensembles



SC-LDPC ensembles with a certain predefined structure
can be constructed by means of protographs <cit.>. The Tanner graph of the protograph-based SC-LDPC code is some M-cover of the protograph, i.e.,
M copies of the protograph are bound together by random permutation of the edges between the same type of sockets. Protograph-based SC-LDPC codes are of practical interest because of their simple hardware implementation and their excellent 
finite-length performance <cit.>.
An exemplary protograph of an SC-LDPC code with non-uniform coupling is shown in Fig. <ref>-a). As the coupled protograph is a chain of repeating segments, we represent coupled protographs by their distinct elementary segment shown in Fig. <ref>-b). We use the 3-tuple (d_v,b_1,b_2) to describe the elementary segment, with d_v the regular variable node degree, b_1 the number of parallel edges between VN v_1 and CN c_1 and b_2 the number of parallel edges between VN v_2 and CN c_1. 






 §.§ Windowed Decoder Complexity


The decoding complexity is an important parameter for practical SC-LDPC codes.
Consider the profile of densities [x_0^(t),x_1^(t),…] in (<ref>). It has been shown in <cit.> that the profile behaves like a “wave”: it shifts along the spatial dimension with “a constant speed” as the BP decoder iterates. The wave propagation speed is analytically analyzed and bounded in <cit.>,<cit.>.

The wave-like behaviour enables efficient sliding windowed decoding <cit.>: the decoder updates the BP messages of edges lying in a window of W_D SPs I times, and then shifts the window one SP forward and repeats. Thus, the decoding complexity scales with O(W_DILMd_v) as there are 2MLd_v BP messages and each BP message is updated W_DI times.

The required window size W_D is an increasing function of the smoothing factor w <cit.> which implies that we should keep w small. The number of iterations I>1/v where v is the speed of the wave. In the continuum limit of the spatial dimension, v is defined as the amount displacement of the profile along the spatial dimension after one iteration. For the discrete case of (<ref>), the speed can be estimated by 

    v≈ v_D=D/T_D,

where T_D in the minimum number of iterations required for the displacement of the profile by more than D SPs, i.e.,

    T_D = min{T∈ℕ| x_z^(t+T)≤ x_z-D^(t),   for t>0 ∧ z≤⌊ L/2⌋}.

The approximation of v becomes more precise by choosing larger D. We chose D=10 in this paper. 

We quickly recapitulate the asymptotic analysis for the windowed decoder here. Instead of the windowed decoder proposed in <cit.>, we employ a slightly modified, more practical version, which updates the complete window after one decoding step. 
For every windowed decoding step, indexed by c∈[1,L], we generate a copy y_c,z^(0) of the vector x=(x_1^(c-1),…,x_L+w-1^(c-1)) on which we apply the update rule (<ref>) for SPs z∈{c,c+1,…,c+W_D-1} only, for a total of I iterations. After I iterations, we update the SPs as

    x_z^(c) = {[       x_z^(c-1) if z ∉[c,c+W_D);     y_z-c+1^(I)       otherwise ].

We use a finite number of iterations in the windowed decoder to accurately predict the performance of a practical decoder.




§ NON-UNIFORM COUPLING: RANDOM ENSEMBLES


In this section, we optimize non-uniformly SC-LDPC ensembles with random coupling for the BEC. First, we consider w=2, the smallest possible smoothing parameter. This case has a high practical interest as w should be kept as small as possible in order to keep the decoding latency and window length W_D manageable when employing windowed decoding. We show numerically that non-uniform coupling improves the BP threshold  and also the decoding complexity as the total number of iterations decreases. Afterwards, we show the advantages of non-uniform coupling w>2. 





 §.§ Non-Uniform Unit-Memory Coupling (w=2)

Consider a random (d_v,d_c,ν,L,M) SC-LDPC ensemble
with smoothing vector ν=[α,1-α]. It is enough to  assume 0≤α≤1/2 because of symmetry. In the limit of M, the  asymptotic performance of the ensemble over BEC can be evaluated using DE. We consider the BP threshold 

    (α) = sup{ : x_z^(ℓ)→ 0 as ℓ→∞,∀ z∈[1,L]},

where x_z^(ℓ) is updated according to (<ref>). 
Figure <ref> illustrates
(α) in terms of α
for different values of d_v.

Each curve has two minima and a maximum. 
The two minima are at α=0 and α=1/2 where
(α=0)= corresponds to
the BP threshold of the uncoupled ensemble and (α=1/2) corresponds to the BP threshold of the SC-LDPC ensemble with uniform coupling.
The respective maxima of the curves are indicated by a marker and obtained for α^*.
We can see that uniform coupling (α=1/2) does not lead to the best thresholds. In particular, if we increase d_v, which is required for constructing codes with very low error floors, uniform coupling with w=2 is not efficient anymore, and the thresholds are significantly away from the BEC capacity. With an optimized α^⋆, we can achieve thresholds that are close to capacity (and the MAP threshold of the uncoupled LDPC ensemble ) and significantly outperform the uncoupled and the uniformly coupled cases. Table <ref> gives the thresholds of the optimized codes together with the unoptimized, uniformly coupled and uncoupled cases. Although coupling always improves the threshold, with w=2, uniform coupling is not a good solution and significantly better thresholds are obtained by non-uniform coupling, especially for larger d_v. Moreover, it is easy to show that the rate-loss Δ is maximized for uniform coupling (α=1/2). Hence non-uniform coupling will always reduce the rate-loss.
We can see that as d_v increases, α^⋆ decreases as well. An interesting open question is whether α saturates to some constant or if it will converge to zero. 





Non-uniform coupling can also decrease the decoding complexity of windowed decoding.
Figure <ref> illustrates the effect of non-uniform coupling on the wave propagation. While uniform coupling (α=1/2) leads to a wave propagation from both ends towards the middle, non-uniform coupling sacrifices one of those waves in favor of the other one, which will (usually) travel at a faster velocity.

We compute the speed v according to (<ref>) for different values of α∈[0,1/2] and different values of ∈[(α=0),(α^⋆)] and show the contour lines of equal decoding speed v in Fig. <ref> 
for d_v=5 and d_v=10. Points along a contour line indicate that the decoding wave moves with the same speed. When building practical decoders, usually a hardware constraint is imposed which limits the amount of operations that can be done. Hence also the decoding speed is limited. We can see that for a fixed speed v, non-uniformly coupled codes can be operated at much higher erasure probability than with uniform coupling. Note that the maxima of the speed contours coincide practically with the α^⋆ maximizing the threshold.




Figure <ref> suggests that windowed decoding also benefits from non-uniform coupling. For this reason, we use density evolution including windowed decoding, as detailed in Sec. <ref>. Figure <ref> exemplarily  shows the thresholds for windowed decoding for the (5,10,[α,1-α],L=100) and the (10,20,[α,1-α],L=100) SC-LDPC ensembles for four window configurations: W_D∈{10,20} and I∈{3,9}. We see a good agreement between the speed contour lines of Fig. <ref> and the windowed decoding thresholds. Again we can see that for non-uniformly coupled codes and identical window configurations, we can significantly increase the decoding threshold.





 §.§ Non-Uniform Coupling with w > 2


We have seen in the previous section that
non-uniform coupling can increase the BP threshold
if we constrain w=2. However, for d_v>5, we have to tolerate a gap to capacity.
In this case, we can relax the constraint on w. In fact, for w>2, non-uniform coupling can be more beneficial as there are more degrees of freedom for optimizing the smoothing vector ν. We numerically show in the following that it results in a faster saturation of the BP threshold to capacity even for small values of w, e.g., w=3. 

Consider the DE equation (<ref>) for a random (d_v,d_c,ν,L) SC-LDPC ensemble over a BEC. Let ν=[ν_1,ν_2,1-ν_1-ν_2] with w=dim(ν)=3.
For regular ensembles with asymptotic rate r=1/2 (d_c=2d_v),
we observe that the BP threshold, (ν), depends on
the choice of ν and can get very close to the capacity. 
We used a grid search with a fine resolution to 
numerically optimize the BP threshold for the ensembles with d_v∈{4,…, 10}. The results are given in Tab. <ref> where 
the optimized smoothing distribution is denoted by ν^⋆=[ν_1^⋆,ν_2^⋆,1-ν_1^⋆-ν_2^⋆]. We observe that the BP thresholds almost saturate to the capacity (or , respectively), while the BP threshold of uniformly coupled ensembles ((ν=[1/3,1/3,1/3])) have a gap to capacity which increases for larger d_v. Note that especially for small d_v, many different choices of ν lead to good thresholds . In that case, we select the optimum ν^⋆ which leads to a good threshold and also yields a small rate loss Δ. Note that in contrast to the w=2 case, where the rate-loss was maximal for uniform coupling,  it is not hard to show that the rate-loss Δ for w=3 is maximized with ν = [1/2,0,1/2]. It is an interesting open question whether it is possible to construct capacity-achieving codes with a finite w. 





 §.§ Non-Uniform Coupling with Different Types

Non-uniform coupling is a general concept. So far, 
we presented the simplest way of non-uniform coupling in which the edges of all VNs in an SP are randomly connected 
according to a distribution ν. Generally, the edges of each VN 
can be connected according to a set of distributions. 
Let us illustrate the benefits of such coupling by an example. Consider again a coupled LDPC ensemble with w=2 and d_c=2d_v. Inspired by the protograph structure shown in Fig. <ref>, we partition the VNs in each SP into two sets of equal size,  called “upper set” and “lower set”. As described in Sec. <ref>, the edges of VNs in the upper set are randomly connected to CNs according to
the “upper” smoothing distribution ν=[α,1-α]. Similarly, the edges of VNs in the lower set are distributed according to the “lower” smoothing distribution ν=[α,1-α]. Therefore, each CN receives two types of BP messages from VNs. Let x_z^(t) (x_z^(t)) denote the average erasure probability of the BP messages flowing from VNs of the upper set (lower set) in SP z at iteration t. Then the DE equations become


    y_z^(t)=(1-(αx_z^(t)+ (1-α)x_z-1^(t)))^d_v-1(1-(αx_z^(t)+ (1-α)x_z-1^(t)))^d_v
       y_z^(t)=(1-(αx_z^(t)+ (1-α)x_z-1^(t)))^d_v(1-(αx_z^(t)+ (1-α)x_z-1^(t)))^d_v-1
       x_z^(t+1)=(1-( αy_z^(t) + (1-α)y_z+1^(t)))^d_v-1
       x_z^(t+1)=(1-( αy_z^(t) + (1-α)y_z+1^(t)))^d_v-1

Using DE analysis and a rough exhaustive search, we optimized α and α to find the largest BP threshold for different values of d_v.
The thresholds are summarized in Tab. <ref>. We observe that the thresholds almost saturate to capacity for d_v=6 and d_v=7 with only w=2.





§ NON-UNIFORM COUPLING: PROTOGRAPH ENSEMBLES 




As most practical codes are based on protographs, we extend the findings of this paper to protograph-based codes with the elementary building segment of Fig. <ref>-b). In comparison to the random ensembles, there is less room for optimization
as there are finite choices for b_1 and b_2, each requiring a
separate DE analysis, which is also slightly more complicated as the BP messages come from different edge types (multi-edge types DE).
We computed DE thresholds for all possible protographs based on a simple elementary segment  with 2 VNs and 2 CNs for L=100 (r=0.495). In Tab. <ref>, we summarize the best protographs and the respective thresholds that we find for different choices of d_v. Some of the best elementary segments are shown in Fig. <ref>. Up to d_v=6, protographs with b_1=b_2=1 are optimal, however, when d_v > 6, interestingly, the choice b_1=1 and b_2=5 becomes optimal. 






In Fig. <ref>, we plot the decoding speeds for the best protographs with d_v∈{4,5,6,7}. We can see that for < 0.488, the protograph (4,1,1) has the highest decoding speed and thus leads to the smallest decoding complexity, while for ≥ 0.488, the protograph (5,1,1) has the highest speed due to its different slope. Using an exhaustive search over all possible elementary protograph segments with 2 VNs and 2 CNs and with d_v≤ 18, we have verified that these two protographs are indeed the ones yielding the highest overall speeds and are good candidates for implementation.






§ ACKNOWLEDGMENTS

The authors would like to acknowledge Rüdiger Urbanke and Shrinivas Kudekar for interesting discussions and suggestions leading to the work in this paper and its presentation.



10

url@samestyle








Lentmaier-ita09
M. Lentmaier, G. P. Fettweis, K. Zigangirov, and D. J. Costello, Jr.,
  “Approaching capacity with asymptotically regular LDPC codes,” in
  Proc. ITA, 2009.

Kudekar-it11
S. Kudekar, T. Richardson, and R. Urbanke, “Threshold saturation via spatial
  coupling: Why convolutional LDPC ensembles perform so well over the
  BEC,” IEEE Trans. Inf. Theory, vol. 57, no. 2, Feb 2011.

Kudekar-it13
——, “Spatially coupled ensembles universally achieve capacity under belief
  propagation,” IEEE Trans. Inf. Theory, vol. 59, no. 12, 2013.

Olmos-it15
P. M. Olmos and R. Urbanke, “A scaling law to predict the finite-length
  performance of spatially-coupled LDPC codes,” IEEE Trans. Inf.
  Theory, vol. 61, no. 6, pp. 3164–3184, June 2015.

kudekarISTC
S. Kudekar, C. Méasson, T. Richardson, and R. Urbanke, “Threshold
  saturation on BMS channels via spatial coupling,” in Proc. ISTC,
  2010.

sanatkar2016increasing
M. R. Sanatkar and H. D. Pfister, “Increasing the rate of spatially-coupled
  codes via optimized irregular termination,” in Proc. ISTC, 2016.

Iyengar-wd
A. R. Iyengar, P. H. Siegel, R. L. Urbanke, and J. K. Wolf, “Windowed decoding
  of spatially coupled codes,” IEEE Trans. Inf. Theory, 2013.

schmalen2015spatially
L. Schmalen, V. Aref, J. Cho, D. Suikat, D. Rösener, and A. Leven,
  “Spatially coupled soft-decision error correction for future lightwave
  systems,” J. Lightw. Technol., vol. 33, no. 5, pp. 1109–1116, 2015.

SchmalenSCC13
L. Schmalen and S. ten Brink, “Combining spatially coupled LDPC codes with
  modulation and detection,” in Proc. ITG SCC, 2013.

JardelNU
F. Jardel and J. J. Boutros, “Non-uniform spatial coupling,” in Proc.
  ITW, Nov. 2014.

noor2015anytime
M. Noor-A-Rahim, K. D. Nguyen, and G. Lechner, “Anytime reliability of
  spatially coupled codes,” IEEE Trans. Commun., vol. 63, 2015.

mitchell2015spatially
D. G. Mitchell, M. Lentmaier, and D. J. Costello, “Spatially coupled LDPC
  codes constructed from protographs,” IEEE Trans. Inf. Theory,
  vol. 61, no. 9, pp. 4866–4889, 2015.

stinner2016waterfall
M. Stinner and P. M. Olmos, “On the waterfall performance of finite-length
  SC-LDPC codes constructed from protographs,” IEEE J. Sel. Areas
  Commun., vol. 34, no. 2, pp. 345–361, 2016.

kudekar2015wave
S. Kudekar, T. J. Richardson, and R. L. Urbanke, “Wave-like solutions of
  general 1-d spatially coupled systems,” IEEE Trans. Inf. Theory,
  2015.

aref2013convergence
V. Aref, L. Schmalen, and S. ten Brink, “On the convergence speed of
  spatially coupled LDPC ensembles,” in Proc. Allerton Conf., 2013.

el2016velocity
R. El-Khatib and N. Macris, “The velocity of the decoding wave for spatially
  coupled codes on BMS channels,” in Proc. ISIT, 2016.



