Error detection/correction and fault detection/recovery – Pulse or data error handling – Error/fault detection technique
Reexamination Certificate
2001-07-05
2004-09-07
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Error/fault detection technique
C714S800000, C714S758000
Reexamination Certificate
active
06789227
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to data error detection and correction, and more particularly to a system and method of generating low density parity check (LDPC) codes using a bit filling technique.
2. Description of the Related Art
It is well known that the probability of errors in digital data transmission increases as the signal-to-noise ratio worsens. Since it is not always practical to reduce noise in the transmission path, techniques for dealing with errors in a received signal have been developed. Many of these techniques, referred to as error control codes, involve the transmission of redundant digits, which do not themselves convey information but make it possible for errors to be controlled at the receiver. Some error control codes detect errors and some detect and correct errors.
One class of error correction codes (ECCs) that both detect and correct errors is known as the “Hamming Codes”, which are widely used for error detection and correction in digital communications data storage systems. The Hamming Codes are capable of detecting multiple bit errors and correcting single bit errors. Another well known ECC algorithm is the “Reed-Solomon code”, widely used for error correction in the compact disk industry. The Reed-Solomon code is able to correct multiple errors per word. Other conventional ECC algorithms include the “b-adjacent” error correction code, and the “odd weight column” code.
One example of an application of an error correction technique commonly used for computer memory systems is known as a Redundant Array of Independent Disks (RAID), wherein a number of small disk drives are used to store data with the data being spread across a number of the disk drives. When data is received from a host computer by a RAID controller, it typically arrives in 8-bit byte form, with a ninth, parity bit for each byte. The controller writes the data across a number of disks, putting different blocks of data in different disks. As the RAID controller writes the data it will typically generate a check code, such as a Cyclic Redundancy Check (CRC). This is basically an exclusive OR (XOR) of each bit position in successive bytes throughout a sector. Another example is linear parity, which is an exclusive OR function of successive words of any convenient length. The aforementioned Reed Solomon codes may also be used in RAID systems.
In addition to these check codes, the RAID controller also provides a parity calculation. The parity is the exclusive OR of the data blocks in each disk drive, with the exclusive OR being a parity block which is stored on a separate parity disk. The parity calculation is usually done not only on the data itself, but also on the check codes, which are stored with the data on each disk drive.
One type of error correction utilizes Low Density Parity Check (LDPC) Codes, which were first introduced in 1963. Initial approaches of designing LDPC codes used a construction that had a fixed weight for all the columns of the parity-check matrix. Recently, it has been shown that LDPC codes can perform very close to the Shannon capacity limit when their associated Tanner graphs posses certain desirable properties. Tanner graphs are bipartite graphs that can be used to represent a parity check matrix of LDPC codes. One desirable property is that Tanner graphs have a large “girth”, which is the smallest cycle in the graph. This is important because when decoding LDPC codes using the sum-product decoding algorithm, the number of independent iterations of the algorithm is proportional to the girth of the Tanner graph corresponding to the code. Another desirable property is high “rate”. For a code with a parity check matrix having m rows and n columns, the rate, R, is given by
R
=
(
n
-
m
)
n
.
U.S. Pat. Nos. 4,295,218 and 3,542,756, both of which are incorporated herein by reference, disclose decoding methods with which the present invention can be used.
Various recent approaches to designing LDPC codes include the use of a fixed girth parity check matrix with a random construction, the design of irregular graphs using random constructions and linear programming, as well as the design of LDPC codes using either array codes, Steiner designs or finite geometries.
The above-discussed techniques for designing LDPC codes typically have exponential time complexity. As a result, they can only be made to work for small parity check column weights and for small girth values. Also, the prior techniques also do not usually yield a satisfactorily high rate. Furthermore, these techniques do not offer sufficient flexibility to permit one to choose codes with certain fixed values, such as girth, and then design the codes with various other desirable parameters optimized. As a result, using conventional techniques cannot choose to trade-off, for example, bit error rate performance against the code rate. An added feature of our technique is that cycles are only formed if necessary. The algorithm starts out using a large girth constraint,
, and then decreases the girth constraint as needed throughout the execution of the algorithm. As a result, the girth is always as high as possible, and the number of short cycles formed is small.
The present invention has carefully considered the above problems and has provided the solution set forth herein.
SUMMARY OF THE INVENTION
A computer-implemented system and method is disclosed 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 m×n 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 a
j
; each row, r, has weight at most b
r
; and the matrix H can be represented by a Tanner graph that has a girth g≧
g
. The method then iteratively adds an (n+1)
th
column (U
1
) to matrix H, wherein the size of U
1
g
is initially empty and is at most a
n+1
, and wherein U
1
comprises a set of i check nodes such that i is greater than or equal to 0 and i is less than a
n+1
. The method then iteratively adds check nodes to U
1
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.
In accordance with another aspect of the invention an LDPC code generator is provided for creating LDPC codes for use in an LDPC error correcting system that includes an LDPC encoder that receives digital data and encodes said data using the LDPC codes. The LDPC code generator includes a unit for generating an m×n matrix (H) having m rows of check nodes and n columns of bit nodes, wherein the weight of the j
th
column is a
j
, each row, r, has weight at most b
r
, and wherein the matrix H can be represented by a Tanner graph that has a girth of at least g≧
g
. The LDPC code generator also includes a processing module for iteratively adding (n+1)
th
columns (U
1
) to matrix H, wherein the size of U
1
is initially empty and is at most a
n+1
, and wherein U
1
comprises a set of i check nodes such that i is greater than or equal to 0 and i is less than a
n+1
. Another processing module iteratively adds check nodes to U
1
such that each check node does not violate predetermined girth and check-degree constraints. An additional processing module updates matrix H when a new column is added and another processing module terminates the iterations if there are no new check nodes that do not violate the girth and check-degree constraints, or if the desired number of bit nodes has been added.
The details of the present invention,
Campello De Souza Jorge
Modha Dharmendra Shantilal
Rajagopalan Sridhar
De'cady Albert
Rogitz John L.
Trimmings John P
LandOfFree
System and method for generating low density parity check... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for generating low density parity check..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for generating low density parity check... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3249521