 |
|
|
|
|
|
 Title: |
US6789227:
System and method for generating low density parity check codes using bit-filling
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
De Souza, Jorge Campello; San Jose, CA
Modha, Dharmendra Shantilal; San Jose, CA
Rajagopalan, Sridhar; San Jose, CA
|
| Assignee: |
International Business Machines Corporation, Armonk, NY
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
2004-09-07
/ 2001-07-05
|
| Application Number: |
US2001000899459
|
| IPC Code: |
Advanced:
H03M 13/03;
H03M 13/05;
H03M 13/11;
H03M 13/25;
Core:
H03M 13/00;
IPC-7:
G06F 11/00;
|
| ECLA Code: |
H03M13/03T; G06F11/10M; H03M13/11;
|
| U.S. Class: |
714/804;
714/800;
714/758;
|
| Field of Search: |
714/804
|
| Priority Number: |
| 2001-07-05 |
US2001000899459 |
|
| Abstract: |
A computer-implemented system and method is for generating low-density parity check (LDPC) codes. One aspect of the invention includes a method for generating high rate LDPC codes that first constructs a matrix (H) of size mxn having m rows of check nodes and n columns of bit nodes. The matrix meets the following requirements: the weight of the j<-th >column equals aj; each row, r, has weight at most br; and the matrix H can be represented by a Tanner graph that has a girth of at least g>=g. The method then iteratively adds an (n+1)<th >column (U1) to matrix H, wherein the size of U1, is initially empty and is at most an+1, and wherein U1, comprises a set of i check nodes such that i is greater than or equal to 0 and i is less than an+1. The method then iteratively adds check nodes to U1. such that each check node does not violate predetermined girth and check-degree constraints. The matrix H is updated when a new column is added. The iterations are terminated if there are no new check nodes that do not violate the girth and check-degree constraints. The method can be modified to optimize various parameters, including the following cases: maximizing the rate for a fixed girth; maximizing the girth for a fixed rate; and maximizing the rate for a fixed girth and fixed length.
|
| Attorney, Agent or Firm: |
Rogitz, John L. ;
|
| Primary / Asst. Examiners: |
Decady, Albert; Trimmings, John P
|
| Maintenance Status: |
E1 Expired Check current status
|
| INPADOC Legal Status: |
Show legal status actions
Family Legal Status Report
|
| Family: |
Show 2 known family members
|
First Claim:
Show all 16 claims |
What is claimed is:
1. A computer-implemented method for generating low-density parity check (LDPC) codes comprising:
- (a) constructing an m×n matrix H having m rows of check nodes and n columns of bit nodes, wherein the jth column has weight aj, each row, r, has a weight at most br the matrix H is representable by a Tanner graph having a girth g;
- (b) iteratively adding an (n+1)th column (U1) to matrix H, wherein the size of U1 is initially empty and is at most an+1, and wherein U1 comprises a set of i check nodes such that i is greater than or equal to 0 and i is less than an+1 ;
- (c) iteratively adding check nodes to U1 such that each check node does not violate predetermined girth constraint g, and check-degree constraint deg (c)<b(c);
- (d) updating matrix H when a new column is added; and
- (e) terminating the iterations if there are no new check nodes that do not violate the girth and check-degree constraints.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 23 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other Abstract Info: |
DERABS C2003-289033
|
| Other References: |
"Comparison of Constructions of Irregular Gallager Codes", David J. C. MacKay et al., Oct., 1999, IEEE Transactions of Communications, vol. 47 No. 10, pp 1449-1454.*
(6 pages)
Cited by 5 patents
[ISI abstract]
"A heuristic Search for Good Low-Density Parity-Check Codes at Short Block Lengths", Yongyi Mao, Jun. 11-14, 2001, IEEE International Conference on Communications, vol. 1, pp 41-44.*
"Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes", Thomas J. Richardson et al., Feb., 2001, IEEE Transactions on Information Theory, vol. 47, No. 2, pp 619-637.*
(19 pages)
Cited by 11 patents
[ISI abstract]
"Low Density Parity Check Codes: Construction Based on Finite Geometries", Yu Kow et al., IEEE Conference on Global Communications, Nov. 27 to Dec. 1, 2000, vol. 2, pp 825-829.*
"Improved Low- Density Parity-Check Codes Using Irregular Graphs", Michael G. Luby et al., Feb., 2001, IEEE Transactions on Information Theory, vol. 47, No. 2, pp 585-596.*
(14 pages)
Cited by 3 patents
[ISI abstract]
"Efficient Encoding of Low-Density Parity-Check Codes", Thomas J. Richardson et al., Feb., 2001, IEEE Transactions on Information Teory, vol. 47, No. 2, pp 638-656.*
(19 pages)
Cited by 16 patents
[ISI abstract]
"Construction of LDPC Codes Using Ramanjan Graphs and Ideas from Margulis", Joachim Rosenthal et al., Oct. 3, 2000, Procedures of 38th Allerton Conference on Communication, Control and Computing, Monticello, Illinois.*
"Parallel Decoding Architectures for Low Density Parity Check Codes", C. Howland, IEEE International Symposium on Circuits and Systems2001, May 6-9, 2001, pp 742-745.
|
|
 Nominate this for the Gallery...
|
|
