An optimized encoding algorithm for systematic polar codes

Polar codes proposed by Arikan [1] can theoretically reach the Shannon limit. It has been widely given attention in the communication field because of its low complexity and good decoding performance. As early as 2008, Arikan proposed the concept of channel polarization and carried out a rigorous mathematical proof [2]. For the selection of information bits of polar codes, there are some patterns, such as Bhattacharyya parameters [3] and density evolution [4]. The hardware implementations of the traditional non-systematic polar code (NSPC) encoding were introduced [5‐7]. However, the complexity and computing resources were significantly consumed when fully utilizing the generator matrix of the polar codes to design the hardware structure. Hoyoung et al. [8] proposed partially parallel encoder structure that can reduce latency. However, the resource consumption increased due to the length of the polar codes. Compared to NSPC, the SPC proposed by Arikan [9] outperformed them in the bit error rate. Vangala et al. [10] proposed three encoding algorithms and used the recursion method to find a suitable equilibrium between a memory cell and a computing unit. Chen et al. [11] improved the encoding algorithms designed by Vangala et al. [10] to simplify the storage patterns for SPC. In [12], Sarkis et al. introduced SPC and developed a hardware structure of the decoder. The improved hardware structure increased the throughput of the polar decoder. When the hardware was implemented [13], the input and output ports were exchanged to obtain the SPC encoder based on the NSPC encoder. However, the latency and resource consumption were twice than that of the hardware implementation with NSPC. Wang et al. found a method that utilized the property of parity check matrix to reduce the computational units [14‐16]. This approach can be utilized for both SPC and NSPC to reduce computational units. By studying the encoding flow graph of SPC, we found out that some of computational units can be omitted. This omission is determined by the encoding structure and the exclusive Or (XOR) operations.

The rest sections of this paper are organized as follows. The comparisons between SPC and NSPC are introduced in Section 2. The existing encoding algorithms of SPC are reviewed in Section 3. Our simplified process to use XOR operations is also discussed in this section. The distribution rule of information bits, definition of variables, and the lemma proof are shown in Section 4. The case study of our optimized encoding algorithm (OEA) matrix transformation is presented in Section 5. Results and analysis are discussed in Section 6. Conclusions are found in Section 7.

Based on the channel polarization theory, the length of polar codes is N = 2ⁿ, n ≥ 1, where n is a positive integer. Let A represent the set of the indices of the information bits. The code rate is R = K/N, where K represents the length of information bits and is the number of the elements in a set of A. Information bits selection is determined by Bhattacharyya parameters [17]. Let Ac represent the complement of a set of A. The index set Ac = {0,1,…,N − 1} − A is for the frozen bits, and the length of Ac is N − K. u = (u₀, u₁, ⋯, u_N − 1) represents the message vector, where u_i denotes an arbitrary element of the vector of u. x = (x₀, x₁, ⋯, x_N − 1) represents a codeword vector, where x_i indicates a random component in the vector of x. The generator matrix G_N is defined as

where ⊗ denotes Kronecker power operation, n = log₂(N), and F denotes two-dimensional matrix F = [1, 0; 1, 1]. Applying the property of Kronecker product, we can construct a generator matrix as

The codeword vector of x for NSPC can be represented by the encoding Eq. (1)

where GA is a submatrix of GN, and it is constructed by the rows of indices in A. GAc is a submatrix of GN and is constructed by the rows of indices in Ac. uA = (ui: i∈A), uA⊆u and uAc = (uj: j∈Ac), uAc⊆u, and uAc = u − uA. The symbol of ⊕ represents a mod-2 addition or a logical XOR operation in the binary domain.

Arikan [9] first proposed the mathematical formula shown in Eqs. (4) and (5) for SPC:

where G_AA denotes the submatrix of G_N consisting of the array of elements (G_i,j) with i∈A, j∈A, and G_AA = (G_i,j: i∈A, j∈A). Similarly for the other submatrices of G_AcA = (G_i,j: i∈Ac, j∈A), G_AAc = (G_i,j: i∈A, j∈Ac), and G_AcAc = (G_i,j: i∈Ac, j∈Ac). There is the same denotation for x_A = (x_i: i∈A) and x_Ac = (x_j: j∈Ac). If the matrix G_AA is invertible and the inputs to SPC encoder are u_Ac and x_A, then the output x_Ac from the SPC encoder is

Consider that the decoding results are not affected by the value of frozen bits [1], we can simplify the encoding procedure by setting zero values to all frozen bits, namely u_Ac = (u_i = 0: i∈Ac). Then, x_Ac in Eq. (6) can be simplified to

where G_AA⁻¹ is a lower triangular matrix with ones on the diagonal and the submatrix of G_AAc also includes a lower triangular matrix. Hence, the matrix product of G_AA⁻¹G_AAc has the same structure as G_AAc. It has a submatrix including a lower triangular matrix. We will use the property of G_AA⁻¹ = G_AA in the binary domain [9] to prove the Lemma 1 in Section 4 and the matrix transformation in Section 5.

The development of the proposed OEA was motivated by [9, 11]. The computational complexity can be decreased by reducing the number of logical XOR computing units. The following example illustrates the procedure of omitting XOR computing units. After logical XOR operations, the output results are the same either from the approach to apply a generator matrix or the method to apply an encoding diagram scheme.

Figure 1 shows the SPC encoding diagram with N = 8 and A = {1,3,5,6,7}. In Fig. 1, the encoding direction is from bottom to top. The encoding process for information bits starts from right to left. Then, the encoding process for frozen bits is from left to right. The gray circles on the rightmost represent the information bits, and the black circles on the leftmost represent the frozen bits. The black arrow on the right represents the computing direction of the information bits. The black arrow on the left represents the computing direction of the frozen bits. Since the value of the frozen bits does not affect the encoding result, we set them to zero. The final outputs of the encoding are the value of the rightmost black circles.

For a SPC encoder in Fig. 1, we can reduce the XOR operation to obtain the output of x₀, x₂, and x₄. From Fig. 1, we can obtain

Consider that u₀, u₂, and u₄ are frozen bits which are set zero. Then, Eq. (8) can be rewritten as

From Fig. 1, we also have the following relations

Substitute Eq. (10) into Eq. (9), x₀ becomes

After applying logical XOR operations, the output results become zero if the input values are the same. Thus, Eq. (11) can be rewritten as

Similarly, x₂ and x₄ can be derived

By combining Eqs. (12), (13), and (14), we simplify the encoding diagram illustrated in Fig. 1 to the diagram in Fig. 2.

Compared with the computation complexity of original algorithm [11], the proposed OEA reduces the computational units without increasing the memory bits. Figures 1 and 2 show the difference of the number of computing units. There are only four XOR computing units to be reduced in Fig. 1. However, 12 XOR operations are omitted in Fig. 2. u₁, u₃, u₅, u₆, and u₇ are intermediate variables that can be ignored. The gray nodes on the rightmost represent the information bits, and the black nodes on the leftmost represent the frozen bits. The right black nodes are unknown. The outputs of the SPC encoder are x₀, x₂, and x₄.

The outputs of the SPC encoder also can be generated from a two-dimensional generator matrix. For example, we construct a generator matrix with the polar code length N = 8

The codeword vector x can be obtained from the matrix product of u (Eq. (3)) and above G₈ (Eq. (15)). For example, we can have the element x₀ (Eq. (16)) by multiplying u (Eq. (3)) with G₈ (Eq. (15))

Comparing x₀ in Eq. (16) to x₀ in Eq. (8), we found that the encoding result is the same. One is from an SPC encoding diagram (Eq. (8)), and another one is from a generator matrix approach (Eq. (16)). The proposed OEA utilizes the characteristics of the generator matrix and the matrix transformation. For a general case with the code length N, Section 4 shows that the outputs from a generator matrix approach are the same as the outputs from a diagram approach. For example, when N = 8 in Eq. (7), A = {1,3,5,6,7}, and G_AA⁻¹G_AAc = [1, 0, 0; 0, 1, 0; 0, 0, 1; 1, 1, 1; 1, 1, 1]. x_Ac has the elements of x₀, x₂, and x₄ as outputs. These outputs are the same as the results from Eqs. (12), (13), and (14). Therefore, the characteristics of the generator matrix can be considered to use in the process of our encoding optimization algorithm for a general case.

Before discussing the characteristics of the generator matrix, we first divide the distribution of information bits [15] into two groups based on the preset value. Then, we divide the distribution of information bits into two areas based on the bit channel index. Figures 3, 4, 5, and 6 show the capacity of binary erasure channels (BEC) when the code length N is 128, 256, 1024, and 2048, respectively. We can map the bit channel index to the set of A and the set of Ac according to the capacity value larger than or smaller than the preset value. For the areas of all bit channel index in A or all bit channel index in Ac, we define them as non-hybrid areas. For the area of the bit channel index belonging to both A and Ac, we define it as a hybrid area. For example, in Fig. 3, we can set up 0.7 as a preset capacity value. When the capacity value is larger than 0.7, the bit channel index belongs to the set of A. When the capacity value is smaller than 0.7, the bit channel index belongs to the set of Ac. For the set of A, we select the lowest index in the area with capacity value larger than 0.7. We draw a line 1 across the lowest index and denote the left side of line 1 as a non-hybrid area. Similarly, for the set of Ac, we select the highest index in Ac to the area with capacity value smaller than 0.7. We draw a line 2 across the highest index. We call the right side of line 2 a non-hybrid area. We denote the area between the line 1 and the line 2 as a hybrid area. There are both frozen bits and information bits distributed in this hybrid area. For Figs. 4, 5, and 6, we can use the same approach to divide the areas into a hybrid or a non-hybrid area and map the distribution of information bits into the set of A and Ac.

The following variables are defined to describe the highest index value in Ac, the lowest index value in A, the number of information bits, and the number of frozen bits in the hybrid and non-hybrid areas. The defined variables are listed in the Table 1.

For the non-hybrid area, the index value of p_fi represents the number of the frozen bits, and N − p_lf − 1 represents the number of the information bits, where N has been defined as the code length previously. The value of N is the total number of all frozen bits and information bits. The width of the hybrid area in the generator matrix can be represented byΔ=p_lf − p_fi + 1. The value of Δ also represents the sum of the frozen bits and the information bits in this hybrid area. Figure 7 shows these defined variables of p_fi, Δ, N − p_lf − 1 when the code length N is 16.

In Section 2, we have denoted G_N as a lower triangular with all ones across the diagonal and G_N is invertible. In binary GF (2), the invertible matrix is equal to itself, G_N⁻¹ = G_N. G_i,j represents an element in the matrix of G_N. i, j∈N, where N = {0,1,...,N − 1}. When i = j, G_i,j = 1; when i < j, G_i,j = 0.

We have following discrete function definitions. These defined functions are used to show the lower triangle structure property of the generator matrix G_N and its submatrices of G_AA and G_AAc.

Discrete function definition:

f_N(x) = x, where a discrete variable x of the function is x∈N. The discrete function is N, f_N(x)⊂N.

f_A(x) = A(x), where a discrete variable x of the function is x ∈{1, 2, ..., K}, K is the length of information bits. The discrete function is A(x), f_A(x)⊂A, and f_A(1) = A(1) = p_fi. f_A(x) is a monotone increasing function.

f_c(x) = Ac(x), where the discrete variable x of the function is x ∈{1, 2, ..., N − K}, N is the code length and N − K is the length of frozen bits. The discrete function is Ac(x), f_c(x)⊂Ac, and f_c(N − K) = Ac(N − K). f_c(x) is a monotone increasing function.

Since both matrix G_N and G_AA are square matrices, for the defined function f_N(x) = x, in which x represents the xth row of G_N as well as the xth column of G_N, f_N(x) can represent the f_N(x)th row of G_N as well as the f_N(x)th column of G_N. For f_A(x) = A(x), x represents the xth row of G_AA and G_AAc, as well as xth column of G_AA. f_A(x) represents A(x)th row in G_N as well as A(x)th column of G_N. For f_c(x) = Ac(x), x represents the xth column of G_AAc and f_c(x) represents the Ac(x)th row of G_N as well as Ac(x)th column of G_N.

Lemma 1: G_AA is a lower triangular with all ones across the diagonal.

Proof: For G_AA, when x = y, x,y∈{1,2,... ,K}, f_A(x) = f_A(y). So f_N(f_A(x)) = f_N(f_A(y)). Since f_A(x),f_A(y)∈A⊂N, and G_fA(x),fA(y) = 1, (G_AA)_x,y = 1. When x < y, x,y∈{1,2,...,K}, due f_A(x) is a monotone increasing discrete function, so f_A(x) < f_A(y). Hence f_N(f_A(x)) < f_N(f_A(y)). Because of f_A(x), f_A(y)∈A⊂N, we obtain that G_fA(x),fA(y) = 0. Hence, (G_AA)_x,y = 0. Given the property that the inverted matrix has the lower triangular structure if the original one has the lower triangular matrix, G_AA is a lower triangular; therefore, the inverted G_AA⁻¹ has a lower triangular matrix.

Lemma 2: A submatrix of G_AAc has the lower triangular structure.

Proof: For f_A(x₁), when x₁∈{1,2,...,Δi}, f_A(x₁)∈{A(1), A(2), ..., A(Δi)}, f_A(1) = A(1) = p_fi. For f_c(x₂), in which x₂∈{N − K − Δf, N − K − Δf+1, ... ,N-K}, f_c(x₂)∈{Ac(N − K − Δf), Ac(N − K − Δf+1),..., Ac(N − K)}. f_c(N − K) = Ac(N − K) = p_lf. In the hybrid area, we know that A(1) < Ac(N − K − Δf) and A(Δi) < Ac(N − K). As we know from the above analysis, each information bit index is smaller than the previous frozen bit index. Due to f_A(x) and f_c(x) are monotone increasing discrete functions, so f_A(x₁) < f_c(x₂), G_{fA(x1),fc(x2)} = 0, and (G_AAc)_x1,x2 = 0. The property of a submatrix G_AAc with lower triangular structure exists if f_A(x₁) < f_c(x₂), where x₁ and x₂ are in different discrete sets, x₁∈{1,2,...,Δi} and x₂∈{N − K − Δf, N − K − Δf+1, ... , N − K}.

For the case of code length of N = 16, suppose the code rate is 1/2, we will have K = 8, A = {3, 5, 7, 9, 11, 13, 14, 15}, and Ac = {0, 1, 2, 4, 6, 8, 10, 12}. For the generator matrix of G₁₆ in Fig. 8a, the rows of information bits indices can be extracted to form (G₁₆)_A shown in Fig. 8a, b, c₁, and c₂ which illustrate the detailed procedures of the matrix transformation.

The row elements in the solid line box in Fig. 8a form a new matrix (G₁₆)_A shown in Fig. 8b. In Fig. 8b, f_A(1) = A(1) = 3 and f_c(N − K) = Ac(N − K) = 12, so the third column represents the first information bit p_fi and the 12th column represents the last frozen bit p_lf . We can form (G₁₆)_AA in Fig. 8c₂ by extracting the columns from the dashed box in Fig. 8b. To form (G₁₆)_AAc shown in Fig. 8c₁, we can use the remaining columns from the Fig. 8b. By the Lemma 1, (G₁₆)_AA is a lower triangular matrix with all ones across the diagonal, (G₁₆)_AA⁻¹ = (G₁₆)_AA, G_AA⁻¹ is a lower triangular matrix. By the Lemma 2, (G₁₆)_AAc has a lower triangular structure. For the general case of N = 2ⁿ, n ≥ 1, the dimension of the lower triangular matrix in (G₁₆)_AAc is N − K − p_fi + 1. The dimension of (G₁₆)_AAc is N − K, minus the first part of the matrix, so the remaining matrix size is d = N − K − p_fi + 1. G_AA⁻¹ is the inverse of itself, and it is a lower triangular matrix with the dimension of K.

The matrix (G₁₆)_AA⁻¹and (G₁₆)_AAc in Fig. 9a and b are partitioned to obtain a block of a zero submatrix. To further discuss about general case, Fig. 9a can be partitioned and written as several submatrices of g₁, g₂, g₃, and g₄ in Fig. 10a. The submatrix g₂ is a zero matrix. Figure 9b can be partitioned into submatrices of c₁, c₂, c₃, and c₄ in Fig. 10b. The submatrix c₂ is a zero matrix.

When d is even, the sizes of the submatrices of g₁, g₂, g₃, and g₄ are \( \frac{d}{2}\times \frac{d}{2} \),\( \frac{d}{2}\times \left(K-\frac{d}{2}\right) \),\( \left(K-\frac{d}{2}\right)\times \frac{d}{2} \), and \( \left(K-\frac{d}{2}\right)\times \left(K-\frac{d}{2}\right) \), respectively. And the sizes of submatrices of c₁, c₂, c₃, and c₄ are \( \frac{d}{2}\times \left(N-K-\frac{d}{2}\right) \),\( \frac{d}{2}\times \frac{d}{2} \),\( \left(K-\frac{d}{2}\right)\times \left(N-K-\frac{d}{2}\right) \), and \( \left(K-\frac{d}{2}\right)\times \frac{d}{2} \), respectively. Due to the zero property of g₂ and c₂, Eq. (7) can be rewritten as

For Eq. (19), when d is even, the dimension of the zero submatrix in G_AA⁻¹G_AAc is \( \frac{d}{2}\times \frac{d}{2} \); when d is odd, the size of the zero submatrix in G_AA⁻¹G_AAc is \( \frac{d-1}{2}\times \frac{d-1}{2} \). The computing procedures are omitted when multiplying such zero submatrix during an encoding process. Therefore, we can save the computing resources after applying the proposed OEA. The OEA is universal for general cases. The pseudocodes of our OEA are listed in the algorithm for the proposed OEA. We can clearly understand the characteristic of the proposed algorithm and the difference between the encoding algorithm in [11].

Table 2 discusses the dimension d of lower triangular submatrix of GAAc at different code lengths of N and different code rates of R, where d = N − K − p_fi + 1. Detailed data of three different code lengths and three different code rates for each of them are listed in this table.

Figure 11 shows the ordinate in a linear plot. The relation between d and R is in a linear relationship for each of code length N. The value changes of p_fi can be negligible to a code length.

Figure 12 shows the variation trend of d with the code length N. At different code rates (for example, R = 0.5, 0.75, and 0.9), d increases when the code length N becomes short. Especially, when R = K/N = 0.5, the growth trend is faster than others. In other words, the smaller the code rate is, the greater the value of d will be.

After applying the proposed OEA to the transformed matrix, the percentages of zero elements of the lower triangular part are shown in Table 3. For SPC and NSPC, the percentages of zero elements shown in Table 3 are calculated by Eqs. (20) and (21), respectively.

For NSPC, 0.47% of the computing resources can be saved when N = 1024 and R = 0.9. However, when N = 1024 and R = 0.5, only 11.8% of the computing resources can be saved. For SPC, 58.5% of the resource consumption can be saved when code rate R = 0.5 and the code length N = 2048. When the code rate increases, the percentage of zero elements in the lower triangle decreases. However, the percentage is almost invariable at different code lengths for SPC and NSPC at the same code rate.

The comparison of systematic polar encoders is shown in Table 4. Unlike [10, 11], we use the total times of XORs to represent the computational complexity in this paper. For the Encoder A in [10] and the SPC in [11], the times of XORs can be approximated as \( \left({N}^2+N\right)\left({n}^2+n\right)/2>\frac{n^2}{2}\cdot {N}^2>{N}^2 \) and \( N\left({N}^2+N\right)/2\ge \frac{N^3}{2} \), respectively. However, for the proposed OEA, the computational complexity can be decreased to NK due to NK − K² − N + K = (N − K)(K − 1) < NK. Therefore, the computational complexity of the OEA is lower than that of Encoder A in [10] and SPC in [11]. As for the Encoder B, Encoder C, and NSPC in [10], the times of XORs can be approximated as N(1 + log₂N) > o(N), N(1 + 2log₂N) > o(N), and \( \frac{N}{2}{\log}_2N>o(N) \), respectively. Compared with the recursive algorithms Encoder B, Encoder C, and NSPC in [10], the advantage of the times of XORs of the proposed OEA is not obvious, but it is beneficial to hardware implementation. For the proposed OEA, the operation of the matrix segmentation and transformation can be completed in the preprocessing stage, followed by multiplication of matrix and vector, which can be realized by XOR gate. There is no reverse transmission process of signal, which is beneficial to the timing and pipeline design of the hardware. The Encoder B, Encoder C, and NSPC in [10] are implemented by the recursive algorithm based on divide-and-conquer method in the software design, and the signal is passed from the first level to the last level, and then passed back to the first level. This process of bidirectional transmission of signals is not conducive to hardware implementation, especially in high-speed pipeline structures.

In this paper, we propose an optimization algorithm OEA for SPC. The number of zero elements in the transformed generator matrix and their locations can be determined in the proposed OEA. In the case of code rate reaching 0.5, half of the number of XOR computing units can be omitted to save computation resources due to the large number of zero elements found in the submatrix. For other code rates higher than 0.5, a smaller number of the computation units is saved. The proposed OEA not only reduces the number of XOR computing units compared with the existing non-recursive algorithms, but also is beneficial to hardware implementation compared with the existing recursive algorithms.