Algorithms for programmers phần 1

Các sản phẩm nhập với dấu hiệu tiêu cực được chỉ báo bằng một trừ đi postfix tại các mục tương ứng. √ Với góc phải chập chưa được thay thế bởi i = -1 có nghĩa là bao bọc xung quanh (tức là h (1)) các thành phần phần tưởng tượng. Đối với các trình duyệt khác, chúng tôi sử dụng | Algorithms for programmers ideas and source code This document is work in progress read the important remarks near the beginning Jorg Arndt arndt@ This document1 was lATgX d at September 26 2002 Tills document is online at http fxt . It will stay available online for free. Contents Some important remarks about this document 6 List of important symbols 7 1 The Fourier transform 8 The discrete Fourier transform. 8 Symmetries of the Fourier transform. 9 Radix 2 FFT algorithms. 10 A little bit of notation. 10 Decimation in time DIT FFT. 10 Decimation in frequency DIF FFT. 13 Saving trigonometric computations. 15 Using lookup tables . 16 Recursive generation of the sin cos-values. 16 Using higher radix algorithms. 17 Higher radix DIT and DIF algorithms. 17 More notation . 17 Decimation in time. 17 Decimation in frequency. 18 Implementation of radix r px DIF DIT FFTs. 19 Split radix Fourier transforms SRFT . 22 Inverse FFT for free . 23 Real valued Fourier transforms . 24 Real valued FT via wrapper routines. 25 Real valued split radix Fourier transforms. 27 Multidimensional FTs . 31 Definition. 31 The row column algorithm . 31 The matrix Fourier algorithm MFA . 32 Automatic generation of FFT codes . 33 1 CONTENTS 2 2 Convolutions 36 Definition and computation via FFT. 36 Mass storage convolution using the MFA. 40 Weighted Fourier transforms . 42 Half cyclic convolution for half the price . 44 Convolution using the MFA. 44 The case R 2. 45 The case R 3. 45 Convolution of real valued data using the MFA. 46 Convolution without transposition using the MFA . 46 The z-transform ZT . 47 Definition of the ZT. 47 Computation of the ZT via convolution. 48 Arbitrary length FFT by ZT. 48 Fractional Fourier transform by ZT. 48 3 The Hartley transform HT 49 Definition .