Efficient correlation over a sliding window
AssigneeEricsson Inc.
InventorsPaul W. Dent, Eric Wang
Life of this patent
Estimating the term…
Abstract
The details of an improved correlator and efficient method of correlation are disclosed. The last M received signal samples are compared with all shifts of a given M-bit binary codeword. The correlator adds or subtracts each of the signal samples accordingly, as the corresponding shift of the codeword contains a binary "1" or "0" in that position. The total is output for each new signal sample received, with a shift of one position between the signal samples and the codeword.
Claims24
A method for producing correlations between a binary code word including a predefined first plurality of bits and a corresponding plurality of successively input signal samples, comprising the steps of:
- storing a first plurality of partially completed correlations in a first storage location;
- inputting a second plurality of said input signal samples to a second storage location, said second plurality less than said first plurality of bits;
- responsive to a sign of said second plurality of said input signal samples, adding or subtracting said second plurality of said input samples in said second storage location to or from said second plurality of said input samples to produce a first plurality of sample combinations;
- and
- responsive to said sign of said second plurality of said input signal samples, adding or subtracting said first plurality of sample combinations to or from a first selected plurality of said partially completed correlations to produce a second plurality of said partially completed correlations and a completed correlation.
A method for computing successive inner products between a first number of given fixed values and the same first number of arbitrary input values selected from a stream of sequential input values, comprising the steps of:
- maintaining a set of partially completed successive inner products;
- selecting a second number of said arbitrary input values to be processed next in sequence, said second number being less than said first number;
- utilizing said second number of said arbitrary input values to complete a calculation of the same second number of successive inner products by combining said second number of said arbitrary input values with the same second number of said partially completed successive inner products using selected ones of said fixed values in multiplication with said selected arbitrary input values;
- forming a set of updating values as inner products between said second number of arbitrary input values and at least all possible sets of the same second number of fixed values selected from adjacent positions within said first number of given fixed values;
- initializing a number of new partially completed inner products corresponding to said same second number of completed successive inner products;
- combining the remaining as yet uncompleted partially completed inner products with selected ones of said updating values to form updated partial inner products;
- and
- repeating the above-recited steps to obtain said second number of inner products each time the above-recited steps are executed.
A method for computing successive inner products between a first plurality of predetermined vectors, each of said first plurality of predetermined vectors containing a first plurality of ordered values and vectors formed by successive shifts of a sequence of arbitrary input values, comprising the steps of:
- maintaining for each of said first plurality of predetermined vectors a set of partially completed successive inner products;
- selecting a number of said input values to be processed next in sequence, said number of said input values being less than said first plurality of ordered values;
- utilizing said number of said input values to complete a calculation for each of said first plurality of predetermined vectors of a number of inner products equal to said number of said input values using selected elements of said predetermined vectors in multiplication with said selected input values;
- forming a set of updating values as inner products between said number of said input values and at least all possible sets of the same number of fixed values selected from adjacent positions within any of said first number of predetermined vectors;
- initializing a number of new partially completed inner products based on said completed inner products;
- combining the remaining as yet uncompleted partially completed inner products with selected ones of said updating values to form updated partially completed inner products;
- and
- repeating the above-recited steps to obtain said number of completed inner products with each of said first plurality of predetermined vectors each time the above-recited steps are executed.
A correlator, comprising:
- a timing controller responsive to a clock signal;
- an input signal storage means for storing input signals;
- a latch coupled to an output of said input signal storage means, for sampling said input signals;
- a signal combining and selecting means coupled to an output of said latch and said input signal storage means, for selecting sample combinations of said input signals;
- a mapping logic means coupled to an input of said signal combining and selecting means and to an output of said timing controller, for generating a sign pattern based on a bit pattern of a codeword being correlated with said input signals;
- a sign modifier coupled to an output of said mapping logic means, said signal combining and selecting means, and said timing controller;
- an address offset storage register coupled to said mapping logic means and said timing controller;
- and
- an output signal storage means coupled to said address offset storage means, said sign modifier, and said timing controller, for temporarily storing a correlated output signal.
Dependencies are inferred from the claim text.