Methods and apparatus for improving performance of information coding schemes
First Claim
1. A decoding method for a linear block code having a parity check matrix that is sparse or capable of being sparsified, the decoding method comprising an act of:
- A) modifying a conventional decoding algorithm for the linear block code such that a performance of the modified decoding algorithm significantly approaches or more closely approximates a performance of a maximum-likelihood decoding algorithm for the linear block code.
2 Assignments
0 Petitions
Accused Products
Abstract
Various modifications to conventional information coding schemes that result in an improvement in one or more performance measures for a given coding scheme. Some examples are directed to improved decoding techniques for linear block codes, such as low-density parity-check (LDPC) codes. In one example, modifications to a conventional belief-propagation (BP) decoding algorithm for LDPC codes significantly improve the performance of the decoding algorithm so as to more closely approximate that of the theoretically optimal maximum-likelihood (ML) decoding scheme. BP decoder performance generally is improved for lower code block lengths, and significant error floor reduction or elimination may be achieved for higher code block lengths. In one aspect, significantly improved performance of a modified BP algorithm is achieved while at the same time essentially maintaining the benefits of relative computational simplicity and execution speed of a conventional BP algorithm as compared to an ML decoding scheme. In another aspect, modifications for improving the performance of conventional BP decoders are universally applicable to “off the shelf” LDPC encoder/decoder pairs. Furthermore, the concepts underlying the various methods and apparatus disclosed herein may be more generally applied to various decoding schemes involving iterative decoding algorithms and message-passing on graphs, as well as coding schemes other than LDPC codes to similarly improve their performance. Exemplary applications for improved coding schemes include wireless (mobile) networks, satellite communication systems, optical communication systems, and data recording and storage systems (e.g., CDs, DVDs, hard drives, etc.).
-
Citations
53 Claims
-
1. A decoding method for a linear block code having a parity check matrix that is sparse or capable of being sparsified, the decoding method comprising an act of:
A) modifying a conventional decoding algorithm for the linear block code such that a performance of the modified decoding algorithm significantly approaches or more closely approximates a performance of a maximum-likelihood decoding algorithm for the linear block code. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
8. A method for decoding received information encoded using a coding scheme, the method comprising acts of:
-
A) executing an iterative decoding algorithm for a predetermined first number of iterations to attempt to decode the received information;
B) upon failure of the iterative decoding algorithm to provide valid decoded information after the predetermined first number of iterations, altering at least one value used by the iterative decoding algorithm; and
C) executing at least a first round of additional iterations of the iterative decoding algorithm using the at least one altered value. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39)
-
-
40. An apparatus for decoding received information that has been encoded using a coding scheme, the apparatus comprising:
-
a decoder block configured to execute an iterative decoding algorithm for a predetermined first number of iterations; and
at least one controller that, upon failure of the decoder block to provide valid decoded information after the predetermined first number of iterations of the iterative decoding algorithm, is configured to alter at least one value used by the iterative decoding algorithm and control the decoder block so as to execute at least a first round of additional iterations of the iterative decoding algorithm using the at least one altered value. - View Dependent Claims (41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53)
-
Specification