Title of Invention  "A METHOD FOR GENERATING RANDOM HOPPING PATTERNS" 

Abstract  A method for generating random hopping patterns, comprising: determining a first number of frequency subcarriers with at least one processor (224, 250, 282, 290); determining a second number of hop ports with at least one processor (224, 250, 282, 290); determining a third number of seeds with at least one processor (224, 250, 282, 290); generating at least one hopping pattern with at least one processor (224, 250, 282, 290) based on the first number of frequency subcarriers, the second number of hop ports, and the third number of seeds ; and transmitting a signal according to the hopping pattern with a transmitter (226, 284). 
Full Text  METHODS AND APPARATUS FOR FLEXIBLE HOPPING IN A MULTIPLEACCESS COMMUNICATION NETWORK CROSSREFERENCE TO RELATED APPLICATIONS [001] This application claims benefit under 35 U.S.C. § 119(e) from U.S. Provisional Patent application Serial No. 60/638,469 entitled "Methods and Apparatus for Flexible Hopping in a MultipleAccess Communication Network" and filed December 22, 2004, the entirety of which is hereby incorporated by reference. BACKGROUND I. Field [002] The present invention relates generally to communications, and more specifically to techniques for generating flexible hopping patterns in a multipleaccess communication network. II. Background [003] Communication systems, are widely deployed to provide various communication services such as voice, packet data, and so on. These systems may be time, frequency, and/or code division multipleaccess systems capable of supporting communication with multiple users simultaneously by sharing the available system resources. Examples of such multipleaccess systems include Code Division Multiple Access (CDMA) systems, MultipleCarrier CDMA (MCCDMA), Wideband CDMA (WCDMA), HighSpeed Downlink Packet Access (HSDPA), Time Division Multiple Access (TDMA) systems, Frequency Division Multiple Access (FDMA) systems, and Orthogonal Frequency Division Multiple Access (OFDMA) systems. [004] A communication system may employ a hopping scheme to improve interference. There is therefore a.nee(d in the art for techniques to efficiently design random hopping patterns in a communication network. SUMMARY [005] Techniques for efficiently designing random hopping patterns in a communications system are disclosed. The disclpsed embodiments provide for methods and systems for generating random hopping patterns, updating the patterns frequently, generating different patterns for different cells/sectors, and generating patterns of nearby frequency subcarriers for block hopping. BRIEF DESCRIPTION OF THE DRAWINGS [006] The features and nature of the present invention will become more apparent from the detailed description set forth below when taken in conjunction with the drawings in which like reference characters identify correspondingly throughout and wherein: [007] HO. 1 depicts a wireless access network,according to one embodiment; [008] FIG. 2 depicts a block diagram of a wireless access network according to one embodiment; [009] FIG. 3 shows one embodiment for generating Hop Permutation; [010] FIG. 4 shows a Feistel Network; [Oil] FIG. 5 shows a Single Stage in the Feistel Network of FIG. 4; [012] FIG. 6 shows one embodiment for Generating HijSECTOR(.) when FLIntraCellHopping is Off; and [013] FIG. 7 shows one embodiment for Channel Tree with Portsets, Constraint Nodes and Subportsets. DETAILED DESCRIPTION [014] The word "exemplary" is used herein to mean "serving as an example, instance, or illustration." Any embodiment or design described herein is "exemplary" and is not necessarily to be construed as preferred or advantageous over other embodiments or designs. [015] FIG. 1 shows a wireless communication system 100 with multiple base stations 110 and multiple terminals 120. A base station is a station that communicates with the terminals. A base station may also be called, and may contain some or all of the functionality of, an access point, a Node B, and/or some other network entity. Each base station 110 provides communication coverage for a particular geographic area 102. The term "cell" can refer to a base station and/or its coverage area depending on the context in which the term is used. To improve system capacity, a base station coverage area may be partitioned into multiple smaller areas, e.g., three smaller areas 104a, 104b, and 104c. Each smaller area is served by a'respective base transceiver subsystem (BTS). The term "sector" can refer to a BTS and/or its coverage area depending on the context in which the term is used. For a sectorized cell, the BTSs for all sectors of that cell are typically colocated within the base station for the cell. The transmission techniques described herein may be used for a system with sectorized cells as well as a system with unsectorized cells. For simplicity, in the following description, the term "base station" is used generically for a BTS that serves a sector as well as a base station that serves a cell. [016] Terminals 120 are typically dispersed throughout the system, and each terminal may be fixed or mobile. A terminal may also be called, and may contain some or all of the functionality of, a mobile station, a user equipment, and/or some other device. A terminal may be a wireless device; a cellular phone, a personal digital assistant (PDA), a wireless modem card, and so on. Each terminal may communicate with zero, one, or multiple base stations on the downlink and uplink at any given moment. The downlink (or forward link) refers to the comrttunicatipn lin.k from the base stations to the terminals, and the uplink (or reverse link) refers to the communication link from the terminals to the base stations. . [017] For a centralized architecture, a,system controller 130 couples to base stations 110 and provides coordination and control for these base stations. For a distributed architecture, the base stations may communicate with one another as needed. [018] FIG. 2 shows a block diagram of an embodiment of an access point 1 lOx and an access terminal 150x, which embody an access point and an access terminal, respectively, in wireless network 100 in FIG. 1. An FL facilitates data transmission from access point HOx to access terminal 150x. An RL facilitates data transmission from access terminal 150x to access point HOx. [019] For forward link data transmission, at access point 1 lOx, a buffer 212 receives and stores data packets from higher layer applications. An FL TX LP entity 220 performs processing on the data packets in buffer 212 and provides a frame sequence containing frames. A MAC/PHY, T^X processor 224 performs forward link MAC and physical layer processing (e.g., multiplexing, encoding, modulation, scrambling, channelization, and so on) on the frame sequence from entity 220 and provides a stream of data samples. A transmitter unit (TMTR) 226 processes (e.g., converts to analog, amplifies, filters, and frequency up converts) the data sample stream from processor 224 and generates a forward link signal, which is transmitted via an antenna 228. ', ' •'»' i , . ' [020] At access terminal 150x, the forward link signal from access point 1 lOx is received by antenna 262 and processed (e.g., filtered, amplified, frequency downconverted, and digitized) by a receiver unit (RCVR) 264 to obtain received samples. A MAC/PHY RX processor 266 performs forward link MAC and physical layer processing (e.g., dechannelization, descrambling, demodulation, decoding, demultiplexing, and so on) on the received samples and provides a received frame sequence. An FL RX LP entity 270 performs receiver processing on the received frame sequence and provides decoded data to a reassembly buffer 274. FL RX LP entity 270 may also generate NACKs for data detected to be missing and may also generate ACKs for data correctly decoded. The NACKs and ACKs are sent via the reverse link to access point 1 lOx and provided to FL TX LP entity 220, which performs retransmission of the missing data if any. A retransmit timer 222 facilitates retransmission of the last frame to flush out the buffer. A NACK timer 24.2 facilitates retransmission of NACKs. These timers are described below. [021] For reverse link data .transmission, at access terminal 150x, a buffer 278 receives and stores data packets from higher layer applications. An RL TX LP entity 280 performs processing on the data packets in buffer 278 and provides a frame sequence containing frames. A MAC/PfTY TX processor 282 performs reverse link MAC and physical layer processing on the frame sequence, from entity 280 and provides a stream of data samples. A transmitter unitr(TMTR) 284.processes the data sample stream from processor 282 and generates a reverse link signal, which is transmitted via antenna 262. [022] At access point HOx, the reverse link signal from access terminal ISOx is received by antenna 228 and processed by a receiver unit (RCVR) 232 to obtain received samples. A MAC/PHY RX processor 234 performs reverse link MAC and physical layer processing on the received samples and provides received frame sequence. An RL RX LP entity 240 performs receiver processing on the received frame sequence and provides decoded data tp a reassembly buffer 242. FL RX LP entity 240 may also generate NACKs for data detected to be missing and may also generate ACKs for data correctly decoded. The NACKs and ACKs are sent via the forward link to access terminal 150x and provided to RL TX LP entity 280, which performs retransmission of the missing data if any. The FL and RL are described in detail below. In general, ACK and/or NACK feedback may be'sent by a link protocol (LP), and ACK and/or NACK feedback may also bfe sent by therphysical layer. Controllers 250 and 290 direct operation at access point liOx and access terminal 150x, respectively. Memory units 252 and 292 store program codes and data used by controllers 250 and 290, respectively, for implementing the disclosed embodiments. » . 'i [023] Access point 1 lOx may transmit data to one or multiple access terminals simultaneously on the forward link. Access terminal 150x may transmit the same data to one or multiple access points on the reverse link. The following description is for forward link data transmission from access point HOx to access terminal 150x and for reverse link data transmission from access terminal 150x to access point llOx. [024] The hop permutation may be used to map a set of hop ports to a set of sub carriers. In one embodiment, the hopports, which may be indexed from NFFT NGUARD to NFFT1, may be mapped to a set of guard carriers by the hop permutation. The individual elements of this mapping may not be specified if these carriers are not modulated. The hopping sequenpe may be described as a mapping from the set of hop ports numbered 0 to NFFTN set of guard subcarriers., onding to hopport index "p" for the jth modulation symbol in superframe index "i". Here, p is an index between 0 and NFFT NGUARD 1, and j is an integer larger than 4. There may be no hop permutation defined for symbols in the superframe preamble, Hij(p) is a value between NGUARD/2 and NFFT  NGUARD/2  1, and it may be, computed according to the procedure: Hij(p) = NGUARD/2+HijQU3BAL(HijSECTOR(p)) where HijGLOBALQ and HijSECTORQ are permutations of the set {0,1, 2, ...,NFFTNGUARD1}. [026] HijGLOBAL(.) is a permutation that may not depend on SECTOR_PN_OFFSET> while HijSECTOR(.) is a permutation that may depend on SECTOR_PN_OFFSET. HijpLOBAL may be the same for two sectors with the same values of FLSectorHopSeed, JffijSECTORjnay be different for different sectors unless the variable FLIntraCellCommonHopping is set. Furthermore, HijSECTOR(.) maps hop ports within a portset to hop ports within that portset. The number of portsets and their sizes are determined from the channel tree, which may be determined by the FTC MAC protocol. [027] Let there be K port sets numbered 0; 1, ..., Kl. Let the number of hop ports in f . • • the kth port set be Nk, excluding hopports in the guard region. If there is only one port set, numbered 0, then NO^ NFFT r NGUARD. The sector dependent permutation HijSECTORQ may map hop ports in the Oth port set i.e., hop ports numbered {0,1, 2, ..., NO1} to numbers in the same set. This mapping is denoted as P0ij(.). Thus HijSECTOR(p) = P0ij(p) if p is in the zeroth hop port set. Similarly, the sector dependent permutation may map hop ports in the 1st port set i.e., hop ports numbered {NO, NO +1, NO+ 2,.... NO+N11) to numbers in the same set. This is done using a permutation on {0,1, 2,.... Nl1 [denoted as Plij(.). Thus, HijSECTOR(p) = NO + Plij(p NO) if p is in the first port set. Similarly, HijSECTOR(p) * NO + Nl + P2ij(pNO Nl) if p is in the second port set. Thus HijSECTORQ is defined by a total of K intraport set permutations P0ij(.), PlijQ,..., PKlij(.). [028] According to one embodiment, one element in the generation of the hopping sequence is a Feistel network. A threestage Feistel network generates pseudorandom permutations of sizes which are pqwers of,2. A Feistel network that generates a permutation n(x) of. {0,1, 2,..., 2n,2,2n 1} operates as follows: 1. The nbit input.x is split into two parts (L,R) with each part containing roughly the same number^pf bits. If n is even, L may be the n/2 MSBs of x, and R may be the n/2 LSBs.. Jf n is odd, L may be the (nl)/2 MSBs of x and R may bethe(n+l)/2LSBsofx, 2. The output n l(x) of the first stage of the Feistel network is an nbit quantity of the form (R, L pf(R)). Here f(R) = (R+S1) mod 2L where L is the number of bits in L, SI is a Lbit seed and D is a bitbybit XOR operation. Seeds may be generated, based on system time, sector_E>, Cell_ID. and/or sector PNoffset. 3. The output n l(x) is fed to the next stage of the Feistel network, which may be identical to the first stage except the seed used is S2. The output n 2(n l(x)) of the second stage is fed to the third stage, which may be identical to the first two stages, except that the seed,used is S3. The output n 3(rc 2(rc l(x))) of the third stage is the final output n(x). [029] FIG. 4 shows a threestage Feistel network. FIG. 5 shows a single Feistel stage for the case n=9. According to one embodiment, the global permutation Hijglobal(.) to be used at the jth symbol in superframe i may be"generated from an initial permutation HiGLOBAL(.) as follows: 1. HijGLOB AL(x) = HiGLOB AL(j+ HiGLOBALfl + x)) where both the additions may be done modulo (NFFT  NGUARD). The initial permutation HiGLOBAL(.) may be generated according to the following procedure: 2. Find the smallest integer n such that NFFT and (nl)/2 if n is odd. 3. Set the Feistel seeds SI, S2 arid S3 as follows: 4. Find S' = [(FLSectorHopSeed*4096 + (i mod 4096)) *2654435761] mod 232. Set S to be the bitreversed value of S' in a 32bit representation. 5. Set S1 to be the L LSBs of S, S2 to be the second L LSBs of S, and S3 to be the third L LSBs of S. In other words, SI = S mod 2L, S2 = (SS1)/2L mod 2Land S3 = (SS1S22L)/22L mod 2L. 6. Initialize two. counters x and y to 0. 7. Find the output n(x) of the FeisteJ network seeded with SI, S2 and S3. If TT(X) is.less than ($pFT NGUARD), set Higlobal(y) = n(x) and increment y by 1. Increment the counter x by 1. If x through 6, else stop. . [030] The generation of HijSECTOR may be described separately for different values of "FLIntraCellCommonHopping." If FLIntraCellCommonHopping is Off, the K intraportset permutations Pkij(.) that make up HijSECTOR(.) may be generated from initial permutations Pki(.) according to the following procedure Pkij(x) = Pki(aj + Pki (Pj +x)), where both the additions are performed modulo Nk. qj and Pj are 9bit random numbers generated using a PNregister with generator polynomial h(D) = D18 + D11 +1. The numbers otj and pj are generated as follows: 1. The SECTORJPN_OFFSET is XORed with the 12 LSBs of the superframe index i to obtain a 12bit number [bllb 10 b9 b8 b7 b6 b5 b4 b3 b2 bl bO] denoted as Boff. 2. The PNregister js initialized to [111111 bl 1 blO b9 b8 b7 b6 b5 b4 b3 b2 bl bO] at the beginning of the superframe. 3. The register is then cloqked 18 times every symbol. The contents of the register before symbol j determine oj and pj, with oj being set to the 9 MSBs of the register and pj being set to the 9 LSBs of the register. (Thus aO = [111111 bl 1 blO b9] and pO = [b8 b7 b6 b5 b4 b3 b2 bl bO]). [031] Referring to FIG. 6, the initial permutations Pki(.) are generated according to the following procedure: (1) Find the smallest integer n such that NFFT and(nl)/2ifnisodd. (2) Set the Feistel seeds SI, S2 and S3 as follows: (3) Find S' = [Boff. *2654435761] mod 232. Set S to be the bitreversed value of S' in a 32bit representation. (4) Set S1 to be the the L LSBs of S, S2 to be the second L LSBs of S, and S3 to be the third L LSBs of S. In other words, SI = S mod 2pL, S2 = (SS1)/2L mod 2Land S3 = (SS1S22L)/22L mod 2L. (5) Initialize K counters yO, y 1,..., yK1 to zero. Initialize another counter x to zero. (6) Find the output TI(X) qf the Feistel network seeded with S1, S2 and S3. (7) If rc(x) corresponds to a hop port in the kth port set (i.e., if NO+ N1+...+ Nk1 n(x) NO* N1+.. Nkl+ Nk) then (8) Set Pki(yk) = 7t(x)  (NO+N1+...+ Nk1) and (9) Incrementyk by, 1. (10) Increment the counter x by 1. If x stop. [032] When the FLIntraCellCommonHopping is On, the K intraportset permutations Pkij(.) that make up HijSECTORQ may be generated from initial permutations Pki(.) according to the procedure Pkij(x) = Pki(oj + Pki (pj +x)), where both the additions are performed modulo Nk. oj and 3j are 9bjt random numbers generated using a PN register with generator polynomial h(D) = D18 + Dl 1 +1. The numbers oj and Pj are generated as follows: . 1. The SECTOR_PN_OFFSET is XORed bitwise with the 12 LSBs of the superframe index i to obtain a 12bit numbpr [bl 1 blO b9 b8 b7 b6 b5 b4 b3 b2 bl bO] denoted as Boff. 2. The PNregisteris initialized to [111111 bll blO b9 b8 i7 i6 i5 b4 b3 b2 bl bO] at the beginning of the superframe where i716 i5 are the 7th, 6th and 5th bits of the superframe index i. The 12bit number [bl 1 blO b9 b8 i7 i6 i5 b4 b3 b2 bl bO] is denoted as Bon. 3. The register is then clocked 18 times every OFDM symbol. The contents of the register before OFDM symbol j determine oj and Pj, with aj being set to the 9 MSBs of the register and pj being set to the 9 LSBs of the register. (Thus aO = [111111 bl 1 blO b9] and pO = [b8 i7 i6 i5 b4f b3J)2 bl bX)]). [033] When the FLIntraCellCommonHopping is on, initial permutations Pki(.) for all portsets except the portset with index 0 are generated based on Bon, while the initial permutation for portset index 0 is generated based on Boff. To make proper use of this mode, the SECTOR_PN_OFFSET for two sectors of the same cell may differ in three bit locations, namely the bits with indices 5, 6 and 7. Here, bit index 0 corresponds to the MSB while bit index 11 corresponds to the LSB. [034] The procedure for generating the initial permutations for all portsets except the one with index 0 is as follows: 1. Find the smallest integer n such that NFFT and(nl)/2if n is odd. 2. Set the Feistel seeds SI, S2 and S3 as follows: 3. Find S' = [Bon *265443576l] mod 232. Set S to be the bitreversed value of S' in a 32bit representation. 4. Set S1 to be the, the L LSBs of S, S2 to be the second L LSBs of S, and S3 to be the thirdL LSBs of S. In other words, SI = S mod 2L, S2 = (SS1)/2L mod 2Land S3 = (SS1TS22L)/22L mod 2L. 5. Initialize K counters yO, yl,..... yK1 to zero. Initialize another counter x to zero. , 6. Find the output n(x) of the Feistel network seeded with SI, S2 and S3. 7. If Ji(x) corresponds to a hop port in the kth port set (i.e., if NO+ N1+...+ ....(..• • « Nk1 0, then: 8. Set Pki(yk) = n(\)  (NO+ N1+...+ Nk1) and 9. Increment yk by 1. 10. Increment the counter x by 1. If x stop. 11. The initial permutation for portset index 0 is generated as follows: 12. Find the smallest integer n such that (NFFT  NGUARD) L=n/2 if n is even and (nl)/2 if n is odd. 13. Set the Feistel seeds S1, S2 and S3 as follows: 14. Find S' = [Boff *2654435761] mod 232. Set S to be the bitreversed value of S' in a 32bit representation. 15. Set S1 to be the the L LSBs of S, S2 to be the second L LSBs of S, and S3 to be the third fL LSBs of S. In ouWwords, SI = S mod 2L, S2 = (S S1)/2L mod 2Land S3 = (SS1S22L)/22L mod 2L. 16. Initialize two counters x and y to zero. 17. Find the output 7t(x) of the Feistel network seeded with SI, S2 and S3. 18. If TI(X) corresponds to a hop port in the Oth port set (i.e., if n(x) 19. Set POi(y) = 7t(x) and 20. Increment y by 1. 21. Increment the counter x by 1. If x stop. [035] The Common Pilot Channel (FCPICH) may occupy an evenly spaced set of subcarriers in every modulation symbol of every PHY Frame. Let Np be the nominal number of pilot subcarriers in each OFDM symbol. Np is given by the "Number of Pilots" field of the "Systemlnfo" block, which is public data of the Overhead Messages Protocol. The spacing between neighboring pilot subcarriers may then be equal to Dp = NFFT/Np. [036] For each symbol in a PHY Frame, a variable Offsetp taking values between 0 and Dp1 may be determined using the following procedure: Let i be the superframe index and let j be the index of the OFDM symbol within the superframe (starting with index 0). The variable Offsetp is not defined if j [037] If j is odd, Offsetp may be determined using a 13bit PNregister with generator polynomial h(D) = D13 + D12 + Dl 1 + D8 +1. The shiftregister may be initialized to the state [1 pi 1 plO p9 p8 p7 p6 p5 p4 p3 p2 pi pO] before the beginning of the superframe, where pi 1, plO, p9,.... pO are the 12 bits of the SECTOR_PNJJHASE, with pi 1 being the MSB and,pO being the LSB. The shiftregister maybe clocked 13 »i . times every symbol. Offsetp may be chosen to be the value of the register modulo Dp. Here, the value of the register is the value before Symbol j, i.e., the value of the register after it has been clocked 13 times. [038] If j is even, the value of Offsetp may be computed by adding the value Dp/2 to the value of Offsetp for the previous OFDM symbol modulo Dp. For each symbol in a PHY Frame, the subcarrier with index isc may be occupied by the FCPICH if the following two conditions are satisfied: isc mod NFFT = Offsetp and the subcarrier with index isc is not a guard subcarrier. [039] Each subcarrier occupied by the FCPICH may be modulated with the complex value W "•"', where P is the ratio of the power spectral density of the FCPICH to the power spectral density of the second symbol in the FACQCH. This ratio is given by the "CommonPilotPower" field of the Systemlnfo block, which may be public data of the Overhead Messages Protocol. [040] According to one embodiment, reverse link may implement block hopping, i.e., the set of hopports is divided into blocks of NBLOCK hopports, which may be in a contiguous manner. Hopports 0, 1,..., NBLOCK1 form Block 0, hopports NBLOCK, NBLOCK+1, ..., 2NBLOCK1 form Block 1, etc. Consecutive hopports in a block are mapped by the hopping pattern to consecutive subcarriers, i.e., if hopport 0 is mapped to subcarrier i, then hop^port 1 is mapped to subcarrier i+1, hopport 2 is mapped to subcarrier i+2, etc. The value of NBLOCK may be 8 for the Long Data Segment and TBD for the Short Data Segment, 'the hopping sequence may be described separately for the Long and Sh'brt Data Segments. [041] The number of guardicarriers'NOUARD'may be an integer multiple of NBLOCK. As mentioned previously, the hopports indexed from NFFTNGUARD to NFFT1 may be mapped to the set of guard carriers by the hop permutation. The individual elements of this mapping are not specified since these carriers are not modulated. The hopping sequence may be described as a mapping from the set of hopports numbered 0 to NFFTNGUARD1 to the set of usable subcarriers (i.e., all but the set of guard subcarriers). [042] The basic element in the generation of the hopping sequence may be a Feistel network. A threestage Feistel network generates pseudorandom permutations of sizes which are powers of 2. A Feistel network which generates a permutation TI(X) of {0, 1, 2, ..., 2n 2, 2n 1} operates as follows: 1. The nbit input x is split into two parts (L,R) with each part containing roughly the same number of bits. If n is even, L may be the n/2 MSBs of x, and R may be the n/2 LSBs. If n is odd, L may be the (nl)/2 MSBs of x and R may bethe(n+l)/2LSBsofx. 2. The output n l(x) of the first stage of the Feistel network is an nbit quantity of the form (R, L Qf(R)). Here f(R) = (R+S1) mod 2L where L is the number of bits in L, SI is an Lbit seed and D is a bitbybit XOR operation. 3. The output n l(x) is fed to the next stage of the Feistel network, which is identical to the first stage except the seed used is S2. The output ti 2(n l(x)) of the second stage is fed to the third stage, which is identical to the first two stages, except that the seed used is S3. The output n 3(n 2(n l(x))) of the third stage is the final output n(x). [043] FIG. 4 shows a threestage Feistel network and FIG. 5 shows a single Feistel stage for the case n=9. The Long Data Segment supports constrained hopping. The channel tree may define a set of nodes to be constraint nodes, and the hopping sequence ensures that the set of all hopports that are part of a constraint node are mapped to a contiguous set of subcarriers. The consecutive hopports may or may not be mapped to V consecutive subcarriers. .,. .. [044] In order to support constrained hopping, the following restrictions are placed on the channel tree: (1) The constraint nodes may satisfy.the following requirements: a. There may be at least two constraint nodes. b. The subgraph comprising of the constraint nodes and their ancestors may be a binary tree. (2) Any base node may have one and only one constraint node as an ancestor. (3) All nodes in a portset may have a common ancestor, and the portset may be the set of all descendants of this ancestor. [045] A portset that may have more than constraint node as descendant may be split into subportsets with each constraint node defining the subportset. The subportsets may be numbered {0, 1, ..., Kl} in ascending order i.e., subportset 0 may contain the lowest numbered hop ports and subportset Kl may contain the highest numbered hop ports. [046] Referring to FIG. 7, a channel tree with portsets, constraint nodes and subportsets is depicted. Let Hij'(p') denote the frequency allocated to hop port p' in the modulation symbol numbered j' in superframe I, where j' is constrained to lie in a Long Data Segment. Here, p' is an index between 0 and NFFT NGUARD 1 and Hij'(p') is a value between NGUARD/2 and NFFT  NGUARD/2  1, and it may be computed according to the following equation: Hij'(p') = NGUARD/2 + NBLOCK * (HijGLOBAL(k)+ HijkSECTOR(p)) + (p' mod NBLOCK). [047] Here "~\P BLOCK J denotes the hopport block which contains hop port p', k denotes the subportset which contains the hopport p', and j denotes the hopinterval index within the superframe corresponding to symbol j'. The hopinterval index is counted sequentially within a superframe while ignoring the Control Segment, i.e, hopintervals 0 and 1 belong to the first frame in the superframe, hopintervals 2 and 3 belong to the 2nd frame in the superframe, etc: HijkSECTORQ is a sectordependent function that permutes hop port blocks within the kth subportset. HijGLOBAL(k) is a function that permutes the subportsets around in frequency (either on a sectorbysector basis or on a sectorindependent basis). [048] The generation of HijSECTOR may be described separately for different values of RLJntraCellCommonHopping. First, there is when RLIntraCellCommonHopping is off. In this case, Let K be the tbtaj number of subportsets and Nk be the number of hopport blocks (excluding hopport blocks in the guard region) in the kth subportset. The number of hop port blocks is the number of hop ports divided by NBLOCK. The SECTOR_PN_OFFSET of the seqtpr of interests XORed bitwise with the 12 LSBs of the superframe index i to obtain a 2bit number [bll blO b9 b8 b7 b6 b5 M b3 b2 bl bO] denoted as Boff. This may be. used to generate the permutations HijkSECTORQ according to the following procedure: (1) Find the smallest integer n such that NFFT and(nl)/2if n is odd. Set the Feistel seeds S1, S2 and S3 as follows: (30 Find S' = [(Boff*32+j) *2654435761] mod 232. Set S to be the bitreversed value of S' in a 32bit representation. Set SI to be the the L LSBs of S, S2 to be the second L LSBs of S, and S3 to be the third L LSBs of S. In other words, SI = S mod 2L, S2 = (SS1)/2L mod 2Land S3 = (SS1S22L)/22L mod 2L. [049] Initialize a counter x to 0. Initialize K counters yO, yl,y2, ...,yKl toO.NO, NO+ Nl, NO+ N1+ N2,.... N04N1+ ...+NK2 respectively. (These initial values correspond to the lowest numbered hop port blocks in that subportset) [050] Find the output 7t(x) of the Feistel network seeded with SI, S2 and S3. [051] If n(x) corresponds to a hop port block in the kth subportset, i.e., if NO+ N1+ .. .+Nkl [052] SetHijkSECTOR(yk) = 7t(x)and [053] Increment yk by 1. [054] Increment the counter x by 1. If x [055] RLJntraCellCommonHopping is On [056] Let K be the total number of subportsets and Nk be the number of hopport blocks in the kth subportset, excluding hopport blocks in the guard region. The number of hopport blocks is the number of hopports divided by NBLOCK. [057] The PNoffset of the sector is XORed bitwise with the 12 LSBs of the superframe index i to obtain a 12bit number [bl 1 blO b9 b8 b7 b6 b5 b4 b3 b2 bl bO] denoted as Boff. The 12bit number [bl 1 bid b9rt>8 i7 i6 i5 b4 b3 b2 bl bO], where i7 i6 i5 are the 7th, 6th and 5th bits of the superframe index i, is denoted as Bon. [058] When RLIntraCellCommohHopping is on, Bon may be used to generate the permutations HijkSECTOR(.) of subportsets that are not part of portset 0, while Boff may be used to generate the permutations HijkSECTORQ of subportsets that are part of portset 0. The SECTOR_PN_OFFSET for two sectors of the same cell may differ in three bit locations, namely the bits with indices 5, 6 and 7. Here, bit index 0 corresponds to the MSB while bit index 11 corresponds to the LSB. [059] For subportsets that are n.o.t part of portset 0, HijkSECTOR(.) may be generated according to. the following procedure: [060] Find the smallest integer n such that NFFT l)/2ifnisodd. [061] Set the Feistel seeds S1, S2 and S3 as follows: [062] Find S' = [(Bon*32+j) *2654435761] mod 232. Set S to be the bitreversed value of S' in a 32bit representation. [063] Set S1 to be the the L LSBs of S, S2 to be the second L LSBs of S, and S3 to be the third L LSBs of S. In other words, SI = S mod 2L, S2 = (SS1)/2L mod 2Land S3 = (SS1S22L)/22L mod;2L. [064] Initialize a counter x to 0. Initialize K counters yO, yl, y2, ...,yKl toO, NO, NO+ Nl, NO+ N1+ N2,.... NO+ N1+ ...+NK2 respectively. These initial values correspond to the lowest numbered hop port blocks in that subportset. [065] Find the output 7t(x) of trie Feistel network seeded with S1, S2 and S3. [066] If n(x) corresponds to a hop port block in the kth subportset, (i.e., if NO+ N1+ .. .+Nkl [067] Set HijkSECTOR(yk>= 7t(x) and [068] Increment yk by 1. [069] Increment the counter x by 1; If x [070] For subportsets that are part of portset 0, HijkSECTOR(.) may be generated according to the following procedure : [071] Find the smallest integer n such that NFFT l)/2ifnisodd. [072] Set the Feistel seeds S1, S2 and S3 as follows: [073] Find S' = [(Boff*32+j) *2654435761] mod 232. Set S to be the bitreversed value of S'in a 32bit representatipn. [074] Set S1 to be the the L LSBs of S, S2 to be the second L LSBs of S, and S3 to be the third L LSBs of S. In other words, SI =S mod 2L, S2 = (SS1)/2L mod 2Land S3 = (SSlS22L)/22L.mod 2L.t [075] Initialize a counter x to 0. Initialize K counters yO, y 1, y2,... ,yK1 to 0, NO, NO+ Nl, NOf N1+ N2,...., NQ+ N1+ ...+ NK2 respectively. (These initial values correspond to the lowest numbered hopport blocks in that subportset) [076] Find the output n(x) of the.Feistel network seeded with SI, S2 and S3. [077] If 7t(x) corresponds to a hop port block in the kth subportset, (i.e., if NO+ N1+ .. .lNkI [078] Set HijkSECTQR(yk) = 7t(x) and [079] Increment yk by 1. [080] Increment the counter x by 1. Jf x [081] Generation of HijQLOBAL(.) [082] The HijGLOBAL(k) may permute the K subportsets in a manner that increases frequency di versity with little or no loss in interference di versity. This may be done according to the following procedure; [083] Generate a seed S according to the following rule: [084] If there is more than one port set, then S' = [(RLSectorHopSeed*4096*32 + (i mod 4096)*32 +j) *2654435761] mod 232 [085] If there is only one port set then S' = [(Boff*32+j) *2654435761] mod 232 [086] S is the bitreversed value of S' in a 32bit representation. [087] The two depth1 nodes (i.e., children of the root node) may be labeled A and B, and KA may be the number of subportsets that are descendants of A, and KB may be the number of subportsets that are descendants of B. (KA +KB = K). [088] The permutations on {0, 1 ,...., KA1} may be listed in alphabetical order and numbered 0 to (KA! 1), where, k!, denotes the product k(kl)(k2)...2 for any positive integer k. For example if KA = 3, then the ordering is 012,021,102,120, 201, 210 with the numbering going from 0 to 5.' The permutation numbered L J *' may be chosen to be the permutation PA of the subportsets which are descendants of A. [089] Similarly, the permutations.oh {KA, KA+1 , ..., KA+KB1} may be listed in alphabetical order and numbered 0 to (KB! 1). For example, if KA = 3 and KA = 2, then the permutations are 34 and 43, numbered 0 and 1 respectively. The permutation numbered L J a ' may be chosen to be the permutation PB of the subportsets which are descendants of B. , [090] A permutation on the set {A,B} is determined as follows: [091] If j is even, the permutation may be AB if S mod 2 = 0 and BA if S mod 2 = 1. [092] If j is odd, the permutation may be the opposite of the permutation chosen at hopinterval j1. [093] The overall permutation on the subportsets may be PAPB or PBPA accordingly. For example, if PA = 021 and PB = 43, and AB was chosen, then the overall permutation may be 02143. If BA was chosen, it would have been 43021. [094] Once the permutation of subportsets is finalized, the function HijGLOBAL(k) may be computed by subtracting the location for the lowest numbered hopport block in that subportset before permuting from the location of the same hopport block after permutation. For example, if the subportset permutation is 02143, then [095] HijGLOBAL(0)=(0)(OV [096] HijGLOBAL( 1) = (NO+ N2)  (NO), [097] HijGLOBAL(2) = (NO)  (NO+ Nl). [098] HijGLOBAL(3) = (NO+ N2+ N1+ N4)  (NOf N1+ N2). [099] HijGLOBAL(4) = (NO+ N2+ Nl)  (NO+ N1+ N2+ N3). [0100] where Nk is the number of hop port blocks in the kth subportset [0101] In one embodiment, a system and method for generating random hopping patterns includes determining a fir^t number of subcarriers and a second number of hop ports. The number of hop ports may be less than the number of subcarriers due to guard bands, which consumes so>rrie subcarriers. The process may also include determining a third number of seeds as described above. The process generates at least one hopping pattern based on the first number of subcarriers, the second number of hop ports, and the third number of seeds, e.g., using the Feistel network, as described above. The seeds may be determined based on a system time, a sector ID, a cell ID, or a combination thereof. [0102] In one embodiment, the generated hop pattern may be updated or changed frequently to ensure frequency diversity. The update may be based on a factor of system time. The update may also include changing the subcarrier frequency of a hop port entity by a predetermined amount every predetermined time period. [0103] In one embodiment, the hop ports ma,y be grouped into smaller groups of hop ports, and each group fed intq a portion/unijt of the Feistel network, thereby generating at least one hopping pattern for .each smaller group of hop ports. In this case, each group of subcarriers may correspond to different sectors in the same or different cells, and may experience lower interference. [0104] In one embodiment, a.block (e.g., contiguous) of the hop ports may be assigned to a user. In order to facilitate channel estimation, for example, the generated hopping pattern for the block of hop ports may comprise nearby frequency subcarriers and/or contiguous frequency subcarriers. [0105] In one embodiment, a plurality of blocks of the hop ports may be assigned to a user. The corresponding hopping patterns for the blocks of hop ports may be placed at desired proximity. To ensure frequency diversity and lower interference, for example, the hopping patterns for the blocks of hop ports may be made apart from each other. However, if the hopping patterns for the blocks of hop ports are too far from each other, out of band spectral emission may increase. [0106] In one embodiment, a method for generating random hopping patterns for a plurality of hop ports includes ordering the hpp port entities (hop port and/or blocks of hop ports) in sequence at the first layer (leaves) of a tree, and swapping each pair of hop port entities at a lower layer if at least a first condition is met, thereby generating a higher layer of hop port entities. The process repeats this act and swaps each pair of hop port entities at the higher layer if at least a second condition is met. This process is repeated until one reaches the top of the tree and a random hopping pattern is generated. The hop port entities may comprise at least one block of contiguous hop ports, which may correspond to a contiguous block of subcarrier frequencies. [0107] For example, consider a set of hop port entities numbered 0, 1, 2, and 3. At the lowest layer, hop port pairs 01 and 23 are present. If a first condition, e.g., tossing a coin for head, is met for a pair, the pair is swapped. For instance, pair 01 may not swap, but pair 23 may swap, resulting in a higher layer hop port entities 01 and 32. Now, repeating the process, the higher layer pair (01 and 32) is swapped if a second or the same condition is met. For instance, the higher layer pair may swap, resulting in the hopping pattern 3, 2,0, and 1. It should be noted that any number of hop ports entities having any number of hop ports may be included in this process. [0108] The disclosed embodiments may be applied to any one or combinations of the following technologies: Code Division Multiple Access (CDMA) systems, MultipleCarrier CDMA (MCCDMA), Wideband CDMA (WCDMA), HighSpeed Downlink Packet Access (HSDPA), Time Division Multiple Access (TDMA) systems, Frequency Division Multiple Access (FDMA) systems, and Orthogonal Frequency Division Multiple Access (OFDMA) systems. [0109] The signaling transmission techniques described herein may be implemented by various means. For example, these techniques may be implemented in hardware, software, or a combination thereof. For a hardware implementation, the processing units used to process (e.g., compress and encode) signaling may be implemented within one or more application specific.integrated circuits (ASICs), digital signal processors (DSPs), digital signal processing devices (DSPDs), programmable logic devices (PLDs), field programmable gate arrays FPGAs), processors, controllers, microcontrollers, microprocessors, other electronic units designed to perform the functions described herein, or a combination thereof. The processing units used to decode and decompress the signaling may also be implemented with one or more ASICs, DSPs, and soon. [0110] For a software implementation, the signaling transmission techniques may be implemented with modules (e.g., procedures, functions, and so on) that perform the functions described herein. The software codes may be stored in a memory unit (e.g., memory unit 252 or 292 in FIG. 2) and executed by a processor (e.g., controller 250 or 290). The memory unit may be implemented within the processor or external to the processor. [0111] The previous description of the disclosed embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without departing from the spirit or scope of the invention. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and features disclosed herein. We Claim: 1. A method for generating random hopping patterns, comprising: determining a first number of frequency subcarriers with at least one processor (224, 250, 282, 290); determining a second number of hop ports with at least one processor (224, 250, 282, 290); determining a third number of seeds with at least one processor (224,250, 282, 290); generating at least one hopping pattern with at least one processor (224, 250, 282, 290) based on the first number of frequency subcarriers, the second number of hop ports, and the third number of seeds ; and transmitting a signal according to the hopping pattern with a transmitter (226, 284). 2. The method as claimed in claim 1, wherein the at least one processor (224, 250, 282, 290) is configured to determine at least one of the third number of seeds based on the system time. 3. The method as claimed in claim 1, wherein the at least one processor (224, 250, 282, 290) is configured to determine at least one of the third number of seeds based on a sector ID. 4. The method as claimed in claim 1, wherein the at least one processor (224, 250, 282, 290) is configured to determine at least one of the third number of seeds based on a cell ID. 5. The method as claimed in claim 1, wherein the first number of frequency subcarriers and the second number of hop ports are different. 6. The method as claimed in claim 1, wherein the at least one processor (224, 250, 282, 290) is configured to change the hopping pattern frequently. 7. The method as claimed in claim 1, wherein the at least one processor (224, 250, 282, 290) is configured to group the second number of hop ports into smaller groups of hop ports; and generate at least one hopping pattern for each smaller group of hop ports, such that the hopping pattern for the small groups are disjoint. 8. The method as claimed in claim 1, wherein the at least one processor (224, 250, 282, 290) is configured to assign a block or plurality of block of the second number of hop ports to a user equipment; and generate at least one hopping pattern for the block of hop ports such that the hopping pattern for the block of hop ports comprises nearby frequency subcarriers. 9. The method as claimed in claim 8, wherein the hopping pattern for at least one block of hop ports comprises contiguous frequency subcarriers. 

5164delnp2007Abstract(11062013).pdf
5164delnp2007Abstract(28082012).pdf
5164delnp2007Claims(11062013).pdf
5164delnp2007Claims(28082012).pdf
5164delnp2007Correspondance Others(11062013).pdf
5164delnp2007Correspondence Others(14032013).pdf
5164delnp2007Correspondence Others(28082012).pdf
5164delnp2007correspondenceothers.pdf
5164delnp2007Description (Complete)(28082012).pdf
5164delnp2007description (complete).pdf
5164delnp2007Drawings(28082012).pdf
5164delnp2007Form1(11062013).pdf
5164delnp2007Form1(28082012).pdf
5164delnp2007Form2(11062013).pdf
5164delnp2007Form2(28082012).pdf
5164delnp2007Form3(14032013).pdf
5164delnp2007Form3(28082012).pdf
5164delnp2007GPA(28082012).pdf
5164delnp2007Petition137(28082012).pdf
Patent Number  257522  

Indian Patent Application Number  5164/DELNP/2007  
PG Journal Number  42/2013  
Publication Date  18Oct2013  
Grant Date  10Oct2013  
Date of Filing  04Jul2007  
Name of Patentee  QUALCOMM INCORPORATED  
Applicant Address  5775 MOREHOUSE DRIVE, SAN DIEGO, CALIFORNIA 921211714,USA  
Inventors:


PCT International Classification Number  H04L 9/00  
PCT International Application Number  PCT/US2005/046743  
PCT International Filing date  20051222  
PCT Conventions:
