`Cimini, Jr. et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,556,557 B1
`Apr. 29, 2003
`
`USOO6556557B1
`
`(54) METHOD AND SYSTEM FOR REDUCING
`OF PEAK-TO-AVERAGE POWER RATO OF
`TRANSMISSION SIGNALS COMPRISING
`OVERLAPPING WAVEFORMS
`
`Primary Examiner Vivian Chin
`ASSistant Examiner John J Lee
`
`(57)
`
`ABSTRACT
`
`(75) Inventors: Leonard Joseph Cimini, Jr., Howell,
`NJ (US); Nelson Ray Sollenberger,
`Tinton Falls, NJ (US)
`(73) Assignee: AT&T Corp., New York, NY (US)
`(*) Notice:
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/324,487
`(22) Filed:
`Jun. 2, 1999
`(51) Int. Cl. ................................................ H04B 71216
`(52) U.S. Cl. ....................... 370/342; 370/208; 370/335;
`375/144; 375/148
`(58) Field of Search ................................. 375/260, 141,
`375/144, 148, 346, 146, 206, 211, 296,
`214, 345; 370/208, 252, 342, 320, 335,
`441, 203, 206
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`9/2000 Ziemer et al. .............. 375/142
`6,122,310 A
`6,128,350 A * 10/2000 Shastri et al...
`... 375/260
`6,222,873 B1 * 4/2001 Bang et al. .......
`... 370/206
`6,236.864 B1 * 5/2001 McGowan et al. ......... 375/296
`6,314,146 B1
`11/2001 Tellado et al. .............. 375/346
`* cited by examiner
`
`The present invention provides a method and System for
`reducing the peak to average power ratio (PAP) of a signal
`with low computational complexity. According to one
`embodiment, the present invention is applied to reduce the
`PAP of an OFDM signal. According to an alternative
`embodiment, the present invention is applied to reduce the
`PAP of a CDMA signal. Rather than seeking the optimum
`Solution, which involves Significant computational
`complexity, the present invention provides for a number of
`sub-optimal techniques for reducing the PAP of an OFDM
`Signal but with much lower computational complexity. In
`particular, according to one embodiment utilizing the PTS
`approach, an iterative technique is used to assign phase
`factors to each of a set of partial transmit Sequences from a
`Set of possible phase factors. Experimental results using the
`iterative technique showed only a slight degradation (1 dB)
`from the optimal approach using the same number of
`Subblocks and Subcarriers. In an alternative embodiment,
`which avoids feedback required by the iterative approach, a
`Sequence of phase factors are generated randomly and
`assigned to each of a set of partial transmit Sequences. This
`procedure is repeated for a pre-determined number of trials
`and the random Sequence generating the lowest PAP is
`Selected. In a third embodiment, a set of phase factorS is
`generated using a structured Sequence Such as a Walsh
`Sequence.
`
`25 Claims, 13 Drawing Sheets
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FOR SYMBOL INTERVAL u, GENERATE SET OF
`PARTIAL TRANSMIT SEQUENCES
`xi)
`ASSIGN PHASE FACTOR b TO EACH PARTIAL
`TRANSMIT SEQUENCE
`
`720
`
`730
`
`CACUATE AND STORE PAP OF LINEAR
`COMBINATION OF PARTIAL TRANSMIT SEQUENCES,
`EACH MULTIPLED BY ITS RESPECTIVE PHASE FACTOR
`
`- 740
`
`STAR FINAL ASSIGNMENT PROCESS FOR NEXT
`PARTIAL TRANSMIT SEQUENCE
`
`^ 745
`
`EMPORARLY STORE PREVIOUSLY ASSIGNED PHASE
`FACTOR, ASSIGN NEXT PHASE FACTOR AND
`CALCULATE PAP
`
`750
`
`CURRENT PAF KSTORED PAP
`
`ASSIGNTERPORARLY STORED PHASE FACTOR TO
`CURRENT PARTIAL TRANSMIT SEQUENCE
`
`ALL PHASE FACTORS CONSIDERED
`YES
`AL PARTIAL TRANSMIT SEQUENCES CONSIDERED?
`
`775
`
`780
`
`760
`S
`STORE CURRENT PAP
`
`
`
`VWGoA EX1022
`U.S. Patent No. 8,467,366
`
`
`
`U.S. Patent
`
`LOLA
`
`LayYOId
`
`Apr. 29, 2003
`
`Sheet 1 of 13
`
`I-Ny
`
`LeeLLeeee_J
`
`OLWId3S
`
`TAITWAVd
`
`
`N(OIadTOAWASHO¥2YO4
`
`
`STYNOISO3LINT-3AIL
`
`YALYSANO)
`
`
`
`(QNISSIO0%d49018)
`
` |II{I!!|I||||{{|(I{|II(IIIIII|0c|YILLINSNVYL
`
`US 6,556,557 B1
`
`REEme7
`
`
`
`
`
`I7
`
`GCOld
`
`Lay4Olud
`
`
`
`
`
`"xYIAIGOIY
`
`U.S. Patent
`U.S. Patent
`
`Apr. 29, 2003
`Apr. 29, 2003
`
`Sheet 2 of 13
`Sheet 2 of 13
`
`US 6,556,557 B1
`US 6,556,557 B1
`
`--------------------------------------
`
`TUTIVaVd
`
`WIMISOL
`
`YALYIANOD
`
`
`
`STYNOISGaLIAT-3NIL
`
`
`
`(QNISSI90%d40079)
`
`||{|||||i|||||I||I||I|||I||II||lltI
`
`
`
`
`
`U.S. Patent
`
`Apr. 29, 2003
`
`Sheet 3 of 13
`
`US 6,556,557 B1
`
`FIG. 3
`
`
`
`.5
`
`N-256 SUBCARRIERS
`QPSK
`
`Pr(PAP)PAP) 03
`
`.003
`
`.001
`
`
`
`
`
`
`
`______ " _________ (______HOWO, ?NIJ, JN10JES
`
`eN?|| * ?--------------------------º
`
`
`
`
`
`
`
`3||
`
`er)|NOISSIWSNW8|||
`|| || || ||
`
`
`
`
`|| || || |} ||
`
`
`US 6,556,557 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`Apr. 29, 2003
`
`Sheet 5 of 13
`
`US 6,556,557 B1
`
`OLIWI83S
`
`TIT
`
`NOISYIANOO
`
`NOILILYVdONY
`
`
`
`OINIYOLISA
`
`SHIOTENS
`
`oeHSE
`U.S. Patent
`09sOvass01s
`
`LYYOIddG“OLA
`
`WNOSviva
`
`ny
`
`
`
`HOVOUddY3ON3NDIS
`
`
`
`
`
`U.S. Patent
`U.S. Patent
`
`Apr. 29, 2003
`Apr. 29, 2003
`
`Sheet 6 of 13
`Sheet 6 of 13
`
`US 6,556,557 B1
`US 6,556,557 B1
`
`
`
`AYONAN|asa/ndd|
`YICNOdSNVUL
`
`q0¢lSe
`
`
`
`Y4M9038YALUIWSNVaL
`
`9D1
`
`orlGO|
`
`
`
`YIONOdSNVYLdSa/ndd
`
`AYOWIN
`
`
`
`
`
`U.S. Patent
`
`Apr. 29, 2003
`
`Sheet 7 of 13
`
`US 6,556,557 B1
`
`FIC. 7
`
`710
`
`FOR SYMBOL INTERVAL u, GENERATE SET OF
`PARTIAL TRANSMIT SEQUENCES
`
`x)
`ASSIGN PHASE FACTOR b TO EACH PARTIAL
`TRANSMIT SEQUENCE
`
`
`
`
`
`CALCULATE AND STORE PAP OF LINEAR
`COMBINATION OF PARTIAL TRANSMIT SEQUENCES,
`EACH MULTIPLIED BY ITS RESPECTIVE PHASE FACTOR
`
`START FINAL ASSIGNMENT PROCESS FOR NEXT
`PARTIAL TRANSMIT SEQUENCE
`
`TEMPORARILY STORE PREVIOUSLY ASSIGNED PHASE
`FACTOR, ASSIGN NEXT PHASE FACTOR AND
`CALCULATE PAP
`
`720
`
`730
`
`740
`
`745
`
`750
`
`760
`
`CURRENT PAP { STORED PAP2
`
`YES
`
`
`
`STORE CURRENT PAP
`
`ASSIGN TEMPORARILY STORED PHASE FACTOR TO
`CURRENT PARTIAL TRANSMIT SEQUENCE
`
`ALL PHASE FACTORS CONSIDERED?
`
`ALL PARTIAL TRANSMIT SEQUENCES CONSIDERED?
`YES
`
`END
`
`780
`
`770
`
`775
`
`
`
`
`
`
`
`
`
`
`
`U.S. Patent
`
`Apr. 29, 2003
`
`Sheet 8 of 13
`
`US 6,556,557 B1
`
`FIG. 8
`
`810
`
`FOR SYMBOL INTERVAL u, GENERATE SET OF
`PARTIAL TRANSMIT SEQUENCES
`
`x()
`
`CALCULATE AND STORE PAP OF LINEAR
`COMBINATION OF PARTIAL TRANSMIT SEQUENCES
`
`GENERATE RANDOM OR STRUCTURED SEQUENCE
`VECTOR r
`
`MULTIPLY EACH PARTIAL TRANSMIT SEQUENCE BY
`CORRESPONDING ENTRY IN r AND CALCULATE PAP
`OF COMBINED SET OF PARTIAL TRANSMIT SEQUENCES
`
`
`
`820
`
`830
`
`840
`
`850
`
`860
`
`PAP K STORED PAP
`
`YES
`
`STORE r AND
`CURRENT PAP
`
`
`
`
`
`
`
`
`
`
`
`ENOUGH RANDOM SEQUENCES CONSIDERED 2
`
`865
`
`YES
`
`END
`
`870
`
`
`
`U.S. Patent
`
`Apr. 29, 2003
`
`Sheet 9 of 13
`
`US 6,556,557 B1
`
`FIG. 9
`
`
`
`.5
`
`N-256 SUBCARRIERS
`QPSK
`BINARY PHASE FACTORS
`
`Pr (PAP)PAP) 03
`
`.01
`
`003
`
`.001
`
`M=16, N/M=16
`ITERATIVE
`
`M=16, N/M=16
`OPTIMUM
`
`
`
`U.S. Patent
`
`Apr. 29, 2003
`
`Sheet 10 Of 13
`
`US 6,556,557 B1
`
`FIC. 1 O
`
`
`
`.3
`
`.1
`
`N-256 SUBCARRIERS
`QPSK
`BINARY PHASE FACTORS
`
`Pr (PAP)PAP) 03
`
`O1
`
`003
`
`,001
`
`
`
`U.S. Patent
`
`Apr. 29, 2003
`
`Sheet 11 of 13
`
`US 6,556,557 B1
`
`FIG. 1 1
`
`
`
`3 - N=256 SUBCARRIERS
`
`Pr (PAP)PAP) 03
`
`QPSK -BINARY
`w
`FOUR-PHASE
`16-QAM ---BINARY
`
`003
`
`M16 SUBBLOCKS
`
`
`
`U.S. Patent
`
`Apr. 29, 2003
`
`Sheet 12 of 13
`
`US 6,556,557 B1
`
`FIG. 12
`
`
`
`3 - N=256 SUBCARRIERS
`QPSK
`BINARY PHASE FACTORS
`
`Pr (PAP)PAP) 03
`
`.01
`
`M-16 SUBBLOCKS
`
`-NO POWER CONTROL
`UNIFORM-10 dB, 0 dB
`---UNIFORM-20 dB, 0 dB
`
`
`
`U.S. Patent
`
`Apr. 29, 2003
`
`Sheet 13 of 13
`
`US 6,556,557 B1
`
`FIC. 13
`
`
`
`
`
`
`
`N-256 SUBCARRIERS
`QPSK
`BINARY PHASE FACTORS
`
`Pr (PAP)PAP) 03
`
`.01
`
`
`
`-ITERATIVE
`RANDOM
`
`12
`
`
`
`US 6,556,557 B1
`
`1
`METHOD AND SYSTEM FOR REDUCING
`OF PEAK-TO-AVERAGE POWER RATO OF
`TRANSMISSION SIGNALS COMPRISING
`OVERLAPPING WAVEFORMS
`
`FIELD OF THE INVENTION
`The present invention relates to communication networkS.
`In particular the present invention relates to a method and
`System for reducing the peak to average power ratio of
`wireleSS Signals.
`
`2
`are used, Specifically those with low peak powerS. See A. E.
`Jones, T. A. Wilkinson, and S. K. Barton, “Block Coding
`Scheme for Reduction of Peak to Mean Envelope Power
`Ratio of Multicarrier Transmission Scheme.” Electron.
`Letts., Vol. 30, No. 25, December 1994, pp. 2098-2099.
`Using this nonlinear block coding approach, a 3-dB PAP can
`be achieved with only a small bandwidth penalty. However,
`the drawback of nonlinear block coding is that it requires
`large look-up tables at both the transmitter and receiver,
`limiting its usefulness to applications with only a Small
`number of Subchannels. There has been progreSS in devel
`oping coding Schemes that reduce the PAP, can be imple
`mented in Systematic form, and have Some error correcting
`capabilities. See A. E. Jones and T. A. Wilkinson, “Com
`bined Coding for Error Control and Increased Robustness to
`System Nonlinearities in OFDM,” Proc. of VTC96, pp.
`904-908. Nevertheless, these coding methods are difficult to
`extend to Systems with more than a few Subchannels and the
`coding gains are Small for reasonable levels of redundancy.
`Two promising techniques for improving the Statistics of
`the PAP of an OFDM signal have been proposed. These
`techniques have been termed the Selective mapping (SLM)
`approach and the partial transmit Sequence (PTS) approach.
`In Selective mapping, M Statistically independent
`Sequences are generated from the same information and that
`sequence with the lowest PAP is chosen for transmission. To
`recover the data, the receiver must "know' which Sequence
`has been used to “multiply” the data; this can be transmitted
`as Side information.
`In the PTS approach, each input data block consisting of
`a set of Subcarrier coefficients is partitioned into disjoint
`Subblocks, which are then combined to minimize the PAP.
`Specifically, each Subcarrier coefficient is multiplied by a
`weighting coefficient, or phase factor. The phase factors are
`chosen to minimize the PAP of the transmitted signal.
`Although both the Selective mapping approach and the
`partial transmit Sequence approach are useful for improving
`the statistics of the PAP of an OFDM signal, both introduce
`additional implementation complexity. In particular the
`SLM approach requires the use of M full-length (i.e.,
`N-point) IFFTs (Inverse Fast Fourier Transforms) at the
`transmitter. The PTS approach requires a similar number of
`IFFT's and in addition introduces additional complexity due
`to the requirement of optimizing the assignment of phase
`factors to each partial transmit Sequence. This computational
`complexity imposes limitations on battery life, particularly
`in the terminal unit. Thus, there is a need for a method to
`reduce the PAP of a signal that can be performed with low
`computational complexity.
`Code Division Multiple Access (CDMA) is another very
`attractive technique for overcoming the bit rate limitations
`of the multipath channel. In addition, one of the approaches
`for achieving higher (as well as variable) bit rates consists of
`individual terminals transmitting multiple CDMA codes
`(multi-code CDMA). In both basic CDMA and multi-code
`CDMA, a similar PAP problem exists and a method for
`reducing the PAP of such a signal is desirable.
`SUMMARY OF THE INVENTION
`The present invention provides a method and System for
`reducing the PAP of a signal with low complexity compared
`to existing techniques. According to one embodiment, the
`present invention is applied to reduce the PAP of an OFDM
`Signal. In an alternative embodiment, the present invention
`is applied to reduce the PAP of a CDMA signal. Rather than
`Seeking the optimum Solution, which involves significant
`
`15
`
`25
`
`BACKGROUND INFORMATION
`It is predicted that the 21st century will witness the
`widespread deployment of wireless networks that will revo
`lutionize the concept of communication and information
`processing for business, professional and private applica
`tions. However, bandwidth scarcity and a hostile radio
`environment are among the two most significant technical
`hurdles for developing the next generation of wireleSS
`information Systems. The latter issue is especially problem
`atic in developing broadband wireleSS networkS.
`In particular, multipath delay spread resulting in interSym
`bol interference imposes an absolute limit on the bandwidth
`of a wireleSS channel. Orthogonal frequency division mul
`tiplexing (OFDM) is a very attractive technique for achiev
`ing high-bit-rate transmission in a radio environment. By
`dividing the total bandwidth into many narrow Subchannels,
`each carrying a lower bit rate, which are transmitted in
`parallel, the effects of multipath delay spread can be mini
`mized. Thus, the problem of intersymbol interference can be
`solved by increasing the symbol duration in the same ratio
`as the number of Subchannels. This approach has been
`proposed or adopted for many wireleSS applications includ
`ing digital audio broadcasting, digital terrestrial television
`broadcasting, wireleSS LANs and high-Speed cellular data.
`Techniques for implementing OFDM are well known.
`However, a significant disadvantage of employing OFDM
`40
`for wireleSS applications is the potentially large peak-to
`average power ratio (PAP) characteristic of a multicarrier
`Signal with a large number of Subchannels. In particular, a
`baseband OFDM signal with N subchannels has a PAP of
`N°/N=N, for N=256, PAP=24 dB. When passed through a
`nonlinear device, Such as a transmit power amplifier, the
`Signal may Suffer significant spectral spreading and in-band
`distortion. With the increased interest in OFDM for wireless
`applications, reducing the PAP is a necessity for implement
`ing OFDM.
`For wireleSS applications, efficient power amplification is
`required to provide adequate area coverage and to minimize
`battery consumption. The conventional solution to the PAP
`problem in OFDM systems is to use a linear amplifier that
`is operated with large backoff from its peak power limit.
`However, this approach results in a significant power pen
`alty.
`Several alternative Solutions have been proposed to
`reduce the PAP For example, one simple solution is to
`deliberately clip the OFDM signal before amplification,
`which provides a good PAP but at the expense of perfor
`mance degradation. See R. O'Neill and L. N. Lopes, “Enve
`lope Variations and Spectral Splatter in Clipped Multicarrier
`Signals.” Proc. of PIMRC 99, pp. 71–75.
`Another known conventional Solution is nonlinear block
`coding, where the desired data Sequence is embedded in a
`larger Sequence and only a Subset of all possible Sequences
`
`35
`
`45
`
`50
`
`55
`
`60
`
`65
`
`
`
`US 6,556,557 B1
`
`3
`computational complexity, the present invention provides
`for a number of sub-optimal techniques for reducing the PAP
`of an OFDM signal but with much lower computational
`complexity. In particular, according to one embodiment
`utilizing the PTS approach, an iterative technique is used to
`assign phase factors to each of a set of partial transmit
`Sequences from a set of possible phase factors. Experimental
`results using the iterative technique showed only a slight
`degradation (1 dB) from the optimal approach using the
`Same number of SubblockS and Subcarriers. In an alternative
`embodiment, which avoids feedback required by the itera
`tive approach, a Sequence of phase factors are generated
`randomly and assigned to each of a set of partial transmit
`Sequences. This procedure is repeated for a pre-determined
`number of trials and the random Sequence generating the
`lowest PAP is selected. In a third embodiment, a set of phase
`factorS is generated using a Structured Sequence Such as a
`Walsh Sequence.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1, which is prior art, is a block diagram that depicts
`an implementation of OFDM at a wireless transmitter.
`FIG. 2, which is prior art, is a block diagram that depicts
`an implementation of OFDM at a wireless receiver.
`FIG. 3 is a graph showing the complementary cumulative
`distribution function (CCDF=PR(PAP-PAP) of the PAP of
`a continuous-time, analog, OFDM Signal for the particular
`case of 256 Subcarriers.
`FIG. 4, which is prior art, is a block diagram depicting the
`SLM approach for reducing the PAP of an OFDM signal.
`FIG. 5, which is prior art, is a block diagram depicting the
`PTS approach for reducing the PAP of an OFDM signal.
`FIG. 6 is a block diagram depicting a wireleSS network
`architecture according to one embodiment of the present
`invention.
`FIG. 7 is a flowchart depicting the steps of an iterative
`algorithm utilizing partial transmit Sequences for reducing
`the PAP of an OFDM signal.
`FIG. 8 is a flowchart depicting the steps of an algorithm
`for reducing the PAP of an OFDM signal using randomly
`generated Sequences of phase factors or Structured
`Sequences according to one embodiment of the present
`invention.
`FIG. 9 shows a comparison of CCDF plots utilizing the
`iterative approach of the present invention and the optimum
`approach.
`FIG. 10 shows a comparison of CCDF plots for the
`iterative technique demonstrating the effect of varying the
`number of Subblocks.
`FIG. 11 shows a comparison of CCDF plots for the
`iterative technique demonstrating the effect of four-phase
`weighting factors and 16 QAM Signal constellations.
`FIG. 12 shows a comparison of CCDF plots for the
`iterative technique demonstrating the effects of the use of
`power control.
`FIG. 13 shows a comparison of CCDF plots for the
`iterative technique and the use of random Sequences.
`DETAILED DESCRIPTION
`The techniques for performing OFDM transmission are
`well known. In OFDM transmission, a block of N symbols
`{X, n=0, 1, .
`.
`. N-1} is formed with each symbol
`modulating one of a set of N Subcarriers {f, n=0, 1, . . .
`N-1}. The N Subcarriers are chosen to be orthogonal, i.e.,
`
`4
`f=nAf, where the Subcarrier spacing Af=1/NT and where T
`is the original data Symbol period. The original signal after
`digital-to-analog conversion can be expressed as:
`
`(1)
`
`An important advantage of OFDM is that, in Sampled form
`equation (1) can be implemented using an Inverse Fast
`Fourier Transform (IFFT).
`FIG. 1, which is prior art, is a block diagram that depicts
`an implementation of OFDM at a wireless transmitter. A
`block of transmission data (corresponding to a particular
`Symbol interval u) is digitally modulated in modulation
`block 110 using an appropriate modulation Scheme Such as
`quadrature amplitude modulation (QAM). A data vector
`output from modulation block 110a d={do. . . . , dy
`is then mapped onto f carriers (140a, 140b, etc.) via a serial
`to parallel converter block 120 to form a modulated Subcar
`rier carrier vector X = X0, . . . , Xu,w}. The Subcarrier
`vector X comprising all carrier amplitudes associated with
`OFDM symbol interval u is transformed into the time
`domain, using an N-point IDFT (Inverse Discrete Fourier
`Transform) (150) or IFFT producing time domain vector X.
`After digital to analog conversion (in D/A converter block
`155), the continuous time signal x(t) (157) is transmitted
`over a wireless channel via RF block 160a.
`FIG. 2, which is prior art, is a block diagram that depicts
`an implementation of OFDM at a wireless receiver. A
`continuous time signal x(t) (157) is received via RF block
`160b. The analog Signal is converted to a digital Signal via
`A/D converter 220 producing time domain vector X. The
`time domain vector X, is transformed to the frequency
`domain using an N-point DFT (Discrete Fourier Transform)
`(230) or FFT (Fast Fourier Transform), producing Subcarrier
`vector Xu. After parallel to serial conversion in block 235,
`the signal is demodulated in QAM block 110b and the
`transmitted data recovered.
`FIG. 3 is a graph showing the complementary cumulative
`distribution function (CCDF=PR(PAP-PAP)) of the PAP of
`continuous-time, analog, OFDM Signal for the particular
`case of 256 subcarriers. The PAP of a transmitted signal is
`defined as:
`
`(2)
`
`To more accurately approximate the true PAP, the results of
`FIG. 3 were computed by oversampling (1) by a factor of
`four (e.g., by Zero-padding the data input to the IFFT).
`FIG.4, which is prior art, is a block diagram depicting the
`SLM approach for reducing the PAP of an OFDM signal.
`Subcarrier vector X multiplied by M random Sequences
`r-r (420). Each multiplied vector is transformed to a time
`domain vector using an IFFT (430).
`The PAP of each time domain vector X, -X, is calcu
`lated and the sequence with the lowest PAP is selected for
`transmission (440).
`FIG. 5, which is prior art, is a block diagram depicting the
`PTS approach for reducing the PAP of an OFDM signal.
`Subcarrier vector X, is partitioned in M Subblocks (510).
`Each of the M Subblocks is transformed to a partial transmit
`sequence X1, ..., X, using an IFFT (530). A peak value
`optimization is then performed on the Set of partial transmit
`Sequences by appropriately assigning to each partial transmit
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`
`
`US 6,556,557 B1
`
`S
`Sequence an appropriate phase factor b So that the PAP of the
`combined set of partial transmit Sequences, each multiplied
`by its assigned phase factor 540, is minimized (550). The set
`of optimized phase factors is obtained by:
`
`argmin
`(E. E.
`
`i
`
`(n)
`b.
`
`EasX, |bC. v.C.
`3X
`n=1
`
`(3)
`
`15
`
`25
`
`The partial transmit Sequences, each multiplied by its
`assigned phase factor, are linearly combined 560 and trans
`mitted.
`In order to reconstruct the Signal at the receiver, the
`receiver must have knowledge regarding the generation
`process of the transmitted OFDM signal (i.e., the chosen set
`of phase factors). The phase factors, therefore, are transmit
`ted as Side information resulting in Some loSS of efficiency.
`Alternatively, differential encoding can be employed acroSS
`the Subcarriers within a Subblock; in this case, the overhead
`is a Single Subcarrier per Subblock. Using 128 Subcarriers
`with four Subblocks and phase factors limited to the set {t1,
`+j}, the 1% PAP can be reduced by more than 3 dB.
`While the SLM and PTS approaches provide significantly
`improved PAP statistics for an OFDM transmit signal with
`little cost in efficiency, a significant issue in implementing
`these approaches is reducing the computational complexity.
`In particular, the SLM approach requires the use of M
`full-length (i.e., N-point) IFFTs at the transmitter. While the
`PTS approach requires a similar number of N-point IFFTs
`(one IFFT for each partial transmit sequence), computation
`complexity in computing these IFFTS is reduced by taking
`advantage of the fact that a large fraction of the input values
`are Zero (in particular, only N/M values are non-zero).
`Nevertheless, in the PTS approach, an optimization is
`required at the transmitter in order to determine the best
`combination of the partial transmit Sequences. In its most
`direct form, this process requires the PAP to be computed at
`every Step of the optimization algorithm, necessitating
`numerous trials to achieve the optimum. It is known from C.
`Tellambura, “Phase Optimisation Criterion for Reducing
`Peak-to-Average Power Ratio in OFDM,” Electron. Letts.,
`Vol. 34, No. 2, January 1998, pp. 169-170, that using an
`alternative performance criterion, leSS computations are
`necessary for each trial of the optimization algorithm.
`FIG. 6 is a block diagram depicting a wireleSS network
`architecture Specifically adapted to reduce the PAP of Signals
`transmitted through the network according to one embodi
`ment of the present invention. The network depicted in FIG.
`6 may be specifically adapted for the transmission of OFDM
`signals. In particular, transmitter 105 contains CPU/DSP
`50
`110a, which is Specifically adapted either through specific
`hardware design or Software components to perform opera
`tions upon digital (discrete time) Signals to be transmitted
`through the wireless network. CPU/DSP 110a may also be
`an ASIC (Application Specific Integrated Circuit Device)
`specifically adapted to perform OFDM as well as other
`operations to reduce the PAP of an OFDM signal.
`CPU/DSP 110a communicates with memory 120a in
`order to Store data and program instructions. For example,
`CPU/DSP 110a may communicate with memory 120a to
`temporarily store intermediate results of DSP operations on
`Signals to be transmitted through the wireleSS network.
`Transmitter 105 also contains digital to analog converter 115
`for conversion of digital Signals for wireleSS transmission to
`receiver via transponder 130a and antenna 140a.
`Receiver 145 receives wireless signals via antenna 140b
`and transponder 130b. Analog Signals received at receiver
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`6
`145 are converted to digital format via analog to digital
`converter 155. Receiver 145 contains CPU/DSP 110b and
`memory 120b for performing operations on received digital
`Signals. In particular, according to one embodiment, CPU/
`DSP 110b is specifically adapted to perform demultiplexing
`of OFDM signals as well as other operations to reconstruct
`the original signals sent by transmitter 105.
`In the PTS approach, a major portion of the computational
`complexity originates from the need to optimize the phase
`factors used for combining the Subblocks. FIG. 7 is a
`flowchart depicting the Steps of a Sub-optimal iterative
`process for reducing the PAP of an OFDM signal. The
`procedure is initiated in step 710. In step 720 a set of partial
`transmit Sequences are generated for a particular Signal
`interval u. For example, this may be accomplished by
`Segmenting a Subcarrier vector X, into M Subblocks. Then
`an IFFT is performed on each Subblock to produce each
`partial transmit Sequence. In Step 730 an initial phase factor
`b, from a set of possible phase factors is assigned to each
`partial transmit sequence. In step 740 the PAP value of a
`linear combination of the partial transmit Sequences, each
`multiplied by its respective phase factor, is calculated and
`stored in memory 120a.
`In Step 745 each partial transmit Sequence is analyzed and
`assigned a final phase factor according to steps 750-765. In
`particular, in Step 750 the current phase factor assigned to
`the partial transmit Sequence under consideration is Stored in
`memory. Then a phase factor from the Set of possible phase
`factors is assigned to the current partial transmit. The PAP
`value of the linear combination of the partial transmit
`Sequences each multiplied by its respective phase factor is
`then calculated. In step 755, this calculated PAP value is
`compared with the PAP value stored in memory. If the
`calculated PAP value is lower than the PAP value stored in
`memory (yes' branch of step 755), the current PAP value is
`Stored (step 760) and the partial transmit sequence under
`consideration retains the assigned phase factor. Otherwise, if
`the current PAP value is greater than the stored PAP value
`(no branch of step 755), the temporarily stored phase factor
`from step 750 is re-assigned to the current partial transmit
`sequence (step 765). In step 770, it is determined whether all
`phase factors from the Set of possible phase factors have
`been examined for the current partial transmit Sequence. If
`not, (no branch of step 770), step 750 is executed again. If
`all phase factors have been examined (yes' branch of Step
`770), in step 775 it is determined whether all partial transmit
`Sequences have been examined and assigned a final phase
`factor. If not ('no' branch of step 775), step 745 is executed
`again. If all partial transmit Sequences have been examined
`and assigned a final phase factor, the procedure ends (Step
`780).
`The following pseudo-code defines an embodiment of the
`present invention:
`
`Steps:
`#define SIZE OF PARTIAL TRANSMIT SEOUENCE 5
`#define NUMBER OF PHASE FACTORS 2
`int phase factors2= {-1, 1};
`int best PAP:
`Struct PTS
`
`intSIZE OF PARTIAL TRANSMIT SEQUENCE:
`int phase factor;
`
`assign initial phase factor to each partial transmit sequence;
`
`
`
`US 6,556,557 B1
`
`7
`
`-continued
`
`best PAP=PAP of combined set of partial transmit sequences each
`multiplied by its corresponding phase factor;
`for each partial transmit sequence do:
`for (i=0;i&=NUMBER OF PHASE FACTORS-1; i++)
`temp phase factor=partial transmit sequence.phase factor;
`partial transmit sequence.phase factor=phase factorsi;
`current PAP=PAP of combined set of partial transmit sequences
`each multiplied by its corresponding phase factor;
`if current PAP&best PAP
`best PAP=current PAP:
`else
`partial transmit sequence.phase factor=temp phase factor;
`
`1O
`
`15
`
`According to one embodiment of the present invention,
`the Set of possible phase factors can take on only binary
`values from the set {1, -1}. Using this example, after
`dividing the input data block into M Subblocks, MN-point
`PTSs are generated using an IFFT. Each partial transmit
`Sequence is assigned the same phase factor, (i.e., b=1 for all
`m). The PAP of the combined signal is then computed. The
`first phase factor b is then inverted and the PAP is then
`recomputed. If the new PAP is lower than in the previous
`Step, b is retained as part of the final phase Sequence.
`Otherwise b is reassigned its previous value. This proce
`dure continues in a Sequential fashion until all of the M
`possibilities for “flipping the Signs of the phase factors have
`been explored.
`Results of the Sub-optimal iterative approach (as dis
`cussed below) show a significant improvement in the PAP of
`an OFDM signal with only a small degradation compared to
`the optimum. Nevertheless, the iterative approach requires
`Some feedback for implementation. An alternative approach,
`which avoids feedback, is to approximate the optimum by
`Simply multiplying the desired information Sequence by a
`number of random Sequences and choosing the best to
`transmit.
`FIG. 8 is a flowchart depicting the steps of a sub-optimal
`technique using random Sequences of random phase factors
`for reducing the PAP of an OFDM signal according to one
`embodiment of the present invention. In step 810 the pro
`cedure is initiated. In step 820, for the symbol interval u, a
`Set of partial transmit sequences is generated (i.e., See
`discussion of step 720 in FIG. 7). In step 830 a PAP value
`of a linear combination of the partial transmit Sequences is
`calculated and stored in memory 120a. In step 840, a vector
`of random phase factors r is generated. In step 850, the PAP
`value of the combined partial transmit Sequences each
`multiplied by a corresponding phase factor in r is calculated.
`If the PAP value using the current vector r is lower than the
`stored PAP value ('yes' branch of step 855), the vector rand
`the current PAP value are stored (step 860). Otherwise (no
`branch of step 855), it is determined whether a sufficient
`number of random sequences have been considered (i.e., the
`number of random Sequences is user determined). If a
`pre-determined number of Sequences have not been consid
`ered (no branch of step 865), step 840 is executed again
`and another random vector is ho generated. Otherwise, the
`procedure ends in step 870 and the currently stored vector r
`is used for transmission.
`According to simulation results (discussed in more detail
`below), it was found that 16 random trials produced Statis
`tically the same results as the iterative approach described
`above. Based upon this observation, according to an alter
`native embodiment of the present invention, a known set of
`Sequences, which are easily generated, were used instead of
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`random Sequences. According to one embodiment, for
`example, Walsh Sequences were used. Walsh functions
`reduce the number of required additions by a large factor if
`partial sums are stored. This is similar to the way a FFT
`reduces the computations required for a DFT. Using Struc
`tured Sequences Such as Walsh Sequences resulted in deg
`radation of only 0.3 dB. Similar results can be obtained with
`other well-known Sequences Such as the Shapiro-Rudin
`Sequences.
`
`Simulation Parameters
`The PAP is associated with the continuous-time OFDM
`transmit Signal. Many experimental results compute the PAP
`based on T or Symbol-sampled data in which case overly
`optimistic results are produced due to missing peaks in the
`Signal. Simulations, with regard to the present invention,
`were conducted in which the transmitted symbol was over
`sampled by a factor of four. Simulations showed that this
`OverSampling was Sufficient to capture Signal peaks. In the
`results, described below, 100000 random OFDM blocks
`were generated to obtain CCDF plots. 256 Subcarriers were
`used as were QPSK data symbols.
`Simulation Results
`FIG. 9 shows a comparison of CCDF plots utilizing the
`iterative approach of the present invention and the optimum
`approach for the case of a single OFDM block and 16
`Subblocks ea