Method and apparatus for the parallel correlator and applications thereof

• US 7,433,910 B2
• Filed: 04/18/2005
• Issued: 10/07/2008
• Est. Priority Date: 11/14/2000
• Status: Expired due to Fees

• Current Assignee: ParkerVision, Inc.
• Original Assignee: ParkerVision, Inc.
• Inventors: Rawlins, Gregory S., Sorrells, David F., Rawlins, Michael W.
• Primary Examiner(s): Malzahn; David H
• Application Number:
  US11/107,862
• Publication Number:
  US 20050185741A1
• Time in Patent Office: 1,268 Days
• Field of Search: 708/422
• US Class Current: 708/422
• CPC Class Codes: G06F 17/141 Discrete Fourier transforms
• CPC Class Codes: G06F 17/147 Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform G06F17/145 takes precedence
• 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

A fast correlator transform (FCT) algorithm and methods and systems for implementing same, correlate an encoded data word (X₀-X_M−1) with encoding coefficients (C₀-C_M−1), wherein each of (X₀-X_M−1) is represented by one or more bits and each said coefficient is represented by one or more bits, wherein each coefficient has k possible states, and wherein M is greater than 1. In accordance with the invention, X₀ is multiplied by each state (C₀₍₀₎through C_0(k−1)) of the coefficient C₀, thereby generating results X₀C₀₍₀₎ through X₀C_0(k−1). This is repeating for data bits (X₁-X_M−1) and corresponding coefficients (C₁-C_M−1), respectively. The results are grouped into N groups. Members of each of the N groups are added to one another, thereby generating a first layer of correlation results. The first layer of results is grouped and the members of each group are summed with one another to generate a second layer of results. This process is repeated as necessary until a final layer of results is generated. The final layer of results includes a separate correlation output for each possible state of the complete set of coefficients (C₀-C_M−1). The final layer of results is compared to identify a most likely code encoded on said data word. In an embodiment, the summations are pruned to exclude summations that would result in invalid combinations of the encoding coefficients (C₀-C_M−1). In an embodiment, substantially the same hardware is utilized for processing in-phase and quadrature phase components of the data word (X₀-X_M−1). In an embodiment, the coefficients (C₀-C_M−1) represent real numbers. In an alternative embodiment, the coefficients (C₀-C_M−1) represent complex numbers. In an embodiment, the coefficients (C₀-C_M−1) are represented with a single bit. Alternatively, the coefficients (C₀-C_M−1) are represented with multiple bits (e.g., magnitude). In an embodiment, the coefficients (C₀-C_M−1) represent a cyclic code keying (“CCK”) code set substantially in accordance with IEEE 802.11 WLAN standard.

Claims

1. A wireless local area network (WLAN) device, comprising:

means for generating in parallel the correlation of a data word vector (X₀, . . . , X<sub>M−

1</sub>) with each valid combination of a coefficient set (C₀, . . . , C<sub>M−

1</sub>); and

means for identifying the correlation corresponding to a code encoded on the data word.

2. The WLAN device of claim 1, wherein the means for generating in parallel the correlation of a data word vector (X₀, . . . , X_M−

1) with each valid combination of a coefficient set (C₀, . . . , C<sub>M−

1</sub>) includes;

means for multiplying each element of the data word vector with each state of a corresponding coefficient in the coefficient set (C₀, . . . , C<sub>M−

1</sub>) to generate a plurality of outputs, wherein each coefficient in the coefficient set has one or more possible states;

means for summing a plurality of groups of multiplying means outputs to produce a set of first correlation results in parallel, wherein each group of multiplying means outputs includes a different combination of multiplying means outputs;

means for summing a plurality of groups of first correlation results to produce a set of second correlation results in parallel, wherein each group of first correlation results includes a different combination of first correlation results; and

means for summing a plurality of groups of second correction results to produce in parallel the correlation of a data word vector (X₀, . . . , X<sub>M−

1</sub>) with each valid combination of the coefficient set (C₀, . . . , C<sub>M−

1</sub>).

3. The WLAN device of claim 1, wherein the means for identifying the correlation corresponding to a code encoded on the data word includes:

means for comparing magnitudes of the correlations to select the maximum result.

4. The WLAN device of claim 1, wherein the means for summing a plurality of groups of multiplying means outputs, includes:

means for identifying valid combinations of multiplying means outputs; and

means for forming groups having valid combinations of multiplying means outputs.

5. The WLAN device of claim 1, wherein the means for summing a plurality of groups of first correlation results, includes:

means for identifying valid combinations of first correlation results; and

means for forming groups having valid combinations of first correlation results.

6. The WLAN device of claim 1, wherein the means for summing a plurality of groups of second correction results, includes:

means for identifying valid combinations of second correlation results; and

means for forming groups having valid combinations of second correlation results.

7. A wireless local area network (WLAN) device, comprising:

a plurality of inputs, one for each element of an encoded data word vector (X₀, . . . , X<sub>M−

1</sub>)

a multiplier module having a coefficient set (C₀, . . . , C<sub>M−

1</sub>), wherein each coefficient in the coefficient set has one or more possible states, wherein the multiplier module receives the plurality of inputs and multiplies each input with each state of a corresponding coefficient;

a first summation module including a plurality of summers, each summer coupled to a different group of multiplier module outputs, wherein each group of multiplier module outputs represents a valid combination of multiplier module outputs, and wherein a first set of correlation results are output in parallel from the first summation tier;

one or more additional summation modules coupled in series, each additional summation module receiving the outputs from a previous summation module, wherein the one or more additional summation modules includes a final summation module and wherein the final summation module outputs in parallel the correlation of the data word vector with each valid combination of the coefficient set; and

a comparator coupled to the final summation module.

8. The WLAN device of claim 7, wherein the one or more additional summation modules, include:

a plurality of summers, each summer coupled to a different group of outputs from the previous summer, wherein each group of outputs from the previous summer represents a valid combination of outputs from the previous summation module.

9. The WLAN device of claim 7, wherein the comparator includes:

a plurality of magnitude comparators,

wherein the plurality of magnitude comparators are arranged in a parallel tree configuration.

10. The WLAN device of claim 7, wherein the comparator is a space splicing comparator.

11. The WLAIN device of claim 7, wherein the multiplier module includes a plurality of multipliers, one for each element of the data word vector.

12. A wireless local area network (WLAN) device, comprising:

a multiplier module having a coefficient set (C₀, . . . , C<sub>M−

1</sub>), wherein each coefficient in the coefficient set has one or more possible states, wherein the multiplier module receives a plurality of inputs, one for each element of an encoded data word vector (X₀, . . . , X_M−

), and multiplies each input with each state of a corresponding coefficient;

a first summation module including a plurality of adders, wherein each adder receives a valid combination of multiplier module outputs and wherein an output of each adder in the first summation module includes two correlation components;

a second summation module including a plurality of adders, wherein each adder receives a valid combination of first summation module outputs and wherein an output of each adder in the second summation module includes four correlation components; and

a final summation module including a plurality adders, wherein each adder receives a valid combination of second summation module outputs and wherein the output of the final summation module is 64 valid correlations, each correlation having eight correlation components.

13. The WLAN device of claim 12, wherein the first summation module has 16 adders, the second summation module has 32 adders, and the final summation module has 64 adders.

14. The WLAN device of claim 12, wherein the device further comprises:

a comparator coupled to the final summation module.

15. The WLAIN device of claim 14, wherein the comparator includes:

a plurality of magnitude comparators,

wherein the plurality of magnitude comparators are arranged in a parallel tree configuration.

16. The WLAN device of claim 14, wherein the comparator is a space splicing comparator.

17. The WLAIN device of claim 14, wherein the multiplier module includes a plurality of multipliers, one for each element of the data word vector.

18. The WLAN device of claim 12, wherein the coefficient states have values of +1 and −

1.

19. The WLAN device of claim 12, wherein the coefficient states have values of +1, −

1, +j, and −

j.