# Patent

## Title
Ranging code detection

## Abstract

A ranging code present in a transmission from a transmitter to a receiver can be detected, and hence a time offset can be determined. For each of the possible ranging codes in a transmitted signal, a correlation is formed between a received signal and the ranging code for multiple subcarriers in the received signal. For multiple adjacent ranging subcarriers, the correlation is multiplied by a conjugate of the correlation of an adjacent ranging subcarrier in order to form a differential phase value. At least one ranging code in the transmitted signal can then be determined based on the differential phase values for said plurality of subcarriers. A time offset in the transmission from the transmitter to the receiver can then be determined, based on the differential phase values for the subcarriers, and based on the determined ranging code.

## Background
BACKGROUND OF THE INVENTION
This invention relates to a method for detection of a ranging code, and to an apparatus implementing the method.
In wireless communications systems, an Orthogonal Frequency Division Multiplexed (OFDM) system is one in which a transmitter sends data to a receiver using a number of different subcarrier frequencies within a transmission frequency band. The receiver then has to detect the data transmitted on each of the carrier frequencies, in order to be able to recreate the original transmitted signal.
In an Orthogonal Frequency Division Multiple Access (OFDMA) system, there may be multiple users, transmitting data to a single receiver. One such system is the so-called WiMAX system, specified in the IEEE 802.16e standard, in which a number of users are able to communicate with an access point. As the users are able to move within the coverage area of the access point, this allows the users to have high data rate wireless access to a communications network while moving.
In the IEEE 802.16e system, the available subcarriers are divided into subchannels, and each of the users can be allocated one or more of the subchannels. It is then the function of a base station to receive transmissions from the users, which may be transmitting simultaneously, and to detect and decode those transmissions. One factor, which must be taken into consideration by the base station, is that the users may be located at different distances from the base station, and therefore signals transmitted from those users will take different lengths of time to reach the base station. In order to be able to handle the transmissions from such users, the base station needs to be able to determine the distances of the users from the base station, and hence the times taken for their transmissions to reach the base station, in order to be able to achieve proper synchronization of operation.
In order to allow the base station to makes these determinations, the user devices transmit ranging codes in a specified ranging subchannel, either when the user device is initially trying to connect to the base station, or periodically thereafter in order to take account of movement of the user device relative to the base station. By detecting the received ranging code, the base station is able to synchronize to subsequent transmissions from that user device.
SUMMARY OF THE INVENTION
According to an aspect of the invention, a ranging code present in a transmission from a transmitter to a receiver can be detected, and hence a time offset can be determined. For each of the possible ranging codes in a transmitted signal, a correlation is formed between a received signal and the ranging code for multiple subcarriers in the received signal. For multiple adjacent ranging subcarriers, the correlation is multiplied by a conjugate of the correlation of an adjacent ranging subcarrier in order to form a differential phase value. At least one ranging code in the transmitted signal can then be determined based on the differential phase values for said plurality of subcarriers. A time offset in the transmission from the transmitter to the receiver can then be determined, based on the differential phase values for the subcarriers, and based on the determined ranging code.
According to another aspect of the invention, there is provided a method of generating a required ranging code, wherein the required ranging code forms part of a specific one of a plurality of groups of ranging codes, the groups of ranging codes together forming a set of available ranging codes, and the method comprising:
on initialization of a device, applying an initialization sequence to a shift register of a pseudorandom sequence generator;
clocking bits through said shift register to generate said set of available ranging codes;
during said clocking bits through said shift register, storing bits present in said shift register at a start of a first ranging code in each of said groups of ranging codes; and
when a required ranging code is identified:
applying to said shift register the stored bits present in said shift register at the start of the first ranging code in said specific one of said plurality of groups of ranging codes; and
clocking bits through said shift register to generate the ranging codes of said specific one of said plurality of groups of ranging codes.



BRIEF DESCRIPTION OF DRAWINGS
FIG. 1 is a block schematic diagram of a wireless communications system in accordance with the present invention.
FIG. 2 is a more detailed block schematic diagram of a base station in the wireless communications system of FIG. 1.
FIG. 3 illustrates the form of a ranging signal transmitted in the wireless communications system of FIG. 1.
FIG. 4 illustrates an alternative form of the ranging signal transmitted in the wireless communications system of FIG. 1.
FIG. 5 is a flow chart, illustrating a method in accordance with an aspect of the present invention.
FIG. 6 is a block schematic diagram illustrating a component in the base station of FIG. 2.
FIG. 7 is a flow chart illustrating a use of the component shown in FIG. 6.
FIG. 8 is a flow chart illustrating a further use of the component shown in FIG. 6.
FIG. 9 illustrates the results of a stage in the process of FIG. 5.
FIG. 10 illustrates the results of a second stage in the process of FIG. 5.



DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS
FIG. 1 is a schematic representation of a wireless communications system incorporating the present invention. In this illustrated embodiment, the wireless communications system is a WiMAX system, operating in accordance with the IEEE 802.16e standard.
A base station 10, with an antenna 11 for transmitting and receiving wireless signals, also has a connection to a computer network, such as the internet 12. Subscriber stations (SS) 14, 16 are then able to move in the area around the base station 10 and communicate with the base station 10 over a wireless connection, in order to be able to connect to the internet 12. It will be appreciated that, although two subscriber stations 14, 16 are shown in FIG. 1, there may be any number of such subscriber stations.
The WiMAX system is an Orthogonal Frequency Division Multiple Access (OFDMA) system, in which the available frequency band is divided into a number of subcarriers, and data can be transmitted on each of these subcarriers. The subcarriers are grouped into subchannels, and, in each OFDM symbol period, each of the multiple users 14, 16 is allocated at least one of the subchannels, on which it can transmit data to the receiver 10. Thus, the subscriber stations can be transmitting data simultaneously to the base station 10.
FIG. 2 is a more detailed illustration of parts of the base station 10. Except as described in more detail below, the base station is generally conventional, and its operation will be understood by the person of ordinary skill in the art.
Briefly, however, in the transmit path 20 of the base station 10, data for transmission to each of the active subscriber stations 14, 16 is passed from the lower Media Access Control (MAC) block 22 to a respective data handling block 24a, 24b, 24c, each of which includes a respective randomization block 26, Forward Error Correction (FEC) coding block 28, interleaver 30, and mapper 32. Although three data handling blocks are shown in FIG. 2, it will be appreciated that there may be any number of such blocks. The data from the data handling blocks 24a, 24b, 24c is then passed to a transmit subchannelization block 34, and to a transmit OFDM kernel 36.
The data is then passed to a crest factor reduction (CFR) block 38, digital upconverter (DUC) 40 and digital predistortion (DPD) block 42, before being passed to a power amplifier and antenna (not shown) for transmission over the air interface, and for reception by the relevant subscriber stations.
In the receive path 50 of the base station 10, signals from the antenna (not shown) are passed to a digital downconverter (DDC) 52, and then to a receive OFDM kernel 54. At the same time, the output signals from the DDC 52 are passed to a time synchronization and coarse frequency synchronization block 56, and the synchronization output from this block is also passed to the OFDM kernel 54. The OFDM kernel 54 includes a Fast Fourier Transform (FIT) block, for converting the received signal from the time domain to the frequency domain. That is, the output of the FFT block contains information about the signals received on each of the subcarriers making up the OFDM signal.
The output from the OFDM kernel 54 is passed to a de-subchannelization block 58, for separation of the subcarriers into the subchannels. The data on each of the subchannels is then passed to a respective signal detection block 60a, 60b, 60c, each of which includes a channel estimation block 62, frequency offset correction block 64, zero-forcing (ZF) block equalizer 66, de-mapper 68, de-interleaver 70, Forward Error Correction (FEC) decoder 72 and de-randomization block 74. The outputs from the signal detection blocks 60a, 60b, 60c are then passed to the lower Media Access Control (MAC) block 22.
Since the subscriber stations 14, 16 may be located at different distances from the base station 10, signals transmitted from those subscriber stations during the same OFDM symbol period will then be received at the base station 10 at different times. The IEEE 802.16e standard therefore allows for the transmission by the subscriber stations 14, 16 of ranging codes. More specifically, the standard specifies 256 different ranging codes, each having 144 bits. When a subscriber station is first connecting to the WiMAX system, or is first connecting to a base station during a handover procedure, or is contending for extra bandwidth, or at periodic intervals during a connection, the subscriber station transmits one of the ranging codes on a ranging subchannel which includes 144 subcarriers.
FIG. 3 illustrates the transmission of a ranging code from a subscriber station during initial ranging. Specifically, during one OFDM symbol period T1, a ranging code is transmitted on the subcarriers of the ranging subchannel. Of the specified ranging codes, some are allocated to initial ranging, and the subscriber selects one of these allocated ranging codes (indicated in FIG. 3 as Code Y) at random. As is conventional in OFDM systems, a portion of the samples from the end of the signal transmitted during the OFDM symbol period T1 are also transmitted at the start of the OFDM symbol period T1 as a cyclic prefix (CP). During the next OFDM symbol period T2, the same ranging code (Code Y) is transmitted on the subcarriers of the ranging subchannel. A portion of the samples from the start of the signal transmitted during the OFDM symbol period T2 are also transmitted during a guard interval (GRD) at the end of the OFDM symbol period T2.
FIG. 4 illustrates an alternative form of the transmission of a ranging code from a subscriber station during initial ranging. Specifically, in this case, during one OFDM symbol period T3, a randomly selected one of the ranging codes allocated to initial ranging (indicated in FIG. 4 as Code X) is transmitted on the subcarriers of the ranging subchannel. Again, a portion of the samples from the end of the signal transmitted during the OFDM symbol period T3 are also transmitted at the start of the OFDM symbol period T3 as a cyclic prefix (CP). During the next OFDM symbol period T4, the same ranging code (Code X) is transmitted on the subcarriers of the ranging subchannel. A portion of the samples from the start of the signal transmitted during the OFDM symbol period T4 are also transmitted during a guard interval (GRD) at the end of the OFDM symbol period T4.
In this case, however, during the next OFDM symbol period T5, the next one of the ranging codes allocated to initial ranging (that is, Code X+1) is transmitted on the subcarriers of the ranging subchannel. Again, a portion of the samples from the end of the signal transmitted during the OFDM symbol period T5 are also transmitted at the start of the OFDM symbol period T5 as a cyclic prefix (CP). During the next OFDM symbol period T6, the same ranging code (Code X+1) is transmitted on the subcarriers of the ranging subchannel. A portion of the samples from the start of the signal transmitted during the OFDM symbol period T6 are also transmitted during a guard interval (GRD) at the end of the OFDM symbol period T6.
In either case, as will be described in more detail below, the receiver detects the presence of the ranging code in the received signals, and is then able to synchronize to the transmissions from that subscriber station.
Specifically, the output from the OFDM kernel 54 is also passed to a ranging block 76, which determines the time offsets in the signals received from the subscriber stations 14, 16. The output from the ranging block 76 is passed to the lower Media Access Control (MAC) block 22.
Although FIGS. 3 and 4 illustrate the transmission of ranging codes during initial ranging, it is will be clear that the requirement to detect a ranging code, and to use this to determine a time offset in a transmission, is the same during periodic, bandwidth and handover ranging.
FIG. 5 is a flow chart, illustrating the procedure carried out in the receive path 50, and in particular in the ranging block 76.
In step 100 of the procedure, the OFDM signal is received and, in step 102, it is transformed into the frequency domain by the FFT block in the receive OFDM kernel 54.
The method proceeds from the recognition that, when a received ranging code is correlated in turn with the possible transmitted ranging codes, the magnitude of the correlation will be greatest when the received ranging code is correlated with the actually transmitted ranging code. Moreover, the propagation time delay of the transmitted ranging code will add a phase delay to the received signal, and the amount of the phase delay will vary from one subcarrier to the next, because a constant time corresponds to a varying phase angle as the subcarrier frequency varies. The present invention therefore uses the difference in the phase angle, between two subcarrier frequencies, as a measure of the time delay.
In step 104 of the method, therefore, one of the possible transmitted ranging codes is selected.
The IEEE 802.16e standard specifies 256 different ranging codes, each having 144 bits. Of these specified ranging codes, a subset are available to each base station, and, of these available ranging codes, some are for use as initial ranging codes, some are available for use as periodic ranging codes, some are available for use for bandwidth requests, and some are available for use for handover ranging. The generation of the ranging codes will now be described in more detail, with particular reference to the situation where the ranging codes are 144 bits long. However, it will be apparent that the same technique for generating ranging codes can be applied to any desired code length.
These ranging codes are defined by means of a pseudorandom sequence generator, as shown in FIG. 6. As is generally known in the art, the pseudorandom sequence generator 160 includes a shift register 162 comprising a number of logic devices, in this case fifteen flip-flops F1, F2, F3, . . . , F15. Starting from an initialization sequence of fifteen bits, applied to the fifteen flip-flops F1, F2, F3, . . . , F15, a sequence of output bits are generated. Specifically, during each clock period, the binary values stored in four of the flip-flops, namely the flip-flops F1, F4, F7, and F15, are supplied to the inputs of an OR gate 164.
The output of the OR gate 164 is then supplied as an output bit c on the output line 164, and is also fed back to the first flip-flop F1 of the shift register 162. Meanwhile, each of the bits stored in the flip-flops F2, F2, F3, . . . , F15 is passed to the next flip-flop in the shift register 162.
The pseudorandom sequence generator 160 therefore generates a sequence of output bits c. Each successive group of 144 consecutive output bits forms one of the ranging codes in the set of ranging codes specified in the standard.
In order to allow the base station to generate a desired ranging code, one possibility would be provide an initialization sequence, and then clock through the codes until the desired code is reached. However, this may take an undesirably long time before reaching the desired code. Alternatively, it would be possible to store the bits stored in the shift register 162 at the start of all of the specified ranging codes, or at least at the start of all of the subset of ranging codes available to that base station. However, this would require relatively large amounts of memory.
FIG. 7 illustrates the operation of the pseudorandom sequence generator 160 in the preferred embodiment of this invention. Specifically, in step 180, the device is first powered up, and then, in step 182, the initialization sequence is applied to the shift register 162, as shown in FIG. 6. As mentioned above, this causes the complete set of ranging codes to be generated, in sequence. During this operation, the device notes and stores four shift register settings, namely those at the start of the first initial ranging code, at the start of the first periodic ranging code, at the start of the first ranging code for bandwidth requests, and at the start of the first handover ranging code. This is shown as step 184 in the flow chart of FIG. 7.
FIG. 8 is a flow chart illustrating the generation of the ranging codes during the receiver operation. Specifically, in subsequent use of the device, the base station may receive a ranging code during a time slot that is reserved for initial ranging or handover ranging. Alternatively, the base station may receive a ranging code during a time slot that is reserved for periodic ranging or bandwidth contention ranging. In either case, this is shown as step 190 in FIG. 8.
The process then passes to step 192, in which one of the groups of ranging codes is selected. Where the ranging code was received during a time slot reserved for initial ranging or handover ranging, then either the group of initial ranging codes or the group of handover ranging codes may be selected. The selection may be predetermined, or may be configurable. Similarly, where the ranging code was received during a time slot reserved for periodic ranging or bandwidth contention ranging, then either the group of periodic, ranging codes or the group of bandwidth contention ranging codes may be selected. Again, the selection may be predetermined, or may be configurable.
In step 194, the stored shift register setting, associated with the first ranging code in the selected group, is applied to the fifteen flip-flops F1, F2, F3, . . . , F15 of the shift register 162. As described above, the next 144 bits output from the pseudorandom sequence generator 160 form the first ranging code in the selected group. When a ranging code has been generated, the process passes to step 196, in which it is determined whether all of the ranging codes in the first selected group have been generated. If not, the process returns to step 194, in which the next 144 bits are output from the pseudorandom sequence generator 160 to form the next ranging code in the selected group, and then to step 196.
When it is determined in step 196 that the first selected group is complete, that is, that all of the codes in that group have been generated, then the process passes to step 198. Where the ranging code was received during a time slot reserved for initial ranging or handover ranging, and one of these groups of codes was selected as the first group in step 192, the other becomes the second group. Similarly, where the ranging code was received during a time slot reserved for periodic ranging or bandwidth contention ranging, and one of these groups of codes was selected as the first group in step 192, the other becomes the second group.
In step 198, the stored shift register setting, associated with the first ranging code in the second group, is applied to the fifteen flip-flops F1, F2, F3, . . . , F15 of the shift register 162. As described above, the next 144 bits output from the pseudorandom sequence generator 160 form the first ranging code in the selected group. When a ranging code has been generated, the process passes to step 200, in which it is determined whether all of the ranging codes in the second group have been generated. If not, the process returns to step 198, in which the next 144 bits are output from the pseudorandom sequence generator 160 to form the next ranging code in the second group, and then to step 200.
When it is determined in step 200 that the second group is complete, that is, that all of the codes in that group have been generated, then the process passes to step 202, and ends.
It should be noted that, although the process of FIG. 5 is intended for use in the base station of a mobile communications system, the procedures of FIGS. 7 and 8, for generating ranging codes in an efficient manner, can also be performed in a mobile communications device, for example such as a laptop computer having wireless connectivity, in order to generate the required ranging codes.
Returning now to the description of FIG. 5, it was mentioned above that, in step 104 of the method, one of the possible transmitted ranging codes is generated, and this is done using the methods described above.
In each subcarrier of the subchannel, the received frequency domain signal R(k) in the kth subcarrier includes the transmitted ranging code C(k) and the effects of the channel H(k). That is:

R(k)=C(k)H(k)exp[−j2πkΔn/N], 

where N is the number of subcarriers, and Δn represents the transmission delay.

In step 104, one of the possible transmitted ranging codes is generated, and, in step 106 of the process, this is autocorrelated with the received frequency domain signal R(k). At this stage, it is of course not known whether the generated ranging code is in fact the transmitted ranging code C(k). However, if the generated ranging code is in fact the transmitted ranging code C(k), the result of the autocorrelation in step 106 is given by:

C(k)R(k)=H(k)exp[−j2πkΔn/N]

It will be noted that the result of this calculation varies with the subcarrier number k. In step 108, this effect is removed by multiplying the result of the autocorrelation step for the kth subcarrier with the result for an adjacent (k−1)th subcarrier in the ranging channel.
The result S(k) of this multiplication is therefore:




  
    
      
        
          S
          ⁡
          
            (
            k
            )
          
        
        =
        
        ⁢
        
          
            C
            ⁡
            
              (
              k
              )
            
          
          ⁢
          
            R
            ⁡
            
              (
              k
              )
            
          
          ⁢
          
            (
            
              
                C
                ⁡
                
                  (
                  
                    k
                    -
                    1
                  
                  )
                
              
              ⁢
              
                R
                ⁡
                
                  (
                  
                    k
                    -
                    1
                  
                  )
                
              
            
            )
          
          *
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            H
            ⁡
            
              (
              k
              )
            
          
          ⁢
          H
          *
          
            (
            
              k
              -
              1
            
            )
          
          ⁢
          
            exp
            ⁡
            
              [
              
                
                  -
                  j2πΔ
                
                ⁢
                
                  
                
                ⁢
                
                  n
                  /
                  N
                
              
              ]
            
          
        
      
    
  




Thus, assuming that the channel is constant over the two subcarriers, the result S(k) of the multiplication in step 108 is dependent only on Δn.
In step 110, this process is repeated across the ranging channel. That is, the autocorrelation of step 106 is performed for each subcarrier in the ranging channel, and the multiplication of step 108 is performed for each of the subcarriers in the ranging channel, for which the immediately preceding subcarrier is also in the ranging subchannel. The ranging channel is not contiguous, that is, it does not contain only adjacent subcarriers. The repetitions of step 110 must therefore ensure that the multiplication of step 108 is performed between two adjacent subcarriers.
In step 112, the results of the repeated multiplications are used to detect the transmitted ranging code. This step relies on the fact that, where the autocorrelation of step 106 is performed using a ranging code that is in fact the transmitted ranging code C(k), the result S(k) of the multiplication in step 108 is dependent only on Δn. This means that the results of the repeated multiplications performed in step 110 will in that event tend to be similar to each other. In step 112, it is determined whether the results of the repeated multiplications performed in step 110 are sufficiently similar to lead to a conclusion that the ranging code in use is the transmitted ranging code.
This can be carried out by performing steps 106, 108 and 110 for all possible ranging codes, and then selecting a ranging code as the most likely transmitted ranging code, or by performing steps 106, 108 and 110 for possible ranging codes until one of them meets some threshold, at which point it is selected as the most likely transmitted ranging code without testing the other possible ranging codes.
FIG. 9 is a representation of the results of the multiplication of step 108, for one particular possibly transmitted ranging code. In FIG. 9, the complex numbers S(1), S(2), . . . , S(5), haying the arguments φ(1), φ(2), . . . , φ(5) respectively, are shown plotted in the complex plane. This assumes that there are five pairs of adjacent subcarriers on which the multiplication of step 108 can be performed. It will be appreciated that any number of such pairs may be used in practice.
As mentioned above, where the autocorrelation of step 106 is performed using a ranging code that is in fact the transmitted ranging code C(k), the result S(k) of the multiplication in step 108 is dependent only on Δn, and so the results of the repeated multiplications performed in step 110 will tend to be similar to each other. This will have the consequence that the arguments φ(1), φ(2), . . . , φ(5) will tend to be similar to each other, and this in turn will have the consequence that the overall magnitude of the sum of the results S(1), S(2), . . . , S(5) will tend to be relatively large, compared with the power of the received signals.
Thus, one possibility for detecting the code in step 112 is to select the possible ranging code which gives the largest value for this overall magnitude M:




  M
  =
  
    
    
      
        ∑
        
          n
          =
          1
        
        s
      
      ⁢
      
        
      
      ⁢
      
        S
        ⁡
        
          (
          n
          )
        
      
    
    
  




Another possibility is to examine the variance of the arguments φ(1), φ(2), . . . , φ(5), and to select the possible ranging code which gives the smallest value for this variance V:

V=var(arg(S(n)))

Alternatively, it is possible to select a possible ranging code for which the variance V is below a threshold.
In step 114, when the most likely candidate for the transmitted ranging code has been selected, the previously obtained results for that ranging code are now used to determine the timing offset.
As noted above, the argument of the result S(k) of the multiplication in step 108 is dependent on Δn. The value of Δn is directly related to the timing offset Δt. FIG. 10 is therefore a repeat of the plot of FIG. 9. Again, there are at least two possible ways in which these results can be used to obtain a value for the timing offset.
Firstly, the results S(1), S(2), . . . , S(5) can be summed as shown in FIG. 10, with the value for the timing offset being derived from the argument φ(T) of their sum. That is:




  
    Δ
    ⁢
    
      
    
    ⁢
    t
  
  =
  
    f
    ⁡
    
      (
      
        arg
        ⁡
        
          (
          
            
              ∑
              
                n
                =
                1
              
              5
            
            ⁢
            
              
            
            ⁢
            
              S
              ⁡
              
                (
                n
                )
              
            
          
          )
        
      
      )
    
  




Alternatively, the value for the timing offset can be derived from the mean of the arguments φ(1), φ(2), . . . , φ(5). That is:




  
    Δ
    ⁢
    
      
    
    ⁢
    t
  
  =
  
    
      f
      ⁡
      
        (
        
          
            
              ∑
              
                n
                =
                1
              
              5
            
            ⁢
            
              
            
            ⁢
            
              Φ
              ⁡
              
                (
                n
                )
              
            
          
          5
        
        )
      
    
    =
    
      f
      (
      
        mean
        ⁡
        
          (
          
            arg
            ⁡
            
              (
              
                S
                ⁡
                
                  (
                  n
                  )
                
              
              )
            
          
          )
        
      
    
  




There is thus described a method for determining the time offset using the received ranging code.
It should be noted that, in some cases, the base station 10 will have multiple antennas, or, put another way, the antenna 11 shown in FIG. 1 may be made up of multiple antenna elements. In that case, it is possible to detect a separate received signal from each of the antenna elements.
In accordance with an embodiment of the invention, each of these separate received signals is transformed into the frequency domain, and correlated in turn with each of the possible ranging codes, as described above with reference to steps 100-110 of the process shown in FIG. 5. Then, in order to perform the determination described with reference to step 112 of the process shown in FIG. 5, the results of the repeated multiplications performed in step 110 are combined. That is, for each of the possible ranging codes, a single complex number is formed, by adding together the results obtained for each of the pairs of adjacent subcarriers in each of the separate received signals.
As before, the ranging code can be selected that gives the largest value for the magnitude of the overall result, or which first meets some predetermined magnitude criterion, or which has the smallest variance between the arguments of the components of the complex number, or which first meets some predetermined variance criterion.
Combining the results in this way is an efficient way of making use of all available information to detect the ranging code, without requiring additional hardware.
Where the time offset may be greater than one OFDM symbol period, the methods described above can be performed over three correlation windows, overlapping with three consecutive received symbols. The following table shows the correlation outputs during those three correlation windows, depending on the relationship between the timing offset Δt, the OFDM symbol period ts, and the cyclic prefix tcp.















Correlation window












Delay
1
2
3







 0 ≦ Δt < tcp 
high
high
low



 tcp ≦ Δt < ts  
low
high
low



  ts ≦ Δt < ts + tcp 
low
high
high



ts + tcp ≦ Δt < 2ts + tcp
low
low
high



2ts + tcp ≦ Δt < 3ts
low
low
low










When the time offset has been determined, it may also be necessary to compensate for any difference between the frequencies on which the subscriber station is transmitting and the frequencies generated in the base station itself.
In some cases, this correction for carrier frequency offset will have been performed before ranging occurs. However, the results of the method described above can also be used to calculate the carrier frequency offset, or to refine a previous calculation of the carrier frequency offset.
Specifically, in step 116 of the process shown in FIG. 5, the carrier frequency offset can be calculated from the previously determined results.
Once the transmitted ranging code has been detected, in step 112 above, it is possible to determine the timing offset in that particular received signal. Then, it is possible to perform a time domain correlation of the received signal with a delayed version of itself at one time instant only, corresponding to the detected timing offset. This exploits the fact that the code is repeated during initial ranging, and that, therefore, autocorrelation of one symbol with the next will have a phase equal to the phase shift over one symbol. This therefore allows the carrier frequency offset to be determined.
As an alternative to this, once the ranging code has been detected, and the timing offset has been determined, it is possible to perform a time domain correlation of the received signal with a time domain version of the ranging code at one time instant only, corresponding to the detected timing offset. As the time domain version of the ranging code should be free of noise, this should improve the performance.
As a further alternative, instead of determining the timing offset and then performing the time domain correlation at only one time instant, corresponding to the detected timing offset, it is possible to perform a time domain correlation of the received signal with a delayed version of itself for all received samples, and then store the results. Then, when the transmitted ranging code has been detected, and the timing offset has been determined, it is possible to determine which of the stored results should be used to determine the carrier frequency offset, based on the detected timing offset.
In the case of this further alternative, the results of the time domain correlations can be used to help provide a more accurate detection of the timing offset. The time domain correlation will include peaks corresponding to the ranging codes, but cannot be used on its own as a measure of the timing offset because there is no mechanism for determining which of the peaks is associated with any particular ranging code (and hence with any particular user). However, if one of the peaks in the frequency domain correlation is close to one of the peaks in the time domain correlation, it is very likely that they are associated with the same ranging code, and hence with the same user. Then, the positions of the two peaks can be used together to generate a final value for the timing offset. For example, a value intermediate the positions of the two peaks can be used as a final value.
There are therefore described methods allowing reception of signals, which can be implemented efficiently, while providing good results.

## Claims

1. A method of determining a time offset at a receiver, the method comprising:
selecting a ranging code from a plurality of ranging codes based, at least in part, on a cost criteria;
for each subcarrier from a plurality of subcarriers in a received signal, determining a correlation between data received on the respective subcarrier and the selected ranging code;
for each of a plurality of pairs of subcarriers from said plurality of subcarriers:
determining a correlation between the data received on each subcarrier in the respective pair of subcarriers, wherein the determination is based, at least in part, on the selected ranging code; and
determining a respective signal phase from the correlation; and

determining the time offset based, at least in part, on an average value of the plurality of determined signal phases corresponding to the plurality of pairs of subcarriers and the selected ranging code.

2. The method of claim 1, wherein determining the correlation comprises multiplying a correlation for a first subcarrier from the pair of respective subcarriers with a conjugate of a correlation for a second subcarrier from the respective pair of subcarriers to form a complex number.

3. The method of claim 2, wherein determining the time offset comprises determining a difference between arguments in two complex numbers derived from said plurality of pairs of subcarriers.

4. The method of claim 3, wherein the two of said complex numbers are obtained from pairs of subcarriers that are separated by the same number of available subcarriers.

5. The method of claim 3, wherein the two of said complex numbers are obtained from pairs of adjacent subcarriers.

6. The method of claim 1, further comprising detecting a correlation between the received signal and each of a plurality of possibly transmitted ranging codes.

7. The method of claim 6, wherein, for each of said plurality of possibly transmitted ranging codes, the step of determining the correlation comprises: multiplying a correlation for a first subcarrier from the respective pair of subcarriers with a conjugate of a correlation for a second subcarrier from the respective pair of subcarriers to form a complex number.

8. The method of claim 1, further comprising selecting the ranging code from said plurality of possibly transmitted ranging codes, based on a variance of arguments of said complex numbers derived from said plurality of pairs of subcarriers.

9. The method of claim 1, wherein each of the plurality of pairs of subcarriers are separated by one available subcarrier.

10. The method of claim 1, wherein the step of determining the correlation is performed for each of a plurality of received signals.

11. The method of claim 10, wherein said plurality of received signals are received at respective antennas in said receiver.

12. A method of determining a ranging code present in a received signal, the method comprising:
for each of a plurality of possible ranging codes in the received signal:
forming a plurality of correlation values, each between the possible ranging code and a respective ranging subcarrier from a plurality of ranging subcarriers in the received signal; and
for each of a subplurality of the plurality of ranging subcarriers, multiplying the corresponding correlation value by a conjugate of a correlation value of an adjacent ranging subcarrier in the plurality of ranging subcarriers to produce a complex number;

determining a variance of the complex numbers corresponding to each of the subplurality;
identifying a ranging code from the plurality of possible ranging codes as corresponding to the smallest variance; and
selecting the identified ranging code as the ranging code present in the received signal.

13. A method of estimating a carrier frequency offset in a received signal, the method comprising:
performing a time domain correlation between the received signal and a delayed version of the received signal at a plurality of time instants;
estimating a ranging code embedded in the received signal from a plurality of ranging codes based, at least in part, on a cost function;
subsequent to said performing a time domain correlation, estimating a time offset in said received signal based, at least in part, on the estimated ranging code; and
estimating said carrier frequency offset based, at least in part, on the time domain correlation between the received signal and a delayed version of the received signal at one of said time instants, wherein the delayed version of the received signal is delayed by an amount of time equal to the estimated time offset.

14. A ranging code detector operable to detect a ranging code present in a received signal, the ranging code detector comprising:
a correlator, the correlator operable to, for each of a plurality of possible ranging codes in the received signal:
form a plurality of correlation values, each between the possible ranging code and a respective ranging subcarrier from a plurality of ranging subcarriers in the received signal; and

a detector, the detector operable to, for each of a subplurality of the plurality of ranging subcarriers:
multiply the corresponding correlation value by a conjugate of a correlation value of an adjacent ranging subcarrier in the plurality of ranging subcarriers to produce a complex number;
determine a variance of the complex numbers corresponding to the subplurality;
identify a ranging code from the plurality of possible ranging codes as corresponding to the smallest variance; and
select the identified ranging code as the ranging code present in the received signal.

15. A time offset detector for determining a time offset at a receiver, the time offset detector comprising:
a selector operable to select a ranging code from a plurality of ranging codes based, at least in part, on a cost criteria;
a correlator operable to determine, for each subcarrier in a plurality of subcarriers, a correlation between the respective subcarrier and the selected ranging code; and
a detector operable to, for each pair of subcarriers in a plurality of pairs of subcarriers:
determine a correlation between data received on each subcarrier in the pair of the subcarriers, wherein the determination is based, at least in part, on the selected ranging code;

determine a respective signal phase from the correlation between data received on each subcarrier in the pair of the subcarriers; and
determine the time offset based, at least in part, on an average value of the plurality of determined signal phases corresponding to the plurality of pairs of subcarriers and the selected ranging code.