Transforms and Fast Algorithms for Signal Analysis and Representations

by Bi, Guoan; Zeng, Yonghong

• ISBN13: 9780817642792
• ISBN10: 081764279X
• Format: Hardcover
• Copyright: 2003-10-01
• Publisher: Birkhauser

Summary

Transforms have diverse applications in digital signal processing and other areas of science, engineering, and technology. Indeed, new transforms are continuously emerging to solve many new or open problems created by technological advances. To improve the implementation of these transforms, fast algorithms have been created and widely used over the last forty years. Although closely related to the discrete Fourier transform, novel fast algorithms for various transforms have to be developed separately in order to minimize computational complexity and implementation costs.This book is a comprehensive presentation of results and recent progress on several commonly used transforms and their fast algorithms. In many cases, additional options are provided for new or improved fast algorithms, some not yet well known in the digital signal processing community. Demonstrated throughout the work is the potential for fast algorithms to meet the demands created by fast computing processors, which may lead to advances in modern applications.Features and Topics:* Systematic presentation of many new fast algorithms for widely used one-dimensional or multi-dimensional transforms such as the discrete Fourier, discrete Hartley, and discrete cosine transforms* Improvements on multi-dimensional integer transforms and fast algorithms important for wireless applications* Comprehensive information on newly created time-frequency transforms to improve resolution of signal representations in the time-frequency domain* Recent theoretical developments on polynomial transform-based algorithms* End-of chapter examples, summaries, and referencesThe work is suitable as a textbook for senior undergraduate and graduate students; it may also be used as a self-study reference for electrical engineers and applied mathematicians working in the fields of electronics, signal, image and speech processing, or digital design and communication.

Table of Contents

List of Figures	ix
List of Tables	xiii
Preface	xvii
Introduction	1	(8)
Discrete linear transforms	1	(2)
Fast algorithms	3	(1)
New transforms	4	(1)
Organization of the book	5	(4)
References	8	(1)
Polynomial Transforms and Their Fast Algorithms	9	(38)
Basic number theory	10	(9)
Basic Polynomial theory	19	(7)
1D polynomial transform	26	(5)
Fast polynomial transform	31	(10)
MD polynomial transform and fast algorithm	41	(2)
Chapter summary	43	(4)
References	44	(3)
Fast Fourier Transform Algorithms	47	(46)
Introduction	47	(2)
Radix-2 and split-radix algorithms	49	(9)
Generalized split-radix algorithm	58	(7)
Prime factor algorithms	65	(5)
Generalized 2D split-radix algorithms	70	(3)
Fast algorithms for generalized DFT	73	(7)
Polynomial transform algorithms for MD DFT	80	(8)
Chapter summary	88	(5)
length 9 DFT computation	89	(1)
length 15 DFT computation	90	(1)
length 5 DFT computation	90	(1)
References	91	(2)
Fast Algorithms for 1D Discrete Hartley Transform	93	(52)
Introduction	93	(2)
Split-radix algorithms	95	(4)
Generalized split-radix algorithms	99	(5)
Radix-2 algorithms for type-II, -III and -IV DHTs	104	(3)
Prime factor algorithms	107	(14)
Radix-q algorithms	121	(10)
Fast algorithms using type-I DHT	131	(2)
Chapter summary	133	(12)
Computation of odd indexed outputs	134	(1)
Subroutines for split-radix DHT algorithm	134	(2)
Computation of C(n, k) and S(n, k)	136	(1)
length 9 DHT computation	137	(1)
length 15 DHT computation	138	(1)
Proof	138	(1)
Proof	139	(1)
Derivation of type-III DCT	139	(2)
Derivation of type-II DCT	141	(1)
References	142	(3)
Fast Algorithms for MD Discrete Hartley Transform	145	(62)
Introduction	146	(1)
Split-radix algorithms for 2D type-I DHT	147	(9)
Fast algorithms for 2D type-II, -III and -IV DHTs	156	(8)
Fast algorithms based on type-I DHT	164	(11)
PT-based radix-2 algorithm for MD type-I DHT	175	(5)
PT-based radix-2 algorithm for MD type-II DHT	180	(6)
PT-based radix-q algorithm for MD type-I DHT	186	(5)
PT-based radix-q algorithm for MD type-II DHT	191	(12)
Chapter summary	203	(4)
References	204	(3)
Fast Algorithms for 1D Discrete Cosine Transform	207	(40)
Introduction	207	(2)
Radix-2 algorithms	209	(3)
Prime factor algorithms	212	(5)
Radix-q algorithms	217	(12)
Fast algorithms based on type-I DCT	229	(9)
Chapter summary	238	(9)
Subroutine for index mapping	239	(1)
Subroutine for length 9 DCT	239	(1)
Subroutine for length 5 DCT	239	(1)
Radix-q algorithm when q =9	240	(1)
Growth rate of computational complexity	240	(1)
Mapping process	241	(3)
References	244	(3)
Fast Algorithms for MD Discrete Cosine Transform	247	(74)
Introduction	247	(2)
Algorithms for 2D type-I, -II and -III DCTs	249	(15)
Prime factor algorithm for MD DCT	264	(7)
PT-based radix-2 algorithm for MD type-II DCT	271	(11)
PT-based radix-2 algorithm for MD type-III DCT	282	(7)
PT-based radix-q algorithm for MD type-II DCT	289	(14)
PT-based radix-q algorithm for MD type-III DCT	303	(12)
Chapter summary	315	(6)
Computational complexity	316	(1)
Subroutine for PFA of type-II 2D DCT	317	(2)
References	319	(2)
Integer Transforms and Fast Algorithms	321	(46)
Introduction	321	(1)
Preliminaries	322	(4)
Integer DCT and fast algorithms	326	(17)
Integer DHT and fast algorithms	343	(12)
MD Integer DCT and fast algorithms	355	(4)
MD Integer DHT and fast algorithms	359	(4)
Chapter summary	363	(4)
References	364	(3)
New Methods of Time-Frequency Analysis	367	(52)
Introduction	367	(3)
Preliminaries	370	(7)
Harmonic transform	377	(20)
Tomographic time-frequency transform	397	(17)
Chapter summary	414	(5)
References	416	(3)
Index	419