CN103023618A - Random code length polar encoding method - Google Patents

Abstract

A polar coding method with arbitrary code length is to use a group of virtual channels with zero capacity to fill the number of channels to the power of 2 when constructing the polar code, if the code length is not a power of 2, Then, each channel is interleaved and mapped according to the principle of capacity equalization, and then the obtained channel is polarized transformed, and among the transformed channels, a channel with a larger channel capacity is selected according to the designed code rate to transmit the information bit sequence , and the remaining channels are used to transmit a fixed bit sequence known to both the transceiver and the receiver. The present invention allows the code length of polar coding to be any positive integer, and can be applied to multi-carrier and high-order modulation systems. By adding drilling operations, the coded bit sequence output by the coder can be of any length; and then through channel interleaving mapping, The polar coding can be adapted to different sub-channels of the parallel channel to obtain better anti-noise performance; the invention greatly improves the flexibility of the polar code when it is used in an actual digital communication system, and has a good application prospect.

Description

A Polar Coding Method with Arbitrary Code Length

technical field

The present invention relates to a polar encoding method with arbitrary code length, which is used to solve the problem of transmission data error caused by channel interference to the communication process in a digital communication system; In the digital communication system of error coding, the polarization coding method of arbitrary code length is realized by channel polarization technology at the signal sending end. The invention belongs to the technical field of channel coding of digital communication.

Background technique

x₂=u₂，为模二加运算。把x₁和x₂分别送入未经极化信道W，得到的输出为y₁和y₂。从该信道极化基本单元的输入（u₁和u₂）和两个信道的输出（y₁和y₂）来看，原本独立的两个未经极化的信道W被合并成一个两输入两输出的向量信道W₂:x²→y²，其中x²=x×x，运算×为笛卡尔积。该向量信道包含两个子信道W₂ ⁽¹⁾:x→y×x（输入为u₁输出为y₁y₂）和W₂ ⁽²⁾:x→y（输入为u₂输出为y₁y₂u₁），这两个子信道即为两个极化信道。经过该单步极化过程，从信道容量上看：I(W₂ ⁽¹⁾)+I(W₂ ⁽²⁾)＝2×I(W)，I(W₂ ⁽¹⁾)≤I(W)≤I(W₂ ⁽²⁾)，其中，I(·)表示求信道容量的函数。也就是说：单步极化后，在保持和容量不变的情况下，与原先未经极化的信道相比较，极化后的两个子信道容量发生了偏离：一个增加，一个减少。如果对两组已经过一次极化操作的信道，再在两组互相独立的转移概率相同的极化信道之间，分别进行单步极化操作，该偏离会更加明显，称这一组单步极化操作为第二层极化操作，而前一组单步极化操作称为第一层极化操作。每多做一层极化操作，需要的信道数就会比原先多一倍。因此，对N＝2ⁿ个信道进行完全的极化，共需要n层极化操作，且每一层极化操作包括了N次单步极化操作。如不加特殊说明，“对N个信道进行极化操作”是指完全极化。理论上已证明，对接近无穷多个信道进行极化操作后，会出现一部分信道的容量为1（即通过其传输的比特一定会被正确接收），其余信道容量为0（即完全无法在其上可靠地传输比特）的现象，而容量为1的信道占全部信道的比例正好为原二进制输入离散信道的容量。Polar Codes (Polar Codes) is a constructive channel coding method proposed by E.Arikan in 2009 that has been strictly proven to be able to achieve channel capacity. Before polar coding, the channel shown in Figure 1 should be applied to N=2 ⁿ independent binary input channels (or the same channel is used N times successively, that is, N available time slots of a channel). The basic unit of polarization repeatedly polarizes binary input discrete channels, where n is a natural number. The most basic channel polarization (see Figure 1) is a single-step polarization operation on two identical unpolarized channels W: x → y, where x is the set of channel input symbols (for a binary input channel, x takes the value {0,1}), and y is the set of channel output symbols. As shown in Figure 1, mark the two input bits of the polarized channel as u ₁ and u ₂ respectively, and obtain x ₁ through a modulo-two adder. On the other hand, assign u ₂ directly to x ₂ , namely

x ₂ =u ₂ , It is a modulo two addition operation. Sending x ₁ and x ₂ into the unpolarized channel W respectively, the output obtained is y ₁ and y ₂ . From the input (u ₁ and u ₂ ) of the channel polarized basic unit and the output of the two channels (y ₁ and y ₂ ), the originally independent two unpolarized channels W are combined into a two-input Vector channel W ₂ of the two outputs: x ² →y ² , where x ² =x×x, and the operation x is a Cartesian product. This vector channel contains two sub-channels W ₂ ⁽¹⁾ : x→y×x (input is u ₁ and output is y ₁ y ₂ ) and W ₂ ⁽²⁾ : x→y (input is u ₂ and output is y ₁ y ₂ u ₁ ), these two sub-channels are two polarized channels. After this single-step polarization process, from the perspective of channel capacity: I(W ₂ ⁽¹⁾ )+I(W ₂ ⁽²⁾ )=2×I(W), I(W ₂ ⁽¹⁾ )≤I( W)≤I(W ₂ ⁽²⁾ ), where I(·) represents a function for calculating the channel capacity. That is to say: after a single-step polarization, under the condition that the sum and capacity remain unchanged, compared with the original unpolarized channel, the capacities of the two polarized sub-channels deviate: one increases and the other decreases. If a single-step polarization operation is performed on two sets of channels that have undergone one polarization operation, and then between two sets of independent polarization channels with the same transition probability, the deviation will be more obvious, and this group is called single-step The polarization operation is the second layer polarization operation, and the previous group of single-step polarization operations is called the first layer polarization operation. For each additional layer of polarization operation, the number of channels required will be doubled. Therefore, to perform complete polarization on N=2 ⁿ channels, a total of n layers of polarization operations are required, and each layer of polarization operations includes N times of single-step polarization operations. Unless otherwise specified, "perform polarization operations on N channels" refers to complete polarization. Theoretically, it has been proved that after performing polarization operations on nearly infinite channels, the capacity of some channels will be 1 (that is, the bits transmitted through it will be received correctly), and the capacity of the rest of the channels will be 0 (that is, it is completely impossible to use them in other channels). Reliable transmission of bits), and the proportion of channels with a capacity of 1 to all channels is exactly the capacity of the original binary input discrete channel.

的信道极化装置作递归操作来表示，递归过程中的最小单元（即当N＝2时）就是图1所示的基本单元。图2中的信道极化装置中有一个长度为N的比特反转交织器，其功能是：先将输入端的十进制序号i按照二进制表示为(b_n-1b_n-2…b₀)，其中，n=log₂N；再将该二进制序列反序，得到(b₀b₁…b_n-1)；最后重新按照十进制表示成θ(i)，作为输入序号i对应的输出序号。比特反转交织器的用处是将输入端序号为i的比特映射到序号θ(i)处。根据编码速率（R）对N个信道进行极化，并选取其中容量最大的K个信道（或者等价地，选取可靠性最高的K个信道，可靠性度量是采用密度进化（Density Evolution）工具或者计算巴塔恰里亚（Bhattacharyya）参数得到的），以承载用于传输消息的比特，称该部分比特为信息比特，并称该部分信道为信息信道（其中

为向下取整运算），其余未被选中的信道用于传输一个约定的比特序列（被称为固定比特序列），并称该部分信道为固定信道（若信道对称，则可简单地传输全零序列），从而形成一个从承载信息的K个比特到最终送入信道的N个比特的映射关系，这样的一种映射关系即为极化码，其码长（即编码后得到的二进制信号所包含的比特数）等于信道极化装置的长度N。Referring to Figure 3, a practical recursive structure of the channel polarization device is introduced. A channel polarization device with a length of N (to polarize N channels) can be used with a length of

The channel polarization device is represented by a recursive operation, and the smallest unit in the recursive process (that is, when N=2) is the basic unit shown in Figure 1 . In the channel polarization device in Fig. 2, there is a bit inversion interleaver with a length of N, its function is: first, the decimal number i at the input end is expressed in binary as (b _n-1 b _n-2 ...b ₀ ), Among them, n=log ₂ N; then reverse the binary sequence to obtain (b ₀ b ₁ …b _n-1 ); finally, re-express it as θ(i) in decimal, as the output sequence number corresponding to the input sequence number i. The purpose of the bit reverse interleaver is to map the bit with the sequence number i at the input end to the sequence number θ(i). The N channels are polarized according to the coding rate (R), and the K channels with the largest capacity are selected (or equivalently, the K channels with the highest reliability are selected. The reliability measurement is based on the Density Evolution tool. Or calculated Bhattacharyya (Bhattacharyya) parameters), to carry the bits used to transmit the message, call this part of the bits as information bits, and call this part of the channel as the information channel (where

is rounded down), and the remaining unselected channels are used to transmit an agreed bit sequence (called a fixed bit sequence), and this part of the channel is called a fixed channel (if the channel is symmetrical, the full Zero sequence), thus forming a mapping relationship from K bits carrying information to N bits finally sent to the channel. Such a mapping relationship is a polar code, and its code length (that is, the binary signal obtained after encoding The number of bits contained) is equal to the length N of the channel polarizer.

其中，自然数序号i的最大值为N，表示将N个信道W极化后得到的序号为i的极化信道）。编码码块经过信道极化装置得到的x₁…x_N，通过N个独立信道W，接收到的信号序列为(y₁…y_N)。The binary signal sequence (u ₁ ... u _N ) composed of information bits and fixed bits and sent to the channel polarization device is a coded code block (the order of which is consistent with the serial number of the polarized channel sent in, that is, u _i is sent to

Among them, the maximum value of the natural number i is N, Indicates the polarized channel with sequence number i obtained after polarizing N channels W). The x ₁ ... x _N obtained by the encoded code block through the channel polarization device passes through N independent channels W, and the received signal sequence is (y ₁ ... y _N ).

The above process can also be equivalently described as: multiply the sequence u=(u ₁ …u _N ) by the matrix G _N , that is, x=u×G _N , where the matrix The N×N-dimensional matrix B _N is a bit reverse order permutation matrix, $f_2=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]$ superscript It means to find the Kronecker product of n F ₂ . B _N is obtained by rearranging the rows of an N×N unit square matrix according to the reverse order of bits: for each natural number i∈{1,2,…,N}, the binary representation of (i-1) is ( b _n ,b _n-1 ,…,b ₁ ), find a natural number j∈{1,2,…,N}, and make the binary representation of (j-1) as (b ₁ ,b ₂ ,…, b _n ), and then set the i-th row of matrix B _N equal to the j-th row of I _N.

图3是一个码长N＝4的极化码的码树。图中的黑实线指出一条串行抵消译码所得到的路径，其对应的比特估计序列为(0110)。The task of the decoder is to obtain a set of bit estimation sequences of the transmitted bit sequence (u ₁ ... u _N ) according to the received signal sequence y ₁ ... y _N

FIG. 3 is a code tree of a polar code with code length N=4. The black solid line in the figure points out a path obtained by serial cancellation decoding, and its corresponding bit estimation sequence is (0110).

The polar code can use the serial cancellation decoding method to make decisions on each bit in the encoded code block sequentially from 1 to N according to the sequence number i. The serial cancellation decoding method can be described as a search process on a code tree (see Figure 3). Figure 3 is a simple example. Serial offset decoding expands gradually on the code tree, selects one of the two candidate paths each time with a relatively high probability value, and performs the next path expansion on the basis of that path.

The traditional polar coding method described above requires that all channels participating in the polarization transformation have the same channel transition probability function, that is, it requires different uses of a time-invariant memoryless channel, and the code length must be a power of 2 . However, in an actual system, due to the use of multi-carrier technology and high-order modulation technology, the channel conditions for transmitting each codeword bit are not exactly the same. On the other hand, due to practical system design considerations such as the number of subcarriers or the modulation order, the output sequence of the encoder should not be fixed to a power of 2.

For multi-carrier systems and systems using bit-interleaved coding and modulation, it can be equivalent to performing serial-to-parallel conversion on the encoded codewords, and then sending them to a group of parallel channels for transmission. The parallel sub-channels have the same input and output symbols. set, but with different channel transition probability functions. The parallel channel coding transmission scheme is shown in Fig. 4 .

The parallel channel transmission model is a more general channel model than the single channel transmission. When the number of sub-channels J=1, the parallel channel transmission problem will degenerate into a single channel transmission problem.

Unless otherwise specified, the present invention uses lowercase English or Greek letters to represent scalars, such as x. Sets are represented by cursive capital English letters, such as X. Use bold lowercase English or Greek letters for vectors (or equivalent sequences), such as x. A certain element in the vector is represented by the lowercase English or Greek letter (not bold) with the same name, and the serial number of the element in the vector is marked with a subscript, such as the i-th element of the vector x is represented by the symbol x _i . A subvector (x _i , x _i+1 , . . . , x _j-1 , x _j ) of a vector x is denoted by the symbol x _i:j . Use bold uppercase English letters to indicate the square matrix, and use the subscript to mark its size, such as X _N means an N×N square matrix.

The disadvantage of the above-mentioned prior art is that: the existing polar coding scheme requires that the code length must be a power of 2. However, in the actual digital communication system, the requirement for the code length is very flexible, and may not be able to meet the requirement of being a power of 2. Moreover, due to the use of multi-carrier technologies (such as Orthogonal Frequency Division Multiple Access, OFDM, etc.) and high-order modulation technologies in actual digital communication systems, channels that depend on channel polarization will have different channel qualities.

Contents of the invention

In view of this, the purpose of the present invention is to provide a polar coding scheme of any code length under parallel channels, so that the polar coding allows the code length to be any positive integer, and can be applied to multi-carrier and high-order modulation systems, It greatly improves the flexibility of the polar code when it is applied to the actual digital communication system, and has a good practical prospect.

In order to achieve the above object, the present invention provides a polar coding method with arbitrary code length, which is characterized in that: if the code length is not a power of 2 when constructing a polar code, a set of virtual codes with a capacity of zero is used The number of channels is filled to the power of 2, and then each channel is interleaved and mapped according to the principle of equal division of capacity, and then the obtained channel is polarized, and in the transformed channel, according to the designed code rate selection A channel with a larger channel capacity is used to transmit information bit sequences, and the remaining channels are used to transmit a fixed bit sequence known to both the receiving and receiving ends; the method includes the following steps:

运算

表示对其参数向上取整；所述用于传输编码序列的信道包含有J个并行子信道，并依次标记为：W₁、W₂、…、W_J；其中的并行子信道数J与编码序列长度M应满足下述条件：M能够被J整除；(1) Determine the encoding parameters according to the requirements, so as to encode an information sequence containing K bits into a binary coded sequence with a length of M, where the natural numbers K and M satisfy the condition of K≤M; then set N=2 ⁿ ,

operation

Indicates that its parameters are rounded up; the channel used to transmit the code sequence contains J parallel sub-channels, which are marked as: W ₁ , W ₂ , ..., W _J ; the number of parallel sub-channels J and the number of coded The sequence length M should meet the following conditions: M can be divisible by J;

与收发两端都已知的固定序列

所组成的长度为N的比特序列u进行下述变换：x=u·G_N，式中，矩阵N×N维的矩阵B_N为比特反序置换矩阵， $F_2=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]$ 的上标

表示求n个F₂的克罗内克积，下标

和

分别为信息信道的序号集合与固定信道的序号集合；(2) Perform the traditional polar encoding operation: the input bit sequence

fixed sequence

The formed bit sequence u with a length of N undergoes the following transformation: x=u·G _N , where the matrix The N×N-dimensional matrix B _N is a bit reverse order permutation matrix, $f_2=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]$ superscript

Indicates to seek the Kronecker product of n F ₂ , the subscript

and

are respectively the sequence number set of the information channel and the sequence number set of the fixed channel;

其中，自然数下标i的最大值为N；(3) Perform interleaving operation: use the channel interleaving function f _π ( ) to interleave and sort the bit sequence x to obtain the bit sequence v:

Among them, the maximum value of the natural number subscript i is N;

(4) Perform puncturing operation: delete the last (NM) bits in the bit sequence v, so that the bit sequence v is transformed into a bit sequence z of length M: z=(v ₁ ,v ₂ ,…,v _M );

的比特序列r^(p)：r^(p)=(z_(p-1)×M/J+1,z_(p-1)×M/J+2,…,z_p×M/J)，其中，自然数序号p的最大值为J，并分别按照顺序送入对应的并行子信道W_p进行传输。(5) Perform serial/parallel conversion operation: divide the bit sequence z into J lengths

The bit sequence r ^(p) : r ^(p) = (z _(p-1)×M/J+1 ,z _(p-1)×M/J+2 ,…,z _p×M/J ), Wherein, the maximum value of the natural number p is J, and are sent to the corresponding parallel sub-channel W _p in order for transmission.

The key to the innovative technology of the arbitrary code length polar coding method of the present invention is: on the basis of ordinary polar coding, the steps of channel interleaving mapping and puncturing are added, and a polar channel selection method and interleaving mapping under the new coding method are provided. The construction method of the function and the sorting operation steps involved in constructing the interleaving mapping function; in addition, a special case is also provided, which is applied to a single channel transmission scenario: the simple construction of the interleaving mapping function when the number of parallel sub-channels is 1 method.

The advantage of the present invention is that: by increasing the puncturing operation, the encoded bit sequence output by the encoder can have any length. Through channel interleaving and mapping, polar coding can adapt to different sub-channels of parallel channels, and has the characteristics of different channel characteristics, so as to obtain better anti-noise performance. Because of the above characteristics, the present invention is more suitable for practical communication systems, and has good prospects for popularization and application.

Description of drawings

FIG. 1 is a schematic diagram of a basic unit structure of channel polarization.

FIG. 2 is a schematic diagram of a recursive structure of a channel polarization device with a length of N, where the minimum unit of recursion (ie when N=1) is the schematic diagram of the basic unit shown in FIG. 1 .

Fig. 3 is a code tree of a polar code with code length N=4. The black solid line in the figure indicates a path obtained by serial cancellation decoding, and the corresponding bit estimation sequence is (0110) schematic diagram.

Fig. 4 is a schematic block diagram of a parallel channel coding transmission scheme.

Fig. 5 is a flow chart of the operation steps of the polar encoding method with arbitrary code length according to the present invention.

Fig. 6 is a flow chart of the operation steps for determining the information channel number and the fixed channel number in the method of the present invention.

Fig. 7 is a flow chart of operation steps for constructing an interleaving mapping function in the method of the present invention.

Fig. 8 is a flow chart of capacity equal division and sorting steps when constructing an interleaving mapping function in the method of the present invention.

Fig. 9 is a schematic diagram of the performance curve of the embodiment of the method of the present invention transmitted under the parallel channel.

Fig. 10 is a schematic diagram of performance curves of transmission under different code lengths according to an embodiment of the method of the present invention.

Detailed ways

In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings.

The polar coding method of arbitrary code length of the present invention is that when constructing polar codes, if the code length is not a power of 2, then use a group of virtual channels with a capacity of zero to fill the number of channels to a power of 2, Then, each channel is interleaved and mapped according to the principle of capacity equalization, and then the obtained channel is polarized transformed, and among the transformed channels, the channel with a larger channel capacity is selected according to the designed code rate to transmit the information bit sequence, The remaining channels are used to transmit a fixed bit sequence known to both the transceiver and receiver.

Referring to Fig. 5, introduce the following operating steps of the inventive method:

运算

表示对其参数向上取整；所述用于传输编码序列的信道包含有J个并行子信道，并依次标记为：W₁、W₂、…、W_J；其中的并行子信道数J与编码序列长度M应满足下述条件：M能够被J整除。Step 1. Determine the encoding parameters according to the requirements, so as to encode an information sequence containing K bits into a binary coded sequence with a length of M, wherein the natural numbers K and M satisfy the condition of K≤M; then set N=2 ⁿ ,

operation

Indicates that its parameters are rounded up; the channel used to transmit the code sequence contains J parallel sub-channels, which are marked as: W ₁ , W ₂ , ..., W _J ; the number of parallel sub-channels J and the number of coded The sequence length M should satisfy the following condition: M can be divisible by J.

与收发两端都已知的固定序列

所组成的长度为N的比特序列u进行下述变换：x=u·G_N，式中，矩阵N×N维的矩阵B_N为比特反序置换矩阵， $F_2=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]$ 的上标

表示求n个F₂的克罗内克积，下标

和

分别为信息信道的序号集合与固定信道的序号集合。Step 2, perform the traditional polar coding operation: the input bit sequence

fixed sequence

The formed bit sequence u with a length of N undergoes the following transformation: x=u·G _N , where the matrix The N×N-dimensional matrix B _N is a bit reverse order permutation matrix, $f_2=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]$ superscript

Indicates to seek the Kronecker product of n F ₂ , the subscript

and

are respectively the sequence number set of the information channel and the sequence number set of the fixed channel.

与固定信道序号集合

的计算操作步骤：Referring to Figure 6, the set of information channel numbers is introduced

set with fixed channel number

Calculation steps for :

次，该M次信道的使用被视为M个单次使用的独立信道；再构建（N-M）个信道容量为0的虚拟信道W₀，用于在步骤4对应被凿去的比特；共得到N个独立信道：(21) Determine the channel before polarization transformation: each parallel sub-channel (W ₁ , W ₂ ,..., W _J ) has been used independently

times, the use of the channel for M times is regarded as M single-use independent channels; construct (NM) virtual channels W ₀ with a channel capacity of 0, which are used to correspond to the bits that were chiseled out in step 4; a total of N independent channels:

表示左右两边的信道具有完全相同的输入、输出和信道转移概率函数，f_π(·)为信道交织函数。According to the correspondence between bits and channels determined in step 4 and step 5, and the interleaving mapping relationship determined in step 3, a set of channels w ₁ , w ₂ , ..., w _N are obtained: in,

Indicates that the left and right channels have exactly the same input, output and channel transition probability functions, and f _π (·) is the channel interleaving function.

Referring to Fig. 7, the following operation content of constructing the channel interleaving function f _π (·) according to the principle of equal division of capacity is introduced:

(211) Construct an N-dimensional capacity sequence c for each i initialization:

式中，I(·)为求参数信道的对称信道容量：若某个信道W输入符号集合为{0,1}、输出符号集合为y、信道转移概率函数为W(y|b)，b∈{0,1}，y∈y，y为信道W的输出符号集合，则其对称信道容量为： $I\left(W\right)=\frac{1}{2}\underset{b\∈\left\{\mathrm{0,1}\right\}}{\mathrm{\Σ}}\underset{y\∈y}{\mathrm{\Σ}}(W\left(y\right|b)\×\mathrm{lo}{g}_2\left(\frac{2\×W\left(y\right|b)}{W\left(y\right|0)+W\left(y\right|1)}\right));$ For i ∈ {1,2,…,M},

In the formula, I( ) is the symmetric channel capacity of the parametric channel: if a certain channel W has an input symbol set of {0,1}, an output symbol set of y, and a channel transition probability function of W(y|b), b ∈{0,1}, y∈y, y is the output symbol set of channel W, then its symmetric channel capacity is: $I\left(W\right)=\frac{1}{2}\underset{b\∈\left\{\mathrm{0,1}\right\}}{\mathrm{\Σ}}\underset{\mathrm{the\; y}\∈\mathrm{the\; y}}{\mathrm{\Σ}}(W\left(\mathrm{the\; y}\right|b)\×\mathrm{lo}{g}_2\left(\frac{2\×W\left(\mathrm{the\; y}\right|b)}{W\left(\mathrm{the\; y}\right|0)+W\left(\mathrm{the\; y}\right|1)}\right));$

For i ∈ {M+1,M+2,…,N}, set c _i =0;

Re-initialize the subscript sequence π: For each natural number i∈{1,2,…,N}, set π _i =i; and initialize the sorting step L=N.

个长度为L的子序列，再对每个序号

得到一个序号为m的子序列λ^(m)：λ^(m)=(π_(m-1)×L+1，π_(m-1)×L+2，…π_m×L)，并对其按照容量等分原则进行排序：若容量等分排序函数为f_ECP(·)，则新的序列ρ^(m)=f_ECP(λ^(m),c)，再用该序列ρ^(m)更新π，即对所有t∈{1,2,…,L}， ${\mathrm{\π}}_{(m-1)\×L+t}={\mathrm{\ρ}}_t^{\left(m\right)}.$ (212) Perform capacity equalization sorting: use the sorting step size L to divide the sequence π into

a subsequence of length L, and for each serial number

Get a subsequence λ ^(m) with sequence number m: λ ^(m) = (π _(m-1)×L+1 , π _(m-1)×L+2 ,…π _m×L ), and It sorts according to the principle of capacity equalization: if the capacity equalization sorting function is f _ECP ( ), then the new sequence ρ ^(m) = f _ECP (λ ^(m) ,c), and then use the sequence ρ ^(m) Update π, that is, for all t ∈ {1,2,…,L}, ${\mathrm{\π}}_{(m-1)\×L+t}={\mathrm{\ρ}}_t^{\left(m\right)}.$

个元素对应的容量值之和

与其后

个元素对应的容量值之和

要尽可能相等，其具体操作步骤包括下列内容（参见图8所示）：The capacity equalization sorting principle in this step requires two input parameters: one is the subscript sequence λ of length L, and the other is the capacity sequence c in step (211), and its output parameter ρ is a sorting sequence λ : should satisfy ρ

The sum of the capacity values corresponding to elements

with after

The sum of the capacity values corresponding to elements

To be as equal as possible, the specific operation steps include the following (see Figure 8):

(212A) Sort λ to obtain a sequence τ, so that for any t∈{1,2,…,L} and s∈{1,2,…,L}, and t≤s, there is a corresponding τ _t The capacity value of is greater than the corresponding capacity value of τ _s , namely

(212B) Initialize two empty sequences, ie sequences α and β with length zero, and set k=1.

若是，则执行后续步骤（212D）；否则，跳转执行步骤（212E）。(212C) Determine whether the lengths of the two sequences α and β are less than

If yes, execute the next step (212D); otherwise, skip to execute step (212E).

(212D) Determine whether the sum of all elements in sequence α is greater than the sum of all elements in sequence β, if so, add τ _k to the end of sequence β; otherwise, add τ _k to the end of sequence α; then, Increase the value of k by 1, that is, k=k+1, and return to step (212C).

若是，则将元素τ_k，τ_k+2，…，τ_L全部添加到α的最末端；否则，将元素τ_k，τ_k+2，…，τ_L全部添加到β的最末端。(212E) Determine whether the length of sequence α is less than

If yes, add all elements τ _k , τ _k+2 ,...,τ _L to the end of α; otherwise, add all elements τ _k , τ _k+2 ,...,τ _L to the end of β.

个元素构成的子序列等于α，则其后

个元素构成的子序列等于β，即对所有

ρ_t=α_t；对所有

并输出得到的序列ρ。(212F) Set the front of the sequence ρ

A subsequence composed of elements is equal to α, then

A subsequence composed of elements is equal to β, that is, for all

ρ _t =α _t ; for all

And output the obtained sequence ρ.

(213) Judging whether the construction is completed: if the value of L is less than or equal to 2, the algorithm terminates and the construction is completed, and the mapping relationship of the function f _π (·) is determined as f _π (i)=j; where, i∈{1, 2,...,N}, j∈{1,2,...,N}, and π _i =j; otherwise, set the value of L to be halved, that is, L=L/2, and return to step (212).

的输入与输出，比特序列x=u·G_N，w_i(·|·)为信道w_i的信道转移概率函数；(22) Perform polarization transformation on the N independent channels obtained in the above steps: get N binary input channels with forward and backward dependencies Among them, the channel transition probability function $W_N^{\left(i\right)}(\mathrm{the\; y},u_{1:i-1}|u_i)=\underset{u_{i+1:N}\&Element;{\left\{\mathrm{0,1}\right\}}^{N-\mathrm{<figure-callout\; id="1"\; label="i"\; filenames="HDA00002727177200013.png,HDA00002727177200041.png"\; state="\{\{state\}\}">i</figure-callout>}}}{\mathrm{\&Sigma;}}\frac{1}{2^{N-1}}\underset{j=1}{\overset{N}{\mathrm{\&Pi;}}}{w}_j\left({\mathrm{the\; y}}_j\right|x_j);$ Among them, u _i and (y,u _1:i-1 ) are channel

The input and output of , the bit sequence x=u G _N , w _i (·|·) is the channel transition probability function of channel w _i ;

的容量后，选择K个容量较大的信道，即其所对应的上标序号i的信道集合构成信息信道集合

剩余的（N-K）个信道所对应的上标序号值的集合构成固定信道序号集合

(23) Determine the channel number set: calculate each channel separately

capacity Finally, select K channels with larger capacity, that is, the channel set corresponding to the superscript number i constitutes the information channel set

The set of superscript serial number values corresponding to the remaining (NK) channels constitutes a fixed channel serial number set

其中，自然数下标i的最大值为N；Step 3, perform the interleaving operation: use the channel interleaving function f _π (·) to interleave and sort the bit sequence x, and obtain the bit sequence v:

Among them, the maximum value of the natural number subscript i is N;

Step 4, perform the puncturing operation: delete the last (NM) bits in the bit sequence v, so that the bit sequence v is transformed into a bit sequence z of length M: z=(v ₁ ,v ₂ ,…,v _M ).

Step 5, perform the serial/parallel conversion operation: divide the bit sequence z into J lengths The bit sequence r ^(p) : r ^(p) = (z _(p-1)×M/J+1 ,z _(p-1)×M/J+2 ,…,z _p×M/J ), Wherein, the maximum value of the natural number p is J, and are sent to the corresponding parallel sub-channel W _p in order for transmission.

It should be pointed out that if the method of the present invention is applied to the transmission scenario of a single channel, that is, when the number of parallel sub-channels J=1, the channel interleaving function f _π (·) can be constructed according to the following equivalent simple method : Set the sequence γ=(1,2,…,N), and then reverse the bit sequence of the sequence γ to obtain the sequence π: π=γ·B _N , then determine the mapping relationship of the function f _π (·) as f _π (i)=j; In the formula, the maximum value of natural numbers i and j are both N, and satisfy π _i =j.

The present invention has carried out a large amount of emulation implementation tests, introduces the test process and performance analysis thereof of the embodiment of the present invention in detail below in conjunction with accompanying drawing:

In the first embodiment, when the number of parallel channels is greater than 1, encoding is performed by using capacity equal division interleaving mapping:

其中操作

为向下取整操作，译码算法采用串行抵消译码算法。Set the code length N=1024, the transmission channel is a group of parallel channels containing J=4 independent binary input additive white Gaussian noise channels (AWGN) channels, and the capacity of the parallel sub-channels is (0.1,0.4,0.6 ,0.9), its average capacity is 0.5, and the code rate R varies between 0.1 and 0.5, namely

which operates

For the rounding down operation, the decoding algorithm adopts the serial cancellation decoding algorithm.

An embodiment is to perform encoding according to the method shown in FIG. 6 , wherein the interleaving mapping function is constructed according to the operation flow shown in FIG. 7 , and the block error probability under this encoding transmission scheme is shown in FIG. 9 . As a comparison scheme, Fig. 9 also shows the encoding according to the method shown in Fig. 6, the interleaving mapping function is a randomly constructed block error rate curve, and the application of traditional polar coding, under the binary input AWGN channel with a capacity of 0.5 Transmission block error rate curve.

It can be seen from the three curves in Figure 9 that the transmission scheme using the capacity equal division interleaving mapping of the present invention has obvious performance improvement compared with the random mapping transmission scheme, that is, in the case of a fixed code rate, using the capacity equal division interleaving mapping The scheme has a lower probability of error. Moreover, since the channel quality of each sub-channel of the parallel channel is different, it can be considered that the channel has already produced a certain degree of polarization before the polarization transformation. Therefore, the transmission curves of the two parallel channels are more obvious than the curves of a single channel. good performance.

The 2nd embodiment, arbitrary code length polar coding under binary input AWGN channel:

所有方案均采用串行抵消译码算法。Set code rate R=0.5, in binary input additive white Gaussian noise channel (AWGN) channel, J=1, signal-to-noise ratio (the ratio of information bit energy to noise power) E _b /N ₀ =3.0dB, code length N varies from 512 to 1024,

All schemes adopt serial cancellation decoding algorithm.

The embodiment is encoded according to the method shown in Figure 6, wherein the interleaving mapping function is constructed according to the channel interleaving function construction method under special circumstances (J=1), and the block error probability under this encoding transmission scheme is shown in Figure 10 . As a comparison, FIG. 10 also shows a scheme of performing random puncturing on encoded bits after encoding according to the traditional polar encoding method.

It can be seen that if the random puncturing scheme is adopted, the performance will deteriorate rapidly when the code length increases from 512. That is to say, when the code length is not a power of 2, if the code length is adapted by random puncturing, serious performance loss will be caused. But adopting the method of the present invention, the change of performance is smoother, and the block error rate gradually decreases with the gradual increase of the code length. When the code length is not a power of 2, the performance is always obviously better than the random punching scheme.

The above description is only an implementation case of the present invention, and is not intended to limit the present invention. Any modifications, equivalent replacements, improvements, etc. made within the spirit and principles of the present invention shall be included in the protection of the present invention. within the range.

Claims (5)

1. A polar encoding method of arbitrary code length, characterized in that: if the code length is not a power of 2 when constructing a polar code, the number of channels is filled up to 2, and then perform interleaving and mapping on each channel according to the principle of equal division of capacity, and then perform polarization transformation on the obtained channel, and in the transformed channel, select a channel with a larger channel capacity according to the designed code rate to use For the transmission of information bit sequences, the remaining channels are used to transmit a fixed bit sequence known to both the receiving and receiving ends; the method includes the following steps: (1) Determine the encoding parameters according to the requirements, so as to encode an information sequence containing K bits into a binary coded sequence with a length of M, where the natural numbers K and M satisfy the condition of K≤M; then set N=2 ⁿ ,

operation

Indicates that its parameters are rounded up; the channel used to transmit the code sequence contains J parallel sub-channels, which are marked as: W ₁ , W ₂ , ..., W _J ; the number of parallel sub-channels J and the number of coded The sequence length M should meet the following conditions: M can be divisible by J; (2) Perform the traditional polar encoding operation: the input bit sequence

fixed sequence

The formed bit sequence u with a length of N undergoes the following transformation: x=u·G _N , where the matrix The N×N-dimensional matrix B _N is a bit reverse order permutation matrix, $f_2=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]$ superscript

Indicates to seek the Kronecker product of n F ₂ , the subscript

and

are respectively the sequence number set of the information channel and the sequence number set of the fixed channel; (3) Perform interleaving operation: use the channel interleaving function f _π ( ) to interleave and sort the bit sequence x to obtain the bit sequence v:

Among them, the maximum value of the natural number subscript i is N; (4) Perform puncturing operation: delete the last (NM) bits in the bit sequence v, so that the bit sequence v is transformed into a bit sequence z of length M: z=(v ₁ ,v ₂ ,…,v _M ); (5) Perform serial/parallel conversion operation: divide the bit sequence z into J lengths The bit sequence r ^(p) : r ^(p) = (z _(p-1)×M/J+1 ,z _(p-1)×M/J+2 ,…,z _p×M/J ), Wherein, the maximum value of the natural number p is J, and are sent to the corresponding parallel sub-channel W _p in order for transmission. 2. The method according to claim 1, characterized in that: the set of information channel serial numbers in the step (2)

set with fixed channel number

It is obtained according to the following steps: (21) Determine the channel before polarization transformation: each parallel sub-channel (W ₁ , W ₂ ,..., W _J ) has been used independently

times, the use of the channel for M times is regarded as M single-use independent channels; construct (NM) virtual channels W ₀ with a channel capacity of 0, which are used to correspond to the bits that have been chiseled in step (4); A total of N independent channels are obtained: According to the correspondence between bits and channels determined in steps (4) and (5), and the interleaving mapping relationship determined in step (3), a set of channels w ₁ , w ₂ , ..., w _N is obtained: in, Indicates that the channels on the left and right sides have exactly the same input, output and channel transition probability functions, and f _π (·) is the channel interleaving function; (22) Perform polarization transformation on the N independent channels obtained in the above steps: get N binary input channels with forward and backward dependencies Among them, the channel transition probability function $W_N^{\left(i\right)}(\mathrm{the\; y},u_{1:i-1}|u_i)=\underset{u_{i+1:N}\&Element;{\left\{\mathrm{0,1}\right\}}^{N-i}}{\mathrm{\&Sigma;}}\frac{1}{2^{N-1}}\underset{j=1}{\overset{N}{\mathrm{\&Pi;}}}{w}_j\left({\mathrm{the\; y}}_j\right|x_j);$ Among them, u _i and (y,u _1:i-1 ) are channel

The input and output of , the bit sequence x=u G _N , w _i (·|·) is the channel transition probability function of channel w _i ; (23) Determine the channel number set: calculate each channel separately

capacity

Finally, select K channels with larger capacity, that is, the channel set corresponding to the superscript number i constitutes the information channel set

The set of superscript serial numbers corresponding to the remaining (NK) channels constitutes a set of fixed channel serial numbers

3. The method according to claim 2, characterized in that: the channel interleaving function f _π (·) in the step (21) is constructed according to the principle of equal division of capacity, including the following operations: (211) Construct an N-dimensional capacity sequence c for each i initialization: For i ∈ {1,2,…,M},

In the formula, I( ) is the symmetric channel capacity of the parametric channel: if a certain channel W has an input symbol set of {0,1}, an output symbol set of y, and a channel transition probability function of W(y|b), b ∈{0,1}, y∈y, y is the output symbol set of channel W, then its symmetric channel capacity is: $I\left(W\right)=\frac{1}{2}\underset{b\&Element;\left\{\mathrm{0,1}\right\}}{\mathrm{\&Sigma;}}\underset{\mathrm{the\; y}\&Element;\mathrm{the\; y}}{\mathrm{\&Sigma;}}(W\left(\mathrm{the\; y}\right|b)\&times;\mathrm{lo}{g}_2\left(\frac{2\&times;W\left(\mathrm{the\; y}\right|b)}{W\left(\mathrm{the\; y}\right|0)+W\left(\mathrm{the\; y}\right|1)}\right));$ For i ∈ {M+1,M+2,…,N}, set c _i =0; Re-initialize the subscript sequence π: For each natural number i∈{1,2,…,N}, set π _i =i; and initialize the sorting step L=N; (212) Perform capacity equalization sorting: use the sorting step size L to divide the sequence π into

a subsequence of length L, and for each serial number

Get a subsequence λ ^(m) with sequence number m: λ ^(m) =(π _(m-1)×L+1 , π _(m-1)×L+2 ,…π _m×L ), and sort them according to the principle of equal division of capacity: if the capacity is equal The sorting function is f _ECP ( ), then the new sequence ρ ^(m) = f _ECP (λ ^(m) ,c), and then use this sequence ρ ^(m) to update π, that is, for all t∈{1,2, ...,L}, ${\mathrm{\&pi;}}_{(m-1)\&times;L+t}={\mathrm{\&rho;}}_t^{\left(m\right)};$ (213) Judging whether the construction is completed: if the value of L is less than or equal to 2, the algorithm terminates and the construction is completed, and the mapping relationship of the function f _π (·) is determined as f _π (i)=j; where, i∈{1, 2,...,N}, j∈{1,2,...,N}, and π _i =j; otherwise, set the value of L to be halved, that is, L=L/2, and return to step (212). 4. The method according to claim 3, characterized in that: the capacity equalization sorting in the step (212) requires two input parameters, one of which is the subscript sequence λ of length L, and the other is the step The capacity sequence c in (211), its output parameter ρ is a sorting sequence λ: it should satisfy the previous

The sum of the capacity values corresponding to elements

with after

The sum of the capacity values corresponding to elements

Be as equal as possible; it includes the following specific steps: (212A) Sort λ to obtain a sequence τ, so that for any t∈{1,2,…,L} and s∈{1,2,…,L}, and t≤s, there is a corresponding τ _t The capacity value of is greater than the corresponding capacity value of τ _s , namely

(212B) Initialize two empty sequences, that is, sequences α and β with length zero, and set k=1; (212C) Determine whether the lengths of the two sequences α and β are less than If yes, execute the next step (212D); otherwise, skip to the execution step (212E); (212D) Determine whether the sum of all elements in sequence α is greater than the sum of all elements in sequence β, if so, add τ _k to the end of sequence β; otherwise, add τ _k to the end of sequence α; then, Increase the value of k by 1, that is, k=k+1, and return to the execution step (212C); (212E) Determine whether the length of sequence α is less than

If so, add all elements τ _k , τ _k+2 ,...,τ _L to the end of α; otherwise, add all elements τ _k , τ _k+2 ,...,τ _L to the end of β; (212F) Set the front of the sequence ρ

A subsequence composed of elements is equal to α, then

A subsequence composed of elements is equal to β, that is, for all

ρ _t =α _t ; for all

And output the obtained sequence ρ. 5. The method according to claim 3, characterized in that: the method is applied to the transmission scenario of a single channel, that is, when the number of parallel sub-channels J=1, the channel interleaving function f _π (·) according to the following The equivalent simple method is to construct: set the sequence γ=(1,2,…,N), and then reverse the sequence γ to obtain the sequence π: π=γ·B _N , then determine the function f _π (· ) is f _π (i)=j; where the maximum values of natural numbers i and j are both N and satisfy π _i =j.

Images