home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume1 / 8707 / 70 / fft.doc < prev   
Encoding:
Text File  |  1990-07-13  |  3.1 KB  |  77 lines
  1.         Documentation for fft.c
  2.  
  3.     This program is a direct translation from FORTRAN IV of E. O. Brigham's
  4. program on the fast Fourier transform, The Fast Fourier Transform.  I suggest
  5. reading the book, to get the details of the method.  
  6.  
  7.     In translating this program from FORTRAN, I retained the bit swapping
  8. function described by Brigham.  Using bit operators, I assume that a more 
  9. efficient manner of bit swapping can be performed.  
  10.  
  11.     I used pointers to the data to be transformed to allow the routine to
  12. be more general.  Thus fft() needs to know the number of data points when it is
  13. called which is only limited by memory size, which can get used up quickly 
  14. since each point is represented by two 8-byte numbers.  A solution might be to 
  15. hold the data on disk and use disk access functions, if you run out of memory
  16. for the data.  This method should be avoided for small data sets, since the
  17. calculation time increases dramatically with more data points to transform.
  18. With disk overhead, calculation time will slow down considerably.  To save
  19. memory space you can redefine the variable types from double to single
  20. precision at the expense of precision.
  21.  
  22.     I have compared the performance of the fft to a regular Fourier trans-
  23. form, and the fft wins out especially when there are more than 512 data points.
  24. The restriction of having the data be a multiple of 2 is usually not prohibi-
  25. tive since the data usually are generated by a computer in base 2, eg. radio
  26. astronomy (my original purpose for writing this program), image analysis, etc.
  27.  
  28.     Enclosed is some sample data and its transform.  Use this to debug the
  29. program if necessary ( I hate to receive a data analysis program with no data 
  30. to test the program ).  These data have been checked for correctness by using
  31. a standard FFT from a mainframe computer math library.
  32.  
  33.     Finally if you have any questions or suggestions, please contact me:
  34.  
  35.             Jim Pisano
  36.             P.O. Box 3134
  37.             Charlottesville, VA 22903
  38.  
  39.     Or contact aeusemrs@csun.uucp (Mike Stump).
  40.  
  41.             INPUT                   OUTPUT
  42. index        real        imaginary    real        imaginary
  43. _____________________________________________________________________________
  44.  
  45.  1        -28.66        0.0        -00.11        0.0
  46.  2        -32.43        0.0        -29.98644    -38.211
  47.  3        -8.42        0.0        -62.32944    -23.91025
  48.  4        40.22        0.0        -58.32872    -10.02253
  49.  5         1.14        0.0        -58.46804    -7.78748
  50.  6        -25.05        0.0        -68.11068    -5.28995
  51.  7        12.14        0.0        -86.80929    -11.77746
  52.  8        27.82        0.0        -137.68        -0.06883
  53.  9        2.4        0.0        -33.03304    202.24
  54. 10        -19.68        0.0        82.43765    72.43995
  55. 11        7.55        0.0        25.90461    18.1517
  56. 12        17.22        0.0        8.26912        6.555
  57. 13        -0.58        0.0        -4.33195    3.91253
  58. 14        -12.5        0.0        -8.54575    -11.5672
  59. 15        0.89        0.0        -20.32586    -3.86289
  60. 16        10.45        0.0        -8.05521    10.74816
  61. 17        -1.16        0.0        1.77        0.0
  62. 18        -7.06        0.0        -8.0552        -10.74816
  63. 19        -0.23        0.0        -20.32586    3.86289
  64. 20        4.59        0.0        -8.54575    11.5672
  65. 21        1.45        0.0        -4.33195    -3.91253
  66. 22        -3.4        0.0        8.26913        -6.55501
  67. 23        3.03        0.0        25.9046        -18.15169
  68. 24        3.05        0.0        82.43763    -72.43996
  69. 25        3.67        0.0        -33.02996    -202.24
  70. 26        -0.51        0.0        -137.68        0.06884
  71. 27        -4.35        0.0        -86.80931    11.77746
  72. 28        -1.45        0.0        -68.11066    5.28995
  73. 29        5.64        0.0        -58.46805    7.78747
  74. 30        -0.96        0.0        -58.32872    10.02253
  75. 31        -4.46        0.0        -62.32945    23.91205
  76. 32        -1.25        0.0        -29.98643    38.21101
  77.