Newtonpedia ES
Home › Computing › Robert G. Gallager
Robert G. Gallager
Image: Wikimedia Commons

Robert G. Gallager

American electrical engineer who pioneered information theory and error-correcting codes · 1931

Born
May 29, 1931
Country
United States
Section
Computing

Biography

Robert Gray Gallager, born in 1931, is an American electrical engineer whose work laid the mathematical foundations for reliable communication. For most of his career he was a professor at the Massachusetts Institute of Technology (MIT), where he developed much of his research on information theory and communication networks. His name is attached to a family of codes that remain in use in modern telecommunications.

Gallager earned his bachelor's degree in electrical engineering at the University of Pennsylvania in 1953. That same year he joined Bell Telephone Laboratories as a member of the technical staff, and from 1954 to 1956 he served in the U.S. Army Signal Corps. He then returned to study at MIT, earning a master's degree in 1957 and a Sc.D. in 1960, both in electrical engineering. From 1960 he remained at MIT as a faculty member, later becoming a principal investigator at the Research Laboratory of Electronics.

His 1960 doctoral thesis dealt with low-density parity-check codes. Put simply, such codes add redundant bits to a message so that the receiver can spot and correct errors caused by noise on the line. MIT Press published the thesis as a monograph in 1963, and a shortened version had already appeared in 1962 in an IRE journal. The codes fell into obscurity for decades because they were too demanding to implement with the technology of the time. Today they are known as Gallager codes and remain useful more than fifty years later. His 1965 paper, which offered a simpler route to the coding theorem, won the IEEE W. R. G. Baker Award in 1966.

In 1968 he published Information Theory and Reliable Communication, a book that put information theory on a firm mathematical footing and is still regarded by many as the standard textbook in the field. His work had practical consequences too. Together with his MIT colleague Dave Forney, he worked on quadrature amplitude modulation, a method of packing data into a signal, which led to 9600 bit-per-second modems. Those devices underpinned the commercial success of Codex Corporation, a company founded in 1962 that he advised and where he served as acting vice president for research in 1971 and 1972. He has been granted five patents for his inventions.

In the mid-1970s his attention turned to data networks, including distributed algorithms, routing, congestion control and random access techniques. In 1978, with graduate student Roger Camrass, he showed that packet switching was optimal in the Huffman coding sense, a measure of efficiency in data compression. In 1988 he published Data Networks with Dimitri Bertsekas, a book that helped establish the conceptual base of the field. During the 1990s he returned to information theory and to stochastic processes, systems whose behaviour evolves randomly over time, and in 1996 he wrote Discrete Stochastic Processes. His later textbook, Principles of Digital Communication, appeared in 2008.

Gallager was also active in the wider scientific community. He was president of the IEEE Information Theory Society in 1971, sat on its board of governors in two separate periods, and edited the society's transactions. He chaired an advisory committee to the National Science Foundation on networking research from 1989 to 1992. His honours include the Claude E. Shannon Award in 1983, the IEEE Medal of Honor in 1990, the Marconi Prize in 2003 and the Japan Prize in 2020. He is a member of the US National Academy of Engineering and of the National Academy of Sciences.

His legacy lies in two areas. His low-density codes, rediscovered in the 1990s, now form part of wireless and data storage systems. His books and his teaching trained generations of researchers, many of whom lead their own fields today. Gallager is married to Marie Gallager and has three children, as well as many grandchildren and step-relatives.

Main contributions

  • 1960Low-density parity-check codes (Gallager codes): codes that add redundant bits so errors in transmission can be detected and corrected.
  • 1968Information Theory and Reliable Communication: a book that gave information theory a rigorous mathematical base.
  • 1978Proof, with Roger Camrass, that packet switching is optimal in the Huffman coding sense.
  • 1988Data Networks: a book written with Dimitri Bertsekas that helped establish the conceptual foundations of data networking.
  • 1996Discrete Stochastic Processes: a textbook on discrete stochastic processes, systems that evolve randomly.
  • 2008Principles of Digital Communication: a textbook on the principles of digital communication.

Teachers and students

Studied under:

Taught:

Erdal ArıkanMuriel MédardElwyn BerlekampDavid TseSerap Ayşe SavariLi ShuAbhay Kumar J. ParekhRandall Alexander BerryRoy David YatesEmre TelatarRajesh PankajJohn Turner Pinkston, IIIShan-Yuan HoJohn Michael Spinelli

See their academic family tree →

Trivia and anecdotes

Forgotten codes

Low-density codes fell out of use for decades because they were too costly to implement with the technology of the time.

9600 bit/s modems

His work on quadrature amplitude modulation, done with Dave Forney, led to 9600 bit-per-second modems.

Their contemporaries

While Robert G. Gallager was alive (1931–)…

Alive at the same time

Discovered or invented in those years

  • 1931
    Big BangA cosmological model describing how the universe expanded from an early state of extreme density and temperature, about 13.8 billion years ago.
  • 1932
    NeutronA subatomic particle with no net electric charge, found in the nucleus of almost every atom alongside protons.
  • 1945
    ComputerA programmable machine that takes in data, processes it by following stored instructions, and produces results, able to switch tasks simply by running different software.
  • 1969
    InternetA global network of interconnected computer networks that communicate using the TCP/IP protocol suite.
  • 1973
    Mobile phoneA handheld wireless phone that lets people make and receive calls while moving across a cellular network area.
  • 1989
    World Wide WebA system of linked documents and resources, connected by hyperlinks and accessed over the Internet with web browsers.

See this life on the timeline →

More people in Computing