Programs for
`Digital Signal Processing
`Edited by the'
`Digital Signal Processing Committee
`IEEE Acoustics, Speech, and Signal Processing Society
`
`Committee members:
`
`Clifford J. Weinstein (Chairman), MJ.T. Lincoln Laboratory
`James W. Cooley, IBM T. J. Watson Research Center
`Ronald E. Crochiere, Bell Laboratories
`Marie T. Dolan, Bell Laboratories
`Joseph R. Fisher, Signal Processing Systems, Inc.
`Howard D. Helms, American Telephone and Telegraph Company
`Leland B. Jackson, University of Rhode Island
`James F. Kaiser, Ben Laboratories
`James H. McClellan, Massachusetts Institute of Technology
`Carol A. McGonegal, Bell Laboratories
`Russell M. Mersereau, Georgia Institute of Technology
`Alan V. Oppenheim, Massachusetts Institute of Technology
`Lawrence R. Rabiner, Bell Laboratories
`Charles M. Rader, M.I.T. Lincoln Laboratory
`Ronald W. Schafer, Georgia Institute of Technology
`Harvey F. Silverman, IBM T. J. Watson Research Center
`Kenneth Steiglitz, Princeton University
`Jose M. Tribolet, Instituto Superior Tecnico
`John W. Woods, Rensselaer Polytechnic Institute
`
`A volume published under the sponsorship of the
`IEEE Acoustics, Speech, and Signal Processing Society.
`
`+IEEE
`. PRESS
`The Institute of Electrical and Electronics Engineers, Inc. New York
`
`1
`
`Micro Motion 1040
`
`

`
`IEEE PRESS
`
`1979 Editorial Board
`
`A. C. Schell, Chairman
`
`George Abraham
`Clarence Baldwin
`Walter Beam
`P. H. Enslow, Jr.
`M. S. Ghausi
`R. C. Hansen
`R..K. Hellmann
`E. W. Herold
`
`Thomas Kailath
`J. F. Kaiser
`Dietrich Marcuse
`Irving Reingold
`P. M. Russo
`Desmond Sheahan
`J. B. Singleton
`S. B. Weinstein
`
`W. R. Crone, Managing Editor
`
`Isabel Narea, Production Manager
`
`Joseph Morsicato, Supervisor, Special Publications
`
`Copyright © 1979 by
`THE INSTITUTE OF ELECTRICAL AND ELECTRONICS ENGINEERS, INC.
`345 East 47 Street, New York, NY 10017
`All rights reserved.
`
`PRINTED IN THE UNITED STATES OF AMERICA
`
`IEEE International Standard Book Numbers: Clothbound: 0·87942·127·4
`Paperbound: 0-87942-128·2
`
`Library of Congress Catalog Card Number 79·89028
`
`Sole Worldwide Distributor (Exclusive of the IEEE):
`
`JOHN WILEY & SONS, INC.
`605 Third Ave.
`New York, NY 10016
`
`Wiley Order Numbers: Clothbound: 0-471-05962·5
`Paperbound: 0·471·05961·7
`
`iv
`
`2
`
`

`
`Contents
`
`Preface
`
`Standards
`
`IlMACH
`RIMACH
`DIMACH
`UNI
`
`Chapter 1: Discrete Fourier Transform Programs
`J. W. Cooley and M. T. Dolan
`
`1.1 FOUREA - A Short Demonstration Version of the FFT
`C. M. Rader
`
`1.2 Fast Fourier Transform Algorithms
`G. D. Bergland and M. T. Dolan
`
`1.3 FFT Subroutines for Sequences with Special Properties
`L. R. Rabiner
`
`1.4 Mixed Radix Fast Fourier Transforms
`R. C. Singleton
`
`1.5 Optimized Mass Storage FFT Program
`D. Fraser
`
`1.6 Chirp z-Transform Algorithm Program
`L. R. Rabiner
`
`1. 7 Complex General-N Winograd Fourier Transform Algorithm (WFT A)
`J. H. McClellan and H. Nawab
`
`1.8 Time-Efficient Radix-4 Fast Fourier Transform
`L. R. Morris
`
`1.9 Two-Dimensional Mixed Radix Mass Storage Fourier Transform
`R. C. Singleton
`
`Chapter 2: Power Spectrum Analysis and Correlation
`L. R. Rabiner
`
`2.1 P.eriodogram Method for Power Spectrum Estimation
`L. R. Rabiner, R. W. Schafer, and D. Dlugos
`
`2.2 Correlation Method for Power Spectrum Estimation
`L. R. Rabiner, R. W. Schafer, and D. Dlugos
`
`v
`
`ix
`
`S-1
`
`S-5
`S-8
`S-10
`S-12
`
`1.0-1
`
`1.1-1
`
`1.2-1
`
`1.3-1
`
`1.4-1
`
`1.5-1
`
`1.6-1
`
`1.7-1
`
`1.8-1
`
`1.9-1
`
`2.0-1
`
`2.1-1
`
`2.2-1
`
`3
`
`

`
`Preface
`During the past fifteen years, digital signal processing has been an extremely active and dynamic
`field. Advances in integrated circuit technology and in processor architecture have greatly enlarged the
`scope of the technical areas to which digital signal processing techniques can be applied. Research in
`fundamental signal processing techniques and algorithms has led to dramatic improvements in the
`efficiency of signal processing systems.
`An important facet of the progress in digital signal processing has been the development of algo(cid:173)
`rithms and their embodiment in computer programs, both for the execution of processing operations on
`signals and for the design of signal processing filters and systems. The purpose of this book is to make
`widely available, in a directly usable form, a comprehensive set of computer programs useful for digital
`signal processing.
`In addition, the book serves as an outlet for excellent programming effort and
`enables authors of programs to receive credit for their work.
`The programs have been carefully selected to cover a broad spectrum of digital signal processing
`applications and design techniques. The programs are categorized into eight chapters, and separate
`summaries (authored by chapter editors who were also asked to make final checks on the documenta(cid:173)
`tion and code) are provided with each chapter. The first chapter focuses on the Discrete Fourier
`Transform (DFT) and presents a variety of Fast Fourier Transform (FFT) and related algorithms.
`Chapter 2 'includes algorithms for the periodogram and correlation methods of power spectrum estima(cid:173)
`tion and for coherence and cross spectrum estimation. A program for high speed, FFT-based convolu(cid:173)
`tion is presented in Chapter 3. Chapter 4 presents several algorithms related to the linear prediction
`techniques of signal processing, including the autocorrelation, covariance, and lattice methods. The
`design and synthesis of Finite Impulse Response (FIR) digital filters are the subjects of Chapter 5.
`Algorithms for optimal (minimax), windowed, and maximally-flat filter designs, and a design program
`which incorporates finite-word-Iength effects, are included. Chapter 6 presents a comprehensive set of
`programs dealing with the design and synthesis of Infinite Impulse Response (IIR) digital filters. The
`first program in that chapter includes most of the classical filter design techniques as well as considera(cid:173)
`tion of finite word length issues such as pairing and ordering in a single but modular package. The
`.other programs in that chapter are specialized either to the finite word length design problem or to filter
`design based on iterative optimization. Chapter 7 deals with cepstral and homomorphic algorithms,
`with specific attention to the difficult problem of phase calculation in a homomorphic system. Finally,
`Chapter 8 presents several programs for interpolation and decimation, the fundamental operations
`necessary for changing sampling rates in a digital system. Included are multistage implementations and
`sampling rate conversion by rational ratios.
`The book is the culmination of a project undertaken in' early 1976 by the Digital Signal Processing
`In contrast to previous
`Committee of the IEEE Acoustics, Speech, and Signal Processing Society.
`books in the IEEE Press reprint series, this book consists largely of material which has not been pub(cid:173)
`lished before. In addition, a unique and complex set of issues regarding the publication of computer
`programs had to be dealt with. These issues included: (1) clarity and uniformity of documentation and
`program presentation; (2) independent review and verification of all programs; (3) portability and
`machine-independence of code; and (4) availability of computer-readable source programs. The project
`has therefore been a very ambitious and time-consuming one for the committee, for the program con(cid:173)
`tributors, and for the reviewers.
`In order to assess the feasibility of the project, the committee distributed to the digital signal pro(cid:173)
`cessing community in early 1976 a description of the proposed project and a request for descriptions of
`candidate programs. The distribution of this request was carried out both through direct mailing and
`through handouts at the 1976 International Conference on Acoustics, Speech, and Signal Processing.
`In a short time, enough very promising candidate programs had been identified to convince the com(cid:173)
`mittee that the book was not only feasible, but potentially a landmark contribution to the digital signal
`In addition, a reasonable organization of the material into the eight sections now
`processing field.
`included in the book began to emerge.
`Because of the large effort to be required of program contributors and of reviewers, it was deemed
`desirable to pre-screen program candidates based on the offered descriptions, and invite submission of
`only those programs judged most likely to fit our rather stringent requirements. In cases where two
`
`ix
`
`4