Abstract:
An apparatus and a method for peak-to-average power ratio reduction of an OFDM signal are disclosed. The method uses the interleaved characteristics of partial transmit sequences to partition input data x[n] of length N into several disjoint subblocks in time domain, and a complete N-point signal {tilde over (x)}[n] is composed after phase optimization, where N is the length of an OFDM signal and n=0, 1, . . . , N−1. Accordingly, the apparatus comprises an N-point inverse fast Fourier transform (N-IFFT), a de-multiplexer, a combiner, a set of memory and an adder. This invention uses only one N-IFFT, whereby it can achieve significant computation reduction. This invention requires (N/2)log 2  N complex multiplications and N memory units. It also preserves the inherent property as well as advantages of an OFDM system.

Description:
FIELD OF THE INVENTION  
       [0001]     The present invention generally relates to the technology for solving the problem of peak-to-average power ratio (PAPR) of an orthogonal frequency division multiplexing (OFDM) signal at transmission side, and more specifically to a method for PAPR reduction of an OFDM signal, and an apparatus of performing the same.  
       BACKGROUND OF THE INVENTION  
       [0002]     Multicarrier communication systems such as discrete multitone (DMT) and OFDM systems have attracted much attention in the applications of high-speed communication. The applications include digital subscriber line (DSL), digital terrestrial broadcasting, wireless local area network (WLAN), wireless metropolitan area network (WMAN), dedicated short range communication (DSRC) and power line communication. They are also becoming the main stream of the next generation mobile communication. The advantages of the multicarrier communication systems lie in partitioning a high-speed data stream into a plurality of parallel data streams, each transmitted by a subcarrier. As such, each data stream is transmitted at low speed, and thus has a stronger capability in anti-multipath channel effect and narrowband interference.  
         [0003]      FIG. 1  shows a block diagram of a conventional OFDM transmitter. In the OFDM transmitter, the input data X[k], k=0, 1, . . . , N−1, are transmitted in an OFDM symbol period. After the serial/parallel transformation, N-point inverse fast Fourier transform (N-IFFT), and parallel/serial transformation, the input data are transformed into the following discrete time sequence:  
                 x   ⁡     [   n   ]       =       1     N       ⁢       ∑     k   =   0       N   -   1       ⁢       X   ⁡     [   k   ]       ⁢     W   N   kn             ,     n   =   0     ,   1   ,   …   ⁢           ,     N   -   1             (   1   )               
 where 
 W N ≡e j2π/N   (2)  
 is the twiddle factor. The discrete time sequence x[n] obtained from equation (1) undergoes the cyclic prefix insertion and digital/analog transformation to obtain an analog signal x(t). The analog signal x(t) is then transmitted to the RF front end for further processing, including an IQ modulation, an up conversion, and a power amplification. The PAPR of the analog signal x(t) is several dB higher than the PAPR of the corresponding discrete time sequence x[n], and is close to the PAPR of x[n/R] where x[n/R] represents the sequence obtained by R times oversampling of x[n]. Therefore, the PAPR of x(t) can be approximated by using x[n/R] as follows:  
             PAPR   =         max     0   ≤   n   ≤     RN   -   1         ⁢            x   ⁡     [     n   /   R     ]            2         E   ⁢     {            x   ⁡     [     n   /   R     ]            2     }                 (   3   )               
 where E{•} is the expectation operation. The approximation is relatively accurate when R≧4. However, one of the main disadvantages of multicarrier communication systems is the high PAPR of the modulated signal. When the modulated signal with a high PAPR passes through the RF front end, the signal is distorted due to the non-linearity of a regular RF amplifier. The non-linearity not only causes the in-band signal distortion which leads to the increase of the bit error rate (BER), but also causes the out-of-band radiation which leads to the interference of adjacent channels, a violation of the government regulation. A straightforward solution to this problem would be using an RF amplifier with a larger linear range. However, the aforementioned solution will lead to the reduction of power efficiency, higher power consumption and a higher manufacturing cost. 
 
         [0004]     There are several conventional methods for solving the aforementioned problem, including block coding, clipping, partial transmit sequences (PTS), selective mapping (SLM), tone reservation (TR), tone injection (TI) and pulse superposition. Among these methods, the PTS method is most attractive due to its relatively low realization complexity and capability in PAPR reduction. Ericsson (U.S. Pat. No. 6,125,103) disclosed a method for using PTS to solve the high PAPR of the signal at the OFDM transmission end, as shown in  FIG. 2 . The explanation is as follows.  
         [0005]     First, the input data X[k] of length N is partitioned in the frequency domain into M disjoint subblocks, represented by X 1 [k], X 2 [k], . . . , X M [k], k=0, 1, . . . , N−1. The partition can be interleaved, adjacent, or irregular, as shown in  FIG. 3  (using M=4 as an example). The M disjoint subblocks are phase-rotated and added to form the following signal:  
                   X   ~     ⁡     [   κ   ]       =       ∑     m   =   1     M     ⁢       b   m     ⁢       X   m     ⁡     [   κ   ]             ,     κ   =   0     ,   1   ,   …   ⁢           ,     N   -   1             (   4   )             
 
 where b m  is the phase rotation parameter of the m-th subblock (m∈{1, 2, . . . , M}) and |b m |=1. 
 
         [0006]     Equation (4), after the N-IFFT, becomes:  
                   x   ~     ⁡     [   n   ]       =       ∑     m   =   1     M     ⁢       b   m     ⁢       x   m     ⁡     [   n   ]             ,     n   =   0     ,   1   ,   …   ⁢           ,     N   -   1             (   5   )             
 
 where x m [n] is the N-IFFT of X m [k]. In the PAPR reduction, the object of the PTS method is the phase optimization, i.e., seeking for the optimal sequence {b 1 , b 2 , . . . , b M } so that the PAPR of the transmitted signal is minimum. In practice, the phase of b m  is usually restricted to one of the four possibilities {+1, −1, +j, −j} so that no multiplication operation is required in the phase rotation. 
 
         [0007]     From  FIG. 2 , it can be seen that an N-point OFDM symbol requires M times of N-IFFT operation. That is, a total of M·(N/2)log 2  N complex multiplications are required. Several methods are further devised to reduce the amount of the computation required in the PTS method. Kang, Kim and Joo, in their article “A Novel Subblock Partition Scheme for Partial Transmit Sequence OFDM,” IEEE Trans. Broadcasting, vol. 45, no. 3, pp. 333-338, September 1999, disclosed a method of using the characteristics of the PTS interleaved partition of the subblocks, as shown in  FIG. 4  (M=8). Each subblock has N points in the frequency domain, but only L points of them have non-zero values (L=N/M). Therefore, the N-IFFT on the N-point subblock X m [k] is equivalent to the L-IFFT on the L-point subblock (where X m [k] has non-zero values), repeating M times in the time domain to form the N-point signal, and multiplying the N-point signal with the N-point complex coefficients: 
 
(1/M)·e j2πmn/N , m=0, 1, . . . , M−1, n=0, 1, . . . , N−1 
 
 This method takes M·(L/2)log 2  L+MN multiplications, and requires MN units of memory space. 
 
         [0008]     Samsung (U.S. Patent 2003/0,067,866) disclosed a similar method, as shown in  FIG. 5 . The Samsung method differs from the previous method in no repetition after the L-IFFT on an L-point subblock. Instead, the multiplication of the L-point complex coefficients in the time domain is performed to make the time domain subblocks orthogonal so that the receiving end can separate each subblock. As there are only L points in each time domain subblock, the PAPR is lower, therefore, the PAPR of the transmitted signal after the phase rotation and the addition is also lower. Although this method takes M·(L/2)log 2  L+N multiplications and requires N units of memory space, this method reduces the length of the OFDM signal from N to L, which means that the capability of anti-multipath channel effect is also greatly reduced. Furthermore, the L-point complex coefficient multiplier to make the time domain subblocks orthogonal is hard to design. This will further make the receiving end more difficult in obtaining the original transmitted data.  
       SUMMARY OF THE INVENTION  
       [0009]     The present invention has been made to overcome the aforementioned drawback of conventional PAPR reduction methods for the OFDM signal. The primary object of the present invention is to provide a PAPR reduction method and apparatus for the OFDM signal. The reduction method uses the characteristics of the interleaved partition of the subblocks of the PTS method. The discrete time sequence x[n] of length N is partitioned in the time domain into a number of disjoint subblocks, and a transformation combination and a phase optimization are performed on the subblocks to obtain a complete N-point signal {tilde over (x)}[n], where N is the length of an OFDM signal, and n=0, 1, . . . , N−1.  
         [0010]     The present invention only uses one N-IFFF so that the amount of computation is greatly reduced. The present invention takes (N/2)log 2  N complex multiplications and requires N units of memory space. But more important, the present invention keeps the original capability of anti-multipath channel effect in the OFDM system.  
         [0011]     The present invention includes the following steps: (1) partitioning the discrete time sequence x[n] of length N in the time domain into a number of disjoint subblocks, each subblock having the length of N/M, M being a power of 2, and N/M being an integer greater than 1; (2) using a combiner to combine the M disjoint subblocks into M different sequences y k [n], each having the length of N/M, where k=1, 2, . . . , M and n=0, 1, . . . , (N/M)−1; and (3) using the symmetric characteristics to phase rotate and add the M sequences y k [n] to obtain a complete N-point signal {tilde over (x)}[n] having the length of N.  
         [0012]     In the present invention, the first and the second embodiments, respectively, using M=2 and M=4, explain the steps of the time-domain method.  
         [0013]     The present invention of a PAPR reduction apparatus for an OFDM signal mainly comprises an N-IFFT, a de-multiplexer, a combiner, a set of memory, and an adder. The N-IFFT transforms the frequency-domain input signal X[k] into the time-domain signal x[n]. The de-multiplexer uses the adjacent partitioning to partition x[n] into M disjoint subblocks of identical length. The combiner combines the M disjoint subblocks into M discrete time sequences y k [n] of length N/M. Use the symmetric characteristics to phase rotate the M sequences y k [n] and use the adder to add them and obtain a complete N-point signal {tilde over (x)}[n]. The memory is for storing the M disjoint subblocks and the M sequences y k [n].  
         [0014]     When M=4, the present invention shows different results in terms of computation amount and the memory requirements, compared to other three PTS methods. Compared to the original PTS method and the method disclosed by Kang, Kim and Joo, the present invention and the Samsung method have the same minimum computation amount and memory requirement. The present invention does not require shortening the length of the OFDM signal, and therefore keeps the features and advantages of the OFDM system.  
         [0015]     The foregoing and other objects, features, aspects and advantages of the present invention will become better understood from a careful reading of a detailed description provided herein below with appropriate reference to the accompanying drawings. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0016]      FIG. 1  shows a schematic view of a conventional OFDM transmitter.  
         [0017]      FIG. 2  shows a PTS method to solve the high PAPR problem of OFDM signal at transmission end.  
         [0018]      FIG. 3  shows the three ways of partitioning the input data X[k] into subblocks.  
         [0019]      FIG. 4  shows the method proposed by Kang, Kim and Joo to reduce the computation amount of PTS.  
         [0020]      FIG. 5  shows the method proposed by Samsung to reduce the computation amount and memory requirement of PTS.  
         [0021]      FIG. 6  shows the PAPR reduction method of an OFDM signal according to the present invention.  
         [0022]      FIG. 7  shows the schematic view of the apparatus according to the present invention for PAPR reduction of an OFDM signal.  
         [0023]      FIG. 8  shows the first embodiment of the present invention in  FIG. 7 .  
         [0024]      FIG. 9  shows the phase rotation parameter setting in  FIG. 8  when M=2.  
         [0025]      FIG. 10  shows the second embodiment of the present invention in  FIG. 7 .  
         [0026]      FIG. 11  shows the phase rotation parameter setting in  FIG. 10  when M=4.  
         [0027]      FIG. 12  shows the comparison of the computation amount and the memory requirement between the present invention and the other three methods. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0028]      FIG. 6  shows a schematic view of the present invention of a PAPR reduction method for an OFDM signal. First, the N-IFFT operation  601  is performed on the frequency-domain signal X[k] of length N to obtain the time domain signal x[n] of length N. The adjacent partitioning is performed on x[n] to obtain M disjoint subblocks having the length N/M, where M is a power of 2 and N/M is an integer greater than 1, as in step  603 . In step  605 , the combiner is used to combine the M disjoint subblocks into M discrete-time sequences y 1 [n], y 2 [n], . . . , y M [n], each having the length N/M. Finally, in step  607 , the M discrete-time sequences y k [n] are phase rotated and added to form a complete N-point transmitted signal {tilde over (x)}[n]: 
   {tilde over (x)}[n]=b   1   y   1   [n]+b   2   y   2   [n]+ . . . +b   M   y   M   [n]   (6)  
 Because the sequences y k [n] are symmetrical, the combiner  605  only needs to form the sequences {y k [0], y k [1], . . . , y k [(N/M)−1]}, each having the length N/M. 
 
         [0029]     In accordance with the method described above,  FIG. 7  shows the schematic view of an apparatus for PAPR reduction for an OFDM signal. The apparatus comprises an N-IFFT  601 , a de-multiplexer  701 , a combiner  703 , a set of memory  705 , and an adder  707 . N-IFFT  601  transforms the frequency-domain input signal X[k] into the time-domain signal x[n]. De-multiplexer  701  partitions the signal x[n] into M adjacent, yet disjoint, subblocks of identical length. Combiner  703  combines the M disjoint subblocks into M sequences y k [n] of length N/M, where k=1, 2, . . . , M and n=0, 1, . . . , (N/M)−1. The M sequences y k [n], after the phase rotation, are added by the adder  707  to obtain a segment of the transmitted signal {{tilde over (x)}[0], {tilde over (x)}[1], . . . , {tilde over (x)}[(N/M)− 1]}, having the length N/M. By using different phase rotation parameter {tilde over (b)}   k , the next segment of the transmitted signal {{tilde over (x)}[N/M], {tilde over (x)}[(N/M)+1], . . . , {tilde over (x)}[(2N/M)−1]} can be obtained from the M sequences y k [n]. By repeating the process, the complete transmitted signal {tilde over (x)}[n] can be obtained. The M disjoint subblocks and the M sequences y k [n] are stored in the memory  705 .  
         [0030]     As shown in  FIG. 8 , when M=2, the sequence x[n], n=0, 1, . . . , N−1, is partitioned by de-multiplexer  701  into two subblocks {x[0], x[1], . . . , x[(N/2)−1]} and {x[N/2], x[(N/2)+1], . . . , x[N−1]}, each having the length N/2. Both subblocks are stored in memory  705 . Combiner  803  combines the two subblocks into the following two discrete time sequences, each having the length N: 
 
 y   1   [n]=x[n]+x[ (( n−N/ 2)) N ]
 
 y   2   [n]=x[n]−x[ (( n−N/ 2)) N ]  (7) 
 
 where ((•)) N  is the N-point circular shift, n=0, 1, . . . , N−1. Combiner  803  has a simple structure of two adders,  803   a  and  803   b , similar to that of 2-IFFT. It can be proved that the discrete-time sequences y 1 [n] and y 2 [n] obtained from equation (7) are identical to the discrete-time sequences x 1 [n] and x 2 [n] obtained by the original PTS in  FIG. 2 . From equation (7), the following equation can be obtained: 
 
 y   1 [(( n+N/ 2)) N   ]=y   1 [(( n−N/ 2)) N   ]=x [(( n−N/ 2)) N   ]+x[n]=y   1   [n] 
 
 y   2 [(( n+N/ 2)) N   ]=y   2 [(( n−N/ 2)) N   ]=x [(( n−N/ 2)) N   ]−x[n]=−y   2   [n]   (8) 
 
 In other words, 
 
 y   1   [N/ 2 ]=y   1 [1],  y   1   [N/ 2+1 ]=y   1 [1 ], . . . , y   1   [N− 1] y   1   [N/ 2−1]
 
 y   2   [N/ 2] =−y   2 [0 ], y   2   [N/ 2+1]=− y   2 [1 ], . . . , y   2   [N− 1] =−y   2   [N/ 2−1]  (9) 
 
 Therefore, combiner  803  only needs to form the sequences {y 1 [0], y 1 [1], . . . , y 1 [(N/2)−1]} and {y 2 [0], y 2 [1], . . . , y 2 [(N/2)−1]} of length N/2. Because the sequence {x[0], x[1], . . . , x[N−1]} is no longer needed, memory  705  can be released to store {y 1 [0], y 1 [1], . . . , y 1 [(N/2)−1]} and {y 2 [0], y 2 [1], . . . , y 2 [(N/2)−1]}. In other words, the memory requirement is N units. Finally, from equation (6) and equation (9), the following can be obtained: 
 
 {tilde over (x)}[n]=b   1   y   1   [n]+b   2   y   2   [n] 
 
 {tilde over (x)}[n+N/ 2 ]=b   1   y   1   [n]−b   2   y   2   [n]   (10) 
 
 where n=0, 1, . . . , (N/2)−1. Equation (10) can be further expressed as: 
 
 {tilde over (x)}[n+pN/ 2 ]={tilde over (b)}   1   y   1   [n]+{tilde over (b)}   2   y   2   [n], p= 0,1 n=0, 1, . . . ,  N/ 2−1  (11) 
 
 where phase rotation parameters {tilde over (b)} 1  and {tilde over (b)} 2  are as shown in  FIG. 9 .  FIG. 8  shows that when {tilde over (b)} k  is +1, −1, +j, or −j, the present invention takes (N/2)log 2  N complex multiplications, all from N-IFFT  601 , and requires N units of memory. When M=4, the schematic view is shown in  FIG. 10 . The sequence x[n], n=0, 1, . . . , N−1, is partitioned by de-multiplexer  701  into four subblocks {x[0], . . . , x[(N/4)−1]}, {x[N/4], . . . , x[(N/2)−1]}, {x[N/2], . . . , x[(3N/4)−1]} and {x[3N/4], . . . , x[N−1]}, each having the length N/4. Combiner  1003  combines the four subblocks into the following four discrete time sequences, each having the length N: 
 
 y   1   [n]=x[n]+x[ (( n−N/ 2)) N   ]+x [(( n−N/ 4)) N   ]+x [(( n− 3 N/ 4)) N ]
 
 y   3   [n]=x[n]+x[ ( (n−N/ 2)) N]   −x[ (( n−N/ 4)) N   ]−x [(( n− 3 N/ 4)) N ]
 
 y   2   [n]=x[n]−x[ (( n−N/ 2)) N   ]+jx [(( n−N/ 4)) N   ]−jx [(( n− 3 N/ 4)) N ]
 
 y   4   [n]=x[n]−x[ (( n−N/ 2)) N   ]−jx [(( n−N/ 4)) N   ]+jx [(( n− 3N/4)) N ]
 
 Combiner  1003  uses 8 adders and an imagery j multiplicator to implement equation (12). The structure is similar to that of 4-IFFT. It can be proved that the discrete-time sequences y 1 [n], y 2 [n], y 3 [n] and y 4 [n] obtained from equation (12) are identical to the discrete time sequences x 1 [n], x 2 [n], x 3 [n] and x 4 [n] obtained by the original PTS in  FIG. 2 . Similarly, by using the symmetric characteristic, the following equation can be obtained: 
 
 {tilde over (x)}[n+pN/ 4] ={tilde over (b)}   1   y   1   [n]+{tilde over (b)}   2   y   2   [n]+{tilde over (b)}   3   y   3   [n]+{tilde over (b)}   4   y   4   [n], p= 0, 1, 2, 3  (13) 
 
 where n=0, 1, . . . , (N/4)−1, and the phase rotation parameter {tilde over (b)} k  is as shown in  FIG. 11 .  FIG. 10  shows that when {tilde over (b)} k  is +1, −1, +j, or −j, the present invention takes (N/2)log2 N complex multiplications, and requires N units of memory. 
 
         [0031]      FIG. 12  shows the comparison of the amount of computation and the memory requirement of the present invention and the other three PTS methods, for M=4 and N=64, 256, 1024, and 2048. As can be seen from  FIG. 12 , the amount of computation and the memory requirement increases as N increases. Compared to the original PTS and the method disclosed by Kang, Kim and Joo, the present invention and the Samsung method takes the minimum number of multiplications and requires the minimum memory space. Both take the same number of multiplications, 192, 1024, 5120 and 11264, respectively; and both require the same amount of memory space, 64, 256, 1024, 2048 units of memory, respectively. However, the PTS method of the present invention does not shorten the length of the OFDM signal, and therefore keeps the features and the advantages of the original OFDM system.  
         [0032]     In summary, the present invention uses the interleaved characteristics of subblock partition of the PTS method, and uses only an N-IFFT to provide a method and an apparatus for PAPR reduction for an OFDM signal. The present invention only takes (N/2)log 2  N complex multiplications and requires only N units of memory space. Furthermore, the present invention keeps the features and the advantages of the original OFDM system.  
         [0033]     Although the present invention has been described with reference to the preferred embodiments, it will be understood that the invention is not limited to the details described thereof. Various substitutions and modifications have been suggested in the foregoing description, and others will occur to those of ordinary skill in the art. Therefore, all such substitutions and modifications are intended to be embraced within the scope of the invention as defined in the appended claims.