Deriving the Normalized Min-Sum Algorithm from Cooperative Optimization

Preprint English OPEN
Huang, Xiaofei (2006)
  • Related identifiers: doi: 10.1109/ITW2.2006.323788
  • Subject: Computer Science - Information Theory
    arxiv: Computer Science::Information Theory

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 the algorithm and offers new insights on its power and limitation. It also gives us a general framework for designing new decoding algorithms.
  • References (18)
    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.

    [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.

    [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.

  • Metrics
    No metrics available
Share - Bookmark