Error detection/correction and fault detection/recovery – Pulse or data error handling – Error/fault detection technique
Reexamination Certificate
2002-09-18
2004-08-31
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Error/fault detection technique
Reexamination Certificate
active
06785863
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to encoding data and in particular, to a method and apparatus for encoding data utilizing low-density parity-check (LDPC) codes.
BACKGROUND OF THE INVENTION
An LDPC code is a linear block code specified by a parity-check matrix H. In general, an LDPC code is defined over a Galois Field GF(q), q≧2. If q=2, the code is a binary code. As with all linear block codes, a k-bit information block S
1×k
is generally encoded by the code generator matrix G
k×n
to become an n-bit codeword X
1×n
, and the code rate is r=k
. The codeword x is transmitted through a noisy channel, and the received signal vector y is passed to the decoder to estimate the information block s
1×k
.
Given an n-dimensional space, the rows of G span the k-dimensional codeword subspace C, and the rows of the parity-check matrix H
m×n
span the m-dimensional dual space C
⊥
, where m=n−k. Since x=sG and GH
T
=0, it follows that xH
T
=0 for all codewords in subspace C, where “T” denotes matrix transpose. In the discussion of LDPC codes, this is generally written as
Hx
T
=0
T
, (1)
where 0 is a row vector of all zeros, and the codeword x
T
is:
x
T
=
[
p
1
⋮
p
n
-
k
s
1
⋮
s
k
]
;
where,
p
1
, . . . p
n−k
are the parity check bits; and
s
1
, . . . s
k
are the systematic bits, equal to the information bits within the information block.
In order to use an LDPC code with good error-correcting performance, an appropriate low-density parity-check matrix H has to be defined. For most irregular LDPC codes, this requires making a large portion of the columns of H to be weight-2 (i.e., two ones in a column) in order to keep the overall density low (i.e., the overall matrix should be sparse). This large number of weight-2 columns can allow high weights (e.g., 30) to be assigned to some columns while still maintaining a low average column weight in H. (Note that the row weights are usually limited in range and are relatively small.)
Designing a parity-check matrix with various row and column weights is complicated when error performance is considered. For example, a matrix can be constructed with a series of randomly generated columns while satisfying the row weight and column weight constraints, however, with a large percentage of weight-2 columns in the matrix, randomly-generated weight-2 columns can easily contain a bad structure which induces an undetectable error event and a low minimum distance. In general, an undetectable error event of N
ud
bits could happen if N
ud
columns of the parity-check matrix sum (modulo 2) to the all-zero column. The all-zero column summation occurs with higher frequency when the parity-check matrix has a small size and contains weight-2 columns. The undetectable error event is directly linked to the minimum distance of the code which is equal to min(N
ud
). As a result, a randomly-generated parity-check matrix can have a small minimum distance, which causes a high probability of undetectable errors and an error floor at high signal-to-noise ratios. Furthermore, since code bits (elements of x) associated with weight-2 columns are much more prone to errors than code bits associated with higher-weight columns, a large percentage of undetectable frame errors is expected to involve weight-2 columns. Although there are several prior-art code construction guidelines cited or implied in literature such as (a) avoiding cycles of length 4 and (b) avoiding overlap between weight-2 columns when possible, these guidelines may not be sufficient for good error performance codes. Therefore, there is a need for deterministic distribution of weight-2 columns in which the occurrence of undetected frame errors is reduced in order to significantly enhance code performance in comparison to a randomly-constructed parity-check matrix.
Notwithstanding the above problem, another issue of LDPC codes is the high encoding complexity of the straightforward method using the generator matrix G corresponding to the H matrix defining the code. For a systematic LDPC encoder, parity check bit p
i
, i=1, . . . , m, is generally computed from the given information bits, s
1
, . . . , s
k
, m=n−k. Letting the codeword be x=[p
1
, . . . , p
m
, s
1
, . . . , s
k
], the parity check bits satisfy the parity-check equations of (1). A conventional encoding method transforms the parity-check matrix H into a systematic form H
sys
=[I
m×m
, P
T
] through Gaussian elimination and column reordering so that the corresponding code generator matrix is G=[P
k×m
, I
k×k
]. Therefore, the conventional encoder calculates the parity check bits using
└p
1
, . . . , p
m
┘=└s
1
, . . . , s
k
┘P. (2):
This straightforward method can cause implementation problems especially when the codeword size n is large. First, although H has low density (i.e., with a few 1's in the matrix and the number of 1's per row not growing with n), P and hence G usually have high density (i.e., many 1's in the matrix and the number of 1's per row increasing as n increases). Implementing the conventional encoder can require a large amount of memory to store the positions of the 1's in P. Secondly, due to the high density of P, the number of binary additions (only counting the terms when the elements of P are ‘1’) is on the order of n
2
; implying that the encoding complexity grows quadratically with n. Therefore, there is a need for an efficient encoder for irregular LDPC codes that takes advantage of the structure of a good performing irregular LDPC code to minimize preprocessing and admit a simple encoding program.
REFERENCES:
patent: 4939733 (1990-07-01), Furutani
patent: 6219817 (2001-04-01), Holman
patent: 6567465 (2003-05-01), Goldstein et al.
Blansksby, A.J. & Howland, C.J. “A 690-m W 1-Gb/s 1024-b, Rate-1/2 Low-Density Parity-Check Code Decoder” IEEE Journal of Solid-State Circuits, vol. 37, No. 3, Mar. 2002.
Chung, Sae-Young; Forney, G. David Jr.; Richardson, Thomas J.; Urbanke, Rudiger. “On The Design of Low-Density Parity-Check Codes within 0.0045dB of the Shannon Limit” IEEE Communications Letters, vol. 5, No. 2, Feb. 2001.
Gallager, R.G. “Low-Density Parity-Check Codes” IRE Transactions on Information Theory, Jan. 1962. PP 21-28.
Hous, Jilei; Siegel, Paul H.; Milstein, Laurence B. “Performance Analysis and Code Optimization of Low Density Parity-Check Codes on Rayleigh Fading Channels” IEEE Journal of Selected Areas in Communications, vol. 10, No. 5 May 2001.
Ping, Li; Leung, W.K.; Phamdo, Nam. “Low Density Parity Check Codes With Semi-random Parity Check Matrix”. Electronics Letters, Jan. 7, 1999, vol. 35 No. 1.
Mackay, David J.C.; Wilson, Simon T.; Davey, Matthew C. “Comparison of Constructions of Irregular Gallager Codes” Transactions Letters. IEEE Transaction of Communications vol. 47, No. 10, Oct. 1999.
Mackay, David JC. “Good Error-Correcting Codes Based on Very Sparse Matrices” IEEE Transactions on Information Theory, vol. 45 No. 2, Mar. 1999.
Richardson, Thomas J.; Shokrollahi, M. Amin; Urbanke, Rudiger L. “Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes”. IEEE Transactions On Information Theory vol. 47, No. 2, Feb. 2001.
Richardson Thomas J; Urbanke Rudiger L. “Efficient Encoding of Low Density Parity-Check Codes ” IEEE Transactions On Information Theory vol. 47 No. 2, Feb. 2001.
M. Luby, M. Mitzenmacher, A. Shokrollahi, D. Speilman, and V. Stemann, “Practical loss-resilient codes,” in Proc. 29th Annu. ACM Symp. Theory of Computing, 1997, pp. 150-159. (Annual ACM Symposium on Theory of Computing).
M. Luby, M. Mitzenmacher, A. Shokrollahi, and D. Spielman, “Analysis of low density codes and improved designs using irregular graphs,” in Proc. 30th Annu. ACM Symp. Theory of Computing, 1998, pp. 249-258. (Annual ACM Symposium on Theory of Computing).
Blankenship Yufei
Classon Brian
Desai Vipul
Abraham Esaw
De'cady Albert
Haas Kenneth A.
Motorola Inc.
LandOfFree
Method and apparatus for generating parity-check bits from a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for generating parity-check bits from a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating parity-check bits from a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3291599