CN106998208B

CN106998208B - Code word construction method of variable length Polar code

Info

Publication number: CN106998208B
Application number: CN201710036000.0A
Authority: CN
Inventors: 刘荣科; 冯宝平; 王闰昕; 赵岭
Original assignee: Beihang University
Current assignee: Beihang University
Priority date: 2017-01-17
Filing date: 2017-01-17
Publication date: 2020-04-28
Anticipated expiration: 2037-01-17
Also published as: CN106998208A

Abstract

The invention provides a code word construction method of a variable-length Polar code, belonging to the field of communication. The construction of a long code generating matrix is realized by expanding a generating matrix of a short code, and firstly, the code length is expressed as a summation form of powers of 2 based on an integer binary representation; then, taking the value of each item forming the summation form as the size of a sub-matrix forming the new generation matrix; and finally, constructing a new generator matrix through combo-sum combined operation. Compared with the traditional method for constructing the variable-length Polar code, the method does not need to perform puncturing and deleting operation, reduces the encoding complexity and the time delay, and avoids the problem that the traditional method estimates the likelihood information of the unknown bit by using the priori knowledge because the likelihood information of the unknown bit is known at the decoding end, thereby reducing the bit error rate of decoding and improving the system performance.

Description

Code word construction method of variable length Polar code

Technical Field

The invention belongs to the field of communication channel coding, and particularly relates to a code word construction method of a variable-length Polar code.

Background

Polar Codes, i.e., polarization code, was 2009 by E.

A new type of channel coding is proposed. Polarization code is designed based on Channel Polarization (Channel Polarization), the first constructive coding scheme that can prove to reach Channel capacity by strict mathematical methods. However, the Polar code is constructed by Kronecker power, and the construction mode limits the code length of Polar code, thus being inconvenient for the use of Polar code in practical system. The original method can only construct the code length of 2ⁿPolar code of (n ═ 1, 2.). Although Polar codes with other code lengths can be constructed by other polarization cores such as BCH code core, the code length of Polar codes constructed by the method is still limited to the power of the core length, and the decoding structure of Polar codes constructed by the method is complex.

It is well known in the art that in practical communication systems the length of the original information is often uncertain, which requires that the code can be adjusted according to the length of the original information. That is, a coding structure with a series of different code length and code rate is obtained according to the channel condition and the length of the information. Currently, the existing code word structure of the variable length polarization code adopts the method that part of code word bits are deleted from the original code word bits with the length of 2 power to realize the code word structure with the power of non-2. The likelihood information of the deleted code word bits is set to be 0,1 and the like when the receiving end decodes, and then the decoding of the common polarization code is carried out. Although the method realizes the Polar code structure with variable code length, the decoding error probability is also improved, and the performance of the communication system is seriously lost. Therefore, a code word construction method of a Polar code with a variable code length and better performance is needed.

Disclosure of Invention

Based on the requirement, the invention provides a code word construction method of variable-length Polar codes, which combines power Polar code generating matrixes with the original length limited to 2 to realize the construction of generating matrixes of Polar codes with any code length.

The invention provides a code word construction method of a variable length Polar code, which comprises 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: and determining the size of the generating matrix to be selected according to the position of the '1' in the binary bit sequence s obtained in the step 1.

Let q be the number of bit values "1" in the sequence s, where h is the index number in the sequence s_dThe bit value of (a) is 1, d represents the d-th 1 occurring from the upper to the lower bits in the sequence s, and d is 1,2, … q. Then select the original generating matrix of q polar codes, which are respectively l in size₁,l₂,...,l_qThe square matrix of (A) is formed,

h_dthe sequence s is indexed from 1 starting from the lower to the upper bits, which is a positive integer.

And step 3: and combining the selected sub-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 C with code length N is represented as:

wherein,

representing a Combo-Sum operation.

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

And

the resulting combined matrix 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.

The invention has the advantages and positive effects that: the code word construction method is realized through Combo-Sum operation, and the Polar code constructed by the method can effectively reduce the decoding error probability and improve the performance of a communication system. The invention realizes the construction of the long code generating matrix by expanding the generating matrix of the short code, and compared with the traditional method, the invention does not need to delete the punching operation, thereby reducing the coding complexity and the time delay. The likelihood information corresponding to the unknown bit at the decoding end is known, so that the problem that the prior knowledge is used for estimating the likelihood information of the unknown bit in the traditional method is solved, the bit error rate of decoding is reduced, and the system performance is improved.

Drawings

FIG. 1 is a flow chart illustrating a codeword construction method according to the present invention;

FIG. 2 is three specific examples of the original generator matrices used in constructing the generator matrices according to the present invention;

FIG. 3 is a diagram illustrating a general correspondence relationship between a new generation matrix and a sub-matrix according to the present invention.

Detailed Description

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

As shown in FIG. 1, the code word construction method of the variable length Polar code of the present invention realizes the construction of Polar code generating matrix through the following steps 1-3.

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

For code length N, using binary expansion to obtain m-bit binary bit sequence s ═ s_m,s_m-1,...,s₂,s₁H is an index number from the lower level to the upper level of the binary bit sequence, and h is 1,2, … m, s_hBit value representing index position h in sequence s, s_hE {0,1}, m denotes the index position of the highest bit 1 of the binary sequence, s_m＝1。

The code length N can be any positive integer, and is not required to be limited to the form of power of 2 like the code length of the original polar code.

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

Step 2: and determining a generator matrix to be selected by the combination operation according to the position of the '1' in the obtained binary expansion sequence.

And finding out the position of the bit value of 1 in the binary expansion sequence, and setting the number of 1 as q. According to the binary expansion sequence obtained in step 1, N can be expressed as:

equation (1) shows that N is expressed in power form of 2 according to the position of 1 in the binary bit sequence, where the index number h in the sequence s_dThe bit value of (a) is 1, and d represents the d-th 1 occurring from the upper to the lower bits in the sequence s.

Then select the source of q polar codesStarting to generate a matrix, wherein the size of the d-th generating matrix is

l_dIs a natural number and is a power of 2 form.

Selecting q l corresponding to N binary decomposition_d×l_dThe original generated matrix of Polar code is used as the sub-matrix to be selected in the combination operation, and the selected sub-matrix is expressed as

Wherein

Is represented by_d×l_dSquare matrix, matrix of

Generating matrices for Polar codes originally, produced by kronecker products, i.e.

Wherein the matrix

The parameter n is log₂l_d，

Representing kronecker multiplications, which are well known in the art, and primitive generator matrices.

For example: when the code length N is 6, 6 is 2²+2¹＝l₁+l₂，l₁＝4，l₂2, then selecting a generating matrix G with the code length of the original Polar code of 4_4×4Generating matrix G with sum code length of 2_2×2The generator matrix G is a sub-matrix constituting a generator matrix having a code length of 6_4×4And G_2×2The specific values are shown in fig. 2.

When the code length N is 8When 8 is 2³＝l₁It can be seen that the original Polar code generator matrix structure with the length of 2 is only a special case of the method of the present invention, and the generator matrix G_8×8As shown in fig. 2.

And step 3: and combining the selected generator matrixes through Combo-Sum operation so as to construct a generator matrix with the code length of N.

First, the definition of the Combo-Sum operation is proposed. Combo-Sum is a combination operation of two matrices, and the Sum C of Combo-Sum of matrix A and matrix B can be expressed as

Matrix array

And

is a square matrix, L₁、L₂Respectively, the size of the matrix A, B. To obtain an arbitrary size C, the sizes of A and B need not be the same, where L is taken₁≥L₂. Wherein the matrix B 'is the same as the matrix B except that all the 0 columns are arranged, and the size of the matrix B' is L₂×L₁Wherein, the former L of B₂Columns are the same as in matrix B, last L₁-L₂The columns are all 0 columns.

The codeword resulting from the matrix C as the generator matrix may be denoted x ═ uC, and then x and u are further decomposed into two parts, denoted x ═ (x), respectively₁,x₂) And u ═ u (u)₁,u₂) X denotes a vector of encoded code words derived from a generator matrix, x₁Represents a front L₁A number of code words that are each associated with a code word,

Figure DEST_PATH_GDA00013284238200000310

x₂after representation of L₂A number of code words that are each associated with a code word,

Figure DEST_PATH_GDA00013284238200000311

u₁representing the first L of a coded input sequence₁One bit of the data is transmitted to the receiver,

Figure DEST_PATH_GDA00013284238200000312

u₂post-L representing encoded input sequence₂One bit of the data is transmitted to the receiver,

Figure DEST_PATH_GDA00013284238200000313

according to the structure of the matrix C, x₁By u₁And u₂Obtained by the matrixes A and B' together

Figure DEST_PATH_GDA00013284238200000314

x₂By u₂Obtaining x from the matrix B₂＝u₂B, so generating codeword x can be expressed as

Figure DEST_PATH_GDA00013284238200000315

Combo-Sum operation defines: two matrixes are given

Figure DEST_PATH_GDA00013284238200000316

Where i denotes the row index of the matrix, j denotes the column index of the matrix, L₁,L₂Denotes the size of the square matrix, and L₁≥L₂. Defining two matrixes to carry out Combo-Sum operation to obtain combination

Figure DEST_PATH_GDA00013284238200000317

Figure DEST_PATH_GDA00013284238200000318

Represents a Combo-Sum combinatorial operation, wherein:

Figure DEST_PATH_GDA00013284238200000319

c is represented by formula (2)_ijAnd a_ijAnd b_ijIs shown in fig. 3. Wherein Γ is {1, 2., L₁A subset of L elements of the set, called the difference set₂Γ is the set of non-zero columns of matrix B ', the first L of B' must be taken₂The order of values is not necessarily in the order of 1,2, …. Let index in set Γ be labeled j₀＝1,2,...,L₂The index j in the matrix C is the jth of the set Γ₀Elements, determining j from Γ according to j₀Obtaining c_ijCorresponding matrix B elements

When in use

Combo-Sum and C can be represented as

The corresponding bit positions represented by equation (3) are shown in fig. 3.

For example

Combinational operation

Has the following limitations:

① the A, B matrices participating in the operation may not be permuted.

② the size of the first matrix cannot be smaller than the second matrix, i.e./₁≥l₂。

③ Combo-Sum operation results are not unique different sets Γ and operation orders will result in different Combo-Sum sums.

For example, the structure of the generator matrix with the code length of 5 may have the following two structures:

the first construction method comprises the following steps:

the second construction method is as follows:

the long code can be decomposed into two or more short codes, and since Combo-Sum operation is not unique, step 3 determines the submatrix participating in Combo-Sum operation according to the binary decomposition order and representation form obtained by step 2 strictly according to the code length N.

For example, for a generator matrix with N-5, this can only be expressed as

And cannot be represented as

Figure DEST_PATH_GDA00013284238200000410

And

Figure DEST_PATH_GDA00013284238200000411

combined or otherwise represented.

Therefore, the calculation process of step 3 is to generate the matrix for q primitive matrices obtained from step 2

Performing Combo-Sum combination operation on the data, and selecting two generator matrixes with the maximum code length each time to participate in the Combo-Sum combination operation in the combination operation process, namely obtaining a generator matrix with the code length of N through the Combo-Sum operation according to q original generator matrixes

For example, the process of generating matrix combination operation with code length N ═ 7 is as follows: obtaining a generator matrix G participating in the combined operation according to the step 2_4×4,G_2×2,G_1×1According to the operation criterion: selecting the largest two generations at a timeThe matrix participates in the operation, then

The matrix combination is represented as:

and taking the combined matrix obtained by each Combo-Sum operation as a new sub-matrix, replacing and combining to generate the sub-matrix, and continuing participating in the next Combo-Sum operation until only one sub-matrix is left to obtain a final generated matrix C with the code length of N.

Example 1: and constructing a generating matrix of Polar codes with the code length N-6.

Step 1: a binary bit sequence having a code length N of 6 is represented by s {1,1,0 }.

Step 2: according to the binary bit sequence obtained in the step 1, selecting a combination matrix with a code length N equal to 6:

according to 6-2²+2¹＝l₁+l₂So that a sub-matrix G having a constituent code length of 6 is obtained_4×4,G_2×2。

And step 3: the submatrices constituting the generator matrix with the code length N of 6 obtained in step 2 are combined by a Combo-Sum operation.

The operation process is as follows:

example 2: and (5) constructing a generating matrix of Polar codes with the code length N being 11.

Step 1: a binary bit sequence with a code length N of 11 is denoted by s {1,0,1,1 }.

Step 2: according to the binary bit sequence obtained in the step 1, selecting a combination matrix with a code length N equal to 11:

according to 11-2³+2¹+2⁰＝l₁+l₂+l₃The size of the submatrix is l₁＝8，l₂＝2，l ₃1. So that a sub-matrix G having a constituent code length of 11 is obtained_8×8,G_2×2,G_1×1。

And step 3: the submatrices constituting the generator matrix with the code length N of 11 obtained in step 2 are combined by a Combo-Sum operation.

The operation process is as follows:

Claims

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

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:

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.