CAPITOLO 3

CAPITOLO 3

LA TECNICA DI ALLOCAZIONE

WATER-FILLING CON SNR GAP

INTRODUZIONE

In questo capitolo viene introdotta la tecnica di allocazione di risorse nota come water-filling con SNR gap, derivante dalla strategia water-filling pura proposta da Shannon. Viene descritto il contesto in cui tale tecnica si applica, nonchè la derivazione matematica della quantità SNR gap e una dettagliata formulazione analitica del

problema di allocazione risorse. Successivamente viene fornita una descrizione dei più importanti algoritmi che implementano in modo computazionalmente efficiente tale strategia, facendo riferimento, in particolare, ai lavori di Hughes-Hartogs, Cioffi, Campello e Fischer.

3.1 IL TEOREMA WATER-FILLING CLASSICO

In questo paragrafo otterremo l’espressione della tecnica di allocazione risorse water-filling proposta da Shannon, padre della teoria dell’informazione, prendendo le mosse da ragionamenti molto generali. Iniziamo ricordando che ad ogni sorgente di dati può essere associata una quantità media di informazione detta entropia della sorgente, definita come [13]

( )

1 N n n n

H s

p I

=

=

∑

[bit/simbolo] (3.1.1)

dove

p

_n è la probabilità di trasmettere il simbolo n-esimo fra gli N possibili, e

I

_n è la quantità di informazione associata a tale simbolo

2

1

log

n n

I

p





=









[bit/simbolo] (3.1.2)

Considerando il caso generale di trasmissione attraverso un qualsiasi canale, è possibile dimostrare che la quantità media di informazione che viene trasferita oltre il mezzo disturbato, nota come informazione mutua, è data da

(

,

)

( )

(

|

)

M

I

s canale

=

H s

−

H s canale

(3.1.3)

in cui

H s canale

(

|

)

prende il nome di equivocazione. Interpretando l’informazione come incertezza, si può affermare che l’informazione di sorgente in uscita dal canale è pari a quella in ingresso meno l’incertezza che permane sul simbolo quando il canale stesso è noto (incertezza a posteriori). La massima quantità di informazione trasferibile senza errori, detta capacità di canale, può, quindi, in generale essere espressa come

(

)

{

}

max

_M

,

C

=

I

s canale

[ bit/uso di canale]

(3.1.4)

Nel caso specifico di canale AWGN Soft Input Soft Output (SISO) tempo continuo, la capacità assume la seguente famosa espressione

2 0

log 1

P

S

C

B

N B





=



+







(3.1.5)

dove

B

e

P

_S sono rispettivamentela banda e la potenza del segnale trasmesso, e

N

₀ è la potenza di rumore. Questa espressione può essere agevolmente generalizzata al caso di canale distorcente affetto da fading, sul quale la trasmissione avviene con tecnica multiportante. In tale situazione, infatti, la capacità complessiva del canale può essere approssimata come somma delle capacità calcolate, in base alla 3.1.5, su ogni sottobanda 2 2 2 1 1

log 1

S S N N k k k k k _k

p H

C

C

f

σ

= =





≅

= ∆



_

+



_





∑

∑

(3.1.6)

Considerando bande

∆ →

f

0

, la 3.1.6 può essere ulteriormente generalizzata

( ) ( )

( )

2 2 0

log 1

B S n

S

f

H f

C

df

S

f









=

+









∫

(3.1.7)

essendo

S

_S

( )

f

la densità spettrale di potenza del segnale,

S

_n

( )

f

quella del rumore, che in generale è colorato, e

H f

( )

2 il modulo quadro della risposta in frequenza del canale.

Il teorema water-filling indica come scegliere la distribuzione di potenza del segnale per massimizzare la quantità 3.1.7 . La soluzione al problema è di questo tipo:

( )

( )

( )

2 n S

S

f

S

f

H f

λ

+

=

(3.1.8)

dove

λ

è una costante. Notiamo come con tale tecnica si tenda a destinare più potenza sulle frequenze caratterizzate da un maggior guadagno di canale, mentre vengono penalizzate le frequenze sulle quali le condizioni di propagazione sono peggiori. Il nome water-filling deriva proprio da una semplice interpretazione grafica di questa procedura di power allocation, visto che rappresentando su un grafico l’andamento dell’ attenuazione introdotta dal canale in funzione della frequenza, la potenza disponibile è distribuita riempiendone gli avvallamenti, fino a raggiungere un livello costante.

Fig. 3.1 Allocazione di potenza water-filling : interpretazione grafica

In un contesto OFDM le varie sottoportanti possono essere viste come un set di canali gaussiani paralleli e indipendenti fra loro, ciascuno caratterizzato da un certo guadagno

complesso imposto dal canale di trasmissione, che può essere considerato piatto in frequenza in corrispondenza di ogni sottobanda. L’espressione di capacità di canale che ci interessa è quindi la 3.1.6, e la soluzione water-filling che fa al caso nostro è la versione discretizzata della 3.1.8 [14].

2 2 n k k

p

H

σ

λ

=

−

(3.1.9)

in cui

σ

_n2 è la varianza del rumore AWGN e il water level

λ

è dato da

2 2

'

'

n k U _k TOT

H

P

N

N

σ

λ

=

+

∈

∑

(3.1.10)

essendo

U

l’insieme delle portanti utili,

N

'

il numero di queste sottoportanti e

P

_TOT

la potenza totale disponibile per la trasmissione. E’ ancora più evidente come i canali meno attenuati siano quelli premiati con una maggiore aliquota di potenza. L’allocazione 3.1.9 può produrre anche valori negativi e, se ciò accade, la portante corrispondente deve essere esclusa dal set

U

di canali utili e l’algoritmo di allocazione deve essere reiterato da capo, calcolando un nuovo water level. Una allocazione di potenza negativa si verifica allorché una sottobanda è così attenuata che non vale la pena utilizzarla per la trasmissione.

Ovviamente a seguito dell’ allocazione di potenza è opportuno disporre una adeguata distribuzione di bit in base alla 3.1.6.

La tecnica water-filling classica, o water pouring, rappresenta una soluzione definitiva del problema di allocazione risorse, ma solo nel caso in cui, in ingresso a canali gaussiani, si abbiano segnali anch’essi caratterizzati da una distribuzione gaussiana. E’ evidente che, nel caso di trasmissioni reali, in cui sono utilizzate modulazioni discrete, questa condizione non e’ rispettata. E’ tuttavia possible dimostrare che , nel caso di trasmissione con costellazioni di simboli, il problema della massimizzazione del bit rate, condizionato ad un certo livello di BER e ad una certa quantità di potenza totale disponibile, mantiene la stessa formulazione matematica del problema della massimizzazione dell’informazione mutua su un set di canali gaussiani indipendenti con ingressi gaussiani, facendo però riferimento ad un canale equivalente in cui SNR e’ ridotto di un fattore detto SNR gap(e quindi la capacità è inferiore) [15]. Si tratta, in pratica, di un’approssimazione, che consente di mantenere,anche in un contesto di modulazione discreta, il modello matematico tipico della tecnica di allocazione waterfilling classica.

3.2 DERIVAZIONE MATEMATICA DI SNR GAP

L’espressione di SNR gap può essere ottenuta mettendo in relazione il numero di bit per simbolo relativo ad una costellazione M-QAM con l’energia dei simboli della costellazione, come mostrato in [16]. Considerando costellazioni QAM quadrate, centrate nell’origine, e indicando con d la distanza fra i punti della costellazione, l’espressione dell’energia dei simboli di modulazione risulta

1

2

6

M

d

ε

=

−

(3.2.1)

dove M rappresenta il numero di punti della costellazione, ed è pari a

2

b, con b numero di bit rappresentati da un singolo simbolo QAM. Notiamo che la (3.2.1) non è un’espressione esatta, ma rappresenta una buona approssimazione per b≥ . Tuttavia 2

nel seguito la ipotizzeremo valida per ogni modulazione QAM. Assumiamo inoltre la presenza di un canale che non introduce ISI, caratterizzato da un guadagno |H|. La probabilità d’errore sul simbolo per costellazioni M-QAM non codificate, è ben approssimata da

4

min

2

S

d

P

Q

σ





=

_

_





(3.2.2)

Dove

d

_min è la minima distanza fra i punti della costellazione all’uscita del canale, ed è data da

d

_min2

=

d H

2 2

(3.2.3)

Mentre la funzione Q(.) è definita come

2 2

1

( )

2

x x

Q x

e

du

π

∞ −

=

∫

(3.2.4)

2 2 min

6

2

b

1

H

M

d

ε

=

= +

(3.2.5)

e definiamo la quantità SNR gap

Γ

come

2 2 1 min 2

1

1

3 4

3

4

d

SER

Q

σ

−









Γ =

=

_

_

_

_









(3.2.6)

Notiamo che

Γ

non dipende da M, ma solo dalla Symbol Error Rate.

Esprimendo la (3.2.5) in funzione di b, e sostituendovi l’espressione di

Γ

, otteniamo finalmente

b

=

log 1

₂



_

+

SNR



_

Γ





(3.2.7)

avendo definito il rapporto segnale-rumore

2 2

2

H

SNR

ε

σ

=

(3.2.8)

Osservando la (3.2.7) risulta evidente che

Γ

è chiamato SNR gap perché il numero di bit che può essere efficacemente trasmesso è inferiore rispetto alla capacità teorica del canale

(

)

2

log 1

C

=

+

SNR

(3.2.9)

ed è invece pari alla capacità di un canale equivalente in cui SNR è ridotto di un fattore

Γ

. SNR gap è quindi una misura della perdita rispetto alle performance ottime

teoriche, dovuta al fatto che il segnale inviato sul canale non ha distribuzione gaussiana. Sottolineiamo che la misura delle prestazioni in termini di SNR gap è una

approssimazione, comunque molto buona per rapporti segnale-rumore abbastanza elevati.

3.3

L’ALGORITMO DI ALLOCAZIONE WATERFILLING CON

SNR GAP

In generale esistono fondamentalmente due tipi di approccio che possono essere seguiti per realizzare una efficiente allocazione delle risorse:

• MMP (Margin Maximisation Problem); • BRMP (Bit Rate Maximisation Problem);

MMP cerca di minimizzare la potenza utilizzata fissato il bit rate e la qualità del

servizio, mentre BRMP si prefigge di massimizzare il bit rate avendo fissato un vincolo sulla potenza totale a disposizione e, ancora, sulla qualità della trasmissione.

Noi ci concentreremo in particolare su BRMP.

La formulazione matematica del problema e’ fondamentalmente la stessa già

considerata nel paragrafo 3.1, ma adattata al caso di uso di costellazioni di modulazione reali tramite l’utilizzo del gap. In particolare si deve trovare

2 2 2 1

max

log 1

k N k k p k n

p H

σ

=





+







_Γ







∑

(3.3.1)

soggetto alla condizione

1 N k T k

p

P

=

≤

∑

(3.3.2) k

p

è la potenza allocata sulla portante k-esima

T

P

è la potenza totale disponibile

2

k

H

rappresenta il guadagno di canale sulla portante k-esima

2

n

σ

è la varianza del rumore gaussiano

Γ

è il valore di SNR gap

Si tratta di un tipico problema di massimo vincolato, che trova soluzione con l’utilizzo della tecnica dei moltiplicatori di Lagrange. Si ottiene la seguente soluzione [15]:

2 2 k k k

p

H

σ

λ

Γ

=

−

(3.3.3)

dove

λ

è detto “water level”, ed è definito come

' 2 2 ' ' 1

1

K n T l _l

P

K

K

_H

σ

λ

=

Γ

=

+

∑

(3.3.4)

essendo K’ il numero di portanti utili. Infatti la soluzione waterfilling può

evidentemente produrre anche valori di

p

_k negativi che, tuttavia, non hanno alcun significato fisico. Le portanti con allocazione negativa devono essere scartate e l’intero algoritmo reiterato, fino ad ottenere solo potenze positive ed individuando quindi, contestualmente, un insieme di portanti idonee alla trasmissione.

L’allocazione di bit come funzione dell’allocazione di potenza è data da:

2 2 2

log 1

k k k n

p H

m

σ





=



_

+



_

Γ





(3.3.5)

Notiamo infine che, con alcuni passaggi algebrici, a partire dalla (3.3.3) e dalla (3.3.5) è possibile ottenere: ' 2 ' 2 ' 2 1

2

mk

1

K

1

T l n k l

P

K

K

H

σ

=

H

=

+

Γ

∑

(3.3.6) cioè il rapporto

2

₂ k m k

H

risulta uguale su tutte le sottoportanti utili. In pratica

l’allocazione water-filling tende ad equalizzare la BER (Bit Error Rate) sui canali utilizzabili in trasmissione.

3.4

ALGORITMI EFFICIENTI DI ALLOCAZIONE RISORSE

Come già affermato in precedenza, la tecnica di allocazione risorse water-filling pura massimizza l’informazione mutua su un set di sottocanali paralleli gaussiani con

ingressi gaussiani, ed in quel contesto costituisce una soluzione ottima. Per tenere conto della granularità delle costellazioni in trasmissioni reali, l’algoritmo di allocazione deve essere modificato, ad esempio introducendo, come visto in precedenza, il concetto di SNR gap, che introduce una approssimazione ma permette di mantenere la stessa formulazione matematica del problema. Molti algoritmi sono stati prodotti, e sono disponibili in letteratura, per realizzare in modo efficiente questo tipo di allocazione, cercando un compromesso fra l’introduzione di approssimazioni, e quindi perdita di prestazioni dell’allocazione risorse, e complessità computazionale.

Nel seguito riportiamo gli algoritmi più importanti presenti in letteratura.

3.4.1 L’ALGORITMO DI HUGHES-HARTOGS

Consideriamo la situazione in cui, dato un certo numero Ns di sottoportanti e fissato il set di modulazioni M-QAM ( tipicamente M = {0,4,16,64} ), si debba allocare potenza e bit su ogni canale, massimizzando il rate totale e rispettando un vincolo sulla potenza totale da trasmettere

P

_T. Si considera ,inoltre, un livello di bit error rate BER0, che fissa il requisito minimo di qualità della trasmissione e che non può essere superato su nessuna sottoportante. E’ noto che la BER su ogni sottocanale dipende dal rapporto fra l’energia media per bit e la potenza di rumore. La prima dipende dal formato di modulazione scelto, ed in particolare diminuisce al crescere della complessità dei

simboli trasmessi, mentre la seconda dipende dalla varianza del rumore gaussiano e dalla risposta in frequenza del canale, affetto da fading in frequenza. L’attenuazione di un canale selettivo in frequenza è, per definizione, diversa sulle varie sottoportanti e, volendo mantenere praticamente costante e prossima al valore massimo consentito la BER sui vari canali, è necessario agire sul formato di modulazione da assegnare ad ogni portante frequenziale : ai canali afflitti da forte attenuazione verrà assegnata una modulazione a bassa complessità e, viceversa, sui canali che sperimentano un maggior guadagno di canale sarà possibile trasmettere con elevata efficienza spettrale. Un’osservazione importante, sulla quale si basa l’algoritmo in questione, riguarda il fatto che, fissato un livello di BER da rispettare, ogni costellazione di modulazione richiede un certo valore del rapporto Eb/N0 e, di conseguenza, una certa potenza in trasmissione, noto il canale. E’ ovvio che costellazioni numerose richiedono una maggiore potenza trasmissiva a parità di BER nei confronti di costellazioni semplici.

Ma entriamo nel dettaglio del funzionamento dell’algoritmo di Hughes-Hartogs [17]. Per ogni canale si calcola il rumore equivalente, definito come la potenza di rumore misurata al ricevitore moltiplicata per l’attenuazione del segnale. Naturalmente il rumore equivalente è diverso su ogni sottoportante, poiché stiamo considerando una trasmissione su canale affetto da fading selettivo in frequenza. Per ogni sottoportante si determinano quindi i livelli di potenza trasmissiva necessari per sostenere le diverse modulazioni M-QAM, moltiplicando i valori di rumore equivalente e i rapporti segnale-rumore richiesti a BER fissata. Fatto ciò, è possibile calcolare le potenze marginali

MP(N1,N2) che indicano la potenza necessaria a passare da N1 bit/simbolo a N2

_{1 2} 2 1 2 1

( ,

)

P

P

MP N N

N

N

−

=

−

(3.4.1)

A questo punto, partendo da una allocazione di bit e potenza nulla, si seleziona il canale con la minore MP(0,2) e ad esso si assegnano 2 bit e la relativa potenza richiesta. La potenza marginale associata a questo canale sarà adesso la MP(2,4), mentre per gli altri sarà ancora la MP(0,2). Ulteriori 2 bit si aggiungono quindi nuovamente alla portante con potenza marginale minima, e così via, fino all’esaurimento della potenza disponibile. In altri termini, si incrementano i bit 2 per volta, assegnandoli ad ogni passo al canale che richiede una potenza aggiuntiva minore per realizzare l’incremento di complessità della modulazione a BER fissata.

L’idea di base dell’algoritmo è semplice ed intuitiva, non altrettanto la realizzazione pratica. Infatti sono in generale necessarie molte scansioni dell’intero set di sottoportanti utili per decidere l’allocazione di risorse, e ciò è particolarmente oneroso nel caso in cui il numero di canali Ns sia elevato. La complessità computazionale, del tipo

( )

(

log

)

O N

N

, si traduce in una lentezza che rende inadatto il procedimento descritto per sistemi veloci con elevato numero di bit per simbolo ed elevato numero di sottoportanti.

Concludiamo notando che l’algoritmo di Hughes-Hartogs, che ha lo scopo di approssimare la tecnica di allocazione water-filling, a differenza di quest’ultima non raggiunge la capacità di canale, ma massimizza la quantità di informazione trasmessa fissato un insieme di modulazioni QAM e una potenza totale disponibile. Inoltre questo procedimento, pur non avendo pretese di ottimalità dal punto di vista teorico, nella pratica si rivela il modo migliore per riprodurre la tecnica water-filling in un contesto di

modulazioni a granularità finita. Peccato che l’eccessiva complessità computazionale ne renda praticamente improponibile l’applicazione pratica.

3.4.2 L’ALGORITMO DI CHOW, CIOFFI E BINGHAM

Il principale obbiettivo di questo procedimento consiste nell’approssimare l’allocazione water-filling con SNR gap con bassa complessità computazionale, superando le difficoltà implementative emerse nell’algoritmo di Hughes-Hartogs. L’algoritmo in questione cerca di avvicinare il più possibile la capacità di canale (channel achieving algorithm); viene tuttavia preso come riferimento un valore fissato di rate da ottenere, che in seguito chiameremo Btarget.

L’algoritmo è composto di 3 sezioni principali [18]:

1) Dopo aver calcolato il rapporto segnale-rumore su ogni sottoportante considerando un livello di energia normalizzata ε(i)=1 per ogni i, si scorrono tutti i canali calcolando per ognuno un’allocazione continua di bit.

dove

Γ

è il valore SNR gap e

γ

_margin è il margine di performance del sistema, definito come la quantità di rumore aggiuntivo che il sistema può tollerare continuando a rispettare i requisiti di bit error rate.

I

b i

( )

vengono quindi arrotondati, secondo il criterio del minimo errore quadratico medio, ai più vicini valori consentiti dal set di modulazioni in uso (0,2,4,6). Viene contestualmente calcolato l’errore di quantizzazione

diff i

( )

, inteso come differenza fra

b i

( )

e il valore approssimato.

(3.4.3)

(3.4.4)

Viene anche aggiornato il valore

γ

_margin che inizialmente era pari a zero db, e

decrementato il numero di portanti utili nel caso in cui alcuni

( )

^

b i

risultino nulli.

(3.4.5)

Si calcola quindi il numero totale di bit allocati .Il ciclo si ripete se il numero di bit allocati

B

_tot è diverso dal valore di riferimento

B

_target. In ogni caso, dopo

un numero massimo di iterazioni

Maxcount

viene forzata la chiusura del ciclo.

2) Si entra in un nuovo loop che produce una soluzione subottima con un numero limitato di iterazioni.In particolare:

• Se Btot>Btarget viene decrementato il numero di bit sulla portante con il più piccolo diff(i),e il diff(i) in questione viene aggiornato

• Se Btot<Btarget viene aumentato il numero di bit sulla portante con il più grande diff(i),e il diff(i) corrispondente viene aggiornato

Tutto ciò finchè Btot = Btarget.

3) Alla fine si applica una distribuzione di potenza tale che, con l’ allocazione di bit calcolata, si abbia la stessa probabilità d’errore su ogni sottoportante. La potenza viene quindi scalata in modo che soddisfi ad un eventuale vincolo sulla potenza totale disponibile.

L’algoritmo di Cioffi e al. risulta subottimo rispetto a quello di Hughes-Hartogs ma, a fronte di un’ accuratezza di poco inferiore, offre notevoli vantaggi in termini computazionali. Basti pensare che il procedimento di Hughes-Hartogs avrebbe una complessità dell’ordine di

O B N

(

_{tot S}

)

, mentre il numero di operazioni per

l’algoritmo in questione è proporzionale, nel peggiore dei casi, a

(

)

(

_S

2

)

O N

Maxcount

+

, dove tipicamente

Maxcount

=

10

.

3.4.3 L’ALGORITMO DI CAMPELLO

Questo procedimento [19] si basa sulla gap approximation e cerca di risolvere il problema MMP. E’ comunque possibile, con qualche aggiustamento, adattare l’algoritmo a risolvere il problema BRMP.

Definendo 2 2 n n n

H

g

σ

=

Γ

(3.4.6)

il numero di bit allocabili su ogni portante risulta

2

log 1

2

n n n

p g

b

=



_

+



_





(3.4.7)

Poiché nello specifico consideriamo il problema MMP, il bit rate è fissato e pari a B, e l’obbiettivo è trovare la distribuzione di bit e potenza tale da minimizzare l’energia totale spesa per realizzare la trasmissione. Una distribuzione di bit

b

− è soluzione del problema se

( )

(

2

)

n n m m

p b

p

b

∆

≤ ∆

+

(3.4.8)

dove

∆

p b

_n

( )

rappresenta la potenza necessaria per passare dalla trasmissione di

2

b

−

a quella di

b

bit. Le allocazioni di bit che soddisfano (3.4.8) sono dette efficienti.

Si dimostra che l’allocazione di bit

b i

( )

− tale che

( )

log

( )

₀b n n

b i

_δ

g

i

−





=

_



_



_

+

_

(3.4.9) È efficiente

∀

i

. Nella (3.4.10) il simbolo

[ ]

b a

x

indica che X è pari a: • X se

a

≤ ≤

x

b

•

b

se

x

≥

b

•

a

se

x

≤

a

e inoltre

δ

=

2

β,

β

è tale che il numero di bit allocati su ogni portante è un suo

multiplo (in genere

β

=

2

) e

b

−

è il valore massimo di bit allocabili su una portante (tipicamente è pari a 6).

E’ necessario, a questo punto, trovare i tale che il numero totale di bit allocati sia più prossimo possibile al valore

B

scelto come target. Ciò viene fatto in modo efficiente partendo dal valore i = 0 e aumentando ( o decrementando ) tale valore fino a giungere alla soluzione. Nel far ciò si sfrutta il fatto che i sottocanali che hanno lo stesso valore di



_

log

_δ

( )

g

_n



_

possono essere raggruppati nel calcolare

i

_B.

Una volta individuato

i

_B e il corrispondente numero di bit allocati

b i

( )

_B , per raggiungere esattamente il bit rate target

B

,è necessario incrementare i

B

−

b i

( )

_B

• Appartengono all’insieme

{

}

( )

{

1,2,...,

: 0

log

_{n B}

}

I

n

N

_δ

g

i

b

−

=

∈

≤



_



_

+

≤

• Sono caratterizzati dai più piccoli

∆

p b

_n

(

_n

+

2

)

Quest’ultimo passo dell’algoritmo può essere realizzato efficacemente o con la tecnica

Order Statistic o con il Counting sort algorithm [20].

Il punto di forza di questo procedimento è la bassa complessità computazionale, anche rispetto all’algoritmo di Cioffi; questa è infatti dell’ordine di

O N

( )

, a fronte di una perdita di prestazioni rispetto al caso ideale generalmente trascurabile e quantificabile in frazioni di db. Altra caratteristica importante è la possibilità di conoscere esattamente il numero di operazioni necessarie, visto che dipende solamente dalla dimensione dei parametri in ingresso all’algoritmo e non dai parametri stessi. Per esempio, nel procedimento di Cioffi , sono presenti cicli la cui velocità di convergenza dipende dai valori assunti dai parametri d’ingresso e non è quindi possibile stabilire a priori il numero esatto di operazioni che saranno necessarie, ma solo un valore medio atteso. La possibilità di conoscere a priori il numero di operazioni necessarie a risolvere il

problema di allocazione risorse è una peculiarità dell’algoritmo di Campello.

3.4.4 L’ALGORITMO DI FISCHER E HUBER

Questo procedimento [21] si differenzia dai precedenti già nell’approccio al problema: non si cerca di raggiungere la capacità di canale, ma di minimizzare la probabilità d’errore fissato il bit rate e la potenza totale disponibile.

Affinchè il sistema raggiunga prestazioni ottime è necessario che la probabilità d’errore sia uguale su tutte le sottoportanti: in caso contrario la probabilità d’errore totale

sarebbe dominata dal termine maggiore. Poiché su ogni canale

{

}

^ 0

Pr

2

n n n _n

d H

x

x

Q

N





≠



_



_





(3.4.10)

con

d

_nminima distanza euclidea fra i punti della costellazione, l’obbiettivo è ottenere

2 2 0 0

4

n n

d H

SNR

const

N

=

=

(3.4.11)

Tale valore, oltre che costante, dovrà essere anche il massimo possibile. Considerando anche le condizioni su potenza e bit rate

1 N T n n

R

R

const

=

=

∑

=

(3.4.12) 1 N T n n

P

p

const

=

=

∑

=

(3.4.13) E definendo _i 0₂ i

N

N

H

=

, si può dimostrare che la migliore partizione di

R

_T fra i

( )

( )

2 2 '

log

log

T l l I i i

R

N

R

N

N

∈

+

=

−

∑

(3.4.14)

Dove

I

è l’insieme delle portanti utili e

N

' è il numero di tali portanti. Infatti l’algoritmo può produrre valori negativi e le portanti corrispondenti devono essere escluse e l’algoritmo reiterato finchè tutti i

R

_i risulteranno positivi. Il grande vantaggio sta nel fatto che i

log

₂

( )

N

_i possono essere calcolati una volta per tutte all’inizio della procedura con una notevole riduzione di complessità computazionale.

Fino a questo punto abbiamo assunto che

R

_i potesse assumere qualsiasi valore reale, mentre in realtà potrà assumere valori discreti appartenenti ad un set finito, fissato dalle modulazioni disponibili: in genere i valori di allocazione possibili sono 0,2,4,6. E’ necessaria quindi un’operazione di quantizzazione, realizzata secondo il criterio del minor errore quadratico medio, al termine della quale avremo ottenuto una allocazione di bit tale da produrre un bit rate, in generale, diverso dal target

R

_T. Si rende necessaria una procedura di rate adjustement che, nella pratica, è assolutamente identica a quella implementata nell’algoritmo di Cioffi, cioè:

• Se il rate ottenuto è maggiore di

R

_T, bisogna decrementare il numero di bit sulla portante con il valore di errore di quantizzazione minore

• Se il rate ottenuto è minore di

R

_T, è necessario aumentare il numero di bit sulla portante con il valore di errore di quantizzazione maggiore

L’ultimo passo da effettuare è l’allocazione della potenza, la quale deve essere distribuita in modo che su tutti i sottocanali venga sperimentata la stessa probabilità d’errore. Si dimostra che deve essere

2

2

Qi Ql R T i i R l l I

P N

p

N

∈

=

∑

(3.4.15)

dove

R

_Qi indica i bit quantizzati assegnati alla portante i-esima, e ovviamente

i

∈

I

.

In Fig.3.3 riportiamo un diagramma che esemplifica il procedimento descritto.

L’algoritmo di Fischer è forse il più interessante algoritmo di allocazione efficiente presente in letteratura. Confrontato con la tecnica di Cioffi produce prestazioni migliori o uguali, ma con una notevole riduzione in complessità che lo rende un credibile candidato per uno sfruttamento in sistemi multiportante reali.