# A Generalization Belief Propagation Decoding Algorithm for Polar Codes Based on Particle Swarm Optimization

Authors: Yingxian Zhang; Aijun Liu; Xiaofei Pan; Shi He; Chao Gong
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

We propose a generalization belief propagation (BP) decoding algorithm based on particle swarm optimization (PSO) to improve the performance of the polar codes. Through the analysis of the existing BP decoding algorithm, we first introduce a probability modifying factor to each node of the BP decoder, so as to enhance the error correcting capacity of the decoding. Then, we generalize the BP decoding algorithm based on these modifying factors and drive the probability update equations for the proposed decoding. Based on the new probability update equations, we show the intrinsic relationship of the existing decoding algorithms. Finally, in order to achieve the best performance, we formulate an optimization problem to find the optimal probability modifying factors for the proposed decoding algorithm. Furthermore, a method based on the modified PSO algorithm is also introduced to solve that optimization problem. Numerical results show that the proposed generalization BP decoding algorithm achieves better performance than that of the existing BP decoding, which suggests the effectiveness of the proposed decoding algorithm.


---

## Body

## 1. Introduction

Since the ability of achieving Shannon capacity and their low encoding and decoding complexity, the polar codes have received much attention in the research field of error-correcting coding recently [1–17]. While compared to some existing coding schemes, such as low-density parity-check (LDPC) and turbo codes, the performance of the polar codes in the finite length regime is disappointing [2, 3]. Hence, motivated by this observation, researchers have proposed many decoding algorithms to improve the performance of the polar codes [4–17].Based on the successive-cancelation (SC) decoding algorithm proposed by Arıkan [1], authors of [4, 5] had introduced a list successive-cancelation (SCL) decoding algorithm with consideration of L SC decoding paths, where the results showed that performance of SCL was very close to that of maximum-likelihood (ML) decoding. Then, to decrease the time complexity of the SCL, another decoding algorithm derived from SC called stack successive-cancelation (SCS) was proposed in [6]. Furthermore, it was proven in [7] that, with cyclic redundancy check (CRC) aided, SCL even outperformed more than some turbo codes. However, due to the serial processing nature of the SC, all the algorithms in [4–7] would suffer a low decoding throughput and high latency. Therefore, some improved versions of SC were further proposed with the explicit aim to increase throughput and reduce the latency without sacrificing error-rate performance, such as simplified successive-cancellation (SSC) [8], maximum-likelihood SSC (ML-SSC) [9], and repetition single parity check ML-SSC (RSM-SSC) [10, 11]. Besides from those SC based algorithms, researchers had also investigated some other algorithms more in parallel, one typical representation of which was the belief propagation (BP) [12] decoding algorithm. With the factor graph representation of polar codes [13], authors in [14, 15] showed that BP polar decoding has particular advantages with respect to the decoding throughput, while the performance was better than that of the SC and some improved SC decoding. What is more, with the minimal stopping set optimized, results of [16, 17] had shown that the error floor performance of polar codes was superior to that of LDPC codes.Indeed, all the decoding algorithms in [4–17] can improve the performance of polar codes to a certain degree. However, as the capacity achieving coding scheme, the results of those algorithms is still limited. Hence, in this paper, we propose a generalization belief propagation (BP) decoding algorithm based on particle swarm optimization (PSO) to improve the performance of the polar codes with the finite length. Based on the analysis results of the existing BP decoding algorithm, we first show that the error-correcting capacity of the BP decoding algorithm is important for performance of the decoding. Motivated by that observation, we introduce a probability modifying factor to each node of the BP decoder to enhance the reliability of the probability updated. Then, we generalize the BP decoding algorithm on the basis of these modifying factors and further drive the probability update equations for the proposed generalization BP decoding. Finally, in order to achieve the best performance, we formulate an optimization problem to find the optimal probability modifying factors for the proposed generalization BP decoding. Furthermore, a method based on the modified PSO algorithm is also introduced to solve the optimization problem. The main contributions of this paper can be summarized as follows.(i)
A generalization belief propagation (BP) decoding algorithm based on probability modifying factor is introduced. Furthermore, as to improve the performance of the proposed decoding, a BP decoding algorithm optimization problem is formulated.
(ii)
A method based on the modified PSO algorithm is introduced to solve the optimization problem.The finding of this paper suggests that with the probability modifying factor, the error-correcting capacity of the BP decoding can be enhanced, and the performance of the polar codes can be improved correspondingly, which is finally proven by the simulation results.The remainder of this paper is organized as follows. In Section2, we explain some notations and introduce some background on the polar codes. And in Section 3, the generalization belief propagation (BP) decoding algorithm based on the probability modifying factors is described in detail. In Section 4, we formulate and solve the optimization problem of finding the probability modifying factors. And Section 5 provides the simulation results for the complexity and bit error performance of the proposed decoding. Finally, we make some conclusions in Section 6.


## 2. Preliminary

### 2.1. Notations

In this paper, the blackboard bold letters, such as𝕏, denote the sets, and |
𝕏
| denotes the number of elements in 𝕏. The notation u
0
N
-
1 denotes an N-dimensional vector (
u
0
,
u
1
,
…
,
u
N
-
1
), and u
i
j indicates a subvector (
u
i
,
u
i
+
1
,
…
,
u
j
-
1
,
u
j
) of u
0
N
-
1, 0
≤
i, j
≤
N
-
1. When i
>
j, u
i
j is an empty vector. Further, given a vector set 𝕌, vector u
→
i is the ith element of 𝕌.The matrices in this paper are denoted by bold letters. The subscript of a matrix indicates its size, for example,A
N
×
M represents an N
×
M matrix A. Specifically, the square matrices are written as A
N, size of which is N
×
N, and A
N
-
1 is the inverse of A
N. Furthermore, the Kronecker product of two matrices A and B is written as A
⊗
B, and the nth Kronecker power of A is A
⊗
n.During the procedure of the encoding and decoding, we denote the intermediate node byv
I
(
i
,
j
) or v
O
(
i
,
j
)
,
0
≤
i
≤
n
,
0
≤
j
≤
N
-
1, where N
=
2
n is the code length. Besides, we also indicate the probability messages of the intermediate node v
I
(
i
,
j
) as p
I
(
i
,
j
), where the probability of v
I
(
i
,
j
) being equal to 0 or 1 is p
I
(
i
,
j
)
(
0
) or p
I
(
i
,
j
)
(
1
). Similarly, the probability messages of v
O
(
i
,
j
) are p
O
(
i
,
j
)
(
0
) and p
O
(
i
,
j
)
(
1
).Throughout this paper, “⊕” denotes the modulo-two sum, and “∑
i
=
0
M
‍
⊕
x
i” means “x
0
⊕
x
1
⊕
,
…
,
⊕
x
M”. While the operators “⊗” and “⊙” are defined as p
x
⊗
p
y
=
p
(
x
⊕
y
) and p
x
⊙
p
y
=
p
x
*
p
y, respectively, x
,
y
∈
{
0,1
}.


### 2.2. Background of Polar Codes

A polar coding scheme can be uniquely defined by three parameters: block-lengthN
=
2
n, code rate R
=
K
/
N, and an information set 𝕀
⊂
ℕ
=
{
0,1
,
…
,
N
-
1
}, where K
=
|
𝕀
|. With these three parameters, a source binary vector u
0
N
-
1 consisting of K information bits and N
-
K frozen bits can be mapped a codeword x
0
N
-
1 by a linear matric G
N
=
B
N
F
2
⊗
n, where F
2
=
[
1
0
1
1
], B
N is a bit-reversal permutation matrix defined in [1], and x
0
N
-
1
=
u
0
N
-
1
G
N.In practice, the construction procedure of a polar code can be divided inton
=
log
⁡
2
N stages, as shown in Figure 1(a), where the circle nodes in the leftmost column are the input nodes of encoder, values of which are equal to binary source vector,that is, v
I
(
0
,
i
)
=
u
i, and the circle nodes in the rightmost column are the output nodes of encoder, v
O
(
n
-
1
,
i
)
=
x
i. It is also noticed that, each encoding stage has N
/
2, so-called processing units (PU) with a generation matrix of F
2, and each PU has two input and two output variable nodes, as shown in Figure 1(b). During the process of polar encoding, based on F
2, we have
(1)
v
O
(
i
,
2
j
)
=
v
I
(
i
,
2
j
)
⊕
v
I
(
i
,
2
j
+
1
)
v
O
(
i
,
2
j
+
1
)
=
v
I
(
i
,
2
j
+
1
)
,
where v
I
(
i
,
2
j
) and v
I
(
i
,
2
j
+
1
) are the input nodes of the jth PU in the ith stage, 0
≤
i
≤
n
-
1
,
0
≤
j
≤
N
/
2
-
1, and similarly, v
O
(
i
,
2
j
) and v
O
(
i
,
2
j
+
1
) are the output nodes. After the procedure of the polar encoding, all the bits in the codeword x
0
N
-
1 are passed to the N-channels, which consisted of N independent channels of W, with a transition probability of W
(
y
i
∣
x
i
), where y
i is ith element of the received vector y
0
N
-
1. Then, the decoder of the receiver will output the estimated codeword x
^
0
N
-
1 and the estimated source binary vector u
^
0
N
-
1 with different decoding algorithms [4–17].(a) Construction procedure of polar codes withN
=
8. (b) Diagram of PU in code construction.
(a)
(b)


## 2.1. Notations

In this paper, the blackboard bold letters, such as𝕏, denote the sets, and |
𝕏
| denotes the number of elements in 𝕏. The notation u
0
N
-
1 denotes an N-dimensional vector (
u
0
,
u
1
,
…
,
u
N
-
1
), and u
i
j indicates a subvector (
u
i
,
u
i
+
1
,
…
,
u
j
-
1
,
u
j
) of u
0
N
-
1, 0
≤
i, j
≤
N
-
1. When i
>
j, u
i
j is an empty vector. Further, given a vector set 𝕌, vector u
→
i is the ith element of 𝕌.The matrices in this paper are denoted by bold letters. The subscript of a matrix indicates its size, for example,A
N
×
M represents an N
×
M matrix A. Specifically, the square matrices are written as A
N, size of which is N
×
N, and A
N
-
1 is the inverse of A
N. Furthermore, the Kronecker product of two matrices A and B is written as A
⊗
B, and the nth Kronecker power of A is A
⊗
n.During the procedure of the encoding and decoding, we denote the intermediate node byv
I
(
i
,
j
) or v
O
(
i
,
j
)
,
0
≤
i
≤
n
,
0
≤
j
≤
N
-
1, where N
=
2
n is the code length. Besides, we also indicate the probability messages of the intermediate node v
I
(
i
,
j
) as p
I
(
i
,
j
), where the probability of v
I
(
i
,
j
) being equal to 0 or 1 is p
I
(
i
,
j
)
(
0
) or p
I
(
i
,
j
)
(
1
). Similarly, the probability messages of v
O
(
i
,
j
) are p
O
(
i
,
j
)
(
0
) and p
O
(
i
,
j
)
(
1
).Throughout this paper, “⊕” denotes the modulo-two sum, and “∑
i
=
0
M
‍
⊕
x
i” means “x
0
⊕
x
1
⊕
,
…
,
⊕
x
M”. While the operators “⊗” and “⊙” are defined as p
x
⊗
p
y
=
p
(
x
⊕
y
) and p
x
⊙
p
y
=
p
x
*
p
y, respectively, x
,
y
∈
{
0,1
}.


## 2.2. Background of Polar Codes

A polar coding scheme can be uniquely defined by three parameters: block-lengthN
=
2
n, code rate R
=
K
/
N, and an information set 𝕀
⊂
ℕ
=
{
0,1
,
…
,
N
-
1
}, where K
=
|
𝕀
|. With these three parameters, a source binary vector u
0
N
-
1 consisting of K information bits and N
-
K frozen bits can be mapped a codeword x
0
N
-
1 by a linear matric G
N
=
B
N
F
2
⊗
n, where F
2
=
[
1
0
1
1
], B
N is a bit-reversal permutation matrix defined in [1], and x
0
N
-
1
=
u
0
N
-
1
G
N.In practice, the construction procedure of a polar code can be divided inton
=
log
⁡
2
N stages, as shown in Figure 1(a), where the circle nodes in the leftmost column are the input nodes of encoder, values of which are equal to binary source vector,that is, v
I
(
0
,
i
)
=
u
i, and the circle nodes in the rightmost column are the output nodes of encoder, v
O
(
n
-
1
,
i
)
=
x
i. It is also noticed that, each encoding stage has N
/
2, so-called processing units (PU) with a generation matrix of F
2, and each PU has two input and two output variable nodes, as shown in Figure 1(b). During the process of polar encoding, based on F
2, we have
(1)
v
O
(
i
,
2
j
)
=
v
I
(
i
,
2
j
)
⊕
v
I
(
i
,
2
j
+
1
)
v
O
(
i
,
2
j
+
1
)
=
v
I
(
i
,
2
j
+
1
)
,
where v
I
(
i
,
2
j
) and v
I
(
i
,
2
j
+
1
) are the input nodes of the jth PU in the ith stage, 0
≤
i
≤
n
-
1
,
0
≤
j
≤
N
/
2
-
1, and similarly, v
O
(
i
,
2
j
) and v
O
(
i
,
2
j
+
1
) are the output nodes. After the procedure of the polar encoding, all the bits in the codeword x
0
N
-
1 are passed to the N-channels, which consisted of N independent channels of W, with a transition probability of W
(
y
i
∣
x
i
), where y
i is ith element of the received vector y
0
N
-
1. Then, the decoder of the receiver will output the estimated codeword x
^
0
N
-
1 and the estimated source binary vector u
^
0
N
-
1 with different decoding algorithms [4–17].(a) Construction procedure of polar codes withN
=
8. (b) Diagram of PU in code construction.
(a)
(b)


## 3. BP Decoding for Polar Codes

In this section, we will generalize the BP decoding algorithm for polar codes with the analysis of the existing polar BP decoding.


### 3.1. Existing BP Decoding

The basic BP process unit (BP-PU) of polar codes is shown in Figure2, where p
I
L
(
i
,
2
j
)
t and p
I
L
(
i
,
2
j
+
1
)
t are the right-to-left probability messages passed to v
I
(
i
,
2
j
) and v
I
(
i
,
2
j
+
1
); t is the iteration number. p
I
R
(
i
,
2
j
)
t
-
1 and p
I
R
(
i
,
2
j
+
1
)
t
-
1 are the left-to-right probability messages passed from the nodes. p
O
L
(
i
,
2
j
)
t
-
1 and p
O
L
(
i
,
2
j
+
1
)
t
-
1 are the right-to-left probability messages passed from v
O
(
i
,
2
j
) and v
O
(
i
,
2
j
+
1
) and p
O
R
(
i
,
2
j
)
t and p
O
R
(
i
,
2
j
+
1
)
t are the left-to-right probability messages passed to the nodes. According to the formula of total probability, there has
(2)
p
I
L
(
i
,
j
)
t
(
0
)
+
p
I
L
(
i
,
j
)
t
(
1
)
=
1
,
p
I
R
(
i
,
j
)
t
(
0
)
+
p
I
R
(
i
,
j
)
t
(
1
)
=
1
,
p
O
L
(
i
,
j
)
t
(
0
)
+
p
O
L
(
i
,
j
)
t
(
1
)
=
1
,
p
O
R
(
i
,
j
)
t
(
0
)
+
p
O
R
(
i
,
j
)
t
(
1
)
=
1
.
Furthermore, based on the transition probability of the channel W, that is, W
(
y
i
∣
x
i
), and the received vector y
0
N
-
1, we have
(3)
p
O
L
(
n
-
1
,
i
)
0
(
0
)
=
W
(
y
i
∣
x
i
=
0
)
P
(
x
i
=
0
)
P
(
y
i
)
p
O
L
(
n
-
1
,
i
)
0
(
1
)
=
W
(
y
i
∣
x
i
=
1
)
P
(
x
i
=
1
)
P
(
y
i
)
,
where P
(
x
i
) and P
(
y
i
) are the probability distribution functions of coded bit x
i and received signal sample y
i. In the BP decoding algorithm [13–17], the messages updated equations are given by
(4)
p
I
L
(
i
,
2
j
)
t
=
p
O
L
(
i
,
2
j
)
t
-
1
⊗
(
p
O
L
(
i
,
2
j
+
1
)
t
-
1
⊙
p
I
R
(
i
,
2
j
+
1
)
t
-
1
)
,
p
I
L
(
i
,
2
j
+
1
)
t
=
(
p
I
R
(
i
,
2
j
)
t
-
1
⊗
p
O
L
(
i
,
2
j
)
t
-
1
)
⊙
p
O
L
(
i
,
2
j
+
1
)
t
-
1
,
p
O
R
(
i
,
2
j
)
t
=
p
I
R
(
i
,
2
j
)
t
-
1
⊗
(
p
I
R
(
i
,
2
j
+
1
)
t
-
1
⊙
p
O
L
(
i
,
2
j
+
1
)
t
-
1
)
,
p
O
R
(
i
,
2
j
+
1
)
t
=
(
p
I
R
(
i
,
2
j
)
t
-
1
⊗
p
O
L
(
i
,
2
j
)
t
-
1
)
⊙
p
I
R
(
i
,
2
j
+
1
)
t
-
1
.Figure 2
The BP decoding algorithm for polar codes is based on the factor graph representation of the codes [13]. In the algorithm, each node v
I
(
i
,
j
) or v
O
(
i
,
j
) is associated with two types of probability messages: left-to-right probability messages and right-to-left probability messages. Both of messages are propagated and updated iteratively between adjacent nodes in the procedure of BP. And the messages updated schedule is the same as that of [14]; that is, messages will firstly propagate from the rightmost nodes to the leftmost nodes. After arriving at the leftmost nodes, the course will be reversed, and messages propagation will move toward the rightmost nodes. This procedure makes oneround iteration of BP. Diagram of BP-PU.Based on (4), when the decoding reaches maximum iteration number (mIter), BP decoder output the decoded vector u
^
=
(
u
^
0
,
…
,
u
^
N
-
1
), each elements of which depended on
(5)
u
^
i
=
{
0
,
p
I
L
(
0
,
i
)
mIter
(
0
)
>
p
I
L
(
0
,
i
)
mIter
(
1
)
1
,
otherwise
.


### 3.2. Analysis of BP Decoder

It is noticed from [13–17], based on the BP decoding, the performance of polar codes can be improved to a certain degree. However, as the capacity achieving coding scheme, the results of those algorithms is still disappointing. Hence, we cannot help wondering why the performance of the polar codes with finite length is inferior to that of LDPC codes [16, 17], and how we can improve it. To answer the questions, we need to make a further analysis of the existing BP decoder.In fact, it is noticed from the factor graph of polar codes in [13] that the degree of the check or variable nodes in the polar BP decoder is 2 or 3. While the average degree of the LDPC codes is usually greater than 3 [12, 18], which means that the error-correcting capacity of the polar BP decoding will be weaken. Hence, the performance of the polar codes is inferior to that of LDPC codes with the same length [18]. As shown in Figure 3, two Tanner graphes with different degree distributions are given. We assume that there exists an error variable node v
1 in a certain iteration. Compared to the check nodes c
0 and c
1 in Figure 3(a), the influence of error probability messages from v
1 to c
0 and c
1 in Figure 3(a) is weak, because with a greater degree number, the proportion of the error probability messages in the input probability messages of c
0 and c
1 will be reduced. What is more, the convergence of BP decoding with a greater average degree will be quicker, which results in less computational iteration number, as shown in [12–18]. Therefore, to improve the performance of polar BP decoding, it is important to enhance the error-correcting capacity of the algorithm.(a) Tanner graph with average degree less than 3. (b) Tanner graph with average degree more than 3.
(a)
(b)


### 3.3. Generalization of BP Decoding

Motivated by aforementioned observation, in this subsection, we will introduce a generalization framework of BP decoder for polar codes. In order to improve the error-correcting capacity of polar BP decoding, twelve probability messages modifying factors are introduced to the nodes of the BP-PU shown in Figure2. When the probability messages of a node of the BP-PU is updated, three probability messages modifying factors are added to other three nodes, respectively.As illustrated in Figure4, γ
L
0
(
i
,
j
)
t
,
…
,
γ
L
5
(
i
,
j
)
t and γ
R
0
(
i
,
j
)
t
,
…
,
γ
R
5
(
i
,
j
)
t are the probability messages modifying factors of the jth BP-PU in ith stage. In this case, each equation in (4) will be correspondingly added with three variables, e.g., the first equation of (4) is added with γ
L
0
(
i
,
j
)
t, γ
L
1
(
i
,
j
)
t, and γ
L
2
(
i
,
j
)
t. Besides, based on the new construction of BP-PU, we further define the result of each nodes’ probability messages calculation as a function with respect to these three variables and the probability messages of other three nodes; hence, we can get the new messages update equations as (6). Consider
(6)
p
I
L
(
i
,
2
j
)
t
=
f
(
i
,
j
)
0
(
p
O
L
(
i
,
2
j
)
t
-
1
,
p
O
L
(
i
,
2
j
+
1
)
t
-
1
,
p
I
R
(
i
,
2
j
+
1
)
t
-
1
,
h
h
h
h
h
h
h
h
h
h
h
h
γ
L
0
(
i
,
j
)
t
,
γ
L
1
(
i
,
j
)
t
,
γ
L
2
(
i
,
j
)
t
)
,
p
I
L
(
i
,
2
j
+
1
)
t
=
f
(
i
,
j
)
1
(
p
O
L
(
i
,
2
j
+
1
)
t
-
1
,
p
O
L
(
i
,
2
j
)
t
-
1
,
p
I
R
(
i
,
2
j
)
t
-
1
,
h
h
h
h
h
h
h
h
h
h
h
h
h
γ
L
3
(
i
,
j
)
t
,
γ
L
4
(
i
,
j
)
t
,
γ
L
5
(
i
,
j
)
t
)
,
p
O
R
(
i
,
2
j
)
t
=
f
(
i
,
j
)
2
(
p
I
R
(
i
,
2
j
)
t
-
1
,
p
I
R
(
i
,
2
j
+
1
)
t
-
1
,
p
O
L
(
i
,
2
j
+
1
)
t
-
1
,
h
h
h
h
h
h
h
h
h
h
h
h
h
γ
R
0
(
i
,
j
)
t
,
γ
R
1
(
i
,
j
)
t
,
γ
R
2
(
i
,
j
)
t
)
,
p
O
R
(
i
,
2
j
+
1
)
t
=
f
(
i
,
j
)
3
(
p
I
R
(
i
,
2
j
+
1
)
t
-
1
,
p
I
R
(
i
,
2
j
)
t
-
1
,
p
O
L
(
i
,
2
j
)
t
-
1
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
γ
R
3
(
i
,
j
)
t
,
γ
R
4
(
i
,
j
)
t
,
γ
R
5
(
i
,
j
)
t
)
.Diagrams of the new BP-PU.
(a)
(b)
(c)
(d)In (6), f
(
i
,
j
)
0
(
φ
0
5
), f
(
i
,
j
)
1
(
φ
0
5
), f
(
i
,
j
)
2
(
φ
0
5
), and f
(
i
,
j
)
3
(
φ
0
5
) are the four probability messages update functions of the jth BP-PU in ith stage, and φ
0
,
…
,
φ
5 are six probability messages variables. Based on (6), we can easily get a new expression of (4) defined as the functions of f
(
i
,
j
)
0
(
φ
0
5
)
,
f
(
i
,
j
)
1
(
φ
0
5
)
,
f
(
i
,
j
)
2
(
φ
0
5
), and f
(
i
,
j
)
3
(
φ
0
5
); that is,
(7)
f
(
i
,
j
)
0
(
φ
0
5
)
=
φ
0
⊗
(
φ
1
⊙
φ
2
)
,
f
(
i
,
j
)
1
(
φ
0
5
)
=
φ
0
⊙
(
φ
1
⊗
φ
2
)
,
f
(
i
,
j
)
2
(
φ
0
5
)
=
φ
0
⊗
(
φ
1
⊙
φ
2
)
,
f
(
i
,
j
)
3
(
φ
0
5
)
=
φ
0
⊙
(
φ
1
⊗
φ
2
)
.
That is to say, the existing BP decoding algorithm is a special case of the generalization BP decoding proposed in this work. Furthermore, with the four probability messages update functions of
(8)
f
(
i
,
j
)
0
(
φ
0
5
)
=
φ
0
⊗
φ
1
,
f
(
i
,
j
)
1
(
φ
0
5
)
=
φ
0
⊙
(
φ
1
⊗
φ
2
)
,
f
(
i
,
j
)
2
(
φ
0
5
)
=
φ
0
⊗
φ
1
,
f
(
i
,
j
)
3
(
φ
0
5
)
=
φ
0
;
we can also get the probability messages update equations of the SC based decoding algorithms as shown in [1, 4–11]. Similarly, it is concluded that the SC based decoding algorithms are also the special cases of our generalization BP decoding, which has shown the intrinsic relationship of the SC based decoding and BP decoding algorithms.Therefore, we can conclude from (6)–(8) that, in order to improve the performance of the polar codes, it is needed to find the optimal functions of f
(
i
,
j
)
0
(
φ
0
5
), f
(
i
,
j
)
1
(
φ
0
5
), f
(
i
,
j
)
2
(
φ
0
5
) and f
(
i
,
j
)
3
(
φ
0
5
), and the optimal parameters of γ
L
0
(
i
,
j
)
t
,
…
,
γ
L
5
(
i
,
j
)
t and γ
R
0
(
i
,
j
)
t
,
…
,
γ
R
5
(
i
,
j
)
t, which will be discussed in the next section.


## 3.1. Existing BP Decoding

The basic BP process unit (BP-PU) of polar codes is shown in Figure2, where p
I
L
(
i
,
2
j
)
t and p
I
L
(
i
,
2
j
+
1
)
t are the right-to-left probability messages passed to v
I
(
i
,
2
j
) and v
I
(
i
,
2
j
+
1
); t is the iteration number. p
I
R
(
i
,
2
j
)
t
-
1 and p
I
R
(
i
,
2
j
+
1
)
t
-
1 are the left-to-right probability messages passed from the nodes. p
O
L
(
i
,
2
j
)
t
-
1 and p
O
L
(
i
,
2
j
+
1
)
t
-
1 are the right-to-left probability messages passed from v
O
(
i
,
2
j
) and v
O
(
i
,
2
j
+
1
) and p
O
R
(
i
,
2
j
)
t and p
O
R
(
i
,
2
j
+
1
)
t are the left-to-right probability messages passed to the nodes. According to the formula of total probability, there has
(2)
p
I
L
(
i
,
j
)
t
(
0
)
+
p
I
L
(
i
,
j
)
t
(
1
)
=
1
,
p
I
R
(
i
,
j
)
t
(
0
)
+
p
I
R
(
i
,
j
)
t
(
1
)
=
1
,
p
O
L
(
i
,
j
)
t
(
0
)
+
p
O
L
(
i
,
j
)
t
(
1
)
=
1
,
p
O
R
(
i
,
j
)
t
(
0
)
+
p
O
R
(
i
,
j
)
t
(
1
)
=
1
.
Furthermore, based on the transition probability of the channel W, that is, W
(
y
i
∣
x
i
), and the received vector y
0
N
-
1, we have
(3)
p
O
L
(
n
-
1
,
i
)
0
(
0
)
=
W
(
y
i
∣
x
i
=
0
)
P
(
x
i
=
0
)
P
(
y
i
)
p
O
L
(
n
-
1
,
i
)
0
(
1
)
=
W
(
y
i
∣
x
i
=
1
)
P
(
x
i
=
1
)
P
(
y
i
)
,
where P
(
x
i
) and P
(
y
i
) are the probability distribution functions of coded bit x
i and received signal sample y
i. In the BP decoding algorithm [13–17], the messages updated equations are given by
(4)
p
I
L
(
i
,
2
j
)
t
=
p
O
L
(
i
,
2
j
)
t
-
1
⊗
(
p
O
L
(
i
,
2
j
+
1
)
t
-
1
⊙
p
I
R
(
i
,
2
j
+
1
)
t
-
1
)
,
p
I
L
(
i
,
2
j
+
1
)
t
=
(
p
I
R
(
i
,
2
j
)
t
-
1
⊗
p
O
L
(
i
,
2
j
)
t
-
1
)
⊙
p
O
L
(
i
,
2
j
+
1
)
t
-
1
,
p
O
R
(
i
,
2
j
)
t
=
p
I
R
(
i
,
2
j
)
t
-
1
⊗
(
p
I
R
(
i
,
2
j
+
1
)
t
-
1
⊙
p
O
L
(
i
,
2
j
+
1
)
t
-
1
)
,
p
O
R
(
i
,
2
j
+
1
)
t
=
(
p
I
R
(
i
,
2
j
)
t
-
1
⊗
p
O
L
(
i
,
2
j
)
t
-
1
)
⊙
p
I
R
(
i
,
2
j
+
1
)
t
-
1
.Figure 2
The BP decoding algorithm for polar codes is based on the factor graph representation of the codes [13]. In the algorithm, each node v
I
(
i
,
j
) or v
O
(
i
,
j
) is associated with two types of probability messages: left-to-right probability messages and right-to-left probability messages. Both of messages are propagated and updated iteratively between adjacent nodes in the procedure of BP. And the messages updated schedule is the same as that of [14]; that is, messages will firstly propagate from the rightmost nodes to the leftmost nodes. After arriving at the leftmost nodes, the course will be reversed, and messages propagation will move toward the rightmost nodes. This procedure makes oneround iteration of BP. Diagram of BP-PU.Based on (4), when the decoding reaches maximum iteration number (mIter), BP decoder output the decoded vector u
^
=
(
u
^
0
,
…
,
u
^
N
-
1
), each elements of which depended on
(5)
u
^
i
=
{
0
,
p
I
L
(
0
,
i
)
mIter
(
0
)
>
p
I
L
(
0
,
i
)
mIter
(
1
)
1
,
otherwise
.


## 3.2. Analysis of BP Decoder

It is noticed from [13–17], based on the BP decoding, the performance of polar codes can be improved to a certain degree. However, as the capacity achieving coding scheme, the results of those algorithms is still disappointing. Hence, we cannot help wondering why the performance of the polar codes with finite length is inferior to that of LDPC codes [16, 17], and how we can improve it. To answer the questions, we need to make a further analysis of the existing BP decoder.In fact, it is noticed from the factor graph of polar codes in [13] that the degree of the check or variable nodes in the polar BP decoder is 2 or 3. While the average degree of the LDPC codes is usually greater than 3 [12, 18], which means that the error-correcting capacity of the polar BP decoding will be weaken. Hence, the performance of the polar codes is inferior to that of LDPC codes with the same length [18]. As shown in Figure 3, two Tanner graphes with different degree distributions are given. We assume that there exists an error variable node v
1 in a certain iteration. Compared to the check nodes c
0 and c
1 in Figure 3(a), the influence of error probability messages from v
1 to c
0 and c
1 in Figure 3(a) is weak, because with a greater degree number, the proportion of the error probability messages in the input probability messages of c
0 and c
1 will be reduced. What is more, the convergence of BP decoding with a greater average degree will be quicker, which results in less computational iteration number, as shown in [12–18]. Therefore, to improve the performance of polar BP decoding, it is important to enhance the error-correcting capacity of the algorithm.(a) Tanner graph with average degree less than 3. (b) Tanner graph with average degree more than 3.
(a)
(b)


## 3.3. Generalization of BP Decoding

Motivated by aforementioned observation, in this subsection, we will introduce a generalization framework of BP decoder for polar codes. In order to improve the error-correcting capacity of polar BP decoding, twelve probability messages modifying factors are introduced to the nodes of the BP-PU shown in Figure2. When the probability messages of a node of the BP-PU is updated, three probability messages modifying factors are added to other three nodes, respectively.As illustrated in Figure4, γ
L
0
(
i
,
j
)
t
,
…
,
γ
L
5
(
i
,
j
)
t and γ
R
0
(
i
,
j
)
t
,
…
,
γ
R
5
(
i
,
j
)
t are the probability messages modifying factors of the jth BP-PU in ith stage. In this case, each equation in (4) will be correspondingly added with three variables, e.g., the first equation of (4) is added with γ
L
0
(
i
,
j
)
t, γ
L
1
(
i
,
j
)
t, and γ
L
2
(
i
,
j
)
t. Besides, based on the new construction of BP-PU, we further define the result of each nodes’ probability messages calculation as a function with respect to these three variables and the probability messages of other three nodes; hence, we can get the new messages update equations as (6). Consider
(6)
p
I
L
(
i
,
2
j
)
t
=
f
(
i
,
j
)
0
(
p
O
L
(
i
,
2
j
)
t
-
1
,
p
O
L
(
i
,
2
j
+
1
)
t
-
1
,
p
I
R
(
i
,
2
j
+
1
)
t
-
1
,
h
h
h
h
h
h
h
h
h
h
h
h
γ
L
0
(
i
,
j
)
t
,
γ
L
1
(
i
,
j
)
t
,
γ
L
2
(
i
,
j
)
t
)
,
p
I
L
(
i
,
2
j
+
1
)
t
=
f
(
i
,
j
)
1
(
p
O
L
(
i
,
2
j
+
1
)
t
-
1
,
p
O
L
(
i
,
2
j
)
t
-
1
,
p
I
R
(
i
,
2
j
)
t
-
1
,
h
h
h
h
h
h
h
h
h
h
h
h
h
γ
L
3
(
i
,
j
)
t
,
γ
L
4
(
i
,
j
)
t
,
γ
L
5
(
i
,
j
)
t
)
,
p
O
R
(
i
,
2
j
)
t
=
f
(
i
,
j
)
2
(
p
I
R
(
i
,
2
j
)
t
-
1
,
p
I
R
(
i
,
2
j
+
1
)
t
-
1
,
p
O
L
(
i
,
2
j
+
1
)
t
-
1
,
h
h
h
h
h
h
h
h
h
h
h
h
h
γ
R
0
(
i
,
j
)
t
,
γ
R
1
(
i
,
j
)
t
,
γ
R
2
(
i
,
j
)
t
)
,
p
O
R
(
i
,
2
j
+
1
)
t
=
f
(
i
,
j
)
3
(
p
I
R
(
i
,
2
j
+
1
)
t
-
1
,
p
I
R
(
i
,
2
j
)
t
-
1
,
p
O
L
(
i
,
2
j
)
t
-
1
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
γ
R
3
(
i
,
j
)
t
,
γ
R
4
(
i
,
j
)
t
,
γ
R
5
(
i
,
j
)
t
)
.Diagrams of the new BP-PU.
(a)
(b)
(c)
(d)In (6), f
(
i
,
j
)
0
(
φ
0
5
), f
(
i
,
j
)
1
(
φ
0
5
), f
(
i
,
j
)
2
(
φ
0
5
), and f
(
i
,
j
)
3
(
φ
0
5
) are the four probability messages update functions of the jth BP-PU in ith stage, and φ
0
,
…
,
φ
5 are six probability messages variables. Based on (6), we can easily get a new expression of (4) defined as the functions of f
(
i
,
j
)
0
(
φ
0
5
)
,
f
(
i
,
j
)
1
(
φ
0
5
)
,
f
(
i
,
j
)
2
(
φ
0
5
), and f
(
i
,
j
)
3
(
φ
0
5
); that is,
(7)
f
(
i
,
j
)
0
(
φ
0
5
)
=
φ
0
⊗
(
φ
1
⊙
φ
2
)
,
f
(
i
,
j
)
1
(
φ
0
5
)
=
φ
0
⊙
(
φ
1
⊗
φ
2
)
,
f
(
i
,
j
)
2
(
φ
0
5
)
=
φ
0
⊗
(
φ
1
⊙
φ
2
)
,
f
(
i
,
j
)
3
(
φ
0
5
)
=
φ
0
⊙
(
φ
1
⊗
φ
2
)
.
That is to say, the existing BP decoding algorithm is a special case of the generalization BP decoding proposed in this work. Furthermore, with the four probability messages update functions of
(8)
f
(
i
,
j
)
0
(
φ
0
5
)
=
φ
0
⊗
φ
1
,
f
(
i
,
j
)
1
(
φ
0
5
)
=
φ
0
⊙
(
φ
1
⊗
φ
2
)
,
f
(
i
,
j
)
2
(
φ
0
5
)
=
φ
0
⊗
φ
1
,
f
(
i
,
j
)
3
(
φ
0
5
)
=
φ
0
;
we can also get the probability messages update equations of the SC based decoding algorithms as shown in [1, 4–11]. Similarly, it is concluded that the SC based decoding algorithms are also the special cases of our generalization BP decoding, which has shown the intrinsic relationship of the SC based decoding and BP decoding algorithms.Therefore, we can conclude from (6)–(8) that, in order to improve the performance of the polar codes, it is needed to find the optimal functions of f
(
i
,
j
)
0
(
φ
0
5
), f
(
i
,
j
)
1
(
φ
0
5
), f
(
i
,
j
)
2
(
φ
0
5
) and f
(
i
,
j
)
3
(
φ
0
5
), and the optimal parameters of γ
L
0
(
i
,
j
)
t
,
…
,
γ
L
5
(
i
,
j
)
t and γ
R
0
(
i
,
j
)
t
,
…
,
γ
R
5
(
i
,
j
)
t, which will be discussed in the next section.


## 4. BP Decoding Algorithm Optimization

Motivated by the aforementioned conclusion, we now consider how to optimize the generalization BP decoding algorithm so as to improve the performance of the polar codes.


### 4.1. Messages Update Functions

It is noticed from (4) and (6)–(8) that, in order to enhance the reliability of messages propagation, it is important to determine the appropriate messages update functions for the generalization BP decoding algorithm. However, in general, it is difficult to find the optimal messages update functions; therefore, in this work, the messages update functions are introduced by the analysis of the construction of polar encoding. And based on (1), we have
(9)
v
I
(
i
,
2
j
)
=
v
O
(
i
,
2
j
)
⊕
v
O
(
i
,
2
j
+
1
)
=
v
O
(
i
,
2
j
)
⊕
v
I
(
i
,
2
j
+
1
)
,
v
I
(
i
,
2
j
+
1
)
=
v
O
(
i
,
2
j
+
1
)
=
v
O
(
i
,
2
j
)
⊕
v
I
(
i
,
2
j
)
,
v
O
(
i
,
2
j
)
=
v
I
(
i
,
2
j
)
⊕
v
I
(
i
,
2
j
+
1
)
=
v
I
(
i
,
2
j
)
⊕
v
O
(
i
,
2
j
+
1
)
,
v
O
(
i
,
2
j
+
1
)
=
v
I
(
i
,
2
j
+
1
)
=
v
I
(
i
,
2
j
)
⊕
v
O
(
i
,
2
j
)
.Therefore, based on the error coding theory and (9), we can get the messages update functions as
(10)
f
(
i
,
j
)
0
(
φ
0
5
)
=
(
(
φ
0
⊙
φ
3
)
⊗
(
φ
1
⊙
φ
4
)
)
f
(
i
,
j
)
0
(
φ
0
5
)
=
⊙
(
(
φ
0
⊙
φ
3
)
⊗
(
φ
2
⊙
φ
5
)
)
,
f
(
i
,
j
)
1
(
φ
0
5
)
=
(
φ
0
⊙
φ
3
)
⊙
(
(
φ
1
⊙
φ
4
)
⊗
(
φ
2
⊙
φ
5
)
)
,
f
(
i
,
j
)
2
(
φ
0
5
)
=
(
(
φ
0
⊙
φ
3
)
⊗
(
φ
1
⊙
φ
4
)
)
f
(
i
,
j
)
0
(
φ
0
5
)
=
⊙
(
(
φ
0
⊙
φ
3
)
⊗
(
φ
2
⊙
φ
5
)
)
,
f
(
i
,
j
)
3
(
φ
0
5
)
=
(
φ
0
⊙
φ
3
)
⊙
(
(
φ
1
⊙
φ
4
)
⊗
(
φ
2
⊙
φ
5
)
)
.That is to say, with the probability messages modifying factors, the new probability messages update equations will be written as(11)
p
I
L
(
i
,
2
j
)
t
=
(
(
p
O
L
(
i
,
2
j
)
t
-
1
⊙
γ
L
0
(
i
,
j
)
t
)
⊗
(
p
O
L
(
i
,
2
j
+
1
)
t
-
1
⊙
γ
L
1
(
i
,
j
)
t
)
)
p
I
L
(
i
,
2
j
)
t
=
⊙
(
(
p
O
L
(
i
,
2
j
)
t
-
1
⊙
γ
L
0
(
i
,
j
)
t
)
p
I
L
(
i
,
2
j
)
t
=
⊗
(
p
I
R
(
i
,
2
j
+
1
)
t
-
1
⊙
γ
L
2
(
i
,
j
)
t
)
)
,
p
I
L
(
i
,
2
j
+
1
)
t
=
(
p
O
L
(
i
,
2
j
+
1
)
t
-
1
⊙
γ
L
3
(
i
,
j
)
t
)
p
I
L
(
i
,
2
j
)
t
=
h
⊙
(
(
p
O
L
(
i
,
2
j
)
t
-
1
⊙
γ
L
4
(
i
,
j
)
t
)
p
I
L
(
i
,
2
j
)
t
=
h
⊗
(
p
I
R
(
i
,
2
j
)
t
-
1
⊙
γ
L
5
(
i
,
j
)
t
)
)
,
p
O
R
(
i
,
2
j
)
t
=
(
(
p
I
R
(
i
,
2
j
)
t
-
1
⊙
γ
R
0
(
i
,
j
)
t
)
⊗
(
p
I
R
(
i
,
2
j
+
1
)
t
-
1
⊙
γ
R
1
(
i
,
j
)
t
)
)
p
I
L
(
i
,
2
j
)
t
=
⊙
(
(
p
I
R
(
i
,
2
j
)
t
-
1
⊙
γ
R
0
(
i
,
j
)
t
)
p
I
L
(
i
,
2
j
)
t
=
⊗
(
p
O
L
(
i
,
2
j
+
1
)
t
-
1
⊙
γ
R
2
(
i
,
j
)
t
)
)
,
p
O
R
(
i
,
2
j
+
1
)
t
=
(
p
I
R
(
i
,
2
j
+
1
)
t
-
1
⊙
γ
R
3
(
i
,
j
)
t
)
p
I
L
(
i
,
2
j
)
t
=
hh
⊙
(
(
p
I
R
(
i
,
2
j
)
t
-
1
⊙
γ
R
4
(
i
,
j
)
t
)
p
I
L
(
i
,
2
j
)
t
=
hh
⊗
(
p
O
L
(
i
,
2
j
)
t
-
1
⊙
γ
R
5
(
i
,
j
)
t
)
)
.Next, our task is to determine the optimal probability messages modifying factors, that is,γ
L
0
(
i
,
j
)
t
,
…
,
γ
L
5
(
i
,
j
)
t and γ
R
0
(
i
,
j
)
t
,
…
,
γ
R
5
(
i
,
j
)
t, so as to achieve the best performance.


### 4.2. Probability Modifying Factors Optimization

In practice, due to the input of frozen bits [1], there exists some so-called frozen nodes in the decoder, and values of these nodes are determined and independent of the decoding algorithm. Hence, if the decoding is correct, the probability messages of a frozen node v
I
(
i
,
j
) or v
O
(
i
,
j
) (the determined value of frozen nodes is 0) must satisfy the condition of
(12)
p
I
L
(
i
,
j
)
t
(
0
)
>
p
I
L
(
i
,
j
)
t
(
1
)
p
I
R
(
i
,
j
)
t
(
0
)
>
p
I
R
(
i
,
j
)
t
(
1
)
or
p
O
L
(
i
,
j
)
t
(
0
)
>
p
O
L
(
i
,
j
)
t
(
1
)
p
O
R
(
i
,
j
)
t
(
0
)
>
p
O
R
(
i
,
j
)
t
(
1
)
.
While in practice, due to the noise of received signal, there may exist some frozen nodes unsatisfied the reliability condition. Therefore, in order to improve the accuracy of decoding, it is needed to find the optimal probability messages modifying factors such that all the frozen nodes could always satisfy the conditions of (12) during the procedure of BP decoding.To achieve above goal, we introduce a pair parameters to each node in the decoder, which are calledleft and right reliability degrees. And for a node v
I
(
i
,
j
) (similar to v
O
(
i
,
j
)), the left and right reliability degrees are denoted as ζ
I
L
(
i
,
j
)
t and ζ
I
R
(
i
,
j
)
t, respectively. Where if v
I
(
i
,
j
) is a frozen node, we can get ζ
I
L
(
i
,
j
)
t and ζ
I
R
(
i
,
j
)
t by
(13)
ζ
I
L
(
i
,
j
)
t
=
p
I
L
(
i
,
j
)
t
(
0
)
p
I
L
(
i
,
j
)
t
(
1
)
,
ζ
I
R
(
i
,
j
)
t
=
p
I
R
(
i
,
j
)
t
(
0
)
p
I
R
(
i
,
j
)
t
(
1
)
;
otherwise, the values of ζ
I
L
(
i
,
j
)
t and ζ
I
R
(
i
,
j
)
t will be given by
(14)
ζ
I
L
(
i
,
j
)
t
=
p
I
L
(
i
,
j
)
t
(
0
)
p
I
L
(
i
,
j
)
t
(
1
)
,
ζ
I
R
(
i
,
j
)
t
=
p
I
R
(
i
,
j
)
t
(
0
)
p
I
R
(
i
,
j
)
t
(
1
)
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
p
I
L
(
i
,
j
)
(
0
)
p
I
L
(
i
,
j
)
(
1
)
>
1
ζ
I
L
(
i
,
j
)
t
=
p
I
L
(
i
,
j
)
t
(
1
)
p
I
L
(
i
,
j
)
t
(
0
)
,
ζ
I
R
(
i
,
j
)
t
=
p
I
R
(
i
,
j
)
t
(
1
)
p
I
R
(
i
,
j
)
t
(
0
)
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
otherwise
,
where ζ
I
L
(
i
,
j
)
t
>
1 and ζ
I
R
(
i
,
j
)
t
>
1.The reliability degrees indicate the reliability of the node’s decision value, and the larger reliability degree, the higher reliability of that value. Specially, when there is no noise in the channel, the reliability degrees of a node will approach to infinity. Based on previous observations, the problem of getting the optimal probability messages modifying factors can be formulated as an optimization problem to maximize the reliability degrees of all the node in decoder, while the target function is written as(15)
arg
max
⁡
0
≤
γ
L
0
(
i
,
k
)
t
,
…
,
γ
L
5
(
i
,
k
)
t
≤
1
0
≤
γ
R
0
(
i
,
k
)
t
,
…
,
γ
R
5
(
i
,
k
)
t
≤
1
⁡
{
∑
i
=
0
log
⁡
2
N
‍
∑
j
=
0
N
‍
(
ζ
I
L
(
i
,
j
)
t
+
ζ
I
R
(
i
,
j
)
t
)
}
s
.
t
.
γ
L
0
(
i
,
k
)
t
(
0
)
+
γ
L
0
(
i
,
k
)
t
(
1
)
=
1
⋮
γ
L
5
(
i
,
k
)
t
(
0
)
+
γ
L
5
(
i
,
k
)
t
(
1
)
=
1
γ
R
0
(
i
,
k
)
t
(
0
)
+
γ
R
0
(
i
,
k
)
t
(
1
)
=
1
⋮
γ
R
5
(
i
,
k
)
t
(
0
)
+
γ
R
5
(
i
,
k
)
t
(
1
)
=
1
,
where ζ
I
L
(
i
,
j
)
t and ζ
I
R
(
i
,
j
)
t are decided by (11) and (13)-(14), and k is the integral value of j
/
2; that is, k
=
⌊
j
/
2
⌋.


### 4.3. Problem Solving Based on Modified PSO Algorithm

Based on (15), we have formulated the problem to find the optimal probability modifying factors, and in this subsection, we will consider the solution of the problem so as to get the optimized BP decoding algorithm.Among the different global optimizers, particle swarm optimization (PSO) has demonstrated its usefulness as an optimizer capable of finding global optimum. The idea of PSO is based on simulation of simplified social models such as birds flocking and fish schooling. Like other stochastic evolutionary algorithms, PSO is independent of mathematical characteristics of objective problems. However, unlike these algorithms, with PSO, each particle has its own unique memory to “remember” its own best solution. Thus, each particle has its own “idea” of whether it has found the optimum. However, in other algorithms, previous knowledge of the problem will be destroyed once the population changes. PSO has attracted increasing attention because of its simple concept, easy implementation, and quick. These advantages allow it to be applied successfully in a variety of fields, mainly for unconstrained continuous optimization problems [19–26]. Therefore, in this work, we explore the PSO algorithm with certain modification based on particle fitness evaluation to solve the problem (15).To present our modified PSO algorithm, we first introduce some preliminary definitions and concepts used in the operation of the PSO algorithm, which is described as follows.(1)  Parameters Definitions. We consider a swarm of L particles, {
z
→
0
,
…
,
z
→
L
-
1
}, where the position of z
→
i
=
(
z
i
0
,
z
i
1
,
…
,
z
i
(
T
-
1
)
) represents a possible solution point of those probability modifying factors in the problem (15), 0
≤
i
≤
L
-
1, and T is the number of the probability modifying factors. Each element of z
→
i is the value of a probability modifying factor; that is, 0
≤
z
i
j
≤
1, 0
≤
j
≤
T
-
1. Based on the work of [19], the position of particle z
→
i can be updated by
(16)
z
→
i
t
+
1
=
z
→
i
t
+
w
→
i
t
+
1
.
In (16), the pseudovelocity w
→
i
t
+
1 is calculated as follows:
(17)
w
→
i
t
+
1
=
ω
t
w
→
i
t
+
c
1
r
1
(
p
→
i
-
z
→
i
t
)
+
c
2
r
2
(
p
→
g
-
z
→
i
t
)
,
where ω
t is particle inertia, t indicates the iteration number, p
→
i represents the best ever position of particle i at iteration t, and p
→
g represents the global best position in the swarm at iteration t. r
1 and r
2 represent uniform random numbers between 0 and 1. It is proven in [19] that, when c
1
=
c
2
=
2, the products, c
1
r
1 or c
2
r
2, have a mean of 1.(2)  Fitness Evaluation. In general, with the parameter definitions aforementioned, we can get the global optimal solution of a optimization problem. However, in problem (15), the situation will be different, because during the procedure of the BP decoding for polar codes, a node’s probability messages calculated on the basis of the probability modifying factors must satisfy the conditions of (12) or (14). In order to check these conditions during the decoding, we further define two functions as
(18)
g
1
(
z
→
i
t
)
=
|
𝕍
F
e
|
|
𝕍
F
|
,
g
2
(
z
→
i
t
)
=
|
𝕍
I
e
|
|
𝕍
I
|
,
where 𝕍
F is the frozen nodes set of the decoder, and 𝕍
F
e is the set of frozen nodes whose probability messages based on z
→
i
t do not satisfy the condition of (12). Similarly, 𝕍
I is the nonfrozen nodes set of the decoder, and 𝕍
I
e is the set of nonfrozen nodes whose left and right reliability degrees based on z
→
i
t do not satisfy (14). Furthermore, we have g
1
(
z
→
i
t
)
,
g
2
(
z
→
i
t
)
∈
[
0,1
]. Based on (18), we can evaluate the fitness of a particle’s current position so as to accelerate the finding of the the optimal solution. After the checking of conditions of (12) and (14), we further get the fitness value h
i
t of a particle by
(19)
h
i
t
(
z
→
i
t
)
=
∑
k
=
0
log
⁡
2
N
‍
∑
j
=
0
N
‍
(
ζ
I
L
(
k
,
j
)
t
+
ζ
I
R
(
k
,
j
)
t
)
.As the summarization of previous description, we now provide the whole procedure of the proposed BP decoding algorithm based on PSO optimization with the form of pseudocode, as shown in Algorithm1.Algorithm 1:BP decoding algorithm based on modified PSO optimization.
Input:
The stopping parametersϵ
1 and ϵ
2;
The frozen nodes set,𝕍
F;
The probability messages of the input nodes of the decoder,{
W
(
y
0
∣
x
0
)
,
…
,
W
(
y
N
-
1
∣
x
N
-
1
)
};
Output:
The decoded source binary vector,u
^
0
N
-
1;
(1)   Initialize the parameters used in the PSO algorithm, including particles initial set{
z
→
0
0
,
…
,
z
→
L
-
1
0
},
the pseudovelocities{
w
→
0
0
,
…
,
w
→
L
-
1
0
}, particle inertia ω
0, maximum iteration number and c
1, c
2;
(2)while (Stopping criterion is not satisfied) do
(3)     Update particle pseudovelocity vectorw
→
i
t
+
1 using (17);
(4)    Update particle position vectorz
→
i
t
+
1 using (16);
(5)    Calculate the probability messages of each nodes in the decoder using (11);
(6)if  g
1
(
z
→
i
t
+
1
)
>
ϵ
1 and g
2
(
z
→
i
t
+
1
)
>
ϵ
2  then
(7)     Calculate the fitness valueh
i
t
+
1 using (19);
(8)if  h
i
t
+
1
≥
h
i
b
e
s
t  then
(9)h
i
b
e
s
t
=
h
i
t
+
1, p
→
i
=
z
→
i
t
+
1;
(10)end if
(11)if  h
i
t
+
1
≥
h
g
b
e
s
t  then
(12)h
g
b
e
s
t
=
h
i
t
+
1, p
→
g
=
z
→
i
t
+
1;
(13)end if
(14)end if
(15)end while
(16) Output the decoded source binary vector by hard decision of the output nodes of the decoder;
(17)return  ℂ;It is noticed form Algorithm1 that the steps 2–15 are the key of the algorithm. The main consideration of these steps is based on the following two observations. On the one hand, if there is no noise in the channel, the BP decoding of the polar codes will be errorless, which means that all the nodes in the decoder will satisfy the condition of (12); that is, g
1
(
z
→
i
t
) and g
1
(
z
→
i
t
) are both equal to 0. However, in practice, this case is impossible to happen due to the noise of channel; hence, we introduce two stopping parameters ϵ
1 and ϵ
2 for g
1
(
z
→
i
t
) and g
1
(
z
→
i
t
). Since the values of the frozen nodes are known to the decoder, we set ϵ
2 to 0. To ensure that the correction of the decoding, ϵ
1 should be as small as possible, such that when a particle z
→
i
t is found to make g
1
(
z
→
i
t
+
1
)
≤
ϵ
1 and g
2
(
z
→
i
t
+
1
)
≤
ϵ
2 both true, which indicates that stopping criterion is satisfied, the loop of (
2
)
–
(
15
) can be stopped. On the other hand, when there exist multiparticles that make the stopping criterion satisfied, we can choose the one which can generate maximum fitness value to be our final solution, as shown in steps (
11
)
–
(
13
).


## 4.1. Messages Update Functions

It is noticed from (4) and (6)–(8) that, in order to enhance the reliability of messages propagation, it is important to determine the appropriate messages update functions for the generalization BP decoding algorithm. However, in general, it is difficult to find the optimal messages update functions; therefore, in this work, the messages update functions are introduced by the analysis of the construction of polar encoding. And based on (1), we have
(9)
v
I
(
i
,
2
j
)
=
v
O
(
i
,
2
j
)
⊕
v
O
(
i
,
2
j
+
1
)
=
v
O
(
i
,
2
j
)
⊕
v
I
(
i
,
2
j
+
1
)
,
v
I
(
i
,
2
j
+
1
)
=
v
O
(
i
,
2
j
+
1
)
=
v
O
(
i
,
2
j
)
⊕
v
I
(
i
,
2
j
)
,
v
O
(
i
,
2
j
)
=
v
I
(
i
,
2
j
)
⊕
v
I
(
i
,
2
j
+
1
)
=
v
I
(
i
,
2
j
)
⊕
v
O
(
i
,
2
j
+
1
)
,
v
O
(
i
,
2
j
+
1
)
=
v
I
(
i
,
2
j
+
1
)
=
v
I
(
i
,
2
j
)
⊕
v
O
(
i
,
2
j
)
.Therefore, based on the error coding theory and (9), we can get the messages update functions as
(10)
f
(
i
,
j
)
0
(
φ
0
5
)
=
(
(
φ
0
⊙
φ
3
)
⊗
(
φ
1
⊙
φ
4
)
)
f
(
i
,
j
)
0
(
φ
0
5
)
=
⊙
(
(
φ
0
⊙
φ
3
)
⊗
(
φ
2
⊙
φ
5
)
)
,
f
(
i
,
j
)
1
(
φ
0
5
)
=
(
φ
0
⊙
φ
3
)
⊙
(
(
φ
1
⊙
φ
4
)
⊗
(
φ
2
⊙
φ
5
)
)
,
f
(
i
,
j
)
2
(
φ
0
5
)
=
(
(
φ
0
⊙
φ
3
)
⊗
(
φ
1
⊙
φ
4
)
)
f
(
i
,
j
)
0
(
φ
0
5
)
=
⊙
(
(
φ
0
⊙
φ
3
)
⊗
(
φ
2
⊙
φ
5
)
)
,
f
(
i
,
j
)
3
(
φ
0
5
)
=
(
φ
0
⊙
φ
3
)
⊙
(
(
φ
1
⊙
φ
4
)
⊗
(
φ
2
⊙
φ
5
)
)
.That is to say, with the probability messages modifying factors, the new probability messages update equations will be written as(11)
p
I
L
(
i
,
2
j
)
t
=
(
(
p
O
L
(
i
,
2
j
)
t
-
1
⊙
γ
L
0
(
i
,
j
)
t
)
⊗
(
p
O
L
(
i
,
2
j
+
1
)
t
-
1
⊙
γ
L
1
(
i
,
j
)
t
)
)
p
I
L
(
i
,
2
j
)
t
=
⊙
(
(
p
O
L
(
i
,
2
j
)
t
-
1
⊙
γ
L
0
(
i
,
j
)
t
)
p
I
L
(
i
,
2
j
)
t
=
⊗
(
p
I
R
(
i
,
2
j
+
1
)
t
-
1
⊙
γ
L
2
(
i
,
j
)
t
)
)
,
p
I
L
(
i
,
2
j
+
1
)
t
=
(
p
O
L
(
i
,
2
j
+
1
)
t
-
1
⊙
γ
L
3
(
i
,
j
)
t
)
p
I
L
(
i
,
2
j
)
t
=
h
⊙
(
(
p
O
L
(
i
,
2
j
)
t
-
1
⊙
γ
L
4
(
i
,
j
)
t
)
p
I
L
(
i
,
2
j
)
t
=
h
⊗
(
p
I
R
(
i
,
2
j
)
t
-
1
⊙
γ
L
5
(
i
,
j
)
t
)
)
,
p
O
R
(
i
,
2
j
)
t
=
(
(
p
I
R
(
i
,
2
j
)
t
-
1
⊙
γ
R
0
(
i
,
j
)
t
)
⊗
(
p
I
R
(
i
,
2
j
+
1
)
t
-
1
⊙
γ
R
1
(
i
,
j
)
t
)
)
p
I
L
(
i
,
2
j
)
t
=
⊙
(
(
p
I
R
(
i
,
2
j
)
t
-
1
⊙
γ
R
0
(
i
,
j
)
t
)
p
I
L
(
i
,
2
j
)
t
=
⊗
(
p
O
L
(
i
,
2
j
+
1
)
t
-
1
⊙
γ
R
2
(
i
,
j
)
t
)
)
,
p
O
R
(
i
,
2
j
+
1
)
t
=
(
p
I
R
(
i
,
2
j
+
1
)
t
-
1
⊙
γ
R
3
(
i
,
j
)
t
)
p
I
L
(
i
,
2
j
)
t
=
hh
⊙
(
(
p
I
R
(
i
,
2
j
)
t
-
1
⊙
γ
R
4
(
i
,
j
)
t
)
p
I
L
(
i
,
2
j
)
t
=
hh
⊗
(
p
O
L
(
i
,
2
j
)
t
-
1
⊙
γ
R
5
(
i
,
j
)
t
)
)
.Next, our task is to determine the optimal probability messages modifying factors, that is,γ
L
0
(
i
,
j
)
t
,
…
,
γ
L
5
(
i
,
j
)
t and γ
R
0
(
i
,
j
)
t
,
…
,
γ
R
5
(
i
,
j
)
t, so as to achieve the best performance.


## 4.2. Probability Modifying Factors Optimization

In practice, due to the input of frozen bits [1], there exists some so-called frozen nodes in the decoder, and values of these nodes are determined and independent of the decoding algorithm. Hence, if the decoding is correct, the probability messages of a frozen node v
I
(
i
,
j
) or v
O
(
i
,
j
) (the determined value of frozen nodes is 0) must satisfy the condition of
(12)
p
I
L
(
i
,
j
)
t
(
0
)
>
p
I
L
(
i
,
j
)
t
(
1
)
p
I
R
(
i
,
j
)
t
(
0
)
>
p
I
R
(
i
,
j
)
t
(
1
)
or
p
O
L
(
i
,
j
)
t
(
0
)
>
p
O
L
(
i
,
j
)
t
(
1
)
p
O
R
(
i
,
j
)
t
(
0
)
>
p
O
R
(
i
,
j
)
t
(
1
)
.
While in practice, due to the noise of received signal, there may exist some frozen nodes unsatisfied the reliability condition. Therefore, in order to improve the accuracy of decoding, it is needed to find the optimal probability messages modifying factors such that all the frozen nodes could always satisfy the conditions of (12) during the procedure of BP decoding.To achieve above goal, we introduce a pair parameters to each node in the decoder, which are calledleft and right reliability degrees. And for a node v
I
(
i
,
j
) (similar to v
O
(
i
,
j
)), the left and right reliability degrees are denoted as ζ
I
L
(
i
,
j
)
t and ζ
I
R
(
i
,
j
)
t, respectively. Where if v
I
(
i
,
j
) is a frozen node, we can get ζ
I
L
(
i
,
j
)
t and ζ
I
R
(
i
,
j
)
t by
(13)
ζ
I
L
(
i
,
j
)
t
=
p
I
L
(
i
,
j
)
t
(
0
)
p
I
L
(
i
,
j
)
t
(
1
)
,
ζ
I
R
(
i
,
j
)
t
=
p
I
R
(
i
,
j
)
t
(
0
)
p
I
R
(
i
,
j
)
t
(
1
)
;
otherwise, the values of ζ
I
L
(
i
,
j
)
t and ζ
I
R
(
i
,
j
)
t will be given by
(14)
ζ
I
L
(
i
,
j
)
t
=
p
I
L
(
i
,
j
)
t
(
0
)
p
I
L
(
i
,
j
)
t
(
1
)
,
ζ
I
R
(
i
,
j
)
t
=
p
I
R
(
i
,
j
)
t
(
0
)
p
I
R
(
i
,
j
)
t
(
1
)
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
p
I
L
(
i
,
j
)
(
0
)
p
I
L
(
i
,
j
)
(
1
)
>
1
ζ
I
L
(
i
,
j
)
t
=
p
I
L
(
i
,
j
)
t
(
1
)
p
I
L
(
i
,
j
)
t
(
0
)
,
ζ
I
R
(
i
,
j
)
t
=
p
I
R
(
i
,
j
)
t
(
1
)
p
I
R
(
i
,
j
)
t
(
0
)
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
otherwise
,
where ζ
I
L
(
i
,
j
)
t
>
1 and ζ
I
R
(
i
,
j
)
t
>
1.The reliability degrees indicate the reliability of the node’s decision value, and the larger reliability degree, the higher reliability of that value. Specially, when there is no noise in the channel, the reliability degrees of a node will approach to infinity. Based on previous observations, the problem of getting the optimal probability messages modifying factors can be formulated as an optimization problem to maximize the reliability degrees of all the node in decoder, while the target function is written as(15)
arg
max
⁡
0
≤
γ
L
0
(
i
,
k
)
t
,
…
,
γ
L
5
(
i
,
k
)
t
≤
1
0
≤
γ
R
0
(
i
,
k
)
t
,
…
,
γ
R
5
(
i
,
k
)
t
≤
1
⁡
{
∑
i
=
0
log
⁡
2
N
‍
∑
j
=
0
N
‍
(
ζ
I
L
(
i
,
j
)
t
+
ζ
I
R
(
i
,
j
)
t
)
}
s
.
t
.
γ
L
0
(
i
,
k
)
t
(
0
)
+
γ
L
0
(
i
,
k
)
t
(
1
)
=
1
⋮
γ
L
5
(
i
,
k
)
t
(
0
)
+
γ
L
5
(
i
,
k
)
t
(
1
)
=
1
γ
R
0
(
i
,
k
)
t
(
0
)
+
γ
R
0
(
i
,
k
)
t
(
1
)
=
1
⋮
γ
R
5
(
i
,
k
)
t
(
0
)
+
γ
R
5
(
i
,
k
)
t
(
1
)
=
1
,
where ζ
I
L
(
i
,
j
)
t and ζ
I
R
(
i
,
j
)
t are decided by (11) and (13)-(14), and k is the integral value of j
/
2; that is, k
=
⌊
j
/
2
⌋.


## 4.3. Problem Solving Based on Modified PSO Algorithm

Based on (15), we have formulated the problem to find the optimal probability modifying factors, and in this subsection, we will consider the solution of the problem so as to get the optimized BP decoding algorithm.Among the different global optimizers, particle swarm optimization (PSO) has demonstrated its usefulness as an optimizer capable of finding global optimum. The idea of PSO is based on simulation of simplified social models such as birds flocking and fish schooling. Like other stochastic evolutionary algorithms, PSO is independent of mathematical characteristics of objective problems. However, unlike these algorithms, with PSO, each particle has its own unique memory to “remember” its own best solution. Thus, each particle has its own “idea” of whether it has found the optimum. However, in other algorithms, previous knowledge of the problem will be destroyed once the population changes. PSO has attracted increasing attention because of its simple concept, easy implementation, and quick. These advantages allow it to be applied successfully in a variety of fields, mainly for unconstrained continuous optimization problems [19–26]. Therefore, in this work, we explore the PSO algorithm with certain modification based on particle fitness evaluation to solve the problem (15).To present our modified PSO algorithm, we first introduce some preliminary definitions and concepts used in the operation of the PSO algorithm, which is described as follows.(1)  Parameters Definitions. We consider a swarm of L particles, {
z
→
0
,
…
,
z
→
L
-
1
}, where the position of z
→
i
=
(
z
i
0
,
z
i
1
,
…
,
z
i
(
T
-
1
)
) represents a possible solution point of those probability modifying factors in the problem (15), 0
≤
i
≤
L
-
1, and T is the number of the probability modifying factors. Each element of z
→
i is the value of a probability modifying factor; that is, 0
≤
z
i
j
≤
1, 0
≤
j
≤
T
-
1. Based on the work of [19], the position of particle z
→
i can be updated by
(16)
z
→
i
t
+
1
=
z
→
i
t
+
w
→
i
t
+
1
.
In (16), the pseudovelocity w
→
i
t
+
1 is calculated as follows:
(17)
w
→
i
t
+
1
=
ω
t
w
→
i
t
+
c
1
r
1
(
p
→
i
-
z
→
i
t
)
+
c
2
r
2
(
p
→
g
-
z
→
i
t
)
,
where ω
t is particle inertia, t indicates the iteration number, p
→
i represents the best ever position of particle i at iteration t, and p
→
g represents the global best position in the swarm at iteration t. r
1 and r
2 represent uniform random numbers between 0 and 1. It is proven in [19] that, when c
1
=
c
2
=
2, the products, c
1
r
1 or c
2
r
2, have a mean of 1.(2)  Fitness Evaluation. In general, with the parameter definitions aforementioned, we can get the global optimal solution of a optimization problem. However, in problem (15), the situation will be different, because during the procedure of the BP decoding for polar codes, a node’s probability messages calculated on the basis of the probability modifying factors must satisfy the conditions of (12) or (14). In order to check these conditions during the decoding, we further define two functions as
(18)
g
1
(
z
→
i
t
)
=
|
𝕍
F
e
|
|
𝕍
F
|
,
g
2
(
z
→
i
t
)
=
|
𝕍
I
e
|
|
𝕍
I
|
,
where 𝕍
F is the frozen nodes set of the decoder, and 𝕍
F
e is the set of frozen nodes whose probability messages based on z
→
i
t do not satisfy the condition of (12). Similarly, 𝕍
I is the nonfrozen nodes set of the decoder, and 𝕍
I
e is the set of nonfrozen nodes whose left and right reliability degrees based on z
→
i
t do not satisfy (14). Furthermore, we have g
1
(
z
→
i
t
)
,
g
2
(
z
→
i
t
)
∈
[
0,1
]. Based on (18), we can evaluate the fitness of a particle’s current position so as to accelerate the finding of the the optimal solution. After the checking of conditions of (12) and (14), we further get the fitness value h
i
t of a particle by
(19)
h
i
t
(
z
→
i
t
)
=
∑
k
=
0
log
⁡
2
N
‍
∑
j
=
0
N
‍
(
ζ
I
L
(
k
,
j
)
t
+
ζ
I
R
(
k
,
j
)
t
)
.As the summarization of previous description, we now provide the whole procedure of the proposed BP decoding algorithm based on PSO optimization with the form of pseudocode, as shown in Algorithm1.Algorithm 1:BP decoding algorithm based on modified PSO optimization.
Input:
The stopping parametersϵ
1 and ϵ
2;
The frozen nodes set,𝕍
F;
The probability messages of the input nodes of the decoder,{
W
(
y
0
∣
x
0
)
,
…
,
W
(
y
N
-
1
∣
x
N
-
1
)
};
Output:
The decoded source binary vector,u
^
0
N
-
1;
(1)   Initialize the parameters used in the PSO algorithm, including particles initial set{
z
→
0
0
,
…
,
z
→
L
-
1
0
},
the pseudovelocities{
w
→
0
0
,
…
,
w
→
L
-
1
0
}, particle inertia ω
0, maximum iteration number and c
1, c
2;
(2)while (Stopping criterion is not satisfied) do
(3)     Update particle pseudovelocity vectorw
→
i
t
+
1 using (17);
(4)    Update particle position vectorz
→
i
t
+
1 using (16);
(5)    Calculate the probability messages of each nodes in the decoder using (11);
(6)if  g
1
(
z
→
i
t
+
1
)
>
ϵ
1 and g
2
(
z
→
i
t
+
1
)
>
ϵ
2  then
(7)     Calculate the fitness valueh
i
t
+
1 using (19);
(8)if  h
i
t
+
1
≥
h
i
b
e
s
t  then
(9)h
i
b
e
s
t
=
h
i
t
+
1, p
→
i
=
z
→
i
t
+
1;
(10)end if
(11)if  h
i
t
+
1
≥
h
g
b
e
s
t  then
(12)h
g
b
e
s
t
=
h
i
t
+
1, p
→
g
=
z
→
i
t
+
1;
(13)end if
(14)end if
(15)end while
(16) Output the decoded source binary vector by hard decision of the output nodes of the decoder;
(17)return  ℂ;It is noticed form Algorithm1 that the steps 2–15 are the key of the algorithm. The main consideration of these steps is based on the following two observations. On the one hand, if there is no noise in the channel, the BP decoding of the polar codes will be errorless, which means that all the nodes in the decoder will satisfy the condition of (12); that is, g
1
(
z
→
i
t
) and g
1
(
z
→
i
t
) are both equal to 0. However, in practice, this case is impossible to happen due to the noise of channel; hence, we introduce two stopping parameters ϵ
1 and ϵ
2 for g
1
(
z
→
i
t
) and g
1
(
z
→
i
t
). Since the values of the frozen nodes are known to the decoder, we set ϵ
2 to 0. To ensure that the correction of the decoding, ϵ
1 should be as small as possible, such that when a particle z
→
i
t is found to make g
1
(
z
→
i
t
+
1
)
≤
ϵ
1 and g
2
(
z
→
i
t
+
1
)
≤
ϵ
2 both true, which indicates that stopping criterion is satisfied, the loop of (
2
)
–
(
15
) can be stopped. On the other hand, when there exist multiparticles that make the stopping criterion satisfied, we can choose the one which can generate maximum fitness value to be our final solution, as shown in steps (
11
)
–
(
13
).


## 5. Numerical Results

In this section, Monte Carlo simulation is provided to show the performance of the proposed decoding algorithm. In the simulation, the BPSK modulation and the additive white Gaussian noise (AWGN) channel are assumed. The code length isN
=
2
3
=
8, code rate R is 0.5, and the index of the information bits is the same as [1].As it is shown in Figure5, the proposed decoding algorithm based on PSO achieves better bit error rate (BER, defined as as the ratio of error decoding bits to the total decoding bits) performance than that of the existing BP decoding. Particularly, in the low region of signal to noise ratio (SNR), that is, E
b
/
N
0 (E
b is the average power of one bit and N
0 is the average value of the noise power spectrum density) the proposed algorithm provides a higher SNR advantage; for example, when the BER is 1
0
-
3, the proposed decoding algorithm provides SNR advantages of 0.9 dB, and when the BER is 1
0
-
4, the SNR advantages are 0.6 dB. Hence, we can conclude that with the proposed generalization BP decoding and PSO, performance of the belief propagation decoding algorithm for polar codes could be improved.Figure 5
Comparison of BER between the proposed and existing BP decoding algorithms for polar codes with(
4,8
). The maximum iteration number is set to 60.Additionally, one important thing to note is that, since the proposed algorithm is implemented depending on the probability messages modifying factors, while values of these factors are optimized by the PSO algorithm. Hence, the time complexity of the existing BP decoding is lower than that of the proposed decoding, which is tightly depending on the convergence time of the PSO algorithm. And the work for the time complexity optimization of the proposed algorithm will be conducted in our future research.


## 6. Conclusion

In this work, we proposed a generalization belief propagation (BP) decoding algorithm based on particle swarm optimization (PSO) to improve the performance of the polar codes. Through the analysis of the existing BP decoding algorithm for polar codes, we first introduced a probability modifying factor to each node of the BP decoder so as to enhance the error-correcting capacity of the BP decoding. Then, we generalized the BP decoding algorithm based on these modifying factors and drive the probability update equations for the proposed generalization BP decoding. Based on these new probability update equations, we further proved the intrinsic relationship of the existing decoding algorithms. Finally, in order to achieve the best performance, we formulated an optimization problem to find the optimal probability modifying factors for the proposed generalization BP decoding. Furthermore, a method based on the modified PSO algorithm was also introduced to solve the optimization problem. Numerical results showed that the proposed generalization BP decoding algorithm achieved better performance than that of the existing decoding, which suggested the effectiveness of the proposed decoding algorithm.



---

*Source: 606913-2014-05-13.xml*