Method and apparatus for a parallel correlator and applications thereof
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 IEEEE 802.11 WLAN standard.
-
Citations
55 Claims
-
1-32. -32. (canceled)
-
33. A method for correlating an encoded data word (X0, . . . , XM-1) with encoding coefficients (C0, . . . , CM-1), wherein each of the encoding coefficients has k possible states, wherein M is greater than 1, comprising:
-
(1) generating in parallel the results of the summation
X0C0+X1C1+. . . +XM-1CM-1for valid combinations of the encoding coefficients (C0, . . . , CM-1), omitting summations that result in invalid combinations of the encoding coefficients (C0, . . . , CM-1); and
(2) identifying the combination of encoding coefficients corresponding to a maximum result as the encoding combination. - View Dependent Claims (34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51)
-
-
52. A method for accelerating the parallel correlation of an encoded data word (X0, . . . , XM-1) with encoding coefficients C0, . . . , CM-1, 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 X0, . . . , XM-1 with respective encoding coefficient C0, . . . , CM-1 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.
-
-
53. A system for correlating an encoded data word (X0, . . . , XM-1) with a cyclic code coefficient set (C0, . . . , CM-1) 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
X0C0+X1C1+. . . +XM-1CM-1for all valid combinations of the coefficient set (C0, . . . , CM-1); and
means for identifying the combination of the coefficient set corresponding to a maximum result as the encoding combination. - View Dependent Claims (54, 55)
-
Specification