Handbook of Real-Time Fast Fourier Transforms: Algorithms to Product Testing / Edition 1

by Winthrop W. Smith

Overview

"This useful, logical, unbiased, FFT compendium allows the user to quickly and accurately obtain practical information to implement a solution or simply acquire a general overview without spending months gathering this information elsewhere."
—Jay Perry, Executive Vice President, Technology, Catalina Research, Inc.

"This is a practical guide for understanding and using FFTs. Win’s (Winthrop Smith, author) years of experience using FFTs to solve real-world problems comes through on page after page. If you’re building an FFT processor, you’ll find this book indispensable."
—Tony Agnello, President, Ariel Corp.

FFTs are at the heart of ADSL, the new telecom standard (T1.413), which allows phones to transfer digital data 200 times faster and simultaneously transmit speech. Fast Fourier Transforms (FFTs) synthesize, recognize, enhance, compress, modify, or analyze signals in products such as Doppler weather radar, CT and MRI scans, AWACS radar, and satellite imaging radar. In this book, you will get the foundation and facts you need to implement FFT algorithms for many diverse applications. Key features you will put to immediate use include:

• Comparison matrices and performance measures for objective selection of weighting functions, algorithm building blocks, algorithms, algorithm mappings, arithmetic formats, and DSP chips
• Extensive algorithm examples with instructions for memory mapping and conversion to code
• An unbiased listing of the FFT features of 51 fixed-point DSP chips, including ASIC and multiprocessor chips, 13 floating-point DSP chips, and six dedicated FFT chips
• Test signals with instructions and examples on how to detect and isolate errors during: FFT algorithm/code development and debugging, and end-product operation
• Design examples for products that use frequency analysis, power spectrum estimation, linear filtering, and two-dimensional processing
• Questions and answers for selecting commercial-off-the-shelf DSP boards

An all-in-one-source for implementing real-time FFT algorithms of any length, this book will be essential to engineers and other technical innovators who want to stay on the cutting edge of FFT technology.

Product Details

ISBN-13:	9780780310919
Publisher:	Wiley
Publication date:	05/22/1995
Pages:	494
Product dimensions:	7.09(w) x 10.30(h) x 1.12(d)

About the Author

Winthrop W. Smith is the author of Handbook of Real-Time Fast Fourier Transforms: Algorithms to Product Testing, published by Wiley.

Read an Excerpt

Handbook of Real-Time Fast Fourier Transforms

Algorithms to Product Testing

---

By Winthrop W. Smith

John Wiley & Sons

ISBN: 0-7803-1091-8

---

Chapter One

1.0 INTRODUCTION

The increased demand for communication, multimedia, and other consumer products has created the need for high-volume, low-cost, multifunction DSP-based products that can use fast Fourier transforms (FFTs) for their signal processing or data manipulation. This book is the first to cover FFTs from algorithms to product testing, with the information needed to create and convert to code FFT algorithms of any length on 10 different architectures. It uses a building-block approach for constructing the algorithms. Included are recommended Memory Maps to streamline assembly and high-level language coding of 17 small-point FFTs, four general algorithms, and seven FFT algorithm examples. To ensure that the algorithms work properly, a test approach for the detection and isolation of errors, refined over many years of time consuming searches for mistakes in FFT algorithms, is detailed.

Spreadsheet-style comparison matrices provide easy to use inventories of the comprehensive array of key FFT elements and performance measures. Dozens of digital signal processing (DSP) chips and criteria for selecting DSP boards are covered. Four design examples at the end of the book show how to apply most of what has been explained.

1.1 LAYING THE FOUNDATION

Chapters 2 and 3 provide the technical foundation and mathematical equations for the algorithms in Chapters 8 and 9. The discrete Fourier transform (DFT) is an equation for converting time domain data into its frequency components. The DFT equation is implemented with FFT algorithms because they are computationally efficient ways of calculating it. All the properties and strengths of the DFT are shared by the wide variety of FFTs that have been developed over the years. However, only three of the five weaknesses of the DFT are also weaknesses of FFT algorithms.

In the beginning of the design process, comparison of the uses and properties of the DFT with the technical specifications of the application will determine if the DFT is a good match. If so, then it makes sense to examine the FFT algorithms, hardware architectures, arithmetic formats, and mappings in this book to decide which combination is best for a specific design.

1.2 DESIGN DECISIONS

The decisions listed are the ones related to real-time FFT selection and implementation. They are listed in an order which differs from the sequence of the chapters, because learning the facts happens more easily in an order that is different from applying them.

Choosing the number of dimensions (Chapters 5-7)

Picking a type of processing (Chapters 5-7)

Selecting the arithmetic format (Chapter 13)

Deciding on a weighting function (Chapter 4)

Determining the transform length (Chapter 5)

Selecting algorithm building blocks (Chapter 8)

Constructing the algorithm (Chapter 9)

Choosing a chip (Chapter 14)

Selecting the architecture (Chapters 10 and 11)

Mapping the algorithm onto the architecture (Chapter 12)

Selecting an off-the-shelf board (Chapter 15)

Creating the test signal and procedures (Chapter 16)

1.2.1 Number of Dimensions

All multidimensional FFTs are done as a sequence of one-dimensional FFTs. The importance of knowing how many dimensions (one, two, or three, usually) there are determines how many FFTs will be needed and how the data must be organized to do the multiple dimensions. This will affect chip processing load and the choice of architecture.

1.2.2 Type of Processing

The type of processing (frequency analysis, convolution, or correlation) will also affect the chip processing load. Frequency analysis requires one FFT for every group of samples, while the other two types require an FFT and an inverse FFT for every group of samples.

1.2.3 Arithmetic Format The choice of fixed-point, floating-point, or block-floating-point arithmetic format will affect the numerical accuracy of the results. Fixed-point DSP chips were the first available and are generally less expensive than floating-point, because this arithmetic takes less silicon area. Floating-point has grown in popularity as semiconductor manufacturers advanced to smaller micron wafers and high-level language compilers became available. Block-floating-point is a compromise approach that provides better accuracy than fixed-point and takes less silicon area than floating-point. It is only available in chips designed specifically for computing FFTs.

1.2.4 Weighting Functions

The selection of one of more than a dozen weighting functions will affect frequency location accuracy while controlling sidelobe effects. They also modify coherent gain, bandwidth, and frequency straddle loss. The selection depends on what combination of these effects matters most in an application.

1.2.5 Transform Length

Choosing a transform length closest to the number of data points to be analyzed will improve the accuracy of the computation, thereby improving frequency accuracy. The size of the transform will directly affect frequency resolution, memory requirements, and the speed at which the computation can be done. A unique feature of this book is the choice of more than one algorithm to compute an FFT of any length.

1.2.6 Algorithm Building Blocks

The algorithm building blocks used will affect the computational load the algorithm requires and the complexity of code to implement that algorithm. This chapter provides 17 small-point transform algorithms for constructing larger algorithms. The choice depends on whether computational load or code complexity is the deciding factor in a specific design.

1.2.7 Algorithm Construction

The way in which the algorithm building blocks are connected to create a larger algorithm will affect the complexity and amount of the code needed to implement it. This chapter details the Bluestein, Winograd, prime factor, and mixed-radix methods for assembling small-point transforms into larger algorithms.

1.2.8 DSP Chips

The selection of which Harvard architecture DSP chip to actually compute the algorithm is determined by the cost and speed considerations of the application, the number of chips needed, a suitable architecture (for multiple-processor designs), and available peripheral hardware to handle some of the functions. This chapter covers the FFT-related features of 51 fixed-point DSP chips, including ASIC and multiple-processor chips, 13 floating-point DSP chips, and 6 dedicated FFT chips.

1.2.9 Architectures

Bit-slice, arithmetic chips were used to construct FFT applications prior to the introduction of DSP chips. However, advances in silicon technology have replaced bit-slice building blocks with DSP chips that include a complete fixed- or floating-point multiplier and adder, as well as memory and program control logic.

All of the DSP chips in this book use a Harvard architecture for interconnecting these elements. FFT-specific chips interconnect several arithmetic building blocks into a small-point FFT to increase performance. Multiprocessor interconnections (pipeline, linear bus, ring bus, crossbar, two- and three-dimensional massively parallel, star, hypercube, and hybrid architectures) of DSP chips are used when a single chip is not adequate. In fact, up to four Harvard processors are now available on a single chip (SPROC 1000 and TMS320C80 families). Chapter 10 describes bit slice, integrated arithmetic and FFT-specific hardware building blocks. Then Chapter 11 shows how to use them in single and multiprocessor architectures. These two chapters prepare the reader for mapping the algorithms in Chapter 9 onto these architectures.

1.2.10 Mapping Algorithms onto Architectures How an algorithm is mapped onto the chosen architecture will affect the throughput (how many FFTs per second) and the latency (the delay between input and output) of that algorithm. This chapter explains how to map FFT algorithms onto single and multiprocessor architectures to attain either maximum throughput or minimum latency performance.

1.2.11 Board Decisions and Selection

A commercial, off-the-shelf (COTS) board can reduce the time and cost of getting to market with a board-level FFT product. With several dozen manufacturers selling a wide variety of DSP boards suitable for doing FFTs, board selection is a complex decision. Whether the chip selection process has narrowed the choice to a chip or to multiple acceptable chips, the following five areas cover the main issues of choosing or developing a board:

1. Algorithm performance

2. I/O Performance

3. Architecture

4. Software support

5. Expansion capability

1.2.12 Test Signals and Procedures

The design process can bog down in algorithm development and conversion to code if there are no easy ways to detect and isolate errors. Having an efficient set of test signals to use as inputs to an FFT algorithm or its code allows quick detection and precise isolation of errors. In combination with these signals, flow graphs of the algorithm and code are needed to trace an error back to its source. The same signals can be used to do end-product and built-in testing.

1.3 TYPES OF EXAMPLES

The extensive use of examples is one of the unique features of the book. In addition to the four design examples in Chapter 17, six kinds of algorithm examples are used to demonstrate the wide array of concepts and facts the book contains. The particular lengths were chosen because they are large enough to show the pattern of an algorithm yet small enough to easily follow.

1.3.1 Eight-Point DFT to FFT Example

Section 3.3 explains that all of the FFT algorithms presented in this book are based on ways to remove redundant computations from the DFT equations without changing the final result of the equations. While deriving an ITT algorithm from its DFT origins is a theoretical process, using an example is a practical way of seeing the principle.

1.3.2 Algorithm Steps and Memory Maps

Sections 8.3 through 8.10 contain 17 examples of building-block algorithms that are most likely to be used to construct larger algorithms. These are the most efficient smallpoint transforms to implement. For each example every arithmetic operation (Algorithm Step) is given, with a memory address (Memory Map) beside it, for the results. Instructions are given for converting these small-point transforms into code. This coding can be in any of the chip vendors' assembly languages or in a high-level language. To convert to assembly language, both the Algorithm Steps and their companion Memory Map will be needed. Conversion to high-level languages, such as versions of C or FORTRAN, only require use of the Algorithms Steps.

1.3.3 Fifteen-Point or 16-Point FFT Algorithm Examples

In Chapter 9 seven 15-point or 16-point FFT algorithm examples, using the building blocks from Chapter 8, show how to implement the general types of FFT algorithms. A technique for relabeling Memory Maps from Chapter 8 is given and illustrated in these examples. Power-of-two and non-power-of-two examples are used to illustrate the range of algorithms that cover computing any transform length.

1.3.4 Sixteen-Point Radix-4 FFT Algorithm Examples

In Chapter 12 a 16-point, radix-4 FFT algorithm is used in one single-processor and nine multiprocessor examples. Maximum throughput and minimum latency examples are done for mapping the algorithm and its data, for a total of 20 examples. A 16-point example is used because it is a typical power-of-two length and familiar from Chapter 9. The reader is given all the input, intermediate, and output steps needed to code the algorithm.

1.3.5 Four-Point FFT and 16-Point Radix-4 FFT Algorithm Examples

In Chapter 16 the 4-point FFT (a small-point building-block algorithm in Chapter 8) and 16-point, radix-4 FFT examples are used again to explain how to detect and isolate errors in FFT algorithm development, code development and debugging, and end-product operation. Flow graphs are used to show how to track an error through an algorithm. Equations show how to verify Algorithm Step accuracy. Algorithm Steps and Memory Maps are used with test signals to show how the results are altered by an error in an algorithm. The altered results illustrate how to isolate a detected error.

1.4 DESIGN EXAMPLES

In Chapter 17, frequency analysis, power spectrum estimation, linear filtering, and two-dimensional processing examples were chosen to illustrate:

Three common uses of the DFT from Chapter 2

Single and multiprocessor architectures from Chapter 11

Three algorithms from Chapter 9

Three classes of chips (fixed-point, floating-point, and FFT-specific) from Chapter 14

Whether the design will be single or multiple chip on single or multiple boards may not be determined until far into the design process. In this chapter both multiple-chip and multiple-board applications are developed to illustrate making those decisions. These are not intended to be full-scale product designs. They are taken far enough into a design to show how to use the wide array of information in the book.

1.4.1 Doppler Radar

Example 1 is the Doppler processing portion of a ground-based air surveillance radar. This can be used for commercial airport air traffic control or for Doppler weather radar, as well as defense applications. Doppler weather radar has become a household word in the 1990s, through its use in daily weather forecasting and broadcasts. Doppler processing is a classical use of frequency analysis, the first common use of the DFT.

1.4.2 Power Spectrum Estimator

Example 2 is a power spectrum estimator personal computer (PC) plug-in board. Commonly used to modify PCs for use as sophisticated instrumentation, plug-in boards generate hundreds of millions of dollars of business. Earthquake prediction, satellite communication, and magnetic fields are areas of intense public interest, where the signals a board like this can analyze are found. There are countless other applications where recognizing signals and the patterns in them can have a life-saving effect. This is the third common use of DFTs-frequency domain conversion.

1.4.3 Speech Recognition

Example 3 is the signal processing portion of a voice-activated number recognition system. Voice dialing of car phones, one of many products for the burgeoning consumer electronics market, is a use for this. This technique can also be applied to other numerical data entry situations, where hands are not free to use a keypad; speaker verification for security systems; and credit card fraud protection. This speech application taps DFT's ability to provide a numerical shorthand of a signal, its second common use, and its use for frequency analysis.

1.4.4 Image Deblurring

Example 4 is another PC plug-in board, this one for doing image deblurring. The PC housing this board could be found at a police station, crime lab, or as instrumentation for an engineer or researcher. Though deblurring images does not have the widespread uses of the first three examples, the image processing principles it employs do. Some of them are CAT scans and MRIs, seismic exploration, and multimedia applications. Like Example 2, this product does frequency domain conversion, the third common use of the DFT.

1.5 CONCLUSIONS

This chapter provides an overview of the contents of the book. From a foundation in the DFT through design examples, the authors have tried to present a logical, easy to follow explanation of how to implement real-time FFTs on commercially available processors. Digital signal processing is a mushrooming field of technology. The FFT is a valuable technique for synthesizing, recognizing, enhancing, compressing, modifying, or analyzing digital signals from many sources.

The next chapter, on the DFT, lays the foundation for all that is said about the FFT in subsequent chapters.

(Continues...)

---

Excerpted from Handbook of Real-Time Fast Fourier Transforms by Winthrop W. Smith Excerpted by permission.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

---

Table of Contents

Preface.

Overview.

The Discrete Fourier Transform.

The Fast Fourier Transform.

Weighting Functions.

Frequency Analysis.

Linear Filtering and Pattern Matching.

Multidimentional Processing.

Building-Block Algorithms.

Algorithm Construction.

Arithmetic Building Blocks for Architectures.

Multiprocessor Architectures.

Algorithm and Data Mappings.

Arithmetic Formats.

Chips.

Board Decisions and Selection.

Test.

Design Examples.

Glossary.

Appendix: Table of Comparison Matrices.

Index.