CN110233628B - Adaptive Belief Propagation List Decoding Method for Polar Codes - Google Patents

Abstract

The invention discloses an adaptive belief propagation list decoding method of polar codes. Firstly, according to the number of BP decoders owned by the receiving end, the maximum number of lists of the method is determined, and the Gaussian approximation method is used to calculate and obtain better results. The BP decoding factor map of the decoding effect, and then select a different BP decoding factor map for the BP decoder recorded in the list to decode, sort the decoding results and perform a cyclic redundancy check. If the result of the cyclic redundancy check is successful, the decoding is stopped, otherwise, the size of the list is automatically adjusted, and the number of lists is doubled, and the BP decoder in the list is continued to be used for decoding.

Description

Adaptive Belief Propagation List Decoding Method for Polar Codes

technical field

The invention relates to an adaptive belief propagation list decoding method of polar codes, which belongs to the technical field of channel coding in wireless communication.

Background technique

Polar code technology is a new type of channel coding technology. When the code length tends to infinity, the transmission rate can reach the channel capacity of binary input memoryless symmetric channel. At present, there are two mainstream decoding methods for polar codes. One is based on Serial Cancellation (Successive Cancellation, SC) decoding method, including Serial Cancellation List (SCL) decoding based on SC decoding. method, the SC-based polar code decoding method belongs to sequential decoding, and the decoded information bits have an impact on the estimation of subsequent information bits, so the information bits in the codeword must be estimated one by one, resulting in a large Decoding delay. Another mainstream decoding method for polar codes is based on the Belief Propagation (BP) decoding method, including the Belief Propagation List (BPL) decoding method. The BP-based decoding method is due to its parallel iterative calculation , its decoding delay is significantly lower than that of SC-based decoding methods and is not sensitive to codeword length, so BP decoding method is suitable for application scenarios with high delay requirements. However, the traditional BP decoding method has poor bit error rate and frame error rate performance. The BPL decoding method improves the bit error rate and frame error rate performance on the basis of the BP decoding method, but brings higher computational complexity. degree and hardware requirements.

Contents of the invention

The present invention provides an adaptive belief propagation list decoding method for polar codes. The code words used are concatenated codes formed by cyclic redundancy check (Cyclic Redundancy Check, CRC) codes and polar codes. The list of the adaptive belief propagation list decoding method is used to record the BP decoders that can decode simultaneously. The number of lists is defined as the number of BP decoders in the list, and the maximum number of lists is defined as the BP decoders that can decode simultaneously. The upper limit of the number of encoders.

The adaptive belief propagation list decoding method proposed in the present invention first determines the maximum list number of the method according to the number of BP decoders owned by the receiving end, and calculates the BP that can achieve better decoding effect through Gaussian approximation method. Decode the factor graph, and then select a different BP decoding factor graph for the BP decoder recorded in the list to decode, sort the decoding results and perform a cyclic redundancy check, if there is a cyclic redundancy check , then the decoding is successful and the decoding is stopped, otherwise the size of the list is automatically adjusted, the number of the list is doubled, and the BP decoder in the list is continued to be used for decoding.

The existing BP decoding method has poor bit error rate and frame error rate performance, while the BPL decoding method uses multiple BP decoders to decode at the same time, at the cost of higher computational complexity and hardware energy consumption Improved Bit Error Rate and Frame Error Rate performance. Compared with the BP decoding method and the BPL decoding method, the adaptive belief propagation list decoding method of polar codes has achieved better bit error rate and frame error rate performance, and the number of lists required to complete the decoding is in The number of lists required under medium and high SNR conditions is significantly smaller than that of the BPL decoding method. This shows that the adaptive belief propagation list decoding method of polar codes requires significantly fewer BP decoders than the BPL decoding method with a constant number of lists under medium and high SNR conditions, thereby achieving a significant reduction in computational complexity. The effect of reducing hardware power consumption.

The present invention adopts the following technical solutions for solving the problems of the technologies described above:

The present invention provides an adaptive belief propagation list decoding method for polar codes, comprising the following steps:

Step 1: Initialize the maximum number of lists L _max allowed, and construct the permutation matrix permutation_matrix corresponding to the 2L _max -1 factor graph for BP decoding, specifically:

(1) independently determine the maximum number of lists L _max according to the number of BP decoders owned by the receiving end;

(2) Narrow down the search range of the required permutation factor map: for a polar code with a code length of N=2 ⁿ , it needs to go through n encoding stages {l ₀ ,...,l _n-1 } during encoding, and the decoding The factor graph used in encoding and the full arrangement of elements in L={l ₀ ,l ₁ ,...,l _n-1 } are in one-to-one mapping relationship; the parameter k is defined so that k satisfies the condition: (nk)! ≥L _max , record a subset of the set L as L _h ＝{l _k ,l _k+1 ,...,l _n-1 }, get the (nk) of the elements in the set L _h ! A full permutation, and before each permutation, the first k encoding stages {l ₀ , l ₁ ,...,l _k-1 } with the same order are added, so as to obtain the (nk) of all elements in the set L ! A permutation, the corresponding (nk) is obtained from the one-to-one mapping relationship between the factor graph and the element permutation in L! kind of factor graph, thus reducing the search range of permutation factor graph to (nk)! kind;

(3) Select the required factor graph from the search range of the replacement factor graph: for (nk) of all elements in the set L obtained in step (2)! Arrangements, respectively calculate the frame error rate of the corresponding factor graph under the Gaussian approximation method, and select the 2L _max -1 factor graph with the smallest frame error rate;

(4) Construct the permutation matrix permutation_matrix corresponding to 2L _max -1 factor graph: Construct a permutation matrix permutation_matrix with 2L _max -1 rows and n columns, and each row in permutation_matrix corresponds to the 2L _max -1 species selected in step (3) one of the full permutations of the set L;

The second step is to perform adaptive belief propagation list decoding of polar codes, specifically:

(A) Initialization: Initialize the current number of BP decoders that can simultaneously perform belief propagation decoding of polar codes l=1;

和

计算出每个译码器得出的码字估计

与接收信号

之间的欧式距离d，其中，

是对信息比特u_i的估计，

是对信息比特u_i经过级联编码后得到的码字比特x_i的估计，y_i表示接收信号的第i个比特；(B) Use l independent BP decoders to perform BP decoding at the same time. Each BP decoder uses the factor graph corresponding to a row of elements that has not been used in the permutation_matrix to perform BP decoding independently, and the BP decoder The output of

and

Compute the codeword estimates from each decoder

and receive signal

The Euclidean distance d between, where,

is the estimate of the information bits u _i ,

is the estimate of the codeword bit x _i obtained by concatenating encoding of the information bit u _i , and y _i represents the i-th bit of the received signal;

排序；(C) Estimate the l group of information bits obtained in step (B) according to the corresponding d ordering rules from small to large

sort;

逐个进行循环冗余校验：如果当前待校验的译码结果

满足循环冗余校验，则自适应置信传播列表译码方法译码成功，返回该译码结果，整个译码流程结束；否则对下一组信息比特估计

进行循环冗余校验，若l组信息比特估计

均未通过循环冗余校验，则转入步骤(E)；(D) Estimating the l group of information bits sorted in step (C)

Carry out cyclic redundancy check one by one: if the decoding result currently to be checked

If the cyclic redundancy check is satisfied, then the adaptive belief propagation list decoding method decodes successfully, returns the decoding result, and the entire decoding process ends; otherwise, the next group of information bits is estimated

Carry out cyclic redundancy check, if l groups of information bits estimate

If they have not passed the cyclic redundancy check, then go to step (E);

作为译码结果，整个译码流程结束；否则令l＝2l，转入步骤(B)。(E) If l≥L _max , output the first group of information bit estimates sorted in step (C)

As a decoding result, the entire decoding process ends; otherwise, let l=2l, and go to step (B).

As a further optimization scheme of the present invention, the value of k in step (1) is determined by the receiving end according to its own computing capability and delay requirements.

As a further optimization scheme of the present invention, in step (B)

Compared with the prior art, the present invention adopts the above technical scheme and has the following technical effects: the adaptive belief propagation list decoding method of polar codes in the present invention first sets the number of lists to a smaller value, and then The decoding results in the list are subjected to a cyclic redundancy check, and after the cyclic redundancy check fails, the number of lists is increased to continue decoding. Compared with the traditional BP decoding method, the adaptive belief propagation list decoding method of polar codes significantly improves the bit error rate and frame error rate performance, and the average decoding delay and calculation The complexity is only slightly higher than the traditional BP decoding method. Compared with the existing BPL decoding methods, the adaptive belief propagation list decoding method of polar codes improves the bit error rate and frame error rate performance, and gradually increases the number of lists to avoid a large number of incorrect BPL decoding methods. The necessary calculation and hardware energy consumption can reduce the calculation complexity by an order of magnitude in the range of medium and high SNR, and obtain bit errors exceeding the BPL decoding method by approaching the calculation complexity and hardware energy consumption of the traditional BP decoding method rate performance. This shows that the method in the present invention can obtain the gain of the bit error rate performance and the simplification of the computational complexity at the cost of a small decoding delay.

Description of drawings

Fig. 1 is the flowchart of the adaptive belief propagation list decoding method of polar codes;

Figure 2 is a schematic diagram of three different factor graphs with a code length of 8 and three encoding stages (l ₀ , l ₁ , l ₂ ), where (a) is a factor that passes through l ₂ , l ₀ , l ₁ in sequence (b) is a factor graph passing through l ₁ , l ₂ , and l ₀ in sequence, and (c) is a factor graph passing through l ₁ , l ₀ , and l ₂ in sequence.

detailed description

Below in conjunction with accompanying drawing, technical scheme of the present invention is described in further detail:

The adaptive belief propagation list decoding method of polar codes in the present invention is described by taking code length N=2048, information bit number K=1024, and cyclic redundancy check code length r=8 as examples. The construction method of the polar code in this example is Gaussian approximation, the signal-to-noise ratio of the code word construction is 2.5 decibels, and the generator polynomial of the cyclic redundancy check code is g(x)=x ⁸ +x ⁶ +x ³ +x ² +1.

As shown in Figure 1, it includes the following steps:

Step 1: Initialize the maximum number of lists L _max allowed (L _max = 4 in this example), and construct the permutations corresponding to 2L _max -1 (2L _max -1 = 7 in this example) factor graphs for BP decoding Matrix permutation_matrix. This step includes the following processes:

(1) According to the number of BP decoders owned by the receiving end, the maximum number of lists L _max is determined independently. Go to step (2).

(2) Narrow down the search range of the required permutation factor graph (the permutation factor graph is an existing concept, and the construction method is briefly described in this step). For a polar code with a code length of N=2 ⁿ , it needs to go through n coding stages {l ₀ ,...,l _n-1 } during encoding, and record the set L={l ₀ ,l ₁ ,... , l _n-1 }. The factor graph used in decoding has a one-to-one mapping relationship with the full arrangement of elements in L, as shown in Figure 2, three different factor graphs when n=3. There are n total permutations of elements in the set L! species, so there are n! different decoding factor graphs. Define the parameter k so that k satisfies the condition: (nk)! ≥L _max , (the value of k is related to the size of the factor graph search range, and the specific value can be determined by the receiving end according to its own computing capability and delay requirements). Denote a subset of the set L as L _h , L _h ={l _k ,l _k+1 ,...,l _n-1 }. Get the (nk) of the elements in the set L _h ! A full permutation, and before each permutation, add the first k encoding stages {l ₀ , l ₁ ,...,l _k-1 } with the same order, so as to obtain the (nk) of all elements in the set L ! A permutation, the corresponding (nk) can be obtained from the one-to-one mapping relationship between the factor graph and the element permutation in L! A factor graph. This completes the search range of the permutation factor map by the original n! Kind of narrowed down to the present (nk)! kind. Go to step (3).

(3) Select the required factor graph from the search range of the replacement factor graph. For (nk) of all elements in the set L obtained in step (2)! For each arrangement, calculate the frame error rate of the corresponding factor map under the Gaussian approximation method, and select the arrangement of all elements in the set L corresponding to the 2L _max -1 factor map with the smallest frame error rate. Go to step (4).

(4) Construct the permutation matrix permutation_matrix corresponding to the required factor graph. Construct a permutation matrix permutation_matrix with a size of 2L _max -1 rows and n columns. Each row in permutation_matrix corresponds to one of the full permutations of 2L _max -1 sets L selected in step (3). This process ends. The permutation_matrix in this example is a matrix with a size of 7 rows and 11 columns as shown below:

Step 2: Perform adaptive belief propagation list decoding of polar codes. This step includes the following processes:

转入步骤(2)。(1) Initialization. Note that the number of BP decoders that can simultaneously perform belief propagation decoding of polar codes is l. Initialize parameter l=1, record the received signal as

Go to step (2).

和

为BP译码器的输出结果，其中

是指对信息比特u_i的估计，

是对信息比特经过级联编码后得到的码字比特x_i的估计。利用l个独立的BP译码器同时进行BP译码，每个BP译码器采用permutation_matrix中尚未使用过的1行元素对应的因子图分别独立地进行BP译码。计算出每个译码器得出的码字估计

与接收信号

之间的欧式距离d，

转入步骤(3)。(2) Simultaneously start one BP decoder to decode according to different factor graphs. remember

and

is the output result of BP decoder, where

is the estimate of the information bits u _i ,

is the estimation of the codeword bits _xi obtained after concatenated encoding of the information bits. Use l independent BP decoders to perform BP decoding at the same time, and each BP decoder uses the factor graph corresponding to the unused 1-row element in the permutation_matrix to perform BP decoding independently. Compute the codeword estimates from each decoder

and receive signal

The Euclidean distance d between

Go to step (3).

排序。按照对应的d从小到大的排序规则对步骤(2)中得到的l组信息比特估计

进行排序。转入步骤(4)。(3) Estimating the l group of information bits obtained in step (2)

Sort. Estimating the l group of information bits obtained in step (2) according to the ordering rule of corresponding d from small to large

put in order. Go to step (4).

逐个进行循环冗余校验。若当前待校验的译码结果

满足循环冗余校验，则自适应置信传播列表译码方法译码成功，返回该译码结果，整个译码流程结束。否则对下一组信息比特估计

进行循环冗余校验。若l组信息比特估计

均未通过循环冗余校验，则转入步骤(5)。(4) Estimating the l group of information bits sorted in step (3)

Cyclic redundancy checks are performed one by one. If the decoding result currently to be verified

If the cyclic redundancy check is satisfied, then the adaptive belief propagation list decoding method decodes successfully, and the decoding result is returned, and the entire decoding process ends. Otherwise, estimate the next set of information bits

Perform a cyclic redundancy check. If l groups of information bits are estimated

If none of them pass the cyclic redundancy check, go to step (5).

作为译码结果，整个译码流程结束。否则更新l→2l，即自适应地调整列表大小，将列表大小调整为原列表大小的两倍。转入步骤(2)。(5) If l≥L _max , then output the first group of information bit estimates sorted in step (3)

As a decoding result, the entire decoding process ends. Otherwise, update l→2l, that is, adjust the size of the list adaptively, and adjust the size of the list to twice the size of the original list. Go to step (2).

The specific embodiments described herein are merely illustrative of the spirit of the invention. Those skilled in the art to which the present invention belongs can make various modifications or supplements to the described specific embodiments or adopt similar methods to replace them, but they will not deviate from the spirit of the present invention or go beyond the definition of the appended claims range.

Claims (3)

1. The self-adaptive belief propagation list decoding method of the polarization code is characterized by comprising the following steps of:

the first step is as follows: maximum number of list allowed by initialization L _max Constructing 2L for BP decoding _max -1 permutation matrix probability _ matrix corresponding to the factor graph, specifically:

(1) According to the number of BP decoders owned by the receiving end, the maximum list number L is automatically determined _max ；

(2) Narrowing the search of the desired permutation factor graph: for code length N =2 ⁿ The polar code of (2) needs to pass through n coding stages l ₀ ,...,l _n-1 Factor graph adopted in decoding and L = { L = } ₀ ,l ₁ ,...,l _n-1 The elements in the Chinese character are arranged in a one-to-one mapping relationship; defining a parameter k so that k satisfies the condition: (n-k)! Not less than L _max Noting that a subset of the set L is L _h ＝{l _k ,l _k+1 ,...,l _n-1 Get set L _h (n-k) of the Medium element! Arranging the seeds completely, and adding the first k encoding stages { l ] with unchanged sequence before each arrangement ₀ ,l ₁ ,...,l _k-1 Thus, get (n-k)!of all elements in the set L! Arranging, obtaining corresponding (n-k)!according to the one-to-one mapping relation between the factor graph and the element arrangement in L! Seed factor graph, thereby reducing the search range of the replacement factor graph to (n-k)! Seed growing;

(3) Selecting a required factor graph from the search range of the replacement factor graphs: (n-k)!for all elements in the set L obtained in step (2)! Arranging, respectively calculating frame error rates obtained by corresponding factor graphs under a Gaussian approximation method, and selecting the 2L with the minimum frame error rate _max -1 factor graph;

(4) Configuration 2L _max -1 factor graph corresponding permutation matrix persistence _ matrix: construct 2L _max -1 row and n columns of permutation matrix multiplication _ matrix, each row of the multiplication _ matrix corresponding to 2L selected in step (3) _max -1 one of a full permutation of sets L;

secondly, decoding a self-adaptive belief propagation list of the polarization code, specifically comprising the following steps:

(A) Initialization: initializing the number l =1 of BP decoders which can simultaneously carry out belief propagation decoding on the polarization codes at present;

(B) BP decoding is carried out by using l independent BP decoders, each BP decoder respectively and independently carries out BP decoding by using a factor graph corresponding to 1 line element which is not used yet in the mutation _ matrix, and the output result of the BP decoder is

And

calculating codeword estimates for each decoder

And receive the signal

The euclidean distance d therebetween, wherein,

is to the information bit u _i The estimation of (a) is performed,

is to the information bit u _i Code word bit x obtained after cascade coding _i Estimate of (a), y _i An ith bit representing a received signal;

(C) The I groups of letters obtained in the step (B) are sorted according to the corresponding sorting rule that d is from small to largeInformation bit estimation

Sorting;

(D) Estimating the I groups of information bits ordered in step (C)

And (3) performing cyclic redundancy check one by one: if the current decoding result to be checked

If the cyclic redundancy check is met, the decoding of the self-adaptive belief propagation list decoding method is successful, the decoding result is returned, and the whole decoding process is finished; otherwise, estimating the next group of information bits

Performing cyclic redundancy check if the l groups of information bits are estimated

If the cyclic redundancy check fails, the step (E) is carried out;

(E) If L is greater than or equal to L _max Outputting the ordered first set of information bit estimates of step (C)

As a decoding result, the entire decoding flow ends; otherwise let l =2l, proceed to step (B).

2. The adaptive belief propagation list decoding method of polar codes according to claim 1, characterized in that the value of k in step (1) is determined by the receiving end itself according to its own computing power and delay requirement.

3. The adaptive belief propagation list decoding method of polarization codes according to claim 1, wherein in step (B)

Images