home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 326.lha / KFFT_v1.1 / fftasm.doc.pp / fftasm.doc
Text File  |  1990-01-03  |  4KB  |  100 lines
  1.  
  2. FFT.ASM.DOC -- Fast Fourier Transform Assembly code documentation
  3.  
  4. KFFT V1.1 (C)Copyright 1989, Jerry Kallaus.  All rights reserved. 
  5. May be freely redistributed for non-commercial use (FREEWARE).
  6.  
  7.  
  8. Assembly code is optionally used for certain words to significantly
  9. improve the speed of the FFT.  The assembly code for use with JForth
  10. version 2.0 or greater uses the forward assembler.  The assembly code
  11. for use with JForth version 1.2 uses the RPN Assembler.
  12. forward Assembler.  It also uses assembler macros, which precludes
  13. use of the assembler Module.
  14.  
  15. Complex number definitions.
  16. Each complex value occupies 2 cells for the real and imaginary part.
  17. Convention for complex number on stack  is the imaginary part is on top.
  18. Convention for complex number in memory is the real part is at lower addr.
  19.  
  20. In the following, z represents a complex value, r a real value,
  21. and n a fixed point value.
  22.  
  23.  
  24. 2**     ( n -- 2**n     )     Two to nth power
  25. 2CELL+  ( n -- n+2cells )     Increment by 2 cells
  26. 2CELL-  ( n -- n-2cells )     Decrement by 2 cells
  27. 2CELLS  ( n -- n*2cells )     Multiply by 2 cells
  28. 4DUP    ( 1 2 3 4 -- 1 2 3 4 1 2 3 4 )
  29. Z@      ( addr -- z )         Complex fetch
  30. Z!      ( z addr -- )         Complex store
  31. Z+      ( z1 z2 -- z1+z2 )    Complex add
  32. Z-      ( z1 z2 -- z1-z2 )    Complex subtract
  33. Z*      ( z1 z2 -- z1*z2 )    Complex multiply
  34. Z2/     ( z -- z/2 )          Shift z right by 1 binary place
  35. Z/2**N  ( z -- z*2**(-n) )    Shift z right by n binary places
  36. ZNEGATE ( z -- -z )           Complex negate
  37.  
  38. NSBITS  ( n -- m )            Number of significant bits of abs n
  39.                               plus 1 for sign bit.
  40.                               Exception is if n = 0, then result is 0.
  41.                               Example, if -128 < n < 127, result is 8.
  42.  
  43. OR.ABS.ARRAY ( a n -- or'd-cells )  The magnitudes of the n cells of
  44.                               array a are or'd together.  Actually,
  45.                               negative cells are one's complimented
  46.                               prior to or'ing.  This is so that,
  47.                               for example, if all the cells were in
  48.                               the range [-128,127], only the low order
  49.                               7 bits of the relult might be set.
  50.  
  51.  
  52. ASHIFT.ARRAY ( a n m -- )     Arithmetic shift array a of n cells by
  53.                               m bits, left if m > 0, right if m < 0.
  54.  
  55. STATS.ARRAY ( a n -- max min sumlo sumhi )  Determine max, min and sum
  56.                              of array a of length n cells.
  57.  
  58. INNER.LOOP ( u le ss n a i le1 -- hi )   FFT inner loop, where:
  59.                               u   is complex twidle factor.
  60.                               le  is loop byte increment.
  61.                               ss  is stage shift right value.
  62.                               n   is loop-end byte value.
  63.                               le1 is delta byte offset of butterfly pair.
  64.                               hi  is logical or of absolute values of
  65.                                      all real and imaginary parts of
  66.                                      stage output; only used for
  67.                                      auto-scale-fft.
  68.  
  69.  
  70. --------------------------------------------------------------------
  71.  
  72. General Comments.
  73. Registers A0-A1,D0-D3 are assummed trashable.
  74.  
  75. ---------------------------------------------------------------------
  76.  
  77. Inner.loop Complex Multiplies.
  78.  
  79. The following method for performing complex multiplies is used in
  80. the assembler code for the FFT inner.loop.
  81.  
  82. The complex product of two complex numbers is
  83.  
  84.   (a b) (c d)  =  (ac-bd  ad+bc)
  85.  
  86. If we let
  87.  
  88.   z = a(c-d)
  89.   f = a-b
  90.   g = a+b
  91.  
  92. then the complex product is
  93.  
  94.   (fd+z gc-z)
  95.  
  96. Which means that instead of four multiplies and two add ops,
  97. the complex multiply can be done with three multiplies and five
  98. add ops.  For the fft inner-loop, two of the add ops can be
  99. moved outside of the loop.
  100.