CN110048814A - A kind of sparse superimposed code design scheme based on mixed iteration power distribution - Google Patents

Abstract

The present invention proposes a sparse superposition code design scheme based on hybrid iterative power allocation. Specifically, the input real-valued signal is sparsely represented by one-hot encoding, so that there is only one non-zero value in each group. Then, the non-zero value in each group of the sparse message vector is assigned by using the hybrid iterative power allocation scheme proposed in the present invention. Then, the linear combination of the corresponding grouping is performed with the random Hadamard design matrix to form the corresponding codeword. Next, the formed codeword is input into the AWGN channel, and the codeword is added with Gaussian white noise with a mean value of 0 and a variance of σ ² . The output noisy codeword is subjected to the AMP decoding algorithm, and the iterative estimation operation of the codeword is performed to obtain the estimated value of the message vector. The bits corresponding to the maximum value in each group of the obtained estimated values are set to the preset values obtained by power allocation, and the remaining bits are set to 0, so that the reconstructed value of the original signal can be obtained. To use spyder3 for experiments, the python third-party packages that need to be used include numpy, pyfht, etc.

Description

A Sparse Superposition Code Design Scheme Based on Hybrid Iterative Power Allocation

technical field

The invention belongs to the technical field of signal processing, in particular to a sparse superposition code design scheme based on hybrid iterative power allocation.

Background technique

As an indispensable part of the digital age and the information society, communication has always been the object of extensive attention of researchers. In 1948, Shannon proposed that channel coding is helpful for the efficient and reliable transmission of signals, and Shannon's three theorems pointed out the direction for the design of channel coding. As long as the information is transmitted at a communication rate lower than the channel capacity, there must be a channel coding method, so that the probability of errors in the transmitted information tends to be infinitely small with the increase of the coding length. Although channel coding can achieve good performance, the existence of Shannon's circle makes the performance of channel transmission no longer increase or even drop sharply after reaching a certain level. Therefore, developing codes that are computationally efficient and capable of reaching the Shannon bound is a long-standing and important goal in information theory. At present, some excellent channel codes have emerged, such as Turbo codes, LDPC codes and Polar codes. No matter in the definite channel theory model or in the actual communication system, the performance close to Shannon capacity can be achieved. Among them, LDPC codes have been shown to achieve capacity-capable communication rates on binary-erased channels, while also showing excellent performance on other channels with binary input, discrete input alphabets. However, many physical communication channels have continuous-valued inputs, such as AWGN channels. To apply Turbo codes, LDPC codes, etc. to such channels, additional modulation schemes are required to modulate the signal, and common modulation schemes include phase shift keying, quadrature amplitude modulation, and the like. The process of combining binary error-correcting codes with a standard modulation scheme is called coded modulation, and it is well documented that coded modulation has excellent empirical performance. But for the AWGN channel, there is no theoretical proof that the coding scheme can achieve the performance of the capacity realization. In order to study an effective channel coding scheme, which can be directly applied to the AWGN channel without modulation, and can achieve the performance of the communication rate approaching the channel capacity, experts and scholars in the field of information theory have conducted extensive research. Among them, A.Joseph and A.Barron proposed a sparse superposition code (Sparse Superposition Code, sparse superposition code) in 2010, also known as a sparse regression code (Sparse regression code, SPARC), on the AWGN channel, the code uses effective decoding Coder decoding can achieve AWGN channel capacity.

Initially, A.Joseph and A.Barron proposed an efficient decoding algorithm-adaptive continuous decoding, and proved that for any fixed communication rate R<C, with the increase of the code length, the use of this decoder can make the sparseness The decoding error probability of the superposition code decays to zero at a nearly exponential rate. Subsequently, an adaptive soft threshold decoder and an approximate message passing (AMP) decoder were proposed. These two decoders introduced a soft threshold and updated the posterior probability iteratively to estimate the original signal. Compared with the decoding method using hard threshold, more excellent decoding performance can be achieved. Although, the above three decoding methods show that the decoding error probability can be attenuated to 0 for any rate R<C when the coding length increases. However, the AMP decoding algorithm has become the mainstream sparse superposition code decoding algorithm due to its low computational complexity and excellent reconstruction performance.

Although the AMP decoder has greatly improved the decoding performance of the sparse superposition code, when the rate approaches the Shannon bound, due to the phase transition constraints, the decoder performance drops sharply when it reaches a certain transmission rate close to the channel capacity. The phenomenon is similar to the LDPC code decoding process. In order to solve this problem and improve the decoding performance of the sparse superposition code under the condition of limited length, the power distribution design of the coding structure of the sparse superposition code can be carried out. Different power allocation schemes have significantly different decoding performance under the condition of limited code length. The key lies in how to design an effective power allocation method to minimize the decoding error of the sparse superposition code. In order to achieve lower decoding errors, several effective power allocation schemes have been proposed. However, there are generally problems of unreasonable allocation, which makes it difficult to start the decoding process, or the power allocation does not meet the decoding requirements, resulting in low decoding accuracy. In view of the above background, the present invention proposes a hybrid iterative power distribution scheme. Based on this power allocation scheme, a sparse superposition code construction method is proposed. The random Hadamard matrix is used for linear coding, and the AMP decoder is used to realize the decoding of the sparse superposition code on the AWGN channel.

SUMMARY OF THE INVENTION

Taking advantage of the positive effect of power allocation on the decoding performance of the sparse superposition code, the present invention proposes a new power allocation scheme - hybrid iterative power allocation, aiming at the deficiencies of the existing power allocation schemes. It first allocates the minimum required power to all groups, and then divides the unallocated power equally between each group. Through this method, each group can obtain power higher than the minimum required power, avoiding the situation that the initial group can only be allocated to the minimum required power in the design of the iterative power allocation scheme, which may cause cascading faults and lead to high decoding errors. . Compared with the iterative power allocation scheme, under the condition that each packet can achieve the minimum required power, there is still excess power for resisting interference, which enhances the robustness of decoding. Better decoding performance than iterative power allocation.

The technical scheme and flow sequence of the present invention are as follows:

(1) Map the real-valued signal to be transmitted into a sparse vector with only one non-zero value for each group by means of one-hot encoding. Using the hybrid iterative power distribution scheme proposed in the present invention, the non-zero value in each group is designed and satisfy

(2) The random Hadamard design matrix and the sparse vector are used to perform linear combination of corresponding groupings, and are encoded as codewords that can be transmitted in the AWGN channel;

(3) The code word is transmitted through the AWGN channel, and the noisy code word is output;

(4) decoding and reconstructing through the AMP decoder to obtain the estimated value of the sparse vector;

(5) Make a hard decision to restore the original signal.

Description of drawings

Figure 1. Working principle diagram of sparse superposition code on AWGN channel

Figure 2 Schematic diagram of the hybrid iterative power allocation scheme

Figure 3 Schematic diagram of linear combination of design matrix A and sparse message vector β

Figure 4. Diagram of sparse superposition code system based on hybrid iterative power allocation

Figure 5 Comparison of decoding errors under different B conditions

Figure 6 Comparison of decoding errors corresponding to different Rs under the conditions of B=L=1024, M=512, and snr=7

Figure 7 Comparison of decoding errors corresponding to different Rs under the conditions of B=L=1024, M=512, and snr=3

Figure 8 Comparison of decoding errors corresponding to different Rs under the conditions of B=L=256, M=256, and snr=7

specific implementation

The present invention is described in further detail below in conjunction with the accompanying drawings.

In the accompanying drawings, Fig. 1 is a working principle diagram of sparse superposition code in AWGN channel. With reference to the accompanying drawings, and in combination with the hybrid iterative power allocation scheme proposed by the present invention, the encoding and decoding process of sparse superposition code is described in detail as follows:

Step 1: Input real-valued signal The signal contains L elements, and the size of each element does not exceed M. The one-hot encoding method is used to convert the input real-valued signal into a sparse message vector β, so that the converted sparse message vector β has L groups, each group has M elements, and each group has only one non-zero value, the remaining M-1 elements are all 0. For a clear understanding of the original signal How is converted to beta, illustrated by a simple example. like Obviously, this real-valued signal has 6 elements, and each element does not exceed d, ie the alphabet contains only four symbols {a,b,c,d}. Therefore, L=6, M=4, then β=[[1000], [0010], [0100], [1000], [0001], [0010]], where [] represents cascade.

Step 2: Set the non-zero value in each group to where P ₁ , P ₂ ,..., _PL are pre-specified positive constants that satisfy the following relationship:

Among them, P is the total power, called The assignment of is power allocation. The present invention makes use of the positive effect of power allocation on the decoding performance of the sparse superposition code, and conducts in-depth research on the existing power allocation scheme.

At present, iterative power allocation can achieve lower decoding errors than other existing power allocation schemes. However, when allocating power to the preceding packets, only the minimum required power for allocating and decoding is considered, so that the first packet may not be correctly decoded due to excessive noise interference, resulting in a cascading failure. Aiming at this problem, the present invention improves iterative power allocation and proposes a hybrid iterative power allocation scheme. The purpose is to reduce noise interference and enhance decoding robustness, so that the sparse superposition code combined with the proposed hybrid iterative power allocation scheme can obtain better decoding performance under the condition of low signal-to-noise ratio.

In order to facilitate the description of the variables in the subsequent power scheme, the AMP decoding algorithm based on power allocation is first described as follows:

Assume that the output of the AWGN channel is y=x+ω=Aβ+ω, where x is the codeword generated by encoding. A is the design matrix used to generate codewords, also known as a "dictionary". ω is Gaussian white noise with mean 0 and variance σ ² . The AMP decoder is iteratively updated to generate successive estimates {βt ^} of the message vector β, where

Initialize β ⁰ =0, calculate

Among them, any variable whose upper and lower labels are negative values are all set to 0. Constant {τ _t } and estimation function Defined as follows:

Among them, σ ² is the variance of Gaussian noise, P is the total power of the codeword, these values are all preset known values, and the signal-to-noise ratio snr=P/σ ² . Assuming that the noise variance σ ² =1 in the AWGN channel, the total power P is equal to the signal-to-noise ratio snr. For the variable x _t-1 in equations (4) and (5), we have

x _t-1 :=x(τ _t-1 ) (6)

In formula (7), j∈[M], Indicates that it is independent and identically distributed of random variables.

for Define the estimation function The formula is as follows:

obvious, it can be noticed depends on all elements of s in sec(i).

make For sufficiently large M, and for any constant δ∈(0,1), we have

Among them, κ ₁ and κ ₂ are general normal numbers.

If the constants κ ₁ and κ ₂ in equations (9) and (10) cannot be precisely specified, in order to design the power distribution scheme, the following approximation of x(τ) is used:

The approximate expression shown in formula (11), with the increase of L and M, the accuracy increases, which has a good guiding role for designing suitable power distribution. For the effective noise variance after t iterations If any group normalized power If it is greater than the threshold 2Rτ ² ln2, the sparse superposition code can be correctly decoded in the (t+1)th iteration. For a given power allocation, the parameter can be set by the lower bound in Eq. (11) Iterative estimation can be performed to quickly check whether reliable decoding can be performed with a given power allocation under large system limits. With reference to Figure 2 in the accompanying drawings, the hybrid iterative power distribution design proposed in the present invention is described as follows:

(1) Divide the L blocks of the sparse superposition code into B blocks equally, each block has L/B blocks, and all are allocated the same power.

(2) The minimum power required for decoding is sequentially allocated to each block. The minimum power is first allocated to the packets in the first block, so that the packets in the first block meet the conditions is translatable in the first iteration. According to equation (11), each grouping in the first block can be set as

Then, using formula (11) and formula (5), we can get

Using the value of equation (13), all packets of the second block can be allocated power According to this method, it can be calculated sequentially until all packets are allocated minimum power.

(3) After the allocation is completed according to this method, when R<C, the allocated power must be less than the total power P, and at this time, the remaining power P _remains are evenly allocated to all the groups.

According to the description of the above steps, the summary algorithm is as follows:

Step 3: Design a design matrix A with a dimension of n×LM, where n is the number of rows of A, and the number of columns is N=LM, and n can be obtained from L, M and R. The design matrix A has L groupings, and the number of columns in each grouping is M. Because the sparse message vector β has L groups, and each group consists of M columns, the total number of codewords is M ^L . In order to obtain the communication rate of Rbits, it is necessary to

M ^L = 2 ^nR (14)

Take the logarithm of both sides to get

Llog ₂ M=nR (15)

Therefore, the number of rows of the design matrix A can be obtained as n=Llog ₂ M/R.

The design matrix A uses a random Hadamard matrix. Compared with the traditional Gaussian matrix, it has significantly lower coding and decoding complexity, and the memory footprint is also much reduced. The construction method of the random Hadamard matrix is to randomly extract n rows from a 2 ^m × 2 ^m Hadamard square matrix and sort them. The row and first column elements are all +1). Therefore, the size of m must satisfy So that there are enough rows and columns for selection, excluding the selection of the first row and column. The design matrix formed by random selection requires that all columns have a mean of 0, and each element in the matrix needs to be divided by Make each column norm 1.

FIG. 3 in the accompanying drawings is a schematic diagram of the linear combination of the design matrix and the sparse message vector, which represents the generation process of the codeword. The construction of the codeword is actually a linear combination of the columns of the design matrix A, which is expressed as

x=Aβ (16)

Step 4: The codeword x formed by linear coding is transmitted through the AWGN channel, so that the output of the receiving end is y, which satisfies

y=x+ω (17)

Step 5: Use the iterative equations shown in equations (2) and (3) in the AMP decoder algorithm in step 2 to iteratively estimate the sparse message vector to obtain an estimated vector β ^T after T iterations.

Step 6: Make a hard decision on the estimated vector β ^T obtained by iteration, and set the position corresponding to the maximum value in each group as And the remaining M-1 bits are 0, the reconstructed sparse vector can be obtained like It means that the original signal input was successfully reconstructed without errors.

In order to evaluate the reconstruction performance, the Section Error Rate (SER) is introduced to evaluate the proportion of reconstructed error packets.

Figure 4 in the accompanying drawings is a flow chart of the coding and decoding of the sparse superposition code working in the AWGN channel, which clearly shows the detailed system work flow of the sparse superposition code under the hybrid iterative power allocation condition proposed by the present invention, which is conducive to understanding the whole coding The working steps of the code system.

In order to illustrate that the hybrid iterative power allocation scheme proposed by the present invention has indeed improved performance compared with the iterative power allocation, it is verified by experimental simulation. In all experiments, the noise variance is set to 1, the maximum number of iterations is 64, 200 different message sequences are randomly generated, and experiments are performed separately, and the average SER of 200 experiments is counted. Because the proposed hybrid iterative power allocation and iterative power allocation both use the approximate relationship of Equation (11), in practice, the minimum required power that can be calculated is an approximate value. In order to obtain the optimal value for the final decoding result, R in the formula does not directly select the current communication rate, but uses R _PA , so that R _PA =aR. For the proposed hybrid iterative power allocation, generally a < 1, and as R increases, the corresponding a also increases. Adjust a to select the optimal decoding result.

The simulation comparison of FIG. 5 in the accompanying drawings of the specification shows the decoding performance of 200 groups of different message sequences of size L=1024 and M=512 under two different signal-to-noise ratio conditions at a certain rate. It can be found that as B increases, the decoding performance does not change much and even lower decoding errors can be obtained. Therefore, B=L was selected for further verification experiments.

Figure 6, Figure 7 and Figure 8 in the accompanying drawings of the description respectively perform exponential decay, iterative allocation and hybrid iterative power allocation. Under the conditions of three different schemes, the sparse superposition code uses different R and different sizes under the conditions of different signal-to-noise ratios. decoding error. It can be seen that the hybrid iterative power allocation scheme can help the sparse superposition code to achieve better decoding performance under the condition of low signal-to-noise ratio and under the condition of medium and high rate close to the channel capacity.

The hybrid iterative power allocation and the implementation process of the coding and decoding system proposed by the present invention have been introduced and described in detail above, which is helpful for understanding the core idea of the present invention. The present invention designs a hybrid iterative power distribution scheme based on the critical effect of power distribution on the decoding accuracy of the sparse superposition code. First, the minimum power required for decoding is allocated to each group, and then the remaining power is equally divided into each group, so that each group has sufficient power for decoding and resists noise interference. Experiments show that compared with exponential decay power allocation and iterative power allocation, the proposed scheme can obtain better reconstruction performance.

Claims (2)

1. a kind of sparse superimposed code design scheme based on mixed iteration power distribution, it is characterised in that: believe the real value of input Number one-hot coding is converted into each grouping only with the sparse vector of a nonzero value；Utilize the mentioned mixed iteration power of the present invention Allocation plan is to the nonzero value assignment in each grouping of sparse vector；According to the size of the grouping of message vector β, by random hada Ma design matrix A carries out the linear combination of corresponding grouping, formation can be on awgn channel to specifications in attached drawing shown in Fig. 2 The code word of transmission；By awgn channel, in addition mean value is 0, variance σ²White Gaussian noise, obtain output codons；Finally, through It crosses AMP decoder and is iterated estimation, the estimated value of message vector is obtained, and use hard-decision method, by each real value element Element corresponds to maximum position and is set as in corresponding vectorRemaining is set as 0 method, recovers original sparse vector.

2. scheme according to claim 1, which is characterized in that using a kind of such as power point shown in Fig. 3 in Figure of description It is the nonzero value assignment in the sparse each grouping of message vector β with scheme.It is characterized in that distributing first each grouping minimum It is required that power, then divides dump power in each grouping equally, specific assigning process includes the following steps:

(1) the L packeting average of message vector β is divided into B block, is then grouped containing L/B for every piece；

(2) distribute identical power to each grouping after piecemeal, based on formula it is as follows:

Then for L/B grouping in first piece, distribution powerL/B in second piece is grouped, Distribution powerWhereinContinue as in the same fashion each piece into Row power distribution is all assigned to minimum power until all pieces.

(3) remaining power P after distributing_remainDivide each grouping equally.

According to such power distribution mode, more excellent decoding performance can be obtained.