A fast correlator transform (FCT) algorithm and methods and systems for
implementing same, correlate an encoded data word (X.sub.0 X.sub.M-) with
encoding coefficients (C.sub.0 C.sub.M-1), wherein each of (X.sub.0
X.sub.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.sub.0 is multiplied by each state (C.sub.0(0) through
C.sub.0(k-1)) of the coefficient C.sub.0, thereby generating results
X.sub.0C.sub.0(0) through X.sub.0C.sub.0(k-1). This is repeating for data
bits (X.sub.1 X.sub.M-1) and corresponding coefficients (C.sub.1
C.sub.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.sub.0 C.sub.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.sub.0
C.sub.M-1). In an embodiment, substantially the same hardware is utilized
for processing in-phase and quadrature phase components of the data word
(X.sub.0 X.sub.M-1). In an embodiment, the coefficients (C.sub.0
C.sub.M-1) represent real numbers. In an alternative embodiment, the
coefficients (C.sub.0 C.sub.M-1) represent complex numbers. In an
embodiment, the coefficients (C.sub.0 C.sub.M-1) are represented with a
single bit. Alternatively, the coefficients (C.sub.0 C.sub.M-1) are
represented with multiple bits (e.g., magnitude). In an embodiment, the
coefficients (C.sub.0 C.sub.M-1) represent a cyclic code keying ("CCK")
code set substantially in accordance with IEEE 802.11 WLAN standard.
