# Easiest way to perform vector cross correlation on USRP?

Hi,
I wonder what if the easiest way to perform real-time cross
correlation in
the FPGA on USRP? I’ve worked weeks on writing a close form algebra
doing
cross correlation,but since all my algorithms are based on floating
points
and multiplication/division, I’m afraid it’s hard to convert that to
Verilog
code later.
All I need to do is for 2 sequence A and B, perform this:
max(ifft(fft(A).*conj(fft(B))));
It’s really easy to do in MATLAB and relativly simple in C++, but in
Verilog? I have no idea…
Please people, if any one has done this before or anything related,
share
some information with me, I would really preciate that!
/Lin Ji

With a Cyclone part with no dedicated multipliers, you are asking a
lot of logic to create your multipliers. I would not suggest trying
to do this type of calculation in this particular FPGA.

If you want to know how to do it in Verilog, you need to take into
this, you have N clock cycles to perform the calculations. If you
were to do something like this, you could possibly have a block that
performs the two FFT’s in parallel and puts the results into a
BlockRAM. By the time this is done, the next frame is ready for the
FFT, so while this is processing you can perform the cross correlation
and store those results in the next BlockRAM. After doing this, you
can do the IFFT out of that BlockRAM and pass the results into a small
block to calculate the max value.

You can get Altera tools to generate cores that will perform FFTs and
IFFTs for you. The cross correlation would then be the handcoded part
along with the max logic.

http://www.altera.com/products/ip/dsp/transforms/m-ham-fft.html

You can also try opencores.org and check out their FFT section, but as
I said earlier - without dedicated multipliers, it would require a
HUGE part and slow down your design significantly.

Hope this helps!

Brian

You don’t use fast convolution when using an FPGA. Do this in the time
domain. That’s the purpose of using hardware over software. Expand your
algorithm for complex cross correlation and you will end up with a
string of simple algebraic terms. You will have to look at your losses
using fixed point vs. floating point.

–Ryan