41Z Routine of the week: DFT

[Ángel Martin]

Discrete Fourier Transform with the 41Z Module.

Not much of a groundbreaking algorithm, the program below uses the straightforward definition to obtain the DFT and inverse DFT of a set of N complex data points, stored in complex data registers ZR01 to ZR0n. You can use the sub-function ZINPT from the module to enter all values.

Just enter the sample size in X, and execute ZDFT. The results are stored in complex registers ZRn+1 to ZR(2n). You can use the sub-function ZOUPT to see the values.

If you want to apply the inverse DFT to the results you can use REGSWAP to reset the locations: 2,00(2+2n)00(2n). i.e. 2,010|008 for n=4. Then run ZIDFT to obtain the original values (except rounding).

Example:

DFT [ 1+2i ; 3+4i ; 5+6i ; 7+8i ] = [ 16+20.i ; -8 ; -4-4.i ; -8.i ]

IDFT [ 16+20.i ; -8 ; -4-4.i ; -8.i ] = [ 1+2i ; 3+4i ; 5+6i ; 7+8i ]

Code:

01   LBL "ZDFT" 
02   CF 01
03   GTO 02
04   LBL "ZIDFT"
05   SF 01
06   LBL 02
07   STO N
08   E3/E+
09   STO M
10   LBL 01
11   VIEW M
12   CLX
13   STO 00
14   STO 01
15   RCL N
16   E3/E+
17   STO O
18   RCL M
19   INT 
20   E
21   -
22   PI
23   *
24   ST+ X
25   RCL N
26   /
27   STO P
28   LBL 00
29   RCL O
30   INT
31   E
32   -
33   RCL P
34   *
35   FC? 01
36   CHS
37   1
38   P-R
39   ZRC* IND O
40   ZST+ 00
41   ISG O
42   GTO 00
43   RCL M
44   INT
45   RCL N
46   +
47   ZRCL 00
48   FC? 01
40   GTO 02
41   RCL N
42   ST/ Z
43   /
44   LBL 02
45   ZSTO IND Z
46   ISG M
47   GTO 01
48   END

As always, the execution time can be rather long for large size samples. Using the 41-CL or an emulator in Turbo mode is recommended.
Feedback is welcome - would be great to get an FFT implementation as well... any volunteers?