¹

1 Introduction↩︎

Quasi-cyclic LDPC codes used in the 5G NR standard [1] form a distinctive class of error-correcting codes that combine strong performance with efficient hardware implementation. In this paper, we consider the minimum distance problem for 5G LDPC codes, which is known to be NP-hard for the general class of linear codes [2]. Special attention is given to the codes formed by the first \(4\) and \(6\) parity circulant blocks, referred to hereafter as the \(4\)-layer and \(6\)-layer codes, respectively, for the following reasons.

The full 5G LDPC parity-check matrix [3] has an unusual structure for a quasi-cyclic LDPC code: it is obtained from four parity layers by appending a sparse matrix below them and a large identity matrix in the lower-right corner, see Fig. 3. On one hand, this structure makes encoding very computationally efficient [4]. On the other hand, one may expect that the presence of weight one columns in the parity-check matrix degrades the minimum distance of the code and, consequently, its decoding performance. However, due to the careful choice of circulant blocks in the matrix construction [3] and the retransmission mechanism of the 5G communication system, this degradation is significantly reduced when a low-complexity approximate decoder such as the layered min-sum decoder is used, although it remains visible for high-rate codes; see Fig. 1.Moreover, the decoder is prone to undetected errors, see Fig. 14. This phenomenon can be explained by the short minimum distances of high-rate 5G LDPC codes, which we establish in this study.

The \(4\)-layer code also plays a central role in the 5G HARQ retransmission scheme. In this scheme, although only certain parts of a codeword are transmitted in each retransmission, the initial transmission (redundancy version 0, RV0) starts at the third circulant block and includes all the remaining information bits and partially the leftmost parity bits. This fact makes RV0 closely related to the \(4\)-layer code.

The \([9984,8448]\) code, which is the \(6\)-layer code with maximum circulant size \(384\), was also adopted as part of the SDA-OCT communication standard [5]. In this standard, the error-detection properties are strengthened. Each information block contains a \(144\)-bit header followed by a \(16\)-bit CRC, and the block is additionally protected by \(800\) parity bits of a convolutional code [5]. As a result, the information-block error-detection capabilities of this standard are much stronger than those in 5G, partly to cope with the use of a simpler retransmission ARQ protocol in SDA-OCT.

The next section presents the necessary preliminaries, including basic definitions, notations, and a description of 5G LDPC codes.

The main goal of this work is to derive upper and lower bounds on the minimum distances of the 5G LDPC codes. To this end, in Section 3 we exploit the block structure of 5G LDPC parity-check matrices to adapt the classical Vontobel–Smarandache construction [6] in a computationally efficient way. This yields solid upper bounds on the minimum distance of quasi-cyclic 5G LDPC codes. For obtaining upper bounds, by comparison, the Brouwer–Zimmermann algorithm implemented in MAGMA [7] is slow for long codes, while the number-geometry-based estimation method of [8] via the open-source MATLAB code of [9], is limited in the input code lengths. In particular, the MATLAB implementation in [9] works for lengths up to 8000 bits, whereas BG1 5G codes have lengths up to \(25344\).

In Section 4 we develop a method for bounding the minimum distances of quasi-cyclic codes based on the natural relationship between a quasi-cyclic code with circulant size \(q\) and its modular reduction with circulant size \(q'\), where \(q' \mid q\). This method turns out to be particularly useful for deriving lower bounds and, when combined with the upper bounds from Section 3, provides tight bounds for minimum distances of several 5G codes with lengths up to \(4992\).

In addition to the minimum distance analysis, we further exploit the ideas from Section 4 and study a practical aspect of early decoding termination in Section  5. The LDPC decoder (typically a min-sum decoder) approximates belief propagation by passing messages between variable and check nodes. It computes soft updates using the min-sum rule to reduce complexity and employs early termination if the syndrome vector is zero (indicating successful decoding) or after a maximum number of iterations. There are also alternative approaches to early termination for quasi-cyclic LDPC codes; see, e.g., [10].

In the classic column-driven min-sum approach to syndrome calculation, at the end of each iteration, the impact of each circulant block must be computed using the corresponding shifter area. With this approach, the number of shifters in hardware equals the maximum column weight of the parity-check matrix.

The hardware for 5G codes must support all codes defined in the standard, as well as the so-called all-layer code, which has the largest parity-check matrix. The first difficulty arises from the fact that the parity-check matrix of the all-layer code has the first two circulant columns dense providing a maximum column weight of \(30\), see Fig. 3, thus requiring \(30\) shifters in the area. This is unusually large for standard LDPC codes; for example, LDPC codes from IEEE 802.11ax WiFi standard have a maximum column weight of only up to \(11\) and DVB-S2 codes have a maximum column weight of only \(6\).

Moreover, the LDPC codes in the 5G standard cover a huge range of circulant sizes (51 possible values for shifters) [1]. The traditional approach does not replace each shifter with \(51\) individual shifters but rather implements several extended shifters (as they were called in [11])—pieces of hardware that shift any data of size up to the maximum possible. The traditional implementation [12] of such single module uses two shifters, which doubles the area per extended shifter. Note that other approaches for implementation of extended shifters have been developed, and for 5G codes, in particular, [11], [13].

In Section 5 we propose a new early termination approach based on circulant modular reduction of the syndrome, which reduces the computational complexity of syndrome calculation and can be useful in hardware implementations of 5G LDPC decoders. Thus, the results of the paper are relevant both from theoretical standpoints (minimum distance analysis) and from engineering standpoints (efficient decoder design).

Observed Error-Floor Behavior for 5G LDPC codes. The tests in this work were performed using the floating-point layered min-sum decoder and the following 5G LDPC code. In accordance with [1], we consider a left-punctured code formed by the first six rows of base graph 1 with lifting set 1 exponent matrix and has circulant size \(384\). The code has the following parameters \[\label{5G32code}5G LDPC code: length 9984, information block length 8448\tag{1}\] and it is the code \(C'({\mathcal{E}}_{[6]},384)\) in the notation of Section 2.3. As one of the results that we show in this study, the minimum distance of the code (1 ) is at most \(14\) and at least \(8\).

In order to compare the performance we chose a random quasi-cyclic LDPC code with circulant size \(192\), fixed column weight four in its parity-check matrix and parameters:\[\label{Random32code}Random code: length 9984, information block length 8447,\tag{2}\] so having almost the same rate and message length as the 5G code (1 ).

In the high SNR region, the 5G LDPC code exhibits a distinctive error floor for the information block, see Fig. 1, which is absent for a random code whose error rates remain relatively similar at an \(Eb/N0\) of around \(3.7\) dB. From the average iterations standpoint, the 5G LDPC code starts to perform worse than the random code over a broader SNR region (for \(Eb/N0 \geq 3.4\) dB), see Fig. 2.

The tests show that, in particular, the BLER of 5G codes is affected by the relatively small minimum distance, as there are instances where the LDPC decoder outputs undetected errors, i.e., events where the decoder converges to a codeword that is different from the transmitted one, see Fig. 14. This observation underlines the importance of the 24-bit CRC employed in the 5G standard for catching such undetected error events [14].

2 Preliminaries↩︎

2.1 Basic definitions↩︎

Let \(\mathbb{F}_2^n\) denote the \(n\)-dimensional vector space over the binary field \(\mathbb{F}_2\). A binary linear code of length \(n\) and dimension \(k\) is a \(k\)-dimensional subspace of \(\mathbb{F}_2^n\). The Hamming distance between words is equal to the number of distinct positions. The weight of a word \(c\) is defined as the number of nonzero symbols in \(c\) and denoted by \(w(c)\). The minimum distance of a linear code is the minimum Hamming distance between two distinct codewords, or equivalently, the minimum weight of its nonzero codewords. For a linear code \(C\), we denote its minimum distance by \(d(C)\).

A generator matrix of a linear code is a matrix whose rows form a basis of the code. Given a matrix \(M\) and a set \(S\) of column indices, we denote by \(M^S\) the submatrix of \(M\) formed by the columns indexed by \(S\). A set \(I\) of coordinate positions of a linear code \(C\) with generator matrix \(G\) is called an information set if \(G^I\) is nonsingular.

A matrix \(H\) is called a parity-check matrix of a linear code \(C\) if \[Hc^T = 0 \Leftrightarrow c \in C.\]

The concatenation of two vectors \(u\) and \(v\) is denoted by \((u,v)\).

Let \(I\) be a set of position indices of a code \(C\). The punctured code \(C'\) is obtained from \(C\) by deleting the symbols in the codewords at positions in \(I\). If the sizes of the code \(C\) and its punctured code \(C'\) coincide, we call \(C'\) an iso-punctured code. We note the following simple property for an iso-punctured code \(C'\): \[\label{punc95min95dist} d(C') \leq d(C).\tag{3}\]

Remark 1 (iso-punctured 5G LDPC codes). If \(H\) is a parity-check matrix of a linear code \(C\) and \(I\) is a set of positions such that \(H^I\) is a full-rank matrix, then the code \(C'\) obtained from \(C\) by puncturing in the positions from \(I\) is iso-punctured. In particular, all punctured codes used in the 5G standard are obtained from certain codes (all-layer codes) and are iso-punctured, see Sections 2.3–2.4 below for more details.

2.2 Quasi-cyclic codes by modular lifting↩︎

A linear code \(C\) is called quasi-cyclic if there exists a divisor \(q\) of its length such that \[(c_1,\ldots,c_n)\in C \Leftrightarrow (c_q,c_1,\ldots,c_{q-1},\ldots,c_n,c_{n-q+1},\ldots,c_{n-1})\in C.\] In particular, quasi-cyclic codes with \(q=n\) are exactly cyclic codes.

Let \(E\) be a matrix whose elements are integers greater than or equal to \(-1\). We denote by \(C(E,q)\) the binary linear code with the parity-check matrix obtained from \(E\) as follows:

• each element \(E_{ij}\neq -1\) is replaced by the circulant matrix of order \(q\) corresponding to a cyclic shift by \(E_{ij} \bmod q\) positions;

• each element equal to \(-1\) is replaced by the zero matrix of order \(q\).

By construction, the code \(C(E,q)\) is quasi-cyclic. The matrix obtained from \(E\) by reducing every element different from \(-1\) modulo \(q\) is called the exponent matrix of \(C(E,q)\). The number \(q\) is called the circulant size of the code.

We index codeword positions starting from \(1\). Let \(c\) be a codeword of a quasi-cyclic code \(C\) of length \(qn\) and circulant size \(q\). The block support of \(c\) is the set \[\{\lceil \tfrac{i}{q} \rceil \,:\, c_i=1,\;i=1,\ldots,qn\}.\]

2.3 5G LDPC codes↩︎

To support a wide range of code rates and block lengths, the 5G standard uses a family of quasi-cyclic LDPC codes [1]. These codes are based on two collections of exponent matrices:

• eight matrices of size \(46 \times 68\), called base graph 1, or briefly BG1;

• eight matrices of size \(42 \times 52\), called base graph 2, or briefly BG2.

The matrices from the two base graphs are paired so that each pair has the same circulant size; we call this size the parent circulant size. The set of all parent circulant sizes is \[2^{8}, \quad 3\cdot 2^{7}, \quad 5 \cdot 2^{6}, \quad 7 \cdot 2^{5}, \quad 9 \cdot 2^{5}, \quad 11 \cdot 2^{5}, \quad 13 \cdot 2^{4}, \quad 15 \cdot 2^{4}.\] All circulant sizes \(q\) used in the standard are related to the corresponding parent circulant size \(\overline{q}\) by \[\frac{\overline{q}}{q}=2^i,for alli\geq 0.\]

For BG1 (respectively BG2) and any parent circulant size \(\overline{q}\), we denote the corresponding \(46\times 68\) (respectively \(42\times 52\)) exponent matrix by \(\mathcal{E}\) and call it the all-layer exponent matrix. For any \(q\) such that \(\overline{q}=2^i q\), the code \(C(\mathcal{E},q)\) is called an all-layer code.

An important feature of the 5G LDPC design is the following block structure of the exponent matrix \(\mathcal{E}\) and the corresponding parity-check matrix of the all-layer code: \[\label{decomp} \mathcal{E}=\left( \begin{array}{cccc} \epsilon & -1 \\ \mathcal{E}' & {\mathcal{T}} \\\end{array} \right)\leftrightarrow H= \left( \begin{array}{cccc} h & {\boldsymbol{0}} \\ H' & I \\\end{array} \right),\tag{4}\] where \(\epsilon\) is a \(4\times 26\) matrix, \({\mathcal{T}}\) is a \(42\times 42\) matrix with zeros on the main diagonal and \(-1\) elsewhere, \(I\) is the identity matrix of size \(42q\times 42q\). For BG2 the structure is analogous, with an identity matrix \(I\) of size \(38q\times 38q\) and a \(4\times 14\) matrix \(\epsilon\).

For \(j\geq 4\) and an all-layer matrix \(\mathcal{E}\), we denote by \({\mathcal{E}}_{[j]}\) its upper-left submatrix of size \[j\times (22+j) \quad \text{for BG1},\] and \[j\times (10+j) \quad \text{for BG2}.\]

In the 5G standard, the transmitted messages are obtained from codewords of \(C({\mathcal{E}}_{[j]},q)\) by puncturing the leftmost \(2q\) bits. We denote the resulting punctured code by \(C'({\mathcal{E}}_{[j]},q)\).

Thus, the LDPC codes supported by the standard can be summarized as follows: \[\label{eq:all95layer95codes} \begin{align} & \text{For any of the 16 all-layer exponent matrices \mathcal{E}} \\ & \text{with fixed parent circulant size \overline{q}, the codes } C'(\mathcal{E}_{[j]},q) \\ & \text{are considered for all j\geq 4 and all q such that } \overline{q}=q2^i,\;i\geq 0. \end{align}\tag{5}\]

Let us consider decomposition (4 ). We observe that the \(4\times 26\) matrix \(\epsilon\) is precisely \({\mathcal{E}}_{[4]}\), and we rewrite (4 ) as follows:

\[\label{eq:decomp2} \mathcal{E} = \left( \begin{array}{cccc} {\mathcal{E}}_{[4]} & -1 \\ \mathcal{E}' & {\mathcal{T}}\\ \end{array} \right) \leftrightarrow H = \left( \begin{array}{cccc} h & 0 \\ H' & I \\ \end{array} \right).\tag{6}\]

Throughout the work, we are especially focused on the codes \(C({\mathcal{E}}_{[4]},q)\) and \(C({\mathcal{E}}_{[6]},q)\) and their left puncturings \(C'({\mathcal{E}}_{[4]},q)\) and \(C'({\mathcal{E}}_{[6]},q)\), which we call \(4\)-layer and \(6\)-layer codes.

2.4 Minimum distance properties of punctured 5G LDPC codes↩︎

In this paper, we study the minimum distances of the codes \(C({\mathcal{E}}_{[j]},q)\) and their left puncturings \(C'({\mathcal{E}}_{[j]},q)\). In terms of error-correction capability, both classes are tightly connected due to the reasoning below.

• In order to reconstruct the punctured bits, the 5G LDPC decoder has to operate with the parity-check matrix of the nonpunctured code \(C({\mathcal{E}},q)\). As a result, its behavior is more naturally related to the code space of \(C({\mathcal{E}},q)\) than to that of \(C'({\mathcal{E}},q)\).

• The code \(C'({\mathcal{E}}_{[j]},q)\) is an iso-punctured code of the all-layer code \(C({\mathcal{E}},q)\). The nonpunctured code \(C({\mathcal{E}}_{[j]},q)\) obviously has minimum distance at least as large as that of the punctured code \(C'({\mathcal{E}}_{[j]},q)\) and for \(4\leq i\leq j\) \[\label{eq:left95punc} d(C'({\mathcal{E}}_{[i]},q)) \leq d(C'({\mathcal{E}}_{[j]},q)) \leq d(C({\mathcal{E}}_{[j]},q)) \leq d(C({\mathcal{E}},q)).\tag{7}\] Indeed, for \(j\geq 4\), the first \(2q\) and the last \(42q\) BG1 (\(38q\) for BG2) columns of the parity-check matrix obtained from \(\mathcal{E}\) are linearly independent, which implies (7 ) by Remark 1.

  Moreover, the leftmost \(2q\) bits are "highly protected"  because the corresponding first columns of the parity-check matrix have large weight, see Fig. 3. Therefore, for sufficiently large circulant sizes \(q\), minimum weight and small-weight codewords of \(C({\mathcal{E}},q)\) are unlikely to contain nonzero bits in the punctured positions. This is consistent with our observations for moderate and large code lengths; see Tables 2 and 3 for the case \(q=24\) and the results of the study of the minimum distances represented in Table 4.

2.5 Decoding of 5G LDPC codes↩︎

According to the 5G standard [1], at the encoder side the information bits are followed by a CRC block, forming the LDPC information block; the encoder then calculates the LDPC parity block, see Fig.  4.

At the decoding end, a high-level scheme for 5G LDPC codes is illustrated in Fig. 5. Each LDPC decoding attempt either terminates early when the full (or partial) syndrome condition is satisfied, or reaches the maximum number of iterations. In the latter case, the decoder still outputs an LDPC information block, which is then passed to the CRC stage for additional error detection. In what follows, we are mainly interested in the error-correction capability of the LDPC block itself, independently of the final CRC verification.

We define the LDPC information block error rate (IBLER) as the ratio of the number of frames in which the decoded information block differs from the transmitted one to the total number of frames. Similarly, we define the undetected information block error rate (UIBLER) for the LDPC block output as the ratio of the number of frames in which the decoded information block is incorrect and the early termination condition is satisfied, to the total number of frames.

For a \(24\)-bit CRC defined in the standard for LDPC codes, the corresponding combined LDPC and CRC undetected information block error rate is expected to be around \(2^{-24}\cdot 10^{-7}\) for a floating point decoder. Here the term \(10^{-7}\) comes from the worst-case LDPC UIBLER, see Section 5 for more details. This extremely low error probability, which cannot be captured with ordinary computer simulations, is one of the reasons CRC-related considerations are excluded from the current study.

2.6 Optical Communications Terminal standard codes↩︎

Some of the 5G LDPC codes introduced in [1] were later adopted in other communication standards, for example in the Optical Communications Terminal Standard Version 4.0.0 [5]. This standard uses the following four BG1 codes [5]: \[C'({\mathcal{E}}_{[6]},384), \quad C'({\mathcal{E}}_{[9]},384), \quad C'({\mathcal{E}}_{[13]},384), \quad C'({\mathcal{E}}_{[24]},384).\] In the OCT standard, each information block contains a \(144\)-bit header followed by a \(16\)-bit CRC, and the block is additionally protected by \(800\) parity bits of a convolutional code [5]. As a result, the information block error-detection capabilities of this standard are much stronger than in 5G, partly because of a simpler retransmission ARQ protocol. By contrast, 5G appends a \(24\)-bit CRC to the information block and uses a more sophisticated retransmission HARQ protocol.

3 Vontobel-Smarandache lemma for 5G LDPC codes↩︎

3.1 Vontobel-Smarandache lemma↩︎

Let \(E\) be an \(r\times n\) matrix with integer entries greater than or equal to \(-1\). For a positive integer \(q\), define the matrix \(P(E,q)\) over the quotient ring \[\mathbb{F}_2[x]/(x^q+1)\] by \[\label{eq:polynomial-shift-matrix} P(E, q)_{ij} = \begin{cases} 0, & E_{ij} = -1,\\ x^{E_{ij}\bmod q}, & E_{ij}\neq -1. \end{cases}\tag{8}\] We call \(P(E,q)\) the polynomial shift matrix associated with the quasi-cyclic code \(C(E,q)\). For \(a(x)=\sum_{t=0}^{q-1}a_t x^t\in \mathbb{F}_2[x]/(x^q+1)\), let \[\overline{a}=(a_0,\ldots,a_{q-1}).\] be its coefficient vector. Following Section 2.1, for a set \(S\) of column indices of \(P\), \(P^S\) denotes the submatrix of \(P\) formed by the columns indexed by \(S\). For a square matrix \(M\), we denote its determinant by \(det(M)\). The following theorem gives the construction of Vontobel and Smarandache.

Whenever \(c(S)\) is nonzero, its Hamming weight gives an upper bound on \(d(C(E,q))\). The method is most computationally effective for small number \(r\), which is the number of rows \(P\), since it requires determinants of \(r\times r\) matrices over \(R_q\). It has been applied to several code families, including AR4JA codes [15]. In [16], Butler used it to bound the minimum distances of several IEEE 802 communication standard codes with \(r\leq 12\).

3.2 Limitations for the all-layer 5G code↩︎

We first consider the all-layer BG1 code \(C({\mathcal{E}},384)\), where \(\mathcal{E}\) is the \(46\times68\) exponent matrix of lifting set 1 (LS1) in the 5G NR standard [1]. A direct application of Theorem 1 to this code is not computationally effective for the reasons below.

• For each subset \(S\) of size \(47\), the construction requires \(47\) determinants of \(46\times46\) matrices over the ring \(\mathbb{F}_2[x]/(x^{384}+1)\). In our experiments, the fastest implementation in Magma [7] required about \(10\) minutes per codeword. Our C++ implementation and publicly available implementations such as [17] were slower.

• Exhaustive enumeration is infeasible: one would have to inspect \(\binom{68}{47}\) subsets. Randomly selected subsets produce codewords of moderate or large weight; after several days of search, the smallest observed weight was \(456\), while typical weights were in the thousands.

Thus, although Theorem 1 is a powerful source of explicit codewords, applying it directly to the all-layer exponent matrix with \(46\) rows does not yield useful minimum distance bounds for the longest 5G code.

3.3 Vontobel–Smarandache lemma via the 4-layer code↩︎

The block decomposition in 6 provides a substantially more efficient way to use the same determinant construction. Recall that, for BG1, \[\mathcal{E}= \begin{pmatrix} {\mathcal{E}}_{[4]} & -1\\ \mathcal{E}' & {\mathcal{T}} \end{pmatrix}, \qquad H= \begin{pmatrix} h & 0\\ H' & I \end{pmatrix},\] where \({\mathcal{E}}_{[4]}\) is a \(4\times26\) exponent matrix and \(h\) is the corresponding parity-check matrix. Applying Theorem 1 to \(C({\mathcal{E}}_{[4]},384)\) requires only the computation of determinants of \(4\times4\) matrices over \(\mathbb{F}_2[x]/(x^{384}+1)\) and the enumeration of \(\binom{26}{5}\) subsets. This computation is practical on a personal computer.

The key observation is that every codeword \(c\) of the 4-layer code (i.e., \(hc^T=0\)) can be extended to a codeword of the all-layer code with parity-check matrix \(H\) as above by appending the uniquely determined parity part: \[c^\star=(c,cH'^T).\] Since \(H'\) is sparse, computing \(cH'^T\) is negligible compared with direct determinant evaluation via the Vontobel–Smarandache lemma for the all-layer matrix.

The resulting collection of weights gives explicit bounds on the minimum distance of the all-layer code. We illustrate the approach with the following toy example.

For \(q=384\), each nonzero codeword obtained from Theorem 1 generates an orbit of size \(384\) under simultaneous cyclic shifts of all circulant blocks. The resulting weight distribution is shown in Fig. 6.

By puncturing the obtained small weight codewords of \(C({\mathcal{E}},384)\) by \((46-j)384\) bits on the right, we obtain low-weight codewords of \(C({\mathcal{E}}_{[j]},384)\). The upper bound results are summarized in Table 1. The corresponding low weight codewords and verification scripts are available in the MATLAB code [18]. It turns out that the obtained low weight codewords are always codewords of the punctured codes \(C'({\mathcal{E}}_{[j]},384)\), supposedly because of a structural property of the code (the first two columns of the exponent matrix are dense, Fig. 3).

9pt

The idea behind Construction 1 can be used to design quasi-cyclic LDPC codes with a parity-check matrix structure similar to that of the 5G codes [8]. In below we note that the approach is equivalent to choosing special subsets \(S\) in Theorem 1, however the realization via calculating extra parity \(cH'^T\) is much more computationally saving than calculating the determinant directly.

4 Minimum distances via reduced quasi-cyclic codes↩︎

The results represented in Subsection 4.1 are rather natural. We could find close but not exact statements in [19], still, these are well-known results. For completeness, we provide their proofs in Appendix A.

4.1 Basic results↩︎

Let \(u_i\), \(i=1,\ldots,n\), be vectors of the same length \(q\). We denote by \(Dub(u_1,\ldots,u_n,l)\) the concatenation of these vectors, where each vector is repeated \(l\) times: \[Dub(u_1,\ldots,u_n,l)= (\underbrace{u_1,\ldots,u_1}_{l\text{ times}}, \underbrace{u_2,\ldots,u_2}_{l\text{ times}}, \ldots, \underbrace{u_n,\ldots,u_n}_{l\text{ times}}).\]

Let \[v = \left( v_1^1,\ldots,v_1^{\overline{q}/q}, v_2^1,\ldots,v_2^{\overline{q}/q}, \ldots, v_n^1,\ldots,v_n^{\overline{q}/q} \right)\] be a vector of \(C(E,\overline{q})\), where \(v_i^j\), \(i \in \{1,\ldots,n\}\), \(j\in \{1,\ldots,\overline{q}/q\}\) are all of lengths \(q\). Define the mapping \(R\) as follows: \[\label{eq:r} R(v,q,\overline{q})= \left( \sum_{t=1}^{\overline{q}/q}v_1^t, \sum_{t=1}^{\overline{q}/q}v_2^t, \ldots, \sum_{t=1}^{\overline{q}/q}v_n^t \right).\tag{9}\]

We finish by noting that the same statements hold for the punctured 5G codes \(C'({\mathcal{E}},q)\). They follow from the fact that the iso-punctured code \(C'({\mathcal{E}},q)\) has the same dimension as \(C({\mathcal{E}},q)\) and all codewords of \(C({\mathcal{E}},q)\) are obtained from those of \(C'({\mathcal{E}},q)\) by adding unique \(2q\) symbols.

As a preambule for the application of these theoretical results we continue with discussion of the code from Example 1.

4.2 Reduced modular Brouwer–Zimmermann algorithms↩︎

We recall the Brouwer–Zimmermann algorithm for finding the minimum distance [20]. Without loss of generality, let \(G\) be a generator matrix of a linear code \(C\) of dimension \(k\) and length \(n\) in the canonical form, i.e., \[G=[I\mid A].\]

To verify that the code distance is at least \(d_L\), we apply a variant of the Brouwer–Zimmermann algorithm using Magma’s VerifyMinimumDistanceLowerBound intrinsic with input \(d_L\).

Both of the above algorithms support a “parallel” realization, where several generator matrices with pairwise disjoint information sets are constructed, providing a faster growth of the lower bound \(d_L\) than nonparallel versions [20].

Straightforwardly, disjoint information sets exist only for low-rate codes, as the dimension is necessarily at most half the length of the code. There are variations of the parallel Brouwer-Zimmermann algorithm for high-rate codes using the notion of a partial information set [20], [21], but the lower bound growth for such codes is not as rapid as for low-rate codes.

Now consider the estimation of the minimum distance for the all-layer 5G LDPC codes \(C({\mathcal{E}},384)\) and \(C({\mathcal{E}}_{[4]},384)\) with the \(46\times68\) BG1 exponent matrix \(\mathcal{E}\) and its submatrix \({\mathcal{E}}_{[4]}\). The minimum distances of \(C({\mathcal{E}},q)\) for \(q=3\) and \(q=6\) are \(8\) and \(14\), respectively, directly applying Magma’s function MinimumDistance. For the code with \(q=12\), using VerifyMinimumDistanceLowerBound, we can calculate \[d\bigl(C({\mathcal{E}},12)\bigr)\geq 22.\] By Theorem 2.[T1:item3], \(22\) is a lower bound on the minimum distance of the codes with \(\overline{q}=12\cdot 2^i\), \(i\geq 0\), including \(\overline{q}=384\): \[d\bigl(C({\mathcal{E}},2^k\cdot3)\bigr)\geq 22,\quad k\geq 2.\]

On the other hand, a direct application of VerifyMinimumDistanceLowerBound for the code with \(\overline{q}=384\) is not available in Magma due to limitations on the code length.

Based on Theorem 3, the same concept applies to punctured codes, and \[d\bigl(C'({\mathcal{E}},384)\bigr)\geq d\bigl(C'({\mathcal{E}},12)\bigr)\geq 22.\]

Similarly, we evaluate the minimum distance of the 24-layer code \(C({\mathcal{E}}_{[24]},384)\): \[d\bigl(C({\mathcal{E}}_{[24]},384)\bigr),\;d\bigl(C'({\mathcal{E}}_{[24]},384)\bigr)\geq d\bigl(C({\mathcal{E}}_{[24]},12)\bigr) = d\bigl(C'({\mathcal{E}}_{[24]},12)\bigr) = 13,\] where the minimum distances of the codes \(C({\mathcal{E}}_{[24]},12)\) and \(C'({\mathcal{E}}_{[24]},12)\) were found by the built-in parallel Brouwer–Zimmermann algorithm in Magma.

\(^*\) All \(96\) words have the following block supports: \(\{4,9,21,22,24\}\), \(\{4,5,8,16,26\}\), \(\{18,20,24,25,26\}\), \(\{5,8,12,19,25\}\)

.

For \(q=48\), solving the problem via the Brouwer–Zimmermann algorithm in Magma directly required a substantial amount of computational time (\(472\,797\) seconds on a personal computer to obtain a lower bound of \(6\)), and it becomes absolutely computationally infeasible for \(q=96\) and \(q=192\), despite the fact that it can be solved in a couple of hours using the approach with a high-level description provided in Algorithms 3 and 4 and the details below.

We gradually increase the circulant sizes starting from \(48\): \(48\), \(96\), and \(192\).

Case \(q=48\), \(96\). The minimum distance of \(C({\mathcal{E}}_{[4]},24)\) is \(5\), and there are exactly \(96\) codewords of weight \(5\) having four different block supports: \[\label{e95supp} \begin{gather} \{4,9,21,22,24\},\quad \{4,5,8,16,26\},\\ \{18,20,24,25,26\},\quad \{5,8,12,19,25\}. \end{gather}\tag{10}\] By Theorem 2.[T1:item3], we observe that the minimum distance of \(C({\mathcal{E}}_{[4]},48)\) is also at least \(5\), and the reduction mapping \(R(v,24,48)\) 9 sends any weight \(5\) codeword \(v\) of \(C({\mathcal{E}}_{[4]},48)\) to a weight \(5\) codeword of \(C({\mathcal{E}}_{[4]},24)\), because the minimum distance of the latter is \(5\). Also, by Corollary 1, the block support of \(R(v,24,48)\) is one of the sets (10 ) for the weight \(5\) codewords of \(C({\mathcal{E}}_{[4]},24)\). Therefore, checking whether \(d\bigl(C({\mathcal{E}}_{[4]},48)\bigr)\) is \(5\) boils down to checking whether \(d\bigl(C({\mathcal{E}}_{[4]}^S,48)\bigr)\) is \(5\) for those four block supports \(S\) from (10 ) such that \(d\bigl(C({\mathcal{E}}_{[4]}^S,24)\bigr)=5\). This solution also benefits from the fact that the code \(C({\mathcal{E}}_{[4]}^S,48)\) has an exponent matrix \({\mathcal{E}}_{[4]}^S\) with only \(4\) rows and \(5\) columns. Due to the rate of the code \(C({\mathcal{E}}_{[4]}^S,48)\) being \(\frac{1}{5}\), most of the time the Brouwer–Zimmermann algorithm uses its parallel version when checking whether the lower bound on \(d\bigl(C({\mathcal{E}}_{[4]}^S,24)\bigr)\) is \(6\). These jobs were finished with a positive answer, indicating that \[d\bigl(C({\mathcal{E}}_{[4]},48)\bigr)\geq 6.\] The idea is generalized in Algorithm 3, which we use as follows:

1. The weight \(5\) codewords of \(C({\mathcal{E}}_{[4]},24)\) are found using Words\((\cdot)\), and \(B\) is the set of their block supports.

2. Algorithm 9 with \(q=48\), \(j=1\), \(E={\mathcal{E}}_{[4]}\), \(B\), and \(d_L=5\) gives \[d(C({\mathcal{E}}_{[4]},48))\geq d_L+1=6.\]

On the other hand, studying the \(6\)-subsets of \(\{1,\ldots,26\}\), we found a set \[S=\{4,7,13,14,17,23\}\] with \(d(C({\mathcal{E}}_{[4]}^S,96))=6\), so from Theorem 2.[T1:item3] we have \[6 \leq d(C({\mathcal{E}}_{[4]},48))\leq d(C({\mathcal{E}}_{[4]},96))=6\] and therefore \(d(C({\mathcal{E}}_{[4]},48))=d(C({\mathcal{E}}_{[4]},96))=6\).

Case \(q=192\). From the above we have \(d(C({\mathcal{E}}_{[4]},96))=6,\) which is a lower bound on \(d(C({\mathcal{E}}_{[4]},192))\) by Theorem 2.[T1:item3] We improve the lower bound from \(6\) to \(8\) as follows. Any weight \(6\) or \(7\) codeword \(v\) of \(C({\mathcal{E}}_{[4]},192)\) has a block support of size \(7\) or less. By Corollary 1 the block support contains the block support of the reduced nonzero word \(R(v,48,192)\) of the code \(C({\mathcal{E}},48)\).

We study all \(7\)-subsets of \(\{1,\ldots,26\}\). For any such \(7\)-subset \(S\) we launch Brouwer–Zimmermann algorithm for the code \(C({\mathcal{E}}_{[4]}^S,48)\) to check whether \(d(C({\mathcal{E}}_{[4]}^S,48))\) (note that the circulant size is \(48\) here) is at least \(8\) (each of which are finished relatively fast). The answer is negative only for \(276\) subsets out of \((^{26}_7)=657800\). For each of these subsets, we launch Brouwer–Zimmermann algorithm to check whether \(d(C({\mathcal{E}}_{[4]}^S,192))\) is at least \(8\). These jobs are finished with positive answer, indicating that \[d(C({\mathcal{E}}_{[4]},192))\geq 8.\] The idea is generalized in Algorithm 4, which we use as follows:

1. Let \(B\) be the set of all \(7\)-subsets of \(\{1,\ldots,26\}\).

2. Apply Algorithm 10 with \(q=48\), \(j=1\), \(E={\mathcal{E}}_{[4]}\), \(B\), and \(d_L=7\). The output \(B'\) contains the block supports of \(C({\mathcal{E}}_{[4]},48)\) (and \(C({\mathcal{E}}_{[4]},192)\) as well) for weight \(6\) and \(7\) words.

3. Apply Algorithm 10 with \(q=192\), \(j=2\), \(E={\mathcal{E}}_{[4]}\), \(B=B'\), and \(d_L=7\). The output is an empty set, so \[d(C({\mathcal{E}}_{[4]},192))\geq 8.\]

On the other hand, studying the \(7\)-subsets of \(\{1,\ldots,26\}\), we found a set \(S=\{5,8,9,15,18,25,26\}\) with \(d(C({\mathcal{E}}_{[4]}^S,192))=8\), thus \[d(C({\mathcal{E}}_{[4]},192))=8.\]

Punctured codes. Because of Theorem 3 similar ideas work for the punctured codes \(C'({\mathcal{E}}_{[4]},q)\). The low weight distribution for the codes \(C'({\mathcal{E}}_{[4]},q)\), \(q=3\), \(6\), \(12\), \(24\) was obtained (see Table 3) using the Magma intrinsic Words\(()\), and the code \(C'({\mathcal{E}}_{[4]},24)\) has the same minimum distance \(5\) as the nonpunctured code \(C({\mathcal{E}}_{[4]},24)\).

All weight \(5\) codewords of \(C({\mathcal{E}}_{[4]},24)\) have \(4\) block supports. Testing this collection \(B\) in Algorithm 3 yields \(6\leq d(C'({\mathcal{E}}_{[4]},48))\), which, combined with the fact that the nonpunctured codes \(C({\mathcal{E}}_{[4]},48)\), \(C({\mathcal{E}}_{[4]},96)\) have minimum distance \(6\), gives us from (3 ): \(6\leq d(C'({\mathcal{E}}_{[4]},48))\leq d(C'({\mathcal{E}}_{[4]},96))\leq d(C({\mathcal{E}}_{[4]},96))\leq 6\), so \[d(C'({\mathcal{E}}_{[4]},48))=d(C'({\mathcal{E}}_{[4]},96))=6.\]

To establish lower bound \[7\leq d(C'({\mathcal{E}}_{[4]},192)),\] it is sufficient to exclude the case \(d(C'({\mathcal{E}}_{[4]},192))=6\). The approach relies on Algorithm 4. The words of weights at most \(6\) of the code \(C'({\mathcal{E}}_{[4]},12)\) were found by the Magma function Words\(()\) and have \(13485\) block supports. By checking that \(d(C'({\mathcal{E}}^S,24))\geq 7\), we exclude some of these block supports, and there are \(4068\) block supports of the words of weight at most \(6\) in the code \(C'({\mathcal{E}}^S,24)\). Further, by checking that \(d(C'({\mathcal{E}}^S,48))\geq 7\), we exclude most of the block supports, and there are just \(22\) block supports of the words of weight at most \(6\) in the code \(C'({\mathcal{E}}^S,48)\). By checking that \(d(C'({\mathcal{E}}^S,96))\geq 7\), we have just \(1\) block support of the words of weight at most \(6\) in the code \(C'({\mathcal{E}}^S,96)\). Finally, we checked that \(d(C'({\mathcal{E}}^S,192))\geq 7\) for the only such subset \(S\), indicating that \(d(C'({\mathcal{E}},192))\geq 7\). Using Algorithm 4, we followed the steps below.

1. Let \(B\) be the set of block supports of codewords of \(C'({\mathcal{E}}_{[4]},12)\) of weight at most \(6\); these supports are found using Words\(()\), and \(|B|=13485\).

2. Apply Algorithm 10 with \(j=1\), \(q=24\), \(d_L=6\), and \(B\); the output \(B'\): \(|B|=4068\).

3. Apply Algorithm 10 with \(j=1\), \(q=48\), \(d_L=6\), and \(B=B'\); the output \(B'\): \(|B|=22\).

4. Apply Algorithm 10 with \(j=1\), \(q=96\), \(d_L=6\), and \(B=B'\); the output \(B'\): \(|B|=1\).

5. Apply Algorithm 10 with \(j=1\), \(q=192\), \(d_L=6\), and \(B=B'\); the output \(B'\): \(|B|=0\), which indicates that \[d(C'({\mathcal{E}}_{[4]},192))\geq 7.\]

Mostly, the minimum distances of the high-rate 5G LDPC codes are small, which, in particular, probably results in a noticeable LDPC UIBLER in their decoding compared to a random code; see Fig. 11. On the pro side, the LDPC UIBLER is easily caught by verifying the CRC block. Moreover, the 5G code design arguably suits better the HARQ protocol and low-complexity encoding in hardware. We proceed further with exploiting modulo reduction ideas for early termination of decoding5G codes in the next section.

5 LDPC early termination based on reduced shifters↩︎

A natural idea to reduce the complexity of syndrome calculation for 5G LDPC codes was proposed in [22] and is based on the decomposition 4 . Since all codes in the 5G standard involve more than four layers of parity checks 5 , it was suggested to terminate decoding early when the word passes the checks corresponding to the first four layers of the parity-check matrix. We refer to this method as the \(4\)-layer early termination approach for LDPC decoding.

Further, the ideas described in the previous section lead us to the following reduction of the syndrome calculation complexity.

Let \(E = \begin{pmatrix} E'\\ E''\\ E''' \end{pmatrix}\) be the exponent matrix of a quasicyclic code \(C(E,q)\), where \(E'\), \(E''\), and \(E'''\) have \(t'\), \(t''\), and \(t'''\) rows, respectively, and \(t = t' + t'' + t'''\) is the total number of rows of \(E\). A word \(v\) is a codeword of \(C(E,q)\) if and only if \[H'v^{T} = 0,\quad H''v^{T} = 0,\quad H'''v^{T} = 0,\] where \(H'\), \(H''\), and \(H'''\) are obtained by unrolling \(E'\), \(E''\), and \(E'''\), respectively, with circulants of size \(q\). By Theorem 2, if \(v\) is a codeword of \(C(E'',q)\), then for a divisor \(q'\) of \(q\), the vector \(R(v,q',q)\), defined in 9 , is a codeword of the “small code” \(C(E'',q')\) with parity-check matrix \(\widetilde{H}''\), which has \(q/q'\) times fewer rows and columns than \(H''\). We say that the early termination condition \(T(t'_{q},t''_{q'})\) holds for \(v\) if \[H'v^{T} = 0,\] and \[\widetilde{H}'' R(v,q',q)^{T} = 0.\]

Early termination conditions are used with the min-sum decoder, see Algorithm 12. The results of this algorithm with various early termination techniques for the 5G code and a random code are shown in Figs. 13 and 14.

We now outline the most important subcases.

Full syndrome early termination \(T(t_q,0)\). We declare LDPC decoding successful for a word \(v\) if \(H'v^{T} = 0\), \(H''v^{T} = 0\), and \(H'''v^{T} = 0\), that is, only when \(v\) is a codeword of the quasi-cyclic code \(C(E,q)\). This is the most reliable termination approach from the undetected error point of view. In Figs. 13 and 14, this case corresponds to the curves shown in light blue and red, namely \(T(6_{384},0)\) and \(T(8_{192},0)\). This approach was also used in the experiments shown in Figs. 1 and 2.

\(4\)-layer early termination \(T(4_q,0)\). In this case we completely disregard two last check layers even in the mod \(q'\) reduced form. The option works only for 5G LDPC code and is arguebly related to matrix design and decomposition (4 ) in particular. This idea was proposed in [22].

We suggest going further and reducing the last two layers of the parity-check matrix \(H\) modulo a small factor \(q'\) of \(q = 384\) (e.g., \(q' = 16\)), and we propose the early termination criterion \(T(2_{384},2_{16})\).

Implementation note. All simulations used the same C++ decoder core. It implements floating point layered normalized min-sum decoder, corresponding to the norm-min-sum mode of the MATLAB LDPC decoder [23]. The min-sum update rule itself is unchanged: the program computes check node signs, the smallest and second smallest incoming magnitudes, applies the normalization factor, and updates LLRs layer by layer. The implemented modification is only the early termination module. It selects which syndrome test is applied to the hard-decision word after an iteration.

More precisely, the C++ program stores the lifted parity-check matrix in a sparse row representation. For every row it keeps the position of the first nonzero entry in a global column-index array, the row weight, and the indices of all nonzero columns. This representation is used both by the layered min-sum update and by the syndrome calculation. Therefore, the experiments do not compare different decoders; they compare the same decoder with different values of the termination modes.

Early termination is evaluated only after a complete iteration has been processed. The hard decision is not stored as a separate vector during the iterations; the syndrome routine reads it directly from the signs of the current LLRs. A negative LLR is interpreted as bit one, and a nonnegative LLR as bit zero. Thus, the full and partial syndrome checks are computed by XOR-summing the signs over the sparse row representation.

The reduced check is evaluated without constructing a new full parity-check matrix. In the C++ code, a reduced layer is handled by scanning the selected rows of the lifted matrix and accumulating their parities into \(q\) bins according to the row index modulo \(q\). This implements the operation \(R(v,q,384)\) in the stopping test. For example, in the \(T(2_{384},2_{16})\) early termination the first two layers give \(2\cdot 384\) ordinary parity checks, while the next two layers give only \(2\cdot 16\) reduced checks.

The simulator records whether the decoder stopped before the maximum number of iterations and returns the iteration count. The same output word is then used to count information-block errors and undetected LDPC errors.

Conclusion. For 5G decoder degradation under alternative termination criterias is insignificant, given that 5G is targeted at retransmission HARQ scheme. Actually, the IBLER plots for \(T(4_{384},0)\) termination vs \(T(6_{384},0)\) termination (full syndrome) 5G code are surprisingly close with a minor difference of \(4*10^{-8}\) for error rate only at low SNR point at \(2.9\), and the IBLER results for other points were identical (we ran \(10^8\) frames for each point). This provides a solid ground for choosing the latter in [22] and as a priority early termination option for OCT standard [5].

In 5G codes with all types of early termination: by all-layers (syndrome), \(4\)-layers and reduced \(4\)-layers early terminations there were instances where decoder stopped with undetected errors such that the decoded information block is incorrect, despite that the syndrome (full, four layers or reduced four layers) is zero, see Fig. 14. We also see that 5G LDPC code with termination criteria \(T(2_{384},2_{16})\) has relatively higher UIBLER, see Fig. 14. Further in CRC check block, see Fig.5 these frames are still detected as erroneous because they highly likely have incorrect CRCs. We exclude the further CRC check in our investigation because combined UIBLER for CRC and LDPC for such 24 bit CRC check is \(2^{-24}10^{-7}\) is impossible to catch using ordinary computer.

We see that the reduced early termination \(T(3_{192},5_{16})\) for the random code shows insignificant increase in undetected errors. In general, the tests of 5G code and random code shows that the reduction approach for syndrome calculation can be used for LDPC codes in communication systems with retransmission and extra error-detection features like CRC.

The authors would like to express their gratitude to Alexander Subach, who provided the first C++ implementation of reduced early termination condition and confirmed its feasibility at the early stages of this study.

6 Appendix A.↩︎

The proof of Lemma 1.

The proof of Theorem 2

References↩︎