So let's look at some examples. And one property that we will use in the following which is obvious from the definition of inner product is that the DFT, the Discrete Fourier Transform transform is a linear operator. So if you have the DFT of the sum of two vectors this would be equal to the sum of the DFTs and the same goes if you have the scalar multiplication. So the first example is a DFT of the discrete time delta. You can see the delta here in the time domain. It is 1 in 0, and 0 everywhere else over the support of the signal. Now if you work out the inner product of the discrete time delta, with the Fourier basis vector you will see that the delta will isolate the 0 component of each basis vector. So the product will be 1 for all values of the index k. So the Fourier transform of the discrete time delta is the constant 1. In other words, delta contains all frequencies over the possible range of frequencies. The dual example of that is the Fourier transform of the unit function. So you have 1 for all values of the time index and if you work out the inner product, you will see that the Fourier transform corresponds to a delta. This is quite intuitive because this is nothing else than the orthogonality formula that we showed before. So it will be equal to big N and 0, and 0 everywhere else. So now let's try to compute the DFT of a sinusoidal function. We take x[n] to be 3 times the cos of 2pi over 16 times n. We are a C^64, so n the dimension of our space is 64. And the fundamental frequency of our Fourier transform would be omega equal to 2pi over 64. All frequencies in the Fourier basis will be a multiple of this. With this in mind, we can start by expressing the frequency of our sinusoid as a multiple of the fundamental frequency of this space. So 2pi over 16 will be equal to 2pi over 64 times 4. With this now, we can use Euler's formula that says that cos of omega is equal to e to the j omega plus e to the minus j omega divided by 2. And express the original cosine as the sum of two complex exponentials. Namely, e to the j 2pi over 64 times 4 times n plus e to the minus j 2pi over 64 times 4 times n. Now we don't like this minus here. So what we're going to do is exploit the fact that we can always add an integer multiple of 2pi to the exponent of the complex exponential. And the point will not change on the complex plane. So minus j 2pi over 64 times 4 times n plus j 2pi n will be equal to e to the j 2pi over 64 times 60 times n because n is an integer. And so now we have expressed the original signal as a sum of two Fourier basis vectors. So x[n] will be equal to 3 over 2 times basis vector number 4 plus basis vector number 60. At this point we can apply the DFT as an inner product with each vector in the basis, and we can exploit the linearity of the operator. So X[k], the kth Fourier coefficient Will be equal to the inner product between basis vector number K, and our signal. If we replace the signal with what we just computed before, we have this formula here. Because of linearity, we can split this into two distinct inner products. And we have 3 over 2 times inner product of the generic basis vector times basis vector number 4 plus 3 over 2 times the inner product of the generic basis vector with the basis vector number 60. But now we know that this guy here, will be none 0 only for k equal to 4. And this guy here will be non-zero only for k = 60. When k = 4, this will be equal to big N namely 64 and when k = 60, this will be equal to again 64. And so if we work out the arithmetic, we got that the DFT of original signal is equal to 96 if k is equal to 4 or is equal to 60, and 0 otherwise. So we can plot the DFT of our cos and it will be 0 everywhere in the real part except in 4 and in 60. Whereas the imaginary part will be 0 everywhere. So let's try another example. Here we take the same cos as before, but we add an initial phase. So we take 3 times the cos of 2pi over 16 times n plus pi over 3. The first thing we do is to express the frequency of the cos as a multiple of the fundamental frequency for the space, we're still in C^64. Then we use Euler's formula and we decompose the cosine as the sum of two conjugate complex exponentials. And we can express the phase term, we can take it out of the complex exponential as a complex scalar multiplicative factor. So then we can use the same trick as before to bring this negative frequency into the 0, 63 range. And we obtain that our signal is simply 3 over 2 times the sum of basis vector number 4 multiplied by e to the j pi over 3 plus basic number vector 60 multiplied e to the minus j pi over 3. And when we compute the DFT, we take the product of that with the generic basis vector for Fourier basis and just like before we obtain just 2 non-zero values. When k is equal to 4, the first term will survive given us a DFT value of 96 times e to j pi over 3. And when k is equals to 60 we will get 96 e to the minus j pi over 3, and 0 everywhere else. We can plot the Fourier transform like before and we will have in this case non-zero values both in the real and the imaginary part. Probably a clear way of plotting this Fourier transform, however is to plot both the magnitude and the phase of the Fourier coefficients. If you remember what we just computed, the magnitude will be equal to 96, both for k = 4 and for k = 60. And the phase will be equal to pi over 3 for k = 4 and minus pi over 3 for k = 60. This way of plotting the data shows that we can use the fully transformed to separate the amplitude of a sinusoid from its phase. So I'm sure that by now most of you will be saying okay, but what about sinusoid whose frequency is not a multiple of the fundamental frequency for the space? What do we do there? And indeed let's say, we take a sinusoid with frequency 2pi over 10, so 3 times the cosine of 2pi over 10 n. Well this cannot be reduced to a multiple of 2pi over 64. It is a frequency that actually falls between 2pi over 64 times 6, and 2pi over 64 times 7. So what do we do there? Well we simply compute DFT numerically. Remember the DFT is an algorithm that requires a finite number of operations and that can be computed with the desired level of precision in numerical packages such as MATLAB. Where you can even write your own C code routine to do so. We will see later in module 4.9 that very, very efficient algorithms exist to compute the DFT, so this is not a problem. So we run the DFT in a numerical package and we obtain the magnitude and the phase. Now if you see high level of magnitude indicates a similarity of the input with the corresponding basis vector, it's a definition of inter product. So here unsurprisingly, the input is particularly close to basis vectors number 6 and number 7 as we showed before. And by extension to 64-6 and 64-7. But in order to obtain the exact 2pi over 10 frequency, we need contributions from all the DFT coefficients in the 0 to 63 range. And similarly the phase is non-zero for the whole range as well. This is actually a general result unless you have an input that is a linear combination of basis vectors, most of your DFT coefficients will be non-zero. Let's go for instance an example that we can compute exactly. Let's consider the DFT of the step vector in CN. We're in CN, and we have a signal that is 1 for n equal to 0 to m-1 and then 0 everywhere else. If we compute the DFT, we can just write the inner product explicitly and replace the values for the input signal. So now x of n will be equal to 1 for small n goes from 0 to big N minus 1, and 0 everywhere else. So this simply reduces the sum, that originally went from 0 to big N-1, to 0 to M-1, and the coefficient for each term will be 1. So this is a geometric sum, we have seen that before. So sum for n that goes from 0 to big M-1 of a to the power of n is equal to 1-a to the power of big M divided by 1-a. So we apply that, we obtain this ratio and now, we're going to perform a little trick. So let me write it here on the side. If we have an expression of the form 1 minus e to the minus j alpha, we can always collect half the phase of this complex exponential. And write e to the minus j alpha over 2, then multiplies e to the j alpha over 2, minus e to the minus j alpha over 2. Why do we do this? Well because this guy here is nothing else than 2j sine of alpha over 2. So we can separate this element into a real valued component and into a phase term. So we do this for this expression and we collect half the phase here and half the phase here. And if we work out the algebra, we get that the DFT coefficients are equal to the ratio of two sin functions times a pure phase term here. Now I'm not going to read out loud this formula, but we're going to try and plot it. So we're going to try and get intuition about how this is going to look. So first of all, if we think about the magnitude of this coefficient, note that this phrase term we will always be equal to magnitude because it's a pure phase term. So the magnitude will be determined by the ratio of these two trigonometric functions. In 0, this ratio is ill defined, but if you go back to the expression for the DFT sum. You can see that if you put k = 0, it becomes simply the sum of big N 1s, so the DFT of 0 = M. Another point to notice is that if k is a multiple of N over M, then the numerator here will be equal to 0 and so the DFT coefficient will be equal to 0. Finally the phase, which depends only on this complex exponential here, is linear in k as you can see from the formula. Except sin changes for the real part where we will have a jump of pi. So if we plug this in magnitude and phase, we have that the shape looks like so. We are using a length 4 step in C^64, so N over M will be equal to 16. And indeed the DFT coefficient will be 0 and 16, 32 and 48, and all multiples of 16. The phase is indeed linear, and whenever there is a discontinuity in the sine of the real part, we will have a jump of pi. So discontinuity, you can see it here. Here we're plotting the magnitude of the real part. But in reality, if we were to plot the part with the sine, this would become negative here. Go back to positive here, and then go negative here. Notice that here the phase extends from 0 to minus 4 pi, this is a little bit unusual. We said that 0 to 2 pi or minus pi to pi is the only interval that we're interested in at this current time because everything maps back to that interval. It's very common to see plots where the phase is wrapped over the minus pi, pi interval. What that means simply is for every value of the phase we add or subtract two pi until we fall back into the minus pi, pi interval. So here's the same plot as before but with the phase wrapped.
