CN107612560B - Polarization code early iteration stopping method based on partial information bit likelihood ratio - Google Patents

Abstract

The invention discloses a polarization code early iteration stopping method based on a part information bit likelihood ratio, which comprises the following steps: s1) presetting the maximum iteration times of BP decoding; s2) decoding the polarized coded information by using a BP decoding algorithm; s3), after one iteration is finished, comparing the likelihood ratios of the information bits output by two adjacent iteration decoding; if the ratio of the same information bit likelihood ratio in the preset comparison space reaches a preset threshold value, stopping iteration and outputting a decoding result obtained by current iteration, otherwise, continuing iteration until reaching a preset maximum iteration number. In each iteration process, judging the likelihood ratio of partial information bits output by the iterative decoder twice before and after; and if the proportion of the same information bit likelihood ratio in the comparison space reaches a preset threshold value, stopping the decoding, thereby greatly reducing the calculation complexity and decoding delay of decoding and effectively reducing the consumption of hardware resources.

Description

Polarization code early iteration stopping method based on partial information bit likelihood ratio

Technical Field

The invention relates to a polarization code processing method, in particular to a polarization code early iteration stopping method based on a partial information bit likelihood ratio.

Background

Based on the channel polarization phenomenon, Arikan in 2008 proposed a code word with a capacity of "reachable" in the ISIT conference, called Polar code, which strictly proves in the paper that the channel capacity can reach the shannon bound when the code length tends to infinity in the binary input discrete memoryless channel. At the decoding end, Arikan also proposes a serial decoding method, called Serial Cancellation (SC). Due to its serial decoding structure, SC algorithm decoding delay is high. In order to reduce decoding delay, iterative Belief Propagation (BP) algorithm is also used for Polar code decoding.

The BP algorithm is parallel, the decoding delay of the BP algorithm is O (IlogN), I is the iteration number, therefore, the reduction of the iteration number is very important for reducing the decoding delay of the BP algorithm, the traditional BP algorithm stops when reaching the preset maximum iteration number, and in practice, a correct decoding result is obtained in the early iteration stage, so related researchers provide a plurality of early iteration stop methods to avoid redundant iteration, such as methods of min LL R, G-Martix, L MA, CA and the like.

Disclosure of Invention

The technical problem to be solved by the invention is to provide a partial information bit likelihood ratio-based polarization code early iteration stopping method, which can greatly reduce the calculation complexity and decoding delay of decoding and is convenient for hardware implementation.

The technical scheme adopted by the invention for solving the technical problems is to provide a polarization code early iteration stopping method based on partial information bit likelihood ratio, which comprises the following steps: s1) presetting the maximum iteration times of BP decoding; s2) decoding the polarization code coding information by using a BP decoding algorithm; s3), after one iteration is finished, comparing the likelihood ratios of partial information bits output by the BP decoders of two adjacent iterations; if the ratio of the same information bit likelihood ratio in the preset comparison space reaches a preset threshold value, stopping iteration and outputting a decoding result obtained in the current iteration step, otherwise, continuing the iteration until reaching the preset maximum iteration times.

The above method for stopping early iteration of a polarization code based on likelihood ratio of partial information bits, wherein the code length of the polarization code is N, the polarization code includes K information bits, and the set a is a set of information bits

Referred to as a comparison space, said set

Contains M information bits with minimum error probability in A, M is called comparison space capacity, K is more than or equal to M>0, the error probability of each polarization channel is obtained by simulation through a gaussian approximation method, and the step S3) stops iteration if the following inequality is satisfied:

wherein, R is a proportional threshold value with the value range of { R |0<R≤1}，

L information representing the ith column and ith row nodes in the BP algorithm factor graph.

The above-mentioned polarization code early iteration stopping method based on partial information bit likelihood ratio, wherein, for the polarization code with parameter (N, K), its corresponding factor graph is represented by N-log₂A calculation unit of N order and N +1 columns of nodes, eachThe order is composed of N/2 processing units, wherein (i, j) represents the nodes of the ith row and the jth column from the left, and the soft information of each node passing through the node (i, j) from the right to the left is recorded as L_i,jFrom left to right, the soft information passing through the node (i, j) is denoted as R_i,jHard decision is carried out on soft information in 1 row of nodes at the leftmost end of the factor graph to obtain an estimated value of the information bit sequence u

The step S2) first propagates L of the update nodes to the left_i,jStarting to propagate R in the update node to the right after reaching the leftmost side_i,jAfter the iteration is terminated, if it is not an information bit, the bit is decoded to 0, otherwise according to L in the leftmost node_i,1Determines whether the information bit is 0 or 1.

The above-mentioned polarization code early iteration stop method based on the likelihood ratio of partial information bits, wherein, the step S3) implements an early iteration stop mechanism by using a comparator, an adder and a threshold comparator in combination; after each iteration, using M comparators to compare the current iteration

And obtained from last iteration

t-1 iterations

Reading from memory of BP decoder, t iterations

Directly from the decoder processing unit; the comparison result of the comparator is { q }₁,q₂,...,q_MGet it before

Q is then_i1, otherwise q_i0; the adder being used for calculating

The result is that

The threshold comparator judges whether Q is greater than or equal to M R, if so, D is output to be 1, otherwise, 0 is output; and if D is 1, the BP decoder stops iterating and outputting the decoding result, and if D is 0, the BP decoder continues iterating until the preset maximum iteration number is reached.

In the above method for stopping the early iteration of the polarization code based on the likelihood ratio of the partial information bits, the maximum number of iterations is preset to be 15-80.

Compared with the prior art, the polarization code early iteration stopping method based on the partial information bit likelihood ratio has the advantages that after one iteration is completed, the information bit likelihood ratios which are output by two adjacent iterations and belong to a comparison space are compared, if the proportion of the same information bit likelihood ratio in the comparison space reaches a preset threshold value, the iteration is stopped, and a decoding result obtained in the current iteration step is output, when the maximum iteration time is 40 times and Eb/N0 is 3.5dB, compared with an original BP decoder which is fixed for 40 times, the average iteration time can be reduced by 83.16%, the calculation complexity and the decoding delay are effectively reduced, the addition complexity of the min LL R standard is N, the comparison operation complexity is N, the addition complexity of the L MA standard is 2N, the comparison operation complexity is N, and compared with the addition complexity of the polarization code early iteration stopping method based on the partial information bit likelihood ratio, the addition complexity of the comparison operation is only N/32, the comparison operation complexity is N/32+1, and the hardware complexity of the early iteration stopping standard can be effectively reduced.

Drawings

FIG. 1 is a diagram of the polarization code factor with the parameter (8, 4) according to the present invention;

FIG. 2 is a diagram of the basic elements of the polarization code factor graph of the present invention;

FIG. 3 is a schematic diagram of the early iteration stop flow of the present invention;

FIG. 4 is an early iteration stop module hardware configuration of the present invention;

FIG. 5 is a diagram illustrating comparison between the maximum number of iterations of the BP decoding method with the maximum number of iterations of the polarization code with the parameter (1024,512) of the present invention and the average number of iterations of the original BP decoder under different SNR channels;

fig. 6 is a diagram illustrating comparison between the decoding performance of the BP decoding method with the parameter (1024,512) of the present invention and the decoding performance of the original BP decoder with the maximum iteration number of 40.

Detailed Description

The invention is further described below with reference to the figures and examples.

In order to reduce the decoding complexity of the BP decoding algorithm, the early iteration stop algorithm is very important. The early iteration stop algorithm is used for adaptively detecting whether reliable decoding output is obtained or not in the decoding iteration process, and if the condition is met, the decoding can be immediately finished. The early iteration stop algorithm can linearly reduce the decoding complexity and decoding delay. The invention provides a polarization code early iteration stopping method based on a part of information bit likelihood ratio, which comprises the following steps:

s1) presetting the maximum iteration times of BP decoding;

s2) decoding the polarized coded information by using a BP decoding algorithm;

s3), after one iteration is finished, comparing the information bit likelihood ratios which are output by two adjacent iterations and belong to a comparison space; if the proportion of the same information bit likelihood ratio in the comparison space reaches a preset threshold value, stopping iteration and outputting a decoding result obtained in the current iteration step, otherwise, continuing the iteration until reaching the preset maximum iteration times.

The invention relates to a polarization code BP decoding method with an early iteration stop mechanism, which decodes a channel receiving value by using a BP decoding algorithm, and has the following information updating formula:

f(x,y)≈α*sign(x)sign(y)min(|x|,|y|) (2)

polar code with code length N contains K bits of information bits, and set A is set of information bits. Collection

Called comparison space, containing M with the minimum error probability in A (K ≧ M)>0) The bit information bits, M, are called the comparative spatial capacity, and the error probability of each polarized channel can be simulated by a gaussian approximation method. And in each iteration process of decoding the polarization code by using the BP decoder, if inequality (3) is met, stopping iteration and outputting a decoding result.

Wherein R is more than or equal to 0 and less than or equal to 1,

and L information of the ith row node in the 1 st column in the BP algorithm factor graph, if the inequality (3) is not satisfied, continuing iteration until the preset maximum iteration number is reached.

Compared with the prior art, the method can obviously reduce the decoding iteration times under the condition of not causing the loss of decoding performance. For (1024,512) polar codes, when the maximum iteration number is 40 and Eb/E0 is 3.5dB, the invention can reduce the average iteration number by 83.16%, thereby effectively reducing the computation complexity and the decoding delay. The addition operation complexity of the invention is N/32, and the comparison operation complexity is N/32+ 1.

This embodiment is tested with Polar code with parameters (1024,512), where the code length is N-1024, K-512, and the code rate is 0.5. Simulating by using a Gaussian approximation method under the condition that the signal-to-noise ratio is 1.5dB to obtain the error probability of 1024 sub-channels, wherein 512 sub-channel positions with the minimum error probability form a set A which is used for transmitting information and called information bits; the remaining 512 channels are used to transmit fixed information, called frozen bits. The modulation scheme is Binary Phase Shift Keying (BPSK), and the channel is an Additive White Gaussian Noise channel (AWGN). Code word

Is made up by length of 1024Is/are as follows

And multiplying the generated matrix G. Generating a matrix

Representation matrix

Log of (a)₂1024 ═ 10 kronecker products. Channel received value Y₁ ^NThe method is expressed by using a log-likelihood ratio (L og-likelihood ratio, LL R). in the embodiment, a 7-bit quantization scheme of 1-bit sign bit, 4-bit integer bit and 2-bit decimal bit is adopted, so that the hardware implementation is convenient.

The factor graph of the polarization code with the parameter (1024,512) is represented by log₂1024-10 (a factor graph with a code length of 8 is shown in fig. 1), where each level is composed of N/2-512 processing units (fig. 2 is a schematic diagram of a single processing unit), a column at the leftmost end of the factor graph corresponds to an information bit u, (i, j) indicates a node at the ith row and jth column from the left, each node has two kinds of information, and the present invention records the information passing through the node (i, j) from right to left as L_i,jThe information passing through the node (i, j) from left to right is denoted as R_i,jThese messages pass updates to each other in the form LL R.

In the decoding process, the maximum iteration number of preset iteration is 40, and R is firstly compared with R_i,1And L_i,n+1Proceed to initialization L_i,n+1Initialized to the channel acceptance value Y_i，R_i,1A maximum value of 15.75 that the 0 and 7 bit quantization schemes can represent is initialized based on the position information, respectively. The specific formula is as follows:

L_i,n+1＝Y_i(5)

in this embodimentα is 0.9, propagating L of the update nodes to the left first according to equation (1), (2)_i,jStarting to update R by starting to propagate to the right after reaching the leftmost side_i,j。

The basic flow of the method of the present invention is shown in FIG. 3. in this embodiment, the parameter M is set to 32, and the value β is set to 1/4. in order to reduce the computational complexity and decoding delay of decoding, if L_i,1And the ratio of i ∈ S which is kept unchanged in the previous iteration and the next iteration is more than 1/4, and the decoding output at the moment can be regarded as reliable decoding output.

If the formula (6) is not satisfied, judging whether the decoding times reach 40 times, and if the decoding times reach the maximum iteration times, terminating the iteration; if not, the information is continuously updated, and the next iteration is carried out.

After the iteration is terminated, if the bit is frozen, the bit is decoded to 0, otherwise, L in the leftmost end node is followed_i,1The sign of (2) judges whether the information bit is 0 or 1, and obtains a decoding result. The hard decision of the BP decoder is based on the following formula:

FIG. 4 is a diagram of an early iteration stop module hardware architecture according to the present embodiment, in which M comparators are used to compare current iterations after each iteration

And obtained from last iteration

t-1 iterations

Reading from memory of BP decoder, t iterations

Directly from the decoder processing unit. The comparison result of the comparator is { q }₁,q₂,...,q_MGet it before

Q is then_i1, otherwise q_i0. The adder being used for calculating

The result is that

In this embodiment, the threshold R is set to 1/4, and the threshold comparator determines whether Q is equal to or greater than M × R, and if so, outputs D equal to 1, otherwise outputs 0. And the BP decoder judges whether to stop iteration according to the output result of the early iteration stopping module, namely the decoder stops iterating and outputs the decoding result when D is 1, and continues iteration until the maximum iteration number is reached when D is 0.

The following table shows the computational complexity of the method of the present invention compared to two other early iteration stop criteria. In this embodiment, when M is equal to N/32, the complexity of the addition operation of the present invention is N/32, and the complexity of the comparison operation is N/32+1, which effectively reduces the computational complexity of the early iteration stop criterion.

Early stop criteria	minLLR	LMA	The invention
				Addition operation	N	2N	N/32
Comparison operation	N	N	N/32+1

Fig. 5 shows the Average iteration times of the present implementation and the conventional polarization code BP decoding method in different signal-to-noise ratio channels, where Eb/N0 is the signal-to-noise ratio, and Average number of iterations indicates the Average iteration times, when the maximum iteration time is 40 times and Eb/N0 is 3.5dB, compared with the original BP decoder whose iteration times are fixed to 40 times, the present invention can reduce the Average iteration times by 83.16%, and compared with min LL R (β is 9.5) and L MA, the iteration reduction performance respectively increases by 6.48% and 8.14%.

Fig. 6 shows the test results of the present implementation and the conventional polar BP decoder in a gaussian additive white noise channel. The abscissa Eb/N0 in the figure is the signal-to-noise ratio, fer in the figure is the frame error rate, ber is the bit error rate, and 40Fixed Iteration indicates that the number of iterations is Fixed to 40. According to fig. 6, it can be seen that the present invention can achieve the same decoding performance as the conventional BP decoder without causing decoding performance loss under the condition that the number of iterations is significantly less than that of the conventional BP decoder.

Although the present invention has been described with respect to the preferred embodiments, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims.

Claims (4)

1. A polarization code early iteration stopping method based on partial information bit likelihood ratio is characterized by comprising the following steps:

s1) presetting the maximum iteration times of BP decoding;

s2) decoding the polarization code coding information by using a BP decoding algorithm;

s3), after one iteration is finished, comparing the likelihood ratios of partial information bits output by the BP decoders of two adjacent iterations; if the proportion of the same information bit likelihood ratio in a preset comparison space reaches a preset threshold value, stopping iteration and outputting a decoding result obtained by current iteration, otherwise, continuing iteration until reaching a preset maximum iteration time;

the code length of the polarization code is N, the polarization code comprises K bit information bits, and a set A is set as a set of the information bits

Referred to as a comparison space, said set

The method comprises M information bits with minimum error probability in A, wherein M is called comparison space capacity, K is more than or equal to M and is more than 0, the error probability of each polarization channel is obtained by simulation through a Gaussian approximation method, and the step S3) stops iteration if the following inequality is met:

wherein, R is a proportional threshold value, and the value range is { R |0 is more than R ≦ 1},

l information representing the ith column and ith row nodes in the BP algorithm factor graph.

2. The method as claimed in claim 1, wherein for the polarization code with parameter (N, K), the corresponding factor graph is represented by N-log₂The soft information passing through the node (i, j) from right to left is recorded as L_i,jPassing soft information through node (i, j) from left to rightIs denoted by R_i,jHard decision is carried out on soft information in 1 row of nodes at the leftmost end of the factor graph to obtain an estimated value of the information bit sequence u

The step S2) first propagates L of the update nodes to the left_i,jStarting to propagate R in the update node to the right after reaching the leftmost side_i,jAfter the iteration is terminated, if it is not an information bit, the bit is decoded to 0, otherwise according to L in the leftmost node_i,1Determines whether the information bit is 0 or 1.

3. The partial information bit likelihood ratio-based polarization code early iteration stop method as claimed in claim 2, wherein the step S3) implements the early iteration stop mechanism by using a comparator, an adder and a threshold comparator in combination; after each iteration, using M comparators to compare the current iteration

i ∈ S and the result of the last iteration

i ∈ S, t-1 iterations

Reading from memory of BP decoder, t iterations

Directly from the decoder processing unit; the comparison result of the comparator is { q }₁,q₂,...,q_MGet it before

Q is then_i1, otherwise q_i0; the adder being used for calculating

The result is that

The threshold comparator judges whether Q is greater than or equal to M R, if so, D is output to be 1, otherwise, 0 is output; and if D is 1, the BP decoder stops iterating and outputting the decoding result, and if D is 0, the BP decoder continues iterating until the preset maximum iteration number is reached.

4. The partial information bit likelihood ratio-based early iteration stop method for the polar code as claimed in claim 3, wherein the maximum number of iterations is preset to 15-80.

Images