CN105262494A - Polar code BP decoding method with iterative early-stopping mechanism - Google Patents

Abstract

The invention discloses a polar code BP decoding method with an iterative early stopping mechanism, belonging to the technical field of channel coding. The present invention utilizes the BP decoding algorithm to decode the polarized coding information; the polarized coding information is obtained by first performing CRC coding on the original information and then performing polarized coding; after using the BP decoding algorithm to decode the polarized coding information In each iteration of decoding, the CRC check is performed on the decoding result obtained in the current iteration step. If the verification is passed, the iteration is stopped and the decoding result obtained in the current iteration step is output. Otherwise, continue to Iterate until the preset maximum number of iterations is reached. Compared with the prior art, the present invention can effectively reduce the computational complexity and decoding delay of decoding, and at the same time facilitate hardware implementation.

Description

A Polar Code BP Decoding Method with Iterative Early Stopping Mechanism

technical field

The invention relates to a polar code decoding method, in particular to a polar code BP decoding method with an iterative early stopping mechanism, and belongs to the technical field of channel coding.

Background technique

The polar code (polarcode) was proposed by Erdal Arikan in the article "ChannelPolarization: AMethod for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels". He proved from the theoretical level that through the combination and separation of channels, when the number of channels tends to infinity, some channels tend to be perfect, while some channels tend to be pure noise channels, which is called channel polarization phenomenon. Based on this channel polarization phenomenon, we select a better channel in the combined channel to construct a polar code. ErdalArikan proved that when the number of channels tends to infinity, polar codes can theoretically approach the Shannon limit.

The main decoding methods of polar codes are SC decoding [E.Arikan, "Channel polarization: A method for constructing capacity achieving codes for symmetrical binary-input memoryless channels," Information Theory, IEEE Transactionson, vol.55, no.7, pp.3051–3073, 2009.] and BP decoding [E. Arikan, "Aperformance comparison of polar codes and reed-muller codes,"

Communications Letters, IEEE, vol.12, no.6, pp.447–449, 2008.]. SC decoding has low computational complexity and good error correction performance, but due to the inherent serial operation structure of SC algorithm, it has a long decoding delay. BP decoding was proposed by ErdalArikan in the article "APerformanceComparisonofPolarCodesandReed-MullerCodes". He proved that because polar codes can be represented by factor graphs, polar codes can be decoded by BP (belief propagation) method. Compared with SC decoding, BP decoding has much less decoding delay than SC decoding due to its inherent parallel structure. However, because BP decoding requires multiple iterations to obtain reliable decoding results, the computational complexity of BP decoding is very high. In order to reduce the decoding complexity of BP decoding, the early stop (or called early termination) algorithm is very important. The early stopping algorithm refers to adaptively detecting whether a reliable decoding output has been obtained during the iterative decoding process, and if the condition is satisfied, the decoding can be ended immediately. Early stopping algorithm can linearly reduce decoding complexity and decoding delay.

The core of the iterative early stopping mechanism is how to determine that the decoding output of the current iteration step is reliable enough. At present, researchers have proposed a polar code BP decoding method with an iterative early stopping mechanism. The Polar Code Improved BP Decoding Method of Iterative Strategy", which uses the likelihood ratio of the information bit of the polar code that the mean value of the left information value of the two consecutive changes is less than a preset threshold as the judgment criterion for the early termination of the iteration. The decoding complexity and decoding delay of the BP polar decoding method are reduced. However, this method cannot prove that the required number of iterations is the minimum. Although the number of iterations is reduced to a certain extent, there is still redundancy in the number of iterations. At the same time, this method needs to use the likelihood ratio value information of three consecutive iterations for calculation, which has high computational complexity and high hardware (register) cost. Since the final step of BP decoding is to judge and decode the information bit by the likelihood ratio of the information bit and the sign of the left information instead of the value, and the patent uses the value change less than a preset threshold as the iteration early termination condition, which is obviously not optimal. Moreover, the preset threshold is a fixed value, which is not suitable for complex and changeable channel conditions in real communication scenarios, and is not self-adaptive.

Contents of the invention

The technical problem to be solved by the present invention is to overcome the deficiencies of the prior art and provide a polar code BP decoding method with an iterative early stopping mechanism, which can effectively reduce the computational complexity and decoding delay of decoding, and at the same time facilitate hardware implementation .

The present invention specifically adopts the following technical solutions:

A polar code BP decoding method with an iterative early stopping mechanism, using a BP decoding algorithm to decode polar coded information; the polar coded information is obtained by first performing CRC coding on the original information and then polarizing Encoding; in each iteration process of decoding the polar coding information by using the BP decoding algorithm, the CRC check is performed on the decoding result obtained in the current iterative step. If the check is passed, the iteration is stopped and output The decoding result obtained in the current iteration step, otherwise, continue to iterate until the preset maximum number of iterations is reached.

Compared with the prior art, the method of the invention can significantly reduce the number of decoding iterations without causing loss of decoding performance, especially in a channel with a high signal-to-noise ratio. Moreover, the method has high reliability, high sensitivity and simple hardware implementation. In addition, due to the small enough missed detection rate of CRC, the number of decoding iterations of the decoding method of the present invention can be regarded as sufficient and necessary, that is, it can be regarded as the minimum number of iterations for decoding to obtain a reliable decoding output. Therefore, the present invention can also be used as a criterion for constant convergence speed of each BP algorithm.

Description of drawings

Figure 1 is a factor diagram of a polar code with a code length of 8;

Figure 2 is the basic unit of the polar code factor diagram;

Fig. 3 is a schematic flow sheet of the inventive method;

Fig. 4 is the performance comparison of the inventive method and the traditional polar code BP decoding method;

Fig. 5 is the average number of iterations of the method of the present invention in channels with different signal-to-noise ratios.

detailed description

The technical scheme of the present invention is described in detail below in conjunction with accompanying drawing:

The traditional BP decoding algorithm for polar codes transmits the log likelihood ratio information from right to left on the factor graph shown in Figure 1 (taking a polar code with a code length of 8 as an example). Figure 2 shows the basic units of a polar coding factor graph. The leftmost column of bits in the factor graph corresponds to information u, and the rightmost column of bits corresponds to codeword x. (i, j) represents the node in column i and row j from the left. Each node has two amounts of information. We denote the amount of information passing through node (i, j) from right to left as L _{i, j} , and the amount of information passing through node (i, j) from left to right Denoted as R _i,j , these information are exchanged and updated in the form of LLR. In the decoding process, first initialize the leftmost R information and the rightmost L information according to the following formula:

${\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span>\left\{\begin{array}{ccc}\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; ,</span>& \mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; f</span>}& \mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; A</span>}\\ \mathrm{<span\; class="notranslate">\; \&infin;</span>}<span\; class="notranslate">\; ,</span>& \mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; f</span>}& \mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; \&NotElement;</span>\mathrm{<span\; class="notranslate">\; A</span>}\end{array}\right.<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

${\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; l</span>}\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; P</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; P</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

A in the formula refers to a collection of information bits. Then pass the updated log likelihood ratio information to the right and to the left according to the following formula:

L _i,j =g(L _i+1,2j-1 ,L _i+1,2j +R _i,j+N/2 )

L _i,j+N/2 = g(R _i,j ,L _i+1,2j-1 )+L _i+1,2j

(3)

R _{i+1, 2j-1} = g(R _{i, j} , L _{i+1, 2j} + R _{i, j+N/2} )

R _i+1,2j =g(R _i,j ,L _i+1,2j-1 )+R _i,j+N/2

g(x, y)≈0.9 sign(x)sign(y)min(|x|,|y|)

When the preset maximum number of iterations is reached, if it is not an information bit, the bit is decoded as 0, otherwise according to the leftmost logarithmic likelihood ratio L(1,j) (1 represents the first stage, which is the leftmost, j represents the symbol of the jth bit)

To judge whether the information bit is 0 or 1, the formula on which the judgment is based is as follows:

${\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; u</span>}}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span>\left\{\begin{array}{ccc}\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; ,</span>& \mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; f</span>}& {\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; \&Greater\; Equal;</span>\mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>& \mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; f</span>}& {\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; <</span>\mathrm{<span\; class="notranslate">\; 0</span>}\end{array}\right.<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; )</span>$

For more detailed information on the BP decoding algorithm of traditional polar codes, please refer to [E.Arikan, "Aperformance comparison of polar codes andreed-muller codes,"

Communications Letters, IEEE, vol.12, no.6, pp.447–449, 2008.].

In order to reduce the computational complexity and decoding delay of decoding, and at the same time facilitate hardware implementation, the idea of the present invention is to use Cyclic Redundancy Check (CRC for short) as the decoding output of judging the current iterative step in the BP decoding process Is there a sufficiently reliable basis.

CRC check is a data transmission error detection function. It performs polynomial calculation on data and attaches the result to the frame. The receiving device also executes a similar algorithm to ensure the correctness and integrity of data transmission. When the miss rate of the cyclic redundancy check is low enough, the decoding output satisfying the condition of the cyclic redundancy check is considered reliable. As a mature verification method, CRC verification is simple, convenient and easy to realize by hardware.

Specifically, the present invention first performs CRC encoding on the original information at the encoding end and then performs polar encoding; at the decoding end, in each iteration of decoding, it is judged whether the obtained decoding result satisfies the cyclic redundancy check or not. If the condition of the test is satisfied, the iteration will be stopped in advance, and the decoding output will be obtained.

Consider a polar code with a code length of N, in which there are K bits of information bits. At the encoding end, first sort the channels according to the channel capacity, and select the K best channels. The corresponding K bits are information bits, and the remaining The NK bit below is the frozen bit (frozenbit), and all the frozen bits are set to 0; the cyclic redundancy check (R bit) and the generator polynomial G(x) of an appropriate length are selected, and the code length is 1024, and the information bit is Take the polar code of 512 as an example, the performance of CRC-16 is good enough, but using CRC-8 as an early stop condition will cause the decoding performance to decline; then carry out CRC encoding, that is, the first KR bit of the K information bit is used as the real information bit, and then the R bit is used as the CRC check bit, the remainder obtained by multiplying the first KR bit by x ^R and then divided by the generator polynomial G(x) is the check code; the frozen bit of the NK bit is fixed at 0, and the K bit information bit formed together where G is the generator matrix, and spread in the channel.

Let the code word received by the decoding end be First, initialize the leftmost information and the rightmost information according to formulas (1) and (2); update the information according to formula (3), and check the decoding to get Whether the CRC condition is met, if the condition is met, considering that the selected CRC miss detection rate is low enough, the decoding output at this time is a reliable decoding output, if the condition is not met, judge whether the maximum number of decoding times is reached, if not, then Continue to update the information for the next iteration. The basic flow of the method of the present invention is shown in FIG. 3 .

Fig. 4 shows the Monterot simulation results of the method of the present invention and the traditional polar code BP decoding method in a Gaussian additive white noise channel, and the maximum number of iterations is set to 30 times. The code length of the polar code is 1024, the information bits are 512 bits, and the selected generator polynomial is CRC-16. In the figure, the abscissa EbN0 is the signal-to-noise ratio, the ordinate errorrates is the bit error rate, ber is the bit error rate in the legend, fer is the frame error rate, constantiterations indicates that the number of iterations is constant, and CRC-16aided indicates that the BP proposed by the present invention is used decoding method. According to FIG. 4, it can be seen that the present invention can achieve the same decoding performance as traditional BP decoding when the number of iterations is less than that of traditional BP decoding.

Fig. 5 shows the average number of iterations of the BP decoding method of the present invention in channels with different SNRs, where the CRC is 32 bits and 16 bits respectively, and the polar code length and information bits are 1024 and 512. In the figure, EbN0 is the signal-to-noise ratio, and avg_Iterations represents the average number of iterations. It is easy to see that the present invention can effectively reduce the number of iterations, especially in medium and high signal-to-noise ratio channels, the effect is more remarkable.

Claims (1)

1. there is the polarization code BP interpretation method that iteration early stops mechanism, utilize BP decoding algorithm to carry out decoding to Polarization Coding information; It is characterized in that, described Polarization Coding information obtains by carrying out Polarization Coding again after first carrying out CRC coding to raw information; Carry out in the iterative process each time of decoding utilizing BP decoding algorithm to Polarization Coding information, all the decode results obtained is walked to current iteration and carry out CRC check, as passed through verification, then stop iteration and export current iteration walking the decode results obtained, otherwise, proceed iteration, until reach default maximum iteration time.