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]- [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 protographbased 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 B = [3,3]. 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 To minimize 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 loglikelihood 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 ≥ 6η, where η = 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 trig-gered 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. 1The 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. 2 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 tm + 1 to time t, remain involved in the decoding process, although these LLRs are no longer updated.
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. 2, where W = 18 and M = 2000. The figure represents the simulation of a total of LN = 5× 10 6 blocks (or 2MLN = 2×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. 3
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 combat error propagation in SWD of SC-LDPC codes, a new CN doped SC-LDPC code design was proposed in 0.75 0.8 0.85 0.9 10 -5 10 -4 10 -3 10 -2 10 -1 10 0 Fig. 2. SWD BLER performance of a (3,6)-regular SC-LDPC code for three different combinations of frame length and number of frames simulated, all with the same total number of simulated blocks. [12]. The key idea of CN doped SC-LDPC codes lies in occasionally inserting additional check nodes into the protograph of a regular SC-LDPC code, which is referred to as check node doping. The resulting structured irregularity limits error propagation by emulating graph termination, as noted earlier. We now use (3,6)-regular SC-LDPC codes as an example to briefly review of the CN doping process and the corresponding decoding scheme.
Fig. 3 shows the construction and SWD schedule of CN doped (3,6)-regular SC-LDPC codes. The red VNs at time t = τ 1 spread their three edges to the CNs at times t = τ 1 + 1, t = τ 1 + 2, and t = τ 1 + 3; the red VNs at time t = τ 2 spread their three edges to the CNs at times t = τ 2 +2, t = τ 2 + 3, and t = τ 2 + 4, and so on. To decode a CN doped (3,6)-regular SC-LDPC code, the window shifting schedule of SWD applied to the doped coupled chain is altered compared to standard SWD. When a doping point (red VN pair) becomes the target block, the window shifts by one VN time unit to include one new block of VNs, as before, but it shifts by two CN time units to include two new blocks of CNs (and thus still including the same total number of CNs), as illustrated in Fig. 3.
As an alternative to introducing occasional reduced-degree check nodes in the coupled chain (called CN doping) [12], here the encoder fixes (sets to "0") occasional variable nodes in the coupled chain, called VN doping, as shown Fig. 4, where each time unit represents a block of 2M coded symbols. The VNs at time t = τ 1 (the green empty circles) are doped by setting the 2M coded bits corresponding to these VNs to be "0". As a result, the CNs at times t = τ 1 , τ 1 + 1, τ 1 + 2 (colored red and shaded) can be viewed as degree-4, rather than degree-6, CNs, thus emulating CN doping without actually altering the graph structure. Similarly, if the VNs at time t = τ 2 are doped, the CNs at times t = τ 2 , τ 2 + 1, τ 2 + 2 (colored red and shaded) can be viewed as degree-4 CNs.
If n c and n v denote the total number of CNs and the total number of unknown VNs in VN doped SC-LDPC codes, respectively, and if there are d doped positions, the design rate of VN doped SC-LDPC codes with frame length L and d doped VNs is
where R = 1 -J/K is the design rate of the uncoupled protograph [6]. Compared to the design rate
(1 -R) of undoped SC-LDPC codes [6], we see from (1) that the design rate of VN doped SC-LDPC codes is smaller, i.e., VN doping results in some rate loss, similar to CN doping.
The decoding process is the same as for undoped codes, except that the doped code symbols and their positions are treated as known, i.e., during the decoding process we set the LLRs of the doped symbols to be a large constant negative value. These known bits have the effect of transmitting perfectly reliable information to their neighbour nodes, thus helping the decoder recover from error propagation. An important implementation advantage of VN doping over CN doping is that the shape of the decoding window remains unaltered.
In this section, rather than altering the code design, we mitigate error propagation by occasionally extending the size of the decoding window. By experimentally recording decoder behavior during error propagation, we find that the average LLR magnitudes of the blocks are typically near zero, a phenomenon also observed for BCCs in [11].
To take advantage of this observation, we can allow the window size W to change dynamically in SWD of SC-LDPC codes, from an initial size W init to a maximum size W max , thereby causing additional decoding resources to be employed when a potential error propagation condition is detected. To formalize this process, we denote the decision LLRs of the 2M coded bits in the ith block of the current window after some fixed number I of iterations by i = i 0 , i 1 , . . . , i 2M -1 , i ∈ {t, t + 1, . . . , t + W -1}. Then the average LLR magnitude of the 2M code bits in block i after I iterations is given by
We also define the observation span τ as the number of consecutive blocks in the decoding window over which the average LLRs magnitude is to be examined. Now assume the current decoding window, with W = W init , covers the blocks (2M bits each) from time t to t + W -1. After I iterations, if any of the average LLR magnitudes of the first τ blocks in the current window, 1 ≤ τ ≤ W , is lower than a predefined threshold θ, i.e., if
) then the target block is not decoded, the window size W is increased by 2 time units 4 , and the decoding process restarts. If none of the first τ blocks satisfies (3), the target block is decoded and the window shifts by 1 time unit. If the current window size reaches W max , then the target block is decoded, the window shifts by 1 time unit, and the window size is reset to W init . 5 An algorithmic description of this process is given in a more complete online version [15].
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. 5, 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 doped (rate R = 0.497), CN doped (rate R = 0.497 [12]), and undoped (rate R = 0.499) (3,6)-regular SC-LDPC codes from Fig. 1 is shown in Fig. 6, 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 in the typical SNR operating range (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. 7 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 in the typical SNR operating range. From another point of view, by comparing Figs. 7(a) and 7(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 in Fig. 7(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 alteration to the shape of the decoding window (in contrast to the previously proposed CN doping). As a result, the BER and BLER performance VN doped SC-LDPC codes was shown to improve by up to two orders of magnitude in the typical SNR operating range. 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.
For the basic concept of doping, we refer the readers to[13] and[14].
Since termination itself serves to truncate error propagation, the effect on short chains is minimal.
Fig.2represents 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.
Increasing the window size by 2 time units was determined experimentally to be the best compromise between performance and complexity.
Note that, since the window size can vary, the decoding latency can be characterized by the average window size.