Abstract:
Embodiments of the present disclosure provide methods, systems, and apparatuses related to a partially random permutation sequence generator. Other embodiments may be described and claimed.

Description:
FIELD 
       [0001]    Embodiments of the present disclosure relate to the field of communications and, more particularly, to a partially random sequence generator used for said communications. 
       BACKGROUND 
       [0002]    Orthogonal frequency division multiple access (OFDMA) communications use an orthogonal frequency-division multiplexing (OFDM) digital modulation scheme to deliver information across broadband networks. OFDMA is particularly suitable for delivering information across wireless networks. 
         [0003]    OFDMA communications may use frequency diversity permutation to enhance the channel reliability by increasing reliability for low signal-to-noise ratio (SNR) communications and/or high-speed mobile stations (MSs). Furthermore, different frequency diversity permutation sequences may be used for different cells in order to reduce the inter-cell interference. 
         [0004]    There are many existing permutation methods, e.g., S-Random, full random, and bit reversal. S-Random sequences typically have large frequency diversity gains; however, S-Random sequences of different lengths need to be searched out and stored into table, which will complicate hardware implementation. While full random sequences may be easily implemented, they typically do not achieve a desired diversity gain. Bit reversal is a fixed sequence that can not be used for inner permutation to avoid the inter-cell interference mentioned above. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0005]    Embodiments will be readily understood by the following detailed description in conjunction with the accompanying drawings. To facilitate this description, like reference numerals designate like structural elements. Embodiments are illustrated by way of example and not by way of limitation in the figures of the accompanying drawings. 
           [0006]      FIG. 1  illustrates a permutation module in accordance with some embodiments. 
           [0007]      FIG. 2  is a flowchart describing a partially random permutation in accordance with some embodiments. 
           [0008]      FIG. 3  illustrates a subchannelization architecture in accordance with some embodiments. 
           [0009]      FIG. 4  illustrates a system in accordance with some embodiments. 
       
    
    
     DETAILED DESCRIPTION 
       [0010]    In the following detailed description, reference is made to the accompanying drawings which form a part hereof wherein like numerals designate like parts throughout, and in which is shown by way of illustration embodiments in which the disclosure may be practiced. It is to be understood that other embodiments may be utilized and structural or logical changes may be made without departing from the scope of the present disclosure. Therefore, the following detailed description is not to be taken in a limiting sense, and the scope of embodiments in accordance with the present disclosure is defined by the appended claims and their equivalents. 
         [0011]    Various operations may be described as multiple discrete operations in turn, in a manner that may be helpful in understanding embodiments of the present disclosure; however, the order of description should not be construed to imply that these operations are order dependent. 
         [0012]    For the purposes of the present disclosure, the phrase “A and/or B” means (A), (B), or (A and B). For the purposes of the present disclosure, the phrase “A, B, and/or C” means (A), (B), (C), (A and B), (A and C), (B and C), or (A, B and C). 
         [0013]    Various components may be introduced and described in terms of an operation provided by the components. These components may include hardware, software, and/or firmware elements in order to provide the described operations. While some of these components may be shown with a level of specificity, e.g., providing discrete elements in a set arrangement, other embodiments may employ various modifications of elements/arrangements in order to provide the associated operations within the constraints/objectives of a particular embodiment. 
         [0014]    The description may use the phrases “in an embodiment,” or “in embodiments,” which may each refer to one or more of the same or different embodiments. Furthermore, the terms “comprising,” “including,” “having,” and the like, as used with respect to embodiments of the present disclosure, are synonymous. 
         [0015]    This disclosure describes a partially random permutation that provides a large distance between neighboring elements while keeping a degree of randomness in the distribution. In some embodiments, it may be applied to distribute resource units across subchannels to provide frequency diversity, and increase diversity gain, in OFDMA-based wireless broadband technologies. 
         [0016]      FIG. 1  illustrates a permutation module  100  in accordance with some embodiments. The permutation module  100  may include a permutation sequence generator (PSG)  104  and a pseudorandom number generator (PRNG)  108 , coupled with each other as shown, to provide a partially random permutation as will be described. 
         [0017]    The PSG  104  may receive an input sequence  112 , e.g., Input[M]. The input sequence  112  may be an ordered sequence of elements, e.g., {I[0], I[1], . . . , I[M-1]}. The elements may be, e.g., resource units. A resource unit, as used herein, may be a unit of a resource used for transmitting communications over a communication link. In some embodiments, as will be described in further detail below, a resource unit may include P_sc contiguous subcarriers over N_sym OFDM symbols. 
         [0018]    The PSG  104  may permutate the input sequence  112  and output a permutated sequence  116 , e.g., Perm[M]. The permutated sequence  116  may include the same elements as the input sequence  112 , except arranged in a different ordered sequence, e.g., {P[0], P[1], . . . , P[M-1]}. The PSG  104  may permutate the input sequence  112  according to a partially random permutation. 
         [0019]    In some embodiments, the PRNG  108  and PSG  104  may be implemented in a transmit chain of a communication station, e.g., a base station or a mobile station. In these embodiments, the transmit chain may receive data as the input sequence  112 , generate the permutated sequence  116 , and distribute the data across a frequency band based at least in part on the permutated sequence  116 . The transmit chain may then cause the data to be transmitted, in a frequency diverse manner, over a wireless network to which it is communicatively coupled by an antenna. These and other embodiments will be described in further detail below. 
         [0020]      FIG. 2  is a flowchart  200  illustrating a partially random permutation provided by the permutation module  100  in accordance with some embodiments. At block  204 , the parameters of the PRNG  108  may be initialized. In particular, parameters a, c, and z may be set to, e.g., 1103515245, 12345, and 232, respectively. These values represent non-limiting examples of possible values, other embodiments may use other values. The PRNG  108  may be a linear congruential generator that generates numbers according to 
         [0000]        X   n+1 =( aX   n   +c ) mod  z.    Equation 1 
         [0021]    At block  208 , the PSG  104  may receive the input sequence  112  and initialize set C 0 ={0, 1, . . . M-1}, where M is the length of the input sequence  112 . 
         [0022]    At block  212 , a first element may be selected from the input sequence  112  and set in a first ordered position of the permutated sequence  116 . This first element, referred to as P[0], may be selected by being set equal to r 0 , where (0≦r 0 &lt;M), generated by: 
         [0000]        X   0 =( a *seed+ c ) mod  z;    Equation 2 
         [0000]      r 0 =X 0  mod M,   Equation 3 
         [0023]    where seed is a function of a cell identifier associated with the PSG  104  and/or a frame index associated with data in the elements, e.g., resource units, of the input sequence  112 . For a simple function, seed may be set equal to a cell identifier of a station, e.g., a base station or a mobile station, which is implementing the PSG  104 . 
         [0024]    At block  216 , an index i may be set to 1 and an initialization phase provided by blocks  204 - 216  may complete. 
         [0025]    After the initialization is complete, the body of the partially random permutation, identified by blocks  220 - 240 , may be used to permutate an input sequence of elements into a permutated sequence by iteratively selecting elements from the input sequence for the permutated sequence. The selection for a particular iteration, e.g., as described by blocks  224 - 236 , will be based at least in part on a pseudorandom selection of one or more non-selected resource units of the input sequence that are at least a given distance away from a selected resource unit of a previous iteration. As may be understood, consecutive iterative selections may result in consecutively ordered elements of the permutated sequence  116 . 
         [0026]    Referring now to block  220 , the index i may be compared to M to determine whether the iterative selections of the permutation sequence have completed, e.g., have all of the elements of the input sequence  112  been selected for the permutated sequence  116 . If it is determined that i&lt;M, e.g., there are unselected elements of the input sequence  112 , the process may advance to block  224 . 
         [0027]    At block  224 , a distance threshold D i−1  may be set. In some embodiments the distance threshold may be set according to: 
         [0000]        D   i−1 =floor( L   i−1   /K ),   Equation 4 
         [0028]    where L i−1  is the length of the set C i−1  and K is a distance factor. Without loss of generality, K may be set to 4. Distance, as used in reference to distance threshold and elsewhere, refers to a distance between indices of two elements in a given ordered sequence. 
         [0029]    At block  228 , elements of the input sequence  112  may be selected for a temporary set T and a candidate set B as follows. The temporary set T may be a subset of C i−1 , e.g., T ⊂ C i−1 . All elements in T may be selected from C i−1  according to: 
         [0000]      Abs( x−y )≦ D   i−1 ,   Equation 5 
         [0030]    where x is an index of Ts element in C i−1  and y is the index of P[i−1] in C i−1 . 
         [0031]    The candidate set B may be computed by: 
         [0000]        B=C   i−1   −T,    Equation 6 
         [0032]    where the length of B is L b . In this manner, the candidate set B may be established such that it only includes the non-selected elements of the input sequence  112  that are beyond a determined distance threshold from the element selected in the previous iteration. In the particular case when B is null, B may be set equal to T. 
         [0033]    At block  232 , a pseudorandom number r i  may be generated by: 
         [0000]        X   i =( a*X   i−1   +c )mod  z;    Equation 7 
         [0000]      r i =X i  mod LB,   Equation 8 
         [0034]    where 0≦r i &lt;L b . 
         [0035]    At block  236 , an element may be selected from the candidate set B and set in an ordered position of the permutated sequence  116  as follows: 
         [0000]      P[i]=B[r i ].   Equation 9 
         [0036]    At block  240 , C i  may be set to C 1−1 −{P[i−1]} and i may be incremented by one. The process may loop back to block  220  to determine whether i is less than M. When it is determined, at block  220 , that i is not less than M, it may be determined that all of the elements of the input sequence  112  have been set into the permutated sequence  116  and the permutated sequence  116  may be output at block  244 . 
         [0037]    The permutation module  100  and the partially random permutation described above may be employed in a number of different embodiments. In a particular embodiment, the permutation module  100  and the partially random permutation may be used to obtain frequency diversity in OFMDA communications. 
         [0038]      FIG. 3  illustrates a subchannelization architecture  300  that may be used in an OFDMA communication network in accordance with some embodiments. The architecture  300  may include a number of physical resource units (PRUs)  304 . A PRU may be a basic physical unit used for allocating resources to communications. A PRU may be composed of P_sc contiguous subcarriers over N_sym contiguous OFDM symbols. 
         [0039]    In a first stage outer permutation (OP)  308 , a sequence of blocks of N 1  contiguous PRUs may be permutated into a first stage OP sequence. The blocks may then be distributed among a number of frequency partitions  312 , e.g., frequency partition  1 , frequency partition  2 , and frequency partition  3 , based at least in part on the first stage OP sequence. In other embodiments, other numbers of frequency partitions may be used. 
         [0040]    In a second stage OP  316 , a sequence of blocks of N 2  contiguous PRUs, as they are arranged in the first stage OP sequence distributed among the frequency partitions  312 , may be permutated into a second stage OP sequence. The blocks of the N 2  contiguous PRUs may then be distributed across the frequency band into localized and/or distributed groups  320  based at least in part on the second stage OP sequence. In one embodiment, N 1  may be set to four while N 2  may be set to one. The values of these outer permutation granularities may change in various embodiments. 
         [0041]    The resource units of the localized groups may be referred to as contiguous resource units (CRUs) while the resource units of the distributed groups may be referred to as distributed resource units (DRUs). The sizes of the CRUs and DRUs may correspond to the PRUs, e.g., P_sc subcarriers by N_sym OFDM symbols. The CRUs may include a group of subcarriers that are contiguous across resource allocation, while the DRUs may include a group of subcarriers that are spread across the distributed resource allocations. Each DRU may be composed of a number of tiles. 
         [0042]    In an inner permutation  324 , a sequence of DRUs, or portions thereof, as arranged in the distributed groups, may be permutated to output an inner permutation sequence that may be used, at least as a partial basis, for distributing the DRUs, or portions thereof, among logical resource units (LRUs)  328 . The LRUs  328  may be organized as one or more subchannels. 
         [0043]    In the case of a downlink channel, the inner permutation  324  may be a subcarrier-based permutation, e.g., the elements of the permutated sequence may have a subcarrier granularity. In the case of an uplink channel, the inner permutation  324  may be a tile-based permutation, e.g., the elements of the permutated sequence may have a tile granularity. 
         [0044]    The permutation module  100  may be employed to provide partially random permutations for the 1 st  stage OP  308 , the 2 nd  stage OP  316 , and/or the inner permutation  324 . Distributing resource units (e.g., PRU blocks, DRUs, tiles, etc.) across frequencies (e.g., frequency partitions, distributed groups, subchannels (either individually or LRUs), etc.) based at least in part on partially random permutation sequences may provide communications with a frequency diversity that is similar to S-random without at least some of the associated hardware implementation concerns. 
         [0045]    The permutation module  100  may be implemented into a system using any suitable hardware and/or software to configure as desired.  FIG. 4  illustrates, for one embodiment, an example system  400  comprising one or more processor(s)  404 , system control logic  408  coupled to at least one of the processor(s)  404 , system memory  412  coupled to system control logic  408 , non-volatile memory (NVM)/storage  416  coupled to system control logic  408 , and one or more communications interface(s)  420  coupled to system control logic  408 . 
         [0046]    System control logic  408  for one embodiment may include any suitable interface controllers to provide for any suitable interface to at least one of the processor(s)  404  and/or to any suitable device or component in communication with system control logic  408 . 
         [0047]    System control logic  408  for one embodiment may include one or more memory controller(s) to provide an interface to system memory  412 . System memory  412  may be used to load and store data and/or instructions, for example, for system  400 . System memory  412  for one embodiment may include any suitable volatile memory, such as suitable dynamic random access memory (DRAM), for example. 
         [0048]    System control logic  408  for one embodiment may include one or more input/output (I/O) controller(s) to provide an interface to NVM/storage  416  and communications interface(s)  420 . 
         [0049]    NVM/storage  416  may be used to store data and/or instructions, for example. NVM/storage  416  may include any suitable non-volatile memory, such as flash memory, for example, and/or may include any suitable non-volatile storage device(s), such as one or more hard disk drive(s) (HDD(s)), one or more compact disc (CD) drive(s), and/or one or more digital versatile disc (DVD) drive(s) for example. 
         [0050]    The NVM/storage  416  may include a storage resource physically part of a device on which the system  400  is installed or it may be accessible by, but not necessarily a part of, the device. For example, the NVM/storage  416  may be accessed over a network via the communications interface(s)  420 . 
         [0051]    System memory  412  and NVM/storage  416  may include, in particular, temporal and persistent copies of permutation logic  424 , respectively. The permutation logic  424  may include instructions that when executed by at least one of the processor(s)  404  result in the system  400  performing partially random permutations as described in conjunction with the permutation module  100  described herein. In some embodiments, the permutation logic  424  may additionally/alternatively be located in the system control logic  408 . 
         [0052]    Communications interface(s)  420  may provide an interface for system  400  to communicate over one or more network(s) and/or with any other suitable device. Communications interface(s)  420  may include any suitable hardware and/or firmware. Communications interface(s)  420  for one embodiment may include, for example, a network adapter, a wireless network adapter, a telephone modem, and/or a wireless modem. For wireless communications, communications interface(s)  420  for one embodiment may use one or more antenna(s). 
         [0053]    For one embodiment, at least one of the processor(s)  404  may be packaged together with logic for one or more controller(s) of system control logic  408 . For one embodiment, at least one of the processor(s)  404  may be packaged together with logic for one or more controllers of system control logic  408  to form a System in Package (SiP). For one embodiment, at least one of the processor(s)  404  may be integrated on the same die with logic for one or more controller(s) of system control logic  408 . For one embodiment, at least one of the processor(s)  404  may be integrated on the same die with logic for one or more controller(s) of system control logic  408  to form a System on Chip (SoC). 
         [0054]    In various embodiments, system  400  may have more or less components, and/or different architectures. 
         [0055]    Although certain embodiments have been illustrated and described herein for purposes of description of the preferred embodiment, it will be appreciated by those of ordinary skill in the art that a wide variety of alternate and/or equivalent embodiments or implementations calculated to achieve the same purposes may be substituted for the embodiments shown and described without departing from the scope of the present disclosure. Similarly, memory devices of the present disclosure may be employed in host devices having other architectures. This application is intended to cover any adaptations or variations of the embodiments discussed herein. Therefore, it is manifestly intended that embodiments in accordance with the present disclosure be limited only by the claims and the equivalents thereof.