# Discrete Fourier Transforms and Fast Fourier Transforms

### Discrete Fourier Transforsm & Fast Fourier Transforms

#### Relationship between Discrete Fourier Transform and Continuous Fourier Tranform

 Introduction The Discrete Fourier Transform is a periodic and the inverse of the Disrete Fourier Transform is also periodic.     Considering an non periodic time domain function and its related non-periodic continuous Fourier Tranform.    If the time domain function is sampled a set of discrete values results.    If this data is transformed then a periodic frequency domain function results.    This data is again in discrete form and the inverse transform of this is a periodic function. The notes and figures below provide an illustration of these operations.     The signal corruption resulting from the alias effect and the corruption of waveform resulting from the selection of T0 are very much exagerated.    In practice the Discrete fourier Transforms using high values of N provide very accurate data. Typical Aperiodic Fourier transform. The figure below show a typical aperiodic waveform and its Fourier transform. The physical sampling function is mathematical equivalent to mutliplying the function with a Dirac Comb - IIIT( i ) function . Dirac comb.    This function and its Fourier Transform is shown below. The sampling interval is T and the sampled function results as follows. The graphical result of this product operation in the time domain and the resulting convolution operation in the frequency domain is shown below.     It should be noted the selection of T relates to the alias effect where, in the frequency domain, the adjacent periodic waveforms overlap and signal information is corrupted an lost.    Ideally T should be selected such that at a k value of 1/2T the amplitude is effectively zero. The sampling operation does not involve an infinite number of samples.    It results from taking N samples over a sample period T0 = N.T. This is mathematically equivalent to truncating the samples using a top hat function.    Top hat with a width of T0 and a height 1.     This is also called a pulse function. This operation is mathematically represented as shown below The graphical result of this operations is shown below. It is clear that the larger the value T0 the narrower the frequency domain function and the less the corruption of the signal. Ideally, stating the obvious, selecting an infinite T0 and a zero T would clearly result in a Discrete Fourier Transform which would be exactly equal to a continuous Fourier transform In practice sample values comprising the discretised time domain function are tranformed to Discrete Fourier Transforms not Continuous Fourier transforms as shown above.    The Discrete Fourier transform is simply the product of the Continuous Fourier Transform and Dirac Comb - IIIa( 1/T0 ) function as illustrated below. The product of the two transforms equates to the convolution of the related time domain functions transforming the original aperiodic function to a periodic function as shown below . The time domain function can be expressed as below Now to derive the frequency domain function from the periodic time domain function. For a periodic time domain function the frequency domain function is a series of pulses. The factor cn is developed as follows The integration is completed over one period and therefore the equation can be simplified to. Because T0 = N.T .The equation can be written The resulting fourier Transform is It can be proved that there are only N distint values computable from this and the equation can be therefore developed into the form.

To be continued....