dsp_files/fft.lib.dsp

   1 /******************************************************************
   2  *  FFT
   3  *  Implementation contributed by Remy Muller
   4  *****************************************************************/
   5
   6 // bus(n) : n parallel cables
   7 bus(2) = _,_; // avoids a lot of "bus(1)" labels in block diagrams
   8 bus(n) = par(i, n, _);
   9
  10 // twiddle_mult(n) : n parallel cables
  11
  12 W(k, n) = 1, (0, ( k, ((2 * PI) / n) : *) : -) : polar_cplx;
  13
  14 twiddle_mult(k, n) = _, W(k, n) : pcplx_mul;
  15
  16 // selector(i,n) : select ith cable among n
  17 selector(i,n) = par(j, n, S(i, j))    with { S(i,i) = _; S(i,j) = !; };
  18
  19 // interleave(m,n) : interleave m*n cables : x(0), x(m), x(2m), ..., x(1),x(1+m), x(1+2m)...
  20 //interleave(m,n) = bus(m*n) <: par(i, m, par(j, n, selector(i+j*m,m*n)));
  21
  22 // interleave(row,col) : interleave row*col cables from column order to row order.
  23 // input : x(0), x(1), x(2) ..., x(row*col-1)
  24 // output: x(0+0*row), x(0+1*row), x(0+2*row), ..., x(1+0*row), x(1+1*row), x(1+2*row), ...
  25 interleave(row,col) = bus(row*col) <: par(r, row, par(c, col, selector(r+c*row,row*col)));
  26
  27 // butterfly(n) : addition then substraction of interleaved signals :
  28 xbutterfly(n) = (bus(n/2), par(k, n/2, twiddle_mult(k, n))) <: interleave(n/2,2), interleave(n/2,2) : par(i, n/2, pcplx_add), par(i, n/2, pcplx_sub);
  29
  30 //btf_downside(n) = bus(n) : interleave(n/2,2);
  31
  32 // fft(n) : fft matrix function of size n = 2^k
  33 //fft(2) = butterfly(2);
  34 //fft(n) = butterfly(n) : (fft(n/2) , fft(n/2));
  35
  36 xbutterflies(2) = xbutterfly(2);
  37 xbutterflies(n) = (xbutterflies(n/2) , xbutterflies(n/2)) : xbutterfly(n);
  38
  39
  40 evens = case {
  41         (2) => _ , ! ;
  42         (n) => _ , ! , evens(n - 2);
  43 };
  44 odds = case {
  45         (2) => ! , _ ;
  46         (n) => ! , _ , odds(n - 2);
  47 };
  48
  49 eo(n) = evens(n), odds(n);
  50
  51 shuffling = case {
  52         (2) => eo(2);
  53         (n) => (evens(n) <: shuffling(n/2)), (odds(n) <: shuffling(n/2));
  54 };
  55
  56 shuffle(n) = bus(n) <: shuffling(n);
  57
  58 real2pcplx(n) = par(i, n, (sca2pcplx));
  59
  60 //fft(n) =  shuffle(n) : xbutterflies(n);
  61 fft(n) = _ <: picks(n) : real2pcplx(n) : shuffle(n) : xbutterflies(n);
  62 fftc(n) = _ <: picks(n) : shuffle(n) : xbutterflies(n) : pcplx_moduls(n); // already complex input
  63
  64
  65 picks(n) = par(i, n, [i]);
  66
  67 concats = case {
  68         (1) => vectorize(1);
  69         (n) => concats(n-1) # vectorize(1);
  70 };
  71
  72 nconcat(n) = concats(n); //fake name for svg block encapsulation
  73
  74 pack = case {
  75         (1) => _;
  76         (n) => pack(n-1), _ : #;
  77 };
  78
  79 delays(m) = _ <: par(i, m, @(i));
  80
  81 overlap(n,m) = vectorize(n/m) : delays(m) : pack(m);
  82
  83 stops(n) = par(i, n, !);