Method and apparatus for a parallel correlator and applications thereof
First Claim
1. A method for correlating an encoded data word (X0-XM-1) with encoding coefficients (C0-CM-1), wherein each of (X0-XM-1) 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 the steps of:
- (1) multiplying X0 with each state (C0(0) through C0(k-1)) of said coefficient C0, thereby generating results X0C0(0) through X0C0(k-1);
(2) repeating step (1) for data bits (X1-XM-1) and corresponding said coefficients (C1-CM-1), respectively;
(3) grouping said results of steps (1) and (2) into N groups and summing combinations within each of said N groups, thereby generating a first layer of correlation results;
(4) grouping the results of step (3) 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 separate correlation output for each possible state of the complete set of coefficients (C0-CM-1); and
(5) comparing magnitudes output of said separate correlation outputs, thereby identifying a most likely code encoded on said data word.
1 Assignment
0 Petitions
Accused Products
Abstract
A fast correlator transform (FCT) algorithm and methods and systems for implementing same, correlate an encoded data word (X0-XM-1) with encoding coefficients (C0-CM-1), wherein each of (X0-XM-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, X0 is multiplied by each state (C0(0) through C0(k-1)) of the coefficient C0, thereby generating results X0C0(0) through X0C0(k-1). This is repeating for data bits (X1-XM-1) and corresponding coefficients (C1-CM-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 (C0-CM-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 (C0-CM-1). In an embodiment, substantially the same hardware is utilized for processing in-phase and quadrature phase components of the data word (X0-XM-1). In an embodiment, the coefficients (C0-CM-1) represent real numbers. In an alternative embodiment, the coefficients (C0-CM-1) represent complex numbers. In an embodiment, the coefficients (C0-CM-1) are represented with a single bit. Alternatively, the coefficients (C0-CM-1) are represented with multiple bits (e.g., magnitude). In an embodiment, the coefficients (C0-CM-1) represent a cyclic code keying (“CCK”) code set substantially in accordance with IEEE 802.11 WLAN standard.
-
Citations
32 Claims
-
1. A method for correlating an encoded data word (X0-XM-1) with encoding coefficients (C0-CM-1), wherein each of (X0-XM-1) 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 the steps of:
-
(1) multiplying X0 with each state (C0(0) through C0(k-1)) of said coefficient C0, thereby generating results X0C0(0) through X0C0(k-1);
(2) repeating step (1) for data bits (X1-XM-1) and corresponding said coefficients (C1-CM-1), respectively;
(3) grouping said results of steps (1) and (2) into N groups and summing combinations within each of said N groups, thereby generating a first layer of correlation results;
(4) grouping the results of step (3) 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 separate correlation output for each possible state of the complete set of coefficients (C0-CM-1); and
(5) comparing magnitudes output of said separate correlation outputs, thereby identifying a most likely code encoded on said data word. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26)
-
-
27. A system for correlating an encoded data word (X0-XM-1) with encoding coefficients (C0-CM-1), wherein each of (X0-XM-1) 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 (X0-XM-1);
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 (C0-CM-1); and
a magnitude comparator coupled to said final layer of results.
-
-
28. A system for correlating an encoded data word (X0-XM-1) with encoding coefficients (C0-CM-1), wherein each of (X0-XM-1) 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 Xwith each state (C0(0) through C0(k-1)) of said coefficient C0, thereby generating results X0C0(0) through X0C0(k-1);
means for repeating step (1) for data bits (X1-XM-1) and corresponding said coefficients (C1-CM-1), respectively;
means for grouping said results of steps (1) and (2) into N groups and summing combinations within each of said N groups, thereby generating a first layer of correlation results;
means for grouping the results of step (3) 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 separate correlation output for each possible state of the complete set of coefficients (C0-CM-1); and
means for comparing magnitudes output of said separate 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 X0, X1, X2, X3, X4, X5, X6, and X7 from which a code must be extracted;
(2) forming four sets of sample pairs (X0, X1), (X2, X3) (X4, X5), and (X6, X7) from said input samples;
(3) forming four correlation kernels (XiCi+XjCj), (−
XiCi+XjCj), (XiCi−
XjCj), and (−
XiCi−
XjCj) for each set of sample pairs formed in step (2), wherein Xi and Xj represent one of the four sample pairs formed in step (2) and wherein Ci and Cj 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; and
(5) using the sixty-four eight-tuple options formed in step (4) to extract the code from the input samples received in step (1).
-
-
30. A system for parallel correlation detection, comprising:
-
a module for receiving noisy input samples X0, X1, X2, X3, X4, X5, X6, and X7 from which a code must be extracted;
a module for forming four sets of sample pairs (X0, X1), (X2, X3), (X4, X5), and (X6, X7) from said input samples;
a module for forming four correlation kernels (XiCi+XjCj), (−
XiCi+XjCj), (XiCi−
XjCj), and (−
XiCi−
XjCj) for each set of sample pairs formed in step (2), wherein Xi and Xj represent one of the four sample pairs formed in step (2) and wherein Ci and Cj represent predetermined weighting factors; and
a module for combining the correlation kernels formed in step (3) to form a fast correlation transform trellis with sixty-four eight-tuple options.
-
-
31. A method for correlating an encoded data word (X0-XM-1) with encoding coefficients (C0-CM-1), wherein each of (X0-XM-1) 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 the steps of:
-
(1) multiplying X0 with states of said coefficient C0;
(2) repeating step (1) for data bits (X1-XM-1) and corresponding said coefficients, respectively;
(3) grouping said results of steps (1) and (2) into N groups and summing combinations within each of said N groups, thereby generating a first layer of correlation results;
(4) grouping the results of step (3) 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; and
(5) comparing magnitudes output of said correlation outputs, thereby identifying a most likely code encoded on said data word.
-
-
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 Xi and Xj represent one of the sample pairs formed in step (2) and wherein Ci and Cj 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; and
(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).
-
Specification