CN110518918B - Decoding method and decoder - Google Patents
Decoding method and decoder Download PDFInfo
- Publication number
- CN110518918B CN110518918B CN201910379686.2A CN201910379686A CN110518918B CN 110518918 B CN110518918 B CN 110518918B CN 201910379686 A CN201910379686 A CN 201910379686A CN 110518918 B CN110518918 B CN 110518918B
- Authority
- CN
- China
- Prior art keywords
- block
- sub
- check matrix
- check
- zero
- 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
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N3/00—Computing arrangements based on biological models
- G06N3/02—Neural networks
- G06N3/04—Architecture, e.g. interconnection topology
- G06N3/044—Recurrent networks, e.g. Hopfield networks
-
- 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
-
- 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/1148—Structural properties of the code parity-check or generator matrix
Landscapes
- Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Mathematical Physics (AREA)
- Probability & Statistics with Applications (AREA)
- Computational Linguistics (AREA)
- Molecular Biology (AREA)
- Artificial Intelligence (AREA)
- Biomedical Technology (AREA)
- Biophysics (AREA)
- Health & Medical Sciences (AREA)
- Data Mining & Analysis (AREA)
- Evolutionary Computation (AREA)
- General Health & Medical Sciences (AREA)
- Life Sciences & Earth Sciences (AREA)
- Computing Systems (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Software Systems (AREA)
- Error Detection And Correction (AREA)
- Compression Or Coding Systems Of Tv Signals (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Abstract
The invention discloses a decoding method, which is based on a TDMP scheduling strategy, updates all variable nodes after updating part of check nodes, then updates the other part of check nodes and then updates all variable nodes, and repeats the process; the method divides the operation of updating part of check nodes into a plurality of sub-operations, and organizes the sub-operations and the operation of updating all variable nodes into a two-stage production line, thereby improving the utilization rate of the component decoder; the method combines the requirement of parallelism degree, constructs the control logic of the production line to skip all-zero pseudo blocks in the check matrix, and can reduce the time consumed by iteration; particularly, the method performs row-column exchange on the check matrix so as to reduce the number of invalid operations, obviously reduce the time consumption of iteration and improve the throughput. The invention also discloses a decoder.
Description
Technical Field
The invention relates to the field of communication, and also relates to the technical field of computers, in particular to a decoding method, an LDPC decoding method and a decoder.
Background
An LDPC (Low-density Parity-check) code is a linear block code with a sparse check matrix, has the advantages of excellent burst error resistance, bit error performance close to shannon limit, easy realization of parallelization, and the like, and is widely applied to existing mainstream high-throughput wireless communication standard protocols, such as IEEE 802.11n/ac, LTE, DVB, and the like. In view of the development of the past decades, the LDPC decoder is developed toward a smaller area and a higher throughput, and thus, the LDPC decoder is also increasingly applied to mobile devices sensitive to power consumption and area, such as a mobile phone.
The decoding algorithm of the LDPC code is based on a parallel iterative decoding algorithm of a sparse matrix, the operation amount of the decoding algorithm is lower than that of a Turbo code decoding algorithm, the decoding algorithm is easy to realize on hardware, and the decoding algorithm has the advantages in large-capacity communication application. The code rate of the LDPC code can be arbitrarily constructed, and the flexibility is higher. In addition, the LDPC code has a lower error floor, and can be applied to occasions with strict requirements on code rate, such as wired communication, deep space communication, disk storage and the like.
The throughput of the decoder is an important parameter that those skilled in the art strive to improve. In order to improve the throughput of the LDPC decoder without increasing the implementation complexity, faster convergence may be achieved by designing a scheduling policy in the Decoding process, typically, the scheduling policy is such as TPMP (Two-Phase Message-paging), TDMP (Turbo-Decoding Message-paging), and VSS (Vertical buffer Schedule). In an iterative decoding structure of the LDPC code, a common binary tree structure divides calculation nodes into two types, variable nodes and check nodes. In the TPMP, after all check nodes are calculated, variable nodes are calculated, and after all variable nodes are calculated, check nodes are calculated, namely, the check nodes and the variable nodes are calculated and updated in a time-sharing manner. A strategy for updating the time-staggered operation of the check node and the variable node can improve the convergence rate of iterative decoding, and is called as layered iteration.
The hierarchical iteration is divided into a horizontal hierarchical iteration and a vertical hierarchical iteration. In the horizontal layered iteration, one iteration process is divided into a plurality of sub-iterations, and partial check nodes and all variable nodes are updated in each sub-iteration, such as a TDMP strategy. In the longitudinal layered iteration, one iteration process is divided into a plurality of sub-iterations, and partial variable nodes and all check nodes, such as a VSS strategy, are updated in each sub-iteration. The TDMP strategy effectively considers both throughput and implementation complexity, and becomes a mainstream technology in a medium-high-speed LDPC decoding scene.
In the TDMP layered iterative decoding of an LDPC code in the prior art, a calculation process is performed in rows, where an LDPC decoder includes row layering, a row block of a check matrix H of the LDPC code is used as a basis for layering in a row layering structure, a non-zero position of the check matrix H is obtained in each iteration cycle, a position of each bit in a last valid row block is marked to obtain a mark position, and after a final result of each bit is obtained, an operation is performed with a final result of the check of a previous bit to obtain check results of all bits. In the method, due to the sparsity of the check matrix, the final iteration result of a certain bit is obtained before the calculation of all rows is completed, and the bit can be ignored in the next iteration calculation for a plurality of times so as to save the operation amount. However, the throughput improvement of the method is limited, and the method has a limited application range.
In the layered iterative decoding of another LDPC code in the prior art, a basic check matrix and an expansion factor are determined first, and then structured LDPC decoding is performed according to the basic check matrix and the expansion factor; the method utilizes the relationship between the adjacent non-zero block element values in any column in the check matrix, so that the LDPC code does not need waiting time or reduces the waiting time when adopting layered decoding, and further improves the throughput rate of the decoder. However, the method depends on the relationship between adjacent blocks in the same column in the check matrix, and lacks generality.
Because the check matrix of the LDPC is a sparse matrix, that is, most elements in the check matrix are 0, certain invalid operation exists in the existing scheduling strategy; and the invalid operations are removed, so that the time length of single iteration can be reduced, and the throughput rate of the LDPC is further improved. However, in the prior art, there is no method for eliminating all invalid operations, and the decoder in the prior art either has insufficient compression amount for the invalid operations or has high requirement on the characteristics of the check matrix, and how to further compress the proportion of the invalid operations for the more general check matrix to increase the throughput rate is a technical problem that needs to be solved urgently by those skilled in the art.
Disclosure of Invention
The invention discloses an LDPC decoding method, which is based on a TDMP scheduling strategy, updates all variable nodes after updating part of check nodes, then updates all variable nodes after updating the other part of check nodes, and repeats the process; the method divides the operation of updating part of check nodes into a plurality of sub-operations, and organizes the sub-operations and the operation of updating all variable nodes into a two-stage production line, thereby improving the utilization rate of the component decoder; the method combines the requirement of parallelism degree, constructs the control logic of the production line to skip all-zero pseudo blocks in the check matrix, and can reduce the time consumed by iteration; particularly, the method performs row-column exchange on the check matrix to reduce the number of invalid operations, remarkably reduce iteration time consumption and improve throughput.
The decoding method disclosed by the invention comprises the following steps:
step 101: selecting decoding parallelism G, and dividing a check matrix H into sub check matrices;
the block columns of the check matrix H are divided into G parts, each part comprises J block columns, the column number of the check matrix is represented as JGZ at the moment, and Z represents an expansion factor; the sub-check matrix obtained by dividing the check matrix is represented as H 1 、H 2 ...H G (ii) a Wherein, the dividing strategy is uniform division, if the block column number of H is not G integerMultiple times, filling columns behind H are needed, and all block matrixes in the filling columns are zero matrixes;
step 102: compressed sub-check matrix H 1 、H 2 ...H G Obtaining a pseudo block array Y by the all-zero block matrix in the step (1);
wherein, the sub-check matrix H is compressed 1 、H 2 ...H G The strategy of the all-zero block matrix in (1) is as follows:
(1) All-zero block backward shift processing is carried out on the sub-check matrix, so that all-zero blocks are concentrated at the position with large column numbers; sub-check matrix H g All zero blocks in the kth row in the sequence are shifted backwards, so that all the all zero blocks are concentrated at the position with large column number; wherein G =1,2.. G; k =1,2.. K, K being the maximum number of rows of the sub-check matrix;
(2) In pair H 1 、H 2 ...H G All the rows in the sequence are subjected to all-zero block backward shift treatment to obtain E 1 、E 2 ...E G ；
(3) Calculation of E 1 、E 2 ...E G The maximum value of the number of the non-zero blocks in the k-th row is recorded as l k (ii) a Wherein, the k-th line in Y has I in common k Element, the ith element is composed of E 1 、E 2 ...E G G blocks in the kth row and the ith column are formed by matrix splicing, and the block is a pseudo block; wherein i =1,2.. L k ；
Step 103: decomposing the calculation of Z check nodes corresponding to the k block row in the dummy block array Y into l k Secondary sub-check operation, wherein each sub-check operation processes one dummy block;
in a preferred embodiment, a sub-check operation comprises all the steps of the horizontal operation in the BP algorithm:
acquiring the output of a variable node corresponding to the current dummy block, acquiring the calculation horizontal operation output of the previous dummy block if the current dummy block is not the first dummy block of the current block line, and calculating the horizontal operation output of the current dummy block;
if the current dummy block is the last dummy block of the current block row, the output of the current dummy block is the final result of the BP algorithm horizontal operation of the current block row;
the BP algorithm comprises the BP algorithm and a deformation algorithm thereof; the deformation algorithm of the BP algorithm comprises a minimum sum algorithm, a normalized minimum sum algorithm and an offset minimum sum algorithm;
step 104: and (3) completing the calculation of GZ variable nodes corresponding to the ith pseudo block in the (K-1 mod K) th line in Y at one time, wherein the operation is vertical operation of a BP algorithm for all inputs of the current variable nodes.
In a preferred embodiment, step 103 and step 104 are pipelined simultaneously.
In a preferred embodiment, when there is a zero matrix in G block matrices in a dummy block, the pipeline circuit corresponding to the zero matrix is turned off.
In a preferred embodiment, the variable node to be used in step 103, if being processed by step 104, waits for the processing of step 104 to be completed.
In a preferred embodiment, after the iterative operation described in the above method is completed, the decision data is subjected to inverse processing according to the sub-check matrix division strategy in step 101, so as to obtain a decoded output.
The invention also discloses an LDPC decoding method, which comprises the following steps:
step 201, randomly selecting a plurality of different sub-check matrix division strategies;
step 202, calculating the iteration time consumption of the division strategies in sequence;
step 203, selecting the partitioning strategy with the minimum iteration time consumption for decoding.
The calculation method in step 202 is the calculation method described in the above embodiment.
The invention also discloses an LDPC decoding method, which comprises the following steps:
step 301: randomly selecting a plurality of different check matrixes H row exchange strategies; the effect of the compression strategy can be effectively improved due to the fact that row-column exchange is conducted on the check matrix.
Step 302, sequentially calculating the iteration time consumption of the row exchange strategy;
and step 303, selecting the row exchange strategy with the minimum iteration time consumption for decoding.
The calculation method in step 302 is the calculation method described in the above embodiment.
The invention also discloses a LDPC decoding method, which comprises the following steps:
step 401: randomly selecting a plurality of different sub-check matrix division strategies and row exchange strategies;
step 402: sequentially calculating the iteration time consumption of the combination strategy;
step 403: and selecting the combination strategy with the minimum iteration time consumption for decoding.
The calculation method in step 402 is the calculation method described in the above embodiment.
The invention also discloses a decoder, which comprises:
a dividing module: the dividing module is used for selecting the decoding parallelism G and dividing the check matrix H into sub check matrices;
the block columns of the check matrix H are divided into G parts, each part comprises J block columns, the column number of the check matrix is represented as JGZ at the moment, and Z represents an expansion factor; the sub-check matrix obtained by dividing the check matrix is represented as H 1 、H 2 ...H G (ii) a If the number of the block columns of the H is not integral multiple of G, filling columns behind the H are required to be filled, and all block matrixes in the filling columns are zero matrixes;
a compression module: the compression module is used for compressing the sub-check matrix H 1 、H 2 ...H G Obtaining a pseudo block array Y by the all-zero block matrix in the step (1);
wherein, the sub-check matrix H is compressed 1 、H 2 ...H G The strategy of the all-zero block matrix in (1) is as follows:
(1) All-zero block backward shift processing is carried out on the sub-check matrix, so that all-zero blocks are concentrated at the position with large column numbers; sub-check matrix H g All zero blocks in the kth row in the sequence are backwards moved, so that all the all zero blocks are concentrated at the position with large column number; wherein G =1,2.. G; k =1,2.. K, K being the sub-proof momentThe maximum number of rows of the array;
(2) In pair H 1 、H 2 ...H G All the rows in the sequence are subjected to all-zero block backward shift treatment to obtain E 1 、E 2 ...E G ；
(3) Calculating E 1 、E 2 ...E G The maximum value of the number of the non-zero blocks in the k-th row is recorded as l k (ii) a Wherein, the k-th line in Y has I in common k Element, the ith element is composed of E 1 、E 2 ...E G The Kth row and the ith column are formed by splicing G block matrixes, and the pseudo block is formed; wherein i =1,2.. L k ；
A first operation module: the first operation module is used for decomposing the calculation of Z check nodes corresponding to the k block row in the pseudo block array Y into l k Performing secondary sub-check operation, wherein each sub-check operation processes one pseudo block;
a second operation module: the second operation module is used for completing the calculation of GZ variable nodes corresponding to the ith pseudo block in the (K-1 mod K) th line in Y at one time, and the operation is vertical operation of a BP algorithm for all inputs of the current variable nodes.
In a preferred embodiment, the decoder further comprises a decoding module: and the decoding module is used for carrying out inverse processing on the judgment data according to a sub-check matrix division strategy in the division module after the iterative operation is finished so as to obtain final decoding output.
In a preferred embodiment, a sub-check operation comprises all the steps of the horizontal operation in the BP algorithm:
acquiring the output of a variable node corresponding to the current dummy block, acquiring the calculation horizontal operation output of the previous dummy block if the current dummy block is not the first dummy block of the current block line, and calculating the horizontal operation output of the current dummy block;
and if the current dummy block is the last dummy block of the current block line, the output of the current dummy block is the final result of the BP algorithm horizontal operation of the current block line.
In a preferred embodiment, the BP algorithm includes the BP algorithm itself and its variant algorithm; the deformation algorithm of the BP algorithm comprises a minimum sum algorithm, a normalized minimum sum algorithm and an offset minimum sum algorithm;
in a preferred embodiment, the first and second arithmetic modules are run concurrently to form a pipeline.
In a preferred embodiment, when there is a zero matrix in G block matrices in a dummy block, the pipeline circuit corresponding to the zero matrix is turned off.
In a preferred embodiment, the variable node to be used in the first operation module waits for the second operation module to complete if it is being processed by the second operation module.
The decoding method and the decoder of the invention construct check node operation and variable node operation in the TDMP scheduling strategy into a two-stage assembly line, thereby improving the utilization rate of the component decoder.
The decoding method and the decoder of the invention decompose one check node operation into a plurality of sub-check operations by taking the dummy block as a unit, and improve the utilization efficiency of the component decoder under the condition of meeting the requirement of parallelism.
The decoding method and the check matrix compression strategy adopted by the decoder effectively compress invalid operation in the check matrix, reduce the time length of single iteration, reduce the power consumption of a production line and improve the throughput.
According to the decoding method and the decoder, before the check matrix is compressed, row-column exchange is carried out on the check matrix, so that the compression strategy can be improved, the time consumption of iteration is reduced, and the throughput is improved.
The decoding method and the decoder adopt the method for avoiding the access conflict of the memory, can avoid the simultaneous read-write operation of the same data of the memory, can avoid the vertical operation when the horizontal operation in the BP algorithm is not completed, and prevent the decoding performance from being reduced.
Drawings
FIG. 1 is a check matrix diagram in the LDPC decoding method of the present invention.
FIG. 2 is a compression matrix diagram in the LDPC decoding method of the present invention.
Detailed Description
In order to describe the technical scheme of the invention in more detail and to facilitate further understanding of the invention, the following description of the embodiments of the invention is provided with reference to the accompanying drawings. It should be understood, however, that all of the illustrative embodiments and descriptions thereof are intended to illustrate the invention and are not to be construed as the only limitations of the invention. Meanwhile, the respective embodiments may be combined without conflict in internal logic.
In the LDPC decoding method of the invention, the LDPC check matrix H used in the wireless protocol is composed of a zxz block matrix, the block matrix is divided into a zero matrix and a non-zero matrix, and the zero matrix and the non-zero matrix are respectively represented by "-" and "P", wherein Z represents a spreading factor. For convenience of representation, P is also used herein for different non-zero block matrices. Fig. 1 shows a typical check matrix, where the presence of a large number of zero-block matrices causes a hierarchical decoder to wait, reducing the utilization of the hierarchical decoder.
The decoding method of the invention is based on BP (Belief Propagation) iterative decoding algorithm, can effectively improve the utilization rate of the component decoder, and comprises the following main steps:
step 101: selecting decoding parallelism G, and dividing a check matrix H into sub check matrices; specifically, the block columns of the check matrix H are divided into G parts, each part includes J block columns, and the column number of the check matrix at this time is represented as JGZ, where Z represents an expansion factor.
Specifically, the scheme for dividing the check matrix is as follows:
(1) The sub-check matrix obtained by division is represented as H 1 、H 2 ...H G ；
(2) The division strategy is uniform division, if the number of block columns of H is not integral multiple of G, a filling column needs to be supplemented behind H, and all block matrixes in the filling column are zero matrixes.
Step 102: compressing the sub-check matrix H 1 、H 2 ...H G Obtaining a pseudo block array Y by the all-zero block matrix in the pseudo block matrix;
wherein, the sub-check matrix H is compressed 1 、H 2 ...H G The strategy of the all-zero block matrix in (1) is as follows:
(1) All-zero block backward shift processing is carried out on the sub-check matrix, so that all the all-zero blocks are concentrated at the position with larger column numbers;
specifically, the sub-check matrix H g (where G =1,2.. G) all zero blocks in the K (K =1,2.. K, K being the maximum row number of the sub-check matrix) row are shifted back so that all zero blocks are concentrated at the position where the column number is larger;
(2) In pair H 1 、H 2 ...H G All the rows in the sequence are subjected to all-zero block backward shift treatment to obtain E 1 、E 2 ...E G ；
(3) Calculation of E 1 、E 2 ...E G The maximum value of the number of the non-zero blocks in the k-th row is recorded as l k (ii) a Wherein, the k-th line in Y has I in common k Element, i (i =1,2.. L) k ) An element is composed of E 1 、E 2 ...E G The Kth row and the ith column are formed by splicing G block matrixes, and the pseudo block is formed;
wherein the dummy block array Y does not have to be a matrix because the number of elements per row in Y is not necessarily equal, as shown in fig. 2, where G =2;
the check matrix compression strategy effectively compresses invalid operation in the check matrix, reduces the time length of single iteration and can reduce the power consumption of a production line.
Step 103: decomposing the calculation of Z check nodes corresponding to the kth block row in the pseudo block array Y into l k Secondary sub-check operation, wherein each sub-check operation processes one dummy block; wherein
The primary sub-check operation comprises all steps of horizontal operation in the BP algorithm:
acquiring the output of a variable node corresponding to the current dummy block, acquiring the calculation horizontal operation output of the previous dummy block if the current dummy block is not the first dummy block of the current block line, and calculating the horizontal operation output of the current dummy block;
and if the current dummy block is the last dummy block of the current block line, the output of the current dummy block is the final result of the BP algorithm horizontal operation of the current block line.
The BP algorithm refers to the BP algorithm itself and a variant algorithm thereof, and common variant algorithms include a min-sum algorithm, a normalized min-sum algorithm, an offset min-sum algorithm, and the like.
Therefore, one check node operation is decomposed into a plurality of sub check operations by taking the dummy block as a unit, so that the utilization efficiency of the component decoder is improved under the condition of meeting the requirement of parallelism.
Step 104: the calculation of GZ variable nodes corresponding to the ith pseudo block in the (K-1 mod K) th line in Y is completed at one time, and the operation is vertical operation of a BP algorithm for all inputs of the current variable nodes; where (K-1 mod K) represents a modulo operation, i.e., the result of (K-1) operation is modulo K.
Wherein, step 103 and step 104 are simultaneously pipelined. Therefore, check node operation and variable node operation in the TDMP scheduling strategy are constructed into a two-stage pipeline, and the utilization rate of the component decoder is improved.
In the method, when a zero matrix exists in G block matrixes in one dummy block, the pipeline circuit corresponding to the zero matrix is closed so as to save power consumption and cache.
In the above method, in order to prevent memory collision, the variable node to be used in step 103 needs to wait for the completion of the processing in step 104 if it is being processed in step 104.
Due to the memory access conflict avoidance method, the simultaneous read-write operation on the same data of the memory can be avoided, the vertical operation when the horizontal operation is not completed in the BP algorithm can be avoided, and the decoding performance is prevented from being reduced.
After the iteration of the method is completed, the decision data is inversely processed according to the sub-check matrix division strategy in the step 101, and the final decoding output can be obtained.
The invention also discloses an LDPC decoding method, which comprises the following steps:
step 201, randomly selecting a plurality of different sub-check matrix division strategies;
step 202, calculating the iteration time consumption of the division strategies in sequence;
step 203, selecting the partitioning strategy with the minimum iteration time consumption for decoding.
Wherein, the specific steps of step 202 are as follows:
step 2021: selecting a decoding parallelism G, and dividing a check matrix H into sub check matrixes; specifically, the block columns of the check matrix H are divided into G shares, each share includes J block columns, and the column number of the check matrix at this time is represented as JGZ, where Z represents an expansion factor.
Specifically, the partitioning strategy for the check matrix is as follows:
(1) The sub-check matrix obtained by division is represented as H 1 、H 2 ...H G ；
(2) The dividing strategy is uniform division, if the number of block columns of H is not integral multiple of G, filling columns need to be supplemented behind H, and all block matrixes in the filling columns are zero matrixes.
Step 2022: compressing the sub-check matrix H 1 、H 2 ...H G Obtaining a pseudo block array Y by the all-zero block matrix in the step (1);
wherein, the sub-check matrix H is compressed 1 、H 2 ...H G The strategy of the all-zero block matrix in (1) is as follows:
(1) All-zero block backward shift processing is carried out on the sub-check matrix, so that all the all-zero blocks are concentrated at the position with larger column numbers;
specifically, the sub-check matrix H g (where G =1,2.. G) all zero blocks in the K (K =1,2.. K, K being the maximum row number of the sub-check matrix) row are shifted back so that all zero blocks are concentrated at the position where the column number is larger;
(2) In pair H 1 、H 2 ...H G All the rows in the sequence are subjected to all-zero block backward shift treatment to obtain E 1 、E 2 ...E G ；
(3) Calculation of E 1 、E 2 ...E G The maximum value of the number of the non-zero blocks in the k-th row is recorded as l k (ii) a Wherein, the k-th line in Y has I in common k Element, i (i =1,2.. L) k ) An element is composed of E 1 、E 2 ...E G G blocks in the kth row and the ith column are formed by matrix splicing, and the block is a pseudo block;
step 2023: correcting Z blocks corresponding to the k block row in the dummy block array YThe computation of the nodes of the experiment is decomposed into l k Performing secondary sub-check operation, wherein each sub-check operation processes one pseudo block; wherein
The primary sub-check operation comprises all the steps of horizontal operation in the BP algorithm:
acquiring the output of a variable node corresponding to the current dummy block, acquiring the calculation horizontal operation output of the previous dummy block if the current dummy block is not the first dummy block of the current block line, and calculating the horizontal operation output of the current dummy block;
and if the current dummy block is the last dummy block of the current block line, the output of the current dummy block is the final result of the horizontal operation of the BP algorithm of the current block line.
The BP algorithm refers to the BP algorithm itself and a variant algorithm thereof, and common variant algorithms include a min-sum algorithm, a normalized min-sum algorithm, an offset min-sum algorithm, and the like.
Step 2024: and (3) completing the calculation of GZ variable nodes corresponding to the ith pseudo block in the (K-1 mod K) th line in Y at one time, wherein the operation is vertical operation of a BP algorithm for all inputs of the current variable nodes.
Wherein step 2023 and step 2024 are pipelined simultaneously.
In the method, when a zero matrix exists in G block matrixes in one dummy block, the pipeline circuit corresponding to the zero matrix is closed so as to save power consumption and cache.
In the above method, in order to prevent memory conflict, the variable node to be used in step 2023, if being processed by step 104, needs to wait for the completion of the processing of step 2024.
When the number of the methods adopting the comparative division strategy is enough, the selected method tends to be optimal according to the probability.
The invention also discloses an LDPC decoding method, which comprises the following steps:
step 301: randomly selecting a plurality of different check matrixes H row exchange strategies; the effect of the compression strategy can be effectively improved due to the fact that row-column exchange is carried out on the check matrix.
Step 302, calculating the iteration time consumption of the line exchange strategy in sequence;
and step 303, selecting the row exchange strategy with the minimum iteration time consumption for decoding.
The specific steps of step 302 are as follows:
step 3021: selecting a decoding parallelism G, and dividing a check matrix H into sub check matrixes; specifically, the block columns of the check matrix H are divided into G shares, each share includes J block columns, and the column number of the check matrix at this time is represented as JGZ, where Z represents an expansion factor.
Specifically, the partitioning strategy for the check matrix is as follows:
(1) The sub-check matrix obtained by division is represented as H 1 、H 2 ...H G ；
(2) The division strategy is uniform division, if the number of block columns of H is not integral multiple of G, a filling column needs to be supplemented behind H, and all block matrixes in the filling column are zero matrixes.
Step 3022: compressed sub-check matrix H 1 、H 2 ...H G Obtaining a pseudo block array Y by the all-zero block matrix in the pseudo block matrix;
wherein, the sub-check matrix H is compressed 1 、H 2 ...H G The strategy of the all-zero block matrix in (1) is as follows:
(1) All-zero block backward shift processing is carried out on the sub-check matrix, so that all the all-zero blocks are concentrated at the position with larger column numbers;
specifically, the sub-check matrix H g (where G =1,2.. G) all zero blocks in the K (K =1,2.. K, K being the maximum row number of the sub-check matrix) row are shifted back so that all zero blocks are concentrated at the position where the column number is larger;
(2) In pair H 1 、H 2 ...H G All the rows in the sequence are subjected to all-zero block post-shift treatment to obtain E 1 、E 2 ...E G ；
(3) Calculation of E 1 、E 2 ...E G The maximum value of the number of the non-zero blocks in the k-th row is recorded as l k (ii) a Wherein, the k-th line in Y has I in common k Element, i (i =1,2.. L) k ) An element consisting of E 1 、E 2 ...E G The k-th row and the i-th column in the total number of G block momentsThe array is spliced into a pseudo block;
here, the dummy block array Y does not necessarily have to be a matrix because the number of elements per row in Y is not necessarily equal.
Step 3023: decomposing the calculation of Z check nodes corresponding to the k block row in the dummy block array Y into l k Secondary sub-check operation, wherein each sub-check operation processes one dummy block; wherein
The primary sub-check operation comprises all the steps of horizontal operation in the BP algorithm:
acquiring the output of a variable node corresponding to the current dummy block, acquiring the calculation horizontal operation output of the previous dummy block if the current dummy block is not the first dummy block of the current block line, and calculating the horizontal operation output of the current dummy block;
and if the current dummy block is the last dummy block of the current block line, the output of the current dummy block is the final result of the horizontal operation of the BP algorithm of the current block line.
The BP algorithm refers to the BP algorithm itself and a variant algorithm thereof, and common variant algorithms include a min-sum algorithm, a normalized min-sum algorithm, a shift min-sum algorithm, and the like.
Step 3024: and (3) completing the calculation of GZ variable nodes corresponding to the ith pseudo block in the (K-1 mod K) th line in Y at one time, wherein the operation is vertical operation of a BP algorithm for all inputs of the current variable nodes.
Wherein step 2023 and step 2024 are pipelined simultaneously.
In the method, when a zero matrix exists in G block matrixes in one dummy block, the pipeline circuit corresponding to the zero matrix is closed so as to save power consumption and cache.
In the above method, in order to prevent memory conflict, the variable node to be used in step 2023, if being processed by step 104, needs to wait for the completion of the processing of step 2024.
When the compared row exchange strategy is adopted enough, the selected method tends to be optimal according to the probability, and the problem that the optimal row and column of the check matrix are difficult to find can be effectively solved according to the found optimal method.
The invention also discloses an LDPC decoding method, wherein the sub-check matrix division strategy and the row exchange strategy are jointly optimized, and the following steps are carried out:
step 401: randomly selecting a plurality of different sub-check matrix division strategies and row exchange strategies;
step 402: sequentially calculating the iteration time consumption of the combination strategy;
step 403: and selecting the combination strategy with the minimum iteration time consumption for decoding.
When the alternative combination of the sub-check matrix division strategy and the combination strategy of the row exchange strategy is enough, the selected combination tends to be optimal according to probability.
The decoder of the present invention comprises:
a dividing module: the dividing module is used for selecting the decoding parallelism G and dividing the check matrix H into sub check matrices; specifically, the block columns of the check matrix H are divided into G parts, each part includes J block columns, and the column number of the check matrix at this time is represented as JGZ, where Z represents an expansion factor.
Specifically, the scheme for dividing the check matrix is as follows:
(1) The sub-check matrix obtained by division is represented as H 1 、H 2 ...H G ；
(2) The division strategy is uniform division, if the number of block columns of H is not integral multiple of G, a filling column needs to be supplemented behind H, and all block matrixes in the filling column are zero matrixes.
A compression module: the compression module is used for compressing the sub-check matrix H 1 、H 2 ...H G Obtaining a pseudo block array Y by the all-zero block matrix in the pseudo block matrix;
wherein, the sub-check matrix H is compressed 1 、H 2 ...H G The strategy of the all-zero block matrix in (1) is as follows:
(1) All-zero block backward shift processing is carried out on the sub-check matrix, so that all the all-zero blocks are concentrated at the position with larger column numbers;
specifically, the sub-check matrix H g (where G =1,2.. G) after all-zero blocks in the K (K =1,2.. K, K being the maximum row number of the sub-check matrix) rowShifting to make all the zero blocks concentrated at the position with larger column number;
(2) In pair H 1 、H 2 ...H G All the rows in the sequence are subjected to all-zero block post-shift treatment to obtain E 1 、E 2 ...E G ；
(3) Calculating E 1 、E 2 ...E G The maximum value of the number of the non-zero blocks in the k-th row is recorded as l k (ii) a Wherein, the k-th line in Y has I in common k Element, i (i =1,2.. L) k ) An element consisting of E 1 、E 2 ...E G G blocks in the kth row and the ith column are formed by matrix splicing, and the block is a pseudo block;
here, the dummy block array Y does not necessarily have to be a matrix because the number of elements per row in Y is not necessarily equal.
A first operation module: the operation module is used for decomposing the calculation of Z check nodes corresponding to the k block row in the pseudo block array Y into l k Performing secondary sub-check operation, wherein each sub-check operation processes one pseudo block; wherein
The primary sub-check operation comprises all the steps of horizontal operation in the BP algorithm:
acquiring the output of a variable node corresponding to the current dummy block, acquiring the calculation horizontal operation output of the previous dummy block if the current dummy block is not the first dummy block of the current block line, and calculating the horizontal operation output of the current dummy block;
and if the current dummy block is the last dummy block of the current block line, the output of the current dummy block is the final result of the BP algorithm horizontal operation of the current block line.
The BP algorithm refers to the BP algorithm itself and a variant algorithm thereof, and common variant algorithms include a min-sum algorithm, a normalized min-sum algorithm, an offset min-sum algorithm, and the like.
A second operation module: and (3) completing the calculation of GZ variable nodes corresponding to the ith pseudo block in the (K-1 mod K) th line in Y at one time, wherein the operation is vertical operation of a BP algorithm for all inputs of the current variable nodes.
Wherein, step 103 and step 104 are simultaneously pipelined.
In the decoder, when a zero matrix exists in G block matrixes in one dummy block, the pipeline circuit corresponding to the zero matrix is closed so as to save power consumption and cache.
In the decoder described above, in order to prevent memory conflict, if the variable node to be used in step 103 is being processed in step 104, it is necessary to wait for the completion of the processing in step 104.
A decoding module: and the decoding module is used for carrying out inverse processing on the judgment data according to a sub-check matrix division strategy in the division module after the iterative operation is finished so as to obtain final decoding output.
For the LDPC decoding method disclosed by the invention, monte Carlo simulation verification is carried out on the decoding method disclosed by the invention by adopting an H1944,1/2,81 check matrix in an IEEE 802.11ac standard. Simulation verification shows that under the condition that the parallelism G =2, the decoding method reduces the time length of one iteration from 288 clocks of the original TDMP strategy to 62 clocks, reduces the iteration time consumption by 4.6 times, is equivalent to the throughput improved by 4.6 times, and averagely outputs 1.53 bits per clock decoding.
The method for improving LDPC decoding throughput in the prior art is mainly to increase parallelism, and the increase of parallelism is at the cost of doubling hardware area. The LDPC decoding method and the device effectively improve the decoding throughput by improving the time utilization rate of the decoding circuit under the condition of keeping the parallelism unchanged, which means that under the condition of given throughput, the parallel degree requirement can be effectively reduced, and the area of a decoder is further reduced.
The above-mentioned embodiments are intended to illustrate the objects, technical solutions and advantages of the present invention, and it should be understood that the above-mentioned embodiments are only exemplary embodiments of the present invention, and are not intended to limit the present invention, and any modifications, equivalents, improvements and the like made within the spirit and principle of the present invention should be included in the protection scope of the present invention.
Claims (14)
1. A decoding method, comprising the steps of:
step 101: selecting decoding parallelism G, and dividing a check matrix H into sub check matrices;
the block columns of the check matrix H are divided into G parts, each part comprises J block columns, the column number of the check matrix is represented as JGZ, and Z represents an expansion factor; the sub-check matrix obtained by dividing the check matrix is represented as H 1 、H 2 ...H G (ii) a If the number of the block columns of the H is not integral multiple of G, filling columns behind the H are required to be filled, and all block matrixes in the filling columns are zero matrixes;
step 102: compressed sub-check matrix H 1 、H 2 ...H G Obtaining a pseudo block array Y by the all-zero block matrix in the step (1);
wherein, the sub-check matrix H is compressed 1 、H 2 ...H G The strategy of the all-zero block matrix in (1) is as follows:
(1) All-zero block backward shift processing is carried out on the sub-check matrix, so that all-zero blocks are concentrated at the position with large column numbers; sub-check matrix H g All zero blocks in the kth row in the sequence are shifted backwards, so that all the all zero blocks are concentrated at the position with large column number; wherein G =1,2.. G; k =1,2.. K, K being the maximum number of rows of the sub-check matrix;
(2) In pair H 1 、H 2 ...H G All the rows in the sequence are subjected to all-zero block post-shift treatment to obtain E 1 、E 2 ...E G ；
(3) Calculation of E 1 、E 2 ...E G The maximum value of the number of the non-zero blocks in the k-th row is recorded as l k (ii) a Wherein, the k-th line in Y has I in common k Element, the ith element is composed of E 1 、E 2 ...E G G blocks in the kth row and the ith column are formed by matrix splicing, and the block is a pseudo block; wherein i =1,2.. L k ；
Step 103: decomposing the calculation of Z check nodes corresponding to the k block row in the dummy block array Y into l k Performing secondary sub-check operation, wherein each sub-check operation processes one pseudo block;
step 104: and (3) completing the calculation of GZ variable nodes corresponding to the ith pseudo block in the (K-1 mod K) th line in Y at one time, wherein the operation is vertical operation of a BP algorithm for all inputs of the current variable nodes.
2. The method of claim 1, wherein one of the sub-check operations comprises all steps of a horizontal operation in the BP algorithm:
acquiring the output of a variable node corresponding to the current dummy block, if the current dummy block is not the first dummy block of the current block row, acquiring the calculation horizontal operation output of the previous dummy block, and calculating the horizontal operation output of the current dummy block;
and if the current dummy block is the last dummy block of the current block line, the output of the current dummy block is the final result of the BP algorithm horizontal operation of the current block line.
3. The method of claim 1, wherein the BP algorithm comprises the BP algorithm itself and its variant algorithms.
4. The method of claim 3, wherein the morphing algorithms of the BP algorithm include a min-sum algorithm, a normalized min-sum algorithm, and an offset min-sum algorithm.
5. The method of claim 1, wherein said step 103 and said step 104 are pipelined simultaneously.
6. The method of claim 1, wherein when a zero matrix exists in G block matrices in one dummy block, the pipeline circuit corresponding to the zero matrix is turned off.
7. The method of claim 1, wherein the variable node to be used in step 103, if being processed by step 104, waits for step 104 processing to be completed.
8. The method of claim 1, further comprising the steps of:
and (4) carrying out inverse processing on the data according to the sub-check matrix division strategy in the step (101) to obtain decoding output.
9. A decoder, comprising:
a dividing module: the dividing module is used for selecting the decoding parallelism G and dividing the check matrix H into sub check matrices;
the block columns of the check matrix H are divided into G parts, each part comprises J block columns, the column number of the check matrix is represented as JGZ, and Z represents an expansion factor; the sub-check matrix obtained by dividing the check matrix is represented as H 1 、H 2 ...H G (ii) a If the number of the block columns of the H is not integral multiple of G, filling columns need to be filled behind the H, and all block matrixes in the filling columns are zero matrixes;
a compression module: the compression module is used for compressing the sub-check matrix H 1 、H 2 ...H G Obtaining a pseudo block array Y by the all-zero block matrix in the pseudo block matrix;
wherein, the sub-check matrix H is compressed 1 、H 2 ...H G The strategy of the all-zero block matrix in (1) is as follows:
(1) All-zero block backward shift processing is carried out on the sub-check matrix, so that all the all-zero blocks are concentrated at the positions with large column numbers; sub-check matrix H g All zero blocks in the kth row in the sequence are backwards moved, so that all the all zero blocks are concentrated at the position with large column number; wherein G =1,2.. G; k =1,2.. K, K being the maximum number of rows of the sub-check matrix;
(2) In pair H 1 、H 2 ...H G All the rows in the sequence are subjected to all-zero block post-shift treatment to obtain E 1 、E 2 ...E G ；
(3) Calculating E 1 、E 2 ...E G The maximum value of the number of the non-zero blocks in the k-th row is recorded as l k (ii) a Wherein, the k-th line in Y has I in common k Element, the ith element is composed of E 1 、E 2 ...E G G blocks in the kth row and the ith column are formed by matrix splicing, and the block is a pseudo block; wherein i =1,2 k ；
First operation module: the first operation module is used for decomposing the calculation of Z check nodes corresponding to the k block row in the pseudo block array Y into l k Secondary sub-check operation, wherein each sub-check operation processes one dummy block;
a second operation module: the second operation module is used for completing the calculation of GZ variable nodes corresponding to the ith dummy block in the (K-1 mod K) th line in Y at one time, and the operation is the vertical operation of the BP calculation algorithm for all inputs of the current variable nodes.
10. The decoder of claim 9, further comprising a decoding module: the decoding module is used for carrying out inverse processing on the data according to the sub-check matrix division strategy in the division module to obtain final decoding output.
11. The decoder of claim 9 or 10, wherein a sub-check operation comprises all steps of a horizontal operation in the BP algorithm:
acquiring the output of a variable node corresponding to the current dummy block, acquiring the calculation horizontal operation output of the previous dummy block if the current dummy block is not the first dummy block of the current block line, and calculating the horizontal operation output of the current dummy block;
and if the current dummy block is the last dummy block of the current block line, the output of the current dummy block is the final result of the horizontal operation of the BP algorithm of the current block line.
12. The transcoder of claim 9 or 10, wherein the BP algorithm comprises the BP algorithm itself and its variants.
13. The decoder of claim 9 or 10, wherein the first operational module and the second operational module are run concurrently forming a pipeline.
14. The decoder of claim 9 or 10, wherein the variable node to be used in the first operation module, if being processed by the second operation module, waits for the second operation module to complete processing.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910379686.2A CN110518918B (en) | 2019-05-08 | 2019-05-08 | Decoding method and decoder |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910379686.2A CN110518918B (en) | 2019-05-08 | 2019-05-08 | Decoding method and decoder |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN110518918A CN110518918A (en) | 2019-11-29 |
| CN110518918B true CN110518918B (en) | 2022-12-20 |
Family
ID=68622437
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201910379686.2A Active CN110518918B (en) | 2019-05-08 | 2019-05-08 | Decoding method and decoder |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN110518918B (en) |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8028214B2 (en) * | 2006-08-17 | 2011-09-27 | Mobile Techno Corp. | Low density parity check codes decoder and method thereof |
| CN101931416A (en) * | 2009-06-24 | 2010-12-29 | 中国科学院微电子研究所 | Parallel layered decoder of LDPC code in mobile digital multimedia broadcasting system |
| CN101753150B (en) * | 2009-12-22 | 2012-10-10 | 华东师范大学 | Decoding check method and device of low-density parity check code |
| CN102664638A (en) * | 2012-05-31 | 2012-09-12 | 中山大学 | FPGA (Field Programmable Gate Array) realization method for multi-code-length LDPC (Low Density Parity Check) code decoder on basis of hierarchical NMS (Network Management System) algorithm |
-
2019
- 2019-05-08 CN CN201910379686.2A patent/CN110518918B/en active Active
Also Published As
| Publication number | Publication date |
|---|---|
| CN110518918A (en) | 2019-11-29 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US11424762B2 (en) | Decoder for low-density parity-check codes | |
| US8601352B1 (en) | Efficient LDPC codes | |
| US8839077B2 (en) | Low density parity check codec | |
| US8321747B2 (en) | QC-LDPC code decoder and corresponding decoding method | |
| US8869003B2 (en) | Method, apparatus, computer program product and device providing semi-parallel low density parity check decoding using a block structured parity check matrix | |
| US9037945B2 (en) | Generating partially sparse generator matrix for a quasi-cyclic low-density parity-check encoder | |
| US20060020870A1 (en) | Layered decoding of low density parity check (PDPC) codes | |
| CN101232288B (en) | A kind of decoding method and decoder of LDPC code based on parity check matrix | |
| CN105049060B (en) | Decoding method and device for low-density parity code LDPC | |
| Liao et al. | A (21150, 19050) GC-LDPC decoder for NAND flash applications | |
| CN103916134B (en) | Low-density parity check code aliasing and decoding method and multi-core collaborative aliasing decoder | |
| CN103220002A (en) | Quasi-cyclic low-density parity-check (LDPC) code construction method capable of eliminating decoder access conflict | |
| CN101594152B (en) | LDPC code decoding method for realizing simultaneous operation of horizontal operation and vertical operation | |
| CN110518918B (en) | Decoding method and decoder | |
| CN108809327B (en) | LDPC decoding method | |
| JP2006339799A (en) | Irregular low density parity check code decoder and method | |
| CN118573213A (en) | FPGA implementation method, system and medium based on layering and product decoding algorithm | |
| CN108809324B (en) | LDPC decoding method | |
| CN102696176B (en) | Decoding device | |
| CN102347774A (en) | Encoding and decoding method of low-density parity-check code | |
| CN108809325B (en) | LDPC decoder | |
| CN103731161B (en) | Overlapping decoding method for low density parity code (LDPC) | |
| TWI583141B (en) | Decoding method and decoder for low density parity check code | |
| CN108809326B (en) | LDPC decoder | |
| CN109428604B (en) | LDPC code decoding method and circuit adopting improved TDMP algorithm |
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 | ||
| CB02 | Change of applicant information |
Address after: 518000 13 / F, union building, No. 1069, Shekou Nanhai Avenue, merchants street, Nanshan District, Shenzhen City, Guangdong Province Applicant after: Shenzhen Quanzhi online Co.,Ltd. Address before: 518000 13 / F, union building, No. 1069, Shekou Nanhai Avenue, merchants street, Nanshan District, Shenzhen City, Guangdong Province Applicant before: XRADIOTECH TECHNOLOGY Co.,Ltd. |
|
| CB02 | Change of applicant information | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |