Στα πλαίσια αυτής της διπλωματικής εργασίας μελετήσαμε μεθόδους κωδικοποίησης με χρήση πινάκων ισοτιμίας μεγάλων διαστάσεων που έχουν χρησιμοποιηθεί και εφαρμοσθεί μέχρι τώρα σε προηγούμενες μελέτες. Επιλέξαμε τη σχεδίαση ενός αποκωδικοποιητή, που στηρίζεται στο WiMAX – 802.16e ΙΕΕΕ πρότυπο μετάδοσης και συγκεκριμένα με χρήση πομπού και δέκτη με περισσότερες από μία κεραίες. Παρουσιάζουμε, λοιπόν τη θεωρία που συσχετίζεται με το θέμα αυτό τόσο από την πλευρά της κωδικοποίησης όσο κι από την πλευρά της ασύρματης ΜΙΜΟ μετάδοσης και το πρότυπο WiMAX. Αναλύουμε κάθε τμήμα του συστήματός που προσομοιώνουμε και παραθέτουμε τα αποτελέσματα της προσομοίωσης. / -

L'objet de cette thèse est l'étude des codes LDPC quantiques. Dans un premier temps, nous travaillons sur des constructions topologiques de codes LDPC quantiques. Nous proposons de construire une famille de codes couleur basée sur des pavages hyperboliques. Nous étudions ensuite les paramètres d'une famille de codes basée sur des graphes de Cayley.Dans une seconde partie, nous examinons les performances de ces codes. Nous obtenons une borne supérieure sur les performances des codes LDPC quantiques réguliers sur le canal à effacement quantique. Ceci prouve que ces codes n'atteignent pas la capacité du canal à effacement quantique. Dans le cas du canal de dépolarisation, nous proposons un nouvel algorithme de décodage des codes couleur basé sur trois décodages de codes de surface. Nos simulations numériques montrent de bonnes performances dans le cas des codes couleur toriques.Pour finir, nous nous intéressons au phénomène de percolation. La question centrale de la théorie de la percolation est la détermination du seuil critique. Le calcul exacte de ce seuil est généralement difficile. Nous relions la probabilité de percolation dans certains pavages réguliers du plan hyperbolique à la probabilité d'erreur de décodage pour une famille de codes hyperboliques. Nous en déduisons une borne sur le seuil critique de ces pavages hyperboliques basée sur des résultats de théorie de l'information quantique. Il s'agit d'une application de la théorie de l'information quantique à un problème purement combinatoire. / This thesis is devoted to the study of quantum LDPC codes. The first part presents some topological constructions of quantum LDPC codes. We introduce a family of color codes based on tilings of the hyperbolic plane. We study the parameters of a family of codes based on Cayley graphs.In a second part, we analyze the performance of these codes. We obtain an upper bound on the performance of regular quantum LDPC codes over the quantum erasure channel. This implies that these codes don't achieve the capacity of the quantum erasure channel. In the case of the depolarizing channel, we propose a new decoding algorithm of color codes based on three surface codes decoding. Our numerical results show good performance for toric color codes.Finally, we focus on percolation theory. The central question in percolation theory is the determination of the critical probability. Computing the critical probability exactly is usually quite difficult. We relate the probability of percolation in some regular tilings of the hyperbolic plane to the probability of a decoding error for hyperbolic codes on the quantum erasure channel. This leads to an upper bound on the critical probability of these hyperbolic tilings based on quantum information. It is an application of quantum information to a purely combinatorial problem.

Dans cette thèse, nous nous intéressons au problème de la reconnaissance de code. Ce problème se produit principalement lorsqu'une communication est observée dans un milieu non-coopératif. Une liste de mots bruités issus d'un code inconnu est obtenue, l'objectif est alors de retrouver l'information contenue dans ces mots bruités. Pour cela, le code utilisé est reconstruit afin de décoder les mots observés. Nous considérons ici trois instances de ce problème et proposons pour chacune d'elle une nouvelle méthode. Dans la première, nous supposons que le code utilisé est un turbo-code et nous proposons une méthode pour reconstruire la permutation interne (les autres éléments du turbo-codeur pouvant être facilement reconstruits grâce aux méthodes existantes). Cette permutation est reconstruite pas à pas en recherchant l'indice le plus probable à chaque instant. Plus précisément, la probabilité de chaque indice est déterminée avec l'aide de l'algorithme de décodage BCJR. Dans la seconde, nous traitons le problème de la reconnaissance des codes LDPC en suggérant une nouvelle méthode pour retrouver une liste d'équations de parité de petits poids. Celle-ci généralise et améliore les méthodes existantes. Finalement, avec la dernière méthode, nous reconstruisons un code convolutif entrelacé. Cette méthode fait appel à la précédente pour retrouver une liste d'équations de parité satisfaites par le code entrelacé. Puis, en introduisant une représentation sous forme de graphe de l'intersection de ces équations de parité, nous retrouvons simultanément l'entrelaceur et le code convolutif. / In this PhD, we focus on the code reconstruction problem. This problem mainly arises in a non-cooperative context when a communication consisting of noisy codewords stemming from an unknown code is observed and its content has to be retrieved by recovering the code that is used for communicating and decoding with it the noisy codewords. We consider here three possible scenarios and suggest an original method for each case. In the first one, we assume that the code that is used is a turbo-code and we propose a method for reconstructing the associated interleaver (the other components of the turbo-code can be easily recovered by the existing methods). The interleaver is reconstructed step by step by searching for the most probable index at each time and by computing the relevant probabilities with the help of the BCJR decoding algorithm. In the second one, we tackle the problem of reconstructing LDPC codes by suggesting a new method for finding a list of parity-check equations of small weight that generalizes and improves upon all existing methods. Finally, in the last scenario we reconstruct an unknown interleaved convolutional code. In this method we used the previous one to find a list of parity-check equations for this code. Then, by introducing a graph representing how these parity-check equations intersect we recover at the same time the interleaver and the convolutional code.

The main subject of this thesis is creating a programme, used for channel coding demonstration. This programme will be used for teaching purposes. The programme contains various codes from simple ones, to those which almost reach Shanon’s channel capacity theorem. Specifically these are the Hamming code, cyclic code, convolutional code and LDPC code. These functions are based on theoretical background described in this thesis and have been programed in Matlab. Practical output of this thesis is user interface, where the user is able to input information word, simulate transmission through the transmission channel and observe coding and decoding for each code. This thesis also contains a comparison between individual codes, concerning bit-error rate depending on SNR and various parameters. There is a computer lab with theoretical background, assignment and sheets for convenient accomplishment of each task.