Dynamic digital communication system control

Abstract

Control of a digital communication system having a plurality of communication lines on which signals are transmitted and received is implemented using a variety of methods and systems. According to one embodiment of the present invention, a method is implemented where the signals are affected by interference during transmission and each of the communication lines has at least one transmitter and at least one receiver. A model is created of the interference characteristics due to the signals carried on the communication lines. Interference characteristics for a line are determined based on the model and actual signals carried on other communication lines different from the line for which the characteristics are being determined. Actual interference is compensated for on the communication line using the determined interference characteristics.

Claims

1. A method of controlling a digital communication system having a plurality of communication channels on which transmissions of signals are communicated by the signals being transmitted and received, the signals being affected by crosstalk interference during transmission, each of the communication channels being used by users and each user having at least one transmitter and at least one receiver, the method comprising the steps of: collecting information about the channel, signal and far-end crosstalk interference characteristics of the communication channels; in response to the collecting, creating a model of the channel, signal and far-end crosstalk interference characteristics of the communication channels; and synchronizing the transmitted and received signals across multiple transmitters and receivers to permit signal processing using the model to remove far-end crosstalk interference from the signals.

2. The method of claim 1, further including performing the step of signal processing using the model to remove far-end crosstalk interference from the signals, which step is performed either: prior to the transmissions of the signals; after reception of the signals; or both prior to the transmissions of the signals and after reception of the signals.

3. The method of claim 1, wherein the step of synchronizing transmissions of signals includes using at least one of: block transmission; and block reception.

4. The method of claim 1, wherein the digital communication system uses multitone transmission and further including performing the step of signal processing using the model to remove far-end crosstalk interference, which step of signal processing is done on a tone by tone basis.

5. The method of claim 1, wherein the step of collecting is performed by a party other than one of the users.

6. The method of claim 1, further including performing the step of signal processing using the model to remove far-end crosstalk interference from the signals, wherein each channel is permitted to transmit and receive signals using a data rate and wherein the step of signal processing using the model to remove far-end interference includes maximizing a weighted sum of the data rates of the plurality of channels.

7. The method of claim 6, wherein the step of maximizing the weighted sum of the data rates of the channels comprises at least one of: allocating energy to each user for the transmissions of signals; creating a matrix which allocates energy to each transmitted frequency, tone or subcarrier; and creating a matrix which allocates energy to a plurality of transmitters.

8. The method of claim 1, further including performing the step of signal processing using the model to remove far-end crosstalk interference from the signals, wherein the signals are sent using a plurality of frequencies and further wherein the step of signal processing using the model includes dynamically adjusting the frequencies used to send the signals.

9. The method of claim 1, further including controlling the digital communication system by allocating a total power to a channel, such that the power is limited by a power constraint applicable to the entire system.

10. The method of claim 1, wherein the digital communication system determines and controls physical layer communications parameters on a communications environment encompassing each of the plurality of communications channels based on an optimization criteria.

11. The method of claim 1, wherein multiple channels support communications with a single user.

12. The method of claim 1, further including performing the step of signal processing using the model to remove far-end crosstalk interference from the signals, wherein the step of signal processing occurs on at least one of: the at least one transmitter of the user; and the at least one receiver of the user.

13. The method of claim 1, further including the step of using an explicit feedback method, based on a transformed estimate of the channel state, to derive the model.

14. The method of claim 1, wherein the model of the channel, signal and far-end crosstalk interference characteristics of the communication channels is based on at least one of: analysis of special symbols that do not carry data sent by the transmitter; and analysis of symbols carrying data between the transmitter and the receiver of one of the users.

15. The method of claim 13, wherein the at least one transmitter uses the transformed estimate of the channel state to calculate a matrix indicating the configuration of individual frequencies or tones of the transmitted signals.

16. The method of claim 1, further including performing the step of signal processing using the model to remove far-end crosstalk interference from the signals, wherein the signals being transmitted are sent by the plurality of transmitters, and wherein the step of signal processing using the model includes modifying power to each transmitter among the plurality of transmitters.

17. The method of claim 1, wherein the signals being transmitted are also sent using the plurality of transmitters.

18. A method of controlling a digital communication system having a plurality of communication channels on which transmissions of signals are communicated by the signals being transmitted and received, the signals being affected by interference during transmission, each of the communication channels being used by users and each user having at least one transmitter and at least one receiver, the method comprising the steps of: collecting information about the channel, signal and far-end interference characteristics of the communication channels; in response to the collecting, creating a model of the channel, signal and far-end interference characteristics of the communication channels; and synchronizing the transmitted and received signals across multiple transmitters and receivers to permit signal processing using the model to remove far-end crosstalk interference from the signals, wherein the interference affecting transmission of signals includes crosstalk from communication channels adjacent the communication channel on which at least one of the signals is sent.

19. A method of controlling a digital communication system having a plurality of communication channels on which transmissions of signals are communicated by the signals being transmitted and received, the signals being affected by crosstalk interference during transmission, each of the communication channels being used by users and each user having at least one transmitter and at least one receiver, the method comprising the steps of: collecting information about the channel, signal and crosstalk interference characteristics of the communication channels; in response to the collecting, creating a model of the channel, signal and crosstalk interference characteristics of the communication channels; synchronizing the transmitted and received signals across multiple transmitters and receivers to permit signal processing using the model to remove crosstalk interference from the signals; and processing the signals using the model to remove crosstalk interference from the signals, wherein the digital communication system uses a multifrequency communications system and the step of processing the signals using the model is done on a frequency-by-frequency basis.

Description

BRIEF DESCRIPTIONS OF THE DRAWINGS

(1) The present invention will be readily understood by the following detailed description in conjunction with the accompanying drawings, wherein like reference numerals designate like structural elements, and in which:

(2) FIG. 1 is a schematic diagram of a set of twisted pair telephone lines used for transmission of an aggregate information stream.

(3) FIG. 2 is a schematic diagram of a DSL system utilizing an existing telephone loop plant.

(4) FIG. 3 is a schematic view of a communication system using link requirements and constraints and line and signal characteristic information on a per line basis.

(5) FIG. 4 is a schematic representation of a DSL system showing a bundle of transmission lines in a binder.

(6) FIG. 5 is a schematic representation of the near-far problem encountered with FEXT crosstalk.

(7) FIG. 6 is a schematic representation of a DSL system showing a bundle of transmission lines in a binder wherein some of the lines share a fiber or other link between a CO and an ONU.

(8) FIG. 7 is a schematic representation of one embodiment of the present invention in which information about line and signal characteristics from a number of DSL lines is shared and used in a joint communication adaptation configuration.

(9) FIG. 8 is an interference channel model showing crosstalk interference among DSL lines.

(10) FIG. 9 is a timing diagram showing synchronization of block transmission and reception at a CO/ONU.

(11) FIG. 10 shows FEXT coupling measurements for loops with length of 1640 feet.

(12) FIG. 11 shows a canceller block of one embodiment of the present invention corresponding to a single tone in a discrete multitone system.

(13) FIG. 12 shows a system for upstream vectored DMT transmission combining canceller blocks of all tones.

(14) FIG. 13 shows a MIMO precoder of the present invention corresponding to a single tone in a discreet multitone system.

(15) FIG. 14 shows a vectored DMT system for downstream transmission combining precoders of the present invention for all tones and including the DMT transmitter and receivers.

(16) FIG. 15 illustrates the QR decomposition of two possible orderings.

(17) FIG. 16 is a graphical depiction of differences in data rates available with one embodiment of the present invention as a function of loop lengths.

(18) FIG. 17 is a flow diagram representation of one embodiment of the present invention in which power levels are determined.

DETAILED DESCRIPTION OF THE INVENTION

(19) The following detailed description of the invention will be with reference to one or more embodiments of the invention, but is not limited to such embodiments. The detailed description is intended only to be illustrative. Those skilled in the art will readily appreciate that the detailed description given herein with respect to the Figures is provided for explanatory purposes as the invention extends beyond these limited embodiments. For example, the present invention is described in some instances in connection with a DSL system. However, the present invention can be used with other systems that would benefit from the improved performance afforded by the present invention. Consequently, the present invention is not limited solely to DSL systems. Moreover, the present invention is described herein primarily in connection with the reduction of crosstalk interference. Again, however, the present invention may be used to reduce or eliminate other undesirable signal interference or to otherwise improve the performance of the system in which the present invention is used.

(20) Performance of the system may be measured by maximizing data rates to users. However, in some systems, operators may wish to be able to offer a variety of services to users. For example, if an operator knows all of the available rates for a bundle, that operator may be able to offer certain users higher data rates as a “premium” service or for specialized needs (such as a hospital or emergency care provider). As will be appreciated from the foregoing, terms such as “optimal” and “optimization” therefore may be subjectively defined and may not necessarily refer to the fastest data rate(s), per se.

(21) “Static spectrum management” uses fixed, inflexible constraints, limits and requirements in connection with various digital communications systems. By contrast, a system with adaptive determination of spectra is referred to herein as “dynamic spectrum management.” Necessarily, static spectrum management is a special case of dynamic spectrum management, so static spectrum management can never outperform dynamic spectrum management. In fact, substantial improvement can be provided by dynamic spectrum management. The present invention illustrates that the level of improvement varies with loop characteristics, crosstalk coupling functions, data rates and symmetries offered, but can be significant. The level of relative improvement increases as loop lengths get shorter and data rates get more symmetric, as is likely to be the case with the present evolution of DSL. Importantly, dynamic spectrum management according to the present invention allows a greater mix of high-performance asymmetric and symmetric services in the same binder.

(22) The present invention will be described in general with respect to a digital communications system. Within the context of dynamic spectrum management, however, there are two situations relating to the unbundling of communications services that will be addressed by example in particular—line unbundling and packet unbundling for DSL service. “Line unbundling” occurs when different service providers place electric physical-layer signals on copper wire lines within a telephone cable, which is the current practice when lines terminate in a central office. A specific illustrative example of the present invention (spectrum balancing) will be presented below and is applicable in a line unbundling environment. “Packet unbundling” occurs when service providers instead lease bit streams from a single common carrier who manages all signals on a telephone cable, meaning that different service providers are utilizing the same telephone cable. This can occur, for example, when fiber is used to connect a central office to an ONU, from which different service providers' twisted pairs in turn emanate. An illustrative example of the present invention (vectored transmission) will be explained below and is applicable in a packet unbundling environment.

(23) General

(24) In some embodiments, the present invention uses methods which make use of some level of knowledge regarding the neighboring systems and the transmission environment, in order to improve performance on all pairs. As a simple example, when crosstalk coupling between lines is weak, various transmission restrictions can be relaxed without substantial impact. Going further, systems on neighboring pairs may shape their power spectral densities so that the mutually induced crosstalk is minimized and their performance targets are met.

(25) The present invention further is defined to include methods and apparatus which determine and control physical layer communication parameters, based on information obtained about the whole transmission environment (the set of all neighboring twisted pairs) and where optimization criteria may relate to all the corresponding links. The communication parameters also may refer to the time periods over which transmission on a pair is allowed, implying schemes similar to time division multiple access. The communication parameter adaptation can occur once (for example, during modem initialization), periodically, or even continuously.

(26) The joint adaptation utilizes information about channel characteristics and about link requirements and constraints, which results in the provisioning of improved services. In some embodiments, information is gathered for all links, but the joint adaptation applies only to a single subset of those links. In another embodiment of the present invention, information is gathered about all of the links, but the joint adaptation is applied independently to subsets of those links. In still other embodiments, information may be gathered about only a subset of the links, with the joint adaptation being applied to all or a subset of the links.

(27) One embodiment of the present invention is shown in FIG. 7. As with earlier systems, a digital communications system 700 uses pairs of modems 710, 711 which are connected by twisted pair lines 712. Universal requirements and constraints (for example, total system power and power constraints on each line) can be applied to all links in the system by a module 714. Again, line and signal characteristics for each line 712 can be acquired and provided to the communication adaptation module 715. The operator of the module 715 may be a single service provider, a group of service providers or an independent entity 716 that collects and evaluates system data and provides instructions to users or, in some cases, possibly controls system parameters to achieve desirable operational characteristics. In FIG. 7 the line and signal characteristics can be acquired for all (or a subset of) lines and can be coordinated or otherwise considered in a joint manner.

(28) In some embodiments of the present invention, information is shared regarding the line characteristics of all links. One example can be found in U.S. Ser. No. 09/788,267, (now U.S. Pat. No. 6,990,196) which is incorporated herein by reference. Line characteristics can include, but are not limited to, loop topology, transfer functions and crosstalk coupling functions. For example, knowledge of crosstalk coupling can allow performance improvements, since the amount of degradation of a link due to transmission on a neighboring link can be accurately estimated, and thus it may be realized that an increase in the transmitted power will improve the performance of the link without degrading the neighboring links.

(29) In still other embodiments of the present invention, information also (or instead) is shared regarding the signaling characteristics. Signaling characteristics can include, but are not limited to, transmitted power spectral density, bandwidth utilization and allocation, modulation type and bit allocation. This may allow the application of a new class of methods and apparatus, such as those involving the distribution in frequency of available power, so that the impact among neighboring links is minimized.

(30) In addition to sharing information regarding line and/or signaling characteristics, joint signal processing methods can be employed which will utilize knowledge of the transmitted bit streams. This coordination level is directly related to the concept of “vectored” transmission, where crosstalk is essentially removed. Again, this allows a different class of adaptation methods, where the power and frequency resources of all links can be optimally allocated in order to achieve the desired requirements.

(31) Two specific implementations of the present invention are now presented. The first uses an adaptive multi-user power control methodology, presented as an example as applied to a VDSL system. Such a system is useful in a line unbundling environment where different service providers may have access to different lines in a binder and/or different services that potentially negatively affect one another are provided on the lines in the binder.

(32) Adaptive Power Control Method

(33) The digital subscriber line (DSL) environment can be viewed as a multi-user system. One embodiment of the present invention is intended to optimize power allocation to identify the maximum achievable data rates for multiple DSL modems in the presence of mutual interference. The following discussion will use VDSL as an example, and show that a multi-user system design with an advanced power allocation scheme can provide a system with substantial performance improvement as compared to a single-user design that does not take the multi-user aspect into account. This advanced power allocation method can be implemented either in a centralized fashion or a distributed fashion. The centralized approach assumes the existence of an entity which acquires knowledge of channel and crosstalk coupling functions, determines the desired signaling characteristics and parameters for each user, and finally instructs each user to employ these transmission characteristics and parameters.

(34) Another embodiment does not require knowledge of the crosstalk coupling functions. In such an embodiment, the modems of each user enter a phase during which each user individually adjusts its own signaling characteristics with the aim of attaining its own desired performance level, while minimizing the crosstalk it induces on the other users. In this embodiment, a centralized entity may still exist, but its role may be restricted to setting the target performance levels of each user.

(35) The following discussion will evaluate transmission techniques where no multi-user detection takes place, and focus solely on advanced power allocation for each user in the network. An interference channel model 800 is shown in FIG. 8. There are N transmitters 810-1 through 810-N and N receivers 820-1 through 820-N in the network 800. The channel from user i to user j is modeled as an ISI channel, whose transfer function in frequency domain is denoted as H.sub.ij(f), where

(36) $0\le f\le F_s,F_s=\frac{1}{2T_s},$
and T.sub.s is the sampling rate. In addition to the interference noise, each receiver also sees a background noise whose power spectrum density is denoted as σ.sub.i(f). The power allocation for each transmitter is denoted as P.sub.i(f), which must satisfy a power constraint:
∫.sub.0.sup.F.sup.s P.sub.i(f)df≦P.sub.i   Equation (1)
The achievable data rate for each user while treating all interference as noise is:

(37) $\begin{array}{cc}{R}_i{\int }_0^{F_s}{\log }_2\left(1+\frac{P_i\left(f\right){.Math.H_{\mathrm{ii}}\left(f\right).Math.}^2}{\Gamma \left({\sigma }_i\left(f\right)+\underset{j\ne i}{.Math.}{P}_j\left(f\right){.Math.H_{\mathrm{ji}}\left(f\right).Math.}^2\right)}\right)\mathrm{df}& \mathrm{Eq}.\left(2\right)\end{array}$
where Γ denotes the SNR-gap which depends on the probability of error, the modulation scheme and the coding applied. A coding and modulation scheme that approaches the information theoretical capacity has Γ=0 dB.

(38) The objective of the system design is to maximize the set of rates {R.sub.1, . . . , R.sub.N} subject to the power constraints of Equation (1). It will be apparent to those of skill in the art that, for each transmitter, increasing its power at any frequency band will increase its own data rate. However, such an increase also causes more interference to other users and is therefore detrimental to other users' transmissions. Thus, an optimization or other advanced design must consider the trade-off among the data rates of all users.

(39) Realistic DSL deployment often requires multiple service rates be supported for all users, and the required level of service of each user could be arbitrary. Therefore, a single figure of merit frequently is inadequate to represent system performance. Also, as noted above, one may wish to know all achievable data rate combinations for the users in a system. For example, if the objective is to maximize the sum rate, then there is no guarantee of a minimal data rate to any one user.

(40) A convenient way to fully characterize the trade-off among the users and the achievable data rates available to them is through the notion of a rate region, which is defined as:
R={(R.sub.1, . . . , R.sub.N):∃(P.sub.1(f), . . . , P.sub.N(f)) satisfying Eqs. (1) and (2)}.   Eq. (3)

(41) The rate region characterizes all possible data rate combinations among all users. Although in theory, the rate region can be found by an exhaustive search through all possible power allocations, or by a series of optimizations involving weighted sums of data rates, computational complexities of these approaches typically are prohibitively high. This is because the rate formula is a non-convex function of power allocations. Consequently, the usual numerical algorithms are able to find only local maxima and not the global maximum. The present invention avoids these complexities by defining a different concept of competitive optimality. Although the methodology of this embodiment of the present invention does not achieve all points in the rate region defined above, it nevertheless performs much better than the current DSL systems.

(42) Instead of finding the global maximum, the present invention utilizes competitive optimality, which has the advantage of providing the locally optimal solution toward which all users have an incentive to move. These competitively optimal points are easy to characterize, and they lead to a power control method that offers a number of advantages compared to the previous methods. First, unlike previous methods that set a PSD level for each VDSL transmitter based solely on its interference emission level, the new power allocation method of the present invention strikes a balance between maximizing each user's own data rate and minimizing its interference emission. In particular, the frequency selective nature of the channel is dealt with explicitly. Second, by taking into account all loop transfer functions and cross-couplings (directly in the embodiment using a centralized control entity, tacitly in the embodiment using a distributed method), the method of the present invention offers the loops an opportunity to negotiate the best use of power and frequency with each other. Third, the usual PSD constraint, which is in place for the purpose of controlling interference, is no longer needed. Only total power constraints apply. Fourth, unlike previous methods, which fix a data rate for each loop regardless of actual service requirement, the new method naturally supports multiple service requirements in different loops. Fifth, the proposed method does not involve arbitrary decisions on the reference noise or reference length. Finally, much better performance can be achieved both in terms of maximum data rates and selectivity of services and/or rates within a system.

(43) Competitive Optimality

(44) The traditional information-theoretic view of an interference channel allows the different transmitters, while sending independent data streams, to be cooperative in their respective coding strategies, so that interference cancellation can take place in the receivers. If such cooperation cannot be assumed, the interference channel can be better modeled as a non-cooperative game. Under this viewpoint, each user competes for data rates with the sole objective of maximizing its performance, regardless of all other users. This scenario is particularly realistic in the current unbundled environment where different loops in the same binder could belong to different service providers, and they indeed compete in the local access market. Now, because each modem has a fixed power budget, each user should adjust its power allocation to maximize its own data rate, while regarding all other interference as noise.

(45) If such power adjustment is done continuously for all users at the same time, they will eventually reach an equilibrium. Such an equilibrium will be a desired system operating point since, at equilibrium, each user will have reached its own local maximum, and nobody has an incentive to move away from that power allocation. From a game theory perspective, this equilibrium point is called the Nash equilibrium.

(46) A Nash equilibrium is defined as a strategy profile in which each player's strategy is an optimal response to each other player's strategy. The following discussion will characterize the Nash equilibrium in the Gaussian interference channel game, and determine its existence and uniqueness in realistic channels.

(47) A two-user interference channel provides the following simplified model:
y.sub.1=x.sub.1+A.sub.2x.sub.2+n.sub.1   Eq. (4)
y.sub.2=x.sub.2+A.sub.1x.sub.1+n.sub.2   Eq. (5)
where the channel transfer functions are normalized to unity. The square magnitude of the interference transfer functions A.sub.1 and A.sub.2 are denoted as α.sub.1(f) and α.sub.2(f), respectively. Let N.sub.1(f) and N.sub.2(f) denote noise power spectrum densities. The two senders are considered as two players in a game. The structure of the game (that is, the interference coupling functions and noise power) are assumed to be common knowledge to both players. A strategy for each player is its transmit power spectrum, P.sub.1(f) and P.sub.2(f), subject to the power constraints ∫.sub.0.sup.F.sup.sP.sub.1(f)df≦P.sub.1 and ∫.sub.0.sup.F.sup.sP.sub.2(f)df≦P.sub.2, respectively, considering only deterministic, or pure strategy here. The payoff for each user is its respective data rate. Under the simplifying assumption that no interference subtraction is performed regardless of interference strength, the data rates are:

(48) $\begin{array}{cc}{R}_1{\int }_0^{F_s}\log \left(1+\frac{P_1\left(f\right)}{N_1\left(f\right)+{\alpha }_2\left(f\right)P_1\left(f\right)}\right)\mathrm{df}& \mathrm{Eq}.\left(6\right)\\ R_2{\int }_0^{F_s}\log \left(1+\frac{P_2\left(f\right)}{N_2\left(f\right)+{\alpha }_1\left(f\right)P_2\left(f\right)}\right)\mathrm{df}& \mathrm{Eq}.\left(7\right)\end{array}$
If we compare the above expression with equation (2), we can identify:

(49) $\begin{array}{cc}{N}_1\left(f\right)=\frac{{\mathrm{\Gamma \sigma }}_1\left(f\right)}{{.Math.H_{11}\left(f\right).Math.}^2}\mathrm{and}& \mathrm{Eq}.\left(8\right)\\ a_2\left(f\right)=\frac{{.Math.H_{21}\left(f\right).Math.}^2}{\Gamma {.Math.H_{11}\left(f\right).Math.}^2}\mathrm{and}& \mathrm{Eq}.\left(9\right)\\ N_2\left(f\right)=\frac{{\mathrm{\Gamma \sigma }}_2\left(f\right)}{{.Math.H_{22}\left(f\right).Math.}^2}\mathrm{and}& \mathrm{Eq}.\left(10\right)\\ a_1\left(f\right)=\frac{{.Math.H_{12}\left(f\right).Math.}^2}{\Gamma {.Math.H_{22}\left(f\right).Math.}^2}& \mathrm{Eq}.\left(11\right)\end{array}$
Thus, the simplified model incurs no loss of generality.

(50) The data rate game discussed here is not a zero-sum game. That is, one player's loss is not equal to the other player's gain. Since at a Nash equilibrium, each user's strategy is the optimal response to the other player's strategy, and for each user, the optimal power allocation given other player's power level is the water-filling of the power against the combined noise and interference, a Nash equilibrium is reached if water-filling is simultaneously achieved for all users.

(51) A complete characterization of the simultaneous water-filling point in the interference channel may be difficult to do, however there are several sufficient conditions for the existence and uniqueness of the Nash equilibrium in the two-user case. For all α.sub.1(f)α.sub.2(f)<1, ∀f, then at least one pure strategy Nash equilibrium in the Gaussian interference game exists. Further, if:

(52) $\begin{array}{cc}{\lambda }_0=\sup \left\{{\alpha }_1\left(f\right)\right\}\sup \left\{{\alpha }_2\left(f\right)\right\}& \mathrm{Eq}.\left(12\right)\\ {\lambda }_1=\sup \left\{{\alpha }_1\left(f\right){\alpha }_2\left(f\right)\right\}& \mathrm{Eq}.\left(13\right)\\ {\lambda }_2=\sup \left\{{\alpha }_1\left(f\right)\right\}\frac{1}{F_s}{\int }_0^{F_s}{\alpha }_2\left(f\right)\mathrm{df}& \mathrm{Eq}.\left(14\right)\\ {\lambda }_3=\sup \left\{{\alpha }_2\left(f\right)\right\}\frac{1}{F_s}{\int }_0^{F_s}{\alpha }_1\left(f\right)\mathrm{df}& \mathrm{Eq}.\left(15\right)\end{array}$
and either
λ.sub.0<1, or   Eq. (16)
λ.sub.1+λ.sub.2<½, or   Eq. (17)
λ.sub.1+λ.sub.3<½  Eq. (18)
then the Nash equilibrium is unique and is stable.

(53) The convergence of the iterative water-filling process shows that the Nash equilibrium is unique. This is because the starting point is arbitrary, so it could be another Nash equilibrium if it were not unique. But each Nash equilibrium is its own fixed point. So, this cannot happen. The stability of the Nash equilibrium also follows from the convergence of the iterative procedure.

(54) Moreover, if the condition for existence and uniqueness of the Nash equilibrium is satisfied, then an iterative water-filling algorithm, where in every step each modem updates its power spectrum density regarding all interference as noise, converges and it converges to the unique Nash equilibrium from any starting point.

(55) Adaptive Power Control

(56) Because of the frequency-selective nature of the DSL channel and the DSL crosstalk coupling, power control algorithms in the DSL environment not only need to allocate power among different users, they also need to allocate power in the frequency domain. This requirement brings in many extra variables and makes the design of advanced power control for DSL difficult. However, by concentrating on the competitive optimal power allocations, and assuming that the existence and uniqueness conditions under a total power constraint for Nash equilibrium are satisfied, total power alone is sufficient to represent all competitive power allocations. Consequently, power control can be based solely on total power despite the frequency selectivity. This simplifies the process tremendously. Although the competitive optimal solutions are in general not globally optimal, impressive improvement can still be realized when compared to existing power back-off algorithms

(57) The goal is to achieve certain target rates for each user. The adaptive process runs in two stages. The inner stage uses given power constraints for each user as the input and derives the competitive optimal power allocation and data rates as output. This is accomplished by the iterative water-filling procedure. With a fixed total power constraint for each user, the first user updates its power allocation as the water-filling spectrum of its channel regarding all other users' crosstalk as noise. Water-filling is then applied successively to the second user, the third user, and so forth, then again to the first user, second user, etc., until each user's power allocation converges. Alternative (or even random) orderings also will work, provided that all users are “served” in due course.

(58) The outer stage finds the optimal total power constraint for each user. The outer procedure adjusts each user's power constraint based on the outcome of the inner iterative water-filling. If a user's data rate is below the user's target rate, then the user's power constraint will be increased, unless it is already at the modem power limit, in which case its power stays the same. If a user's data rate is above its target rate by a prescribed amount, its power will be decreased. If the data rate is only slightly above the target rate (less than the prescribed amount), its power will be unchanged. The outer procedure converges when the set of target rates is achieved.

(59) The method described above applies to the distributed version, where each user acts independently, apart from the fact that its target data rate has been “imposed” on the user by an outside agent or entity. It is easy to derive a centralized version, where a central entity performs the inner and outer iteration steps, and then determines power allocations, which it then instructs the users to adopt. The centralized version implies that the entity has acquired knowledge of some or all of the line and/or signal characteristics.

(60) In a K-user system, using P as the modem power limit and T.sub.i as the target rate of user i, the preferred process can be summarized as follows:

(61) TABLE-US-00001   Initialize P.sub.i = P, i = 1, . . . , K.   repeat    repeat     for i = 1 to K      $N\left(f\right)=\underset{j=1,j\ne i}{\overset{K}{.Math.}}{.Math.H_{\mathrm{ji}}\left(f\right).Math.}^2{P}_j\left(f\right)+{\sigma }_i\left(f\right);$      P.sub.i(f) = water-filling spectrum with channel |H.sub.ii(f)|.sup.2, noise       N(f), and power constraint P.sub.i      R.sub.i = data rate on channel |H.sub.ii(f)|.sup.2 with the power       allocation P.sub.i(f), and noise N(f)     end    until the desired accuracy is reached.    for i = 1 to K     If R.sub.i > T.sub.i + ε, set P.sub.i = P.sub.i − δ.     If R.sub.i < T.sub.i, set P.sub.i = P.sub.i + δ.     If P.sub.i > P, set P.sub.i = P.    end   until R.sub.i > T.sub.i for all i.

(62) This process works well with the parameters δ=3 dB and s equal to 10% of the target rate. The outer iteration converges only if the set of target rates is achievable. Unfortunately, which set of target rates is achievable cannot be known a priori. However, a centralized agent with full knowledge of all channel and interference transfer functions can decide, by running through all possible total power constraints, which sets of target rates can be deployed in a DSL bundle. In effect, the power allocation problem has been separated into two parts. A centralized agent may decide on a target rate and a power constraint for each loop in the bundle. Then the loops themselves can undergo the iterative water-filling procedure to arrive at the desired rates without the need of centralized control. The amount of information that needs to be passed by the central control to each loop is small.

(63) Comparing the present invention to conventional power control methods, this new method offers two key advantages. First, because the interference is controlled systematically, no power spectral density constraints are needed, thus, allowing more efficient use of total power by all users. Secondly, because a single-user water-filling is performed at each stage, optimizing each user's data rate regarding all other users as noise, the iterative water-filling algorithm offers an opportunity for different loops in a binder to negotiate the use of frequency Thus, each loop has an incentive to move away from frequency bands when interference is strong, and concentrate on the frequency bands that it can most efficiently utilize.

(64) Simulations show that the competitively optimal power allocation method of the present invention offers a dramatic improvement in performance. This improvement is possible because the new power control methodology considers all loops in the binder as a whole, taking into account all interactions and globally allocating power to each user. Although the competitively optimal operating points are not necessarily globally optimal, the present invention offers substantial improvement over current power back-off methods which consider only each loop by itself. These competitively optimal points are easy to find because iterative water-filling converges very fast.

(65) It should be noted that other “transmission optimization” techniques and methods can be used instead of the disclosed water-filling method (for example, discrete loading methods). Also, the rate maximization criterion can be replaced by a margin maximization criterion, where the target data rates are fixed for each user.

(66) Vectored Transmission

(67) In the following example, vectored transmission for DSL systems is explained. This implementation of the present invention is useful in a packet unbundling environment where a single line is used by multiple users (for example, when leased by a single operator or where a fiber connection ends at an ONU and provides multiple parties with service from multiple service providers).

(68) Channel Model and DMT Transmission

(69) The DSL channel model for the architecture of FIG. 4 is now presented. The L users 420-1 through 420-L are assumed to correspond to a subset of the twisted-pairs of a group in binder 410. The sampled output for a specific user for either upstream or downstream transmission depends on the present and past input symbols of both the intended user and the other crosstalking users. A block of N output samples for user i satisfies:
y.sub.i=H.sub.i,1.sup.cx.sub.1.sup.p+ . . . +H.sub.i,i.sup.cx.sub.i.sup.p+ . . . +H.sub.i,L.sup.cx.sub.L.sup.p+n.sub.i   Eq. (19)
where H.sub.i,1.sup.c, . . . , H.sub.i,L.sup.c are convolution matrices derived from the channel impulse response matrix, y.sub.i is the vector of N output samples of receiver i, x.sub.k.sup.p is the vector of N+v input symbols of user k, and n.sub.i is the vector of N noise samples of receiver i. v represents the maximum memory of the transfer and crosstalk coupling functions expressed in number of samples. The noise samples represent the superposition of several noise sources such as crosstalk from neighboring DSL systems, radio frequency ingress and impulse noise. In the following, n.sub.i is considered to be white and gaussian and, without loss of generality, has unit variance.

(70) Two fundamental assumptions are used in connection with this discussion of a preferred embodiment. First, all users employ block transmission with a cyclic prefix (CP) of at least length v. Also, block transmission and reception at the CO/ONU are synchronized as illustrated in the timing diagram of FIG. 9.

(71) Given the co-location assumption for the CO/ONU, synchronized block transmission is relatively straightforward to implement. However, synchronized block reception requires additional consideration, although various methods and configurations will be apparent to those of ordinary skill in the art. The block boundaries for upstream transmission are aligned so that the blocks of all users arrive simultaneously at the CO/ONU. This block-level synchronization can be performed during initialization, and is analogous to the problem of synchronized uplink transmission in a wireless environment.

(72) Synchronization at the CO/ONU is automatically achieved when “zipper” FDD is used. According to this technique, a cyclic suffix (CS) larger than the channel propagation delay is included in addition to the CP. This “zippering” offers the benefit of eliminating residual NEXT and near-echo resulting from “spectral leakage” at frequencies close to the upstream/downstream band edges. Nevertheless, in this disclosure, the less stringent assumptions noted above will be used, understanding that residual NEXT and near-echo are mitigated by transmitter pulse-shaping and receiver windowing which are known in the art.

(73) Taking the above into account, Equation (19) becomes:
y.sub.i=H.sub.i,1x.sub.1+ . . . +H.sub.i,ix.sub.i+ . . . +H.sub.I,LX.sub.L+n.sub.i   Eq. (20)
where x.sub.k is a vector of N input symbols of user k, and H.sub.i,j,i,j=1, . . . ,L are circulant matrices. Combining the L users, Equation (20) becomes:
y=Hx+n   Eq. (21)
where y=[y.sub.1.sup.Ty.sub.2.sup.T . . . y.sub.L.sup.T].sup.T, x=[x.sub.1.sup.Tx.sub.2.sup.T . . . x.sub.L.sup.T].sup.T, n=[n.sub.1.sup.Tn.sub.2.sup.T . . . n.sub.L.sup.T].sup.T, and H is a matrix whose (i,j) block is H.sub.i,j. The noise covariance matrix is assumed to be R.sub.nn=I.

(74) Applying Discrete Fourier Transform (DFT) modulation, which is known in the art, an Inverse Discrete Fourier Transform (IDFT) operation is performed on each transmitted data block (prior to appending the CP), and a DFT operation is performed on each received data block (after discarding the CP), thus yielding a channel description where the samples are stacked in groups corresponding to users, and each of the groups contains samples corresponding to tones. It is desirable to reorganize these samples for further processing by stacking in groups corresponding to tones, where each group contains samples corresponding to different users. To this end, a permutation matrix P having NL rows and NL columns is defined, which is composed of the N×N blocks P.sub.ij where i, j=1, . . . , L. The block P.sub.ij contains all zeros, except for a one at position (j,i). When matrix P is right-multiplied with a vector of size NL, the elements of P are re-ordered from L groups of N components into N groups of L components. Also, note that P.sup.−1=P*=P. Applying this reordering operation to both the transmitter and the receiver samples, yields:
Z.sub.i=T.sub.iU.sub.i+N.sub.i, i=1, . . . , N   Eq. (22)

(75) Therefore, Z.sub.i, U.sub.i and N.sub.i contain the received samples, transmitted symbols and noise samples of all users corresponding to tone i, and T.sub.i fully characterizes MIMO transmission within tone i. In the following, a distinction between upstream and downstream will be made by adopting the notation T.sub.i,up and T.sub.i,down.

(76) Equation (22) shows that crosstalk cancellation can be performed independently in each tone. Therefore, as explained in more detail below, an array of canceller blocks can be employed at the CO/ONU to remove crosstalk within each tone for upstream communication. Similarly, precoder blocks can be used at the CO/ONU to pre-distort the transmitted signals within each tone, so that signals received at the CPE are crosstalk-free. Determining the parameters of the canceller/precoder blocks relies on perfect knowledge of the channel matrix and noise covariance matrix at the CO/ONU. This assumption is reasonable for DSL, since the twisted pair channels are stationary, and systems can afford training-based channel identification during initialization.

(77) The additional requirement of having a CP longer than the memory of both the transfer and the crosstalk coupling functions can be satisfied without suffering an excessive loss. FIG. 10 shows FEXT coupling measurements for loops with length of 1640 feet. Since only magnitude data is provided, linear phase was assumed in order to derive the impulse responses. It was found that 99.9% of the signal energy is contained within 9 sec. With a DMT block size of 4096 samples and sampling rate of 17.664 MHz, this corresponds to 159 samples. Therefore, a CP length of 320 samples (corresponding to a 7.8% loss) is more than adequate.

(78) The average delay of a typical twisted pair is approximately 1.5 μs/kft. Given that VDSL loops usually have lengths shorter than 6000 ft, and with the previous DMT assumptions, the propagation delay corresponds to fewer than 160 samples. Therefore, even if “zippering” is used, the length of the CP plus the CS does not exceed the proposed 320 samples. As is known to those of ordinary skill in the art, in cases where the channel has unusually long memory, various techniques are available for “shortening” the memory. For example, a MIMO Time-Domain-Equalizer may be used at the CO/ONU and a MIMO extension of an appropriate precoder may be utilized for downstream communication.

(79) Crosstalk Cancellation Via QR Decomposition

(80) Starting with Equation (22), the methods to remove crosstalk within each tone are described first for upstream and then for downstream communication. In the following, the matrices T.sub.i,up and T.sub.i,down are assumed to be non-singular (the justification for this assumption and the consequences of ill-conditioning are discussed below).

(81) Upstream

(82) For upstream transmission, the co-location of the CO/ONU transceiver equipment gives the opportunity to perform joint signal processing of the received samples. The computation of the QR decomposition of matrix T.sub.i,up yields:
T.sub.i,up=Q.sub.iR.sub.i   Eq. (23)
where Q.sub.i is a unitary matrix and R.sub.i is an upper triangular matrix. If the received samples are “rotated/reflected” by Q.sub.i*, then Equation (22) becomes:

(83) $\begin{array}{cc}\begin{array}{cc}{\tilde{Z}}_i& =Q_i^{*}{Z}_i\end{array}& \mathrm{Eq}.\left(24\right)\\ \begin{array}{cc}& =R_i{U}_i+{\tilde{N}}_i\end{array}& \mathrm{Eq}.\left(25\right)\end{array}$
where Ñ.sub.i=Q.sub.i*N.sub.i has an identity covariance matrix. Since R.sub.i is upper triangular and Ñ.sub.i has uncorrelated components, the input U.sub.i can be recovered by back-substitution combined with symbol-by-symbol detection. Thus, as seen in FIG. 11, a decision feedback structure 1100 is created with the feedforward matrix module 1110 using Q.sub.i*, and the feedback matrix module 1120 using I−R.sub.i. The detection of the k.sup.th element of U.sub.i is expressed as:

(84) $\begin{array}{cc}{\left(\hat{U}\right)}_k=\mathrm{dec}\left[\frac{1}{r_{k,k}^i}{\left({\tilde{Z}}_i\right)}_k-\underset{j=k+1}{\overset{L}{.Math.}}\frac{r_{k,j}^i}{r_{\mathrm{jmj}}^i}{\left(\hat{U}\right)}_j\right],k=L,L-1,\mathrm{.Math.},1& \mathrm{Eq}.\left(26\right)\end{array}$
where r.sub.k,j.sup.i is the (k, j) element of R.sub.i. Assuming that the previous decisions are correct, crosstalk is completely cancelled, and L “parallel” channels are created within each tone. The operations described above can be used to define a preferred canceller block corresponding to a single tone, which is shown in FIG. 11. Combining the canceller blocks of all tones, and taking into account DMT transmission, a system 1200 for upstream vectored DMT transmission is shown in FIG. 12. The transmitters 1210-1 through 1210-L send their respective signals through channel 1220. The receivers 1230-1 through 1230-L receive the signals from channel 1220 and process the received signals using canceller blocks 1240-1 through 1240-L which, in the preferred embodiment, resemble the block of FIG. 11.
Downstream

(85) For downstream transmission in the preferred embodiment, joint signal processing of the transmitted symbols is used. The QR decomposition of T.sub.i,down.sup.T results in:
T.sub.i,down.sup.T=Q.sub.iR.sub.i   Eq. (27)
where again Q.sub.i is a unitary matrix and R.sub.i is an upper triangular matrix. Assuming that the symbols are “rotated/reflected” by Q.sub.i.sup.T* prior to being transmitted:
U.sub.i=Q.sub.i.sup.T*U′.sub.i   Eq. (28)
So, choosing:

(86) $\begin{array}{cc}{\left(U_i^{\prime }\right)}_k={\Gamma }_{M_{i,k}}\left[{\left({\tilde{U}}_i\right)}_k-\underset{j=1}{\overset{k-1}{.Math.}}\frac{r_{j,k}^i}{r_{k,k}^i}{\left(U_i^{\prime }\right)}_j\right],k=1,2,\mathrm{.Math.},L& \mathrm{Eq}.\left(29\right)\end{array}$
crosstalk-free reception is achieved, where the transmitted symbols in tone i are the elements of Ũ.sub.i. The following operation is performed at the receiver:

(87) 0$\begin{array}{cc}\begin{array}{cc}{\left({\hat{Z}}_i\right)}_k={\Gamma }_{M_{i,k}}\left[\frac{{\left(Z_i\right)}_k}{r_{k,k}^i}\right],k=1,2,\mathrm{.Math.},L& \mathrm{Eq}.\left(30\right)\end{array}& \end{array}$
where Γ.sub.M.sub.i,k is defined as:

(88) $\begin{array}{cc}{\Gamma }_{M_{i,k}}\left[x\right]=x-M_{i,k}d\left[\frac{x+\frac{M_{i,k}d}{2}}{M_{i,k}d}\right]& \mathrm{Eq}.\left(31\right)\end{array}$
and M.sub.i,k is the constellation size of user k on tone i, while d is the constellation point spacing. (If x is complex, then

(89) ${\Gamma }_{M_{i,k}}\left[x\right]={\Gamma }_{\sqrt{M_{i,k}}}\left[\mathrm{.Math.}\left(x\right)\right]+j{\Gamma }_{\sqrt{M_{i,k}}}\left[\mathrm{��}\left(x\right)\right].)$
These operations result in:
{circumflex over (Z)}.sub.i=Ũ.sub.i+[diag(R.sub.i.sup.T)].sup.−1N.sub.i   Eq.(32)
which implies crosstalk-free reception. The preferred MIMO precoder described above corresponds to a single tone and is shown in FIG. 13. Combining the precoders of all tones and including the DMT transmitters and receivers, the vectored DMT system for downstream transmission is shown in FIG. 14. This system resembles the system of FIG. 12, except that signals are “pre-processed” with precoders 1420-1 through 1420-L before being sent by the system transmitters 1410-1 through 1410-L, respectively.

(90) Assuming that transmit and receive filtering at the CO/ONU and at the CPE is identical, and noise within a tone has the same statistics for all users, the reciprocity property for twisted pair transmission implies that T.sub.i,up=T.sub.i,down.sup.T. In that case, Equations (23) and (27) give the QR decomposition of the same matrix.

(91) For the upstream channel, regardless of the loop topology, the diagonal element of a column of T.sub.i is larger in magnitude than the off-diagonal elements of the same column. This occurs because, in upstream transmission, the crosstalk coupled signal originating from a specific transmitter can never exceed the “directly” received signal of the same transmitter, and typically the magnitude difference is more than 20 dB. The insertion loss of a signal is always smaller than the coupling loss that it experiences when it propagates into a neighboring pair.

(92) Visualizing the columns of T.sub.i in vector space, it is seen that the columns are almost orthogonal to each other, which implies that Q.sub.i is close to being an identity matrix. Thus, the magnitudes of the diagonal elements of R.sub.i do not differ significantly from those of the diagonal elements of T.sub.i, which indicates that QR cancellation performs almost as good as perfect crosstalk removal. This is illustrated in FIG. 15 for a two user case. As shown in FIG. 15, this holds for both possible detection orderings.

(93) The preceding discussion concerning upstream transmission can be readily extended to downstream transmission by starting with the observation that the crosstalk signals at a specific receiver can never exceed the magnitude of a “directly” received signal. Alternatively, the same conclusions can be reached by using the transpose relationship between the upstream and downstream channel matrices.

(94) The computational cost incurred by the QR cancellation is decomposed into the cost of the QR decompositions and the cost associated with signal processing. DSL channels are stationary, so the QR decompositions need to be computed infrequently (preferably during initialization). Generally, the number of flops per tone (for example, using the Householder transform) can be greatly reduced by taking advantage of the crosstalk environment characteristics. It is known that the crosstalk noise in a pair originates mostly from just three or four neighboring pairs, which implies that a typical T.sub.i matrix is almost sparse with only three or four relatively large off-diagonal elements per row. Therefore, approximating T.sub.i as a sparse matrix, Givens rotations can be employed to triangularize T.sub.i with a reduced number of flops. On the other hand, the real-time computational burden due to the canceller and precoder blocks cannot be reduced. In a straightforward implementation, the operations dominating the total cost are those of Equations (24) and (28).

(95) Although the assumption of perfect channel matrix knowledge is reasonable in the given environment, it is still worth briefly considering the effects of channel estimation errors. The upstream channel matrix for a given tone can be estimated, including a channel estimation error. Then, the QR decomposition with the reciprocity assumption can be performed to get the QR factor estimates. Starting from Equation (24), the effect on upstream communication can be computed. Doing this, it is found that the estimation errors impact transmission by introducing a “bias” in the detection and also by permitting some residual crosstalk. A similar analysis can be applied for downstream communication, but modulo arithmetic complicates the expressions. Ignoring the modulo operations, the effects of the estimation errors can be separated into a detection bias term and a residual crosstalk term.

(96) The results of this analysis reveal that the impact of channel estimation errors is aggravated when any of the diagonal elements of {circumflex over (R)}.sub.i are small. Although channel matrix singularity is almost impossible in the DSL environment, an ill-conditioned channel (implying small diagonal elements) cannot be ruled out, thus increasing the impact of channel estimation errors and posing several computational problems. Such cases arise in high frequencies (for example, in loop topologies that have extreme loop length differences) or in the presence of bridged taps. Nevertheless, the energy allocation algorithms discussed below prevent the occurrence of such phenomena by not allowing transmission in frequencies where the diagonal elements of R.sub.i are small.

(97) As seen above, the elimination of crosstalk in the signals of a system will substantially improve performance of the system. Optimizing energy allocations in the system, when taken in conjunction with the crosstalk elimination likewise improves system performance. Also, as noted above, appropriate energy allocation can help avoid problems resulting from the impact of estimation errors in ill-conditioned channels.

(98) Transmission Optimization

(99) “Transmission optimization” as used in the following example will refer to maximization of a weighted data rate sum. However, in the broadest sense of the present invention, the term “optimization” is not so limited. Optimization may also mean determining the maximum rates available and allocating or provisioning available resources (including data rates for various users) within a digital communication system.

(100) The methods disclosed in the following discussion concern energy allocation in frequency generally, energy allocation in frequency while observing constraints on induced crosstalk, and energy allocation combined with upstream/downstream frequency selection.

(101) Energy Allocation in General

(102) The optimization objective is the maximization of the weighted sum of the data rates of all users:

(103) $\begin{array}{cc}\max \underset{k=1}{\overset{L}{.Math.}}{a}_k{R}_k& \mathrm{Eq}.\left(33\right)\end{array}$
where a.sub.k≧0 is the weight assigned to the k.sup.th user, and R.sub.k is the achievable data rate of the k.sup.th user, which may refer to either the upstream or the downstream direction. In order to compute the data rate, an appropriate known gap approximation is employed. Taking into account the fact that vectoring essentially “diagonalizes” the channel (and assuming no error propagation in the upstream direction), the upstream and downstream achievable rates are obtained:

(104) $\begin{array}{cc}{R}_{k,\mathrm{up}}=\underset{i\in N_{\mathrm{up}}}{.Math.}\frac{1}{2}{\log }_2\left(1+\frac{{.Math.r_{k,k}^i.Math.}^2{\mathrm{.Math.}}_{k,\mathrm{up}}^i}{\Gamma }\right)& \mathrm{Eq}.\left(34\right)\\ R_{k,\mathrm{down}}=\underset{i\in N_{\mathrm{down}}}{.Math.}\frac{1}{2}{\log }_2\left(1+\frac{{.Math.r_{k,k}^i.Math.}^2{\mathrm{.Math.}}_{k,\mathrm{down}}^i}{\Gamma }\right)& \mathrm{Eq}.\left(35\right)\end{array}$
where Γ is defined as the transmission gap, and depends on the probability of error requirement, the coding gain and the required margin. Also, N.sub.up and N.sub.down are the sets of upstream and downstream tone indices correspondingly, which depend on the FDD plan. Error propagation effects are generally limited since DSL systems operate at very small probabilities of error.

(105) The parameters with respect to which optimization takes place are ε.sub.k,up.sup.i for upstream transmission and ε.sub.k,down.sup.i for downstream transmission. These parameters are constrained by limits on the transmitted energy. In upstream transmission, the total transmit energy is constrained by:

(106) $\begin{array}{cc}\underset{i\in N_{\mathrm{up}}}{.Math.}{\mathrm{.Math.}}_k^i\le {\mathrm{.Math.}}_{k,\mathrm{up}}& \mathrm{Eq}.\left(36\right)\end{array}$
where ε.sub.k.sup.i is the energy of (U.sub.i).sub.k in Equation (25), and ε.sub.k,up is the maximum allowed upstream transmitted energy of user k. Since ε.sub.k,up.sup.i=ε.sub.k.sup.i, it is deduced that:

(107) $\begin{array}{cc}\underset{i\in N_{\mathrm{up}}}{.Math.}{\mathrm{.Math.}}_{k,\mathrm{up}}^i\le {\mathrm{.Math.}}_{k,\mathrm{up}}& \mathrm{Eq}.\left(37\right)\end{array}$
In downstream transmission, the total transmit energy constraint is expressed as:

(108) $\begin{array}{cc}\underset{i\in N_{\mathrm{down}}}{.Math.}{\mathrm{.Math.}}_k^i\le {\mathrm{.Math.}}_{k,\mathrm{down}}& \mathrm{Eq}.\left(38\right)\end{array}$
where ε.sub.k.sup.i is the energy of (U.sub.i).sub.k in Equation (21), and ε.sub.k,down is the maximum allowed downstream transmitted energy of user k. Unfortunately, this constraint does not translate directly to a constraint for {tilde over (ε)}.sub.k.sup.i=ε.sub.k,down.sup.i, due to non-linear precoding.

(109) However, simulation results for extreme loop topologies indicate that use of the preferred precoder described above does not result in considerable correlation between the transmitted signals of different users. It is reasonable to assume that this result holds generally, since the simulated loops correspond to a worst-case situation with regard to the crosstalk coupling.

(110) Therefore, the approximation ε.sub.k.sup.i≈{tilde over (ε)}.sub.k.sup.i=ε.sub.k,down.sup.i is made and Equation (38) for downstream becomes:

(111) $\begin{array}{cc}\underset{i\in N_{\mathrm{down}}}{.Math.}{\mathrm{.Math.}}_{k,\mathrm{down}}^i\le {\mathrm{.Math.}}_{k,\mathrm{down}}& \mathrm{Eq}.\left(39\right)\end{array}$

(112) With this in mind, it is seen that the energy allocation problem of Equation (33) becomes independent for each user, and thus the a.sub.k weights are irrelevant in this scenario. The optimization problem for each transmission direction is broken into k waterfilling problems expressed by:

(113) $\begin{array}{cc}\max \underset{i\in N_{\mathrm{up}}}{.Math.}\frac{1}{2}{\log }_2\left(1+\frac{{.Math.r_{k,k}^i.Math.}^2{\mathrm{.Math.}}_{k,\mathrm{up}}^i}{\Gamma }\right)& \mathrm{Eq}.\left(40\right)\\ \mathrm{subject}\mathrm{to}\underset{i\in N_{\mathrm{up}}}{.Math.}{\mathrm{.Math.}}_{k,\mathrm{up}}^i\le {\mathrm{.Math.}}_{k,\mathrm{up}}\mathrm{and}\mathrm{by}\text{:}& \mathrm{Eq}.\left(41\right)\\ \max \underset{i\in N_{\mathrm{down}}}{.Math.}\frac{1}{2}{\log }_2\left(1+\frac{{.Math.r_{k,k}^i.Math.}^2{\mathrm{.Math.}}_{k,\mathrm{down}}^i}{\Gamma }\right)& \mathrm{Eq}.\left(42\right)\\ \mathrm{subject}\mathrm{to}\underset{i\in N_{\mathrm{down}}}{.Math.}{\mathrm{.Math.}}_{k,\mathrm{down}}^i\le {\mathrm{.Math.}}_{k,\mathrm{down}}& \mathrm{Eq}.\left(43\right)\end{array}$
Solutions to these problems can be derived using known techniques. The resulting transmission spectra are optimal in the context of vectored DMT.
Energy Allocation with Power Back-Off

(114) As discussed above, all users in the preferred vectored transmission correspond to a group of neighboring twisted pairs. This does not preclude the operation of other “alien” DSL systems in neighboring twisted pairs, which on one hand cause crosstalk into the vectored systems, and on the other hand suffer from crosstalk originating from the vectored systems. The current approach in dealing with this problem is to impose limits on the transmitted power spectral densities (PSDs), so that the performance of systems is not excessively affected by crosstalk.

(115) Additionally, as in the situation illustrated in FIG. 5, VDSL systems suffer from the fact that upstream signals on short lines detrimentally affect upstream performance on long lines (similarly to the near-far situation in wireless communications). In order to avoid imposing an overly restrictive universal PSD mask, power back-off methods have been proposed which effectively make the PSD mask dependent solely on the loop length of the specific user. A similar scenario, where the downstream communication of neighboring DSL systems may suffer considerably is shown in FIG. 16. Dramatic loop length differences will occur more frequently as ONUs are installed on some lines while twisted pair connections to the COs remain.

(116) Vectoring combined with full channel matrix knowledge can prove effective in limiting the crosstalk induced by vectored systems, without resorting to the introduction of a universal PSD mask, or the use of power back-off methods (which do not necessarily take into account knowledge about crosstalk coupling resulting from matrix channel identification).

(117) Equation (22) can be augmented to include the received samples of alien systems:

(118) 0$\begin{array}{cc}\left[\begin{array}{c}Z\\ Z_n\end{array}\right]=\left[\begin{array}{cc}T& C_n\\ C& T_n\end{array}\right]\left[\begin{array}{c}U\\ U_n\end{array}\right]+\left[\begin{array}{c}N\\ N_n\end{array}\right]& \mathrm{Eq}.\left(44\right)\end{array}$
where Z.sub.n, U.sub.n, and N.sub.n are vectors of the received samples, of the transmitted symbols and of the noise samples, respectively, of the alien systems. The definitions of the block matrices C, C.sub.n and T.sub.n depend on both the channel and the characteristics of the alien DSL systems; and, although T is block diagonal, this property will not generally hold for the other matrices.

(119) When Z and Z.sub.n correspond to systems belonging to different service providers, it may be difficult to identify the crosstalk coupling matrices C and C.sub.n, due to the fact that the current unbundling framework does not allow the first provider to obtain access to either Z or Z.sub.n, and similarly for the second provider. However, a “third party” of the type disclosed in U.S. Ser. No. 09/788,267, overcomes this difficulty by introducing an impartial third-party site or operation, which captures all transmitted and received data to produce estimates of the crosstalk coupling matrices.

(120) Limiting the FEXT in the mean square sense, results in the following conditions:

(121) $\begin{array}{cc}\underset{k=1}{\overset{L}{.Math.}}\underset{i\in N_{\mathrm{up}}}{.Math.}{.Math.C_{j,\left(k-1\right)N+i}.Math.}^2{\mathrm{.Math.}}_{k,\mathrm{up}}^i\le {\mathrm{.Math.}}_{j,\mathrm{up}}^c,j=1,\mathrm{.Math.},{\mathrm{MN}}_N& \mathrm{Eq}.\left(45\right)\\ \underset{k=1}{\overset{L}{.Math.}}\underset{i\in N_{\mathrm{down}}}{.Math.}{.Math.C_{j,\left(k-1\right)N+i}.Math.}^2{\mathrm{.Math.}}_{k,\mathrm{down}}^i\le {\mathrm{.Math.}}_{j,\mathrm{down}}^c,j=1,\mathrm{.Math.},{\mathrm{MN}}_N& \mathrm{Eq}.\left(46\right)\end{array}$
where M is the number of neighboring systems, N.sub.N is the number of “dimensions” (for example, the number of tones) per neighboring system, ε.sub.j,up.sup.c, ε.sub.j,down.sup.c are the maximum allowable crosstalk energies in sample j of the neighboring systems for upstream and downstream, and c.sub.j,l is the (j,l) element of the MN×LN matrix C. Note that this approach can be generalized, so that both FEXT and NEXT are restricted.

(122) The set of inequalities in Equations (45) and (46), combined correspondingly with those of Equations (37) and (39), form a set of linear inequality constraints. Including the rate maximization objective of Equation (33) yields the following optimization problems:

(123) $\begin{array}{cc}\max \underset{k=1}{\overset{L}{.Math.}}{a}_k\underset{i\in N_{\mathrm{up}}}{.Math.}\frac{1}{2}{\log }_2\left(1+\frac{{.Math.r_{k,k}^i.Math.}^2{\mathrm{.Math.}}_{k,\mathrm{up}}^i}{\Gamma }\right)& \mathrm{Eq}.\left(47\right)\\ \mathrm{subject}\mathrm{to}\underset{i\in N_{\mathrm{up}}}{.Math.}{\mathrm{.Math.}}_{k,\mathrm{up}}^i\le {\mathrm{.Math.}}_{k,\mathrm{up}},k=1,\mathrm{.Math.},L& \mathrm{Eq}.\left(48\right)\\ \underset{k=1}{\overset{L}{.Math.}}\underset{i\in N_{\mathrm{up}}}{.Math.}{.Math.c_{j,\left(k-1\right)N+i}.Math.}^2{\mathrm{.Math.}}_{k,\mathrm{up}}^i\le {\mathrm{.Math.}}_{j,\mathrm{up}}^c,j=1,\mathrm{.Math.},{\mathrm{MN}}_N\mathrm{and}\mathrm{by}\text{:}& \mathrm{Eq}.\left(49\right)\\ \max \underset{k=1}{\overset{L}{.Math.}}{a}_k\underset{i\in N_{\mathrm{down}}}{.Math.}\frac{1}{2}{\log }_2\left(1+\frac{{.Math.r_{k,k}^i.Math.}^2{\mathrm{.Math.}}_{k,\mathrm{down}}^i}{\Gamma }\right)& \mathrm{Eq}.\left(50\right)\\ \mathrm{subject}\mathrm{to}\underset{i\in N_{\mathrm{down}}}{.Math.}{\mathrm{.Math.}}_{k,\mathrm{down}}^i\le {\mathrm{.Math.}}_{k,\mathrm{down}},k=1,\mathrm{.Math.},L& \mathrm{Eq}.\left(51\right)\\ \underset{k=1}{\overset{L}{.Math.}}\underset{i\in N_{\mathrm{down}}}{.Math.}{.Math.c_{j,\left(k-1\right)N+i}.Math.}^2{\mathrm{.Math.}}_{k,\mathrm{down}}^i\le {\mathrm{.Math.}}_{j,\mathrm{down}}^c,j=1,\mathrm{.Math.},{\mathrm{MN}}_N& \mathrm{Eq}.\left(52\right)\end{array}$

(124) The objective functions are concave (since they are sums of log functions), and the constraints form convex sets (because they are linear inequalities). Thus, solutions can be efficiently produced using known convex programming techniques. Other restrictions (such as PSD masks or bit caps) can be included in the above optimization problems, since they only require the introduction of linear inequality constraints, which preserve the convexity of the problem.

(125) Energy Allocation and Upstream/Downstream Frequency Selection

(126) Although all existing DSL systems employing FDD have a fixed upstream/downstream frequency duplexing band plan, a dynamically configured band plan may offer significant advantages. Such a plan is common for all users, but is determined during modem initialization, depending on the specific transmission environment, as well as user requirements.

(127) Examples of the disadvantages of a fixed band plan arise in the presence of bridged taps, where transmission in one direction may face a disproportionate degradation, while transmission in the opposite direction may remain unscathed. Adopting a dynamic band methodology in such a case can provide a fairer distribution of the impact on both upstream and downstream activity.

(128) The optimization objective can now be expressed by:

(129) $\begin{array}{cc}\max \underset{k=1}{\overset{L}{.Math.}}\left(a_{k,\mathrm{up}}{R}_{k,\mathrm{up}}+a_{k,\mathrm{down}}{R}_{k,\mathrm{down}}\right)& \mathrm{Eq}.\left(53\right)\end{array}$
where a.sub.k,up,a.sub.k,down≧0 are the weights assigned to upstream and downstream transmission for user k, and R.sub.k,up, R.sub.k,down are the achievable upstream and downstream rates of user k. Here, the optimization parameters involve not just the energies assigned but also the selection of upstream/downstream tones. However, if Equations (34) and (35) are used, the partition of the set of tones into N.sub.up and N.sub.down is a binary constrained problem, whose solution has very high complexity.

(130) Instead, the binary constraints can be relaxed, which greatly simplifies the computations. This idea has previously been used for the computation of the FDMA capacity of the Gaussian multiple access channel in the presence of intersymbol interference. In more detail, it initially is assumed that each tone is time-shared between upstream and downstream, thus obtaining the following achievable rates:

(131) $\begin{array}{cc}{R}_{k,\mathrm{up}}=\underset{i=1}{\overset{N}{.Math.}}{t}_{i,\mathrm{up}}\frac{1}{2}{\log }_2\left(1+\frac{{.Math.r_{k,k}^i.Math.}^2{\mathrm{.Math.}}_{k,\mathrm{up}}^i}{t_{i,\mathrm{up}}\Gamma }\right)& \mathrm{Eq}.\left(54\right)\\ R_{k,\mathrm{down}}=\underset{i=1}{\overset{N}{.Math.}}{t}_{i,\mathrm{up}}\frac{1}{2}{\log }_2\left(1+\frac{{.Math.r_{k,k}^i.Math.}^2{\mathrm{.Math.}}_{k,\mathrm{down}}^i}{t_{i,\mathrm{down}}\Gamma }\right)& \mathrm{Eq}.\left(55\right)\end{array}$
where t.sub.i,up, t.sub.i,down describe the fraction of time in tone i used for upstream and downstream transmission correspondingly, and t.sub.i,up+t.sub.i,down=1; t.sub.i,up,t.sub.i,down≧0. The existence of t.sub.i,up and t.sub.i,down in the denominators inside the log expressions implies that the assigned energy is “boosted” since transmission takes place over only some fraction of time. The energy constraints for user k are:

(132) $\begin{array}{cc}\underset{i=1}{\overset{N}{.Math.}}{\mathrm{.Math.}}_{k,\mathrm{up}}^i\le {\mathrm{.Math.}}_{k,\mathrm{up}}& \mathrm{Eq}.\left(56\right)\\ \underset{i=1}{\overset{N}{.Math.}}{\mathrm{.Math.}}_{k,\mathrm{down}}^i\le {\mathrm{.Math.}}_{k,\mathrm{down}}& \mathrm{Eq}.\left(57\right)\end{array}$

(133) Therefore, the optimization problem has the following form:

(134) $\begin{array}{cc}\max \underset{k=1}{\overset{L}{.Math.}}\left[a_{k,\mathrm{up}}\underset{i=1}{\overset{N}{.Math.}}{t}_{i,\mathrm{up}}\frac{1}{2}{\log }_2\left(1+\frac{{.Math.r_{k,k}^i.Math.}^2{\mathrm{.Math.}}_{k,\mathrm{up}}^i}{t_{i,\mathrm{up}}\Gamma }\right)+a_{k,\mathrm{down}}\underset{i=1}{\overset{N}{.Math.}}{t}_{i,\mathrm{down}}\frac{1}{2}{\log }_2\left(1+\frac{{.Math.r_{k,k}^i.Math.}^2{\mathrm{.Math.}}_{k,\mathrm{down}}^i}{t_{i,\mathrm{down}}\Gamma }\right)\right]& \mathrm{Eq}.\left(58\right)\\ \mathrm{subject}\mathrm{to}\underset{i=1}{\overset{N}{.Math.}}{\mathrm{.Math.}}_{k,\mathrm{up}}^i\le {\mathrm{.Math.}}_{k,\mathrm{up}},k=1,\mathrm{.Math.},L& \mathrm{Eq}.\left(59\right)\\ \underset{i=1}{\overset{N}{.Math.}}{\mathrm{.Math.}}_{k,\mathrm{down}}^i\le {\mathrm{.Math.}}_{k,\mathrm{down}},k=1,\mathrm{.Math.},L& \mathrm{Eq}.\left(60\right)\\ t_{i,\mathrm{up}}+t_{i,\mathrm{down}}=1,i=1,\mathrm{.Math.},N& \mathrm{Eq}.\left(61\right)\end{array}$

(135) The objective function is concave, because it is a sum of functions of the form

(136) $x\log \left(1+\frac{y}{x}\right),$
which are known to be concave in x,y≧0. The constraint sets are clearly convex, since they are defined by linear inequalities. Therefore, the problem is convex and a variety of methods can be used to efficiently derive a solution.

(137) Still, such a solution would actually yield a hybrid between an FDD and a Time Division Duplexing (TDD) implementation. Since an FDD implementation is required, an approximate solution is obtained by rounding t.sub.i,up and t.sub.i,down. Naturally, this is suboptimal, but when the number of tones is fairly large, it will be adequately close to the optimal solution. Simulation results validate this claim. Note that the power back-off constraints of the previous subsection also can be included in the problem formulation without considerably affecting the difficulty of obtaining a solution.

(138) In the above discussion, the objective has been the maximization of a weighted data rate sum. It will be apparent to one of ordinary skill, however, that by adjusting the weights, different surface points of the data rate region achievable by vectored transmission can be determined, and thus the whole multi-dimensional surface can be determined as well. However, visualizing the inherent tradeoffs becomes difficult when the weighted sums include more than three terms. One practical question that can be posed to a service provider is whether a given vectored system can support a set of rate requirements and, if so, what energy allocation is required for achieving the requirements. This problem actually has a duality relationship with the weighted data rate sum problem, and thus the weighted sum problem provides an alternative method to solve the “feasibility” problem.

(139) Vectoring without power back-off or frequency planning can improve performance significantly in several respects. For a given loop length, VDMT allows the achievement of much higher data rates. These rate increases are considerable for lengths in the range of 3500-4500 feet or less. The gains can be even greater in short loops, where transmission is obviously FEXT-limited. Also, vectored DMT can extend the maximum loop length given a data rate requirement. For example, a downstream rate requirement of 50 Mbps typically limits a standard DMT system to loop lengths shorter than 1150 feet. Use of the present invention can extend the reach to lengths on the order of 2650 feet and possibly longer.

(140) The following refers to an example flowchart commensurate with the foregoing discussion. As illustrated in FIG. 17, one approach for controlling a digital communication system having a plurality of data-carrying communication lines having the available total power for use in the system limited by a power constraint is implemented as follows:

(141) As depicted by block 1700, the total power constraint for each line is assigned an initial value. As depicted by block 1702, a competitively optimal data rate is determined for each line. According to one example embodiment, the competitively optimal data rate is determined by performing the steps of: determining a power allocation within the total power constraint of each line by iteratively allowing each line to optimize its power allocation as detected in block 1701, and determining the competitively optimal data rate for each line based on the determined power allocation for the line in block 1702. As depicted by block 1703, a model of the line, signal and the actual interference characteristics of the communication lines is created. As depicted by block 1704, signals are processed using the model to remove interference from signals including evaluating the competitively optimal data rate for each line. According to one example embodiment, the signals are processed by performing the steps of: comparing the competitively optimal data rate of a line with a target rate for the line as depicted in block 1705; increasing the power constraint for a line if the competitively optimal data rate of the line is less than the target rate for the line as depicted in block 1706; decreasing the power constraint for the line if the competitively optimal data rate of the line exceeds the target rate for the line by at least a prescribed variance as depicted in block 1708; maintaining the power constraint for the line if the competitively optimal data rate of the line is equal to the target rate for the line; and maintaining the power constraint for the line if the competitively optimal data rate of the line exceeds the target rate for the line by less than the prescribed variance as depicted in block 1707.

(142) When energy allocation is further constrained by the requirement that some “alien” DSL system also must be protected against crosstalk from the vectored system, then a service provider can perform power back-off in a “selective” way, so that the performance impact can be distributed according to the service priorities. Further improvements are seen when the upstream/downstream duplexing frequency plan is allowed to vary in each vectored bundle depending on the loop characteristics and the service requirements.

(143) Generally, embodiments of the present invention employ various processes involving data transferred through one or more computer systems and/or modems. Embodiments of the present invention also relate to a hardware device or other apparatus for performing these operations. This apparatus may be specially constructed for the required purposes, or it may be a general-purpose computer selectively activated or reconfigured by a computer program and/or data structure stored in the computer. The processes presented herein are not inherently related to any particular computer or other apparatus. In particular, various general-purpose machines may be used with programs written in accordance with the teachings herein, or it may be more convenient to construct a more specialized apparatus to perform the required method steps. A particular structure for a variety of these machines will be apparent to those of ordinary skill in the art based on the present description.

(144) In addition, embodiments of the present invention relate to computer readable media or computer program products that include program instructions and/or data (including data structures) for performing various computer-implemented operations. Examples of computer-readable media include, but are not limited to, magnetic media such as hard disks, floppy disks, and magnetic tape; optical media such as CD-ROM disks; magneto-optical media; semiconductor memory devices, and hardware devices that are specially configured to store and perform program instructions, such as read-only memory devices (ROM) and random access memory (RAM). The data and program instructions of this invention may also be embodied on a carrier wave or other transport medium. Examples of program instructions include both machine code, such as produced by a compiler, and files containing higher level code that may be executed by the computer using an interpreter.

(145) The many features and advantages of the present invention are apparent from the written description, and thus, the appended claims are intended to cover all such features and advantages of the invention. Further, since numerous modifications and changes will readily occur to those skilled in the art, the present invention is not limited to the exact construction and operation as illustrated and described. Hence, all suitable modifications and equivalents are deemed to fall within the scope of the invention.