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

• US 7,454,453 B2
• Filed: 11/24/2003
• Issued: 11/18/2008
• Est. Priority Date: 11/14/2000
• Status: Expired due to Fees

• Current Assignee: ParkerVision, Inc.
• Original Assignee: ParkerVision, Inc.
• Inventors: Rawlins, Gregory S., Kassel, Ray
• Primary Examiner(s): Malzahn; David H
• Application Number:
  US10/719,058
• Publication Number:
  US 20040230628A1
• Time in Patent Office: 1,821 Days
• Field of Search: 708/422, 708/425, 708/314, 708/319, 708/603
• US Class Current: 708/425
• 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. 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 repeated 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 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 the data word. The summations can be optimized to exclude summations that would result in invalid combinations of the encoding coefficients (C₀-C_M−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 correlating an encoded data word (X₀-X_M−

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

1</sub>), wherein each of (X₀-X<sub>M−

1</sub>) is represented by one or more bits and each said coefficient is represented by one or more bits, wherein each said coefficient has k possible states, wherein M is greater than 1, comprising;

(1) receiving the encoded data word (X₀-X<sub>M−

1</sub>);

(2) multiplying X₀ with states C₀₍₀₎ through C<sub>0(K−

1)</sub> of said coefficient C₀, thereby generating results X₀C₀₍₀₎ through X₀C<sub>0(K−

1)</sub>;

(3) repeating step (1) for data bits (X₁-X<sub>M−

1</sub>) and corresponding said coefficients (C₁-C<sub>M−

1</sub>), respectively;

(4) grouping said results of steps (2) and (3) into N groups and summing combinations within each of said N groups, thereby generating a first layer of correlation results;

(5) grouping the results of step (4) and summing combinations of results within each group to generate one or more additional layers of results, and repeating this process until a final layer of results includes a correlation output for states of the set of coefficients (C₀-C<sub>M−

1</sub>);

(6) comparing magnitudes output of said correlation outputs, thereby identifying a most likely code encoded on said data word; and

(7) outputting the most likely code.

2. The method according to claim 1, wherein (4) and (5) comprise omitting summations that would result in invalid combinations of the encoding coefficients (C₀-C_M−

1).

3. The method according to claim 1, further comprising performing steps (1) through (7) using substantially the same hardware for in-phase and quadrature phase components of the data word (X₀-X_M−

1).

4. The method according to claim 1, wherein said coefficients (C₀-C_M−

1) represent real numbers.

5. The method according to claim 1, wherein said coefficients (C₀-C_M−

1) represent complex numbers.

6. The method according to claim 1, wherein each said coefficient (C₀-C_M−

1) is represented by a single bit.

7. The method according to claim 1, wherein each said coefficient (C₀-C_M−

1) is represented by multiple bits.

8. The method according to claim 1, wherein said code patterns (C₀-C_M−

1) represent a cyclic code keying (“

CCK”

) code set substantially in accordance with IEEE 802.11 WLAN standard.

9. The method according to claim 8, wherein:

M equals 8;

each said coefficient (C₀-C<sub>M−

1</sub>) has two states, plus and minus;

N equals 4;

said first level of results comprises at least a portion of the following;

(X₀C₀+X₁C₁), (X₀(—

C₀)+X₁C₁), (X₀C₀+X₁(—

C₁)), (X₀(—

C₀)+X₁(—

C₁)), (X₂C₂+X₃C₃), (X₂(—

C₂)+X₃C₃), (X₂C₂+X₃(—

C₃)), (X₂(—

C₂)+(X₃(—

C₃)), (X₄C₄+X₅C₅), (X₄(—

C₄)+X₅C₅), (X₄C₄+X₅(—

C₅)), (X₄(—

C₄)+X₅(—

C₅)), (X₆C₆+X₇C₇), (X₆(−

C₆)+X₇C₇), (X₆C₆+X₇(—

C₇)), and (X₆(—

C₆)+(X₇(—

C₇)); and

wherein said second level of results comprises at least a portion of the following;

((X₀C₀+X₁C₁)+(X₂C₂+X₃C₃)), (i.e., B₀),

((X₀C₀+X₁C₁)+(X₂(—

C₂)+X₃C₃)), (i.e., B₁),

((X₀C₀+X₁C₁)+(X₂C₂+X₃(—

C₃)), (i.e., B₂),

((X₀C₀+X₁C₁)+(X₂(—

C₂)+(X₃(—

C₃)), (i.e., B₃),

((X₀(—

C₀)+X₁C₁)+(X₂C₂+X₃C₃)), (i.e., B₄)

((X₀(—

C₀)+X₁C₁)+(X₂(—

C₂)+X₃C₃)), (i.e., B₅),

((X₀(—

C₀)+X₁C₁)+(X₂C₂+X₃(—

C₃)), (i.e. B₆),

((X₀(—

C₀)+X₁C₁)+(X₂(—

C₂)+(X₃(—

C₃)), (i.e., B₇),

((X₀C₀+X₁(—

C₁))+(X₂C₂+X₃C₃)), (i.e., B₈)

((X₀C₀+X₁(—

C₁))+(X₂(—

C₂)+X₃C₃)), (i.e., B₉),

((X₀C₀+X₁(—

C₁))+(X₂C₂+X₃(—

C₃)), (i.e., B₁₀),

((X₀C₀+X₁(—

C₁))+(X₂(—

C₂)+(X₃(—

C₃)), (i.e., B₁₁),

((X₀(—

C₀)+X₁(—

C₁))+(X₂C₂+X₃C₃)), (i.e., B₁₂)

((X₀(—

C₀)+X₁(—

C₁))+(X₂(—

C₂)+X₃C₃)), (i.e., B₁₃),

((X₀(—

C₀)+X₁(—

C₁))+(X₂C₂+X₃(—

C₃)), (i.e., B₁₄),

((X₀(—

C₀)+X₁(—

C₁))+(X₂(—

C₂)+(X₃(—

C₃)), (i.e., B₁₅),

((X₄C₄+X₅C₅)+(X₆C₆+X₇C₇)), (i.e., B₁₆),

((X₄C₄+X₅C₅)+(X₆(—

C₆)+X₇C₇)), (i.e., B₂₀),

((X₄C₄+X₅C₅)+(X₆C₆+X₇(—

C₇)), (i.e., B₂₄),

((X₄C₄+X₅C₅)+(X₆(—

C₆)+(X₇(—

C₇)), (i.e., B₂₈),

((X₄(—

C₄)+X₅C₅)+(X₆C₆+X₇C₇)), (i.e., B₁₇)

((X₄(—

C₄)+X₅C₅)+(X₆(—

C₆)+X₇C₇)), (i.e., B₂₁),

((X₄(—

C₄)+X₅C₅)+(X₆C₆+X₇(—

C₇)), (i.e., B₂₅),

((X₄(—

C₄)+X₅C₅)+(X₆(—

C₆)+(X₇(—

C₇)), (i.e., B₂₉),

((X₄C₄+X₅(—

C₅))+(X₆C₆+X₇C₇)), (i.e., B₁₈)

((X₄C₄+X₅(—

C₅))+(X₆(—

C₆)+X₇C₇)), (i.e., B₂₂),

((X₄C₄+X₅(—

C₅))+(X₆C₆+X₇(—

C₇)), (i.e., B₂₆),

((X₄C₄+X₅(—

C₅))+(X₆(—

C₆)+(X₇(—

C₇)), (i.e., B₃₀),

((X₄(—

C₄)+X₅(—

C₅))+(X₆C₆+X₇C₇)), (i.e., ₁₉)

((X₄(—

C₄)+X₅(—

C₅))+(X₆(—

C₆)+X₇C₇)), (i.e., B₂₃),

((X₄(—

C₄)+X₅(—

C₅))+(X₆C₆+X₇(—

C₇)), (i.e., B₂₇),

((X₄(—

C₄)+X₅(—

C₅))+(X₆(—

C₆)+(X₇(—

C₇)), (i.e., B₃₁).

10. The method according to claim 9, wherein said second level of results omits one or more of B₀ through B₃₁.

11. The method according to claim 9, wherein said second level of results omits one or more of B₀ through B₃₁ that represent invalid combinations of one or more of (C₀-C_M−

1).

12. The method according to claim 9, wherein said second level of results omits one or more of B₀ through B₃₁ where the omitted combination(s) would be redundant based on said CCK code specification.

13. The method according to claim 9, wherein said second level of results omits B₂₄ through B₃₁.

14. The method according to claim 13, wherein said final level of results comprises:

(B₀+B₁₉), (B₀+B₂₁), (B₁+B₂₀), (B₁+B₁₈), (B₁+B₂₃), (B₂+B₂₀), (B₂+B₁₇), (B₂+B₂₃), (B₃+B₁₆), (B₃+B₂₂), (B₄+B₁₇), (B₄+B₁₈), (B₄+B₂₃), (B₅+B₁₆), (B₅+B₂₂), (B₆+B₂₁), (B₆+B₁₉), (B₇+B₂₀), (B₇+B₁₇), (B₇+B₁₈), (B₈+B₂₀), (B₈+B₁₇), (B₈+B₁₈), (B₉+B₂₁), (B₉+B₁₉), (B₁₀+B₁₆), (B₁₀+B₂₂), (B₁₁+B₁₇), (B₁₁+B₁₈), (B₁₁+B₂₃), (B₁₂+B₁₆), (B₁₂+B₂₂), (B₁₃+B₂₀), (B₁₃+B₁₇), (B₁₃+B₂₃), (B₁₄+B₂₀), (B₁₄+B₁₈), (B₁₄+B₂₃), (B₁₅+B₂₁), and (B₁₅+B₁₉).

15. The method according to claim 13, wherein said final level of results consists of:

(B₀+B₁₉), (B₀+B₂₁), (B₁+B₂₀), (B₁+B₁₈), (B₁+B₂₃), (B₂+B₂₀), (B₂+B₁₇), (B₂+B₂₃), (B₃+B₁₆), (B₃+B₂₂), (B₄+B₁₇), (B₄+B₁₈), (B₄+B₂₃), (B₅+B₁₆), (B₅+B₂₂), (B₆+B₂₁), (B₆+B₁₉), (B₇+B₂₀), (B₇+B₁₇), (B₇+B₁₈), (B₈+B₂₀), (B₈+B₁₇), (B₈+B₁₈), (B₉+B₂₁), (B₉+B₁₉), (B₁₀+B₁₆), (B₁₀+B₂₂), (B₁₁+B₁₇), (B₁₁+B₁₈), (B₁₁+B₂₃), (B₁₂+B₁₆), (B₁₂+B₂₂), (B₁₃+B₂₀), (B₁₃+B₁₇), (B₁₃+B₂₃), (B₁₄+B₂₀), (B₁₄+B₁₈), (B₁₄+B₂₃), (B₁₅+B₂₁), and (B₁₅+B₁₉).

16. The method according to claim 9, wherein said final level of results omits one or more possible combinations of B₀ through B₃₁.

17. The method according to claim 9, wherein said final level of results omits one or more combinations of B₀ through B₃₁ that represent invalid combinations of one or more of (C₀-C_M−

1).

18. The method according to claim 9, wherein said final level of results omits one or more combinations of B₀ through B₃₁ where the omitted combination(s) would be redundant based on a code specification.

19. The method according to claim 9, wherein said final level of results omits one or more combinations B₂₄ through B₃₁ where the omitted combination(s) would be invalid based on a code specification.

20. The method according to claim 1, further comprising performing an equalization process during one or more of steps (4) and (5).

21. The method according to claim 1, further comprising performing an MLSE process during one or more of steps (4) and (5).

22. The method according to claim 1, further comprising performing an adaptive process during one or more of steps (4) and (5).

23. The method according to claim 1, further comprising performing an adaptive equalization process during one or more of steps (4) and (5).

24. The method according to claim 1, wherein one or more of (C₀-C_M−

1) are constants.

25. The method according to claim 1, wherein one or more of (C₀-C_M−

1) are variable.

26. The method according to claim 1, wherein steps (4) and (5) are implemented in accordance with:

$N=\frac{n!}{r!<br><br>\left(n-r\right)!}-L$

wherein;

n represents a number of summer inputs;

r represents a number of summing inputs per kernal; and

L represents a number of invalid combinations.

27. A system for correlating an encoded data word (X₀-X_M−

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

1</sub>), wherein each of (X₀-X<sub>M−

1</sub>) is represented by one or more bits and each said coefficient is represented by one or more bits, wherein each said coefficient has k possible states, wherein M is greater than 1, comprising;

inputs for each of (X₀-X<sub>M−

1</sub>);

a multiplier coupled to each said input;

N summers, each coupled to a different group of outputs of said multipliers, whereby outputs of said N summers form a first layer of correlation results;

one or more additional layers of summers, each said additional layer of summers coupled to outputs of a previous layer of correlation results, said one or more additional layers of summers including a final layer of summers having a final layer of results including a separate correlation output for each possible state of the complete set of coefficients (C₀-C<sub>M−

1</sub>);

a magnitude comparator coupled to said final layer of results; and

means for selecting a state of the complete set of coefficients (C₀-C<sub>M−

1</sub>) associated with a maximum correlation output.

28. A system for correlating an encoded data word (X₀-X_M−

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

1</sub>), wherein each of (X₀-X<sub>M−

1</sub>) is represented by one or more bits and each said coefficient is represented by one or more bits, wherein each said coefficient has k possible states, wherein M is greater than 1, comprising;

means for multiplying X₀ with states C₀₍₀₎ through C<sub>0(K−

1)</sub> of said coefficient C₀, thereby generating results X₀C₀₍₀₎ through X₀C<sub>0(K−

1)</sub>;

wherein said means for multiply includes means for multiplying X₁-X<sub>M−

1</sub> with corresponding coefficients (C₁-C<sub>M−

1</sub>), respectively;

first means for grouping results of said means for multiplying into N groups and for summing combinations within each of said N groups, thereby generating a first layer of correlation results;

second means for grouping results of said first means for grouping and for summing combinations of results within each group to generate one or more additional layers of results, and repeating this process until a final layer of results includes a correlation output for states of said set of coefficients (C₀-C<sub>M−

1</sub>); and

means for comparing magnitudes output of said correlation outputs, thereby identifying a most likely code encoded on said data word.

29. A method for parallel correlation detection, comprising the steps of:

(1) receiving noisy input samples X₀, X₁, X₂, X₃, X₄, X₅, X₆, and X₇ from which a code is to be extracted;

(2) forming four sets of sample pairs (X₀, X₁), (X₂, X₃), (X₄, X₅), and (X₆, X₇) from said input samples;

(3) forming four correlation kernels (X_iC_i+X_jC_j), (—

X_iC_i+X_jC_j), (X_iC_i—

X_jC_j), and (—

X_iC_i—

X_jC_j) for each set of sample pairs formed in step (2), wherein X_i and X_j represent one of the four sample pairs formed in step (2) and wherein C_i and C_j represent predetermined weighting factors;

(4) combining the correlation kernels formed in step (3) to form a fast correlation transform trellis with sixty-four eight-tuple options;

(5) using the sixty-four eight-tuple options formed in step (4) to extract the code from the input samples received in step (1); and

(6) outputting the extracted code.

30. A system for parallel correlation detection, comprising:

a first module that receives noisy input samples X₀, X₁, X₂, X₃, X₄, X₅, X₆, and X₇ from which a code must be extracted;

a second module that forms four sets of sample pairs (X₀, X₁), (X₂, X₃), (X₄, X₅), and (X₆, X₇) from said input samples;

a third module that forms four correlation kernels (X_iC_i+X_jC_j), (−

X_iC_i+X_jC_j), (X_iC_i−

X_jC_j), and (—

X_iC_i—

X_jC_j) for each set of sample pairs formed in said second module, wherein X_i and X_j represent one of the four sample pairs formed in said second module and wherein C_i and C_j represent predetermined weighting factors;

a fourth module that combines the correlation kernels formed in said third module to form a fast correlation transform trellis with sixty-four eight-tuple options; and

a fifth module that compares magnitudes of outputs of said fast correlation transform trellis to identify a most likely code encoded in said noisy input samples.

31. A method for correlating an encoded data word (X₀-X_M−

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

1</sub>), wherein each of (X₀-X<sub>M−

1</sub>) is represented by one or more bits and each said coefficient is represented by one or more bits, wherein each said coefficient has k possible states, wherein M is greater than 1, comprising;

(1) receiving the encoded data word (X₀-X<sub>M−

1</sub>);

(2) multiplying X₀ with states of said coefficient C₀;

(3) repeating step (2) for data bits (X₁-X<sub>M−

1</sub>) and corresponding said coefficients, respectively;

(4) grouping said results of steps (2) and (3) into N groups and summing combinations within each of said N groups, thereby generating a first layer of correlation results;

(5) grouping the results of step (4) and summing combinations of results within each group to generate one or more additional layers of results, and repeating this process until a final layer of results includes a correlation output for each possible state of the set of coefficients;

(6) comparing magnitudes output of said correlation outputs, thereby identifying a most likely code encoded on said data word; and

(7) outputting the most likely code.

32. A method for parallel correlation detection, comprising the steps of:

(1) receiving noisy input samples from which a code must be extracted;

(2) forming at least four sets of sample pairs from said input samples;

(3) forming at least four correlation kernels for each set of sample pairs formed in step (2), wherein X_i and X_j represent one of the sample pairs formed in step (2) and wherein C_i and C_j represent predetermined weighting factors;

(4) combining the correlation kernels formed in step (3) to form a fast correlation transform trellis with at least sixty-four eight-tuple options;

(5) using the at least sixty-four eight-tuple options formed in step (4) to extract the code from the input samples received in step (1); and

(6) outputting the extracted code.