umn logo IMA home |  Contact IMA 
IMA Web

1999 IMA Summer Program: Codes, Systems and Graphical Models
August 2-13, 1999

Bibliographic Items Related to Week 1:
Codes on Graphs and Iterative Decoding
August 2-6, 1999

Prepared with the support of the IEEE Information Theory Society

  1. Aji, S.M. and R.J. McEliece The generalized distributive law. IEEE Transactions on Information Theory, submitted. pdf (611K)    postscript (2.6M)

  2. Bahl, L.R., J. Cocke, F. Jelinek and J. Raviv (1974). Optimal decoding of linear codes for minimizing symbol error rate. IEEE Transactions on Information Theory 20:284-287.

  3. Baum, L.E. and T. Petrie (1966). Statistical inference for probablistic functions of finite state Markov chains. Annals of Mathematical Statistics 37:1554-1563.

  4. Benedetto, S., D. Divsalar, G. Montorsi and F. Pollara (1998). Serial concatenation of interleaved codes: performance analysis, design and iterative decoding. IEEE Transactions on Information Theory 44:909-926 (3, May)

  5. Benedetto, S. and G. Montorsi (1996). Unveiling turbo codes: some results on parallel concatenated coding schemes. IEEE Transactions on Information Theory 42:409-428 (2, March).

  6. Berrou, C., A. Glavieux and P. Thitimajshima (1993). Near Shannon limit error-correcting coding and decoding: turbo codes. Proceedings of the 1993 IEEE International Conference on Communication, May, Geneva, Switzerland, pp. 1064-1070.

  7. Bryant, R.E. (1986). Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers 35:677-691 (8, Aug).

  8. Bryant, R.E. (1992). Symbolic boolean manipulation with ordered binary decision diagrams. ACM Computing Surveys 24:293-318 (Sept).

  9. Divsalar, D., H. Jin and R.J. McEliece (1998) . Coding theorems for "turbo-like" codes. Proceedings on the Thirty-Sixth Annual Allerton Conference on Communication, Control, and Computing, Sept. 23-25, 1998, Allerton House, Monticello, IL, pp. 201-210.

  10. Forney, G.D., Jr. (1972). Maximum likelihood sequence estimation of digital sequences in presence of intersymbol interference. IEEE Transactions on Information Theory 18:363-378.

  11. Forney, G.D., Jr. (1997). On iterative decoding and the two-way algorithm. Proceedings of the International Symposium on Turbo Codes and Related Topics, Sept. 1997, Brest, France.

  12. Forney, G.D., Jr. (1998). Codes on graphs: Generalized state realizations. IEEE Transactions on Information Theory, submitted. pdf (389K)    postcript (1M)

  13. Forney, G.D., Jr. (1998). Generalized state realizations of Reed-Muller codes (supplement to "Codes on graphs: generalized state realizations"). IEEE Transactions on Information Theory, submitted. pdf (980K)    postcript (339K)

  14. Frey, B.J., F.R. Kschischang, H.-A. Loeliger and N. Wiberg (1997). Factor graphs and algorithms. Proceedings of the Thirty-Fifth Annual Allerton Conference on Communication, Control and Computing, Sept. 29-Oct. 1, 1997, Allerton House, Monticello, IL, pp. 666-680.

  15. Gallager, R.G. (1963). Low-density parity-check codes. MIT Press, Cambridge, MA.

  16. Hagenauer, J., E. Offer and L. Papke (1996). Iterative decoding of binary block and convolutional codes. IEEE Transactions on Information Theory 42:429-445.

  17. Hakimi, S.L. and J.G. Bredeson (1967). Decoding of graph theoretic codes. IEEE Transactions on Information Theory 14:348-349 (April).

  18. Hakimi, S.L. and J.G. Bredeson (1968). Graph theoretic error-correcting codes. IEEE Transactions on Information Theory 14:584-591 (July, No. 4).

  19. Jordan, M.I., Z. Ghahramani, T.S. Jaakkola and L.K. Saul (1999). An introduction to variational methods for graphical models, Part I: Inference. In: Learning in Graphical Models} (Jordan, M.I., ed), Kluwer Academic Publishers, pp. 105-161.

  20. Katter, R. and A. Vardy (1998). Factor graphs: construction, classification and bounds. Proceedings of the International Symposium on Information Theory, August 1998, Cambridge, MA.

  21. Kschischang, F.R. and B.J. Frey (1998). Iterative decoding of compound codes by probability propagation in graphical models. IEEE Journal on Selected Areas in Communication 16:219-230 (2).

  22. Kschischang, F.R., B.J. Frey and H.-A. Loeliger (1998). Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, submitted.

  23. Lafferty, J. and A. Vardy (1999). Ordered binary decision diagrams and minimal trellises. IEEE Transactions on Computers, in press.

  24. Loeliger, H.-A., F. Tarkay, F. Lustenberger and M. Helfenstein (1999). Decoding in analog VLSI. IEEE Communications Magazine April, 99-101.

  25. Luby, M.G., M. Mitzenmacher, M. A. Shokrollahi and D.A. Spielman (1998). Analysis of low density codes and improved designs using irregular graphs. Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, May 23-26, 1998, Dallas, TX, pp. 249-258.

  26. Luby, M.G., M. Mitzenmacher, M.A. Shokrollahi, D.A. Spielman and V. Stemann (1997). Practical loss-resilient codes. Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, May 4-6, 1997, El Paso, TX, pp. 150-159.

  27. MacKay, D.J.C. (1999). Good error correcting codes based on very sparse matrices. IEEE Transactions on Information Theory 45:399-431 (2).

  28. MacKay, D.J.C. and R.M. Neal (1997). Near Shannon limit performance of low density parity check codes. Electronics Letters 33:457-458 (6).

  29. Massey, J.L. (1969). Shift-register synthesis and BCH decoding. IEEE Transactions on Information Theory 15:122-127 (Jan).

  30. Massey, J.L. (1998). Codes and ciphers: Fourier and Blahut. In: Codes, Curves and Signals: Common Threads in Communication. Part II. Codes and Signals, Chapter 9 (Vardy, A., ed), Kluwer Academic Publishers, Dordrecht, The Netherlands. pp. 105-119.

  31. Massey, J.L. and S. Serconek (1994). A fourier transform approach to the linear complexity of nonlinearly filtered sequences. In: Advances in Cryptology-CRYPTO '94, Lecture Notes in Computer Science, No. 839 (Desmedt, Y.G., ed ), Springer-Verlag, New York. pp. 332-340.

  32. McEliece, R.J., D.J.C. MacKay and J.-F. Cheng (1998). Turbo decoding as an instance of Pearl's belief propagation algorithm. IEEE Journal on Selected Areas of Communications 16:140-152 (2).
    pdf (295K)    postscript (2M)

  33. Richardson, T., A. Shokrollahi and R. Urbanke (1999). Design of provably good low-density parity check codes. IEEE Transactions on Information Theory, submitted.

  34. Richardson, T. and R. Urbanke The capacity of low-density parity check codes under message-passing decoding. IEEE Transactions on Information Theory, submitted.

  35. Spielman, D. (1996). Linear-time encodeable and decodable error-correcting codes. IEEE Transactions on Information Theory 42:1723-1731 (Nov).

  36. Tanner, R.M. (1981). A recursive approach to low complexity codes. IEEE Transactions on Information Theory 27:533-547 (Sept).

  37. Tanner, R.M. (1984). Explicit concentrators from generalized N-gons. SIAM Journal on Algebraic and Discrete Methods 5:287-293 (Sept, No. 3).

  38. Y. and W.T. Freeman (1999). Correctness of belief propagation in Gaussian graphical models of arbitrary topology. UC Berkeley CS Department TR UCB Report No. UCB/CSD-99-1046.

  39. Wiberg, N. (1996). Codes and decoding on general graphs, no. 440. Dept. of Electrical Engineering, University of Sweden, Sweden.

  40. Wiberg, N., H.-A. Loeliger and R. Koetter (1995). Codes and iterative decoding on general graphs. European Transactions in Telecommunication 6:513-525 (Sept/Oct).

  41. Zyablov, V.V. and M.S. Pinsker (1975). Estimation of the error-correction complexity for Gallager low-density codes. Problems of Information Transmission 11:18-28 (Jan).


Bibliography of Suggested Reading

  1. Duff, I.S., A.M. Erisman and J.K. Reid (1986). Direct Methods for Sparse Matrices. Oxford University Press, Oxford.

  2. Heegard, C. and S. Wicker (1999). Turbo coding. Kluwer Academic Publishers.

  3. Jensen, F.V. (1996). An Introduction to Bayesian Networks. Springer, New York.

  4. Massey, J.L. and S. Serconek (1996). Linear complexity of periodic sequences: a general theory. In: Advances in Cryptology-CRYPTO '96, Lecture Notes in Computer Science, No. 1109 (Koblitz, N., ed), Springer, New York. pp. 358-371.

  5. Pearl, J. (1988). Probablistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufman Publishers, San Mateo, CA.

Back to top of page

Material used during the talk

Bibliographic Items Related to Week 2: Connections among Coding Theory, System Theory and Symbolic Dynamics
August 9-13, 1999

Prepared with the support of the IEEE Information Theory Society

  1. R. L. Adler, D. Coppersmith, and M. Hassner. Algorithms for sliding block codes - an application of symbolic dynamics to information theory. IEEE Trans. Inform. Theory, IT-29:5 - 22, 1983.

  2. Jon Ashley, Brian Marcus, Dominique Perrin and Selim Tuncel, Surjective extensions of sliding block codes, SIAM J. Discrete Math., 1993, 6, 582-611.

  3. F. Bassino, M-P Beal and D. Perrin, "A finite state version of Kraft-McMillan" preprint available at http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/super.ps

  4. Frederique Bassino, Marie-Pierre Beal, Dominique Perrin, A "finite state" version of the Kraft-McMillan theorem, rapport IGM 97-27, 1997, http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/super.ps

  5. M. P. Béal. Codage Symbolique. Masson, Paris, 1993.

  6. M-P Beal and O. Carton, "Asynchronous sliding block maps" preprint available at http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/synchrone.ps

  7. Marie-Pierre Béal and Dominique Perrin. Symbolic dynamics and finite automata. In Handbook of formal languages, Vol. 2, pages 463-506. Springer, Berlin, 1997. http://www-igm.univ-mlv.fr/~beal/Recherche/MiseAJourHandBook/Handbook.ps

  8. Bernhard Beckermann and George Labahn. Recursiveness in matrix rational interpolation problems. J. Comput. Appl. Math., 77(1-2):5-34, 1997. ROLLS Symposium (Leipzig, 1996).

  9. R. Berger, The undecidability of the Domino Problem, Mem. Amer. Math. Soc. 66 (1966).

  10. M. Boyle, Algebraic aspects of symbolic dynamics, 1997 Temuco Lectures, http://www.math.umd.edu/~mmb/

  11. M. Boyle, Symbolic dynamics and matrices, Combinatorial and graph-theoretical problems in linear algebra (Minneapolis, MN, 1991), 1-38, IMA Vol. Math. Appl., 50, Springer, New York, 1993.

  12. M. Boyle and D. Handelman, Algebraic shift equivalence and primitive matrices. Trans. Amer. Math. Soc. 336 (1993), 121-149.

  13. M. Boyle and D. Handelman, The spectra of nonnegative matrices via symbolic dynamics. Annals of Math. (2) 133 (1991), 249-316.

  14. M. Boyle, B. Kitchens, B. Marcus, A Note on Minimal Covers for Sofic systems, Proceedings fo the AMS, 95 No.3, (Nov. 1985), 403-411.

  15. R. W. Brockett. Dynamical systems and their associated automata. In Systems and networks: mathematical theory and applications, Vol. I (Regensburg, 1993), pages 49-69. Akademie-Verlag, Berlin, 1994.

  16. C. Cohn, N. Elkies and J. Propp, Local statistics for random domino tilings of the Aztec diamond, Duke Math. J. 85 (1996), 117-166.

  17. F. Fagnani and S. Zampieri. Dynamical systems and convolutional codes over finite abelian groups. IEEE Trans. Inform. Theory, 42(6, part 1):1892-1912, 1996. Codes and complexity.

  18. F. Fagnani and S. Zampieri. Minimal syndrome formers for group codes. IEEE Trans. Inform. Theory, 45(1):3-31, 1999.

  19. P. Fitzpatrick. On the key equation. IEEE Trans. Inform. Theory, IT-41(5):1290-1302, 1995.

  20. P. Fitzpatrick and Sylvia M. Jennings. Comparison of two algorithms for decoding alternant codes. Appl. Algebra Engrg. Comm. Comput., 9(3):211-220, 1998.

  21. Patrick Fitzpatrick. On the scalar rational interpolation problem. Math. Control Signals Systems, 9(4):352-369, 1996.

  22. Patrick Fitzpatrick. Solving a multivariable congruence by change of term order. J. Symbolic Comput., 24(5):575-589, 1997.

  23. E. Fornasini and M.E. Valcher. Algebraic aspects of 2D convolutional codes. IEEE Trans. Inform. Theory, IT-40(4):1068-1082, 1994.

  24. E. Fornasini and M.E. Valcher. Multidimensional systems with finite support behaviors: Signal structure, generation, and detection. SIAM J. Control Optim., 36(2):760-779, 1998.

  25. G. D. Forney. Convolutional codes I: Algebraic structure. IEEE Trans. Inform. Theory, IT-16(5):720-738, 1970.

  26. G. D. Forney. Structural analysis of convolutional codes via dual codes. IEEE Trans. Inform. Theory, IT-19(5):512-518, 1973.

  27. G. D. Forney, B. Marcus, N. T. Sindhushayana, and M. Trott. A multilingual dictionary: System theory, coding theory, symbolic dynamics and automata theory. In Different Aspects of Coding Theory, number 50 in Proceedings of Symposia in Applied Mathematics, pages 109-138. American Mathematical Society, 1995.
    pdf (202K)    postscript (207K)

  28. G. D. Forney and M. D. Trott. The dynamics of group codes: State space, trellis diagrams and canonical encoders. IEEE Trans. Inform. Theory, IT-39:1491-1513, 1993.

  29. G. D. Forney and M. D. Trott. Controllability, observability, and duality in behavioral group systems. In Proc. of the 34th IEEE Conference on Decision and Control, pages 3259-3264, New Orleans, Louisiana, 1995.

  30. P. A. Fuhrmann. A Polynomial Approach to Linear Algebra. Universitext. Springer-Verlag, New York, 1996.

  31. W. Geller and J. Propp, The projective fundamental group of a Z2-shift, Ergod. Th. & Dynam. Sys. 15 (1995), 1091-1118.

  32. R. Johannesson and Z. Wan. A linear algebra approach to minimal convolutional encoders. IEEE Trans. Inform. Theory, IT-39(4):1219-1233, 1993.

  33. R. Johannesson and K. Sh. Zigangirov. Fundamentals of Convolutional Coding. IEEE Press, New York, 1999.

  34. N. Jonoska: Sofic Systems with Synchronizing Representations, > Theoretical Computer Science, 158 1-2 (1996) 81-115.

  35. N. Jonoska and B. Marcus, Minimal presentations for irreducible sofic shifts IEEE-Transactions on Information Theory 40 (1994), 1818-1827.

  36. K.H. Kim, N. Ormes and F. W. Roush. The spectra of nonnegative integer matrices via formal power series, preprint, http://rene.ma.utexas.edu/users/ormes/

  37. K.H. Kim and F. W. Roush, The Williams conjecture is false for irreducible subshifts ERA Amer. Math. Soc. 3 (1997), pp. 105-109. http://www.ams.org/era/home-1997.html

  38. K.H. Kim and F. W. Roush, The Williams conjecture is false for irreducible subshifts Annals of Math. 149, (1999), 545-558.

  39. B. Kitchens and K. Schmidt, Markov subgroups of (Z/2) Z2, Contemp. Math. 135 (1992), 265-283.

  40. B. Kitchens and K. Schmidt, Mixing sets and relative entropies for higher dimensional Markov shifts, Ergod. Th. & Dynam. Sys. 13 (1993), 705-735.

  41. B. Kitchens and K. Schmidt, Periodic points, decidability and Markov subgroups, in: Dynamical Systems, Proceeding of the Special Year, Lecture Notes in Mathematics, vol. 1342, Springer Verlag, Berlin-Heidelberg-New York, 1988, 440-454.

  42. Bruce P. Kitchens. Symbolic dynamics. Springer-Verlag, Berlin, 1998. One-sided, two-sided and countable state Markov shifts.

  43. M. Kuijper. First-Order Representations of Linear Systems. Birkhäuser, Boston, 1994.

  44. M. Kuijper. An algorithm for constructing a minimal partial realization in the multivariable case. Systems Control Lett., 31(4):225-233, 1997.

  45. M. Kuijper. The Berlekamp-Massey algorithm, error-correction, keystreams and modeling. In Dynamical systems, control, coding, computer vision (Padova, 1998), pages 321-341. Birkhäuser, Basel, 1999.

  46. D. Lind and B. Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, 1995.

  47. H. A. Loeliger, G. D. Forney, T. Mittelholzer, and M. D. Trott. Minimality and observability of group systems. Linear Algebra Appl., 205/206:937-963, 1994.

  48. H. A. Loeliger and T. Mittelholzer. Convolution codes over groups. IEEE Trans. Inform. Theory, 42(6):1660-1686, 1996.

  49. B. Marcus, The impact of Roy Adler's work on symbolic dynamics and applications to data storage, Contemporary Mathematics, 135 (1992), 33-56.

  50. B. Marcus, P. Siegel and J. Wolf, Finite State Modulation Codes for Data Storage IEEE-Journal on Selected Areas of Communication, 10 (1992) 5-37.

  51. B. Marcus, R. Roth and P. Siegel, Constrained systems and coding for recording channels, Chapter 20, Volume II of Handbook of Coding Theory (ed., V.S. Pless and W. C. Huffman), Elsevier Press, 1998.

  52. B. Marcus and S. Tuncel Entropy at a weight-per-symbol and an imbedding theorem for Markov chains, Inventiones Mathematicae, 102 (1990), 235-266.

  53. B. Marcus and S. Tuncel, The weight-per-symbol polytope and scaffolds of invariants associated with Markov chains, Ergodic Theory and Dynamical Systems, 11 (1991), 129- 180.

  54. B. Marcus and S. Tuncel, Matrices of polynomials, positivity, and finite equivalence of Markov chains, AMS Journal, 6(1993), 131- 147.

  55. Brian Marcus. Symbolic dynamics and connections to coding theory, automata theory and system theory. In Different aspects of coding theory (San Francisco, CA, 1995), volume 50 of Proc. Sympos. Appl. Math., pages 95-108. Amer. Math. Soc., Providence, RI, 1995.    pdf (230K)    postscript (180K)

  56. C. F. Martin and R. Hermann. Applications of algebraic geometry to system theory: The McMillan degree and Kronecker indices as topological and holomorphic invariants. SIAM J. Control Optim., 16:743-755, 1978.

  57. J. L. Massey. Applications of automata theory in coding. In Julius T. Tou, editor, Applied Automata Theory. Academic Press, New York, 1968.

  58. J. L. Massey. Shift-register synthesis and BCH decoding. IEEE Trans. Inform. Theory, IT-15:122-127, 1969.

  59. J. L. Massey, D. J. Costello, and J. Justesen. Polynomial weights and code constructions. IEEE Trans. Inform. Theory, IT-19(1):101-110, 1973.

  60. J. L. Massey and M. K. Sain. Codes, automata, and continuous systems: Explicit interconnections. IEEE Trans. Automat. Contr., AC-12(6):644-650, 1967.

  61. W. Parry, Instances of cohomological triviality and rigidity, Ergod. Th. & Dynam. Sys. 15 (1995), 685-696.

  62. Dominique Perrin, Marcel-Paul Schutzenberger, Synchronizing words and automata and the road coloring problem, in Symbolic Dynamics and its Applications, 1992, Peter Walters ed., 295-318, American Mathematical Society, Contemporary Mathematics, vol. 135.

  63. P. Piret, Convolutional Codes, an Algebraic Approach. Cambridge, MA: MIT Press, 1988.

  64. R.M. Robinson, Undecidability and nonperiodicity for tilings of the plane, Invent. Math. 12 (1971), 177-209.

  65. M. S. Ravi and J. Rosenthal. A smooth compactification of the space of transfer functions with fixed McMillan degree. Acta Appl. Math, 34:329-352, 1994.

  66. J. Rosenthal. An algebraic decoding algorithm for convolutional codes. In G. Picci and D.S. Gilliam, editors, Dynamical Systems, Control, Coding, Computer Vision: New Trends, Interfaces, and Interplay, pages 343-360. Birkäuser, Boston-Basel-Berlin, 1999.

  67. J. Rosenthal, J. M. Schumacher, and E.V. York. On behaviors and convolutional codes. IEEE Trans. Inform. Theory, 42(6, part 1):1881-1891, 1996.

  68. J. Rosenthal and R. Smarandache. Maximum distance separable convolutional codes. Appl. Algebra Engrg. Comm. Comput., 10(1):15-32, 1999.

  69. Joachim Rosenthal and Eric V. York. BCH convolutional codes. IEEE Trans. Inform. Theory, 45(6):1833-1844, 1999.    pdf (561 KB)    compressed postscript (682 K)

  70. N. T. Sindhushayana, B. Marcus, and M. Trott. Homogeneous shifts. IMA J. Math. Control Inform., 14(3):255-287, 1997.

  71. R. Smarandache, H. Gluesing-Luerssen, and J. Rosenthal.   Constructions of MDS-convolutional codes. Submitted to IEEE Trans. Inform. Theory, August 1999.

  72. K. Schmidt, The cohomology of higher-dimensional shifts of finite type, Pacific J. Math. 170 (1995), 237-270.

  73. K. Schmidt, Dynamical systems of algebraic origin, Birkhäuser Verlag, Basel-Berlin, 1995.

  74. K. Schmidt, Tilings, fundamental cocycles and fundamental groups of symbolic Zd-actions, Ergod. Th. & Dynam. Sys. 18 (1998), 1473-1525.

  75. P. Trow: Lifting covers of sofic shifts, preprint.

  76. M.E. Valcher and E. Fornasini. On 2D finite support convolutional codes: an algebraic approach. Multidim. Sys. and Sign. Proc., 5:231-243, 1994.

  77. H. Wang, Proving theorems by pattern recognition II, AT&T Bell Labs. Tech. J. 40 (1961), 1-41.

  78. P. Weiner.   Multidimensional Convolutional Codes. University of Notre Dame, May 1998.
    Compressed gzip file.

  79. Benjamin Weiss, Subshifts of finite type and sofic systems, Monats. Math., 77, 462-474, 1973.

  80. J. C. Willems. From time series to linear system. Part I: Finite dimensional linear time invariant systems. Automatica, 22:561-580, 1986.

  81. J. C. Willems. Models for dynamics. In U. Kirchgraber and H. O. Walther, editors, Dynamics Reported, volume 2, pages 171-269. John Wiley & Sons Ltd, 1989.

  82. J. C. Willems. Paradigms and puzzles in the theory of dynamical systems. IEEE Trans. Automat. Control, AC-36(3):259-294, 1991.

  83. S. Williams: A sofic system with infinitely many minimal covers, Proc. Amer. Math. Soc. 98, No. 3 (1986) 503-505.

  84. S.Williams: Covers of non-almost-finite-type systems, Proc. Amer. Math. Soc. 104 (1988), 245-252.

 

Material used during the talk

1999 IMA Summer Program: Codes, Systems and Graphical Models

©2006 Regents of the University of Minnesota. All rights reserved.
The University of Minnesota is an equal opportunity educator and employer.
Trouble seeing the text? | Contact U of M | Privacy
Last modified on