In Memoriam: Robert J. McEliece
Tribute to Robert J. McEliece, who passed away May 8, 2019. Dariush Divsalar and Mario Blaum write about Bob's broad and substantial contributions to information theory, coding theory and cryptography.
May 14, 2019

Robert J. McEliece was born in Washington, DC, on May 21, 1942, and passed away on May 8, 2019 in Pasadena. He received the B.S. and Ph.D. degrees in mathematics from the California Institute of Technology in 1964 and 1967, respectively, and attended Trinity College, Cambridge University, England, during 1964–65. From 1963 to 1978 he worked at Caltech's Jet Propulsion Laboratory (JPL), and he had been a consultant at JPL since 1978. From 1978 to 1982 he was Professor of Mathematics and Research Professor at the Coordinated Science Laboratory, University of Illinois, Urbana-Champaign. He joined the faculty at Caltech in 1982, and became an Allen E. Puckett Professor in 1997. He was also a regular consultant at the Sony Corp. in Tokyo.

Prof. McEliece made fundamental contributions to the theory, design and practice of channel codes for communication systems. Prof. McEliece’s achievements are many. At Jet Propulsion Laboratory, Prof. McEliece has contributed to the design and analysis of many coded interplanetary telecommunication systems, for example the Golay-coded non-imaging system for the Voyager spacecraft, and the "Big Viterbi Decoder" which has been used on the Galileo, Mars Pathfinder, Cassini, and Mars Exploration Rover missions. He has won several NASA awards for this work.

As a faculty member at Caltech, he has five times won awards for excellence in teaching, and has mentored more than 30 Ph.D. students, four of whom are IEEE Fellows. From 1990–1999, he served as Executive Officer (chairman) for the Electrical Engineering Department, and under his leadership Caltech's small (12 FTE) EE Department rose to rank 5th nationally, behind only MIT, Stanford, Berkeley, and the University of Illinois.

Prof. McEliece is the author of three textbooks and more than 250 research articles, jointly with more than 75 coauthors (his top 12 papers yield 10291 citations on Google Scholar— Prof. McEliece is currently listed as a Highly Cited Researcher by Thompson-ISI).

Besides his technical achievements, Prof. McEliece had many other interests. Among them, he was an avid runner, and he loved music and singing. He had an affable personality and he was loved and respected by his peers and his students. He influenced greatly the careers of many of us. He was a truly outstanding lecturer and was an excellent popularizer of information theory. He can be described as a "mathemagician". Enjoy for example his lecture  Safety in Numbers - Protecting Data Mathmagically, Part 1  and Part 2 on YouTube.

He is survived by three daughters, a son and a step-daughter.

Below is a chronological list of some of Prof. McEliece’s most important achievements.

1. McEliece’s Theorem. This theorem, which identifies the largest power of p that divides all the weights in a p-ary cyclic code, and which contains the celebrated Ax divisibility theorem as a special case, is one of the deepest mathematical results to come out of coding theory. McEliece’s theorem has inspired a large and impressive body of later work by Wilson, Calderbank, Katz, and others. Reference [R1] and [R2].

2. The Theory of Information and Coding. In print continuously since 1977, this classic textbook book has been compared to Richard Feynman's Lectures on Physics, as a standard and authoritative book in its field. Reference [R3]

3. The JPL Bound. Since 1977 this result has stood as the best known upper bound on the basic combinatorial problem of Information Theory: the tradeoff between rate and minimum distance of the best binary codes. Winner of an Information Theory Society Golden Jubilee Award, 1998. Reference [R4]

4. The McEliece Public-key Cryptosystem. Has withstood repeated continuous attacks of cryptanalysts for more than 30 years, and thus (with RSA) is one of a small handful of successful public-key cryptosystems. McEliece cryptosystem is a candidate for post-quantum cryptography since it is immune to attacks using Shor’s algorithm. Reference [R5]

5. Decoding is NP-hard. The first proof that maximum-likelihood decoding of linear block codes is an intractable problem. This result has inspired many similar results by later researchers. Reference [R6]

6. Block interference channel models. A class of channel models with memory that is (a) simple enough to allow precise analysis and (b) realistic enough to yield insights into real channels. This class of channel models has proved essential in the study of wireless fading channels. Reference [R7]

7. The capacity of the Hopfield Neural network. This paper gave the first rigorous estimate of the potential of neural-network type memories. Reference [R8]

8. Turbo decoding and belief propagation. Winner of the 1998 Leonard G. Abraham award. This paper put the term “belief propagation” in the coding theory vocabulary. Reference [R9]

9. The Generalized Distributive Law. An important synthesis showing deep and previous unsuspected connections between the fast Fourier Transform, Viterbi’s algorithm, Turbo decoding, and many other basic algorithms. (a patent). Reference [R10]

10. Repeat-Accumulate Codes. An astonishingly simple and powerful class of codes which bridge the gap between turbo-codes and LDPC codes, and which have become an industry standard. (two patents). Reference [R11] and [R12].


[R1] Weight Congruences for p-ary Cyclic Codes, Discrete Math. 3 (1972), pp.177--192.

[R2] Zeroes of Functions in Finite Abelian Group Algebras (with P. Delsarte), Am. J. Math. 98 (1976), pp. 197--224.

[R3] The Theory of Information and Coding (Addison-Wesley, 1977); 2nd Ed., (Cambridge U Press, 2002); Student Ed., (Cambridge U Press, 2004).

[R4] New Upper Bounds on the Rate of a Code via the Delsarte-MacWilliams Inequalities (with E. Rodemich, H. Rumsey, L. Welch), IT-23 (1977), pp. 57--166.

[R5] A Public-Key Cryptosystem Based on Algebraic Coding Theory, JPL DSN Progress Reports vol. 44 (1978), pp. 114--116.

[R6] On the Inherent Intractability of Certain Coding Problems (with E.R. Berlekamp and H. Van Tilborg), IT-24 (1978), pp. 384--386.

[R7] Channels with Block Interference (with W. Stark), IT-30 (1984), pp. 44--53.

[R8] The Capacity of the Hopfield Associative Memory (with E. C. Posner, E. Rodemich, and S. Venkatesh), vol. IT-33 (July 1987), pp. 461--482. Reprinted in: V. Vemuri, Ed., Artificial Neural Networks: Theoretical Concepts. Los Angeles, IEEE Computer Society Press, 1988.

[R9] Turbo Decoding as an Instance of Pearl's `Belief Propagation' Algorithm,' (with David MacKay and J.-F. Cheng), IEEE J. Sel. Areas Comm., vol. 16, no. 2 (Feb. 1998), pp. 140--152.

[R10] The Generalized Distributive Law (with S. M. Aji), IEEE Trans. Inform. Theory, vol. IT-46, no. 2 (March 2000), pp. 325--343.

[R11] Coding Theorems for `Turbo-Like' Codes, (with D. Divsalar and H. Jin), Proc. 1998 Allerton Conference, pp. 201--210.

[R12] Irregular Repeat-Accumulate Codes,'' (with H. Jin and A. Khandekar), Proc. 2nd. International Conf. Turbo Codes, Brest, France, 4--7 Sept. 2000, pp. 1-8.

References note: “IT” is short for the IEEE Transactions on Information Theory.

Robert J. McEliece’s Honors/Awards

1) Associated Students of the California Institute of Technology Award for Excellence in Teaching, 1985, 1989, 1990, 1999.

2) Caltech Graduate Student Council Teaching Award, 1996.

3) Erdos number one: ``Ramsey Bounds for Graph Products'' (with Paul Erdos and Herbert Taylor), Pac. J. Math. 37 (1971), pp. 45--46.

4) NASA Group Achievement Award for Voyager Mission Operations Systems Design and Development, June 1981.

5) Elected President of the IEEE Information Theory Group (one-year term of office, 1984)

6) NASA Group Achievement Award for the Advanced Error-Correcting Code Research and Development Team, June 1992. (“In recognition of research and development resulting in a new error-correcting system providing an increase of data rate by a factor of 1.6 to benefit all future space missions”)

7) Elected to National Academy of Engineering, 1998.

8) Elected Fellow, IEEE, 1984

9) Paper ``New Upper Bounds on the Rate of a Code via the Delsarte-MacWilliams Inequalities,'' selected for an Information Theory Society Golden Jubilee Award, 1998

10) Paper ``Turbo Decoding as an Instance of Pearl's `Belief Propagation' Algorithm'' awarded the 1998 Leonard G. Abraham Prize paper Award

11) IEEE Third Millennium Medal.

12) IEEE Information Theory Society 2004 Claude E Shannon Award

13) IEEE Alexander Graham Bell Medal, 2009

Read more about R. J. McEliece's life at Caltech News