Method and apparatus for a parallel correlator and applications thereof

• US 7,233,969 B2
• Filed: 04/18/2005
• Issued: 06/19/2007
• 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,861
• Publication Number:
  US 20050193049A1
• Time in Patent Office: 792 Days
• Field of Search: 708/422, 708/314, 708/319
• 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−) 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 method for correlating an encoded data word (X₀, . . . , X_M−

1) with encoding coefficients (C₀, . . . , C<sub>M−

1</sub>), wherein each of the encoding coefficients has possible states, wherein M is greater than 1, comprising;

(1) generating in parallel the results of the summation

X₀C₀+X₁C₁+ . . . +X<sub>M−

1</sub>C<sub>M−

1</sub>

for all valid combinations of the encoding coefficients (C₀, . . . , C<sub>M−

1</sub>), omitting summations that result in invalid combinations of the encoding coefficients (C₀, . . . , C<sub>M−

1</sub>); and

(2) identifying the combination of encoding coefficients corresponding to a maximum result as the encoding combination.

2. The method of claim 1, wherein step (1) comprises:

(a) multiplying each of X₀, . . . , X<sub>M−

1</sub> by all possible states of respective coefficient C₀, . . . , C<sub>M−

1</sub>, thereby generating (M×

k) results;

(b) grouping the results and summing valid combinations thereof within each group, thereby generating a first layer of correlation kernels; and

(c) repeating step (b) until each of the correlation kernels includes a combination of every one of X₀, . . . , X<sub>M−

1</sub>.

3. The method of claim 2, wherein the number of correlation kernels resulting after step (b) is in accordance with:

Nk=n!/[r!(n−

r)!]−

L

wherein;

n represents the number of results in a group;

r represents the number of summing elements per correlation kernel; and

L represents the number of invalid combinations within the group.

4. The method of claim 2, wherein step (b) comprises omitting the summation of one or more combinations of the results.

5. The method of claim 4, wherein the omitted summations represent summations of invalid combinations of one or more of C₀, . . . , C_M−

1 based on the encoding code specification.

6. The method of claim 1, wherein the valid combinations represent combinations valid in accordance with an encoding code specification.

7. The method of claim 1, wherein invalid combinations represent combinations invalid in accordance with an encoding code specification.

8. The method of claim 1, wherein step (2) comprises a maximum likelihood decoding process.

9. The method of claim 8, wherein step (2) comprises:

comparing the magnitudes of the results corresponding to valid combinations of the encoding coefficients.

10. The method of claim 9, wherein the comparing of the magnitudes comprises a space slicing process, wherein:

(1) the most significant bit (MSB) of the magnitudes is examined and magnitudes not active in the MSB are eliminated; and

(2) step (1) is repeated with the next most significant bit as the MSB until the maximum magnitude is determined.

11. The method of claim 9, wherein the comparing of the magnitudes comprises a parallel magnitude compare process with (log₂L)−

1 magnitude compare operations, wherein L is the total number of results.

12. The method of claim 11, wherein the comparing of the magnitudes comprises comparing two results by creating the difference between the two.

13. The method of claim 1, wherein the encoding coefficients represent binary coefficients having one of two possible values.

14. The method of claim 13, wherein the encoding coefficients represent a cyclic code keying (CCK) code set.

15. The method of claim 1, wherein the encoding coefficients represent M-ary coefficients having one of M possible values.

16. The method of claim 1, wherein one or more of C₀, . . . , C_M−

1 are hard-coded constant values.

17. The method of claim 1, wherein one or more of C₀, . . . , C_M−

1 are soft-coded variable values.

18. The method of claim 1, wherein C₀, . . . , C_M−

1 represent real numbers.

19. The method of claim 1, wherein C₀, . . . , C_M−

1 represent complex numbers.

20. A method for accelerating the parallel correlation of an encoded data word (X₀, . . . , X_M−

1) with encoding coefficients C₀, . . . , C_M−

, wherein each of the encoding coefficients has k possible states, wherein M is greater than 1, comprising;

(a) generating in parallel the results of the multiplication of each of X₀, . . . , X<sub>M−

1</sub> with respective encoding coefficient C₀, . . . , C<sub>M−

1</sub> for all k possible states of the encoding coefficient;

(b) grouping the results and summing only valid combinations thereof within each group, thereby reducing the number of addition operations; and

(c) repeating step (b) until a final layer of results is generated.

21. A system for correlating an encoded data word (X₀, . . . , X_M−

1) with a cyclic code coefficient set (C₀, . . . , C<sub>M−

1</sub>) in accordance with IEEE 802.11 WLAN standard, wherein each coefficient in the coefficient set has k possible states, comprising;

means for generating in parallel the results of the summation

X₀C₀+X₁C₁+ . . . +X<sub>M−

1</sub>C<sub>M−

1</sub>

for all valid combinations of the coefficient set (C₀, . . . , C_M−

); and

means for identifying the combination of the coefficient set corresponding to a maximum result as the encoding combination.

22. The system of claim 21, wherein means for generating comprises:

means for multiplying each of X₀, . . . , X<sub>M−

1</sub> by all possible states of respective coefficient C₀, . . . , C<sub>M−

1</sub>; and

means for grouping the results and summing valid combinations thereof within each group.

23. The system of claim 21, wherein means for identifying comprises:

means for comparing magnitudes of the results corresponding to valid combination of the combination set.