Academic literature on the topic 'Pseudo-codewords'

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.

In the last six years, we have witnessed an explosion of interest in the coding theory community, in iterative decoding and graphical models, due primarily to the invention of turbo codes. While the structural properties of turbo codes and low density parity check codes have now been put on a firm theoretical footing, what is still lacking is a satisfactory theoretical explanation as to why iterative decoding algorithms perform as well as they do. In this thesis we make a first step by discussing the behavior of various iterative decoders for the graphs of tail-biting codes and cycle codes. By increasing our understanding of the behavior of the iterative min-sum (MSA) and sum-product (SPA) algorithms on graphs with cycles, we can design codes which achieve better performance. Much of this thesis is devoted to the analysis of the performance of the MSA and SPA on the graphs for tail-biting codes and cycle codes. We give sufficient conditions for the MSA to converge to the maximum likelihood codeword after a finite number of iterations. We also use the familiar union bound argument to characterize the performance of the MSA after many iterations. For a cycle code, we show that the performance of the MSA decoder is asymptotically as good as maximum likelihood. For tail-biting codes this will depend on our choice of trellis.

碩士<br>國立中正大學<br>通訊工程研究所<br>94<br>Earlier work of LDPC codes showed that Tanner graph mainly affects the decoding performance of iterative decoding. Pseudo-codewords and pseudo-weights on Tanner graph are found playing an important rule in determining the performance. Computation tree and graph covers are proposed by different researchers to find the pseudo-codewords and pseudo-weights. Definitions of pseudo-codeword using computation tree and graph-cover are somewhat different. Actually, neither computation tree or graph-covers is a good tool to analysis any known codes. In this thesis we will introduce both approachers and the corresponding algorithms. Also, the simulation result will be shown.