Nonlinear Phenomena in Turbo Decoding Algorithms

  • Ljupco Kocarev
Part of the Institute for Nonlinear Science book series (INLS)


The turbo decoding algorithm is a high-dimensional dynamical system parameterized by a large number of parameters (for a practical realization the turbo decoding algorithm has more than 103 variables and is parameterized by more than 103 parameters). In this chapter we treat the turbo decoding algorithm as a dynamical system parameterized by a single parameter that closely approximates the signal-to-noise ratio (SNR). A whole range of phenomena known to occur in nonlinear systems, such as the existence of multiple fixed points, oscillatory behavior, bifurcations, chaos, and transient chaos are found in the turbo decoding algorithm. We develop a simple technique to control transient chaos in the turbo decoding algorithm and improve the performance of the standard turbo codes.


Lyapunov Exponent Periodic Point Chaotic Attractor LDPC Code Turbo Code 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Berrou, C., Glavieux, A., Thitimajshima, P. Near Shannon limit errorcorrecting coding and decoding: Turbo-Codes. Proc. IEEE International Communications Conference, pp. 1064–1070, 1993.Google Scholar
  2. 2.
    MacKay D. J. C., Neal, R. M. Near Shannon limit performance of Low Density Parity Check Codes. Electronics Letters, vol. 32, pp. 1645–1646, 1996.CrossRefGoogle Scholar
  3. 3.
    MacKay, D. J. C. Good error correcting codes based on very sparse matrices. IEEE Trans. Information Theory, vol. 45, pp. 399–431, 1999.zbMATHMathSciNetCrossRefGoogle Scholar
  4. 4.
    Richardson, T., Urbanke, R. The capacity of low-density parity check codes under message-passing decoding. IEEE Trans. Information Theory, vol. 47(2), pp. 599–618, 1999.MathSciNetCrossRefGoogle Scholar
  5. 5.
    Shannon, C. E. A mathematical theory of communication. Bell Systems Technical Journal, vol. 27, pp. 379–423; pp. 623–56, 1948.Google Scholar
  6. 6.
    Wiggins S., F. John, F. Introduction to Applied Nonlinear Dynamical Systems and Chaos, 3rd ed. (Springer-Verlag, New York, 1990).zbMATHGoogle Scholar
  7. 7.
    Gallager, R. G. Low density parity check codes. IRE Trans. Inf. Theory, vol. 8, pp. 21–28, 1962.zbMATHMathSciNetCrossRefGoogle Scholar
  8. 8.
    Wiberg, N. Codes and decoding on general graphs. Dissertation thesis no. 440, Dept. of Electrical Engineering, Linkoping University, Sweden, 1996Google Scholar
  9. 9.
    Benedetto, S., Montorsi, G. Unveiling turbo codes: some results on parallel concatenated coding schemes. IEEE Trans. Information Theory, vol. 42, pp. 409–428, 1996; Benedetto, S., Divsalar, D., Montorsi G., Pollara, F. Serial concatenation of interleaved codes: performance analysis, design and iterative decoding. IEEE Trans. Inform. Theory, vol. 44, pp. 909–926, 1998.zbMATHCrossRefGoogle Scholar
  10. 10.
    Perez, L., Seghers, J., Costello, D. A distance spectrum intrepretation of turbo codes. IEEE Trans. Inform. Theory, vol. 42, pp. 1690–1709, 1996.MathSciNetGoogle Scholar
  11. 11.
    Richardson, T. The geometry of turbo-decoding dynamics. IEEE Trans. Information Theory, vol. 46, pp. 9–23, 2000.zbMATHCrossRefGoogle Scholar
  12. 12.
    Agrawal, D., Vardy, A. The turbo decoding algorithm and its phase trajectories. IEEE Trans. Inform. Theory, vol. 47, pp. 699–722, 2000.MathSciNetCrossRefGoogle Scholar
  13. 13.
    Kuznetsov, Y. A. Elements of Applied Bifurcation Theory (Springer-Verlag, New York, 1995).zbMATHGoogle Scholar
  14. 14.
    Ott, E. Chaos in Dynamical Systems (Cambridge University Press, New York, 1993).zbMATHGoogle Scholar
  15. 15.
    Sinai, Y.G. Gibbs measures in ergodic theory. Russ. Math. Surv., vol. 166, pp. 21–69, 1972.MathSciNetCrossRefGoogle Scholar
  16. 16.
    Bowen, R., Ruelle, D. The ergodic theory of axiom A flows. Inventiones Math., vol. 29, pp. 181–202, 1975zbMATHMathSciNetCrossRefADSGoogle Scholar
  17. 17.
    Bahl, L. R., Cocke, J., Jelinek, F., Raviv, J. Optimal decoding of linear codes for minimizing symbol error rate. IEEE Trans. Inform. Theory, vol. 20, pp. 284–287, 1974.zbMATHMathSciNetCrossRefGoogle Scholar
  18. 18.
    Kocarev, L., Tasev, Z., Vardy, A. Improving turbo codes by control of transient chaos in turbo-decoding algorithms. Electronics Letters, vol. 38(20), pp. 1184–1186, 2002.CrossRefGoogle Scholar
  19. 19.
    Kocarev, L., Lehmann, F., Maggio, G.M., Scanavino, B., Tasev, Z., Vardy, A. Nonlinear dynamics of iterative decoding systems and applications. to appear in IEEE Trans. Inform. Theory, 2006.Google Scholar

Copyright information

© Springer Science+Business Media, LLC 2006

Authors and Affiliations

  • Ljupco Kocarev
    • 1
  1. 1.Institute for Nonlinear ScienceUniversity of California, San DiegoLa Jolla

Personalised recommendations