In late 1996 and 1997 Dr. G. David Forney, Jr. was awarded both the Marconi International Fellowship and the Christopher Columbus Prize in International Communication for his contributions to the field of data transmission technology. These awards were described at greater length in the March 1997 issue of the Newsletter. At the request of the Editor, Professor Robert Gallager of the Massachusetts Institute of Technology held the following conversation with Dr. Forney.
Interview Friday, April 4, 1997
Bob: First, congratulations on winning both the Marconi award and the Christopher Columbus award recently. You certainly deserve these awards on the basis of your research career alone, and also on the basis of your industrial career alone. Since our readers are probably more familiar with your research career, let's start with the industrial side. Tell us about your first years at Codex (now part of Motorola).
Dave: I'm quite sure that I first heard about Codex from you. When I was finishing my doctoral thesis at MIT, everyone was saying that there wasn't much academic future for information theory; we knew how to get close to channel capacity and the real action was going to be in applications. That was fine with me. You suggested looking at Bell Labs, IBM Labs, and maybe Codex. I interviewed at all those places and got offers from each. Codex was my lowest offer, but I liked the idea of this little start-up. There weren't very many start-ups in the world then. I believe that Codex had 12 people there at the time, and I accepted their offer.
Bob: When you got there, I recall that you were working on error correction. Tell us a little about the products, their commercial success, and your role in them.
Dave: Initially most of our business involved convolutional burst-error-correcting decoders for government applications. When I arrived, Codex was just putting its first standard product into production, the TD-12 error-corrector (for threshold decoder, constraint length 12). Arthur Kohlenberg asked me to look at the threshold decoding equations. When I did, I thought I saw a way to save two flip-flops. Now at this time a flip-flop came in a large 1"x1"x2" epoxy package, so saving two of them was a big deal. After Jim Massey verified that the new equations were OK, the order went out to stop production and redesign the TD-12. I felt that my career at Codex was off to a good start.
However, most of my work in the first two years was on coding for the NASA Pioneer deep space missions. We started out looking at threshold decoding, but with the encouragement of Dale Lumb at NASA Ames Research Center, I ultimately designed and programmed a rate-1/2 sequential decoder that was able to obtain more than 3 dB coding gain at 10^{-3} error probabilities at data rates up to 512 b/s, using a commercial Honeywell minicomputer with a 1 MHz clock rate. So this decoder extended the range of the Pioneer satellites by a factor of 1.4. It turned out to be the first coder to go into space, and as of a few months ago, at least one of those Pioneer spacecraft was still operating.
Bob: I remember you working on sequential decoders. I was impressed that your design was so much simpler and more elegant than what Lincoln had done a few years earlier. It was a great job of engineering.
Dave: Thank you, but probably the sequential decoder you're thinking of was a much higher speed 5 Mb/s device that we built for the Defense Communications Agency. That was for an earth-orbiting satellite communications system, and we did build hardware that was quite elegant. It used the Fano algorithm, which seems to be not too widely appreciated nowadays, but which goes incredibly fast in hardware. Our decoder ran at 15 MHz and could handle up to 5 Mb/s of data. It was also an important experience for me because it taught me how to design with TTL logic, which was useful later for modems.
Bob: Did you feel that the Codex products were ahead of the market need, or did you think it was just a problem of educating the market?
Dave: I was young in the business world at the time, but it was becoming obvious to all of us that a stand-alone error-correction business didn't make sense. Our business was to put bandages on systems that had already been designed. If the system was running at 10^{-2} error probability, then coding couldn't fix it, but if it was running at 10^{-5}, then it was already good enough, so there was only a narrow window for improvement. We were able to get some business, almost all from the government, but it was becoming clear to management and to me that stand-alone error-correction was not the way to go.
Bob: At what time did Codex start getting into the modem business and start achieving commercial success?
Dave: It started through the acquisition of Jerry Holsinger's group from a California defense firm. I believe that you were the person who brought Jerry to the attention of Codex management. He was working on the design of a single-side-band 9600 b/s partial-response modem, but had come to the conclusion that it didn't belong in a defense company. What Codex acquired was Jerry and another guy, plus the beginnings of the hardware design for what eventually became our AE-96 modem. I believe that the acquisition was in 1967 and that the AE-96 first appeared sometime in 1968. It was a large beast that sold for $23,000. But it was the world's first 9600 b/s modem, and there was a lot of interest in it.
Bob: Tell us a little bit about how Codex started to make the transition from a single-side-band modem to quadrature-carrier modems and a broader product line.
Dave: The AE-96 worked, but not reliably. There were a lot of circuits that had problems, which we ultimately discovered were due mainly to phase jitter. We nonetheless sold a couple of hundred of them. After Jerry left Codex in 1969, I became much more involved in modems. I designed a partial-response error-correcting circuit for the AE-96 that gained us 2-3 dB of margin and extended the life of the product for a year or two. Meanwhile, the marketing vice-president, Art Carr, wanted to sell a broader range of products. At that time, you had been looking into the basic theory and structure of QAM modems, and I had been following what you were doing.
To make a long story short, I started on the development of a 4800 b/s QAM modem in February 1970. In that year we were essentially forced to make a total transition from government to commercial business for all kinds of reasons. The government business was drying up generally and for error-correction in particular. Also the company had some serious tragedies that year. Jim Cryer, the president, dropped dead of a heart attack on the tennis court, and Arthur Kohlenberg succumbed to Hodgkins' disease. The company was out of money, out of products, and out of markets. The only thing going for us was this 4800 b/s modem I was designing. There was also a very stalwart board of directors, who scraped together a million dollars to keep us going for maybe another twelve months. We went from 200 people down to about 90, and we concentrated on getting this modem plus an accompanying multiplexer out the door.
Bob: I remember that project as an almost single-handed effort on your part to actually design that 4800 b/s modem. There were a number of other people doing bits and pieces, but you were not only the central architect but also did a great deal of the detailed design.
Dave: Yes, I was the chief designer, and I did all the detailed TTL logic design, which I had learned how to do from the sequential decoder project. The analog circuits, the dynamic shift register memory, the packaging, and so forth were done by others. Also, I always felt that I was building on your earlier work on double-side-band quadrature-carrier modulation and signal constellations. We worked very closely together. I remember initially I had a strange 8-point asymmetrical constellation that you kept telling me was ugly, and ultimately I ripped it out and put in a symmetrical two-ring 8-point constellation.
Bob: How long was it after that design that the 4800 b/s modem was in full production? It seemed very quick compared with the product cycles that I was familiar with at Bell Labs.
Dave: You have to remember that we were in survival mode then, and totally focused on this project. We introduced the modem at the Fall Joint Computer Conference in Houston in December 1970. It was not quite ready for shipment then, but it was shipping a few months later in early 1971. So from concept to shipment, it was about a year. Then we followed up with a 9600 b/s QAM modem which was to a large extent an extension, although it required quite a bit more logic. It came out later in 1971.
Bob: I guess after the great commercial success of these modems, you started to have more and more people working for you. How did you enjoy being a manager and executive?
Dave: My career as a manager didn't happen that quickly. First, I went to Stanford for a year in 1971-72, wondering whether I might want to be a professor. It was a good year, but I decided to remain at Codex. I continued as head of research until 1975. During this time we started our second-generation LSI-based modem in partnership with Rockwell. This put Rockwell into the high-speed modem business, and turned out to be a great deal for both of us. I also hired Jim VanderMey, who began to develop our first network products.
In 1975 there was a major reorganization in the company, and I became head of all "innovations," including research, development, product planning, and strategic marketing. I had well over 100 people working for me and the character of my life changed. I tried to keep my hand in technical issues but really couldn't. As a member of the Board of Directors at Codex, I was very much involved in our acquisition by Motorola in 1977. From 1982 to 1986, I was a group executive for Motorola as the number 2 person under Art Carr in the Motorola Information Systems Group, which oversaw Codex, UDS (an Alabama modem company), and Four-Phase Systems (a California minicomputer company). That was certainly the least satisfying job I ever held, partly because of the intrinsic nature of a a group executive position and partly because of the intractable problems at Four-Phase.
Bob: I remember at some point during that period that you had a lot of technical fun working on large lattices with your Canadian subsidiary ESE. You seemed to be getting back to serious research while you were still an executive.
Dave: Yes, I was never completely out of touch with research. Gord Lang was vice president of research at ESE. He and Rudi De Buda were great advocates of using lattices to get to channel capacity on additive white Gaussian noise channels; lattices seem to have been perpetually popular in the British Commonwealth. Gord had even made proposals in the early 1970s for an E8 lattice modem to the CCITT. I remember going up there once when Coxeter was visiting. He was almost 90 then, and he was fascinating.
I did begin learning about lattices at that time, but what really got me back into technical work was the advent of the V.32 modem standard development and its requirement for trellis coding, which we had been doing some work on at Codex. I happened to be in London in 1983 for the first key CCITT meeting, where Bell Labs proposed a sort of one-dimensional trellis code and Gord Lang proposed a lattice code. I suggested that we ought to look at a paper by this fellow Gottfried Ungerboeck, and then we were off and running. I started regularly attending the standards meetings and getting deeply involved in trellis coding technology.
Bob: Facetiously, are you the only technical person who has ever managed to do real technical work at a standards committee?
Dave: Well, no, not at all. The committees on modem standards have really done an extraordinary job over the years in coming up with the best practicable technology. It is quite typical for invention to occur during the standards process, with the final result being better than any individual contribution. The V.29 standard, which was the original 9600 b/s private line modem standard, was to a large extent written around our 9600 b/s modem. But there were a number of improvements during the standards process. The V.32 standards process stimulated considerable innovation, particularly in trellis coding. Lee-Fang Wei ultimately invented a nonlinear 8-state two-dimensional rotationally invariant trellis code that caused the theorists to scratch their heads for quite a while. More recently, the V.34 standard was a marvelous example of innovation in many areas, including trellis codes, shaping, and precoding. So I think that the modem standards groups have a pretty good record.
Bob: We seem to be talking mostly about research now, so perhaps we should start back with your days as a student and work up through your research career from the beginning.
Dave: I was really lucky in my education. I believe that I had about the best education that the U.S. has to offer. I went to an outstanding private elementary school, New Canaan Country School. Then I went to Choate, a good private boarding school, to Princeton as an undergraduate, and finally to MIT as a graduate student. It would really be hard to improve on any of those. I've always felt that the most important school is the first, because that's where you get excited about learning.
At Princeton, going into engineering was in some ways a fluke because I didn't know at all what I wanted to be. The catalogue said that you could go from a BSE to an AB course but not the other way, so declaring for a BSE seemed like a good way to keep my options open. Also, at that point my mother had just married J. S. McDonnell, head of McDonnell Aircraft; he was an engineer and my two older step-brothers were both engineers at Princeton, so that also influenced me toward engineering. I took the absolute minimum of EE courses at Princeton, at most 2 per term, which was possible in those days. I took lots of courses over a wide spectrum: philosophy, architecture, sociology, literature, physics. I wish I had taken more than one math course. I very much believe in getting the broadest possible education as an undergraduate, but I think it's very hard to do that now. Engineering curricula have gotten so full that there are few chances for electives, even at a place like Princeton, and certainly at MIT.
When I graduated from Princeton, I still wasn't sure that I wanted to go on for a PhD. I really came to MIT because I was interested in a girl at Wellesley, who I married a year later. Otherwise I probably would have gone to Stanford or CalTech. You know that at MIT I got serious about engineering. I recall that I was attracted to information theory by your course, and I wound up doing an interesting master's thesis in information theory and quantum mechanics (which I've always intended to come back to, but never have).
Bob: I remember your doctoral thesis very well. Your monograph on Concatenated Codes, and the papers that came out of the thesis, are still widely read and have had an enormous impact. Tell us how all of that came about.
Dave: When I finished my master's thesis, people were saying that information theory was dead and I should go find something else. I think even you were guilty of that, though less so than others. I spent a pretty unfocused, unproductive, and unhappy six months looking around operations research and elsewhere. But then a very fortunate thing happened. Claude Shannon taught an advanced seminar called Topics in Information Theory, and his method was great. He just got up to the board and started talking about problems that he had been thinking about, some of which he had made some progress on and some of which he hadn't. It was similar to a thermodynamics course that I took from John Wheeler at Princeton. His method was just to stand up and talk about how to attack various thermodynamic problems that he had encountered in his consulting -- desalinization in the Arizona desert and so forth. I did a term paper in that course on Brillouin's book on Physics and Information Theory, which was probably the real beginning of my interest in information theory.
Anyway, during Shannon's course, I got interested in one problem and got some results, and then in another and so forth. Before I knew it, I was back doing information theory again. I think that it was Jack Wozencraft who suggested that it might be helpful to code with more than one code, and I started running with that idea, which fairly quickly started looking like a doctoral thesis. There were three papers that came out of the thesis if you count the monograph. One was on erasure-and-error correction for BCH and Reed-Solomon codes. I believe that I was one of the first to recognize the value of Reed-Solomon codes. I tried to understand their decoding algorithm, and found a way to decode erasures as well as errors. Then I came up with the idea of using soft information in what I called generalized minimum distance decoding. I'm pleased to see that this has become a hot topic again -- just like your low-density parity-check codes. It's one of those ideas that lies fallow for 30 years and then the time becomes ripe. Finally, my over-arching idea was concatenating codes, which I was doing to solve a theoretical problem. People had realized by then that the basic problem was performance versus complexity. What good is exponentially decreasing error probability if the complexity is exponentially increasing? The thesis was aimed at improving this tradeoff between performance and complexity, specifically to get exponentially decreasing error probability for all rates less than capacity with polynomial complexity.
I remember presenting my results at places like Bell Labs and putting Reed-Solomon codes with four-digit block lengths up on the board. People sort of rolled their eyes and were obviously thinking, "This guy isn't very practical." However, somewhat to my surprise, within ten years concatenation became a very useful and practical tool for such applications as space communications. But I do believe that there was a fair element of luck that the thesis came together as well as it did, with at least three quite different ideas meshing in a very nice way.
Bob: I think that it's certainly true that there's a great deal of luck in any thesis. But some people recognize when they are lucky and other people ignore it and go off in some other unlucky direction. How about the research part of your career in your first few years at Codex?
Dave: I was very lucky being in a place like Codex where I had the chance to do some research as a hobby and to produce about one paper a year. It would be a rather leisurely production schedule for an assistant professor. Fortunately, I didn't have the pressures of an assistant professor and was able to really think about papers and not submit them until I was happy with them.
Another reason that I was really lucky to be at Codex is that the problems there led so naturally to nice research. While I was working on error correction, it was clear that convolutional codes were much better than block codes in terms of performance versus complexity. Yet we had no theory for convolutional codes. This is what really motivated me to produce some of my early papers on convolutional codes, one on their algebraic structure and two others on maximum likelihood and sequential decoding. During my NASA work, I came up with the idea of a trellis to understand convolutional codes and also to understand the Viterbi decoding algorithm. That may perhaps be the longest lived of my ideas, although it seemed pretty simple at the time.
The work on the algebraic structure of convolutional codes got me into linear system theory, because the algebraic structure theory is very closely related to that of linear systems. Fortunately this was just at the time when the state space approach of Kalman and others was becoming widely enough known so that I could read it. Massey had been working with Sain out at Notre Dame on tying these two things together. I was in close contact with Jim Massey, so the time was very ripe.
Bob: Why don't we go on to the time that you spent in Stanford where, I remember, you wrote a very nice set of notes on Information Theory which were used by quite a few people afterwards. Could you make some comments on that?
Dave: In 1971, I was exhausted from modem development and also had a nice invitation from Stanford, so I thought I'd really give the professor thing a try. I taught the Information Theory course in the fall and spent a great deal of effort in thinking about the course and developing these notes. Yes, they did seem to be highly popular for quite a few years. Hundreds of copies circulated around. But I also taught a coding course in the spring. My method for that was very different. I just came in and talked about coding problems, how you solved them and so forth. The student reviews that I got for the coding course were actually much better than for the information theory course. The information theory course was predominantly taken by masters' students, most of whom thought it was too hard, too abstract, and not immediately useful. The coding course was taken more by third-year graduate students, who loved the intellectual elegance of it. But also I think I probably taught it better.
While at Stanford, I met a number of outstanding people working on linear system theory. I learned enough more about it to produce my one paper in the SIAM Journal on Control. This was basically a rewrite of my paper on the algebraic structure of convolutional codes, written for a system theory audience. About 15 years later, I found that this had had a tremendous impact in system theory and that everybody knows this famous paper. For me, however, it was a case of "I shot an arrow in the air, it fell to earth I know not where," and for a long time I had no idea what became of it.
Bob: Tell us something about your research after you returned to Codex from Stanford and after you became an executive.
Dave: When I became head of R&D at Codex, I found that I wasn't able to keep up in research at all. I even stopped going to Information Theory Symposia from the one at Ronneby in Sweden in 1976, until the one at Brighton in 1985. Even this was by chance, since I just happened to be in England for other reasons and decided to drop in on the Brighton Symposium. It was great fun. I saw all my old friends, went to a lot of sessions, and found I could understand much of what people were talking about -- not that different from what they were talking about 10 years earlier! Shannon was there. That was certainly a major stimulus to my wanting to get back into the field again. I had also just written a review paper on modulation and coding with you, Gord Lang, Fred Longstaff and Shahid Qureshi back in 1984. This was one of the first tutorial papers in this area, and as usual I learned a lot by writing.
Bob: It was much more than tutorial. There were a lot of new results in it.
Dave: Well, there were a number of new results, but I think what I was trying to do here as always was to understand what was going on -- to separate effects. For instance, I believe that separating shaping from coding was a significant conceptual contribution, rather than a "result." Likewise teasing out the key parameters that determine coding gain and constellation expansion were conceptual contributions.
Trying to understand coding in Euclidean space led me into my coset code papers, which evolved for a few years until Dan Costello finally forced me to publish them as invited papers in the IT Transactions. The notion of geometrical uniformity led to group structure and ultimately to the group code work with Mitch Trott, which in turn ricocheted back into system theory, since it turned out that this was closely related to Willems' work in behavioral system theory. We were able to extend much of what he was able to say about linear systems to group systems. In some sense, the group systems seemed more transparent. On other fronts, my work on shaping and on coding for intersymbol interference channels has led to a variety of practical developments in combined coding and equalization and a lot of tangled threads.
Bob: Over the last 10 years, you've had an enormous number of papers in this area of modems, group structure, geometric structure, and also the question of the capacity of these coded systems. This seems to be a rich field that goes on and on. Do you have a plan for pursuing these problems?
Dave: Basically, I just follow my nose. It's always been my experience throughout my career that if you look at the right problem in the right way, and ask the right questions about it, you come up with nice results-- sometimes brand new, sometimes simply clarifications of what other people have sensed. But I've never had any problem finding fascinating new areas of research that continue to have relevance to the real world.
We now know how to get very close to channel capacity on an arbitrary non-ideal Gaussian channel. That's the central thread of what I've been working on ever since I worked on space communications at Codex, where the channel was an ideal power-limited white Gaussian noise channel. The modem channel is a non-ideal band-limited non-white Gaussian noise channel. In V.34, and more recently in turbo codes, in new kinds of low-density parity-check codes and so forth, we know how to get very close to capacity, and that's almost true in a practical sense as well. So, it's going to be hard to justify to deans and funding agencies that there are huge practical advances to be made here.
But there are still large areas that are not understood very well. Turbo codes is the most obvious one right now. Like other developments I've mentioned, turbo codes work very well, but we don't understand them. That was the state of convolutional codes when I arrived at Codex. We had inventions and particular examples that worked very well, but there wasn't much theoretical understanding. So, I think that's a problem that's worth working on. Invariably, in my experience, if you tackle a problem that's thrown up by reality, you will discover things that will have ramifications in areas that you didn't dream of when you started. So my research philosophy is basically that one thing almost always leads to another and the hell with long-range planning.
Bob: Do you ever think of going seriously into the wireless field, where we have multiple users, multiple receivers, multipath, rapid variation of channels, and so forth? Do you view this as a new challenge, or is it just much too complicated?
Dave: Well, I'll admit I'm a little bit intimidated by it. I think what's really happened with me and wireless is that I haven't had the practical motivation that I've had in these other areas, which is what has always driven me. I'm in the peculiar situation of being in a premier wireless company, but in the part of it whose charter is to do non-wireless things. Within Motorola, we're the wireline group. So I've never actually worked on any real wireless problems and I haven't gone through the process that I've gone through in other areas of getting interested, wondering why, and then starting to smoke out what's really going on. I don't doubt that there are wonderful things for people to do who have gone through that process.
Bob: Thank you, Dave. Its been a delight to interview you, and to provide our readers with a better sense of what makes your research tick.