CN113794478B - LDPC (Low Density parity check) step decoding method and system based on noise power - Google Patents
LDPC (Low Density parity check) step decoding method and system based on noise power Download PDFInfo
- Publication number
- CN113794478B CN113794478B CN202111037601.6A CN202111037601A CN113794478B CN 113794478 B CN113794478 B CN 113794478B CN 202111037601 A CN202111037601 A CN 202111037601A CN 113794478 B CN113794478 B CN 113794478B
- Authority
- CN
- China
- Prior art keywords
- node
- check
- value
- iteration
- noise power
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 27
- 230000005540 biological transmission Effects 0.000 claims abstract description 14
- 238000004364 calculation method Methods 0.000 claims abstract description 13
- 238000004422 calculation algorithm Methods 0.000 claims description 13
- 239000011159 matrix material Substances 0.000 claims description 12
- 238000004088 simulation Methods 0.000 claims description 3
- 230000009286 beneficial effect Effects 0.000 abstract 1
- 238000007689 inspection Methods 0.000 description 6
- 238000010586 diagram Methods 0.000 description 3
- 238000005457 optimization Methods 0.000 description 3
- 230000002159 abnormal effect Effects 0.000 description 2
- 238000005516 engineering process Methods 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
- H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
- H03M13/1105—Decoding
- H03M13/1111—Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms
- H03M13/1125—Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms using different domains for check node and bit node processing, wherein the different domains include probabilities, likelihood ratios, likelihood differences, log-likelihood ratios or log-likelihood difference pairs
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L1/00—Arrangements for detecting or preventing errors in the information received
- H04L1/004—Arrangements for detecting or preventing errors in the information received by using forward error control
- H04L1/0056—Systems characterized by the type of code used
- H04L1/0061—Error detection codes
- H04L1/0063—Single parity check
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Physics & Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Theoretical Computer Science (AREA)
- Error Detection And Correction (AREA)
Abstract
The invention provides an LDPC (low density parity check) step decoding method and system based on noise power, and belongs to the technical field of LDPC decoding. The method comprises the following steps of initializing parameters, judging whether iteration times are reached or not, ending if not, executing step four, sequentially carrying out message transmission on each check node, updating the probability value of node information after each check node is updated, storing each check node value, and carrying out bit judgment on the probability value of node information after all check nodes are updated, wherein the iteration is ended. The invention also provides a system for realizing the LDPC step-by-step decoding method based on the noise power. The method has the beneficial effects that the calculation complexity is greatly reduced.
Description
Technical Field
The invention relates to an LDPC decoding technology, in particular to an LDPC step-by-step decoding method and system based on noise power.
Background
The IEEE802.11 standard has two schemes in bit coding, one is BCC coding, and the other is LDPC coding, where the LDPC coding is applicable in a wider scenario, so the capability of LDPC decoding at the receiving end plays a relatively important role in the performance of the WLAN system. The LDPC code is a linear block code, the information bit (bit) is obtained from a specific constraint matrix, and the information bit, the check bit and the known check matrix are received at the receiving end to correct the error bit in transmission.
Among them, the check matrix of the LDPC and this encoding process thereof can be defined as a bipartite graph, called a factor graph. The factor graph has two classes of nodes-symbol nodes and check nodes, representing the transmission bits and parity check constraints, respectively. Each check node (CHeck node) is connected to a symbol node (Bit node) by a plurality of solid lines (edges), as shown in fig. 1.
The left information bits are connected to the same check node through edge to obtain check bits.
And the LDPC receiving end is used for decoding a message by using a message transfer algorithm mainly adopted, and the shown factor graph is used for message transfer, so that posterior probability distribution of the last variable node is obtained through multiple iterations. The message here refers to a probability distribution, i.e. the ratio of the probability of the received information bit 0to 1 is logarithmic:
Wherein y is the complex symbol after equalization, s is the standard constellation point closest to y, b i,s is the ith bit in the constellation point, and after deduction, the LLR value is calculated as:
Where σ 2 denotes the noise power, Is the minimum Euclidean distance between the complex symbol y and the constellation point with the ith bit of 0 in the standard constellation points, and the same is trueIs the minimum euclidean distance for bit to be 1.
In the process of message transmission, the formula for transmitting the message from the symbol node to the check node is as follows:
Where Q vc represents the message that symbol node v passes to check node c, P v is the prior probability of v, i.e., LLR value, and R c′v checks the message that node c passes to symbol node v, where c' e N (v) \c represents that check node c does not include the message that v passes to check node c when it passes to symbol node v.
The formula for transferring a message from a check node to a variable node is:
Where R cv represents the message passed by check node c to check node v, Q v′c represents the message passed by check node v to check node c, v' εN (c) \v represents that the message passed by check node v to check node c does not contain the message passed by c to check node v.
The computation of the check node can be simplified as:
Wherein the method comprises the steps of
Wherein the sign function is-1 when x <0, otherwise 1.
The algorithm flow is as follows:
(1) Initializing parameters, Q vc←Pv
(2) For all of the check nodes,
(3) For all of the variable nodes that are to be considered,
(4) Repeating the iteration for N times to obtain the posterior probability of the variable node
(5) Bit decision, outputting bit value as
From the existing LDPC decoding algorithm and related algorithm, firstly, the algorithm complexity is relatively high, the time consumption is relatively long, the algorithm is mainly reflected in the message transmission process, secondly, the LLR calculation does not well fit the characteristic of LDPC block linear codes, the original noise power sigma 2 is an estimated average value, when some symbols are abnormal, the abnormal LLR value is not highlighted under the average power sigma 2, and therefore the probability of correcting errors by bits with constraint relation with the LLR value cannot be enhanced.
Disclosure of Invention
The invention provides an LDPC step-by-step decoding method based on noise power and a system for realizing the LDPC step-by-step decoding method based on noise power, which aims to solve the technical problems that in the prior art, algorithm complexity is large and probability of bit correction errors cannot be enhanced.
The LDPC step decoding method based on noise power comprises the following steps:
initializing parameters, wherein the parameters comprise probability values of node information and check node values;
Step two, starting iteration;
judging whether the iteration times are reached, if so, ending, and if not, executing the fourth step;
step four, sequentially carrying out message transmission on each check node, updating the probability value of the node information after each check node is updated, and storing the value of each check node;
and fifthly, after all the check nodes are updated, carrying out bit judgment on the probability value of the node message, and ending the iteration.
The invention further improves, and also comprises a step six of adopting an inspection matrix H to carry out bit inspection after bit judgment, ending if the inspection result is a set value, otherwise carrying out the next iteration.
The invention further improves, in the fifth step, after one iteration is completed, sign judgment is carried out on the node information probability valueP v' is the probability value of the information node v after each check node update.
In the sixth step, the invention adopts the checking matrix H to check, if Hx=0, the iteration is ended, otherwise, the next iteration is carried out until the set maximum iteration times are reached.
The invention is further improved, in the first step, LLR value P v is assigned to P v′,Pv as the prior probability value of the check node, P v' is the probability value of the information node v updated by each check node, and the check node value is initialized Representing the ith iteration, the jth check node passes the message to the information node.
The invention further improves, the prior probability value P v of the check node is calculated based on the noise power sigma 2 value of each symbol, the noise power sigma 2 value is the noise power rough estimation value of each symbol, the calculation method is sigma 2＝|yi-si|2+|yq-sq|2, y i、yq is the real imaginary part of the symbol y after equalization, and s i、sq is the real imaginary part of the standard constellation point nearest to y.
The invention is further improved by setting the lowest threshold value sigma 0 2 of the noise power according to the simulation data.
In the fourth step, the calculation formula of the updated value of each check node is as follows: Wherein v' ∈n (c) \v denotes that the message transmitted from the symbol node v to the check node c does not contain the message transmitted from c to the symbol node v, and the calculation formula of the updated node information probability value is as follows:
The invention also provides a system for realizing the LDPC step-by-step decoding method based on the noise power, which comprises the following steps:
the initialization module is used for initializing parameters, wherein the parameters comprise probability values of node information and check node values;
The iteration starting module is used for starting iteration;
The judging module is used for judging whether the iteration times are reached, if yes, ending, and if not, executing iteration;
The iteration module is used for sequentially carrying out message transmission on each check node, updating the probability value of the node information after each check node is updated, and storing the value of each check node;
And the bit judging module is used for carrying out bit judgment on the probability value of the node message after all the check nodes are updated.
The invention is further improved for performing a bit check on the decision value after the bit decision using the check matrix H.
Compared with the prior art, the LDPC decoding method has the advantages of reducing the complexity of LDPC decoding, accelerating the convergence rate of decoding and improving the decoding capability.
Drawings
FIG. 1 is a schematic diagram of a prior art LDPC factor graph;
FIG. 2 is a flow chart of the method of the present invention;
FIG. 3 is a schematic diagram of a first iteration of the present invention;
Fig. 4 is a schematic diagram of a second iteration of the present invention.
Detailed Description
The invention will be described in further detail with reference to the drawings and examples.
The invention aims at the noise power sigma 2 value of LLR, calculates the rough noise power estimated value of each symbol independently, sigma 2＝|yi-si|2+|yq-sq|2,yi、yq is the real imaginary part of the symbol after equalization, s i、sq is the real imaginary part of the standard constellation point nearest to y, and meanwhile sets the lowest threshold value sigma 0 2 of the noise power according to the simulation data.
As shown in fig. 2, the present invention optimizes the existing LDPC decoding flow. The LDPC step decoding method based on noise power comprises the following steps:
Initializing parameters, assigning LLR value P v to P v′,Pv' as probability value of information node v updated by each check node, initializing check node value Representing the ith iteration, the jth check node passes the message to the information node. Then, message transmission is carried out on each check node in turn, after each check node is updated, the probability value P v' of the information node is updated, andThe value is saved to participate in the calculation when the next iteration is performed. After updating all the inspection nodes, carrying out sign function judgment on P v ', carrying out bit inspection on the P v' and the inspection matrix H, ending if Hx=0, and otherwise, carrying out the next iteration.
The specific algorithm of the invention is as follows:
(1) The initialization parameters, P v′←Pv,
(2) Messaging, updating, and updating each checkAt the time of the first iteration of the process,The upper right mark indicates the first iteration, the first check node, and then the update information probabilityThen preserveThe value is used for the next iteration;
(3) After one iteration is completed, sign judgment is carried out on the information probability value And checking with the checking matrix H, if Hx=0, ending iteration, otherwise, performing the next iteration until the set maximum iteration number is reached.
The data updated and saved in the first iteration of the invention is shown in fig. 3, and the data updated and saved in the second iteration is shown in fig. 4.
Compared with the optimized decoding method, the traditional LDPC algorithm has higher complexity, the length of the information bit is assumed to be m, the length of the check node is assumed to be n, and the traditional algorithm only stores when each check node transmits informationAfter the n nodes are transmitted, the m information nodes are required to be transmitted again to obtain the final information probability P v', and the total message transmission times are m+n. And when the optimized method carries out message transmission on the check node, the P v 'value is updated at the same time, after the check node is updated, the information probability P v' value is updated, at the moment, the message transmission times are only n, and in LDPC coding, the length m of the information node is much longer than the length n of the check node, so that the calculation complexity is greatly reduced. Meanwhile, the updated P v ' value after the check node information is equivalent to decoding the current check node, and substituting the result into the next check node decoding, along with the process of the check node transmission, the decoded bits are more and more, and the optimization of LLR value calculation is added, so that compared with the traditional algorithm, the convergence speed of the optimized algorithm P v ' is much faster after the result of all check nodes is required to be output and then the update of P v ' is carried out.
In addition, by increasing the check matrix H to check the bit judgment value, iteration can be stopped after the set condition is reached, so that the calculation efficiency is greatly improved.
The invention is directed to LLR computation for LDPC optimization including but not limited to 802.11a/p/g/n/ac/ax/be, and likewise, directed to flow optimization for LDPC decoding including but not limited to 802.11a/p/g/n/ac/ax/be. According to the method, the LLR calculation and the LDPC decoding flow are optimized, so that the LDPC decoding performance is effectively improved, and the decoding complexity is reduced.
The above embodiments are preferred embodiments of the present invention, and are not intended to limit the scope of the present invention, which includes but is not limited to the embodiments, and equivalent modifications according to the present invention are within the scope of the present invention.
Claims (6)
1. An LDPC step-by-step decoding method based on noise power is characterized by comprising the following steps:
initializing parameters, wherein the parameters comprise probability values of node information and check node values;
Step two, starting iteration;
judging whether the iteration times are reached, if so, ending, and if not, executing the fourth step;
step four, sequentially carrying out message transmission on each check node, updating the probability value of the node information after each check node is updated, and storing the value of each check node;
step five, after all the check nodes are updated, bit judgment is carried out on the probability value of the node message, the iteration is ended,
In step one, the probability distribution LLR value calculated by the message passing algorithm, that is, P v is assigned to P v′,Pv as the prior probability value of the check node, P v' as the probability value of the information node v updated by each check node, and the check node value is initialized Representing the ith iteration, the jth check node passes the message to the information node,
The prior probability value P v of the check node is calculated based on the noise power sigma 2 value of each symbol, the noise power sigma 2 value is a rough noise power estimated value of each symbol, the calculation method is sigma 2＝|yi-si|2+|yq-sq|2, wherein y i is the real part of the symbol y after equalization, y q is the imaginary part of the symbol y after equalization, s i is the real part of the standard constellation point nearest to the symbol y after equalization, s q is the imaginary part of the standard constellation point nearest to the symbol y after equalization,
In the fourth step, the calculation formula of the updated value of each check node is: Wherein v' ∈n (c) \v denotes that the message transmitted from the symbol node v to the check node c does not contain the message transmitted from c to the symbol node v, and the calculation formula of the updated node information probability value is as follows:
in the fifth step, after one iteration is completed, sign judgment is carried out on the node information probability value P v' is the probability value of the information node v after each test node update, x is the bit value after judgment, sign is the sign function.
2. The LDPC step decoding method based on noise power according to claim 1 further comprising the step of performing bit check using a check matrix H after bit decision, ending if the check result is a set value, otherwise performing the next iteration.
3. The method of LDPC step decoding based on noise power according to claim 2 wherein in step six, the check matrix H is used to check, if Hx=0, the iteration is ended, otherwise the next iteration is performed until the set maximum number of iterations is reached.
4. The method of LDPC step decoding based on noise power according to any of claims 1 to 3 wherein the lowest threshold value σ 0 2 of the noise power is set according to the simulation data.
5. A system for implementing the noise power based LDPC step-wise decoding method of any one of claims 1-4, comprising:
the initialization module is used for initializing parameters, wherein the parameters comprise probability values of node information and check node values;
The iteration starting module is used for starting iteration;
The judging module is used for judging whether the iteration times are reached, if yes, ending, and if not, executing iteration;
The iteration module is used for sequentially carrying out message transmission on each check node, updating the probability value of the node information after each check node is updated, and storing the value of each check node;
And the bit judging module is used for carrying out bit judgment on the probability value of the node message after all the check nodes are updated.
6. The system of claim 5, further comprising a bit check module for bit checking the decision value using the check matrix H after bit decision.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202111037601.6A CN113794478B (en) | 2021-09-06 | 2021-09-06 | LDPC (Low Density parity check) step decoding method and system based on noise power |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202111037601.6A CN113794478B (en) | 2021-09-06 | 2021-09-06 | LDPC (Low Density parity check) step decoding method and system based on noise power |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN113794478A CN113794478A (en) | 2021-12-14 |
| CN113794478B true CN113794478B (en) | 2024-12-17 |
Family
ID=78879592
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202111037601.6A Active CN113794478B (en) | 2021-09-06 | 2021-09-06 | LDPC (Low Density parity check) step decoding method and system based on noise power |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN113794478B (en) |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102325001A (en) * | 2011-05-24 | 2012-01-18 | 东南大学 | A Bandwidth Adaptive Large Iterative Receiver |
| CN104539295A (en) * | 2015-01-16 | 2015-04-22 | 北京邮电大学 | Initialization method of novel LDPC (Low Density Parity Check) iterative decoding based on characteristic bit apriori information |
Family Cites Families (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP4403334B2 (en) * | 2000-03-30 | 2010-01-27 | ソニー株式会社 | Decoding device, decoding method, and recording medium on which decoding program is recorded |
| JP4296949B2 (en) * | 2004-02-03 | 2009-07-15 | ソニー株式会社 | Decoding apparatus and method, and information processing apparatus and method |
| KR100846869B1 (en) * | 2004-12-16 | 2008-07-16 | 한국전자통신연구원 | Low complexity LDPC decoding device and method |
| JP4574680B2 (en) * | 2005-09-28 | 2010-11-04 | Ｋｄｄｉ株式会社 | Multi-carrier code division multiplexing transmission system and method, and receiving apparatus |
| US7398453B2 (en) * | 2005-10-03 | 2008-07-08 | Motorola, Inc. | Method and apparatus for a low-density parity-check decoder |
| CN102545913B (en) * | 2012-02-07 | 2015-05-27 | 中兴通讯股份有限公司 | Iterative decoding method and system |
| CN107196737B (en) * | 2017-04-24 | 2020-04-28 | 广西大学 | SCMA decoding method based on message passing algorithm |
| CN108768409A (en) * | 2018-06-06 | 2018-11-06 | 重庆邮电大学 | A kind of LDPC interpretation methods based on normalization minimum value of optimization |
-
2021
- 2021-09-06 CN CN202111037601.6A patent/CN113794478B/en active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102325001A (en) * | 2011-05-24 | 2012-01-18 | 东南大学 | A Bandwidth Adaptive Large Iterative Receiver |
| CN104539295A (en) * | 2015-01-16 | 2015-04-22 | 北京邮电大学 | Initialization method of novel LDPC (Low Density Parity Check) iterative decoding based on characteristic bit apriori information |
Also Published As
| Publication number | Publication date |
|---|---|
| CN113794478A (en) | 2021-12-14 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN109257148B (en) | Polarization code BP decoding method based on Gaussian approximate threshold judgment | |
| CN106301517B (en) | Based on the satellite multi-beam joint-detection and interpretation method it is expected to propagate and system | |
| CN107689801B (en) | An Early Stopping Method for ADMM Iterative Decoding of LDPC Codes | |
| CN107612560B (en) | Early Iterative Stopping Method for Polar Codes Based on Partial Information Bit Likelihood Ratio | |
| CN106803759A (en) | Polar yards of effective adaptive decoding method based on Gauss construction | |
| CN112564716B (en) | PC-SCMA system joint decoding method based on pruning iteration | |
| CN108092673B (en) | A BP iterative decoding method and system based on dynamic scheduling | |
| CN104393877B (en) | Irregular LDPC codes linear programming interpretation method based on weighting | |
| CN107565978B (en) | BP decoding method based on Tanner graph edge scheduling strategy | |
| CN110233628B (en) | Adaptive Belief Propagation List Decoding Method for Polar Codes | |
| CN111726202B (en) | Early termination iteration method for polarization code belief propagation decoding | |
| CN108809518B (en) | Cascaded Spinal Code Construction Method for Reduced Error Performance | |
| CN112600568A (en) | Code modulation transmission method combining nonstandard 6-order modulation and LDPC code | |
| Lu et al. | Deep learning aided SCL decoding of polar codes with shifted-pruning | |
| CN113014271B (en) | A Polar Code BP Decoding Method with Reduced Flip Sets | |
| CN113794478B (en) | LDPC (Low Density parity check) step decoding method and system based on noise power | |
| CN118868975A (en) | A LDPC-Hadamard hybrid coding and decoding method in low signal-to-noise ratio environment | |
| KR20090012189A (en) | Decoding Apparatus and Method Using Scaling-based Improved MINI-SMW Iterative Decoding Algorithm for Performance Improvement of LDPC Code | |
| CN116633483B (en) | A rule variable node degree fountain encoding method | |
| CN109217984B (en) | Efficient Blind Detection Decoding Method and Decoder for Polar Codes | |
| CN114337691B (en) | A Zipper code soft decoding method based on Chase-Pyndiah algorithm | |
| CN113965292A (en) | Low-complexity polarization code SC decoding method based on aggregation structure | |
| Lyu et al. | Reliability-oriented decoding strategy for LDPC codes-based D-JSCC system | |
| Xia et al. | A two-staged adaptive successive cancellation list decoding for polar codes | |
| Zhang et al. | Neural network based successive cancellation decoding algorithm for polar codes in URLLC |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |