IEEE
You are not logged in, please sign in to edit > Log in / create account  

Oral-History:G. David Forney

From GHN

(Difference between revisions)
Jump to: navigation, search
(9 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
== About G. David Forney  ==
 
== About G. David Forney  ==
  
[[Image:G. David Forney, Jr. 2255.jpg|thumb|left|G. David Forney, Jr.]]As an electrical engineering student, G. David Forney, Jr. viewed his undergraduate education at Princeton as a rare opportunity to study the liberal arts. He became serious about his engineering education as a graduate student at MIT, where he acquired an interest in information theory. His thesis focused on concatenated codes that had exponential performance with polynomial complexity (a performance versus complexity trade-off). His work in this area sustained interest for years both academically and in practical application. He joined Codex, one of the first companies concerned with making information theory and coding theory practical. At the time he joined, they had just received an exploratory research contract from NASA to look into the possible application of error-correcting codes in deep space missions. The focus of their work eventually shifted to sequential decoding, and they were contracted to design the code utilized by the [[Pioneer and Voyager Missions|Pioneer missions]].  
+
[[Image:G. David Forney, Jr. 2255.jpg|thumb|left|G. David Forney, Jr.]]As an electrical engineering student, [[G. David Forney, Jr.|G. David Forney, Jr.]] viewed his undergraduate education at Princeton as a rare opportunity to study the liberal arts. He became serious about his engineering education as a graduate student at MIT, where he acquired an interest in information theory. His thesis focused on concatenated codes that had exponential performance with polynomial complexity (a performance versus complexity trade-off). His work in this area sustained interest for years both academically and in practical application. He joined Codex, one of the first companies concerned with making information theory and coding theory practical. At the time he joined, they had just received an exploratory research contract from NASA to look into the possible application of error-correcting codes in deep space missions. The focus of their work eventually shifted to sequential decoding, and they were contracted to design the code utilized by the [[Pioneer and Voyager Missions|Pioneer missions]].  
 
+
<br>
+
 
+
<br>
+
  
 
Ultimately, Codex moved out of the coding business, and began focusing on developing a modem. In 1970, after major blows to Codex both in its business and its corporate structure, including problems with the design of its modem and the death of both founders within a year, the company was on the brink of failing. Concentrating their resources, they developed a new modem, and over the course of the next four years became the leader in the high-speed modem industry before being acquired by Motorola. Following the development of the new modem, Forney continued to write papers but took a reprieve from Codex, spending 1971-1972 moving between Stanford and MIT before returning to Codex. At this point, his involvement in Codex changed from that of a technical contributor to an engineering manager. He ends the discussion with the emergence of digital networks and Codex’s decision to diversify into wide-area networking products.  
 
Ultimately, Codex moved out of the coding business, and began focusing on developing a modem. In 1970, after major blows to Codex both in its business and its corporate structure, including problems with the design of its modem and the death of both founders within a year, the company was on the brink of failing. Concentrating their resources, they developed a new modem, and over the course of the next four years became the leader in the high-speed modem industry before being acquired by Motorola. Following the development of the new modem, Forney continued to write papers but took a reprieve from Codex, spending 1971-1972 moving between Stanford and MIT before returning to Codex. At this point, his involvement in Codex changed from that of a technical contributor to an engineering manager. He ends the discussion with the emergence of digital networks and Codex’s decision to diversify into wide-area networking products.  
 
<br>
 
  
 
== About the Interview  ==
 
== About the Interview  ==
Line 27: Line 21:
 
G. David Forney, Jr., an oral history conducted in 1995 by Andrew Goldstein, IEEE History Center,&nbsp;New Brunswick, NJ, USA.  
 
G. David Forney, Jr., an oral history conducted in 1995 by Andrew Goldstein, IEEE History Center,&nbsp;New Brunswick, NJ, USA.  
  
<br>
+
== Interview  ==
  
== Interview ==
+
Interview: G. David Forney
 +
 
 +
Interviewer: Andrew Goldstein
  
Interview: G. David Forney<br>Interviewer: Andrew Goldstein<br>Date: 10 May, 1995  
+
Date: 10 May, 1995  
  
 
=== Education  ===
 
=== Education  ===
Line 85: Line 81:
 
Actually, I was. I had taken a physics course at MIT given by John Wheeler, who's a very interesting guy. His method of teaching this course on thermodynamics was to talk about various consulting assignments that he'd had. It was basically an engineering course. Faced with a given problem — you want to distill so much water out in the middle of the Arizona desert — what are the kinds of rules of thumb you need, what are the constants you need to remember, the conversion factors and so forth? How much area is it going to take to convert so much water? It's basically a thermodynamics problem, but he approached it in a very engineering way, and I liked that.  
 
Actually, I was. I had taken a physics course at MIT given by John Wheeler, who's a very interesting guy. His method of teaching this course on thermodynamics was to talk about various consulting assignments that he'd had. It was basically an engineering course. Faced with a given problem — you want to distill so much water out in the middle of the Arizona desert — what are the kinds of rules of thumb you need, what are the constants you need to remember, the conversion factors and so forth? How much area is it going to take to convert so much water? It's basically a thermodynamics problem, but he approached it in a very engineering way, and I liked that.  
  
The centerpiece of the course was your own project, which could be an experimental project or a book review. I did a review of Leon Brillouin's book on information theory and thermodynamics. He basically addressed the problem of Maxwell's demon. He resolved it to his satisfaction by showing that the demon needed so much information in order to open his little door and close his little door, and to get that information he needed to expend a tiny little quantum of energy. That brought all the thermodynamics back into balance, so that the basic laws of thermodynamics are not violated. So I did a book report on that and that was my introduction to information theory. Then at MIT I took information theory the first year, I can't remember if it was the first term, and it was an exciting course to take. That was the golden age of MIT in information theory. A lot of the brightest people on the faculty were working in that area. If I remember correctly, Bob Gallager gave the course, but I'm not absolutely sure of that.  
+
The centerpiece of the course was your own project, which could be an experimental project or a book review. I did a review of Leon Brillouin's book on information theory and thermodynamics. He basically addressed the problem of [[James Clerk Maxwell|Maxwell's]] demon. He resolved it to his satisfaction by showing that the demon needed so much information in order to open his little door and close his little door, and to get that information he needed to expend a tiny little quantum of energy. That brought all the thermodynamics back into balance, so that the basic laws of thermodynamics are not violated. So I did a book report on that and that was my introduction to information theory. Then at MIT I took information theory the first year, I can't remember if it was the first term, and it was an exciting course to take. That was the golden age of MIT in information theory. A lot of the brightest people on the faculty were working in that area. If I remember correctly, [[Robert G. Gallager|Bob Gallager]] gave the course, but I'm not absolutely sure of that.  
  
 
'''Goldstein:'''  
 
'''Goldstein:'''  
  
Two years ago I had a conversation with Bob Gallager much like this and he was telling me much the same thing, that there was tremendous intellectual excitement about it. But the interesting thing was that although bounds were being made theoretically, there was no practical application for what they were doing. There just wasn't that much data communication that required error correction.  
+
[[Oral-History:Robert Gallager|Two years ago I had a conversation with Bob Gallager]] much like this and he was telling me much the same thing, that there was tremendous intellectual excitement about it. But the interesting thing was that although bounds were being made theoretically, there was no practical application for what they were doing. There just wasn't that much data communication that required error correction.  
  
 
'''Forney:'''  
 
'''Forney:'''  
  
His story is going to be very similar to my story. He was involved in the founding of Codex in 1962, as well as Jim Massey and other people at MIT. Shannon had some original founder's stock in Codex; Jake Ziv was involved. So Codex was really the first company that was set up to try and make some of this information theory and coding theory practical. As we go on I can get into some of the problems that there were back in those days. But yes, it was an exciting research field.  
+
His story is going to be very similar to my story. He was involved in the founding of Codex in 1962, as well as [[James L. Massey|Jim Massey]] and other people at MIT. [[Claude Shannon|Shannon]] had some original founder's stock in Codex; Jake Ziv was involved. So Codex was really the first company that was set up to try and make some of this information theory and coding theory practical. As we go on I can get into some of the problems that there were back in those days. But yes, it was an exciting research field.  
  
To jump ahead a little bit, when I was finishing my thesis and getting out of MIT, the common wisdom among the faculty was that most of the things that were ever going to be done in information theory research had been done. All the important questions had been settled at that point, and the real action was going to be in applications. So I was advised by Jack Wozencraft and others not to be a professor continuing in academic research, but to try and do something a little bit more practical. So I only interviewed at three places, which were Bell Labs, IBM Research Labs, and at Bob Gallager's suggestion, I went to take a look at Codex. I thought that Codex really seemed interesting. So that's where I went.  
+
To jump ahead a little bit, when I was finishing my thesis and getting out of MIT, the common wisdom among the faculty was that most of the things that were ever going to be done in information theory research had been done. All the important questions had been settled at that point, and the real action was going to be in applications. So I was advised by [[John M. Wozencraft|Jack Wozencraft]] and others not to be a professor continuing in academic research, but to try and do something a little bit more practical. So I only interviewed at three places, which were [[Bell Labs|Bell Labs]], IBM Research Labs, and at Bob Gallager's suggestion, I went to take a look at Codex. I thought that Codex really seemed interesting. So that's where I went.  
  
 
=== Codex and NASA  ===
 
=== Codex and NASA  ===
Line 107: Line 103:
 
During the '60s Codex was basically trying to find a market for error-correcting codes, and really the only market during that period was the military. Most of the systems we were working on were aimed at long-range radio channels, HF channels, tropospheric scatter channels and so forth where the atmospheric conditions meant that the channels were quite bursty. You'd get bursts of errors in the data. We developed several families of so-called burst-error-correcting codes. There was a Massey threshold decoder family and there was also a Gallager family. We attempted to sell these into military systems. It was a rough slog. When I started at Codex, happily, they had just gotten an exploratory research contract from NASA to look into the possible application of error correction in deep space missions, and that turned out to be a much cleaner and more rewarding problem. This is not a bursty channel, it's a very well behaved additive white Gaussian noise channel, so you could directly apply the kinds of random error-correcting codes that had been developed in this academic research.  
 
During the '60s Codex was basically trying to find a market for error-correcting codes, and really the only market during that period was the military. Most of the systems we were working on were aimed at long-range radio channels, HF channels, tropospheric scatter channels and so forth where the atmospheric conditions meant that the channels were quite bursty. You'd get bursts of errors in the data. We developed several families of so-called burst-error-correcting codes. There was a Massey threshold decoder family and there was also a Gallager family. We attempted to sell these into military systems. It was a rough slog. When I started at Codex, happily, they had just gotten an exploratory research contract from NASA to look into the possible application of error correction in deep space missions, and that turned out to be a much cleaner and more rewarding problem. This is not a bursty channel, it's a very well behaved additive white Gaussian noise channel, so you could directly apply the kinds of random error-correcting codes that had been developed in this academic research.  
  
For that problem, we were looking at threshold decoding, which is an extremely simple decoding method invented by Jim Massey in 1962, and if I remember correctly we were looking at hard decisions. But basically we were using a very primitive error correction technique that would buy you a couple dB, which was worthwhile. Three dB means that the mission can last for several more years and go out tens of millions of more miles. So 3 dB is very important in deep-space communications, and that was the kind of gain we were talking about.  
+
For that problem, we were looking at threshold decoding, which is an extremely simple decoding method invented by [[James L. Massey|Jim Massey]] in 1962, and if I remember correctly we were looking at hard decisions. But basically we were using a very primitive error correction technique that would buy you a couple dB, which was worthwhile. Three dB means that the mission can last for several more years and go out tens of millions of more miles. So 3 dB is very important in deep-space communications, and that was the kind of gain we were talking about.  
  
 
=== Sequential Decoding  ===
 
=== Sequential Decoding  ===
Line 115: Line 111:
 
To go back to the climate at MIT in the early '60s, first of all, people had recognized by that time that the problem was not simply designing good codes that were theoretically capable of achieving channel capacity. There were lots of such codes that could be devised. The real question was finding codes that had structure that would allow them to be decoded with reasonable complexity. So it's a performance versus complexity trade-off that people were really working on. I ultimately did my thesis on something called concatenated codes which had exponential performance with polynomial complexity, and that's what you really wanted.  
 
To go back to the climate at MIT in the early '60s, first of all, people had recognized by that time that the problem was not simply designing good codes that were theoretically capable of achieving channel capacity. There were lots of such codes that could be devised. The real question was finding codes that had structure that would allow them to be decoded with reasonable complexity. So it's a performance versus complexity trade-off that people were really working on. I ultimately did my thesis on something called concatenated codes which had exponential performance with polynomial complexity, and that's what you really wanted.  
  
People felt that from a practical point of view the performance/complexity problem had been cracked by sequential decoding, which was invented by Jack Wozencraft at MIT and Lincoln laboratories back in the fifties. By then it had been shown that with sequential decoding you could decode convolutional codes very nicely and very simply at close to channel capacity. On a deep-space channel it would be within 3 dB of channel capacity, at a very reasonable decoding complexity. That was one of the prime reasons why people said well, we've basically solved the problem and now the issue is to go out and apply it.  
+
People felt that from a practical point of view the performance/complexity problem had been cracked by sequential decoding, which was invented by [[John M. Wozencraft|Jack Wozencraft]] at MIT and Lincoln laboratories back in the fifties. By then it had been shown that with sequential decoding you could decode convolutional codes very nicely and very simply at close to channel capacity. On a deep-space channel it would be within 3 dB of channel capacity, at a very reasonable decoding complexity. That was one of the prime reasons why people said well, we've basically solved the problem and now the issue is to go out and apply it.  
  
 
Jumping now back to the late '60s, after spending the better part of a year probably investigating threshold decoding for the deep-space channel, we were talking to Dale Lumb, who was the project manager at NASA Ames out in California. He was running the contract, and we said, "Well, of course you could do much better than this with sequential decoding," and Dale said, "Why aren't we looking at sequential decoding then?" We said, "Well, I guess we should be." So the focus of the work changed to sequential decoding. Indeed, we found we could get right up to within 3 dB of the absolute Shannon limit on that channel. The data rates, this was for the [[Pioneer and Voyager Missions|Pioneer mission]], they only went up to 512 bits per second, so even with the computing technology of that day we could program it on a Honeywell minicomputer that had a clock rate, an instruction rate, of one million instructions per second. Far less than a personal computer nowadays, and it could keep up very nicely and get the full gain of sequential decoding. For that Dale Lumb was named Telemetry Man of the Year. It was a very nice accomplishment. But it didn't pay much rent at Codex. We were just being paid for our time on designing this thing and that was hardly the kind of thing that you can build a business on.  
 
Jumping now back to the late '60s, after spending the better part of a year probably investigating threshold decoding for the deep-space channel, we were talking to Dale Lumb, who was the project manager at NASA Ames out in California. He was running the contract, and we said, "Well, of course you could do much better than this with sequential decoding," and Dale said, "Why aren't we looking at sequential decoding then?" We said, "Well, I guess we should be." So the focus of the work changed to sequential decoding. Indeed, we found we could get right up to within 3 dB of the absolute Shannon limit on that channel. The data rates, this was for the [[Pioneer and Voyager Missions|Pioneer mission]], they only went up to 512 bits per second, so even with the computing technology of that day we could program it on a Honeywell minicomputer that had a clock rate, an instruction rate, of one million instructions per second. Far less than a personal computer nowadays, and it could keep up very nicely and get the full gain of sequential decoding. For that Dale Lumb was named Telemetry Man of the Year. It was a very nice accomplishment. But it didn't pay much rent at Codex. We were just being paid for our time on designing this thing and that was hardly the kind of thing that you can build a business on.  
Line 179: Line 175:
 
I don't remember to tell you the truth. This is all military contracting, cost-plus. I expect we charged a whole lot for them. By today's standards they were trivial pieces of equipment. You could do the whole thing on one corner of a chip. I remember what they looked like. They were designed in a military package. It was about three and a half inches wide and five inches high. Because the constraint length was twelve, they basically had twelve flip-flops, single delay elements, in the transmitter and twenty-four in the receiver. Most of what was in this 19-inch long box was these thirty-six flip-flops. Back then a flip-flop was about 1 inch by 1 inch by 3 inches.  
 
I don't remember to tell you the truth. This is all military contracting, cost-plus. I expect we charged a whole lot for them. By today's standards they were trivial pieces of equipment. You could do the whole thing on one corner of a chip. I remember what they looked like. They were designed in a military package. It was about three and a half inches wide and five inches high. Because the constraint length was twelve, they basically had twelve flip-flops, single delay elements, in the transmitter and twenty-four in the receiver. Most of what was in this 19-inch long box was these thirty-six flip-flops. Back then a flip-flop was about 1 inch by 1 inch by 3 inches.  
  
When I came to work at Codex, the first thing my boss Arthur Kohlenberg did was to show me the equations of the TD-12, just to familiarize me with them. I think it was the first or second day I came to work. I looked at them. They were standard threshold decoding equations. I think they were probably out of Jim Massey's thesis or book, and I played with them and understood how they worked. Then I thought I was able to see a way where by rejiggering the equations you could save two flip-flops. Big deal. But in something that had only thirty-eight flip-flops I was able to get it down to thirty-six or something like that, which ''was'' a big deal. I remember that this thing was starting down the production line and Arthur said, "Hold the factory!" I don't know where Jim Massey was, but we called him long distance, asking, "Is this right?" Jim looked them over and said, "Yes, by God, it's right." So the equipment was redesigned to save these two flip-flops and I really felt like I had made a major contribution. (Laugh).  
+
When I came to work at Codex, the first thing my boss Arthur Kohlenberg did was to show me the equations of the TD-12, just to familiarize me with them. I think it was the first or second day I came to work. I looked at them. They were standard threshold decoding equations. I think they were probably out of [[James L. Massey|Jim Massey's]] thesis or book, and I played with them and understood how they worked. Then I thought I was able to see a way where by rejiggering the equations you could save two flip-flops. Big deal. But in something that had only thirty-eight flip-flops I was able to get it down to thirty-six or something like that, which ''was'' a big deal. I remember that this thing was starting down the production line and Arthur said, "Hold the factory!" I don't know where Jim Massey was, but we called him long distance, asking, "Is this right?" Jim looked them over and said, "Yes, by God, it's right." So the equipment was redesigned to save these two flip-flops and I really felt like I had made a major contribution. (Laugh).  
  
It has a larger moral to it: that we were way ahead of our time in the technology then, compared to where we are now. My career started with these things being barely buildable at all, and only at great expense. The TD-12 cost five thousand dollars or something. Now an extremely complicated V.34 modem going at 28,800 bits per second, using every last dollop of technology that we know about, doing tens of millions of digital signal processing operations per second, is down at your local computer store for 299 bucks. That's the dramatic thing that's happened during my career. So overall, what has happened is we've been able to build as sophisticated algorithms as we wanted to, whereas back then it was all academic research because nobody could imagine building this stuff. That's what Bob Gallager said, I'm sure.  
+
It has a larger moral to it: that we were way ahead of our time in the technology then, compared to where we are now. My career started with these things being barely buildable at all, and only at great expense. The TD-12 cost five thousand dollars or something. Now an extremely complicated V.34 modem going at 28,800 bits per second, using every last dollop of technology that we know about, doing tens of millions of digital signal processing operations per second, is down at your local computer store for 299 bucks. That's the dramatic thing that's happened during my career. So overall, what has happened is we've been able to build as sophisticated algorithms as we wanted to, whereas back then it was all academic research because nobody could imagine building this stuff. That's what [[Robert G. Gallager|Bob Gallager]] said, I'm sure.  
  
 
=== The Coding Business and Linkabit  ===
 
=== The Coding Business and Linkabit  ===
Line 191: Line 187:
 
'''Forney:'''  
 
'''Forney:'''  
  
As best as I can recall, we were all by ourselves, and there was a very good reason for that which is that there wasn't any business there. Codex was the first company to try and find a real market for error-correcting code and we were never very successful at it. To jump ahead a little bit, we basically made a decision to get into the commercial business in the late '60s and very quickly, by 1970, had decided to focus all our resources on the commercial side. Not error-correction, but modems and multiplexers. We basically got out of the error-correcting code business. At just about that time another company called Linkabit was starting out on the West Coast with Irwin Jacobs, Andy Viterbi, Jerry Heller, and a few other bright people. We sort of passed the torch to them in the coding business and they did extremely well. Have you talked to any of these people?  
+
As best as I can recall, we were all by ourselves, and there was a very good reason for that which is that there wasn't any business there. Codex was the first company to try and find a real market for error-correcting code and we were never very successful at it. To jump ahead a little bit, we basically made a decision to get into the commercial business in the late '60s and very quickly, by 1970, had decided to focus all our resources on the commercial side. Not error-correction, but modems and multiplexers. We basically got out of the error-correcting code business. At just about that time another company called Linkabit was starting out on the West Coast with [[Irwin M. Jacobs|Irwin Jacobs]], [[Andrew J. Viterbi|Andy Viterbi]], Jerry Heller, and a few other bright people. We sort of passed the torch to them in the coding business and they did extremely well. Have you talked to any of these people?  
  
 
'''Goldstein:'''  
 
'''Goldstein:'''  
Line 217: Line 213:
 
'''Forney:'''  
 
'''Forney:'''  
  
<flashmp3>254_-_forney_-_clip_1.mp3</flashmp3>  
+
<p><flashmp3>254_-_forney_-_clip_1.mp3</flashmp3></p>
  
 
Certainly I think the advent of digital technology was extremely important for Linkabit and I will tell you an anecdote about that. There's a very famous vignette in the history of our business that occurred at the very first Communication Theory Workshop in 1970 in Florida. Everybody knows about this workshop because during the workshop there was a session on coding. Ned Weldon made a talk in which his principal illustration was a slide with lots of rats all crowding into the corner of some cage that they were in. God knows what they were doing in that corner. He said basically this is what coding theorists are doing, we're all scrabbling around the same small set of problems and they aren't really the relevant problems anyway.  
 
Certainly I think the advent of digital technology was extremely important for Linkabit and I will tell you an anecdote about that. There's a very famous vignette in the history of our business that occurred at the very first Communication Theory Workshop in 1970 in Florida. Everybody knows about this workshop because during the workshop there was a session on coding. Ned Weldon made a talk in which his principal illustration was a slide with lots of rats all crowding into the corner of some cage that they were in. God knows what they were doing in that corner. He said basically this is what coding theorists are doing, we're all scrabbling around the same small set of problems and they aren't really the relevant problems anyway.  
  
It became known as the "coding is dead" talk, session, workshop. Coding is dead, it's a played-out field; we ought to stop research. This has been a recurring theme. I've said a number of times I've spent my whole career working in fields that have been declared to be dead. Anyway, this was the "coding is dead" workshop. Bob Lucky wrote a column on it for ''Spectrum'' five or ten years ago. It grew to say modems were dead and so forth, when actually these things were just at the take-off point.  
+
It became known as the "coding is dead" talk, session, workshop. Coding is dead, it's a played-out field; we ought to stop research. This has been a recurring theme. I've said a number of times I've spent my whole career working in fields that have been declared to be dead. Anyway, this was the "coding is dead" workshop. Bob Lucky wrote a column on it for ''[[IEEE Spectrum|Spectrum]]'' five or ten years ago. It grew to say modems were dead and so forth, when actually these things were just at the take-off point.  
  
I didn't agree with that. Irwin Jacobs was in the back of the room, and he rose to say this is absolutely wrong. He held up a fourteen-pin dual in-line package, DIP, which contained probably a four-bit shift register or something, medium scale integration, and he said "This is where it's at. This new digital technology out there is going to let us build all this stuff." So once again, applications are where it's at, and he was absolutely right. And Elwyn Berlekamp chimed in to the same effect, and I think I may have said something to the same effect. Elwin went on to found a coding company called Cyclotomics where he did some fantastic things in hardware. But I think that was a very important reason for Linkabit's success was that they were riding on the first real wave of digital technology, MSI TTL technology, which we simply did not have available to us. We were building things out of transistors in epoxy packages, made up of flip-flops and so forth.  
+
I didn't agree with that. [[Irwin M. Jacobs|Irwin Jacobs]] was in the back of the room, and he rose to say this is absolutely wrong. He held up a fourteen-pin dual in-line package, DIP, which contained probably a four-bit shift register or something, medium scale integration, and he said "This is where it's at. This new digital technology out there is going to let us build all this stuff." So once again, applications are where it's at, and he was absolutely right. And Elwyn Berlekamp chimed in to the same effect, and I think I may have said something to the same effect. Elwin went on to found a coding company called Cyclotomics where he did some fantastic things in hardware. But I think that was a very important reason for Linkabit's success was that they were riding on the first real wave of digital technology, MSI TTL technology, which we simply did not have available to us. We were building things out of transistors in epoxy packages, made up of flip-flops and so forth.  
  
 
=== Reed-Solomon and Concatenated Codes  ===
 
=== Reed-Solomon and Concatenated Codes  ===
Line 251: Line 247:
 
Well, let me tell you the story of Reed-Solomon codes. They were announced in a very brief paper by Reed and Solomon in 1960, which was a stone that fell without making any ripples. They were briefly mentioned in Peterson's book, which was about '61 or '62, but the main interest then was in binary codes. Reed-Solomon are non-binary codes. BCH codes, Bose-Chandhuri-Hacquenghem code, from one point of view can be viewed as subcodes of Reed-Solomon codes, but that wasn't the way they were studied back then. I believe that the Reed-Solomon codes were completely ignored up to my thesis. I used them as a component in a two-level coding scheme called concatenated coding. They were the outer codes; then you used a short optimum code as the inner code. I showed that the combination could get you this performance/complexity trade off that I mentioned before. Gus Solomon was one of the outside readers on my thesis, or maybe it was the MIT Press monograph that came out, and he was just ecstatic about this development. But I think no one had looked at Reed-Solomon codes in any way before that.  
 
Well, let me tell you the story of Reed-Solomon codes. They were announced in a very brief paper by Reed and Solomon in 1960, which was a stone that fell without making any ripples. They were briefly mentioned in Peterson's book, which was about '61 or '62, but the main interest then was in binary codes. Reed-Solomon are non-binary codes. BCH codes, Bose-Chandhuri-Hacquenghem code, from one point of view can be viewed as subcodes of Reed-Solomon codes, but that wasn't the way they were studied back then. I believe that the Reed-Solomon codes were completely ignored up to my thesis. I used them as a component in a two-level coding scheme called concatenated coding. They were the outer codes; then you used a short optimum code as the inner code. I showed that the combination could get you this performance/complexity trade off that I mentioned before. Gus Solomon was one of the outside readers on my thesis, or maybe it was the MIT Press monograph that came out, and he was just ecstatic about this development. But I think no one had looked at Reed-Solomon codes in any way before that.  
  
I remember when I went around to give seminars based on my thesis. At Bell Labs in particular, I went down and talked to Bob Lucky's group. When I put some actual numbers up on the board, outer codes of lengths in hundreds or thousands of symbols long and correcting tens of errors, perhaps hundreds of errors, people sort of rolled their eyes. It was obvious they were saying to themselves that this is not a very practical guy. But in fact, as technology has advanced, Reed-Solomon codes are the most successful block codes there are. They are a standard component in everything from stereo systems to what have you. People use them in the way that they were used in concatenated coding systems. And they're extremely effective. I don't think they really took off practically until the mid-'70s or early '80s. Again, the technology wasn't there until then. Elwyn Berlekamp's company that I mentioned did a lot to make them practical, but it was really Philips and places like that which used them for commercial systems and made them practical. So as far as we were concerned at Codex, during the time that we were interested in coding, which ended in 1969, they were far from anything we could even consider using.  
+
I remember when I went around to give seminars based on my thesis. At [[Bell Labs|Bell Labs]] in particular, I went down and talked to [[Robert W. Lucky|Bob Lucky's]] group. When I put some actual numbers up on the board, outer codes of lengths in hundreds or thousands of symbols long and correcting tens of errors, perhaps hundreds of errors, people sort of rolled their eyes. It was obvious they were saying to themselves that this is not a very practical guy. But in fact, as technology has advanced, Reed-Solomon codes are the most successful block codes there are. They are a standard component in everything from stereo systems to what have you. People use them in the way that they were used in concatenated coding systems. And they're extremely effective. I don't think they really took off practically until the mid-'70s or early '80s. Again, the technology wasn't there until then. Elwyn Berlekamp's company that I mentioned did a lot to make them practical, but it was really Philips and places like that which used them for commercial systems and made them practical. So as far as we were concerned at Codex, during the time that we were interested in coding, which ended in 1969, they were far from anything we could even consider using.  
  
 
'''Goldstein:'''  
 
'''Goldstein:'''  
Line 281: Line 277:
 
The way things have generally happened in this field is that the academic and theoretical researchers go after a well-posed hard problem. To me a well-posed hard problem always has some index of complexity in it. This has often led to some of the very best theoretical research problems in our field and has focused attention where a purely mathematical approach would have ignored it. The interplay between performance and complexity has been a major theme in my own work. This is probably what I'm going to talk about when I give the Shannon Lecture this fall at the International Symposium on Information Theory.  
 
The way things have generally happened in this field is that the academic and theoretical researchers go after a well-posed hard problem. To me a well-posed hard problem always has some index of complexity in it. This has often led to some of the very best theoretical research problems in our field and has focused attention where a purely mathematical approach would have ignored it. The interplay between performance and complexity has been a major theme in my own work. This is probably what I'm going to talk about when I give the Shannon Lecture this fall at the International Symposium on Information Theory.  
  
But in going at a well-posed performance versus complexity problem, theoreticians have repeatedly come up with schemes that are to prove theorems. People at Codex, Linkabit, and Bell Labs can read theoretical papers and translate them into practical application, and then realize that this can actually be used. I think what got Linkabit off the ground was the realization that the performance of relatively short constraint-length convolutional codes was pretty good, and that you could build them. Andy Viterbi attributes that to Jerry Heller, and it was a great contribution, because he was right. It was in tune with the technology of that day. This has happened again and again. In our field I don't think that communication goes directly from the guy who writes the paper for the ''Transactions on Information Theory'' to the shirtsleeves engineer in the lab. There are hundreds of people like myself working in industry or in Jet Propulsion Laboratories or Lincoln Laboratories who can read the ''Transactions'' paper, and if they're in the right place at the right time, they say "Hey, this could actually be useful in my system." That's where the translation takes place. Then other people say "Wow, that's really good performance. I didn't realize you could actually build that," and that's the way it propagates out to the industry as a whole. The standards bodies are another important mechanism for getting it out to the industry as a whole.  
+
But in going at a well-posed performance versus complexity problem, theoreticians have repeatedly come up with schemes that are to prove theorems. People at Codex, Linkabit, and Bell Labs can read theoretical papers and translate them into practical application, and then realize that this can actually be used. I think what got Linkabit off the ground was the realization that the performance of relatively short constraint-length convolutional codes was pretty good, and that you could build them. [[Andrew J. Viterbi|Andy Viterbi]] attributes that to Jerry Heller, and it was a great contribution, because he was right. It was in tune with the technology of that day. This has happened again and again. In our field I don't think that communication goes directly from the guy who writes the paper for the ''Transactions on Information Theory'' to the shirtsleeves engineer in the lab. There are hundreds of people like myself working in industry or in Jet Propulsion Laboratories or Lincoln Laboratories who can read the ''Transactions'' paper, and if they're in the right place at the right time, they say "Hey, this could actually be useful in my system." That's where the translation takes place. Then other people say "Wow, that's really good performance. I didn't realize you could actually build that," and that's the way it propagates out to the industry as a whole. The standards bodies are another important mechanism for getting it out to the industry as a whole.  
  
 
=== Trellis-Coded Modulation  ===
 
=== Trellis-Coded Modulation  ===
Line 291: Line 287:
 
'''Forney:'''  
 
'''Forney:'''  
  
I would pose this as a very good question for you because I've never gotten the answer to it. Why was it that it took trellis-coded modulation so long to be recognized as the extraordinarily valuable and practical technique that it was? It was invented by Ungerboeck in the mid-'70s. He talked about it at an Information Theory Symposium in Sweden in 1976. He spent quite a bit of time trying to convince other people including me that on a bandwidth-limited channel this is a great way to get 3 dB at least. He basically got nowhere for about five years. He stopped trying to promote it for a while. What really made trellis-coded modulation take-off in a practical way was when it began to be considered for the V32 modem standard in 1982. Then modem designers and every modem company that there was started to program this up and see "Gee whiz, it does get you three, three-and-a-half, 4 dB gain." That's just what they needed to get reliable transmission at high data rates over the real telephone network. All of a sudden everybody knew about trellis-coded modulation. It became the hot thing for the next decade. But why this lag of at least five years, maybe seven years, between invention and anybody using it? It's still a great mystery to me. So as you go around and talk to people, I propose that as a question for you. I was fully equipped to understand exactly what Ungerboeck was doing. I was in a modem company, and could fully appreciate what the advantages of it could be. The biggest mystery is why did I miss this?  
+
I would pose this as a very good question for you because I've never gotten the answer to it. Why was it that it took trellis-coded modulation so long to be recognized as the extraordinarily valuable and practical technique that it was? It was invented by [[Oral-History:Gottfried Ungerboeck|Ungerboeck]] in the mid-'70s. He talked about it at an Information Theory Symposium in Sweden in 1976. He spent quite a bit of time trying to convince other people including me that on a bandwidth-limited channel this is a great way to get 3 dB at least. He basically got nowhere for about five years. He stopped trying to promote it for a while. What really made trellis-coded modulation take-off in a practical way was when it began to be considered for the V32 modem standard in 1982. Then modem designers and every modem company that there was started to program this up and see "Gee whiz, it does get you three, three-and-a-half, 4 dB gain." That's just what they needed to get reliable transmission at high data rates over the real telephone network. All of a sudden everybody knew about trellis-coded modulation. It became the hot thing for the next decade. But why this lag of at least five years, maybe seven years, between invention and anybody using it? It's still a great mystery to me. So as you go around and talk to people, I propose that as a question for you. I was fully equipped to understand exactly what Ungerboeck was doing. I was in a modem company, and could fully appreciate what the advantages of it could be. The biggest mystery is why did I miss this?  
  
 
'''Goldstein:'''  
 
'''Goldstein:'''  
Line 309: Line 305:
 
'''Forney:'''  
 
'''Forney:'''  
  
On the one hand I'd agree that relatively few theoretical papers focus explicitly on complexity. But on the other hand I've already said that I think this was clearly in the air at MIT in the early '60s. We knew that any random code that we choose out of the air could get effectively optimal performance, which means an exponentially decreasing error rate at any data rate less than capacity. That's what Gallagher's great 1965 paper showed. It actually showed the rate at which the error probability decreases for random codes. But by then, people realized that that's not the issue, the issue is finding codes that are decodable in a reasonable amount of time.  
+
On the one hand I'd agree that relatively few theoretical papers focus explicitly on complexity. But on the other hand I've already said that I think this was clearly in the air at MIT in the early '60s. We knew that any random code that we choose out of the air could get effectively optimal performance, which means an exponentially decreasing error rate at any data rate less than capacity. That's what [[Robert G. Gallager|Gallagher's]] great 1965 paper showed. It actually showed the rate at which the error probability decreases for random codes. But by then, people realized that that's not the issue, the issue is finding codes that are decodable in a reasonable amount of time.  
  
 
The solution at that point was believed to be sequential decoding, which has been largely forgotten, interestingly. It has been completely superseded by other things like the Viterbi algorithm, although I privately think it's due for a renaissance, and I have a little research going on right now at MIT to show that. So I'd say that within the information theory and coding community the issue of performance versus complexity was understood as the key issue back in that time. Maybe it wasn't understood widely, but it certainly was baked into me. That's why I did my thesis in that area.  
 
The solution at that point was believed to be sequential decoding, which has been largely forgotten, interestingly. It has been completely superseded by other things like the Viterbi algorithm, although I privately think it's due for a renaissance, and I have a little research going on right now at MIT to show that. So I'd say that within the information theory and coding community the issue of performance versus complexity was understood as the key issue back in that time. Maybe it wasn't understood widely, but it certainly was baked into me. That's why I did my thesis in that area.  
Line 449: Line 445:
 
'''Forney:'''  
 
'''Forney:'''  
  
It worked. [laugh] That was an important feature. It was also much more reliable, a new generation of technology. It was basically the same technology I talked about with Irwin Jacobs, when I had learned about by designing this high-speed sequential decoder. That was another very fortuitous thing. I learned how to design with MSI TTL logic in '68 to '69 by building this high-speed sequential decoder. So I did basically all the logical design of this new modem. Again, I think a key to its success was that somebody who understood what needed to be done algorithmically was also doing all the digital design and could optimize the design. So it was much more reliable, much lower in factory cost, and a lot more modern in design.  
+
It worked. [laugh] That was an important feature. It was also much more reliable, a new generation of technology. It was basically the same technology I talked about with [[Irwin M. Jacobs|Irwin Jacobs]], when I had learned about by designing this high-speed sequential decoder. That was another very fortuitous thing. I learned how to design with MSI TTL logic in '68 to '69 by building this high-speed sequential decoder. So I did basically all the logical design of this new modem. Again, I think a key to its success was that somebody who understood what needed to be done algorithmically was also doing all the digital design and could optimize the design. So it was much more reliable, much lower in factory cost, and a lot more modern in design.  
  
From a technical point of view the key thing was that we went from single-sideband to QAM double-sideband, which was really an idea that Bob Gallagher had been pursuing for a couple of years while Jerry Holsinger was working on single sideband. He felt intuitively that double-sideband was a more natural and better way to go, particularly when the limiting impairment was phase jitter. It turns out you can deal with phase jitter much more naturally and effectively in a QAM system than you can in a single-sideband system where there really isn't much you can do about it. So we were way ahead of the rest of the industry. We came out with QAM modems in 1970 and the first competing QAM modems from AT&amp;T and Racal-Milgo came out in '73 or '74. So we had a four-year head start on what became accepted as very much the preferred technology. We just made a lot of right choices. We made a right choice in the modulation scheme, the adaptive equalizer, and the hardware that we used to build it. Fortunately it was in an area where paper-and-pencil design translated directly into real-world performance, and where real-world performance was highly valuable. I mean, we were the only people who had a 9600 bit per second modem that actually worked reliably. And we had a bunch of customers for whom that was very important, so it was like shooting fish in a barrel. I don't want to diminish the achievements of the manufacturing and marketing and the field service people. All that was extremely important; without that we wouldn't have been successful either. But when you have a product that fills a need and works and nobody else does, you're in a very favorable position.  
+
From a technical point of view the key thing was that we went from single-sideband to QAM double-sideband, which was really an idea that [[Robert G. Gallager|Bob Gallager]] had been pursuing for a couple of years while Jerry Holsinger was working on single sideband. He felt intuitively that double-sideband was a more natural and better way to go, particularly when the limiting impairment was phase jitter. It turns out you can deal with phase jitter much more naturally and effectively in a QAM system than you can in a single-sideband system where there really isn't much you can do about it. So we were way ahead of the rest of the industry. We came out with QAM modems in 1970 and the first competing QAM modems from AT&amp;T and Racal-Milgo came out in '73 or '74. So we had a four-year head start on what became accepted as very much the preferred technology. We just made a lot of right choices. We made a right choice in the modulation scheme, the adaptive equalizer, and the hardware that we used to build it. Fortunately it was in an area where paper-and-pencil design translated directly into real-world performance, and where real-world performance was highly valuable. I mean, we were the only people who had a 9600 bit per second modem that actually worked reliably. And we had a bunch of customers for whom that was very important, so it was like shooting fish in a barrel. I don't want to diminish the achievements of the manufacturing and marketing and the field service people. All that was extremely important; without that we wouldn't have been successful either. But when you have a product that fills a need and works and nobody else does, you're in a very favorable position.  
  
 
'''Goldstein:'''  
 
'''Goldstein:'''  
Line 575: Line 571:
 
Good. Thank you.  
 
Good. Thank you.  
  
<br>
+
[[Category:People and organizations|Forney]] [[Category:Corporations|Forney]] [[Category:Engineers|Forney]] [[Category:Inventors|Forney]] [[Category:Universities|Forney]] [[Category:Business, management & industry|Forney]] [[Category:Business|Forney]] [[Category:Communication industry|Forney]] [[Category:Management|Forney]] [[Category:Research and development management|Forney]] [[Category:Communications|Forney]] [[Category:Communication equipment|Forney]] [[Category:Modems|Forney]] [[Category:Communication networks|Forney]] [[Category:Local area networks|Forney]] [[Category:Military communication|Forney]] [[Category:Satellite communication|Forney]] [[Category:Telephony|Forney]] [[Category:Computers and information processing|Forney]] [[Category:Information theory|Forney]] [[Category:Codes|Forney]] [[Category:Communication channels|Forney]] [[Category:Decoding|Forney]] [[Category:Error compensation|Forney]] [[Category:Information entropy|Forney]] [[Category:Rate distortion theory|Forney]] [[Category:Signals|Forney]] [[Category:Signal processing|Forney]] [[Category:Signal reconstruction & restoration|Forney]] [[Category:Signal denoising|Forney]] [[Category:Signal error correction|Forney]] [[Category:Standardization|Forney]] [[Category:Military aerospace equipment|Forney]] [[Category:Satellites|Forney]] [[Category:Telemetry|Forney]] [[Category:News|Forney]]
 
+
[[Category:People_and_organizations]] [[Category:Corporations]] [[Category:Engineers]] [[Category:Inventors]] [[Category:Universities]] [[Category:Business,_management_&_industry|Category:Business,_management_&amp;_industry]] [[Category:Business]] [[Category:Communication_industry]] [[Category:Management]] [[Category:Research_and_development_management]] [[Category:Communications]] [[Category:Communication_equipment]] [[Category:Modems]] [[Category:Communication_networks]] [[Category:Local_area_networks]] [[Category:Military_communication]] [[Category:Satellite_communication]] [[Category:Telephony]] [[Category:Computers_and_information_processing]] [[Category:Information_theory]] [[Category:Codes]] [[Category:Communication_channels]] [[Category:Decoding]] [[Category:Error_compensation]] [[Category:Information_entropy]] [[Category:Rate_distortion_theory]] [[Category:Signals]] [[Category:Signal_processing]] [[Category:Signal_reconstruction_&_restoration|Category:Signal_reconstruction_&amp;_restoration]] [[Category:Signal_denoising]] [[Category:Signal_error_correction]] [[Category:Standardization]] [[Category:Military_aerospace_equipment]] [[Category:Satellites]] [[Category:Telemetry]]
+

Revision as of 19:49, 26 March 2012

Contents

About G. David Forney

G. David Forney, Jr.
G. David Forney, Jr.
As an electrical engineering student, G. David Forney, Jr. viewed his undergraduate education at Princeton as a rare opportunity to study the liberal arts. He became serious about his engineering education as a graduate student at MIT, where he acquired an interest in information theory. His thesis focused on concatenated codes that had exponential performance with polynomial complexity (a performance versus complexity trade-off). His work in this area sustained interest for years both academically and in practical application. He joined Codex, one of the first companies concerned with making information theory and coding theory practical. At the time he joined, they had just received an exploratory research contract from NASA to look into the possible application of error-correcting codes in deep space missions. The focus of their work eventually shifted to sequential decoding, and they were contracted to design the code utilized by the Pioneer missions.

Ultimately, Codex moved out of the coding business, and began focusing on developing a modem. In 1970, after major blows to Codex both in its business and its corporate structure, including problems with the design of its modem and the death of both founders within a year, the company was on the brink of failing. Concentrating their resources, they developed a new modem, and over the course of the next four years became the leader in the high-speed modem industry before being acquired by Motorola. Following the development of the new modem, Forney continued to write papers but took a reprieve from Codex, spending 1971-1972 moving between Stanford and MIT before returning to Codex. At this point, his involvement in Codex changed from that of a technical contributor to an engineering manager. He ends the discussion with the emergence of digital networks and Codex’s decision to diversify into wide-area networking products.

About the Interview

G. DAVID FORNEY, JR.: An Interview Conducted by Andrew Goldstein, Center for the History of Electrical Engineering, May 10, 1995

Interview #254 for the Center for the History of Electrical Engineering, The Institute of Electrical and Electronics Engineers, Inc.

Copyright Statement

This manuscript is being made available for research purposes only. All literary rights in the manuscript, including the right to publish, are reserved to the IEEE History Center. No part of the manuscript may be quoted for publication without the written permission of the Director of IEEE History Center.

Request for permission to quote for publication should be addressed to the IEEE History Center Oral History Program, 39 Union Street, New Brunswick, NJ 08901-8538 USA. It should include identification of the specific passages to be quoted, anticipated use of the passages, and identification of the user.

It is recommended that this oral history be cited as follows:

G. David Forney, Jr., an oral history conducted in 1995 by Andrew Goldstein, IEEE History Center, New Brunswick, NJ, USA.

Interview

Interview: G. David Forney

Interviewer: Andrew Goldstein

Date: 10 May, 1995

Education

Goldstein:

Let's start with your background before your education.

Forney:

Before my education?

Goldstein:

Leading up to your professional training.

Forney:

Before kindergarten you mean?

Goldstein:

How was nursery school?

Forney:

I don't think this is so interesting, but I had a private school education throughout. I had a very fine education, I think, at New Canaan Country School in Connecticut, then at Choate School. My undergraduate education was at Princeton, where I was an electrical engineer but took as little electrical engineering as possible, and then got serious about it when I did my graduate education at MIT. You have the story in front of you.

Goldstein:

When you say you took as little electrical engineering as possible at the undergraduate level at Princeton, were you more interested in math?

Forney:

Oh no, no. I took much more history, philosophy, art and architecture, all the things that Princeton was good at. I really valued being at a liberal arts place. I'm sorry that most undergraduates in engineering don't get that opportunity. There are just too many requirements to allow for many electives. I'm on the advisory councils at Princeton and various other places and I'm always pushing to allow undergraduates more latitude. Of course, many of them don't take advantage of it. But I feel that, for me at least, it was a dynamite combination to take just the minimum two courses a term necessary to get into graduate school and meanwhile take advantage of everything else. I got my real electrical engineering education in graduate school, with a good foundation.

MIT and Information Theory

Goldstein:

You started graduate school in 1961?

Forney:

Yes.

Goldstein:

Were you interested in information theory right away?

Forney:

Actually, I was. I had taken a physics course at MIT given by John Wheeler, who's a very interesting guy. His method of teaching this course on thermodynamics was to talk about various consulting assignments that he'd had. It was basically an engineering course. Faced with a given problem — you want to distill so much water out in the middle of the Arizona desert — what are the kinds of rules of thumb you need, what are the constants you need to remember, the conversion factors and so forth? How much area is it going to take to convert so much water? It's basically a thermodynamics problem, but he approached it in a very engineering way, and I liked that.

The centerpiece of the course was your own project, which could be an experimental project or a book review. I did a review of Leon Brillouin's book on information theory and thermodynamics. He basically addressed the problem of Maxwell's demon. He resolved it to his satisfaction by showing that the demon needed so much information in order to open his little door and close his little door, and to get that information he needed to expend a tiny little quantum of energy. That brought all the thermodynamics back into balance, so that the basic laws of thermodynamics are not violated. So I did a book report on that and that was my introduction to information theory. Then at MIT I took information theory the first year, I can't remember if it was the first term, and it was an exciting course to take. That was the golden age of MIT in information theory. A lot of the brightest people on the faculty were working in that area. If I remember correctly, Bob Gallager gave the course, but I'm not absolutely sure of that.

Goldstein:

Two years ago I had a conversation with Bob Gallager much like this and he was telling me much the same thing, that there was tremendous intellectual excitement about it. But the interesting thing was that although bounds were being made theoretically, there was no practical application for what they were doing. There just wasn't that much data communication that required error correction.

Forney:

His story is going to be very similar to my story. He was involved in the founding of Codex in 1962, as well as Jim Massey and other people at MIT. Shannon had some original founder's stock in Codex; Jake Ziv was involved. So Codex was really the first company that was set up to try and make some of this information theory and coding theory practical. As we go on I can get into some of the problems that there were back in those days. But yes, it was an exciting research field.

To jump ahead a little bit, when I was finishing my thesis and getting out of MIT, the common wisdom among the faculty was that most of the things that were ever going to be done in information theory research had been done. All the important questions had been settled at that point, and the real action was going to be in applications. So I was advised by Jack Wozencraft and others not to be a professor continuing in academic research, but to try and do something a little bit more practical. So I only interviewed at three places, which were Bell Labs, IBM Research Labs, and at Bob Gallager's suggestion, I went to take a look at Codex. I thought that Codex really seemed interesting. So that's where I went.

Codex and NASA

Goldstein:

Can you tell me what systems Codex was planning to build and who they were planning to sell them to, if there was a business plan?

Forney:

During the '60s Codex was basically trying to find a market for error-correcting codes, and really the only market during that period was the military. Most of the systems we were working on were aimed at long-range radio channels, HF channels, tropospheric scatter channels and so forth where the atmospheric conditions meant that the channels were quite bursty. You'd get bursts of errors in the data. We developed several families of so-called burst-error-correcting codes. There was a Massey threshold decoder family and there was also a Gallager family. We attempted to sell these into military systems. It was a rough slog. When I started at Codex, happily, they had just gotten an exploratory research contract from NASA to look into the possible application of error correction in deep space missions, and that turned out to be a much cleaner and more rewarding problem. This is not a bursty channel, it's a very well behaved additive white Gaussian noise channel, so you could directly apply the kinds of random error-correcting codes that had been developed in this academic research.

For that problem, we were looking at threshold decoding, which is an extremely simple decoding method invented by Jim Massey in 1962, and if I remember correctly we were looking at hard decisions. But basically we were using a very primitive error correction technique that would buy you a couple dB, which was worthwhile. Three dB means that the mission can last for several more years and go out tens of millions of more miles. So 3 dB is very important in deep-space communications, and that was the kind of gain we were talking about.

Sequential Decoding

Forney:

To go back to the climate at MIT in the early '60s, first of all, people had recognized by that time that the problem was not simply designing good codes that were theoretically capable of achieving channel capacity. There were lots of such codes that could be devised. The real question was finding codes that had structure that would allow them to be decoded with reasonable complexity. So it's a performance versus complexity trade-off that people were really working on. I ultimately did my thesis on something called concatenated codes which had exponential performance with polynomial complexity, and that's what you really wanted.

People felt that from a practical point of view the performance/complexity problem had been cracked by sequential decoding, which was invented by Jack Wozencraft at MIT and Lincoln laboratories back in the fifties. By then it had been shown that with sequential decoding you could decode convolutional codes very nicely and very simply at close to channel capacity. On a deep-space channel it would be within 3 dB of channel capacity, at a very reasonable decoding complexity. That was one of the prime reasons why people said well, we've basically solved the problem and now the issue is to go out and apply it.

Jumping now back to the late '60s, after spending the better part of a year probably investigating threshold decoding for the deep-space channel, we were talking to Dale Lumb, who was the project manager at NASA Ames out in California. He was running the contract, and we said, "Well, of course you could do much better than this with sequential decoding," and Dale said, "Why aren't we looking at sequential decoding then?" We said, "Well, I guess we should be." So the focus of the work changed to sequential decoding. Indeed, we found we could get right up to within 3 dB of the absolute Shannon limit on that channel. The data rates, this was for the Pioneer mission, they only went up to 512 bits per second, so even with the computing technology of that day we could program it on a Honeywell minicomputer that had a clock rate, an instruction rate, of one million instructions per second. Far less than a personal computer nowadays, and it could keep up very nicely and get the full gain of sequential decoding. For that Dale Lumb was named Telemetry Man of the Year. It was a very nice accomplishment. But it didn't pay much rent at Codex. We were just being paid for our time on designing this thing and that was hardly the kind of thing that you can build a business on.

Goldstein:

What was your schedule of deliverables when you were working?

Forney:

On this particular project we delivered some technical reports, but ultimately we delivered the program, which I wrote in machine language on this Honeywell, I think it was a 516 at some time-sharing place, Philip Hankins Inc. I think, which became part of Wang. Basically, we wrote the program to do sequential decoding. Once we designed the code, it was incorporated into Pioneer missions. We delivered the program.

Goldstein:

I see, so Codex wasn't supplying any hardware.

Forney:

That's right.

Goldstein:

You received specs about what hardware was being used.

Forney:

Right. I think the total contract awards from NASA were probably a couple of hundred thousand dollars for this whole thing. As I say, it didn't do much more than pay for one or two salaries.

Goldstein:

How did that sort of work mesh with the analysis that you had done for your thesis?

Forney:

As I said, it was a rare and unusual opportunity because it was what's called an additive white Gaussian noise channel. This is the channel that's always used in your first course on data communications, because it's analytically very well behaved. So you could take anything that theoreticians had developed for this channel, such as sequential decoding, and apply it, and it worked the way theoretically it was supposed to. As I've spent a career in engineering I've found there are not very many places where you can go directly from academic research to practical application. But this was one of them.

Burst-Error-Correcting Coding Equipment

Goldstein:

Did Codex have any contracts involving burstier channels?

Forney:

Sure. That was the main-line business, this burst-error-correcting coding business. As I said, that was a much more difficult slog. From a business point of view, Codex was founded in 1962. I arrived in 1965. I was the thirteenth employee. At that point Codex was building its first real product, the TD-12 error corrector, which was TD for Threshold Decoding and twelve for a constraint length of twelve, which was ridiculously short. So for the first three years there were basically no hardware sales. Then, between 1965 and 1970, there were some painfully won hardware sales. I don't think that during that time we ever sold more than a million dollars worth of equipment in a year. I would have to go back and look at our prospectus when we went public in 1968. Maybe it was over a million dollars for some year. But it was difficult to move the equipment.

The basic reason was that we were coming along as a Band-Aid after the system had already been designed. Somebody would have designed an HF or tropospheric scatter channel. Either the system was designed well enough so that you could get an appropriately low error rate, 10-5 error probability or something like that, in which case they didn't need us, or, if they were having severe error problems on it, so that the error rate was unsatisfactory, then often it was so unsatisfactory that you just couldn't get anything through it at all. The error probability was one half, and no error-correction system could work in that kind of channel. So the window in which we could work was one in which there were bursts of errors, but relatively well-defined, far enough apart, not too long. It's very hard to go in and find many channels like that. We did sell quite a few systems. We had a major contract with the Ballistic Missile Early Warning System. A lot of our people spent a lot of time in Greenland, cleaning up the links from there back to the United States. I think we had some modest success, but by the end of the '60s it was becoming clear to all that it was going to be extremely hard to make a major business out of error-correction, which was the business goal for Codex all during that time.

Goldstein:

What stimulated the development of the TD-12 if it wasn't obvious where it fit into the communication needs of any of your potential clients?

Forney:

I think the feeling was that we needed a standard product. Prior to that there had been some custom designs for particular channels, particular capabilities, and that involves you in a lot of engineering every time through. I wasn't there when the decision to design the TD-12 was made, but my recollection is that we needed something that we could have on the shelf. If a customer wanted error-correction, we could ship it out, the factory knew how to make it, and so forth. But I don't think we ever sold more than a hundred of them, and maybe it was less than that.

Goldstein:

How much per unit?

Forney:

I don't remember to tell you the truth. This is all military contracting, cost-plus. I expect we charged a whole lot for them. By today's standards they were trivial pieces of equipment. You could do the whole thing on one corner of a chip. I remember what they looked like. They were designed in a military package. It was about three and a half inches wide and five inches high. Because the constraint length was twelve, they basically had twelve flip-flops, single delay elements, in the transmitter and twenty-four in the receiver. Most of what was in this 19-inch long box was these thirty-six flip-flops. Back then a flip-flop was about 1 inch by 1 inch by 3 inches.

When I came to work at Codex, the first thing my boss Arthur Kohlenberg did was to show me the equations of the TD-12, just to familiarize me with them. I think it was the first or second day I came to work. I looked at them. They were standard threshold decoding equations. I think they were probably out of Jim Massey's thesis or book, and I played with them and understood how they worked. Then I thought I was able to see a way where by rejiggering the equations you could save two flip-flops. Big deal. But in something that had only thirty-eight flip-flops I was able to get it down to thirty-six or something like that, which was a big deal. I remember that this thing was starting down the production line and Arthur said, "Hold the factory!" I don't know where Jim Massey was, but we called him long distance, asking, "Is this right?" Jim looked them over and said, "Yes, by God, it's right." So the equipment was redesigned to save these two flip-flops and I really felt like I had made a major contribution. (Laugh).

It has a larger moral to it: that we were way ahead of our time in the technology then, compared to where we are now. My career started with these things being barely buildable at all, and only at great expense. The TD-12 cost five thousand dollars or something. Now an extremely complicated V.34 modem going at 28,800 bits per second, using every last dollop of technology that we know about, doing tens of millions of digital signal processing operations per second, is down at your local computer store for 299 bucks. That's the dramatic thing that's happened during my career. So overall, what has happened is we've been able to build as sophisticated algorithms as we wanted to, whereas back then it was all academic research because nobody could imagine building this stuff. That's what Bob Gallager said, I'm sure.

The Coding Business and Linkabit

Goldstein:

It's a crucial issue: the utilization of new technology, either computer technology or new coding schemes. I want to get back to that, but first, I want to find out what Codex's competition was. Were there any other firms, marketing services of this kind, any in-house expertise?

Forney:

As best as I can recall, we were all by ourselves, and there was a very good reason for that which is that there wasn't any business there. Codex was the first company to try and find a real market for error-correcting code and we were never very successful at it. To jump ahead a little bit, we basically made a decision to get into the commercial business in the late '60s and very quickly, by 1970, had decided to focus all our resources on the commercial side. Not error-correction, but modems and multiplexers. We basically got out of the error-correcting code business. At just about that time another company called Linkabit was starting out on the West Coast with Irwin Jacobs, Andy Viterbi, Jerry Heller, and a few other bright people. We sort of passed the torch to them in the coding business and they did extremely well. Have you talked to any of these people?

Goldstein:

No. Actually, I was hoping you might speak on the expansion of the need for error-correcting codes.

Forney:

You'd do better to talk to them. From about mid-1969 or the latter part of '69 we basically made a decision to get out of the coding business. Of course, we continued to get a lot of telephone calls from people who were interested in trying it out, and I just began referring them all out to Linkabit. So I think we were very helpful to Linkabit in their formative years. And they went on to great success, mostly on earth-orbiting satellite channels which are also additive white Gaussian noise channels. They took a different approach, basically using short constraint-length convolutional codes which can be decoded optimally with a Viterbi algorithm. They just did a much better job in finding a market. They did what we didn't: they got into the design of the whole system, with the code designed in from the start as an integral part of the system, and that's the way to do it. You get the benefits of coding if you design the whole system knowing that coding is going to be there. All the different parts of the system are tuned for that. They were able to do that and Linkabit was one of the big success stories of the 1970s.

Goldstein:

That sounds like a smart move, but I was getting the impression that Linkabit's success in this field compared to Codex was not so much, due to the fact that they used the Viterbi algorithm or that they designed the whole system, but that the demand for error-correcting code increased.

Forney:

I think that's right. But we just wholly got out of that business. Made a complete U-turn. So I don't feel like I can speak authoritatively. I think they did an awfully good technical marketing job in creating that demand. That is my impression from some distance. And they sold it into the NASA community, the military community, and ultimately the commercial community. I think they did a much better job of generating business where none had been there before than Codex ever did.

"Coding is Dead" Talk

Goldstein:

I guess I don't want to spend too much time talking about what Linkabit did if you weren't directly there. But you were talking earlier about what microprocessors can do. Was the error-correcting business able to expand because you could work in less well-behaved channels?

Forney:

Certainly I think the advent of digital technology was extremely important for Linkabit and I will tell you an anecdote about that. There's a very famous vignette in the history of our business that occurred at the very first Communication Theory Workshop in 1970 in Florida. Everybody knows about this workshop because during the workshop there was a session on coding. Ned Weldon made a talk in which his principal illustration was a slide with lots of rats all crowding into the corner of some cage that they were in. God knows what they were doing in that corner. He said basically this is what coding theorists are doing, we're all scrabbling around the same small set of problems and they aren't really the relevant problems anyway.

It became known as the "coding is dead" talk, session, workshop. Coding is dead, it's a played-out field; we ought to stop research. This has been a recurring theme. I've said a number of times I've spent my whole career working in fields that have been declared to be dead. Anyway, this was the "coding is dead" workshop. Bob Lucky wrote a column on it for Spectrum five or ten years ago. It grew to say modems were dead and so forth, when actually these things were just at the take-off point.

I didn't agree with that. Irwin Jacobs was in the back of the room, and he rose to say this is absolutely wrong. He held up a fourteen-pin dual in-line package, DIP, which contained probably a four-bit shift register or something, medium scale integration, and he said "This is where it's at. This new digital technology out there is going to let us build all this stuff." So once again, applications are where it's at, and he was absolutely right. And Elwyn Berlekamp chimed in to the same effect, and I think I may have said something to the same effect. Elwin went on to found a coding company called Cyclotomics where he did some fantastic things in hardware. But I think that was a very important reason for Linkabit's success was that they were riding on the first real wave of digital technology, MSI TTL technology, which we simply did not have available to us. We were building things out of transistors in epoxy packages, made up of flip-flops and so forth.

Reed-Solomon and Concatenated Codes

Goldstein:

Can you tell me something about how outside developments affected what was going on at Codex? Maybe the development of Reed-Solomon codes or different coding schemes. Were they influencing the sort of work you were doing?

Forney:

No, in a word. We never had anything to do with Reed-Solomon codes, although that had been a principal theme of my thesis, which was on concatenated codes.

Goldstein:

I may have the dates wrong. Anyway, go ahead.

Forney:

Well, what's your impression and I'll react to it?

Goldstein:

I was looking actually for outside developments, either technical or theoretical during the '60s when you were at Codex. So clearly Reed-Solomon was before then. But I was interested in what you were saying.

Forney:

Well, let me tell you the story of Reed-Solomon codes. They were announced in a very brief paper by Reed and Solomon in 1960, which was a stone that fell without making any ripples. They were briefly mentioned in Peterson's book, which was about '61 or '62, but the main interest then was in binary codes. Reed-Solomon are non-binary codes. BCH codes, Bose-Chandhuri-Hacquenghem code, from one point of view can be viewed as subcodes of Reed-Solomon codes, but that wasn't the way they were studied back then. I believe that the Reed-Solomon codes were completely ignored up to my thesis. I used them as a component in a two-level coding scheme called concatenated coding. They were the outer codes; then you used a short optimum code as the inner code. I showed that the combination could get you this performance/complexity trade off that I mentioned before. Gus Solomon was one of the outside readers on my thesis, or maybe it was the MIT Press monograph that came out, and he was just ecstatic about this development. But I think no one had looked at Reed-Solomon codes in any way before that.

I remember when I went around to give seminars based on my thesis. At Bell Labs in particular, I went down and talked to Bob Lucky's group. When I put some actual numbers up on the board, outer codes of lengths in hundreds or thousands of symbols long and correcting tens of errors, perhaps hundreds of errors, people sort of rolled their eyes. It was obvious they were saying to themselves that this is not a very practical guy. But in fact, as technology has advanced, Reed-Solomon codes are the most successful block codes there are. They are a standard component in everything from stereo systems to what have you. People use them in the way that they were used in concatenated coding systems. And they're extremely effective. I don't think they really took off practically until the mid-'70s or early '80s. Again, the technology wasn't there until then. Elwyn Berlekamp's company that I mentioned did a lot to make them practical, but it was really Philips and places like that which used them for commercial systems and made them practical. So as far as we were concerned at Codex, during the time that we were interested in coding, which ended in 1969, they were far from anything we could even consider using.

Goldstein:

You raise two interesting questions about your thesis. One was where you came down on this complexity versus performance trade-off. The other thing I'm curious about has to do with how widely accepted your thesis was, and when concatenated codes started to become significant.

Forney:

I think other people viewed it as a very nice theoretical piece of work. Like Reed-Solomon codes, the Viterbi algorithm, and the Ziv-Lempel compression algorithm, concatenated codes were basically invented to solve a theoretical problem. In this case the problem was to find a coding scheme that would give you exponentially decreasing error rates at data rates up to channel capacity, while giving you only polynomial decoding complexity. And concatenated codes solved that research problem. I think the thesis was widely admired for that and a couple of the things that were in it to get to that result. But at the time neither I nor anybody else thought that this was practical, as my anecdote about my seminar at Bell Labs illustrates. It was a nice piece of academic research. Ten years later people actually started building systems based on these lines and found that that was in fact the way to go. That's the way everybody builds a high-performance system, with the concatenated idea.

Goldstein:

Had there been sustained interest in your thesis during that lag, or did people come back and discover it again once you had the computational power available?

Forney:

I didn't continue to work in that area. I remember the sales reports from the MIT press monograph stayed very steady for as long as they kept reporting it, which was ten or fifteen years. We just kept selling them and selling them, which I guess means people were reading them and reading them. There were other people who extended the idea. Jorn Justesen notably improved on it in his thesis and later in Denmark. The Russians became very interested in it. Concatenated Codes was translated into Russian. They did a lot of work on generalized concatenated codes which are now seen to be a precursor of what we do in the most fancy Euclidean-space coding schemes. So I'd say it never got forgotten. People thought this was very interesting, at first primarily academically, but then over time in practice. It was never forgotten, people kept looking at it.

Relation of Theory to Practice

Goldstein:

Was there any problem in communicating the results of your research to practicing engineers? I wonder if everybody spoke the theoretical language that you were using.

Forney:

Most probably not. I wasn't trying to reach practical engineers at that point. I think the fact that it came out as an MIT Press monograph helped circulate it widely, but it was intended for the research community. Again, at Bell Labs, Bob Lucky's group was a group at the interface between theory and practice. They understood theory very well, but their object was to come up with practical data communications systems, or at least the architecture and algorithms for them. Their reaction in 1965 was that this was off the radar screen as far as being practical, although I think they understood what was being proposed perfectly well. I don't think there was a fundamental difficulty there.

The way things have generally happened in this field is that the academic and theoretical researchers go after a well-posed hard problem. To me a well-posed hard problem always has some index of complexity in it. This has often led to some of the very best theoretical research problems in our field and has focused attention where a purely mathematical approach would have ignored it. The interplay between performance and complexity has been a major theme in my own work. This is probably what I'm going to talk about when I give the Shannon Lecture this fall at the International Symposium on Information Theory.

But in going at a well-posed performance versus complexity problem, theoreticians have repeatedly come up with schemes that are to prove theorems. People at Codex, Linkabit, and Bell Labs can read theoretical papers and translate them into practical application, and then realize that this can actually be used. I think what got Linkabit off the ground was the realization that the performance of relatively short constraint-length convolutional codes was pretty good, and that you could build them. Andy Viterbi attributes that to Jerry Heller, and it was a great contribution, because he was right. It was in tune with the technology of that day. This has happened again and again. In our field I don't think that communication goes directly from the guy who writes the paper for the Transactions on Information Theory to the shirtsleeves engineer in the lab. There are hundreds of people like myself working in industry or in Jet Propulsion Laboratories or Lincoln Laboratories who can read the Transactions paper, and if they're in the right place at the right time, they say "Hey, this could actually be useful in my system." That's where the translation takes place. Then other people say "Wow, that's really good performance. I didn't realize you could actually build that," and that's the way it propagates out to the industry as a whole. The standards bodies are another important mechanism for getting it out to the industry as a whole.

Trellis-Coded Modulation

Goldstein:

As you were saying about trellis-coded modulation.

Forney:

I would pose this as a very good question for you because I've never gotten the answer to it. Why was it that it took trellis-coded modulation so long to be recognized as the extraordinarily valuable and practical technique that it was? It was invented by Ungerboeck in the mid-'70s. He talked about it at an Information Theory Symposium in Sweden in 1976. He spent quite a bit of time trying to convince other people including me that on a bandwidth-limited channel this is a great way to get 3 dB at least. He basically got nowhere for about five years. He stopped trying to promote it for a while. What really made trellis-coded modulation take-off in a practical way was when it began to be considered for the V32 modem standard in 1982. Then modem designers and every modem company that there was started to program this up and see "Gee whiz, it does get you three, three-and-a-half, 4 dB gain." That's just what they needed to get reliable transmission at high data rates over the real telephone network. All of a sudden everybody knew about trellis-coded modulation. It became the hot thing for the next decade. But why this lag of at least five years, maybe seven years, between invention and anybody using it? It's still a great mystery to me. So as you go around and talk to people, I propose that as a question for you. I was fully equipped to understand exactly what Ungerboeck was doing. I was in a modem company, and could fully appreciate what the advantages of it could be. The biggest mystery is why did I miss this?

Goldstein:

Had you heard of it, had you passed it over?

Forney:

I was not at the Ronneby symposium that I mentioned, so I never actually heard Ungerboeck speak about it, but he buttonholed me several times at conferences. That was during a period from about 1975 through '85 or '86 when I was completely out of the research business. I didn't go to the symposia, I didn't write any papers, I didn't read the papers. At that point I was totally involved in management. I was head of research and development at Codex. Later on during that time I was Motorola group executive. I was just out of touch with what was going on, so I missed a lot of stuff. I can at least give myself the excuse that when Gottfried buttonholed me I just wasn't thinking about getting a few more dB. But I still kick myself.

Focus on Performance/Complexity Tradeoff

Goldstein:

I wanted to return once again to this question of performance versus complexity. It surprises me that somebody working theoretically would devote a lot of attention to that question. It seems like it's a question that comes up when you're designing systems and you're forced to make those trade-offs. I wonder if you could tell me whether it was unusual for a theoretical paper to focus on that. Why do you think you did?

Forney:

On the one hand I'd agree that relatively few theoretical papers focus explicitly on complexity. But on the other hand I've already said that I think this was clearly in the air at MIT in the early '60s. We knew that any random code that we choose out of the air could get effectively optimal performance, which means an exponentially decreasing error rate at any data rate less than capacity. That's what Gallagher's great 1965 paper showed. It actually showed the rate at which the error probability decreases for random codes. But by then, people realized that that's not the issue, the issue is finding codes that are decodable in a reasonable amount of time.

The solution at that point was believed to be sequential decoding, which has been largely forgotten, interestingly. It has been completely superseded by other things like the Viterbi algorithm, although I privately think it's due for a renaissance, and I have a little research going on right now at MIT to show that. So I'd say that within the information theory and coding community the issue of performance versus complexity was understood as the key issue back in that time. Maybe it wasn't understood widely, but it certainly was baked into me. That's why I did my thesis in that area.

Another great thing was to be at Codex, where that was clearly the issue. Here we were building what today would be viewed as toy codes and toy decoders, basically because they were as complex as we could implement. It took a major paradigm shift, a major discontinuity in thought process to even imagine that we could build something like sequential decoding for these deep-space communication channels. That didn't come easily, the idea that that was something you could build. Once having conceived of that idea we found we could build it. I didn't mention to you that we then went on to actually build a sequential decoder for the Army that could go up into the megabit region. We found in fact that this stuff really was practical. But I don't think that was widely appreciated then.

Goldstein:

When was the army contract?

Forney:

The army contract was in the late '60s.

Goldstein:

Just before Codex got out.

Forney:

There's a paper or two on it there. It was a pure hardware, very high-speed design, hard decision-sequential decoder, 15 megahertz clock rate, and it could decode up to about five megabits and it worked just the way it was supposed to. But that was completed just about the time we decided to get out of the coding business.

Anyway, the great thing about being at Codex was that it focused you very heavily on these issues of performance versus complexity. In my own personal research we found in everything we did that convolutional codes were much better from a performance-versus-complexity point of view than block codes. Ninety-eight percent of coding research at that time was on block codes. BCH codes, cyclic codes, etc. Why was everybody studying block codes if convolutional codes were clearly better? That led me to try to understand why convolutional codes were better in a basic theoretical sense, which led to a series of papers. Convolutional codes have a fundamentally different type of theory than block codes do. It's much more like linear system theory. And so I had to learn some linear system theory and I wrote some basic papers here that are among the papers I'm most proud of. They were inspired by this daily evidence that these codes were better, but that nobody understood them. We knew how to build them, but there was no theory of convolutional codes. So that's why I started work on a theory of convolutional codes. But I've gotten off your question about performance versus complexity.

Goldstein:

I was just surprised that that was a subject for a theoretical paper when it seemed like it comes up most urgently in the commercial setting.

Forney:

You know, often it's hard to find a good metric for complexity. In the case of convolutional codes they are generated by finite-state machines and a pretty reasonable complexity metric is the number of states in the finite-state machine that generates the convolutional code. So you do have a nice hard complexity metric. In an awful lot of areas of engineering, it would be very difficult to say what the complexity of something was in any way that people could agree on. So I suppose in this field we were lucky there. But the fact that we wanted to define complexity in terms of a certain finite-state system which is also a linear system led to making a bridge connecting linear system theory with convolutional coding theory.

Again, to jump ahead 20 years, in the past couple of years one of the really hot topics in block code research has been to look at block code complexity in the same way. To look at block codes as actually dynamic linear systems, and to measure their complexity by the number of states in those systems. There must be dozens of papers in this area. This is something that every block coding researcher seems to be working on. It's exactly the same thing that we were looking at with convolutional codes 25 years ago. But now it's understood that this raises good questions for block codes too, and people are looking at them that way. These ideas seem to be fundamental, and they come around again and again.

Advantages of Block Codes

Goldstein:

You said before that the convolutional codes offered better performance for their complexity than block codes did. Where were block codes strongest? Which side did they favor, low complexity or high performance?

Forney:

From today's perspective, and I think this was probably already understood by a lot of people in the '70s, the real strength of block codes is that you have algebraic decoding algorithms for them that allow you to use very long, very powerful block codes and still have a reasonable decoding algorithm. This is why Reed-Solomon codes have become the workhorse that they've become. A sort of standard Reed-Solomon code is a code in which the symbols are bytes, 8 bit words, and the code is maybe 255 bytes long, 223 information bytes and thirty-two parity-check bytes. With such a code you can correct up to sixteen errors in a block, which is a 2,000-bit block. Sixteen-byte errors. Sixteen-byte error-correction is a very powerful code, but it's reasonable because there are these algebraic decoding algorithms.

That's the great strength of block codes: you can actually build very long, very powerful, error-correcting codes. That's why they're useful as outer codes in concatenated codes, and why they're useful in combination with interleavers for burst error-correcting codes. I think the only block codes that are really used nowadays are Reed-Solomon codes. They are used for that kind of purpose, just the way I suggested they should be back in '65.

Otherwise, when you're trying to go over a real channel where your output in the first instance is a real signal, you want an output that is not just a one or a zero, but a so-called soft decision that has information about the reliability of the decision built into it. In those cases convolutional codes have a strong advantage. So the standard design now is to build an inner convolutional code that operates directly on the channel, normally decoded by something like the Viterbi algorithm. If it's a bursty channel, you include some interleaving in there to break up the bursts and make it appear more like a random channel. You use that to get an error rate like 10-2 or 10-3. Then you add on the outside of that a Reed-Solomon code, very long, very powerful, with a very complex error corrector which nonetheless you can build. That drives your error rate down to 10-12 or whatever you need for your compact disk player or whatever.

Goldstein:

Okay, so we don't have a situation here where convolutional codes supplant block codes. Rather, used in combination, concatenated, they mutually reinforce.

Forney:

Yes. The standard design uses them in this complementary fashion.

Eclipse of Sequential Codes

Goldstein:

But we do see sequential codes being replaced.

Forney:

Yes, sequential decoding was, I would say, almost completely supplanted in a practical sense. Sequential decoding uses long convolutional codes with an iterative decoding algorithm. It was almost completely supplanted by the Viterbi algorithm used with short convolutional codes. That is not quite as powerful, but it was the appropriate technology for the early '70s. It benefited from an extremely good job of technical marketing by Linkabit and so it sort of became the standard. My feeling is that nowadays one might go back to sequential decoding which is actually capable of better performance than the Viterbi algorithm, use longer codes, and use sequential decoding. That will probably happen in various applications over the next couple of years.

Goldstein:

Do you think there was unanimity about the Viterbi algorithm being superior to sequential decoding in the early '70s? Might anyone have disagreed and felt that sequential decoding was still better in some ways.

Forney:

Perhaps. In fact, I don't think the case was ever seriously argued. We got completely out of the field. Had we stayed in we might have continued to explore the sequential decoding alternative, but Linkabit was basically alone in the early '70s as we had been alone in the '60s, and the Viterbi algorithm swept everything before it. It got adopted as a standard in a number of space communication systems. It got incorporated into custom LSI chips capable of very high speeds. So there was kind of a bandwagon effect where you could get this standard thing off the shelf from Linkabit, or ultimately from somebody else, that did a very good job. Nobody that I remember was promoting sequential decoding, or even looking at it from a practical point of view during that time. The comparisons that were being made were basically between the Viterbi algorithm and block codes and in practical settings the Viterbi algorithm beat block codes of comparable complexity all the time. They won. [laugh]

Goldstein:

It's always interesting to see how that process happened.

Forney:

You ought to talk to Viterbi or somebody and get a more inside view on how that all took place.

Goldstein:

I'd also be interested in learning if there was anyone who still thought there was some promise for sequential decoding.

Forney:

It seemed to me that it was completely forgotten. Maybe I'm unaware of some places where the flame still burned, but it was just kind of wiped off the map.

The Modem Business and the AE-96

Goldstein:

Can you tell me what happened at Codex once you decided to get out of error-correcting codes? You said you were working with modems.

Forney:

The story here is that about '67 or '68 the then management of Codex decided that it was just too hard to try to make a business of error-correcting codes. Furthermore, it didn't want to be 100 percent dependent on government business, which then and now is crummy business, and wanted to develop a commercial business.

They did several things. They first bought a company called Teldata from California. It was a subsidiary of some larger company; I don't remember which one. Basically Teldata consisted of Jerry Holsinger and one other guy, Eli Adelson. They had a design for a 9600 bits per second single sideband modem. They developed it basically in a government-oriented environment, and the idea was to exploit it commercially which Jerry very much wanted to do. The company he was in was a totally government oriented company, so he came to Codex to try to make this fly as a commercial product. It became our AE-96, which was our original 9600-bit modem. I think the first shipments were in '69. We hired a guy named Art Carr out of Honeywell as Vice President of Marketing because he had experience in the commercial mini-computer business, and he was going to lead us into the commercial world.

In 1969 and '70 just about everything bad that could ever possibly happen to a company happened to Codex Corporation. It's really remarkable. We had gone public in 1968 at a price of 17, which seemed very high to me, but that was a very frothy time for electronics companies and we were a new high-tech company. The stock price ultimately got up to about 50. However, 1969 and early '70 was basically one of those times when the military electronics markets just dried up. There wasn't any business for anybody. I don't remember exactly what was happening. Basically, all of our error-correction contracts were drying up, which made it easy to decide to get out of that business. At the same time, the AE-96 was having severe problems out in the field. It turned out to be subject to a problem called phase jitter which we didn't know existed in the telephone network. The telephone network really didn't know it existed either.

Goldstein:

I don't want to interrupt your flow, but did you mention what the AE-96 was?

Forney:

That was the first commercial 9600 bits per second modem by anyone. AE stood for adaptive equalization, ninety-six for 9600. It was single sideband, and had a digital adaptive equalizer; it was basically Jerry Holsinger's design. But we brought it out as a commercial product. It looked like a military product. It was ugly as sin, because it had a military package. Originally it came out at $23,000. We sold it primarily to people like British Airways, or banks, or whoever had rented a dedicated voice line across the Atlantic and were sending 2400 bits per second over it. By putting this modem on there you could go at 9600 bits per second.

Goldstein:

You were saying there was this phase-jitter problem.

Forney:

Right, and a performance problem due to phase-jitter. It required a lot of tweaking in the field. I think there were other reliability problems. The thing was a pig from a design point of view. Anyway, it wasn't jumping off the shelves. I think we sold a total of 300 of them or something. The joke was it was really only 100 of them, which went out three times and came back twice. It was very hard to make them stick because they were just marginal performers, marginally reliable. But it was a tremendous learning experience. We learned what the real problems were in phone lines. So as we get into our successful high-speed modems, I still think the AE-96 was very worth doing.

Lows and Highs of Business

Forney:

Anyway, it wasn't making us any money in '69 or '70; it was costing us money. I think Jerry Holsinger left during '69 or something like that, which was partly due to the problems we were having. There were also personality conflicts and so forth. He went on to start his own company called Intertel in the modem business, which was fairly successful. He ultimately sold it for a few million dollars, so it was successful from his point of view. It was never a major factor in the industry.

So, the military business was drying up, the commercial business wasn't getting off the ground, and in 1970 the stock price was starting to come down. I think the bloom was off the rose in the stock market. In early 1970 we began the development of a second-generation modem, but it was probably going to take us at least a year or so to get it developed. I was in charge of that. And then we needed more financing. We had concluded an agreement with the bank in April of 1970, and the weekend before the closing of that financing our president, Jim Cryer dropped dead on the tennis court of a heart attack. That was absolutely shattering news both personally and from a corporate point of view.

The financing didn't go through. We were out of money. The other founder of the company, Arthur Kohlenberg, who was the technical head and my mentor, had had Hodgkins' disease, which was in remission. It came back that year in the springtime and he died in July of 1970. So we lost both of our founders, both our top management. We were out of money. We had no products that were making any money. By all rights we should have gone out of business. The board of directors and the interim management, Jim Storey, who was the acting CEO, and Art Carr, basically cut back from 200 people to under a hundred people. We concentrated all our resources on getting this new modem done and building a multiplexer to go with it. And what ultimately happened was that the board scraped up a million dollars, at a stock price of four, in September of 1970, just to keep us going for a year. Based on that financing we got the new modem out. It was successful. It really began to take off in the following year.

We did another private placement in September of the following year, and the company then had a meteoric success. We went from a million to two million to four million to eight million to sixteen million over the next four years and really became the leader in the high-speed modem industry. I guess in terms of sales the leader was Racal-Milgo during that time, but we caught up to them sometime in the mid-'70s and passed them. By all rights we should have been out of business, but we just hung in there and recovered on the back of these new second generation high-speed modems. Those were really the glory days for Codex. We were at about $40-million when we were acquired by Motorola in 1977.

Second Generation High-Speed Modems

Goldstein:

What features did the second-generation modem offer?

Forney:

It worked. [laugh] That was an important feature. It was also much more reliable, a new generation of technology. It was basically the same technology I talked about with Irwin Jacobs, when I had learned about by designing this high-speed sequential decoder. That was another very fortuitous thing. I learned how to design with MSI TTL logic in '68 to '69 by building this high-speed sequential decoder. So I did basically all the logical design of this new modem. Again, I think a key to its success was that somebody who understood what needed to be done algorithmically was also doing all the digital design and could optimize the design. So it was much more reliable, much lower in factory cost, and a lot more modern in design.

From a technical point of view the key thing was that we went from single-sideband to QAM double-sideband, which was really an idea that Bob Gallager had been pursuing for a couple of years while Jerry Holsinger was working on single sideband. He felt intuitively that double-sideband was a more natural and better way to go, particularly when the limiting impairment was phase jitter. It turns out you can deal with phase jitter much more naturally and effectively in a QAM system than you can in a single-sideband system where there really isn't much you can do about it. So we were way ahead of the rest of the industry. We came out with QAM modems in 1970 and the first competing QAM modems from AT&T and Racal-Milgo came out in '73 or '74. So we had a four-year head start on what became accepted as very much the preferred technology. We just made a lot of right choices. We made a right choice in the modulation scheme, the adaptive equalizer, and the hardware that we used to build it. Fortunately it was in an area where paper-and-pencil design translated directly into real-world performance, and where real-world performance was highly valuable. I mean, we were the only people who had a 9600 bit per second modem that actually worked reliably. And we had a bunch of customers for whom that was very important, so it was like shooting fish in a barrel. I don't want to diminish the achievements of the manufacturing and marketing and the field service people. All that was extremely important; without that we wouldn't have been successful either. But when you have a product that fills a need and works and nobody else does, you're in a very favorable position.

Goldstein:

You were selling it again to banks and airlines?

Forney:

Yes. When this modem came out it cost $11,500 and it went into high-return-on-investment types of situations: expensive, long-distance private lines, corporate networks, and some government networks. We got an important government contract for Worldwide Channel Packing. Basically, the sales justification was that you can save a lot of money by running four 2400 bit per second channels down one phone line that might cost $10,000 per month, transatlantic, something like that. We'll sell you $23,000 worth of modems at each end and you'll pay that back in six months on this expensive channel. It was a very easy, direct sales proposition.

Goldstein:

And you could take advantage of the widely felt dissatisfaction with the unreliability of your competitors. I'm wondering how you marketed your QAM, which may not have been meaningful to your clients.

Forney:

They didn't care what was inside it. For that price, in that era you always had to demonstrate that you could work over the guy's channel before you could make a sale.

Goldstein:

So you'd come over and install it.

Forney:

Yes. You needed field people to install it, to show that it actually would work. We would go in and show that ours worked and I presume other people went in and would have more difficulty, and we could get the order. Again, I'm making it sound easier than it really is, but that was basically the story.

Goldstein:

Was there a disadvantage being a pioneer at this stage? You make it sound like Codex discovered the phase jitter problem on phone lines, and that seems like it was a market advantage to your competitors.

Forney:

One of Art Carr's favorite expressions is the pioneer is the guy with the arrows in his ass, and we nearly went out of business pioneering the AE-96. We didn't go around writing technical papers saying that phase jitter was the problem on telephone channels. I think we told key customers, and certainly AT&T became aware of it. Our primary competitors became aware, but probably a little bit later than we did and probably reacted a little bit slower than we did. Pioneering nearly put us out of business, but it did give us the experience and knowledge of the real network that allowed us to be successful the second time around. The second-generation solution really worked, and to the extent that we were pioneering with that it was entirely in our favor.

Stanford and MIT

Goldstein:

Was there was less theoretical work in this stage of Codex' development? Fewer papers?

Forney:

Yes. Papers were always something I did on the side, sort of as a hobby. It was never something that was part of Codex's business. If you look at my bibliography I was writing papers through about 1973 or so, and then I basically stopped. After developing this new modem family I basically went "aaaggghhh," and went off to Stanford for a year. I spent a year at Stanford, 1971-72. I was really wrung out from everything Codex went through and the pressures of this development. When I went, I didn't know whether I might become a professor, or come back to Codex, or do something else. The upshot of that year was Stanford wanted me to stay as a professor but I never could quite commit to that, I wanted to come back to the East. I came back to the East, actually spent some more time at MIT before deciding to come back to Codex. I basically gravitated back to Codex for lack of having committed to anything else. I showed up again in the fall of 1972 and said, "Okay, what's to do?" Certainly from that point forward I was much more involved in developments that were less based on theoretical breakthroughs. I quickly became much more involved as an engineering manager than as a technical contributor.

The next major projects were to turn this design into a custom LSI design, which we did in combination with Rockwell in 1973-75. We came out in '75 with an LSI model modem, which again was a tremendous leap over the whole rest of the industry. That was the basis for our growth for the next seven, eight, nine years. It was a tremendously successful development for both Codex and Rockwell. It is the basis of Rockwell's current dominance of the modem chip industry and the fax modem industry. But it was extremely good for us too. We had cost performance that no one else could approach for a long time.

Networking Business

Forney:

Also, we began as far back as then to try and develop a networking business. I hired a guy named Jim Vander May from the University of Illinois in 1973. He was a very bright guy who developed our first networking products, which are basically statistical multiplexer products. He went through a lot of pioneering pain with those, which ultimately led to Jim leaving the company. He then went on to found a very successful company in the printer business. But his work was the basis of such success as we've had in the networking business in the 1975-85-time period. And that's a field where you don't work from IEEE Transactions papers at all. It's much more like the computer business where the idea is to make something that will function at all, not something that will be optimized.

Goldstein:

These are LAN and WAN networks?

Forney:

These were basically WAN products. That lingo didn't exist back then, but stat muxes were the original wide-area networking products.

Goldstein:

Who decided to take Codex in that direction?

Forney:

We all agreed that we didn't want to be totally dependent on modems. Again, to return to a theme I mentioned early in this discussion, it was agreed by 1972 or so that modems were basically dead. People said that theoretical and algorithmical development had gone as far as you could go, that 9600 bits per second was as high as you could ever realistically get over the general telephone network, and that furthermore digital networks were the coming thing. AT&T's Digital Data Service, DDS, was announced in 1972. This was sort of the ISDN of its day. Instead of getting a private voice line or a switched voice line you could get a dedicated digital line or a switched dedicated line anywhere in the country. At least, that's what DDS was going to be. It threw us and everybody else in the modem business into a panic.

For a variety of reasons, most of which I don't know, most of which were internal to the telephone company stepping on its own toes from a marketing point of view, a pricing point of view, and an availability point of view, DDS turned out to be a flop. It was actually, retrospectively, very helpful to us because nobody else entered the modem business. There were no new entrants for a long time in the modem business because Wall Street and venture capital people knew that modems were perhaps an interesting interim technology in which you could make a few bucks, but obviously they were going to get killed eventually by digital networks. So there wasn't a whole lot of dog-eat-dog competition in the modem business, a lot of hungry new entrants. It was the original people who just kept selling more and more modems, and what a happy thing for us.

Goldstein:

I'm a little bit surprised to hear you say that for some reason DDS went bust. It sounds like something you might have been watching very closely, perhaps even trying to influence.

Forney:

Well, I wasn't the one who was watching it closely or meeting it out in the field, so I don't have a clear understanding of why it went bust. But among the factors was that it was always priced higher than a voice circuit. Probably more important than that even was that it was never widely available. If you were a bank or an airline or somebody with a large corporate network, maybe DDS would be available at seventy-percent of your locations, so you would have to decide whether to piece out a DDS network with modems.

If you're interested in this I really encourage you to look at this book by Pelkey which probably doesn't take the story as far forward as it should on DDS. You know, when I say I really don't understand all the reasons for it, I'm referring more to the days before the Bell System was broken up. My picture is that there were people at headquarters who promoted DDS but that when you got down to it it was sold and installed by people out in the local operating companies. They tried to support it with the same craftspeople who were supporting the voice network. They didn't understand it, and they wished it would go away. Nobody in New England Telephone really cared a whole lot about DDS or was committed to making it successful. They didn't want to price it in such a way that it might possibly eat into their voice revenues, and so forth. You just never got the sense when you got down to the local telcos that they were wholly behind it. I think that probably accounts for as much as these more tangible factors that I mentioned before.

Goldstein:

So the impact on a company like Codex was to stimulate you to diversify to networking?

Forney:

Right. We were scared to death. We honestly believed that we had maybe five more years in the modem business, and by then we damn well better be in some other business. And that's a powerful incentive to try to develop some new business, so we went in a direction which was very logical. Our customer base was basically made of large corporate networks, and our competence was sending as much data as possible down the pipe in the most efficient possible way. We could see that with statistical multiplexers in a point-to-point link, and much more in a networking environment, we could do things a lot more efficiently than they were being done by the computer networks of that day. So we set our cap to go after that business.

Goldstein:

I'm worried about the time and whether you need to wrap up. We could continue the story a little bit further if you have the time but I don't want to keep you.

Forney:

This would make a logical stopping point. I mean, we're basically up to 1975. I think you're more interested in the business history than in the intellectual history or the personal history. All these things continued after 1975. But maybe that's something for another day.

Goldstein:

Okay, great.

Forney:

Is this what you wanted?

Goldstein:

Oh, I think so. Perhaps I made a mistake by asking questions that indicate that I'm more interested in the business history. Actually, the intellectual history is interesting too. I'm not sure I'm in the position to ask really meaningful questions about it. I'm always fascinated when there's an intersection between all three, where the personal predispositions motivate an intellectual interest which have a commercial impact, things like that.

Forney:

Well, there's certainly a lot that could be said along those lines, but as I say maybe that's for another day.

Goldstein:

Sure. I can stop this and just mention that the book you mentioned is a confidential typescript, not for distribution, by James Pelkey called The Emergence of Economic Life: Computer Communications, 1968-1988, and that's available for reference from you?

Forney:

Well, I'm lending it to you for your personal perusal. I think it will give you valuable background on the period we've been talking about.

Goldstein:

Good. Thank you.