1 00:00:00,650 --> 00:00:04,660 Hi, and welcome to module 4.3 of Digital Signal Processing. 2 00:00:04,660 --> 00:00:07,420 In this module we will look at the DFT 3 00:00:07,420 --> 00:00:11,690 in practice by showing some analysis example by showing 4 00:00:11,690 --> 00:00:15,140 you how to label the DFT axis to relate 5 00:00:15,140 --> 00:00:19,220 the DFT to physical quantities like real world frequency. 6 00:00:19,220 --> 00:00:21,480 We will talk about DFT synthesis, how we 7 00:00:21,480 --> 00:00:24,760 move from the frequency domain to the time domain. 8 00:00:24,760 --> 00:00:25,910 And finally we will introduce 9 00:00:25,910 --> 00:00:30,650 a close relative of DFT called the discreet Fourier series, which 10 00:00:30,650 --> 00:00:35,760 is just a different flavor of DFT applied to periodic signals. 11 00:00:35,760 --> 00:00:40,638 You remember that we tried to wet your appetite with respect to Fourier 12 00:00:40,638 --> 00:00:45,840 analysis in the beginning of module 4.1, by showing you a mystery signal. 13 00:00:45,840 --> 00:00:50,740 And by showing you that by changing the basis in which the signal is represented, 14 00:00:50,740 --> 00:00:54,060 we all of a sudden could see some structure in the data. 15 00:00:54,060 --> 00:00:56,300 So now we can go back to that example 16 00:00:56,300 --> 00:01:00,400 and analyze it applying what we know about DFT. 17 00:01:00,400 --> 00:01:02,740 So we take the DFT of the mystery signal, 18 00:01:02,740 --> 00:01:06,200 we plot the real and imaginary part of the DFT, 19 00:01:06,200 --> 00:01:09,200 and we see that the structure that appears is 20 00:01:09,200 --> 00:01:14,760 a couple of spikes at symmetric positions in the spectrum. 21 00:01:14,760 --> 00:01:15,880 Now, we already know that this 22 00:01:15,880 --> 00:01:19,730 indicates the presence of a strong sinusoidal component 23 00:01:19,730 --> 00:01:22,850 and more importantly, a sinusoidal component has a 24 00:01:22,850 --> 00:01:25,580 frequency which is a multiple of the basic 25 00:01:25,580 --> 00:01:29,410 frequency for the space that the signal lives in. 26 00:01:29,410 --> 00:01:33,500 Now, if you look in detail at what happens in the spectrum, we see 27 00:01:33,500 --> 00:01:39,190 that the peaks are for k equal to 64 and k equal to 960. 28 00:01:39,190 --> 00:01:40,960 We also see that the 29 00:01:40,960 --> 00:01:46,400 peaks appear only in the real part of the spectrum and we remember that 30 00:01:46,400 --> 00:01:49,720 when this happens the underlying sinusoid, the 31 00:01:49,720 --> 00:01:53,050 sinusoid represented by those peaks, is a cosine. 32 00:01:53,050 --> 00:01:56,670 So from this simple visual inspection, we can already 33 00:01:56,670 --> 00:01:59,595 write our signal as such, it will be a 34 00:01:59,595 --> 00:02:02,460 cosine component and we will have to determine both 35 00:02:02,460 --> 00:02:05,710 the frequency and the initial phase of this cosine. 36 00:02:05,710 --> 00:02:10,590 And there will be another part that we can probably call 37 00:02:10,590 --> 00:02:13,660 a noise component, in the sense that it doesn't have any structure. 38 00:02:14,810 --> 00:02:19,230 Since the imaginary part of the Fourier transform doesn't exhibit any particular 39 00:02:19,230 --> 00:02:23,650 peak, we can assume that the phase of the cosine is zero. 40 00:02:24,780 --> 00:02:28,180 And as far as the frequency is concerned, we 41 00:02:28,180 --> 00:02:31,320 know that the peak occurs at k equals 64. 42 00:02:31,320 --> 00:02:37,179 We are in a space of 1,024 points, and therefore omega will be equal to 43 00:02:37,179 --> 00:02:43,390 2 pi over 1,024, the basic frequency for the space, times 64. 44 00:02:43,390 --> 00:02:47,570 If it blocked the two components separately at this point, we see 45 00:02:47,570 --> 00:02:52,670 that we have indeed a cosine that oscillates 64 times in 1,024 points. 46 00:02:52,670 --> 00:02:57,050 And we have an additional noise component 47 00:02:57,050 --> 00:02:59,720 that doesn't really seem to have any structure. 48 00:02:59,720 --> 00:03:01,520 Let's now look at another signal, one that 49 00:03:01,520 --> 00:03:04,740 we showed in the introduction to this class. 50 00:03:04,740 --> 00:03:10,170 And that is a time series that maps the solar activity since the 1700s. 51 00:03:11,210 --> 00:03:13,910 Astronomers have noticed that solar activity could be 52 00:03:13,910 --> 00:03:17,340 related to what they call a sunspot number. 53 00:03:17,340 --> 00:03:19,610 The details are not really important, but fundamentally 54 00:03:19,610 --> 00:03:22,580 a measure of how many solar spots are 55 00:03:22,580 --> 00:03:26,040 at a given point in time on the face of the sun. 56 00:03:26,040 --> 00:03:28,460 So we have a data set that goes from 1749 to 2003, 57 00:03:28,460 --> 00:03:35,270 that is equivalent to 2,900 months, solar spots are computed every month. 58 00:03:36,390 --> 00:03:40,538 And as we plot this data we see that there is an oscillatory behavior. 59 00:03:40,538 --> 00:03:42,818 We're interested in finding out if 60 00:03:42,818 --> 00:03:46,650 there's any fundamental periodicity in solar activity. 61 00:03:46,650 --> 00:03:48,820 So we can take the Fourier transform. 62 00:03:48,820 --> 00:03:52,120 The sunspot time series is a real signal. 63 00:03:52,120 --> 00:03:55,000 Now, if we are interested just in the magnitudes of the DFT 64 00:03:55,000 --> 00:03:59,600 coefficients, you remember we need only show the first half of them. 65 00:04:00,770 --> 00:04:04,630 Even so, if you look at the first 1,500 coefficients you see that 66 00:04:04,630 --> 00:04:07,120 after the 100th coefficient or so, their 67 00:04:07,120 --> 00:04:09,610 magnitude becomes too small to be relevant. 68 00:04:09,610 --> 00:04:11,480 So in this plot, for clarity, we just 69 00:04:11,480 --> 00:04:14,410 show the first 100 DFT coefficients in magnitude. 70 00:04:14,410 --> 00:04:18,600 And indeed we can see that there is not just one peak but a series of peaks. 71 00:04:18,600 --> 00:04:20,730 Now, what is the fundamental period? 72 00:04:20,730 --> 00:04:24,760 What is the most dominant mode of this time series? 73 00:04:24,760 --> 00:04:28,368 The main peak happens at k equal 22. 74 00:04:28,368 --> 00:04:32,860 There are 22 cycles over the entire data set. 75 00:04:32,860 --> 00:04:35,470 So the data set is 2900 months, so the 76 00:04:35,470 --> 00:04:39,940 frequency of the solar spot activity is 2900 divided 77 00:04:39,940 --> 00:04:43,290 by 22 which is approximately 11 years. 78 00:04:43,290 --> 00:04:49,040 So solar activity seems to have an inherent period of 11 years. 79 00:04:49,040 --> 00:04:52,790 We can perform the same analysis with a data set that records the daily 80 00:04:52,790 --> 00:05:00,080 temperature over a total of 2920 days. If we take the DFT of this time 81 00:05:00,080 --> 00:05:05,300 series, we see there is actually a very pronounced periodicity in the spectrum, 82 00:05:05,300 --> 00:05:07,780 there is basically just one peak. 83 00:05:07,780 --> 00:05:12,780 And if we plot the normalized DFT coefficient, so 84 00:05:12,780 --> 00:05:15,840 if we divide the DFT coefficients by the length 85 00:05:15,840 --> 00:05:18,925 of the temperature vector, we can actually extract some 86 00:05:18,925 --> 00:05:22,270 information about the temperature values in this time series. 87 00:05:22,270 --> 00:05:25,725 So remember, for instance, the DFT coefficient for k equal to 88 00:05:25,725 --> 00:05:30,984 0 is the known normalized average of all the data points 89 00:05:30,984 --> 00:05:36,010 because x of 0 is simply the sum of all the points in 90 00:05:36,010 --> 00:05:39,870 the time series for n that goes from 0 to big N minus 1. 91 00:05:39,870 --> 00:05:43,040 So if you plot the normalized coefficients, 92 00:05:43,040 --> 00:05:45,010 the coefficient in 0 will be the average 93 00:05:45,010 --> 00:05:47,100 temperature for the time series, which in 94 00:05:47,100 --> 00:05:51,220 this case happened to be 12.3 Celsius degrees. 95 00:05:51,220 --> 00:05:56,490 And then we remark that there is a peak in the DFT for k equal to 8. 96 00:05:56,490 --> 00:06:01,656 So if we sum up what we learned from the DFT about the temperature signal, we 97 00:06:01,656 --> 00:06:04,690 know the average value of the temperature is 98 00:06:04,690 --> 00:06:09,625 the 0th DFT coefficient normalized, so 12.3 degrees Celsius. 99 00:06:09,625 --> 00:06:14,290 The main peak is at k equal to 8, for a value of 6.4 degrees. 100 00:06:15,320 --> 00:06:18,040 What that means is there are eight cycles 101 00:06:18,040 --> 00:06:21,640 of the temperature signal over the entire duration of 102 00:06:21,640 --> 00:06:25,010 our data set, which is 2,920 days. 103 00:06:25,010 --> 00:06:30,840 So the frequency is 2,900 divided by 8, which happens to be 365 days. 104 00:06:30,840 --> 00:06:37,070 So indeed the temperature has a yearly periodicity, as we all know very well. 105 00:06:37,070 --> 00:06:41,930 Now, the value of the DFT main peak is 6.4 degrees Celsius. 106 00:06:41,930 --> 00:06:46,997 Now, if we have a sinusoid of the form A cosine of omega 107 00:06:46,997 --> 00:06:52,142 n, and we take the DFT of this signal, we will have a peak in magnitude 108 00:06:52,142 --> 00:06:57,460 at some, for some index k, that has a value of A 109 00:06:57,460 --> 00:07:03,110 over 2, remember the definition of the DFT of a cosine function. 110 00:07:03,110 --> 00:07:07,150 So from this we can say that the temperature excursion around 111 00:07:07,150 --> 00:07:11,200 the average is twice the value of the DFT main peak. 112 00:07:11,200 --> 00:07:11,960 And, so we can say, 113 00:07:11,960 --> 00:07:14,620 that the yearly temperature at the point of measurement for the 114 00:07:14,620 --> 00:07:20,390 year was an average of 12.3 degrees plus or minus 12.8. 115 00:07:20,390 --> 00:07:22,880 So this is a second example in which, in 116 00:07:22,880 --> 00:07:26,130 order to find the real world frequency of a certain 117 00:07:26,130 --> 00:07:29,230 DFT component, we take the total length of the 118 00:07:29,230 --> 00:07:32,790 signal and we divide by the location of the peak. 119 00:07:32,790 --> 00:07:37,400 This is actually a general method to label the frequency 120 00:07:37,400 --> 00:07:41,420 axis of a DFT plot and it will be very useful in the future 121 00:07:41,420 --> 00:07:43,790 when we start analyzing generic signals that 122 00:07:43,790 --> 00:07:46,780 have been sampled in a variety of contexts. 123 00:07:46,780 --> 00:07:50,685 So if you remember, in module 2.2, we informally introduced 124 00:07:50,685 --> 00:07:54,405 the notion of a clock for a digital signal processing system. 125 00:07:54,405 --> 00:07:57,930 And this is really equivalent to associating a certain 126 00:07:57,930 --> 00:08:02,860 time interval, Ts, measured in actual physical seconds between successive 127 00:08:02,860 --> 00:08:04,810 samples in the signal. 128 00:08:04,810 --> 00:08:09,380 So, for instance for the solar spot signal, we had a Ts of 129 00:08:09,380 --> 00:08:14,080 one month, whereas in the temperature signal, the Ts was equal to one day. 130 00:08:14,080 --> 00:08:17,250 We will see that for audio signal Ts becomes very small 131 00:08:17,250 --> 00:08:21,340 because we will need to take at least 8,000 samples per second. 132 00:08:21,340 --> 00:08:23,800 Now if we have a value for Ts, which is determined 133 00:08:23,800 --> 00:08:28,140 by the experimental setup, we can reason like so, the fastest positive 134 00:08:28,140 --> 00:08:33,230 frequency in a digital signal is omega equal to pi. 135 00:08:33,230 --> 00:08:36,730 So a sinosoid at that frequency needs two samples 136 00:08:36,730 --> 00:08:39,370 to do a full revolution, remember the unit circle. 137 00:08:40,450 --> 00:08:46,020 Something that moves at a speed of pi will be here at instance n, here at n 138 00:08:46,020 --> 00:08:51,750 plus one, here at n plus two, so two samples to complete the full revolution. 139 00:08:51,750 --> 00:08:53,250 Now, the clock Ts can 140 00:08:53,250 --> 00:08:58,520 also be expressed as 1 over Fs, where Fs is the frequency of the system. 141 00:08:58,520 --> 00:09:02,620 This is a standard relationship between period and frequency for any system. 142 00:09:02,620 --> 00:09:07,680 So, if the real world period for the fastest sinusoid in a digital system 143 00:09:07,680 --> 00:09:12,730 is 2 times Ts measured in seconds, the real world frequency for the fastest 144 00:09:12,730 --> 00:09:18,280 sinusoid is Fs over 2. So the maximum frequency, 145 00:09:18,280 --> 00:09:21,900 once we've fixed the period between samples, is 146 00:09:21,900 --> 00:09:25,440 Fs over 2, or equivalently, 1 over 2 Ts. 147 00:09:26,460 --> 00:09:28,040 So let's take a concrete example. 148 00:09:28,040 --> 00:09:32,240 Suppose I give you an audio file that records a train whistle 149 00:09:32,240 --> 00:09:36,524 and I'm asking you to find out which notes make up the whistle 150 00:09:36,524 --> 00:09:37,127 [SOUND]. 151 00:09:37,127 --> 00:09:42,129 And of course your idea is to take the DFT of this file and find out the peaks 152 00:09:42,129 --> 00:09:46,475 and the Fourier transform, which will probably correspond to 153 00:09:46,475 --> 00:09:50,998 the fundamental frequencies of the notes that are being played. 154 00:09:50,998 --> 00:09:54,454 So in order to do so you need some extra information and namely you 155 00:09:54,454 --> 00:09:56,502 need to know the sampling frequency of 156 00:09:56,502 --> 00:10:00,220 this file, namely the time between successive samples. 157 00:10:00,220 --> 00:10:02,850 So the sampling frequency is Fs 158 00:10:02,850 --> 00:10:09,745 equal to 8000 hertz, which means that Ts is 1 over 8000 seconds, 159 00:10:09,745 --> 00:10:16,630 this is the time between samples, and also the file contains 32768 samples. 160 00:10:16,630 --> 00:10:22,740 We will see it later why we often choose signal lengths that are a power of two. 161 00:10:22,740 --> 00:10:24,890 So if you take the DFT of this file and plot 162 00:10:24,890 --> 00:10:27,850 its magnitude you see that there are three peaks that probably 163 00:10:27,850 --> 00:10:30,590 corresponds to the three notes being played. 164 00:10:30,590 --> 00:10:33,430 Now in order to label the axis remember what we said, the 165 00:10:33,430 --> 00:10:35,770 highest frequency for a digital system 166 00:10:35,770 --> 00:10:38,880 corresponds to half the inherent sampling rate. 167 00:10:39,920 --> 00:10:44,770 And on the DFT vector, this point will correspond to the midpoint in 168 00:10:44,770 --> 00:10:49,200 the vector, namely the point for k is equal to N over 2. 169 00:10:49,200 --> 00:10:53,810 So here indeed we have the midpoint of the DFT vector and 170 00:10:53,810 --> 00:10:58,540 therefore, this will correspond to a frequency of four kilohertz. 171 00:10:58,540 --> 00:11:01,740 We also have three peaks to take place for different values of k. 172 00:11:01,740 --> 00:11:04,240 To find the real frequency there, we just apply a 173 00:11:04,240 --> 00:11:07,200 linear mapping from zero to four kilohertz, and so the 174 00:11:07,200 --> 00:11:12,810 frequency of any intermediate point will be 4 kilohertz divided 175 00:11:12,810 --> 00:11:16,920 by the total number of points multiplied by the index k. 176 00:11:16,920 --> 00:11:19,040 And with this rule, we find that the peaks 177 00:11:19,040 --> 00:11:25,610 take place at 494 hertz, 559 hertz, 739 hertz. 178 00:11:25,610 --> 00:11:30,076 And if we look up what these frequencies correspond to in the standard 179 00:11:30,076 --> 00:11:34,400 western scale, we find that the whistle is a simple B minor chord. 180 00:11:34,400 --> 00:11:39,320 Okay, so far we have looked at DFT as an analysis tool, let's now spend 181 00:11:39,320 --> 00:11:41,960 some time thinking about the synthesis properties 182 00:11:41,960 --> 00:11:44,200 of the DFT, how we build the signal 183 00:11:44,200 --> 00:11:45,680 starting from DFT coefficients. 184 00:11:45,680 --> 00:11:48,310 And to better understand how the DFT 185 00:11:48,310 --> 00:11:51,540 reconstruction formula works, it's useful to look at 186 00:11:51,540 --> 00:11:55,190 the standard sinusoidal generator that works at one 187 00:11:55,190 --> 00:11:57,990 of the standard frequencies in the Fourier basis. 188 00:11:57,990 --> 00:12:01,610 So here you have a complex exponential with a frequency which is a 189 00:12:01,610 --> 00:12:05,976 multiple of 2 pi over big N and with an initial phase, phi k. 190 00:12:07,520 --> 00:12:09,880 The way this generator works is 191 00:12:09,880 --> 00:12:15,112 by successively generating points on the unit circle, starting at the phase 192 00:12:15,112 --> 00:12:19,560 phi k and proceeding in increments of 2 pi over big N. 193 00:12:19,560 --> 00:12:23,150 We can draw this concisely with this notation where here inside you 194 00:12:23,150 --> 00:12:28,230 have the index of the Fourier frequency that the generator will produce. 195 00:12:28,230 --> 00:12:31,710 And the input parameters for the generators are 196 00:12:31,710 --> 00:12:34,929 of course the initial phase here, and again 197 00:12:34,929 --> 00:12:38,148 factor A of k, that will lead to A of k times to 198 00:12:38,148 --> 00:12:41,158 e to the j 2 pi over big N, kn plus phi k. 199 00:12:41,158 --> 00:12:44,400 So the DFT reconstruction formula can be drawn 200 00:12:44,400 --> 00:12:48,477 graphically like a machine composed of big N sinusoidal 201 00:12:48,477 --> 00:12:51,680 generators, each one of which will be initialized 202 00:12:51,680 --> 00:12:54,570 with a gain factor and with a phase factor. 203 00:12:54,570 --> 00:12:58,190 All their outputs will be summed together and 204 00:12:58,190 --> 00:13:01,120 this will give us back the original signal. 205 00:13:01,120 --> 00:13:03,340 How do we initialize each one of these blocks? 206 00:13:03,340 --> 00:13:05,220 Well the amplitude will be the amplitude 207 00:13:05,220 --> 00:13:08,800 of the corresponding Fourier analysis coefficient normalized by 208 00:13:08,800 --> 00:13:10,800 big N, and the phase will be 209 00:13:10,800 --> 00:13:14,960 the phase of the corresponding Fourier analysis coefficient. 210 00:13:14,960 --> 00:13:20,030 So, lets look at an example. Lets take a simple signal, a seven point 211 00:13:20,030 --> 00:13:26,460 long signal that looks like a triangle, and we perform a Fourier analysis 212 00:13:26,460 --> 00:13:30,770 on this vector and we get seven Fourier coefficients 213 00:13:30,770 --> 00:13:35,360 that we list here in terms of amplitude and phase. 214 00:13:35,360 --> 00:13:37,922 Now we initialize the seven generators with the As 215 00:13:37,922 --> 00:13:40,380 and the phis that we found in the analysis part. 216 00:13:40,380 --> 00:13:43,160 And then we turn the crank seven times and we 217 00:13:43,160 --> 00:13:47,130 will sum the outputs together to obtain the original signal. 218 00:13:47,130 --> 00:13:51,460 So here is how it works. In the first line, 219 00:13:51,460 --> 00:13:56,000 we will show the output of each generator in turn, starting 220 00:13:56,000 --> 00:13:59,060 for k equal to 0 up to k equal to 6. 221 00:13:59,060 --> 00:14:02,090 And here on the bottom line, we will show the cumulative 222 00:14:02,090 --> 00:14:06,830 sum of the outputs as k proceeds from 0 to 6. 223 00:14:06,830 --> 00:14:10,100 So the first generator is the one for k equal to 0, 224 00:14:10,100 --> 00:14:14,410 so the frequency is 0, and the output will be simply a constant. 225 00:14:14,410 --> 00:14:15,630 As a matter of fact, the value of this contes, 226 00:14:15,630 --> 00:14:18,750 constant will be equal to A of 0. 227 00:14:18,750 --> 00:14:21,840 And so the cumulative sum now has only one term, 228 00:14:21,840 --> 00:14:25,370 so the output at this point will look like a constant. 229 00:14:25,370 --> 00:14:28,110 For k equal to 1, we have now a sinusoid 230 00:14:29,400 --> 00:14:32,200 that will have a certain initial phase and a certain amplitude. 231 00:14:32,200 --> 00:14:35,510 And we can see that as we add this to the previous constant, here in 232 00:14:35,510 --> 00:14:40,320 grey you see the previous sum, and here the updated sum for k equal to 1, 233 00:14:40,320 --> 00:14:44,740 the real part of the signal starts to look a little bit like a triangle. 234 00:14:44,740 --> 00:14:49,050 We also have a significant non-negligible imaginary part which will have to 235 00:14:49,050 --> 00:14:53,190 disappear in the end because remember, we started from a real signal. 236 00:14:53,190 --> 00:14:57,170 So as we proceed for k equal to 2, we see that the coefficient 237 00:14:57,170 --> 00:15:01,380 amplitude is very small and so this will be just small adjustments in the sum. 238 00:15:01,380 --> 00:15:04,220 It's very hard to see the difference between this step and the previous step. 239 00:15:05,270 --> 00:15:08,670 K equal to 3 is very similar, small adjustments. 240 00:15:08,670 --> 00:15:14,150 For k equal to 4, we're going in the, counter-clockwise part of the spectrum, 241 00:15:14,150 --> 00:15:19,310 so more adjustments still, that will start to bring down the imaginary part to 0. 242 00:15:19,310 --> 00:15:21,080 Here you see another small adjustment. 243 00:15:21,080 --> 00:15:24,700 And finally k equal to 6, the last coefficient will completely kill the 244 00:15:24,700 --> 00:15:29,230 imaginary part and give us back exactly the signal we were starting from. 245 00:15:29,230 --> 00:15:30,670 So why do we think 246 00:15:30,670 --> 00:15:34,340 about the DFT reconstruction formula as a machine? 247 00:15:34,340 --> 00:15:36,730 Because in reality these machines were used in 248 00:15:36,730 --> 00:15:39,330 the past for instance to predict the tides. 249 00:15:39,330 --> 00:15:43,960 The tide is a periodic phenomenon and once you find the modes you can actually use 250 00:15:43,960 --> 00:15:46,710 the experimental data to predict the evolution of 251 00:15:46,710 --> 00:15:50,160 the tide as a superposition of sinusoidal components. 252 00:15:50,160 --> 00:15:52,570 So this machine, that was originally invented by 253 00:15:52,570 --> 00:15:56,860 Lord Kelvin, is nothing but a mechanical implementation 254 00:15:56,860 --> 00:15:59,540 of the DFT reconstruction machine that we just saw before. 255 00:16:00,940 --> 00:16:03,100 So here's a question, what happens if you turn 256 00:16:03,100 --> 00:16:06,170 the crank of the machine more than big N times? 257 00:16:06,170 --> 00:16:10,562 Well it turns out that the output will become periodic, in other words, 258 00:16:10,562 --> 00:16:13,174 x of small n plus big N will be equal to x of n. 259 00:16:13,174 --> 00:16:16,055 This is actually quite apparent from the structure 260 00:16:16,055 --> 00:16:19,370 of the synthesis and analysis formulas of the DFT. 261 00:16:19,370 --> 00:16:21,510 Let's start from the synthesis formula. 262 00:16:21,510 --> 00:16:22,160 So in 263 00:16:22,160 --> 00:16:26,890 theory, the output index small n should go from 0 to big N minus 1. 264 00:16:26,890 --> 00:16:31,050 But you can see that it only appears here, inside this complex exponential. 265 00:16:31,050 --> 00:16:36,930 Now this guy is 2 pi periodic, so if you push n over big N minus 1, this will 266 00:16:36,930 --> 00:16:44,340 simply cycle over once again as if n was looping over the 0 to n minus 1 range. 267 00:16:44,340 --> 00:16:47,260 So in the end, you can actually safely take n 268 00:16:47,260 --> 00:16:51,990 to be from the set of integers and the output 269 00:16:51,990 --> 00:16:54,390 will be an N periodic signal in the time domain. 270 00:16:55,410 --> 00:16:57,970 Actually the same holds for the analysis formula. 271 00:16:57,970 --> 00:17:00,980 You can let the index k roam over the entire 272 00:17:00,980 --> 00:17:03,930 set of integers and since it appears only in this 273 00:17:03,930 --> 00:17:07,580 complex exponential here, again, it will be as if k 274 00:17:07,580 --> 00:17:11,860 was looping over the 0 to n minus 1 range. 275 00:17:11,860 --> 00:17:12,590 So what happens 276 00:17:12,590 --> 00:17:15,720 really, is that you can consider the sequence of DFT 277 00:17:15,720 --> 00:17:19,550 coefficients as an N periodic signal in the frequency domain. 278 00:17:21,200 --> 00:17:26,820 Now, when we talk explicitly about the periodicity of the Fourier 279 00:17:26,820 --> 00:17:32,570 transform, we prefer to use the term discrete Fourier series or DFS for short. 280 00:17:32,570 --> 00:17:36,720 So the DFS is just the DFT with the periodicity explicit. 281 00:17:36,720 --> 00:17:38,270 The DFS maps 282 00:17:38,270 --> 00:17:42,810 an N-periodic signal onto an N-periodic sequence of Fourier coefficients. 283 00:17:42,810 --> 00:17:45,270 And the inverse DFS maps an N-periodic 284 00:17:45,270 --> 00:17:49,130 sequence of Fourier coefficients onto an N-periodic signal. 285 00:17:49,130 --> 00:17:53,360 But mathematically the two are the same, it's just a conceptual difference. 286 00:17:53,360 --> 00:17:58,100 However, DFS helps understand, for instance, why we said that the 287 00:17:58,100 --> 00:18:03,420 natural shift for finite length sequences is actually a periodic shift. 288 00:18:03,420 --> 00:18:06,710 Let's consider an N-periodic sequence x tilda of n. 289 00:18:06,710 --> 00:18:09,540 For periodic sequences, shifts are well-defined. 290 00:18:09,540 --> 00:18:12,550 We can take x tilda of n minus big M 291 00:18:12,550 --> 00:18:16,000 and it's just a normal shift of an infinite two-sided sequence. 292 00:18:17,040 --> 00:18:22,600 If we take the DFS of this periodic sequence with a shift, we can work out 293 00:18:22,600 --> 00:18:28,690 very easily that the DFT coefficient for index k is equal to the DFT coefficient 294 00:18:28,690 --> 00:18:31,790 for index k of the original sequence without the shift. 295 00:18:31,790 --> 00:18:38,860 So, x of k is simply the DFS of tilde x of n 296 00:18:40,960 --> 00:18:46,720 with a phase shift term, e to the minus j, 2 pi over n, big M times k. 297 00:18:46,720 --> 00:18:48,600 Similarly, it's very easy to verify that the 298 00:18:48,600 --> 00:18:51,670 inverse discrete Fourier series of a vector of 299 00:18:51,670 --> 00:18:56,030 DFS coefficients multiplied by a phase delay factor, 300 00:18:56,030 --> 00:19:00,860 is simply the periodic sequence delayed by M. 301 00:19:00,860 --> 00:19:02,980 So this term, e to the minus j, 2 pi 302 00:19:02,980 --> 00:19:07,420 over n, Mk is a delay factor in the frequency domain. 303 00:19:07,420 --> 00:19:09,130 So what happens for finite length signals? 304 00:19:10,160 --> 00:19:14,820 We saw that in this case, a shift is not a well-defined operation and we need to 305 00:19:14,820 --> 00:19:18,070 embed the signal into an infinite length signal, either 306 00:19:18,070 --> 00:19:21,260 by building a finite support or a periodic signal. 307 00:19:22,280 --> 00:19:28,110 Now we can always build x tilda of n as x of n modules big N. 308 00:19:28,110 --> 00:19:32,580 Now mathematically, the DFS of this periodic signal is equal to 309 00:19:32,580 --> 00:19:37,530 the DFT of the original signal. So the inverse DFT of the DFT 310 00:19:37,530 --> 00:19:42,700 of the signal times this delay factor, that we showed in the previous slide, 311 00:19:42,700 --> 00:19:48,360 is numerically equal to the inverse DFS of the same quantity. 312 00:19:48,360 --> 00:19:54,490 But we know that the inverse DFS of this will be a delayed periodic sequence. 313 00:19:54,490 --> 00:19:57,610 And if we go back to the definition of how we build this periodic 314 00:19:57,610 --> 00:20:02,990 sequence this will be simply x of n minus big N modulus big N. 315 00:20:02,990 --> 00:20:07,680 What we have shown here is that if we think of the Fourier representation of a 316 00:20:07,680 --> 00:20:13,550 finite length signal, circular shifts are the natural extension of the shift 317 00:20:13,550 --> 00:20:16,550 operator to finite length signals because the 318 00:20:16,550 --> 00:20:18,830 underlying Fourier representation is the same as 319 00:20:18,830 --> 00:20:23,280 that what would use for a periodic symbol built on the finite length signal.