Click above to get retro games delivered to your door ever month!

      Fourier transforms are an important tool often used in digital
      signal processing. The purpose of the transform is to convert
      information from the time domain to the frequency domain. The
      inverse Fourier transform converts information from the frequency
      domain to the time domain. Implementation of Fourier transforms that
      are computationally efficient are known as fast Fourier transforms
      (FFT's).

      In addition to the shorter processing time on the TMS320C25, an
      addressing feature has been added that enhances radix-2 FFT
      computation and programming. The scrambling of data addressing for
      radix-2 is accomplished by bit reversal.  For an eight point FFT:

                                Bit-Reversed     Bit-Reversed
          Index     Bit Pattern   Pattern           Index
            0           000         000               0
            1           001         100               4
            2           010         010               2
            3           011         110               6
            4           100         001               1
            5           101         101               5
            6           110         011               3
            7           111         111               7

      On the TMS32020, the bit reversal is handled by loading the
      accumulator with pairs of pints that needed to be swapped and then
      storing them back in the swapped locations.  An addressing features
      that uses reverse carry-bit propagation allows the TMS32025 to
      scramble the inputs or outputs while it is performing the I/O.  The
      addressing mode is part of the indirect addressing implemented with
      the auxiliary registers and the associated arithmetic unit.  In this
      mode (a derivative of indexed addressing), a value (index) contained
      in AR0 is either added or subtracted from the auxiliary register
      being pointed to by the ARP.  However, instead of propagating the
      carry bit in the forward direction, it is propagated in the reverse
      direction.  The result is a scrambling in the address access.

      The procedure for generating the bit-reversal address sequence is
      to load AR0 with a value corresponding to one-half the length of the
      FFT and to load another auxiliary register, e.g., AR1, with the base
      address of the data array.  Implementations of FFTs involve complex
      arithmetic; as a result, there are two data memory locations (one
      real and one imaginary) associated with every data sample.
      Generally, the samples are stored in memory in pairs with the real
      part in the even address locations and the imaginary part in the odd
      address location.  This means that the offset from the base address
      for any given sample is twice the sample index.  REal input data is
      easily transferred into the data memory and stored in the scrambled
      order, with every other location in the data memory representing the
      imaginary part of the data.

      The following list shows the contents of auxiliary register AR1 when
      AR0 is initialize with a value of 9 (8-point FFT) and when data is
      being transferred by the code that follows.

            MSB                               LSB

      AR0   0 0 0 0   0 0 0 0   0 0 0 0   1 0 0 0   8-Point FFT
      AR1   0 0 0 0   0 0 1 0   0 0 0 0   0 0 0 0   Base Address

            RPTK  7
            IN    *BR0+,PA0

      AR1   0 0 0 0   0 0 1 0   0 0 0 0   0 0 0 0   XR(0)
      AR1   0 0 0 0   0 0 1 0   0 0 0 0   1 0 0 0   XR(4)
      AR1   0 0 0 0   0 0 1 0   0 0 0 0   0 1 0 0   XR(2)
      AR1   0 0 0 0   0 0 1 0   0 0 0 0   1 1 0 0   XR(6)
      AR1   0 0 0 0   0 0 1 0   0 0 0 0   0 0 1 0   XR(1)
      AR1   0 0 0 0   0 0 1 0   0 0 0 0   1 0 1 0   XR(5)
      AR1   0 0 0 0   0 0 1 0   0 0 0 0   0 1 1 0   XR(3)
      AR1   0 0 0 0   0 0 1 0   0 0 0 0   1 1 1 0   XR(7)

************************************************************
*           AN 8-POINT DIT FFT                             *
************************************************************
*
X0R:   .set 00
X0I:   .set 01
X1R:   .set 02
X1I:   .set 03
X2R:   .set 04
X2I:   .set 05
X3R:   .set 06
X3I:   .set 07
X4R:   .set 08
X4I:   .set 09
X5R:   .set 10
X5I:   .set 11
X6R:   .set 12
X6I:   .set 13
X7R:   .set 14
X7I:   .set 15
W:     .set 16
WVALUE .set 05a82h       ; value for sin(45) or cos(45)
*
ZERO   $MACRO    PR,PI,QR,QI
*
*      CALCULATE Re[P+Q] AND Re[P-Q]
*
       LAC     :PR:,15   ;ACC := (1/2)(PR)
       ADD     :QR:,15   ;ACC := (1/2)(PR+QR)
       SACH    :PR:      ;PR  := (1/2)(PR+QR)
       SUBH    :QR:      ;ACC := (1/2)(PR+QR)-(QR)
       SACH    :QR:      ;QR  := (1/2)(PR-QR)
*
*      CALCULATE Im[P+Q] AND Im[P-Q]
*
       LAC     :PI:,15   ;ACC := (1/2)(PI)
       ADD     :QI:,15   ;ACC := (1/2)(PI+QI)
       SACH    :PI:      ;PI  := (1/2)(PI+QI)
       SUBH    :QI:      ;ACC := (1/2)(PI+QI)-(QI)
       SACH    :QI:      ;QI  := (1/2)(PI-QI)
       $END
*
PIBY2  $MACRO    PR,PI,QR,QI
*
*      CALCULATE Re[P+jQ] AND Re[P-jQ]
*
       LAC     :PI:,15   ;ACC := (1/2)(PI)
       SUB     :QR:,15   ;ACC := (1/2)(PI-QR)
       SACH    :PI:      ;PI  := (1/2)(PI-QR)
       ADDH    :QR:      ;ACC := (1/2)(PI-QR)+(QR)
       SACH    :QR:      ;QR  := (1/2)(PI+QR)
*
*      CALCULATE Im[P+jQ] AND Im[P-jQ]
*
       LAC     :PR:,15   ;ACC := (1/2)(PR)
       ADD     :QI:,15   ;ACC := (1/2)(PR+QI)
       SACH    :PR:      ;PR  := (1/2)(PR+QI)
       SUBH    :QI:      ;ACC := (1/2)(PR+QI)-(QI)
       DMOV    :QR:      ;QR  -> QI
       SACH    :QR:      ;QR  := (1/2)(PR-QI)
       $END
*
PIBY4  $MACRO    PR,PI,QR,QI,W
*
       LT      :W:       ;T-REGISTER :=W=COS(PI/4)=SIN(PI/4)
       LAC     :QI:,14   ;ACC := (1/4)(QI)
       SUB     :QR:,14   ;ACC := (1/4)(QI-QR)
       SACH    :QI:,1    ;QI  := (1/2)(QI-QR)
       ADD     :QR:,15   ;ACC := (1/4)(QI+QR)
       SACH    :QR:,1    ;QR  := (1/2)(QI+QR)
       LAC     :PR:,14   ;ACC := (1/4)(PR)
       MPY     :QR:      ;P-REGISTER := (1/4)(QI+QR)*W
       APAC              ;ACC := (1/4)[PR+(QI+QR)*W]
       SACH    :PR:,1    ;PR  := (1/2)[PR+(QI+QR)*W]
       SPAC              ;ACC := (1/4)(PR)
       SPAC              ;ACC := (1/4)[PR-(QI+QR)*W]
       SACH    :QR:,1    ;QR  := (1/2)[PR-(QI+QR)*W]
       LAC     :PI:,14   ;ACC := (1/4)(PI)
       MPY     :QI:      ;P-REGISTER := (1/4)(QI-QR)*W
       APAC              ;ACC := (1/4)[PI+(QI-QR)*W]
       SACH    :PI:,1    ;PI  := (1/2)[PI+(QI-QR)*W]
       SPAC              ;ACC := (1/4)(PI)
       SPAC              ;ACC := (1/4)[PI-(QI-QR)*W]
       SACH    :QI:,1    ;QI  := (1/2)[PI-(QI-QR)*W]
       $END
*
PI3BY4       $MACRO    PR,PI,QR,QI,W
*
       LT      :W:       ;T-REGISTER :=W=COS(PI/4)=SIN(PI/4)
       LAC     :QI:,14   ;ACC := (1/4)(QI)
       SUB     :QR:,14   ;ACC := (1/4)(QI-QR)
       SACH    :QI:,1    ;QI  := (1/2)(QI-QR)
       ADD     :QR:,15   ;ACC := (1/4)(QI+QR)
       SACH    :QR:,1    ;QR  := (1/2)(QI+QR)
       LAC     :PR:,14   ;ACC := (1/4)(PR)
       MPY     :QI:      ;P-REGISTER := (1/4)(QI-QR)*W
       APAC              ;ACC := (1/4)[PR+(QI-QR)*W]
       SACH    :PR:,1    ;PR  := (1/2)[PR+(QI-QR)*W]
       SPAC              ;ACC := (1/4)(PR)
       SPAC              ;ACC := (1/4)[PR-(QI-QR)*W]
       MPY     :QR:      ;P-REGISTER := (1/4)(QI+QR)*W
       SACH    :QR:,1    ;QR  := (1/2)[PR-(QI-QR)*W]
       LAC     :PI:,14   ;ACC := (1/4)(PI)
       SPAC              ;ACC := (1/4)[PI-(QI+QR)*W]
       SACH    :PI:,1    ;PI  := (1/2)[PI-(QI+QR)*W]
       APAC              ;ACC := (1/4)(PI)
       APAC              ;ACC := (1/4)[PI+(QI+QR)*W]
       SACH    :QI:,1    ;QI  := (1/2)[PI+(QI+QR)*W]
       $END
*
COMBO  $MACRO    R1,I1,R2,I2,R3,I3,R4,I4
*
*      CALCULATE PARTIAL TERMS FOR R3,R4,I3 AND I4
*
       LAC     :R3:,14   ;ACC := (1/4)(R3)
       ADD     :R4:,14   ;ACC := (1/4)(R3+R4)
       SACH    :R3:,1    ;R3  := (1/2)(R3+R4)
       SUB     :R4:,15   ;ACC := (1/4)(R3+R4)-(1/2)(R4)
       SACH    :R4:,1    ;R4  := (1/2)(R3-R4)
       LAC     :I3:,14   ;ACC := (1/4)(I3)
       ADD     :I4:,14   ;ACC := (1/4)(I3+I4)
       SACH    :I3:,1    ;I3  := (1/2)(I3+I4)
       SUB     :I4:,15   ;ACC := (1/4)(I3+I4)-(1/2)(I4)
       SACH    :I4:,1    ;I4  := (1/2)(I3-I4)
*
*      CALCULATE PARTIAL TERMS FOR R2,R4,I2 AND I4
*
       LAC     :R1:,14   ;ACC := (1/4)(R1)
       ADD     :R2:,14   ;ACC := (1/4)(R1+R2)
       SACH    :R1:,1    ;R1  := (1/2)(R1+R2)
       SUB     :R2:,15   ;ACC := (1/4)(R1+R2)-(1/2)(R2)
       ADD     :I4:,15   ;ACC := (1/4)[(R1-R2)+(I3-I4)]
       SACH    :R2:      ;R2  := (1/4)[(R1-R2)+(I3-I4)]
       SUBH    :I4:      ;ACC := (1/4)[(R1-R2)-(I3-I4)]
       DMOV    :R4:      ;I4  := R4 = (1/2)(R3-R4)
       SACH    :R4:      ;R4  := (1/4)[(R1-R2)-(I3-I4)]
       LAC     :I1:,14   ;ACC := (1/4)(I1)
       ADD     :I2:,14   ;ACC := (1/4)(I1+I2)
       SACH    :I1:,1    ;I1  := (1/2)(I1+I2)
       SUB     :I2:,15   ;ACC := (1/4)(I1+I2)-(1/2)(I2)
       SUB     :I4:,15   ;ACC := (1/4)[(I1-I2)-(R3-R4)]
       SACH    :I2:      ;I2  := (1/4)[(I1-I2)-(R3-R4)]
       ADDH    :I4:      ;ACC := (1/4)[(I1-I2)+(R3-R4)]
       SACH    :I4:      ;I4  := (1/4)[(I1-I2)+(R3-R4)]
*
*      CALCULATE PARTIAL TERMS FOR R1,R3,I1 AND I3
*
       LAC     :R1:,15   ;ACC := (1/4)(R1+R2).
       ADD     :R3:,15   ;ACC := (1/4)[(R1+R2)+(R3+R4)]
       SACH    :R1:      ;R1  := (1/4)[(R1+R2)+(R3+R4)]
       SUBH    :R3:      ;ACC := (1/4)[(R1+R2)-(R3+R4)]
       SACH    :R3:      ;R3  := (1/4)[(R1+R2)-(R3+R4)]
       LAC     :I1:,15   ;ACC := (1/4)(I1+I2)
       ADD     :I3:,15   ;ACC := (1/4)[(I1+I2)+(I3+I4)]
       SACH    :I1:      ;I1  := (1/4)[(I1+I2)+(I3+I4)]
       SUBH    :I3:      ;ACC := (1/4)[(I1+I2)-(I3+I4)]
       SACH    :I3:      ;I3  := (1/4)[(I1+I2)-(I3+I4)]
       $END
*
* INITIALIZE FFT PROCESSING
*
FFT    SPM  0            ; no shift of PR output
       SSXM              ; set sign extension mode
       ROVM              ; reset overflow mode
       LDPK 4            ; set data page pointer to 4
       LALK WVALUE       ; get twiddle factor value
       SACL W            ; store sin(45) or cos(45) in W
*
* INPUT SAMPLES, STORING IN BIT-REVERSED ORDER
*
       LARK AR0,8        ; load length of FFT in AR0
       LRLK AR1,0200h    ; load AR1 with data page 4 address
       LARP AR1
       RPTK 7
       IN   *BR0+,PA0    ; only real valued input
*
* FIRST & SECOND STAGES COMBINED WITH DIVIDE-BY-4 INTERSTAGE SCALING
*
       COMBO      X0R,X0I,X1R,X1I,X2R,X2I,X3R,X3I
       COMBO      X4R,X4I,X5R,X5I,X6R,X6I,X7R,X7I
*
* THIRD STAGE WITH DIVIDE-BY-2 INTERSTAGE SCALING
*
       ZERO       X0R,X0I,X4R,X4I
       PIBY4      X1R,X1I,X5R,X5I,W
       PIBY2      X2R,X2I,X6R,X6I
       PI3BY4     X3R,X3I,X7R,X7I,W
*
* OUTPUT SAMPLES, SUPPLYING IN SEQUENTIAL ORDER
*
       LRLK AR1,0200h    ; load AR1 with data page 4 address
       RPTK 15
       OUT  *+,PA0       ; complex valued output
       RET