Étude des propriétés des codes convolutionnels récursifs doublement-orthogonaux

Cette thèse propose l'étude des codes convolutionnels récursifs doublement orthogonaux (RCDO). Ces codes correcteur d'erreur trouvent leur source dans les travaux développés au cours des dernières années à l'École Polytechnique de Montréal et ont pour objectif de corriger les erreurs se produisant lors du transfert de l'information entre une source et un destinataire. Les codes RCDO représentent une famille de codes convolutionnels récursifs qui offrent des performances d'erreur qui s'approchent des limites prédites par la théorie pour les canaux de communications considérés dans cette thèse. Outre les excellentes performances d'erreur offertes par les codes RCDO, il s'avère que cette famille de codes correcteurs d'erreur peut être générée par un encodage qui est très simple à réaliser en comparaison avec des techniques de codage qui offrent des performances d'erreur similaires. De plus, le décodage de ces codes s'effectue à l'aide d'un décodeur itératif qui est composé d'une chaîne successive du même décodeur. Le nombre de décodeurs qui se succèdent dans la chaîne représente le nombre d'itérations effectuées lors du décodage. Le fait de répéter la même structure facilite grandement la conception du décodeur itératif, car uniquement la conception d'un seul décodeur doit être prise en compte pour réaliser l'ensemble du décodeur itératif. La simplicité de mise en oeuvre de la technique de codage proposée facilite donc les opérations d'encodage et de décodage et est ainsi adaptée à des sources d'information délivrant des symboles d'information à hauts débits et qui nécessitent de hautes performances d'erreur. Les objectifs de cette thèse sont multiples. Dans un premier temps, ce travail permet d'établir la correspondance entre les codes Low-Density Parity-Check (LDPC) et les codes RCDO. À partir de cette correspondance, il devient possible de quantifier un seuil de convergence asymptotique associé à une famille de codes RCDO. C'est-à-dire que sous ce seuil, la probabilité d'effectuer une erreur de décodage ne converge pas vers zéro. Nous avons aussi analysé la complexité associée aux opérations liées à l'encodage et au décodage des codes RCDO. Suite à ce travail, il devient donc possible d'imposer des critères de conception matérielle et ainsi générer les codes RCDO qui offrent les meilleurs seuils de convergence théorique.

Abstract

This thesis presents Recursive Convolutional Doubly-Orthogonal (RCDO) codes. These new error correcting codes represent a class of convolutionnal Low-Density Parity-Check (LDPC) codes that can be easily decoded iteratively. The doubly-orthogonal conditions of RCDO codes allow the decoder to estimate a symbol with a set of equations that are independent over two successive iterations. This reduces the error propagation throughout the iterative decoding process and therefore improves the error performances. The fondation of this research founds his source in recent works that has been presented in the last decade at École Polytechnique de Montréal. As presented in this document, the error performances of RCDO codes are near the Shannon capacity for the additive white gaussian noise and the binary erasure channels. In order to achieve these error performances, only a simple multi shift registers recursive convolutional encoder is required at the encoder. Moreover, the iterative decoder is realized only by concatenating, a certain number of time, the same simple threshold decoder. Therefore, the complete decoder is a cascade of the same threshold decoder. It follows that only the design of one simple threshold decoder is needed for constructing the complete iterative decoder. The implementation simplicities of the encoder and of the iterative decoder of RCDO codes is advantageous as compared to the implementation complexity of error correcting techniques that achieve similar error performances. This thesis has many objectives. First of all, this work presents a bridge between the family of LDPC block codes and the RCDO codes, indeed both families of codes are constructed from their parity-check matrix. From this fact, it becomes possible to identify an asymptotic threshold value that represents the limit above which the error performances of a family of RCDO codes can converge to zero. Moreover, we also present the complexity analysis associated to the encoding and to the decoding of RCDO codes. From this analysis, it becomes now possible to impose material criterions and to search for an ensemble of RCDO codes that meet all the material requirements and have the best theoretical threshold value. The question that motivates this thesis is the following. Is it possible to approach the theoretical Shannon limits associated to error correcting codes over binary symmetric memoryless channels using the doubly-orthogonal conditions imposed on convolutional codes? For this thesis, the symmetric channels are : the Binary Erasure Channel (BEC) and the Additive White Gaussian Noise (AWGN) channel.