Algorithms for programmers

Скачать в pdf «Algorithms for programmers»



Algorithms for programmers


ideas and source code


Jorg Arndt

arndt@jjj.de


This document1 was LTEX’d at September 26, 2002

Contents


Some important remarks about this document    6


List of    important symbols    7


1    The    Fourier transform    8


1.1    The discrete Fourier transform…………………………… 8


1.2    Symmetries of the Fourier transform………………………… 9


1.3    Radix 2 FFT algorithms………………………………. 10


1.3.1    A little bit of notation……………………………. 10


1.3.2    Decimation in time (DIT) FFT……………………….. 10


1.3.3    Decimation in frequency (DIF) FFT…………………….. 13


1.4    Saving trigonometric computations…………………………. 15


1.4.1    Using lookup tables …………………………….. 16


1.4.2    Recursive generation of the sin/cos-values………………….. 16


1.4.3    Using higher radix algorithms………………………… 17


1.5    Higher    radix DIT and DIF algorithms……………………….. 17


1.5.1    More notation ……………………………….. 17


1.5.2    Decimation in time……………………………… 17


1.5.3    Decimation in frequency…………………………… 18


1.5.4    Implementation of radix r = px DIF/DIT FFTs……………….. 19


1.6    Split radix Fourier transforms (SRFT)……………………….. 22


1.7    Inverse FFT for free ………………………………… 23


1.8    Real valued Fourier transforms …………………………… 24


1.8.1    Real valued FT via wrapper routines…………………….. 25


1.8.2    Real valued split radix Fourier transforms………………….. 27


1.9    Multidimensional FTs ……………………………….. 31


1.9.1    Definition………………………………….. 31


1.9.2    The row column algorithm …………………………. 31


1.10    The matrix Fourier algorithm (MFA)………………………… 32


1.11    Automatic generation of FFT codes ………………………… 33


2    Convolutions    36


2.1 Definition and computation via FFT………………………… 36

Скачать в pdf «Algorithms for programmers»