Decoding Quadratic Residue Codes Using Deep Neural Networks

Abstract

In this paper, a low-complexity decoder based on a neural network is proposed to decode binary quadratic residue (QR) codes. The proposed decoder is based on the neural min-sum algorithm and the modified random redundant decoder (mRRD) algorithm. This new method has the same asymptotic time complexity as the min-sum algorithm, which is much lower than the difference on syndromes (DS) algorithm. Simulation results show that the proposed algorithm achieves a gain of more than 0.4 dB when compared to the DS algorithm. Furthermore, a simplified approach based on trapping sets is applied to reduce the complexity of the mRRD. This simplification leads to a slight loss in error performance and a reduction in implementation complexity.

1. Introduction

Binary channel codes are of significant importance in physical-layer digital communications, and the minimum Hamming distance has a direct effect on their error correction performance. As a class of cyclic Bose–Chaudhuri–Hocquenghem (BCH) codes with rates no less than 1/2, the binary quadratic residue (QR) codes [1] generally have large minimum Hamming distances and many of them are known to have the best error performances among binary codes which have similar code lengths and rates. Practically, the (24,12,8) extended QR code has been used in imaging systems for space exploration [2] and high-frequency radio systems [3].

To the best of our knowledge, the algebraic algorithms are the only approaches for decoding QR codes. Until now, the most efficient general algorithm was the DS algorithm [4], which is a look-up table decoding method. The complexity of the DS algorithm grows rapidly as the code length grows. Therefore, the DS algorithm could hardly be implemented on devices with limited hardware resources, especially for QR codes of long block lengths. For example, to decode a (127,64,19) QR code, the DS algorithm may need more than $4\times {10}^7$ finite field additions and $2\times {10}^6$ real additions. Recently, Duan et al. [5] developed an improved version of the DS algorithm, i.e., the IDS algorithm, which further speeds up the decoding of QR codes of lengths within 100. However, the IDS algorithm is still too complex to decode many longer QR codes. Therefore, the error-correcting performance of most QR codes of lengths beyond 150 is unknown so far. On the other hand, with the rapid development of graphics processing units, deep learning (DL)-based encoding/decoding schemes have been extensively investigated (see [6,7,8,9,10,11,12,13,14,15] and references therein). They provide alternative solutions to channel decoding and also motivate our work on developing neural decoders for QR codes because neural decoders’ complexity has a lower order of growth than that of the DS algorithm.

In general, DL-aided neural decoders can be designed using either data-driven or model-driven approaches. It is noted that the main disadvantages of pure data-driven decoders/autoencoders lie in the high training complexity and weak scalability to long block lengths, as such decoders only depend on random training data. Additionally, the performance superiority of neural channel codes comes from the continuous codeword distribution as opposed to binary codewords [6,11]. Therefore, they are not compatible with current digital communication systems. As an alternative, model-driven neural decoders are built from widely deployed decoding algorithms and could avoid the aforementioned drawbacks. One of the most commonly used decoding schemes is the belief propagation (BP) algorithm, which performs decoding on a sparse factor graph. It is known that the BP algorithm is optimal for Tanner graphs without cycles. Practically, the algorithm achieves satisfactory performance for decoding LDPC codes with a limited number of short cycles in a graph. Inspired by this fact, researchers have built various BP-driven neural decoders [7,8,10,14,15,16,17,18]. In [16], Gruber et al. observed that a neural network could generalize to codewords which had not been trained in the training stage. In [17], Nachmani et al. proposed a neural network structure by unrolling the iterative decoding structures of the BP algorithm. By doing so, the weights associated with the edges of the original Tanner graph could be optimized during the training process, which enhanced the decoding performance. In [18], Lugosch et al. further reduced the complexity by generalizing the min-sum algorithm to neural networks. Notably, RNN-based and graph-neural-network-based BP-driven neural decoders have been investigated in [10] and [8], respectively. In addition to the aforementioned BP-driven neural decoders, a neural decoder driven by the conventional max-log-maximum a posteriori (MAP) algorithm was designed to decode turbo codes in [12].

It is worth pointing out that the performance of BP decoders deteriorates severely for high-density parity-check (HDPC) codes such as BCH codes and QR codes. It is because the corresponding graphs of these codes always comprise many short cycles. In [10], BP-driven neural decoders were utilized to decode linear codes such as BCH codes. Moreover, the authors of [10] also applied the proposed BP-driven neural decoder into the modified random redundant decoder (mRRD) [19], and the resultant neural mRRD method could approach the maximum likelihood (ML) performance. However, it suffered from an extensive storage and computational complexity corresponding to the demanding permutation group and the number of iterations. For instance, the size of the permutation group of a the (23,12,7) QR code amounts to around ${10}^7$, which greatly limits the practical circuit implementations.

In [15], a deep-learning-aided node-classified redundant decoding algorithm was presented for decoding BCH codes. The algorithm first partitioned the variable nodes into different categories by the k-median method. Then, a list of permutations was produced for bit positions, and these permutations were sorted according to their reliability metrics. Finally, the BP-driven neural decoder conducted decoding based on the sorted permutations. It was shown that certain permutations indeed performed better for some specific codewords, but a substantial number of computations for evaluating and sorting permutations was still required. More recently, a BP-driven neural decoder imposing a cyclically invariant structure was proposed for decoding BCH codes [7].

In order to address the problem of the inefficient design of BP-driven neural decoders for binary QR codes, this paper simplifies the neural network based on the min-sum algorithm and the mRRD algorithm. The proposed neural decoder utilizes only cyclic permutations that are selected according to the distribution of small trapping sets, instead of using all possible permutations in the permutation group and is hence more practical for hardware implementations. We further point out that most of the min-sum iterations can be processed in parallel. To summarize, the main contributions of this paper include the following:

• We illustrate that the performance of the BP/min-sum algorithm is highly relevant to small trapping sets rather than four-cycles for some QR codes.
• We modify the original mRRD using a neural network decoder. We replace the random permutations by a cyclic shift. The cyclic shift is selected based on the distribution of small trapping sets.
• We obtain the error performances of QR codes of lengths beyond 200 using the proposed Cyclic-mRRD algorithm. The performances of these QR codes are hard to obtain using traditional methods such as the DS algorithm, because their minimum distances are unknown and the decoding algorithm is extremely complex.

The remainder of this paper is structured as follows. Section 2 provides some preliminaries about QR code, mRRD, trapping sets and linear programming decoding. Section 3 introduces the neural BP-based algorithms. Section 4 describes the proposed Cyclic-mRRD and Chase-II-mRRD with a trapping sets analysis. Section 5 gives the simulation results and complexity analysis of the proposed algorithms. Finally, this paper concludes with a summary in Section 6.

2. Preliminaries

2.1. Quadratic Residue Code

An $(n,k)$ QR code is a QR code of length n and dimension k. The code length of a QR code is a prime number n which satisfies $n=8l\pm 1$ with l being a positive integer. Moreover, the set $Q_n$ represents the quadratic residues modulo n, i.e.,

$$Q_n=\left\{i\right|i\equiv j^2\mathrm{mod}n,\mathrm{for}j\in \{1,2,...,n-1\}\}.$$

(1)

Let m be the smallest positive integer such that n divides $2^m-1$, $\alpha$ be a primitive element in $GF\left(2^m\right)$ and $\beta$ be a primitive nth root of unity in $GF\left(2^m\right)$. Then, we have $\beta ={\alpha }^{(2^m-1)/n}$, and the generator polynomial of a QR code of length n is given by,

$$g\left(x\right)=\prod _{i\in Q_n}(x-{\beta }^i).$$

(2)

The codeword polynomial $u\left(x\right)$ can be derived from the message polynomial $m\left(x\right)$ and the generator polynomial $g\left(x\right)$ using $u\left(x\right)=m\left(x\right)·g\left(x\right)$.

There are 11 QR codes with a code length below 100. They are the (7,4), (17,9), (23,12), (31,16), (41,21), (47,24), (71,36), (73,37), (79,40), (89,45) and (97,49) QR codes.

2.2. Modified RRD Algorithm

A permutation permutes the order of bits in a codeword. For example, a permutation $\sigma =\left(\begin{array}{ccc}0& 1& 2\\ 2& 1& 0\end{array}\right)$ permutes any codeword $\mathbf{u}=(u_0,u_1,u_2)$ to $\sigma \left(\mathbf{u}\right)=(u_2,u_1,u_0)$. A permutation group $\mathrm{Per}\left(C\right)$ is a group of permutations which send any codeword in codebook $C$ back to the codebook itself. That is, after applying any permutation $\sigma$ in the $\mathrm{Per}\left(C\right)$ to any codeword in $C$, the result is still a codeword in $C$, i.e.,

$$\mathrm{Per}\left(C\right)=\left\{\sigma \right|\sigma \left(\mathbf{u}\right)\in C,\forall \mathbf{u}\in C\}.$$

(3)

It is obvious that all cyclic shifts will be in $\mathrm{Per}\left(C\right)$ for any cyclic code. The algorithm to compute the group generators to generate the whole $\mathrm{Per}\left(C\right)$ was proposed in [20].

The mRRD is a modified version of RRD [21]. Compared with RRD, the mRRD has better error performance and a lower complexity. An mRRD decoder can be denoted as $\mathrm{mRRD}(W,L,I)$, which means the mRRD decoder contains W parallel pipelines, each pipeline consisting of L BP decoders and every BP decoder conducting I BP iterations, as shown in Figure 1. The mRRD algorithm uses the permutations in the permutation group of a code to permute the input log-likelihood-ratio (LLR) vector before each BP decoder. At the end, the following least metric selector (LMS) is applied to the candidate codeword set $\widehat{U}$ and the received sequence $\mathbf{r}$, and the best codeword is chosen.

$$\mathrm{LMS}:\widehat{\mathbf{u}}={\mathrm{argmax}}_{\widehat{\mathbf{u}}\in \widehat{U}}\sum _{i=1}^n{|r_i-\widehat{u_i}|}^2.$$

(4)

2.3. Trapping Set

The term “trapping set” was introduced by Richardson [22] in 2003. A Tanner graph G can be denoted by $G=(\mathbb{V}\cup \mathbb{C},\mathbb{E})$, where $\mathbb{V}$, $\mathbb{C}$, $\mathbb{E}$ represent the sets of variable nodes, check nodes and edges connecting the variable nodes and check nodes. Let S be a subset of $\mathbb{V}$, $\Gamma \left(S\right)$ be a set of check nodes connected to variable nodes in S and $T\left(S\right)$ be a subgraph containing S, $\Gamma \left(S\right)$ and the edges connecting S and $\Gamma \left(S\right)$. $\Gamma \left(S\right)$ can be further divided into two sets: ${\Gamma }_o\left(S\right)$ representing check nodes of odd degree and ${\Gamma }_e\left(S\right)$ representing check nodes of even degree. Denoting $a=\left|S\right|$ and $b=|{\Gamma }_o\left(S\right)|$, then $T\left(S\right)$ is an $(a,b)$ trapping set. See Figure 2 for an exemplary (3,1) trapping set.

Generally speaking, trapping sets with smaller a and b are considered to be more harmful. Hence, they are called dominant trapping sets. The existence of dominant trapping sets can affect the performance of the BP algorithms dramatically.

3. Neural Belief Propagation Network

The classic BP algorithm is a message-passing algorithm performed on the Tanner graph of a code. Let $\mathbf{r}$ be the received information vector, $V_{ij}$ be the information passed from variable node $v_i$ to check node $c_j$ and $C_{ji}$ be the information passed from $c_j$ to $v_i$. Assume the codeword $\mathbf{u}\in {\{0,1\}}^n$ is sent through a binary input additive white Gaussian noise (BI-AWGN) channel. Then, we have a BPSK-modulated vector $\mathbf{y}\in {\{-1,+1\}}^n$ where $y_i={(-1)}^{u_i}$, a noise vector $\mathbf{n}\in {\mathbb{R}}^n$ where $n_i\sim \mathcal{N}(0,{\sigma }^2)$ and a received vector $\mathbf{r}=\mathbf{y}+\mathbf{n}$. For log-domain belief propagation (BP) algorithm, the LLR value of $v_i$ is:

$${\gamma }_i=\ln \frac{\mathrm{Pr}(y_i=+1|r_i)}{\mathrm{Pr}(y_i=-1|r_i)}=\frac{2r_i}{{\sigma }^2}.$$

(5)

The messages from variable nodes to check nodes are given by,

$$V_{ij}={\gamma }_i+\sum _{j^{\prime }\in N\left(v_i\right)\setminus c_j}{C}_{j^{\prime }i},$$

(6)

where $N\left(x\right)\setminus y$ means the set of x’s neighbors excluding y. For the first iteration, there are no incoming messages from the check nodes, so the values of $C_{j^{\prime }i}$ are set to 0. Furthermore, the messages from check nodes to variable nodes are given by,

$$C_{ji}=2{\tan \mathrm{h}}^{-1}\left(\prod _{i^{\prime }\in N\left(c_j\right)\setminus v_i}\tan \mathrm{h}(V_{i^{\prime }j}/2)\right).$$

(7)

For neural networks, each layer represents a half-BP iteration (check nodes to variable nodes or variable nodes to check nodes). Therefore, it needs two layers (an odd layer and an even layer) to perform a single BP iteration. We denote the weights associated with each layer as ${\mathbf{w}}^{\mathbf{o}\mathbf{2}\mathbf{e}}$ and ${\mathbf{w}}^{\mathbf{e}\mathbf{2}\mathbf{o}}$. Accordingly, (6) and (7) are replaced, respectively, by,

$$V_{ij}={\gamma }_i+\sum _{j^{\prime }\in N\left(v_i\right)\setminus c_j}{w}_{j^{\prime }i}^{e2o}·C_{j^{\prime }i},$$

(8)

$$C_{ji}=2{\tan \mathrm{h}}^{-1}\left(\prod _{i^{\prime }\in N\left(c_j\right)\setminus v_i}{w}_{i^{\prime }j}^{o2e}·\tan \mathrm{h}(V_{i^{\prime }j}/2)\right).$$

(9)

An example structure of constructed neural network for the (7,4) QR code is illustrated in Figure 3.

By replacing BP decoders by min-sum decoders, we can obtain neural min-sum decoders as in (10). Here, we used a modified min-sum algorithm called threshold attenuated min-sum algorithm (TAMS) [23], and the neural network version was given by,

$$C_{ji}=\left\{\begin{array}{c}{\alpha }_c\underset{i^{\prime }\in N\left(c_j\right)\setminus v_i}{\min }|w_{i^{\prime }j}^{o2e}·V_{i^{\prime }j}|\prod _{i^{\prime }\in N\left(c_j\right)\setminus v_i}\mathrm{sign}(w_{i^{\prime }j}^{o2e}·V_{i^{\prime }j})\phantom{aaaa}\mathrm{if}\underset{i^{\prime }\in N\left(c_j\right)\setminus v_i}{\min }|w_{i^{\prime }j}^{o2e}·V_{i^{\prime }j}|<\tau \hfill \\ \underset{i^{\prime }\in N\left(c_j\right)\setminus v_i}{\min }|w_{i^{\prime }j}^{o2e}·V_{i^{\prime }j}|\prod _{i^{\prime }\in N\left(c_j\right)\setminus v_i}\mathrm{sign}(w_{i^{\prime }j}^{o2e}·V_{i^{\prime }j})\phantom{aaaaaa}\mathrm{otherwise},\hfill \end{array}\right.$$

(10)

where ${\alpha }_c$ and $\tau$ are an attenuation coefficient and a threshold, respectively. The values of ${\alpha }_c$ and $\tau$ were set empirically to 0.7 and 1.5, respectively. Moreover, a sigmoid function was applied to convert LLR to probabilities after the final iteration.

Given a parity check matrix, the network structure is determined. We applied the algorithm in [21] to reduce the cycles in parity check matrices and used the cycle-reduced parity-check matrix to construct the neural network. We used different weights for I times of BP/min-sum iterations, and the parameter space was $\Omega =\{{\mathbf{w}}^{\mathbf{o}\mathbf{2}\mathbf{e},\mathbf{1}},{\mathbf{w}}^{\mathbf{e}\mathbf{2}\mathbf{o},\mathbf{1}},\cdots ,{\mathbf{w}}^{\mathbf{o}\mathbf{2}\mathbf{e},\mathbf{I}},{\mathbf{w}}^{\mathbf{e}\mathbf{2}\mathbf{o},\mathbf{I}}\}.$ When all weights are set to 1, the neural BP/min-sum turns back to the original BP/min-sum algorithm.

To measure the difference between the output of network and the true codeword, we used the multiloss binary cross-entropy (BCE). Given iterations of I and code length of n, the neural network yielded output $\mathbf{O}=({\mathbf{O}}^{\mathbf{1}},{\mathbf{O}}^{\mathbf{2}},\cdots ,{\mathbf{O}}^{\mathbf{I}})$, where ${\mathbf{O}}^{\mathbf{i}}=(O_1^i,O_2^i,\cdots ,O_n^i)$ and $1\le i\le I$. The multiloss BCE between the true codeword $\mathbf{u}$ and the outputs $\mathbf{O}$ was calculated and accounted for the total loss after every BP/min-sum iteration as follows:

$$L(\mathbf{O},\mathbf{u})=\frac{1}{I·n}\sum _{j=1}^I\sum _{i=1}^n{u}_i\ln \left(O_i^j\right)+(1-u_i)\ln (1-O_i^j).$$

(11)

4. Cyclic mRRD

Trapping sets of small sizes can greatly influence the performance of BP or min-sum algorithms as shown in Figure 4. The trapping sets were found by using the algorithm proposed in [24]. Figure 4 and Figure 5 show that the distribution of errors are more similar to the distribution of trapping sets rather than 4-cycles. That means trapping sets can also greatly affect the BP/min-sum performance for QR codes at high SNR such as LDPC codes, and the effect of short cycles become less important. Referring to Figure 1, the mRRD chooses and applies a random permutation from $\mathrm{Per}\left(C\right)$ before each BP/min-sum decoder, which is equivalent to using a different parity check matrix for each BP/min-sum decoder. By permuting LLRs to other positions, the mRRD prevents nodes from receiving messages from the same group of neighboring nodes in the trapping sets or cycles and a falsely converged variable node may be corrected by the other nodes after the next BP decoder.

As we have analyzed before, $\mathrm{Per}\left(C\right)$ contains not only the cyclic shift, but also many other permutations for a cyclic code. The order of permutation groups for different QR codes are listed in

Table 1. The order of permutation groups for each QR code.

Codes	(23,12)	(31,16)	(47,24)	(71,36)
$\left|\mathrm{Per}\right(C\left)\right|$	10,200,960	465	1081	2485
Codes	(73,37)	(79,40)	(89,45)	(97,49)
$\left|\mathrm{Per}\right(C\left)\right|$	2628	3081	3916	4656

. We notice that the order of the permutation group of the (23,12) QR code is significantly larger than the others. That is because the permutation group of the (24,12) extended QR code contains two distinct groups of projective special linear (PSL) type, while the permutation groups of most other codes contain only one [25]. Furthermore, the permutation group of the original code is composed by permutations which fix the overall check bit in the permutation group of the extended code.

Each permutation can be stored as a one-dimensional array using Cauchy’s two-line notation with the first line omitted. However, it still requires much memory to store those permutations. Alternatively, we can store the group generators only, which brings additional overheads at runtime to compute the composition of permutations. Furthermore, the implementation of a random permutation on circuits is complex when LLRs can be shuffled to any position. As a result, it needs multiple random swaps between LLR values to perform a single random permutation. Otherwise, we need a more complex design in order to shuffle LLRs in one step.

Cyclic shifts are easier to be implemented in hardware than random permutations. By shifting LLRs to their neighboring positions in a loop, any length of shift permutation can be easily implemented and rapidly performed. By using the same cyclic shift every time, the complexity of the implementation can be further reduced. Considering the above analysis, we can first compute the trapping set distribution ${\mathbf{D}}_{\mathbf{T}}=[t_1,t_2,\cdots ,t_n]$, where $t_i$ is the number of trapping sets associated with node $V_i$. Then, we select a cyclic shift based on the distribution, that is, the bits associated with large numbers of trapping sets will be moved to the positions with less trapping sets. It allows zero overhead during the decoding process. The criterion to select good shifts from all cyclic shift permutations is proposed as Algorithm 1. After performing the algorithm, we can select the cyclic shift which has the highest score. If the algorithm returns multiple shifts with the same score, we choose the shift $\sigma$ that has the least length (i.e., is closest to 0 or n). For example, suppose the algorithm returns 40 and 23 for the (47,24) QR code, implying that cyclic right shifts of 40 bits and 23 bits are both optimal. However, shifting right by 40 bits can be implemented as shifting left by 7, which is less than 23, so the final result is a cyclic shifting right by 40 bits.

Algorithm 1 Criterion to find the best shift

Input: Distribution of trapping sets: ${\mathbf{D}}_{\mathbf{T}}$      Output: The best shift: $\sigma$     for $i\leftarrow 1$ to n do        $\mathbf{x}\leftarrow {\mathbf{D}}_{\mathbf{T}}-({\mathbf{D}}_{\mathbf{T}}>>n)$ //Measure the change of the number of trapping sets for each bit.        $Score\left[i\right]\leftarrow {\sum }_{x_i>0}{x}_i$     end for     $S\leftarrow \left\{i\right|Socre\left[i\right]==\max \left(Score\right)\}$     if $\left|S\right|\ne 1$ then        $\sigma \leftarrow \underset{\sigma \in S}{\mathrm{argmax}}\left(\right|\sigma -\frac{n}{2}\left|\right)$     else        $\sigma \leftarrow S\left[1\right]$     end if

The proposed method replaces the first random permutation by a random cyclic shift for each pipeline to give every pipeline a different starting point. After that, all the other random permutations in the original mRRD are replaced by a fixed right shift permutation. Since all permutations are replaced by cyclic shifts, we call the new modified mRRD Cyclic-mRRD. The Cyclic-mRRD is given in detail as Algorithm 2.

Algorithm 2 Cyclic-mRRD

Input: Cyclic right shift: $\sigma$, parity check matrix: $\mathbf{H}$                  code length: n, LLR vector: $\mathsf{\gamma }$                  mRRD Size: $(W,L,I)$      Output: Decode results: $\widehat{\mathbf{u}}$     $S,F\leftarrow \varnothing$     for $i\leftarrow 1$ to W do         $\Sigma \leftarrow \mathrm{RandomInt}\left(\right)\mathrm{mod}n$         $\mathbf{w}\leftarrow \mathsf{\gamma }>>\Sigma$         for $j\leftarrow 1$ to L do              $\mathbf{w}\leftarrow I\mathrm{iterations}\mathrm{of}\mathrm{BP}/\min -\mathrm{sum}\left(\mathbf{w}\right)$              $\widehat{\mathbf{u}}\leftarrow \mathrm{HardDecision}(\mathbf{w})$              if $\widehat{\mathbf{u}}·{\mathbf{H}}^{\mathbf{T}}=0$ then                  $\widehat{\mathbf{u}}\leftarrow \widehat{\mathbf{u}}<<\Sigma$ //Rearrange bits to the original order                  $S\leftarrow S\cup \left\{\widehat{\mathbf{u}}\right\}$ //Append $\widehat{\mathbf{u}}$ to success set                  break               else                  $\mathbf{w}\leftarrow \mathbf{w}>>\sigma$                 $\Sigma \leftarrow (\Sigma +\sigma )\mathrm{mod}n$ //Record total shifted bits               end if         end for         $\Sigma \leftarrow (\Sigma -\sigma )\mathrm{mod}n$         $\widehat{\mathbf{u}}\leftarrow \widehat{\mathbf{u}}<<\Sigma$ //Rearrange bits to the original order         $F\leftarrow F\cup \left\{\widehat{\mathbf{u}}\right\}$ //Append $\widehat{\mathbf{u}}$ to default set     end for     if $\left|S\right|=0$ then         $S\leftarrow F$ //No valid codewords, select from default set     end if     $\widehat{\mathbf{u}}\leftarrow \mathrm{LMS}(S)$

5. Simulation Results

The simulation and training were carried under BI-AWGN channels. All LLRs beyond $[-20,+20]$ were clipped to −20/+20. The training set contained ${10}^6$ vectors, which were all-zero codewords corrupted by random noises at $E_b/N_0$ = 3–5 dB, and the batch size was 200, whereas the BER and FER curves were obtained using randomly generated codewords and noises. We used the RMSProp optimizer in which the learning rate was set to 0.01. Other parameters were set to their default as per PyTorch’s implementation.

5.1. Neural BP/Min-Sum

We first demonstrate the neural network versions of the BP and TAMS algorithms. As illustrated in Figure 6, the neural network versions of the BP and TAMS algorithms both outperform the original BP/TAMS algorithm. The neural BP achieves a gain of 1.1 dB compared to BP when the BER is $2\times {10}^{-4}$. Neural TAMS has the best performance among these four decoders, and the gain is about 0.6 dB at a BER of $4\times {10}^{-5}$, when compared with the original TAMS algorithm. In addition, it has a relatively low complexity compared to the BP algorithm and neural BP. Therefore, we used neural TAMS as the default decoder in the following experiments.

Figure 7 shows the error distributions of the TAMS algorithm and neural TAMS. The errors were counted until more than 5000 bit errors occurred. Though a neural network can mitigate the effect of trapping sets, the mitigation is limited, especially for those nodes which are involved in many trapping sets. So the error occurrences of these nodes become more dominant in a high-SNR regime.

5.2. Neural mRRD/Neural Cyclic-mRRD

Figure 8, Figure 9, Figure 10 and Figure 11 show the comparison on error performances of neural mRRD (5,10,5) and neural Cyclic-mRRD (5,10,5). The results were calculated after 100 frames errors had occurred and more than 1000 frames had been processed. The cyclic shifts were selected by using Algorithm 1 with trapping sets satisfying $a+b<7\mathrm{and}a<4$.

Referring to Figure 8, for the (47,24) QR code, the neural mRRD achieved a gain of 0.5 dB at BER $=4\times {10}^{-6}$, compared with the DS algorithm. The neural Cyclic-mRRD had a slight loss of performance, which was about 0.08 dB at BER $={10}^{-6}$, compared to neural mRRD, which randomly chooses permutations from the whole group. The selected cyclic right shift length was 22 based on Algorithm 1. We also observed that the FER of neural Cyclic-mRRD was lower than DS at all SNRs. However, at very low SNR, each incorrect mRRD/Cyclic-mRRD frame introduced additional bit errors compared to the DS algorithm.

Figure 9 shows the FER/BER performance of the neural mRRD and neural Cyclic-mRRD on the (71,36) QR code. The neural mRRD obtained a gain of about 1.0 dB at BER $=2\times {10}^{-5}$ compared to the DS algorithm. The selected cyclic shift for neural Cyclic-mRRD was a right shift of 36, and the loss of performance compared to the neural mRRD was about 0.3 dB at BER $={10}^{-6}$.

Figure 10 shows the FER/BER performance of the neural mRRD and neural Cyclic-mRRD on the (73,37) QR code. The neural mRRD obtained a gain of about 0.5 dB at BER $=3\times {10}^{-6}$ compared to the DS algorithm. The selected cyclic shift for neural Cyclic-mRRD was a right shift of 31 bits. The performance loss compared to the neural mRRD was about 0.1 dB at BER $={10}^{-6}$.

Figure 11 shows the FER/BER performance of the neural mRRD and neural Cyclic-mRRD on the (97,49) QR code. The neural mRRD obtained a gain of about 0.4 dB improvement at BER $=2\times {10}^{-6}$ compared to the DS algorithm. The selected cyclic shift for neural Cyclic-mRRD was a right shift of 31 bits. The performance loss compared to the neural mRRD was about 0.04 dB at BER $={10}^{-6}$.

5.3. Longer QR Codes

Note that we used a different set of hyperparameters to train the neural network for QR codes with code length more than 200. The training set contained $2\times {10}^6$ vectors which were corrupted by noises with SNR varying from 1 to 8 dB. The learning rate was set to 0.001, and the other hyperparameters remained the same. Furthermore, we used an ordinary BCE loss function instead of a multiloss BCE. We could not obtain the performance of the DS algorithm because the minimum distances of long QR codes are still unknown, and the complexity of the DS algorithm is very high for long QR codes. Neural TAMS and TAMS applied five iterations and Cyclic-mRRD’s size was (5,10,5). Figure 12 shows the BER/FER performance of the neural mRRD and neural Cyclic-mRRD on the (241,121) QR code. The cyclic shift for neural Cyclic-mRRD was a right shift of 191 bits, which was selected by using trapping sets with $a\le 4$ and $a+b<8$.

Figure 13 shows the BER/FER performance of the neural mRRD and neural Cyclic-mRRD on the (263,132) QR code. The cyclic shift was a right shift of 232 bits, which was selected by using trapping sets with $a\le 5$ and $a+b<8$.

5.4. Complexity Analysis

The proposed Cyclic-mRRD method employs multiple BP/min-sum decoders and more multiplications on every iteration. However, most of them can run in parallel. Assume the number of edges in a Tanner graph is e. Each neural BP/min-sum iteration needs on average $2e$ more multiplications than the original BP/min-sum iteration. However, the latency nearly remained the same because different nodes can process incoming messages simultaneously.

For the Cyclic-mRRD $(W,L,I)$, it needs $W\times L\times I$ BP/min-sum iterations in the worst case, and $W\times I$ iterations for the best case, because there are only I iterations to be performed for each pipeline in the best case. Considering that there are no data dependencies among different pipelines, W pipelines can decode the different shifted inputs at the same time. Then, the latency in the worst case reduces to $L\times I$ iterations and I iterations for the best case. For our Cyclic-mRRD (5,10,5), the latency in parallel was 50 iterations in the worst case and 5 iterations in the best case.

It is hard to analyze the average complexity of the above decoders. Thus, the average time complexity at different SNRs was obtained by computing the average iterations needed to converge using 10,000 random frames, as shown in

Table 2. Average complexity on the (47,24) QR code.

SNR	0	1	2	3	4	5	6	7
Iterations (serial)	219.9	191.3	144.8	89.9	49.8	30.9	25.7	25.0
Iterations (parallel)	48.4	45.3	38.3	27.1	15.5	8.1	5.5	5.0

. The legend “serial” means the sum of the number of min-sum iterations from all pipelines, and “parallel” denotes the largest number of iterations among all pipelines. The average serial/parallel iterations were calculated by summing up all iterations for each pipeline and divided by the number of codewords, which represents the time complexity when all pipelines run in serial. We can see that the average complexity of neural Cyclic-mRRD nearly achieved the best complexity at $E_b/N_0\ge 6$ (about 25 iterations in serial and 5 iterations in parallel), and the worst complexity at $E_b/N_0=0$ (about 220 iterations in serial and 48 iterations in parallel).

6. Conclusions

In this paper, we proposed several neural-network-based methods to decode binary QR codes. We observed that the performance of the BP/min-sum algorithm was mainly affected by a small part of trapping sets, even though there were a huge number of four-cycles in the parity check matrix of QR codes. Based on this phenomenon, the proposed Cyclic-mRRD moved the nodes out from the trapping sets by using cyclic shifts. The simplification achieved similar performance as mRRD, while reducing the complexity of implementation and memory usage. Both the mRRD and Cyclic-mRRD outperformed the DS algorithm in terms of BER/FER performance, with less asymptotic time complexity.

Finally, we obtained the BER/FER performance of two longer QR codes using the proposed Cyclic-mRRD, though their error performances could not be determined without knowing their minimum distances.

Our future work will include approaching ML performance for longer QR codes with less or the same complexity. Furthermore, there are some possible improvements on the neural network, including training, data quantization and trapping set issues.