Computing cross-correlations for sparse data

Patent metadata

Field	Value
Publication number	US-9858304-B2
Application number	US-201514671614-A
Country	US
Kind code	B2
Filing date	Mar 27, 2015
Priority date	Apr 15, 2014
Publication date	Jan 2, 2018
Grant date	Jan 2, 2018

Abstract

A method for computing a cross-correlation between a first sequence and a second sequence includes: generating a first index vector based on the first sequence, the first index vector including a plurality of first elements, the first index vector excluding indices of zero valued elements of the first sequence; generating a second index vector based on the second sequence, the second index vector including a plurality of second elements, the second index vector excluding indices of zero valued elements of the second sequence; computing, on a processor, a plurality of pairwise differences between each of first elements of the first index vector and each of the second elements of the second index vector; and binning, on the processor, the plurality of pairwise differences to generate the cross-correlation of the first sequence and the second sequence.

First claim

What is claimed is:

1. A method for signal processing of radar signals to determine target range information, using a cross-correlation between a first signal pulse sequence and a second signal pulse sequence, the method comprising:
transmitting the first signal pulse sequence towards a target, by a transmitter;
receiving the second signal pulse sequence reflected from the target, by a receiver;
determining the cross-correlation between the first signal pulse sequence and the second signal pulse sequence, wherein determining the cross-correlation comprises:
generating a first index vector based on the first signal pulse sequence, the first index vector comprising a plurality of first elements, the first index vector excluding indices of the zero valued elements of the first signal pulse sequence;
generating a second index vector based on the second signal pulse sequence, the second index vector comprising a plurality of second elements, the second index vector excluding indices of the zero valued elements of the second signal pulse sequence;
computing, on a processor, a plurality of pairwise differences between each of the first elements of the first index vector and each of the second elements of the second index vector; and
time binning, on the processor, the plurality of pairwise differences to generate the cross-correlation of the first signal pulse sequence and the second signal pulse sequence; and

generating target range information from the cross-correlation of the first signal pulse sequence and the second signal pulse sequence.

2. The method of claim 1 , further comprising identifying a largest valued bin from among a plurality of time bins produced by the time binning the plurality of pairwise differences.

3. The method of claim 1 , wherein the first signal pulse sequence and the second signal pulse sequence are binary valued.

4. The method of claim 1 , wherein the first signal pulse sequence and the second signal pulse sequence are real valued or complex valued.

5. The method of claim 4 , wherein the first signal pulse sequence comprises a plurality of first weights and wherein the second signal pulse sequence comprises a plurality of second weights.

6. The method of claim 5 , wherein time binning of the pairwise differences into a plurality of time bins to generate the cross-correlation of the first signal pulse sequence and the second signal pulse sequence comprises, for each time bin:
multiplying the weights of the values of each pair of elements of the time bin to generate a plurality of products; and
summing the plurality of products of the time bin.

7. The method of claim 1 ,
wherein all of the elements of the first index vector are non-zero, and
wherein all of the elements of the second index vector are non-zero.

8. The method of claim 1 , further comprising converting elements of the first signal pulse sequence below a threshold level to a value of zero before generating the first index vector based on the first signal pulse sequence.

9. A system for signal processing of radar signals to determine target range information, using a cross-correlation between a first signal pulse sequence and a second signal pulse sequence, the system comprising:
a transmitter for transmitting the first signal pulse sequence towards a target;
a receiver for receiving the second signal pulse sequence reflected from the target;
a memory configured to store the first signal pulse sequence and the second signal pulse sequence; and
a processor configured to determine the cross-correlation between the first signal pulse sequence and the second signal pulse sequence, wherein determining the cross-correlation comprises:
generate a first index vector based on the first signal pulse sequence, the first index vector comprising a plurality of first elements, the first index vector excluding indices of the zero valued elements of the first signal pulse sequence;
generate a second index vector based on the second signal pulse sequence, the second index vector comprising a plurality of second elements, the second index vector excluding indices of the zero valued elements of the second signal pulse sequence;
compute a plurality of pairwise differences between each of the first elements of the first index vector and each of the second elements of the second index vector;
time bin the plurality of pairwise differences to generate the cross-correlation of the first signal pulse sequence and the second signal pulse sequence; and
generate target range information from the cross-correlation of the first signal pulse sequence and the second signal pulse sequence.

10. The system of claim 9 , wherein the processor is further configured to identify a largest valued time bin from among a plurality of time bins of pairwise differences.

11. The system of claim 9 , wherein the first signal pulse sequence and the second signal pulse sequence are binary valued.

12. The system of claim 9 , wherein the first signal pulse sequence and the second signal pulse sequence are real valued or complex valued.

13. The system of claim 9 , wherein the first signal pulse sequence comprises a plurality of first weights and wherein the second signal pulse sequence comprises a plurality of second weights.

14. The system of claim 13 , wherein the processor is further configured to time bin the plurality of differences into a plurality of time bins to generate the cross-correlation of the first signal pulse sequence and the second signal pulse sequence by, for each time bin:
multiplying the weights of the elements of each pair of elements of the time bin to generate a plurality of products; and
summing the plurality of products of the time bin.

15. The system of claim 9 ,
wherein all of the elements of the first index vector are non-zero, and
wherein all of the elements of the second index vector are non-zero.

16. The system of claim 9 , wherein the processor is further configured to convert elements of the first signal pulse sequence below a threshold level to a value of zero before generating the first index vector based on the first signal pulse sequence.

Assignees

• Raytheon Co

Inventors

• Marcus Eran
• Fluckiger David U
• Boland Brian F

Classifications

• G06F16/2272 Primary

  Management thereof · CPC title

• G06F17/142

  Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm · CPC title

• G01S7/486

  Receivers · CPC title

• G06F16/24578

  using ranking · CPC title

• G01S17/10

  using transmission of interrupted, pulse-modulated waves (determination of distance by phase measurements G01S17/32) · CPC title