Neural-Network-Assisted Polar Code Decoding Schemes

Abstract

The traditional fast successive-cancellation (SC) decoding algorithm can effectively reduce the decoding steps, but the decoding adopts a sub-optimal algorithm, so it cannot improve the bit error performance. In order to improve the bit error performance while maintaining low decoding steps, we introduce a neural network subcode that can achieve optimal decoding performance and combine it with the traditional fast SC decoding algorithm. While exploring how to combine neural network node (NNN) with R1, R0, single-parity checks (SPC), and Rep, we find that the decoding failed sometimes when the NNN was not the last subcode. To solve the problem, we propose two neural network-assisted decoding schemes: a key-bit-based subcode NN-assisted decoding (KSNNAD) scheme and a last subcode NN-assisted decoding (LSNNAD) scheme. The LSNNAD scheme recognizes the last subcode as an NNN, and the NNN with nearly optimal decoding performance gives rise to some performance improvements. To further improve performance, the KSNNAD scheme recognizes the subcode with a key bit as an NNN and changes the training data and label accordingly. Computer simulation results confirm that the two schemes can effectively reduce the decoding steps, and their bit error rates (BERs) are lower than those of the successive-cancellation decoder (SCD).

1. Introduction

To reduce interference in the communication process and enable the system to automatically check and correct errors to improve the reliability of data transmission, channel coding technology is widely used in various wireless communication systems. Currently, commonly used coding techniques include Reed–Solomon (RS) codes [1], low-density parity-check (LDPC) codes [2,3], turbo codes [4,5], Bose–Chaudhuri–Hocquenghem codes [6,7,8], convolutional codes [9], and polar codes [10]. Polar codes have been strictly proven to reach the Shannon limit under the binary discrete memoryless channel and binary erasure channel when the code length tends to infinity [11], and due to their excellent short-code performance, they became the control channel selection coding scheme for 5G enhanced mobile broadband scenarios at the 2016 3GPP RAN1#87 conference [12]. As the only channel coding that has been proven to reach the Shannon limit, polar codes are very important for 5G communication and future 6G communication. In the field of wireless communication, the decoding of polar codes has received extensive attention globally. Examples are the traditional belief propagation (BP) algorithm [13], the successive-cancelation (SC) algorithm [14], the early stop BP algorithm [15], other low complexity BP algorithms [16], the fast SC decoding scheme [17,18,19], and successive cancellation stack [20]. These traditional algorithms and their improvements can only reduce the decoding complexity or improve the decoding performance but cannot satisfy the requirements of improving communication quality and reducing decoding steps at the same time.

In recent years, the rapid development of deep learning in computer vision and language translation has attracted widespread attention from experts and scholars in the field of communication. Some algorithms directly train deep learning as a polar decoder, Chao, Z.W. et al. explored a polar code residual network decoder with a denoiser and a decoder. The denoiser used a multi-layer perceptron (MLP) [21], a convolutional neural network (CNN) [22], and a recurrent neural network (RNN) [23], while the decoder used a CNN [24]. The decoding performances nearly reached those of a traditional successive cancelation list (SCL) [25] algorithm when the code length was less than 32. In terms of reducing decoding complexity, Xu, W.H. et al. applied a neural network to polar code decoding, but the application was only used for limited code length [26]. Hashemi, S. et al. used the deep learning algorithm to reduce the complexity of the SC algorithm [27]. However, all of them cannot be directly applied to decoding longer polar codes. To apply the machine learning in polar code decoding, researchers combine machine learning with traditional polar decoding algorithms.

There are many combinations of BP algorithm and machine learning. In terms of reducing the complexity, Gruber, T. et al. proposed a neural network BP decoder that can be executed at any code length, which reduced the decoding bit error rate (BER) and saved 50% of the hardware cost [28]. Cammerer, S. et al. proposed a segmentation decoding scheme based on neural networks, which complied with the BP decoding law and divided polar codes into single-parity checks (SPCs) and repetition code (RC) nodes and decoded them using a neural network to achieve the same bit error performance as the SC and BP algorithms with lower complexity [29]. In terms of improving decoding performance, Teng, C.F. et al. used the check relationship between the cyclic redundancy check (CRC) remainder and the decoding result to propose a comprehensive loss function of polar code frozen bits, which realized the unsupervised decoding of the polar codes, and the decoding performance was better than that of the traditional BP decoding algorithm [30]. Gao, J. et al. proposed a BP structure similar to the res-net network, which achieved better decoding performance than the standard BP algorithm [31]. In terms of simultaneously improving decoding performance and reducing complexity, Xu, W. et al. used deep learning to improve the decoding performance of the BP algorithm and used lower computational complexity to achieve a bit error performance close to that of the CRC-aided SCL (CA-SCL) algorithm [32].

The SC algorithm and machine learning are less frequently combined. Doan, D. et al. divided the polar code into equal-length nodes and decoded them using neural networks [33] and obtained a lower complexity than [29]. However, when the code length is longer, the number of neural network models that need to be called for decoding is higher, and the increase in the calculation amount is not negligible. None of the above studies have achieved a low-complexity low-bit-error decoding performance by combining the SC algorithm and machine learning.

To achieve a low-complexity low-bit-error decoding performance by combining SC algorithm and machine learning, this paper proposes a decoding method combining neural network nodes (NNNs) and traditional nodes. This scheme avoids the extra complexity caused by frequent calls of the neural network model and proposes a decoding scheme that can not only reduce the delay, but also improve the decoding performance.

The remainder of this paper is organized as follows: Section 2 introduces the knowledge required for polar code decoding, including the SC decoding scheme, traditional special nodes, and the fast SC decoding scheme. Section 3 introduces the system model and the decoding scheme based on the NNN and CNN structure and then analyzes the performance of the model in decoding. Two NNN recognition strategies are explored. Section 4 presents the simulation results over the additive white Gaussian noise (AWGN) and Rayleigh channel. Section 5 summarizes the paper.

2. Preliminaries

2.1. SC Decoding Algorithm

A polar code $(x_1,x_2,\cdots ,x_N)$ with length $N=2^n$ can be encoded by $(x_1,x_2,\cdots ,x_N)=(u_1,u_2,\cdots ,u_N){\mathbf{F}}^{\otimes n}$, $\mathbf{F}=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]$, $\otimes$ is Kronecker operation. Consider two independent and identically distributed random variables $u_1$ and $u_2$, which are encoded by polar codes:

$$(x_1,x_2)=(u_1,u_2)\mathbf{F}=(u_1,u_2)\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]=(u_1\oplus u_2,u_2).$$

(1)

Obviously, at this time, $N=2$, $n=1$. As shown in Figure 1, $(x_1,x_2)$ passes through a binary discrete memoryless channel (BDMC) with transition probability $W(y|x)$. Then, the received signal $(y_1,y_2)$ is obtained, but we always use its log likelihood ratio (LLR) $(L_1,L_2)$. The process of solving $(u_1,u_2)$ from $(L_1,L_2)$ is the decoding process.

As shown in Figure 1, we solve $u_1$ using the $u_1=f(L_1,L_2)$ operation, and solve $u_2$ using the $u_2=g(u_1,L_1,L_2)$ operation; indeed, $f$ operation and $g$ operation are conditional probabilities. Specifically, we solve $u_1=0$ when $\frac{\mathrm{Pr}(y_1{y}_2|u_1=0)}{\mathrm{Pr}(y_1{y}_2|u_1=1)}\ge 0$; otherwise, $u_1=1$.

$$\begin{array}{ll}\mathrm{Pr}(y_1{y}_2|u_1)& =\frac{\mathrm{Pr}(y_1{y}_2{u}_1)}{\mathrm{Pr}(u_1)}=\frac{{\displaystyle \sum {}_{u_2\in \{0,1\}}\mathrm{Pr}(y_1{y}_2{u}_1{u}_2)}}{\mathrm{Pr}(u_1)}\\ & =\frac{{\displaystyle \sum {}_{u_2\in \{0,1\}}\mathrm{Pr}(y_1{y}_2|u_1{u}_2)\mathrm{Pr}(u_1{u}_2)}}{\mathrm{Pr}(u_1)}\\ & \stackrel{(a)}{=}\frac{1}{2}{\displaystyle \sum {}_{u_2\in \{0,1\}}\mathrm{Pr}(y_1{y}_2|x_1{x}_2)}\\ & \stackrel{(b)}{=}\frac{1}{2}{\displaystyle \sum {}_{u_2\in \{0,1\}}\mathrm{Pr}(y_1|x_1)\mathrm{Pr}(y_2|x_2)}\\ & =\frac{1}{2}{\displaystyle \sum {}_{u_2\in \{0,1\}}\mathrm{Pr}(y_1|u_1\oplus u_2)\mathrm{Pr}(y_2|u_2)}\end{array}$$

(2)

where $(a)$ means $\mathrm{Pr}(u_1)=0.5$; $\mathrm{Pr}(u_1{u}_2)=0.25$; $(b)$ means $W$ is a BDMC.

$$\begin{array}{ll}\ln \frac{\mathrm{Pr}(y_1{y}_2|u_1=0)}{\mathrm{Pr}(y_1{y}_2|u_1=1)}& =\ln \frac{{\displaystyle \sum {}_{u_2\in \{0,1\}}\mathrm{Pr}(y_1|u_2)\mathrm{Pr}(y_2|u_2)}}{{\displaystyle \sum {}_{u_2\in \{0,1\}}\mathrm{Pr}(y_1|1\oplus u_2)\mathrm{Pr}(y_2|u_2)}}\\ & =\ln \frac{\mathrm{Pr}(y_1|0)\mathrm{Pr}(y_2|0)+\mathrm{Pr}(y_1|1)\mathrm{Pr}(y_2|1)}{\mathrm{Pr}(y_1|1)\mathrm{Pr}(y_2|0)+\mathrm{Pr}(y_1|0)\mathrm{Pr}(y_2|1)}\\ & =\ln \frac{\frac{\mathrm{Pr}(y_1|0)\mathrm{Pr}(y_2|0)}{\mathrm{Pr}(y_1|1)\mathrm{Pr}(y_2|0)}+1}{\frac{\mathrm{Pr}(y_2|0)}{\mathrm{Pr}(y_2|1)}+\frac{\mathrm{Pr}(y_1|0)}{\mathrm{Pr}(y_1|1)}}=\ln \frac{1+e^{L_1+L_2}}{e^{L_1}+e^{L_2}}\end{array}$$

(3)

where $L_1=\ln \frac{\mathrm{Pr}(y_1|0)}{\mathrm{Pr}(y_1|1)}$ and $L_2=\ln \frac{\mathrm{Pr}(y_2|0)}{\mathrm{Pr}(y_2|1)}$ are the LLRs of the received signal. Equation (3) is called the $f$ operation, which is commonly estimated as follows:

$$\ln \frac{1+e^{L_1+L_2}}{e^{L_1}+e^{L_2}}\approx \mathrm{sign}(L_1)\mathrm{sign}(L_2)\min \{\left|L_1\right|,\left|L_2\right|\},$$

(4)

where $\mathrm{sign}(-a)=-1$; $\mathrm{sign}(a)=1$; $a>0$; $\min$ indicates taking the minimum value.

$U_2=0$ if $\ln \frac{\mathrm{Pr}(y_1{y}_2{u}_1|u_2=0)}{\mathrm{Pr}(y_1{y}_2{u}_1|u_2=1)}\ge 0$, where

$$\begin{array}{ll}\mathrm{Pr}(y_1{y}_2{u}_1|u_2)& =\frac{\mathrm{Pr}(y_1{y}_2{u}_1{u}_2)}{\mathrm{Pr}(u_2)}=\frac{\mathrm{Pr}(y_1{y}_2|u_1{u}_2)\mathrm{Pr}(u_1{u}_2)}{\mathrm{Pr}(u_1)}\\ & =\frac{1}{2}\mathrm{Pr}(y_1{y}_2|u_1{u}_2)=\frac{1}{2}\mathrm{Pr}(y_1{y}_2|x_1{x}_2)\\ & =\frac{1}{2}\mathrm{Pr}(y_1|x_1)\mathrm{Pr}(y_2|x_2)\\ & =\frac{1}{2}\mathrm{Pr}(y_1|u_1\oplus u_2)\mathrm{Pr}(y_2|u_2)\end{array}$$

(5)

The same can be obtained as follows:

$$\begin{array}{ll}\ln \frac{\mathrm{Pr}(y_1{y}_2{u}_1|u_2=0)}{\mathrm{Pr}(y_1{y}_2{u}_1|u_2=1)}& =\ln \frac{\mathrm{Pr}(y_1|u_1)\mathrm{Pr}(y_2|0)}{\mathrm{Pr}(y_1|1\oplus u_1)\mathrm{Pr}(y_2|1)}\\ & =\ln \frac{\mathrm{Pr}(y_1|u_1)}{\mathrm{Pr}(y_1|1\oplus u_1)}+\ln \mathrm{Pr}(y_2|0)\mathrm{Pr}(y_2|1)\\ & =(1-2u_1)L_1+L_2\end{array}$$

(6)

Equation (6) is called the $g$ calculation. We use a tree diagram to represent the decoding process of Figure 1, which is more intuitive.

As shown in Figure 2, the circles represent nodes; the upper node is the root node; and the lower two nodes are leaf nodes. After the root node calculates the LLR of the data, $u_1$ is obtained using $u_1=f(L_1,L_2)$ operation. Then, it returns the result to the root node. After that, $u_2$ is obtained using the $u_2=g(u_1,L_1,L_2)$ operation, and then, $u_2$ is returned to the root node to finally obtain the decoding results. When the code length is 4, the decoding diagram is as shown in Figure 3.

As shown in Figure 3, the polar code of length 4 can be divided into three basic units: the red solid line block diagram in the lower left corner, the red dotted line block diagram in the lower right corner, and the blue dot-dash line block diagram above. According to the algorithm in Figure 2, nodes $u_1$, $u_2$, 1, $u_3$, $u_4$, 3 and 1 are calculated sequentially, and the calculation function is marked next to the line. Any polar code with a code length of $N=2^n$ can perform SC decoding in sequence according to this rule, where $n$ is a positive integer. However, the frozen bit transmission information is fixed and does not need to be decoded. Therefore, in order to reduce the amount of calculation in the actual execution process, the frozen bit part is not included in the recursive calculation. Let white circles denote nodes that contain only frozen bits, black circles denote nodes that contain only information bits, and gray circles denote nodes with both frozen bits and information bits. Unless otherwise specified, the meanings of the nodes in this paper are the same as above. A polar code with a code length of $N=32$ and information bit length $K=16$ constructed through the Gaussian approximation (GA) method is used, and the signal-to-noise ratio is 2.5 dB. Then, the polar code tree diagram is as shown in Figure 4. We usually measure the decoding time complexity by decoding steps. The decoding steps are calculating by adding the numbers of operation $f$, operation $g$ and data return. As shown in Figure 4, the downward solid arrow with solid line represents the $f$ operation; the downward non-solid arrow with chain line represents the $g$ operation; the upward solid arrow with dotted line represents the direction of data return, which is calculated through (1). The serial numbers in the figure record the counting process of decoding time step. The total number of decoding step is 81. Note that the R0 does not need a data return. Unless otherwise specified, the meanings of the arrows in this paper are the same as above.

2.2. Decoding of Traditional Special Nodes

This section introduces four special nodes: R0 node, R1 node, Rep node, and SPC node, which are distinguished by the positions of the frozen bits and information bits. A node that has all frozen bits is an R0 node; a node that has all information bits is an R1 node; a node that has only one information bit at the last bit position is a Rep node; a node that has only one frozen bit at the first bit position is an SPC node. Assuming that a polar code $s_1^{N_S}=(s_1,s_2,\cdots ,s_{N_S}),s_i\in \{0,1\}$ with length $N_S$ is transmitted, after the BDMC with transition probability $\mathrm{Pr}(y|s),s\in \{0,1\}$, the received signal $y=(y_1,y_2,\cdots ,y_{N_S})$ is chosen to obtain the sequence $({\beta }_1,{\beta }_2,\cdots {\beta }_{N_S})$, where

$${\beta }_i=(1-sign(\ln \frac{\mathrm{Pr}(y_i|0)}{\mathrm{Pr}(y_i|1)}))/2,$$

(7)

If the node is R1, $({\beta }_1,{\beta }_2,\cdots {\beta }_{N_S})$ is its fast decoding result. If the node is R0, there is no need to decode. The decoding method of the Rep node and SPC node are as follows.

2.2.1. Fast Decoding of a Rep Node

The log-likelihood ratio (LLR) sum of a Rep node with a code length of $N_S$ can be calculated as follows:

$$S_q={\displaystyle \sum _{i=1}^{N_S}\ln \frac{\mathrm{Pr}(y_i|0)}{\mathrm{Pr}(y_i|1)}},$$

(8)

where $S_q$ is the LLR sum and $\mathrm{Pr}$ denotes probability. The decoding result of Rep is 0 when $S_q\ge 0$ and 1 otherwise.

2.2.2. Fast Decoding of an SPC Node

For an SPC node with a code length of $N_S$, if ${\displaystyle {\sum }_{i=1}^{N_S}{\beta }_i}=0$, $({\beta }_1,{\beta }_2,\cdots {\beta }_{N_S})$ is its decoding result. Otherwise, find ${\beta }_p$, which is the smallest absolute LLR of $({\beta }_1,{\beta }_2,\cdots {\beta }_{N_S})$. Let ${\beta }_p=1-{\beta }_p$. Then, $({\beta }_1,{\beta }_2,\cdots {\beta }_{N_S})$ is the decoding result.

2.3. Traditional Fast SC Decoding

When we recognize a polar code with length $N$ to a string of subcodes, we first judge if the whole polar code can be recognized as a subcode; if not, we will judge the former, and the latter $N/2$ polar code can be recognized as a subcode. If so, the recognition stops, and if not, we divide the $N/2$ polar code by the $N/4$ polar code and continue the recognition, until the original is totally recognized as subcodes. When decoding a polar code with a code length of 32, as discussed in Section 2.1, the polar codes are first recognized as special nodes, as shown in Figure 5.

After node recognition, the nodes are decoded as discussed in Section 2.2. The decoding sequence is the same as that in Section 2.1.

The decoding process is shown in Figure 6. Though the traditional fast SC decoding costs 19 decoding steps which is much lower than SC decoding, it cannot improve the bit-error performance. Maintaining the low time step of the fast SC algorithm while improving the bit-error performance is the goal of the algorithm in this paper.

3. Neural Network-Assisted Polar Code Decoding Scheme

Considering that the traditional fast SC decoding algorithm can effectively reduce the decoding time step, in this paper, we will reduce the BER of fast SC decoding structure. Xu Xiang studied the decoding performance of the polar code neural network decoder based on CNNs, RNNs, long short-term memory, and MLP under different network designs and parameter settings [34]. In comparison, it can be seen that the CNN-based decoder can achieve a better performance with fewer parameters. Therefore, we consider using the CNN to improve the decoding performance and call the scheme neural network assisted (NNA) decoding scheme.

3.1. System Model

Figure 7 shows the block diagram of the proposed decoding scheme system, which is composed of training and decoding parts. The “Training Part” is executed first, followed by the “Decoding Part”. The Training Part is composed of “Polar Encoder1” and “Neural Network Training”; the Decoding Part comprises “Polar Encoder2”, “Mapper”, “Noise”, and “NNA Decoding Scheme”. Note that the Mapper Layer, Noise Layer, and Decoder Layer are trained in the training part, but only the model of the Decoder Layer is saved and called in NNA Decoding. Although the decoder layer decodes ${\dot{y}}_1^{N_S}$ to obtain ${\widehat{\dot{u}}}_1^{N_S}$, the purpose of the training part is to obtain the trained Decoder Layer model and not the ${\widehat{\dot{u}}}_1^{N_S}$.$N_S$ and $K_S$ denote the code length and information length of the codewords to be trained, respectively, while $N$ and $K$ denote the code length and information length of the codewords to be decoded, respectively. $u_1^N$ denotes a row vector $(u_1,\cdots ,u_N)$. The two parts have different inputs, ${\dot{u}}_1^{N_S}$ and $u_1^N$, and different diagram structures, but ${\dot{u}}_1^{N_S}\mapsto {\dot{y}}_1^{N_S}$ and $u_1^N\mapsto y_1^N$ are mapped in the same way. Taking $u_1^N\mapsto y_1^N$ as an example, consider single-carrier signaling in which $N$ binary streams $u_1^N$ are encoded with a channel encoder that generates a codeword of length $N$. The codeword $x_1^N$ is then mapped to binary phase-shift keying (BPSK) symbols $s_1^N$ by the mapper. Then, $s_1^N$ is transmitted over noisy channels by the noise block, and finally, the signal $y_1^N$ is received. When the channel noise is additive gaussian white noise (AWGN), $y_1^N$ is given by $y_1^N=s_1^N+n_w$, $n_w~N(0,{\sigma }_w^2)$. Similarly, ${\dot{y}}_1^{N_S}$ can be obtained from ${\dot{u}}_1^{N_S}$. Note that ${\dot{u}}_1^{N_S}$ is determined by the Node Recognizer. We can obtain the LLR values through $2y_1^N/{\sigma }_w^2$, where ${\sigma }_w^2$ denotes Gaussian noise power. In this paper, the channel-side information is assumed to be known at the receiver. The details of the neural network (NN) model and decoding scheme are introduced in the following section.

3.2. Neural Network Model and NNN

The NN model is trained by the training part in Figure 7. We write matrix $\dot{U}$ with size $2^{K_S}\times K_S$ to denote all the possible information sequences and matrix $\dot{X}$ with size $2^{K_S}\times N_S$ to denote all the possible codewords, resulting in, ${\dot{x}}_1^{N_S}\in \dot{X}$. Let $A$ denote the position set of the information bits. The decoder layer is trained to find the ${\dot{u}}_1^{K_S}$ corresponding to ${\dot{y}}_1^{N_S}$, with ${\dot{u}}_1^{K_S}\in \dot{U}$. To fully train the NN, additional layers without trainable parameters are added to perform certain actions, namely mapping the codewords to BPSK symbols and adding noise. Therefore, the NN model approximates ${\dot{x}}_1^{N_S}$ to ${\dot{u}}_1^{K_S}$. Therefore, $\dot{X}$ represents the training data in this machine learning problem and $\dot{U}$ is the label. We can generate as much training data as desired by Monte Carlo simulations. The activation functions used in the decoder layer are sigmoid functions and a rectified linear unit (ReLU), which are defined as follows:

$$g_{sigmoid}(z)=\frac{1}{1+e^{-z}},$$

(9)

$$g_{\mathrm{Re}LU}(z)=\max \{0,z\}.$$

(10)

Mini-batch gradient descent is used to train the NN, and in each batch, different data are fed into the NN.

Table 1. The structure of the NN.

Layer	Output Dimensions	Convolutional Filters	Activation Function
Input	N	/	/
Mapper (Lambda)	N	/	/
Noise (Lambda)	N	/	/
NN Layer 1	16KS	128	ReLU
NN Layer 2	8KS	64	ReLU
NN Layer 3	4KS	32	ReLU
Output	KS	/	Sigmoid

summarizes the architecture of the proposed NN model. In this scheme, the batch size, which is equal to the size of the label set and that of the codeword set, is $2^{K_S}$. Thus, the training complexity scales exponentially with $K_S$, which makes training the NN decoder for long polar codes not feasible in actuality. To solve this problem, we define the short codes ($N_S$ is generally less than 32) decoded by the NN decoder as NNNs and combine them with the traditional special nodes mentioned in Section 2.2 to derive an NNA decoding scheme. Note that an NNN could be one of the R1, R0, Rep, or SPC nodes, or none of them. Arıkan’s system polar code coding scheme [35] is used in this paper unless otherwise stated.

The neural network structure in this paper consists of a mapper layer, a noise layer, and a decoding layer. All three layers need to be trained. In real-life decoding, only the decoding layer is needed. The structure of the NN is shown in Table 1. The mapper layer and the noise layer are both custom-function layers generated by the Keras tool in Tensorfow2. In this paper, Gaussian white noise is used unless otherwise stated; the Gaussian construction method is used to generate polar codes; the modulation method is BPSK. The input of the network during training is $\dot{X}$. The label is $\dot{U}$. Each round of training adds different noises, i.e., the data of each round of training are different from each other to prevent overfitting.

A trained CNN can classify the received signal, find the corresponding information sequence, and finally decode the polar code. A well-trained neural network can achieve the performance of MAP decoding [26]. The decoding results of the NNN with $N_S=16$ and $K_S=4$ are shown in Figure 8.

As shown in Figure 8, NNN decoding performance is better than SC algorithm, almost the same as the optimal MAP decoding algorithm, while the traditional fast decoding adopts a suboptimal decoding algorithm, and its decoding performance is similar to SC. Therefore, using well-trained CNN to decode subcodes can obtain better decoding performance than traditional classified subcodes.

3.3. Neural Network-Assisted (NNA) Decoding

The NNA decoding scheme is composed of a node recognizer and a decoder. The former recognizes the code as a concatenation of smaller constituent codes that were simply named nodes, which includes the NNN, and then the latter decodes these nodes. Note that the NNN is decoded by the trained model from the neural network model. Since the decoding scheme proposed in this paper is only for the receiving end, we use BER as the metric to measure the decoding performance. To avoid the computational complexity of the recursive structure of the successive-cancellation decoder (SCD), a vector of size $2\times N-1$ is used to store the intermediate calculation results of the SC decoding algorithm. The decoding error rate will decrease as the SNR increases, i.e., when a BER is $6\times {10}^{-7}$ at a lower signal noise rate (SNR), the BERs at higher SNRs with the same parameters are definitely lower than $6\times {10}^{-7}$. Let $6\times {10}^{-7}$ denote BER threshold. If a BER is lower than the threshold, it will not be displayed in the figures. Therefore, the calculations of higher SNRs with BERs lower than $6\times {10}^{-7}$ can be skipped to further improve the calculation speed.

To determine how to recognize the NNN, we must determine how it works. The progress of the signal process is shown in the training part of Figure 7. When $N=16$, $K$ ranges from 1 to 16. As shown in Figure 7 and as explained in Section 3.1, “Polar Encoder1” generates $2^{K_S}$ possible codewords of $N_S$ bits size in the training part. Considering the multiple possibilities of node recognition, we trained the polar code with $N_S=16$, $K_S=1-16$, with $N_S=8$, $K_S=1-8$, and with $N_S=4$, $K_S=1-4$ in epochs. The gradient of the loss function is calculated in each epoch using the Adam optimizer [36], and the trained model is finally saved to be used in the decoding part.

When only four kinds of traditional special nodes need to be identified, we first identify the polar code with the entire length of $N$ and judge whether the code is one of the above four kinds of nodes. If so, we directly perform maximum likelihood decoding. If not, we continue to identify the first half and the second half, and the above process is repeated until the original code is completely decomposed into nodes. Although the recognition process is a recursive process, this process is only performed once, and the computational complexity increase is limited. This method of transferring half of the original sequence into the recursive operation to identify the subcode is called dichotomy.

Assuming that the length of the NNN is 8, if we execute dichotomy, when the subcode with a code length of 8 does not belong to the four traditional special nodes mentioned before, it will be recognized as an NNN. In practice, the decoding performance will be greatly reduced in some cases. To find the reasons and explore a proper division method of the NNN, we recognized and decoded polar codes with a code length of 16 and information bit length 1–16. In this experiment, the codewords were constructed using the GA method. Taking polar codes with $N=16$ and $K=3$ as an example, we write R0(8) to denote an R-0 node with a code length of 8, SPC(4) to denote the SPC node with a code length of 4, and NNN(8/3) to denote an NNN with $N_S=8$ and $K_S=3$. When the code is recognized in the traditional way, the node-type structure is R0(8) + R0(4) + SPC(4) and the node can be recognized as R0(8) + NNN(8/3) by the node recognizer as well, that is, the NNN structure is R0(4) + SPC(4). Note that when $N_S=16$, the code can also be recognized as NNN(16/3).

We simulated multiple times and found that when the NNN is the last node of the original code, the decoding performance is always better than that of the traditional fast SC decoding algorithm. When an NNN is decoded as the non-last subcode, the polarization effect cannot be generated sometimes. This is because the information bits position determined by encoder 1 is different from the actual NNN determined by the recognizer. So, the decoding model is mismatched and errors are propagated in the decoding tree, resulting in decoding failure.

There are two ways to solve the abovementioned problems: one is to use an NNN as the last decoded subcode directly, and the other is to consider adapting the model and improving the correct probability of the first error, thus preventing the decoding error propagation. The two solutions lead to two decoding schemes, which are described below.

3.4. Last Subcode Neural Network-Assisted Decoding (LSNNAD) Scheme

Let $N_S$ denote the code length of the last subcode neural network node (LSNNN). The main idea of this scheme is to identify the last subcode as LSNNN. Note that at this time, LSNNN may be one of the four traditional subcodes mentioned above, or it may be different from the above four subcodes. The type, length, position, and order are determined at the moment when the codeword is constructed. In this experiment, 0 and 1 are used to represent the frozen bits and information bits, i.e., the sequence $information\_pos\in {\left\{0,1\right\}}^N$ of code length N is obtained after the codeword is constructed. When $information\_pos=1$, the information bits are stored. Otherwise, the frozen bits are stored. In this experiment, all frozen bits are 0. The LSNNN identification flowchart is shown in Figure 9.

The input $N$ is the same as in Figure 1. Let $D$ denote the position of bits and $A$, an arbitrary subset of $\{1,\cdots ,N\}$, denote the position of information bits. $I$ denotes the vector of the index, the initial content of which is in the range $0\mathrm{to}N-1$, and it represents the sequence position currently being processed. $I[0]$ denotes the first element of the vector $I$ and represents the starting position of the code being processed. $D$, $I$, and $N$ constantly change during the calculation process depicted in the flowchart (Figure 9). $D(0:N/2)$ denotes the first half of the vector $D$, $D(N/2:N)$ denotes the second half of the vector $D$, and $N_Z=N-N_S$ denotes the starting point of the NNN that is already fixed when the total code length and length of the NNN are determined. The output $Re$ is a matrix with five rows, with the first to the last rows denoting the node type, the starting point, $K$, $N$, and the information position of every node, respectively. In the node identification process, the decoding depth of each node is recorded, i.e., the node position in the SC decoding tree is recorded. The decoding tree after dividing the subcodes according to the above rules is shown in Figure 10.

3.5. Key-Bit-Based Subcode Neural Network-Assisted Decoding (KSNNAD) Scheme

Although the LSNNAD minimizes the loss of decoding errors caused by model mismatches, the performance improvement is limited. So, we must find another scheme to improve the decoding performance.

Ref. [37] analyzed the SC decoding error of polar codes and found that the first error is usually caused by channel noise, and the frequency of decoding failure caused by this error increases with the increase of code length. Ref. [38] analyzed and proved that when the polar code is divided into several R1 nodes, the first error in SC decoding of the polar code is likely to occur at the first information bit of the R1 nodes. Therefore, the decoding performance of the SC algorithm can be improved as long as the first error is correct. It can be seen from the above analysis that the first error is likely to occur at the first information bit position. This bit is defined as a key bit, and the node containing this bit is recognized as an NNN. In this scheme, all the NNNs are recorded and trained, and the models are saved to be called in the decoding part so that the model mismatched error is solved. Note that the label $\dot{U}$ is the decoding result whose key bit is flipped in the decoding process. So, the training part of the KSNNAD does not need a polar encoder.

The scheme is called a KSNNAD scheme, and the NNN is called the key bit based neural network node (KSNNN). We solve another problem: how to recognize a KSNNN.

The simplest idea of recognizing a KSNNN is to select the key bit as the first bit of the KSNNN. Assuming that the position is $Pos$ and the subcode length is $N_S$, the position of the last bit of the KSNNN is $Pos+N_S$. However, the dichotomy does not ensure that the key bit is the first position of the KSNNN; it may be the middle position. Next, we need to recognize a polar code with a KSNNN and the other four traditional subcodes mentioned above. Considering the complexity, the code length of KSNNN is limited to $N_S\le 16$. The identification flowchart is shown in Figure 11.

Taking the polar code with $N=32$, which is mentioned above as an example, the recognized result and decoding process are shown in Figure 12.

As shown in Figure 13, the time step required for decoding at this time is 12. The structure of the KSNNN is R0(8) + Rep(4) + SPC(4), compared with Figure 6. The structure of the original polar code is KSNNN(16) + Rep(4) + SPC(4) + R1(8). In the actual execution process, the subcode classification procedure is first executed. All possible forms of KSNNN are recorded. The key bit flip results corresponding to all possible situations of each specific form are trained as labels. Finally, the models are saved and called in the decoding part separately.

.

4. Numerical Simulation

This section simulates over the AWGN channel for Section 4.1, Section 4.2, Section 4.3 and Section 4.4. Section 4.5 is simulated over a Rayleigh channel. The SNR is expressed as $E_s/N_0$, where $E_s$ is the energy per symbol and $N_0$ is the single-sided noise power spectral density. We used Keras as the front end of the Tensorflow2 platform with an NVIDIA 3080 graphics card and Intel(R) Core(TM) i9 CPU to run the NN model, with the configuration given in Table 1. NNNs in Section 4.2, Section 4.3, Section 4.4 and Section 4.5 have the code length $N_S=16$. The polar code was constructed at 2.5 dB unless otherwise stated. Since the decoding scheme in this paper is proposed for the receiving end, the decoding performance is focused on the BER.

4.1. Performance with Different $N_S$

When simulated with a code length of 1024, a code rate of 0.5 and $N_S$ of 4, 8 and 16, the BER performance are shown in Figure 13. The BER curve of KSNNAD with $N_S$ 4 is marked as KSNNAD $N_S=4$, while LSNNAD with $N_S$ 4 marked as LSNNAD $N_S=4$, and so on.

As shown in Figure 13, combining NNN with R1, R0, SPC, and Rep can indeed improve decoding performance, but the improvement differs with different $N_S$ and different schemes. Both KSNNAD and LSNNAD have bit error performance improvement as $N_S$ increases and the longer the $N_S$, the smaller the improvement. KSNNAD outperforms LSNNAD due to performance boost at the key bit, regardless of the value of $N_S$.

4.2. Performance with Different Code Rates

When simulated with a code length of 1024 and code rate of 0.25, 0.5, and 0.75, the BER performance is shown in Figure 13. The BER curve of KSNNAD with code rate 0.25 is marked as KSNNAD K = 0.25, while LSNNAD with code rate 0.25 marked as LSNNAD K = 0.25, FSC decoding scheme with code rate 0.25 marked as FSCD K = 0.25, and so on.

As shown in Figure 14, both of the KSNNAD and LSNNAD have bit error performance improvement compared with SC and the lower the code rate, the better the improvement. When the code rate is 0.25, compared to SC decoder, LSNNAD needs 0.049 dB less to reach BER ${10}^{-4}$, while KSNNAD needs about 0.078 dB less.

4.3. Performance with Different Code Lengths

This section simulates the KSNNAD, LSNNAD and SC BER performance with a code rate of 0.5 and code lengths of 64, 128, 256, 512, and 1024. The results are shown in Figure 14. The BER curve of KSNNAD with a code length of 64 is marked as KSNNAD N = 64, while LSNNAD with a code length of 64 marked as LSNNAD N = 64, the FSC decoding scheme with code length 64 marked as FSCD N = 64, and so on.

As shown in Figure 15, the decoding performance of the KSNNAD and LSNNAD are better than that of the SC decoder. When the code length is 1024, compared to the SC decoder, LSNNAD needs 0.049 dB less to reach BER ${10}^{-4}$, while KSNNAD needs approximately 0.127 dB less.

4.4. Performance Comparison under AWGN Channel

This section simulates the BER performance comparison of different algorithms with a code length of $N=1024$ and a code rate of $R=0.5$. The BER performance of the LSNNAD and that of the KSNNAD are compared with those proposed in [17,19,25,33,39]. The simplified SC decoder proposed in [17] is marked as SSCD [17], the SCL decoder proposed in [25] with a list length of 2 is marked as SCLD L = 2 [25], the fast SC flip decoder proposed in [19] with $T_{max}=2$ is marked as FSCFD $T_{max}=2$ [19], the recursive trellis decoding scheme proposed in [39] with $\tau =4$ is marked as RTD $\tau =4$ [39], and so on. The results are shown in Figure 16.

As shown in Figure 16, the BER curves of SCD, SSCD and SCLD with L = 1 are just the same. The BER performance of LSNNAD scheme was slightly worse than NSCD and RTD with $\tau =6$, whereas the performance of KSNNAD is better than FSCFD with $T_{max}=3$ and worse than SCL decoder with L = 2.

4.5. Performance Comparison under Rayleigh Channel

A transmitted signal $s$ passes through the Rayleigh flat-fading channel, and the received signal can be expressed as follows:

$$g_{\mathrm{Re}LU}(z)=\max \{0,z\}.$$

(11)

where $h(t)$ is the fading factor, which obeys the Rayleigh distribution; $\theta (t)$ is the phase; and $n(t)$ is the complex white Gaussian noise. The comparison between the two decoding schemes and SC algorithm is shown in Figure 17.

As shown in Figure 17, the decoding performance from poor to excellent over Rayleigh channel is as follows: SCD, LSNNAD, and KSNNAD.

4.6. Decoding Complexity

4.6.1. Number of Arithmetic Operations

Compared with FSCD, the difference in the LSNNAD scheme and the KSNNAD scheme lies in node recognition and the training of the NN model. The complexity of NNN recognition and NN training can be ignored because they can be performed offline before the decoding. As to the complexity of node recognition online, LSNNAD needs at most $(2+N)\cdot {\log }_{2}N-18$ comparisons in the worst situation but only $2N/3-16$ comparisons in the best situation, while KSNNAD needs at most $(4+N)\cdot {\log }_{2}N-18$ comparisons but only $2N/3-16$ comparisons in the best situation.

Since the subcodes are not of equal length, a specific expression of the arithmetic operation cannot be given for each specific polar code. Let $N_S^{}$ denote code length of different special nodes. When decoding a polar code with a code length of 1024, a code rate of 0.5, and construction SNR 2.5 dB, number of special nodes with different node length for different decoding schemes is shown in

Table 2. Number of special nodes for different decoding schemes.

	NS	R1	R0	Rep	SPC	Type-I	Type-II	Type-III	Type-IV	Type-V	NNN
FSCFD [19]	8 16 32 64 128	1 1 0 0 0	0 0 1 0 0	6 4 0 1 1	8 4 1 1 1	0 0 0 0 0	2 0 1 0 0	1 0 1 0 0	1 0 0 1 0	9 1 0 1 0	0 0 0 0 0
FSCD	8 16 32 64 128	3 4 1 0 0	3 4 2 0 0	5 9 0 1 1	5 7 1 1 1	0 0 0 0 0	0 0 0 0 0	0 0 0 0 0	0 0 0 0 0	0 0 0 0 0	0 0 0 0 0
LSNNAD (NS = 16)	8 16 32 64 128	3 5 2 0 0	3 4 2 0 0	5 9 0 1 1	5 7 1 1 0	0 0 0 0 0	0 0 0 0 0	0 0 0 0 0	0 0 0 0 0	0 0 0 0 0	0 1 0 0 0
KSNNAD (NS = 16)	8 16 32 64 128	3 4 1 0 0	3 5 3 1 0	5 9 0 1 0	5 7 1 1 1	0 0 0 0 0	0 0 0 0 0	0 0 0 0 0	0 0 0 0 0	0 0 0 0 0	0 1 0 0 0

, number of arithmetic operations for different decoding steps is shown in

Table 3. Number of arithmetic operations for different decoding steps.

Decoding Step	Arithmetic Operation	FSCFD [19]	FSCD	LSNNAD	KSNNAD
Subcode recognition	Comparison	5984	6128	6264	6315
R1	Addition Multiplication	9NS − 7 NS − 1	2NS 4NS	2NS 4NS	2NS 4NS
Rep	Addition Multiplication	8NS − 6 NS − 1	NS 3NS	NS 3NS	NS 3NS
SPC	Addition Multiplication	11NS − 7 2NS − 1	NS 0	NS 0	NS 0
Type-I	Addition Multiplication	8NS − 7 NS − 1	0 0	0 0	0 0
Type-II	Addition Multiplication	10NS − 5 NS	0 0	0 0	0 0
Type-III	Addition Multiplication	10NS − 3 NS + 1	0 0	0 0	0 0
Type-IV	Addition Multiplication	10NS − 3 NS + 1	0 0	0 0	0 0
Type-V	Addition Multiplication	41NS − 7 69NS − 1	0 0	0 0	0 0
NNN	Addition Multiplication	0 0	0 0	164$K_S^2$ 164$K_S^2$	164$K_S^2$ 164$K_S^2$

, and total number of arithmetic operations for different decoding schemes is shown in

Table 4. Total number of arithmetic operations for different decoding schemes.

Arithmetic Operation	FSCFD [19]	FSCD	LSNNAD	KSNNAD	RTD [39] (τ = 4)	RTD [39] (τ = 6)
Comparison Addition Multiplication	5984 15,081 (Tmax + 1) 11,653 (Tmax + 1)	6128 864 1248	6264 43,152 43,280	6315 43,056 43,208	3587 5358 0	60,270 69,256 0

. Among them, LSNNAD and KSNNAD were simulated under the NN code length of $N_S^{}=16$.

One symbolic operation, taking absolute values and subtracting, is recorded as one addition; and one logarithmic and exponential operation is recorded as two multiplications. The operations of each decoding process are shown as Table 3.

An exclusive or operation is recorded as an addition, so FSCFD’s CRC check needs N additions at most. Calling the model once will introduce $164K_S^2$ multiplications and $164K_S^2+13K_S^{}$ additions in LANNAD and KSNNAD. Now we have the number of arithmetic operations for different special nodes and the subcode recognition, as well as the number of special nodes, so the total number of arithmetic operations for different decoding schemes can be calculated, and the results are shown in Table 4.

As shown in Table 4, when T_max = 2, FSCFD and KSNNAD are the closest in complexity, and the performance of KSNNAD is better than FSCFD, according to simulation results in Figure 16. RTD with $\tau =6$ is much more computationally intensive than KSNNAD but does not perform as well as KSNNAD in Figure 16.

4.6.2. Decoding Steps

Since the subcodes are not of equal length, a specific expression of the time step cannot be given for each specific polar code.

Table 5. Comparison of decoding steps.

Decoding Algorithm	Decoding Steps	Node Structure
SCD	317	None(128)
SSCD [17]	146	21R1 + None (64)
NSCD [33]	28/60	8NNN/16NNN
LSNNAD	66/70	2R0 + 6Rep + 4SPC + 5R1 + NNN/ 2R0 + 6Rep + 4SPC + 6R1 + NNN
KSNNAD	70/74	3R0 + 5Rep + 4SPC + 6R1 + NNN/ 4R0 + 5Rep + 4SPC + 6R1 + NNN

shows the decoding steps and node structure of LSNNAD, KSNNAD, and the algorithms proposed in Refs. [17,33] for a polar code with a code length of 128, a code rate of 0.5, and construction SNR 2.5 dB. Among them, NSCD proposed in Ref. [33], LSNNAD and KSNNAD were simulated under the NN code length of $N_S^{}=16/N_S^{}=8$. Let None (64) denote 64 bits that have not been recognized by any nodes. Note that the 64 bits are not 64 consecutive bits but several continuous strings scattered of bits. Further, 21R1 denotes that there are 21 R1 nodes to be recognized in total, but we do not provide every length of the R1 nodes.

It can be seen from Table 5 that the decoding steps of Ref. [33] were greatly affected by the length of the NNN. Moreover, they call the NN model multiple times, and each call will give rise to $164K_S^2$ multiplications and $164K_S^2+13K_S^{}$ additions. In contrast, the decoding schemes proposed in this paper are less affected by the length of the NNN because they only call the decoding model once. Compared with the traditional SCD algorithm, they can still effectively reduce the running time step of the decoding algorithm.

5. Conclusions

This paper proposes two NNA decoding schemes named LSNNAD and KSNNAD. There are two differences between the two schemes: one is the recognition method. After recognizing the polar code as a combination of NNN, R1, R0, SPC, and Rep node, decoding is performed and the trained NN model is called. The other is the training label. The LSNNAD scheme’s training label is the original information bits, and the KSNNAD scheme’s training label is the right decoding result with the flipping key bit derived from a definitely matched model. The simulation results verified the effectiveness of the two schemes. Since KSNNAD can effectively improve the decoding accuracy of the first error location, its decoding BER performance curve is better than that of the LSNNAD.