Beginnings: the first hardware digital filters IEEE SIGNAL PROCESSING MAGAZINE Leland B. Jackson Beginnings: The First Hardware Digital Filters NOVEMBER 2004 55 ate may tap you on the shoulder anywhere, including an airplane. In December 1965, while flying to Atlanta for Christmas, I ran into Edward E. David, then executive director for Communications Research at Bell Labs and later science advisor to President Nixon. Ed was also from Atlanta, and I had met him in 1961 when I worked at Bell Labs as a Massachusetts Institute of Tech- nology (MIT) co-op student in Henry S. McDonald’s department. James F. Kaiser was another mem- ber of Hank’s department, and dur- ing the Kennedy administration, Jim and I had been known as “the other JFK and LBJ.” On the plane, Ed offered me a job in Hank’s department with the understanding that I would attend Stevens In- stitute of Technology part time for my Sc.D. and, as an adjunct profes- sor at Stevens, Ed would be my the- sis advisor. Thus, on that fateful plane trip began my career in digital signal processing. When I reported to work in August 1966, Hank and Jim intro- duced me to an exciting new area called digital filtering, based largely on earlier results from the field of sampled-data control systems. Jim had recently published the first book with an extensive chapter on digital filters [1]. Hank was a true visionary and a salesman, and he could already see the tremendous impact that this new technology would have on communication systems in F L eland Jackson was born on 23 July 1940 in Atlanta, Georgia, and grew upthere. He obtained the S.B. and S.M. degrees from the MassachusettsInstitute of Technology (1963) and the Sc.D. degree from the Stevens Institute of Technology (1970). He has been a member of the technical staff with Bell Laboratories (1966–1970) and vice president of engineering with Rockland Systems Corporation (1970–1974). Since 1974, Dr. Jackson has been with the Department of Electrical and Computer Engineering, University of Rhode Island, where he is currently a professor of electrical engineering. His research work has focused on quantization effects in digital filters and parametric signal modeling. Dr. Jackson coauthored the books Digital Filters and Signal Processing (1986; 1989; 1996), and Signals, Systems, and Transforms (1991). For his work in finite word length design and hardware implementation of dig- ital signal processing systems, he received the Technical Achievement Award of the IEEE Signal Processing Society (1983). Mixing professional and personal interests was easy for Dr. Jackson, who has been the audio engineer for the digital recordings of his wife Diana’s pipe organ music. An accomplished organist, she has had more than 20,000 plays of her music on the web, including works by Bach, Widor, and Vierne, all wear- ing his engineering fingerprint. In recent years, he has become interested in genealogy and was surprised to learn that his eighth great grandfather, Sir Anthony Jackson, was imprisoned by Cromwell in the Tower of London between 1651–1659, and that his fifth and sixth-great grandfathers were Quakers who immigrated to Pennsylvania in 1717. The Jacksons have also traveled to far-away destinations, where the inherit- ed adventurous spirit of his forefathers must have been their guide: East Africa, Australia, New Zealand, Peru, Costa Rica, the Galapagos Islands, and the Amazon River. At home in Rhode Island, Leland Jackson enjoys sailing, hiking, digital photography, and reading historical novels. He is also looking forward to reading more bedtime stories to his grandchildren, now that they have moved to a new house next door. For the “DSP History” column, Dr. Leland Jackson tells the story of his pio- neering work in digital filter hardware implementations with simplicity and interleaved bits of humor. Enjoy! —Adriana Dumitras and George Moschytz “DSP History” column editors adrianad@ieee.org moschytz@isi.ee.ethz.ch 1053-5888/04/$20.00©2004IEEE dsp history IEEE SIGNAL PROCESSING MAGAZINE56 NOVEMBER 2004 dsp history continued the future. He had been telling any- one he could buttonhole at Bell Labs about these new developments (and with his boundless energy and enthusiasm, that was just about everyone), and he was pushing man- agement to devote more R&D resources to this area. He decided that to demonstrate the possibilities, he would select an analog unit in current use in the Bell System, and we would build a prototype digital equivalent. His choice was the touch-tone receiver (TTR), the unit in the local telephone central office that decodes the multifrequency tones used for dialing, because it con- tained every type of frequency-selec- tive filter: low pass, high pass, band pass, and band rejection. The original block diagram of that TTR is shown in Figure 1. Thus, my first assignment was to design and build an all-digital TTR. Hank was excited about the latest advance in the integrated-circuit (IC) technology, transistor-transis- tor logic (TTL), which was rapidly replacing the older diode-transistor logic (DTL), and resistor-transistor logic (RTL). We could buy four two-input gates, two four-input gates, two flip-flops, or two full adders in a single 14-pin dual-inline IC package! We could even get an 8-b shift register in a single package. Hank realized that, because of the parallelism inherent in digital filters, we could use bit-serial arithmetic and still be fast enough to keep up with the data rate in real time. In fact, using later very large scale inte- gration (VLSI) terminology, our circuits were flow simple, cell sim- ple, completely pipelined, locally connected, and thus systolic [2]. The sampling rate was 10 kHz, with 10-b rounding of multiplication products, for a basic bit rate of 100 kb/s. The TTL bit-serial circuits could run at least an order of mag- nitude faster, so we multiplexed the filters by eight; i.e., by interleaving the samples from different filter inputs into a basic second-order sec- tion, lengthening the shift registers comprising each delay (z −1 ) by a factor of eight, and cycling through the filter coefficients from a read- only memory, we could realize eight low-pass or bandpass filters with a single second-order section. Similarly, two second-order high- pass filters and two sixth-order bandstop filters were multiplexed into a single section. Hank and I have a patent on this digital-filter multiplexing scheme, and I have another on the implementation of saturation arithmetic in digital fil- ters. I am aware of earlier fixed clut- ter-rejection digital filters in moving-target-indicator radars, but to my knowledge, this demonstra- tion TTR was the first realization of a fully programmable digital filter in hardware form. It’s interesting how we discov- ered the existence of overflow oscil- lations in fixed-point digital filters and thus the need for overflow detection and saturation arithmetic. The TTR was built in a single 6-in- high chassis with wire-wrapped cards mounted vertically. A fluorescent light was mounted over the chassis. The unit would be operating prop- erly with a sampled sinusoid displayed on the oscillo- scope, but if we turned on the light, the signal would break up into a seemingly random, full-scale oscilla- tion. Turning the unit off and then on again to reset the delays (z −1 ), the sinu- soid would reappear and normal operation would resume. We tried this over and over, and were per- plexed at what was going on. However, we quickly realized that the inherently nonlinear overflow charac- teristic of twos-complement arithmetic, coupled with the feedback in a recursive digital filter, could easily produce oscillations for▲ 1. A digital touch-tone receiver. Notations A-D, HPF, BPF, LPF, BRF, HWR, LIM stand for analog-to- digital converter, high-pass filter, band-pass filter, low-pass filter, band-rejection filter, half-wave rec- tifier, and limiter, respectively. HPF 2 BRF 2 BPF 1 BPF 4 BPF 5 BPF 8 BRF 1 HPF 2 A-D HPF1 Touch- Tone Signal LIM LIM (Multiplexed Units Enclosed in Dotted Lines) HWR HWR HWR HWR LPF LPF LPF LPF Level Detect Level Detect Level Detect Level Detect Detection Logic Detected Digit (continued on page 81) tion for contextual information and for time registration. And, the dimensionality of the supervector might lead to computational intractability. At the other extreme, one might run “recognition” on each mode separately to conclusion and then compare word string results across modes. The disparities in richness could make this approach inefficient, or at worse, useless. Where we stand at present, and on which the systems of Figures 6, and 7 depend, is to use speech as totally centric, bearing the main communication burden, and to uti- lize gaze and gesture mainly at the feature level as complements to resolve deictic references that speech leaves ambiguous. This is not satis- fying. But it’s where we are! Acknowledgment Aspects of this research have been supported by the National Science Foundation and by the Defense Advanced Research Projects Agency. References [1] R. Chandrasekaran, “Statistical modeling of user input in a multimodal speech and graphics environment,” M.S. thesis, Dept. Elec. Comput. Eng., Rutgers Univ., 2004. [2] S. Dusan, G. Gadbois, and J. Flanagan, “Multimodal interaction on PDA’s integrating speech and pen inputs,” in Proc. of EUROSPEECH, Geneva, Switzerland, 2003, pp. 2225–2228. [3] J. Flanagan and T. Huang, “Human-computer multimodal interface,” Proc. IEEE, vol. 91, no. 9, pp. 1267–1271, 2003. [4] F. Flippo, A. Krebs, and I. Marsic, “A frame- work for rapid development of multimodal interfaces,” in Proc. Int. Conf. on Multimodal Interfaces (ICMI 2003), Vancouver, BC, pp. 109–116, 2003. [5] M. Kaur, M. Tremaine, N. Huang, J. Wilder, Z. Gakofski, F. Flippo, and C. Mantravadi, “Where is it? Event synchronization in gaze- speech input systems,” in Proc. Int. Conf. on Multimodal Interfaces (ICMI 2003), Vancouver, BC, pp. 151–158, 2003. [6] S. Oviatt, R. Coulton, S. Tomko, and B. Xiao, “Toward a theory of organized multimodal integration patterns during human-computer interaction,” in Proc. IEEE Int. Conf. on Multimodal Interfaces (ICMI 2003), Vancouver, BC, pp. 44–51, 2003. IEEE SIGNAL PROCESSING MAGAZINENOVEMBER 2004 81 certain initial conditions. Electro- magnetic radiation generated by turning on the fluorescent light was generating the required initial con- ditions. Intuitively, we added over- flow detection and saturation circuits to the feedback loops of the filters, which fixed the problem, and our colleagues Ebert et al. [3] sub- sequently proved that this indeed precluded overflow oscillations in second-order sections. Separately, I also investigated and modeled the small-scale limit cycles caused by multiplication rounding [4] and the tradeoff of roundoff noise versus dynamic range in fixed-point digital filters [5]. Another groundbreaking idea of Hank McDonald was the use of delta modulation to implement analog-to- digital (A/D) conversion. Our homemade A/D converter consisted of a simple delta-modulator, followed by an up/down counter and a “leaky” accumulator. The contents of the counter were transferred out at regular intervals, with the counter then being reset, to produce a differ- ential pulse code modulated (DPCM) signal. The DPCM signal was, in turn, accumulated (with a slight “leak” for stability) to produce the desired pulse code modulated input. This made a very simple and effective A/D converter. If only we’d thought of delta-sigma converters! A paper on our approach to digi- tal-filter implementation was pub- lished in IEEE Transactions on Audio and Electroacoustics (the fore- runner of IEEE Transactions on Signal Processing) in September of 1968 [6]. If you look at my picture at the end of that 1968 article, you will see a very serious young man gazing blankly into space. This pic- ture was taken on 6 June 1968, and that evening I proposed to my wife. Evidently, the enormity of what I was contemplating had begun to dawn on me! References [1] J.F. Kaiser, “Digital Filters,” in System Analysis by Digital Computer, J.F. Kaiser and F.F. Kuo, Eds. New York: Wiley: 1966, pp. 218–85. [2] L.B. Jackson, Digital Filters and Signal Processing, 3rd ed. Boston, MA: Kluwer, 1996. [3] P.M. Ebert, J.E. Mazo, and M.G. Taylor, “Overflow oscillations in digital filters,” Bell Sys. Tech. J., vol. 48, pp. 2999–3020, 1969. [4] L.B. Jackson, “An analysis of limit cycles due to multiplication rounding in recursive digital fil- ters,” in Proc. 7th Allerton Conf. Cir. Sys. Th., 1969, pp. 69–78. [5] L.B. Jackson, “On the interaction of roundoff noise and dynamic range in digital filters,” Bell Sys. Tech. J., vol. 49, pp. 159–184, 1970. [6] L.B. Jackson, J.F. Kaiser, and H.S. McDonald “An approach to the implementation of digital filters,” IEEE Trans. Audio Electroacoustics, vol. AU-16, pp. 413–421, 1968. dsp history continued from page 56 footer1: