CN106998208B - Code word construction method of variable length Polar code - Google Patents

Abstract

The invention provides a codeword construction method of a variable-length Polar code, which belongs to the field of communication. The present invention realizes the construction of the long code generation matrix by extending the generation matrix of the short code, firstly, based on the integer binary representation, the code length is expressed as the summation form of the power of 2; then the value of each item constituting the summation form is expressed as the size of the submatrices that make up the new generator matrix; finally, the new generator matrix is constructed by the combo‑sum combinatorial operation. Compared with the construction method of the traditional variable-length Polar code, the present invention does not need the puncturing and deletion operation, reduces the coding complexity, reduces the time delay, and the likelihood information of the unknown bits is known at the decoding end, avoiding the traditional traditional method. The problem of estimating unknown bit likelihood information using prior knowledge reduces the bit error rate of decoding and improves system performance.

Description

A Codeword Construction Method for Variable Length Polar Codes

technical field

The invention belongs to the field of communication channel coding, in particular to a codeword construction method of a variable-length Polar code.

Background technique

提出的一种新型信道编码。极化码基于信道极化(Channel Polarization)进行设计，是第一种能够通过严格的数学方法证明达到信道容量的构造性编码方案。然而，极化码由Kronecker幂构造，这种构造方式限制了Polar码的码长，不便于Polar码在实际系统中的使用。原始方法只能构造码长为2ⁿ(n＝1,2,...)的Polar 码。尽管其他码长的Polar码可以由BCH码核等其他极化核构造，但是这种方法构造的Polar 码码长依然限制在核长的幂次，并且这种方法构造的Polar码的译码结构较为复杂。Polar Codes, or polar codes, was created in 2009 by E.

A new type of channel coding proposed. Polar codes are designed based on channel polarization (Channel Polarization), and are the first constructive coding scheme that can be proved to achieve channel capacity through rigorous mathematical methods. However, polar codes are constructed from Kronecker powers, which limits the code length of Polar codes and is inconvenient for Polar codes to be used in practical systems. The original method can only construct Polar codes with code length ²ⁿ (n=1,2,...). Although Polar codes of other code lengths can be constructed by other polarized cores such as BCH code cores, the code length of the Polar codes constructed by this method is still limited to the power of the core length, and the decoding structure of the Polar codes constructed by this method more complicated.

It is well known in the art that in an actual communication system, the length of the original information is often uncertain, which requires that the encoding can be adjusted according to the length of the original information. That is, a coding structure with a series of different code lengths and rates is obtained according to the channel conditions and the length of the information. At present, the codeword structure of the existing variable length polar code adopts the codeword structure that is not a power of 2 by deleting part of the codeword bits whose original length is a power of 2. In this method, the likelihood information of the deleted codeword bits is set to 0, 1, etc. probability during decoding at the receiving end, and then the ordinary polar code is decoded. Although this method realizes the construction of Polar code with variable code length, its decoding error probability is also improved, which seriously loses the performance of the communication system. Therefore, there is a need for a better codeword construction method for variable code length Polar codes.

SUMMARY OF THE INVENTION

Based on this requirement, the present invention proposes a codeword construction method of a variable-length Polar code, which combines the generator matrix of the Polar code whose original length is limited to a power of 2 to realize the construction of the generator matrix of the Polar code with any code length.

A method for constructing a codeword of a variable-length Polar code provided by the present invention includes the following steps:

Step 1: Binary expansion of the code length N to obtain the corresponding binary bit sequence s; where N is a positive integer;

Step 2: Determine the size of the generator matrix to be selected according to the position of "1" in the binary bit sequence s obtained in step 1.

h_d为正整数，序列s从低位到高位从1开始进行索引编号。Let the number of bits with a value of "1" in the sequence s be q, where the bit value of the index number h _d in the sequence s is 1, and d represents the d-th 1 that appears from the high order to the low order in the sequence s, d=1, 2 ,…q. Then select the original generator matrices of q polar codes, which are square matrices of size l ₁ , l ₂ ,..., l _q , respectively,

h _d is a positive integer, and the sequence s is indexed from low to high from 1.

Step 3: Combining the above selected sub-matrices through the Combo-Sum operation, thereby obtaining a generator matrix with a code length of N.

则码长为N的生成矩阵C表示为：Assuming that q generator matrices are obtained according to step 2

Then the generator matrix C with code length N is expressed as:

其中，

表示Combo-Sum运算。

in,

Represents a Combo-Sum operation.

和

得到组合矩阵为：The described Combo-Sum operation is: let the matrix participating in the operation be

and

The combined matrix is obtained as:

Among them, L ₁ and L ₂ are the sizes of the matrices A and B respectively, the size of the matrix B' is L ₂ ×L ₁ , the first L ₂ columns in B' are the same as the matrix B, and the last L ₁ -L ₂ columns are all 0s List.

The advantages and positive effects of the present invention are: the codeword construction method of the present invention is realized by Combo-Sum operation, and the Polar code constructed by the method can effectively reduce the decoding error probability and improve the performance of the communication system. Compared with the traditional method, the invention realizes the construction of the long code generation matrix by extending the generation matrix of the short code, does not need to delete the punching operation, reduces the coding complexity and reduces the time delay. The invention knows the likelihood information of unknown bits at the decoding end, avoids the problem of using prior knowledge to estimate the likelihood information of unknown bits in traditional traditional methods, thereby reducing the bit error rate of decoding and improving system performance.

Description of drawings

1 is a schematic flowchart of a codeword construction method proposed by the present invention;

Fig. 2 is three specific examples of the original generator matrix used in the process of constructing the generator matrix of the present invention;

FIG. 3 is a schematic diagram of the general correspondence between the newly generated matrix and the sub-matrix of the present invention.

Detailed ways

The present invention will be further described in detail below with reference to the accompanying drawings and embodiments.

As shown in FIG. 1 , in the method for constructing a codeword of a variable-length Polar code according to the present invention, the following steps 1 to 3 are used to realize the construction of the generating matrix of the Polar code.

Step 1: The binary bit sequence representation is obtained by binary expansion for the code length N. N is a positive integer.

For code length N, use binary expansion to obtain m-bit binary bit sequence s={s _m , s _m-1 ,..., s ₂ , s ₁ }, let h be the index number of the binary bit sequence from low to high, h=1,2,...m, sh represents the bit value of the index position _{h in the sequence s, s h ∈} {0,1}, m represents the index position of the highest bit 1 of the binary sequence, s _m =1.

Here, the code length N can take any positive integer, and it does not need to be limited to the form of a power of 2 as the code length of the original polar code.

For example, when the code length N=13, the corresponding binary sequence s={1,1,0,1}.

Step 2: Determine the generator matrix to be selected by the combination operation according to the position of "1" in the obtained binary expansion sequence.

Find the position where the bit value is "1" in the binary expansion sequence, and let the number of "1" be q. According to the binary expansion sequence obtained in step 1, N can be expressed as:

Formula (1) indicates that N is expressed as a power of 2 according to the position of 1 in the binary bit sequence, wherein the bit value of the index number h _d in the sequence s is 1, and d represents the sequence s from high to low. The dth 1.

l_d是自然数并且为2的幂次形式。Then select the original generator matrix of q polar codes, where the size of the dth generator matrix is

l _d is a natural number and is a power of 2.

其中

表示l_d×l_d的方阵，矩阵

为Polar码原始生成矩阵，通过克罗内克乘积产生，即

其中矩阵

参数 n＝log₂l_d，

表示克罗内可乘积运算，该克罗内可乘积运算和原始生成矩阵为领域内所公认。Select the original generator matrix of q 1 _d × 1 _d Polar codes corresponding to the binary decomposition of N as the sub-matrix to be selected by the combination operation, and the selected sub-matrix is expressed as

in

Represents a square matrix of l _d ×l _d , a matrix

The original generator matrix for the Polar code is generated by the Kronecker product, that is

where the matrix

The parameter n=log ₂ l _d ,

Represents the Crone productable operation, which is known in the field, and the original generator matrix.

For example: when the code length N=6, 6=2 ² +2 ¹ =l ₁ +l ₂ , l ₁ =4, l ₂ =2, then select the generator matrix G _{4×4 with the original Polar code code length 4} The generator matrix G _2×2 with a code length of 2 is used as a sub-matrix constituting a generator matrix with a code length of 6, and the specific values of the generator matrices G _4×4 and G _2× 2 are shown in FIG. 2 .

When the code length N=8, 8=2 ³ =l ₁ , it can be seen that the construction of the original Polar code generator matrix whose length is a power of 2 is only a special case of the method of the present invention, and the generator matrix G _8×8 is shown in Figure 2 shown.

Step 3: Combine the above-selected generator matrices through the Combo-Sum operation, thereby constructing a generator matrix with a code length of N.

矩阵

和

是方阵，L₁、L₂分别为矩阵A、B的大小。为了得到任意的大小C，A和B的大小不需要相同，这里取L₁≥L₂。式中矩阵B′除了全0列以外，和矩阵B相同，B′大小为L₂×L₁，其中，B′的前L₂列与矩阵B 中的列相同，后L₁-L₂列为全0列。Firstly, the definition of matrix Combo-Sum operation is proposed. Combo-Sum is a combined operation of two matrices. The sum C of Combo-Sum of matrix A and matrix B can be expressed as

matrix

and

is a square matrix, and L ₁ and L ₂ are the sizes of the matrices A and B, respectively. In order to obtain an arbitrary size C, the sizes of A and B do not need to be the same, here L ₁ ≥L ₂ is taken. In the formula, matrix B' is the same as matrix B except for all 0 columns, and the size of B' is L ₂ ×L ₁ , where the first L ₂ columns of B' are the same as the columns in matrix B, and the last L ₁ -L ₂ columns are the same as those in matrix B . for all 0 columns.

x₂表示后L₂个码字，

u₁表示编码输入序列的前L₁个比特，

u₂表示编码输入序列的后L₂个比特，

根据矩阵C的结构，x₁由u₁和u₂通过矩阵A和B′共同得到

x₂由u₂通过矩阵B得到x₂＝u₂B，所以生成码字x可以表示为

The codeword obtained by the matrix C as the generator matrix can be expressed as x=uC, and then further decompose x and u into two parts, respectively expressed as x=(x ₁ , x ₂ ) and u=(u ₁ , u ₂ ) , x represents the encoded codeword vector obtained from the generator matrix, x ₁ represents the first L ₁ codewords,

x ₂ represents the last L ₂ code words,

u ₁ represents the first L ₁ bits of the encoded input sequence,

u ₂ represents the last L ₂ bits of the encoded input sequence,

According to the structure of matrix C, x ₁ is jointly obtained by u ₁ and u ₂ through matrices A and B'

x ₂ is obtained from u ₂ through matrix B x ₂ =u ₂ B, so the generated codeword x can be expressed as

其中i表示矩阵的行索引，j表示矩阵的列索引，L₁,L₂表示方阵的大小，并且L₁≥L₂。定义两个矩阵进行Combo-Sum 运算得到组合

表示Combo-Sum组合运算，其中：Combo-Sum operation definition: Given two square matrices

where i represents the row index of the matrix, j represents the column index of the matrix, L ₁ , L ₂ represent the size of the square matrix, and L ₁ ≥ L ₂ . Define two matrices for Combo-Sum operation to get a combination

Represents a Combo-Sum combinatorial operation, where:

The corresponding specific bit positions of c _ij represented by formula (2), a _ij and b _ij are shown in FIG. 3 . Among them, Γ is a subset of {1,2,...,L ₁ }, called the difference set, the number of set elements is L ₂ , and Γ is the set of non-zero columns of matrix B', which must be B' The first L ₂ columns of , but the value order is not necessarily in the order of 1, 2, .... Let the index in the set Γ be marked as j ₀ =1,2,...,L ₂ , the index j in the matrix C is the j _0th element in the set Γ, determine j ₀ from Γ according to j, and obtain the corresponding c _ij The elements in matrix B of

Combo-Sum和C可以表示为when

Combo-Sum and C can be expressed as

The corresponding bit position represented by equation (3) is shown in FIG. 3 .

E.g

有以下限定：Combinatorial operations

The following restrictions apply:

① The A and B matrices involved in the operation cannot be exchanged in order.

②The size of the first matrix cannot be smaller than the second matrix, that is, l ₁ ≥l ₂ .

③The result of Combo-Sum operation is not unique. Different difference sets Γ and order of operations will result in different Combo-Sum sums.

For example, the construction of a generator matrix with a code length of 5 can have the following two construction methods:

Construction method one:

Construction method two:

The long code can be decomposed into two or more short codes. Since the Combo-Sum operation is not unique, in step 3, when determining the submatrix participating in the Combo-Sum operation, the binary decomposition sequence obtained in step 2 is strictly in accordance with the code length N and representation.

而不能表示为

和

组合形式或者其它表示形式。For example, the generator matrix of N=5 can only be expressed as

rather than being expressed as

and

combination or other representation.

对其进行Combo-Sum组合运算，规定在组合运算过程中，每次选择码长最大的两个生成矩阵参与Combo-Sum组合运算，即根据q个原始生成矩阵通过Combo-Sum运算得到的码长为N 的生成矩阵

Therefore, the calculation process of step 3 is based on the q original generator matrices obtained in step 2

The Combo-Sum combination operation is performed on it, and it is stipulated that in the process of combination operation, the two generator matrices with the largest code length are selected each time to participate in the Combo-Sum combination operation, that is, the code length obtained by the Combo-Sum operation according to the q original generator matrices generator matrix of N

矩阵组合表示为：For example, the generator matrix combination operation process of code length N=7 is: according to step 2, the generator matrices participating in the combination operation are obtained as G _4×4 , G _2×2 , G _1×1 , according to the operation criterion: select the largest one each time Two generator matrices participate in the operation, then

The matrix combination is expressed as:

The combination matrix obtained by each Combo-Sum operation is used as a new sub-matrix, and its sub-matrix is generated by replacing the combination, and it continues to participate in the next round of Combo-Sum operation until only one sub-matrix remains, and the final code length is N The generator matrix C.

Embodiment 1 : The generator matrix construction process of the Polar code with code length N=6.

Step 1: A binary bit sequence with code length N=6 is represented as s={1,1,0}.

Step 2: According to the binary bit sequence obtained in Step 1, select the combination matrix that constitutes the code length N=6:

According to 6=2 ² +2 ¹ =l ₁ +l ₂ , the submatrices constituting the code length of 6 are obtained as G _4×4 , G _2×2 .

运算过程如下：Step 3: Combine the submatrices that form the generator matrix of code length N=6 obtained in Step 2 by Combo-Sum operation.

The operation process is as follows:

Embodiment 2 : The construction process of the generator matrix of the Polar code with the code length N=11.

Step 1: A binary bit sequence of code length N=11 is represented as s={1,0,1,1}.

Step 2: According to the binary bit sequence obtained in Step 1, select a combination matrix that constitutes a code length N=11:

According to 11=2 ³ +2 ¹ +2 ⁰ =l ₁ +l ₂ +l ₃ , the size of the submatrix is l ₁ =8, l ₂ =2, l ₃ =1. Therefore, the submatrices with a code length of 11 are obtained as G _8×8 , G _2×2 , and G _1×1 .

运算过程如下：Step 3: Combine the submatrices that form the generator matrix with the code length N=11 obtained in Step 2 through the Combo-Sum operation.

The operation process is as follows:

Claims (3)

1. a code word construction method of Polar codes with variable code length is characterized by comprising the following steps:

step 1: spreading the code length N binary system to obtain a corresponding binary bit sequence s; wherein N is a positive integer;

step 2: determining the size of a generating matrix to be selected according to the position of '1' in the obtained binary bit sequence s;

let q be the number of bit values "1" in the sequence s, where h is the index number in the sequence s_dD represents the d-th 1 occurring from the upper to the lower in the sequence s, and d is 1,2, … q; then, the generator matrices of q polar codes are selected, and the size is l₁,l₂,...,l_qThe square matrix of (A) is formed,

h_dis a positive integer(ii) a The sequence s is indexed from 1 from the low order to the high order;

and step 3: combining the selected generator matrixes through Combo-Sum operation to obtain a generator matrix with the code length of N;

obtaining q generating matrixes according to the step 2

The generator matrix with code length N is represented as:

wherein,

represents Combo-Sum operation;

the Combo-Sum operation is: let the matrix involved in the operation be

And

the resulting combined matrix C is:

wherein L is₁、L₂Respectively, the size of the matrix A, B, and the size of the matrix B' is L₂×L₁Front L in B₂Column and matrix B are identical, last L₁-L₂The columns are all 0 columns.

2. The method for constructing Polar code words with variable code length according to claim 1, wherein in the step 3, the Combo-Sum operation is implemented by: let two matrices participate in Combo-Sum operation as

And

the Combo-Sum operation result of the two matrices is

Wherein the elements

Wherein Γ is {1, 2., L₁A subset of the set, called the difference set, with L elements of the set Γ₂Index in the set Γ is marked j₀＝1,2,...,l₂J-th of the set Γ₀The value of each element is an index j in C.

3. The method as claimed in claim 2, wherein in the Combo-Sum operation, the matrices a and B involved in the operation cannot exchange orders, and the size of the first matrix a cannot be smaller than that of the second matrix B.

Images