# Robustness Maximization of Parallel Multichannel Systems

Authors: Jean-Yves Baudais; Fahad Syed Muhammad; Jean-François Hélard
Journal: Journal of Electrical and Computer Engineering
 (2012)

---

## Abstract

Bit error rate (BER) minimization and SNR-gap maximization, two robustness optimization problems, are
solved, under average power and bitrate constraints, according to the waterfilling policy. Under peak power
constraint the solutions differ and this paper gives bit-loading solutions of both robustness optimization
problems over independent parallel channels. The study is based on analytical approach, using
generalized Lagrangian relaxation tool, and on greedy-type algorithm approach. Tight BER expressions
are used for square and rectangular quadrature amplitude modulations. Integer bit solution of analytical
continuous bitrates is performed with a new generalized secant method. The asymptotic convergence of
both robustness optimizations is proved for both analytical and algorithmic approaches. We also prove
that, in the conventional margin maximization problem, the equivalence between SNR-gap maximization
and power minimization does not hold with peak-power limitation. Based on a defined dissimilarity
measure, bit-loading solutions are compared over Rayleigh fading channel for multicarrier systems. Simulation
results confirm the asymptotic convergence of both resource allocation policies. In nonasymptotic
regime the resource allocation policies can be interchanged depending on the robustness measure
and on the operating point of the communication system. The low computational effort leads to a good
trade-off between performance and complexity.


---

## Body

## 1. Introduction

In transmitter design, a problem often encountered is resource allocation among multiple independent parallel channels. The resource can be the power, the bits or the data, and the number of channels. The resource allocation policies are performed under constraints and assumptions, and the independent parallel channels can be encountered in multitone transmission.Independent parallel channels result from orthogonal design applied in time, frequency, or spatial domains [1]. They can either be obtained naturally or in a situation where the transmit and receive strategies are to orthogonalize multiple waveforms. The orthogonal design can also be applied in many communication scenarios when there are multiple transmit and receive dimensions.  Orthogonal frequency-division multiplexing (OFDM) and digital multitone (DMT) are two successful commercial applications for wireless and wireline communications with orthogonality in the frequency domain.To perform resource allocation, relations between various resources are needed, and one is the channel capacity. This capacity ofn-independent parallel Gaussian channels is the well-known sum of the capacity of each channel
(1)C=∑i=1n‍Ci=∑i=1n‍log⁡2(1+snri).
This relation, which holds for memoryless channels, links the supremum bitrate 𝒞i, here expressed in bit per two dimensions, to the signal to noise ratio, snri, experienced by each channel or subchannel i. Any reliable and implementable system must transmit at a bitrate ri below capacity 𝒞i over each subchannel, and then the margin, or SNR-gap, γi is introduced to analyze such systems [2, 3]
(2)γi=2Ci-12ri-1.
This SNR-gap is a convenient mechanism for analyzing systems that transmit below capacity or without Gaussian input, and
(3)ri=log⁡2(1+snriγi),
with ri the bitrate in bits per two-dimensional symbol (bits per second per subchannel) which is also the number of bits per constellation symbol.Resource allocation is performed using loading algorithms, and diverse criteria can be invoked to decide which portion of the available resource is allocated to each of the subchannels. From an information theory point of view, the criterion is the mutual information, and the optimal resource allocation under average power constraint was first devised in [4] for Gaussian inputs and later for non-Gaussian inputs [5]. Since the performance measure is the capacity, the SNR-gap in (3) is γi=1 for all i. In other cases, γi is higher than 1, and (3) has been exploited into many optimal and suboptimal resource allocation policies. In fact, resource allocation is a constraint optimization problem, and generally two cases are of practical interest: rate maximization (RM) and margin maximization (MM), where the objective is the maximization of the data or bitrate, and the maximization of the system margin (or power minimization in practice), respectively [6]. The MM problem gathers all non RM problems including power minimization, margin maximization (in its strict sense), and other measures such as error probabilities or goodput (In this paper MM abbreviation is related to the general family of non-RM problems and not only to the margin maximization problem in its strict sense. The expanded form is reserved for the margin maximization in its strict sense.).   It is not necessary to study all the resource allocation strategies, and equivalence or duality can be found. Families of approaches are defined, and unified processes have been used [7–10]. The loading algorithms are also split in to two families. The first is based on greedy-type approach to iteratively distribute the discrete resources [11], and the second uses Lagrangian relaxation to solve continuous resource adaptation [12]. Both approaches have been compared in terms of performance and complexity [7, 12–14]. All these adaptive resource allocations are possible when channel state information (CSI) is known at both transmitter and receiver sides. This CSI can be perfect or imperfect, and full or partial. The effects of channel estimation error and feedback delay on the performance of adaptive modulated systems can also be considered in the resource allocation process [15–17].In this paper we shall focus henceforth on MM problems, and the main contributions are as follows:(i)
the new resource allocation algorithm and(ii)
the comparison of the different resource allocation strategies. It is assumed that the channel estimation is perfect, and feedback CSI delay and overhead are negligible. The considered peak-power constraint, instead of the conventional average power constraint or sum power constraint, results from power mask limitation and has been taken into account in resource allocation problem [13, 18–20]. With this peak power constraint, each channel must satisfy a power constraint. Note that the sum power constraint is historically the first considered constraint [4]. Bitrate constraint comes from communication applications or service requirements, where different flows can exist, but one of them is chosen at the beginning of the communication. In this configuration, the remaining parameter to optimize is then the SNR-gap γi which is also related to the error probability of the communication system.Two similar problems of MM have the same objective, that is, to maximize the system robustness. What we call robustness in this paper is the capability of a system to maintain acceptable performance with unforeseen disturbances.The first measure of robustness is the SNR gap, or system margin, and its maximization ensures protection against unforeseen channel impairments or noise. The system margin maximization is the maximization of the minimal SNR-gapγi in (3) over the n subchannels. In that case the conventional equivalence between margin maximization and power minimization in MM problems is not generally true. In this paper we show that this equivalence can nevertheless be obtained in particular configurations.The second robustness measure is the bit error rate (BER) and its minimization can reduce the packet error rate and the data retransmissions. In transmitter design, the BER minimization can be realized using uniform bit-loading and adaptive precoding [21, 22]. Analytical studies have been performed with peak-BER or average BER (computed as arithmetic mean) approaches [15, 17]. With nonuniform bit loading, the average BER must be computed as weighted arithmetic mean, and the resource allocation has been performed using a greedy-type algorithm [23]. The first main contribution of this paper is the analytical solution of the resource allocation problem in the case of weighted arithmetic mean BER minimization.To perform the analytical study, based on a generalized Lagrangian relaxation tool, we develop a new method for finding roots of functions. This method generalizes the secant method to better fit the function-depending weight and to speed up the search of the roots. Both robustness polices are compared using a new measure. This measure evaluates the difference of the bit distributions instead of the bitrates. We also prove that both robustness policies provide the same bit distribution in asymptotic regime, which is defined for high SNR and high bitrate regimes, and this is the second main contribution in this paper. The proof is given in the case of unconstrained modulations (i.e., continuous bitrates and analytical solution) and also for QAM constellations and greedy-type algorithms. The convergence is exemplified by simulation in multicarrier communications systems.The organization of the paper is as follows. In Section2, the quantities to be used throughout the paper are introduced, and the robustness optimization problem is formulated in a general way for both system margin maximization and BER minimization. The equivalences between margin maximization and power minimization are worked out. Section 3 presents the considered expressions of accurate BER, the new measure of the bit distribution differences, and the new search method of roots of functions. The solutions of formulated problems are given in Section 4 in the form of an optimum resource allocation policy based on greedy-type algorithms. The conditions of equivalence of both margin maximization and BER minimization are given in this section. Section 5 presents the analytical solution and both greedy-type and analytical methods are compared in Section 6. This Section 6 exemplifies the application of robustness optimization to multicarrier communication systems. Finally, the paper concludes in Section 7 with the proofs of several results relegated to the appendices.Notation. The bitrates {ri}i=1n are defined as a number of bits per two dimensions and they are simply given by a number of bits (undertone per constellation).


## 2. Problem Formulation

Considern parallel subchannels. On the i-th subchannel, the input-output relationship is
(4)Yi=hiSi+Wi,
where Si is the transmitted symbol, Yi is the received one, and hi the complex scalar channel gain. The complex Gaussian noise Wi is a proper complex random variable with zero-mean and variance equal to σWi2.The conventional average power constraint is(5)1n∑i=1n‍E[|Si|2]≤P,
whereas the peak-power constraint, or power spectrum density constraint, considered in this paper is
(6)E[|Si|2]≤P,i=1,…,n.It is convenient to use normalized unit-power symbol{Xi}i=1n such that
(7)Si=piPXi,
which leads to the peak-power constraint
(8)pi≤1,i=1,…,n.It is also convenient to introduce two other variables. The first one is the conventional SNR(9)snri=|hi|2piPσWi2
and the second is called power spectrum density noise ratio (PSDNR)
(10)psdnr=1n∑i=1n‍|hi|2PσWi2,
which is the mean signal to noise ratio over the n subchannels if and only if pi=1 for all i. This PSDNR is the ratio between the power mask at the receiver side (the transmitted power mask through the channel) and the power spectrum density of the noise. The system performance will be given according to this parameter to point out the ability of a system to exploit the available power under peak-power constraint.Using the previous notations, (3) becomes
(11)ri=log⁡2(1+|hi|2piPγiσWi2).
With pi/γi=1 for all i, ri is the subchannel capacity under power constraint P. With unconstrained modulations, ri is defined in ℝ, but constrained modulations are used in practice and ri takes a finite number of nonnegative values. Noninteger number of bits per symbol can also be used with fractional bit constellations [24, 25]. In this paper, modulations defined by discrete points are used with integer number of bits per symbol. Typically, ri∈{0,β,2β,…,rmax}, where β is the granularity in bits and rmax is the number of bits in the richest available constellation. The peak-power and bitrate constraints are then
(12)pi≤1∀i,∑i=1n‍ri=R,ri∈{0,β,2β,…,rmax⁡}∀i.
Obviously, the exploitation of the available power leads to pi=1  foralli and the constraint is simplified as
(13)∑i=1n‍ri=R,ri∈{0,β,2β,…,rmax⁡}∀i.
With peak-power and bitrate constraints, the resource allocation strategy is then to use all available power and to optimize the robustness.The problem we pose is to determine the optimal bitrate allocation{ri*}i=1n that maximizes a robustness measure, or inversely minimizes a frailness measure, under constraints given in (13). In its general form, this problem can be written as
(14)[r1*,…,rn*]=argmin⁡∑i=1nri=Rri∈{0,β,2β,…,rmax⁡}⁡ϕ({ri}i=1n),
where ϕ(·) is the frailness measure. In this paper, this measure is given by the SNR gap or the BER. In addition to the bitrate allocation, the receiver is presumed to have knowledge of the magnitude and phase of the channel gain {hi}i=1n, whereas the transmitter needs only to know the magnitude {|hi|}i=1n. The objective is to find the data vector [r1*,…,rn*] which is the final relevant information for the transmitter. The resource allocation can then be computed on the receiver side to reduce the feedback data rate from n real numbers to n finite integer numbers. Furthermore, the integer nature of the data rates allows a full CSI at the transmitter, which is not possible with real numbers.


### 2.1. System Margin Maximization

The SNR-gapγi of the subchannel i is (3)
(15)γi=snri2ri-1.
With reliable communications, γi is higher than 1 for all subchannels. Let the system margin, or system SNR-gap, be the minimal value of the SNR gap in each subchannel
(16)γ=min⁡iγi.
Let γinit be the initial system margin of one communication system ensuring a given QoS. Let γ be the optimized system margin of this system. Then, the system margin improvement ensures system protection in unforeseen channel impairment or noise, for example, impulse noise; bitrate and system performance targets are always reached for an unforeseen SNR reduction of γ/γinit over all subchannels. This robustness optimization does not depend on constellation and channel-coding types. The system margin γ is defined and optimized without knowledge of used constellations and coding, and the proposed robustness optimization works for any coding and modulation scheme.The objective is the maximization of the system margin which is equivalent to the minimization ofγ-1. We note γi(ri) the function that associates ri to γi. The function ϕ(·) in (14) is then given by
(17)ϕ({ri}i=1n)=max⁡i1γi(ri),(18)[r1*,…,rn*]=argmin⁡∑i=1nri=Rri∈{0,β,2β,⋯,rmax⁡}⁡max⁡iγi-1.
This problem is the inverse problem of bitrate maximization under peak-power and SNR-gap constraints. The solution of the bitrate maximization problem is obvious under the said constraints and given by
(19)ri*=β⌊1βlog⁡2(1+snriγi)⌋∀i.Following the conventional SNR-gap approximation [2], the symbol error rate (SER) of QAM depending on the SNR-gap is constellation size independent with
(20)seri(ri)=2erfc⁡(32γi)∀ri,
where the complementary error function is usually defined as
(21)erfc⁡(x)=2π∫x∞‍e-t2dt.
The system margin maximization is then equivalent to the peak-SER minimization in high-SNR regime. Note that, with (16), the system margin maximization can also be called a trough-SNR-gap maximization, and it is strongly related to the peak-power minimization. Whereas the bit-loading solution is the same for power minimization and margin maximization with sum-margin or sum-power constraints, instead of peak constraints, the following lemma gives sufficient conditions for equivalence in the case of peak constraints.Lemma 1.
The bit allocation that maximizes the system margin under peak-power constraint{pimargin}i=1n minimizes the peak-power under SNR-gap constraint {γipower}i=1n if pimarginγipower=α for all i.Proof.
It is straightforward using (11) and (18). Both problems have the same expression and therefore the same solution.This lemma provides a sufficient but not necessary condition for the equivalence of solutions, and it says that if the power and the SNR-gap constraints have proportional distributions for margin maximization and peak-power minimization problems, respectively, then both problems have the same optimal bitrate allocation. In the general case, we cannot conclude that both problems have the same solution.


### 2.2. BER Minimization

In communication systems, the error rate of the transmitted bits is a conventional robustness measure. By definition, the BER is the ratio between the number of wrong bits and the number of transmitted bits. With a multidimensional system, there exists several BER expressions [15, 23]. Let the BER be evaluated over the transmission of m multidimensional symbols.  (We suppose that m is high enough to respect the ergodic condition and to make possible use of error probability.)  In our case, the multidimensional symbols are the symbols sent over n subchannels. Let ei be the number of erroneous bits received over subchannel i during the transmission. The BER is then given as
(22)ber=∑i=1neim∑i=1nri=∑i=1nri(ei/mri)∑i=1nri.
The BER over subchannel i is ei/mri, and the BER of n subchannels is then
(23)ber({ri}i=1n)=∑i=1nriberi(ri)R
with beri(ri) the function that associates the BER of channel i with the bitrate ri. The BER of multiple variable bitrate ri is then not the arithmetic mean of BER but is the weighted mean BER. Weighted mean BER and arithmetic mean BER are equal if ri=rj  foralli,j or if beri=0 forall i. As there exists beri≠0, then weighted mean BER and arithmetic mean BER are equal if and only if ri=rj  foralli,j. Note that if the number m of transmitted multidimensional symbols depends on the subchannel i, (23) does not hold anymore. These obvious results on mean measures are not taken into account, and mean BER is erroneously used instead of mean weighted BER [15, 17].The functionϕ(·) in (14) is then given by
(24)ϕ({ri}i=1n)=1R∑i=1n‍riberi(ri),(25)[r1*,…,rn*]=argmin⁡∑i=1nri=Rri∈{0,β,2β,…,rmax⁡}⁡ber({ri}i=1n).To simplify the notations, letber(R) be the BER of the system. In high SNR regime with Gray mapping, riberi(ri)=seri(ri), and then weighted mean BER can be approximated by arithmetic mean SER divided by the number of transmitted bits.Contrary to system margin maximization, the BER minimization needs the knowledge of constellation and coding schemes, and it is based on accurate expressions of BER functions. In this paper, the used constellations are QAM, and the optimization is performed without a channel coding scheme. When dealing with practical coded systems, the ultimate measure is the coded BER and not the uncoded BER. However, the coded BER is strongly related to the uncoded BER. It is then generally sufficient to focus on the uncoded BER when optimizing the uncoded part of a communication system [26].


## 2.1. System Margin Maximization

The SNR-gapγi of the subchannel i is (3)
(15)γi=snri2ri-1.
With reliable communications, γi is higher than 1 for all subchannels. Let the system margin, or system SNR-gap, be the minimal value of the SNR gap in each subchannel
(16)γ=min⁡iγi.
Let γinit be the initial system margin of one communication system ensuring a given QoS. Let γ be the optimized system margin of this system. Then, the system margin improvement ensures system protection in unforeseen channel impairment or noise, for example, impulse noise; bitrate and system performance targets are always reached for an unforeseen SNR reduction of γ/γinit over all subchannels. This robustness optimization does not depend on constellation and channel-coding types. The system margin γ is defined and optimized without knowledge of used constellations and coding, and the proposed robustness optimization works for any coding and modulation scheme.The objective is the maximization of the system margin which is equivalent to the minimization ofγ-1. We note γi(ri) the function that associates ri to γi. The function ϕ(·) in (14) is then given by
(17)ϕ({ri}i=1n)=max⁡i1γi(ri),(18)[r1*,…,rn*]=argmin⁡∑i=1nri=Rri∈{0,β,2β,⋯,rmax⁡}⁡max⁡iγi-1.
This problem is the inverse problem of bitrate maximization under peak-power and SNR-gap constraints. The solution of the bitrate maximization problem is obvious under the said constraints and given by
(19)ri*=β⌊1βlog⁡2(1+snriγi)⌋∀i.Following the conventional SNR-gap approximation [2], the symbol error rate (SER) of QAM depending on the SNR-gap is constellation size independent with
(20)seri(ri)=2erfc⁡(32γi)∀ri,
where the complementary error function is usually defined as
(21)erfc⁡(x)=2π∫x∞‍e-t2dt.
The system margin maximization is then equivalent to the peak-SER minimization in high-SNR regime. Note that, with (16), the system margin maximization can also be called a trough-SNR-gap maximization, and it is strongly related to the peak-power minimization. Whereas the bit-loading solution is the same for power minimization and margin maximization with sum-margin or sum-power constraints, instead of peak constraints, the following lemma gives sufficient conditions for equivalence in the case of peak constraints.Lemma 1.
The bit allocation that maximizes the system margin under peak-power constraint{pimargin}i=1n minimizes the peak-power under SNR-gap constraint {γipower}i=1n if pimarginγipower=α for all i.Proof.
It is straightforward using (11) and (18). Both problems have the same expression and therefore the same solution.This lemma provides a sufficient but not necessary condition for the equivalence of solutions, and it says that if the power and the SNR-gap constraints have proportional distributions for margin maximization and peak-power minimization problems, respectively, then both problems have the same optimal bitrate allocation. In the general case, we cannot conclude that both problems have the same solution.


## 2.2. BER Minimization

In communication systems, the error rate of the transmitted bits is a conventional robustness measure. By definition, the BER is the ratio between the number of wrong bits and the number of transmitted bits. With a multidimensional system, there exists several BER expressions [15, 23]. Let the BER be evaluated over the transmission of m multidimensional symbols.  (We suppose that m is high enough to respect the ergodic condition and to make possible use of error probability.)  In our case, the multidimensional symbols are the symbols sent over n subchannels. Let ei be the number of erroneous bits received over subchannel i during the transmission. The BER is then given as
(22)ber=∑i=1neim∑i=1nri=∑i=1nri(ei/mri)∑i=1nri.
The BER over subchannel i is ei/mri, and the BER of n subchannels is then
(23)ber({ri}i=1n)=∑i=1nriberi(ri)R
with beri(ri) the function that associates the BER of channel i with the bitrate ri. The BER of multiple variable bitrate ri is then not the arithmetic mean of BER but is the weighted mean BER. Weighted mean BER and arithmetic mean BER are equal if ri=rj  foralli,j or if beri=0 forall i. As there exists beri≠0, then weighted mean BER and arithmetic mean BER are equal if and only if ri=rj  foralli,j. Note that if the number m of transmitted multidimensional symbols depends on the subchannel i, (23) does not hold anymore. These obvious results on mean measures are not taken into account, and mean BER is erroneously used instead of mean weighted BER [15, 17].The functionϕ(·) in (14) is then given by
(24)ϕ({ri}i=1n)=1R∑i=1n‍riberi(ri),(25)[r1*,…,rn*]=argmin⁡∑i=1nri=Rri∈{0,β,2β,…,rmax⁡}⁡ber({ri}i=1n).To simplify the notations, letber(R) be the BER of the system. In high SNR regime with Gray mapping, riberi(ri)=seri(ri), and then weighted mean BER can be approximated by arithmetic mean SER divided by the number of transmitted bits.Contrary to system margin maximization, the BER minimization needs the knowledge of constellation and coding schemes, and it is based on accurate expressions of BER functions. In this paper, the used constellations are QAM, and the optimization is performed without a channel coding scheme. When dealing with practical coded systems, the ultimate measure is the coded BER and not the uncoded BER. However, the coded BER is strongly related to the uncoded BER. It is then generally sufficient to focus on the uncoded BER when optimizing the uncoded part of a communication system [26].


## 3. Interludes

Before solving the optimization problem, the BER approximation of QAM is presented. This approximation plays a chief role in BER minimization, and a good approximation is therefore needed. Since this paper deals with bitrate allocation, a measure of difference in the bitrate distribution is proposed and presented in this section. This section also presents a new research method of roots of functions. This method generalizes the secant method and converges faster than the secant one.


### 3.1. BER Approximation

Conventionally, the BER approximation of square QAM has been performed by either calculating the symbol error probability or by simply estimating it using lower and upper bounds [27]. This conventional approximation tends to deviate from the exact values when the SNR is low and cannot be applied for rectangular QAM. Exact and general closed-form expressions are developed in [28] for arbitrary one and two-dimensional amplitude modulation schemes.An approximate BER expression for QAM can be obtained by neglecting the higher-order terms in the exact closed-form expression [28]. 								(26)beri≃1ri(2-1Ii-1Ji)erfc⁡(3Ii2+Ji2-2snri)
with Ii=2⌊ri/2⌋, Ji=2⌈ri/2⌉, and ri=log2(Ii·Ji). By symmetry, Ii and Ji can be inverted. The BER can also be expressed using the SNR-gap γi. Using (3) and (26), the BER is written as
(27)beri≃1ri(2-1Ii-1Ji)erfc⁡(3(IiJi-1)Ii2+Ji2-2γi).These two approximations allow the extension of theberi(ri) function from ℕ to ℝ+ which is useful for analytical studies. Figure 1 gives the theoretical BER curves and the approximated ones from the binary phase shift keying (BPSK) to the 32768-QAM. For BER lower than 5·10-2, the relative error is lower than 1% for all modulations.Figure 1
Exact BER curves and approximations (26).


### 3.2. Dissimilar Resource Allocation Measure

Two resource allocations can have the same bitrate, but this does not mean that the bitrates per subchannel are the same. To measure the difference in the bit distribution between different resource allocation strategies, we need to evaluate thedissimilarity. This dissimilarity measure must verify the following properties: (1) if two resource allocations lead to the same bit distribution, then the measure of dissimilarity must be null, whereas (2) if two resource allocations lead to two completely different bit distributions in loaded subchannels, then the measure of dissimilarity must be equal to one, and (3) the measure is symmetric; that is, the dissimilarity between the resource allocations X and Y must be the same as the dissimilarity between the resource allocations Y and X. We choose that the empty subchannels do not impact the measure.Definition 2.
The dissimilarity measure between the resource allocationsX and Y is
(28)μ(X,Y)=∑i=1nδ(ri(X)-ri(Y))max⁡j∈{X,Y}∑i=1nδ(ri(j)),
where δ(x)=1 if x≠0 else δ(x)=0.This dissimilarity has the following properties.Property 1.
μ
(
X
,
Y
)
=
0 iff ri(X)=ri(Y)  foralli.Property 2.
μ
(
X
,
Y
)
=
1 iff ri(X)≠ri(Y) or ri(X)=ri(Y)=0  foralli.Property 3.
μ
(
X
,
Y
)
=
μ
(
Y
,
X
).Property 4.
Ifμ(X,Y)=0, then, for all resource allocation Z, μ(X,Z)=μ(Y,Z).All these properties are direct consequences of Definition2. For a null dissimilarity, μ(X,Y)=0, all the subchannels transmit the same number of bits, that is, ri(X)=ri(Y)  foralli. For a full dissimilarity, μ(X,Y)=1, all the nonempty subchannels of both resource allocations X and Y transmit a different number of bits, that is,  foralli such as ri(X)≠0 and ri(Y)≠0, then ri(X)≠ri(Y). It is obvious that the measure is symmetric μ(X,Y)=μ(Y,X). If two resource allocations have a null dissimilarity μ(X,Y)=0, then they are identical and for any resource allocation Z  μ(X,Z)=μ(Y,Z). The converse of this last property is not true. Note that the dissimilarity is not defined for two empty resource allocations.For example, letn=4 and [r1(X),…,r4(X)]=[4330]. If [r1(Y),…,r4(Y)]=[3222] or [r1(Y),…,r4(Y)]=[5500], then μ(X,Y)=1. If [r1(Y),…,r4(Y)]=[4321], then μ(X,Y)=1/2. The measure μ(X,Y) is null if and only if [r1(Y),…,r4(Y)]=[4330]. The dissimilarity does not evaluate the total bitrate differences but only the bit distribution differences; the contribution of two bitrates ri(X) and rj(Y) in the dissimilarity measure is independent of the bitrate difference |ri(X)-rj(Y)|.


### 3.3. Generalized Secant Method

There are many numerical methods for finding roots of functions. We propose a new method, called the generalized secant method, that is, based on the secant method. This new method better fits the function-depending weight than secant method do and then improves the speed of the convergence. Before explaining this new method, a brief overview of the secant method is given.In our case, the objective functionf(x) is monotonous, nondifferentiable and computable over x∈[x1,x2] with f(x1)/|f(x1)|=-f(x2)/|f(x2)|. The secant method is as follows for an increasing function f(x): (1)
i=0, y0=f(x1);(2)
x0=(x2f(x1)-x1f(x2))/(f(x1)-f(x2)), yi+1=f(x0);(3)
if|yi+1-yi|≤ϵ, then x0 is the root of f(x), else {yi+1<0thenx1=x0yi+1>0thenx2=x0}, i→i+1 and go to step 2. The objective of the secant method is to approximate f(x) by a linear function gi(x)=aix+bi at each iteration i, with gi(x1)=f(x1) and gi(x2)=f(x2), and to set x0 as the root of gi(x). The search for the root of f(x) is completed when the desired precision ϵ is reached. The precision is given for yi, but it can also be given for xi.As the functionf(x) is computable, it can be plotted and an a posteriori simple algebraic or elementary transcendental invertible function over [x1,x2] can be used to better fit the function f(x). The a posteriori information is then used to improve the search for the root. The function f(x) is iteratively approximated by aih(x)+bi instead of aix+bi, where h(x) is the invertible function. This method is then given as follows for an increasing function f(x): (1)
i=0, y0=f(x1);(2)
x0=h-1((x2f(x1)-x1f(x2))/(f(x1)-f(x2))), yi+1=f(x0);(3)
if|yi+1-yi|≤ϵ, then x0 is the root of f(x), else {yi+1<0thenx1=x0yi+1>0thenx2=x0}, i→i+1 and go to step 2. Compared to the secant method, only step 2 differs and the computation of x0 is performed taking into account the approximated shape h(x) of the function f(x).This generalized secant method is used in Section5 to find the root of the Lagrangian and is compared to the conventional secant method. In our case, f(x) is the sum of logarithmic functions, and the function h(x) is then the logarithmic one.


## 3.1. BER Approximation

Conventionally, the BER approximation of square QAM has been performed by either calculating the symbol error probability or by simply estimating it using lower and upper bounds [27]. This conventional approximation tends to deviate from the exact values when the SNR is low and cannot be applied for rectangular QAM. Exact and general closed-form expressions are developed in [28] for arbitrary one and two-dimensional amplitude modulation schemes.An approximate BER expression for QAM can be obtained by neglecting the higher-order terms in the exact closed-form expression [28]. 								(26)beri≃1ri(2-1Ii-1Ji)erfc⁡(3Ii2+Ji2-2snri)
with Ii=2⌊ri/2⌋, Ji=2⌈ri/2⌉, and ri=log2(Ii·Ji). By symmetry, Ii and Ji can be inverted. The BER can also be expressed using the SNR-gap γi. Using (3) and (26), the BER is written as
(27)beri≃1ri(2-1Ii-1Ji)erfc⁡(3(IiJi-1)Ii2+Ji2-2γi).These two approximations allow the extension of theberi(ri) function from ℕ to ℝ+ which is useful for analytical studies. Figure 1 gives the theoretical BER curves and the approximated ones from the binary phase shift keying (BPSK) to the 32768-QAM. For BER lower than 5·10-2, the relative error is lower than 1% for all modulations.Figure 1
Exact BER curves and approximations (26).


## 3.2. Dissimilar Resource Allocation Measure

Two resource allocations can have the same bitrate, but this does not mean that the bitrates per subchannel are the same. To measure the difference in the bit distribution between different resource allocation strategies, we need to evaluate thedissimilarity. This dissimilarity measure must verify the following properties: (1) if two resource allocations lead to the same bit distribution, then the measure of dissimilarity must be null, whereas (2) if two resource allocations lead to two completely different bit distributions in loaded subchannels, then the measure of dissimilarity must be equal to one, and (3) the measure is symmetric; that is, the dissimilarity between the resource allocations X and Y must be the same as the dissimilarity between the resource allocations Y and X. We choose that the empty subchannels do not impact the measure.Definition 2.
The dissimilarity measure between the resource allocationsX and Y is
(28)μ(X,Y)=∑i=1nδ(ri(X)-ri(Y))max⁡j∈{X,Y}∑i=1nδ(ri(j)),
where δ(x)=1 if x≠0 else δ(x)=0.This dissimilarity has the following properties.Property 1.
μ
(
X
,
Y
)
=
0 iff ri(X)=ri(Y)  foralli.Property 2.
μ
(
X
,
Y
)
=
1 iff ri(X)≠ri(Y) or ri(X)=ri(Y)=0  foralli.Property 3.
μ
(
X
,
Y
)
=
μ
(
Y
,
X
).Property 4.
Ifμ(X,Y)=0, then, for all resource allocation Z, μ(X,Z)=μ(Y,Z).All these properties are direct consequences of Definition2. For a null dissimilarity, μ(X,Y)=0, all the subchannels transmit the same number of bits, that is, ri(X)=ri(Y)  foralli. For a full dissimilarity, μ(X,Y)=1, all the nonempty subchannels of both resource allocations X and Y transmit a different number of bits, that is,  foralli such as ri(X)≠0 and ri(Y)≠0, then ri(X)≠ri(Y). It is obvious that the measure is symmetric μ(X,Y)=μ(Y,X). If two resource allocations have a null dissimilarity μ(X,Y)=0, then they are identical and for any resource allocation Z  μ(X,Z)=μ(Y,Z). The converse of this last property is not true. Note that the dissimilarity is not defined for two empty resource allocations.For example, letn=4 and [r1(X),…,r4(X)]=[4330]. If [r1(Y),…,r4(Y)]=[3222] or [r1(Y),…,r4(Y)]=[5500], then μ(X,Y)=1. If [r1(Y),…,r4(Y)]=[4321], then μ(X,Y)=1/2. The measure μ(X,Y) is null if and only if [r1(Y),…,r4(Y)]=[4330]. The dissimilarity does not evaluate the total bitrate differences but only the bit distribution differences; the contribution of two bitrates ri(X) and rj(Y) in the dissimilarity measure is independent of the bitrate difference |ri(X)-rj(Y)|.


## 3.3. Generalized Secant Method

There are many numerical methods for finding roots of functions. We propose a new method, called the generalized secant method, that is, based on the secant method. This new method better fits the function-depending weight than secant method do and then improves the speed of the convergence. Before explaining this new method, a brief overview of the secant method is given.In our case, the objective functionf(x) is monotonous, nondifferentiable and computable over x∈[x1,x2] with f(x1)/|f(x1)|=-f(x2)/|f(x2)|. The secant method is as follows for an increasing function f(x): (1)
i=0, y0=f(x1);(2)
x0=(x2f(x1)-x1f(x2))/(f(x1)-f(x2)), yi+1=f(x0);(3)
if|yi+1-yi|≤ϵ, then x0 is the root of f(x), else {yi+1<0thenx1=x0yi+1>0thenx2=x0}, i→i+1 and go to step 2. The objective of the secant method is to approximate f(x) by a linear function gi(x)=aix+bi at each iteration i, with gi(x1)=f(x1) and gi(x2)=f(x2), and to set x0 as the root of gi(x). The search for the root of f(x) is completed when the desired precision ϵ is reached. The precision is given for yi, but it can also be given for xi.As the functionf(x) is computable, it can be plotted and an a posteriori simple algebraic or elementary transcendental invertible function over [x1,x2] can be used to better fit the function f(x). The a posteriori information is then used to improve the search for the root. The function f(x) is iteratively approximated by aih(x)+bi instead of aix+bi, where h(x) is the invertible function. This method is then given as follows for an increasing function f(x): (1)
i=0, y0=f(x1);(2)
x0=h-1((x2f(x1)-x1f(x2))/(f(x1)-f(x2))), yi+1=f(x0);(3)
if|yi+1-yi|≤ϵ, then x0 is the root of f(x), else {yi+1<0thenx1=x0yi+1>0thenx2=x0}, i→i+1 and go to step 2. Compared to the secant method, only step 2 differs and the computation of x0 is performed taking into account the approximated shape h(x) of the function f(x).This generalized secant method is used in Section5 to find the root of the Lagrangian and is compared to the conventional secant method. In our case, f(x) is the sum of logarithmic functions, and the function h(x) is then the logarithmic one.


## 4. Optimal Greedy-Type Resource Allocations

The general problem is to find the optimal resource allocation[r1*,…,rn*] that minimizes ϕ(·), the inverse robustness measure, or frailness. This is a combinatorial optimization problem or integer programming problem. The core idea in this iterative resource allocation is that a sequential approach can lead to a globally optimum discrete loading. Greedy-type methods then converge to the optimal solution. Convexity is not required for the convergence of the algorithm and monotonicity is sufficient [29]. This monotonicity ensures that the removal or addition of β bits at each iteration converges to the optimal solution. In this paper the used functions ϕ(·) are monotonic increasing functions.In its general form and when the objective functionϕ(·) is not only a weighted sum function, the iterative algorithm is as follows: (1)
start with allocation[r1(0),…,rn(0)]=0,(2)
k=0,(3)
allocate one more bit to the subchannelj for which
(29)ϕ({ri(k+1)}i=1n)
is minimal, with rj(k+1)=rj(k)+β and ri(k+1)=ri(k)foralli≠j,(4)
if∑i‍ri(k+1)=R, terminate; otherwise k→k+1 and go to step 3.The obtained resource allocation is then optimal [29] and solves (14). This algorithm needs R/β iterations. The target bitrate R is supposed to be feasible; that is, R is a multiple of β. Note that an equivalent formulation can be given starting with ri(0)=rmax for all i and using bit removal instead of bit addition with maximization instead of minimization. For bitrates higher than (n/2)rmax, the number of iterations with bit removal is lower than with bit addition. The opposite is true with bitrate lower than (n/2)rmax.Iterative resource allocations have been firstly applied to bitrate maximization under power constraint [11]. Many works have been devoted to complexity reduction of greedy-type algorithms; see, for example, [6, 12, 30, 31] and references therein. In this section, only greedy-type algorithms are presented in order to compare the analytical resource allocation to the optimal iterative one. Note that the analytical solution can also be used as an input of the greedy-type algorithm to initialize the algorithm and to reduce the number of iterations.


### 4.1. System Margin Maximization

The system margin, or system SNR gap, maximization under bitrate and peak-power constraints is the inverse problem of the bitrate maximization under SNR-gap and peak-power constraints. This inverse problem has been solved, for example, in [18]. To comply with the general problem formulation, the inverse system margin minimization is presented instead of the system margin maximization.Lemma 3.
Under bitrate and peak-power constraints, the greedy-type resource allocation that minimizes the inverse system marginγ-1 (16) allocates sequentially β bits to the subchannel i bearing ri bits and for which
(30)2ri+β-1snri
is minimum.Proof.
It is straightforward using (17) and (29). See Appendix A for an original proof.The main advantage of system margin maximization is that the optimal resource allocation can be reached independently of the SNR regime. Resource allocation is always possible even for very low SNR, but it can lead to unreliable communication with SNR gap lower than 1. Lemma3 is given with unbounded modulation orders, that is, rmax=∞ and ri∈βℕforalli. With full constraints (13), the subchannels that reach rmax are simply removed from the iterative process.


### 4.2. BER Minimization

The system BER minimization under bitrate and peak-power constraints is the inverse problem of bitrate maximization under peak-power and BER constraints. This inverse problem has been solved, for example, in [23]. Using (29) and (24), the solution of BER minimization is straightforward, and the corresponding greedy-type algorithm is also known as Levin-Campello algorithm [5, 32, 33]. The main drawback of this solution is that it requires good approximated BER expressions even in low-SNR regime. This constraint can be relaxed, and the following lemma gives the optimal greedy-type resource allocation for the BER minimization.Lemma 4.
In high SNR regime and under bitrate and peak-power constraints, the greedy-type resource allocation that minimizes the BER minimizes(ri+β)beri(ri+β) at each step.Proof.
See AppendixB.Lemma4 states how to allocate bits without mean BER computation at each step. It is given without modulation order limitation. Like system margin maximization solution, the bounded modulation order is simply taken into account using rmax and subchannel removal.


### 4.3. Comparison of Resource Allocations

To compare the two optimization policies, we callℬ the resource allocation that maximizes the system margin and 𝒞 the resource allocation that minimizes the BER. Table 1 gives an example of bitrate allocation over 20 subchannels where the SNR follows a Rayleigh distribution and with β=1. In this example, the PSDNR defined in (10) is equal to 25 dB, and the maximum allowed bitrate per subchannel is never reached. As expected, the system margin minimization leads to a minimal SNR gap, miniγi, higher than that provided by the BER minimization policy with a gain of 0.3 dB. On the other hand, the BER minimization policy leads to BER lower than that provided by system margin minimization (2.6·10-5 versus 3.1·10-5). In this example, the dissimilarity is μ(ℬ,𝒞)=0.1, and two subchannels convey different bitrates. All these results are obtained with rmax=10.Table 1
Example of system margin and BER withn=20, R=100, psdnr=25dB, and β=1.
System margin
BER
maximization
minimization
(ℬ)
(𝒞)
min
i
γ
i
6.9 dB
6.6 dB
ber
3.1
·
1
0
-
5
2.6
·
1
0
-
5This example shows that the difference between the resource allocation policies can be small. The question is whether both resource allocations converge and if they converge then in what cases. The following theorem answers the question.Theorem 5.
In high-SNR regime with square QAM and under bitrate and peak-power constraints, the greedy-type resource allocation that maximizes the system margin converges to the greedy-type resource allocation that minimizes the BER.Proof.
See AppendixD.The consequence of Theorem5 is that the dissimilarity between the resource allocation that maximizes the system margin and the resource allocation that minimizes the BER is null in high-SNR regime and with square QAM. With square QAM, β should be a multiple of 2. Note that with square modulations, β can also be equal to 1 if the modulations are, for example, those defined in ADSL [34]. Figure 6 exemplifies the convergence with β=2 as we will see later in Section 6.


## 4.1. System Margin Maximization

The system margin, or system SNR gap, maximization under bitrate and peak-power constraints is the inverse problem of the bitrate maximization under SNR-gap and peak-power constraints. This inverse problem has been solved, for example, in [18]. To comply with the general problem formulation, the inverse system margin minimization is presented instead of the system margin maximization.Lemma 3.
Under bitrate and peak-power constraints, the greedy-type resource allocation that minimizes the inverse system marginγ-1 (16) allocates sequentially β bits to the subchannel i bearing ri bits and for which
(30)2ri+β-1snri
is minimum.Proof.
It is straightforward using (17) and (29). See Appendix A for an original proof.The main advantage of system margin maximization is that the optimal resource allocation can be reached independently of the SNR regime. Resource allocation is always possible even for very low SNR, but it can lead to unreliable communication with SNR gap lower than 1. Lemma3 is given with unbounded modulation orders, that is, rmax=∞ and ri∈βℕforalli. With full constraints (13), the subchannels that reach rmax are simply removed from the iterative process.


## 4.2. BER Minimization

The system BER minimization under bitrate and peak-power constraints is the inverse problem of bitrate maximization under peak-power and BER constraints. This inverse problem has been solved, for example, in [23]. Using (29) and (24), the solution of BER minimization is straightforward, and the corresponding greedy-type algorithm is also known as Levin-Campello algorithm [5, 32, 33]. The main drawback of this solution is that it requires good approximated BER expressions even in low-SNR regime. This constraint can be relaxed, and the following lemma gives the optimal greedy-type resource allocation for the BER minimization.Lemma 4.
In high SNR regime and under bitrate and peak-power constraints, the greedy-type resource allocation that minimizes the BER minimizes(ri+β)beri(ri+β) at each step.Proof.
See AppendixB.Lemma4 states how to allocate bits without mean BER computation at each step. It is given without modulation order limitation. Like system margin maximization solution, the bounded modulation order is simply taken into account using rmax and subchannel removal.


## 4.3. Comparison of Resource Allocations

To compare the two optimization policies, we callℬ the resource allocation that maximizes the system margin and 𝒞 the resource allocation that minimizes the BER. Table 1 gives an example of bitrate allocation over 20 subchannels where the SNR follows a Rayleigh distribution and with β=1. In this example, the PSDNR defined in (10) is equal to 25 dB, and the maximum allowed bitrate per subchannel is never reached. As expected, the system margin minimization leads to a minimal SNR gap, miniγi, higher than that provided by the BER minimization policy with a gain of 0.3 dB. On the other hand, the BER minimization policy leads to BER lower than that provided by system margin minimization (2.6·10-5 versus 3.1·10-5). In this example, the dissimilarity is μ(ℬ,𝒞)=0.1, and two subchannels convey different bitrates. All these results are obtained with rmax=10.Table 1
Example of system margin and BER withn=20, R=100, psdnr=25dB, and β=1.
System margin
BER
maximization
minimization
(ℬ)
(𝒞)
min
i
γ
i
6.9 dB
6.6 dB
ber
3.1
·
1
0
-
5
2.6
·
1
0
-
5This example shows that the difference between the resource allocation policies can be small. The question is whether both resource allocations converge and if they converge then in what cases. The following theorem answers the question.Theorem 5.
In high-SNR regime with square QAM and under bitrate and peak-power constraints, the greedy-type resource allocation that maximizes the system margin converges to the greedy-type resource allocation that minimizes the BER.Proof.
See AppendixD.The consequence of Theorem5 is that the dissimilarity between the resource allocation that maximizes the system margin and the resource allocation that minimizes the BER is null in high-SNR regime and with square QAM. With square QAM, β should be a multiple of 2. Note that with square modulations, β can also be equal to 1 if the modulations are, for example, those defined in ADSL [34]. Figure 6 exemplifies the convergence with β=2 as we will see later in Section 6.


## 5. Optimal Analytical Resource Allocations

The analytical method is based on convex optimization theory [35]. Unconstrained modulations lead to bitrates ri defined in ℝ. With ri∈ℝ+ the solution is the waterfilling one. With bounded modulation order, that is, 0≤ri≤rmax, the solution is quite different from the waterfilling one. The solution is obtained in the framework of generalized Lagrangian relaxation using Karush-Kuhn-Tucker (KKT) conditions [36].As the bitrates are continuous and not only integers in this analytical analysis, the constraints (13) do not hold anymore and become
(31)∑i=1n‍ri=R,0≤ri≤rmax⁡∀i.
The KKT conditions associated to the general problem (14) with (31) instead of (13) write [36]
(32)-ri≤0,i=1,…,n,(33)ri-rmax⁡≤0,i=1,…,n,(34)R-∑i=1n‍ri=0,(35)μi≥0,i=1,…,n,(36)νi≥0,i=1,…,n,(37)μiri=0,i=1,…,n,(38)νi(ri-rmax⁡)=0,i=1,…,n,(39)∂∂riϕ({rj}j=1n)-λ-μi+νi=0,i=1,…,n,
where λ, μi and νi are the Lagrange multipliers. The first three equations (32)–(34) represent the primal constraints, (35) and (36) represent the dual constraints, (37) and (38) represent the complementary slackness, and (39) is the cancellation of the gradient of Lagrangian with respect to ri. When the primal problem is convex and the constraints are linear, the KKT conditions are sufficient for the solution to be primal and dual optimal. For the system margin maximization problem, the function ϕ(·) is convex over all input bitrates and SNR whereas this function is no longer convex for the BER minimization problem. Appendix C gives the convex domain of the function ϕ(·) in the case of BER minimization problem.The properties of the studied functionϕ(·) are such that
(40)∂∂riϕ({rj}j=1n)=ψi(ri)
is independent of rj for all j≠i. The optimal solution that solves (32)–(39) is then [36]
(41)ri*(λ)={0,ifλ≤ψi(0),ψi-1(λ),ifψi(0)<λ<ψi(rmax⁡),rmax⁡,ifλ≥ψi(rmax⁡)
for all i=1,…,n and with λ verifying the constraint
(42)∑i=1n‍ri*(λ)=R.It is worthwhile noting that the above general solution is the waterfilling one ifrmax≥R. The waterfilling is also the solution in the following case. Let ℐ′ be the subset index such that
(43)I′={i∣ri*≠{0,rmax⁡}},
and let R′ the target bitrate over ℐ′. In this subset, {ri*}i∈ℐ′ are solutions of
(44){∂∂riϕ({rj}j=1n)-λ=0,∀i∈I'R′-∑i∈I′‍ri(λ)=0.
This is the solution of (14) with unbounded modulations over the subchannel index subset ℐ′. If ℐ′={1,⋯,n} and R′=R, and (44) is also the solution of (14) with unconstrained modulations.


### 5.1. System Margin Maximization

Theorem 6.
Under bitrate and peak-power constraints, the asymptotic bit allocation which minimizes the inverse system margin is given by(45)ri*=R′|I′|+1|I′|∑j∈I'‍log⁡2snrisnrj,∀i∈I'.Proof.
See AppendixE.The solution given by Theorem6 holds for high modulation orders which defines the asymptotic regime, compare Appendix E. If the set ℐ′ is known, then Theorem 6 can be used directly to allocate the subchannel bitrates. Otherwise,  ℐ′ should be found first.The expression ofri* in Theorem 6 is a function of the target bitrate R′, the number |ℐ′| of subchannels, and the ratios of SNR. This expression is independent of the mean received SNR or PSDNR. It does not depend on the link budget but only on the relative distribution of subchannel coefficients {|hi|2}i=1n.


### 5.2. BER Minimization

The arithmetic mean BER minimization has been analytically solved, for example, in [22, 37]. This arithmetic mean measure needs to employ the same number of bits per constellation which limits the system efficiency. The following theorem gives the solution of the weighted mean BER minimization that allows variable constellation sizes in the multichannel system.Theorem 7.
Under bitrate and peak-power constraints, the asymptotic bit allocation which minimizes the BER is given by(46)ri*=R′|I′|+1|I′|∑j∈I'‍log⁡2snrisnrj∀i∈I'
with equal in-phase and quadrature bitrates.Proof.
See AppendixF.The solution given by Theorem7 holds for high modulation orders and for subchannel BER lower than 0.1, and these parameters define the asymptotic regime in this case, compare  Appendix F. The optimal asymptotic resource allocation leads to square QAM with ri* conveyed bitrate in each in-phase and quadrature components of the signal of subchannel i. It is important to note that, in asymptotic regime, BER minimization and system margin maximization lead to the same subchannel bitrate allocation. In that case, the asymptotic regime is defined by the more stringent context which is the BER minimization. As we will see in Section 6, this asymptotic behavior can be observed when β=2.The main drawback of the formulas in Theorems7 and 6 is that the subset ℐ′ must be known. To find this subset, the negative subchannel bitrates and those higher than rmax should be clipped, and ℐ′ can be found iteratively [18]. But clipping negative bitrates first can decrease those higher than rmax, and clipping bitrates higher than rmax first can increase the negative ones. It is then not possible to apply first the waterfilling solution and after that to clip the bitrates ri greater than rmax to converge to the optimal solution. Finding the set ℐ′ requires many comparisons, and we propose a fast iterative solution based on the generalized secant method.


### 5.3. Lagrangian Resolution

To solve (41), numerical iterative methods are required. It is important to observe that the function defined in (41) is not differentiable, and, thus, methods like Newton's cannot be used [18]. We use the proposed generalized secant method to better fit the function-depending weight and increase the speed of the convergence. An important point for the iterative method is that the initialization value must lead to feasible solution and should be as close as possible to the final solution.The root of the function defined by (42) is now calculated. Let
(47)f(λ)=∑i=1n‍ri(λ)-R.
Theorems 6 and 7 show that r(λ) is the sum of log2(·) functions. This is the reason why the function log2(·) is used in the generalized secant method. Figure 2 shows three functions versus the parameter λ. The first function is the input function f(λ), the second one is the function used by the generalized secant method, and the last one if the linear function used by the secant method. In this example, the common points are λ=0 and λ=2.3. As it is shown, the generalized secant method better fits the input function than the secant method and therefore can improve the speed of the convergence to find the root which is around λ=1/80 in this example.Figure 2
Approximation of the input functionf(λ) with the generalized secant method and the secant method, n=1024 and rmax=15.To ensure the convergence of the secant methods, the algorithm should be initialized withλ1 and λ2 such as f(λ1)<0 and f(λ2)>0. For both optimization problems, system margin maximization and BER minimization, the parameter λ is given by the function ψi(ri), and it can be reduced to λ=2ri/snri, as shown in Appendices E and F. Parameters {λ1,λ2} are then chosen as
(48)λ1=1max⁡isnri,λ2=2rmax⁡min⁡isnri.
Using (41), λ≤λ1 leads to ri(λ)=0 for all i, and λ≥λ2 leads to ri(λ)=rmax for all i. Then, it follows that f(λ1)<0 and f(λ2)>0 if R∈(0,nrmax).Figure3 shows the needed number of iterations for the convergence of the generalized and conventional secant methods versus the target bitrate R. Results are given over a Rayleigh distribution of the subchannel SNR with 1024 subchannels. The possible bitrates are then R∈[0,n×rmax] and β=2. Here, rmax=15 and then R≤15360 bits per multidimensional symbol. For comparison, the number of iterations needed by the greedy-type algorithm is also plotted. Note that the greedy-type algorithm can start by empty bitrate or by full bitrate limited by rmax for each subchannel. The number of iterations is then given by min{R,nrmax-R}. The iterative secant and generalized secant methods are stopped when the bitrate error is lower than 1. A better precision is not necessary since exact bitrates {ri}i∈ℐ′ can be computed using Theorems 6 and 7 when ℐ′ is known. As it is shown in Figure 3, the generalized secant method converges faster than the secant method, except for the very low target bitrates R. For very high target bitrates, near from n×rmax, the number of iterations with the generalized secant method can be higher than that with the greedy-type algorithm. Except for these particular cases, the generalized secant method needs no more than 4-5 iterations to converge. In conclusion, we can say that with Rayleigh distribution of {snri}i=1n and for target bitrates R such that 3%≤R/nrmax≤97%, the generalized secant method converges faster than the secant method or the greedy-type algorithm.Figure 3
Number of iterations of the secant and generalized secant methods, and greedy-type algorithm versus the target bitrate,n=1024, rmax=15.Using the generalized secant method, the bitrates are not integers and for alli, ri*∈[0,rmax]. These solutions have to be completed to obtain integer bitrates.


### 5.4. Integer-Bit Solution

Starting from the continuous bitrate allocations previously presented, a loading procedure is developed taking into account the integer nature of the bitrates to be allotted. A simple solution is to consider the integer part of{ri*}i∈ℐ′ and to complete by a greedy-type algorithm to achieve the target bitrate R. The integer part of {ri*}i∈ℐ′ is then used as a starting point for the greedy algorithm. This procedure can lead to a high number of iterations. Therefore, the secant or bisection methods are suitable to reduce the number of iterations. The problem to solve is then to find the root of the following function [18]:
(49)g(α)=∑i∈I'‍⌊ri*+βα⌋-R′,
where ri*, ℐ′, and R′ are given by the continuous Lagrangian solution. This is a suboptimal integer bitrate problem, and the optimal one needs to find {αi}i=1n instead of a unique α. As the optimal solution leads to a huge number of iterations, it is not considered. The function (49) is a nondecreasing and nondifferentiable staircase function such that g(0)<0, g(1)>0 because ∑i∈ℐ′‍ri*=R′. The iterative methods can then be initialized with α1=0 and α2=1.Two iterative methods are compared: the bisection one and the secant one. Both methods are also compared to the greedy-type algorithm. Figure4 presents the number of iterations of the three methods to solve the integer-bit problem of the Lagrangian solution with β=1. Results are given over a Rayleigh distribution of the subchannel SNR, with 1024 subchannels and the target bitrates are between 0 and n×rmax=15360. As it is shown, the convergence is faster with bisection method than with greedy-type algorithm. For target bitrates between 10% and 90% of the maximal loadable bitrate, the secant method outperforms the bisection one with a mean number of iterations around 4 whereas the number of iterations for bisection method is higher than 8. Figure 4 also shows that |g(0)| is all the time lower than the half of number of subchannels and around this value for target bitrate between 10% and 90% of the maximal loadable bitrate. Then, if the number of iterations induces by the greedy-type algorithm to solve the integer-bit problem of the Lagrangian solution that is acceptable in a practical communication system, this greedy-type completion can be used and appears to lead to the optimal resource allocation. This result obtained without proof means that the greedy-type procedure has enough bits to converge to the optimal solution. If the number of iterations induced by the greedy-type algorithm is too high (this number is around n/2), the secant method can be used.Figure 4
Number of iterations of the bisection and secant methods, and greedy-type algorithm for integer-bit solution versus target bitrate,n=1024, rmax=15.The overall analytical resolution of (14) needs few iterations compared to the optimal greedy-type algorithm. Whereas the continuous solution of (14) is optimal, the analytical integer bitrate solution is suboptimal.


## 5.1. System Margin Maximization

Theorem 6.
Under bitrate and peak-power constraints, the asymptotic bit allocation which minimizes the inverse system margin is given by(45)ri*=R′|I′|+1|I′|∑j∈I'‍log⁡2snrisnrj,∀i∈I'.Proof.
See AppendixE.The solution given by Theorem6 holds for high modulation orders which defines the asymptotic regime, compare Appendix E. If the set ℐ′ is known, then Theorem 6 can be used directly to allocate the subchannel bitrates. Otherwise,  ℐ′ should be found first.The expression ofri* in Theorem 6 is a function of the target bitrate R′, the number |ℐ′| of subchannels, and the ratios of SNR. This expression is independent of the mean received SNR or PSDNR. It does not depend on the link budget but only on the relative distribution of subchannel coefficients {|hi|2}i=1n.


## 5.2. BER Minimization

The arithmetic mean BER minimization has been analytically solved, for example, in [22, 37]. This arithmetic mean measure needs to employ the same number of bits per constellation which limits the system efficiency. The following theorem gives the solution of the weighted mean BER minimization that allows variable constellation sizes in the multichannel system.Theorem 7.
Under bitrate and peak-power constraints, the asymptotic bit allocation which minimizes the BER is given by(46)ri*=R′|I′|+1|I′|∑j∈I'‍log⁡2snrisnrj∀i∈I'
with equal in-phase and quadrature bitrates.Proof.
See AppendixF.The solution given by Theorem7 holds for high modulation orders and for subchannel BER lower than 0.1, and these parameters define the asymptotic regime in this case, compare  Appendix F. The optimal asymptotic resource allocation leads to square QAM with ri* conveyed bitrate in each in-phase and quadrature components of the signal of subchannel i. It is important to note that, in asymptotic regime, BER minimization and system margin maximization lead to the same subchannel bitrate allocation. In that case, the asymptotic regime is defined by the more stringent context which is the BER minimization. As we will see in Section 6, this asymptotic behavior can be observed when β=2.The main drawback of the formulas in Theorems7 and 6 is that the subset ℐ′ must be known. To find this subset, the negative subchannel bitrates and those higher than rmax should be clipped, and ℐ′ can be found iteratively [18]. But clipping negative bitrates first can decrease those higher than rmax, and clipping bitrates higher than rmax first can increase the negative ones. It is then not possible to apply first the waterfilling solution and after that to clip the bitrates ri greater than rmax to converge to the optimal solution. Finding the set ℐ′ requires many comparisons, and we propose a fast iterative solution based on the generalized secant method.


## 5.3. Lagrangian Resolution

To solve (41), numerical iterative methods are required. It is important to observe that the function defined in (41) is not differentiable, and, thus, methods like Newton's cannot be used [18]. We use the proposed generalized secant method to better fit the function-depending weight and increase the speed of the convergence. An important point for the iterative method is that the initialization value must lead to feasible solution and should be as close as possible to the final solution.The root of the function defined by (42) is now calculated. Let
(47)f(λ)=∑i=1n‍ri(λ)-R.
Theorems 6 and 7 show that r(λ) is the sum of log2(·) functions. This is the reason why the function log2(·) is used in the generalized secant method. Figure 2 shows three functions versus the parameter λ. The first function is the input function f(λ), the second one is the function used by the generalized secant method, and the last one if the linear function used by the secant method. In this example, the common points are λ=0 and λ=2.3. As it is shown, the generalized secant method better fits the input function than the secant method and therefore can improve the speed of the convergence to find the root which is around λ=1/80 in this example.Figure 2
Approximation of the input functionf(λ) with the generalized secant method and the secant method, n=1024 and rmax=15.To ensure the convergence of the secant methods, the algorithm should be initialized withλ1 and λ2 such as f(λ1)<0 and f(λ2)>0. For both optimization problems, system margin maximization and BER minimization, the parameter λ is given by the function ψi(ri), and it can be reduced to λ=2ri/snri, as shown in Appendices E and F. Parameters {λ1,λ2} are then chosen as
(48)λ1=1max⁡isnri,λ2=2rmax⁡min⁡isnri.
Using (41), λ≤λ1 leads to ri(λ)=0 for all i, and λ≥λ2 leads to ri(λ)=rmax for all i. Then, it follows that f(λ1)<0 and f(λ2)>0 if R∈(0,nrmax).Figure3 shows the needed number of iterations for the convergence of the generalized and conventional secant methods versus the target bitrate R. Results are given over a Rayleigh distribution of the subchannel SNR with 1024 subchannels. The possible bitrates are then R∈[0,n×rmax] and β=2. Here, rmax=15 and then R≤15360 bits per multidimensional symbol. For comparison, the number of iterations needed by the greedy-type algorithm is also plotted. Note that the greedy-type algorithm can start by empty bitrate or by full bitrate limited by rmax for each subchannel. The number of iterations is then given by min{R,nrmax-R}. The iterative secant and generalized secant methods are stopped when the bitrate error is lower than 1. A better precision is not necessary since exact bitrates {ri}i∈ℐ′ can be computed using Theorems 6 and 7 when ℐ′ is known. As it is shown in Figure 3, the generalized secant method converges faster than the secant method, except for the very low target bitrates R. For very high target bitrates, near from n×rmax, the number of iterations with the generalized secant method can be higher than that with the greedy-type algorithm. Except for these particular cases, the generalized secant method needs no more than 4-5 iterations to converge. In conclusion, we can say that with Rayleigh distribution of {snri}i=1n and for target bitrates R such that 3%≤R/nrmax≤97%, the generalized secant method converges faster than the secant method or the greedy-type algorithm.Figure 3
Number of iterations of the secant and generalized secant methods, and greedy-type algorithm versus the target bitrate,n=1024, rmax=15.Using the generalized secant method, the bitrates are not integers and for alli, ri*∈[0,rmax]. These solutions have to be completed to obtain integer bitrates.


## 5.4. Integer-Bit Solution

Starting from the continuous bitrate allocations previously presented, a loading procedure is developed taking into account the integer nature of the bitrates to be allotted. A simple solution is to consider the integer part of{ri*}i∈ℐ′ and to complete by a greedy-type algorithm to achieve the target bitrate R. The integer part of {ri*}i∈ℐ′ is then used as a starting point for the greedy algorithm. This procedure can lead to a high number of iterations. Therefore, the secant or bisection methods are suitable to reduce the number of iterations. The problem to solve is then to find the root of the following function [18]:
(49)g(α)=∑i∈I'‍⌊ri*+βα⌋-R′,
where ri*, ℐ′, and R′ are given by the continuous Lagrangian solution. This is a suboptimal integer bitrate problem, and the optimal one needs to find {αi}i=1n instead of a unique α. As the optimal solution leads to a huge number of iterations, it is not considered. The function (49) is a nondecreasing and nondifferentiable staircase function such that g(0)<0, g(1)>0 because ∑i∈ℐ′‍ri*=R′. The iterative methods can then be initialized with α1=0 and α2=1.Two iterative methods are compared: the bisection one and the secant one. Both methods are also compared to the greedy-type algorithm. Figure4 presents the number of iterations of the three methods to solve the integer-bit problem of the Lagrangian solution with β=1. Results are given over a Rayleigh distribution of the subchannel SNR, with 1024 subchannels and the target bitrates are between 0 and n×rmax=15360. As it is shown, the convergence is faster with bisection method than with greedy-type algorithm. For target bitrates between 10% and 90% of the maximal loadable bitrate, the secant method outperforms the bisection one with a mean number of iterations around 4 whereas the number of iterations for bisection method is higher than 8. Figure 4 also shows that |g(0)| is all the time lower than the half of number of subchannels and around this value for target bitrate between 10% and 90% of the maximal loadable bitrate. Then, if the number of iterations induces by the greedy-type algorithm to solve the integer-bit problem of the Lagrangian solution that is acceptable in a practical communication system, this greedy-type completion can be used and appears to lead to the optimal resource allocation. This result obtained without proof means that the greedy-type procedure has enough bits to converge to the optimal solution. If the number of iterations induced by the greedy-type algorithm is too high (this number is around n/2), the secant method can be used.Figure 4
Number of iterations of the bisection and secant methods, and greedy-type algorithm for integer-bit solution versus target bitrate,n=1024, rmax=15.The overall analytical resolution of (14) needs few iterations compared to the optimal greedy-type algorithm. Whereas the continuous solution of (14) is optimal, the analytical integer bitrate solution is suboptimal.


## 6. Greedy-Type versus Analytical Resource Allocations

In the previous section, the numbers of iterations of the algorithms have been compared. In this section, robustness comparison is presented and the analytical solutions obtained in asymptotic regime are also applied in nonasymptotic regime which means thatβ=1 and modulation orders can be low.The evaluated OFDM communication system is composed of 1024 subcarriers without interferences between the symbols or the subcarriers. The channel is the Rayleigh fading one with independent and identically distributed elements. The richest modulation order isrmax=10. The robustness measures are evaluated for different target bitrates which are given with the following arbitrary equation:
(50)R=⌊∑i=1n‍min⁡(log⁡2(1+snri2),rmax⁡)⌋.
This equation ensures reliable communications for all the input target bitrates or PSDNR. The empirical relationship between PSDNR and target bitrate is also given in Figure 5.Figure 5
Target bitrate versus input PSDNR.Figure 6
BER, system margin and dissimilarity versus target bitrate for Lagrangian (𝒜), greedy-type system margin maximization (ℬ) and greedy-type BER minimization (𝒞) algorithms, n=1024, rmax=10, and  β∈{1,2}.Figure6 presents the output BER and the system margin of three resource allocation policies versus the target bitrate R. The first one, 𝒜, is obtained using analytical optimization, the second, ℬ, is the solution of the greedy-type algorithm which maximizes the system margin, and the third, 𝒞, is the solution of the greedy-type algorithm which minimizes the BER. Two cases are presented: one with β=1 and the other with β=2. All subchannel BER are lower than 2·10-2 to use valid BER approximations. Note that, with β=1, the system margin of allocation ℬ is almost equal to 8.9 dB for all target-bit rates. This constant system margin γ is not a feature of the algorithm but is only a consequence of the relation between the target bitrate and the PSDNR.To enhance the equivalences and the differences between the resource allocation policies, the dissimilarity is also given in Figure6 with β=1 and β=2. As expected in both cases, β=1 and β=2, the minimal BER are obtained with allocation 𝒞, and the maximal system margins with allocation ℬ.Withβ=1 and when the target bitrate increases, the Lagrangian solution converges faster to the optimal system margin maximization solution, ℬ, than to the optimal BER minimization solution, 𝒞. Note that Theorem 7 is an asymptotic result valid for square QAM. With β=1, the QAM can be rectangular, and the asymptotic result of Theorem 7 is not applicable, contrary to the result of Theorem 6 where there is not any condition on the modulation order.The caseβ=2 shows the equivalence between the optimal system margin maximization allocation and the optimal BER minimization allocation. In this case, the asymptotic result given by Theorems 5 and 7 can be applied because the modulations are square QAM, and the convergence is ensured with high modulation orders, that is, high target bitrates. Beyond a mean bitrate per subchannel around 6, that corresponds to a target bitrate around 6000, all the allocations 𝒜, ℬ and 𝒞 are equivalent, and the dissimilarity is almost equal to zero. In nonasymptotic regime, the differences in BER and system margin are low. The system margin differences are lower than 1 dB, and the ratios between two BER are around 3. In practical integrated systems, these low differences will not be significant and will lead to similar solutions for both optimization policies. Therefore, these resource allocations can be interchanged.


## 7. Conclusion

Two robustness optimization problems have been analyzed in this paper. Weighted mean BER minimization and minimal subchannel margin maximization have been solved under peak-power and bitrate constraints. The asymptotic convergence of both robustness optimizations has been proved for analytical and algorithmic approaches. In non asymptotic regime, the resource allocation policies can be interchanged depending on the robustness measure and the operating point of the communication system. We have also proved that the equivalence between SNR-gap maximization and power minimization in conventional MM problem does not hold with peak-power limitation without additional conditions. Integer bit solution of analytical continuous bitrates has been obtained with a new generalized secant method, and bit-loading solutions have been compared with a new defined dissimilarity measure. The low computational effort of the suboptimal resource allocation strategy, based on the analytical approach, leads to a good tradeoff between performance and complexity.



---

*Source: 840513-2012-07-18.xml*