Apparatus for the cross-correlation of a pair of complex sampled signals

• US 4,937,775 A
• Filed: 11/21/1988
• Issued: 06/26/1990
• Est. Priority Date: 11/21/1988
• Status: Expired due to Fees

• Current Assignee: General Electric Company
• Original Assignee: General Electric Company
• Inventors: O'Donnell, Matthew N, Engeler, William E.
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): Nguyen, Long T.
• Application Number:
  US07/274,473
• Time in Patent Office: 582 Days
• Field of Search: 364/728.03, 364/728.05, 364/820, 364/413.13, 364/728.04, 364/728.06, 364/728.07
• 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

Abstract

Apparatus for the cross-correlation of two complex sampled digital data signals X and Y uses a first N-stage CORDIC rotator of pipeline sequential form for rotating each of the real and imaginary data portions of the first (X) complex sampled signal sequentially through a summation of angles θ=ξ_i α_i where ξ_i =+1 or -1, α₁ =90° and α_n-2 =tan^-1 (2^-n) for n=0, 1, 2, 3, . . . N-2) until X_Im is approximately zero and a substantially zero phase angle is reached. The sign from each i-th stage, of this first pipeline is also utilized to determine the sign of rotation in each like-positioned i-th stage of a plurality M of additional CORDIC pipeline rotators, where M is the total number of time delays at which the cross-correlation function is evaluated. The real and imaginary portions of the complete M-th interval cross-correlation product are each obtained by multiplying the associated complex output of each of the Y pipeline rotators by the first pipeline magnitude signal output; N samples are then summed to provide at the j-th rotator output the appropriate pair of the real and imaginary parts of the j-th complex digital data output sample C(j).

Claims

1. Apparatus for cross-correlating first and second complex digital data signals, comprising:

a multiplier section having a first pipeline CORDIC rotator means with a plurality N of sequential stages, receiving separate and independent imaginary and real portions of the first complex data signal, for rotating the independent imaginary and real portions through predetermined decreasing angles α

to progressively reduce the magnitude of the imaginary-portion of the first complex data signal toward zero in each of the plurality N of sequential stages, and providing output data equal to the absolute value of the first complex data signal; and

a multiplicand section having a plurality M of additional pipeline CORDIC rotator means, each means having a like plurality N of sequential stages, for modifying the read and imaginary portions of the second complex data signal to cause rotation, responsive to a selection signal, through each of like angles α and

with a rotation in each j-th rotator means, where 1≦

j≦

(M-1), being progressively delayed by one common delay time interval greater than a total time delay in the previous (j-1)-th rotator means; and

means for arithmetically processing the modified second complex data signal from all of the M additional rotator means to provide, at any one time one set of data corresponding to the cross-correlation of both complex signals at that time.

2. The apparatus of claim 1, wherein each of the plurality N of stages in the first rotator means rotates each real and imaginary input data portion in a direction selected by a selection data bit state dependent upon a sign of the imaginary-portion data input to that stage;

and each stage includes one of a plurality N of comparator means for monitoring the stage imaginary-portion data input to establish the said selection data bit state.

3. The apparatus of claim 2, wherein the comparator means connected to each stage of the first rotator means receives the imaginary-portion data output from an immediately previous stage.

4. The apparatus of claim 1, wherein angle α

_i is the rotational angle for the i-th stage, where 1≦

i≦

N, with α

₁ =90° and

α

_i =tan^-1 (2^-n)°

with n=i-31 2 i=2,3,. . . ,N.

5. The apparatus of claim 1, wherein said multiplicand section further includes:

a plurality (M-1)xN of means for delaying an input data signal by one common-time-interval (CTI), each delay means receiving the selection signal from a selected i-th stage, where 1≦

i≦

N, of a previous j-th one of the additional rotator means and providing a delayed selection signal to the same i-th stage of a next (j+1)-th one of the additional rotator means; and

a plurality 2M of final means, each coupled to one of the real-portion and imaginary-portion outputs of each of the M additional rotator means, for processing that rotator means output with the first complex data signal absolute value to obtain a like portion of that one of M time-delayed correlator data outputs.

6. The apparatus of claim 5, wherein each of said plurality of final means includes:

means for obtaining data equal to a product of the associated multiplicand section output data and the multiplier section absolute value output data;

means for delaying the product data by N common-time-intervals (CTIs);

first adder means for subtracting the delayed product data from the product data to provide a first added output;

second adder means for adding the first added output and a correlator data output for that portion, to provide a second added output; and

means for accumulating the second added output to provide the portion correlator data output.