Fagnani Fabio

Homepage


Ensembles of turbo and low density codes




A thesis on this topic?

A PhD fellowship on this topic?




Coding theory, in the last 60 years, had been studying the way to realiably transmit information along a noisy channels. In the last 15 years fundamental achievements have been obtained with the invention of the so-called turbo codes and the rediscover and analysis of low density codes. Turbo-codes consist of two convolutional encoders interconnected (in a serial or parallel scheme) by means of a long permutation which is typically chosen in a random fashion; low-density codes instead are block codes which can be represented through very sparse syndrome matrices. A common property shared by these two familes of codes is that both can be efficiently decoded through a low complexity subotpimal decoding algorithm (known as iterative decoding) which applies to the graphical representations of such codes. Both families turn out to be quite good and allow to get very close to Shannon theoretical limit. The performance analysis is typically done averaging over an ensemble of possible codes, since the analysis of a single code turns out to be to difficult. The typical ensemble considered in the turbo case is the one obtained by fixing the two encoders and then considering all possible interleaving permutations, while in the low density case the ensemble is the set of all possible syndromes with certain specified number of one's in rows and columns. Concentration analysis for such ensembles is in many cases still missing.

An important problem still open is that of finding codes sharing the good properties of both turbo and low density codes, namely linear complexity at the encoding level and a sparse syndrome as a low density. An interesting family of such codes can be constructed by considering multiple turbo codes with a systematic branch. An interesting question is if the classical theory of low density codes (density evolutions, thresholds, area theorems) can be extended to these new codes.

In application where delays are a crucial issue (for instance when the communication channel is used for control or estimation purpouses), it is important to be able to construct coding/decoding schemes capable of working on-line. This is not at all a trivial extension of classical coding theory since essentially all the available coding schemes do not have this property: decoding is done only at the end of the transmission. Recently introduced digital fountain codes form a promising family of codes for such applications but most work still needs to be done.

Most of modern coding theory has been developped for channels with binary inputs. In many situations, however, is necessary to consider more general non-binary transmission channels: a typical example is the multi-dimensional Gaussian channel with the inputs forming geometrically uniform constellation (e.g. the 8-PSK constellation consisting of the 8 vertices of a regular octagon centered in the origin). While on binary channels, binary linear codes play a fundamental role, on these new channels, codes with a group or ring structure become more natural. The goal is to extend to this setting the construction of codes available for the binary case: convolutional codes, turbo interconnections, low-denmsity schemes. Main mathematical difficulties we have to face are mostly of algebraic nature since we are replacing vector spaces with more complex algebraic structures. The theory of group over codes has shown important connections with symbolic dynamics.


Specific reaserch topics:

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'.

Publications:

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, submitted, 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.

Papers in conferences

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), July 2008.

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.

PhD thesis

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.

Master thesis

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.