publication . Preprint . Conference object . 2006

Deriving the Normalized Min-Sum Algorithm from Cooperative Optimization

Xiaofei Huang;
Open Access English
  • Published: 15 Sep 2006
Abstract
The normalized min-sum algorithm can achieve near-optimal performance at decoding LDPC codes. However, it is a critical question to understand the mathematical principle underlying the algorithm. Traditionally, people thought that the normalized min-sum algorithm is a good approximation to the sum-product algorithm, the best known algorithm for decoding LDPC codes and Turbo codes. This paper offers an alternative approach to understand the normalized min-sum algorithm. The algorithm is derived directly from cooperative optimization, a newly discovered general method for global/combinatorial optimization. This approach provides us another theoretical basis for th...
Subjects
arXiv: Computer Science::Information Theory
ACM Computing Classification System: Data_CODINGANDINFORMATIONTHEORY
free text keywords: Computer Science - Information Theory, Population-based incremental learning, Turbo code, Difference-map algorithm, Sequential decoding, Discrete mathematics, Theoretical computer science, Berlekamp–Welch algorithm, BCJR algorithm, FSA-Red Algorithm, Computer science, Mathematical optimization, Factor graph, Algorithm
Related Organizations
18 references, page 1 of 2

[1] J. Chen and M. Fossorier, “Density evolution of two improved BP-based algorithms for LDPC decoding,” IEEE Communications Letters, vol. 6, pp. 208-210, 2002.

[2] J. Chen, “Reduced complexity decoding algorithms for low-density parity check codes and turbo codes,” Ph.D. dissertation, University of Hawaii, Dept. of Electrical Engineering, 2003.

[3] F. R. Kschischang, B. J. Frey, and H. andrea Loeliger, “Factor graphs and the sum-product algorithm,” IEEE Transactions on Information Theory, vol. 47, no. 2, pp. 498-519, February 2001.

[4] S. Aji and R. McEliece, “The generalized distributive law,” IEEE Transactions on Information Theory, vol. 46, pp. 325-343, March 2000. [OpenAIRE]

[5] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near shannon limit error-correcting coding and decoding: turbo codes,” in Proceedings of the 1993 IEEE International Conference on Communication, 1993, pp. 1064-1070.

[6] R. G. Gallager, “Low-density parity-check codes,” Ph.D. dissertation, Department of Electrical Engineering, M.I.T., Cambridge, Mass., July 1963. [OpenAIRE]

[7] D. J. C. MacKay and R. M. Neal, “Good codes based on very sparse matrices,” in Cryptography and Coding, 5th IMA Conference, December 1995.

[8] N. Wiberg, “Codes and decoding on general graphs,” Ph.D. dissertation, Department of Electrical Engineering, Linkoping University, Linkoping, Sweden, 1996.

[9] J. G. D. Forney, “The Viterbi algorithm,” Proc. IEEE, vol. 61, pp. 268- 78, Mar. 1973.

[10] J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, 1988.

[11] M. Fossorier, M. Mihaljevic, and H. Imai, “Reduced complexity iterative decoding of low density parity check codes based on belief propagation,” IEEE Transactions on Communications, vol. 47, pp. 673-680, May 1999. [OpenAIRE]

[12] J. Hagenauer, E. Offer, and L. Papke, “Iterative decoding of binary block and convolutional codes,” IEEE Transactions on Information Theory, vol. 42, pp. 1064-1070, 1996. [OpenAIRE]

[13] C. E. Shannon, “A mathematical theory communication,” Bell Sys. Tech. J., vol. 27, pp. 379-423,623-656, 1948.

[14] X. Huang, “Cooperative optimization for solving large scale combinatorial problems,” in Theory and Algorithms for Cooperative Systems, ser. Series on Computers and Operations Research. World Scientific, 2004, pp. 117-156.

[15] --, “Near perfect decoding of LDPC codes,” in Proceedings of IEEE International Symposium on Information Theory (ISIT), 2005, pp. 302- 306.

18 references, page 1 of 2
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Preprint . Conference object . 2006

Deriving the Normalized Min-Sum Algorithm from Cooperative Optimization

Xiaofei Huang;