--- author: Quentin Bordignon, Lucas Dufour, Elisa Vignoud, Mathis Faucheux date: 18/12/2021 title: Rapport codage LDPC - Groupe 2 --- # CNA - Projet LDPC [Polycopié Chapitre 6](https://moodle.insa-lyon.fr/pluginfile.php/185264/mod_resource/content/9/CoursCNA2021-2022-chapter6.pdf) [Polycopié Chapitre 7](https://moodle.insa-lyon.fr/pluginfile.php/302719/mod_resource/content/9/CoursCNA2021-2022-chapter7.pdf) [Annexes](https://moodle.insa-lyon.fr/pluginfile.php/302720/mod_resource/content/9/CoursCNA2021-2022-annexes-part2.pdf) [LaTeX symbols](https://oeis.org/wiki/List_of_LaTeX_mathematical_symbols) [LaTex symbols 2](https://www.caam.rice.edu/~heinken/latex/symbols.pdf) [Projet](https://moodle.insa-lyon.fr/mod/folder/view.php?id=64114) ###### tags : `CNA` `TD` ## Rappels > a) Quel est le rôle du codage canal ? Le codage canal permet de rendre le code plus robuste aux modifications liées au canal (bruit, atténuation, etc...) *Exemple : code à répétition, code en bloc* > b) Comment se positionnent le codeur et le décodeur dans la chaîne de transmission par rapport à la modulation et la démodulation ? Le codeur se trouve avant la modulation et le décodeur après la démodulation. > c) Qu’est ce qu’un codage en bloc ? Le codage en blocs consiste à associer à un bloc de données $d$ de $k$ symboles issus de la source d’information un bloc $c$, appelé mot de code, de $n$ symboles avec $n ≥ k$. La différence $(n−k)$ représente la quantité de redondance introduite par le code. > d) Quel est le rôle de la matrice génératrice ? **Définition :** Soit $L$ un $[n,k]$. La matrice génératrice **$G$** est de dimension (k x n). Ses lignes forment une base de $L$. La notion de matrice génératrice possède à la fois un intérêt théorique dans le cadre de l'étude des codes correcteurs, par exemple pour définir la notion de code systématique, et un intérêt pratique pour une implémentation efficace. > e) Qu’est-ce que la distance de Hamming ? Elle permet de quantifier la différence entre deux séquences de symboles. *Exemple : $d_{Hamming}(0010110, 0001110) = 2$* car il ya deux bits de différence entre les deux séquences. > f) Quelle est la différence entre correction et détection d’erreur ? La detection d'erreur permet de déceler une erreur, la correction consiste à corriger l'erreur et à anticiper les erreurs à venir. ## Principes de Codage/Décodage Supposons que l’on ait implémenté un modulateur et un démodulateur à décisions dures (c’est à dire que chaque symbole est estimé indépendamment des autres). > a) Dans un tel récepteur, le démodulateur résoud pour chaque symbole un problème de détection optimal. Exprimez le problème de détection ainsi posé. Espace d'événement X discret et espace d'observation discret Y ainsi qu'une loi de probabilité connue : $f_{Y|X}(y|x)$ > b) Supposons qu’on ait une modulation de type QPSK. Donnez les régions de décisions associées à chaque symbole. Il y a 4 régions de décisions assoiciées à chaque couple de bit $\{00, 01, 10, 11\}$. ![](https://i.imgur.com/kDgvxcc.png) > c) Lorsqu’on associe un codage canal, cette approche n’est pas optimale. Pourquoi ? Démontrez-le sur un codage simple de type codage à répétition. Code à répétition : $00101101 \rightarrow 0000101011110101$ Estimer chaque symbole indépendamment va créer des zones d'incertitudes plutôt que de les estimer conjointement. Cela va augmenter les probabilités d'erreur. > d) En partant de l’expression du MAP pour un code donné, faites apparaître la vraisemblance et la probabilité a priori des séquences de codes. $\frac{f_{X|Y}(x_1|y)}{f_{X|Y}(x_0|y)} \lessgtr \frac{C_{fp} \cdot P_0}{C_{nd} \cdot P_1} \Leftrightarrow \frac{f_{Y|X}(y|x_0) \cdot f_y(y)}{f_{Y|X}(y|x_1) \cdot f_y(y)} \lessgtr \frac{C_{fp} \cdot P_0}{C_{nd} \cdot P_1}$ > e) Montrez alors pourquoi démoduler et décoder séparémment n’est pas optimal. ## Étude du LDPC **Low-density parity-check (LDPC)** **Code LDPC régulier :** - *if wc is constant for every column and wr = wc · (n/m) is also constant for every row* - *if same number of incoming edges for every v-node and also for all the c-nodes.* **Code LDPC irrégulier :** *If H is low density but the numbers of 1’s in each row or column aren’t constant the code is called a irregular LDPC code.* ### Préliminaires : Étude du document `ldpc.pdf` > a) À quelle famille de codes le LDPC appartient-il ? Le code LDPC appartient à la famille des codes linéaires (*class of linear block LDPC codes*) > b) À quoi fait référence le nom LDPC ? LDPC pour *Low-density parity-check*, rappelle la méthode de vérification utilisée ; ici le contrôle de **parité**. Le terme low-density indique que ce code associe peu de liens, le graph de relation n'est pas dense. > c) Pourquoi la représentation graphique est-elle importante pour comprendre le décodage ? Il existe deux manière de représenter le LDPC : - Par matrice : - Comme tous les codes linéaires : besoin d'une matrice très large ; pas logique pour du *low density* clamée par LDPC *(matrix should usually be very large, so the example matrix can’t be really called low-density.)* - Par représentation graphique : - Permet une représentation complète du code - Permet de mieux comprendre l'algorithme de décodage => On utilise alors un graph de Tanner Un graphique de **Tanner** est biparti (chaque arête possède une extremité dans chacun des deux espaces). Les deux types de noeuds de ce graph sont les **variable nodes** (v_nodes) et les **check nodes** (c_nodes). Voici ci dessous un exemple de graphique de Tanner associé à sa matrice de liens. ![Représentation matricielle et graphique](https://i.imgur.com/cPP0exv.png) ### Études des décodeurs > a) Quelle différence y a-t-il entre le décodeur hard et le décodeur soft ? Le décodeur HARD décode symbole par symbole sans prendre en compte le lien entre les symboles. Pour ce type de décodeur, on procède à un vote par majorité pour décider du résultat d'un bit (si deux nodes "pensent" 1 et une seule 0 alors le résultat retenu sera 1). Un décodeur SOFT décode globalement les symboles. Ce décodeur prends en compte dans ces décisions des probabilités, les choix sont plus nuancés, et on trouve des résultats plus fiables. >b) En déduire pourquoi un décodeur soft a plus de chance d’être performant qu’un décodeur hard. Un décodeur HARD est moins fiable, il n'est très pas robuste aux erreurs. Le décodeur SOFT est plus flexible. ### Implémentation des décodeurs Vous trouverez ci joint dans notre archive les fichiers MATLAB suivants : * HARD_DECODER_GROUPE2 * SOFT_DECODER_GROUPE2 Accompagnés des fichiers suivants : * LDPC_STUDENT_TEST_SCRIPT * student_dataset ### (Bonus) Évaluation des décodeurs Pour évaluer les performances des décodeurs, on pourrait mesurer les temps de décodage en fonction de la taille des mots codes. Il faudrait également prendre en compte le taux de réussite.