Decoding low density parity codes

Details Decoding low density parity codes Decoding low density parity codes

2004-10-08

2008-03-04

Chase, Shelly (Department: 2112)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Error/fault detection technique

Reexamination Certificate

active

07340671

ABSTRACT:
The present invention includes a technique for updating messages that originate at the constraint nodes of bi-partite graphs in Low Density Parity Check codes. The technique computes only two outgoing magnitudes at each constraint node and exhibits no measurable performance loss as compared to exact belief propagation which computes a unique magnitude for each departing edge from a given constraint node. The technique eliminates the need for memory based table look-up in the constraint node processing and has been implemented, in one embodiment, using only shift, add, and comparison operations.

REFERENCES:
patent: 6633856 (2003-10-01), Richardson
patent: 6938196 (2005-08-01), Richardson
patent: 7137060 (2006-11-01), Yu et al.
R.G. Gallagher, “Low-density parity-check codes,” IRE Trans. Inform. Theory, vol. IT-8, pp. 21 28, Jan. 1962.
C. Berrou, A. Glavieux, and P. Thilimajshima, “Near Shannon limit error-correcting coding and decoding: Turbo codes,” in Proc. IEEE Int. Conf. Commun., Geneva, Switzerland, May 1993, pp. 1064-1070.
D.J.C. MacKay, “Good error-correcting codes based on very sparse matrices,” IEEE Trans. Inform. Theory, vol. 45, pp. 399-431, Mar. 1999.
M. Luby, M. Mitzenmacher, A. Shokrollahi, and D. Spielman, “Improved low-density parity-check codes using irregular graphs,” IEEE Trans. Inform. Theory, vol. 47, pp. 585-598, Feb. 2001.
T. Richardson, A. Shokrollahi, and R. Urbanke, “Design of capacity approaching irregular low density parity check codes,” IEEE Trans. on Inform. Theory, vol. 47, pp. 618-637, Feb. 2001.
J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. San Francisco, CA: Morgan Kaufmann, 1998.
T. Tian, C. Jones, J. Villasenor, and R.D. Wesel, “Characterization and selective avoidance of cycles in irregular LDPC code construction,” International Conference on Communications (ICC) 2003.
C. Jones, A. Matache, T.Tian, J. Villasenor and R. Wesel, “LDPC Codes—University Good for Wireless Channels,” Proceedings of the Military Communications Conference, Oct. 2003.
C. Jones, T. Tian, A. Matache, R. Wesel and J. Villasenor, “Robustness of LDPC Codes on Periodic Fading Channels,” Proceedings of GlobeCom, Nov. 2002.
T. Richardson and R. Urbanke, “Efficient Encoding of Low Density Parity Check Codes,” IEEE Trans. on Inform. Theory, vol. 47, pp. 638-656, Feb. 2001.
J. Chen, A. Dholakia, E. Elefheriou, M. Fossoner, and X.Y. Hu, “Near Optimum Reduced-Complexity Decoding Algorithms for LDPC codes,” Proc. IEEE Int. Sym. Inform. Theory, Lausanne, Switzerland, Jul. 2002.
E. Eleftheriou, T. Mittleholzer and A. Dholakia, A Reduced-Complexity Decoding Algorithm for Low Density Parity Check Codes, IEEE Electron. Letters, vol. 37, pp. 102-104,Jan. 2001.
J. Chen and M Fossorier, “Density Evolution for BP-based decoding Algorithm of LDPC codes and their Quanitized Versions,” Proc. IEEE Globecom, Taipei, Taiwan, Nov. 2002.
L. Dong-U, J. Villasenor, and W. Luk, “A Hardware Gaussian Noise Generator For Exploring Channel Code Behavior At Very Low Bit Error Rates,” In Proceedings of FCCM, May 2003.
Chen and Fossorier, Near Optimum Universal Belief Propagation Based Decoding of LDPC Codes and Extension to Turbo Decoding, IEEE Trans. on Comm., vol. 50, No. 3, Mar. 2001.

Affiliated with

Also associated with

Rating

Decoding low density parity codes does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Decoding low density parity codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decoding low density parity codes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3980802