Simplified circuit for correlating binary and non-binary sequences

• US 6,934,732 B2
• Filed: 02/04/2002
• Issued: 08/23/2005
• Est. Priority Date: 02/06/2001
• Status: Expired due to Fees

• Current Assignee: 3G.Com, Inc.
• Original Assignee: 3G Com Incorporated
• Inventors: Lavi, Yoav
• Primary Examiner(s): Ngo, Chuong D
• Application Number:
  US10/061,278
• Publication Number:
  US 20020138532A1
• Time in Patent Office: 1,296 Days
• Field of Search: 708/422, 708/423, 708/424, 708/425, 708/426
• US Class Current: 708/422
• CPC Class Codes: G06F 17/15 Correlation function computation including computation of convolution operations arithmetic circuits for sum of products per se, e.g. multiply-accumulators G06F7/5443; digital filters, e.g. FIR, IIR, adaptive filters H03H17/00
• CPC Class Codes: G06F 7/5443 Sum of products for applications thereof, see the relevant places, e.g. G06F17/10, H03H17/00

Abstract

A correlator circuit for calculating the correlation between a signal sequence and a binary reference sequence. A unique method of calculating the correlation value between the two sequences provides for the reduction in necessary computations and, as a result, a reduction in the amount of time expended in calculating the correlation is realized.

Claims

1. A correlator system used to calculate a correlation between a short binary sequence and a signal sequence, said correlator comprising:

a first shift register operative to receive said signal sequence, wherein said first shift register comprises a plurality of first register blocks and each of said first register blocks is operative to store a successive value of said signal sequence;

a second shift register comprising a plurality of second register blocks, wherein each of said second register blocks is operative to store a successive value of said short binary sequence;

a first subtractor operative to calculate a difference between a next value of said signal sequence and a last value of said signal sequence;

a first adder operative to calculate the sum of the result of said first subtractor calculation and an output of a sum holding register, wherein said sum holding register is operative to store the output of said first adder;

a second adder operative to calculate the sum of a selected one of said successive values of said signal sequence and the output of an accumulator, wherein said accumulator is operative to accumulate successive results of said second adder;

a second subtractor operative to calculate the difference between the output of said sum holding register and the output of said accumulator.

2. A correlator system as claimed in claim 1 further comprising:

a counter operative to sequentially select each successive value of said signal sequence, wherein the selected value is presented to said second adder.

3. A correlator system as claimed in claim 2, further comprising:

a mux device operable to receive an output value of said counter and use said output value to determine the selected value.

4. A correlator for calculating a value representative of a correlation between a first and second sequence of values, said correlator comprising:

an accumulator operable to accumulate individual values of said first sequence, wherein each successive value of said first sequence is either added to an accumulation value or discarded based on a value of said second sequence corresponding to the successive value being either accumulated or discarded.

5. A correlator as claimed in claim 4, further comprising:

a summer operable to sum all values of said first sequence.

6. A correlator as claimed in claim 5, further comprising:

a subtractor operable to subtract a result of said summer from a result of said accumulator.

7. A correlator as claimed in claim 4, wherein said accumulator is clocked by a final clocking signal, said final clocking signal being generated by a combination of said value of said second sequence corresponding to the successive value being either accumulated or discarded and an initial clocking signal.

8. A method of calculating a correlation value for a short binary sequence comprising a plurality of binary values and a signal sequence comprising a plurality of signal values, said method comprising:

sequentially inputting said signal sequence into a first shift register, wherein said first shift register is operative to store a plurality of successive values of said signal sequence;

storing said short binary sequence in a second shift register;

sequentially applying each value of said short binary sequence to an adder;

selectively accumulating the successive values of said signal sequence, wherein each of said successive values is either accumulated or not accumulated depending on a corresponding value of said short binary sequence sequentially applied to said adder;

subtracting said accumulated values of said signal sequence from a stored previous value of said signal sequence.

9. A method as claimed in claim 8, wherein said stored previous value of said signal sequence is calculated by:

subtracting a first stored value of said signal sequence from a next value of said signal sequence;

adding a result of said subtracting to a second signal;

storing a result of said adding for a time period equal to a time required to input each successive value of said signal sequence into said first shift register; and

increasing the stored result of said adding by a factor.

10. A method of calculating a correlation value within a computer for a short binary sequence comprising a plurality of binary values and a signal sequence comprising a plurality of signal values, said method comprising:

(a) calculating a sum of said plurality of binary values;

(b) obtaining a first value of said signal sequence;

(c) obtaining a first value of said binary sequence;

(d) determining if said first value of said signal sequence is equal to minus one;

(e) adding said first value of said signal sequence to a present accumulation value if said first value of said signal sequence is not equal to minus one;

(f) determining if said first value of said binary sequence is a last value of said binary sequence;

(g) repeating (b) through (f) if said first value of said binary sequence is not a last value of said binary sequence and subtracting said sum of said plurality of binary values from the present accumulation value if said first value of said binary sequence is a last value of said binary sequence.

11. A method of determining a correlation value within a computer between a first sequence having a finite number of samples and a second sequence, said method comprising:

(a) calculating a sum of all samples of said first sequence and initializing a first pointer to zero;

(b) obtaining a first sample of said second sequence;

(c) obtaining a first sample of said first sequence;

(d) determining whether said first sample of said second sequence is equal to minus one;

(e) adding said first sample of said second sequence to an accumulator value if said first sample of said second sequence is not equal to minus one or determining if said first sample of said first sequence is a last sample of said first sequence if said first sample of said second sequence is equal to minus one;

(f) incrementing said first pointer by one and repeating (b) through (f) if said first sample of said first sequence is the last sample of said first sequence or setting said first pointer to zero and incrementing a second pointer by one if said first sample of said first sequence is the last sample of said first sequence;

(g) subtracting the sum of all samples of said first sequence from the accumulator value;

(h) determining if said first sample of said second sequence is a last sample of said second sequence; and

(i) incrementing said second pointer by one, resetting the accumulator value and repeating (b) through (i) if said first sample of said second sequence is not the last sample of said second sequence and ending the method if said first sample of said second sequence is the last sample of said second sequence.