CN111988044B - Code word construction method of punctured Polar code - Google Patents

Abstract

The invention discloses a code word construction method of a punctured Polar code, which comprises the following steps: determining encoding parameters and setting a polarization kernel; sequencing all the split sub-channels according to the channel capacity of the split sub-channels, and constructing an information sequence according to a fixed coding length; calculating a polarization generating matrix according to the fixed coding length and the polarization kernel; calculating an initial coding sequence according to the information sequence and the polarization generating matrix; sequentially selecting a columns in the column weight of each column of the polarization generating matrix, and constructing a code word deleting matrix according to the index number of the column weight; and according to the code word deletion matrix, respectively indexing the elements at the corresponding positions in the initial coding sequence and deleting the elements to obtain the final coding sequence. The invention deletes the code words according to the correlation degree of the code mapping, not only realizes low complexity and high application flexibility of Polar codes, but also has better decoding performance, ensures the stability of a communication system and has wide application prospect.

Description

A codeword construction method for punctured Polar codes

technical field

The invention belongs to the field of digital communication channel coding, and in particular relates to a codeword construction method for punctured Polar codes.

Background technique

Polar code is a coding scheme for communication proposed by Professor E. Arikan in 2009. In theory, it is a coding method that can be proved by rigorous mathematical reasoning to reach the Shannon limit. At the transmitting end, N independent channels are mutually polarized, and the channel capacity of the split sub-channels tends to be 0 or 1. The channel polarization process is shown in Figure 1, including two processes of channel combining and channel splitting. When the code length tends to infinity, some channels become pure noise channels, and the other part channels become noiseless channels. The ratio of split sub-channels with a channel capacity of 0 or 1 after polarization to the total channel varies with the code length as shown in Figure 2, and the channel capacity distribution diagram when the code length N=512 is also shown in Figure 3. At the receiving end, the special structure of the polar code makes it possible to use the serial cancellation algorithm to obtain a performance similar to the maximum likelihood decoding with a lower complexity. Excellent performance makes it an important coding method for 5G communication.

Since the traditional polar code is constructed based on the Kronecker power of the Arikan kernel, the code length of the polar code is limited to 2 ⁿ (n is a positive integer), and in the actual communication system we know the original information The length is often uncertain, so the encoding can be adjusted according to the length of the original information, which is a problem we must consider. Although the use of other polarized cores, such as BCH code cores, can achieve the purpose of constructing other code lengths, but the code length is still Limited by the power of the kernel length, and the decoding structure of the Polar code constructed by this method is more complicated; although some current codeword deletion algorithms can construct Polar codes of any length, they are not enough to consider factors when deleting codewords. sufficient, the constructed Polar code has poor performance, which impairs the performance of the communication system. Therefore, it is urgent to develop a codeword construction method for punctured Polar codes with better performance to meet communication requirements.

SUMMARY OF THE INVENTION

The present invention provides a method for constructing a codeword of a punctured Polar code, which is convenient to use and has excellent decoding performance. .

For realizing the above-mentioned technical purpose, the present invention adopts following technical scheme:

A codeword construction method for puncturing Polar codes, comprising the following steps:

Step 1, determine the encoded information bit length K, the fixed encoding length N and the final encoding length M, and set the polarization core of the polarization encoding;

Step 2, sorting all N split sub-channels after channel polarization under a specific signal-to-noise ratio according to their channel capacity, and constructing an information sequence of length N according to the sorted channel capacity matrix and the fixed coding length K;

Step 3, according to the fixed code length N and the polarization kernel, calculate the polarization generator matrix;

Step 4, according to the information sequence obtained in step 2 and the polarization generator matrix obtained in step 3, obtain an initial coding sequence with a length of N;

Step 5: Calculate the column weight of each column of the polarization generation matrix, select column a in order of magnitude according to the column weight, and construct a codeword deletion matrix of length a according to the index number of the a column in the polarization generation matrix ;

Wherein a takes the value according to the number of codewords to be deleted: a=N-M;

Step 6, according to the value of a element in the codeword deletion matrix, index to the corresponding element in the initial coding sequence and delete it to obtain a final coding sequence with a length of M.

Further, in step 5, when selecting the a-th column, if there are several columns with the same column weight, the odd-numbered column with a larger index number is preferentially selected.

Further, the calculation formula of the polarization generating matrix G _N is:

表示对极化核F进行n次Kronecker幂计算，B_N表示对得到的

进行反序重排，其中N＝2ⁿ。In the formula, F represents the polarized nucleus,

Indicates that n times Kronecker power calculation is performed on the polarized nucleus F, and B _N represents the obtained

Reverse order rearrangement is performed, where N=2 ⁿ .

Further, the specific process of the step 2 is as follows: firstly, all polarized split sub-channels are marked as W ₁ , W ₂ ,..., W _N , and the density evolution method is used to analyze the N sub-channels with a specific signal-to-noise ratio. The channel capacity of the split sub-channels is sorted; then the K split sub-channels with large channel capacity are used to set information bits, and the remaining NK split sub-channels are set to freeze bits or fixed bits to construct an information sequence of length N.

Further, the calculation formula of the initial coding sequence in step 4 is:

表示初始编码序列，包括用于标志信息位的1和用于标志冻结位或固定位的0；

表示信息序列，G_N表示极化生成矩阵。In the formula,

Indicates the initial coding sequence, including 1 for marking information bits and 0 for marking frozen bits or fixed bits;

represents the information sequence, and _GN represents the polarization generator matrix.

beneficial effect

The advantages of the codeword construction method of the punctured Polar code provided by the present invention are: the calculation and operation methods are simple and easy to operate, the calculation complexity is low, and both the encoder and the decoder are known to delete the initial coding sequence. It can construct Polar codes with arbitrary code lengths, which overcomes the application limitations of traditional Polar codes. At the same time, the present invention deletes the code word according to the correlation degree of the coding mapping, and constructs the Polar code of any code length by deleting the code word sequence output by the encoder as "no damage" as possible, so as to ensure the effective transmission of information. Polar codes with arbitrary code lengths improve application flexibility and at the same time greatly reduce the decoding error rate, that is, improve the decoding performance of Polar codes with arbitrary code lengths and ensure the stability of the communication system. In current and future communications Has broad application prospects.

Description of drawings

Fig. 1 is a schematic diagram of the polarization process of the channel polarization phenomenon;

FIG. 2 is a schematic diagram showing the relationship between the proportion of split sub-channels with a channel capacity of 0 or 1 and the code length N;

Fig. 3 is a channel capacity distribution diagram with a code length N of 512;

Fig. 4 is a simplified diagram of polarization coding mapping;

5 is a schematic diagram of a coding mapping class defined in the present invention;

Fig. 6 is the schematic flow chart of the method of the present invention;

FIG. 7 is a comparison diagram of the performance advantages of the method of the present invention and the existing method when the values are N=32, M=28, and K=16;

FIG. 8 is a comparison diagram of the performance advantages of the method of the present invention and the existing method when the values are N=128, M=110, and K=64.

Detailed ways

The embodiments of the present invention are described in detail below. This embodiment is carried out on the basis of the technical solutions of the present invention, and provides a detailed implementation manner and a specific operation process, and further explains the technical solutions of the present invention.

The present invention provides a method for constructing a codeword of a punctured Polar code, which is convenient to use and has excellent decoding performance. Application flexibility and its bit error rate performance, as shown in Figure 6, includes the following steps:

Step 1: Determine the coding parameters, and set the polarized core required for polarized coding.

The encoding parameters specifically include the encoding information bit length K, the fixed encoding length N, and the final encoding length M. The final code length M is the length of the constructed Polar code of any code length, and they satisfy the relationship: K<M<N, N=2 ⁿ , and n is a positive integer; the polarization kernel is set as

Step 2: Sort all N split sub-channels after channel polarization under a specific signal-to-noise ratio according to their channel capacity, and construct an information sequence of length N according to the sorted channel capacity matrix and the fixed coding length K, The specific process is:

Step 2.1, mark all polarized split sub-channels as W ₁ , W ₂ ,...,W _N , and use the density evolution method to sort the channel capacity of the N split sub-channels under a specific signal-to-noise ratio;

Step 2.2, the K split sub-channels with large channel capacity are used to set information bits, and the remaining NK split sub-channels are set to freeze bits or fixed bits to construct an information sequence of length N.

其中，

表示对极化核F进行n次Kronecker幂计算，B_N表示进行反序重排计算。Step 3, according to the fixed code length N and the polarization core F, calculate the polarization generator matrix G _N , and the calculation formula is:

in,

Indicates that n times of Kronecker power calculations are performed on the polarized core F, and B _N represents the reverse order rearrangement calculation.

和步骤3得到的极化生成矩阵G_N，得到长度为N的初始编码序列

计算公式为：

Step 4, according to the information sequence obtained in step 2

and the polarization generator matrix G _N obtained in step 3 to obtain an initial coding sequence of length N

The calculation formula is:

表示根据步骤2得到的信息序列(u₁,u₂,u₃,…,u_N)，其中包含K个信息位和N-K个冻结位；

表示经计算得到的初始编码序列(x₁,x₂,x₃,…,x_N)。in

represents the information sequence (u ₁ , u ₂ , u ₃ ,..., u _N ) obtained according to step 2, which contains K information bits and NK frozen bits;

represents the calculated initial coding sequence (x ₁ , x ₂ , x ₃ , . . . , x _N ).

Step 5, according to the polarization generation matrix _GN obtained in step 3 and the number a of codewords to be deleted, calculate the codeword deletion matrix, and specifically adopt the following steps to calculate and obtain the codeword deletion matrix:

Step 5.1, set the product factor; multiply and accumulate all elements of each column of the polarization generation matrix G _N and the product factor to obtain the column weight of the corresponding column of the polarization generation matrix G _N ;

Step 5.2, select columns 1 to a at a time according to the column weights, and mark their indices and store them as the codeword deletion matrix z; when the a-th column is selected with the same weight, the odd-numbered columns with larger index numbers are preferentially selected .

The value of the number a of codewords to be deleted is: a=N-M.

经极化编码后得到的初始编码序列

他们之间并不是一对一关系，例如u₁经极化编码之后并不就是x₁。经研究发现，它们之间存在一个关联程度，当在码字端删除与信息序列中冻结位关联程度最大的码字位时，得到的凿孔极化码(即任意码长的极化码，亦即本发明所述的最终编码序列)性能最优。当信息序列中的u₁为冻结位的时候，初始编码序列中的x₁并不一定是与冻结位u₁关联程度最大的位，这是由于极化生成矩阵G_N的作用。经研究得到，在极化编码中存在编码映射分类的差别，本发明将之定义为一类映射和二类映射，如图5所示。编码映射中的一类映射数目越多，信息序列与初始编码序列的位之间的关联程度越大，反应到生成矩阵G_N中就是列权重的大小，因此本发明选择列权重最大的列索引号作为码字删除矩阵的元素，从而索引到初始编码序列的相应位置的信息并删除，得到最终编码序列，即任意码长的极化码。当存在列权重相同的列时，优先选择数值较大的奇数列索引号。In the coding mapping of polar codes, as shown in Figure 4, the information sequence

The initial coding sequence obtained after polar coding

There is no one-to-one relationship between them. For example, u ₁ is not x ₁ after polarization coding. After research, it is found that there is a degree of correlation between them. When the codeword bit with the greatest degree of correlation with the frozen bit in the information sequence is deleted at the codeword end, the obtained punctured polar code (that is, the polar code of any code length, That is, the final coding sequence described in the present invention has the best performance. When u ₁ in the information sequence is a frozen bit, x ₁ in the initial coding sequence is not necessarily the bit most related to the frozen bit _{u 1} , which is due to the effect of the polarization generation matrix GN. It is obtained through research that there is a difference in the classification of coding mappings in polar coding, which is defined as a first-class mapping and a second-class mapping in the present invention, as shown in FIG. 5 . The more the number of one type of mapping in the coding mapping, the greater the degree of correlation between the information sequence and the bits of the initial coding sequence, which is reflected in the generator matrix G _N is the size of the column weight, so the present invention selects the column index with the largest column weight. The number is used as an element of the codeword deletion matrix, so that the information of the corresponding position of the initial coding sequence is indexed and deleted to obtain the final coding sequence, that is, the polar code of any code length. When there are columns with the same column weight, the odd-numbered column index number with the larger value is preferred.

Step 6, delete a element value in the matrix according to the codeword, the element value is the column index number with the largest column weight in the polarization generation matrix G _N , respectively index to the element at the corresponding position in the initial coding sequence and delete it to obtain: The final coding sequence of length M is the codeword of any code length M

Since the column weight of each column in the polarization generation matrix G _N reflects the degree of correlation between the coding and mapping between the information sequence and the initial coding sequence, the present invention uses the correlation degree as the core of designing the punctured polar code The idea is to use the column weights of each column in the polarization generation matrix to construct the codeword deletion matrix, and then use the codeword deletion matrix to index to delete the codewords in the initial coding sequence that are most closely related to the frozen bits or fixed bits. , so that the performance of the polar code is affected as little as possible, so a polar code of any code length with better performance can be finally obtained.

Below, in conjunction with a specific embodiment, the method of the present invention is further described:

When constructing any Polar code whose code length is not 2 ⁿ , the correlation degree of coding mapping is used as the main reference element, which is mainly reflected in the calculation of the column weight of the generator matrix. The elements of the word deletion matrix are stored, and the initial coding sequence is deleted bit by bit according to the matrix to realize Polar coding of arbitrary code length.

First determine the encoded information bit length K=4, the fixed encoding length N=8 and the final encoding length M=5, where M is the length of the constructed Polar code with any code length, and the polarization kernel adopts the Arikan kernel

All the polarized split sub-channels are marked as W ₁ , W ₂ , W ₃ , W ₄ , W ₅ , W ₆ , W ₇ , W ₈ , and the density evolution method is used to analyze the eight split sub-channels under a specific signal-to-noise ratio. The channel capacity of the channel is sorted, and the sorted channel index sequence is marked as matrix j=[W ₄ W ₇ W ₆ W ₈ W ₁ W ₃ W ₂ W ₅ ], according to the channel capacity and coding parameter information bit K=4 , select 4 split sub-channels with larger channel capacity (ie W ₄ , W ₇ , W ₆ , W ₈ ) to transmit information bits to obtain information sequence

对F进行n次Kronecker幂

计算得到极化矩阵G：set polarized nucleus

Raising F to the Kronecker power n times

Calculate the polarization matrix G:

Rearrange the polarization matrix G in reverse order to obtain the polarization generating matrix G ₈ :

The number of deleted code words a=N-M=8-5=3;

是为初始编码序列；经过第一类映射数目计算，即折射至生成矩阵中表现为计算列权重大小。设乘积因素为1，则G₈中第1列的列权重为8，为所有列中最大，第2，3，5列的列权重都为4，我们需要选取三列进行删除，由奇数列大数目准则选取第1，3，5列进行删除，得到码字删除矩阵z＝[1 3 5]；information sequence

is the initial coding sequence; after the number of mappings of the first type is calculated, the refraction into the generator matrix is expressed as the calculation of column weights. Assuming that the product factor is 1, the column weight of the first column in G ₈ is 8, which is the largest among all columns, and the column weights of the second, third, and fifth columns are all 4. We need to select three columns to delete, by the odd column The large number criterion selects the 1st, 3rd, and 5th columns for deletion, and obtains the codeword deletion matrix z=[1 3 5];

中相应位置索引进行删除得到最终编码序列

Delete the elements in the matrix z according to the codeword, and the initial coding sequence

Delete the corresponding position index in the final code sequence

FIG. 7 and FIG. 8 are performance simulation result diagrams of the present invention, wherein BER in the figures refers to the bit error rate, and FER refers to the frame error rate, which are the key indicators for checking the correctness of decoding. It can be seen from the figure that when constructing a Polar code of arbitrary code length, the performance of the method used in the present invention is obviously improved compared with the method proposed in the existing paper.

The labels of the steps described in the present invention do not represent the sequence of execution of the steps, and those skilled in the art can change the execution sequence of the above steps (for example, the execution sequence of step 2 and step 3, the execution sequence of step 4 and step 5) , can be arbitrarily exchanged, and there is no conflict in the execution of subsequent steps), all belong to the protection scope of the present invention.

The above embodiments are the preferred embodiments of the application, and those of ordinary skill in the art can also carry out various transformations or improvements on this basis. Without departing from the general concept of the application, these transformations or improvements should belong to the present application. within the scope of the application for protection.

Claims (4)

1. a codeword construction method of perforated Polar code, is characterized in that, comprises the following steps: Step 1, determine the encoded information bit length K, the fixed encoding length N and the final encoding length M, and set the polarization core of the polarization encoding; Step 2, sorting all N split sub-channels after channel polarization under a specific signal-to-noise ratio according to their channel capacity, and constructing an information sequence of length N according to the sorted channel capacity matrix and the fixed coding length K; Step 3: Calculate the polarization generator matrix according to the fixed encoding length N and the polarization kernel; Step 4, according to the information sequence obtained in step 2 and the polarization generator matrix obtained in step 3, obtain an initial coding sequence with a length of N; Step 5: Calculate the column weight of each column of the polarization generation matrix, select column a in order of magnitude according to the column weight, and construct a codeword deletion matrix of length a according to the index number of the a column in the polarization generation matrix ; Wherein a takes the value according to the number of codewords to be deleted: a=N-M; When selecting the a-th column, if there are several columns with the same column weight, select the odd-numbered column with a larger index number; Step 6, according to the value of a element in the codeword deletion matrix, index to the corresponding element in the initial coding sequence and delete it to obtain a final coding sequence with a length of M. 2. method according to claim 1, is characterized in that, the calculation formula of polarization generation matrix G _N is:

In the formula, F represents the polarized nucleus,

Indicates that n times Kronecker power calculation is performed on the polarized nucleus F, and B _N represents the obtained

Reverse order rearrangement is performed, where N=2 ⁿ . 3. The method according to claim 1, wherein, the specific process of step 2 is: firstly mark all polarized split sub-channels as W ₁ , W ₂ ,...,W _N , The density evolution method is used to sort the channel capacity of N split sub-channels under a specific signal-to-noise ratio; then the K split sub-channels with large channel capacity are used to set information bits, and the remaining NK split sub-channels are set to freeze bits or fixed bits , construct an information sequence of length N

4. method according to claim 1, is characterized in that, in step 4, the calculation formula of initial coding sequence is:

In the formula,

Indicates the initial coding sequence, including 1 for marking information bits and 0 for marking frozen bits or fixed bits;

represents the information sequence, and _GN represents the polarization generator matrix.

Images