The present invention relates to the optimization of transmission bandwidth or discrete multitone modulation (DMT), and more specifically to a discrete loading algorithm for maximizing the system performance or data rate of DMT transmission. 
The following is a list of references cited in the disclosure of this invention.  For convenience, the reference number of a prior art in the list will be included when the prior art is referred to in the following description. 
[1] J. M. Cioffi, xe2x80x9cAsymmetric digital subscriber lines,xe2x80x9d Chapter 34 of the Communications Handbook, Editor-in-Chief, J. D. Gibson, CRC Press in Cooperation with IEEE Press, 1997. 
[2] J. M. Cioffi et al.,  xe2x80x9cVery-high-speed digital subscriber lines,xe2x80x9d IEEE Commun.  Mag.,  vol.  37, pp.  72-79, Apr. 1999. 
[3] A. Ruiz, J. M. Cioffi, and S. Kasturia, xe2x80x9cDiscrete multiple tone modulation with coset coding for the spectrally shaped channel,xe2x80x9d IEEE Trans.  Commun.,  vol.  40, pp.  1012-1029, Jun. 1992. 
[4] T. M. Cover and J. A. Thomas, Elements of Information Theory.  Wiley, N.Y., 1991. 
[5] J. Campello, xe2x80x9cOptimal discrete bit loading for multicarrier modulation system,xe2x80x9d in Proc.  1998 IEEE Int.  Symp.  Inform.  Theory, MIT, pp.  193, Aug. 1998. 
[6] J. Campello, xe2x80x9cPractical bit loading for DMT,xe2x80x9d in Conf.  Rec.  1999 IEEE Int.  Conf.  Commun. ( ICC ""99), Vancouver, Canada, Jun. 1999, pp.  801-805. 
[7] A. Leke and J. M. Cioffi, xe2x80x9cA maximum rate loading algorithm for discrete multitone modulation systems,xe2x80x9d in Conf.  Rec.  1997 IEEE Global Telecommun.  Conf. ( GLOBECOM""97), Phoenix, Ariz., November 1997, pp.  1514-1518. 
[8] D. Hughes-Hartogs, xe2x80x9cEnsemble modem structure for imperfect transmission media,xe2x80x9d U.S. Pat.  Nos.  4,679,227, (July 1987), 4,731,816 (March 1988), and 4,833,796 (May 1989). 
[9] P. S. Chow, Bandwidth Optimized Digital Transmission Techniques for Spectrally Shaped Channels with Impulse Noise.  Ph.D. Dissertation, Stanford University, May 1993. 
[10] P. S. Chow, J. M. Cioffi, and J. A. C. Bingham, xe2x80x9cA practical discrete multitone transceiver loading algorithm for data transmission over spectrally shaped channels,xe2x80x9d IEEE Trans.  Commun.,  vol.  43, pp.  773-775, Febuary/March/April 1995. 
[11] R. F. H. Fischer and J. B. Huber, xe2x80x9cA new loading algorithm for discrete multitone transmission,xe2x80x9d in Conf.  Rec.  1996 IEEE Global Telecommun.  Conf. ( GLOBECOM""96), London, pp.  724-728, November 1996. 
[12] American National Standards Institute (ANSI), xe2x80x9cNetwork and Customer Installation Interfaces-Asymmetric Digital Subscriber Line (ADSL) Metallic Interface,xe2x80x9d Draft American National Standard for Telecommunications, Jun. 12, 1998. 
[13] L. M. C. Hoo, J. Tellado, and J. M. Cioffi, xe2x80x9cDual Qos loading algorithms for multicarrier systems,xe2x80x9d in Conf.  Rec.  1999 IEEE Int.  Conf.  Commun. ( ICC""99), Vancouver, Canada, June 1999, pp.  796-800. 
As the Internet gradually becomes part of our life, the demand for high-speed transmission networks is ever increasing.  There have been a number of approaches proposed for improving/constructing the information infrastructure.  Among them, asymmetric digital subscriber line (ADSL) technology [1] and very-high-speed digital subscriber line (VDSL) technology [2] are two of the most promising solutions that can provide data rates up to 8 megabits per second and 52 megabits per second respectively over ordinary twisted-pair phone lines from a central office to a customer""s premise.  For the ADSL service, the discrete multitone modulation (DMT) [1], [3] has been selected as a standard by various standards institutes.  Transmission technique using DMT is now also being considered as an international standard for the future VDSL service. 
A basic DMT structure [1] is shown in FIG.  1.  At first, the input data stream is encoded, including the use of forward error correcting (FEC) codes, trellis codes (optional), and interleaving.  The usable bandwidth of a channel is divided into N subchannels (or tones) that are assumed to be independent.  With an appropriate loading algorithm, the data bits to be transmitted are assigned to these N subchannels for transmission, where the bit loading algorithm is trying to optimize the transmission bandwidth based on all the subchannels"" conditions. 
The data bits assigned to each subchannel are mapped onto QAM constellation to form a complex sample, and then the resulting N complex samples from the N subchannels are extended to be a 2N-point complex-conjugate symmetric sequence.  This 2N-point complex sequence is further modulated by the 2N-point inverse fast Fourier transform (IFFT) to generate 2N-point real samples for transmission through the channel.  In order to overcome severely intersymbol interference (ISI) and to make the transmitted signals look periodic, the last v samples of each 2N-sample block are circularly wrapped to prefix the block itself.  After receiving the signals transmitted, the receiver discards the first v samples, and then the remaining received samples are demodulated by the 2N-point FFT.  The resulting transform samples are further processed by a frequency-domain equalizer (FEQ) and a memoryless decoder to recover the original data bits. 
The problem of optimizing the transmission bandwidth was first solved by Shannon in 1948 [4], known as xe2x80x9cwater-fillingxe2x80x9d method, but the corresponding method is impractical to be implemented for the DMT system due to its high complexity and infinite-granularity in the constellation size.  To overcome this problem, several discrete loading algorithms have been proposed for an optimal or suboptimal solution in the finite-granularity constellation case.  Basically, these algorithms can be classified into two categories [5], [6]:
(1) Bit Rate Maximization Problem (BRMP)xe2x80x94Maximize the data rate subject to power and system performance margin constraints, i.e.,                     max        ⁢                              ∑                          n              =              1                        N                    ⁢                      xe2x80x83                    ⁢                      b            n                                              (        1        )            
subject to                                           ∑                          n              =              1                        N                    ⁢                      xe2x80x83                    ⁢                                    p              n                        ⁡                          (                              b                n                            )                                      ≤        p                            (        2        )            
where bn is the number of bits that are transmitted on the nth tone, pn id the power distribution required to transmit bn bits on the nth tone, and p is the total power constraint. 
(2) Margin Maximization Problem (MMP)xe2x80x94Maximize the system performance margin subject to power and data rate constraints, i.e.,                     min        ⁢                              ∑                          n              =              1                        N                    ⁢                      xe2x80x83                    ⁢                                    p              n                        ⁡                          (                              b                n                            )                                                          (        3        )            
subject to                                           ∑                          n              =              1                        N                    ⁢                      xe2x80x83                    ⁢                      b            n                          =        B                            (        4        )            
where pn is a function of bn and B is the data rate constraint. 
The optimal discrete loading algorithm presented by Leke and Cioffi [7] is of BRMP type.  It utilizes the water-filling solution to determine the turned-on subchannels first, and then assigns energy to each turned-on subchannel using the water-filling distribution to maximize the data rate.  The Hughes-Hartogs loading algorithm [8] can be regarded as BRMP type or MMP type, depending on the constraint used.  This algorithm assigns one additional bit to the subchannel that needs the least energy until the data rate or power constraint is met.  It gives an optimal discrete solution but its computational complexity becomes impractical when the number of bits to be transmitted per DMT symbol is large. 
The suboptimal discrete loading algorithm proposed by Chow, Cioffi, and Bingham [9], [10] is of MMP type.  It distributes the data bits among all the usable subchannels according to a well-known formula, and then assigns energy to each usable subchannel with the flat distribution.  Due to the use of the flat-energy distribution, this loading algorithm suffers some performance degradation as compared to the Hughes-Hartogs algorithm but it involves less computational complexity.  In another prior art [11], Fischer and Huber paid their attention on minimizing the error probability of transmission (equivalent to MMP) and derived a closed form to distribute the bits among those usable subchannels.  Like the algorithm described in [9] and [10], this method adopts the flat-energy distribution for bit loading and is suboptimal but it has a slight improvement in performance. 
Campello [6] proposed a discrete loading algorithm that attempts to maximize the data rate (BRMP) or the system performance margin (MMP) at a given constraint.  This algorithm first finds an initial bit distribution for the subchannels appropriately, and then approaches the optimal solution using the Hughes-Hartogs method.  It is actually a suboptimal algorithm but has less complexity than those previous algorithms. 
From the forgoing discussion, it is understandable that there is strong need in finding an optimal algorithm for maximizing the system performance or data rate for DMT transmission. 
The present invention has been made to overcome the above mentioned drawbacks of conventional discrete loading algorithms for DMT modulation.  The primary object of the invention is to provide a method of discrete bit-loading algorithm to optimize the performance or data rate of transmission.  It is also an object of the invention to provide a discrete bit-loading algorithm that is computationally efficient for DMT modulation. 
In the present invention, a continuous bit distribution scheme that provides the same solution as the water-filling solution for DMT transmission is first derived.  The bit distribution is then rounded appropriately to form an integer bit distribution that is also optimal in the discrete case.  A method for implementing the discrete bit distribution algorithm with high-performance and low-complexity features is presented.  The algorithm is well suited to practical high-speed DMT applications, such as the ADSL and VDSL services over existing twisted-pair phone lines. 
Accordingly, the present invention determines a preliminary bit assignment for each subchannel by optimizing a DMT system with N carriers for transmission over an additive white Gaussian channel given an available bandwidth assuming that all subchannels are turned on.  The subchannels that receive negative bit assignments are then excluded, and the procedure for determining the bit assignments is repeated until all the bit assignments are positive for the remaining turned-on subchannels. 
The bit assignment of each subchannel is rounded and a corresponding rounding error is calculated.  If the total bit number of the bit assignments is greater than the target data rate (or the data rate constraint), the bit assignment of the subchannel having the least rounding error is decreased by one bit.  If the total bit number of the bit assignments is smaller than the target data rate, the bit assignment of the subchannel having the largest rounding error is increased by one bit. 
When the total bit number of the bit assignments is identical to the available bandwidth, transmission power is distributed to each channel according to a power distribution formula.  If the total power distributed is greater than the power constraint of the system, the power constraint has to be loosed.  On the other hand, if the total power distributed is less than the power constraint of the system, the excess power can be uniformly distributed to each subchannel.  The excess power can also be distributed by assigning one additional bit to a subchannel that has the largest rounding error repeatedly until the power constraint is met. 
The algorithm of the present invention can maximize the system performance margin or the data rate, depending on the constraints that are put on the system.  As compared to the optimal algorithm proposed by Hughes-Hartogs [8], the present invention achieves the same performance with much less complexity.  It also has advantages over the suboptimal algorithm described by Chow, Cioffi, and Bingham [9], [10] in terms of both performance and complexity.