United States Patent
`
`[19]
`
`[11] Patent Number:
`
`6,134,274
`
`Sankaranarayanan et al.
`
`[45] Date of Patent:
`
`Oct. 17, 2000
`
`USUUGI34-274A
`
`[54] METHOD AND APPARATUS FOR
`ALLOCATING DATA FOR TRANSMISSION
`VIA DISCRETE MULTIPLE TONES
`
`[75]
`
`lI1V611t0rSI Lillltllfl Sankaranarayanan,
`Bedmlmlef; Rania“ V- Senalkal‘,
`N Oflh C/alClW€ll, bolh Of NJ.
`
`[73] Assign“? AT&T C0rP> New York NY
`
`[21] Appl. No: 08/997,167
`
`[22]
`
`].71']Cd;
`
`[)ec_ 23, 1997
`
`Int. Cl.
`[51]
`[52] U.S. Cl.
`
`H04L 27/04
`375/295; 375/296; 375/260;
`375/2549 704/2294 704/200
`[58] Field Of Search ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~ 375/396, 360,
`375/347, 244, 254, 241, 295; 704/229,
`200, 500, 205
`
`[56]
`
`References Cited
`US. PATENT DOCUMENTS
`
`.......................
`
`375/254
`704/200
`I
`,
`375/260
`
`5,206,884
`4/1993 Bhaskar
`5335571
`8/1993 MQZOF
`1;/£2;
`1]:.fi3l’§ka“’a ct “ '
`,
`,
`/
`,
`,
`ie er
`..... ..
`$822,374 10/1998 Levin .........................N
`OTHER PUBLICATIONS
`.
`g
`.
`.
`Lake at 31:’ A Maxlmum Rate Loadmg Algomhm for D15"
`Crete Multitone Modulatiom IEEE’ Pp 1514”1518’ Aug
`1997'
`Fischer et al. A New Loading Algorithm for Discrete Mul-
`titone Transmission, IEEE, p. 724728, May 1996.
`
`Chow et al., A Practical Discrete Multitone Tranceiver
`Loading Algorithm for Data Transmission over Spectrally
`Shaped Channel, IEEE, p. 773775, Feb. 1995.
`American National Standards Institite, Standards Docu-
`ment—’I‘1.413—1995; “Network and Customer Installation
`Interfaces—Asymmetric Digital Subscriber Line (ADSL)
`Metallic Interface”; Approved Aug. 18, 1995, pages: cover
`page; two inside sheets; i—vi; 1-115.
`“Multicarrier Modulation for Data Transmission: an Idea
`whose Times Has Come”, author: John A.C. Bingham, IEEE
`Communications magazine, May 1990, pp. 5-14.
`
`Primary Examiner—Steplien Chin
`Assistant Examiner—Shuwang Liu
`[57]
`ABSTRACT
`
`A method of allocating bits to discrete frequencies in a
`discrctc multitonc modulator comprises the steps of allocat-
`ing bits to frequencies on a per frequency basis such that the
`bits are successively allocated until a niaxiniuin power level
`for that frequency is exceeded. Then, a total power level for
`bits allocated to a plurality of transmit frequencies is cal-
`culated to see if a maximum permissible total power level is
`exceeded. If the maximum permissible total power level is
`not exceeded, then the process is complete. If the maximum
`total power level is exceeded, successive bits are removed
`until the total power level is no longer exceeded. In one bit
`~
`~
`removal method, bits are removed in order oftthe amount of
`power the bit would consume of the transmit power spec-
`trum. The algorithm may be implemented in the combina-
`tion of transmitter elements including tone ordering
`circuitry, gain scaling circuitry and the inverse discrete
`Fourier transform modulator of the discrete multitone data
`transmitter.
`
`9 Claims, 5 Drawing Sheets
`
`11:1. 351 um, AND hm,"
`
`L sk =|
`*"'G HI
`/3P,mosl<kgk
`‘W
`M «
`I
`»,
`bk=MlN (Lmaskk, hmux)
`
`swnz INDICES or THE ARRAY Ark"
`CORRESPONDING TO THE om IN ARRAY um‘,
`mm ARRAY lNDEX(k). som ARRAY om? IN
`uzscauumc own INTO mm nzik sum
`[N uzcwumc om, KEEPING TRACK OF am
`
`DE1"=°E1"/2- bindexlt
`mam THE NEW mus or mm? mm THE
`APPNOPRIAIE LOCATION IN ARRAY DEIF TO
`MAINTAIN mt DESCENDING ORDER. MOVE THE
`VALUE or lNDEX(1) mm ARRAY INDEX (1),
`CORRESPONDING TO THE NEW POSITION OF DE R
`
`Dish
`Exhibit 1015, Page 1
`
`

`
`U.S. Patent
`
`0002771LC0
`
`Sheet 1 of 5
`
`6,134,274
`
`E232$N65%
`
`
`
`A|*::+c3+".5+“.Kt.E+o.53=.+omt.3+“.io
`
`Dish
`Exhibit 1015, Page 2
`
`

`
`U.S. Patent
`
`Oct. 17,2000
`
`Sheet 2 of 5
`
`6,134,274
`
`ozzsmas
`
`225528
`e:E8:ozwfixo
`
`
`
`E»:E3
`
`
`
`5%E85m_2<E<53”=..<~_.._<55E2cu.zocsfimzs5&8H:x2:
`
`E><H._._~_Ez_
`
`Qm<éz§BZEE“fl______
`
`011 )|>JOM1I-IN 'lV1IOI(] 01
`
`Dish
`Exhibit 1015, Page 3
`
`

`
`U.S. Patent
`
`Oct. 17, 2000
`
`Sheet 3 of 5
`
`6,134,274
`
`gs:<53
`
`5%E85.“_:<~_.._£2E2EzozsémzsV32o<_2z§52%;.
`
`
`
`5><E=z2~_m%.<A~__%mo
`
`225928M22s;m>s_§
`
`
`
`seam22¢.5528
`
`H...0
`
`..1_8OWGIAUII.V_|N3I.M03VA
`
`Dish
`Exhibit 1015, Page 4
`
`

`
`U.S. Patent
`
`Oct. 17, 2000
`
`Sheet 4 of 5
`
`6,134,274
`
`FIG. 3
`
`1<=1, SET hm AND bmin
`
`b_maskk=|092
`
`3P_maskk k
`
`I
`bmax)
`
`Gc+1>]
`
`Etota|>Pbudet 7
`
`STORE INDICES OF THE ARRAY AEkR
`CORRESPONDING TO THE ORDER IN ARRAY DE;R.
`INTO ARRAY INDEX(k). SORT ARRAY DEkR IN
`DESCENDING ORDER INTO ARRAY DEiR SORT
`IN DECENDING ORDER, KEEPING TRACK OF BIN
`
`Etotu|=Etota|'DE1R
`DE1R=DE1R/2' Pindex 1
`‘P index 1 "1
`
`INSERT THE NEW VALUE OF DE1R INTO THE
`APPROPRIATE LOCATION IN ARRAY DEiR T0
`MAINTAIN THE DESCENDING ORDER. MOVE THE
`
`INTO ARRAY INDEX (k),
`VALUE OF INDEX(1)
`CORRESPONDING TO THE NEW POSITION OF DE1R
`
`EtotaI>Pbudet ?
`NO
`
`Dish
`Exhibit 1015, Page 5
`
`

`
`U.S. Patent
`
`0002771LC0
`
`Sheet 5 of 5
`
`N_.:5%3,:
`
`K+oat.33St.5..N+o
`
`Dish
`Exhibit 1015, Page 6
`
`

`
`6,134,274
`
`1
`METHOD AND APPARATUS FOR
`ALLOCATING DATA FOR TRANSMISSION
`VIA DISCRETE MULTIPLE TONES
`
`BACKGROUND OF THE INVENTION
`
`1. Technical Field
`This invention relates to the field of data transmission via
`discrete multi-tone modulation and, more particularly,
`to
`method and apparatus for allocating data for modulation via
`discrete multiple tones.
`2. Description of the Related Arts
`In a typical discrete multi-tone modulator, for example, a
`modulator described by A.N.S.I. Standard T1413-1995, a
`plurality of discrete tones are utilized for carrying data
`modulated thereon. Aproblem with this approach is that the
`particular carrier frequencies selected for data modulation
`may be likewise utilized for, for example, AM radio broad-
`casts or may already be used by modulators transmitting
`data on other adjacent cable pairs and the like. Thus,
`time—varying far end crosstalk and near end crosstalk or
`cable ingress of noise from external sources can interfere
`with data transmission of discrete multitone data modula-
`tors. For example, in the discrete multi-tone modulation
`approach, carrier frequencies are spaced approximately
`every four kilohertz across a broad spectrum of frequencies
`(for example, from (P1 megahertz) for data transmission.
`There may be an AM radio broadcast or a data transmission
`on an adjacent cable pair at 530 kilohertz that may interfere
`with a data transmission at approximately the same fre-
`quency. The interfering signal creates noise which precludes
`data transmission at a higher bit carrying capacity than
`would have been achievable without the presence of the
`noisy 530 kilohertz interfering signal.
`Noise from carrier channels using the same frequencies
`can thus detract from bit-carrying capacity on those chan-
`nels. Some tones on the same cable pair can carry more data
`than other tones (depending on what adjacent cable pairs are
`carrying and the amount of noise ingress from external
`sources among other factors). When one views the entire
`power spectrum, and without any power constraint on the
`system, one may allocate bits to frequencies freely to fill or
`pour bits into the power spectrum like water into the peaks
`and valleys of the spectrum until all frequencies are equally
`f11ll.
`In a typical modulator of the multi-tone variety, a .
`channel signal to noise ratio estimation phase is employed.
`The transmitter sends a known pseudo-random noise
`sequence to a receiver and the receiver computes the
`received signal to noise ratio by computing the coherence
`between the received signal and its stored replica. The _
`characteristics are computed in the form of a ratio of the
`channel gain to noise for each channel or tone. Let us denote
`this quantity by gain-to-noise ratio GNR.
`Referring briefly to FIG. 1, there is shown such GNR for
`a series noise spectrum for a series of discrete tones, a+f,
`a+2f, a+3f .
`.
`.
`, where a represents a displacement frequency
`from 0 Hertz and f the carrier or tone spacing, for example,
`approximately 4000 Hz. The GNR plot resembles a “terrain”
`with peaks and valleys. Some frequencies such as a+f are
`noisier than other frequencies such as a+6f. Once the GNR
`is determined, bits are poured into the spectrum (terrain)
`until a maximum total power level (water level) P is reached.
`Two power levels, P1 and P2, are shown by way of example.
`Where a is the initial frequency and f is the tone spacing,
`then bits are poured on each possible tone until a total power
`level P is reached above the terrain GNR. For example, for
`power level P2, bits are poured on or allocated to frequen-
`
`2
`cies: a+2f, a+3f, a+4f, and a+6f. For power level P1, a higher
`power level, bits may be allocated to all tones except a+7f.
`This technique is described by Mr. John A. C. Bingham in
`his paper “Multicarrier Modulation for Data Transmission:
`An Idea Whose Time Has Come,” I.E.E.E. Cumrmmicatiorzs,
`May, 1990, pp. 5-14, incorporated by reference as to its
`entire contents.
`
`Bingham goes on to describe a ‘water filling’ bit alloca-
`tion process that we describe more accurately by the analogy
`of ‘ice cube filling’. Bingham’s algorithm adds bits one bit
`a time according to selecting a bit for addition to a bin that
`is the least expensive in additional power needed. Because
`the bit added represents a chunk of power, we prefer to call
`the technique “ice cube filling” instead of a more smooth
`“water pouring” analogy used by Bingham. The “waterfall,”
`bit “pouring,” or even the “ice cube filling” technique for
`allocating bits to tones of a tone or frequency power spec-
`trum has been practiced for years to advantage. Total power
`is the primary constraint considered in allocating bits to
`tones in these approaches. However, as these types of
`techniques have become more predominant, problems have
`evolved. For example, these approaches do not take into
`consideration the allocation of a maximum or minimum
`number of bits to each tone or frequency bin as will be
`further described herein or consideration of a power mask
`for each tone as will be defined herein. These additional
`constraints can be design imposed or imposed by the stan-
`dard under which the techniques must operate (such as
`A.N.S.I. standard T1.413-1995) Thus, there has been felt a
`need to develop other methods for allocating bits to a power
`spectrum.
`
`SUMMARY OF THE INVENTION
`
`In accordance with the principles of the present invention,
`bits are allocated to tones by calculating the maximum
`number of bits per each tone. Then bits are allocated on a
`tone by tone basis depending on the maximum power at
`which each tone can be transmitted. Once the bits are
`allocated, then, the total maximum power level for the tone
`power spectrum is calculated. If that power level is not
`exceeded, then, the bit allocation process is complete and the
`bits may be transmitted. On the other hand, if the total power
`level has been exceeded, bits are selectively removed from
`tone or frequency bins until the total power level is no longer
`exceeded. The first bit that is removed according to one bit
`removal alternative is that bit that saves the most amount of
`power. For example and referring to FIG. 1, it may be a bit
`at the tone, a+3f, or one at the tone, a+6f, depending on
`which of these saves the greater amount of power. If the total
`power level is now no longer exceeded, the process of bit
`removal ends. On the other hand, if the total power level is
`still exceeded, another bit is removed, likewise having the
`greatest remaining power savings and so on until the total
`power level is no longer exceeded.
`In an alternative bit removal process, a bit for removal is
`searched for whose power level value just decreases the total
`power level to be just less than the maximum total power
`level for the total
`tone spectrum. While the transmitted
`power level will be a maximum and so somewhat more
`efficient than the first alternative approach to bit removal, it
`is believed that determining which bit to remove becomes a
`more computationally intensive process and is thus less
`preferable than the first alternative discussed above at
`present.
`In summary, the algorithm briefly described above for
`allocating bits in a multi-tone modulation process permits
`
`Dish
`Exhibit 1015, Page 7
`
`

`
`6,134,274
`
`3
`the consideration of additional constraints, operates faster
`and generally requires fewer computations than the water
`pouring or ice cube filling approaches of the prior art.
`These and other features of the present invention will be
`better understood through reference to the drawings and the
`following detailed description.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a drawing for describing the prior art technique
`of bit allocation in a multi-tone modulator of “pouring” bits
`on tones or into frequency bins until a maximum power level
`P (P1 or P2) for the entire spectrum (analogously, a water
`level) is exceeded.
`FIG. 2A is a functional block diagram of a typical discrete
`multi-tone modulator or transmitter according to the prior art
`(taken from T1.413-1995) in which, to practice the present
`invention, the tone ordering, gain scaling and IDFT modu-
`latio11 blocks are modified to practice the present invention
`and FIG. 2B is a functional block diagram taken from the
`same reference of a typical receiver/demodulator.
`FIG. 3 is a flowchart of the algorithm of the present
`invention, showing a method of allocating bits first to fill up
`each channel according to a maximum number of bits and a
`maximum power per channel and then, if a total power level
`(power budget) for the entire spectmm is exceeded, remov-
`ing bits one at a time until the total power level permitted is
`no longer exceeded.
`FIG. 4 shows the application of the present invention to
`a typical power mask and tone or bin arrangement with
`increasing frequency versus power where 7>< represents the
`power for three bits at frequency a+f.
`
`DETAILED DESCRIPTION
`
`The present invention will now be described with refer-
`ence to FIGS. 2—4. Referring to FIG. 2A, there is shown
`respectively an ATU-C transmitter whose reference diagram
`is taken from A.N.S.I. standard Tl .413-1995. ATU-C refers
`
`to an Asymmetric Digital Subscriber Line (ADSL) Trans-
`mitter Unit at a Central ofiice. A corresponding remote or
`subscriber unit (ATU-R) would have similar oomponents
`and is not shown or described herein. The ATU-C typically
`is utilized on non-loaded high capacity twisted pair cables
`which may be utilized for transmitting several megahertz of ,
`spectral bandwidth. In FIG. 2A, there is shown an expanded
`functional block diagram of the transmitter portion. FIG. 2B
`provides a functional block diagram of a receiver portion. A
`multiplexer/sync control unit 200 provides the interface to
`the digital network 110. Various high speed data rate links _
`ASO, AS], AS2 and AS3 at multiples of 1 .536 Mbits/sec are
`provided toward digital network 110. In particular, each AS
`link represents an independent downstream simplex
`(unidirectional downstream) bearer of data traffic. Lower
`speed data services are also shown and represented by LSO
`(16 or 64 kbits/sec), LS1 (160 kbits/see) and LS2 (384 or
`576 kbits/sec). Each LS link may represent a duplex bearer
`(bi—directional) carrying both downstream and upstream
`traffic or, in the alternative, a unidirectional simplex bearer.
`For a more thorough understanding of the Figure, the reader
`is encourged to study ANSI T1.413—1995, incorporated by
`reference as to any subject matter deemed essential to an
`understanding of the present invention.
`CRC 205 and CRC 210 represent cyclic redundancy
`check in each direction of transmission. Scrambler and
`forward error correction 215, 220 represent scrambling and
`forward error correction in each direction of transmission.
`
`4
`Interleaver 225 provides a data interleaving function as is
`further described in A.N.S.I. T1413-1995,
`incorporated
`herein by reference as necessary. Tone ordering function 230
`provides tone selection and control functions as are also
`described by A.N.S.I. T1.413—1995. Constellation encoder
`(if used) and gain scaling functions are represented by block
`235. The inverse discrete Fourier transform (IDFT) function
`applied for data modulation is represented by block 240.
`Two data directions are shown coupling IDFT 240 and
`output parallel to serial buffer 245 where a cyclic prefix is
`added to each data frame. Finally, a digital
`to analog
`converter and analog signal processing function are repre-
`sented by block 250 which interfaces the subscriber facility
`125, as indicated above, typically a high capacity twisted
`wire cable pair.
`invention is preferably implemented at a
`The present
`controller (not shown) for the blocks entitled tone orderer
`230, gain sealer 235 and IDFT 240 or as a component
`alogirthm or hardware implementtion within one or more of
`those blocks in combinaiton. Within a controller of these
`blocks, typically the decision has been made in the past to
`allocate bits to tones according to the prior art techniques
`described above known variously as water pouring,
`waterfalling, ice cube filling and the like. The decision has
`been made as described above with respect to the discussion
`of FIG.
`1
`in the Description of the Related Arts section.
`According to the present invention, the following con-
`straints are considered first:
`the maximum number of bits
`allowed in each tone or frequency bin for transmission and
`the maximum power to be transmitted in each bin (or power
`mask). Then, the total power constraint (power budget) is
`applied and, if necessary, bits are removed according to a bit
`removal process.
`The maximum number of bits per bin is calculated first
`according to prior art techniques (FIG. 1) and depending
`_ only on the power mask constraint. First the gain—to—noise
`ratio, GNR,
`is calculated in an initialization period or
`periodically as will be further described below. Then, the
`maximum number of bits that can be allocated to each bin
`is calculated. This computation is done from a relationship
`between the number of bits (bk) to be transmitted in a bin k
`and the power needed to transmit that many bits (bk) in bin
`number k. For this calculation, the power mask value in bin
`k is used as the amount of power available in bin k. The
`overall power constraint comprises two components, an
`overall constraint
`that establishes a total constraint, for
`example, of 100 milliwatts on the cable pair, but, more
`importantly at this point in the algorithm, a total power limit
`calculated for each tone or frequency. For example,
`the
`power limit for frequencies or tones between 0 and 200
`kilohertz must be less than 40 dBm/Hz (a power level
`referenced to one milliwatt over 1 Hz bandwidth). Above
`200 kHz (to frequencies in the megahertz of spectrum), the
`constraint may be -34 dBm/Hz. This power mask may be
`dictated by the standard used in a particular country irnple-
`menting the standard (such as A.N.S.I. standard T1 .413-
`1995). The power mask may also be a design constraint
`intentionally imposed by a modem designer for some other
`reason. For example, a designer may intentionally impose a
`constraint that no more than n bits are to be transmitted on
`transmit channel frequency, a+10f Similarly, the designer
`may impose a constraint that a minimum (or maximum)
`number of bits (or no bits) must be transmitted on a
`particular tone or frequency. The individual
`tone or fre-
`quency constraint
`is applied first,
`then,
`the total power
`constraint (the power budget) is applied.
`Once all the transmit frequency or tone bins are filled with
`bits and may be overflowing from following the constraint
`
`Dish
`Exhibit 1015, Page 8
`
`

`
`6,134,274
`
`6
`ing one bit in each frequency bin at step 350. Algorithm
`efficiency can be achieved by employing a partial sorting
`technique that finds the array eleme11t with the maximun1
`power saved without resorting to further sorting the array.
`The algorithm calculates the cost of the last bit (in terms of
`power saved by removing one bit) in each bin and then
`removes the bit from the bin that is the most expensive in
`terms of the additional power. This process 355, 360, 365 is
`continued until the total power level consumed is no greater
`than the total power budget, for example, of I00 milliwatts
`at step 365. Finally at step 375, the algorithm is done (the
`allocated bits may be transmitted).
`The process of allocating bits to frequency bins (per FIG.
`3) should be repeated periodically during the day as condi-
`tions change. Traffic, for example, slows in the early morn-
`ing hours, so noise decreases and data transmission ca11
`reach maximum levels. The character of traflic on a given
`cable pair may change from, for example, voice traffic to
`data traffic. Even if data traffic is assumed, the data carrying
`demand may change, for example, in an available bit rate or
`variable bit rate kind of data scenario. Thus, it is recom-
`mended that the bit allocation process be performed at least
`twice a day, and, it may be advantageous to perform the bit
`allocation procedure as frequently as every minute to take
`advantage of predictable, periodic changes in traflic patterns.
`A review of the following will assist in understanding the
`bit-by-bit allocation and bit removal process briefly
`described above from reference to FIG. 3. The relationship
`between the number of bits in a frequency bin and the power
`needed to transmit that number of bits by uncoded quadra-
`ture amplitude modulation (QAM), for a specified bit error
`rate (BER) at a receiver, for which
`
`3 N
`
`k
`
`is the measured profile, where g is the channel gain and N
`is the noise at frequency k is given by the following
`expression:
`
`KNk
`
`= 2" -1
`<
`k
`
`Ek
`
`> mac
`
`where:
`
`bk is the number of bits carried in frequency bin k, Ek is the
`power required in bin k to transmit the bk bits, g,/N,, is the
`measured gain to noise ratio in bin k.
`K is given by:
`
`where Pg is the error probability given by:
`
`P-41
`K’
`[
`
`1
`2
`-V/2T_1Q51\JTC‘-,
`
`Nk=Noise Power
`In the above equations, PE is the bit error rate (BER), N8 is
`the number of nearest neighbors, and the Q—function, Q(x) is
`defined as the partial integral of the normal distribution
`function as follows:
`
`5
`of filling the bins until their individual power level is met,
`the total power constraint (or power budget for all tones), for
`example, of 1(l0 milliwatts is applied. This 100 milliwatt
`total maximum power constraint
`is the total maximum
`power level for bit
`transmission on all
`the frequencies
`utilized where the 100 milliwatts parameter is dictated by
`the A.N.S.I. standard. Following another standard, the maxi-
`mum total power level (or power budget) may be different.
`If the total maximum power is not exceeded,
`then,
`the
`algorithm is complete. On the other hand, if the total power
`lin1it is exceeded, then a bit removal process follows.
`According to a presently preferred bit removal process,
`bits are removed according to the most power saved by its
`removal. The first bit removed then is the bit from the
`frequency bin with the most power saved in comparison
`with the bits of all other frequencies or frequency bins, anc
`the corresponding power saved is subtracted from the tota
`power. If the total power constraint is still exceeded after
`removal of the first bit, the next most power consuming bi
`is removed. VVith each bit removed, the comparison with the
`total power constraint (or power budget) is made until the
`power constraint is no longer exceeded and the algorithm is
`done. Referring to FIG. 1, if a power level P1 is the presen
`power level, one may select the bit from bin a+3f as the mos
`power consuming bit. After that bit is removed, and if the
`total power level is still exceeded, the next bit that may be
`removed may be a bit from the bin a+6f Since the approach
`to bit removal suggested here removes chunks of power, i
`may come to be called an ice cube removal technique.
`Having briefly described the algorithm of the presen
`invention, the algorithm will be further explained in con-
`siderable detail with reference to FIGS. 3 and 4. The
`example power mask of -40 dBn1/Hz changing to -34
`dBm/Hz at 200 kilohertz is shown at top. Aone dimensiona
`matrix for N frequencies where N is typically around 255
`different frequencies (for A.N.S.I. T1.413-1995) is formec
`and stored in memory. Each entry in the matrix is the
`maximum number of bits for that frequency. The algorithm
`of the present invention first computes the bit distribution (or
`allocation) within the constraints of the power spectrum
`mask shown in FIG. 4 and the maximum number of bits in
`a bin, but without
`the total power constraint (or power
`budget). Initialization step 300 to final bin step 335 of FIG.
`3 comprise the initial steps of allocating bits to frequencies.
`The bit allocation steps for allocating bits to a particular
`frequency bin 300-335 take into consideration constraints of
`1) the maximum number of bits allowed in each bin and 2)
`the maximum power level permitted for that frequency (for
`example, by calculating a power level from the constraint
`-40 dB1n/Hz for frequencies less than 200 kilohertz and -34 I
`dBm/Hz for frequencies greater than 200 kilohertz). The first
`constraint may be set by a modulator designer divorced from
`a standard. It may be set as a minimun1 or maximum number
`of bits per frequency or both (i.e. a range of permissible
`number of bits).
`Then, the total power needed to transmit the number of
`bits is calculated at step 340. If the total power required is
`less than the power budget (for example, 100 milliwatts),
`then the bit allocation function is necessarily completed. If
`the total power is greater than the budgeted power at step
`345,
`then the algorithm needs to reduce the bits to be
`transmitted in order to operate within the power budget
`constraints by following steps 350-365.
`In order to achieve the objective of reducing the bits
`transmitted to satisfy the maximum total power constraint,
`the algorithm first sorts the array of power saved by remov-
`
`Dish
`Exhibit 1015, Page 9
`
`

`
`6,134,274
`
`Ql:x,I:r [L-2
`x
`«/1171
`
`Now consider a code gain value of G6 to apply an effective
`amphfication factor in Eq. 1.
`
`The above equation can be inverted to express the power in
`terms of the number of bits as follows:
`
`E, [bkbizs] = ab‘ -1)-[
`
`KM
`35’/(G,
`
`]A(-22»; _ Uwk
`
`Eq. 3
`
`The power needed to transmit one additional bit in bin k, that
`already contains bk bits, for the K determined by the desired
`P, ca11 be derived to be:
`
`AF? : F_'k[(l;k + l)/zirs] — Fk U7k]IifS]
`
`= [(2% —1;»—<2”* — mm
`
`Eq_ 4
`
`This quantity is also the power that would be saved if the
`number of bits in bin k is reduced from bk+1 bits to bk bits.
`In other words, if the bin contains b,, bits, then the power
`saved by removing one bit from that bin is equal to the
`following:
`
`AE,f = wk -2“: -1
`
`Eq- 5
`
`’
`
`.
`
`This relationship leads to two different bit allocation
`algorithms:
`1. Each additional bit in a particular bin requires twice the
`amount of power needed as for the last bit that was added to
`the bin (briefly refer to FIG. 4 for seeing how each new bit
`at a given frequency costs twice the previous power). That
`is, from equation 4 above, if bk is increased by 1 to (bk+1),
`then AEA, is doubled. Therefore, one version of a bit alloca-
`tion algorithm is to calculate the power needed to add one
`more bit to each of the bins, then add a bit to that bin which
`requires the least amount of incremental power for the
`additional bit. The bit added is the least expensive bit in
`terms of incremental power needed. Then, one n1ust recal-
`culatc the power needed to add one more bit to this bin and
`then continue adding the least expensive bits to bins at each
`incremental stage, until the budgeted power is used up or
`any one of the constraints, maximum number of bits or
`maximum power spectrum mask is met. An algorithm fol-
`lowing this strategy is suggested by Bingham except that
`Bingham does not consider the additional constraints of
`transmit power spectrum mask and the maximum/minimum
`number of bits to be transmitted in one frequency channel.
`2. The second version of the algorithm is based upon
`removing bits. First, fill each frequency bin with the lesser
`of either the maximum allowable number of bits in one bin
`or the number of bits in one bin that corresponds to trans-
`mitting the maximum allowable power as prescribed by the
`power mask. Perform this bit allocation without any con-
`sideration for the total power budget (steps 300-335). Then
`sum the power required over all the bins (step 340). If the
`
`8
`total power is greater than the budgeted power, then remove
`bits one at a time until the power budget is met (steps
`350-365). For example, remove bits one at a time in an order
`that corresponds to removing the most expensive bit in terms
`of power saved.
`The algorithm that is a subject of the present invention is
`in accordance with the second approach. The steps in this
`algorithm again are as follows:
`1 . Steps 305-315. For each k and according to equation 2,
`compute the maximum number of bits that can be transmit-
`ted within that bin subject to the two constraints that the
`power in the bin must be no greater than P_maskk and that
`the number of bits can be no greater than bmax. This is
`achieved by substituting P_maskk for Ek in Eq. 2 to calcu-
`late b_m askk and using the smaller of bum, and b_maskk as
`the number of bits in bin k. If bk is less thanbmm, then use
`b,,=0, where bmm is the minimum number of bits (other than
`0 bits) to be transmitted in any bin.
`bk=MIl\'(b_mask,(, bmwc)
`
`Eq. 6
`
`,, to the sum of
`
`2. Steps 330-335. Calculate the value of Ek for all k
`according to equation 3.
`mm
`3. Step 340. Set the total power used, E
`all values of E,_,.
`then bit allocation as
`4. Step 345. If E,O,,,,<P_budget,
`calculated above is complete and go to step 12. On the other
`hand, if E,o,,,,<P_budget, then go to step 5.
`5. Step 350. Compute the array of 66 Ek for all k
`according to Eq. 5, using the value of bk in bin k, as
`calculated in step 1.
`6. Step 350. Sort the array of AE., in descending order so
`that the bin element with index=1 corresponds to the bin that
`would yield the largest savings in power if one bit from that
`bin is removed. The sorting operation needs to be performed
`only initially. For subsequent steps, only the value of one bin
`changes and the bin that changes value will be pushed into
`the appropriate new position in the array in step 10, below.
`In the following steps, the subscripts refer to the sorted
`array.
`7. Step 350. Reduce the number of bits in bin index=1 by
`one.
`
`8. Step 355. Reduce the value of EM“, by AE1.
`9. Step 355. Calculate the new value of AE1 as per Eq. 5
`using the value of bl reduced by 1. Note that the new value
`of AE1 is half the old value of AE.
`10. Step 355. Insert element 1 (the first element in the
`array) to the appropriate new position in the array of
`descending values of incremental power as determined by
`the new and smaller by half value of AE1. After this insertion
`in the array, the first element in the array again refers to
`another bin that would save the largest amount of power by
`the removal of one bit from that frequency bin. Note that the
`first element even after being reduced by the factor of 2 in
`step 6 may still remain in the first position, even after
`re-ordering, if the original value of AEl was greater than
`twice the value of the second element in the array.)
`11. Step 365. Go to step 5.
`12. Step 375. Exit algorithm. Depending on the environ-
`ment and circumstances, the bit allocation algorithm should
`be periodically performed within a twenty—four hour day.
`Conditions such as amount and type of telecommunications
`traffic change during the day as do external noise influences
`such as radio broadcast stations and the like.
`The algorithm detailed above will determine the maxi-
`mum number of bits that can be transmitted in one DMT
`
`symbol (for example, 8 bits) since the algorithm expends
`power in the most efficient way. Moreover, the algorithm
`
`Dish
`Exhibit 1015, Page 10
`
`

`
`6,134,274
`
`9
`also applies the constraints that ought to be applied in a
`practical implementation of the ADSL modem using DMT
`modulation technology. That is, the constraints consisting of
`power spectrum mask, the limits on the minimum or maxi-
`mum r1un1ber of bits or range of bits to be transmitted in one
`frequency bin and the discrete levels of power required to
`transmit integer bits.
`FIG. 4 is a graph of signal power and the individua
`frequency power constraint mask. At left, an exemplary bi
`allocation for the frequency bin a+f is shown whereby the
`first bit has a power level x, but with the addition of the nex
`bit, twice the power level is added or 2x. With the third bit,
`twice the cumulative power level is added again or 3>< more
`for a total of six times the power witl1 three bits added. A
`the top of the graph is shown the power mask constraint tha
`no power level on any given frequency below 200 kilohertz
`should exceed -40 dBm (where n1 is one milliwatt). No
`power level on frequencies above 200 kilohertz shoulc
`exceed -34 dBm per A.N.S.I. standard T1.413-1995.
`Thus there l1as been shown and described a method an:
`apparatus for allocating b