CN104426553A - Encoding method for low-density parity check matrix - Google Patents
Encoding method for low-density parity check matrix Download PDFInfo
- Publication number
- CN104426553A CN104426553A CN201310371629.2A CN201310371629A CN104426553A CN 104426553 A CN104426553 A CN 104426553A CN 201310371629 A CN201310371629 A CN 201310371629A CN 104426553 A CN104426553 A CN 104426553A
- Authority
- CN
- China
- Prior art keywords
- check
- bits
- density parity
- matrix
- low density
- 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.)
- Granted
Links
- 239000011159 matrix material Substances 0.000 title claims abstract description 71
- 238000000034 method Methods 0.000 title claims abstract description 30
- 125000004122 cyclic group Chemical group 0.000 claims abstract description 16
- 238000012545 processing Methods 0.000 claims description 6
- 238000004891 communication Methods 0.000 description 5
- 230000005540 biological transmission Effects 0.000 description 3
- 238000004364 calculation method Methods 0.000 description 2
- 238000012937 correction Methods 0.000 description 2
- 238000011161 development Methods 0.000 description 2
- 230000018109 developmental process Effects 0.000 description 2
- 230000009977 dual effect Effects 0.000 description 2
- RPICHNHPPUQIHI-UHFFFAOYSA-N 4,6-dichloro-7-(2,4,5-trichlorophenoxy)-2-(trifluoromethyl)-1h-benzimidazole Chemical compound C=12NC(C(F)(F)F)=NC2=C(Cl)C=C(Cl)C=1OC1=CC(Cl)=C(Cl)C=C1Cl RPICHNHPPUQIHI-UHFFFAOYSA-N 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 238000011160 research Methods 0.000 description 1
Landscapes
- Error Detection And Correction (AREA)
Abstract
The invention discloses an encoding method for a low-density parity check matrix, the encoding method including the steps of: setting the sizes of check parts and cyclic submatrixes in the low-density parity check matrix; initializing each check bit corresponding to the check parts; dividing the check bits into groups in accordance with the sizes of the cyclic submatrixes to obtain a plurality of check bit groups; accumulating the check bits in each check bit group with related information bits in the low-density parity check matrix; interleaving each accumulated check bit; and performing MOD2 addition operation on each interleaved check bit to obtain the final check bit. According to the encoding method for the low-density parity check matrix, the encoding complexity is reduced.
Description
Technical Field
The invention relates to the field of coding, in particular to a coding method of a low-density parity check matrix.
Background
The LDPC code was proposed by Gallager in his phd paper in 1963 for the first time, meanwhile Gallager also proposed a probability decoding algorithm of the LDPC code, but since the probability iterative decoding calculation is too complex, the LDPC code quickly sinks the sea in the communication field at that time in view of the difficulty in implementation of the technology development at that time. After that, few learners have paid much attention to LDPC codes, except for the bipartite graph that Tanner visualizes in the 80's last century to describe iterative decoding.
In 1993, the Turbo code was proposed, so that 45 years later, a coding scheme approaching the Shannon limit was first seen. Until now, people have paid attention to the excellent performance of iterative decoding, and meanwhile, the iterative theory based on bipartite graph (Tanner graph) has made a great breakthrough: spielman explains the error correction process as a process of gradually reducing errors, proves that a bipartite Graph-based coding and decoding algorithm has linear complexity, on the basis, scholars propose conditions and a method for generating a bipartite Graph with certain error correction capability by using an Expander Graph, and then Kschischang and the like establish the theory of a Factor Graph (Factor Graph) and further deepen the Graph theory basis based on LDPC iterative decoding; based on these studies, Wiber proposed a graph-based LDPC iterative decoding algorithm. All these developments have been made, so that in 1995 Mackay and Neal discovered that LDPC codes have performance approaching the shannon limit as Turbo codes, thereby causing a hot tide of research on LDPC codes.
The LDPC code is more technically and particularly more advantageous in complexity than the Turbo code, and is more suitable for high-speed data transmission and high-performance requirements of a future system, and thus is widely used. Currently, communication systems using LDPC codewords include: the european second generation digital broadcast television transmission standard DVB2 series; IEEE802.11 n wireless local area network standard; the ieee802.11e wireless wide area network standard; the terrestrial transmission standard for digital television (DTTB) in china, and the near-earth, deep space communication systems of the north american CCSDS, and the like.
From an implementation perspective, several challenges need to be faced. For example, storage is an important reason that LDPC codes are not widely used in practice. Also, one key issue in LDPC code implementation is how to implement a connection network between several processing engines (nodes) of the decoder. In addition, the computational load in the decoding process, especially check node calculation, also presents problems.
Therefore, there is a need for an LDPC communication system that uses simple encoding and decoding processes. There is also a need to efficiently support high data rates using LDPC codes without introducing greater complexity. There is also a need to improve the performance of LDPC encoders and decoders, to minimize the memory requirements for implementing LDPC encoding, and to a simplified communication scheme between processing nodes of an LDPC decoder.
Disclosure of Invention
The invention solves the problem that the existing coding method of the low-density parity check matrix is relatively complicated.
To solve the above problem, an embodiment of the present invention provides a method for encoding a low density parity check matrix, including: setting the size of a check part in the low-density parity check matrix and the size of a cyclic sub-matrix; initializing each check bit corresponding to the check part; grouping the check bits according to the size of the cyclic subarray to obtain a plurality of check bit groups; accumulating the check bits in each check bit group and the information bits related to the check bits in the low-density parity check matrix; interleaving each accumulated check bit; and performing modulo-2 addition operation on each check bit subjected to interleaving processing to obtain a final check bit.
Optionally, the size of the check portion is M × M, and the size of the cyclic sub-array is q × q; the grouping the check bits according to the size of the cyclic sub-array to obtain a plurality of check bit groups comprises: setting said check bits to a}; grouping the check bits sequentially by q bitsThe rows are grouped to obtain a plurality of check bit groups.
Optionally, the accumulating the check bits in each check bit group and the information bits associated with the check bits in the low density parity check matrix includes:
for q bits in each check bit groupThe following XOR operation is performed:
=(ii) a Wherein,；represented in a low density parity check matrixThe associated information bits are then transmitted to the receiver,
obtained according to the following formula:
wherein x represents a position of a column in which "1" in a row in the low density parity check matrix represented by the first check bit in each check bit group is located, but does not include a position of a column of "1" in a parity part in the low density parity check matrix.
Optionally, the interleaving processing on the accumulated check bits includes:
and interleaving the accumulated check bits according to a permutation format, wherein the permutation format is realized by the following formula:
wherein,；i=0、1、2、3、……、q-1；Q=M/q;
{denotes the check bits before interleaving;
{denotes the interleaved check bits.
Optionally, performing modulo-2 addition on each parity bit after interleaving to obtain a final parity bit is implemented by the following formula:
wherein,represents the position of the second "1" in the last column of the parity check part in the low density parity check matrix; said final check bit is}。
Optionally, before initializing each parity bit corresponding to the parity part, the method further includes the following steps: setting a position of a second "1" in a last column of the parity part in the low density parity check matrix.
Compared with the prior art, the technical scheme of the invention has the following advantages:
the embodiment of the invention adopts a double diagonal structure (before interleaving) of a low-density parity check matrix check part and is characterized in that: there is a 1 in the upper right corner of the matrix of the check portion (i.e., the last column of the first row) and a 1 in the middle of the last column (the k-th row, the number of rows starting from 0). Based on such a structure, the bits of the parity part can be obtained by using the bit and parity equations of the information part without using a coding matrix, thereby reducing the coding complexity.
Drawings
Fig. 1 is a flowchart illustrating an embodiment of a method for encoding a low density parity check matrix according to the present invention.
Detailed Description
The inventor finds that the existing encoding method of the low-density parity check matrix is relatively complicated.
In view of the above problems, the inventors have studied to provide a method for encoding a low density parity check matrix, thereby reducing the encoding complexity.
In order to make the aforementioned objects, features and advantages of the present invention comprehensible, embodiments accompanied with figures are described in detail below.
Fig. 1 is a flow chart illustrating an embodiment of a method for encoding a low density parity check matrix according to the present invention. Referring to fig. 1, the encoding method includes the steps of:
step S1: setting the size of a check part in the low-density parity check matrix and the size of a cyclic sub-matrix;
step S2: initializing each check bit corresponding to the check part;
step S3: grouping the check bits according to the size of the cyclic subarray to obtain a plurality of check bit groups;
step S4: accumulating the check bits in each check bit group and the information bits related to the check bits in the low-density parity check matrix;
step S5: interleaving each accumulated check bit;
step S6: and performing modulo-2 addition operation on each check bit subjected to interleaving processing to obtain a final check bit.
The following describes an implementation of the above coding method with reference to a specific embodiment.
The size of the parity portion of the low density parity check matrix and the size of the cyclic sub-matrix are set as described in step S1.
The low density parity check matrix includes an information bit portion and a check portion.
Let the code word of LDPC be(ii) a Wherein,for information bits, are knownSequence of。For the check bits, for the bits to be calculated.
In this embodiment, the size M of the parity portion in the low density parity check matrix is q × q, and the size of the cyclic sub-matrix is q × q. Typically, the check portion is located at the right part of the low density parity check matrix, as shown in the structure of codeword c of the above LDPC.
Before executing step S2, the present embodiment further includes: setting a position k of a second "1" in a last column of a parity part in the low density parity check matrix. The check part matrix (P matrix) is constructed as follows, and the rows of the P matrix are counted from 0.
The structure of the P matrix which is a dual diagonal matrix structure before interweaving is different from the prior structure in that: there is a 1 in the top right corner of the P matrix (i.e., the last column in the first row) and a 1 in the middle of the last column (the k-th row, starting with 0).
In step S2, each parity bit corresponding to the parity part is initialized.
Namely, it isEach of whichRepresenting a column in a check matrix, e.g.Representing the mth column in the check matrix.
As shown in step S3, the check bits are grouped according to the size of the cyclic sub-array to obtain a plurality of check bit groups.
Specifically, first, the check bit is set to}. Then, the check bits are grouped in sequence by q bits to obtain a plurality of check bit groups.
For example, the check bit group is:
wherein j is (0, 1, 2, …, q-1).
As described in step S4, the check bits in each check bit group are accumulated with their associated information bits in the low density parity check matrix.
Specifically, for q bits in each check bit groupThe following XOR operation is performed:
=；
wherein,；
representing the ANDs in the low density parity check matrixThe associated information bits are then transmitted to the receiver,
obtained according to the following formula:
formula (1)
Where x represents the first parity bit in each parity bit group (e.g., may be，，，) The row in the low density parity check matrix represented (corresponding to the secondRow) of the parity check matrix, but does not include the column position of the "1" in the parity portion of the low density parity check matrix.
Taking the code word of table 1 as an example,number of check bitsNumber of information bitsThe position of the middle 1 of the last column。
First row number in table 1:
528 、689、 768、 1333、 4402 、5010
each digit representing the first row (corresponding to the first check bit) in the low density parity check matrix) A position of middle "1" (i.e., a position of a column), but this position does not include a position of a column of "1" of the check portion of the low density parity check matrix.
The number of the row isRepresents the first bit in the first check bit blockThe position of the "1" in row 0 of the check matrix is represented (i.e., the position of the column, which also starts counting with 0).
Then there are:
after this is done, there is, according to equation (1):
the next second row of numbers:
441 695 1268 1778 2308 5044
and the rest of the rows are analogized according to the formula (1) and are not listed.
As described in step S5, the accumulated parity bits are interleaved.
Specifically, the method comprises the following steps: and interleaving the accumulated check bits according to a permutation format, wherein the permutation format is realized by the following formula:
wherein i =0, 1, 2, 3, … …, q-1.
Taking Table 1 as an example, the code length is 15120 and the code rate is1/2, code table with the size of the circular sub-array being 126 × 126. At this time, the process of the present invention,，，。
the interleaving process specifically includes:
in this embodiment, the toneDenotes the check bits before interleaving;
{denotes the interleaved check bits.
As shown in step S6, the parity bits after interleaving are modulo-2 added to obtain the final parity bits.
Specifically, this step is realized by the following formula:
wherein,represents the position of the second "1" in the last column of the parity check part in the low density parity check matrix.
ObtainedNamely the finally coded check bit, and the finally obtained LDPC code。
Table 1 below shows a code table with a code length 15120, a code rate 1/2, and a cyclic sub-array size 126 × 126.
In summary, the dual diagonal structure (before interleaving) of the low density parity check matrix check part adopted in the embodiments of the present invention is characterized in that: there is a 1 in the upper right corner of the matrix of the check portion (i.e., the last column of the first row) and a 1 in the middle of the last column (the k-th row, the number of rows starting from 0). Based on such a structure, the bits of the parity part can be obtained by using the bit and parity equations of the information part without using a coding matrix, thereby reducing the coding complexity.
Although the present invention has been described with reference to the preferred embodiments, it is not intended to limit the present invention, and those skilled in the art can make variations and modifications of the present invention without departing from the spirit and scope of the present invention by using the methods and technical contents disclosed above.
Claims (6)
1. A method for encoding a low density parity check matrix, comprising the steps of:
setting the size of a check part in the low-density parity check matrix and the size of a cyclic sub-matrix;
initializing each check bit corresponding to the check part;
grouping the check bits according to the size of the cyclic subarray to obtain a plurality of check bit groups;
accumulating the check bits in each check bit group and the information bits related to the check bits in the low-density parity check matrix;
interleaving each accumulated check bit;
and performing modulo-2 addition operation on each check bit subjected to interleaving processing to obtain a final check bit.
2. The method of encoding a low density parity check matrix according to claim 1, wherein the check portion has a size M x M and the cyclic sub-matrix has a size q x q; the grouping the check bits according to the size of the cyclic sub-array to obtain a plurality of check bit groups comprises:
setting said check bits to a}；
And grouping the check bits by taking q bits as a group in sequence to obtain a plurality of check bit groups.
3. The method for encoding a low density parity check matrix according to claim 1, wherein accumulating the check bits in each check bit group with the information bits associated therewith in the low density parity check matrix comprises:
for q bits in each check bit groupThe following XOR operation is performed:
=(ii) a Wherein,；represented in a low density parity check matrixThe associated information bits are then transmitted to the receiver,
obtained according to the following formula:
wherein x represents a position of a column in which "1" in a row in the low density parity check matrix represented by the first check bit in each check bit group is located, but does not include a position of a column of "1" in a parity part in the low density parity check matrix.
4. The method of encoding a low density parity check matrix according to claim 3, wherein the interleaving the accumulated check bits comprises:
and interleaving the accumulated check bits according to a permutation format, wherein the permutation format is realized by the following formula:
wherein i =0, 1, 2, 3, … …, q-1; q = M/Q;
{denotes the check bits before interleaving;
{denotes the interleaved check bits.
5. The method of encoding a low density parity check matrix according to claim 4, wherein performing modulo-2 addition on each interleaved check bit to obtain a final check bit is implemented by the following equation:
wherein,represents the position of the second "1" in the last column of the parity check part in the low density parity check matrix; said final check bit is}。
6. The method for encoding a low density parity check matrix according to claim 1, further comprising the following steps before initializing the check bits corresponding to the check portion:
setting a position of a second "1" in a last column of the parity part in the low density parity check matrix.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201310371629.2A CN104426553B (en) | 2013-08-23 | 2013-08-23 | The coding method of low-density parity check (LDPC) matrix |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201310371629.2A CN104426553B (en) | 2013-08-23 | 2013-08-23 | The coding method of low-density parity check (LDPC) matrix |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN104426553A true CN104426553A (en) | 2015-03-18 |
| CN104426553B CN104426553B (en) | 2017-07-28 |
Family
ID=52974620
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201310371629.2A Active CN104426553B (en) | 2013-08-23 | 2013-08-23 | The coding method of low-density parity check (LDPC) matrix |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN104426553B (en) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107919941A (en) * | 2016-10-10 | 2018-04-17 | 深圳超级数据链技术有限公司 | Modulation-demo-demodulation method and device based on overlapping multiplexing |
| WO2018171043A1 (en) * | 2017-03-24 | 2018-09-27 | 中兴通讯股份有限公司 | Processing method and device for quasi-cyclic low density parity check coding |
| US11477065B2 (en) | 2015-04-15 | 2022-10-18 | Zte Corporation | Method and apparatus for code block division |
Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7343539B2 (en) * | 2005-06-24 | 2008-03-11 | The United States Of America As Represented By The United States National Aeronautics And Space Administration | ARA type protograph codes |
| CN101453220A (en) * | 2007-12-03 | 2009-06-10 | 华为技术有限公司 | Weaving and coding method for duplicate accumulation code encoding, corresponding equipment |
| CN101521511A (en) * | 2008-02-28 | 2009-09-02 | 重庆无线绿洲通信技术有限公司 | Method for constructing and coding multiple irregular RA code |
| CN101635573A (en) * | 2008-07-23 | 2010-01-27 | 电子科技大学 | Quasi-cyclic RA code-based multivariate LDPC code, and implementation device thereof |
| US20130007558A1 (en) * | 2011-06-30 | 2013-01-03 | Fujitsu Limited | Error correcting code decoding device, decoding method, and mobile station apparatus |
-
2013
- 2013-08-23 CN CN201310371629.2A patent/CN104426553B/en active Active
Patent Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7343539B2 (en) * | 2005-06-24 | 2008-03-11 | The United States Of America As Represented By The United States National Aeronautics And Space Administration | ARA type protograph codes |
| CN101453220A (en) * | 2007-12-03 | 2009-06-10 | 华为技术有限公司 | Weaving and coding method for duplicate accumulation code encoding, corresponding equipment |
| CN101521511A (en) * | 2008-02-28 | 2009-09-02 | 重庆无线绿洲通信技术有限公司 | Method for constructing and coding multiple irregular RA code |
| CN101635573A (en) * | 2008-07-23 | 2010-01-27 | 电子科技大学 | Quasi-cyclic RA code-based multivariate LDPC code, and implementation device thereof |
| US20130007558A1 (en) * | 2011-06-30 | 2013-01-03 | Fujitsu Limited | Error correcting code decoding device, decoding method, and mobile station apparatus |
Non-Patent Citations (1)
| Title |
|---|
| 陈兵: "基于DVB-S2标准IRA-LDPC编译码算法的研究", 《万方数据库》 * |
Cited By (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US11477065B2 (en) | 2015-04-15 | 2022-10-18 | Zte Corporation | Method and apparatus for code block division |
| CN107919941A (en) * | 2016-10-10 | 2018-04-17 | 深圳超级数据链技术有限公司 | Modulation-demo-demodulation method and device based on overlapping multiplexing |
| CN107919941B (en) * | 2016-10-10 | 2022-01-25 | 深圳市硅派科技有限公司 | Modulation-demodulation method and device based on overlapping multiplexing |
| WO2018171043A1 (en) * | 2017-03-24 | 2018-09-27 | 中兴通讯股份有限公司 | Processing method and device for quasi-cyclic low density parity check coding |
| US11368169B2 (en) | 2017-03-24 | 2022-06-21 | Zte Corporation | Processing method and device for quasi-cyclic low density parity check coding |
| US11843394B2 (en) | 2017-03-24 | 2023-12-12 | Zte Corporation | Processing method and device for quasi-cyclic low density parity check coding |
Also Published As
| Publication number | Publication date |
|---|---|
| CN104426553B (en) | 2017-07-28 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN109891753B (en) | Method and apparatus for encoding and decoding LDPC code | |
| CN104333390B (en) | A kind of building method of the check matrix of LDPC code and coding method | |
| CN107786306B (en) | Low-code-rate LDPC code word structure and coding method for multi-point cooperative communication system | |
| CN104779961B (en) | A kind of LDPC structure, code word and corresponding encoder, decoder and coding method | |
| CN103944586A (en) | Method for constructing code-rate compatibility QC-LDPC code | |
| CN107786210B (en) | Middle and high code rate LDPC code word structure and coding method for multi-point cooperative communication system | |
| CN102904686A (en) | Construction method of QC-LDPC code used for coding and modulation and coding and modulation method | |
| CN104426553B (en) | The coding method of low-density parity check (LDPC) matrix | |
| CN105024703B (en) | Based on the long LDPC of quasi-cyclic middle short code and codec and coding method | |
| CN111464191A (en) | RC-L DPC code construction method based on matrix expansion and Fibonacci sequence | |
| CN103401655A (en) | LDPC decoding message storage structure and decoding method | |
| CN103427847B (en) | A kind of code construction method of LDPC code | |
| CN104821830B (en) | A kind of LDPC structure, code word and corresponding encoder, decoder and coding method | |
| CN107276595A (en) | LDPC code word and coding method and codec | |
| CN109150192B (en) | LDPC code word structure and code word coding method | |
| CN102811064B (en) | Method for constructing multi-rate low density parity check (LDPC) code | |
| CN105322970B (en) | For the LDPC code word of next-generation radio broadcasting and coding method and codec | |
| CN101789795A (en) | Encoding method based on multi-rate protograph low density parity check code and encoder | |
| CN103199875B (en) | A kind of high efficiency encoding method based on quasi-cyclic LDPC code | |
| CN102386932A (en) | LDPC code constitution method | |
| CN107465414A (en) | The coding method of LDPC code | |
| CN105322971B (en) | For the LDPC code word of next-generation radio broadcasting and coding method and codec | |
| CN107437947A (en) | The coding method of LDPC code | |
| CN105281784B (en) | For the LDPC code word of next-generation radio broadcasting and coding method and codec | |
| CN105471440A (en) | LDPC codes for next generation of wireless broadcast and coding method and coder and decoder thereof |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| CB02 | Change of applicant information |
Address after: Room 1018, block B, No. three East Bridge Road, Pudong New Area, Shanghai, 200125, China Applicant after: Shanghai NERC-DTV National Engineering Research Center Co., Ltd. Address before: 200125 Shanghai East Road, Pudong New Area, No. three, No. 1018 Applicant before: Shanghai NERC-DTV National Engineering Research Center Co., Ltd. |
|
| COR | Change of bibliographic data | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |