`

`US 6,424,681 B1
`Page 2
`
`OTHER 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. Miil1er 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-to-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.
`
`A.E. 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
`
`

`

`

`

`

`

`~
`~
`~
`QO
`<:1\
`
`~e
`5"
`CF.l
`c:::
`
`'"'" ~
`
`~
`
`Q
`~
`
`('I> ....
`00 =- ('I>
`
`N g
`N SJ4
`~ = :-
`
`N
`
`~ """ ~ = """
`
`~
`rJ1 •
`Cj .
`
`120(N-1)
`
`frequency (f)
`
`fN-1
`
`f7
`
`120(6) 120(7)
`
`f6
`
`110(5)
`\
`fS
`
`110(4)
`I
`
`110(2)
`I
`
`120(3)
`
`120(0) 120(1)
`
`f4
`
`f3
`
`f2
`
`f1
`
`to
`
`Fig. 3
`
`I
`100
`
`• • •
`
`120(4) 120(5)
`
`120(2)
`
`I
`110(N-1)
`
`I
`110(7)
`
`I
`110(6)
`
`I
`110(3)
`
`I
`110(1 )
`
`I
`110(0)
`
`Amplitude
`
`5
`
`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`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)--IO(n). Each
`signallO(I)-(n) is centered a different frequency f(l)-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 (IFFI') 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
`illnstrates 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(l)-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(l)-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
`
`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 charmel 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 IFIT 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 IFIT 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 IFITs that must be performed on the subsets of the signals
`increase, according to the number of signals incorporated
`within a single IFIT. The complexity of the transmitter
`thereby increases by the number of IFITs that must be
`performed, compared to a single IFIT. 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 IFIT of all the signal compo(cid:173)
`nents is scaled to bring the peaks below the maxinlum 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 significant 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.
`
`30
`
`SUMMARY OF 1HE 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. 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. 5
`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 TIlE 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 25
`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-
`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 lflip(t)ax(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 S5
`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.
`
`3S
`
`20
`
`4
`communication systems without significantly reducing the
`amount of bandwidth. The present inventions may also be
`implemented with a low amonnt 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 commnnica(cid:173)
`tion systems utilizing multiple carriers. By way of example,
`the present inventions apply to Discrete Multi-Tone (DMT),
`Orthogonal Frequency Division Multiplexing (OFDM) and
`Discrete Wavelet Multi-Tone (DWM1) 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 12O(O)-(N-l). 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
`DMT systems.
`Each signal 12O(O)-(N-l) 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
`modulation, M-ary phase shift key, frequency modulation,
`30 amplitUde modulation, continuous phase modulation or any
`other type of suitable modulation scheme. The illustrated
`signals are M-ary quadrature amplitude modulated. Thus,
`each signal 11O(O)-(N-l) 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, ¢. 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-1) 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. The 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
`
`DETAILED DESCRIPTION OF THE PRESENT
`INVENTIONS
`The present inventions provide apparatuses and methods
`of reducing peak to average power ratios in multi-carrier
`
`65
`
`17
`
`

`

`US 6,424,681 B1
`
`6
`at the non-peak reduction frequencies are always zero, such
`that the values of C do not interfere with X. Thns,
`
`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 ofDMT a discrete time signal
`x is generated from a number of complex valued QAM
`modulated signals 1l0(O)--(N-l), or X. Where
`
`The elements of X are complex values that represent the
`amplitude and phase of the signals Xo-XN_I , where the
`frequencies fo-fN_H are of equal bandwidth and separated by
`Iff, where T is the time duration of a DMT symbol. Each
`element of x is a symbol derived from X defined by:
`
`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
`LIN. 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
`lS 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 EO {il ... , iz.} or C, 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 sbow the frequency domain
`representations of X and C, respectively, according to one
`embodiment of the present inventions. The frequencies flO
`25 is, f,;, ~ and ~-2 are chosen as peak reduction frequencies.
`Accordingly, the values for Xl> Xs, x.s, Xr and XN _ 2 are
`
`zero. The other values for X correspond to the amplitude and
`phase of those signals.
`In alteroate embodinlents, 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, Xr 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 fI , 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 the frequencies con(cid:173)
`tain a signal. The non-zero values of peak reduction signals
`4S 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 of C may then be represented as the
`initial values C(O). If C(O) are zeroes, then X+C(O) ~x, and
`x+e(O)ax. The time domain representation of x+e(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 x"lip(t)=X(t)+e(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.
`
`which can be written as x=Qx, where Q is the IFFr matrix 30
`and the elements of Q are
`
`The peak to average power ratio (PAR) of x is then:
`
`PAR=~
`eOIxlI!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 phase. 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
`
`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
`
`

`

`7
`The values for C* and c*, the optimal solution that would
`provide an Xdip(t) with the smallest PAR, may be obtained
`by solving the following equation:
`
`Q is the sub-matrix of Q constructed from the columns
`il> ... , 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:
`
`D'
`C
`subject tox+ QC SN lIN,
`
`Moving all the unknowns to the left hand side, the equations
`may be rewritten as:
`
`.....
`C
`subject to QC - IlN SN -x, or
`QC+IlN <::N-X
`
`D'
`C
`
`SUbi<ettO( Q -IN YC)sw(-X)
`_Q -IN ~ r
`
`x
`
`20
`
`25
`
`30
`
`35
`
`The linear program has 2L+l unknowns {Real(t), Imag(l:),
`t} and 2N inequalities written in the standard linear program
`form:
`min cTx
`subject to Ax~N b
`Unear 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 accor(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)
`tiou 5(t) at those peak time values. The impulse function,
`however, must be constructed from the peak reduction
`frequencies, {il> iz, ... , 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 accor(cid:173)
`dance with one embodiment of the present inventions. Since
`only the L peak reduction frequencies can be used to create 65
`the approximate impulse function p(t), or kernel, p(t) is not
`ideal. One useful constraint that may be placed upon p(t) is
`
`US 6,424,681 B1
`
`8
`that the value for p(O) is equal to one. This allows p(t) 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:
`
`T
`(,r,)-I,r
`1
`I
`.J>
`,T
`1'2 = Q Q Q.o = Q '0 = ..-;- [I ... I) = - IL
`#
`'IN
`
`.., 1 ,
`f2 = .,[NQIL
`
`Since the value for Po should be equal to one we can scale
`the result to obtain the mean square error optimal solution
`for p, p*.
`.
`
`Since P has non-zero values only at the peak reduction
`frequencies, C may be represented as any suitable linear
`combination of P. The linear combinations of P correspond
`to the scaled and shifted versions of the kernel, p, such that
`the scaled and shifted versions of p negate the peaks of x.
`For example, if pet) of FIG. 10e were to be applied to x(t)
`of FIG. 8, pet) would be inverted and shifted to t-2 in order
`to cancel out the first peak 130. Also, if the first peak 130
`exceeded the maximum value by some factor a, p(t-2)
`would be scaled by a value greater than a, such as (L2a).
`When x(t) and (L2a)p(t-2) are added the value at t=2 would
`be the maximum value +a-lo2a, which gives us a value less
`than the maximum value (maximum value -O.2a). The
`scaling and time shifting of p merely scales and phase shifts
`the values of P, and therefore t. t, which is a linear
`combination of P, will have zero values at the non-peak
`reduction frequencies.
`Any number of peaks may be clipped in this fashion in
`one iteration. However, reducing one or more peaks may
`cause the resulting waveform to exceed the maximum value
`at other positions. Therefore, the process may be repeated
`with the resulting xclip +c to achieve a new X
`clip with a PAR
`that is satisfactory.
`In order to minimize the second highest peak of pet),
`thereby reducing all the peaks other than the peak at p(O), a
`
`19
`
`

`

`US 6,424,681 B1
`
`9
`linear program may be used to solve for the infinite norm
`equation.
`
`P:' = argminll[PI pz ..• PN-dn!" subi· to Po = 1
`
`~
`
`10
`number of peaks per iteration. Once an iteration is complete
`the kernels may be linearly combined to produce c(j), where
`j is the current iteration. After computing c(j) aud adding it
`to x, the new xc/p, r1iPG), can be reevaluated to determine
`if further peaks require cancellation.
`Further iterations may be performed by taking the previ(cid:173)
`ous rlip and adding another set of values for c, i.e.,
`xc/ipG)=xclipG-l )+c(j). Since the values of x remain the same
`because p and P are only functions of the peak reduction
`10 frequencies this sum expands to
`
`5
`
`p* ~ provides the optimal solution, producing a p(t) that
`resembles the waveform illustrated in FIG. lOe.
`The solution of p regardless of its order may be computed
`in advance, or off-line, since only the peak reduction fre(cid:173)
`quencies need to be known. Thus, p may be predetermined
`once the peak reduction frequencies have been chosen. Once
`p is known, p may be linearly combined in any fashion to 15
`produce the necessary values for c and C. The resulting c is
`a good approximation of c* depending upon the number of
`iterations performed.
`In one embodiment, the choice of the peak reduction
`frequencies may be based upon obtaining a good kernel, p. 20
`Once the number of peak reduction frequencies, L, has been
`determined, the Incation of the peak reduction frequencies
`may be determined based upon deriving a good, or the best,
`kernel, p. Certain quality factors may be imposed before
`accepting a p as a valid kernel. By way of example, a p with 2S
`secondary peaks greater than a predetermined magnitude
`may be rejected. That set of peak reduction frequencies may
`then be rejected and a new set of peak reduction frequencies
`selected to provide a better p.
`It has been found that randomly selected peak reduction 30
`frequencies will often times provide a good kernel. If a first
`set of peak reduction frequencies chosen randomly does not
`provide a good kernel, a new selection of peak reduction
`frequencies that swap a subset of the first randomly chosen
`peak reduction frequencies sometimes provides a better 35
`kernel. The combinatious of peak reduction frequencies may
`be iteratively evaluated until a kernel with the appropriate
`characteristics is obtained.
`In another embodiment, peak reduction frequencies may
`be chosen based upon the bit rates of the frequencies. In one 40
`instance, a pseudo-random selection of the peak reduction
`frequencies may be performed with weights applied to those
`frequencies that have low bit rates that make the selection of
`those frequencies more likely. If after several iterations a
`proper kernel, p, cannot be obtained the weights may be 45
`adjusted since the weighted frequencies may not be good
`candidates for constructing a proper kernel.
`After the peak reduction frequencies have been chosen the
`optimal, or a good approximation of the optimal kernel is
`computed. Using the resulting kernel, p, the peak reduction 50
`vector c, containing the peak reduction signals, or peak
`reduction signals, may be constructed. Initially, the vector
`x+c(0), where the values of c(0) is all zeroes, is computed by
`taking the IFFT of the vector X, containing zero values in the
`peak reduction frequencies. If only one peak is negated 55
`during a single iteration of applying the kernel, p, is per(cid:173)
`formed XC1p(1)=x+c(1), where c(l)=Alp[(n-~l)k in the
`discrete time domain, where is A a scaling factor and ~ is a
`time shift. If two peaks are canceled in one iteration
`
`~(J1 = x+c(O) +c(l) + ... + c(j -1) +c(J1. or
`
`j
`
`m=O
`
`ccllp{J) = x + 2: c(m), and
`-
`c· = t c(m) as j .... 00
`
`The sum of c's is equal to a number of scaled and/or shifted
`kernels, p. If only one peak is corrected (only one peak is
`canceled) per iteration then the equation hecomes:
`
`x<liPU) = x+A1P[(n- t.JllN +Azp[(n- t.z)lN + ... +
`Aj-lP[(n-t.j-.J1N + Ajp[(n- t.j)lN' or
`x<lip(j) = x + 2: Amp[(n - t.mllN
`
`j
`
`m=O
`
`Thus, c is computed simply by performing multiplies and
`adds, and does not require any additional transforms, which
`are significantly more computationally intensive. Thus, the
`present inventions require significantly fewer computational
`resources than other methods that have been used to reduce
`the PAR of a multi-carner signal.
`The process may be repeated indefinitely until the sum(cid:173)
`mation of c approaches the optimal peak reduction signal
`vector c*. But a good approximation of c* may be obtained
`in as little as one or two iterations. The quality of c depends
`upon the quality of the kernel p, which depends upon the
`number and location of the peak reduction frequencies.
`Thus, as L, the number of peak reduction frequencies
`increases towards N, the total number of frequencies, better
`approximations of c· are obtained in fewer iterations.
`By way of example, four iterations at one kernel appli-
`cation per iteration when the ratio of UN is 5% has produced
`good results. Application of the present inventions with
`higher UN ratios have produces better results with fewer
`iterations.
`In alternative embodiments, discussed further below, it be
`helpful to know the values of C once c has been computed.
`In those cases a fourier transform of c provides the values for
`C. Since c does not contain any frequency components in th