home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / TURBO_C / FFT.ARC / README.DOC < prev   
Encoding:
Text File  |  1988-08-07  |  3.9 KB  |  151 lines
  1. I originally saw an FFT program in Byte Magazine many years ago.  I wrote
  2. a version for BASIC that worked pretty good.  Then I thought I'd translate
  3. it into C.  These programs are the result.  I don't do windows though...
  4.  
  5. Needs a graphic interface, but the time escapes me.  Please upload any better
  6. graphic versions.
  7.  
  8. The original Byte Magazine program was designed for real data only.  In my
  9. experiments I needed to preserve both real and imaginary data.  If you feed
  10. the FFT real data only, then the output will be a mirror image, and you can
  11. ignore the left side.
  12.  
  13. For an example try:
  14.  
  15.     gen 16 in
  16.     1000
  17.     3000
  18.  
  19. Which will sample the 1 Khz data every 333 microseconds (1 / 3 Khz).
  20. Note: The sample frequency should be greater than 2 times the input
  21. frequency (Nyquist and all that...).
  22.  
  23. Then run fft.exe like so:
  24.  
  25.     fft 16 in out
  26.  
  27. And you should see a display like so:
  28.  
  29. 0    |=======                      (-1500.0 Hz)
  30. 1    |=====                          (-1312.5 Hz)
  31. 2    |====                          (-1125.0 Hz)
  32. 3    |====                           (-937.0 Hz)
  33. 4    |===                           (-750.0 Hz)
  34. 5    |===                           (-562.5 Hz)
  35. 6    |===                           (-375.0 Hz)
  36. 7    |===                           (-187.5 Hz)
  37. 8    |====        <-------   DC            (000.0 Hz)
  38. 9    |====        <-------   Fundamental        (187.5 Hz)
  39. 10    |======        <-------   Second Harmonic    (375.0 Hz)
  40. 11    |========                    (562.5 Hz)
  41. 12    |==============                    (750.0 Hz)
  42. 13    |========================================================
  43. 14    |============================            (1125.0 Hz)    ^
  44. 15    |===========                    (1312.5 Hz)    |
  45.                                 |
  46.                 [13 - 8 (center)] * 187.5 = 937.0 Hz
  47.  
  48. The fundamental display frequency is:
  49.  
  50.     T  = Time Increment Between Samples
  51.     N  = Number Of Samples
  52.     Tp = N * T
  53.  
  54.     Then F = 1 / Tp
  55.  
  56.     In the example above, the time increment between samples is
  57.     1 / 3000 or 333 microseconds.  N = 16, so Tp = 5333 microseconds
  58.     and 1 / .005333 is 187.5 Hz.
  59.  
  60.     Therefore each filter is a multiple of 187.5 Hertz.  Filter 8 in this
  61.     example is center, so that would be zero, 9 would be one, etc.
  62.  
  63. In this case the sample interval didn't work so good for the frequency and
  64. shows the limitation of the Discrete Fourier Transform in representing a
  65. continuous signal.  A better sample rate for 1000 Hz would be 4000 Hz,
  66. in which case T = 250 ms, Tp = 4 ms, and F = 250 Hz.  1000 / 250 = 4.  The
  67. power should all be in filter 12 (8 + 4) in this case.
  68.  
  69. Let's run it and see:
  70.  
  71.     gen 16 in
  72.     1000
  73.     4000
  74.  
  75.     fft 16 in out
  76.  
  77. 0    |
  78. 1    |
  79. 2    |
  80. 3    |
  81. 4    |
  82. 5    |
  83. 6    |
  84. 7    |
  85. 8    |
  86. 9    |
  87. 10    |
  88. 11    |
  89. 12    |========================================================
  90. 13    |
  91. 14    |
  92. 15    |
  93.  
  94. Well what do you know...
  95.  
  96. The output file data can be used by other programs as needed.
  97.  
  98. By using negative frequencies in gen.exe you can generate opening targets:
  99.  
  100.     gen 16 in
  101.     -1000
  102.     3000
  103.     fft 16 in out
  104.  
  105. Produces:
  106.  
  107. 0    |=======
  108. 1    |===========
  109. 2    |============================
  110. 3    |=======================================================
  111. 4    |==============
  112. 5    |========
  113. 6    |======
  114. 7    |====
  115. 8    |====        <-------- Zero Hertz (DC)
  116. 9    |===
  117. 10    |===
  118. 11    |===
  119. 12    |===
  120. 13    |====
  121. 14    |====
  122. 15    |=====
  123.  
  124. You can see in these examples where weighting functions would be nice.
  125. For an example of what happens when the imaginary data is not input
  126. (ie, zeros put in) for a 1000 Hz frequency at 3000 Hz sample rate:
  127.  
  128. 0    |===============
  129. 1    |==================
  130. 2    |===================================
  131. 3    |========================================================
  132. 4    |===========
  133. 5    |====
  134. 6    |==
  135. 7    |=                Trash this part
  136. ---------------------------------------------------------------------
  137. 8    |
  138. 9    |=
  139. 10    |==
  140. 11    |====
  141. 12    |===========
  142. 13    |=======================================================
  143. 14    |===================================
  144. 15    |==================
  145.  
  146. The left side is redundant and can be deleted.  This is what the original
  147. Byte Magazine article did (December 1978 Issue).
  148.  
  149. Good luck, have fun with it,
  150. Steve Sampson, CompuServe: 75136,626  Unix: sampson@killer.dallas.tx.us
  151.