Decoder Error Propagation Mitigation for Spatially Coupled LDPC Codes

Spatially coupled low-density parity-check (SC-LDPC) codes, a type of LDPC convolutional code [1], have been shown to achieve threshold saturation, i.e., the suboptimal belief propagation (BP) iterative decoding threshold of SC-LDPC code ensembles over memoryless binary-input symmetric-output channels coincides with the maximum a posteriori probability (MAP) threshold of their underlying LDPC block code (LDPC-BC) ensembles [2, 3, 4, 5]. Further, regular SC-LDPC code ensembles not only have capacity approaching iterative decoding thresholds, but they are asymptotically good, i.e., their minimum distance grows linearly with frame length [6]. Therefore, SC-LDPC codes combine the best features of both regular and irregular LDPC-BCs.

SC-LDPC codes can be formed by applying a protograph-based construction technique [6]. In this paper we consider SC-LDPC codes constructed by coupling together a sequence of $L$ disjoint $(J,K)$-regular LDPC-BC protographs into a single coupled chain, where infinite $L$ results in an unterminated coupled chain and finite $L$ results in a terminated coupled chain. Without loss of generality, we consider an example of constructing (3,6)-regular SC-LDPC codes. We begin with an independent (uncoupled) sequence of (3,6)-regular LDPC-BC protographs with base matrix ${\bf{B}}=\left[{3,3}\right]$. Fig. 1 shows the resulting unterminated (3,6)-regular SC-LDPC code chain obtained by applying the edge-spreading technique of [6] to the uncoupled protographs. The edge spreading is defined by a set of component base matrices ${{\bf{B}}_{0}}={{\bf{B}}_{1}}={{\bf{B}}_{2}}=\left[{1~{}~{}1}\right]$ that must satisfy ${\bf{B}}={{\bf{B}}_{0}}+{{\bf{B}}_{1}}+{{\bf{B}}_{2}}$. In general, an arbitrary edge spreading must satisfy ${\bf{B}}=\sum\nolimits_{i=0}^{m}{{{\bf{B}}_{i}}}$, where $m$ is referred to as the coupling width.

Applying the lifting factor $M$ to the SC-LDPC protograph of Fig. 1 results in an unterminated ensemble of (3,6)-regular SC-LDPC codes in which each time unit represents a block of $2M$ coded bits (variable nodes).

To reduce the decoding latency and memory, sliding window decoding (SWD) was proposed for SC-LDPC codes in [7], where a standard BP flooding schedule is applied to all the nodes in the window. For example, in Fig. 1, the rectangular box represents a decoding window of size $W$ (blocks). To decode, a BP flooding schedule is applied to all the nodes in the window for some fixed number of iterations, or until some stopping criterion is met, the target block of $2M$ symbols in the first window position is decoded according to the signs of their log-likelihood ratios (LLRs), and the window shifts one time unit (block) to the right (see Fig. 1). Decoding continues in the same fashion until the entire chain is decoded, where the decoding latency in bits is given by $2MW$.

In order to reduce decoding latency and memory, the window size $W$ should be chosen as small as possible. In [8] the authors experimentally showed that near optimal performance can be maintained at higher signal-to-noise ratios (SNRs) as long as $W\geq 6\eta$, where $\eta=m+1$ is decoding constraint length. When low latency operation is desired, however, at typical operating SNRs, smaller values of $W$ can sometimes result in infrequent but severe decoder error propagation. Error propagation is triggered when, after a block decoding error occurs, the decoding of the subsequent block is also affected, which in turn can cause a continuous string of block errors, resulting in an unacceptable loss in performance. This is particularly damaging for very long code chains or for streaming applications. Klaiber et al. in [9] proposed to adapt the number of decoder iterations and/or shift the window position in order to combat decoder error propagation for SC-LDPC codes. For a related class of spatially coupled codes, viz. braided convolutional codes (BCCs), with SWD [10], a window extension algorithm, a synchronization mechanism, and a retransmission strategy were all used to mitigate error propagation [11]. More recently, Zhu et al. proposed a check node (CN) doped SC-LDPC code design [12] to limit error propagation. A disadvantage of these approaches is that they all require some modification of the decoding process.

The CN doped code design was motivated by the fact that the boundaries of a coupled chain have lower degree CNs, which has the effect of propagating more reliable information throughout the chain during iterative decoding. Inserting occasional lower degree CNs in a code chain, i.e., CN doping, has the same effect, thus allowing the decoder to recover from error propagation, although the shape of the decoding window must be altered at the doping points.

In a similar vein, known (or fixed) variable nodes in a coupled chain can also aid the iterative decoding process. This motivates us to propose a new class of variable node (VN) doped SC-LDPC codes in this paper, which operate by inserting occasional fixed (known) VNs in a code chain, thus allowing the decoder to recover from error propagation, with the added advantage of leaving the shape of the decoding window unchanged. The CN doping and VN doping code designs introduce occasional irregularities in the coupled chain, which results in some rate loss. However, since code doping is primarily useful for long or unterminated chains, the rate loss associated with doping is very slight.¹¹1Since termination itself serves to truncate error propagation, the effect on short chains is minimal. We present numerical results showing that, similar to CN doping, VN doping improves performance by up to two orders of magnitude compared to undoped SC-LDPC codes in the typical SNR operating range.

We also adapt the log-likelihood ratio (LLR) based window extension algorithm, first proposed in [10] for BCCs, to combat error propagation in SWD of SC-LDPC codes. This approach, which requires the size of the decoding window to occasionally be extended, but involves no rate loss, is shown to be capable of reducing the decoding latency by a significant fraction without suffering any loss in performance.

During SWD of SC-LDPC codes, when a block of target symbols at time $t$ is decoded, the window shifts to include the most recent block of received symbols at time $t+W$, and decoding commences on the block of target symbols at time $t+1$. During the decoding of the time $t+1$ block, for a coupling width of $m$, the final LLRs of the $m$ past decoded blocks, from time $t-m+1$ to time $t$, remain involved in the decoding process, although these LLRs are no longer updated, as illustrated in Fig. 2, which depicts the base parity-check matrix of a (3, 6)-regular SC-LDPC code with $W=3$ and $m=2$.

Under normal operation, decoding proceeds with correctly decoded blocks until such time as a block of target symbols contains one or more LLRs with incorrect signs when the window shifts, thus resulting in a block decoding error. Typically, if only a few symbols have incorrect LLRs and most of the correct LLRs have large magnitudes, the LLRs of the incorrectly decoded block will have only a small effect on the decoding of the next block, and the decoder will recover and continue to correctly decode subsequent blocks, assuming most of the symbols in the window have large and correct LLRs. This type of operation results in randomly distributed error blocks.

However, if an error block contains many incorrect LLRs, particularly if they have large magnitudes and a significant number of the LLRs associated with the correct symbols are small, those “bad” LLRs may negatively affect the decoding of the next block of target symbols, causing a block error that would not have occurred under normal operating conditions. This in turn can trigger additional block errors, resulting in an error propagation effect, i.e., a continuous sequence of incorrectly decoded blocks.

In an application where information is transmitted in frames of a small fixed length $L$ (in time units), with graph termination (reduced check node degrees for $m$ time units) following the last block of transmitted variable nodes, any error propagation will be limited and decoding will start fresh with the next frame. However, if $L$ is large, a significant number of blocks could be affected by error propagation, thus severely degrading performance. In a streaming application, with no termination, the situation could be catastrophic, resulting in a block error rate (BLER) that asymptotically tends to 1.

We now give an example illustrating the effect of this error propagation. The simulated BLER performance of SWD of a (3,6)-regular SC-LDPC code based on the coupled protograph in Fig. 1 is shown in Fig. 3, where $W=18$ and $M=2000$. The figure represents the simulation of a total of $LN=5\times{10}^{6}$ blocks (or $2MLN=2\times{10^{10}}$ bits), where $L$ is the frame length and $N$ is the number of frames simulated, for three different combinations of $L$ and $N$. From the figure, we observe that, with increasing $L$, the BLER performance becomes worse, even though there are relatively few error-propagation frames overall, thus confirming the above observation.²²2Fig. 3 represents only a narrow range of SNRs, below the threshold of the underlying LDPC-BC, where error propagation presents a significant problem. For larger values of $E_{b}/N_{0}$ and/or $W$, SWD typically recovers from an error burst.

In this section, we briefly review CN doping and then describe the new VN doping and window extension error propagation mitigation methods in detail.

In order to illustrate the effectiveness of the proposed mitigation methods, the bit error distribution per block of a typical error-propagation frame in SWD of the VN doped and undoped (3,6)-regular SC-LDPC codes of Fig. 1 sent over an AWGN channel with BPSK signaling is plotted in Fig. 7, where $M=1000$, $L=500$, and $W=18$. The figure clearly shows that VN doping truncates the error propagation at the doping point in the center of the frame, whereas the errors continue to the end of frame in the undoped case. Similar behavior has been observed for CN doping (see [12]) and window extension.

The bit error rate (BER) and BLER performance of VN doping with rate $R=0.49699$, CN doping with rate $R=0.497$ [12], and undoped with rate $R=0.499$ (3,6)-regular SC-LDPC codes of Fig. 1 is shown in Fig. 8, where the termination length is $L=500$ and the window size is $W=18$. We observe that both VN doping and CN doping gain approximately two orders of magnitude in BER and one order of magnitude in BLER compared to the undoped code at those SNR operating points of interest (below the threshold of the underlying LDPC-BC). Also, the fact that the performance of both doping methods is essentially equivalent corroborates our earlier observation that VN doping emulates the CN doping process while not requiring any alteration to the shape of the decoding window.

To illustrate the advantage of allowing a dynamic window size, Fig. 9 shows the performance of the (3,6)-regular SC-LDPC codes of Fig. 1 with and without window extension for $L=250$ and window sizes $W=18$ and $W=9$. From the figure, we see that, for $W=18$, window extension gives only a slight improvement compared to not using window extension. However, for $W=9$, window extension gains more than two orders of magnitude in both BER and BLER at SNR operating points of interest. From another point of view, by comparing Figs. 9(a) and 9(b), we see that the performance with $W=9$ and window extension is roughly equivalent to that of $W=18$ with no window extension, while the average window size (decoding latency), indicated on the BER curve with window extension as shown in Fig. 9(b), is reduced by about 1/3.

In this paper, we proposed two new methods of mitigating decoder error propagation in SWD of SC-LDPC codes: VN doping from the code design aspect and window extension from the decoder design aspect. The first, VN doping, takes advantage of occasional fixed (known) variable nodes in the protograph to allow SWD to recover from error propagation, without requiring any alteration to the shape of the decoding window (in contrast to the previously proposed CN doping). As a result, the BER and BLER performance of VN doped SC-LDPC codes was shown to improve by up to two orders of magnitude at SNR operating points of interest. The second method, window extension, adapts the window size dynamically to bring more decoding resources to bear in error propagation conditions. Simulation results show that window extension with $W=9$ can reduce the decoding delay (latency) on average by about 1/3 compared to using $W=18$ without window extension, while maintaining the same BER and BLER performance.