CN116633483A - A Regular Variable Node Degree Fountain Coding Method - Google Patents

Abstract

A regular variable node degree fountain coding method comprises the steps of firstly constructing a coding node symbol degree distribution function, accelerating a decoding process by improving the probability of occurrence of small degree value coding symbols, and generating a degree value according to the degree distribution function; then selecting an original information symbol to participate in the coding according to the information symbol selection probability, and splicing the degree information field and the coding information field to construct a transmission data packet; secondly, the probability of selecting the information nodes is updated by recording the participation coding times of all original information nodes; finally, the received data is decoded at the destination node by a belief propagation algorithm. The invention improves the probability of occurrence of the small-scale value coding symbol by optimizing the coding node degree distribution function, adopts the information node selection strategy of the coding participation times, realizes regularization of the symbol variable node degree value, selects the information node with small degree value during coding, achieves the purposes of reducing error code platform and saving decoding cost in the fountain coding process, and reduces coding complexity at the source node.

Description

A Regular Variable Node Degree Fountain Coding Method

technical field

The invention belongs to the technical field of wireless communication, and in particular relates to a regular variable node degree fountain coding method.

Background technique

Fountain code, as a coding method with no fixed bit rate, was originally used to solve the problems of large-scale data distribution, reliable multicast, and multicast in the binary erasure channel, and it can also deal with the transmission caused by the feedback retransmission mechanism under long transmission distances. The phenomenon of long waiting time at the terminal can effectively avoid the "feedback storm" in traditional linear block codes and ensure the reliability of data transmission. Therefore, fountain codes are also used in deep space communications, high-speed aircraft plasma sheath communications, and over-the-horizon communications Such as the harsh transmission environment that requires extremely high communication reliability. In the above-mentioned transmission environment, due to the long distance of the communication link, the electromagnetic signal is affected by the propagation loss of free space, and the transmission component of the useful signal at the receiver is relatively low. At the same time, considering factors such as external noise interference during the transmission process, the communication The quality deteriorated rapidly and the communication process was interrupted.

In order to ensure the reliability of communication, currently commonly used technical means include spread spectrum communication and diversity combining technology. In spread spectrum communication, after the original information is processed by the spread spectrum code word sequence, the frequency bandwidth occupied by the signal transmission is much larger than the minimum frequency bandwidth required by the information itself, and the anti-narrowband interference and anti-multipath are realized by obtaining the spread spectrum gain. However, spread spectrum itself cannot overcome the impact of noise, and it still cannot solve the problem of rapid deterioration of communication quality in an extremely low signal-to-noise ratio environment. Diversity reception technology refers to providing several signals carrying the same information sent on independent fading channels to the receiver, and the receiver combines the received independent signals that are not correlated with each other according to certain rules, so that the received useful signal energy The maximum, and then improve the signal-to-noise ratio of the received signal, so as to achieve the purpose of anti-fading, the diversity gain is directly related to the diversity order, but with the continuous expansion of the diversity order, there are multiple demodulation branches at the receiver, resulting in Hardware implementation complexity and cost increase.

In the traditional fountain coding process, robust soliton distribution is mostly used, and the original information nodes are randomly selected to participate in coding. Therefore, it is very likely that a certain information node has not participated in coding or has participated in coding for a small number of times. At the same time, considering the loss in the transmission process The package factor causes the information amount of the information symbol node at the receiving end to be 0, which affects the decoding process, resulting in the problems of high error platform and high decoding cost. At present, for this problem, the existing solution is to use the degree value lookup table to realize the regularization of the degree value of the information symbol at the encoding end, but it is necessary to traverse and sort the degree value lookup table every time encoding, and continuously The table is maintained. As the number K of original information nodes increases, the sorting process of the degree value lookup table becomes more complicated, and while reducing the bit error platform, the decoding waterfall area at the decoding end is delayed, and the decoding cost increases.

The existing patent, CN201910613926.0, deduces and analyzes the optimal degree distribution function that can realize the regularization of coded symbol node degree values, but does not consider the decoding speed slowdown caused by the regular variable node degree fountain coding itself, and the decoding Issues such as increased costs.

In the communication transmission process such as deep space communication and trans-horizon communication, due to the joint influence of many factors such as large-scale fading, small-scale fading, external noise, interference, etc., the communication quality deteriorates rapidly in the environment of extremely low signal-to-noise ratio , the communication process is interrupted.

Based on this, it is of great significance to consider how to optimize the existing fountain coding algorithm to improve the communication service rate performance in the harsh transmission environment with obvious fading characteristics and low useful signal power.

Contents of the invention

In order to overcome the deficiencies in the above-mentioned prior art, the object of the present invention is to provide a regular variable node degree fountain coding method, which takes into account the impact of the harsh transmission environment on communication performance, and improves the small The occurrence probability of degree-value coding symbols adopts the information node selection strategy based on the number of coding participation times to realize the regularization of symbol variable node degrees, and achieve the purpose of reducing the error platform and saving decoding overhead during the fountain coding process. On the premise of ensuring communication reliability Next, increase the service transmission rate.

In order to achieve the above object, the technical scheme adopted in the present invention is:

A regular variable node degree fountain coding method, comprising the following steps;

Step 1: Define the sender as the source node in the communication process, there are K original information symbols at the source node as information nodes waiting to be transmitted, randomly select a degree value d according to the symbol degree distribution function, that is, there are d original information symbols participate in encoding;

Step 2: The source node selects d original information symbols with the least number of encoding times according to the selection probability, and performs a modulo two addition operation to obtain encoded information symbols. The length of the degree information field is K bits, corresponding to K original information symbols. If this encoding In the process, if a certain original information symbol is selected to participate in encoding, the corresponding degree information bit is 1, otherwise it is 0, and the encoding information symbol and the degree information field are spliced to obtain the transmission data packet;

Step 3: Among the K original symbol nodes, record the original information symbol nodes that participated in the encoding process, and add one to the total number of codes selected for the symbol node, and calculate the original information used in the next fountain encoding. Information symbol node selection probability;

Step 4: Define the receiving end as the destination node in the communication process, obtain the generated matrix at the destination node according to the degree information field of the received data packet, and use the belief propagation algorithm to decode and restore the original information symbol. When the destination node successfully completes the decoding When , send feedback to the source node, and the source node terminates the encoding operation.

The step 1 is specifically:

The code node signed degree distribution function polynomial Ω(x) is defined as Among them, K represents the number of original information nodes, and is also the maximum degree value of encoding, Ω _d represents the probability of selecting degree value d, which is further expressed as Among them, the probability mass function ρ(d) and the correction function τ(d) respectively satisfy:

in c is a constant greater than 0, δ is the maximum decoding failure probability, /> Indicates rounding down, and β ₁ and β ₂ are correction factors, which are used to increase the occurrence probability of encoded data packets with degree values 1 and 2.

The step 2 is specifically:

Assuming that there are K original information symbols in the source node, expressed as S=[S ₁ , S ₂ , S ₃ ,, S _K ], among them, the original information symbol nodes with less coding times are selected with high probability, according to the probability from K Select d symbols from the original information symbols and perform modulo-two addition operation to obtain coded symbols. Assume that the degree information field at the i-th encoding time is expressed as a vector G _i , and its length is K, corresponding to K original information symbols respectively. If this encoding In the process, if a certain original information symbol participates in the encoding, the corresponding value in the degree information field vector G _i is 1, otherwise it is 0, and the encoding symbol and the degree information field are spliced to obtain the transmission data packet;

Through the original information node selection scheme based on the number of coding participation times, the regularization of variable symbol nodes is realized, and the specific implementation method of analyzing the performance of the current fountain coding by using the asymptotic analysis method is as follows;

Suppose the channel is a random packet loss channel, define the number of original information nodes as K, the total number of symbols sent by the code segment as N, the symbols lost during transmission as N _e , the number of symbols successfully received by the receiver as N _r , and the channel packet loss rate for The decoding overhead is γ=N _r /K.

When the packet loss rate ε is 0, the symbol degrees of all information nodes at the sending end are equal under the regular variable node degree fountain coding method, and the encoding symbols obtained by the receiving end are the same as those at the sending end; define the average degree of information symbol nodes at the receiving end as α, because The degree value is a positive integer, so the actual degree value of the information symbol is or /> Indicates rounding up, the information symbol node degree distribution is Λ(x)=Λ _h-1 x ^h-1 + Λ _h x ^h , where the parameter /> The coefficients Λ _h-1 and Λ _h respectively represent the probability of the receiving end information symbol degree value h, h-1, and satisfy:

Define the information symbol edge degree distribution function polynomial as λ(x)=λ _h-2 x ^h-2 +λ _h-1 x ^h-1 , the coefficients λ _h-2 and λ _h-1 satisfy:

Since the encoding node degree distribution function Ω(x) used in regular variable node degree fountain encoding is pre-defined, when the number of original information nodes K→∞, the asymptotic bit error rate y at the receiving end is expressed as where y _l is the bit error rate after l times of iterative decoding, which is further expressed as:

Wherein the encoding symbol edge degree distribution ω(x) can be calculated from the encoding node degree distribution function Ω(x), ω(x)=Ω′(x)/Ω′(1);

When the packet loss rate ε is not 0, take any information symbol as an example, use s to represent the information symbol, and the number of code symbols with the information symbol s as the neighbor node among N code symbols is h, and use H to represent h The set of encoding symbols, then h=card (H), card (A) represents the cardinality of set A, and the value range of receiving end information symbol degree value d is 0≤d≤h, and d is an integer; expressed by _Ne The set of lost coding symbols, let I==HN _e , when the set I is an empty set, the degree value of the information symbol s at the receiving end does not change; when I is not an empty set and there is card(I)=i, the receiving end The degree value of the information symbol s is reduced to di; use _ph (i) to represent the probability of card(I)=i appearing, which means the probability of losing i symbols in the coding symbol set H with s as the neighbor node. The number of all sets N _e satisfying card(I)=i is All the numbers of the set N _e are /> So p _h (i) is expressed as:

The probability of the coded symbol degree value at the receiving end is h is the probability that all coded symbols of the neighbor nodes are not lost when the information symbol with the coded end degree value is h, that is, p _h (0). At this time, the information symbol degree value at the receiving end The probability of being h is Λ _h p _h (0); similarly, the degree value of the information symbol at the receiving end is h-1, which contains two possible situations. One coded symbol is lost, and the second one is that all coded symbols of the neighboring nodes are not lost when the information symbol with coded terminal degree value is h-1, so the probability of receiving terminal information symbol with degree value h-1 can be obtained is Λ _h p _h (1)+Λ _{h- 1} p _h-1 (0); and so on, when the packet loss rate ε is not 0, the node degree distribution of information symbols at the receiving end is expressed as:

By the formula ω(x)=Ω′(x)/Ω′(1), λ(x)=Λ′(x)/Λ′(1), the degree distribution of coding symbols and information symbols is obtained, so that the rule The bit error rate _y l of variable node degree fountain coding after l iteration decoding is expressed as:

In the traditional fountain encoding process, the original information nodes participating in the encoding are randomly selected. When the number of original information nodes K→∞, the degree distribution of information symbol nodes is Poisson distribution, that is, Λ(x)=exp(α(x-1)), Where α represents the average degree of information symbol nodes, and the Taylor series expansion is performed on the degree distribution polynomial of information symbol nodes to obtain:

Λ(x)=exp(α(x-1))

＝exp(-α)+αexp(-α)x+α ² exp(-α)x ² +...

Among them, the constant term exp(-α) represents the probability that the information symbol does not participate in the encoding when the average degree of the information symbol node is α, that is, the probability that the receiving end cannot decode the information symbol, so the error platform of the traditional fountain coding is exp(- a);

For regular variable node degree fountain coding, when the channel packet loss rate ε = 0, all information symbols participate in the coding process, which can effectively reduce the error platform. When ε ≠ 0, when a certain information symbol is the neighbor node When all the coded symbols are lost, there is also a constant term in the node degree distribution of the information symbols at the receiving end. At this time, the probability that the information symbol degree at the receiving end is equal to 0 is Λ ₀ = Λ _h-1 p _h-1 (h-1) + Λ _h p _h (h), the bit error platform under the regular variable node degree fountain coding is related to the average degree of coding symbols and the channel packet loss rate, when Λ ₀ < exp(-α), the bit error platform of the regular variable node degree fountain coding is lower than Traditional fountain coding.

The step 3 is specifically:

Step 3.1: Define P(k) as the selection probability of the kth information node, where k=1, 2, K, and all original information nodes are selected with the same probability P(k) in the encoding initialization stage, which is set to 1/K , where K represents the number of original information nodes, and for each original information node, set the encoding times s _k to 1;

Step 3.2: Every time the fountain coding is completed, record the original information nodes participating in the coding, and add 1 to the corresponding coding times _sk ;

Step 3.3: After updating the coding times of all information nodes, recalculate the selection probability P(k) of each information node, where

Step 3.4. If the source node receives the decoding success feedback information sent by the destination node, return to step 3.1 to complete the initialization operation; otherwise, return to step 3.2.

The step 4 is specifically:

Step 4.1: Assume that the degree information field in the i-th received data packet obtained at the destination node is G _i , then the generation matrix can be expressed as G=[G ₁ ,G ₂ ,…,G _i ,…], and the corresponding Bipartite graph and start the decoding process;

Step 4.2: Select an encoding symbol with a degree value of 1 from the bipartite graph, and directly restore the original information symbol uniquely connected to it, and delete the connection between the original information symbol and the encoding symbol in the bipartite graph;

Step 4.3: Find the encoding symbols connected to the original symbols through the generation matrix, XOR the values of these encoding symbols with the original symbol values, and delete the corresponding connection lines in the bipartite graph;

Step 4.4: Repeat steps 4.2 and 4.3 until all original symbols are restored and the decoding is completed or there is no coded symbol with a degree value of 1 and the decoding is stopped.

Beneficial effects of the present invention:

In the transmission process that requires high reliability such as deep space communication, high-speed aircraft plasma sheath communication, and over-the-horizon communication, the effective distance of the communication link reaches thousands of kilometers, and the actual electromagnetic signal is simultaneously affected by large The impact of scale fading and small-scale fading leads to a large reduction in the number of encoded data packets successfully received at the destination node during the communication process, so that a huge decoding overhead is required to complete the decoding operation, which greatly reduces the effective communication rate. Therefore, it needs to be considered in the extremely low Ensure the communication quality in the signal-to-noise ratio transmission environment, seek coding performance gain, and realize reliable communication;

The present invention applies fountain coding to solve the problem of rapid deterioration of communication quality in harsh transmission environments, optimizes the node degree distribution function of coding symbols, and at the same time updates the selection probability of information nodes based on the number of times information nodes participate in coding to realize the regularization of node variables. In the packet channel environment, compared with the existing fountain coding algorithm, the performance improvement of bit error rate and decoding cost is achieved.

Description of drawings

FIG. 1 is a flow chart of a method for encoding a regular variable node degree fountain according to an embodiment of the present invention.

Fig. 2 is a schematic diagram of the comparison of decoding cost performance effect of the algorithm in the verification embodiment of the present invention and the traditional Fountain LT coding algorithm under different channel transmission error probabilities.

FIG. 3 is a schematic diagram of comparing the bit error rate performance effect of the algorithm in the verification embodiment of the present invention and other algorithms when the channel transmission error probability is 0.5.

Fig. 4 is a system processing flowchart of a regular variable node degree fountain coding method according to an embodiment of the present invention.

Detailed ways

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

In an embodiment of the present invention, a regular variable node degree fountain coding method is shown in the flow chart in Figure 1, which is specifically implemented according to the following steps:

Step 1 is as follows:

The code node signed degree distribution function polynomial Ω(x) is defined as Among them, K represents the number of original information nodes, and it is also the maximum degree value of encoding, and Ω _d represents the probability of selecting degree value d, which can be further expressed as Among them, ρ(d) and τ(d) respectively satisfy:

in c is a constant greater than 0, δ is the maximum decoding failure probability, /> Indicates rounding down, and β ₁ and β ₂ are correction factors, which are used to increase the occurrence probability of encoded data packets with degree values 1 and 2.

Step 2 is as follows:

Through the original information node selection scheme based on the number of encoding participation times, the degree value regularization of variable symbol nodes is realized. In the traditional LT encoding process, the original information nodes are randomly selected, and all original data packets participate in the encoding process with the same probability. At the same time, combined with the packet loss factor in the transmission process, it may cause some original information nodes to participate in encoding less or not. The phenomenon that the receiving end has not been able to obtain the effective information of these information nodes, and cannot complete the decoding, the bit error rate of the system is maintained on an error platform and it is difficult to reduce.

In order to improve the error platform phenomenon, so that all original information nodes can participate in the encoding process, the degree of information nodes is counted at the encoding end. When a certain information node is used to encode and transmit more times than other information nodes, it can be It is considered that the receiving end has obtained the amount of information of this node. If the node continues to be used for encoding, it will not only increase the complexity of the decoding process, but also have no gain for successful decoding. Therefore, in the subsequent encoding process, the priority of this information node will become lower. , the probability of selecting this node for encoding decreases. Similarly, if a certain original information node has not participated in coding or has participated in coding for a very small number of times, it will be difficult for the receiving end to obtain useful information of the node, which will lead to the emergence of error platforms. Therefore, such nodes should be preferred in the subsequent coding process. information node. The specific implementation of analyzing the performance of regular variable node degree fountain coding by using asymptotic analysis method is as follows.

Suppose the channel is a random packet loss channel, define the number of original information nodes as K, the total number of symbols sent by the code segment as N, the symbols lost during transmission as N _e , the number of symbols successfully received by the receiver as N _r , and the channel packet loss rate for The decoding overhead is γ=N _r /K.

When the packet loss rate ε is 0, the symbol degrees of all information nodes at the sending end are equal under the regular variable node degree fountain encoding method, and the encoding symbols obtained at the receiving end are the same as those at the sending end. Define the average degree of the information symbol node at the receiving end as α, since the degree value is a positive integer, the actual degree of the information symbol is or /> Indicates rounding up, the information symbol node degree distribution is Λ(x)=Λ _h-1 x ^h-1 + Λ _h x ^h , where the parameter /> The coefficients Λ _h-1 and Λ _h respectively represent the probability of the receiving end information symbol degree value h, h-1, and satisfy:

Define the information symbol edge degree distribution function polynomial as λ(x)=λ _h-2 x ^h-2 +λ _h-1 x ^h-1 , the coefficients λ _h-2 and λ _h-1 satisfy:

Since the encoding node degree distribution function Ω(x) used in regular variable node degree fountain encoding is pre-defined, when the number of original information nodes K→∞, the asymptotic bit error rate y at the receiving end can be expressed as where y _l is the bit error rate after l times of iterative decoding, which can be further expressed as:

Wherein, the edge degree distribution ω(x) of coded symbols can be calculated from coded node degree distribution function Ω(x), ω(x)=Ω′(x)/Ω′(1).

When the packet loss rate ε is not 0, take any information symbol as an example, use s to represent the information symbol, and the number of code symbols with the information symbol s as the neighbor node among N code symbols is h, and use H to represent h A set of encoding symbols, then h=card(H), card(A) represents the cardinality of the set A, and the value range of the information symbol degree value d at the receiving end is 0≤d≤h, and d is an integer. Denote the set of missing encoding symbols by _Ne , let When the set I is an empty set, the degree value of the information symbol s at the receiving end does not change; when I is not an empty set and there is card(I)=i, the degree value of the information symbol s at the receiving end is reduced to di. Use _ph (i) to represent the probability that card(I)=i appears, and represent the probability that i symbols are lost in the coded symbol set H with s as the neighbor node. The number of all sets N _e satisfying card(I)=i is /> All the numbers of the set N _e are /> So p _h (i) can be expressed as: />

The probability of the coded symbol degree value at the receiving end is h is the probability that all coded symbols of the neighbor nodes are not lost when the information symbol with the coded end degree value is h, that is, p _h (0). At this time, the information symbol degree value at the receiving end The probability of being h is Λ _h p _h (0); similarly, the degree value of the information symbol at the receiving end is h-1, which contains two possible situations. One coded symbol is lost, and the second one is that all coded symbols of the neighboring nodes are not lost when the information symbol with coded terminal degree value is h-1, so the probability of receiving terminal information symbol with degree value h-1 can be obtained It is Λ _h p _h (1)+Λ _{h- 1} p _h-1 (0). By analogy, when the packet loss rate ε is not 0, the node degree distribution of information symbols at the receiving end can be expressed as:

By the formula ω(x)=Ω′(x)/Ω′(1), λ(x)=Λ′(x)/Λ′(1), we can get the edge degree distribution of coding symbols and information symbols, so that The bit error rate y _l of regular variable node degree fountain coding after l iteration decoding can be expressed as:

In the traditional fountain encoding process, the original information nodes participating in the encoding are randomly selected. When the number of original information nodes K→∞, the degree distribution of information symbol nodes is Poisson distribution, that is, Λ(x)=exp(α(x-1)), Where α represents the average degree of information symbol nodes, and the Taylor series expansion of the degree distribution polynomial of information symbol nodes can be obtained:

Λ(x)=exp(α(x-1))

＝exp(-α)+αexp(-α)x+α ² exp(-α)x ² +...

Among them, the constant term exp(-α) represents the probability that the information symbol does not participate in the encoding when the average degree of the information symbol node is α, that is, the probability that the receiving end cannot decode the information symbol, so the error platform of the traditional fountain coding is exp(- a).

For regular variable node degree fountain coding, when the channel packet loss rate ε = 0, all information symbols participate in the coding process, which can effectively reduce the error platform. When ε ≠ 0, when a certain information symbol is the neighbor node When all the coded symbols are lost, there is also a constant term in the node degree distribution of the information symbols at the receiving end. At this time, the probability that the information symbol degree at the receiving end is equal to 0 is Λ ₀ = Λ _h-1 p _h-1 (h-1) + Λ _h p _h (h). The error platform under the regular variable node degree fountain coding is related to the average degree of coding symbols and the channel packet loss rate. When Λ ₀ <exp(-α), the error platform of the regular variable node degree fountain coding is lower than the traditional fountain coding.

Step 3 is as follows:

Step 3.1. Define P(k) as the selection probability of the kth information node, where k=1, 2, K. In the coding initialization stage, all original information nodes are selected with the same probability P(k), which is set to 1/K , where K represents the number of original information nodes, and for each original information node, set the encoding times s _k to 1;

Step 3.2, each time the fountain coding is completed, record the original information nodes participating in the coding, and add 1 to the corresponding coding times _sk ;

Step 3.3. After updating the coding times of all information nodes, recalculate the selection probability P(k) of each information node, where

Step 3.4. If the source node receives the decoding success feedback information sent by the destination node, return to step 3.1 to complete the initialization operation; otherwise, return to step 3.2.

In each encoding process, the two processes of generating encoded data packets and updating the selection probability of original information nodes are processed in parallel, that is, the record update of the number of encoding times and the calculation update of the selection probability will not affect the normal encoding process, ensuring the high efficiency of source node encoding conduct.

Step 4 is as follows:

Step 4.1, the destination node reconstructs the generation matrix according to the degree information field in the received data packet, obtains the corresponding bipartite graph and starts the decoding process;

Step 4.2, select a coding symbol with a degree value of 1 from the bipartite graph, directly restore the original information symbol uniquely connected to it, and delete the corresponding edge at the same time;

Step 4.3, find the encoding symbols connected to the original symbols through the generation matrix, XOR the values of these encoding symbols with the original symbol values, and delete the corresponding connected edges in the bipartite graph;

Step 4.4, repeating steps 4.2 and 4.3, until all original symbols are restored and decoding is completed or there is no coded symbol with a degree value of 1 and this decoding is stopped.

The method of the embodiment of the present invention is verified, assuming that the number of original information symbol nodes is 128, the symbol length of each information node is 3520 bits, and the packet loss rate in the deletion channel is set to be 0.3 to 0.8 respectively, and different channel transmission environments are simulated.

As shown in Fig. 2, the comparison method adopted by the present invention is: (1) traditional fountain LT encoding algorithm: the node degree distribution function of the encoding symbol selects the robust soliton distribution, and randomly selects the original information node during each encoding. (2) The regular variable node degree fountain encoding algorithm proposed in the present invention: the node degree distribution of encoding symbols uses an optimized degree distribution function to increase the probability of occurrence of encoding symbols with small degree values, and at the same time adopts the original information node selection strategy based on the number of encoding times to calculate The probability is selected, and information nodes with small degree values are selected to participate in encoding in each encoding process.

As shown in Figure 2, under different channel transmission error probabilities, compared with the traditional Fountain LT coding, the algorithm proposed by the present invention can obtain decoding cost performance gain, and with the increase of transmission error probability, the transmission environment quality The performance gain of the proposed algorithm becomes more and more obvious. The algorithm proposed by the invention effectively reduces the times of encoding transmission and improves the actual service transmission rate while obtaining decoding cost performance gain.

As shown in Figure 3, the channel transmission error probability is fixed at 0.5. Under the above comparison method, the existing Regularized variable-node Luby Transform (RLT) algorithm is included in the performance comparison. The degree distribution function of stick solitons, and the way of degree value lookup table is used to realize the regularization of the degree value of code segment information symbols. In each encoding, the degree value lookup table needs to be traversed and sorted, and the information node with the minimum degree value is selected to participate in the encoding. The table needs to be maintained during the encoding process. As the number K of original information nodes increases, the sorting process of the degree value lookup table becomes more complicated.

As shown in Figure 3, the RLT coding algorithm adopts the regular variable node degree coding method to increase the coverage of information nodes in the coding process. Compared with the traditional fountain LT coding, the bit error rate can be reduced at the same decoding cost. However, while the RLT encoding algorithm realizes the regularization of the degree value of information nodes, the "waterfall area" in the decoding process is delayed, resulting in a slow decoding process. The algorithm proposed by the present invention adopts the optimized code symbol node degree distribution function, which effectively increases the probability of small degree values in code symbols, code symbols with a degree value of 1 can be directly decoded at the destination node, and code symbols with a degree value of 2 can only be decoded. Decoding can be achieved with one dismantling operation, thereby speeding up decoding. At the same time, in each encoding process, the original signal node with a smaller degree value is selected according to the selection probability to realize the regularization of the variable node degree value. Compared with the RLT coding algorithm, the reduction process of the bit error rate is more rapid and obvious, which reflects that the algorithm of the present invention has good performance in the packet loss channel environment.

The system processing flow chart of a regular variable node degree fountain coding method according to an embodiment of the present invention, as shown in Figure 4, the destination node completes the regular variable node degree fountain coding through the algorithm proposed by the present invention, and after completing the outer layer erasure correction coding, sends to Add cyclic redundancy check bits to the coded data, and then continue to add redundant information to the inner turbo code to improve error correction performance, complete the matching mapping between business resources and actual system physical resources through rate matching, and then pass the interleaving operation A series of burst errors appearing in the system are converted into random errors, and finally the signal is transmitted through symbol modulation. The sent data reaches the destination node after passing through the wireless channel. The destination node obtains the encoded data through a series of inverse operations such as demodulation, de-interleaving, de-rate matching, and Turbo decoding. The cyclic redundancy check is used to determine whether the data packet is correct and verify the correct data. The packet continues to perform subsequent decoding operations, and the verification error data packet is directly discarded without processing.

Claims (6)

1. A regular variable node degree fountain coding method is characterized by comprising the following steps of;

step 1: defining a transmitting end as a source node in the communication process, wherein K original information symbols exist at the source node as information nodes to wait for transmission, and randomly selecting a degree value d according to a symbol degree distribution function, namely, d original information symbols participate in the coding process;

step 2: the source node selects d original information symbols with least participation in coding times according to the selection probability, carries out modulo double addition operation to obtain coded information symbols, the length of a degree information field is K bits, the corresponding K original information symbols are 1 if a certain original information symbol is selected to participate in coding in the coding process, otherwise, the corresponding degree information bit is 0, and the coded information symbols and the degree information field are spliced to obtain a transmission data packet;

step 3: recording the original information symbol nodes participating in the coding process of the K original symbol nodes, adding one operation to the total number of times of selecting the codes of the symbol nodes, and calculating the selection probability of the original information symbol nodes used for the next fountain coding;

step 4: and defining a receiving end as a destination node in the communication process, obtaining a generating matrix at the destination node according to the degree information field of the received data packet, decoding by using a belief propagation algorithm, recovering an original information symbol, and sending feedback to a source node when the destination node successfully completes decoding, and terminating the encoding operation at the source node.

2. The regular variable node degree fountain coding method according to claim 1, wherein the step 1 is specifically:

the code node symbol degree distribution function polynomial Ω (x) is defined asWherein K represents the number of nodes of the original information and is also the maximum value of the code, Ω _d The probability of the selection value d is further expressed asWherein the probability mass function ρ (d) and the correction function τ (d) respectively satisfy:

wherein the method comprises the steps ofc is a constant greater than 0, delta is the maximum decoding failure probability, ++>Representing a rounding down, beta ₁ 、β ₂ The correction factor is used for improving the occurrence probability of the coded data packet with the degree value of 1 and 2.

3. The regular variable node degree fountain coding method according to claim 1, wherein the step 2 is specifically:

assume that there are K original information symbols at the source node, denoted s= [ S ] ₁ ,S ₂ ,S ₃ ,…,S _K ]Wherein the original information symbol node with less participation in coding is selected with large probability, d symbols are selected from K original information symbols according to probability for modulo double addition operation to obtain coding symbol, and the ith coding time information field is assumed to be represented as vector G _i The length is K, and the K original information symbols respectively correspond toIf some original information symbol participates in the encoding process, a degree information field vector G _i If the corresponding value in the code symbol is 1, otherwise, the code symbol is 0, and the code symbol and the degree information field are spliced to obtain a transmission data packet;

the regularization of variable symbol nodes is realized through an original information node selection scheme based on coding participation times, and the specific implementation mode of analyzing the performance of the current fountain coding by using a progressive analysis method is as follows;

setting the channel as a random packet loss channel, defining the number of nodes of original information as K, setting the total number of transmitted symbols of a coding section as N, and setting the lost symbols in the transmission process as N _e The number of symbols successfully received by the receiving end is N _r The packet loss rate of the channel is as followsThe coding overhead is gamma=n _r /K。

4. The regular variable node degree fountain coding method according to claim 3, wherein when the packet loss rate epsilon is 0, the symbol degrees of all information nodes of a transmitting end are equal in the regular variable node degree fountain coding mode, and the coding symbols obtained by a receiving end are the same as the transmitting end; defining the average degree of the information symbol nodes of the receiving end as alpha, and the actual degree value of the information symbol is as positive integerOr->Representing an upward rounding, the information symbol node degree distribution is Λ (x) =Λ _h-1 x ^h-1 +Λ _h x ^h Wherein parameter->Coefficient lambda _h-1 Sum lambda _h The probability of the receiving end information symbol degree value h and h-1 is respectively represented, and the following conditions are satisfied:

defining information symbol edge distribution function polynomial as lambda (x) =lambda _h-2 x ^h-2 +λ _h-1 x ^h-1 Coefficient lambda _h-2 And lambda (lambda) _h-1 The method meets the following conditions:

as the coding node degree distribution function omega (x) used in the regular variable node degree fountain coding is predefined, when the number K & gtto & gtinfinity of the original information nodes is calculated, the progressive error rate y at the receiving end is expressed asWherein y is _l The error rate after l times of iterative decoding is further expressed as:

wherein the encoded symbol edge degree distribution ω (x) can be calculated from the encoded node edge degree distribution function Ω (x), ω (x) =Ω '(x)/Ω' (1);

when the packet loss rate epsilon is not 0, taking any information symbol as an example, s is used for representing the information symbol, the number of the coding symbols taking the information symbol s as a neighbor node in N coding symbols is H, H is used for representing a set of H coding symbols, h=card (H), card (A) represents the base number of the set A, the value range of the receiving end information symbol degree value d is 0-d-H, and d is an integer; by N _e Representing a missing set of encoded symbols, letWhen the set I is an empty set, the degree value of the information symbol s of the receiving end is not changedA change; when I is not an empty set and there is a card (I) =i, the degree value of the receiving-end information symbol s is reduced to d-I; by p _h (i) The probability of occurrence of card (I) =i is represented as the probability of losing I symbols in the coded symbol set H having s as the neighbor node. All sets N satisfying card (I) =i _e The number of (2) is->Set N _e All numbers are->Thus p is _h (i) Expressed as: />

The probability of the code symbol degree value h of the receiving end is the probability that all code symbols taking the information symbol with the code terminal degree value h as neighbor nodes are not lost, namely p _h (0) At this time, the probability of the receiving end information symbol degree value h is Λ _h p _h (0) The method comprises the steps of carrying out a first treatment on the surface of the The same method comprises two possible cases that the information symbol degree value of the receiving end is h-1, wherein the first is that all coding symbols taking the information symbol with the coding end degree value of h as a neighbor node lose 1, and the second is that all coding symbols taking the information symbol with the coding end degree value of h-1 as the neighbor node do not lose, so that the probability that the information symbol degree value of the receiving end is h-1 is Λ _h p _h (1)+Λ _h-1 p _h-1 (0) The method comprises the steps of carrying out a first treatment on the surface of the Similarly, when the packet loss rate epsilon is not 0, the node degree distribution of the information symbol of the receiving end is expressed as follows:

the edge degree distribution of the coding symbol and the information symbol is obtained through formulas omega (x) =omega '(x)/omega' (1) and lambda (x) =lambda '(x)/lambda' (1), so that the error rate y of the regular variable node degree fountain coding after l times of iterative decoding is obtained at the moment _l Expressed as:

in the conventional fountain coding process, original information nodes participating in coding are randomly selected, when the number of the original information nodes is K & gtto & gtinfinity, the information symbol node degree distribution is poisson distribution, namely Λ (x) =exp (alpha (x-1)), wherein alpha represents the average degree of the information symbol nodes, and Taylor series expansion is carried out on an information symbol node degree distribution polynomial, so that the information symbol node degree distribution polynomial is obtained:

Λ(x)＝exp(α(x-1))

＝exp(-α)+αexp(-α)x+α ² exp(-α)x ² +…

when the average degree of the nodes of the information symbol is alpha, the constant term exp (-alpha) represents the probability that the information symbol does not participate in encoding, namely the probability that the receiving end cannot decode the information symbol, so that the error code platform of the traditional fountain coding is exp (-alpha);

for regular variable node degree fountain coding, when the channel packet loss rate epsilon=0, all information symbols participate in the coding process, so that an error code platform can be effectively reduced, when epsilon is not equal to 0, when the coding symbols taking a certain information symbol as a neighbor node are all lost, constant items exist in the node degree distribution of the information symbol of a receiving end, and at the moment, the probability that the information symbol degree of the receiving end is equal to 0 is lambda ₀ ＝Λ _h-1 p _h-1 (h-1)+Λ _h p _h (h) Error code platform under regular variable node degree fountain coding is related to coding symbol average degree and channel packet loss rate, and when Λ ₀ And when the value is less than exp (-alpha), the code error platform of the regular variable node degree fountain code is lower than the traditional fountain code.

5. The regular variable node degree fountain coding method according to claim 1, wherein the step 3 is specifically:

step 3.1: defining P (K) as the probability of selecting the kth information node, wherein k=1, 2, … K, and the probability of selecting all original information nodes P (K) is the same in the encoding initialization stage, and is set to 1/K, wherein K represents the original information nodeNumber of initial information nodes, for each original information node, number of codes s is set _k Are all 1;

step 3.2: every time fountain coding is completed, the original information nodes participating in coding are recorded, and the corresponding coding times s are recorded _k Adding 1;

step 3.3: after the number of times of coding of all the information nodes is updated, recalculating the selection probability P (k) of each information node, wherein

Step 3.4, if the source node receives the decoding success feedback information sent by the destination node, returning to the step 3.1, and finishing the initialization operation; otherwise, returning to the step 3.2.

6. The regular variable node degree fountain coding method according to claim 1, wherein the step 4 is specifically:

step 4.1: assume that the degree information field in the ith received packet obtained at the destination node is G _i The generator matrix may be expressed as g= [ G ] ₁ ,G ₂ ,…,G _i ,…]Obtaining a corresponding bipartite graph and starting a decoding process;

step 4.2: selecting a coding symbol with a degree value of 1 from the bipartite graph, directly recovering an original information symbol uniquely connected with the coding symbol, and deleting a connecting line between the original information symbol and the coding symbol in the bipartite graph;

step 4.3: searching coding symbols connected with the original symbols through the generating matrix, performing exclusive OR on the values of the coding symbols and the original symbol values, and deleting corresponding connecting lines in the bipartite graph;

step 4.4: and repeating the steps 4.2 and 4.3 until all original symbols are restored to finish decoding or the coded symbol with the absence degree value of 1 is stopped.