Beyond 100 Gbit/s Pipeline Decoders for Spatially Coupled LDPC Codes

In the following, we use italic letters, e.g., x, for the representation of scalars, bold lowercase letters, e.g., \({\mathbf {x}}\), for the representation of vectors, and bold uppercase letters, e.g., \({\mathbf {X}}\), for the representation of matrices. \({\mathbb {N}}_0\) denotes the set of positive integers, including the 0-element, \({\mathbb {Z}}\) the set of integers, \({\mathbb {R}}\) the set of real numbers, and \({\mathbb {F}}_2\) the Galois field 2. \(\log _2(x)\) denotes the base 2 logarithm of variable x, and \(\lceil x \rceil\) is the least integer greater than or equal to x.

We define a system for the continuous transmission of data blocks, as depicted in Fig. 1. An information source generates a stream, or sequence, of information blocks \({\mathbf {u}}_{[-\infty ,\infty ]} = [{\mathbf {u}}_{-\infty }, ..., {\mathbf {u}}_{\infty }]\), with each information block being composed of b bits, i.e., \({\mathbf {u}}_t = [u_t(1), ..., u_t(b)], t \in {\mathbb {Z}}\) and \(u_t{(\cdot )} \in {\mathbb {F}}_2\). An encoder maps this sequence of information blocks on a sequence of code blocks \({\mathbf {v}}_{[-\infty ,\infty ]} = [{\mathbf {v}}_{-\infty }, ..., {\mathbf {v}}_{\infty }]\) with \({\mathbf {v}}_t = [v_t(1), ..., v_t(c)]\), \(c>b\) and \(v_t{(\cdot )} \in {\mathbb {F}}_2\). After modulation, transmission over a noisy channel, and subsequent bit-level demodulation, the decoder receives a sequence of blocks \({\mathbf {y}}_{[-\infty ,\infty ]}\) each comprising c log-likelihood ratio (LLR) values, i.e., \({\mathbf {y}}_t = [y_t(1), ..., y_t(c)]\) and \(y_t{(\cdot )} \in {\mathbb {R}}\). Finally, a decoder provides an estimation \(\mathbf {{\hat{u}}}_{[-\infty ,\infty ]}\) on the initially transmitted information, with \(\mathbf {{\hat{u}}}_t = [{\hat{u}}_t(1), ..., {\hat{u}}_t(b)]\) and \({\hat{u}}_t{(\cdot )} \in {\mathbb {F}}_2\).

We define an \(R=b/c\) SC-LDPC code as the set of code sequences \({\mathbf {v}}_{[-\infty ,\infty ]}\) satisfyingwhereis also denoted as the parity-check matrix or syndrome former matrix of the SC-LDPC code. The elements \({\mathbf {H}}_{i}(t) \ne {\mathbf {0}}\) are binary, full rank sub-matrices of dimension \((c-b) \times c\). From Eq. 1, it follows that each \({\mathbf {v}}_t\) satisfiesand is thus coupled to \(m_s\) preceding and ascending code blocks. Consequently, \(m_s\) is also referred to as the coupling width or the memory of the code, \((m_s+1)\) as the constraint length.

We define the parity-check matrix of a terminated SC-LDPC code of finite length L as \({\mathbf {H}}_{[1,L]}\). For simplification, we consider in this work only time-invariant codes, i.e., \({\mathbf {H}}_{i}(t) = {\mathbf {H}}_{i}(t')\) for \(i=0, \ldots , m_\mathrm {s}\) and \(t,t' \in {\mathbb {Z}}\). For a detailed description of SC-LDPC codes, we refer to [7, 10] and [9].

SC-LDPC codes are decoded with message-passing algorithms, i.e., an exchange of probabilistic messages between variable and check nodes in the corresponding Tanner graph of the code. The Tanner graph can be directly derived from \({\mathbf {H}}_{[1,L]},\) and the decoding can be performed similarly to a conventional LDPC block code by repeatedly updating the respective variable nodes and check nodes. This block scheduling, however, does not take advantage of the limited memory of the code and the consequent diagonal band structure of \({\mathbf {H}}_{[1,L]}\). Instead, it is more efficient to use a sliding window scheduling. Here, the decoding is not performed simultaneously on the full graph corresponding to \({\mathbf {H}}_{[1,L]}\), but time-delayed on multiple sub-graphs each defined by a decoding window \({\mathcal {W}}(t)\) of length W. The decoding window can be considered as the Tanner graph corresponding to a sub-matrix of \({\mathbf {H}}_{[1,L]}\) comprising W rows and \(W+m_s\) columns. Throughout the decoding process, the window traverses \({\mathbf {H}}_{[1,L]}\) from the upper left to the lower right, moving by one sub-block each time step t. The advantage of a window decoding schedule is a significantly lower structural latency than a block schedule, as the decoder can start the decoding right after receiving the first sub-block \({\mathbf {y}}_1\). Furthermore, since the window length is typically much smaller than the block length, i.e., \(W \ll L\), the memory requirements are far less compared to a conventional LDPC block decoder of similar length.

For the processor design, we utilize the node-splitting concept [12] that was initially introduced for the check nodes in the FPWD and apply it to the variable nodes of a row-wise decoder and the check nodes of a column-wise decoder. Furthermore, the on-demand variable node activation (OVA) schedule for the row-wise decoding is extended to column-wise decoding.

With the described processors, different window processing schedules can be implemented by differently interconnecting the processors.

The column-wise decoders require an input stage to generate the initial list for the first processor in the pipeline from the channel values. This input stage is equivalent to a CFUi stage in the CN–CN processor. The row-wise decoders do not require a designated input stage, as the right APP values can be initialized directly with the channel values and the left APP values with zero messages. Instead, the row-wise decoders require an output stage to combine the left and right partial APP values. Therefore, the right APP messages of the last processor are stored in a register stage and then added to the current left APP messages.

We estimate the computational complexity of the decoders based on the number of edge messages that are computed and transferred in every clock cycle [20]. Let \(E_\text {row}\) denote the number of edges corresponding to a row-layer and \(E_\text {col}\) the number of edges corresponding to a column layer of \({\mathbf {H}}_{[1,L]}\). For a (\(d_v\),\(d_c\)) regular code, the number of edges can be expressed as \(E_\text {row} = d_c \cdot (c-b)\) and \(E_\text {col} = d_v \cdot c\), which is equivalent to the number of ones in \({\mathbf {H}}_r(t)\) and \({\mathbf {H}}_c(t)\), respectively. Since \({\mathbf {H}}_r(t)\) and \({\mathbf {H}}_c(t)\) of a time-invariant code are composed of the same sub-matrices \({\mathbf {H}}_1\) and \({\mathbf {H}}_0\), the number of edges in one row-layer equals the number of edges in one column layer, i.e., \(E_\text {row} = E_\text {col}\). From this, it follows that the VN–VN processor and the CN–CN processor compute the same number of edge messages in each clock cycle and thus exhibit similar computational complexity. However, the node splitting introduces additional edges for the exchange of messages between processors. The resulting number of edges for the row processor is then \({\hat{E}}_\text {row} = E_\text {row} + 2 \cdot c\) and for the column processor \({\hat{E}}_\text {col} = E_\text {col} + 2 \cdot (c-b)\). Taking into account the number of iterations (processors) I, we can define the complexity of the row-wise decoders asand for the column-wise decoders as

Figure 6a shows a side-by-side performance comparison of the row- and the column-layered decoder with 4, 8, 16, and 64 iterations (floating point). For better classification of the results, performance curves of the (64800, 51804) DVB-S2 code and the (648, 540) Wi-Fi code are also shown, each decoded with 200 iterations Normalized MS (NMS) (\(\gamma =0.75\), flooding schedule). Both codes are comparable to the SC-LDPC code in terms of code rate (\(R=0.8\) and \(R=0.83\)). The DVB-S2 serves as a reference LDPC code, that is similar in length to a full code block (64800 bit vs. 51238 bit). Conversely, the Wi-Fi code can be considered an uncoupled counterpart to the SC-LDPC code with a block length similar to one sub-block (648 bit vs. 640 bit). We see that for the same number of iterations, the row-layered decoder outperforms the column-layered decoder. This observation is also made for the compact decoders in Fig. 6b and the compact decoders with one additional pipeline stage in the processor in Fig. 6c. We also see that the performance decreases from the layered to the compact and the double-compact decoders. For better visualization, Fig. 6d shows the signal-to-noise ratio (SNR) at BER \(10^{-6}\) for all presented decoders over the iterations. This representation helps to illustrate the convergence behavior of the decoders, where a strong curvature toward the origin of the diagram indicates a faster convergence. The fastest convergence is achieved with layered decoding, the slowest with double-compact decoding. Furthermore, we see that all decoders asymptotically approach an SNR of approximately 3.1 dB. This behavior is expected as the exchanged messages in the compact, particularly in the double-compact decoder, are less recent, which affects the convergence speed of the decoder.

To compare the efficiency of different pipeline decoders, we implementedThe pipeline stage was inserted in the minimum search tree of the CFU stage for the row-wise processor and after the VFU stage for the column-wise processor. The respective number of iterations was selected such that all decoders achieve the same FEC performance (fixed point) of \(\text {BER}=10^{-6}\) at 4.2 dB, which is around 1 dB from the maximum MS performance of the code. All decoders use 4 bits to represent the channel values and the extrinsic messages. The row processors’ APP, R2L, and L2R values are quantized with 6 bits. The performance loss compared to floating point for this configuration is less than 0.2 dB up to a BER of \(10^{-6}\).

The layouts of the implemented decoders are depicted in Fig. 7, and Table 1 summarizes the results. When comparing the respective row- and column-wise decoders, we see that the column-wise decoders outperform the respective row-wise decoders in terms of throughput, energy, and area efficiency. For the layered architecture, the column-wise decoder achieves \(25\%\) higher clock frequency (throughput), around \(19\%\) better energy efficiency and \(22\%\) better area efficiency. For the compact and double-compact architectures, the improvements are even more profound with \(50\%\) (freq.), \(59\%\) (energy eff.), and \(135\%\) (area eff.), and with \(38\%\) (freq.), \(24\%\) (energy eff.) and \(38\%\) (area eff.), respectively.

At first glance, these results seem unexpected, especially considering the fact that the column-wise decoders are composed of an equal or even larger number of processors. However, an important fact to consider is the lower number of edge message computations of the column-wise processors (\({\hat{E}}_\text {col}=2816\) vs. \({\hat{E}}_\text {row}=3840\)). Relating the calculated computational complexity values to implementation metrics such as energy and area efficiency, we observe a large discrepancy. We attribute this to the data transfer dominance of the decoder. It was already shown in [21] that for data transfer dominated applications, like LDPC decoding, the number of operations has little impact on area and energy efficiency. Another important aspect to consider for the better efficiency of the column-wise decoders is that the data transfer between the processors is much lower (\(256\cdot Q_\text {ext}=1024\) vs. \(1296 \cdot Q_\text {app}=7776\)) and, consequently, the wiring load for the logic circuit resulting in smaller logic cells. Furthermore, the column processor has \(57\%\) fewer registers (Eq. 5 and Eq. 6), and thus a smaller clock tree.

A similar observation is made when comparing the compact and the double-compact decoders. Despite a higher computational complexity of the latter, the energy efficiency improves. Here, the introduction of an additional pipeline stage reduces the wiring load and toggling rates. Consequently, the energy efficiency per processor improves by \(28\%\) for the column-wise decoder and \(60\%\) for the row-wise decoder.

It should be noted that there is a large drop in frequency and degradation in energy efficiency from the row-layered to the row-compact decoder. The reason for this is that the row-layered decoder does not process exchange messages (see Sect. 4.2.1). Consequently, the adders in the row processors and the corresponding wiring were not synthesized, which contributes to the better efficiency of the row-layered decoder.

Finally, Table 2 shows the results for the column double-compact decoder in comparison to data from the fastest LDPC Block Code (LDPC-BC) and LDPC-CC decoders in the literature. The column double-compact decoder was selected for the comparison as it achieves the highest throughput of the presented decoders. The FPWD in [12] is not listed in Table 2, as the results are similar to the column-compact decoder in Table 1.

The LDPC-BC decoder in [8] is implemented in the same 22 nm technology and features a similar code rate and (sub-)block size and therefore allows for a detailed comparison. The throughput of the SC-LDPC decoder is about 20% lower than the throughput of the unrolled block decoder. This results from the fewer pipeline stages per iteration of the SC-LDPC decoder (2 vs. 3). As a result, the LDPC-BC decoder achieves a higher maximum frequency. The area of both decoders is similar. However, the SC-LDPC decoder achieves a gain in error correction performance of 0.7 dB over the LDPC-BC decoder. With an \(E_b/N_0\) of 4.2 dB the SC-LDPC decoder surpasses the maximum performance of the Wi-Fi code at 200 iterations (see Fig. 6c). This illustrates the great potential of SC-LDPC codes for high-throughput decoding beyond 5G.