Let’s start with finite length signals, which are the easiest to handle. We have seen that a finite length signal is simply a vector in C^N. It turns out the free analysis in this case, is simply a change of bases in C^N. Now remember a change of bases is a change of perspective. And a change of perspective can reveal things. You’re looking at things from a different angle. So for example, imagine you have the signal like this. This is a 1,024 points signal. And as you look at it in the time domain, yeah you can see some oscillatory behavior, but it’s not really clear what’s going on. Well, if we perform an appropriate change of basis, and we will show shortly how to do that, the signal will look like this. So in the Fourier basis, the same signal will have this structure. And it is clear here that we have two very different things going on at the same time. We have two spikes, and we will see very shortly what the spikes mean. And then we have something that looks like noise in the bottom. Well, Fourier analysis allows us to separate these two elements that in the time domain were indistinguishable. So here is the Fourier bases for C^N. Remember C^N as I mentioned N. So we will need N different vectors each one of which will have length N. So k will be the index that indicates different vector. And k will go from 0 to big N-1. And then we will use small n to indicate the index of the element with image vector, and small n would also range from 0 to big N-1. The N signals will have this form. So remember k is the index of the signal, and small n is the index of the element within each signal. And each element is simply e to the j Pi over big N and k. What does that mean? This is simple complex exponential at a frequency omega which is two Pi over big N times k. So the index of the vector or of the signal, gives you the fundamental frequency of the complex exponential. We claim that this constitutes a set of orthogonal vectors in C^N. We can express the signals in vector notation, so remember our convention we use bold face letter to indicate vectors, a superscript in parentheses will give you the index of the vector when the vector comes from the set. In this case it comes from the set of big N vectors and a subscript will indicate the element within each vector so again w of k of n is simply equal to e to the j 2 pi over N and k. We can quickly get a feeling for what these vectors look like if we remember the complex explanational generating machine we saw a few modules back. So here for instance we show the components of w^1, the second vector in our basis. And as we go through the components, so this would be the first component of the vector, it would be equal to 1, the second component would translate the point around the circle by an angle 2 pi over N and so on and so forth. Remember, w^1 of n will be equal e to the j 2 Pi over big N and so we’re going around the circles in increments of 2 Pi over big N. Now the second vector in the basis, w2 of n will be of the form te to the j two Pi over big N, 2N. And so this vector will move in increments of two Pi over N times 2. So the points for that would actually be these guys and so on. Okay so let’s look to at a concrete example by setting big N equal to 64 and look at the Fourier basis for the space C^64. Here we're looking at the real and imaginary components of each basis vector. This, if you think of the point moving around in circles in the complex plane, will be the cosine and sine of its subtangent angle as the point moves along the circle. So here we have the first factor in the basis, w^0 and each component of this factor will be simply e to the j 2 pi over big N 0 times N. And because of the multiplication by 0, the exponent will be always 0 and so this vector is identically equal to 1. Its real component therefore is one for all instances, and its imaginary component is zero everywhere. The next vector is w^1, and here the fundamental angle of the complex exponential is omega 2 pi over N. What this means is that the point will complete one full revolution over 64 points and we can see this in the plots of its real and imaginary components. Here we have a full cosine period for the real part and a full sine period for the imaginary part. The next vector goes twice as fast. Now the fundamental frequency of the complex exponential will be 2 pi over big N times 2. And indeed we have two periods of the cosine and two periods of the sine in the imaginary part. The next vector is w 3. And the fundamental frequency will be 2 pi over big N times 3. So we have three periods both in the real and in the imaginary Pi. By now you underhand what’s going on. And as we go up with the Basis index, the vectors will start moving faster and faster. Because of the discrete nature here, it will be hard at one point to recognize that we have sinusoids. Here, for instance, you have w^16 that moves very quickly, but you have to imagine that the movement captures a rotation that goes very fast around the unit circle. Here, for instance, we have only four points because the angle of the complex exponential turns out to be 2 Pi over 64 times 16, which is equal to Pi over 2. From here, the point will move between these four points. And if you look at the coordinates in the real and imaginary part, you see exactly this behavior. As we increase the index of our Fourier vector, the underlying frequency increases as well. Now, the discrete nature of the vector makes it a little bit hard to understand the signs of the shape of the signal. But you can see for instance here that we are in the high frequency range because the sign of the samples changes at every step. So the sign alternation is a tell tale sign of a high frequency sitazoid. Finally, we reach the highest frequency that discrete time complex exponential can have. So here it happens for K equal to 32 where our frequency becomes 2 pi over 64 times 32, which is equal to pi. At this point, we will be moving from this position to this position in the complex plane. And this is clearly indicated by the real and imaginary components of the vector, which are alternating plus and minus one in the real part and identical to zero in the imaginary part. As we go forward index, as we saw in model 2.2, the apparent speed of the point decreases and the direction of the rotation changes from counterclockwise to clockwise. So here as the index increases from 32 up to 63, we see that the apparent speed of the sinusoid decreases back to 0. But the sign that we’re past pi, as far as the angular increment at each step is concerned, comes from the phase of the imaginary part, which is inverted with respect to the equivalent frequency that we have seen for low values of the index. So here, for instance, if you compare this basis vector to w of 2, you would see that the real part is the same, but the imaginary part has a sign in version. In w of 2, it would be like this. Same goes for w^63, real part is equal to w^1, but imaginary part has a sided version. Okay, so this is all nice and fine. We just showed a very beautiful family of little vectors, but in order for these vectors to be a basis of C^N, we have to prove that they are orthogonal to each other. Orthogonality requires that the inner product between any two vectors of the family is zero. So we write out the inner-product between w of k and w of h. We write out explicitly the inner product by considering each component of the first vector. Conjugate the component and multiplied by the corresponding component of the second vector. And we obtain a sum for n, small n goes from 0 to big N-1 of e to the j 2 Pi over N h - k times n. So how do we solve this formula? Well there are two cases. First of all let’s assume h is equal to k. So we’re actually taking the inner product of a vector with itself. At this point all these elements in the sum will be equal to one and so the sum will converge to N. In case h is not equal to k, then this is a sum of the form small n that goes from 0 to big N-1 a to the n. And we know that this is equal to 1- a to the big N, 1- a. So we plug the complex exponential into this formula and we obtain this ratio. But now this guy here on top is e to j 2 Pi times h minus k. This guy is an integer and therefore, this is e to the j times an integer multiple of 2 pi. So what that means is that no what the value of h-k is, we’re in this point here on the complex plane. And so 1-1 will be 0, and this will be 0 for all h not equal to k. So, the vectors are orthogonal and therefore, they form a basis for C^N. Now, note that the vectors are not orthonormal because w(h), w(h)=N as shown before. The normalization factor will be one over square root of n, but you will see later that we usually keep this normalization factor explicit rather than implicit for computational reasons.
