Title Page
Copyright Page
Contents
List of Figures
List of Tables
Preface
Acknowledgments.
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.1.1 Divisibility, greatest common divisor GCD and Euclid's algorithm
Definition 1
Properties of divisibility
Theorem 1
Definition 2
Theorem 2 Fundamental Theorem of Arithmetic
Definition 3
Properties of GCD
Euclid's algorithm:
Example 1
Solution.
Definition 4
Properties of LCM
2.1.2 Congruence and Chinese remainder theorem
Definition 5
Properties of congruence
Definition 6
Definition 7
Definition 8 Euler's totient function
Properties of the Euler's totient function
Theorem 3
Theorem 4
Theorem 5 Chinese Remainder Theorem CRT
Proof.
Example 2
Solution.
2.1.3 Euler's theorem and primitive roots
Theorem 6 Euler's Theorem
Fermat's theorem:
Definition 9
Theorem 7 Primitive Root Theorem
Theorem 8
2.2 BASIC POLYNOMIAL THEORY
Definition 10
2.2.1 Divisibility, GCD and Euclid's algorithm
Theorem 9
Example 3
Solution.
Definition 11
Properties of polynomial divisibility
Definition 12
Properties of GCD
Euclid's algorithm:
Example 4
Solution.
Theorem 10
Definition 13
Definition 14
Theorem 11
2.2.2 Congruence and CRT
Definition 15
Properties of polynomial congruence
Example 5
Theorem 12 Chinese Remainder Theorem
Example 6
Solution.
Example 7
Solution.
2.3 1D POLYNOMIAL TRANSFORM
2.3.1 Definition
Definition 16
2.3.2 Formation of polynomial transform
Theorem 13
Proof.
Theorem 14
Theorem 15
Proof.
Example 8
Theorem 16
Example 9
2.3.3 Properties of polynomial transform
? Linearity
? Symmetries
? Shift property
? Convolutional property
Proof.
? Parseval property
2.4 FAST POLYNOMIAL TRANSFORM
2.4.1 Radix-2 fast polynomial transform
Algorithm 1
Step 1.
Step 2.
2.4.2 Radix-Γ° fast polynomial transform
Example 10
Algorithm 2
Step 1.
Step 2.
2.5 MD POLYNOMIAL TRANSFORM AND FAST ALGORITHM
2.5.1 MD polynomial transform
Definition 17
Example 11
2.5.2 Fast algorithm for MD polynomial transform
Example 12
2.6 CHAPTER SUMMARY
REFERENCES
3 Fast Fourier Transform Algorithms
3.1 INTRODUCTION
3.2 RADIX-2 AND SPLIT-RADIX ALGORITHMS
3.2.1 Radix-2 algorithm
Index reordering
Butterfly operation
Twiddle factor
3.2.2 Split-radix algorithm
3.2.3 Discussions
Recursion and regularity
Computational complexity
Computational structure
Memory consumption
Sequence lengths
3.3 GENERALIZED SPLIT-RADIX ALGORITHM
3.3.1 Decimation-in-frequency algorithm
3.3.2 Decimation-in-time algorithm
3.3.3 Computational complexity
Complex input sequence
Real input sequence
Comparison
3.4 PRIME FACTOR ALGORITHMS
3.4.1 Algorithm
Step 1.
Step 2.
Step 3.
3.4.2 Computational complexity
3.5 GENERALIZED 2D SPLIT-RADIX ALGORITHMS
3.5.1 Algorithm
3.5.2 Computational complexity
3.6 FAST ALGORITHMS FOR GENERALIZED DFT
3.6.1 Algorithm
Generalized DFT
Odd-squared DFT
Odd-time DFT
Odd-frequency DFT
Real-valued GDFT
3.6.2 Computational complexity
Generalized DFT
Odd-squared DFT
Odd-time and odd-frequency DFT
3.7 POLYNOMIAL TRANSFORM ALGORITHMS FOR MD DFT
3.7.1 Polynomial transform algorithm for 2D DFT
Lemma 1
Proof.
Algorithm 3
Step 1.
Step 2.
Step 3.
Step 4.
3.7.2 Polynomial transform algorithm for MD DFT
Lemma 2
Proof.
Lemma 3
Proof.
Algorithm 4
Step 1.
Step 2.
Step 3.
Step 4.
3.7.3 Computational complexity
3.8 CHAPTER SUMMARY
Appendix A. length 9 DFT computation
Appendix B. length 15 DFT computation
Appendix C. length 5 DFT computation
REFERENCES
4 Fast Algorithms for 1D Discrete Hartley Transform
4.1 INTRODUCTION
4.2 SPLIT-RADIX ALGORITHMS
4.2.1 Split-radix 2/4 algorithm
4.2.2 Split-radix 3/9 algorithm
4.3 GENERALIZED SPLIT-RADIX ALGORITHMS
4.3.1 Algorithm
4.3.2 Computational complexity
4.3.3 Comparison
4.4 RADIX-2 ALGORITHMS FOR TYPE-II, -III AND -IV DHTS
4.4.1 Algorithm for type-II DHT
4.4.2 Algorithm for type-III DHT
4.4.3 Algorithm for type-IV DHT
4.5 PRIME FACTOR ALGORITHMS
4.5.1 Algorithm for type-I DHT
4.5.2 Algorithm for type-II DHT
4.5.3 Algorithm for type-III DHT
4.5.4 Index mapping for type-II and -III DHTs
4.5.5 Computational complexity for type-II and -III DHTs
4.6 RADIX-q ALGORITHMS
4.6.1 Algorithm for type-II DHT
4.6.2 Algorithm for type-III DHT
4.6.3 Algorithm for type-IV DHT
4.6.4 Computational complexity
Computation for N = 3m
Computation for N = 5m
Comparison
4.7 FAST ALGORITHMS USING TYPE-I DHT
4.7.1 Algorithm for type-II DHT
4.7.2 Algorithm for type-III DHT
4.7.3 Algorithm for type-IV DHT
4.8 CHAPTER SUMMARY
Appendix A. Computation of odd indexed outputs
Appendix B. Subroutines for split-radix DHT algorithm
Appendix C. Computation of Cn, k and Sn, k
Appendix D. length 9 DHT computation
Appendix E. length 15 DHT computation
Appendix F. Proof
Appendix G. Proof
Appendix H. Derivation of type-III DCT
Example:
Appendix I. Derivation of type-II DCT
REFERENCES
5 Fast Algorithms for MD Discrete Hartley Transform
5.1 INTRODUCTION
5.2 SPLIT-RADIX ALGORITHMS FOR 2D TYPE-I DHT
5.2.1 Decimation-in-frequency algorithm
Even-even decomposition
Even-odd decomposition
Odd-even decomposition
Odd-odd decomposition
5.2.2 Computational complexity
5.2.3 Decimation-in-time algorithm
5.2.4 Computational complexity
5.3 FAST ALGORITHMS FOR 2D TYPE-II, -III AND -IV DHTs
5.3.1 Algorithm for type-II DHT
The type-II even-odd decomposition
The type-II odd-even decomposition
5.3.2 Algorithm for type-III DHT
5.3.3 Algorithm for type-IV DHT
5.3.4 Computational complexity
5.4 FAST ALGORITHMS BASED ON TYPE-I DHT
5.4.1 Algorithm for 2D type-II DHT
5.4.2 Algorithm for 2D type-III DHT
5.4.3 Algorithm for 2D type-IV DHT
5.4.4 Algorithm for 3D type-II DHT
5.4.5 Discussion
5.5 PT-BASED RADIX-2 ALGORITHM FOR MD TYPE-I DHT
5.5.1 Algorithm
Lemma 4
Proof.
Algorithm 5
Step 1.
Step 2.
Step 3.
Step 4.
5.5.2 Computational complexity
5.6 PT-BASED RADIX-2 ALGORITHM FOR MD TYPE-II DHT
5.6.1 Algorithm
Lemma 5
Proof.
Algorithm 6
Step 1.
Step 2.
Step 3.
5.6.2 Computational complexity
5.6.3 PT-based radix-2 algorithm for MD type-III DHT
Algorithm 7
Step 1.
Step 2.
Step 3.
5.7 PT-BASED RADIX-q ALGORITHM FOR MD TYPE-I DHT
5.7.1 Algorithm
Algorithm 8
Step 1.
Step 2.
Step 3.
Step 4.
5.7.2 Computation of reduced type-I DHT
Algorithm 9
Step 1.
Step 2.
Step 3.
Step 4.
5.7.3 Computational complexity
5.8 PT-BASED RADIX-q ALGORITHM FOR MD TYPE-II DHT
5.8.1 PT-based radix-q algorithm for 2D type-II DHT
Lemma 6
Lemma 7
Proof.
Algorithm 10
Step 1.
Step 2.
Step 3.
Step 4.
5.8.2 Radix-q algorithm for reduced type-II DHT
Algorithm 11
Step 1.
Step 2.
Step 3.
Step 4.
5.8.3 Cyclic convolution algorithm for reduced type-II DHT
Lemma 8
Proof.
Algorithm 12
Step 1.
Step 2.
Step 3.
5.8.4 PT-based radix-q algorithm for MD type-II DHT
Algorithm 13
Step 1.
Step 2.
Step 3.
Step 4.
5.8.5 Computational complexity
5.9 CHAPTER SUMMARY
REFERENCES
6 Fast Algorithms for 1D Discrete Cosine Transform
6.1 INTRODUCTION
6.2 RADIX-2 ALGORITHMS
6.2.1 Algorithm for type-II DCT
6.2.2 Algorithm for type-III DCT
6.2.3 Algorithm for type-IV DCT
6.2.4 Computational complexity
6.3 PRIME FACTOR ALGORITHMS
6.3.1 Algorithm for type-II DCT
6.3.2 Index mapping
Step 1.
Step 2.
Step 3.
6.3.3 Algorithm for type-III DCT
6.3.4 Computational complexity
6.4 RADIX-q ALGORITHMS
6.4.1 Radix-q algorithm for type-II DCT
6.4.2 Radix-q algorithm for type-III DCT
6.4.3 Computational complexity
6.4.4 Algorithm for composite sequence lengths
Step 1.
Step 2.
Step 3.
6.5 FAST ALGORITHMS BASED ON TYPE-I DCT
6.5.1 Algorithm for type-I DCT
6.5.2 Algorithm for type-I DST
6.5.3 Algorithm for type-II DCT
6.5.4 Algorithm for type-III DCT
6.5.5 Algorithm for type-IV DCT
6.6 CHAPTER SUMMARY
Appendix A. Subroutine for index mapping
Appendix B. Subroutine for length 9 DCT
Appendix C. Subroutine for length 5 DCT
Appendix D. Radix-q algorithm when q =9
Appendix E. Growth rate of computational complexity
Appendix F. Mapping process
REFERENCES
7 Fast Algorithms for MD Discrete Cosine Transform
7.1 INTRODUCTION
7.2 ALGORITHMS FOR 2D TYPE-I -II AND -III DCTs
7.2.1 Algorithm for 2D type-II DCT
7.2.2 Algorithm for type-III DCT
7.2.3 Algorithm for 2D type-I DCT
7.2.4 Algorithm for type-I cosine-sine array
7.2.5 Algorithm for type-I-II cosine-cosine array
7.2.6 Algorithm for type-I-II sine-cosine array
7.2.7 Implementation issues
7.2.8 Discussion
7.3 PRIME FACTOR ALGORITHM FOR MD DCT
7.3.1 Algorithm for type-II DCT
7.3.2 Algorithm for type-III DCT
7.3.3 Input/output index mapping
7.3.4 Discussions
7.4 PT-BASED RADIX-2 ALGORITHM FOR MD TYPE-II DCT
7.4.1 PT-based radix-2 algorithm for 2D type-II DCT
Lemma 9
Proof.
Algorithm 14
Step 1.
Step 2.
Step 3.
7.4.2 Fast polynomial transform
Lemma 10
Proof.
7.4.3 Computational complexity
7.4.4 PT-based radix-2 algorithm for MD type-II DCT
Algorithm 15
Step 1.
Step 2.
Step 3.
7.5 PT-BASED RADIX-2 ALGORITHM FOR MD TYPE-III DCT
7.5.1 PT-based radix-2 algorithm for 2D type-III DCT
Lemma 11
Proof.
Algorithm 16
Step 1.
Step 2.
Step 3.
7.5.2 Fast polynomial transform
Lemma 12
Proof.
7.5.3 Computational complexity
7.5.4 PT-based radix-2 algorithm for MD type-III DCT
Algorithm 17
Step 1.
Step 2.
7.6 PT-BASED RADIX-q ALGORITHM FOR MD TYPE-II DCT
7.6.1 PT-based radix-q algorithm for 2D type-II DCT
Lemma 13
Proof.
Algorithm 18
Step 1.
Step 2.
Step 3.
Step 4.
Step 5.
7.6.2 Fast polynomial transform
Lemma 14
Proof.
7.6.3 Radix-q algorithm for reduced type-II DCT
Step 1.
Step 2.
Step 3.
Step 4.
Step 5.
Algorithm for q = 3
Step 1.
Step 2.
Step 3.
Algorithm for q = 5
7.6.4 PT-based radix-q algorithm for rD type-II DCT
Algorithm 19
Step 1.
Step 2.
Step 3.
Step 4.
Step 5.
7.6.5 Computational complexity
7.7 PT-BASED RADIX-q ALGORITHM FOR MD TYPE-III DCT
7.7.1 PT-based radix-q algorithm for 2D type-III DCT
Lemma 15
Proof.
Algorithm 20
Step 1.
Step 2.
Step 3.
Step 4.
Step 5.
Example 13
Step 1.
Step 2.
Step 3.
Step 4.
Step 5.
7.7.2 Fast polynomial transform
Lemma 16
Proof.
7.7.3 PT-based radix-q algorithm for rD type-III DCT
Algorithm 21
Step 1.
Step 2.
Step 3.
Step 4.
7.7.4 Computational complexity
7.8 CHAPTER SUMMARY
Appendix A. Computational complexity
Appendix B. Subroutine for PFA of type-II 2D DCT
REFERENCES
8 Integer Transforms and Fast Algorithms
8.1 INTRODUCTION
8.2 PRELIMINARIES
Definition 18
Definition 19
Definition 20
Lemma 17
Proof.
Example 14
Proof.
Theorem 18
8.3 INTEGER DCT AND FAST ALGORITHMS
8.3.1 Lifting factorization of type-IV DCT
Lemma 18
Example 15
8.3.2 Integer type-IV DCT and fast algorithm
Algorithm 22
Step 1.
Step 2.
Step 3.
Algorithm 23
Step 1.
Step 2.
Step 3.
8.3.3 Integer-to-integer transform
Algorithm 24
Step 1.
Step 2.
Step 3.
8.3.4 Integer type-II and -III DCTs
Lifting factorization of type-II DCT
Lemma 19
Example 16
Definition 22
Algorithm 25
Step 1.
Step 2.
Lifting factorization of the type-III OCT
Lemma 20
Definition 23
Algorithm 26
Step 1.
Step 2.
8.3.5 Approximation performance
8.3.6 Improvements on the short-length transforms
Figure 8.7 Outputs of type-IV OCT and IntDCT-IV N = 128, signal 2, normalized.
8.3.7 Comparison between DCT and IntDCTIII-DCT
8.4 INTEGER DHT AND FAST ALGORITHMS
8.4.1 Factorization of type-IV DHT
Lemma 21
Example 17
8.4.2 Integer type-IV DHT and fast algorithm
Definition 24
Algorithm 27
Step 1.
Step 2.
Step 3.
Algorithm 28
Step 1.
Step 2.
Step 3.
8.4.3 Integer-to-integer type-IV DHT
Algorithm 29
Step 1.
Step 2.
Step 3.
8.4.4 Other types of integer DHTs
Integer type-II DHT
Lemma 22
Definition 25
Algorithm 30
Step 1.
Step 2.
Integer type-III DHT
Lemma 23
Example 18
Definition 26
Algorithm 31
Step 1.
Step 2.
Integer type-I DHT
Lemma 24
Example 19
Definition 27
Algorithm 32
Step 1.
Step 2.
8.4.5 Performance comparison
8.5 MD INTEGER DCT AND FAST ALGORITHMS
8.5.1 Row-column MD type-II integer DCT
Definition 28
8.5.2 PT-based 2D Integer DCT-II
Definition 29
Step 1.
Step 2.
Step 3.
Step 4.
8.5.3 Comparison
8.5.4 Reconstruction algorithm for 2D IntDCT-II
Algorithm 33
Step 1.
Step 2.
Step 3.
Step 4.
8.6 MD INTEGER DHT AND FAST ALGORITHMS
8.6.1 Row-column MD integer DHT
Definition 30
8.6.2 PT-based MD type-II integer DHT
Definition 31
Step 1.
Step 2.
Step 3.
Step 4.
8.6.3 Inverse MD integer DHT
Algorithm 34
Step 1.
Step 2.
Step 3.
Step 4.
8.7 CHAPTER SUMMARY
REFERENCES
9 New Methods of Time-Frequency Analysis
9.1 INTRODUCTION
Short-time Fourier transform
Spectrogram and scalogram
Wigner distribution and ambiguity function
Cohen and affine classes
9.2 PRELIMINARIES
9.2.1 Basic concepts
Marginal conditions
Total energy
Time and frequency shift invariance
Linear scaling
9.2.2 STFT
Examples
9.2.3 WD
9.2.4 Fractional Fourier transform
9.3 HARMONIC TRANSFORM
9.3.1 Description of HT
Definition
Properties
9.3.2 Discrete calculation
Harmonic transform
Inverse harmonic transform
9.3.3 Discrete harmonic transform
Definition
ProofofDHT
9.3.4 Examples of using the DHT
Synthetic signals
Speech signals
STHT
Step 1.
Step 2.
Step 3.
Step 4.
Step 5.
9.4 TOMOGRAPHIC TIME-FREQUENCY TRANSFORM
9.4.1 Computed tomography
Fourier slice theorem
Filtered backprojection algorithm
9.4.2 Tomographic time-frequency transform
FRFT
9.4.3 Interference suppression
Examples
9.5 CHAPTER SUMMARY
REFERENCES
Index