2.83) (2.77) Thus a 16 point DFT requires 4 stages, as shown in Figure 2.8. The algorithm is now re-applied to each of the N/2 sample DFT's. Assuming N same can out = x,(k)-wxx2(k) (2.78) each of DFT's to further reduce the computation. that point is even, the process be carried N = 2M then the whole process can be repeated M times to (2.79) reduce the computation to that of evaluating N single point DFT's. (2.80) Linear time-invariant digital systems Since the DFT output is periodic Equations 2.81 and 2.82 can be The theory of discrete-time, linear, time invariant systems forms obtained and the form of the algorithm given above is refered to as the basis for digital signal processing, and a discrete-time system the decimation in time FFT butterfly, and an example for a sixteen performs an operation on the input signal according to a defined point FFT is shown in Figures 2.6 and 2.7 criteria to produce a modified output signal. The input signal x(n), is the system excitation, and y(n) is the response of the system to the (2.81) excitation, see Figure 2.9, (Kamen, 1990). The transformation oper- ation can be represented by the operator R. Linear and time-invari- Linear time-invariant digital systems 2/11 Stage 3 point x(12) point x(10) x(14) point x(13) point x(11) x(15) Figure 2.7 Second step in developing a 16 point decimation in time FFT signal flow graph ant systems can be completely characterised by their impluse re- The z-transform provides a very powerful method for the analysis sponse, h(n), which is defined by Equation 2.84. of linear time-invariant discrete systems, which can be represented in terms of difference equations, via the operator R, relating the h(n)=R[8(n)] = (2.84) input signal samples to the output signal samples. In the following, we will define the properties of the z-transform Once the impulse response is determined, the output of the system and then we will apply the methods to the analysis of discrete time for any given input signal is obtained by convolving the input with linear time-