Methods, systems, and computer program products for parallel correlation and applications thereof

• US 20080294708A1
• Filed: 01/24/2008
• Published: 11/27/2008
• Est. Priority Date: 11/14/2000
• Status: Active Grant

• Current Assignee: ParkerVision, Inc.
• Original Assignee: ParkerVision, Inc.
• Inventors: Rawlins, Gregory S., Kassel, Ray
• Granted Patent: US 7,991,815 B2
• Time in Patent Office: Days
• US Class Current: 708/314
• 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. Substantially the same hardware can be utilized for processing in-phase and quadrature phase components of the data word (X₀-X_M-1). The coefficients (C₀-C_M-1) can represent real numbers and/or complex numbers. The coefficients (C₀-C_M-1) can be represented with a single bit or with multiple bits (e.g., magnitude). The coefficients (C₀-C_M-1) represent, for example, a cyclic code keying (“CCK”) code set substantially in accordance with IEEE 802.11 WLAN standard.

Claims

1. A method for decoding, comprising:

(a) receiving a transmitted encoded data word;

(b) generating in-phase (I) and quadrature-phase (Q) components of the transmitted encoded data word based on the transmitted encoded data word;

(c) determining whether a phase shift occurred in the transmitted encoded data word;

(d) independently applying a fast correlator transform (FCT) to each of the I and Q components of the transmitted encoded data word to generate I and Q correlation outputs;

(e) combining the I and Q correlation outputs to generate a decoded data word.

2. The method of claim 1, wherein the transmitted encoded data word is encoded according to a Cyclic Code Keying (CCK) scheme.

3. The method of claim 1, wherein the transmitted encoded data word is encoded according to the IEEE 802.11 signaling scheme.

4. The method of claim 1, wherein step (b) comprises generating the I and Q components of the transmitted encoded data word based on a mapping of encoded input to I and Q encoded outputs according to an encoding scheme.

5. The method of claim 1, wherein the phase shift in the transmitted encoded data word is due to a differential encoding of the encoded data word.

6. The method of claim 1, wherein step (c) further comprises:

determining whether the I component of the transmitted encoded data word is inverted, thereby corresponding to a π

/2 phase shift in the transmitted encoded data word; and

determining whether the Q component of the transmitted encoded data word is inverted, thereby corresponding to a 3π

/2 phase shift in the transmitted encoded data word.

7. The method of claim 6, further comprising:

swapping the I and Q components when a π

/2 phase shift or a 3π

/2 phase shift is determined in the transmitted encoded data word.

8. The method of claim 1, wherein step (d) further comprises:

generating a respective plurality of correlation outputs for each of the I and Q components;

selecting for each of the I and Q components a respective maximum correlation output value from its respective plurality of correlation outputs.

9. The method of claim 8, wherein the maximum correlation output value has an absolute value of 8.

10. The method of claim 8, wherein step (e) further comprises:

combining the respective I and Q maximum correlation output values to generate the decoded data word.

11. A decoder, comprising:

input circuitry to receive a transmitted encoded data word;

mapping circuitry to map the transmitted encoded data word to corresponding in-phase (I) and quadrature (Q) components of the transmitted encoded data word;

phase shift detection circuitry to determine whether a phase shift occurred in the transmitted encoded data word;

I and Q fast correlator transform (FCT) circuitry to independently perform FCT correlation on each of the I and Q components of the transmitted encoded data word and to generate I and Q correlation outputs;

adder circuitry to combine the I and Q correlation outputs and generate a decoded data word.

12. The decoder of claim 11, wherein the transmitted encoded data word is encoded according to a Cyclic Code Keying (CCK) scheme.

13. The decoder of claim 11, wherein the transmitted encoded data word is encoded according to the IEEE 802.11 signaling scheme.

14. The decoder of claim 11, wherein the mapping circuitry comprises a mapping of encoded input to I and Q encoded outputs according to an encoding scheme.

15. The decoder of claim 11, wherein the phase shift in the transmitted encoded data word is due to a differential encoding of the encoded data word.

16. The decoder of claim 11, wherein the phase detection circuitry further comprises:

inverted channel detection circuitry to determine whether the I component of the transmitted encoded data word is inverted, thereby corresponding to a π

/2 phase shift in the transmitted encoded data word; and

to determine whether the Q component of the transmitted encoded data word is inverted, thereby corresponding to a 3π

/2 phase shift in the transmitted encoded data word.

17. The decoder of claim 16, further comprising:

circuitry to swap the I and Q components when a π

/2 phase shift or a 3π

/2 phase shift is determined in the transmitted encoded data word.

18. The decoder of claim 11, wherein the I and Q FCT circuitry:

circuitry to generate a respective plurality of correlation outputs for each of the I and Q components;

circuitry to select for each of the I and Q components a respective maximum correlation output value from its respective plurality of correlation outputs.

19. The decoder of claim 18, wherein the maximum correlation output value has an absolute value of 8.

20. The decoder of claim 18, wherein the adder circuitry combines the respective I and Q maximum correlation output values to generate the decoded data word.

21. An apparatus, comprising:

(a) means for receiving a transmitted encoded data word;

(b) means for generating in-phase (I) and quadrature-phase (Q) components of the transmitted encoded data word based on the transmitted encoded data word;

(c) means for determining whether a phase shift occurred in the transmitted encoded data word;

(d) means for independently applying a fast correlator transform (FCT) to each of the I and Q components of the transmitted encoded data word to generate I and Q correlation outputs;

(e) means for combining the I and Q correlation outputs to generate a decoded data word.

22. The apparatus of claim 21, wherein the transmitted encoded data word is encoded according to a Cyclic Code Keying (CCK) scheme.

23. The apparatus of claim 21, wherein the transmitted encoded data word is encoded according to the IEEE 802.11 signaling scheme.

24. The apparatus of claim 21, wherein said generating means comprises means for generating the I and Q components of the transmitted encoded data word based on a mapping of encoded input to I and Q encoded outputs of an encoding scheme.

25. The apparatus of claim 21, wherein the phase shift in the transmitted encoded data word is due to a differential encoding of the encoded data word.

26. The apparatus of claim 21, wherein said determining means further comprises:

means for determining whether the I component of the transmitted encoded data word is inverted, thereby corresponding to a π

/2 phase shift in the transmitted encoded data word; and

means for determining whether the Q component of the transmitted encoded data word is inverted, thereby corresponding to a 3π

/2 phase shift in the transmitted encoded data word.

27. The apparatus of claim 26, further comprising:

means for swapping the I and Q components when a π

/2 phase shift or a 3π

/2 phase shift is determined in the transmitted encoded data word.

28. The apparatus of claim 21, wherein said independently applying means further comprises:

means for generating a respective plurality of correlation outputs for each of the I and Q components;

means for selecting for each of the I and Q components a respective maximum correlation output value from its respective plurality of correlation outputs.

29. The apparatus of claim 28, wherein the maximum correlation output value has an absolute value of 8.

30. The apparatus of claim 28, wherein said combining means further comprises:

means for combining the respective I and Q maximum correlation output values to generate the decoded data word.