IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 43, NO. 2/3/4, FEBRUARY /MARCH/ APRIL 1995
`
`773
`
`A Practical Discrete Multitone Thansceiver Loading Algorithm for Data
`Thansmission over Spectrally Shaped Channels
`
`Peter S. Chow, John M. Cioffi, and John A.C. Bingham
`
`.4bstract- In this paper, we present a finite-granularity, load(cid:173)
`ing algorithm for a Discrete Multitone (DMT) modulation sys(cid:173)
`tem. The proposed algorithm offers significant implementa(cid:173)
`tional advantages over the well-known water-pouring method
`and the earlier Hughes-Hartogs algorithm, while typically suf(cid:173)
`fering only negligible performance degradation relative to the
`optimal solution. We also present simulation results of this
`loading algorithm applied to the newly proposed Asymmetric
`Digital Subscriber Lines (ADSL) service.
`
`I. INTRODUCTION
`In recent years, various digital subscriber line (DSL) [l]
`and high-speed voice-band modem applieations [2] have
`generated a tremendous amount of research interest in de(cid:173)
`signing high performance, yet cost effective, digital data
`transmission systems. One extremely efficient modulation
`and equalization technique that is particularly well suited
`for these types of applications is Discrete Multitone modu(cid:173)
`[3], [4], and [5)). A crucial aspect in the design of
`lation
`a DMT system for data transmission over spectrally shaped
`channels is the need to optimize the system transmission
`bandwidth through an optimal loading algorithm. In this
`paper, we present a practical and efficient DMT loading
`algorithm.
`
`II. A DMT LOADING ALGORITHM
`
`It has long been known that the capacity-achieving en(cid:173)
`ergy distribution for a spectrally shaped channel corre(cid:173)
`sponds to a "water-pouring" distribution [6]. However,
`while the water-pouring energy allocation will indeed yield
`the optimal solution, it is often difficult to compute, and
`it tacitly assumes infinite granularity in constellation size,
`wl:Uch is not realizable. One known finite-granularity mul(cid:173)
`ticarrier loading algorithm is the Hughes-Hartogs algo(cid:173)
`rithm(see [7]). Unfortunately, the Hughes-Hartogs algo(cid:173)
`rithm is very slow for applications like ADSL, where a large
`number of bits (in the range of 400 to 2000+) will be con(cid:173)
`tained in each DMT symbol and transmitted over a large
`number of subchannels (typically 256). As an alternative
`to Hughes-Hartogs, we propose the following iterative al-
`
`Paper approved by Paul H. Wittke, the Editor for Communication The(cid:173)
`of the IEEE Communications Society. Manuscript received September
`1993; revised May 4, 1994 and September 12, 1994. This research was
`supported in part by a National Science Foundation Presidential Young
`Investigator award ( l63C856) with matching funds from Bell Communica(cid:173)
`tioJJS Research and Apple Computers, and a National Science Foundation
`graduate fellowship.
`P.S. Chow is formerly with Information Systems Laboratory, Stanford
`University, Stanford, CA 94305 and currently with Amati Communica(cid:173)
`tions Corporation, Mountain View, CA 94040.
`.J.M. Cioffi is with Information Systems Laboratory, Stanford Univer(cid:173)
`Stanford, CA 94305, and also with Amati Communications Corpo(cid:173)
`Mountain View, CA 94040.
`J.A.C. Bingham is with Amati Communications Corporation, Mountain
`View, CA 94040.
`IEEE Log Number 9410871.
`
`gorithm. This algorithm consists of three main sections. It
`first finds the (approximately) optimal system performance
`margin, "lrnargin 1, then it guarantees convergence with a
`suboptimal loop, and lastly it adjusts the energy distri(cid:173)
`bution accordingly on a subchannel-by-subchannel basis2 .
`Algorithmically, this procedure can be summarized as fol(cid:173)
`lows:
`l. Compute
`ra-
`signal-to-noise
`subchannel
`tio, SNR(i), Vi, assuming that all subchannels are
`used with a normalized energy level of£( i) = 1 Vi.
`2. Let /margin = 0 (dB), IterateCount
`0, and
`U sedCarriers = N, where /margin is the current sys(cid:173)
`tem performance margin, and N is the maximum num(cid:173)
`ber of usable carriers.
`3. For i = 1 to N, calculate b(i), b(i), diff(i), and
`U sedCarriers according to:
`
`.
`b(i) = log2(l + r
`
`SNR(i)
`. (dB))
`+/margin
`
`b( i)
`
`round[b(i)J
`
`dif f(i)
`
`b(i) - b(i)
`
`(1)
`
`(2)
`
`(3)
`
`UsedCarriers -1 (4)
`If b(i) =0, UsedCarriers
`where r in Equation (1) is the "SNR gap" in the well(cid:173)
`known "gap approximation" [8].
`4. Let Btotat = I:f':1 b( i). Stop and declare bad channel
`if Btotal = 0.
`5. Compute new /margin according to:
`
`~{margin
`
`/margin + 10 [0910(2 Vs"1Carri<rs )
`
`Bt<ltai-Btarget
`
`'
`
`(5)
`
`where Btarget is the desired number of bits per DMT
`symbol.
`IterateCount + 1.
`6. Let IterateCount
`-:/:- Btarget and lterateCount < MaxCount,
`7. If Btotal
`let U sedCarriers = N and go to step 3, else go to
`step 8.
`8. If Btotal > Btarget, then subtract one bit at a time
`from b( i) on the carrier that has the smallest dif f ( i),
`adjust dif f(i) for that particular carrier, and repeat
`until Btotal
`Btarget.
`9. If Btotal < Btarget, then add one bit at a time to b( i) on
`the carrier that has the largest dif f(i), adjust dif f(i)
`for that particular carrier, and repeat until Btotal =
`Btarget·
`
`1System performance, or noise, margin is defined as the additional
`amount of noise (in dB) that the system can tolerate, while still achieving
`the minimum desired bit error rate requirement.
`2The final energy adjustment section is only used when the transmission
`system is constrained by the total transmit power,
`0090-6778/95$4.00 © 1995 IEEE
`
`CSCO-1032
`Cisco v. TQ Delta, IPR2016-01020
`Page 1 of 3
`
`

`

`774
`
`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 43, NO. 2/3/4, FEBRUARY /MARCH/ APRIL 1995
`
`10. Adjust input energy distribution accordingly so that
`Pe(i) = Pe,target Vi given the bit allocation b(i). At
`the end of this operation, the resulting transmit power
`mask will no longer be perfectly flat, but rather the
`transmit power mask will have a saw-tooth shape with
`approximately a 3 dB peak-to-peak deviation due to
`the integer bit constellation constraint.
`11. Scale final energy distribution for all used carriers
`with a common scaling factor so that the total energy
`level, ftotal, equals to the target energy level, ftarget·
`This common scaling factor is equivalent to the final
`system performance margin at the specified bit error
`rate.
`In essence, steps 1 to 7 will iteratively find the appro(cid:173)
`If the algo(cid:173)
`priate system performance margin, /margin·
`rithm does not converge after MaxCount iterations, con(cid:173)
`vergence is forced with steps 8 and 9. Lastly, steps 10
`and 11 fine tune the energy distribution on a subchannel(cid:173)
`by-subchannel basis to assure equal and optimal system
`performance margin over all used subchannels at the spec(cid:173)
`ified bit error rate (BER). FUrthermore, for an uncoded,
`zero-margin system with a BER of 10- 1 , the SNR gap, f,
`in the calculation of b( i) in step 3 above is approximately
`9.8 dB3 .
`While this algorithm may be slightly suboptimal relative
`to the Hughes-Hartogs algorithm at times4 , it will typically
`converge much faster than Hughes-Hartogs for applications
`like ADSL. Unlike Hughes-Hartogs, whose average running
`time is proportional to 0 (Btotal x N), the worst case run(cid:173)
`ning time for our proposed algorithm is proportional to
`0 (M axCount x N + 2N). Based on actual system imple(cid:173)
`mentation with commercial DSP chips, it has been found
`that the number of iterations, IterateCount, necessary to
`bring this algorithm to convergence over real ADSL loops is
`no more than 10; i.e, M axCount = 10 will suffice. FUrther(cid:173)
`more, this algorithm offers the added advantage of no ad(cid:173)
`ditional penalty in terms of execution time when we reduce
`the granularity of constellation size from integer number of
`bits to fractional number of bits, say half bit increments.
`The running time for Hughes-Hartogs algorithm, on the
`other hand, will be doubled with half bit constellation sizes.
`More details on the general conditions for convergence on
`our proposed algorithm can be found in (9].
`To illustrate the operation of this algorithm, in Figure
`1 we plot the received SNR curve for ADSL canonical test
`loop 95 [10] with 100 mW of input power in the presence
`of 49 ADSL far-end crosstalkers and AWGN. We have as(cid:173)
`sumed a sampling rate of 2.048 MHz, a lower bandedge
`
`3The SNR gap is a convenient single-parameter characterization of a
`transmission system, and it is a function of the chosen coding scheme, the
`target BER, and the desired minimum system performance margin. In
`particular, the SNR gap effectly estimates the difference between channel
`capacity and the actual achievable rate of a transmission system.
`4In fact, often the two algorithms will yield the same solution, depending
`on the actual line and noise scenario.
`5 ADSL canonical test loop 9 consists of a segment of (3000 ft/26 AWG)
`wire, followed by a (1500 ft/26 AWG) bridged tap, followed by a segment
`of (6000 ft/26 AWG) wire, followed by another (1500 ft/26 AWG) bridged
`tap, followed by a segment of (1500 ft/26 AWG) wire, and followed by a
`last (1500 ft/26 AWG) bridged tap.
`
`ADSL Loop #9 SNR Plot - self-FEXT + AWGN
`
`10
`
`o'-~~-'--~~-"-~~-'-~~~~~~~~---"
`0
`10
`12
`
`Frequency (Hz)
`
`xl05
`
`Fig. 1. ADSL Loop 9 Received SNR Curve with 49 ADSL FEXT Dis(cid:173)
`turbers + AWGN
`
`of 40 kHz, and a FFT size of 512. The frequency domain
`"ripples" are due to unterminated bridged taps. In Figures
`2 and 3, we show the resulting bit and input power dis(cid:173)
`tributions, respectively. The data rate for this particular
`
`ADSL Loop #9 Bit Distribution
`
`Carner Number
`
`Fig. 2. ADSL Loop 9 Bit Distribution with 49 ADSL FEXT Disturbers
`+AWGN
`
`simulation is 1.728 Mbps, which corresponds to a (216,200)
`Reed-Solomon coded transmission at a raw data rate of 1.6
`Mbps.
`
`III. APPLICATIONS AND RESULTS
`We now apply the loading algorithm presented earlier
`to the provisioning of ADSL service over copper twisted
`pairs. We will focus our simulation efforts on the ADSL
`downstream, or the high speed, direction of transmission,
`where the data rate is in the range of 1.6 Mbps to 6.4+
`Mbps, and the required BER is 10-7 (see (11]). The ADSL
`environment introduces a variety of impairments, includ(cid:173)
`ing ISI, AWGN from a number of possible sources, far-end
`crosstalk (FEXT) from adjacent twisted pairs within the
`same binder group, and impulse noise [12]. For the sim(cid:173)
`ulations, we will assume an AWGN floor of -143 dBm/Hz
`
`CSCO-1032
`Cisco v. TQ Delta, IPR2016-01020
`Page 2 of 3
`
`

`

`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 43, NO. 2/3/4, FEBRUARY /MARCH/ APRIL 1995
`
`775
`
`ADSL Loop #9 Input Power Distribution
`
`as the optimal water-pouring solution with infinite granu(cid:173)
`larity in constellation size, as long as we adjust the input
`energy appropriately on a subchannel-by-subchannel basis.
`
`[I)
`
`[2]
`
`[3)
`
`[4)
`
`[5)
`
`[6)
`
`[7]
`
`[8)
`
`[9)
`
`[10)
`
`[11)
`
`[12]
`
`REFERENCES
`J. W. Lechleider. High Bit Rate Digital Subscriber Lines: A Review
`of HDSL Progress. IEEE Journal on Selected Areas in Communica(cid:173)
`tions, 9(6):769-784, August 1991.
`CCITT Study Group XVII. Technical Contributions and Recom(cid:173)
`mendations for the Standardization of V.fast Family of Modems.
`Period: 1989-1992 .
`J.A.C. Bingham. Multicarrier Modulation for Data Transmission :
`An Idea Whose Time Has Come. IEEE Communications Magazine,
`28(5):5-14, May 1990.
`I. Kalet. The Multitone Channel. IEEE Transactions on Communi(cid:173)
`cations, 37(2):119-124, February 1989.
`A. Ruiz, J.M. Cioffi, and S. Kasturia. Discrete Multiple Tone Modu(cid:173)
`lation with Coset Coding for the Spectrally Shaped Channel. IEEE
`Transactions on Communications, 40(6):1012-1029, June 1992.
`R.G. Gallager.
`Information Theory and Reliable Communication.
`Wiley, New York, NY, 1968.
`D. Hughes-Hartogs. Emsemble Modem Structure for Imperfect
`Transmission Media. U.S. Patents Nos. 4,679,227 (July 1987),
`4,731,816 (March 1988) and 4,833,706 (May 1989).
`G.D. Forney Jr. and M.V. Eyuboglu. Combined Equalization
`and Coding Using Precoding.
`IEEE Communications Magazine,
`29(12):25-34, December 1991.
`Peter S. Chow. Bandwidth Optimized Digital Transmission Tech(cid:173)
`niques for Spectrally Shaped Channels with Impulse Noise. PhD the(cid:173)
`sis, Stanford University, May 1993.
`K. Sistanizadeh. Proposed Canonical Loops for ADSL and Their
`Loss Characteristics. ANSI TlEl.4 Technical Subcommittiee Work(cid:173)
`ing Group Contribution, (91-116), August 1991. Montreal.
`P.S. Chow, J.C. Tu, and J.M. Cioffi. Performance Evaluation of
`a Multichannel Transceiver System for ADSL and VHDSL. IEEE
`Journal on Selected Areas in Communications, 9(6):909-919, August
`1991.
`J.-J. Werner. The HDSL Environment. IEEE Journal on Selected
`Areas in Communications, 9(6):785-800, August 1991.
`
`t :···mMJ•
`
`-3
`
`.
`
`.s-
`
`.5 .
`
`Carrier Number
`
`Fig. 3. ADSL Loop 9 Input Power Distribution with 49 ADSL FEXT
`Disturbers+ AWGN
`
`(two-sided) and 49 ADSL FEXT disturbers only. Impulse
`noise is not included in our simulation. The basic DMT sys(cid:173)
`tem that is used for simulation has a sampling rate of 2.048
`MHz and a FFT size of 512, resulting in a multicarrier sym(cid:173)
`bol rate of 4 kHz. We will compare the performance of a
`DMT system implemented with the algorithm presented in
`this paper with that of an optimized, water-pouring, DMT
`system (see [3] and [4] for example). In fact, we will further
`restrict our integer bit constellation algorithm to have at
`least 2 bits and at most 10 bits per used carrier. We also
`assume a 40 kHz lower bandedge and use two representa(cid:173)
`tive ADSL loops; namely, the 9 kft, 26 gauge loop and the
`18 kft, 24 gauge loop, with two possible data rates; i.e.,
`4.0 Mbps and 1.6 Mbps. Table I summarizes our computer
`simulation results of system performance margin. Clearly,
`
`Rate
`4.0 Mbps
`1.6 Mbps
`4.0 Mbps
`1.6 Mbps
`
`Length
`9 kft
`9 kft
`18 kft
`18 kft
`
`Gauge
`26AWG
`26AWG
`24AWG
`24AWG
`
`Water-Pour
`15.9 (dB)
`27.5 /dB)
`3.0 idB)
`20.9 (dB)
`
`Integer Bit
`15.7 dB
`27.3 dB
`1.7 dB
`20.7 dB
`
`Difference
`0.2 idB
`0.2 (dB
`1.3 (dB
`0.2 (dB
`
`TABLE I
`SYSTEM PERFORMANCE MARGIN OF WATER-POURING, 00
`
`GRANULARITY DMT VS. INTEGER BIT GRANULARITY DMT
`
`the performances of the two systems are virtually identical,
`except for the worst case scenario, where we are trying to
`transmit 4.0 Mbps over the 18 kft, 24 gauge loop, and in
`that case, we lose 1.3 dB. This degradation in performance
`turns out to be caused mainly by the 2 bit minimum/10
`bit maximum constraint that we imposed on our system.
`
`IV. CONCLUSION
`
`In this paper, we have presented a practical DMT loading
`algorithm for high speed data transmission over channels
`with severe ISI, as in the ADSL transmission environment.
`We showed, through computer simulation, that the per(cid:173)
`formance of our algorithm using only constellations with
`integer number of bits per 2D symbol is nearly as good
`
`CSCO-1032
`Cisco v. TQ Delta, IPR2016-01020
`Page 3 of 3
`
`