(12) United States Patent
`Tellado et at.
`
`1111111111111111111111111 IIIIIIIIIIIIIIIIIIIIIII~~ 111111111111111
`USOO6424681Bl
`US 6,424,681 BI
`Jul. 23, 2002
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54) PEAK TO AVERAGE POWER RATIO
`REDUCTION
`
`(75)
`
`Inventors: Jose Tellado, Mountain View; John M.
`Ciofti, Cupertino, both of CA (US)
`
`(73) Assignee: The Board of Trustees of the Leland
`Stanford Junior University, Palo Alto,
`CA(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/062,867
`
`(22) Filed:
`
`Apr. 20, 1998
`Int. CU ................................................ H04L 25/03
`
`(51)
`
`(52) U.S. CI. ....................... 375/296; 375(295; 375/297;
`375/298; 375/316
`
`(58) Field of Search ................................. 375/296, 297,
`375/298, 295, 316; 330/129
`
`(56)
`
`References Gted
`
`U.S. PATENT DOCUMENTS
`
`5,268,938 A
`5,282,222 A
`5,285,474 A
`5,302,914 A
`5,598,436 A
`5,621,762 A
`5,835,536 A
`5,838,732 A
`6,125,103 A
`6,130,918 A
`6,175,551 B1
`
`12/1993 Feig et al.
`1/1994 Fattouche et al.
`2/1994 Chow et aI.
`• 4/1994 Arntz et al ................. 330/129
`1/1997 Brajal et aI.
`• 4/1997 Miller et al. ................ 375{298
`• 11/1998 May et al. .................. 375/316
`• 11/1998 Carney ....................... 375{297
`9/2000 Biiuml et al. ............... 370{203
`• 10/2000 Humphrey et aI.
`. ........ 375{295
`1{2001 Awater et al.
`.............. 370{21O
`
`21O(0)·(N-1 }
`
`/
`
`Xo
`
`QAM
`
`QAM
`
`QAM
`
`QAM
`
`QAM
`
`FOREIGN PATENT DOCUMENTS
`
`wo
`WO
`
`WO 95/17049
`WO 98/10567
`
`6/1995
`• 3/1998
`
`........... H04U27/26
`
`OTIlER PUBLICATIONS
`
`Muller et aI., A Comparison of Peak: Power Reduction
`Schemes for OFDM, 1997, IEEE, Globecom '97, vol. 1, pp.
`1-5.*
`Mathias Friese, "OFDM Signals with Low Crest-Factor",
`Nov. 1997, Globecom, pp. 290-294.
`
`(List continued on next page.)
`
`Primary Examiner-Stephen Chin
`Assistant Examiner-Shuwang Liu
`(74) Arrorney, Agent, or Firm-Beyer Weaver & Thomas
`LLP
`(57)
`
`ABSTRACT
`
`The present inventions provide methods and systems for
`reducing the peak: to average power ratio of a multi-carrier
`signal. Reducing the peak: to average power ratio of a signal
`ensures that amplifiers and transmitters are not saturated,
`causing loss of data. Further, reducing peak: to average
`power ratios reduces the consumption of power during
`transmission. Peak: to average power ratios are reduced by
`selecting a subset of a plurality of frequencies that make up
`a multi-carrier symbol. Peak reduction signals, carried at the
`subsetof frequencies, are computed to reduce the PAR of the
`symbol. In one embodiment, a kernel is generated that has
`components in the subset of frequencies. The kernel is
`adjusted to negate one or more peaks in the multi-carrier
`symboL The adjustment of the kernel creates a subset of
`signals of a plurality of signals centered at the plurality of
`frequencies. Negation of the peaks may be performed itera(cid:173)
`tively to remove any peaks produced during prior peak:
`reduction operations.
`
`40 Claims, 13 Drawing Sheets
`
`x
`
`x(n)
`
`Kernel
`Engine
`
`222
`
`204
`
`206
`
`EXHIBIT
`:r-e \ lClclt'l
`20l?..
`
`TQ Delta Exhibit 2012
`Cisco Systems, Inc. v. TQ Delta LLC
`IPR2016-01021
`
`1
`
`

`

`US 6,424,681 Bl
`Page 2
`
`ornER PUBLICATIONS
`
`Stefan Miller, et aI., "A Comparison of Peak Power Reduc(cid:173)
`tion Schemes for OFDM", Nov. 1997, Globecom, pp. 1-5.
`Alan Gatherer et al., "Controlling Oipping Probability in
`DMT Transmission", Nov. 1997, Askomar, pp. 578-584.
`Jacky S. Chow et al., "Mitigating Clipping Noise in Multi(cid:173)
`Carrier Systems", Jun. 1997, ICC, pp. 715-719.
`S.H. Miiller et aI., "OFDM with Reduced Peak-to-Average
`Power Ratio by Optimum Combination of Partial Transmit
`Sequences", Feb. 27, 1997, Electronics Letters, vol. 33, No.
`5, pp. 368-369.
`M. Friese, "Multicarrier Modulation with Low Peak-ta-Av(cid:173)
`erage Power Ratio", Apr. 11,1996, Electronics Letters, vol.
`32, No.8, pp. 713-714.
`
`Denis J.G. Mestdagh, "A Method to Reduce the Probability
`of Oipping in DMT-Based Transceivers", Oct. 1996, IEEE
`Transactions on Communications, vol. 44, No. 10, pp.
`1234-1238.
`
`D. Wulich, "Reduction of Peak to Mean Ratio of Multicar(cid:173)
`rier Modulation Using Cyclic Coding", Feb. 29, 1996,
`Electronics Letters, vol. 32, No.5, pp. 432-433.
`
`AE. Jones et al., "Blockcoding Scheme for Reduction of
`Peak to Mean Envelope Power Ratio of Multicarrier Trans(cid:173)
`mission Schemes", Dec. 8, 1994, vol. 30, No. 25, pp.
`2098-2099.
`
`.. cited by examiner
`
`2
`
`

`

`"""'"
`"""'" 0=
`~ (:,.,
`~ rn
`
`Q'\
`
`QC
`
`~
`I-'
`
`Q .....
`~ ....
`~
`::r'
`r.n
`
`I-'
`
`N = = N
`~ c: :-
`
`~~
`N
`
`Fig. 1
`
`frequency (f)
`
`fn
`
`• • •
`
`fa
`I I
`
`f7
`I \
`
`f6
`I \
`
`fs
`I I
`
`\
`
`f4
`I
`
`\
`
`f3
`I
`
`f2
`I \
`
`f1
`I
`
`/
`10(n)
`
`/
`10(8)
`
`/
`10(7)
`
`/
`10(5) 10(6)
`
`/
`
`/
`10(3) 10(4)
`
`/
`
`/
`10(1 ) 10(2)
`
`/
`
`Amplitude
`
`~ = ~
`o .
`
`•
`00
`
`== ~
`
`('t)
`
`3
`
`

`

`u.s. Patent
`
`US. Patent
`
`J ul. 23, 2002
`Jul. 23, 2002
`
`Sheet 2 of 13
`Sheet 2 of 13
`
`US 6,424,681 Bl
`US 6,424,681 B1
`
`CD
`
`E -
`
`Fig.2
`
`C\J
`
`0> u::
`
`o
`
`Amplitude (dB)
`
`o
`
`T'"""
`I
`
`4
`
`

`

`""""
`"""" c=
`
`QO
`Q\
`~,f;..
`N
`1:..
`Q\
`e r:n
`
`"""
`,...
`c
`~
`~ ....
`00 =-~
`
`~
`
`N g
`
`N
`
`;...; = :-
`
`~~
`N
`
`120(N-1 )
`
`frequency (f)
`
`fN-1
`
`120(6) 120(7)
`
`110(5)
`\
`
`110(2)
`I
`
`120(3)
`
`120(0) 120(1)
`
`f7
`
`f6
`
`15
`
`f4
`
`f3
`
`f2
`
`f1
`
`fa
`
`110(4)
`I
`
`Fig. 3
`
`I
`100
`
`• • •
`
`120(4) 120(5)
`
`120(2)
`
`I
`11 O(N-1)
`
`I
`110(7)
`
`I
`110(6)
`
`I
`110(3)
`
`I
`11 O( 1)
`
`I
`110(0)
`
`Amplitude
`
`rtI = f"'I"
`
`f"'I"
`~
`~
`•
`rJJ.
`
`Cj .
`
`5
`
`

`

`u.s. Patent
`
`US. Patent
`
`J ul. 23, 2002
`Jul. 23,2002
`
`Sheet 4 of 13
`Sheet 4 of 13
`
`US 6,424,681 Bl
`US 6,424,681 B1
`
`----.
`
`~
`
`0
`
`•
`
`~
`
`(t') ---0
`~ ~)r
`T"'" •
`
`FIG.4
`
`.
`CJ
`u.
`
`•
`
`•
`
`o
`o
`
`6
`
`

`

`u.s. Patent
`
`US. Patent
`
`Jul. 23, 2002
`Jui. 23, 2002
`
`Sheet 5 0f 13
`Sheet 5 of 13
`
`US 6,424,681 B1
`Us 6,424,681 B1
`
`8>
`
`.
`>. o
`c
`0>
`-
`::l
`a)L.._
`0-
`0>
`......
`'(cid:173)
`
`oCa
`
`)3o
`
`.-
`Z
`......
`
`I
`
`C\I . z
`
`......
`
`<'"l Z
`;><
`
`C')
`
`Z
`......
`
`Fig.5
`
`-I Z
`><
`
`0'1
`;><
`
`<'"l
`
`><
`
`LO
`
`OJ u:::
`
`•
`•
`•
`
`a .-
`.....
`
`.....
`en
`
`......
`CD
`
`......
`I"-
`
`~
`
`(Q
`
`......
`
`~
`
`~t
`
`t-
`
`II)
`
`......
`
`......
`V
`
`C')
`
`......
`
`......
`C\I
`
`.-
`......
`~
`a
`......
`
`a -><
`
`00
`
`><
`
`"<t ><
`
`N
`;><
`
`a
`;><
`
`Amplitude
`
`7
`
`

`

`u.s. Patent
`
`US. Patent
`
`J ul. 23, 2002
`Jul. 23, 2002
`
`Sheet 6 of 13
`Sheet 6 of 13
`
`US 6,424,681 Bl
`US 6,424,681 B1
`
`A 3
`
`:>0C(
`
`........ ----~ c
`~ -
`
`D3U
`
`Q)
`'
`::l
`(DI—q.
`C'"
`Q)
`
`Fig.6
`
`Amplitude
`
`8
`
`

`

`u.s. Patent
`
`US. Patent
`
`Jul. 23, 2002
`J ul. 23, 2002
`
`Sheet 7 of 13
`Sheet 7 of 13
`
`US 6,424,681 B1
`US 6,424,681 B1
`
`......... ----
`
`.7:v
`>.
`
`OCc
`
`u3U
`
`"
`cuL“—
`
`-z
`
`~
`
`>!
`
`><
`
`0 .--
`m -
`co -
`I'--
`to -
`tn -
`v -
`C\I -
`.--
`0 -
`
`.....
`
`(1)
`
`Fig.7
`
`.-
`
`2: -C\I
`I z -(1)
`Z -
`
`•
`•
`•
`
`. .=-1 u
`I Z
`~
`
`C"l
`
`0 -><
`
`00
`
`><:
`v
`cJ~
`
`.~
`U
`
`N
`
`(F
`v ><
`
`N ><: -cJ~
`
`u
`X+C
`+
`:.<
`
`0 ><:
`
`Amplitude
`
`Q)
`"C
`::::I
`.:::
`"C..
`E «
`
`9
`
`

`

`u.s. Patent
`
`US. Patent
`
`Jul. 23, 2002
`Jul. 23, 2002
`
`Sheet 8 of 13
`Sheet 8 of 13
`
`US 6,424,681 Bl
`US 6,424,681 B1
`
`CD
`E
`+=
`
`
`
`co
`w.9“.
`Ol u::
`
`-~ x
`
`mua=ae<
`
`£3
`
`.xm_>_
`
`w2m>
`
`.xm_>_-
`
`o:_m>
`
`1O
`
`10
`
`

`

`u.s. Patent
`
`Jui. 23, 2002
`
`Sheet 9 of 13
`
`US 6,424,681 Bl
`
`--(cid:173).... -
`
`(j)
`
`Cl u::
`
`-----...,.; u
`
`+
`
`..-...
`
`.... --.~
`
`C3
`X
`
`.(])
`X
`::J
`ctS-
`~~
`
`11
`
`

`

`u.s. Patent
`
`US. Patent
`
`Jul. 23,2002
`Jul. 23, 2002
`
`Sheet 10 0f 13
`Sheet 10 of 13
`
`US 6,424,681 Bl
`US 6,424,681 B1
`
`ct:I
`0
`
`2:.mi
`
`C)
`
`u:::
`
`.0
`0
`T"""
`
`nor.5
`C> u:
`
`(.)
`0
`
`2:.9”.
`C> u:
`
`..-.. ----Q)
`
`E
`
`'';::
`
`......... ----Q)
`
`E
`
`'';::
`
`..-.. -'-"'
`
`Q)
`
`E
`
`'';::
`
` 833:2 833:2 3335
`
`......... -Ii
`
`Q)
`"'0
`:J
`
`,,!::: c..
`E «
`
`c ---a.
`
`Q)
`"C
`:::J
`,,!:::
`a.
`E «
`
`12
`
`12
`
`

`

`Joooo" c=
`QO
`0-,
`~
`~
`Q\
`00
`~
`
`Joooo"
`
`306
`
`304
`
`302
`
`FIG.13
`
`data
`
`Decoder
`
`-I
`
`Xreceived
`
`f-----to.I Demodulator 1
`
`FFT
`
`xr(t)
`or
`xr(n)
`
`~
`1-0'(cid:173)
`
`Q ....
`
`1-0'-
`1-0'-
`~
`It>
`
`r.n =(cid:173)
`
`J~ g
`~ F-
`
`N
`
`~
`~
`~
`rJ:J •
`o .
`
`~ = ~
`
`208
`
`206
`
`204
`
`202
`
`FIG.11
`
`x(t)
`
`Converter
`
`Analog
`Digital to
`
`x(n)
`
`Applicator
`
`Kernel
`
`X
`
`Modulator
`
`Encoder
`
`..
`
`data
`
`r-
`
`\
`200
`
`13
`
`

`

`u.s. Patent
`
`US. Patent
`
`B.mJ
`Jul. 23,2002
`
`-0 )
`0) c
`0:5:
`c:: .-
`.... 0)
`~~
`
`Ehoficmc.
`
`
`
`2.M5:38W$me@99523x
`
`31f021teehS
`Sheet 12 of 13
`
`US 6,424,681 Bl
`US 6,424,681 B1
`
`co o
`mom
`C\I
`
`C\I
`C\I
`C\I
`
`o
`C\I
`C\I
`
`
`
`N_..OE
`
`~ o
`vow
`C\I
`
`2.21805
`
`:2:
`:2:
`:2:
`« « «
`a a a
`
`:2:
`:2:
`• •• « «
`a a
`
`•••
`
`14
`
`14
`
`
`

`

`u.s. Patent
`
`Jut 23, 2002
`
`Sheet 13 of 13
`
`US 6,424,681 Bl
`
`402
`
`404
`
`Choose
`Peak Reductiion
`Frequencies
`
`406
`
`Compute
`Kernel (P,P)
`
`408
`
`Upate Transmiitter
`wth Kernel and Peak
`Reductiioin Frequencies
`
`FIG. 14
`
`452
`
`receive
`x + cO); j=O
`
`Apply Kernel, p,
`to x + cO)
`
`j=j+1
`
`Generate
`cO)
`
`454
`
`456
`
`457
`
`458
`
`459
`
`cO) = c(j) + c(j-1 )
`
`y
`
`464 r-------lL..-_---,
`Send
`xcliipO) = x + cO)
`to DAC
`
`FIG. 15
`
`15
`
`

`

`US 6,424,681 B1
`
`1
`PEAK TO AVERAGE POWER RATIO
`REDUCTION
`
`BACKGROUND OF TIIE INVENTION
`
`This invention relates generally to communication sys(cid:173)
`tems. More specifically to reducing peak to average power
`ratios in multi-carrier communication systems.
`In recent years multi-carrier communication systems have
`received more attention. Multi-carrier communication sys(cid:173)
`tems offer the promise of increased bandwidth combined
`with two-way communications.
`However, several problems still remain to be solved to
`ensure the widespread use of multi-carrier communication
`systems. One concern is how to reduce the peak to average
`power ratio of a multi-carrier transmission.
`Referring to FIG. 1, a multi-carrier transmission is com(cid:173)
`posed of a number of independent signals. FIG. 1 is a
`frequency domain plot of several signals 10(1)-10(n). Each
`signaI10(1)-{n) is centered a different frequency f(1)-f(n).
`Often times the frequencies are equally spaced. apart. The
`frequencies are commonly referred to as carrier frequencies.
`In most multi-carrier communication systems the signals
`10(1)-{n) are combined together as a vector. An inverse fast
`fourier transform (IFF!) is usually performed on the vector
`to produce a discrete time domain signal which is converted
`to a continuous time domain signal and transmitted. FIG. 2
`illustrates a continuous time domain representation of a
`typical output signal 30 of a multi-carrier transmitter.
`Signal 30 contains a number of peaks 31-34. A problem
`with the output signal is that the peaks 31-34 often times
`exceeds the output capabilities of the transmitter. If the
`transmitter is only capable of transmitting at amplitudes of
`up to +/-10 dB, the peaks saturate the transmitter and the 35
`peaks are cutoff in the transmitted signal. Saturation causes
`the transmitted signal to lose a significant amount of
`information, which mayor may not be corrected for by the
`receiver. Thus, it is important to reduce the peaks in order to
`maintain the integrity of the transmitted signal.
`Reducing the peak to average power ratio of a signal
`requires that the number and magnitude of the peaks are
`reduced. There have been several attempts to reduce peak to
`average power ratios, although they are only successful to a
`certain extent.
`The placement of the different signals 10(1)-{n) at dif(cid:173)
`ferent carrier frequencies f(1)-f(n) affects the shape of the
`output signal 30. One method randomly shuffles the phase of
`the signals 10(1)-10(n) at each carrier frequency f(1)-f(n).
`Random shuffling does not completely eliminate the 50
`problem, although randomizing has been shown to some(cid:173)
`what reduce the peak to average power ratio to an extent.
`Random shuffling also requires performing an additional
`IFFT. In addition to not completely reducing the peak to
`average power ratio to a practical point, that particular 55
`method also requires that additional information, side
`information, be sent along with the transmitted signal. In
`order for the receiver to be able to decode the transmitted
`signal the receiver must also know how the signals 10(1)-
`10(n) were randomized. Thus, the randomization scheme 60
`requires extra bandwidth to transmit the side information
`and does not effectively reduce the peak to average power
`ratio.
`Another method has been applied to multi-carrier com(cid:173)
`munication systems that use a small number of carrier
`frequencies. In that method all the different possible outputs
`of each signal 10(1)-10(n) are simulated. For example, if
`
`5
`
`30
`
`2
`each signal10(1)-{n) is a 4-ary quadrature amplitude modu(cid:173)
`lated signal, each signal would be one of four different
`waveforms. If there are ten carrier frequencies, then over a
`million combinations are simulated. Those combinations of
`the outputs of signals 10(1)-{n) that exhibit peak to power
`ratios that exceed a specified limit are not used in actual
`transmissions. Typically, a chaunel must be simulated peri(cid:173)
`odically because of changes in the channel's characteristics.
`The elimination of some of the possible combinations of
`10 the outputs of the signals, however, reduces the bandwidth
`of the communication scheme. Further, the method can only
`be applied to communication systems that use a few carriers
`since the number of simulations required increases expo(cid:173)
`nentially with an increase in the number of carriers. That is,
`15 if M-ary QAM and N frequencies are used, NM combina(cid:173)
`tions must be simulated. M can be as high as 1024 and N
`even larger. Thus, this method becomes impractical when
`even a moderate number of carriers are used.
`A third method involves performing inverse fast fourier
`20 transforms on subsets of the signals 10(1)-{n). For example,
`an IFFT may be performed on the first one fourth signals,
`another IFFf for the second one fourth, and etc. The four
`output signals may then be linearly combined to provide one
`output signal. Reducing the number of carriers within a
`25 single IFFT output reduces the peak to average power ratio
`for that output signal since there are fewer signal compo(cid:173)
`nents. The linear combinations are compared to determine
`which combination has the best PAR.
`As the number of signals and carriers increase the number
`of lFFTs that must be performed on the subsets of the signals
`increase, according to the number of signals incorporated
`within a single IFFT. The complexity of the transmitter
`thereby increases by the number of IFFTs that must be
`performed, compared to a single IFFT. Further, information
`about the linear combination of the transmitted signal must
`also be passed along to the receiver. This information is even
`more vital, and usually requires additional bandwidth to
`ensure proper reception and decoding of the information.
`In yet another method of reducing peak to average power
`40 ratio, the output signal of an IFFf of all the signal compo(cid:173)
`nents is scaled to bring the peaks below the maximum level.
`A problem with this solution is that the signal to noise ratio
`is reduced proportionally with the scaled factor. Reducing
`the signal to noise creates a great number of other problems
`45 which makes this method unattractive. For example, as the
`signal to noise ratio decreases more errors occur during
`transmission.
`What is desired is a method of reducing the peak to
`average power ratio of a transmission within a multi-carrier
`communication system without a sigrtificant decrease in the
`amount of usable bandwidth, and with low complexity such
`that reduction of the peak to average power ratio may be
`performed in real time.
`SUMMARY OF THE INVENTION
`The present inventions provide methods and systems for
`reducing the peak to average power ratio of a multi-carrier
`signal. Reducing the peak to average power ratio of a signal
`ensures that amplifiers and transmitters are not saturated,
`causing loss of data. Further, reducing peak to average
`power ratios reduces the consumption of power during
`transmission.
`Peak to average power ratios are reduced by selecting a
`subset of a plurality of frequencies that make up a multi-
`65 carrier symbol. Peak reduction signals, carried at the subset
`of frequencies, are computed to reduce the PAR of the
`symbol.
`
`16
`
`

`

`US 6,424,681 B1
`
`3
`In one embodiment, a kernel is generated that has com(cid:173)
`ponents in the subset of frequencies. 1be kernel is adjusted
`to negate one or more peaks in the multi-carrier symbol. The
`adjustment of the kernel creates a subset of signals of a
`plurality of signals centered at the plurality of frequencies.
`Negation of the peaks may be performed iteratively to
`remove any peaks produced during prior peak reduction
`operations.
`In one embodiment, the subset of frequencies are chosen
`prior to transmission. In alternate embodiments, the subset 10
`of frequencies may be reselected during communication.
`The subset of frequencies may be chosen to obtain a
`kernel that may better negate the peaks of the multi-carrier
`symbol. In one embodiment the subset of frequencies may
`be chosen based upon the characteristics of the channel. In 15
`other embodiments, the subset of signals may be chosen
`randomly, pseudo-randomly, or combinations thereof.
`These and other advantages of the present invention will
`become apparent to those skilled in the art upon a reading of
`the following descriptions of the invention and a study of the
`several figures of the drawing.
`BRIEF DESCRIPTION OF 1HE DRAWINGS
`FIG. 1 illustrates a frequency domain plot of several
`signals of a multi-carrier communication system.
`FIG. 2 illustrates a continuous time domain representation
`of a typical output signal of a multi-carrier transmitter.
`FIG. 3 illustrates a frequency domain plot of a DMT
`symbol prior to applying an inverse fast fourier transform.
`. FIG. 4 illustrates a signal constellation of a signal that is
`4-ary quadrature amplitude modulated.
`FIG. 5 illustrates a frequency domain representation of X
`in accordance with an embodiment of the present inventions.
`FIG. 6 illustrates the frequency domain representation of
`C in accordance with an embodiment of the present inven(cid:173)
`tions.
`FIG. 7 illustrates the frequency domain representation of
`X+C in accordance with one embodiment of the present
`inventions.
`FIG. 8 illustrates the continuous time domain represen- 40
`tation of a symbol signal x(t) of a multi-carrier communi(cid:173)
`cation system in accordance with an embodiment of the
`present inventions.
`FIG. 9 illustrates a time domain representation of a
`desired symbol signal r-liP(t)=x(t)+c(t) in accordance with 45
`an embodiment of the present inventions.
`FIGS. 10a-c illustrate several approximate impulse func(cid:173)
`tions p(t) in accordance with an embodiment of the present
`inventions.
`FIG. 11 illustrates a multi-carrier transmitter in accor- 50
`dance with an embodiment of the present inventions.
`FIG. 12 illustrates block diagrams of the modulator and
`the kernel applicator of FIG. 11 in accordance with an
`embodiment of the present inventions.
`FIG. 13 illustrates a receiver in accordance with an 55
`embodiment of the present inventions.
`FIG. 14 illustrates the preliminary process of determining
`the peak reduction channels in accordance with an embodi(cid:173)
`ment of the present inventions.
`FIG. 15 illustrates a flow chart of the operation of the 60
`kernel engine. of FIG. 12 in accordance with an embodiment
`of the present inventions.
`
`35
`
`DETAILED DESCRIPTION OF TIlE PRESENT
`INVENTIONS
`The present inventions provide apparatuses and methods
`of reducing peak to average power ratios in multi-carrier
`
`65
`
`4
`communication systems without significantly reducing the
`amount of bandwidth. 1be present inventions may also be
`implemented with a low amount of complexity such that
`they may be implemented in real time. Additionally, no
`significant amount of side information is required, which
`would reduce bandwidth, nor is there a reduction in the
`signal to noise ratio or quality of service.
`The present inventions apply to any type of communica(cid:173)
`tion systems utilizing multiple carriers. By way of example,
`the present inventions apply to Discrete Multi-Tone (OM]),
`Orthogonal Frequency Division Multiplexing (OFDM) and
`Discrete Wavelet Multi-Tone (OWM1) communication sys(cid:173)
`tems.
`Referring to FIG. 3, a multi-carrier communication sys-
`tem takes advantage of a channel by sending several signals
`over a wide band of frequencies. FIG. 3 is a frequency
`domain plot of a DMT symbol 100 prior to applying an
`inverse fast fourier transform. The DMT symbol is a func-
`tion of a number of signals 11O(O)-11O(N-1), each centered
`at a different frequency UO(O)-(N-1). While details of the
`present inventions are discussed in terms of a DMT com-
`munication system, the advantages of the present inventions:
`apply readily to other types of multi-carrier communication
`systems, and the present inventions are not restricted to only
`25 DMT systems.
`Each signal UO(O)-(N-1) may carry any number of bits
`of information in a digital system. By way of example, each
`signal may be modulated by M-ary quadrature amplitude
`30 ~~;~!~~~~~~7ti~!~n:!o:~h:d::~:~~U!:ti:n~
`
`20
`
`other type of suitable modulation scheme. The illustrated
`signals are M-ary quadrature amplitude modulated. Thus,
`each signal 11O(O)-(N-1) has a magnitude and a phase in
`addition to its frequency.
`FIG. 4 is a signal constellation of signal 110(3) that is
`4-ary quadrature amplitude modulated. Signal 110(3) has an
`amplitude, A, and a phase, I'l. Depending upon the amplitude
`and phase, signal 110(3) may represent one of four binary
`values, 00, 01, 10 and 11, as illustrated.
`Each signal 110(O)-(N-l) are all quadrature amplitude
`modulated, but may have different constellations. The num(cid:173)
`ber of constellation points that a signal represents depends
`upon the characteristic of the channel for that particular
`frequency. That is, if frequency 120(4) is less noisy than
`frequency 120(3), then signal 110(4) may have an 8-ary
`QAM constellation or greater. Thus, by looking at the
`characteristics of the channel less noisy frequencies may
`carry signals that represent a greater number of bits.
`In one embodiment of the present inventions, those fre(cid:173)
`quencies that have a lot of noise and are capable of only
`carrying low bit rate signals are used as peak reduction
`frequencies. 1be peak reduction frequencies may carry no
`signal at all. It has been found that having peak reduction
`frequencies that carry no signal may sometimes marginally
`help to reduce the peak to average power ratio of a trans-
`mISSion.
`In another embodiment, the peak reduction frequencies
`carry peak reduction signals. Peak reduction signals, like
`regular signals, have an amplitude and a phase. However, in
`one embodiment, the peak reduction signals generally do not
`carry any data. Rather, the peak reduction signals are scaled
`and shifted such that the peaks of the output signal are
`dramatically reduced.
`In alternate embodiments of the present inventions, the
`peak reduction frequencies may be chosen by any suitable
`method. Frequencies that are noisy are utilized as peak
`
`17
`
`

`

`US 6,424,681 Bl
`
`6
`at the non-peak reduction frequencies are always zero, such
`that the values of C do not interfere with X. Thus,
`
`5
`reduction frequencies since the decrease in data rate of the
`output symbol is minimized. However, a different selection
`of peak reduction frequencies may provide better peak to
`average power ratio reduction with fewer peak reduction
`frequencies. It has been found that randomly selected peak
`reduction frequencies provides good peak to average power
`ratio attenuation. Selection of peak reduction frequencies is
`discussed further below.
`Because of the properties of an inverse fourier transform
`changing the attnbutes of one or more of the components of
`a signal before it is inverse fourier transformed effects the
`transformed signal. In the case of DMT a discrete time signal
`x is generated from a number of complex valued QAM
`modulated signals 1l0(O)-{N-l), or X. Where
`
`X=(!'1 •.. x • ... XH ]
`
`The elements of X are complex values that represent the
`amplitude and phase of the signals Xo-XN_l> where the
`frequencies fa-fN_I> are of equal bandwidth and separated by
`UT, where T is the time duration of a DMT symbol. Each
`element of x is a symbol derived from X defined by:
`
`I N-l
`
`x,. = ~ r.;-2:: X, efl""'IN , k = 0, ... , N - I
`'I N ,=0
`
`which can be written as x=Qx, where Q is the IFFT matrix 30
`and the elements of Q are
`
`Initially, Ck may be set to zero, and the values for Ck
`changed later to reduce the PAR. L is the number of peak
`10 reduction frequencies that are utilized to reduce the PAR of
`x. If N frequencies are available, then the ratio of peak
`reduction frequencies to the overall number of frequencies is
`UN. However, the actual bandwidth loss is the number of
`bits that the peak reduction frequencies were capable of
`carrying over the total number of bits that all N frequencies
`15 are capable of carrying. By selecting peak reduction fre(cid:173)
`quencies that are capable of carrying few, or zero, bits per
`symbol, bandwidth loss is minimized. The non-zero values,
`Ck for k E {il ••• , iLl or t, are called the peak reduction
`signals, or peak reduction tones in the case of DMT, or more
`20 generally dummy signals.
`The values for X are zeroed out at the peak reduction
`frequencies. FIGS. 5 and 6 show the frequency domain
`representations of X and C, respectively, according to one
`embodiment of the present inventions. The frequencies f
`25 4,~, 4 and fN_2 are chosen as peak reduction frequencies.
`"
`Accordingly, the values for Xl> Xs, x", Xr and XN _ 2 are
`zero. The other values for X correspond to the amplitude and
`phase of those signals.
`In alternate embodiments, only one component of the
`values of X may be zeroed out and used for peak reduction
`purposes. By way of example, the real part of the values of
`Xl> Xs, X6, ~ and XN _ 2 may be zeroed out and the
`imaginary part of the components used to carry information.
`Analogously, one of the phase or amplitude components of
`the values of X may be zeroed out and used for peak
`35 reduction while the other is used to carry information.
`The values for C correspond to the peak reduction fre(cid:173)
`quencies. The index i conforms to the peak reduction
`frequencies, e.g., il is the index for the first peak reduction
`frequency fl , i2 is the index for the second peak reduction
`40 frequency 4, and etc.
`FIG. 7 illustrates the frequency domain representation of
`X+c, in accordance with one embodiment of the present
`inventions. In the combined signal all tbe frequencies con(cid:173)
`tain a signal. The non-zero values of peak reduction signals
`45 C are located at the peak reduction frequencies, while the
`actual signals X are located at the non-peak reduction
`frequencies. Initially, the peak reduction signals C may have
`any arbitrary values. However, it is useful to initialize the
`values of C at zero.
`The first set of values ofC may then be represented as the
`initial values C(O). If C(O) are zeroes, then X+C(O) =x, and
`x+c(O)=x. The time domain representation of x+c(O) is
`equivalent to the unmodified signal x(t), as illustrated in
`FIG. 8. However, the values for C should be chosen to
`55 provide a signal (x+c) that does not have peaks that exceed
`a predetermined magnitude. FIG. 9 is a time domain repre(cid:173)
`sentation of a desired signal Xdip(t)=x(t)+c(t) generated by
`the vector X+c.
`The continuous time domain waveforms depicted in
`60 FIGS. 8, 9 and other figures are representative of analogous
`discrete time domain waveforms. A majority of the algo(cid:173)
`rithms used in the present inventions are predominantly
`performed in discrete time due to practical considerations.
`The continuous time domain waveforms are used for pur-
`65 poses of illustration. However, the scope of the present
`inventions includes analogous algorithms performed in con(cid:173)
`tinuous time and frequency domains.
`
`The peak to average power ratio (PAR) of x is then:
`
`PAR=~
`"OIxlI!l/N
`
`where IIvll= is the norm of the vector v, or the maximum
`absolute value, v2 is the 2-norm of the vector v, or the root
`mean square, and E[f(v)] is the expected value of the
`function f( v).
`The peak reduction frequencies, once chosen, can be
`assigned arbitrary amplitudes and phases. In one
`embodiment, the peak reduction frequencies may be initial(cid:173)
`ized with zero amplitude and zero pbase. The values for the
`peak reduction signals are represented as the vector c in the 50
`time domain, and C in the frequency domain, where.
`
`The possible values for c are chosen such that
`
`PAR = (c') = min" 11% + cll!.« ~
`£[11xfI!11 N
`£[11xf1~11 N
`
`where c* is the optimal solution for c. The value of the right
`side of the inequality is the PAR of the signal generated from
`the vector x, and the left side of the inequality is the PAR of
`the peak reduced signal generated from the vector x+c.
`The values for C at the peak reduction frequencies may be
`any suitable value that helps to reduce the peaks in the
`transmitted multi-carrier symbol. However, the values for C
`
`18
`
`

`

`US 6,424,681 B1
`
`7
`The values for C* and c*, the optimal solution that would
`provide an XcIip(t) with the smallest PAR, may be obtained
`by solving the following equation:
`
`Q is the sub-matrix of Q constructed from the columns
`i" ... , iL , and t represents the non-zero values of C. c* can
`actually be solved through linear programming. Solutions
`may also be found separately for the real and the imaginary
`parts of x or X.
`The above equation may be rewritten in the following
`form:
`
`.... ,
`C
`5Ubject tox+ QC Sw lIN,
`
`Moving all the unknowns to the left hand side, the equations
`may be rewritten as:
`
`mi ...
`C
`rubject to QC - cl N !ON -x, or
`
`QC+lIN?:eN -x
`
`.... ,
`
`c
`
`8
`that the value for p(O) is equal to one. This allows pet) to be
`scaled more readily.
`FIG. lOa may be a first approximation of an impulse. The
`lobes around the impulse should however be reduced in
`5 magnitude. The side lobes should be reduced to ensure that
`when the impulse is applied to x(t) to clip a particular peak
`no other portion of x(t) exceed the maximum value. Another
`approximation of an impulse may look like the approxima(cid:173)
`tion in FIG. lOb. Obviously, the secondary peaks of FIG.
`10 lOb poses a problem when applied to x(t). Ideally, pet)
`should resemble the waveform depicted in FIG. lOc.
`Solving for the mean square error between p=Q P and an
`ideal discrete time impulse eo=[l 0 ... Of provides the
`15 solution for an approximation of p that is the mean square
`error. The mean square error minimizes the sum of all the
`peaks of the kernel, or power, other than the peak at p(O).
`
`The solution becomes:
`
`20
`
`25
`
`30
`
`35
`
`The linear program has 2L+l unknowns {Real(t), Imag(t),
`t} and 2N inequalities written in the standard linear program
`form:
`min cTx
`subject to Ax~N b
`linear programming algorithms exist to solve for c·. The 40
`linear programming solutions provide the ideal solution c·.
`Currently, the exact solution approach is most practical in
`communication systems operating at data rates of approxi(cid:173)
`mately 500 kbps or lower because of the amount of com(cid:173)
`putations required to compute the exact solution for c*. 45
`However, good approximations of c· may be obtained such
`that the PAR of x can be satisfactorily reduced in real time
`for higher data rate systems. However, as processing power
`becomes more readily available in the future the linear
`programming solution may be utilized in multi-carrier com- 50
`munication systems operating at higher speeds in a=r(cid:173)
`dance with the present inventions.
`Approximating c, C
`As seen in FIG. 8, the time domain signal x(t) has several
`peaks 130-133. The peaks 130-133 can be reduced by 55
`adding or subtracting an appropriately scaled impulse func(cid:173)
`tion lI(t) at those peak time values. The impulse function,
`however, must be constructed from the peak reduction
`frequencies, {il' i2 , •.• , iL }. Since a true impulse function
`cannot be created by less than all the frequency components, 60
`i.e., when L<N, an approximate impulse must be used, p.
`FIGS. lOa-c illustrate several approximate impulse func(cid:173)
`tions p(t), generated from different values of p, in a=r(cid:1