IIRC, an inverse FFT can be implemented as 1. Complex conjugate 2. Fft 3. Complex conjugate
Which is mathematically identical iirc to an ifft, if slightly less efficient computationally. In general, the output will not be real valued of course On Tue, Dec 9, 2014, 2:45 PM Jonathan Weintroub <jweintr...@cfa.harvard.edu> wrote: > Thanks to Richard and everyone who responded earlier for the comments, > which in some cases are very detailed. It is good to know we are not the > only ones worrying about this. Our DSP group is digesting the material and > looking at options, and other followup will likely follow. I did not want > to delay thanks and acknowledgment. > > One basic question which did come up is it appears that even an inverse > FFT would present some challenges. We stuff the 32k forward FFT with real > time series data and extract 16k complex frequency domain points. Might I > ask if any CASPER folks have experience implementing an inverse FFT > relevant to this case, as a real time FPGA bit code? > > Thanks again. > > Jonathan Weintroub > SAO > > > > On Dec 8, 2014, at 9:50 PM, Richard Shaw <jr...@cita.utoronto.ca> wrote: > > > > Hi, > > > > I thought I'd comment as this is a problem we've been having to deal > > with recently for some VLBI observations. Fortunately we've had some > > success with an offline least-squares inversion of the PFB. This is > > probably not the scheme that you want, as it essentially operates on > > the whole PFB'd timestream at once, so realistically you need a > > cluster to do it. However, there is prototype code available here [1] > > if it's useful. > > > > The rationale for doing this is is that when you look at the whole PFB > > timestream very little information is actually lost (essentially only > > a few samples at the ends), though it may be spread across frequency > > and time samples. For N PFB samples of length M, there are roughly > > 2*N*M total numbers measured, which depend on 2*(N+P-1)*M numbers in > > the underlying timestream (where P is the number of taps). As > > typically P << N, there are very few unmeasured linear combinations, > > and so a statistical inversion can be pretty accurate. Fortunately it > > turns out this inversion can also be done pretty efficiently. > > > > The general scheme is this: > > > > 1. inverse FFT to generate a pseudo-timestream > > 2. the coupling matrix between elements in this pseudo-timestream and > > the real timestream is sparse diagonal, and is trivially calculable > > from the window function > > 3. Perform a shuffle on the timstream to turn this into a series of > > band diagonal matrices (bandwidth ~ 2*P) > > 4. Use a band diagonal least-squares solve to invert the > > pseudo-timestream back to the underlying timestream. > > > > A fuller description is here [2]. > > > > The complexity is O(N), and as the inversion breaks into blocks it > > parallelises pretty trivially up to M processes (where M is the number > > of samples in the window function). > > > > We did look at some iterative ways that step through the PFB > > timestream, but they seem to accumulate errors as they go, and become > > horribly inaccurate very quickly. This avoids it by treating the whole > > timestream at once. Your accuracy improves the longer the length you > > use at once. > > > > Juan Mena Parra and Kevin Bandura (cc'd) have also been looking at > > what would need to change about the PFB to make it more easily > > invertible in a streaming fashion (rather than having to touch the > > whole timestream at once). My memory is that changing the window > > functions seems to be a big help, so hopefully one of them could chime > > in to clarify that. > > > > Anyway, hope that is of some help, > > Richard > > > > [1]: http://github.com/jrs65/pfb-inverse/ > > [2]: http://nbviewer.ipython.org/github/jrs65/pfb-inverse/blob/ > master/notes.ipynb > > > > >