Labwork 7

Exercise 1

Recursive-FFT(a) Inverse-FFT(y) 
  1. n = a.length
  2. if n == 1
  3.     return a
  4. ωn = e2πi/n
  5. ω = 1
  6. a[0] = (a0, a2, ..., an - 2)
  7. a[1] = (a1, a3, ..., an - 1)
  8. y[0] = Recursive-FFT(a[0])
  9. y[1] = Recursive-FFT(a[1])
  10. for k = 0 to n/2 - 1
  11.     yk = yk[0] + ωyk[1]
  12.     yk+(n/2) = yk[0] - ωyk[1]
  13.     ω = ωωn
  14. return y
 
  1. n = y.length
  2. if n == 1
  3.     return y
  4. ωn = 1 / e2πi/n
  5. ω = 1
  6. y[0] = (y0, y2, ..., yn - 2)
  7. y[1] = (y1, y3, ..., yn - 1)
  8. a[0] = Inverse-FFT(y[0])
  9. a[1] = Inverse-FFT(y[1])
  10. for k = 0 to n/2 - 1
  11.     ak = ak[0] + ωak[1]
  12.     ak+(n/2) = ak[0] - ωak[1]
  13.     ω = ωωn
  14. for k = 0 to n - 1
  15.     ak = ak / n
  16. return a