Signal Processing and Digital Filtering – serie

Fourier transforms of large multidimensional data sets arise in many fields --ranging from seismology to medical imaging. The rapidly increasing power of computer chips, the increased availability of vector and array processors, and the increasing size of the data sets to be analyzed make it both possible and necessary to analyze the data more than one dimension at a time. The increased freedom provided by multidimensional processing, however, also places intesive demands on the communication aspects of the computation, making it difficult to write code that takes all the algorithmic possiblities into account and matches these to the target architecture. This book develops algorithms for multi-dimensional Fourier transforms that yield highly efficient code on a variety of vector and parallel computers. By emphasizing the unified basis for the many approaches to one-dimensional and multidimensional Fourier transforms, this book not only clarifies the fundamental similarities, but also shows how to exploit the differences in optimizing implementations.This book will be of interest not only to applied mathematicians and computer scientists, but also to seismologists, high-energy physicists, crystallographers, and electrical engineers working on signal and image processing. Topics covered include: tensor products and the fast Fourier transform; finite Abelian groups and their Fourier transforms; Cooley- Tukey and Good-Thomas algorithms; lines and planes; reduced transform algorithms; field algorithms; implementation on Risc and parallel

This book is based on several courses taught during the years 1985-1989 at the City College of the City University of New York and at Fudan Univer­ sity, Shanghai, China, in the summer of 1986. It was originally our intention to present to a mixed audience of electrical engineers, mathematicians and computer scientists at the graduate level a collection of algorithms that would serve to represent the vast array of algorithms designed over the last twenty years for computing the finite Fourier transform (FFT) and finite convolution. However, it was soon apparent that the scope of the course had to be greatly expanded. For researchers interested in the design of new algorithms, a deeper understanding of the basic mathematical concepts underlying algorithm design was essential. At the same time, a large gap remained between the statement of an algorithm and the implementation of the algorithm. The main goal of this text is to describe tools that can serve both of these needs. In fact, it is our belief that certain mathematical ideas provide a natural language and culture for understanding, unifying and implementing a wide range of digital signal processing (DSP) algo­ rithms. This belief is reinforced by the complex and time-consuming effort required to write code for recently available parallel and vector machines. A significant part of this text is devoted to establishing rules and procedures that reduce and at times automate this task.

This book is based on several courses taught during the years 1985-1989 at the City College of the City University of New York and at Fudan Univer­ sity, Shanghai, China, in the summer of 1986. It was originally our intention to present to a mixed audience of electrical engineers, mathematicians and computer scientists at the graduate level a collection of algorithms that would serve to represent the vast array of algorithms designed over the last twenty years for computing the finite Fourier transform (FFT) and finite convolution. However, it was soon apparent that the scope of the course had to be greatly expanded. For researchers interested in the design of new algorithms, a deeper understanding of the basic mathematical concepts underlying algorithm design was essential. At the same time, a large gap remained between the statement of an algorithm and the implementation of the algorithm. The main goal of this text is to describe tools that can serve both of these needs. In fact, it is our belief that certain mathematical ideas provide a natural language and culture for understanding, unifying and implementing a wide range of digital signal processing (DSP) algo­ rithms. This belief is reinforced by the complex and time-consuming effort required to write code for recently available parallel and vector machines. A significant part of this text is devoted to establishing rules and procedures that reduce and at times automate this task.

Fourier transforms of large multidimensional data sets arise in many fields --ranging from seismology to medical imaging. The rapidly increasing power of computer chips, the increased availability of vector and array processors, and the increasing size of the data sets to be analyzed make it both possible and necessary to analyze the data more than one dimension at a time. The increased freedom provided by multidimensional processing, however, also places intesive demands on the communication aspects of the computation, making it difficult to write code that takes all the algorithmic possiblities into account and matches these to the target architecture. This book develops algorithms for multi-dimensional Fourier transforms that yield highly efficient code on a variety of vector and parallel computers. By emphasizing the unified basis for the many approaches to one-dimensional and multidimensional Fourier transforms, this book not only clarifies the fundamental similarities, but also shows how to exploit the differences in optimizing implementations. This book will be of interest not only to applied mathematicians and computer scientists, but also to seismologists, high-energy physicists, crystallographers, and electrical engineers working on signal and image processing. Topics covered include: tensor products and the fast Fourier transform; finite Abelian groups and their Fourier transforms; Cooley- Tukey and Good-Thomas algorithms; lines and planes; reduced transform algorithms; field algorithms; implementation on Risc and parallel

Algorithms for computation are a central part of both digital signal pro­ cessing and decoders for error-control codes and the central algorithms of the two subjects share many similarities. Each subject makes extensive use of the discrete Fourier transform, of convolutions, and of algorithms for the inversion of Toeplitz systems of equations. Digital signal processing is now an established subject in its own right; it no longer needs to be viewed as a digitized version of analog signal process­ ing. Algebraic structures are becoming more important to its development. Many of the techniques of digital signal processing are valid in any algebraic field, although in most cases at least part of the problem will naturally lie either in the real field or the complex field because that is where the data originate. In other cases the choice of field for computations may be up to the algorithm designer, who usually chooses the real field or the complex field because of familiarity with it or because it is suitable for the particular application. Still, it is appropriate to catalog the many algebraic fields in a way that is accessible to students of digital signal processing, in hopes of stimulating new applications to engineering tasks.

This book is dedicated to electrical and mechanical engineers involved with the design of magnetic devices for motion con­ trol and other instrumentation that uses magnetic principles and technology. It can be of benefit to graduate and postgrad­ uate students to gain experience with electro-magnetic princi­ ples and also with different aspects of magnetic coupling mech­ anisms and magnetic circuitry analysis for the design of devices such as electrical servo motors, tachogenerators, encoders, gyro­ magnetic suspension systems, electro-magnetic strip lines, and other electro-magnetic instruments. The rapidly growing areas of production automation, robotics, precise micro-electronics, and pilot navigation place demands on motion control technology in terms of accuracy, reliability, cost effectiveness, and miniaturization. New ferromagnetic materials having quasi-linear and non-linear high-squareness characteris­ tics as well as high-energy permanent magnets, fine lithography, and high-t.emperature superconductivit.y (t.o be expected com­ mercially) motivate the implementation of new motion control components that exploit these new materials and technologies. This book presents classical miniature electrical machine de­ signs as well as several modifications in the geometry of mag­ netic couplings which lead to new motor and encoder design methodologies and other motion control devices such as new coil deposition patterns for incremental and absolute encoders, free spherical gyro suspension in a traveling magnetic field for navigation instrumentation, and magnetic strip lines in combi­ nation with resistive and capacitive media to generate a variety of low-noise LC filters and other signal processing devices.

Convolution is the most important operation that describes the behavior of a linear time-invariant dynamical system. Deconvolution is the unraveling of convolution. It is the inverse problem of generating the system's input from knowledge about the system's output and dynamics. Deconvolution requires a careful balancing of bandwidth and signal-to-noise ratio effects. Maximum-likelihood deconvolution (MLD) is a design procedure that handles both effects. It draws upon ideas from Maximum Likelihood, when unknown parameters are random. It leads to linear and nonlinear signal processors that provide high-resolution estimates of a system's input. All aspects of MLD are described, from first principles in this book. The purpose of this volume is to explain MLD as simply as possible. To do this, the entire theory of MLD is presented in terms of a convolutional signal generating model and some relatively simple ideas from optimization theory. Earlier approaches to MLD, which are couched in the language of state-variable models and estimation theory, are unnecessary to understand the essence of MLD. MLD is a model-based signal processing procedure, because it is based on a signal model, namely the convolutional model. The book focuses on three aspects of MLD: (1) specification of a probability model for the system's measured output; (2) determination of an appropriate likelihood function; and (3) maximization of that likelihood function. Many practical algorithms are obtained. Computational aspects of MLD are described in great detail. Extensive simulations are provided, including real data applications.

This book is intended as an introduction to array signal process­ ing, where the principal objectives are to make use of the available multiple sensor information in an efficient manner to detect and possi­ bly estimate the signals and their parameters present in the scene. The advantages of using an array in place of a single receiver have extended its applicability into many fields including radar, sonar, com­ munications, astronomy, seismology and ultrasonics. The primary emphasis here is to focus on the detection problem and the estimation problem from a signal processing viewpoint. Most of the contents are derived from readily available sources in the literature, although a cer­ tain amount of original material has been included. This book can be used both as a graduate textbook and as a reference book for engineers and researchers. The material presented here can be readily understood by readers having a back­ ground in basic probability theory and stochastic processes. A prelim­ inary course in detection and estimation theory, though not essential, may make the reading easy. In fact this book can be used in a one semester course following probability theory and stochastic processes.

Radar, like most well developed areas, has its own vocabulary. Words like Doppler frequency, pulse compression, mismatched filter, carrier frequency, in-phase, and quadrature have specific meaning to the radar engineer. In fact, the word radar is actually an acronym for RAdio Detection And Rang­ ing. Even though these words are well defined, they can act as road blocks which keep people without a radar background from utilizing the large amount of data, literature, and expertise within the radar community. This is unfortunate because the use of digital radar processing techniques has made possible the analysis of radar signals on many general purpose digi­ tal computers. Of special interest are the surface mapping radars, such as the Seasat and the shuttle imaging radars, which utilize a technique known as synthetic aperture radar (SAR) to create high resolution images (pic­ tures). This data appeals to cartographers, agronomists, oceanographers, and others who want to perform image enhancement, parameter estima­ tion, pattern recognition, and other information extraction techniques on the radar imagery. The first chapter presents the basics of radar processing: techniques for calculating range (distance) by measuring round trip propagation times for radar pulses. This is the same technique that sightseers use when calculat­ ing the width of a canyon by timing the round trip delay using echoes. In fact, the corresponding approach in radar is usually called the pulse echo technique.

This book is intended to be a comprehensive reference to multiplicative com­ plexity theory as applied to digital signal processing computations. Although a few algorithms are included to illustrate the theory, I concentrated more on the develop­ ment of the theory itself. Howie Johnson's infectious enthusiasm for designing efficient DfT algorithms got me interested in this subject. I am grateful to Prof. Sid Burrus for encouraging and supporting me in this effort. I would also like to thank Henrik Sorensen and Doug Jones for many stimulating discussions. lowe a great debt to Shmuel Winograd, who, almost singlehandedly, provided most of the key theoretical results that led to this present work. His monograph, Arithmetic Complexity o/Computations, introduced me to the mechanism behind the proofs of theorems in multiplicative complexity. enabling me to return to his earlier papers and appreciate the elegance of his methods for deriving the theory. The second key work that influenced me was the paper by Louis Auslander and Winograd on multiplicative complexity of semilinear systems defined by polynomials. After reading this paper, it was clear to me that this theory could be applied to many impor­ tant computational problems. These influences can be easily discerned in the present work.