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 <[email protected]> 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 <[email protected]> > 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 <[email protected]> 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, < > [email protected]> 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 >> "[email protected]" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> To post to this group, send email to [email protected]. >> > > > -- > You received this message because you are subscribed to the Google Groups " > [email protected]" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > > > -- You received this message because you are subscribed to the Google Groups "[email protected]" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected].
