IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 43, NO. 12, DECEMBER 1995
`
`2941
`
`A Coded and Shaped Discrete Multitone System
`
`T. Nicholas Zogakis, Member, IEEE, James T. Aslanis Jr., Member, IEEE,
`and John M. Cioffi, Senior Member, IEEE
`
`this paper, we show how coding and constella-
`Abstract-In
`tion shaping may provide significant gains to a discrete multi-
`tone (DMT) system transmitting over spectrally-shaped channels.
`First, we present and analyze a concatenated coding scheme con-
`sisting of an inner trellis code and outer block code when applied
`to DMT modulation, and we address some of the implementation
`issues associated with this scheme. Some laboratory test results
`for a DMT prototype employing the coding scheme are presented.
`Next, we propose a method for applying Forney’s trellis shaper
`across the tones in a DMT system to realize significant shaping
`gain. To illustrate the coding and shaping gains achieved, we use
`scenarios indicative of the newly introduced asymmetric digital
`subscriber line service. By combining a powerful coding scheme,
`shaping, and DMT modulation, we arrive at an implementable
`transceiver that can provide very high data rates over spectrally-
`shaped channels.
`
`I. INTRODUCTION
`HE transmission of high-speed data over spectrally-
`
`T shaped channels can be achieved by a sophisticated
`
`technique. One
`combined modulation and equalization
`approach that has been found well suited for a number of
`new applications is the use of multicarrier modulation, and
`we focus upon a particular form of multicamier modulation
`known as discrete multitone (DMT) modulation [ 11. With this
`approach, the channel is divided into a number of independent
`subchannels in the frequency domain, and bits and power
`are allocated among the subchannels to maximize throughput.
`The primary advantage of the multicarrier approach is that the
`problem of bandwidth optimization is greatly simplified, thus
`allowing very high data rates to be achieved with reasonable
`implementation complexity.
`Given a DMT transceiver with the capability of perform-
`ing bandwidth optimization, we address the problem of the
`application of coding and shaping to the system. First, we
`present a flexible, implementable, bandwidth-efficient coding
`scheme consisting of an outer block code and inner trellis
`code operating across the subchannels, and we analyze the
`performance of this scheme for a number of realistic sce-
`narios. Implementation issues specific to DMT modulation
`
`Paper approved by E. Eleftheriou, the Editor for Equalizahon and Coding
`of the IEEE Communications Society. Manuscript received August 9, 1994;
`revised February 27, 1995.
`T. N. Zogalus was with the Information Systems Laboratory, Stm-
`ford University, Standford, CA 94305 USA. He is now with Amati
`Communications Corporation, Mountam View, CA 94040 USA (e-mail:
`zogakis@isl.stanford.edu).
`J. T. Aslanis Jr. is with Amati Communications Corporation, Mountaih
`View, CA 94040 USA (e-mail: redlands@isl. stanford. edu).
`J. M. Cioffi is with the Information Systems Laboratory, Stanford
`(e-mail: ciof f ieshannon.
`University, Stanford, CA, 94305 USA
`stanford. edu).
`IEEE Log Number 9415929.
`
`are addressed, and some laboratory test results are presented.
`Next, we show how trellis shaping may be applied across the
`tones in a DMT syslem to obtain significant shaping gain. By
`combining the proposed coding and shaping schemes, real (as
`opposed to asymptotic) coding plus shaping gains exceeding
`6.0 dB at a bit error rate (BER) of
`and 7.0 dB at a
`BER of lo-’ are achieved in the DMT system. To illustrate
`various results, we use examples from the asymmetric digital
`subscriber line (ADSL), a service proposed for providing a
`downstream data rate ranging from 1.544 Mbps to 6.4+ Mbps
`from the telephone company’s central office to the customer,
`along with a lower-speed return channel over existing copper
`twisted pair [ 2 ] .
`In Section 11, we review the concept of DMT modulation
`and establish the baseline DMT system to which we will apply
`both coding and shaping. In Section 111, we show how coding
`is applied to the syslem and analyze the coding gains possible
`with the proposed scheme. Next, in Section IV, we address the
`problem of the application of shaping to DMT modulation, and
`we evaluate the shaping gains realized for the same scenarios
`used in the coding gain analysis of Section 111. Finally, we
`summarize our results in Section V and conclude with the
`presentation of a practical multicarrier encoder structure.
`
`11. BASELINE DMT SYSTEM
`A simplified block diagram of the basic DMT transmitter
`is presented in Fig. 1 [3]. At the input to the system, the bit
`stream is partitioned into blocks of size b = RT bits, where
`R is the uncoded bit rate, T is the DMT symbol period, and b
`is the number of bits contained in one DMT symbol. The bits
`collected during the mth symbol interval are allocated among
`N subchannels or tones in a manner determined during system
`initialization, with rnore bits given to those subchannels with
`higher signal-to-noise ratios (SNR’ s). Depending upon the data
`rate and SNR function, some of the channels may not be
`assigned any bits. We let b, denote the number of bits assigned
`to the ith tone, so that b =
`b,. On subchannel i , the b, bits,
`represented by the constellation label d,,,,
`are mapped to a
`complex constellation point X,,, = f[d,,,]
`in a constellation
`of size 2ba, where .f[.] denotes the mapping operation. Next,
`a block of real time-domain samples, {x%,+}, is formed by
`performing a length N = 2N Inverse Fast Fourier Transform
`(IFFT) on the complex symbols {Xt,m, i = O , l , . . . , N - l},
`where Xo,, = 0 and {X,,, = X&--z,m, i = N + 1,N +
`2, . . . , N - 1). A cyclic prefix consisting of the last L/ samples
`of the data block { z , , ~ } is added to the beginning of the block
`to form the signal transmitted over the channel. The receiver
`
`0090-6778/95$04.00 0 1995 IEEE
`
`
`
`CommScope, Inc.
`IPR2023-00066, Ex. 1009
`Page 1 of 9
`
`

`

`2942
`
`i"
`
`k R T bus
`
`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 43, NO. 12, DECEMBER 1995
`
`Fig. 2. Coded DMT transmitter.
`
`Fig. 1. Uncodedhshaped DMT transmitter.
`
`corresponding to the transmitter illustrated in Fig. I merely
`consists of the inverse operations.
`In this paper, we assume that N and Y are chosen sufficiently
`large so that the tones are well approximated as indepen-
`dent and memoryless subchannels.' Under these conditions,
`the complex point E,, obtained at the output of the ith
`subchannel is given by Y,,, = H,X,,, + Nz,m, where H,
`represents the complex gain of the subchannel and
`is
`a sample of a complex Gaussian noise process. Hence, the
`key to analyzing the uncoded and unshaped DMT system is
`to note that each of the N subchannels may be considered
`as supporting a low-speed, memoryless, quadrature amplitude
`modulated (QAM) signal 141. We let P, = E{IXz,m12} denote
`the two-dimensional (2-D) symbol power allocated to the ith
`= E{lNz,m12} the 2-D noise variance.
`subchannel and 2,:
`With these definitions, the output S N R for the ith tone is
`given by snr, = T .
`
`P, I H , I
`A useful parameter for analyzing the DMT system's per-
`formance is the SNR gap, I', which represents the distance
`between the performance of a QAM signaling scheme and
`capacity over a memoryless channel 171, 181. Using the S N R
`gap approximation, we can relate b, to snr, by the expression
`b, = log,(l + *),
`where the SNR gap, r ( C , p Z - D ) ,
`is a function of the coding scheme C and 2-D error rate
`Pz-D. In formulating this relationship, we are assuming that
`the DMT system is designed to provide equal error rate on
`each subchannel.
`For an uncoded DMT system operating at a 2-D error rate
`of PZ-D, the SNR gap may be written as r d B ( C , P Z - D ) =
`rO,dB(PZ-D) f "im,dB, where rO,dB(PZ--D) is the "J3
`inal gap (in dB) required to meet the error rate and
`is any required system margin [4]. Using well-
`Ym,dB
`known QAM relationships, we can show that PZpD =
`4 Q ( d m ) , where Q(.) is the Gaussian probabil-
`ity of error function. When a coding scheme with gain
`Y ~ , ~ B ( C , P Z - D ) and shaping scheme with gain Ys,dB are
`applied, the SNR gap is reduced to r d B ( c , & D )
`=
`r0,dB(p2-D) + "im,dB - "ic,dB(C,P2-D) - Ys,dB and thus
`141, 181. In
`p 2 - D = 4Q(J3r(C, PZ-D)YC(C, P Z - D ) Y ~ / Y ~ )
`the remainder of this paper, we present and analyze methods
`for applying coding and shaping to DMT modulation to
`achieve large Yc,dB (C, P ~ - D ) and Ts,dB over spectrally-shaped
`channels.
`
`'See [I], [4] for a discussion of the choice of
`to reduce the length of v.
`
`and [5], [6] for methods
`
`Fig. 3. Coded DMT receiver.
`
`111. &PLICATION OF CODING
`
`A. Coded DMT System Model
`The coding scheme that we apply to the DMT system should
`have large coding gain, reasonable implementation complex-
`ity, flexibility (adaptable to data rate), and some measure of
`burst immunity. A suitable scheme for achieving all these goals
`is a concatenated coding scheme consisting of an inner trellis
`code operating across the tones as suggested in [9]-[ 111 and
`an outer block code with variable outer code parameters. The
`parameters of the outer code are determined according to the
`desired data rate and even may be determined on a channel
`by channel basis, if necessary. Figs. 2 and 3 illustrate how the
`proposed coding scheme is incorporated in the DMT system,
`where only those portions of the DMT transceiver involving
`the encoding of bits into complex symbols and the decoding '
`of complex symbols into bits are depicted.
`The binary data stream at the input to the system is first
`encoded by an outer, interleaved Reed-Solorhon (RS) code
`with code length n and information length k. In traditional
`applications, block codes result in an increase in the symbol
`rate (ie., increase in bandwidth) to maintain the same informa-
`tion rate, but for DMT modulation, the redundancy associated
`with the block code is absorbed by increasing the number of
`bits contained in each DMT symbol by a factor of n / k . As
`a result, the bit allocation algorithm makes the best tradeoff
`between bandwidth expansion, where a greater fraction of the
`N tones are used for transmission, and signal set expansion,
`where the sizes of the constellations supported by a subset of
`the used tones are increased, in distributing the additional bits.
`In contrast to the block encoder, the inner trellis encoder in
`Fig. 2 operates on the bits at the output of the bit allocation
`unit, producing a set of complex symbols that serves as
`the input to the IFFT block. The only change from a basic
`trellis encoder as defined in [12] is that the signal selector
`component must select points from different size constellations
`as the encoder operates across the tones; the convolutional
`encoder and coset selector remain the same. As a result of the
`redundancy of the trellis code, the number of bits on the ith
`subchannel is increased to b, + F, where F is the normalized
`redundancy of the code in bits per 2-D symbol.
`
`,
`
`CommScope, Inc.
`IPR2023-00066, Ex. 1009
`Page 2 of 9
`
`

`

`ZOGAKIS et al.: A CODED AND SHAPED DISCRETE MULTITONE SYSTEM
`
`2943
`
`In the receiver, depicted in Fig. 3, a single Viterbi decoder
`operates across the subchannels on the noisy constellation
`points at the output of the FFT, which is not pictured. In
`using the Viterbi decoder across the subchannels, we are
`implicitly exploiting the important fact that the subchannels are
`independent and memoryless in the DMT system. Hence, the
`gain obtained from applying the trellis code will essentially be
`the same as that obtained in an intersymbol interference-free
`environment.
`
`B. Theoretical Pegormance
`To determine the theoretical coding gain afforded by the
`codes when applied to the DMT system, we consider the
`components of the overall gain individually. During the course
`of the analysis, it will be convenient to work with 2-D
`symbol error rates, bit error rates, and RS symbol error rates,
`depending upon what part of the system is being considered.
`For simplicity, we assume that these quantities are related by
`constant factors, and we use the 2-D error rate as a common
`basis. In particular, 2-D error rates are converted to bit error
`rates by multiplying by one-half. Similarly, 2-D error rates
`are converted to RS symbol error rates by multiplying by a
`constant c, where c represents the average number of tones
`contributing bits to each RS symbol.
`With P b i t denoting the required bit error rate at the output of
`the overall system, the net coding gain is conveniently divided
`into the following components:
`the gain obtained by the RS code
`1) Yrs,dB((n, k ) , &t),
`without taking into account the penalty for the increased
`data rate.
`2) Ytc,dB( (n, k ) , P b i t ) , the gain provided by the trellis code
`at the error rate required by the RS code to achieve P b i t .
`3) Yloss,dB( (n, k ) , b), the loss incurred for increasing the
`data rate.
`The overall coding gain is computed as
`
`Yc,dB((nn, k ) i P b i t ) = Ytc,dB((n, k ) , P b i t ) + ?rs,dB((n, IC), P b i t )
`- Yloss,dB((n, k ) , b).
`Each of the coding gain components is now considered in turn.
`A RS codeword is correctly decoded
`+ r s , d ~ ((n, k ) &):
`provided it contains no more than t = L(n - k)/21 errors
`[ 131. Assuming sufficient interleaving so that the errors appear
`random at the RS decoder's input and assuming the RS
`decoder does not attempt to correct the codeword if greater
`than t errors are detected, we may relate the output RS symbol
`error rate Pr, to the input RS symbol error rate P, by
`
`(1)
`
`Pr, =
`i=t+l
`
`- 2 P:(l- Ps)n-i
`n
`
`demodulator to obtain Pb((n, k ) , & I t ) = 2 Q ( G ) , from
`which an expression for the SNR gap rrS is derived.2 Now,
`we define the SNR gap
`required for an uncoded system
`to achieve the output bit error rate P b l t as the solution to
`P b l t = 2 Q ( a ) . The gain of the RS code without taking
`into account the data rate penalty is computed as the difference
`?rs,dB((n,, k ) , Pbit) = r 0 , d B - r r s , d B .
`(3)
`In the concatenated coded system, the
`Ytc,dB((n, k ) , P b l t ) :
`2-D error rate required at the output of the trellis decoder is
`given by Pz-D = :2Pb((n, k ) , &it), where Pb((n, k ) , P b i t )
`is the bit error rate required at the input to the RS decoder
`to achieve P b l t . Given PZ-D, we determine the SNR gap
`r t c , d B ( P Z - D ) required to achieve this error rate by using the
`trellis code's performance curve. The gain of the trellis code
`is given by
`
`?/tc,dB((n, k ) , p b i t ) = rO,dB(PZ-D) - r t c , d B ( P 2 - D )
`(4)
`where rO,dB(PZ-D) is the SNR gap for an uncoded system at
`the error rate P2-D.
`Yloss,dB((n, k ) , b): TO determine the loss for the increased
`data rate associated with the RS code, we first define Pco,(b)
`as the minimum amount of power required to achieve the data
`rate b in a DMT system with a gap of 0.0 dB. This quantity
`is determined as the solution to the following optimization
`problem
`
`subject to b =
`
`b;,
`
`2=1
`
`where the ith term in the first summation is understood
`to be equal to zero if b, = 0 and snrch,, = 0. In (5),
`{b,} represents the DMT bit distribution, and snr,h,% =
`lH,I2/(2u,2) is the channel gain-to-noise function. With d(.)
`denoting the permutaiion of the subchannel indices that results
`in a decreasing sequence for snr,h,d(,), the solution to the
`optimization problem is given by
`
`The parameter u signifies the number of subchannels actually
`used for transmission and is determined by finding the largest
`such that loga(KsnrCh,d(u~) > 0. Hence, the
`integer u 5
`power distribution is simply given by a discrete version of the
`well-known water-pour distribution
`
`(7)
`
`and the minimum power by
`
`Hence, given the output bit error rate P b i t , we equate Prs =
`and iteratively solve (2) for P,. The corresponding input
`bit error rate is given by Pb((n, k ) , P b i t ) = Ps/(2c). This bit
`error rate is equated to the error rate at the output of a QAM
`
`'The factor of two in front of the &(.) function results from our assumption
`that bit error rates are one-half the 2-D error rates.
`
`CommScope, Inc.
`IPR2023-00066, Ex. 1009
`Page 3 of 9
`
`

`

`2944
`
`EEE C TRANSACTIONS ON COMMUNICATIONS, VOL. 43, NO. 12, DECEMBER 1995
`
`The loss now may be expressed as
`
`C. Integer Constraints
`The theoretical coding gain analysis provided in Section
`II1.B assumes infinite bit granularity and allows infinite con-
`stellation sizes. In a practical DMT system, the bit granularity
`is determined by the complexity of the signal selector, while
`the constellation size is limited by finite precision, nonlinear-
`ity, and timing jitter constraints. Hence, we now consider the
`coding gains realized under more practical constraints on the
`bit distribution.
`We assume that the number of bits assigned to each carrier
`must be an integer before the application of the trellis code.
`In addition, we restrict the number of bits per used tone to
`lie in the range blow 5 b, 5 b,,,,
`where blow and b,,
`are
`integers; typically,we have blow = 2. The analysis remains
`the same as in Section 1II.B except for the computation of
`yloss,dB((n, k ) , b), which is now given by
`
`Yloss,dB((nn, I C ) , b ) = i)t*ot,dB(nb/k) - p:ot,dB(b)
`(lo)
`where p&(b) is the solution to the following integer-
`constrained optimization problem
`
`rv
`
`b,
`subject to b =
`b, E {O,blow,how + 1,*..,bm,}.
`z=1
`(11)
`The solution to (1 1) is too difficult to compute in a practical
`DMT system. However, this optimization problem is closely
`related to the problem of determining the optimum bit and
`power allocation schemes for maximizing the margin of a
`DMT system at a given data rate. A practical, albeit ad-hoc,
`method for computing the DMT bit and power distributions
`is proposed in [14], and versions of this algorithm are imple-
`mented in current DMT products. It can be verified that for
`practical scenarios, the theoretical coding gains do not change
`is not too small. For instance, in the ADSL
`as long as b,,
`= 10 is usually sufficient, and b,,
`application b,,
`= 15
`covers the worst scenarios.
`
`D. Accommodation of Trellis Code Redundancy
`Unlike the situation for traditional single-carrier systems, a
`trellis-coded DMT system that allows a fractional normalized
`redundancy, T , must accommodate many different multidimen-
`sional constellation sizes. While these different constellations
`could be supported by using an algorithmic multidimensional
`encoder based on generalized cross constellations [15], [I61 or
`some other multidimensional technique, the additional com-
`plexity may be unwarranted in a practical DMT system.
`Indeed, even with an integer bit assignment, a DMT system
`based on 2N-point FFT’s effectively supports a bit granularity
`of l / N bits per 2-D symbol.
`
`Under the constraints that the bit distribution must be integer
`and that b, 5 b,,
`for both the cases of a system with and
`without trellis coding, we provide the following method by
`which a practical bit and power allocation algorithm that solves
`(1 1) can be used to determine the bit and power allocations
`for the trellis-coded DMT system:
`1) Solve (11) for n b / k bits and find u, the number of
`2) Compute utc = F, the number of tones to be used in
`subchannels required.
`
`the trellis-coded case.
`3) Sort the channel gain-to-noise ratios in descending order:
`snrch,d( ) -
`4) Set snr,h,d(,) = 0, i > utc.
`5) Set bt, = n b / k + Tutc.
`6) Solve (11) for bt, given sqr,h,d(%).
`The suboptimal approach for accommodating the trellis code
`redundancy should result in approximately the same SNR loss
`as would be expected for expanding the constellation by a
`factor of 2T on each tone. However, an exception arises when
`many of the tones are already constrained by the limitation
`of bmax. Under these conditions, the redundant bits are forced
`onto poor subchannels, leading to a degradation in the gain
`expected for the trellis code. We refer to this effect as bit-
`capping. If p;ot,dB(nb/k) denotes the required power for the
`( btc) the required
`system without trellis coding and &!ot,dB
`power for the system with trellis coding, the bit-capping loss
`incurred is given by
`
`E. DMT Coding Gain Results
`By using the analysis discussed above, we computed the
`coding gains expected at BER’s of lop7 and lo-’
`for two
`ADSL scenarios. The first scenario corresponds to a frequency-
`division multiplexed system operating at 1.6 Mbps over ANSI
`loops [ 171 in the presence of near-end crosstalk (NEXT) from
`49 digital subscriber line (DSL) disturbers. The second is
`for the case of an echo canceled system transmitting at 6.4
`Mbps over CSA loops [18] in the presence of NEXT from 10
`DSL and 24 high bit-rate DSL (HDSL) disturbers, and NEXT
`and far-end crosstalk (FEXT) from 10 ADSL disturbers. The
`configurations of the eight specific loops used in the analysis
`are given in Fig. 4, where the two numbers above each segment
`give the length of the segment in feet and the gauge of the wire
`(AWG). Based on the spectral efficiencies typically required
`for the two data rates along with simulation results, we set
`c = 2.5 for the 1.6 Mbps scenario and c = 1.5 for the 6.4 Mbps
`scenario, The parameters common to both scenarios include
`a RS information length of 5 = 200, the use of 512-length
`FFT’s, a 4.0 kHz DMT symbol rate, bit assignment constraints
`= 10, a 4.3125 kHz carrier spacing, and
`of blow = 2 and b,,
`the presence of additive white Gaussian noise (AWGN) with
`a two-sided power spectral density of -143.0 dBmIHz.
`Table I presents the maximum coding gains achieved at
`for both the cases of an applied RS
`BER’s of lop7 and lo-’
`code over GF(256) and a concatenated code consisting of an
`
`CommScope, Inc.
`IPR2023-00066, Ex. 1009
`Page 4 of 9
`
`

`

`ZOGAKIS et al.: A CODED AND SHAPED DISCRETE MULTITONE SYSTEM
`
`2945
`
`loop, rate (Mbps)
`
`ANSI 1, 1.6
`ANSI6, 1.6
`ANSI9, 1.6
`ANSI 15, 1.6
`CSA 1, 6.4
`
`7qdB
`3.5
`3.4
`3.7
`3.6
`3.1
`
`io-’ e m r rate
`1 0 P e m r rate
`RSf Wet
`RSf Wet
`RS
`RS
`n 7e,dB
`n f , d B
`n 7c.dB
`n
`226
`5.4
`212
`4.3 226
`6.4
`212
`226
`5.2 210
`4.3
`226
`6.2
`214
`228
`5.4 210
`4.5
`234
`6.4
`212
`226
`5.4
`212
`4.5
`216
`5.2
`208
`3.9
`
`228
`220
`
`6.4 214
`6.2
`208
`
`CSA 4. 6.4
`CSA 6, 6.4
`
`1 3.1
`3.2
`
`216 1 5.2
`208 1 3.9
`216
`5.3 208
`3.9
`
`218 I 6.1
`218
`6.2
`
`210
`208
`
`outer RS code and an inner 16-state, 4-D trellis code devised
`by Wei [15]. The performance of the Wei code was obtained
`by combining Monte Carlo simulation results for high error
`rates and distance spectrum analysis for low error rates to
`generate an accurate curve over a wide range of error rates
`[19]. In obtaining the DMT coding gains, we used integer bit
`distributions and accommodated the trellis code redundancy in
`the suboptimal fashion described in Section 1II.D. Also listed
`in Table I is the optimum code length for realizing each of the
`coding gains listed. From the results, we find that RS codes
`can provide over 3.0 dB of gain at a BER of lop7, while the
`concatenated code provides over 5.0 dB of gain at the same
`error rate. We note that the gains obtained for a RS(216,200)
`code, the default code specified in the ADSL standard for the
`two data rates considered, differ from the optimum gains listed
`in Table I by at most 0.35 dB.
`To confirm our coding gain analysis, we conducted labora-
`tory tests on a DMT prototype for ADSL in October, 1993 at
`Amati Communications Corporation. The Amati DMT system
`operates at a sampling rate of 2.208 MHz and a DMT symbol
`rate of 4.0 kHz. A length 512 FFT is used for modulation
`and demodulation in the downstream direction, resulting in a
`carrier spacing of 4.3125 kHz. Furthermore, a maximum of
`b,,, = 11 bits per tone is supported. We tested performance
`at an effective data rate of 6.208 Mbps over a 6 kft, 26 AWG
`loop in the presence of AWGN with two different RS codes,
`a RS(202,194) code and a RS(210,194) code. Plots of the
`data points obtained in the lab are presented in Fig. 5 along
`with solid error rate curves derived using the same analysis
`techniques as those used to obtain the results in Table I. The
`theoretical curve and set of data points on the far right of the
`graph correspond to the uncoded system, while the group of
`
`normalized snr (de)
`Laboratory results for case of AWGN and a 6 kft, 26 AWG loop.
`
`Fig. 5.
`
`curves on the far left correspond to the concatenated RS + Wei
`coded system. The middle group of curves pertain to the case
`where only a RS code was applied to the data stream.
`The correspondence between the data points and the the-
`oretical performance curves is quite good, thus verifying the
`accuracy of our anadysis. We note that the apparent coding
`gains in Fig. 5 are larger than any of the gains in Table
`I because the “uncoded” curve in Fig. 5 is actually for an
`uncoded system at the same data rate as the RS(202,194)
`coded system. In other words, all the curves in the figure
`that correspond to system performance with coding do not
`include the penalty for the addition of eight check bytes.3 The
`penalty is easily determined to be 0.8 dB in this case, and by
`subtracting 0.8 dB from the coding gains implied by Fig. 5, we
`find that the extrapolated gains are 3.1 dB for the RS(210,194)
`code and 5.2 dB for the RS(202,194) + Wei code at a BER
`of 10-7.
`
`Iv. APPLICATION OF SHAPING
`
`A. Shaping Across the Tones
`Now that a good coding scheme for achieving large
`Y ~ , ~ B ( C , P ~ - D )
`in a DMT system has been derived and
`analyzed, we turn to the problem of the application of shaping
`to achieve large Ts,dB. As in the case of trellis coding, a
`straightforward approach would be to shape the constellations
`on each of the subchannels individually, but this would require
`too much delay, storage, and complexity. Hence, we consider
`a method of applying trellis shaping [20] across the tones in
`the DMT system. For simplicity, we focus only on the 4-state
`shaper discussed in [20], and we concentrate on the case in
`which one large circular constellation is stored in memory
`with an embedded labeling scheme to support the various size
`constellations needeld on the DMT subchannels. The embedded
`labeling scheme is generated by ordering points on the half-
`integer grid Z 2 + 1(0.5,0.5) according to increasing energy
`
`3The curves involving a RS(210,194) code do include the penalty for
`increasing from 6.464 Mbps to 6.720 Mbps.
`
`CommScope, Inc.
`IPR2023-00066, Ex. 1009
`Page 5 of 9
`
`

`

`2946
`
`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 43, NO. 12, DECEMBER 1995
`
`Fig. 7.
`
`Illustration of standard and modified labeling schemes.
`
`bi-1 ,
`
`ld%-2i2isn,dh-3im, ... doim]
`I
`
`c
`
`Fig. 6. The 4-state, 2-D trellis shaper applied across the tones.
`
`and assigning larger labels to points with higher energy, where
`labels are interpreted as unsigned integers. For the interested
`reader, an algorithmic encoder that generates square and cross
`constellations with labeling schemes that work well with the
`4-state shaper is provided in [all.
`Fig. 6 illustrates the trellis shaper that is applied across the
`tones. The first step in applying the shaper is to double the size
`of the constellation on each tone. Next, the sequence of most-
`significant bits {&;'}
`of the unshaped constellation labels is
`passed through a rate one-half coset representative generator
`( H ; ~ ( D ) ) ~
`to form an initial sequence of region specifier
`for the expanded constellations. Since an
`bits { u : ; ~ , v;,";'}
`embedded labeling scheme is used, the region specifier bits
`(vp;,,, , v:;;') produced during symbol period m designate one
`of four concentric circular rings. Ths concept is depicted in
`the left-hand side of Fig. 7, where the four regions are labeled
`with the four possible values of (v:;~,v:;;').
`The sequence
`{ v g ; , , ~ ~ ; ~ ' } is subsequently modified by the modulo two
`addition of a codeword {e&, e&}
`from the rate one-half
`convolutional code C, with generator matrix G,(D) = [l +
`0' 1 + D + D2] and parity check matrix H,(D) to form the
`CB e&}. n e
`sequence {z,":,,.~,":;'} =
`CB C&,V;;;'
`b
`choice of codeword is determined by performing the Viterbi
`algorithm to search for the lowest-energy sequence out of
`an equivalence class of possible transmit sequences 1201. In
`particular, the squared magnitude of the constellation point
`
`I
`
`(13)
`may serve as the weight of a branch in the trellis for the
`shaping code, where the branch is associated with the label
`In (13), fo [.] represents the mapping of labels to
`(c,",,, e:,,).
`points in the stored constellation, and P,(b,) is the average
`2-D symbol power of a 2bs-point constellation based on the
`half-integer gnd. Hence, division by d m normalizes the
`unshaped constellation to unity energy, while multiplication by
`fl incorporates the DMT power distribution. Once a trellis
`path is chosen, a mapping operation that includes transmit
`power scaling is performed to obtain the transmitted points
`{xZ,m}.
`Before assessing the performance of shaping across the
`tones in a DMT system, it is instructive first to evaluate the
`performance of the 4-state shaper for different Jixed constel-
`lation sizes. Simulation results reported in [20] show that
`a gain on the order of 1.0 dB with respect to a "square"
`constellation is obtained for the case of a 128-point constel-
`
`'2
`O
`
`3
`
`4
`
`7
`2
`5
`6
`brts per 2D symbol
`Performance of 4-state trellis shaping code as a function of constel-
`Fig. 8.
`lation sue.
`
`8
`
`9
`
`i
`
`I O
`
`
`
`lation. However, it is not clear whether such gains may be
`achieved for small constellations for which the continuous
`approximation [ 161 does not hold. To ascertain the relationship
`between Constellation size and shaping gain, simulations were
`conducted using constellation sizes ranging from 4 to 1024
`points, and the results are presented in Fig. 8 for the shaping
`gains achieved with respect to the original, unshaped, circular
`constellation. The lower curve in Fig. 8 corresponds to the
`case in which the original embedded labeling scheme was
`maintained, whereas the upper curve was achieved when the
`labeling scheme was modified as discussed in [20] such that
`the points in the outer-most and next-to-inner-most rings were
`labeled from high energy to low energy and the two most-
`significant bits of each constellation label in the two middle
`rings were interchanged. The latter modification is equivalent
`to interchanging our definitions of regions one and two. Fig.
`7 compares the standard embedded labeling scheme (left-hand
`side) with the modified labeling 'scheme (right-hand side) for
`an arbitrary constellation size, where the arrows indicate the
`direction of increasing constellation labels within each region.
`?;he modified labeling scheme' is not compatible with the
`embedded labeling scheme that would be used to store a
`constellation in the DMT system. Moreover, creating different
`look-up tables for all possible constellation sizes is clearly
`impractical. Fortunately, the desired labeling scheme may be
`induced on a stored, embedded constellation by using the
`following algorithm to modify the signal selector.
`
`CommScope, Inc.
`IPR2023-00066, Ex. 1009
`Page 6 of 9
`
`

`

`ZOGAIUS et al.: A CODED A N D SHAPED DISCRETE MULTITONE SYSTEM
`
`2947
`
`(dl-', d2-', dl-3,
`label,
`Given an Z-bit constellation
`... , d2, d', do), first check to see whether or not I 5 4. If
`so, then the constellation point X is obtained in the normal
`,
`, ,
`I-1 dl-2 dl-3 ... d2 dl do]
`9 where fJ.1
`way: X = f,[d
`>
`>
`>
`denotes the original mapping operation. On the other hand, if
`I > 4, then the mapping is performed based on the values of
`the region specifier bits (dl-',
`as follows
`dl-ldl-2 = 00 =+ x = fo[dl-l,dl-2,dl-3,. . . ,d2, dl,dO],
`dl-ldl-2 - - 01 =+ x = jo[2-l, 2-2, d l - 3 , . . . , d2, d l , do],
`dl-ldl-2 - - 10 * x = j 0 [ Z - l , 2 - 2 , 2 - 3 , . . . , K , d l , do],
`dZ-ldl-2 - - 11 =+ x = f o [ d l - l , d l - 2 , 2 - 3 , . . . ,2, d l , do]
`where 2 is the binary complement of d. Inverse operations
`may be performed in the receiver to retrieve the original
`constellation labels.
`The dependency of the achievable shaping gain on the size
`of the constituent constellation implies that the overall shaping
`gain will depend on the DMT scenario and in particular on the
`bit and power distributions. If a separate trellis shaper were
`applied to each tone, then we c