Ever since the publication of Shannon's seminal work in 1948, the search for capacity achieving codes has led to many interesting discoveries in channel coding theory. Low-density parity-check (LDPC) codes originally proposed in 1963 were largely forgotten and rediscovered recently. The significance of LDPC codes lies in their capacity approaching performance even when decoded using low complexity sub-optimal decoding algorithms. Iterative decoders are one such class of decoders that work on a graphical representation of a code known as the Tanner graph. Their properties have been well understood in the asymptotic limit of the code length going to infinity. However, the behavior of various decoders for a given finite length code remains largely unknown.An understanding of the failures of the decoders is vital for the error floor analysis of a given code. Broadly speaking, error floor is the abrupt degradation in the frame error rate (FER) performance of a code in the high signal-to-noise ratio domain. Since the error floor phenomenon manifests in the regions not reachable by Monte-Carlo simulations, analytical methods are necessary for characterizing the decoding failures. In this work, we consider hard decision decoders for transmission over the binary symmetric channel (BSC).For column-weight-three codes, we provide tight upper and lower bounds on the guaranteed error correction capability of a code under the Gallager A algorithm by studying combinatorial objects known as trapping sets. For higher column weight codes, we establish bounds on the minimum number of variable nodes that achieve certain expansion as a function of the girth of the underlying Tanner graph, thereby obtaining lower bounds on the guaranteed error correction capability. We explore the relationship between a class of graphs known as cage graphs and trapping sets to establish upper bounds on the error correction capability.We also propose an algorithm to identify the most probable noise configurations, also known as instantons, that lead to error floor for linear programming (LP) decoding over the BSC. With the insight gained from the above analysis techniques, we propose novel code construction techniques that result in codes with superior error floor performance.

Dans cette thèse, nous abordons le sujet d'optimisation des méthodes utlisées pour l'évaluation de performance des codes correcteurs d'erreurs. La durée d'une simula- tion Monte Carlo pour estimer le taux d'erreurs dans un système de communication augmente exponentiellement avec l'accroissement du Rapport Signal sur Bruit (RSB). Importance Sampling (IS) est une des techniques qui permettent à réduire le temps de ces simulations. Dans ce travail, on a étudié et mis en oeuvre une version avancée d'IS, appelé Adaptive Importance Sampling (AIS), pour l'évaluation efficace des codes cor- recteurs d'erreurs aux taux d'erreur très bas. D'abord, nous présentons les inspirations et motivations en analysant différentes approches actuellement mises en pratique. On s'intéresse plus particulièrement aux méthodes inspirées de la physique statistique. Ensuite, basé sur notre analyse qualita- tive, nous présentons une méthode optimisée, appelé la méthode de Fast Flat Histogram (FFH) qui est intrinsèquement très générique. La méthode emploie l'algorithme de Wang-Landau, l'algorithme de Metropolis-Hastings et les chaines de Markov. Elle fonctionne dans le cadre de l'AIS et nous donne un gain de simulation satisfaisant. Différents paramètres sont utilisés pour assurer une précision statistique suffisante. L'extension vers d'autres types de codes correcteurs d'erreurs est directe. Nous présentons les résultats pour les codes LDPC et turbocodes ayant dif- férentes tailles et différents rendements. Par conséquent, nous montrons que la méthode FFH est générique et valable pour une large gamme des rendements, tailles et structures. De plus, nous montrons que la méthode FFH est un outil puissant pour trouver des pseudocodewords dans la région de RSB élévé en appliquant l'algorithme de décodage Belief Propagation aux codes LDPC.