Water-filling algorithm: Difference between revisions

Revision as of 03:53, 27 July 2012

Latest revision as of 05:05, 23 July 2025

(26 intermediate revisions by 13 users not shown)

Line 1:

The '''water-filling algorithm''' is a technique used in [[digital communications]] systems for allocating power among different channels in multicarrier schemes. It was described by R. C. Gallager in 1968<ref name="gallager">{{cite book |last=Gallager |first=R. C. |publisher=Wiley |year=1968 |title=Information Theory and Reliable Communications}}</ref> along with the '''water-filling theorem''' which proves its optimality for channels having [[Additive White Gaussian Noise]] (AWGN) and [[intersymbol interference]] (ISI).

{{stub}

For this reason, it is a standard baseline algorithm for various digital communications systems, such as [[MIMO|MIMO wireless systems]].<ref>{{ cite patent

==Introduction==

| country = USA

Water filling algorithm, is a general name given to the ideas in [[communication systems]] design and practice for [[channel equalization]] strategies. As the name suggests, just as water finds it level even when filled in one part of a vessel woth multiple openings, as a consequence of [[pascals law]], the amplifier systems in communications network repeaters, or receivers amplify each channel upto the required power level compensating for the channel impairments.

| number = 6973122

==Single Channel Systems==

| title = Power allocation scheme for DMT-based modems employing simplex transmission

In a single channel communication system the deamplification and loss present on the can be simplistically taken as attenuation by a percentage ''g'', then amplifiers restore the signal power level to the same value at transmission setup by operating at a gain of 1/ (1-g). E.g. if we experience 6dB attenuation in transmission, i.e. 75% loss, then we have to amplify the signal by a factor of ''4x'' to restore the signal to the transmitter levels.

| pubdate = Dec 6 2005

==Multichannel Systems==

| fdate = Jan 26 2001

Same ideas can be carried out in presence impairments and a multiple channel system. Amplifier nonlinearity, crosstalk and power budgets prevent the use of these waterfilling algorithms to restore all channels, and only a subset can benefit from them.

| inventor = Miller II et al

| quote = The optimum approach for Additive White Gaussian Noise (AWGN), has been proved to be a `water pouring` algorithm of power distribution, where the g.sub.k.multidot.N.sub.k.sup.1 profile is considered to be equivalent to the `terrain` and the available power budget is likened to `water that is poured` on the terrain. In this analogy, the water depth at position k is equivalent to the power allocated to the frequency bin k.

}}</ref>

The intuition that gives the algorithm its name is to think of the communication medium as if it was some kind of water container with an uneven bottom. Each of the available channels is then a section of the container having its own depth, given by the reciprocal of the frequency-dependent [[Signal-to-noise ratio|SNR]] for the channel.<ref name="gallager"/><ref name="horrible">{{cite journal |last=Biglieri |first=Ezio |title=Coding and modulation for a horrible channel |journal=IEEE Communications Magazine |volume=41 |issue=5 |date=May 2003 |pages=92–98 |doi=10.1109/MCOM.2003.1200107 }}</ref>

To allocate power, imagine pouring water into this container (the amount depends on the desired maximum average transmit power). After the water level settles, the largest amount of water is in the deepest sections of the container. This implies allocating more power to the channels with the most favourable SNR. Note, however, that the ratio allocation to each channel is not a fixed proportion but varies nonlinearly with the maximum average transmit power.

==See also==

#* [[Zero Forcing-forcing equalizer]]

#* [[Robert Lucky]]

#* [[EDFA]]

#[[Amplifier systems]]

#[[EDFA]]

==References==

#* Proakis, Digital Communication Systems, 4th Ed., McGraw Hill, (2001).

<references/>

{{telecomm-stub}}

[[Category:Error detection and correction]]

[[Category:Information theory]]

[[Category:Telecommunications]]

[[Category:Telecommunication theory]]