Transforms and Fast Algorithms for Signal Analysis and Representations

This book is a comprehensive presentation of recent results and developments on several widely used transforms and their fast algorithms. In many cases, new options are provided for improved or new fast algorithms, some of which are not well known in the digital signal processing community. The book is suitable as a textbook for senior undergraduate and graduate courses in digital signal processing. It may also serve as an excellent self-study reference for electrical engineers and applied mathematicians whose work is related to the fields of electronics, signal processing, image and speech processing, or digital design and communication.

1 Introduction.- 1.1 Discrete linear transforms.- 1.2 Fast algorithms.- 1.3 New transforms.- 1.4 Organization of the book.- References.- 2 Polynomial Transforms and Their Fast Algorithms.- 2.1 Basic number theory.- 2.2 Basic polynomial theory.- 2.3 1D polynomial transform.- 2.4 Fast polynomial transform.- 2.5 MD polynomial transform and fast algorithm.- 2.6 Chapter summary.- References.- 3 Fast Fourier Transform Algorithms.- 3.1 Introduction.- 3.2 Radix-2 and split-radix algorithms.- 3.3 Generalized split-radix algorithm.- 3.4 Prime factor algorithms.- 3.5 Generalized 2D split-radix algorithms.- 3.6 Fast algorithms for generalized DFT.- 3.7 Polynomial transform algorithms for MD DFT.- 3.8 Chapter summary.- 4 Fast Algorithms for 1D Discrete Hartley Transform.- 4.1 Introduction.- 4.2 Split-radix algorithms.- 4.3 Generalized split-radix algorithms.- 4.4 Radix-2 algorithms for type-II, -III and -IV DHTs.- 4.5 Prime factor algorithms.- 4.6 Radix-q algorithms.- 4.7 Fast algorithms using type-I DHT.- 4.8 Chapter summary.- 5 Fast Algorithms for MD Discrete Hartley Transform.- 5.1 Introduction.- 5.2 Split-radix algorithms for 2D type-I DHT.- 5.3 Fast algorithms for 2D type-II, -III and -IV DHTs.- 5.4 Fast algorithms based on type-I DHT.- 5.5 PT-based radix-2 algorithm for MD type-I DHT.- 5.6 PT-based radix-2 algorithm for MD type-II DHT.- 5.7 PT-based radix-q algorithm for MD type-I DHT.- 5.8 PT-based radix-q algorithm for MD type-II DHT.- 5.9 Chapter summary.- References.- 6 Fast Algorithms for 1D Discrete Cosine Transform.- 6.1 Introduction.- 6.2 Radix-2 algorithms.- 6.3 Prime factor algorithms.- 6.4 Radix-q algorithms.- 6.5 Fast algorithms based on type-I bCT.- 6.6 Chapter summary.- 7 Fast Algorithms for MD Discrete Cosine Transform.- 7.1 Introduction.- 7.2 Algorithms for 2Dtype-I, -II and -III DCTs.- 7.3 Prime factor algorithm for MD DCT.- 7.4 PT-based radix-2 algorithm for MD type-II DCT.- 7.5 PT-based radix-2 algorithm for MD type-III DCT.- 7.6 PT-based radix-q algorithm for MD type-II DCT.- 7.7 PT-based radix-q algorithm for MD type-III DCT.- 7.8 Chapter summary.- 8 Integer Transforms and Fast Algorithms.- 8.1 Introduction.- 8.2 Preliminaries.- 8.3 Integer DCT and fast algorithms.- 8.4 Integer DHT and fast algorithms.- 8.5 MD Integer DCT and fast algorithms.- 8.6 MD Integer DHT and fast algorithms.- 8.7 Chapter summary.- References.- 9 New Methods of Time-Frequency Analysis.- 9.1 Introduction.- 9.2 Preliminaries.- 9.3 Harmonic transform.- 9.4 Tomographic time-frequency transform.- 9.5 Chapter summary.- References.