Fagnani Fabio

Homepage


Ensemble di codici turbo e low density




Una tesi su questo argomento?

Una borsa PhD su questo argomento?




La teoria dei codici da circa 60 anni studia il modo di trasmettere informazioni su canali disturbati nel modo più fedele possibile. Negli ultimi 15 anni sono stati fatti passi enormi grazie all'invenzione di due famiglie di codici binari particolarmente importanti: i turbo-codici ed i codici low-density. I turbo-codici consistono di due codificatori convoluzionali interconnessi (in serie od in parallelo) attraverso una lunga permutazione che tipicamente viene scelta in modo casuale; i codici low-density sono invece codici a blocco la cui matrice sindrome è una matrice sparsa con pochi elementi non nulli. Sono accumunati dal fatto che uno stesso tipo di decodifica a bassa complessità (detta decodifica iterativa) si può usare efficacemente per entrambi utilizzando le rappresentazioni a grafo di Tanner e a traliccio per questi codici. Inoltre, con entrambi si sfiorano i limiti teorici posti da Shannon alla quantità di informazione che si può fedelmente trasmettere su un canale. L'analisi della probabilità di errore tipicamente viene fatta mediando su un ensemble di questi codici essendo l'analisi per il singolo troppo difficile. Nel caso dei codici turbo tipicamente si media su tutte le possibili permutazioni mantenendo fissi i due codificatori, mentre per i low-density si considera un ensemble omogeneo di matrici sparse (ad esempio stessa densità di 1). L'analisi delle fluttuazioni intorno alla media è in molti casi ancora mancante, in particolare quando si utilizzano algoritmi di decodifica iterativa.

Rimane ancora un problema centrale quello di trovare codici che uniscano i vantaggi delle due categorie: complessità lineare di codifica tipica dei turbo, struttura del grafo di Tanner come un low-density per sfruttarne le caratteristiche in fase di decodifica. Una possibile famiglia di codici con queste caratteristiche si può costruire considerando interconnessioni turbo seriali multiple accoppiate con un ramo sistematico. Una questione interessante è capire se la teoria classica dei codici 'low density' (evoluzione delle densità, soglie di convergenza, theoremi di area) si può estendere a questa nuova famiglia.

Nelle applicazioni dove i ritardi sono cruciali (ad esempio nel caso di canali di comunicazione usati per scopi di controllo o stima), è importante costruire schemei di codifica/decodifica in grado di lavorare 'on-line'. Questa non è affatto un'estensione banale della teoria classica dei codici poichè in generale gli schemi di codifica classici non hanno questa proprietà: la decodifica è fatta soltanto alla fine della trasmissione. I codici a fontana di recente introduzione formano una famiglia particolarmente promettente di codici per schemi di codifica/decodifica sequenziale ma la maggior parte del lavoro rimane da fare.

La maggior parte della moderna teoria dei codici si è sviluppata per canali di trasmissione ad ingresso binario. In molte situazioni è tuttavia necessario considerare canali di trasmissione non binaria; tipici esempi sono il canale Gaussiano con gli ingressi ristretti ad una costellazione dello spazio euclideo geometricamente uniforme (ad esempio la 8-PSK dove si considerano 8 segnali sul piano che formano i vertici di un ottagono regolare centrato nell'origine). Mentre per i canali binari i codici binari lineari giocano un ruolo fondamentale, su questi nuovi canali diventano fondamentali i codici con struttura di gruppo o di anello. L'obbiettivo è di estendere a questo nuovo contesto le costruzioni di codici e gli algoritmi di decodifica noti nel caso lineare: i codici di convoluzione, le interconnessioni turbo, gli schemi a bassa densità. Le difficoltà che si incontrano matematicamente sono essenzialmente dovute al fatto che se deve passare dall'algebra lineare sul campo binario, alla teoria dei gruppi e degli anelli. Come è facile intuire questo comporta tutta una serie di problem tecnici che sono del tutto assenti nel caso binario. Alcuni aspetti della teoria dei codici su gruppi ha mostrato anche interessanti collegamenti con la dinamica simbolica.


Argomenti specifici di ricerca:

1. Codici ottenuti con interconnessioni seriali multiple: Analisi delle distanze e delle probabilità di errore, comportamenti asintotici.

2. Ensemble di codici LDPC strutturati: Analisi delle prestazioni 'maximum likelihood'. Algoritmi di decodifica iterativa che operano sul cluster di nodi e di check. Analisi della decodifica iterativa mediante la 'density evolution'.

3. Ensemble di codici su gruppi: Capacità, distanze, esponenti di errore.

4. Ensemble di codici LDPC e turbo su gruppi: Analisi delle prestazioni ML. Analisi della decodifica iterativa mediante la 'density evolution'.

Pubblicazioni:

F. Fagnani, C.Ravazzi, Spectra and Minimum Distances of Repeat Multiple Accumulate codes, submitted to IEEE Trans. on Inform. Theory, 2008.

F. Garin, F. Fagnani, Analysis of serial turbo codes over Abelian groups for Geometrically Uniform constellations, SIAM J. on Discrete Mathematics, 22, pp. 1488-1526, 2008. DOI: 10.1137/07068802X

G. Como, F. Fagnani, Average spectra and minimum distances of low density parity check codes over cyclic groups, SIAM J. on Discrete Mathematics, 23, pp. 19-53, 2008. DOI: 10.1137/070686615

G. Como, F. Fagnani, The capacity of Abelian group codes over symmetric channels, IEEE Trans. Inf. Theory, 2005, to appear.

F. Fagnani, Performance of parallel concatenated schemes , IEEE Trans Inf. Theory, IEEE Trans Inf. Theory 54 (4), pp.1521-1535, 2008.

F. Fagnani, S. Zampieri, Minimal and systematic convolutional codes over finite Abelian groups, Linear Algebra Appl., 378, pp.31-59, 2004.

F. Fagnani, S. Zampieri, System theoretic properties of convolutional codes over rings, IEEE Trans. Inform. Theory, 47 (6), pp.2256-2274, 2001.

F. Fagnani, S. Zampieri, Minimal syndrome formers for group codes, IEEE Trans. Inform. Theory, 45 (1), pp.3-31, 1999.

F. Fagnani, Shifts on compact and discrete Lie groups: algebraic-topological invariants and classification problems, Adv. Math. 127, pp. 283-306, 1997.

F. Fagnani, S. Zampieri, Classification problems for shifts on modules over a principal ideal domain, Trans. Amer. Math. Soc., 349, pp. 1993-2006, 1997.

F. Fagnani, S. Zampieri, Dynamical systems and convolutional codes over finite abelian groups, IEEE Trans. Inform. Theory, 42, pp. 1892-1912, 1996.

F. Fagnani, Some results on the classification of expansive automorphisms of compact abelian groups, Ergodic Theory Dynam. Systems 16, pp. 45-50, 1996.

Contributi in conferenze

D. Capirone, G. Como, F. Fagnani, F. Garin, Non-binary Decoding of Structured LDPC Codes: Density Evolution, Proceedings of IEEE International Symposium on Information Theory (ISIT 2008), Toronto (Canada), 6-11 July 2008 pp. 950-954 2008.

D. Capirone, G. Como, F. Fagnani, F. Garin, Nonbinary decoding of structured LDPC codes, Proc. of 2008 International Zurich Seminar on Communications, (Zurich, CH), March 12-14, pp. 68-71, 2008.

F. Fagnani, C. Ravazzi, Spectra and minimum distances of multiple repeat-accumulate codes, Proc. of ITA workshop 2008, San Diego, Jan.27-Feb.1, pp.77-86, 2008.

G. Como, F. Fagnani, On the Gilbert-Varshamov distance of Abelian group codes, Proceedings of ISIT IEEE Int. Symposium on Information Theory, 24-29 June 2007, pp. 2651 - 2655, 2007.

F. Garin, G. Como, F. Fagnani, Staircase and other structured linear-time encodable LDPC codes: analysis and design, ISIT IEEE Int. Symposium on Information Theory, 24-29 June 2007, pp. 1226 - 1230, 2007

F. Fagnani, R. Garello, F. Garin, Average ML Asymptotic Performances of Different Serial Turbo Ensembles, ISIT IEEE Int. Symposium on Information Theory 2006, pp:572- 576, 2006.

G. Como, F. Garin, F. Fagnani, ML Performances of Serial Turbo Codes do not Concentrate, Proc. of the 4th International Symposium on Turbo Codes and Related Topics (Munich, Germany), April 2006. F. Fagnani, F. Garin, Analysis of serial concatenation schemes for non-binary modulations, ISIT IEEE Int. Symposium on Information Theory 2005, Adelaide, pp.745-749, 2005.

G. Como, F. Fagnani, Ensemble of codes over Abelian groups, ISIT IEEE Int. Symposium on Information Theory 2005, Adelaide, pp. 1788-1792, 2005.

Tesi di dottorato

Giacomo Como, Ensembles of codes over Abelian groups, Politecnico di Torino, 2008

Federica Garin, Generalized serial turbo coding ensembles: analysis and design, Politecnico di Torino, 2008.

Tesi di laurea

Chiara Ravazzi, Interconnessioni seriali muliple: probabilità di errore e distanze minime Politecnico di Torino, 2007.

Valentina Martina, Interconnessioni seriali multiple per modulazioni non binarie, Politecnico di Torino, 2007

Marta Sanz, Schemi di interconnessione turbo paralleli non classici, Politecnico di Torino, 2006

Dario Giannoccaro, Codici a bassa densità con sindromi strutturate, Politecnico di Torino, 2006

Giulia Ajmone Marsan, Codici su strutture di gruppo semidirette, Politecnico di Torino, 2005.

Giacomo Como, Ensemble di codici su gruppi Abeliani, Politecnico di Torino, 2004.

Federica Garin, Codici turbo seriali su anelli per modulazioni non binarie, Politecnico di Torino, 2004.