Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-10-12
2004-03-30
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S800000
Reexamination Certificate
active
06715121
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a simple and systematic process for constructing and coding codes which are known by the abbreviation LDPC standing for “Low Density Parity Check”.
Gallager's codes, proposed around 1963, are the progenitor of the LDPC codes currently envisaged as an alternative to turbocodes.
An article published in the IEEE journal Transaction on Information Theory, Vol. 45 No. 2, March 1999 by M. J. C. MacKay entitled “Good Error Correcting Codes Based on very Sparse Matrices” presents interesting results regarding these codes, in particular the fact that:
for blocks of large size, they are asymptotically “very good codes”
the weighted decoding (or “soft decoding” or “flexible decoding”) is easy to implement.
However, there is no method other than heuristic for constructing them.
According to this coding technique a code (N, K) comprising N symbols, of which K are free, is defined by its parity check matrix A comprising M=N−K rows and N columns.
The check matrix A is characterized by its low “density”: this should be understood to mean that it comprises a small number of nonzero elements.
More precisely, it comprises exactly t nonzero symbols in each column, all the others being equal to 0.
If the symbols of a code word are denoted ci, i=0 . . . N−1 and the elements of the check matrix Aij, the code satisfies M=N−K relations of the form:
∑
i
=
0
…
N
-
1
A
mi
C
i
for
m
=
0
…
M
-
1
The methods proposed by M. J. C. MacKay consist in building an initial matrix A from smaller unit matrices or tridiagonal matrices, then in permuting their columns so as to arrive at the desired result. Experience shows, however, that it is difficult to satisfy the various constraints imposed in respect of their construction.
The aim of the invention is to alleviate the aforesaid drawbacks.
SUMMARY OF THE INVENTION
To this end the subject of the invention is a process for constructing LDPC codes comprising N symbols, of which K are free, each code being defined by a check matrix A comprising M=N−K rows N columns and t nonzero symbols in each column, which process consists:
a—in allocating the same number of nonzero symbols “t” to all the rows of the check matrix A,
b—in taking as number of symbols “t” the smallest possible odd number,
c—in defining the columns in such a way that any two columns of the check matrix A have at most only one nonzero value,
d—and in defining the rows in such a way that two rows of the check matrix A have only one nonzero common value.
The process according to the invention has the advantage that it makes it possible to simplify the coding and decoding algorithms by using a check matrix A having the lowest possible density whilst giving good performance for reasonable complexity, the computational power required being proportional to the number t. Insofar as there are few errors, constraint “c” above allows the decoding algorithm to converge in all circumstances.
REFERENCES:
patent: 4027261 (1977-05-01), Laurent et al.
patent: 4382232 (1983-05-01), Laurent
patent: 4603393 (1986-07-01), Laurent et al.
patent: 4799241 (1989-01-01), Laurent
patent: 4852098 (1989-07-01), Brechard et al.
patent: 4888778 (1989-12-01), Brechard et al.
patent: 4905256 (1990-02-01), Laurent
patent: 4945312 (1990-07-01), Auger et al.
patent: 4982341 (1991-01-01), Laurent
patent: 5016278 (1991-05-01), Rochette et al.
patent: 5243685 (1993-09-01), Laurent
patent: 5313553 (1994-05-01), Laurent
patent: 5412667 (1995-05-01), Havemose
patent: 5425038 (1995-06-01), Chen
patent: 5522009 (1996-05-01), Laurent
patent: 5537427 (1996-07-01), Chen
patent: 5600659 (1997-02-01), Chen
patent: 5745507 (1998-04-01), Chen
patent: 5757823 (1998-05-01), Chen et al.
patent: 5768294 (1998-06-01), Chen et al.
patent: 5872798 (1999-02-01), Baggen et al.
patent: 6016469 (2000-01-01), Laurent
patent: 6195777 (2001-02-01), Luby et al.
patent: 6307487 (2001-10-01), Luby
patent: 6320520 (2001-11-01), Luby
patent: 6463563 (2002-10-01), Chen et al.
David J. Mackay, “Good Error-Correcting Codes Based on Very Sparse Matrices”, IEEE Transactions on Information theory, Mar. 1999, vol. 45, No. 2, pp. 399-431.
Li Ping, et al., “Low Density Parity Check Codes with Semi-Random Parity Check Matrix”, Electronics Letters, Jan. 7, 1999, vol. 35, No. 1, XP002143043, pp. 38-39.
X.-H. Peng, et al., “Efficient Permutation Criterion for Obtaining Minimal Trellis of a Block Code”, Electronics Letters, May 23, 1996, vol. 32, No. 11, XP000599121, pp. 983-984.
J. Boutrost, et al., “Generalized Low Density (Tanner) Codes”, 1999 IEEE International Conference on Communications (Cat. No. 99CH36311), Jun. 6-10, 1999, vol. 1, XP002143044, pp. 441-445.
Richard E. Blahut, “Theory and Practice of Error Control Codes ISBN: 0-201-10102-5”, XP002143045, pp. 47-49.
"Thomson-CSF"
Chaudry Mujtaba
De'cady Albert
Oblon & Spivak, McClelland, Maier & Neustadt P.C.
LandOfFree
Simple and systematic process for constructing and coding... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Simple and systematic process for constructing and coding..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simple and systematic process for constructing and coding... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3192379