CN106656214A - Dynamic distribution sorting algorithm based on successive cancellation list polarization code decoding - Google Patents

Abstract

The invention discloses a dynamic distribution sorting algorithm based on serial offset list polar code decoding, and two child nodes extended by each parent node are set as FC and NC, wherein FC is a better node and NC is a worse node . The L FC nodes are used as the preferred L optimal paths, and the final sorting is completed through the dynamic replacement of individual FCs and NCs. Due to the advantages of FC nodes in SCL decoding, fewer nodes need to be replaced. Using this property, the complexity of sorting can be greatly reduced.

Description

A Dynamic Distribution Sorting Algorithm Based on Serial Cancellation List Polar Code Decoding

technical field

The invention relates to a dynamic distribution sorting algorithm based on serial cancellation list polar code decoding.

Background technique

Arlkan proposed that polar codes are the first class of channel coding that can almost achieve the capacity of symmetric binary-input discrete memoryless channels (B-DMCs). Due to its low computational complexity of O(NlogN), where N is the length of the polar code; and the decoding structure in the form of Fast Fourier Transformation (FFT), serial offset decoding successive cancellation (SC) algorithm Has become one of the most effective polar decoding algorithms. However, compared with the maximum likelihood (ML) decoder, the decoding performance of the serial cancellation decoder still has a large decline. In order to narrow the performance gap caused by the suboptimal path selection of the traditional serial offset decoder, the list serial offset decoding algorithm (list SC polar decoder) came into being. After joining the list (L), it brings more opportunities for path selection.

The main idea of the SCL decoding algorithm is to select the optimal L paths in the decoding tree expansion, and expand the optimal L paths again. Each level of decoding involves a sorting operation to select the best L nodes from 2L candidate nodes. The main disadvantage of the serial cancellation list decoder is that the complexity of the ordering part of the decoder increases non-linearly as the size of the list L increases. During the path extension process, L paths with the largest path metric values need to be selected from the 2L extended paths as candidate paths. If you choose a method similar to bubble sorting or selection sorting, its computational complexity is O(L ² ); if you choose a method similar to heap sorting, its computational complexity is O(Llog2L), but it also increases required memory unit. In addition, the delay of the two algorithms is relatively large, which is not conducive to high-speed hardware implementation.

Contents of the invention

Purpose of the invention: the purpose of the present invention is to provide a dynamic distribution sorting algorithm based on serial cancellation list polar code decoding that can solve the defects in the prior art.

Technical scheme: in order to achieve this goal, the present invention adopts following technical scheme:

The dynamic distribution sorting algorithm based on serial cancellation list polar code decoding of the present invention comprises the following steps:

S1: Extend for L paths: set the two extended child nodes of each parent node as FC and NC respectively, where FC is the better path and NC is the worse path, and the obtained L FC nodes are set as a set FCS, set the obtained L NC nodes as the set NCS;

S2: Set L FC nodes as L optimal paths, represented by a set C;

S3: Initialize i=1, i is the number of sorting rounds;

S4: Set the maximum number of sorting rounds n according to the actual performance requirements, and 1≤n≤L-1;

S5: For the i-th round of sorting, select the worst path FC i from the remaining L-i+1 FC nodes in the set FCS, and select the worst path FC _i from the remaining L-i+1 NC nodes in the set NCS Find the optimal path NC _i ;

S6: Comparing FC _i and NC _i : if FC _i is better, the sorting ends and jumps to step S12; otherwise, proceed to step S7;

S7: replace the FC _i path in the set C with the NC _i node;

S8: Delete the FC _i element in the set FCS, then the number of elements in the set FCS becomes Li;

S9: delete the NC _i element in the set NCS, then the number of elements in the set NCS becomes Li;

S10: update i value, i=i+1;

S11: If i<n, jump to step S5 for the next round of sorting; otherwise, continue to step S12;

S12: The sorting is completed, and the optimal L paths are the paths in the set C.

Beneficial effects: compared with the prior art, the present invention has the following beneficial effects:

1) The present invention utilizes the feature of selecting L optimal paths from 2L extended paths in the SCL decoding requirements, and does not need to know the sequence results for the L selected paths, avoiding direct sorting;

2) The present invention utilizes the L FCs nodes in the extended nodes that are likely to be the final L optimal paths, based on the FC nodes, the sorting results are adjusted by replacing the poorer FCs, which greatly reduces the complexity of sorting Spend;

3) The present invention reduces the bubble sorting with O(L ² ) complexity or the heap sorting with O(Llog2L) complexity to the dynamic distributed sorting with O(L) complexity;

4) The present invention is dynamic sorting, and its sorting delay is not fixed. Since the FC nodes are largely superior to the NC nodes, in the dynamic sorting of each layer for a frame of polar codes, most sorting only needs one round of sorting, that is, there is no replacement of NC nodes and FC nodes.

Description of drawings

Fig. 1 is the search code tree of N bit Polar code;

Fig. 2 is the frame error rate performance comparison chart of adopting the specific embodiment method of the present invention and adopting general SCL decoding algorithm;

Fig. 3 is the average calculation cycle of DS2 algorithm in the specific embodiment of the present invention;

Fig. 4 is the average calculation period of the DS3 algorithm in the specific embodiment of the present invention.

detailed description

The technical solution of the present invention will be further introduced below in combination with specific embodiments.

1. Search code tree

The SCL decoding algorithm of the Polar code is essentially a breadth-first tree search algorithm. The search code tree of the N-bit Polar code is shown in Figure 1, and L is the number of reserved paths. In Figure 1, the path (survival path) with the largest path metric value (Path Metric, PM) in the Nth layer is the decoding output The number of times represents a vector, and the labels are N decoding results from 1 to N.

2. SCL algorithm

For the parameter is Polar code, N is the code length, K is the number of information bits. The output vector corresponding to the channel W _N is Indicates the number of accepted N received data, numbered from 1 to N. A is a collection of information bit distribution situations. is the value of the frozen bit, usually set to 0. The decoded path metric is defined as the channel transition probability It is often used in its logarithmic form. In order to reduce the complexity of computation and storage, we use equivalent path metrics defined as follows:

The recursive formula of its decoding is as follows:

in Indicates the i-th decoded PM value of the N-bit decoder, Indicates the corresponding node part of and . and Indicates the connection node The two partial sums of the upper iteration. Represents XOR calculation, max ^* represents Jacobi logarithm:

initialization condition where ^σ2 is the noise variance. max(x ₁ , x ₂ ) is to take the maximum value among x ₁ , x ₂ .

3. This specific implementation method

During the path extension process, L paths with the largest path metric values need to be selected from the 2L extended paths as candidate paths. If you choose a method similar to bubble sorting or selection sorting, its computational complexity is O(L ² ); if you choose a method similar to heap sorting, its computational complexity is O(Llog2L), but it also increases required memory unit. In addition, the delay of the two algorithms is relatively large, which is not conducive to high-speed hardware implementation.

This specific embodiment discloses a dynamic distribution sorting algorithm based on serial cancellation list polar code decoding, which includes the following steps:

S1: Extend for L paths: set the two extended child nodes of each parent node as FC and NC respectively, where FC is the better path and NC is the worse path, and the obtained L FC nodes are set as a set FCS, set the obtained L NC nodes as the set NCS;

S2: Set L FC nodes as L optimal paths, represented by a set C;

S3: Initialize i=1, i is the number of sorting rounds;

S4: Set the maximum number of sorting rounds n according to the actual performance requirements, and 1≤n≤L-1;

S5: For the i-th round of sorting, select the worst path FC i from the remaining L-i+1 FC nodes in the set FCS, and select the worst path FC _i from the remaining L-i+1 NC nodes in the set NCS Find the optimal path NC _i ;

S6: Comparing FC _i and NC _i : if FC _i is better, the sorting ends and jumps to step S12; otherwise, proceed to step S7;

S7: replace the FC _i path in the set C with the NC _i node;

S8: Delete the FC _i element in the set FCS, then the number of elements in the set FCS becomes Li;

S9: delete the NC _i element in the set NCS, then the number of elements in the set NCS becomes Li;

S10: update i value, i=i+1;

S11: If i<n, jump to step S5 for the next round of sorting; otherwise, continue to step S12;

S12: The sorting is completed, and the optimal L paths are the paths in the set C.

The distributed sorting algorithm (DS) disclosed in this specific embodiment is similar to a general sorting algorithm, but its storage and comparison complexity is lower than that of a general sorting algorithm. When the previous comparison does not meet the conditions, the algorithm exits, and no subsequent comparison is performed, which greatly reduces the average comparison complexity. It can be seen from the analysis and related simulations that the smaller the path metric value corresponding to the larger i value in PMs, it is likely to need to be discarded, and the influencing factors on the algorithm are dominant. Only take i=L-1~Ln to complete path expansion and measure value sorting, which is called DSn, and set parameter n as the maximum number of comparison rounds. At this point, in Algorithm 1 for The sorting operation of is not needed, it is only necessary to find several values such as the largest, smallest, second largest and second smallest values. In hardware implementation, we can make further changes, find The minimum and second minimum value of the search instead of The smallest and second smallest values of , in the case of the same complexity, improve the decoding performance. It can be known from the simulation that after the SCL decoding algorithm based on DS2 (L=4) or DS3 (L=8) is combined with the CRC check, the performance loss of the decoding misdiagnosis rate is almost negligible. When L is large, such as L=16, 32, the performance loss caused by the simple DS2 or DS3 algorithm is relatively large, the complete DS algorithm is used for the first N/2 bits, and the DS3 algorithm is used for the last N/2 bits.

Taking L=4 as an example, the path expansion process based on the DS2 algorithm is as follows: 1. Separate the four paths into four FC nodes and four NC nodes; 2. Find the worst node FC ₁ among the four FC nodes , find the optimal node NC ₁ among the four NC nodes; 3, compare FC ₁ and NC ₁ , if FC ₁ is larger, the sorting ends, and the selected four optimal paths are the paths corresponding to the four FCs, there is no need Perform the following operations, and vice versa; 4. Replace FC ₁ with the path corresponding to NC ₁ , and these two values will not enter the comparison operation; 5. Select the worst node among the remaining three FCs FC ₂ , find the optimal node NC ₂ among the remaining three NC nodes; 6, compare FC ₂ and NC ₂ , if FC ₂ is larger, the sorting ends, and the four optimal paths selected are three FC The path corresponding to NC ₁ , otherwise, the selected four paths are the remaining two FC paths corresponding to NC ₁ and NC ₂ , and the sorting ends. The DS2 algorithm reduces the comparison complexity of metric values from O(L ² ) to O(L). The DS2 algorithm is easy to realize on the parallel pipeline of the hardware, which can reduce the complexity and improve the data processing rate.

For different L values, the frame error rate performance comparison between the improved SCL decoding and the general SCL decoding is shown in Figure 2, and Figure 2 is a polar code with a code length of 1024 effective information bits and 512 bits. When L=4, SCL decoding based on DS2 algorithm has almost the same frame error rate performance as general SCL decoding, which can be used as a better choice for low-complexity hardware implementation; when L=8, SCL decoding based on DS3 algorithm Decoding has almost the same frame error rate performance as general SCL decoding, and can be used as a better choice for low-complexity hardware implementation.

Another advantage of this particular embodiment is that this sorting is a dynamic sorting process, and the number of rounds to be sorted is uncertain. Due to the nature of the SCL decoding process itself, the extended FC nodes in the L paths are most likely to be the final selected L optimal paths. Therefore, most distributed sorting processes only need one round of sorting in the decoding process. It can be proved by simulation that the sorting length is extremely low.

As can be seen from the simulation of Figure 3, when L=4, the DS2 sorting algorithm in this specific embodiment only needs to carry out 1.075 rounds of sorting (8 cycles) on average, which is also greatly improved than strict sorting in timing (if The sorting clock needed to use traditional bubble sorting is on the order of L ² , that is, 16 cycles). As can be seen from the simulation of Fig. 4, when L=8, the DS3 sorting algorithm in this specific embodiment only needs to carry out 1.074 rounds of sorting (16 cycles) on average, which is also greatly improved than strict sorting in timing (if The sorting clock needed to use the traditional bubble sorting is ^on the order of L2, that is, 64 cycles). The distributed sorting algorithm in this specific embodiment consumes about one round of sorting on average, which greatly reduces the time delay wasted by sorting.

Claims (1)

1. It is 1. a kind of that the DYNAMIC DISTRIBUTION sort algorithm that list polarization code is decoded is offset based on serial, it is characterised in that：Including following step Suddenly：

   S1：It is extended for L paths：Two extension child nodes of each father node are set to FC and NC, and wherein FC is Compared with shortest path, NC is poor path, and the L FC node for obtaining is set to into set FCS, and the L NC node for obtaining is set to into collection Close NCS；

   S2：L FC node is set to into L bar optimal paths, is represented with set C；

   S3：Initialization i=1, i are sequence wheel number；

   S4：The maximum sequence wheel number n of setting, and 1≤n≤L-1 are required according to actual performance；

   S5：For the i-th wheel sequence, worst path FC will be selected in L-i+1 FC node remaining in set FCS_i, will gather The path NC of optimum is selected in L-i+1 NC node remaining in NCS_i；

   S6：Relatively FC_iWith NC_i：If FC_iMore excellent, then sequence terminates, and jumps to step S12；Otherwise, step S7 is proceeded；

   S7：By the FC in set C_iPath replacement is NC_iNode；

   S8：By the FC in set FCS_iElement is deleted, then the element number in set FCS is changed into L-i；

   S9：By the NC in set NCS_iElement is deleted, then the element number in set NCS is changed into L-i；

   S10：Update i values, i=i+1；

   S11：If i<N, then jumping to step S5 carries out next round sequence；Otherwise, then step S12 is proceeded；

   S12：Sequence is completed, and optimum L paths are the path in set C.