CN109286401A - Decoding circuit and method for quasi-cyclic low-density parity check code - Google Patents
Decoding circuit and method for quasi-cyclic low-density parity check code Download PDFInfo
- Publication number
- CN109286401A CN109286401A CN201710595307.4A CN201710595307A CN109286401A CN 109286401 A CN109286401 A CN 109286401A CN 201710595307 A CN201710595307 A CN 201710595307A CN 109286401 A CN109286401 A CN 109286401A
- Authority
- CN
- China
- Prior art keywords
- decoding
- transmission data
- matrix
- block
- sub
- 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.)
- Withdrawn
Links
- 238000000034 method Methods 0.000 title claims abstract description 20
- 230000005540 biological transmission Effects 0.000 claims abstract description 71
- 239000011159 matrix material Substances 0.000 claims abstract description 58
- 238000010586 diagram Methods 0.000 description 9
- 238000005516 engineering process Methods 0.000 description 2
- 239000000463 material Substances 0.000 description 2
- 238000004364 calculation method Methods 0.000 description 1
- 238000004891 communication Methods 0.000 description 1
- 230000007812 deficiency Effects 0.000 description 1
- 238000006073 displacement reaction Methods 0.000 description 1
- 238000004519 manufacturing process Methods 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/1148—Structural properties of the code parity-check or generator matrix
- H03M13/116—Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices
Landscapes
- Physics & Mathematics (AREA)
- Mathematical Physics (AREA)
- Probability & Statistics with Applications (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Error Detection And Correction (AREA)
Abstract
准循环低密度奇偶校验码的解码电路及准循环低密度奇偶校验码的解码方法。解码方法应用于一校验矩阵与多笔传送资料，该校验矩阵包含N个子矩阵。该解码方法利用w个(w<360)解码单元进行解码且包含以下步骤：将对应于一第一子矩阵的一第一区块的w笔传送资料输入该w个解码单元进行解码；以及解码完对应于该第一子矩阵的一第一区块的w笔传送资料后，将对应于一第二子矩阵的一第一区块的w笔传送资料输入该w个解码单元进行解码。
A decoding circuit for a quasi-cyclic low-density parity check code and a decoding method for a quasi-cyclic low-density parity check code. The decoding method is applied to a check matrix and multiple transmission data, wherein the check matrix includes N sub-matrices. The decoding method uses w (w<360) decoding units for decoding and includes the following steps: inputting w transmission data corresponding to a first block of a first sub-matrix into the w decoding units for decoding; and after decoding the w transmission data corresponding to a first block of the first sub-matrix, inputting w transmission data corresponding to a first block of a second sub-matrix into the w decoding units for decoding.
Description
Technical field
The present invention relates to low density parity check codes, especially with respect to quasi-circulating low-density parity check (Quasi-
Cyclic Low-Density Parity-Check) code decoding circuit and its method.
Background technique
Low-density checksum (Low-Density Parity-Check, LDPC) code is usually used in communication system to improve money
The transmission accuracy of material.The firsthand information and generator matrix (Generate matrix, G matrix) that transmission end can will transmit
It is multiplied, generates the transmission data also longer than firsthand information.Receiving end is right according to check matrix (Check matrix, H matrix)
Transmission data is decoded to correct transmission data, to reply firsthand information.In implementation, receiving end be using interative computation come pair
Transmission data is decoded, it follows that the decoding operation of low density parity check code is related to largely calculating, therefore how simultaneous
Caring for circuit cost and operation efficiency becomes the important topic of this field.
Summary of the invention
In view of the deficiency of prior art, a purpose of the present invention is that providing a kind of quasi-cyclic low-density parity check codes
Decoding circuit and its method, to improve operation efficiency.
The invention discloses a kind of decoding circuits of quasi-cyclic low-density parity check codes, include: a memory, store a school
Matrix and more transmission data are tested, wherein the check matrix includes N number of submatrix；W decoding unit, wherein w < 360；And one
Controller couples the memory and the w decoding unit, and wherein the controller will be passed according to following order according to the check matrix
Send the data input w decoding unit to be decoded: the w pen that will correspond to one first block of one first submatrix transmits data
The w decoding unit is inputted to be decoded；And the w pen transmission money of one first block corresponding to first submatrix is decoded
After material, the w pen transmission data input w decoding unit for corresponding to one first block of one second submatrix is decoded.
A kind of another bright coding/decoding method for disclosing quasi-cyclic low-density parity check codes of this hair is applied to a check matrix and more
Pen transmission data, the check matrix include N number of submatrix.The coding/decoding method be decoded using w (w < 360) decoding units and
Comprise the steps of: by correspond to one first submatrix one first block w pen transmission the data input w decoding unit into
Row decoding；And decoded corresponding to first submatrix one first block w transmission data after, will correspond to one second
W pen transmission data input w decoding unit of one first block of submatrix is decoded.
Compared to traditional technology, the decoding circuit and its method of quasi-cyclic low-density parity check codes of the invention use essence
The circuit of letter completes decoding operation, and takes into account efficiency.
Detailed description of the invention
For the above objects, features and advantages of the present invention can be clearer and more comprehensible, below in conjunction with attached drawing to tool of the invention
Body embodiment elaborates, in which:
Fig. 1 is the schematic diagram of the decoding circuit in the LDPC decoder according to depicted in one embodiment of the invention；
Fig. 2 is the decoding scheduling schematic diagram of a check matrix H according to depicted in one embodiment of the invention；
Fig. 3 is the schematic diagram of the decoding circuit in the LDPC decoder according to depicted in another embodiment of the present invention；
Fig. 4 A~4C is the decoding scheduling schematic diagram of a check matrix H according to depicted in one embodiment of the invention；And
Fig. 5 is the flow chart of an embodiment of the coding/decoding method of quasi-cyclic low-density parity check codes of the present invention.
Symbol description:
101,301 memory
102,302 controller
103,303 decoding unit
I1-1~I1-4, I2-1~I2-4, I10-1~I10-4 submatrix
B1, B2, B3 block
S510~S560 step
Specific embodiment
Disclosure of the invention includes the decoding circuit and its method of quasi-cyclic low-density parity check codes.It is being embodied as
Under the premise of possible, the art tool usually intellectual can select equivalent element according to the disclosure of this specification
Or step realizes the present invention, that is, implementation of the invention be not limited to after the embodiment chatted.
Under the considering of decoding efficiency, LDPC decoder mostly uses greatly the framework of parallel calculation.For example, quasi- circulation is low
The check matrix of density parity check code (Quasi-Cyclic Low-Density Parity-Check, QC-LDPC) includes more
A submatrix is the unit matrix (identity matrix) of 360*360, therefore QC-LDPC decoder mostly uses 360 groups
Identical decoding circuit carries out parallel decoding operation to check matrix.
Referring to Fig. 1, Fig. 1 is the decoding circuit 100 in the LDPC decoder according to depicted in one embodiment of the invention
Schematic diagram.As shown in Figure 1, decoding circuit 100 includes a memory 101, a controller 102 and 360 groups of decoding units
103-1~103-360.Memory 101 stores a check matrix H and more transmission data, and controller 102 is according to check matrix
H, once by correspond to a submatrix 360 transmission data input respectively 360 groups of decoding unit 103-1~103-360 into
Row decoding is to generate revised data；Then, revised transmission data is stored back to memory 101 again by controller 102, with complete
Secondary amendment of this 360 transmission data in pairs.Decoding unit 103-1~103-360 can be multiple processing cores or one
Multiple engines of a special application integrated circuit (application-specific integrated circuit, ASIC)
(engine), but not limited to this.About the implementation of controller 102, how transmission data is carried out with decoding unit 103
Decoding and implementation are known technology, and are not described in detail herein.
For example, referring to Fig. 2, the decoding that Fig. 2 is a check matrix H according to depicted in one embodiment of the invention is arranged
Journey schematic diagram.As shown in Fig. 2, check matrix H can be divided into 10 column in the longitudinal direction as unit of submatrix, check matrix H is with son
Matrix is that each column of unit include 4 submatrixs, and wherein submatrix can be unit matrix (shifted identity after a displacement
matrix).For example, the 1st column in check matrix H as unit of submatrix (that is, the 0th~359 column of check matrix H)
Comprising submatrix I1-1~I1-4, the 2nd column in check matrix H as unit of submatrix (that is, the 360th of check matrix H~
719 column) it include submatrix I2-1~I2-4, and so on.In other words, it includes 10*4 submatrix that check matrix H, which has altogether,
His element is " 0 ".In the present embodiment, controller 102 can be according to decoding scheduling { an I1-1~I1-4, I2-1~I2-
4 ..., I10-1~I10-4 }, 360 transmission data corresponding to submatrix are inputted into 360 groups of decoding unit 103- respectively every time
1~103-360 is decoded, to complete primary amendment to transmission data.
After transmission data has been corrected once according to above-mentioned decoding scheduling, decoding circuit 100 exports revised transmission
Data a to checking circuit (is not painted), to judge whether revised transmission data restrains.If not converged, decoding circuit 100
Transmission data is modified again according to above-mentioned decoding scheduling, until the convergence of revised transmission data.
In one embodiment, the quantity of the decoding unit in decoding circuit is smaller than 360, to reduce the manufacture of decoding circuit
Cost.For example, referring to Fig. 3, Fig. 3 is the decoding in the LDPC decoder according to depicted in another embodiment of the present invention
The schematic diagram of circuit 300.As shown in figure 3, decoding circuit 300 includes a memory 301, a controller 302 and w (w < 360)
Group decoding unit 303-1~303-w.In one embodiment, the quantity of the decoding unit in decoding circuit 300 is decoding circuit
The q/p of the quantity of decoding unit in 100, i.e. w=360 × q/p, wherein p, q are relatively prime, q/p < 1, and p is 360 factor.
However, the decoding scheduling of check matrix must especially be set when the quantity of decoding unit in decoding circuit is less than 360
Meter, otherwise will affect decoding efficiency.For example, Fig. 4 A~4C is please referred to, Fig. 4 A~4C is according to one embodiment of the invention
The decoding scheduling schematic diagram of a depicted check matrix H.Assuming that w=240 (that is, q=2 and p=3), then such as Fig. 4 A~4C institute
Show, the one first block B1 (as shown in the oblique line block of Fig. 4 A) of each submatrix includes the 1st~240 column of submatrix, each
The one second block B2 (as shown in the oblique line block of Fig. 4 B) of submatrix includes the 121st~360 column of submatrix, each submatrix
A third block B3 (as shown in the oblique line block of Fig. 4 C) include submatrix the 1st~120 and the 241st~360 arrange.
In the present embodiment, controller 302 is a processor, but the present invention is not limited thereto, in other embodiments,
Controller 302 also can for a special application integrated circuit (Application-specific integrated circuit,
ASIC), a programmable gate array (Field Programmable Gate Array, FPGA) or a Digital Signal Processing
Device, (digital signal processor, DSP).Fig. 5 is the coding/decoding method of quasi-cyclic low-density parity check codes of the present invention
An embodiment flow chart.Below in conjunction with the decoding scheduling of Fig. 5 explanatory diagram 4A~4C.Firstly, controller 302 chooses first
Block B1 (step S510), then controller 302 according to one decoding scheduling I1-1~I1-4, I2-1~I2-4 ..., I10-1~
I10-4 }, 240 transmission data corresponding to the first block B1 by submatrix input 240 groups of decoding unit 303- respectively every time
1~303-240 is decoded (step S520~S540 is executed 40 times).Then, controller 302 is decoded according to not completing still
The second block B2 (step S510) is chosen in one judgement (step S550) of block, and further in accordance with a decoding scheduling { I1-1~I1-
4, I2-1~I2-4 ..., I10-1~I10-4 }, 240 transmission data corresponding to the second block B2 by submatrix are divided every time
240 groups of decoding unit 303-1~303-240 are not inputted is decoded (i.e. step S520~S540 is executed 40 times).Then, it controls
Device 302 chooses third block B3, and further in accordance with a decoding according to still there is the judgement (step S550) for not completing decoded block
Scheduling { I1-1~I1-4, I2-1~I2-4 ..., I10-1~I10-4 }, every time corresponding to the third block B3 by submatrix
240 transmission data input 240 groups of decoding unit 303-1~303-240 respectively and are decoded (i.e. step S520~S540 execution
40 times), it finally exports revised transmission data (step S560) a to checking circuit and (is not painted), to judge revised biography
Send whether data restrains.If not converged, decoding circuit 100 is again modified transmission data according to above-mentioned decoding scheduling, directly
Until the convergence of revised transmission data.
It is worth noting that, just being exported revised after the primary amendment of completion every compared to 102 pairs of transmission data of controller
Transmission data carries out convergent judgement, and controller 302 is just exported revised after to the every completion modified twice of transmission data
Transmission data carries out convergent judgement, in this way, which convergent judgement number can be reduced, accelerates the convergence rate of transmission data,
Improve decoding efficiency.
In addition, will not continuously be decoded for the transmission data corresponding to identity element in check matrix H " 1 "
(such as 240 groups of decoding unit 303-1~303-240 first sequentially respectively to the first, second, third block B1 of submatrix I1-1,
240 transmission data corresponding to B2, B3 are decoded, then sequentially respectively to the first, second, thirdth area of submatrix I1-2
240 transmission data corresponding to block B1, B2, B3 are decoded, and so on), lead to invalid decoding.
Furthermore every time when decoding, controller 302 will not input the transmission data corresponding to different submatrixs to 240 groups of solutions
Code unit 303-1~303-240 (such as input corresponding to matrix I1-1 120 transmission data to decoding unit 303-1~
303-120, input correspond to 120 transmission data of matrix I1-2 to decoding unit 303-121~303-240, come while right
Transmission data corresponding to different submatrixs is decoded), to improve decoding efficiency.In more detail, since transmission data exists
The location mode of memory 301 is designed, when reading or being stored in transmission data corresponding to same submatrix, it is only necessary to storage
Device 301 carries out primary access, and when taking out or being stored in transmission data corresponding to different submatrixs, need to memory 301 into
The access of row more than once.Therefore, if 240 groups of decoding unit 303-1~303-240 are simultaneously to biography corresponding to 2 submatrixs
Data is sent to be decoded, controller 302 must carry out 4 accesses to memory 301 and (access 2 times when reading, when deposit accesses 2
It is secondary), in this way, lessen the decoding efficiency of decoding circuit 300.
The columns of above-mentioned check matrix H and each submatrix number for including that arranges are non-for limiting this hair only to illustrate
It is bright.
Due to the art, tool usually intellectual can understand this case by the disclosure of the device inventions of this case
Method invention implementation detail and variation, thus while the embodiment of the present invention as described above, however these embodiments be not
For limiting the present invention, the art tool usually intellectual according to the present invention can express or implicit content is to the present invention
Technical characteristic impose variation, all this kind variation may belong to patent protection scope sought by the present invention, in other words, this
The scope of patent protection of invention must regard subject to the claim institute defender of this specification.
Claims (8)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201710595307.4A CN109286401A (en) | 2017-07-20 | 2017-07-20 | Decoding circuit and method for quasi-cyclic low-density parity check code |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201710595307.4A CN109286401A (en) | 2017-07-20 | 2017-07-20 | Decoding circuit and method for quasi-cyclic low-density parity check code |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN109286401A true CN109286401A (en) | 2019-01-29 |
Family
ID=65184313
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201710595307.4A Withdrawn CN109286401A (en) | 2017-07-20 | 2017-07-20 | Decoding circuit and method for quasi-cyclic low-density parity check code |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN109286401A (en) |
Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20070157062A1 (en) * | 2006-01-03 | 2007-07-05 | Broadcom Corporation, A California Corporation | Implementation of LDPC (Low Density Parity Check) decoder by sweeping through sub-matrices |
| TW201123745A (en) * | 2009-12-31 | 2011-07-01 | Nat Univ Tsing Hua | Low density parity check codec and method of the same |
| US8607116B2 (en) * | 2011-03-29 | 2013-12-10 | Mstar Semiconductor, Inc. | Readdressing decoder for quasi-cyclic low-density parity-check and method thereof |
| US20140223254A1 (en) * | 2013-02-01 | 2014-08-07 | Samsung Electronics Co., Ltd. | Qc-ldpc convolutional codes enabling low power trellis-based decoders |
| TW201717208A (en) * | 2015-11-05 | 2017-05-16 | 大心電子股份有限公司 | Decoding method, memory storage device and memory control circuit unit |
-
2017
- 2017-07-20 CN CN201710595307.4A patent/CN109286401A/en not_active Withdrawn
Patent Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20070157062A1 (en) * | 2006-01-03 | 2007-07-05 | Broadcom Corporation, A California Corporation | Implementation of LDPC (Low Density Parity Check) decoder by sweeping through sub-matrices |
| TW201123745A (en) * | 2009-12-31 | 2011-07-01 | Nat Univ Tsing Hua | Low density parity check codec and method of the same |
| US8607116B2 (en) * | 2011-03-29 | 2013-12-10 | Mstar Semiconductor, Inc. | Readdressing decoder for quasi-cyclic low-density parity-check and method thereof |
| US20140223254A1 (en) * | 2013-02-01 | 2014-08-07 | Samsung Electronics Co., Ltd. | Qc-ldpc convolutional codes enabling low power trellis-based decoders |
| TW201717208A (en) * | 2015-11-05 | 2017-05-16 | 大心電子股份有限公司 | Decoding method, memory storage device and memory control circuit unit |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Ferraz et al. | A survey on high-throughput non-binary LDPC decoders: ASIC, FPGA, and GPU architectures | |
| CN104868925B (en) | Encoding method, decoding method, encoding device and decoding device of structured LDPC code | |
| US20180357530A1 (en) | Deep learning decoding of error correcting codes | |
| US10536169B2 (en) | Encoder and decoder for LDPC code | |
| KR102019893B1 (en) | Apparatus and method for receiving signal in communication system supporting low density parity check code | |
| US20190149168A1 (en) | Systems and methods for decoding error correcting codes | |
| CN109586731B (en) | System and method for decoding error correction codes | |
| CN109560818A (en) | Improved minimum and decoding for LDPC code | |
| CN105049061A (en) | Advanced calculation-based high-dimensional polarization code decoder and polarization code decoding method | |
| US8843810B2 (en) | Method and apparatus for performing a CRC check | |
| CN101335592B (en) | High speed LDPC decoder implementing method based on matrix block | |
| CN107239362B (en) | Parallel CRC (Cyclic redundancy check) code calculation method and system | |
| CN109787639A (en) | System and method for decoding and error code | |
| CN105553485B (en) | BCH coding and decoding device and its decoding method based on FPGA | |
| CN103886915A (en) | Circuitry and method for correcting 3-bit errors containing adjacent 2-bit error | |
| CN106936444A (en) | One kind set interpretation method and set decoder | |
| CN112953554B (en) | LDPC decoding method, system and medium based on layered confidence propagation | |
| CN101273532B (en) | Decoding device and receiving device | |
| CN120958728A (en) | Dedicated hardware device for decoding non-binary polarization codes | |
| CN115664899A (en) | A channel decoding method and system based on graph neural network | |
| CN103793289B (en) | Circuitry and method for multi-bit correction | |
| CN108141227A (en) | The check-node of nonbinary LDPC decoder and corresponding method | |
| CN109286401A (en) | Decoding circuit and method for quasi-cyclic low-density parity check code | |
| CN102347775B (en) | PLDA (parallel layered decoding algorithm)-based LDPC (low density parity check) decoder | |
| CN102412844A (en) | Decoding method and decoding device for IRA (irregular repeat-accumulate) LDPC (Low Density parity check) codes |
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 | ||
| TA01 | Transfer of patent application right |
Effective date of registration: 20200413 Address after: No.1, Duhang 1st Road, Hsinchu City, Hsinchu Science Park, Taiwan, China Applicant after: MEDIATEK Inc. Address before: 1/2, 4th floor, 26 Taiyuan Street, Zhubei City, Hsinchu County, Taiwan, China Applicant before: MStar Semiconductor, Inc. |
|
| TA01 | Transfer of patent application right | ||
| WW01 | Invention patent application withdrawn after publication |
Application publication date: 20190129 |
|
| WW01 | Invention patent application withdrawn after publication |