dave, jack, jonathan, going back to august emails, here's another trick to computing an inverse FFT from a forward FFT.
the usual technique to implement a inverse complex FFT from an complex forward FFT: 1) complex conjugate the input 2) complex forward FFT 3) complex conjugate the output 4) scale if needed (perhaps by 1/N, or 1/sqrt(N), depending on your forward FFT scale factor here's an easier way to do it: 1) swap the real and imaginary on on the input complex data 2) complex forward FFT 3) swap the real and imaginary on on the output complex data 4) scale if needed (by 1/N, or 1/sqrt(N), depending on your forward FFT scale factor stolen from richard lyons, intro to dsp, sections 10.6.1, and 10.6.2 dan On Tue, Aug 14, 2018 at 3:01 PM Jack Hickish <jackhick...@gmail.com> wrote: > While we're on this fun topic... > > The biplex FFT which Dave mentions does all the 2 x real = 1 x complex > tricks. However, in the fft_wideband_real block, this is followed by a > parallel FFT direct block which doesn't have any of these optimizations, > and is thus ~2x bigger than it needs to be. > This probably wasn't a big concern when the block was designed, and the > fastest sample rates were ~4x the FPGA clock rate, so the direct FFT inside > the fft_wideband_real was a relatively small contribution to resource use. > Looking ahead to 10+ GHz ADCs this might cease to be the case - it's > probably worth building some of the real-input optimizations into this > block as well. I believe Ryan Monroe's version of the FFT ( > https://www.worldscientific.com/doi/abs/10.1142/S2251171716410026?journalCode=jai) > might do this (as well as a whole bunch of other tricks). > > It would be great for someone to look at this further and maybe (cough) > work some optimizations into a new non-simulink-based FFT library.... :) > > Jack > > On Tue, 14 Aug 2018 at 22:15 David MacMahon <dav...@berkeley.edu> wrote: > >> Hi, Jonathan, >> >> The biplex FFT has two complex inputs and two complex outputs. The two >> input signals are presented "in parallel" (i.e. simultaneously) one sample >> per input per FPGA cycle, but the output spectra appear serially (i.e. one >> signal's spectrum followed by the other signal's spectrum) two frequency >> channels per FPGA cycle. This block and its various sub-blocks comprise >> the basic FFT functionality of the CASPER library. All the other FFT >> blocks exist to perform various "tricks" to perform FFTs on other types of >> input data (e.g. real and/or "wideband"), but the underlying core is the >> biplex FFT. >> >> One of the tricks is to combine two real inputs into a single complex >> input. The positive (non-redundant) frequency channels of each real input >> can be recovered from the complex output spectrum by adding/subtracting >> channel X with channel -X. I am not aware of any CASPER FFT that processes >> a real input as a complex input with the imaginary component set to 0. >> >> Getting back to Alex's question, I think Jack is on the right track that >> performing inverse FFTs of two N point complex spectra of real inputs can >> probably be accomplished by creating a 2N point complex spectra that is not >> symmetric (via linear combinations of the two input spectra) and then >> inverse FFTing and taking the real and imaginary outputs as the time >> series. I would recommend working this out analytically first (to ensure >> this is in fact a valid option), then experimenting with MATLAB to ensure >> that the mechanics are understood, then implement in simulink and simulate >> to ensure that the implementation is correct. There will be some details >> about fft_shift that might be hard to solve if the signals have different >> power levels or spectral shapes. >> >> HTH, >> Dave >> >> >> On Aug 14, 2018, at 13:35, Jonathan Weintroub <jweintr...@cfa.harvard.edu> >> wrote: >> >> Thanks for the response, Jack. Hope you are properly caffeinated today >> ;) >> >> I thought Alex put our application question really clearly, and he’s >> building some very nice bitcodes to see how the various processes work. >> I’d like to ask you, and the community, some simpler meta questions which >> came up for me as we dug into the CASPER blocks. Personnel changes have >> caused some loss of institutional memory, which is the context. >> >> Jack you said: "you should be able to do FFTs of two streams, A, B, in >> parallel.” I was under the impression CASPER streaming FFTs are very >> efficient, so that if a real FFT is needed, they are indeed done this way, >> in pairs and stuffed into the real and imaginary part of a complex-in >> complex-out FFT. Alex is using two CASPER blocks, one called simply “fft” >> which is complex-in complex-out and works as expected. The other called >> “wideband_fft_real”. What is curious to me about the latter block is that >> it takes a real input stream, and produces half the number of complex >> points at the output (which is the same amount of data, of course). >> >> There is, of course, a redundant copy of the spectrum produced by >> wideband_fft_real too, but that data seems to be stubbed out in the inner >> workings. What worries me about this is that it seems to be working by >> effectively setting the imaginary part of the inner complex FFT to zero, >> zeroing the redundant hermitian conjugate, and in so doing, is apparently >> doing a factor of two more computation than it needs to in principal. I >> feel I must be mistaken in this, since I really thought CASPER FFTs would >> not waste computation in this way. >> >> Can someone help guide me to the source of my assumed misunderstanding? >> It may be helpful to know something of the history of wideband_fft_real, >> and it’s relationship to “fft” and any other blocks which might be useful. >> >> As a sidelight, I’ve been trying to find a venerable paper I recall Aaron >> Parsons et al. wrote on the CASPER Biplex FFT. I can’t seem to find the >> one I recall, this is the closest I have come, but doesn’t have the >> singular focus on the FFT I recall in another useful reference. >> >> https://arxiv.org/pdf/0809.2266.pdf >> >> Can someone point me in the right direction. >> >> >> >> On Aug 14, 2018, at 2:27 AM, Jack Hickish <jackhick...@gmail.com> wrote: >> >> Hi Alex, >> >> I don't know if there's a way to avoid generating the full spectra prior >> to taking the fft (I suspect if there is, it just pushes the buffering >> somewhere else), but it certainly seems like you should be able to do FFTs >> of two streams, A, B, in parallel. I would think this would work by (after >> generating the full spectra) computing FFT(A+iB) such that FFT(A) emerges >> in the real part of the output, and FFT(B) in the imag. >> If you don't need to FFT two independent streams you can probably do >> something smart (like the wideband real fft) to leverage the above to do >> the multiple serial FFTs on a wideland input. >> >> I think? I haven't had coffee yet. >> >> Jack >> >> On Mon, 13 Aug 2018, 11:36 pm Alexander Raymond, < >> alexander.raym...@cfa.harvard.edu> wrote: >> >>> Dear CASPER List, >>> >>> I am a postdoc working with Jonathan Weintroub and am new to CASPER. >>> >>> We are working on bitcode for ROACH2 to reformat the data product at the >>> Submillimeter Array in real time so that it can be used directly in VLBI >>> observations as part of the Event Horizon Telescope. As part of that >>> reformatting, we wish to convert the demultiplexed frequency domain streams >>> of the SWARM F-engine (https://arxiv.org/abs/1611.02596) to time domain >>> streams. In other words, we want to take the inverse FFT of demultiplexed >>> frequency-domain samples. >>> >>> Ordinarily, we would would achieve the inverse fft using the CASPER >>> complex_conj and fft blocks in series; however, the SWARM frequency domain >>> output comes from an fft_wideband_real block, which discards the negative >>> frequencies, so direct application of complex_conj+fft will not work. One >>> approach to inverting the data would be to buffer and copy the positive >>> (complex) frequencies emitted by fft_wideband_real, assemble a stream of >>> positive and (mirrored) negative frequencies, then feed the complete >>> spectrum into complex_conj+fft blocks. >>> >>> Jonathan suggested I check with the CASPER community to see, is there a >>> more efficient way of performing our inverse FFT? Is there a way to take >>> advantage of the knowledge that the output from our iFFT block should be >>> real-valued? >>> >>> We appreciate any guidance the mailing list can provide. >>> >>> Sincerely, >>> >>> Alex Raymond >>> >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "casper@lists.berkeley.edu" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to casper+unsubscr...@lists.berkeley.edu. >>> To post to this group, send email to casper@lists.berkeley.edu. >>> >> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "casper@lists.berkeley.edu" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to casper+unsubscr...@lists.berkeley.edu. >> To post to this group, send email to casper@lists.berkeley.edu. >> >> >> -- > You received this message because you are subscribed to the Google Groups " > casper@lists.berkeley.edu" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to casper+unsubscr...@lists.berkeley.edu. > To post to this group, send email to casper@lists.berkeley.edu. > -- You received this message because you are subscribed to the Google Groups "casper@lists.berkeley.edu" group. To unsubscribe from this group and stop receiving emails from it, send an email to casper+unsubscr...@lists.berkeley.edu. To post to this group, send email to casper@lists.berkeley.edu.
