Patent Publication Number: US-8971433-B2

Title: Compressive wireless modulation

Description:
BACKGROUND 
     In digital wireless communication systems, wireless link adaptation is an important process for selecting coding and modulation schemes based on varying channel conditions. For example, if the channel conditions are good (e.g., the sending device and the receiving device are located in close proximity to one another and there is little or no interference), then a coding and modulation scheme that includes only a small amount of redundant data may be selected. In contrast, if the channel conditions are bad (e.g., there is significant interference), then a coding and modulation scheme may be selected that includes a larger amount of redundant data to assist the receiving device in decoding data that is received. 
     In many existing systems, a sending device uses a particular coding and modulation scheme, transmits data to a receiving device, and awaits feedback from the receiving device. Based on the received feedback, which represents current channel conditions, the sending device may select a different coding and/or modulation scheme to better suit the current channel conditions. Selecting a coding and modulation scheme based on feedback from the receiving device can result in a mismatch between the current channel conditions and the selected coding and modulation scheme. For example, the channel conditions may change more quickly than is reflected by the received feedback. 
     SUMMARY 
     This document describes compressive wireless modulation. In one aspect, a projection code is applied to a set of binary source bits to generate rateless multilevel symbols. Each rateless multilevel symbol is a weighted arithmetic sum of a subset of binary source bits. The symbols are then combined to form constellation points that are sequentially mapped through a QAM constellation to modulate a data signal. 
     The modulated data signal is transmitted over a wireless network from a transmitting device to a receiving device. The receiving device demodulates the received data signal, identifying a plurality of received symbols. The received symbols may differ from the encoded rateless multilevel symbols due to channel noise on the wireless network. 
     The receiving device iteratively analyzes the received symbols according to a belief propagation algorithm using statistics derived from the same projection code that was used to encode the original binary source bits. Upon successful demodulation and decoding, the receiving device sends an acknowledgment to the transmitting device signaling the transmitting device to cease encoding, modulation and transmission for the current set of binary source bits. 
     This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter. The term “techniques,” for instance, may refer to device(s), system(s), method(s) and/or computer-readable instructions as permitted by the context above and throughout the document. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The detailed description is described with reference to the accompanying figures. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The same numbers are used throughout the drawings to reference like features and components. 
         FIG. 1  is a block diagram of an example environment in which compressive wireless modulation may be implemented. 
         FIG. 2  is a symbolic diagram of projection coding applied to an example set of binary input bits. 
         FIG. 3  is a symbolic diagram of example rateless symbols sequentially mapped through a QAM constellation. 
         FIG. 4  is a symbolic diagram of an example matrix representation of a projection code to encode input binary bits using weight values to generate multi-level rateless symbols. 
         FIG. 5  is a block diagram that illustrates modules of an example projection coding component. 
         FIG. 6  is a block diagram that illustrates modules of an example modulation component. 
         FIG. 7  is a flow diagram of an example process for data coding and modulation. 
         FIG. 8  is a block diagram that illustrates modules of an example demodulation component. 
         FIG. 9  is a block diagram that illustrates modules of an example projection decoding component. 
         FIG. 10  illustrates an example process for demodulating and decoding a received data signal. 
     
    
    
     DETAILED DESCRIPTION 
     Quadrature amplitude modulation (QAM) is used extensively as a modulation scheme for digital telecommunication systems. In a digital environment, QAM is a modulation scheme in which two digital bit streams are conveyed by changing the amplitudes of two carrier waves using the amplitude-shift keying (ASK) digital modulation scheme and summing the two modulated waves. A constellation diagram is a two-dimensional grid that provides a useful representation of the QAM scheme. The more points represented in the constellation, the more bits can be transmitted per symbol. However, having more points in the constellation also requires that the points be closer together, and makes the modulation scheme more susceptible to noise. 
     In wireless network environments, channel quality can vary significantly over short periods of time. The quantity and quality of data being transmitted over a wireless link is affected by the efficiency with which the wireless link is adapted based on the channel quality. For example, if the channel quality is good, a larger QAM constellation can be used, resulting in greater throughput, without causing significant data quality degradation. In contrast, if the channel quality is poor, it is advantageous to use a smaller QAM constellation, and thus small throughput, to minimize the effect of the channel noise on the decoding process. 
     Existing wireless network environments rely on a feedback loop between the sender and the receiver whereby the receiver notifies the sender of the current channel conditions, and the receiver then adapts the constellation being used based on channel conditions as reported by the sender. However, relying on feedback from the receiver introduces a degree of latency, and because the channel conditions can change very quickly, the channel conditions reported by the receiver may not still be the channel conditions after the sender adapts the wireless link based on the feedback. 
     Compressive wireless modulation, as described herein, provides smooth wireless link adaptation without channel feedback. In embodiments described herein, a projection coding scheme that is approximately random is used to provide redundancy, and a uniform QAM constellation is used regardless of channel conditions. As a result, data transmission occurs more efficiently because the transmitting device does not make any adjustments due to channel conditions. Rather, the receiving device determines when the transmitting device has transmitted a sufficient amount of data, which will vary based on the channel conditions. That is, for a given set of input bits being transmitted, multiple symbols are transmitted. When the receiving device is able to successfully decode the symbols, the receiving device sends an acknowledgment to the transmitting device, indicating that the data has been successfully received and decoded. If the channel conditions are favorable, less data will be needed by the receiving device to properly decode the input bits. On the other hand, if the channel conditions are less favorable (e.g., more noise is introduced), then more data will be needed by the receiving device to properly decode the input bits. 
     Example Environment 
       FIG. 1  illustrates an example environment  100  usable to implement compressive modulation. Example environment  100  includes a transmitting device  102 , a wireless network  104 , and a receiving device  106 . Each of the transmitting device  102  and the receiving device  106  may be implemented in many forms, including, but not limited to, a personal computer, a mobile computing device, router, or any other type of digital device configured to communicate over wireless network  104 . 
     Transmitting device  102  includes a wireless network interface  108 , a processor  110 , and a memory  112 . Wireless network interface  108  enables transmitting device  102  to transmit a modulated data signal  114  over wireless network  104  to a receiving device  106 . Although not shown in  FIG. 1 , an operating system and one or more applications may be stored in memory  112  for execution by processor  110 . A projection coding component  116  and a modulation component  118  are also stored in memory and executed by processor  110 . 
     Projection coding component  116  encodes binary information bits using a weighted arithmetic addition operation to create non-binary, multi-level rateless symbols. Modulation component  118  performs a sequential mapping of the multi-level rateless symbols using a dense constellation (e.g., a 23×23 QAM), to generate the modulated data signal  114 . 
     Receiving device  106  includes a wireless network interface  120 , a processor  122 , and a memory  124 . Wireless network interface  120  enables receiving device  106  to receive a modulated data signal  114  over wireless network  104 . 
     Although not shown in  FIG. 1 , an operating system and one or more applications may be stored in memory  124  and executed on processor  122 . Receiving device  106  also includes a demodulation component  126  and a projection decoding component  128 , each stored in memory  124  and executed on processor  122 . 
     Demodulation component  126  receives the modulated data signal  114  over wireless network  104 , and demodulates the received signal, resulting in multi-level rateless symbols. The symbols determined by demodulation component  126  will vary from the originally encoded symbols based on the channel quality of the wireless network  104  over which the modulated data signal was transmitted. 
     Projection decoding component  128  utilizes statistics of channel noise through belief propagation to decode the received, demodulated symbols. The production decoding is an iterative process, with the number of iterations depending on the channel quality. The better the channel quality, the fewer iterations, and fewer symbols, are needed to successfully obtain the original binary information bits. 
     Although illustrated in  FIG. 1  as being stored in memory  112  of transmitting device  102 , projection coding component  116  and/or modulation component  118 , or portions thereof, may be implemented using any form of computer-readable media that is accessible by transmitting device  102 . Similarly, demodulation component  126  and/or projection decoding component  128 , or portions thereof, may be implemented using any form of computer-readable media that is accessible by receiving device  106 . 
     Computer-readable media includes, at least, two types of computer-readable media, namely computer storage media and communications media. 
     Computer storage media includes volatile and non-volatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules, or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other non-transmission medium that can be used to store information for access by a computing device. 
     In contrast, communication media may embody computer readable instructions, data structures, program modules, or other data in a modulated data signal, such as a carrier wave, or other transmission mechanism. As defined herein, computer storage media does not include communication media. 
     Example Coding and Modulation 
       FIG. 2  illustrates projection coding of an example set of binary input bits. As discussed above with reference to  FIG. 1 , a projection coding component  116  encodes binary information bits using a weighted arithmetic addition operation to create non-binary, multi-level rateless symbols.  FIG. 2  illustrates an example in which the weights are each set to a value of 1, so the operation is effectively a non-weighted arithmetic addition operation. 
     In  FIG. 2 , the input bits are 01001011, and are shown in a column down the left side of the  FIG. 2 . In this example, the input bits are combined in approximately random groups of three to generate a rateless symbol. For example, the first three bits (010) are arithmetically added together (0+1+0=1) to generate the first symbol, “1”. The solid lines between the first three input bits and first symbol indicate that the first symbol is generated from the arithmetic addition of these first three input bits. 
     Similarly, dashed lines indicate that the second symbol, “0” is generated from the arithmetic addition of the first, third, and fourth input bits (0+0+0=0). The second, fifth, and seventh input bits (1, 1, and 1) are combined to generate the third symbol, “3”, and so on. 
     The number of rateless symbols that can be generated from the input bits depends on the total number of input bits being encoded and the number of bits being combined to form each measurement. In the described example, each rateless symbol is generated from an approximately random subset of the input bits. In alternate implementations, any number of techniques may be utilized to select and combine input bits to generate the rateless symbols. 
     Pairs of symbols are then concatenated to form points that are to be mapped to a quadrature amplitude modulation (QAM) constellation. In the illustrated example, the first two symbols are concatenated to form the constellation point “10”. Similarly, the third and fourth symbols are concatenated to form the constellation point “32”, and the fifth and sixth symbols are concatenated to form the constellation point “12”. 
       FIG. 3  illustrates sequential mapping of rateless symbols through a QAM constellation. The symbols that were concatenated to form the constellation points illustrated in  FIG. 2  are shown down the left side of  FIG. 3 . 
     In this example, because three binary input values are combined to form each symbol, each symbol has a value of 0, 1, 2, or 3. Therefore, because two symbols are concatenated to form each constellation point, each constellation point has a value between 00 and 33.  FIG. 3  illustrates a 16-QAM constellation that includes each constellation point that can be generated from the example input bits and weight values. The symbols are mapped to the square QAM constellation using Gray code such that the first digit of the constellation points increases sequentially in each row from left to right, and the second digit of the constellation points increases sequentially in each column from bottom to top. The three example constellation points are designated “A”, “B”, and “C”, and are shown as such on the 16-QAM constellation in  FIG. 3 . 
       FIGS. 2 and 3  provide a simplistic example of how multilevel rateless symbols are generated and mapped to a QAM constellation. As described above with reference to  FIG. 2 , in the illustrated example, the weights used in the arithmetic addition operation were all set to a value of “1”.  FIG. 4  illustrates a matrix representation of weight values and input binary bits that may be used by projection coding component  116  to generate multi-level rateless symbols. 
     In an example implementation, the source bits to be transmitted are divided into frames, with each frame having a length denoted by N. Depending on the specific implementation, a frame may have a length of, for example, 100, 400, 500, etc. As illustrated in  FIG. 4 , the source bits B 1 , B 2 , . . . , B N  for a particular frame are arranged as a column to form an N×1 source matrix. 
     A set of weight values is identified and used to form a low-density projection coding N×M matrix, where M represents a number of symbols to be generated from the frame of source bits. The set of weight values may take any of a variety of forms. For example, any number of weight values may be used. The number of weight values used determines the number of source bits that are combined to form each symbol. For example, if three weight values are used, then three source bits will be combined to form each symbol. Similarly, if seven weight values are used, then seven source bits will be combined to form each symbol. 
     The values of the selected weight values determine the size of the QAM constellation that will be used to map the generated symbols. For example, if the set of weight values is {1, 2, 4}, then each symbol will have a value in the set {0, 1, 2, 3, 4, 5, 6, 7}. As a result, a 64-QAM constellation will be used to map the generated symbols. 
     The selected weights may be integer or floating point numbers, and may be symmetric or non-symmetric. Symmetric weight sets include positive weight values, and corresponding negative weight values. As an example, the weight set {1, 2, 4} is a non-symmetric, integer set of weights. As another example, the weight set {−4, −2, −1, 1, 2, 4} is a symmetric, integer set of weights. Other example symmetric weight sets include {−2, −2, −1, −1, −1, 1, 1, 1, 2, 2} and {−4, −4, −2, −1, 1, 2, 4, 4}. 
     Referring back to  FIG. 4 , the projection coding matrix is constructed with M rows, each with N values. The values in each row are all zeros, except for the weight values. For example, if the weight set is {W 1 , W 2 , . . . , W L }, then the values W 1 , W 2 , . . . , W L  will be found in each row of the projection coding matrix, with each other value in each row being zero, such that a symbol generated from any given row of the projection coding matrix represents a weighted addition of L source bits. The weight values are distributed in the rows of the projection coding matrix such that multiplying the M× N matrix by the N×1 matrix generates M symbols, each based on a different weighted combination of L source bits. Both the order and the position of the L weight values in the rows of the projection coding matrix vary from one row to another, resulting in approximately random combinations of source bits. 
       FIG. 5  illustrates example modules of projection coding component  116  including a source matrix  502 , a projection coding matrix  504 , and a matrix multiplication module  506 . Source matrix  502  is a matrix of source bits. Projection coding matrix  504  is a large, low-density matrix with a set of weight values distributed in each row. Matrix multiplication module  506  is configured to multiply projection coding matrix  504  by source matrix  502  to generate a series of symbols. 
       FIG. 6  illustrates example modules of modulation component  118 . Symbol combining module  602  is configured to combine symbols generated from projection coding component  116  to form constellation points. QAM constellation  604  is a two-dimensional map of the possible symbol pair values that may be generated by symbol combining module  602 . As described above, the size of the QAM constellation  604  depends on the selected weight values. Signal modulator  606  modulates the generated rateless multilevel symbols to channel dimensions, generating a modulated data signal. 
       FIG. 7  is a flow diagram of an example process for data coding and modulation. This process is illustrated as a collection of blocks in a logical flow graph, which represents a sequence of operations that can be implemented in hardware, software, or a combination thereof. In the context of software, the blocks represent computer-executable instructions stored on one or more computer storage media that, when executed by one or more processors, cause the processors to perform the recited operations. Note that the order in which the process is described is not a limitation, and any number of the described process blocks can be combined in any order to implement the process, or alternate processes. Additionally, individual blocks may be deleted from the processes without departing from the spirit and scope of the subject matter described herein. Furthermore, while this process is described with reference to the transmitting device  102  of  FIG. 1 , other computer architectures may implement one or more portions of this process, in whole or in part. 
       FIG. 7  illustrates an example process  700  for coding and modulation of binary source data. 
     At block  702 , a block of source bits, x, is identified, where x=(x 1 , x 2 , . . . , x N ). For example, projection coding component  116  receives binary source data to be transmitted. 
     At block  704 , projection coding component  116  encodes the identified source bits into a series of symbols (s 1 , s 2 , . . . ) by projection, s i =c i ·x T , where c i  is a low-density vector. As described above with reference to  FIG. 4 , L entries in c i  are non-zero and they take values from a weight set {w 1 , w 2 , . . . , W L }. The position of the non-zero entry in c i  that takes weight w l  can be denoted by i l  (l=1, 2, . . . , L). In input vector x, only the entries at corresponding positions are sampled, so projection s i  can also be denoted as: 
     
       
         
           
             
               s 
               i 
             
             = 
             
               
                 ∑ 
                 
                   l 
                   = 
                   1 
                 
                 L 
               
               ⁢ 
               
                   
               
               ⁢ 
               
                 
                   w 
                   l 
                 
                 · 
                 
                   x 
                   
                     i 
                     l 
                   
                 
               
             
           
         
       
     
     A number of projections are applied to the block of source bits to generate multiple symbols to be transmitted. The projections s i  generate multi-level values through arithmetic weighted sums, creating a finite alphabet, S={Σ lεΛ w l |Λ ∪ {1, 2, . . . , L}}. 
     In this alphabet, the minimum and maximum values are s min =Σ w     l     &lt;0 w l  and s max =Σ w     l     &gt;0 w l . 
     At block  706 , modulation component  118  performs modulation of the symbols encoded from the source bits to generate the modulated data signal for transmission over wireless network  104 . For example, as described above with reference to  FIG. 3 , the symbols are mapped, in pairs, onto a QAM constellation. The size of the QAM constellation is based on minimum and maximum values of alphabet, S, defined above. 
     In an example implementation, the symbol values are sequentially and evenly mapped to modulated parameters of each channel dimension. In amplitude modulation, the mapping is from [s min , s max ] to [−A, A], where A represents the maximum amplitude in use. Therefore, the actual amplitude a i , used to transmit symbol s i  is given by: 
     
       
         
           
             
               a 
               i 
             
             = 
             
               
                 - 
                 A 
               
               + 
               
                 
                   
                     2 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     A 
                   
                   
                     
                       s 
                       max 
                     
                     - 
                     
                       s 
                       min 
                     
                   
                 
                 ⁢ 
                 
                   ( 
                   
                     
                       s 
                       i 
                     
                     - 
                     
                       s 
                       min 
                     
                   
                   ) 
                 
               
             
           
         
       
     
     At block  708 , the modulated data signal is transmitted over the wireless network. For example the modulated data signal is sent from modulation component  118 , through the wireless network interface  108 , over the wireless network  104 . 
     At block  710 , the transmitting device determines whether or not an acknowledgment has been received. For example, as described above with reference to  FIG. 1 , the receiving device sends an acknowledgement when the receiving device has been able to successfully decode the transmitted data. If no acknowledgment has been received (the “No” branch from block  710 ), then processing continues as described above with reference to block  704 , with a different projection being applied to the block of source bits. 
     If, at block  710 , an acknowledgement has been received (the “Yes” branch from block  710 ), then at block  712 , the transmitting device ceases the encoding and modulation of the source bits. 
     Example Demodulation and Decoding 
       FIG. 8  illustrates example modules of demodulation component  126  including demodulator  802  and symbol accumulator  804 . 
     Demodulator  802  demodulates a received signal, resulting in a received symbol, which may be different from the transmitted symbol due to channel noise. 
     Symbol accumulator  804  accumulates the demodulated symbols until a threshold number of symbols have been received. The threshold number is set based on a likelihood that the number of symbols will include enough data to enable successful decoding of the symbols, resulting in the original binary information bits. 
       FIG. 9  illustrates example modules of projection decoding component  128  including projection coding matrix  902 , initializer  904 , belief propagation process module  906 , and acknowledgment module  908 . 
     Projection coding matrix  902  corresponds to projection coding matrix  504 , which is used by the transmitting device to encode the input bits. Projection coding matrix  902  is used by the projection decoding component  128  to decode the received symbols. 
     Initializer  904  sets initial probability values for each input bit to be either a 0 a 1. For example, in an implementation, initializer  904  sets the initial probability values to 0.5, indicating that the input bits are assumed to be random, meaning that a particular input bit has an equal probability of being 0 as it has probability of being 1. In an alternate example, transmitting device  102  provides receiving device  106  with information indicating the relative distribution of 0&#39;s and 1&#39;s in the input bits. For example if approximately 75% of the input bits are 1&#39;s, then initializer  904  sets initial probability values such that the probability of a particular input bit being 1 is equal to 0.75 and the probability of a particular input bit being 0 is equal to 0.25. 
     Belief propagation process module  906  iteratively analyzes the accumulated symbols and determines, for each received symbol, probabilistic values of the input bits that were combined to create the symbol. 
     Acknowledgment module  908  confirms that the received symbols have been properly decoded. In one implementation for determining whether the source bits are properly decoded, some CRC (cyclic redundant check) bits are included in the source bits. When it is determined that the received symbols have been properly decoded, acknowledgment module  908  sends an acknowledgment message to the transmitting device  102 , signaling the transmitting device to stop sending symbols generated from the current set of input bits. 
       FIG. 10  illustrates an example process  1000  for demodulating and decoding a received data signal. This process is illustrated as a collection of blocks in a logical flow graph, which represents a sequence of operations that can be implemented in hardware, software, or a combination thereof. In the context of software, the blocks represent computer-executable instructions stored on one or more computer storage media that, when executed by one or more processors, cause the processors to perform the recited operations. Note that the order in which the process is described is not intended to be construed as a limitation, and any number of the described process blocks can be combined in any order to implement the process, or alternate processes. Additionally, individual blocks may be deleted from the processes without departing from the spirit and scope of the subject matter described herein. Furthermore, while this process is described with reference to the receiving device  106  described above with reference to  FIGS. 1 ,  8 , and  9 , other computer architectures may implement one or more portions of this process, in whole or in part. 
     At block  1002 , a modulated data signal is received. For example, as illustrated in  FIG. 1 , receiving device  106  receives a modulated data signal  114  over wireless network  104  that was sent by transmitting device  102 . 
     At block  1004 , receiving device  106  performs demodulation to determine a received symbol. For example, demodulator  802  demodulates the received signal, resulting in a symbol, which may be different from the symbol that was transmitted, due to channel noise. 
     When modulated data signal  114  is transmitted over wireless network  104 , the amplitude of the signal is modified based on channel noise. The more noise on the channel, the more the signal is modified. Due to channel noise, the amplitude of the received signal, denoted â i , is a noisy version of the amplitude of the signal that was transmitted, a i . When a Gaussian channel is considered,
 
 â   i   =a   i   +e   i   c   ,e   i   c   N (0,σ c   2 )
 
where e i   c  is the Gaussian noise with variance σ c   2 . Accordingly, the received rateless symbol, r i , corresponding to s i  can be computed as:
 
               r   i     =       s   min     +           s   max     -     s   min         2   ⁢           ⁢   A       ⁢     (         a   ^     i     +   A     )               
which reduces to:
 
               r   i     =       s   i     +           s   max     -     s   min         2   ⁢           ⁢   A       ⁢     e   i   c               
where e i  is the symbol noise with a value of:
 
               e   i     =           s   max     -     s   min         2   ⁢           ⁢   A       ⁢     e   i   c             
Because s max , s min , and A are all constants for a given projection code design, e i  is also a Gaussian variable, and its variance is given by:
 
     
       
         
           
             
               σ 
               2 
             
             = 
             
               
                 
                   
                     s 
                     max 
                   
                   - 
                   
                     s 
                     min 
                   
                 
                 
                   2 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   A 
                 
               
               ⁢ 
               
                 σ 
                 c 
                 2 
               
             
           
         
       
     
     At block  1006 , the receiving device determines whether or not a sufficient number of symbols have been received from the transmitting device. For example, symbol accumulator  804  collects the received symbols from demodulator  802 . Depending on the specific projection code design, symbol accumulator  804  continues collecting symbols until a particular number of symbols has been accumulated before beginning the decoding process. 
     At block  1008 , receiving device  106  decodes the symbols that have been received and accumulated. For example, projection decoding component  128  decodes the accumulated symbols. 
     Although a particular received symbol, r i , may not belong to the encoding alphabet, S, the value of r i  is, in most cases, in the range of [s min , s max ]. Using this information, the receiving device decodes the received symbols into binary digits using maximum a posteriori estimation. Assuming M symbols are accumulated for decoding, the rateless decoding problem can be represented by: 
     
       
         
           
             
               x 
               ^ 
             
             = 
             
               arg 
               ⁢ 
               
                 
                   max 
                   
                     x 
                     ∈ 
                     
                       
                         GF 
                         ⁡ 
                         
                           ( 
                           2 
                           ) 
                         
                       
                       N 
                     
                   
                 
                 ⁢ 
                 
                   P 
                   ⁡ 
                   
                     ( 
                     
                       
                         x 
                         ❘ 
                         
                           r 
                           1 
                         
                       
                       , 
                       
                         r 
                         2 
                       
                       , 
                       … 
                       ⁢ 
                       
                           
                       
                       , 
                       
                         r 
                         M 
                       
                     
                     ) 
                   
                 
               
             
           
         
       
       
      
       s.t. r=Cx 
       T 
       +e  
      
     
     where r=(r 1 , r 2 , . . . , r M ) T  is the vector of received symbols, and e=(e 1 , e 2 , . . . , e M ) T  is the corresponding noise vector. C is an M×N projection coding matrix  902  in which each row is a projection vector as used by the transmitting device to encode the symbols. 
     The projection code that is used to encode binary digits into multilevel symbols can be represented by a bipartite graph, where left nodes are binary input and right nodes are encoded multilevel symbols. According to this structure, initializer  904  initializes the message sent by each input node x j  to its connected symbol node s i  as: 
                   {               u   ji     (   0   )       ⁡     (   0   )       =     P   ⁡     (       x   j     =   0     )                       u   ji     (   0   )       ⁡     (   1   )       =     P   ⁡     (       x   j     =   1     )                       
With an initial assumption that the input bits are random, the probabilities P(x j =0) and P(x j =1) are equal. However, in an example implementation, the transmitting device notifies the receiving device of the distribution of 1&#39;s and 0&#39;s in the original data. P(x j =0) and P(x j =1) are initialized accordingly. Having this information is not necessary, but if it is available, the efficiency of the decoding process is increased.
 
     As discussed above with reference to the encoding process, an encoded rateless symbol is the weighted sum of multiple input bits. When the encoded rateless symbol is transmitted, channel noise modifies the amplitude of the signal carrying the rateless symbol. Accordingly, a received rateless symbol r i  can be expressed as:
 
 r   i   =w   1   x   i     1     w   2   x   i     2     + . . . +w   L   x   i     L     e   i  
 
     If j=i l  and X i =r i −w l x j , then the message sent from the i-th symbol node to the j-th variable node in the t-th iteration round is: 
     
       
         
           
               
             
               { 
               
                 
                   
                     
                       
                         
                           v 
                           ij 
                           
                             ( 
                             t 
                             ) 
                           
                         
                         ⁡ 
                         
                           ( 
                           0 
                           ) 
                         
                       
                       = 
                       
                         
                           P 
                           ⁡ 
                           
                             ( 
                             
                               
                                 x 
                                 j 
                               
                               = 
                               
                                 0 
                                 ❘ 
                                 
                                   r 
                                   i 
                                 
                               
                             
                             ) 
                           
                         
                         = 
                         
                           P 
                           ⁡ 
                           
                             ( 
                             
                               
                                 X 
                                 j 
                               
                               = 
                               
                                 r 
                                 i 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
                 
                   
                     
                       
                         
                           v 
                           ij 
                           
                             ( 
                             t 
                             ) 
                           
                         
                         ⁡ 
                         
                           ( 
                           1 
                           ) 
                         
                       
                       = 
                       
                         
                           P 
                           ⁡ 
                           
                             ( 
                             
                               
                                 x 
                                 j 
                               
                               = 
                               
                                 1 
                                 ❘ 
                                 
                                   r 
                                   i 
                                 
                               
                             
                             ) 
                           
                         
                         = 
                         
                           P 
                           ⁡ 
                           
                             ( 
                             
                               
                                 X 
                                 j 
                               
                               = 
                               
                                 
                                   r 
                                   i 
                                 
                                 - 
                                 
                                   w 
                                   l 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
             
           
         
       
     
     The distribution of X j  is the convolution product of the weighted distribution of every other variable node and e i , given by: 
               P   ⁡     (     X   j     )       =       {           ⊗               i   k     ,     0   &lt;   k   ≤   L     ,     k   ≠   l             ⁢     P   ⁡     (       w   k     ⁢     x     i   k         )         }     ⊗     P   ⁡     (     e   i     )               
where the distribution of the weighted variable is:
 
     
       
         
           
               
             
               { 
               
                 
                   
                     
                       
                         P 
                         ⁡ 
                         
                           ( 
                           
                             
                               
                                 w 
                                 k 
                               
                               ⁢ 
                               
                                 x 
                                 
                                   i 
                                   k 
                                 
                               
                             
                             = 
                             0 
                           
                           ) 
                         
                       
                       = 
                       
                         
                           u 
                           
                             i 
                             
                               k 
                               i 
                             
                           
                           
                             ( 
                             
                               t 
                               - 
                               1 
                             
                             ) 
                           
                         
                         ⁡ 
                         
                           ( 
                           0 
                           ) 
                         
                       
                     
                   
                 
                 
                   
                     
                       
                         P 
                         ⁡ 
                         
                           ( 
                           
                             
                               
                                 w 
                                 k 
                               
                               ⁢ 
                               
                                 x 
                                 
                                   i 
                                   k 
                                 
                               
                             
                             = 
                             
                               w 
                               k 
                             
                           
                           ) 
                         
                       
                       = 
                       
                         
                           u 
                           
                             k 
                             
                               k 
                               i 
                             
                           
                           
                             ( 
                             
                               t 
                               - 
                               1 
                             
                             ) 
                           
                         
                         ⁡ 
                         
                           ( 
                           1 
                           ) 
                         
                       
                     
                   
                 
               
             
           
         
       
     
     The convolution is implemented through simple addition in the Fourier domain. The decoding algorithm is further simplified based on the knowledge that the input digits are binary. Based on this knowledge, the message sent by the j-th variable node to the i-th symbol node in iteration round t is: 
                   {               u   ji     (   t   )       ⁡     (   0   )       =       C   ji     ⁢     P   ⁡     (       x   j     =   0     )       ⁢       ∏     k   ∈       T   j     ⁢   \   ⁢   i         ⁢           ⁢       u   kj     (   t   )       ⁡     (   0   )                           u   ji     (   t   )       ⁡     (   1   )       =       C   ji     ⁢     P   ⁡     (       x   j     =   1     )       ⁢       ∏     k   ∈       T   j     ⁢   \   ⁢   i         ⁢           ⁢       u   kj     (   t   )       ⁡     (   1   )                           
where T j  is the index set of the symbol nodes connected with variable node j. If there is an edge between variable node j and symbol node i, then iεT j . C ji  is a normalization constant which ensures:
 
 u   ji   (t) (0)+ u   ji   (t) (1)=1
 
     After T rounds of iteration, the belief propagation process stops and outputs the following posterior probabilities of the j-th variable node being 0 and 1: 
     
       
         
           
               
             
               { 
               
                 
                   
                     
                       
                         
                           u 
                           j 
                           
                             ( 
                             T 
                             ) 
                           
                         
                         ⁡ 
                         
                           ( 
                           0 
                           ) 
                         
                       
                       = 
                       
                         
                           C 
                           j 
                         
                         ⁢ 
                         
                           P 
                           ⁡ 
                           
                             ( 
                             
                               
                                 x 
                                 j 
                               
                               = 
                               0 
                             
                             ) 
                           
                         
                         ⁢ 
                         
                           
                             ∏ 
                             
                               k 
                               ∈ 
                               
                                 T 
                                 j 
                               
                             
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             
                               u 
                               kj 
                               
                                 ( 
                                 T 
                                 ) 
                               
                             
                             ⁡ 
                             
                               ( 
                               0 
                               ) 
                             
                           
                         
                       
                     
                   
                 
                 
                   
                     
                       
                         
                           u 
                           j 
                           
                             ( 
                             T 
                             ) 
                           
                         
                         ⁡ 
                         
                           ( 
                           1 
                           ) 
                         
                       
                       = 
                       
                         
                           C 
                           j 
                         
                         ⁢ 
                         
                           P 
                           ⁡ 
                           
                             ( 
                             
                               
                                 x 
                                 j 
                               
                               = 
                               0 
                             
                             ) 
                           
                         
                         ⁢ 
                         
                           
                             ∏ 
                             
                               k 
                               ∈ 
                               
                                 T 
                                 j 
                               
                             
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             
                               u 
                               kj 
                               
                                 ( 
                                 T 
                                 ) 
                               
                             
                             ⁡ 
                             
                               ( 
                               1 
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
             
           
         
       
     
     Then, the values of the input binary digits are estimated by: 
     
       
         
           
             
               x 
               j 
             
             = 
             
               { 
               
                 
                   
                     0 
                   
                   
                     
                       
                         
                           u 
                           j 
                           
                             ( 
                             T 
                             ) 
                           
                         
                         ⁡ 
                         
                           ( 
                           0 
                           ) 
                         
                       
                       ≥ 
                       
                         
                           u 
                           j 
                           
                             ( 
                             T 
                             ) 
                           
                         
                         ⁡ 
                         
                           ( 
                           1 
                           ) 
                         
                       
                     
                   
                 
                 
                   
                     1 
                   
                   
                     otherwise 
                   
                 
               
             
           
         
       
     
     At block  1010 , projection decoding component  128  determines whether or not the received symbols have been successfully decoded. For example, based on the channel coding rate used to transmit the data, acknowledgment module  908  verifies the estimated values of the input binary digits against included redundancy data. 
     If acknowledgment module  908  determines that the received symbols have not been successfully decoded (the “No” branch from block  1010 ), then processing continues as described above with reference to block  1004  with additional symbols being received, demodulated, and accumulated. 
     On the other hand, if acknowledgment module  908  determines that the received symbols have been successfully decoded (the “Yes” branch from block  1010 ), then at block  1012 , acknowledgment module  908  sends an acknowledgment message over wireless network  104  to transmitting device  102 , signaling transmitting device  102  to stop sending symbols based on the current set of input bits. 
     A transmitting device implements compressive wireless modulation, as described herein, through projection coding and modulation using a dense QAM constellation. A projection code described herein generates symbols based on a weighted arithmetic sum of approximately random combinations of input bits. As described herein, QAM modulation is used, however, other types of digital modulation and analog modulation techniques, including, for example, PSK (phase-shift keying), FSK (frequency-shift keying), AM (amplitude modulation), PM (phase modulation), or FM (frequency modulation), may also be implemented to support compressive wireless modulation. Furthermore, alternate demodulation and decoding techniques may be used as appropriate, based on the specific encoding and modulation techniques that are implemented. 
     CONCLUSION 
     Although the subject matter has been described in language specific to structural features and/or methodological operations, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or operations described. Rather, the specific features and acts are disclosed as example forms of implementing the claims.