/****************************************************************** * FFT * Implementation contributed by Remy Muller *****************************************************************/ // twiddle_mult(n) : n parallel cables W(k, n) = 1, (0, ( k, ((2 * PI) / n) : *) : -) : polar_cplx; twiddle_mult(k, n) = _, W(k, n) : pcplx_mul; // butterfly(n) : addition then substraction of interleaved signals : 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); //btf_downside(n) = bus(n) : interleave(n/2,2); // fft(n) : fft matrix function of size n = 2^k //fft(2) = butterfly(2); //fft(n) = butterfly(n) : (fft(n/2) , fft(n/2)); xbutterflies(2) = xbutterfly(2); xbutterflies(n) = (xbutterflies(n/2) , xbutterflies(n/2)) : xbutterfly(n); evens = case { (2) => _ , ! ; (n) => _ , ! , evens(n - 2); }; odds = case { (2) => ! , _ ; (n) => ! , _ , odds(n - 2); }; eo(n) = evens(n), odds(n); shuffling = case { (2) => eo(2); (n) => (evens(n) <: shuffling(n/2)), (odds(n) <: shuffling(n/2)); }; shuffle(n) = bus(n) <: shuffling(n); real2pcplx(n) = par(i, n, (sca2pcplx)); //fft(n) = shuffle(n) : xbutterflies(n); fft(n) = _ <: picks(n) : real2pcplx(n) : shuffle(n) : xbutterflies(n); fftc(n) = _ <: picks(n) : shuffle(n) : xbutterflies(n) : pcplx_moduls(n); // already complex input picks(n) = par(i, n, [i]); concats = case { (1) => vectorize(1); (n) => concats(n-1) # vectorize(1); }; nconcat(n) = concats(n); //fake name for svg block encapsulation pack = case { (1) => _; (n) => pack(n-1), _ : #; }; delays(m) = _ <: par(i, m, @(i)); overlap(n,m) = vectorize(n/m) : delays(m) : pack(m); stops(n) = par(i, n, !);