Photo: joSon
These days, in developed countries, you can’t so much as rent a car or buy a shirt without setting in motion a burst of digital information spanning hundreds of kilometers. Data stream toward a waiting credit card database through the air, over cables, and back again, bouncing and meeting interference, and encountering other signals along the way. And yet the right bits get to their destination not just usually, but virtually without fail, statistically speaking. They emerge from the noise with the seeming magic of a rabbit coming out of a hat.
Just as in a magic show, however, there’s a lot going on behind the scenes: in this case, algorithms that electrical engineers, computer scientists, and mathematicians have been refining for decades. And the roots of many of those algorithms go back to one master magician, Thomas Kailath.
Kailath, a professor emeritus at Stanford University, has worked for four decades on algorithms that detect signals distorted by bouncing off objects in the environment, separate wireless signals by determining their direction using antenna arrays, and compensate for the distortion of optical systems used in semiconductor processing. And, though Kailath spent most of his career in academia, his efforts to see his algorithms make a difference led him to cofound no fewer than four start-up companies.
Along the way, he established new ways of structuring complex problems to speed up their calculation. This work has improved the efficiency of much of the technology that makes modern life possible—not only paying for gas and clothing by credit card but also sending text messages and video images to cellphones. It is for this body of work that Kailath was awarded the 2007 Medal of Honor, the IEEE’s highest commendation.
Kailath didn’t seem destined for a technical career. Growing up in Pune, India, he so dreaded math class that in sixth grade he would duck behind the student in front of him so a sarcastic teacher wouldn’t call on him. He passed exams that year by memorizing the solutions to all the homework problems. However, a rather good thing happened that year, too. The scary math teacher introduced the class to geometry, and for the first time, Kailath realized that math could be engaging. Maybe even more than engaging. He started getting together with classmates to work on proofs. For fun.
Still, he didn’t think much about math as a career. He assumed he would go into the civil service, a typical route for a middle-class kid in India. However, the civil service had strict vision requirements, and the myopic Kailath didn’t meet them. Plan B was to work for All India Radio, a state-owned broadcast monopoly. He enrolled at the University of Poona (now called the University of Pune).
In 1950, his first year at Pune’s Ferguson College, he was blissfully perusing magazines in the stacks of the school library, when he came upon an article in a 1949 issue of Popular Science explaining the basic idea of a new field called information theory. The article speculated about how it would be applied to the then-emerging technology of television broadcasting, pointing out that you could use less bandwidth by sending only the changes between television frames, not each frame in its entirety. It was but one use for information theory, but the article predicted that there would be many others.
For the young Kailath, standing in the quiet, wood-paneled, high-ceilinged room, it was a revelation. Not only was the idea appealing, but he found the name itself, “information theory,” attractive. It involved the concepts of mathematical proofs that he had so loved in geometry and also offered the possibility of practical applications, such as improving telecommunications. He began to read more about the subject, including Claude Shannon’s and Norbert Wiener’s pioneering books; this reading was a relief from his less theoretical engineering courses. Kailath had found his calling, and in 1956, approaching graduation, he sent letters to MIT and Harvard asking to be considered as a graduate student in the field. Both accepted him.
On 30 August 1957, after a long journey, mostly by ship, he unpacked his bags at MIT. He was to become the first India-born student, but certainly not the last, to earn a doctorate in electrical engineering from that institution. And to Kailath’s delight, Shannon had just become a professor there.
So began phase one of Kailath’s four-phase career. Each phase lasted approximately a decade, and each involved distinct technical fields. Kailath picked up each wave as interest in the technology started to build, rode it until he made a major contribution, and then, while the ripples created by his work moved into wider circles, quietly withdrew to explore other technological seas. In the late 1950s and throughout the 1960s, Kailath focused on communications. In the 1970s, he turned to control theory. The 1980s found him looking at how signals could better be detected by antenna arrays and problems in very-large-scale integration (VLSI) chips. And in the 1990s, he made his biggest leap, into semiconductor manufacturing.
His colleagues credit this wanderlust for the freshness of perspective that underlies Kailath’s diverse contributions. Says Patrick Dewilde, scientific director of the ICT—Delft Research Centre, in the Netherlands: “In science and technology many fields have a certain tradition, a certain way of thinking about problems. That is effective when it is first discovered but later it gets in the way of innovation. Tom had these flashes of insight into fields in which he was not an expert originally because he brought in connections from other experiences.”
“Tom has a broad knowledge. And he is never satisfied with the first explanation or answer to a problem. He digs deep to find the most intuitive and eloquent explanation,” says Ali H. Sayed, professor and chairman of the electrical engineering department at the University of California, Los Angeles, and a former student of Kailath’s. “This approach is rare.”
Kailath’s first major contribution came directly out of his research at MIT. Robert Price and Paul Green had just developed Rake, a system for communicating in a constantly changing environment with a lot of scattering, where the signal arrives at the receiver via paths with random strengths and varying delays. The intended application was for military communications that were being jammed, although Kailath was not aware of this at the time.
Kailath’s advisor, Jack Wozencraft, suggested that for a master’s thesis Kailath try to develop a mathematical model for these constantly changing channels and then identify the channel by sending in “test” signals. It took him months of work, mostly in his head, occasionally on paper. After almost giving up, he found a condition of channel parameters under which identification was possible by assuming that signals are both time and frequency limited, even though, mathematically, a signal cannot have a finite duration and a finite bandwidth.
This way of understanding and characterizing changing channels was a step along the way in the development of cellphone systems. While researchers elsewhere were doing similar work, much of that was proprietary; Kailath’s work, being in the public domain, helped speed research in cellphone technology.
Just last year, Götz Pfander from the University of Bremen and David Walnut from George Mason University finally completed a full mathematical proof. They published it in the November IEEE Transactions on Information Theory and credited Kailath’s work.
Kailath’s success in solving this problem, and his doctoral research on the detection of random signals in noise, got considerable attention and led, 18 months after his graduation, to an associate professorship at Stanford University.
There, Kailath and a graduate student worked out a theory for using a separate feedback channel to provide information about noise in a communications channel and adapt the incoming signals to move through the noise. That work has yet to find practical application. But in the past few years, a new generation of researchers in communications networks, where two-way links are ubiquitous, has become interested in it, Kailath says, so it may still get used. That makes him happy.
And that’s what makes Kailath an engineer, as opposed to a mathematician. “I want some potential application in mind,” he says. “Even though my ideas may never be implemented in my lifetime, I want them to be potentially applicable.”
In the early 1970s, Kailath began working with problems in control and linear systems and design of VLSI chips. He didn’t like the standard university textbooks in linear systems, which separated the study of the mathematics from the engineering applications. So he wrote a textbook that blended the applications with the mathematics. Linear Systems, first published by Prentice-Hall in 1980, changed the way this field was taught—and won Kailath the IEEE Education Medal. He also tackled VLSI design, starting a research group on the design of VLSI chips for signal processing applications. The group developed computer algorithms for the systematic design of special-purpose chips, replacing many steps that previously had had to be done by hand.
In the 1980s, a local engineer, Ralph Schmidt, talked to Kailath about a different way of attacking an old problem—determining the directions of signals being received by an antenna array. Schmidt proposed using a combination of geometric and algebraic concepts to separate signals closer in direction than had been possible with earlier methods. Kailath was intrigued by the idea, encouraged Schmidt to develop it into a Ph.D. thesis, and launched a research group to pursue sensor array processing. The group laid the groundwork for what came to be called the Esprit algorithm, discovered by Arogyaswami Paulraj, then a visitor in Kailath’s group (both Kailath’s and Paulraj’s names are on the patent). Esprit is now used in military surveillance. In 1993, Paulraj, who had returned to Kailath’s group as a research associate, began to redirect the array-processing research to wireless communications. The new team developed spatial multiplexing in multiple-input multiple-output, or MIMO, antenna systems. MIMO significantly improved wireless performance and is now used in Wi-Fi, WiMax, and other wireless communications standards.
In 1990, Louis Auslander, then manager of the mathematics research program at the Defense Advanced Research Projects Agency (DARPA), mentioned to Kailath that he’d like to fund some of Kailath’s research and asked him to send a proposal. But after the proposal arrived, Auslander called Kailath with bad news; the money to fund mathematical research had already been committed. But Auslander had an idea—because the U.S. government was then worried about Japan’s surging manufacturing prowess, there was lots of money available to fund research in manufacturing. Would Kailath be interested in moving into that field?
Kailath wasn’t sure, but he thought it couldn’t hurt to check it out. He walked down the street to ask the researchers at Stanford’s Center for Integrated Systems if they had any interesting problems. It turned out they did: they told him they would love to know exactly how fast you could heat and cool a wafer as part of the semiconductor manufacturing process.
The semiconductor industry generally processes wafers in batches. Dozens of wafers go through one step in the process together and then go on to the next step. At several points in the manufacturing process, the wafers go into large ovens to be heated to about 1000 C. Then they slowly cool to room temperature before moving on to the next step in the process. With large batches of wafers scattered around an oven, designers have to expect a certain amount of variation in heating and cooling. Manufacturers wanted to process wafers one at a time, which would mean more uniformity. For such single-wafer processing to be commercially viable, however, each step had to happen as close to instantaneously as possible. If it didn’t, the process would be too slow to be commercially viable. But when manufacturers heated or cooled wafers too quickly, the wafers warped.
Kailath set out to determine the optimal heating and cooling process. With colleague Stephen Boyd and several students, he made a mathematical model of a silicon cylinder. He used a cylinder because he felt the wafer shape was too complex and a cylinder would yield nearly the same results. While the conventional wisdom indicated that wafers should be heated uniformly, Kailath and Boyd determined that two or more independent sources of heat, applied unevenly, would allow a wafer to be heated quickly without warping. Though single-wafer processing did not take the semiconductor industry by storm, its use is growing. [See “Chip-Making’s Singular Future,” IEEE Spectrum , February 2005.] Applied Materials, in Santa Clara, Calif., sells some US $550 million worth of single-wafer processing equipment annually, a 78 percent market share.
That wasn’t Kailath’s only significant contribution to semiconductor fabrication. He went on to determine an efficient way to calculate how much a mask used for etching the circuits on a microchip needs to be distorted to compensate for the distortion of the optical system that focuses the etching beam. By compensating for such distortion, designers have been able to fit a vastly greater number of transistors on a chip without changing the physical chemistry of the chip or the manufacturing process. Such phase-shift masks and related resolution enhancement techniques are widely used in semiconductor manufacturing today.
Although Kailath spent most of his career at Stanford, working his way through the professorial ranks to director of the Information Systems Laboratory and associate department chair, Stanford didn’t completely keep this professor down on “The Farm,” as that university is casually called. Kailath took full advantage of the sabbatical system, working at various times in Belgium, England, Germany, India, Israel, and the Netherlands, as well as at Bell Labs and MIT in the United States. He also became one of the many Stanford professors to catch Silicon Valley’s start-up fever.
In 1980 Kailath cofounded Integrated Systems to do contract research in control systems and signal processing. One of the engineers at Integrated Systems developed some software to extend the popular Matlab package to speed up the design and simulation of control systems. Integrated Systems decided to sell that software commercially, and by 1990, when the company went public, it was bringing in about $12 million annually. “We made a fair amount of money,” Kailath recalls. “Not on the scale of companies that go public today, but in those days, a few million was a lot.” Kailath could have retired comfortably at that point, or at least upgraded his lifestyle. He didn’t. “My wife and I made some investments, got involved in some charitable ventures, and put money in trusts for our kids,” he said. But they kept living in the Mediterranean-style house they had built in 1968 on Stanford property not far from his office. (Integrated Systems merged with Wind River Systems in 1999.)
In 1995, with his postdoctoral scholar Buno Pati and his Ph.D. student Yao-Ting Wang, Kailath started Numerical Technologies to commercialize their methods for compensating for lens distortion in semiconductor processing. Pati took the company public in 2000, and in 2003 it was acquired by the design automation toolmaker Synopsis, in Mountain View, Calif. In 1998 former student Debu Pal invited Kailath to join in starting Excess Bandwidth Corp. to develop technology for symmetric DSL, which differs from today’s more typical asymmetric DSL in that the upstream and downstream data rates are the same. Virata Corp. acquired the company in 2000; it’s now part of Conexant Systems (formerly Rockwell Semiconductor).
In his most recent venture, in 2003, he joined three former colleagues from Numerical Technologies in founding Clear Shape Technologies to commercialize mathematical modeling techniques that predict chip faults, like shorts and open circuits, that could be caused by the manufacturing process. The Santa Clara—based company raised $10 million in venture capital and in 2006 introduced two design-for-manufacturability tools.
Kailath handles business challenges with as much aplomb as technical ones, says Bill Davidow, a partner in Mohr Davidow Ventures and one of Silicon Valley’s pioneering venture capitalists. Davidow, who served on the board of Numerical Technologies, recalls Kailath as being the judgment icon: “Everyone in the company, employees and management alike, would constantly seek his advice. He was able to help people get through rough periods, because he had their confidence. I recall one key technical contributor who I am convinced would have been out the door without Tom’s ability to make him feel better.”
Kailath stepped down from teaching in 2001 after over seeing nearly 80 Ph.D. theses, an impressive number. Copies of every single one of them line the walls of the tiny office he still maintains on campus, their cardinal-red spines dominating his bookshelves. He follows the careers of many of his former students, like Guanghan Xu, whose Beijing-based company, growing out of his Ph.D. research in the array-processing group, now has 2600 employees. It took Kailath a few years to wind down his research projects, however, and he continued to supervise students until 2004. These days Kailath still finds time for colleagues and students seeking advice or encouragement. He remains on the board of Clear Shape.
So what research area would he be plunging into now if he were launching a fifth phase of his career? One word: biotechnology. Stanford’s interdisciplinary biotech program intrigues him.
And while researchers from many different disciplines are tackling problems in biotech, Kailath thinks it still has room for mathematical engineers. “We have a different approach,” he says. “And our fundamental tools—some from control theory, some from information theory, some from linear algebra—are pretty powerful.” Powerful indeed, and perhaps, in the hands of the right person, just a little bit magic.
