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
Wrap
Text File
|
1990-01-03
|
4KB
|
100 lines
FFT.ASM.DOC -- Fast Fourier Transform Assembly code documentation
KFFT V1.1 (C)Copyright 1989, Jerry Kallaus. All rights reserved.
May be freely redistributed for non-commercial use (FREEWARE).
Assembly code is optionally used for certain words to significantly
improve the speed of the FFT. The assembly code for use with JForth
version 2.0 or greater uses the forward assembler. The assembly code
for use with JForth version 1.2 uses the RPN Assembler.
forward Assembler. It also uses assembler macros, which precludes
use of the assembler Module.
Complex number definitions.
Each complex value occupies 2 cells for the real and imaginary part.
Convention for complex number on stack is the imaginary part is on top.
Convention for complex number in memory is the real part is at lower addr.
In the following, z represents a complex value, r a real value,
and n a fixed point value.
2** ( n -- 2**n ) Two to nth power
2CELL+ ( n -- n+2cells ) Increment by 2 cells
2CELL- ( n -- n-2cells ) Decrement by 2 cells
2CELLS ( n -- n*2cells ) Multiply by 2 cells
4DUP ( 1 2 3 4 -- 1 2 3 4 1 2 3 4 )
Z@ ( addr -- z ) Complex fetch
Z! ( z addr -- ) Complex store
Z+ ( z1 z2 -- z1+z2 ) Complex add
Z- ( z1 z2 -- z1-z2 ) Complex subtract
Z* ( z1 z2 -- z1*z2 ) Complex multiply
Z2/ ( z -- z/2 ) Shift z right by 1 binary place
Z/2**N ( z -- z*2**(-n) ) Shift z right by n binary places
ZNEGATE ( z -- -z ) Complex negate
NSBITS ( n -- m ) Number of significant bits of abs n
plus 1 for sign bit.
Exception is if n = 0, then result is 0.
Example, if -128 < n < 127, result is 8.
OR.ABS.ARRAY ( a n -- or'd-cells ) The magnitudes of the n cells of
array a are or'd together. Actually,
negative cells are one's complimented
prior to or'ing. This is so that,
for example, if all the cells were in
the range [-128,127], only the low order
7 bits of the relult might be set.
ASHIFT.ARRAY ( a n m -- ) Arithmetic shift array a of n cells by
m bits, left if m > 0, right if m < 0.
STATS.ARRAY ( a n -- max min sumlo sumhi ) Determine max, min and sum
of array a of length n cells.
INNER.LOOP ( u le ss n a i le1 -- hi ) FFT inner loop, where:
u is complex twidle factor.
le is loop byte increment.
ss is stage shift right value.
n is loop-end byte value.
le1 is delta byte offset of butterfly pair.
hi is logical or of absolute values of
all real and imaginary parts of
stage output; only used for
auto-scale-fft.
--------------------------------------------------------------------
General Comments.
Registers A0-A1,D0-D3 are assummed trashable.
---------------------------------------------------------------------
Inner.loop Complex Multiplies.
The following method for performing complex multiplies is used in
the assembler code for the FFT inner.loop.
The complex product of two complex numbers is
(a b) (c d) = (ac-bd ad+bc)
If we let
z = a(c-d)
f = a-b
g = a+b
then the complex product is
(fd+z gc-z)
Which means that instead of four multiplies and two add ops,
the complex multiply can be done with three multiplies and five
add ops. For the fft inner-loop, two of the add ops can be
moved outside of the loop.