Logo: University of Southern California

Elwyn Berlekamp Delivers Viterbi Keynote Lecture, "Adventures in Coding Theory"

The distinguished UC Berkeley professor emeritus presents a talk full of reminiscences and puzzle-solving to the keynote namesake and others

March 04, 2011 —

Introduced by Ming Hsieh Department of Electrical Engineering Systems Chair Alexander Sawchuk, the ninth Viterbi Lecturer spoke to an audience of academic celebrities including several scientists whose work he discussed.

Berlekamp 3
Ming Hsieh Systems Chair Sandy Sawchuk, Elwyn Berlekamp, Andrew Viterbi, Dean Yannis Yortsos
Elwyn Berlekamp, an emeritus professor at Berkeley who is a member of the NAS, NAE and AAAS spoke about “Adventures in Coding Theory.” In the front row center was coder Andrew J. Viterbi, namesake of the series and the school and a frequent reference in the talk, seated next to his former teacher and fellow coder, the Viterbi School’s Sol Golomb, with Dean Yannis C. Yortsos nearby.

Three rows back was Caltech’s Robert J. McEliece, who delivered the Viterbi Lecture in 2007, and whose work in what Berlekamp called “the golden age of JPL consultants” was another frequent footnote.

So was the work of the Viterbi School’s Lloyd Welch, seated with his wife near the podium.  Welch was the co-author of some of Berlekamp’s patented coding inventions. Len Adleman, on whose doctoral committee Berlekamp had served, was also in the audience.

Not in attendance, but invoked in name was Irving Reed, co-creator with Gus Solomon of the Reed-Solomon codes, development of which was a highlight of Berlekamp’s illustrious career.  That career included great entrepreneurial success in finance and computers, in addition to his renowned academic achievements.

The presentation took off from three problems, sharing what the lecturer said was a starting point for scientific thought: arresting, simple to state, but problems that would take more than an hour or a single day to solve, and all with connections to algorithms that link to coding theory.

One of these, known as the coins, had caught his attention as a 10-year old batboy in Kentucky in 1950. (You have 12 coins. You know one is counterfeit and either heavier or lighter than the genuine articles. You have a balance. Your assignment: to find the fake coin in three weighings.)

The young batboy concentrated, persevered, solved the problem, and was hooked: he

Berlekamp 1
Sandy Sawchuk, right, presents USC hat....
found ‘math is fun,’ and went on to create solutions, working with or influenced by (in addition to the people in the room) names such as Hamming, Shannon, Gallager, Elias, Kelly and others.

Added to these Added to these were many faculty of the Hsieh Department, shown in a PowerPoint slide (see below) that displayed their photos in rows, all wearing hats, some red, some blue, as part of Berlekamp's analysis of the hat game. (You are wearing either a red or blue hat. You cannot see the hat on your head, but you can see all the others. The task is to guess the color of your own hat, when your turn comes up.) The strategy involves team play, is not at all obvious, but works impressively well.

...and Viterbi t-shirt
Berlekamp’s elucidations of these two problems and a third (a version of the old game of NIM, solved by statement in binary form) and their legacies in coding theory were combined with his memories of the environment of the coding frontiers in the sixties and seventies, a kind of glowing era in which he briefly served as an assistant professor at the University of Southern California, before leaving for the north.

During these times, celebrity coders from the Bay Area had an arrangement that enabled them to travel by jet and helicopter to the JPL campus in only two hours total travel time. Times have changed…