15
$\begingroup$

There are a few excellent discussion threads and answers on this site (eletronics.se) on the theory of Fourier transforms. I tried implementing the same in a simulation tool (MS Excel :)).

I have a few interpretation and implementation issues regarding the same. I am trying to analyse an voltage waveform of 50 Hz. However, the data below is just generated dummy data trying to establish a conceptual framework for implementation on a a memory and processing power constrained 16 bit embedded low cost processor.


ETA (May 30,2012)

TL;DR version:

It went without saying on electronics.se but I am using a memory and processing power constrained embedded processor.

There are a few questions here that are still unanswered:

  1. How is windowing performed on the samples that I have without significantly increasing the memory footprint of the algorithm? I would like these to be a basic step by step description, as I am pretty new to DSP.
  2. Why were the magnitudes halved when I interpolated 41 samples to derive 32, but remained as they were (except for some noise) when I interpolated them to derive 64?

I am declaring a bounty on the question with the hope that I get some excellent answers which are actionable for a novice in DSP.


Experiment 1:

Time Domain input

I generated a sine wave using $ \sin(2n \pi /64) $ to generate 64 samples. I then added 30% $3rd$ harmonics, 20% $5th$ harmonics, 15% $7th$ harmonics, 10 % $ 9th $ harmonic, and 20% $ 11th $ harmonics. This led to these samples:

0, 0.628226182, 0.939545557, 0.881049194, 0.678981464, 0.602991986, 0.719974543, 
0.873221372, 0.883883476, 0.749800373, 0.636575155, 0.685547957, 0.855268479, 
0.967780108, 0.904799909, 0.737695292, 0.65, 0.737695292, 0.904799909, 0.967780108, 
0.855268479, 0.685547957, 0.636575155, 0.749800373, 0.883883476, 0.873221372, 
0.719974543, 0.602991986, 0.678981464, 0.881049194, 0.939545557, 0.628226182, 0, 
-0.628226182, -0.939545557, -0.881049194, -0.678981464, -0.602991986, -0.719974543, 
-0.873221372, -0.883883476, -0.749800373, -0.636575155, -0.685547957, -0.855268479, 
-0.967780108, -0.904799909, -0.737695292, -0.65, -0.737695292, -0.904799909, 
-0.967780108, -0.855268479, -0.685547957, -0.636575155, -0.749800373, -0.883883476, 
-0.873221372, -0.719974543, -0.602991986, -0.678981464, -0.881049194, -0.939545557,
-0.628226182

And this waveform:

Time domain Waveform 64 samples period 64

I took a DFT of these samples based on a Radix 2 algorithm and got these values:

0, -32i, 0, -9.59999999999999i, 0, -6.4i, 0, -4.79999999999999i, 0, -3.20000000000001i,
0, -6.4i, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6.4i, 0, 3.19999999999999i, 0, 4.8i, 0,
6.4i, 0, 9.60000000000001i, 0, 32i

Taking the absolute values of the complex numbers above as the ratio to the fundamental(2nd value) and ignoring phase information(if there was any), I got the magnitudes of the injected harmonic components exactly as injected.

Frequency Domain Representation

enter image description here

So far so good.


Experiment 2:

Time Domain input

I generated a sine wave again using $ \sin(2n \pi /41) $ to generate 64 samples. Why 41? Because in actual implementation, my microcontrollers ADC samples at a multiple of the external oscillator, and I have only a few types of crystals available. I then added 30% $ 3rd $ harmonics, 20% $ 5th $ harmonics, 15% $ 7th $ harmonics, 10 % $ 9th $ harmonic, and 20% $ 11th $ harmonics. This led to these samples:

0, 0.853079823, 0.857877516, 0.603896038, 0.762429734, 0.896260999, 0.695656841, 
0.676188057, 0.928419527, 0.897723205, 0.664562475, 0.765676034, 0.968738879, 
0.802820512, 0.632264626, 0.814329015, 0.875637458, 0.639141079, 0.696479632, 
0.954031849, 0.50925641, -0.50925641, -0.954031849, -0.696479632, -0.639141079, 
-0.875637458, -0.814329015, -0.632264626, -0.802820512, -0.968738879, -0.765676034, 
-0.664562475, -0.897723205, -0.928419527, -0.676188057, -0.695656841, -0.896260999, 
-0.762429734, -0.603896038, -0.857877516, -0.853079823, -6.87889E-15, 0.853079823, 
0.857877516, 0.603896038, 0.762429734, 0.896260999, 0.695656841, 0.676188057, 
0.928419527, 0.897723205, 0.664562475, 0.765676034, 0.968738879, 0.802820512, 
0.632264626, 0.814329015, 0.875637458, 0.639141079, 0.696479632, 0.954031849, 
0.50925641, -0.50925641, -0.954031849 

And this waveform:

enter image description here

I took a DFT of these samples based on a Radix 2 algorithm and got these values:

14.03118145099, 22.8331789450432+2.81923657448236i, -17.9313890484703-4.4853739490832i, 
-2.54294462900052-0.971245447370764i, 1.74202662319821+0.944780377248239i, 
-7.2622766435314-5.09627264287862i, -1.5480700475686-1.37872970296476i, 
-0.136588568631116-0.126111953353714i, -3.99554928315394-5.93646306363598i, 
-0.840633449276516-1.60987487366169i, -0.373838501691708-0.955596009389976i, 
-1.326751987645-5.7574455633693i, -0.168983464443025-1.34797078005724i, 
-9.49818315071085E-003-1.20377723286595i, 0.571706242298176-4.14055455367115i,  
0.192891008647316-0.865793520825366i, 0.457088076063747-1.22893647561869i, 
3.15565897700047-5.67394957744733i, -0.573520124828716+0.682717512668197i, 
-0.20041207669728+0.127925509089274i, -7.95516670999013E-002-1.22174958722397E-002i, 
-1.57510358481328E-002-6.44533006507588E-002i, 2.50067192003906E-002-8.46645685508359E-
002i, 5.3665806842526E-002-9.01867018999554E-002i, 7.49143167927897E-002-
8.80550417489663E-002i, 9.11355142202819E-002-8.16075816185574E-002i, 
0.103685444073525-7.25978085593222E-002i, 0.11339684328631-6.20147712757682E-002i, 
0.120807189654211-5.04466357453455E-002i, 0.126272708495893-3.82586162066316E-002i, 
0.130029552904267-2.56872914345987E-002i, 0.132228055573542-1.28943815159261E-002i, 
0.1329519244939, 0.132228055573544+1.28943815159441E-002i, 
0.130029552904267+2.56872914345769E-002i, 0.126272708495892+3.82586162066264E-002i, 
0.12080718965421+5.04466357453468E-002i, 0.113396843286315+6.20147712757588E-002i, 
0.103685444073529+7.25978085593135E-002i, 9.11355142202805E-002+8.16075816185583E-002i, 
7.4914316792795E-002+8.80550417489592E-002i, 5.36658068425271E-002+9.01867018999563E-
002i, 2.50067192003947E-002+8.46645685508275E-002i, -1.57510358481296E-
002+6.44533006507526E-002i, -7.95516670999005E-002+1.22174958722402E-002i, 
-0.20041207669728-0.127925509089278i, -0.573520124828709-0.682717512668206i, 
3.15565897700049+5.67394957744733i, 0.45708807606375+1.22893647561869i, 
0.192891008647318+0.865793520825373i, 0.571706242298199+4.14055455367114i, 
-9.49818315070294E-003+1.20377723286595i, -0.168983464443023+1.34797078005724i, 
-1.32675198764498+5.75744556336931i, -0.373838501691692+0.955596009389972i, 
-0.840633449276515+1.6098748736617i, -3.99554928315393+5.93646306363599i, 
-0.136588568631125+0.126111953353722i, -1.54807004756858+1.37872970296476i, 
-7.26227664353139+5.09627264287866i, 1.7420266231982-0.944780377248243i, 
-2.54294462900053+0.971245447370785i, -17.9313890484703+4.48537394908326i, 
22.8331789450432-2.81923657448243i

Frequency Domain representation

enter image description here

The magnitudes of the complex numbers above do not reveal anything that I can infer back to the injected values in the time domain.


Experiment 3

Time Domain Input:

I now took the same waveform and zero padded it i.e. set all samples beyond 41 to zero. So the following is the time domain input:

0, 0.853079823, 0.857877516, 0.603896038, 0.762429734, 0.896260999, 0.695656841,  
0.676188057, 0.928419527, 0.897723205, 0.664562475, 0.765676034, 0.968738879, 
0.802820512, 0.632264626, 0.814329015, 0.875637458, 0.639141079, 0.696479632, 
0.954031849, 0.50925641, -0.50925641, -0.954031849, -0.696479632, -0.639141079, 
-0.875637458, -0.814329015, -0.632264626, -0.802820512, -0.968738879, -0.765676034, 
-0.664562475, -0.897723205, -0.928419527, -0.676188057, -0.695656841, -0.896260999, 
-0.762429734, -0.603896038, -0.857877516, -0.853079823, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

And the waveform:

enter image description here

I took a DFT of these samples based on a Radix 2 algorithm and got these values:

0, 20.0329458083285-9.47487772467906i, -10.5723252177717-8.67648307596821i, 
-8.88751906208901E-002+0.354809649783859i, 3.59322342970171-0.714736578926027i, 
-3.28379151210465-4.42768029850565i, -0.232297876050463+0.434598758428557i, 
1.68672762980862+8.28636148716246E-002i, -1.54927040705738-3.7402696285012i, 
-0.551413356435698+0.608390885175318i, 0.616809338622588+0.187107067289195i, 
-0.458965526924983-3.09409425549091i, -0.966784216252588+0.645984560777537i, 
7.03082277241579E-003+4.21411299459407E-003i, 0.196179960454289-1.99184856512683i, 
-0.919089774378072+0.328855579674163i, 0.222736292145887+0.222736292145884i, 
1.23799833509466-3.45997355924453i, -3.29198268057418+0.324231994037239i, 
-0.495840326552116-0.827259606915814i, -0.434268223171498+0.649928325340974i, 
-1.13740282784196-0.168717771696843i, -8.50255402020411E-002-0.280291642522456i, 
-0.495871287837938+0.449431537929797i, -0.705190861543966-0.292099618913078i, 
-1.8498657760867E-003-3.76548829156425E-002i, -0.56327531746565+0.301076929791613i, 
-0.445444858519027-0.330364422654705i, -2.53084763487132E-002+0.12723430263342i, 
-0.608135034699087+0.152329896227613i, -0.254967975468-0.31067937701979i, 
-0.114451748984804+0.241987891739128i, -0.623647028694518, -0.114451748984793-
0.241987891739111i, -0.254967975467992+0.310679377019776i, -0.608135034699088-
0.152329896227612i, -2.53084763487126E-002-0.127234302633416i, 
-0.445444858519022+0.330364422654704i, -0.563275317465649-0.301076929791616i, 
-1.84986577609081E-003+3.76548829156447E-002i, -0.705190861543962+0.292099618913075i, 
-0.495871287837939-0.449431537929793i, -8.50255402020378E-002+0.280291642522452i, 
-1.13740282784196+0.168717771696845i, -0.434268223171501-0.649928325340972i, 
-0.495840326552115+0.827259606915815i, -3.29198268057417-0.324231994037237i, 
1.23799833509466+3.45997355924453i, 0.222736292145887-0.222736292145884i, 
-0.919089774378077-0.328855579674149i, 0.1961799604543+1.99184856512683i, 
7.03082277241257E-003-4.21411299459534E-003i, -0.966784216252593-0.645984560777534i, 
-0.458965526924974+3.09409425549092i, 0.616809338622592-0.187107067289204i, 
-0.551413356435713-0.608390885175314i, -1.54927040705737+3.74026962850121i, 
1.68672762980861-8.28636148716247E-002i, -0.232297876050455-0.434598758428559i, 
-3.28379151210465+4.42768029850566i, 3.59322342970171+0.714736578926018i, 
-8.88751906209093E-002-0.354809649783852i, -10.5723252177717+8.67648307596825i, 
20.0329458083285+9.47487772467899i 

Frequency Domain Representation

enter image description here

Again, The magnitudes of the complex numbers above do not reveal anything that I can infer back to the injected values in the time domain.


ETA Since the answers here pointed me to windowing, I did another experiment and got the following results after a lot of false starts.

Experiment 4

Time domain representation

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.853079823, 0.857877516, 0.603896038,
0.762429734, 0.896260999, 0.695656841, 0.676188057, 0.928419527, 0.897723205, 
0.664562475, 0.765676034, 0.968738879, 0.802820512, 0.632264626, 0.814329015, 
0.875637458, 0.639141079, 0.696479632, 0.954031849, 0.50925641, -0.50925641, 
-0.954031849, -0.696479632, -0.639141079, -0.875637458, -0.814329015, -0.632264626, 
-0.802820512, -0.968738879, -0.765676034, -0.664562475, -0.897723205, -0.928419527, 
-0.676188057, -0.695656841, -0.896260999, -0.762429734, -0.603896038, -0.857877516, 
-0.853079823, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Looks like:

enter image description here

Hamming Window Coefficients

0.08, 0.082285843, 0.089120656, 0.100436509, 0.116120943, 0.136018076, 0.159930164, 
0.187619556, 0.218811064, 0.253194691, 0.290428719, 0.330143098, 0.371943129, 
0.415413385, 0.460121838, 0.505624157, 0.551468118, 0.597198104, 0.64235963, 
0.686503859, 0.729192067, 0.77, 0.808522089, 0.844375485, 0.877203861, 0.906680953, 
0.932513806, 0.954445679, 0.972258606, 0.985775552, 0.99486218, 0.999428184, 
0.999428184, 0.99486218, 0.985775552, 0.972258606, 0.954445679, 0.932513806, 
0.906680953, 0.877203861, 0.844375485, 0.808522089, 0.77, 0.729192067, 0.686503859, 
0.64235963, 0.597198104, 0.551468118, 0.505624157, 0.460121838, 0.415413385, 
0.371943129, 0.330143098, 0.290428719, 0.253194691, 0.218811064, 0.187619556, 
0.159930164, 0.136018076, 0.116120943, 0.100436509, 0.089120656, 0.082285843, 0.080.08, 
0.082285843, 0.089120656, 0.100436509, 0.116120943, 0.136018076, 0.159930164, 
0.187619556, 0.218811064, 0.253194691, 0.290428719, 0.330143098, 0.371943129, 
0.415413385, 0.460121838, 0.505624157, 0.551468118, 0.597198104, 0.64235963, 
0.686503859, 0.729192067, 0.77, 0.808522089, 0.844375485, 0.877203861, 0.906680953, 
0.932513806, 0.954445679, 0.972258606, 0.985775552, 0.99486218, 0.999428184, 
0.999428184, 0.99486218, 0.985775552, 0.972258606, 0.954445679, 0.932513806, 
0.906680953, 0.877203861, 0.844375485, 0.808522089, 0.77, 0.729192067, 0.686503859, 
0.64235963, 0.597198104, 0.551468118, 0.505624157, 0.460121838, 0.415413385, 
0.371943129, 0.330143098, 0.290428719, 0.253194691, 0.218811064, 0.187619556, 
0.159930164, 0.136018076, 0.116120943, 0.100436509, 0.089120656, 0.082285843, 0.08

Look like this

enter image description here

Their Product (Would it be a simple product only?)

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.354380777, 0.394728179, 0.305344425, 
0.420455691, 0.53524537, 0.446861871, 0.464205711, 0.676996154, 0.691246868, 
0.537313441, 0.646518073, 0.849781485, 0.727902068, 0.589595493, 0.77723281, 
0.851346054, 0.63004965, 0.692901245, 0.953486318, 0.508965209, -0.506639943, 
-0.940461272, -0.677158316, -0.610025441, -0.816544018, -0.738336608, -0.554624971, 
-0.67788196, -0.783246782, -0.589570546, -0.484593685, -0.616290445, -0.596379223, 
-0.403818226, -0.383632569, -0.453171212, -0.350810571, -0.250866497, -0.319081647, 
-0.281638415, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Look Like:

enter image description here

Frequency Domain Representation

1.01978454171002, -1.04956742046721-14.885596686908i, 
0.729587297164687+12.4883097743251i, -0.393281811348907-4.24261013057826i, 
0.761581725234628+3.2398820477072i, -0.876737136684714-3.79393194973719i, 
0.480276094694696+1.88418789653125i, -0.735142602781246-1.8175563772351i, 
1.02811278581892+2.5331069394699i, -0.584707361656586-1.41705783059227i, 
0.642189640425863+1.09157435002371i, -1.08027274688044-1.77950446999262i, 
0.690373934734768+1.16057125940753i, -0.45786262480057-0.586349217392973i, 
0.837117486838485+0.985681387258948i, -0.684335876271999-0.810862267851556i, 
0.930190039748881+0.842491953501215i, -2.11497450796919-1.82531206712061i, 
1.77660184883125+1.59539043421572i, -8.20687157856373E-003-0.123202767234891i, 
-0.280149317662962-0.244195928734504i, -0.313777442633104-0.174757927010731i, 
-5.83069102281942E-002+1.54514819958589E-002i, 0.211135948552966+0.12606544182717i, 
0.227409826380236+7.86489707052085E-002i, 2.49029866186928E-003-3.26908578232317E-002i, 
-0.204885728671642-7.60371335974082E-002i, -0.174609549526536-2.58285031988847E-002i, 
4.55943100777029E-002+3.62216126377679E-002i, 0.205437067084294+3.66474457853982E-002i, 
0.130866115437055-7.39089659931302E-003i, -8.90307098969982E-002-2.75195665163235E-
002i, -0.206016142964952, -8.90307098969848E-002+2.75195665163199E-002i, 
0.130866115437044+7.39089659931835E-003i, 0.205437067084297-3.66474457854036E-002i, 
4.55943100777004E-002-3.62216126377661E-002i, -0.174609549526531+2.58285031988801E-
002i, -0.204885728671643+7.60371335974132E-002i, 2.49029866187001E-
003+3.26908578232264E-002i, 0.227409826380234-7.86489707052067E-002i, 0.21113594855297-
0.126065441827174i, -5.83069102281978E-002-1.54514819958551E-002i, 
-0.313777442633101+0.174757927010727i, -0.280149317662962+0.244195928734507i, 
-8.20687157856043E-003+0.123202767234886i, 1.77660184883125-1.59539043421572i, 
-2.11497450796919+1.82531206712061i, 0.930190039748879-0.842491953501215i, 
-0.684335876271989+0.810862267851559i, 0.837117486838478-0.985681387258952i, 
-0.457862624800567+0.586349217392971i, 0.690373934734765-1.16057125940753i, 
-1.08027274688043+1.77950446999263i, 0.642189640425861-1.09157435002371i, 
-0.584707361656583+1.41705783059227i, 1.02811278581891-2.5331069394699i, 
-0.735142602781236+1.81755637723511i, 0.480276094694689-1.88418789653125i, 
-0.876737136684699+3.79393194973719i, 0.76158172523462-3.2398820477072i, 
-0.393281811348889+4.24261013057827i, 0.729587297164646-12.4883097743252i, 
-1.04956742046715+14.885596686908i

Look Like this:

enter image description here

Are these valid results? Because I still do not seem to be getting anywhere whatsoever!


I did two more experiments and seem to be tantalizingly close to the intended results, but it the solution has the feel of a hack to me.

Experiment 5

So at this point, I have 41 time domain samples representing fundamental + 30% $3rd$ harmonics, 20% $5th$ harmonics, 15% $7th$ harmonics, 10 % $ 9th $ harmonic, and 20% $ 11th $ harmonics.

0, 0.853079823, 0.857877516, 0.603896038, 0.762429734, 0.896260999, 0.695656841, 
0.676188057, 0.928419527, 0.897723205, 0.664562475, 0.765676034, 0.968738879, 
0.802820512, 0.632264626, 0.814329015, 0.875637458, 0.639141079, 0.696479632, 
0.954031849, 0.50925641, -0.50925641, -0.954031849, -0.696479632, -0.639141079, 
-0.875637458, -0.814329015, -0.632264626, -0.802820512, -0.968738879, -0.765676034, 
-0.664562475, -0.897723205, -0.928419527, -0.676188057, -0.695656841, -0.896260999, 
-0.762429734, -0.603896038, -0.857877516, -0.853079823.

I did a linear interpolation and derived 64 samples from the same. They looked like the following:

enter image description here

The frequency domain representation compared to the desired ideal output (First experiment) is as under:

enter image description here

I have stripped off the second half of the sample space as the components fold after the Nyquist limit. There is a little attenuation at the frequencies of interest, but a noise floor is added across the spectrum. Explanations?


Experiment 6

Same as Experiment 5, but 32 interpolated samples.

enter image description here

Frequency domain comparison:

enter image description here

The ratios are correct but magnitudes are halved ! Why?


So I may infer, and I may be wrong(I hope I am), that if the number of samples in a complete waveform period are not a power of 2, the FFT of the same does not reveal anything without some kind of an operation, that eludes me at the moment.

Since I have very little control over the sampling frequency, What are the options open to me so as to get back the values that I injected in the time domain?

$\endgroup$
  • $\begingroup$ Rather then post a great big list of numbers, can you post a graph of the DFT output? It's rather hard to get a rough idea of the output as just a big list of numbers. $\endgroup$ – Fake Name May 25 '12 at 5:53
  • $\begingroup$ Would you like a graph of the magnitudes(Absolute values)? $\endgroup$ – Vaibhav Garg May 25 '12 at 5:56
  • $\begingroup$ Is that fine now? $\endgroup$ – Vaibhav Garg May 25 '12 at 6:06
  • $\begingroup$ I think windowing doesn't work well over just a single period, just like the DFT over 1 period without windowing. There's no trace of your original signal. $\endgroup$ – stevenvh May 25 '12 at 7:17
  • 1
    $\begingroup$ I'm not sure what you're getting at with the bounty. I just see a big pile of plots with some scattered comments and vague questions. Understanding the subtleties of the DFT and windowing will require at least some theoretical study in DSP. I would recommend Lyons' introductory book. Secondly, what is your specific question on implementation of windowing? It's a simple technique, and you would understand best how to implement it in your constrained system. $\endgroup$ – Jason R May 30 '12 at 12:03
12
$\begingroup$

Welcome to windowing. Nothing to do with William G.

The easiest cure which works by brute force burying the errors in noise by using averaging is to sample a large number of cycles so that the boundary conditions do not predominate.

I have not looked at your numerical results, but:

Look at your second and third graphs.
The waveforms that you displayed are the waveforms that are being analysed.
The first example has 2 positive half cycles and one negative one.
I'd expect it to be very strong in 3rd harmonic and reasonablyt so in other odd harmonics and probably with far lower even ones. That's an intuitive guesstimate.
Whatever the result, the transform is (done properly) describing what it sees and what you see.

I'd expect that the second example would be immensely hard to represent well and would need a large number of high frequency components. It is 1/3 +ve, 1/3 -ve and 1/3 zero. It's shard to say how you'd easily get the totally zero right hand output without a large number of nearly equal high frequency terms of about opposite phase cancelling each other out.

SO

The DFT or FFT tells what it sees. You need to feed it integral waveforms of the signal of interest or take special account of the end points. There is a whole artform dedicated to the latter task. Terms like windowing, raised cosine, hamming window (and many more) will start you on your journey.

Wikipedia - windowing Cooley Hann Lanczos Hamming Blackman Kaiser Nutttall and many friends :-)

Probably useful

National Instruments and again here

DFT spectrum analysis

$\endgroup$
  • $\begingroup$ The third one-third of the third waveform has been set to zero forcibly-in excel here, and in firmware during implementation. $\endgroup$ – Vaibhav Garg May 25 '12 at 5:48
  • 5
    $\begingroup$ Forcing part of the signal to zero will just rectangular window the data with a shorter rectangle, which will just convolved the result with a wider Sinc function. $\endgroup$ – hotpaw2 May 25 '12 at 6:56
  • $\begingroup$ @VaibhavGarg - The 0's are in spreadsheet and on your graph. So I assumed they are in your analysis. If so, then the general comments apply. If not then you need to change what you show. $\endgroup$ – Russell McMahon May 25 '12 at 7:00
  • $\begingroup$ @RussellMcMahon Yup- I agree. $\endgroup$ – Vaibhav Garg May 25 '12 at 7:15
  • $\begingroup$ Windowing an integer number of periods aligns the sinc's nulls to the harmonic spacing, which prevents leakage between harmonics when the window spectrum is convolved. Here's a 1024-point DFT (interpolated with zero padding) for experiments 2 & 3 (i.e. 64-point rectangular window vs 41-point rectangular window). The ideal values are plotted as blue dots. Experiment 2 shows spectral leakage (especially at the even harmonics that should be zero), but experiment 3 is correct at the harmonics. $\endgroup$ – Eryk Sun Jun 7 '12 at 7:37
7
$\begingroup$

The FFT results actually do reveal everything about the original injected frequencies. But because the injected frequencies were not exactly periodic in the FFT aperture length, the frequencies have been convolved into Sinc waveforms due to this non-periodic-related windowing, and then resampled. To get the original frequencies back, you may need to deconvolve, interpolate and rescale based on the length of the FFT.

$\endgroup$
  • $\begingroup$ Could you please illustrate the 3 steps? I can send you the excel file with the original samples to play with if you want. $\endgroup$ – Vaibhav Garg May 25 '12 at 5:11
6
$\begingroup$

This is not a complete answer by any means, and I don't expect it to be accepted, but I also think there's significant educational value in this response.

So I may infer, and I may be wrong(I hope I am), that if the number of samples in a complete waveform period are not a power of 2, the FFT of the same does not reveal anything without some kind of an operation, that eludes me at the moment.

You are mostly right. The FFT takes advantage of symmetry of frequency samples along the unit circle in the z-plane:

Generic Unit Circle

If your number of samples is a power of 2, as shown above, you can see symmetry across both the real axis and the imaginary axis. Essentially what the FFT does is use this symmetry to collapse the samples down to 1 quadrant (or less? not sure the details of this symmetry) of the unit circle. This means the FFT only has to do a small number of computations, relative to the entire frequency range.

What you can do with zero-padding is increase the resolution of the FFT by adding zeros to produce a higher power of 2 samples. The symmetry is still there, there's just more samples packed in the unit circle now.

So if you DON'T have a power of 2, less robust FFT's won't zero-pad for you, and you can run into aliasing in your output.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.