CN114900198A

CN114900198A - Method and device for encoding polarization-adjusted convolutional code

Info

Publication number: CN114900198A
Application number: CN202210329701.4A
Authority: CN
Inventors: 陈立; 刘文鑫; 刘星成
Original assignee: Sun Yat Sen University
Current assignee: Sun Yat Sen University
Priority date: 2022-03-31
Filing date: 2022-03-31
Publication date: 2022-08-12

Abstract

The present invention provides a polarization adjustment convolutional code encoding method and device. The method mainly includes the following steps: acquiring an input signal, constructing a generator matrix for polarization encoding according to the definition of polarization encoding, and determining according to the generator matrix The RM weight of the polarized sub-channel; determine that the code length, information dimension and code rate of the target signal satisfy the first preset condition, and construct an initial information index set and an alternative index set; according to the RM weight, the initial information index set and the The candidate index set is constructed to obtain the target channel set; the coded target signal is output through the channels in the target channel set; at the same time, under the condition of the code length and code rate that can be designed by the RM-like structure, the PAC code constructed by the technical solution of the present application It is exactly the same as the class RM. It does not need a lot of simulations while achieving close performance. It has the advantage of low construction complexity and can be widely used in the field of wireless communication technology.

Description

Method and device for encoding polarization-adjusted convolutional code

Technical Field

The present invention relates to the field of wireless communication technologies, and in particular, to a method and an apparatus for polarization-adjusted convolutional code encoding.

Background

Channel coding, a key technique for ensuring reliable transmission, plays a key role in wireless communication systems of all ages. In the face of new application scenarios and challenges of high reliability and low delay, channel coding techniques, especially channel coding with medium and short code length, need further research and development. As a novel channel coding method, a Polarization-Adjusted Convolutional code (PAC) code concatenates Convolutional coding and Polarization coding, and with the aid of a Fano decoder, a theoretical performance limit close to a finite code length is obtained. Although the performance is excellent, the related construction theory and the optimal construction method are still an open problem and are widely concerned by academia and industry.

In the related art, the typical construction schemes can be classified into two types, namely polar-like construction methods and Reed-Muller (RM) -like construction methods. The polar-like construction method, such as a density evolution-Gaussian approximation construction method, is the same as the polar construction idea in the construction idea, and firstly performs approximate estimation on the capacity or reliability of the polarized sub-channel, and then selects the position of the highly reliable polarized sub-channel for information transmission. The similar RM code structure reselects a transmission channel according to the Hamming of the row of the polar code generating matrix, and selects the position with the maximum Hamming value as an information bit. And an RM-polar structure combining the RM structure and the polar structure, wherein partial channels are determined according to Hamming, and then the rest channels are determined according to the reliability of the polarized sub-channels. In addition, there are also simulation-based monte carlo construction methods.

However, in the scheme provided by the related art, the polar structure does not consider the code word structure, so that the decoding performance expressed under the same Fano decoder is the worst; RM-polar improves some of the performance on this basis, but is still less than ideal; the similar RM structure can provide excellent performance, but the optional code rate of the structure scheme is small, for example, the PAC code with the length of 128 codes has only 8 optional code rates, and the problem of discontinuous code rate exists. While the monte carlo structure method is based on simulation, although it can provide a good enough structure for the PAC code with any code length and code rate, its structure needs a lot of simulation and can not keep the superiority of performance under the channel different from the simulation condition.

Disclosure of Invention

In view of the above, to at least partially solve one of the above technical problems, an embodiment of the present invention provides a systematic method for encoding a polarization-adjusted convolutional code that is independent of simulation, has a continuous code rate, and has excellent performance, and an apparatus capable of implementing the method.

In one aspect, the present technical solution provides a method for encoding a polarization-adjusted convolutional code, including the following steps:

acquiring an input signal, constructing a generation matrix of polarization codes according to the definition of the polarization codes, and determining the RM weight of a polarization sub-channel according to the generation matrix;

determining that the code length, the information dimension and the code rate of a target signal meet a first preset condition, and constructing to obtain an initial information index set and an alternative index set;

constructing a target channel set according to the RM weight, the initial information index set and the alternative index set;

outputting the coded target signal through the channels in the target channel set;

the step of constructing and obtaining a target channel set according to the RM weight, the initial information index set and the alternative index set comprises the following steps:

determining an error probability of the polarized sub-channel;

screening the polarized sub-channels according to the error probability to obtain a reference channel index set;

determining a target index according to the RM weight and the weighted sum of the channel utilization rates of the channels in the reference channel index set;

and adding channels in the alternative index set to the initial information index set according to the target index to obtain the target channel set.

In a possible embodiment of the present disclosure, the first preset condition is:

wherein the code length of the target signal is N-2 ⁿ K is an information dimension, h is a positive integer, and h satisfies 0-1.

In a possible embodiment of the present disclosure, after the steps of obtaining an input signal, constructing a generator matrix of polarization codes according to the definitions of the polarization codes, and determining RM weights of polarization subchannels according to the generator matrix, the method further includes the following steps:

determining that the code length, the information dimension and the code rate of the determined target signal meet second preset conditions, and screening according to preset weight value conditions to obtain the target channel set;

the second preset condition is as follows:

wherein the code length of the target signal is N-2 ⁿ K is an information dimension, h is a positive integer, and h satisfies 0-1; the preset weight value conditions are as follows:

f _w (i-1)>h

wherein f is _w (i-1) is the RM weight, and i satisfies 1. ltoreq. i.ltoreq.N.

In a possible embodiment of the present disclosure, the step of determining the error probability of the polarized sub-channel includes:

determining an error probability of the polarized sub-channel by Gaussian approximation, wherein the error probability is as follows:

wherein,

representing the i-th polarized sub-channel,

representing the mean of the ith polarized subchannel output, the function Q is defined as:

in a possible embodiment of the present disclosure, the average value of the output of the ith polarized subchannel may be iterated through the following formula:

the function φ is defined as:

wherein the initial iteration value

The initial iteration value is an initial value with a Gaussian approximate structure signal-to-noise ratio of 0 dB.

In a possible embodiment of the present disclosure, the input signal includes information bits and freeze bits, and before the step of determining the target index according to the RM weight and a weighted sum of channel utilization rates of channels in the reference channel index set, the method further includes:

determining a bit state of the input signal according to the information bit and the frozen bit;

and calculating the number of information bits transmitted by the polarized sub-channel according to the bit state and the generator polynomial to obtain the channel utilization rate.

In a possible embodiment of the present disclosure, after the step of outputting the encoded target signal through the channels in the target channel set, the method further includes:

determining a log-likelihood value or a path value of the virtual channel;

carrying out convolution inverse mapping on the log likelihood value to obtain a first echo value, or carrying out convolution inverse mapping on the path value to obtain a second echo value;

and iteratively updating the virtual channel according to the first return value or the second return value, and outputting the updated virtual channel to obtain a decoding result.

In a possible embodiment of the present disclosure, the step of determining the log-likelihood values or the path values of the virtual channels includes:

performing iterative computation through a butterfly diagram to obtain the log-likelihood value;

and determining a global optimal path through depth-first search, wherein the global optimal path is a virtual channel with the highest reliability determined through posterior probability accumulation according to the path value of the global optimal path.

On the other hand, the technical solution of the present application further provides an apparatus for encoding a polarization-adjusted convolutional code, including:

the code rate configuration unit is used for acquiring an input signal and performing code rate configuration on the input signal; determining that the code length, the information dimension and the code rate of a target signal meet a first preset condition, and constructing to obtain an initial information index set and an alternative index set; constructing a target channel set according to the RM weight, the initial information index set and the alternative index set;

the convolution coding unit is used for constructing and obtaining a convolution coding generating matrix according to a convolution coding generating polynomial and outputting a convolution coding signal;

the polarization coding unit is used for constructing a generation matrix of polarization coding according to the definition of the polarization coding, determining RM weight of a polarization subchannel according to the generation matrix, and outputting a target signal after the polarization coding through a channel concentrated by the target channel;

constructing a target channel set according to the RM weight, the initial information index set and the alternative index set, wherein the method comprises the following steps:

determining an error probability of the polarized sub-channel;

In a possible embodiment of the solution of the present application, the system further comprises:

a decoding unit for determining a log-likelihood value or a path value of a virtual channel;

the polarization mapping unit is used for carrying out convolution inverse mapping on the log likelihood value to obtain a first echo value, or carrying out convolution inverse mapping on the path value to obtain a second echo value; and iteratively updating the virtual channel according to the first return value or the second return value

And the information extraction unit is used for outputting the updated virtual channel to obtain an original signal and extracting information of the original signal to obtain a decoding result.

Advantages and benefits of the present invention will be set forth in part in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention:

compared with a systematic theoretical construction method, namely a similar RM construction method, in the related technology, the technical scheme of the application can provide code rate continuous design; meanwhile, under the condition that the code length code rate can be designed by the similar RM structure, the PAC code constructed by the technical scheme of the application is completely the same as the similar RM. The scheme can be regarded as a general popularization method for any code length code rate similar to an RM construction method. Compared with a Monte Carlo construction method based on simulation, the technical scheme of the application does not need to carry out a large amount of simulation while realizing approximate performance, and has the advantage of low construction complexity.

Drawings

In order to more clearly illustrate the technical solutions in the embodiments of the present application, the drawings needed to be used in the description of the embodiments are briefly introduced below, and it is obvious that the drawings in the following description are only some embodiments of the present application, and it is obvious for those skilled in the art to obtain other drawings based on these drawings without creative efforts.

Fig. 1 is a flowchart of a method for encoding a polarization-adjusted convolutional code according to the present invention;

FIG. 2 is a flowchart illustrating the steps of encoding a PAC code according to the present invention;

FIG. 3 is a flowchart of the steps for calculating a weighted sum according to the teachings of the present application;

fig. 4 is a schematic diagram illustrating transmission of information bits on a plurality of polarized subchannels according to the present disclosure;

FIG. 5 is a schematic diagram of generating a (4, 2) PAC code according to an embodiment of the present application;

FIG. 6 is a flowchart illustrating the steps of decoding the PAC code according to the present invention;

fig. 7 is a schematic diagram of a process of performing iterative computation through a butterfly diagram in the technical solution of the present application;

fig. 8 is a flow chart of a code tree of a Fano decoding algorithm of polar codes with a code length N-4 in the present application;

fig. 9 is a graph illustrating frame error rate performance of PAC codes having information dimensions of 42 and 85, respectively, according to an embodiment of the present invention;

fig. 10 is a graph of frame error rate performance of a PAC code having a code length of 64 and an information dimension of 32 according to the present invention.

Detailed Description

Reference will now be made in detail to embodiments of the present invention, examples of which are illustrated in the accompanying drawings, wherein like or similar reference numerals refer to the same or similar elements or elements having the same or similar function throughout. The embodiments described below with reference to the accompanying drawings are illustrative only for the purpose of explaining the present invention, and are not to be construed as limiting the present invention. The step numbers in the following embodiments are provided only for convenience of illustration, the order between the steps is not limited at all, and the execution order of each step in the embodiments can be adapted according to the understanding of those skilled in the art.

Based on the foregoing theoretical basis and the indicated deficiencies or drawbacks of the related art, as shown in fig. 1, the embodiment method includes steps S100-S400:

s100, acquiring an input signal, constructing a generation matrix of polarization codes according to the definition of the polarization codes, and determining the RM weight of the polarization sub-channel according to the generation matrix.

Specifically, in the embodiment, as shown in fig. 2, the encoding of the PAC code is first configured by the code rate, and the information bits are first arranged

Put to vector

In the information bits of (1), the corresponding subscript set is

Freezing bit fixed to 0, subscript set to

And then, obtaining the PAC code word of which the outer code is a convolutional code and the inner code is a Polar code through convolutional conversion and polarization conversion with the code rate of 1.

Illustratively, the polarization-encoded generator polynomial is g (x) g ₀ +g ₁ x+…+g _t x ^t The constraint length is t + 1. The resulting matrix of polarization encoding can be represented in the form of an upper triangular toeplitz matrix:

further, the code word of the convolutional code

Satisfies the following conditions:

taking the code word of the convolutional code as the input of the Polar encoder, the code word of the PAC code can be obtained:

wherein,

in order to flip the matrix for the bits,

is the product of n-times kronecker of F,

representing a binary field, i.e. representing a set of values of N binary fields.

For example, the PAC code of the embodiment needs to be designed with a code length N-2 ⁿ The information dimension is K, the code rate is R, and the convolution generator polynomial used is g (x) g ₀ +g ₁ x+…+g _t x ^t (ii) a The example first introduces two new parameters: 1) a reference RM weight; 2) the channel utilization, which is defined in relation to:

1) reference RM weight:

given the constructed channel ratio, e.g., set to 0dB in the example, the error probability of the ith polarized subchannel is calculated by Gaussian approximation

The polarized sub-channels are sorted according to the error probability from small to large before being selected

Each channel is used as a reference channel and the index set of the reference channel is

Reference toRM weight ω _i Is defined as follows:

wherein i is more than or equal to 1 and less than or equal to N, f _w (i) The number of 1's in the binary representation representing i. I.e. for the reference channel its reference RM weight is equal to the original RM weight, and for the non-reference channel its reference RM weight is set to 0. For example, if the binary expression of 5 is 101, where the number of 1 s is 2, then f _w (5) 2. Generating matrix G for polar _p The RM weight of the ith row is defined as f _w (i-1) the Hamming weight of the row equals

2) Channel utilization rate:

it can be found from the structure of the PAC code that the PAC code does not directly transmit information bits or freeze bits on the polarized sub-channel. But before the transmission of the polarized subchannel, the convolution transformation with the code rate of 1 is carried out, thereby realizing more flexible capacity allocation. In order to match the assigned transmission tasks to the channel conditions, the utilization of each polarized subchannel needs to be characterized.

That is, before the method obtains the target PAC code, a step of calculating a channel utilization rate may be included, which may include sub-steps S101-S102:

s101, determining the bit state of an input signal according to the information bit and the frozen bit;

and S102, calculating the number of information bits transmitted by the polarized sub-channel according to the bit state and the generator polynomial, and obtaining the channel utilization rate.

In particular embodiments, the input of a convolution transform

Can be divided into information bits with index set of

And frozen bits, indexed set of which

Let B _i Denotes v _i The state of (b), i.e. the state of the signal bit, can result in:

wherein i is more than or equal to 1 and less than or equal to N, the channel utilization rate is tau _i Expressed as:

wherein i is more than or equal to 1 and less than or equal to N,

τ _i representing the number of information bits transmitted over the ith polarized subchannel.

S200, determining that the code length, the information dimension and the code rate of a target signal meet a first preset condition, and constructing to obtain an initial information index set and an alternative index set;

in particular, in the embodiment, based on the RM weights and the channel utilization rate proposed in the previous section, as shown in fig. 3, in the embodiment, the RM weight of each row of the generation matrix of the polarization coding, i.e. the RM weight of the ith row, is calculated as f _w (i-1). Selecting a positive integer h, wherein h is more than or equal to 0 and less than or equal to n-1 to satisfy the following conditions:

in the embodiment, if the left equal sign is true,

that is, it is determined that the code length, the information dimension, and the code rate of the target signal satisfy the second preset condition, the embodiment is straightSelecting RM weights satisfying f _w (i-1)>h, i is more than or equal to 1 and less than or equal to N is used as an information bit index for PAC coding. The design result in this case is the same as in the prior art RM construction.

In an embodiment, if the equal sign is not true, the first preset condition is satisfied:

according to f _w (i-1) defining an initial information bit index set

And an alternative index set S. Wherein,

collecting RM weights satisfying f _w (i-1)>h,1 is more than or equal to i is less than or equal to N, S collects RM weight and satisfies f _w And (i-1) is h, and 1 is not less than i and not more than N.

S300, constructing a target channel set according to the RM weight, the initial information index set and the alternative index set;

in an embodiment, step S300 may further include steps S301 to S304:

s301, determining the error probability of the polarized sub-channel;

in particular, in an embodiment, the error probability of a polarized subchannel is determined by gaussian approximation. The gaussian approximation is a method commonly used to estimate the reliability of polarized sub-channels. For a binary input white Gaussian noise channel, the noise power is sigma ² The output of the channel follows a gaussian distribution with a mean of 2/sigma ² Variance of 4/σ ² Assuming that a transmitting end transmits all-zero code words, a channel transition probability Likelihood Ratio (Log-Likelihood Ratio, LLR) in a decoding process is a random value subject to gaussian distribution. Then for an N long polar code, the average of the output of its ith polarized subchannel

The calculation can be performed by the following iterative formula:

with an initial iteration value of

Where φ (-) is defined as follows:

the error probability of each polarized subchannel can be obtained through an iterative formula

Wherein Q (·) is defined as follows:

s302, screening the polarized sub-channels according to the error probability to obtain a reference channel index set;

in particular, in embodiments, when a condition is satisfied

By construction

Collecting RM weights satisfying f _w (i-1)>t,1 is more than or equal to i and less than or equal to N, the row sequence number is used as an initial information index set, and S collection RM weight satisfies f _w Lines where t is t, 1. ltoreq. i.ltoreq.NThe sequence number serves as an alternative index set.

S303, determining a target index according to the RM weight and the weighted sum of the channel utilization rates of the channels in the reference channel index set;

specifically, in the embodiment, in order to more accurately characterize the condition of the polarized subchannel, the reference RM weight is attenuated by using the channel utilization rate, and the weight of the polarized subchannel after a certain number of information bit positions is determined is analyzed. For the ith polarized subchannel, the initial channel weight is the reference RM weight, i.e. ω _i . The channel utilization rate of the sub-channel is tau _i I.e. with τ _i An information bit is transmitted over the channel. For example, the information bits transmitted on the channel are independent of each other, sharing the transmission capability of the channel; at this time, for a newly added information bit, it will be equal to τ _i The information bits share the channel, and the newly added information bits can obtain 1/tau of the polarized subchannel _i +1 transmission resource. Correspondingly, the weight of the channel is attenuated to 1/(τ) of the original _i +1), i.e. ω _i /τ _i +1。

As shown in fig. 4, the information bits v are transformed by convolution _i Can transmit on a plurality of polarized subchannels, will participate in the transmission v _i The weights of the polarized subchannels of (1) are added, the resulting weighted sum being:

wherein i is more than or equal to 1 and less than or equal to N. Weighting generalizes the channel condition profile from a polarized subchannel to before convolutional coding, where θ _i Reflecting the priority, θ, of the transmission of information bits as information bits in line i _i The larger the size, the more reliable the information transmission using the position.

S304, adding channels in the alternative index set to the initial information index set according to the target index to obtain a target channel set;

in particular, in an embodiment, the index i with the largest weighted sum in the candidate index set is determined ^* Which satisfies:

i ^* ＝argmax{θ _i ,i∈S}

will i ^* Move from S to

Calculating out

Number of elements (2)

If it is

Then output

As a final result, the example method terminates; if it is

The process of calculating the channel utilization ratio is skipped back to the step, the channel utilization ratio is iteratively updated, and the steps S301 to S304 are iterated.

S400, outputting the coded target signal through the target channel set;

in particular, in an embodiment, the implementation finally outputs the target signal after completion of the polar convolutional encoding.

The polarization-adjusted convolutional encoding process provided by the embodiments of the present application is described in detail with reference to the accompanying drawings:

illustratively, the code length of the PAC code to be designed is N-2 ⁿ The information dimension is K, the code rate is R, and the convolution generator polynomial used is g (x) g ₀ +g ₁ x+…+g _t x ^t 。

(1) Calculating the RM weight of each row of the generation matrix of the polarization coding, namely the RM weight of the ith row is f _w (i-1). A positive integer h is selected, h is more than or equal to 0 and less than or equal to n-1

(2) If the left side equal sign is true, that is

Collecting RM weights satisfying f _w (i-1)>h, i is more than or equal to 1 and less than or equal to N, and outputting

As a final result, the algorithm terminates; if the equal sign is not true

Collecting RM weights satisfying f _w (i-1)>t, i is more than or equal to 1 and less than or equal to N, the row sequence number is used as an initial information index set, and S collection RM weight satisfies f _w Taking the row sequence number of (i-1) ═ t, i is more than or equal to 1 and less than or equal to N as an alternative index set;

(3) calculating error probability of each polarized subchannel

It can be obtained by a gaussian approximation method:

wherein Q (·) is defined as follows:

the value of (c) can be calculated by the following iterative formula:

initial iteration value thereof

Constructing an initial value at a signal-to-noise ratio of 0dB corresponding to a Gaussian approximation, wherein φ (-) is defined as follows:

(4) sorting the polarized sub-channels from small to large according to the error probability, and selecting the first channel before the first channel is selected

The reference RM weights are calculated according to:

(5) the channel utilization is calculated according to the following formula:

wherein B is _i Denotes v _i The state of (1). Namely:

(6) for i ∈ S, a weighted sum is calculated according to:

(7) determining the weighted index and the maximum index in the alternative index set:

i ^* ＝argmax{θ _i ,i∈S}

will i ^* From S to

(8) Computing

Number of elements (2)

If it is

Then output

As a final result, the algorithm terminates; if it is

Then the iteration is performed by jumping back to the step (5).

As shown in fig. 5, to design a (4, 2) PAC code, a convolution generates polynomial bits g (x) 1+ x ² The convolutional network is shown in fig. 5. The RM weight of each row is calculated to be { f _w (0),f _w (1),f _w (2),f _w (3) 0,1,1, 2. The available h is 1, i.e. the initial information index set at this time

Alternative index set S ═ {2,3 }. According to the formula

The number of reference channels obtained at this time is 3, and the weight of the reference RM is

According to the beginningIndex set of start information

The available channel utilization rate is

From this, a weighted sum of

It can be seen that the weighted sum of {2} in the alternative index set is maximized, moving it from S to

Namely, it is

S ═ 3. At this time

The iteration is terminated, i.e. the set of information bit indexes of the final design is

In addition, as shown in fig. 6, the present application provides a decoding process of the PAC code, that is, the method of the embodiment may further include steps S500 to S700:

s500, determining a log-likelihood value or a path value of a virtual channel;

in the embodiment, the logarithm likelihood value can be obtained by iterative computation through the butterfly diagram; or determining a global optimal path through depth-first search, wherein the global optimal path is a virtual channel with the highest reliability determined through posterior probability accumulation according to the path value of the global optimal path.

In particular, in embodiments, the PAC code shifts the binary tree search process to convolutional codes, compared to Polar decoding methods. U is obtained by SC or Fano decoding calculation _i Log likelihood value of

Or path value

S600, carrying out convolution inverse mapping on the log likelihood value to obtain a first echo value, or carrying out convolution inverse mapping on the path value to obtain a second echo value;

in particular, in embodiments, the current convolution register state is based on

v _i →u _i The following mapping relationship exists: 0 → 0,1 → 1. Convolution inverse mapping log-likelihood values, i.e.

Or

Using the soft value to perform a corresponding tree search algorithm, and then determining the value

And returning. If v is _i →u _i The mapping relation is satisfied: 0 → 1,1 → 0

Or

Feedback estimate

S700, iteratively updating the virtual channel according to the first return value or the second return value, and outputting the updated virtual channel to obtain a decoding result;

specifically, in the embodiment, iteration is performed according to the return value to obtain the next logarithm likelihood value or path value, and so on until the search is finished, so as to obtain a complete decoding result.

In addition, two decoding methods are provided in the embodiment:

SC decoding algorithm

Encoded codeword vectorcAfter BPSK modulation and discrete memoryless channel, obtaining the receiving symbol vector

By using

An information vector representing a decoding estimate. Based on the channel polarization theory, the i-th polarized subchannel after polarization can be regarded as the input

And

an output of u _i Virtual channel of (2), channel transition probability likelihood ratio thereof

Satisfies the following conditions:

wherein,

in order to be a channel-transition probability,

the representation of the real number field is performed,

the set of values representing the N real number fields should be N (codeword length). As shown in figure 7 of the drawings,

as LLR value can pass through a butterflyThe pattern is iteratively calculated. Butterfly diagram-total log of Polar code with code length N ₂ And N +1 layers. Starting from the leftmost, at the decoding node of each layer,

represents the ith information bit u of Polar code with code length N _i The LLR value of (1) can be calculated by the LLR values of two sub-codes with the next code length of N/2, and so on, and finally can be decomposed into N sub-codes with the code length of 1. This portion is the LLR value of the received symbol

It can be directly obtained by channel observation:

wherein i is more than or equal to 1 and less than or equal to N.

The recursive formula for LLR is as follows:

wherein,

and

respectively represent

The elements corresponding to the odd index values and the elements corresponding to the even index values. f. of ₊ (. and f) _- (. cndot.) is defined as follows:

wherein

The LLR value of the information bit end can be calculated through the recursion, and the LLR value is directly judged to be 0 for all the frozen bits, namely the LLR value is judged to be 0

For information bits

Then the following decision is made:

fano decoding algorithm

Compared with the decoding idea of SC decoding local optimization, the Fano decoding algorithm adopts a strategy of depth-first search on the basis of SC to seek global optimization. Assuming a uniform distribution of information bits, i.e.

P(u _i ＝0)＝P(u _i 1) to 0.5. Using Bayesian equations, a posterior Probability (A Posteriori Probability, APP) can be obtained

Satisfies the following conditions:

wherein

Can be obtained by an iterative formula of SC. In order to fairly compare the reliability of paths of different lengths, the algorithm proposes a new metric value based on the posterior probability of the path. Suppose from

To

The accumulated value of the posterior probabilities of the paths is:

this value represents the reliability of the estimated path. Ideally, this value can reach an upper bound of the accumulated value of MAP:

in embodiments where the information bits are independent of each other, the upper bound is approximated as follows:

wherein

For the ith information bit

The lower bound of the decoding error probability can be obtained by a Gaussian approximation method. The original path metric value can be corrected by using the value so as to achieve the fair comparison of paths with different lengths. The path metric value of the Fano decoding algorithm is represented as follows:

wherein

Initialized to 0, the physical meaning of this value is the offset of the current path from the ideal optimal path. In the representation of the binary tree,

the path metric value of the node of the ith layer is represented by two kinds of representations

And

representing the metric values of the left and right paths in meters extending from layer i-1, respectively. Larger metric values represent more reliable paths. To prevent the wrong path from being extended, the Fano decoding algorithm introduces a threshold T and a step size Δ. Only if the metric value of a path is greater than T is the path considered worth expansion. Meanwhile, in order to make the decoder always output a complete decoding result, the threshold value T is dynamically changed according to the step size Δ, i.e. T ∈ {0, ± Δ, ± 2 Δ, … }. The specific decoding description algorithm is as follows:

for each new extension node

The decoder will be

And

comparing with threshold T for convenient expression

The larger of the two values is

The corresponding decoding estimate is

Otherwise it is recorded as

And

1. if it satisfies

Then expand

2. If it satisfies

It means that the current path is not ideal, and the decoder will generate a fallback to traverse the parent node of the current node from near to far

Until a node is found that meets the following conditions or back to the starting point.

a)

b)

Is not expanded.

During the forward or backward process, the threshold T is dynamically adjusted according to the following rules:

1. in the process of advancing, if the expanded conditions are satisfied

T + j Δ,

j

1,2, …, such that the updated T satisfies

2. In the process of rollback, if

Let T be T- Δ;

3. if it returns to the starting point. Let T be T- Δ.

Once a complete path from the root node to the leaf node is obtained, the decoder stops decoding, and a result corresponding to the complete path is output as a final decoding result.

As shown in fig. 8, a flow chart of a Fano decoding algorithm code tree for polar code with code length N-4 is shown, in this embodiment,

the threshold T is-4 and the step size Δ is 4. Wherein the number next to the node represents the path value of the path, and the number on the arrow represents u _i The value of (a). When i is 3, the calculation result is

And

satisfy the requirements of

Selecting

The path of (2) is expanded. Subsequent calculation

Value of (2), discovery

At this point, the decoder rolls back and finds

Selecting

The path of (2) is expanded. Followed by

So far, the decoder is smoothly expanded to the leaf node, the decoding is finished, and the decoding result is

In order to prove the advantages of the scheme, a related simulation result is given below, the simulation channel condition is an additive white gaussian noise channel, the modulation mode is binary phase shift keying, and the step length delta of the used Fano decoder is 1;

as shown in fig. 9, a comparison of frame error rate performance is given for PAC codes with a code length of 128 and information dimensions of 42 and 85, respectively. Wherein, the curve of Weighted Sum is the PAC code decoding frame error rate curve constructed by the method provided by the scheme, the curve of RM-polar is the PAC code frame error rate curve constructed by RM-polar, and NA is the lower bound of the theoretical frame error rate under the condition of the code length and code rate. It is noted that the above example cannot be designed by the RM-like construction method. It can be seen that the designed PAC code performs far better than the PAC code constructed by RM-polar under the same decoder.

As shown in fig. 10, a comparison of frame error rate performance is given for a PAC code having a code length of 64 and an information dimension of 32. Wherein the curve of "Monte-Carlo XdB" represents the frame error rate curve of PAC code designed based on Monte Carlo method under the condition of constructing signal-to-noise ratio XdB. It can be seen that the performance of the PAC code provided by the present scheme effectively approaches that of the PAC code designed by monte carlo. Meanwhile, the technical scheme of the application does not depend on simulation, and has the advantage of low construction complexity.

On the other hand, the technical scheme of the application also provides a data processing device; it includes:

the code rate configuration unit is used for acquiring an input signal and carrying out code rate configuration on the input signal; determining that the code length, the information dimension and the code rate of a target signal meet a first preset condition, and constructing to obtain an initial information index set and an alternative index set; constructing a target channel set according to the RM weight, the initial information index set and the alternative index set;

determining an error probability of the polarized sub-channel;

and adding channels in the alternative index set to an initial information index set according to the target index to obtain the target channel set.

In some alternative embodiments, the system is further capable of performing a transcoding function, the system comprising:

And the information extraction unit is used for outputting the original signal through the updated virtual channel and extracting information of the original signal to obtain a decoding result.

From the above specific implementation process, it can be concluded that the technical solution provided by the present invention has the following advantages or advantages compared to the prior art:

(1) compared with the systematic theoretical construction method with the best performance and the similar RM construction method, the method provided by the technical scheme of the application can provide code rate continuous design. Meanwhile, under the condition of code length and code rate which can be designed by the similar RM structure, the PAC code constructed by the method provided by the scheme is completely the same as the similar RM. The proposal can be regarded as a general popularization method for any code length code rate similar to an RM construction method;

(2) compared with a Monte Carlo construction method based on simulation, the technical scheme of the application does not need to carry out a large amount of simulation while realizing approximate performance, and has the advantage of low construction complexity.

In alternative embodiments, the functions/acts noted in the block diagrams may occur out of the order noted in the operational illustrations. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality/acts involved. Furthermore, the embodiments presented and described in the flow charts of the present invention are provided by way of example in order to provide a more thorough understanding of the technology. The disclosed methods are not limited to the operations and logic flows presented herein. Alternative embodiments are contemplated in which the order of various operations is changed and in which sub-operations described as part of larger operations are performed independently.

Furthermore, although the present invention is described in the context of functional modules, it should be understood that, unless otherwise stated to the contrary, one or more of the functions and/or features may be integrated in a single physical device and/or software module, or one or more of the functions and/or features may be implemented in a separate physical device or software module. It will also be appreciated that a detailed discussion of the actual implementation of each module is not necessary for an understanding of the present invention. Rather, the actual implementation of the various functional modules in the apparatus disclosed herein will be understood within the ordinary skill of an engineer, given the nature, function, and internal relationship of the modules. Accordingly, those skilled in the art can, using ordinary skill, practice the invention as set forth in the claims without undue experimentation. It is also to be understood that the specific concepts disclosed are merely illustrative of and not intended to limit the scope of the invention, which is defined by the appended claims and their full scope of equivalents.

The logic and/or steps represented in the flowcharts or otherwise described herein, e.g., an ordered listing of executable instructions that can be considered to implement logical functions, can be embodied in any computer-readable medium for use by or in connection with an instruction execution system, apparatus, or device, such as a computer-based system, processor-containing system, or other system that can fetch the instructions from the instruction execution system, apparatus, or device and execute the instructions.

In the description herein, references to the description of the term "one embodiment," "some embodiments," "an example," "a specific example," or "some examples," etc., mean that a particular feature, structure, material, or characteristic described in connection with the embodiment or example is included in at least one embodiment or example of the invention. In this specification, the schematic representations of the terms used above do not necessarily refer to the same embodiment or example. Furthermore, the particular features, structures, materials, or characteristics described may be combined in any suitable manner in any one or more embodiments or examples.

While embodiments of the present invention have been shown and described, it will be understood by those of ordinary skill in the art that: various changes, modifications, substitutions and alterations can be made to the embodiments without departing from the principles and spirit of the invention, the scope of which is defined by the claims and their equivalents.

While the preferred embodiments of the present invention have been illustrated and described, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims.

Claims

1. A method of polarization adjusted convolutional code encoding, comprising the steps of:

acquiring an input signal, constructing a generation matrix of polarization codes according to the definition of the polarization codes, and determining RM weights of polarization sub-channels according to the generation matrix;

determining an error probability of the polarized sub-channel;

2. The method of claim 1, wherein the first predetermined condition is:

3. The method of claim 1, wherein after the steps of obtaining the input signal, constructing a generator matrix of the polarization coding according to the definition of the polarization coding, and determining the RM weight of the polarization subchannel according to the generator matrix, the method further comprises the steps of:

the second preset condition is as follows:

f _w (i-1)>h

wherein f is _w (i-1) is the RM weight, and i satisfies 1. ltoreq. i.ltoreq.N.

4. The method of claim 1, wherein the step of determining the error probability of the polarized subchannel comprises:

wherein,

representing the i-th polarized sub-channel,

5. the method of claim 4, wherein the average of the i-th polarized subchannel output is iterated by the following formula:

the function φ is defined as:

wherein the initial iteration value

6. The method of claim 1, wherein the input signal comprises information bits and frozen bits, and wherein prior to the step of determining the target index based on the weighted sum of the RM weights and the channel utilization of the channels in the reference channel index set, the method further comprises:

7. The method of claim 1, wherein after the step of outputting the encoded target signal over the channels in the target set of channels, the method further comprises:

determining a log-likelihood value or a path value of the virtual channel;

carrying out convolution inverse mapping on the log-likelihood value to obtain a first feedback value, or carrying out convolution inverse mapping on the path value to obtain a second feedback value;

8. The method of claim 6, wherein the step of determining the log-likelihood or path values of the virtual channels comprises:

9. An apparatus for polarization modulated convolutional code encoding, comprising:

the code rate configuration unit is used for acquiring an input signal and carrying out code rate configuration on the input signal; determining that the code length, the information dimension and the code rate of the target signal meet a first preset condition, and constructing to obtain an initial information index set and an alternative index set; constructing a target channel set according to the RM weight, the initial information index set and the alternative index set;

the convolutional coding unit is used for constructing a generated matrix of convolutional coding according to a generating polynomial of the convolutional coding and outputting a signal after the convolutional coding;

determining an error probability of the polarized sub-channel;

10. The apparatus for polarization modulated convolutional code encoding as claimed in claim 9, wherein said system further comprises: a decoding unit for determining a log-likelihood value or a path value of a virtual channel;