Abstract:
A system and method to reduce a ratio between a peak signal power and an average power (PAPR) in a multi-tone communication system. The system includes an encoder configured to receive a plurality of input bits and to generate a plurality of coded symbols based on the plurality of input bits, and a phase shift calculator configured to calculate a plurality of phase shift values for the coded symbols that minimizes the peak to average power ratio. The system further includes an encoding phase shifter coupled to the encoder and the phase shift calculator, configured to receive the phase shift values from the phase shift calculator and configured to phase shift the plurality of coded symbols to generate a plurality of phase shifted symbols.

Description:
REFERENCE TO RELATED APPLICATIONS 
     This application claims the benefit of U.S. Provision Application No. 60/092,813, filed Jul. 14, 1998. 
    
    
     FIELD OF THE INVENTION 
     This invention relates to communication systems with multi-tone transformation and, in particular, communication systems in which the multi-tone transformed signals are phase shifted in order to reduce their peak to average power ratios. 
     BACKGROUND OF THE INVENTION 
     Communication systems with multi-tone transformation are well known in the art. The multi-tone transformation is also referred as a discrete multi-carrier modulation or orthogonal frequency division multiplexing (OFDM). 
     Multi-tone transformation has widespread practical communication applications including communication systems using twisted pairs of wires which provide high speed wireline communication connections. Further, its hardware implementation lends itself to discrete Fourier Transformation (DFT) structures which are both inexpensive and well understood. 
     FIG. 1 illustrates a conventional multi-tone transformation transmitter  101  which includes a channel coder  103 , a constellation mapper  105 , an Inverse Discrete Fourier Transform (IDFT) device  107  and an RF amplifier  109 . Illustratively, the output of RF amplifier  109  is provided on a pair of twisted wires  111  or over a wireless communication channel. The channel coder  103  receives a plurality of input bits. The combination of the channel coder  103  and the constellation mapper  105  converts the received input bits to constellation symbols. The constellation symbols are input to the IDFT device  107 , and its output signal is fed to the RF amplifier  109 . With certain combinations of the constellation symbols, the output signal from IDFT device  107  has peak signals having larger signal magnitudes than that of average signals. This requires that the RF amplifier  109  operate linearly for a wide range of magnitudes in order to avoid clipping the peak signals. Amplifiers that have a wide dynamic range are expensive. Furthermore, practical amplifiers with reasonable dynamic range saturate at a certain peak and may attenuate the peak signals. This is known as the peak to average signal power ratio problem. 
     A number of possible solutions to the peak to average signal power ratio problem have been suggested. For example, U.S. Pat. No. 5,835,536 (May), which is incorporated herein by reference, teaches a communication system which generates time-domain discrete multi-tone symbols. Its peak to average power requirements are reduced by (1) comparing the magnitude of the time-domain discrete multi-tone symbols with a magnitude threshold and (2) clipping the magnitude of those time-domain discrete multi-tone symbols which have larger magnitudes than that of the magnitude threshold. However, by clipping the magnitudes, it loses information. 
     In another example, U.S. Pat. No. 5,838,732 (Carney) discloses a multi-channel wireless communication system which produces digital baseband modulated signals by modulating digital baseband channel signals according to its desired interface standard. In order to reduce its peak to average variance, the digital baseband modulated signals are then phase shifted by digital phase shifters. 
     SUMMARY OF THE INVENTION 
     The present invention provides a simplified and efficient method and system for reducing the peak to average power ratio (PAPR) in communication systems having multi-tone transformation. This is achieved without changing the error correction capability of the overall system, the encoding rate of its transmitter, and the decoding complexity of its receiver. 
     The method of the present invention includes the steps of receiving at least one block of bits of information and then generating a codeword which includes an N number of digital multi-tone symbols based on the block of input bits, wherein N is a positive integer. The method further includes the steps of calculating a plurality of phase shift values for the digital multi-tone symbols that minimizes the PAPR and phase shifting the digital multi-tone symbols by the phase shift values, to thereby reduce the PAPR. 
     The system of the present invention includes an encoder configured to receive a plurality of input bits and to generate a plurality of coded symbols based on the plurality of input bits and a phase shift calculator configured to calculate a plurality of phase shift values for the coded symbols that minimizes the peak to average power ratio. The system further includes an encoding phase shifter coupled to the encoder and the phase shift calculator, configured to receive the phase shift values from the phase shift calculator and configured to phase shift the plurality of coded symbols to generate a plurality of phase shifted symbols and an amplifier coupled to the encoding phase shifter and configured to amplify a plurality of symbols it receives. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a schematic diagram of a conventional transmitter; 
     FIG. 2 is a schematic diagram of a transmitter of the present invention; and 
     FIG. 3 is a schematic diagram of a receiver of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     In the following description, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be obvious, however, to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known circuits, structures and techniques have not been shown in detail in order not to unnecessarily obscure the present invention. 
     Referring to FIG. 2, a transmitter  201  of the present invention includes an encoder  203 , a serial/parallel device  205 , an Inverse Discrete Fourier Transform (IDFT) device  207 , an RF device  209 , and an encoding phase shifter  213 . In the preferred embodiment, a phase shift calculator  215  is provided separate from the transmitter  201 . In an alternative embodiment, the phase shift calculator  215  can be provided in the transmitter  201  as well. 
     The encoder  203  receives blocks B T  of k bits at each predetermined period T=0, T, 2T, . . . The received k bits are encoded into a sequence of N constellation symbols of a constellation Q with 2 a  elements, where “k” and “a” are each any arbitrary integer. In the preferred embodiment, N=2 m  (which allows better and faster hardware implementations). In alternative embodiments, N can be any arbitrary integer. In the preferred embodiment, the encoding rate of the encoder  203  is R=k/aN. 
     In another preferred embodiment, the encoder  203  is a cascade of a channel coder and a constellation mapper, whereby the channel coder first maps the k input bits into a sequence of the output bits, and then the constellation mapper maps the output bits into a sequence of N constellation symbols. In an alternative embodiment, the encoder  203  is a coded modulator, wherein the encoder uses a coded modulation scheme to map the input bits to the N output constellation symbols. It should be noted that an encoder can be an apparatus or an ensemble of devices (such as the channel coder and the constellation mapper) which generates a sequence of N constellation symbols given an input block of k bits. 
     Upon processing the k input bits B T , the output of the encoder  203  is a sequence of N constellation symbols c 0   T , c 1   T , . . . , c N−1   T . Any possible output sequence of the encoder  203  is called a codeword (of the encoder). The output of the encoder goes through the serial to parallel device  205  and the IDFT device  207  produces a sequence of symbols C 0   T , C 1   T , . . . , C N−1   T , which are represented as:                  C   T   l     =       ∑     i   =   0       N   -   1              c   T   i          exp        [     2                 π                   lj   /   N       ]             ,           (   1   )                                
     for l=0, 1, 2, . . . N−1, where j={square root over (−)}1. 
     Alternatively, the IDFT device  207  can be placed before the serial to parallel device  205 . In any event, the sequence of symbols is input to the RF device  209  which produces a transmitted signal. The transmitted signal at time t is then given as:                  S   T          (   t   )       =       ∑     i   =   0       N   -   1              c   T   i          exp        [     2                   π        (       f   0     +     if   s       )          j                 t     ]                   (   2   )                                
     for 0≦t≦1/f s , where f 0  is the carrier frequency and f s  is the bandwidth of each tone, and preferably f s =1/T. 
     In one exemplary embodiment, the signal constellation Q is binary phase shift keying (BPSK). This means that the C T   i , i=0,1, . . . ,N−1 are allowed to take only values 1 and −1. In this embodiment, k=N and the encoder  203  maps a sequence of k input bits to N constellation symbols by mapping the i-th input bit b T   i , i=0,1, . . . N−1 to the constellation symbol (−1) b     T       i   . The transmitted signal at time T is then given as:                    S   T          (   t   )       =       ∑     i   =   0       N   -   1                (     -   1     )       b   T   i            exp        [     2                   π        (       f   o     +     if   s       )          j                 t     ]             ,           (   3   )                                
     where        0   ≤   t   ≤       1     f   s       .                            
     For any arbitrary block of input bits B T , the average power of the above signal is N. Some arrangement of bits, however, allow constructive additions of the instantaneous powers of the components of S T (t). For instance, the all zero input bit stream 000 . . . 0 is mapped to the sequence of all ones 1,1, . . . , 1 symbols producing          ∑     i   =   0       N   -   1            exp        [     2                   π        (       f   0     +     if   s       )          jt     ]                              
     at the output of the RF device. This signal has its peak power N 2  at time t=0. Thus, in this embodiment, the peak to average power ratio of the transmitted signals can vary within the range 0 to N. As mentioned above, this requires that the amplifier operate linearly for a wide range in order to avoid clipping the peak signals. 
     The encoding phase shifter  213  and phase shift calculator  215  reduce the peak power of the peak signal. The following is a discussion relating to the theoretical derivation for implementing the encoding phase shifter  213  and phase shift calculator  215 . 
     For the encoder  203 , the peak to average power ratio of the encoder  203  is defined to be the maximum possible peak to average power ratio of its codewords of the encoder  203 . That is, Peak to Average Power Ratio is defined as:                PAPR        (   C   )       =       max     c   ∈   C            [     PAPR        (   c   )       ]               (   4   )                                
     For a codeword c=c 0 c 1  . . . c N−1 , c 0 , c 1 , . . . c N−1  are referred to as the zero-th, the first, . . . , and the (N−1)-th coordinates of C, respectively. 
     The preferred embodiment of the present invention shifts the i-th coordinates of all the codewords of C by a known phase φ i . Thus, any arbitrary codeword c=c 0 c 1  . . . c N−1  is mapped into: 
     
       
           c   0  exp( jφ   0 ) c   1  exp( jφ   1 ) . . .  c   N−1  exp( jφ   N−1 ). 
       
     
     The set of all these codewords is denoted by C(φ 0 , φ 1 , . . . , φ N−1 ). The output of a corresponding RF device  209  is thus the signal as defined by:                    s   T          (     t   ,     φ   0     ,     φ   1     ,   …              ,     φ     N   -   1         )       =       ∑     i   =   0       N   -   1              c   i          exp        [       (       2                   π        (       f   0     +     if   s       )          t     +     φ   i       )        j     ]             ,           (   5   )                                
     for 0≦t≦1/f s . 
     It can be easily seen that the peak power of s T (t, φ 0 , φ 1 , . . . , φ N−1 ) is given as:                max     0   ≤   t   ≤     1   /     f   s                         ∑     i   =   0       N   -   1              c   i          exp        [       (       2                 π                   if   s        t     +     φ   i       )        j     ]                2             (   6   )                                
     which by a simple normalization is equal to:                max     0   ≤   t   ≤   1                     ∑     i   =   0       N   -   1              c   i          exp        [       (       2                 π                 it     +     φ   i       )        j     ]                2             (   7   )                                
     Furthermore, the average power of s T (t, φ 0 , φ 1 , . . . , φ N−1 ) is          ∑     i   =   0       N   -   1                     c   i          2     .                            
     Thus, the peak to average power ratio of the signal s T (t) is given as:                  PAPR        (     c   ,     φ   0     ,     φ   1     ,   …              ,     φ     N   -   1         )       =       max     0   ≤   t   ≤   1                       ∑     i   =   0       N   -   1              c   i          exp        [       (       2                 π                 it     +     φ   i       )        j     ]                2         ∑     i   =   0       N   -   1                   c   i          2             ,           (   8   )                                
     which is independent of f s  and only depends on the codeword c 0 c 1  . . . c N− and the phase shift values φ 0 , φ 1 , . . . φ N−1 . Therefore:                PAPR        (     C        (       φ   0     ,     φ   1     ,   …              ,     φ     N   -   1         )       )       =       max     c   ∈   C            PAPR        (     c   ,     φ   0     ,     φ   1     ,   …              ,     φ     N   -   1         )                 (   9   )                                
     depends only on the structure of the encoder  203  and the phases shift values φ 0 , φ 1 , . . . , φ N−1 . 
     Given that φi, i=0, 1, . . . , N−1 are chosen appropriately, the code C(φ 0 , φ 1 , . . . , φ N−1 ) may have a lower peak to average power ratio than that of the encoder without applying the phase shift values. Indeed, the phase shift values of φ 0 , φ 1 , . . . , φ N−1  are chosen such that the peak to average power ratio of C(φ 0 , φ 1 , . . . , φ N−1 ) is minimized among all the possible choices. Thus the values of φ 0 , φ 1 , . . . , φ N−1  are given by the minimizing values of the PAPR(C(φ 0 , φ 1 , . . . , φ N−1 )). In mathematical terminology: 
      arg min  PAPR ( C (φ 0 , φ 1 , . . . , φ N−1 ))  (10) 
     is computed. 
     For the encoder  203 , the minimizing values φ 0 , φ 1 , . . . , φ N−1  are computed only once and can be tabulated therein. In the preferred embodiment, the φ 0 , φ 1 , . . . , φ N−1  are calculated by the phase shift calculator  215 , off-line. 
     The value PAPR(C(φ 0 , φ 1 , . . . , φ N−1 )) can be rewritten as:                PAPR        (     C        (       φ   0     ,     φ   1     ,   …              ,     φ     N   -   1         )       )       =       max       0   ≤   t   ≤   1     ,     c   ∈   C                           ∑     i   =   0       N   -   1              c   i          exp        [       (       2                 π                 it     +     φ   i       )        j     ]                2         ∑     i   =   0       N   -   1                   c   i          2         .               (   11   )                                
     It follows that in order to minimize the PAPR(C(φ 0 , φ 1 , . . . , φ N−1 )), values for φ 0 , φ 1 , . . . , φ N−1  are calculated that attain:                min       φ   0     ,   …              ,     φ     N   -   1                  max       0   ≤   t   ≤   1     ,     c   ∈   C                         ∑     i   =   0       N   -   1              c   i          exp        [       (       2                 π                 it     +     φ   i       )        j     ]                2         ∑     i   =   0       N   -   1                   c   i          2                   (   12   )                                
     In other words, Eq. 12 is maximized with respect to codeword c, then maximized with respect to t between 0 and 1, and then minimized with respect to φ. 
     In another embodiment, the transmitted signal at time t is represented as:          s        (     t   ,     φ   0     ,     φ   1     ,   …              ,     φ     N   -   1         )       =     ℜ        (       ∑     i   =   0       N   -   1              c   i          exp        [       -     (       2                   π        (       f   0     +     if   s       )          t     +     φ   i       )          j     ]           )                              
     for 0≦t≦1/f s , and where (func( )) represents the real part of func( ). It follows that:                PAPR        (       C        (         φ   0          φ   1       ,   …              ,     φ     N   -   1         )       ,   ς     )       =     2   *       max       0   ≤   t   ≤   1     ,     c   ∈   C                         ∑     i   =   0       N   -   1            [         d   i          cos        (       2                   π        (     ς   +   i     )          t     +     φ   i       )         +       e   i          sin        (       2                   π        (     ς   +   i     )          t     +     φ   i       )           ]            2            c        2                   (   13   )                                
     where ζ=f 0 /f s &gt;&gt;1, and c i =d i +e i j where d i  and e i  are real and imaginary parts of c i , respectively. Hence, PAPR can be represented as:                  PAPR        (       C        (         φ   0          φ   1       ,   …              ,     φ     N   -   1         )       ,   ς     )       =     2                     max     0   ≤   t   ≤   1                       g        (     t   ,   ς     )             ,     
            g        (     t   ,   ς     )       =       max     c   ∈   C                       ∑     i   -   0       N   -   1            [         d   i          cos        (       2                   π        (     ς   +   i     )          t     +     φ   i       )         +       e   i          sin        (       2                   π        (     ς   +   i     )          t     +     φ   i       )           ]            2            c        2                   (   14   )                                
     for 0≦t≦1. In order to efficiently attain the value of function g(t, ζ) for each t a codeword 
     
       
           c= ( d   0   +e   0   j,d   1   +e   1   j, . . . d   N−1   +e   N−1   j ) 
       
     
     is calculated for which its unit vector ĉ=c/∥c∥ is geometrically the closest to or the farthest from the vector:            ω   ^          (     t   ,   ς     )       =       1     N            (       exp        [       (       2                 π                 ς                 t     +     φ   0       )        j     ]       ,     
          exp        [       (       2                   π        (     ς   +   1     )          t     +     φ   1       )        j     ]       ,   …              ,       exp   [       2                   π        (     ς   +   N   -   1     )          t     +     φ     N   -   1         )        j       ]             )                              
     The above relationship is further explained by defining          x   ·   y     =       ∑     i   =   0       N   -   1              x   i            y   _     i                                
     as an inner product of x and y, where x=(x 0 x 1 , . . . , x N−1 ) and y=(y 0 y 1 , . . . , y N-1 ). It follows that g(t, ζ)=N|(ĉ·{circumflex over (ω)}(t, ζ))| 2 , where (ĉ·{circumflex over (ω)}(t, ζ)) is the real part of (ĉ·{circumflex over (ω)}(t, ζ)). 
     Let c denote the codeword for which g(t, ζ) is attained. If (ĉ·{circumflex over (ω)}(t, ζ))≧0, then c maximizes (ĉ·{circumflex over (ω)}(t,ζ)) amongst all codewords. This means that ∥ĉ−{circumflex over (ω)}(t,ζ)∥ 2 =2−2(ĉ·{circumflex over (ω)}(t,ζ)) is minimized. Alternatively, if (ĉ·{circumflex over (ω)}(t,ζ))&lt;0, then c minimizes (ĉ·{circumflex over (ω)}(t,ζ)) amongst all codewords. This means that ∥ĉ−{circumflex over (ω)}(t,ζ)∥ 2 =2−2(ĉ·{circumflex over (ω)}(t,ζ)) is maximized. 
     The computation of the codeword c is accomplished by using the Viterbi algorithm which is well known in the art. Once the codeword c is calculated, that codeword is used to calculate the g(t,ζ). Subsequently, g(t,ζ) is maximized with respect to t and then minimized with respect to φ. This step generates the minimizing values of φi, i=0,1, . . . , N−1. 
     In alternative embodiments, solutions to minimax problems that are well known in the art can be used to compute the minimizing values of φi, i=0,1, . . . , N−1. For instance, sequential quadratic programming can be used for solving the above minimax problem defined in Eq. 12. 
     In one exemplary embodiment, the encoder  203  receives input blocks of length of 4 and generates sequences of binary phase shift keying (BPSK) constellation symbols of length 4. If the i-th bit of the input block is b i , the i-th element of the constellation symbol sequence is (−1) bi . Using the sequential quadratic programming, the following minimizing phase shift values for φ 0 , φ 1 , . . . , φ N−1  are obtained as: 
     
       
         φ 0 =149.76, 
       
     
     
       
         φ 1 =0, 
       
     
      φ 2 =336.6, 
     and 
     
       
         φ 3 =79.56, 
       
     
     where all the angles are given in degrees. The PAPR (C(φ 0 , φ 1 , φ 2 , φ 3 )) is 1 dB less than PAPR(C)=6 dB. 
     In another exemplary embodiment, the encoder  203  receives input blocks of length 8 and outputs sequences of BPSK constellation symbols of length 8. If the i-th bit of the input block is b i , the i-th element of the constellation symbol sequence is (−1) bi . Using the sequential quadratic programming the following minimizing phase shift values for φ 0 , φ 1 , . . . , φ N−1  are obtained as: 
     
       
         φ 0 =91.16, 
       
     
     
       
         φ 1 =39.96, 
       
     
     
       
         φ 2 =11.19, 
       
     
     
       
         φ 3 =145.8, 
       
     
     
       
         φ 4 =243.0, 
       
     
     
       
         φ 5 =289.8, 
       
     
     
       
         φ 6 =100.44, 
       
     
     and 
     
       
         φ 7 =127.08, 
       
     
     where all the angles are given in degrees. The PAPR(C(φ 0 , φ 1 , φ 2 , . . . , φ 7 )) is 1.8 dB less than PAPR(C)=9 dB. 
     To recap, once the phase shift values are calculated by the phase shift calculator  215 , the phase shift values are downloaded to and stored in the encoding phase shifter  213 . In turn, the encoding phase shifter phase shifts the code words to: 
     
       
           c   0  exp( jψ   0 ) c   1  exp( jψ   1 ) . . . c N−1  exp( jψ   N−1 ), 
       
     
     as described above. Corresponding signals are generated by the serial to parallel device  205 , the IDFT device  207 , and the RF device  209 . The output of the RF device is sent to a receiver via a twisted pair of wires  211 . Alternatively, the output of the RF device is sent over a wireless communication channel. 
     Referring to FIG. 3, a receiver  301  includes an RF device  303 , a Discrete Fourier Transform (DFT) device  305 , a parallel to serial device  307 , a decoder  309 , and a decoding phase shifter  311 . 
     The receiver  301  receives the signal S T (t) perturbed by noise. The RF device  303  processes the received signal and obtains estimates of the parameters C T   i , i=0,1, . . . , N−1. The DFT device  305  applies discrete Fourier transform on these estimates. The decoder  309  then generates estimates of c T   0 , c T   1 , . . . , c T   N−1  from which it extracts the bit block B T  after the phase shifting by the decoding phase shifter  311  is applied. Alternatively, the parallel to serial device  307  can be placed before the DFT device  303 . 
     It should be noted that the phase shift values are downloaded to both the encoding phase shifter  213  and the decoding phase shifter  311 . Because the i-th coordinate of all the codewords is phase shifted by a fixed amount φ i , phase shifts can be compensated in the decoder  309  following the application of the DFr device  305 . Thus, these phase shifts do not change the error correction capability, the rate of the encoder, and the decoding complexity of the receiver. 
     In other words, assuming that the signal coding scheme in the encoder has the desired transmission rate as well as a certain desired error protection level, the present invention reduces the PAPR(C) without reducing the rate or error protection capability of the coding scheme and without increasing the decoding complexity. 
     It should be understood that various modifications will be readily apparent to those skilled in the art without departing from the scope and spirit of the invention. For example, the present invention can also be applied to Multislit Spectroscopy (see M. J. E. Golay, “Multislit Spectroscopy”,  J. Opt. Soc. Amer.,  39, pp. 437-444, 1949, which is incorporated herein by reference). Accordingly, it is not intended that the scope of the claims appended hereto be limited to the description set forth herein, but rather that the claims be construed as encompassing all the features of patentable novelty that reside in the present invention, including all features that would be treated as equivalents thereof by those skilled in the art to which this invention pertains.