Presentiamo adesso alcune conclusioni che si possono trarre da quello che abbiamo detto. Al di là delle varie osservazioni parziali fatte durante il lavoro, riguardanti la giusti cazione della bontà dei codici LDPC e del
Figura 6.3: Regione della capacità per canale ad accesso multiplo gaussiano
sistema CDMA, si possono ricavare osservazioni più generali. Premesso che le applicazioni del teorema della capacità coprono altri casi interessanti nelle telecomunicazioni (capacità di canale in presenza di rumore colorato, capacità del canale broadcast), si possono fornire tre conclusioni in ordine crescente di generalità.
Prima conclusione
La prima conclusione è semplicemente pratica e nasce dall'uni cazione del concetto di codici LDPC e di sistema CDMA. Benché il teorema della capacità per canali ad accesso multiplo indichi l'esistenza di un codice multi- utente che rende la probabilità di errore piccola a piacere, resta il problema dovuto al fatto che, per esempio, in un sistema radiomobile con diversi tipi di tra co e un numero di utenti variabile la regione della capacità varia nel tempo.
Avremmo quindi bisogno, se usassimo codici LDPC, di matrici di parità diverse per ogni apparecchio e variabili in funzione del tempo.
I codici di spreading rendono unica la parola di codice per ogni apparec- chio.
In pratica la codi ca si realizza nel terminale mobile con il contributo della stazione radio.
Nel sistema UMTS si utilizzano i Turbocodici, ma il discorso rimane concettualmente valido.
Seconda conclusione
Sia il sistema CDMA, sia i codici LDPC, sono tecnologie relativamente recenti, benché concepiti almeno tre decenni fa.
Questo indica che la teoria dell'informazione è alla base delle scelte tec- nologiche dei sistemi di telecomunicazione degli ultimi decenni. Gli esempi potrebbero essere molti altri e anche in altri campi come l'informatica dove la tecnica di codi ca universale (che rientra nella compressione senza perdite) trova la sua dimostrazione ancora nel teorema della capacità di Shannon.
Nauralmente le indicazioni della teoria dell'informazioni hanno un prezzo: si tratta dell'aumento della complessità dei sistemi. In molti casi la sempli- cità, che si traduce in particolare in a dabilità oltre che in una generale questione economica, può essere in certi casi la scelta migliore.
Terza conclusione
Il legame tra la teoria della probabilità e la teoria dell'informazione è sicuramente molto stretto ed esistono diversi modi di introdurre quest'ultima. In questo lavoro abbiamo scelto di introdurre l'entropia e le altre gran- dezze semplicemente de nendole ed utilizzando le proprietà della probabilità per svilupparle.
mazione ovvero si può far derivare la teoria della probabilità dalla teoria dell'informazione.
Concludiamo il lavoro osando aermare che, se la legge dei grandi nume- ri appartiene alla teoria della probabilità, il vero snodo tra le due teorie è rappresentato dal teorema di equipartizione asintotica.
Per cui l'espressione
lim n→+∞Pr −1 nlog pSn(S n ) − H(S) < ,
considerando la frequenza con cui ritorna nella teoria dell'informazione, può essere ritenuta il suo fondamento teorico (e sperimentale per n tendente all'in nito).
Appendice A
Analisi delle caratteristiche delle
sequenze tipiche
Riportiamo una funzione Matlab per fornire alcuni elementi sperimentali sulle sequenze tipiche. Data una variabile aleatoria binaria, la funzione vuo- le come variabili di ingresso il numero di prove ripetute, la probabilità p e l'intervallo in cui varia . Fornisce in uscita tre gra ci che indicano, rispetti- vamente, il numero di sequenze tipiche, la percentuale di sequenze tipiche e la probabilità dell'insieme tipico.
function dati=aepst(n,emin,emax,p) close all;
clear all;
display('La funzione grafica il numero di sequenze tipiche,');
display('la percentuale di sequenze tipiche su tutte le sequenze,'); display('e la probabilità dell''insieme tipico,');
display('nel caso di variabile aleatoria binaria.');
display('Deve essere fissato il numero n delle prove ripetute,'); display('la probabilità di successo p');
display('e l''intervallo [emin,emax].' ); n=input('Numero prove ripetute:');
emin=input('Limite inferiore come potenza di 10:'); emax=input('Limite superiore come potenza di 10:'); p=input('ProbabilitÓ di successo:'); H=-(p*log2(p)+(1-p)*log2(1-p)); for k=0:1:n ps(1,k+1)=p.^k*(1-p).^(n-k); end numel=25;
for pul=1:1:numel ct(pul)=0; pst(pul)=0; end eps=logspace(emin,emax,numel); for nn=1:1:numel in=2.^-(n*H+n*eps(nn)); up=2.^-(n*H-n*eps(nn)); for k=0:1:n if(in<ps(1,k+1))&(ps(1,k+1)<up) bm=factorial(n)/(factorial(k)*factorial(n-k)); ct(nn)=ct(nn)+bm; pst(nn)=pst(nn)+bm*ps(1,k+1); end end end subplot(1,3,1); plot(eps,ct), xlabel('\epsilon'),
ylabel('Numero sequenze tipiche'); rap=(ct/(2^n))*100;
subplot(1,3,2); plot(eps,rap),
xlabel('\epsilon'),
ylabel('Percentuale sequenze tipiche'); subplot(1,3,3);
plot(eps,pst),
xlabel('\epsilon'),
ylabel('Probabilità insieme sequenze tipiche');
Si osservi che n dipende da e, ssato , per n maggiore di un certo ¯n, la probabilità dell'insieme tipico rimane praticamente unitaria.
Appendice B
Caratteristica di una matrice di
parità casuale
Queste due funzioni Matlab calcolano la media e la varianza della carat- teristica di n matrici di dimensioni p × q. Il gra co mostra le caratteristiche delle n matrici. Nella prima funzione, la matrice è casuale composta da 0 ed 1 equiprobabili, nella seconda è sempre casuale ma con valori interi e distribuzione non uniforme1.
function stn=frk(n,p,q) close all;
clear all;
display('La funzione genera n matrici di parità casuali,'); display('grafica la caratteristica delle n matrici');
display('e calcola la media e la varianza statistica'); display('delle caratteristiche stesse.');
display('La distribuzione è uniforme.'); n=input('Numero matrici:'); p=input('Numero di righe:'); q=input('Numero di colonne:'); for i=1:1:n A=round(rand(p,q)); rkv(1,i)=rank(A); end plot(rkv),xlabel('Numero matrici'),ylabel('Caratteristica'); st=[mean(rkv) var(rkv)]; function stn=frkn(n,p,q)
close all; clear all;
display('La funzione genera n matrici di parità casuali,'); display('grafica la caratteristica delle n matrici');
display('e calcola la media e la varianza statistica'); display('delle caratteristiche stesse.');
display('La distribuzione non è uniforme.'); n=input('Numero matrici:'); p=input('Numero di righe:'); q=input('Numero di colonne:'); for i=1:1:n A=round(randn(p,q)); rkv(1,i)=rank(A); end plot(rkv),xlabel('Numero matrici'),ylabel('Caratteristica'); stn=[mean(rkv) var(rkv)];
Si noti che, in entrambi i casi, per piccole dimensioni della matrice, la varianza può essere alta, mentre per dimensioni maggiori la caratteristica è massima sempre.
Questo dimostra che, l'osservazione sulla caratteristica di una matrice di parità casuale, presente nel teorema della capacità nel caso di canale BSC, non è troppo stringente.
Questo comportamento della caratteristica è probabilmente dovuto alla proprietà di equipartizione asintotica: per n grande ogni riga (o colonna) è una sequenza tipica e queste, come sappiamo, sono equiprobabili. Questo intuitivamente può forse giusti care l'indipendenza lineare delle righe (o delle colonne) delle matrici.
Il secondo caso esempli ca quindi la proprietà di equipartizione asintotica a una distribuzione non uniforme.
Bibliogra a
[1] Robert B. Ash.: Information theory, Dover Publications, 1990.
[2] Thomas M. Cover, Joy A. Thomas: Elements of Information Theory, Wiley-Interscience, 2006.
[3] Giuseppe Gestri: Teoria dell'Informazione, ETS editrice, 1991.
[4] Charles M. Goldie, Richard G.E. Pinch: Communication Theory, Cambridge University Press, 1991.
[5] Richard W. Hamming: Coding and Information Theory, Prentice Hall, 1986.
[6] Giuseppe Longo: Teoria dell'Informazione, Bollati Boringhieri, 1980. [7] David J.C. MacKay: Information Theory, Inference and Learning
Algorithms, Cambridge University Press, 2003
[8] C. E. Shannon: A mathematical theory of communication, The Bell System Technical Journal, vol 27, lug e ott 1948.