Help with cross correlation

Altera_Forum · ‎04-10-2013

Hi,

I've been learning VHDL this semester and am trying to build a program that can take two input signals and cross correlate them. I've tried to implement a brute force summation algorithm, but it seems like the compiler just ignores most of what I tried to do. I think this means I'm writing un-synthesizable code, but I haven't yet figured out how to know if what I write can be created in hardware or not.

Here's one of my tries so far. Ultimately I'd like to make the inputs vectors of unsigned or standard logic, but for now I just want it to work with anything.


PACKAGE dataTypes IS
    TYPE inputVector IS ARRAY (NATURAL RANGE <>) OF INTEGER;
    TYPE outputVector IS ARRAY (NATURAL RANGE <>) OF INTEGER;
END PACKAGE dataTypes;
---------------------------------------------------------------------
LIBRARY ieee;
USE ieee.std_logic_1164.all;
USE ieee.numeric_std.all;
USE work.dataTypes.all;
---------------------------------------------------------------------
ENTITY xcorr is
  GENERIC
  (
    Nrcv: NATURAL := 16;
     Nknwn: NATURAL := 4
  );
  PORT
  (
    rcvSig: IN inputVector(1 TO Nrcv);
     knwnSig: IN inputVector(1 TO Nknwn);
     clk: IN STD_LOGIC;
    corrSig: OUT outputVector(1 TO (Nrcv+Nknwn-1))
  );
END ENTITY;
---------------------------------------------------------------------
ARCHITECTURE circuit OF xcorr IS
     CONSTANT zeroKnwnSig: inputVector(1 TO Nknwn) := (OTHERS => 0);
     CONSTANT padRcvSig: inputVector(1 TO (Nrcv + 2*Nknwn)) := (zeroKnwnSig & rcvSig & zeroKnwnSig);
BEGIN
  compute_output: PROCESS (clk)
    VARIABLE tempCorrSig: outputVector(1 TO (Nrcv+Nknwn-1)) := (OTHERS => 0);
    VARIABLE sum: INTEGER;
  BEGIN
      IF clk'EVENT AND clk = '1' THEN
          FOR i IN 1 TO Nrcv LOOP
            sum := 0;
            
             FOR j IN 1 TO Nknwn LOOP
               sum := sum + knwnSig(j) * padRcvSig(i+j);
             END LOOP;
             
            tempCorrSig(i) := sum;
             
          END LOOP;
        
        --ELSE
          --NULL;
      END IF;
        
        corrSig <= tempCorrSig;
        
  END PROCESS;
  
END ARCHITECTURE;

Altera_Forum · ‎04-11-2013

You need to draw yourself a timing diagram. What you have written is analogous to C-code where you have all the samples in a vector.

In hardware, you're more likely to have two new samples valid on every clock. To start with, you would zero out an accumulator, and on every subsequent clock, multiply the two new samples together and then add the product to a running sum. That running sum would be accumulated for a user defined period (your vector length), and then that "correlation" estimate would be output. The accumulator would be zeroed, and the process repeated.

Your approach assumes that the timing of the two signals is known and identical, i.e., that both signals show up at the same time. If there is uncertainty in the relative timing of signals, then you will need to perform this calculation at multiple delays, or "lags". If you calculate the cross-correlation at multiple lags, you can Fourier transform the lags into a cross-power spectrum. The phase-slope of that spectrum is the relative delay of the correlated signal in the two inputs.

Cheers,

Dave

Altera_Forum · ‎04-12-2013

Dave,

Thank you for taking a few minutes to explain how to me some of the "big picture" I'm missing here. It took me some time to finally get all of my assignments to have the correct sizes and types, but:

LIBRARY ieee;USE ieee.std_logic_1164.all;
USE ieee.numeric_std.all;
USE ieee.math_real.all;
---------------------------------------------------------------------
ENTITY xcorr is
  GENERIC
  (
     -- length of the known signal
     lenKnown: NATURAL := 4;
     -- bit depth of a sample
     bitDepth: NATURAL := 12
  );
  PORT
  (
    rcvPt: IN STD_LOGIC_VECTOR(bitDepth-1 DOWNTO 0);
     clk: IN STD_LOGIC;
    corrPt: OUT STD_LOGIC_VECTOR(NATURAL(CEIL(LOG2(REAL(lenKnown) * (2.0**(REAL(bitDepth)**2.0))-1.0))) DOWNTO 0)
  );
END ENTITY;
---------------------------------------------------------------------
ARCHITECTURE circuit OF xcorr IS
  TYPE sampData IS ARRAY (NATURAL RANGE <>) OF SIGNED(bitDepth-1 DOWNTO 0);
  TYPE multData IS ARRAY (NATURAL RANGE <>) OF SIGNED((bitDepth**2)-1 DOWNTO 0);
  CONSTANT sigKnown: sampData(0 TO lenKnown-1) := ((0 => '1', OTHERS => '0'),(0 => '1', OTHERS => '0'),(0 => '1', OTHERS => '0'),(0 => '1', OTHERS => '0'));
BEGIN
  compute_output: PROCESS (clk)
    VARIABLE sigRec: sampData(0 TO lenKnown-1) := (OTHERS => (OTHERS => '0'));
     VARIABLE sigMult: multData(0 TO lenKnown-1) := (OTHERS => (OTHERS => '0'));
     VARIABLE sum: SIGNED(NATURAL(CEIL(LOG2(REAL(lenKnown) * (2.0**(REAL(bitDepth)**2.0))-1.0))) DOWNTO 0);
  BEGIN
      IF clk'EVENT AND clk = '1' THEN
          sum := (OTHERS => '0');
          
          FOR i IN lenKnown-1 DOWNTO 1 LOOP
            sigRec(i) := sigRec(i-1);             
          END LOOP;
          
          sigRec(0) := SIGNED(rcvPt);
          
          FOR i IN 0 TO lenKnown-1 LOOP
            sigMult(i) := RESIZE((sigRec(i) * sigKnown(i)), (bitDepth**2));
             sum := sum + sigMult(i);
          END LOOP;
          
        ELSE
          NULL;
      END IF;
        
        corrPt <= STD_LOGIC_VECTOR(sum);
        
  END PROCESS;
  
END ARCHITECTURE;

and in the tiny bit of testing I've done so far it works and it works fast (~8ns delay)! I guess this approach seems more like a detector to me than the mathematical idea of a cross correlation, but I think I'm starting to think in discrete time.

Altera_Forum · ‎04-12-2013

Here's some more info to get you started ...

http://www.ovro.caltech.edu/~dwh/wbsddc/correlator_efficiency.pdf

including how this relates to a discrete correlation.

Cheers,

Dave

Altera_Forum · ‎04-12-2013

Wow, what a small world. I didn't realize until I saw your name on the pdf that I've read through your thesis several times. I used to do acoustics research for the US Navy and they basically handed me a copy of your thesis to read on the first day. Thank you for all the help then too!

Pat

Altera_Forum · ‎04-12-2013

Hi Pat,

--- Quote Start ---

Wow, what a small world. I didn't realize until I saw your name on the pdf that I've read through your thesis several times. I used to do acoustics research for the US Navy and they basically handed me a copy of your thesis to read on the first day. Thank you for all the help then too!

--- Quote End ---

Ha! That is classic. I'm glad to have been able to help you :)

Here's what I'm working on now:

http://www.ovro.caltech.edu/~dwh/wbsddc/altera_fpgas_in_radio_astronomy.pdf

At the time I finished my thesis, there wasn't exactly a lot going on in the world of SAS. Things have changed now though, a lot of well-known names in the field have just spun-off this company:

http://www.krakensonar.com/index.php/en/technology/synthetic-aperture-sonar

Cheers,

Dave