// // Programmer: Craig Stuart Sapp // Creation Date: Fri Feb 7 00:44:33 PST 1997 // Last Modified: Thu Feb 12 20:17:59 GMT-0800 1998 // Filename: ...sig/maint/code/utilities/transforms/transforms-private.cc // Web Address: http://sig.sapp.org/src/sig/transforms-private.cpp // Syntax: C++ // // Description: Private helper functions for the Transforms.cc file. // Many of these functions are taken from: // Ofranidis, Sophocles J. "Introduction to Signal Processing", // Prentice Hall, 1996. page 520. // #include "transforms-private.h" #include "Block.h" #include "ComplexD.h" #include ////////////////////////////// // // fft_destructive -- // void fft_destructive(Block& X) { shuffle(X); // bit reversal dftmerge(X); // merging of DFTs } ////////////////////////////// // // ifft_destructive -- // void ifft_destructive(Block& X) { int N = X.getSize(); int k; for (k=0; k& X) { int n, r; int N = X.getSize(); int B = 1; // number of bits while ( (N >> B) > 0 ) { B++; } B--; // N = 2**B for (n=0; n=0; m--) { // B is the number of digits if ((n>>m)==1) { // if 2**m term is present r += two(B-1-m); // add 2**(B-1-m) to r n -= two(m); // subtract 2**m from n } } return r; } ////////////////////////////// // // makeComplex -- make a Complex number given the real and imaginary parts. // ComplexD makeComplex(double realPart, double imagPart) { ComplexD output(realPart, imagPart); return output; } ////////////////////////////// // // cexp -- complex exponential // ComplexD cexp(ComplexD Z) { double R = exp(Z.re()); ComplexD output(R * cos(Z.im()), R * sin(Z.im())); return output; } ////////////////////////////// // // dftmerge -- put DFTs back together // void dftmerge(Block& XF) { int N = XF.getSize(); double pi = 4.0 * atan(1.0); int k, i, p, q, M; ComplexD A, B, V, W; M = 2; while (M <= N) { // two (M/2)-DFT's into one M-DFT W = cexp(makeComplex(0.0, -2 * pi / M)); // order-M twiddle factor V = makeComplex(1., 0.); // successive powers of W for (k=0; k> i) & 0x00000001; } return (sum == 1); } // md5sum: 063191a89db477caf2af07af44d98a8d transforms-private.cpp [20010708]