Bibliography

(full paper available in ps or pdf)

1

S.M. Aji and R.J. McEliece.
A general algorithm for distributing information in a graph.
Proc. IEEE Int. Symp. Inform. Theory, page 6, 1997.

2

S.M. Aji and R.J. McEliece.
The generalized distributive law.
IEEE Transactions on Information Theory, July 1998.
Submitted for publication.

3

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

4

E.R. Berlekamp.
Algebraic Coding Theory.
McGraw-Hill, 1968.

5

E.R. Berlekamp, R.J. McEliece, and H.C.A. van Tilborg.
On the inherent intractability of certain coding problems.
IEEE Transactions on Information Theory, 24:384-386, 1978.

6

C. Berrou and A. Glavieux.
Near optimum error correcting coding and decoding: turbo-codes.
IEEE Trans. Commun., 44:1261-1271, 1996.

7

R.E. Blahut.
Theory and practice of data transmission codes, 1994.

8

A.E. Brouwer and T. Verhoeff.
An updated table of minimum-distance bounds for binary linear codes.
IEEE Transactions on Information Theory, 39:662-677, 1993.

9

R.A. Brualdi and V.S. Pless.
Greedy codes.
Journal of Comb. Th. (A), September 1993.

10

J. Bruck and M. Blaum.
Neural networks, error-correcting codes, and polynomials over the binary n-cube.
IEEE Transactions on Information Theory, 35:976-987, 1989.

11

A. Glavieux C. Berrou and P. Thitimajshima.
Near Shannon limit error-correcting coding and decoding: turbo codes.
Proc. IEEE Int. Conf. on Communications, pages 1064-1070, 1993.

12

J. Conway and N.J.A. Sloane.
Sphere Packings, Lattices and Groups.
Springer-Verlag, 1993.

13

J.H. Conway.
Integral lexicographic codes.
Discrete Math, 83:219 - 235, 1990.

14

J.H. Conway and N.J.A. Sloane.
Lexicographic codes: error-correcting codes from game theory.
IEEE Transactions on Information Theory, 32:337-348, 1986.

15

T.H. Cormen, C.E. Leiserson, and R. L. Rivest.
Introduction to Algorithms.
MIT Press, 1990.

16

R.G. Downey, M.R. Fellows, A. Vardy, and G. Whittle.
On the parametrized complexity of certain fundamental problems in coding theory.
To appear.

17

M. Esmaeili and A.K. Khandani.
Acyclic tanner graphs and maximum-likelihood decoding of linear block codes.
preprint, May 1998.

18

T. Etzion, A. Trachtenberg, and A. Vardy.
Which codes have cycle-free tanner graphs?
Technical report, Technion - Israel Institute of Technology, November 1997.
Technical Report #0925.

19

T. Etzion, A. Trachtenberg, and A. Vardy.
Which codes have cycle-free tanner graphs?
In 1998 IEEE International Symposium on Information Theory, Cambridge, MA, 1998.

20

T. Etzion, A. Trachtenberg, and A. Vardy.
Which codes have cycle-free tanner graphs?
IEEE Transactions on Information Theory, 45(6):2173 - 2180, September 1999.

21

T. Etzion and A. Vardy.
On perfect codes and tilings: Problems and solutions.
SIAM Journal of Discrete Math, 11(2):205-233, May 1998.

22

J. Feigenbaum, G.D. Forney Jr., B.H. Marcus, R.J. McEliece, and A. Vardy.
Special issue on ``codes and complexity''.
IEEE Transactions on Information Theory, 42:1649-2064, November 1996.

23

B.J. Frey.
Baysean networks for pattern classification, data compression, and channel coding.
PhD thesis, University of Toronto, Canada, July 1997.
Department of Electrical Engineering.

24

B.J. Frey, F.R. Kschischang, H.A. Loeliger, and N. Wiberg.
Factor graphs and the sum-product algorithm.
In preparation, 1997.

25

R.G. Gallager.
Low-density parity-check codes.
IRE Trans. Inform. Theory, 8:21-28, January 1962.

26

R.G. Gallager.
Low-Density Parity-Check Codes.
MIT Press, Cambridge, MA, 1963.

27

R.L. Graham and N.J.A. Sloane.
On the covering radius of codes.
IEEE Transactions on Information Theory, 31:385-401, 1985.

28

S.L. Hakimi and J. Bredeson.
Graph theoretic error-correcting codes.
IEEE Transactions on Information Theory, 14:584-591, 1968.

29

S.L. Hakimi and H. Frank.
Cut-set matrices and linear codes.
IEEE Transactions on Information Theory, 11:457-458, 1965.

30

Mor Harchol-Balter, Tom Leighton, and Daniel Lewin.
Resource discovery in di stributed networks.
In 18th Annual ACM-SIGACT/SIGOPS Symposium on Principles of Distributed Computing, Atlanta, GA, May 1999.

31

K.A.S. Immink.
Coding Techniques for Digital Recorders.
Prentice Hall, New York, 1991.

32

G.D. Forney Jr.
Final report on a coding system design for advanced solar missions.
Technical report, NASA Ames Research Center, Moffet Field, CA, December 1967.
Contract NAS2-3637.

33

G.D. Forney Jr.
The forward-backward algorithm.
In Proc. 34-th Annual Allerton Conference on Communications, Control and Computing, Monticello, IL., October 1996.

34

F.R. Kschischang and G.B. Horn.
A heuristic for ordering a linear block code to minimize trellis state complexity.
In Proc. 32-nd Annual Allerton Conference on Communications, Control and Computing, pages 75-84, Monticello, IL, September 1994.

35

F.R. Kschischang and V. Sorokine.
On the trellis structure of block codes.
IEEE Transactions on Information Theory, 41:1924-1937, 1995.

36

A. Lafourcade and A. Vardy.
Lower bounds on trellis complexity of block codes.
IEEE Transactions on Information Theory, 41(6), November 1995.

37

G.R. Lang and F.M. Longstaff.
A Leech lattice modem.
IEEE J. Select. Areas Comm., 7:968-973, 1989.

38

K.Y. Liu and J.J. Lee.
Recent results on the use of concatenated Reed-Solomon/Viterbi channel coding for space communications.
IEEE Trans. Comm., 32:456-471, 1984.

39

D.J.C. MacKay.
Gallager codes that are better than turbo codes.
In Proc. 36-th Allerton Conference on Communications, Control and Computing, Monticello, IL., September 1998.

40

D.J.C. MacKay.
Good error-correcting codes based on very sparse matrices.
IEEE Transactions on Information Theory, 1999.
To appear.

41

D.J.C. MacKay and R.M. Neal.
Near Shannon limit performance of low-density parity-check codes.
Electronics Letters, 32:1645-1646, 1996.

42

F.J. MacWilliams and N.J.A. Sloane.
The Theory of Error-Correcting Codes.
North-Holland Publishing Company, New York, 1977.

43

R.J. McEliece.
On the BCJR trellis for linear block codes.
IEEE Transactions on Information Theory, 42:1072-1092, 1996.

44

Y. Minsky and A. Trachtenberg.
Efficient reconciliation of undoredered databases.
41st Annual ACM Symposion on Theory of Computing, May 1999.
Submitted.

45

D.J. Muder.
Minimal trellises for block codes.
IEEE Transactions on Information Theory, 34:1049-1053, 1988.

46

P.R.J. Ostergard, T. Baicheva, and E. Kolev.
Optimal binary one-error-correcting codes of length 10 have 72 codewords.
IEEE Transactions on Information Theory, 45(4):1229-1231, May 1999.

47

J. Pearl.
Probabilistic Reasoning in Intelligent Systems:Networks of Plausible Inference.
Kaufmann, San Mateo, CA, 1988.

48

W.W. Peterson and Jr. E.J. Weldon.
Error-Correcting Codes.
MIT Press, Cambridge, MA, 2-nd edition, 1961.

49

C.E. Shannon.
A mathematical theory of communication.
Bell Syst. Tech. J., 27:379-423, 623-656, 1948.

50

M. Sipser and D.A. Spielman.
Expander codes.
IEEE Transactions on Information Theory, 42:1710-1722, 1996.

51

P. Solé and T. Zaslavsky.
The covering radius of the cycle code of a graph.
Discrete Applied Math., 45:63-70, 1993.

52

P. Solé and T. Zaslavsky.
A coding approach to signed graphs.
SIAM J. Discrete Math., 7:544-553, 1994.

53

D.A. Spielman.
Linear-time encodable and decodable codes.
IEEE Transactions on Information Theory, 42:1723-1731, 1996.

54

J. Stern.
Approximating the number of error locations within a constant ratio is NP-complete.
Lect. Notes Comp. Science, 673:325-331, 1993.

55

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

56

A. Trachtenberg.
Computational methods in coding theory.
Master's thesis, University of Illinois at Urbana-Champaign, 1996.

57

A. Trachtenberg and Y. Minsky.
Efficient reconciliation of unordered databases.
Technical report, Cornell University, Ithaca, NY, November 1999.

58

A. Trachtenberg and A. Vardy.
Designing lexicographic codes for a given trellis complexity.
In preparation.

59

A. Trachtenberg and A. Vardy.
Full rank tilings in eight and nine dimensions.
In preparation.

60

A. Trachtenberg and A. Vardy.
Lexicographic codes: constructions, bounds, and trellis complexity.
In Proc. 31st Annual Conference on Information Sciences and Systems, pages 521-527, Baltimore, MD, March 1997.

61

A. Vardy.
Algorithmic complexity in coding theory and the minimum distance problem.
In Twenty-ninth annual ACM symposium on Theory of computing, 1997.

62

A. Vardy.
Trellis structure of codes.
In V.S. Pless and W. Cary Huffman, editors, Handbook of Coding Theory. Elsevier Science Publishers, Amsterdam, 1998.

63

A.J. Viterbi.
Error bounds for convolutional codes and an asymptotically optimum decoding algorithm.
IEEE Transactions on Information Theory, 13:260-269, 1967.

64

D.B. West.
Introduction to Graph Theory.
Prentice-Hall, Englewood Cliffs, NJ, 1996.

65

N. Wiberg.
Codes and Decoding on General Graphs.
PhD thesis, Linkoping University, 1996.

66

N. Wiberg, H.-A. Loeliger, and R. Kötter.
Codes and iterative decoding on general graphs.
Euro. Trans. Telecommun., 6:513-526, 1995.

67

S. Zhang.
Design of linear block codes with fixed state complexity.
Master's thesis, University of Toronto, 1996.