Abstract:
The present invention groups a set of N, nearly orthogonal, CCK code words into M subgroups, with each subgroup consisting of N/M orthogonal code words. For the 64-ary CCK communication standard for wireless local area networks (WLAN), N is 64 and M is preferably 8. Based on the orthogonal subgrouping, most significant bit (MSB) comparitors, instead of full-scale comparitors, are used to compare cross-correlations for each subgroup. In the subgroup containing the desired maximum correlation, all other cross-correlations, except the maximum, are zero in an ideal case, or very close to zero in a noisy environment due to the selected orthogonality. The maximum correlation value can be distinguished by looking at only the most significant bit or bits among all the cross-correlations. In the subgroups that do not contain the global, maximum correlation value, it does not matter which cross-correlation value is picked. The maximum correlation from all the subgroups, which will include the global maximum from one of the subgroups, are monitored to select the maximum correlation value and the corresponding code word.

Description:
BACKGROUND OF THE INVENTION 
     The present invention relates to spread spectrum communications, and in particular, to a spread spectrum receiver incorporating complementary code keying (CCK). IEEE 802.11(b) provides a standard for wireless local area network communications using complementary code keying. Receivers capable of demodulating CCK modulated signals require extensive circuitry to correlate received data with the numerous possible code words. Traditionally, each received word is correlated with all possible code words for proper correlation. For a 64-word code set, at least 63 full-scale comparitors are necessary for correlation. This vast number of comparitors results in a major hardware cost. There is a need to efficiently correlate received data with the code words in a CCK code set without requiring the extensive amount of components, semiconductor area, and power associated with correlation architectures requiring full-scale comparitors for each code word. 
     SUMMARY OF THE INVENTION 
     The present invention groups a set of N, nearly orthogonal, CCK code words into M subgroups, with each subgroup consisting of N/M orthogonal code words. For the 64-ary CCK communication standard for wireless local area networks (WLAN), N is 64 and M is preferably 8. Based on the orthogonal subgrouping, most significant bit (MSB) comparators, instead of full-scale comparators, are used to compare cross-correlations for each subgroup. In the subgroup containing the desired maximum correlation value, all other cross-correlation values, except the maximum, are zero in an ideal case, or very close to zero in a noisy environment due to the selected orthogonality. The maximum correlation value within the subgroup can be distinguished by looking at only the most significant bit or bits among all the cross-correlations. The maximum correlation values from all the subgroups, which will include the global maximum from one of the subgroups, are monitored to select the maximum correlation value and the corresponding code word. In the subgroups that do not contain the global, maximum correlation value, it does not matter which cross-correlation value is picked. The invention yields substantial savings on hardware costs by reducing the amount of components and silicon required to implement correlation circuitry, and also reduces power consumption. 
    
    
     BRIEF DESCRIPTION OF THE DRAWING FIGURES 
     FIGS. 1A and 1B define a 64-length complementary code keying code set. 
     FIG. 2 is a table defining 8 orthogonal subgroups for the complementary code keying code set of FIGS. 1A and 1B. 
     FIG. 3 is a block representation of a complementary code keying receiver. 
     FIG. 4 is a flow chart outlining the basic flow of the present invention. 
     FIG. 5A is a block representation of maximum decision circuitry in a particular subgroup. 
     FIG. 5B is a block representation of multiple, most significant bit decision circuitry operable within the Structure of FIG.  5 A. 
     FIG. 6 is a block representation of indexing circuitry capable of keeping track of the correlation corresponding to the maximum correlation value. 
     FIG. 7 is a block representation of the overall maximum decision circuitry according to the preferred embodiment. 
     FIG. 8 is a block representation of the overall indexing circuitry according to the preferred embodiment. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     Complementary code keying (CCK) is used in spread spectrum communications according to the standard set forth in IEEE 802.11(b) for wireless Local Area Networks (WLAN). A standard 64-word CCK code set is shown in FIGS. 1A and 1B. The code index is data to be transmitted, and is shown in decimal and binary form. The “length-8 code words” represent symbols corresponding to the data to be transmitted. Those skilled in the art will recognize that other CCK code sets are possible; however, the 64-word CCK code set is used for the purpose of disclosing the present invention. Further, as shown in FIG. 2, the 64-word code set may be divided into subgroups wherein the code words within any one subgroup are orthogonal to one another. FIG. 2 outlines eight subgroups according to the preferred embodiment. 
     Turning now to FIG. 3, a block representation of a CCK receiver  10  is depicted. Generally, a received CCK signal  12  is sampled and digitized using an analog-to-digital converter  14  and down-converted using mixing circuitry  16  and carrier recovery circuitry  18 , which controls the mixing circuitry  16 . The resulting recovered data is continuously fed into decimation circuitry (not shown) to effectively reduce the sampling rate of the complex CCK signal to two times the chip rate of eight chips per symbol. The decimation circuitry typically incorporates a register, such as a flip-flop, and summation circuitry to effectively sum the samples corresponding to a particular chip. Preferably, the decimation circuitry is clocked at a sample rate to provide a decimated CCK signal that is serially shifted into a 16-stage shift register  20 . Notably, the CCK signal is complex and remains complex substantially throughout processing. Signal lines including a diagonal hash mark indicate complex signals. Further, all signals downstream from the analog-to-digital converter  14  are complex. Preferably, these complex signals are represented by real and imaginary digital coordinates, I+jQ, in traditional quadrature form. 
     With the 64-word CCK code set, preferably the shift register  20  can output  16  complex values corresponding to the received data  22 . Pairs of these values are summed using summing circuitry  23  to provide eight complex values  22 . Each complex value  22  corresponds to one of eight chips, which are sent to circuitry  24  capable of performing a Fast Walsh Transform on the eight complex values to provide 64 complex, cross-correlations. These cross-correlations represent the correlation properties of any given received data with each of the 64 code words in the CCK code set. Given the substantially orthogonal nature of the CCK code set, the received data corresponding to one of the 64 code words will have a correlation property significantly larger than the remaining cross-correlations  26 . 
     The present invention provides a significant improvement over the prior art in the ability to rapidly and efficiently determine which of the 64 cross-correlations has the highest correlation property. Reordering circuitry  30  is provided to divide and group the 64 cross-correlations into predefined subgroups wherein the corresponding code words within any one group are orthogonal. The reordering is done according to that defined in FIG.  2 . As such, the cross-correlations are regrouped into eight groups of eight cross-correlations. Each of these eight complex correlations  32  is sent to corresponding subgroup, maximum decision circuitry  34  (SG  1 -SG  8 ). For each subgroup, maximum decision circuitry  34 , a maximum correlation value  36  and a maximum correlation index  38  is provided. The maximum correlation property value  36  corresponds to the maximum value of any of the cross-correlations within the given subgroup. The maximum correlation index  38  provides a reference to the particular cross-correlation, or code word, associated with the maximum correlation property value. The output of each of the maximum decision circuitries  34  identifies the cross-correlation having the greatest correlation value and the correlation value itself. 
     The resulting eight maximum correlation property values  36  and corresponding maximum correlation indices  38  from the eight maximum decision circuitries  34  are provided to an overall maximum decision circuitry  44 , which selects the overall maximum correlation value  40  and a corresponding overall maximum correlation index  42 . From the overall maximum correlation value and index  40 ,  42 , the transmitted data  46  is determined using processing circuitry  48 . 
     Importantly, the present invention is configured to determine the cross-correlation having the greatest value without analyzing the entirety of the complex cross-correlation values for each of the code words. In particular, the present invention is capable of monitoring one or more of the most significant bits of the cross-correlation properties. In general and with reference to FIG. 4, received data is correlated with each possible code word in the CCK code set (block  100 ). The correlation property of the received data for each possible code word is measured (block  102 ). The steps in block  100  and block  102  are simultaneously performed using FWT. These correlation properties are grouped into subgroups where the code words within each subgroup are orthogonal with respect to one another (block  104 ). The maximum correlation property for each subgroup is determined based on the most significant bit or bits of the measured correlation properties. The overall maximum correlation property is determined from the outputs of each of the subgroups (block  108 ). While the maximum correlations for the individual subgroups in the overall correlation is determined, an index is maintained to associate the maximum correlation property with a corresponding code word most likely to be associated with the transmitted data (block  110 ). 
     The preferred configuration of the subgroup maximum decision circuitry  34  is shown in FIGS. 5A and 6. The circuitry for determining the maximum correlation property value  36  is divided into three stages, Stage  1  ( 50 ), Stage  2  ( 52 ) and Stage  3  ( 54 ). The Stage  1  decision circuitry  50  preferably includes four multiplexers  56 . Each multiplexer is capable of receiving two complex cross-correlations  32 . The cross-correlations may be passed through circuitry to perform a magnitude function. The functions may include summing the real and imaginary components of the cross-correlation as shown using summing circuitry  55 . Alternatively, one may look at the largest of the I or Q coordinates, take the sum of the squares, calculate an exact magnitude using the square root of I 2 +Q 2 , or any number of ways to determine exact or approximate magnitude. As such, the four multiplexers  56  together are capable of receiving each of the eight cross-correlations  32  for the given subgroup. For each of these Stage  1  multiplexers  56 , one of the two cross-correlation inputs is fed to MSB detection circuitry  58 , which monitors the most significant bit or bits and provides an output to control the multiplexer  56 . Based on the value of the most significant bit or bits, the multiplexer  56  will pass one of the two cross-correlations appearing at the two inputs. 
     Although the MSB detection circuitry  58  can monitor both of the cross-correlation inputs, only one cross-correlation input need be monitored based on the orthogonality of the code words for each subgroup maximum decision circuitry  34 . In fact, the largest correlation by far will appear at only one of the 64 cross-correlations. Thus, only one subgroup will see the large correlation, and within that subgroup, only one of the eight inputs to the multiplexers  56  will have a significantly large value. Thus, the MSB detection circuitry  58  can monitor one of the two inputs and make a decision on whether or not the large value is present. In Stage  1 , if the large value is present on the line being monitored by the MSB detection circuitry  58 , that value will be passed through the multiplexer on to Stage  2 . If the cross-correlation being monitored is not the large value, based on the most significant bit or bits, then the other line is passed, whether or not the large value is present. As such, the only guarantee at Stage  1  is that if the most significant bit or bits indicate the large correlation value was detected, that value will be passed. Otherwise, it doesn&#39;t matter which low value correlation is propagated through to Stage  2 . 
     Notably, the output of the most significant bit detection circuitry not only controls which input is passed through the multiplexer, but also keeps track of which input was passed. Thus, the output for each of the MSB detection circuitry  58  is monitored. These outputs are DECW, DECX, DECY and DECZ shown in FIG.  6 . These outputs are discussed in further detail below. 
     The Stage  2  decision circuitry  52  is essentially identical to that of half of the Stage  1  decision circuitry, and includes two multiplexers  60 , each having corresponding MSB detection circuitry  62 . Each of the multiplexers  60  of Stage  2  receives the correlation values passed through from the first stage. Based on the most significant bit or bits of one of the corresponding outputs from Stage  1 , the multiplexer and MSB decision circuitry  62  passes the largest value on to the Stage  3  decision circuitry  54 . Preferably, only one of the two inputs for the multiplexer  60  is monitored. If the most significant bit or bits indicate the largest correlation value is present, that value will be passed through to Stage  3 . Otherwise, one value is passed through, but given the likely low correlation values of all cross-correlations other than the proper correlation, the value passed doesn&#39;t really matter. Further, the output of the MSB detection circuitries  62 , DECA and DECB, are used to keep track of the correlation having the largest value passed through to Stage  3 . 
     The Stage  3  decision circuitry  54  has two inputs. The first input is the largest correlation value of CI  1  through CI  4 , and the second input is the largest correlation value of CI  5  through CI  8 . A single multiplexer  64  receives these two inputs. Final MSB detection circuitry  66  monitors one (or both) of these inputs and provides an output to control the multiplexer  64 . This output is also used to keep track of which correlation has the maximum value. In essence, the Stage  1  decision circuitry  50  compares CI  1  and CI  2  and propagates the correlation having the largest value to Stage  2 . The same comparison and propagation occurs for CI  3  and CI  4 ; CI  5  and CI  6 ; and CI  7  and CI  8 . Stage  2  compares pairs of the four outputs from Stage  1  to provide the largest correlation value out of CI  1  through CI  4  and that from CI  5  through CI  8 . Stage  3  makes a final comparison of the remaining two correlation values to determine a maximum correlation value  36  for the subgroup (Max SG). 
     FIG. 5A depicts MSB detection circuitry  58 ,  62 ,  66  for each of the three stages capable of monitoring the most significant bit for one of the inputs. As shown in FIG. 5B, the MSB detection circuitry may monitor multiple ones of the most significant bits with multiple MSB detection circuitry  74  and take a logical OR of the monitored bits using logic gate  72  to provide an output controlling a generic multiplexer  70 . As such, it may be preferable to monitor multiple ones of the most significant bits to an extent that if any of these more significant bits are set, it is likely the maximum correlation value has been detected. 
     Referring to FIGS. 5A and 6, the output of the upper two MSB detection circuitry  58  (DECW and DECX) are provided to another multiplexer  78 . The multiplexer is controlled by the output of the MSB detection circuitry  62  (DECA) of the upper bracket of the Stage  2  decision circuitry  52 . Similarly, multiplexer  80  receives outputs from the MSB detection circuitry  58  (DECY and DECZ) of the lower brackets of the Stage  1  decision circuitry  50 . The output of the MSB detection circuitry  62  of the lower bracket of the Stage  2  decision circuitry  54  (DECB) is used to control multiplexer  80 , Multiplexer  78  operates to keep track of the correlation, which is propagated through the upper bracket of the Stage  1  and Stage  2  decision circuitry  50 ,  52 . Similarly, multiplexer  80  operates to keep track of the correlation value being propagated through the lower bracket of the Stage  1  and Stage  2  decision circuitry  50 ,  52 . 
     The circuitry of FIG. 6 is not directly concerned with the maximum correlation values. Rather, the circuitry of FIG. 6 keeps track of indexing of the decision that is associated with the maximum correlation value. In order to accomplish this indexing, DECW and DECX are provided to multiplexer  78 , which is controlled by DECA. The outputs of multiplexer  78  and DECA are merged to form a two-bit value at combining circuitry  82 . Likewise, DECY and DECZ are fed to multiplexer  80 , which is controlled by DECB. The output of multiplexer  80  and DECB are merged to form a 2-bit value by combining circuitry  84 . The two 2-bit values from combining circuitry  82  and combining circuitry  84  are each provided to multiplexer  86 , which is controlled by DECSG. The output of multiplexer  86  and DECSG are merged to form a 3-bit value at combining circuitry  88 . The resulting 3-bit value identifies which of the eight correlations, CI  1  through CI  8  have the maximum correlation value. For example, if CI  4  has the maximum correlation value, the output of the corresponding MSB detection circuitry  58  will set DECX equal one. Given the orthogonality within any subgroup, C  1  through C  4 , and C  5  through C  8 , will all have their most significant bit or bits equal zero. As such, DECW, DECY and DECZ will all equal zero. Further, the output of the Stage  1  multiplexers  56  will all equal zero, with the exception of the multiplexer  56  comparing CI  3  and CI  4 , which will be set to one. As such, the corresponding MSB detection circuitry  62  will set DECA equal one. DECB will be zero, since all the MSBs of the corresponding correlation values will be zero. Thus, the upper bracket in Stage  2  will result in its multiplexer  60  having an output equal one. The lower bracket multiplexer  60  will have an output equal to zero. Thus, the corresponding MSB selector  66  in Stage  3  will be set to zero, thus selecting the output of the upper stage multiplexer  60  from Stage  2  as the maximum correlation value. Thus, the cross-correlation having the greatest value is propagated through Stage  1 . Since DECX and DECA were set to one during this progression and DECW, DECY, DECZ, DECB and DECSG were all set to zero, the circuitry shown in FIG. 6 will provide a 3-bit output identifying CI  4  as the correlation having the greatest correlation value. Notably, the 3-bit value can select any one of the eight corresponding inputs. 
     Turning now to FIG. 7, each of the eight subgroup, maximum decision circuitries  34  are shown, each having a maximum correlation value  36  and a maximum correlation index  38 . Comparitor circuitry  90  monitors each of the subgroup maximum correlation values to determine which subgroup contains the maximum correlation value and to provide the corresponding 3-bit subgroup index  92  and the maximum value itself  93 . Referring now to FIG. 8, the maximum correlation index for each of the subgroups  38  (DEC SG 1  Through DEC SG 8 ) are provided to indexing multiplexer  96 , which is controlled by the subgroup index  92 . DEC SG 1  through DEC SG 8  represent the correlation associated with the maximum value within each subgroup. The subgroup index  92  represents the subgroup having the maximum correlation value. As such, the output of multiplexer  96  is merged with the SG index using combining circuitry  98  to form a 6-bit word wherein three of the bits identify the subgroup having the maximum value and the remaining three bits identify the correlation within that subgroup as associated with the maximum correlation for all of the possible 64 code words. The 6-bit word represents the overall maximum correlation index  42 , which may directly or indirectly represent the received data. If the overall maximum correlation index directly represents the words, this value may be simply latched and recognized as the data. Otherwise, processing circuitry  48  may be used to associate the overall maximum correlation index  42  with a table containing corresponding data. As such, the index is essentially a pointer. Furthermore, the index could be run through an algorithm to determine or associate the index with the data. 
     The most significant bit circuitry is preferably configured to operate on correlation magnitude values. As such, determining the magnitude from complex values may take many forms. For example, one may look at the largest of the I or Q coordinates, take the sum of the squares, calculate an exact magnitude using the square root of I 2 +Q 2 , or any number of ways to determine exact or approximate magnitude. The orthogonality of the code words associated with the subgroups results in significant differences between the proper correlation value and all other cross-correlation values. Even with significant noise, the difference between the maximum correlation value for the proper correlation and all other correlation values within a subgroup are generally at least in order of magnitude. Those of ordinary skill in the art will recognize variations and modifications to carry out the inventive concept disclosed within the above description. All such variations and modifications are considered within the scope of the disclosure and the following claims. Examples of such modifications may include using code sets having more or less than 64 code words. Further, the orthogonal subgroupings may vary, for example, the 64-word code set may be broken down into  16  groups of four orthogonal code words. Further, other reduced complexity decision circuitry may be created that utilizes the orthogonal subgroupings.