Codes correcteurs d'erreurs

Jona · May 2009

Bonjour, je suis en train de faire un exercice, mais je ne dispose pas de la correction ... Il n'est pas bien compliqué, néanmoins je débute dans l'étude des codes correcteurs, et j'aimerais être sûr de mes réponses :

On note $(0,1,2)$ les éléments de $\mathbb{F}_3$. Soit $C$ le code linéaire sur le corps $\mathbb{F}_3$, de matrice génératrice $$G=\begin{pmatrix} 1 & 0 & 2 & 2 \\ 0 & 1 & 1 & 2 \end{pmatrix}$$
1) Donner la longueur, la dimension, et le nombre de mots de $C$.
Ma réponse : on a respectivement : Longueur$=4$, Dimension$=2$, Nombre de mots$=3^2=9$.

2) Encoder le message $m=(2,1)$.
Ma réponse : $(2120)$

Voilà ce que j'ai fait pour l'instant, après il y a d'autre questions, mais je ne les ai pas encore traitées.

Merci d'avance pour votre correction, c'est le cas de le dire ...

Le barbu rasé · May 2009

Pour moi, c'est tout bon.

Ton code est systématique (c'est à qire qu'on se contente de rajouter des "trits" (je ne sais pas dire bit en base 3) de contrôle à la fin du message originel) ce qui sera certainement une bonne affaire pour les questions suivantes.

Jona · May 2009

Oui en effet, j'avais remarqué après avoir posté que mon code était systématique !

Je dois maintenant trouver une matrice $H$ de contrôle. Néanmoins, à part avoir compris que la matrice de contrôle aura $(n-k)$ lignes et $n$ colonnes, je n'ai pas bien compris comment on peut la déterminer ?? Pourrais-tu m'expliquer ? (éventuellement sur un autre exemple pour que je puisse essayer de faire le mien tout seul ensuite.)

Merci.

Le barbu rasé · May 2009

C'est justement pour ça que c'est une super bonne affaire !

On est d'accord pour dire qu'une matrice de contrôle $H$ est de rang 2 et telle que $G\times H=(0)$ ?

Parce que là, c'est cool, $G=(I_2 ~~ G')$.

Du coup, je te propose de chercher $H$ sous la forme $\left ( \begin{array}{c} H' \\ I_2\end{array} \right )$. Tu ne devrais pas avoir trop de mal à trouver un bon $H'$ (normalement, ce truc est le premier qu'on voit quand on étudie les codes systématiques).

Le barbu rasé · May 2009

Ah, j'ai mis des $I_2$ mais par rapport à tes notations $k$ et $n$, on a bien sûr $k=2$ et $n=4$.

Si tu définis la matrice de contrôle comme ayant $n-k$ lignes et $n$ colonnes, la matrice de contrôle est bien sûr ${}^tH$ et non $H$.

Evidemment, la technique évoquée marche sans problème pour $k$ et $n$ quelconques.

Jona · May 2009

Le barbu rasé a écrit:

On est d'accord pour dire qu'une matrice de contrôle $ H$ est de rang 2 et telle que $ G\times H=(0)$ ?

Euh... Je viens de découvrir ça ! Tu veux dire que $G\times H=$ la matrice nulle ?

Le barbu rasé · May 2009

Ne renversons pas les rôles. C'est à toi d'avoir une définition sous la main. Si tu n'en as pas, tu n'as pas d'autre choix que de m'acheter la mienne. Mais alors c'est grave.

Normalement, vu que tu es en train de faire un exercice sur les matrices de contrôle, tu dois avoir vu une définition (le fait que tu indiques un nombre de lignes et de colonnes pour H va dans ce sens). Je reformule donc mon "on est d'accord pour..." de la façon suivante : "quelle est ta définition d'une matrice de contrôle" ?

Le barbu rasé · May 2009

Je découvre que l'article de wikipedia sur le sujet n'est pas mal, même en français...

Jona · May 2009

Bon je retire ce que j'ai dit... Encore une fois j'avais mal lu mon cours...

Mon cours a écrit:

$$H^{\;t}G=0$$

Donc je ne devrais pas avoir trop de problème à trouver cette matrice de contrôle finalement, je la cherche rapidement, et je la poste.

Le barbu rasé · May 2009

Oui attention quand même : les vecteurs (lignes ou colonnes, suivant comment tu définis $H$ ou ${}^tH$, dans ton cas c'est les vecteurs lignes) doivent former une base de l'orthogonal de $C$. D'où ma remarque sur le rang : Il ne suffit pas d'avoir $H^{\;t}G=0$, ce serait trop facile, on prendrait $H=(0)$ :P

Jona · May 2009

Bon je viens de comprendre pourquoi on doit se réjouir d'avoir ici un code systématique

Alors je trouve : $$H=\begin{pmatrix} 1 & 2 & 1 & 0 \\ 1 & 1 & 0 & 1 \end{pmatrix}$$

Jona · May 2009

J'aimerais en déduire si le mot $(2202)$ est un mot de $C$ ... Mais je ne vois pas comment faire ... Peut-être encore une fois, ai-je mal lu mon cours...?

egoroff · May 2009

Salut,

Sans être un gros pro, il me semble que les mots de $C$ sont exactements les éléments de l'image de $G$ non ? Et on a choisi $H$ pour que l'imge de $G$ soit exactement le noyau de $H^t$...

Jona · May 2009

Salut, mais comment trouver le noyau de la transposée de H ?

remarque · May 2009

La méthode de Gauss me semble très bien pour ça...

Jona · May 2009

Comment tu fais ? (Je suis désolé, je vais peut-être reconnaitre la méthode, mais le nom ne me dit rien...)

nicolas.patrois · May 2009

Ben, le pivot de Gauss ?

Jona · May 2009

Tu veux dire que de ça :
$\displaystyle H=\begin{pmatrix}1 & 2 & 1 & 0 \\ 1 & 1 & 0 & 1 \end{pmatrix}$

J'obtiens ça :
$\displaystyle H=\begin{pmatrix}1 & 2 & 1 & 0 \\ 0 & 2 & 2 & 1 \end{pmatrix}$

Et ensuite ? (Désolé, je suis pas très bon en algèbre linéaire...)

Le barbu rasé · May 2009

Calmons-nous. Pas de Gauss ici.

Les lignes de G (puisque tu écris G en ligne) forment une base de C. Pour déterminer si un mot est dans C, on peut faire toutes les combinaisons linéaires possibles des lignes de G et regarder si notre mot est dedans. Ça va être assez long, et vite impraticable lorsque k ou même n grandit.

Donc on fait autrement : on cherche une matrice magique $H$ telle que $x \in C \Leftrightarrow H\times{}^tx = 0$. Une telle matrice est appelée matrice de contrôle du code, et il est bien clair qu'on l'obtient en écrivant en ligne une base du noyau de $G$.

Donc, ça y est. Notre calcul de noyau, il est fait, il s'est d'ailleurs fait tout seul par magie car le code était systématique. Vade retro, Gauss.

Tu veux savoir si $(2202)$ est un mot du code ? Très bien, calcule $H\times \left ( \begin{array}{c}2\\2\\0\\2 \end{array} \right )$. Ça donnera zéro si et seulement si $(2202)$ est combinaison linéaire des lignes de $G$, c'est à dire si $(2202)$ est un mot du code.

Ça va aller ?

Jona · May 2009

Merci beaucoup pour cette explication ! Je comprends maintenant comment procéder.

Ici en l'occurrence, (2202) est bien un mot de $C$. (Puisqu'on trouve $(00)$ en faisant $H\times ^t (2202)$)

Je me demande maintenant, comment faire pour trouver la distance minimum de $C$. J'ai regardé dans mon cours, mais je n'ai pas clairement compris la méthode... Et dans mes exos corrigés, ils donnent directement la réponse sans afficher le cheminement ce qui n'est pas très aidant... :S

Merci d'avance.

Le barbu rasé · May 2009

Jona a écrit:

Ici en l'occurrence, (2202) est bien un mot de $ C$.

Oui. Pourquoi était-ce en fait évident ?

Jona a écrit:

Je me demande maintenant, comment faire pour trouver la distance minimum de $ C$. J'ai regardé dans mon cours, mais je n'ai pas clairement compris la méthode...

M'enfin ! C'est quoi ce cours ??? Tu es sûr d'avoir bien regardé ??

La distance minimale, c'est (théorème) le nombre minimal de colonnes de $H$ linéairement dépendantes (donc :
- si $H$ a une colonne nulle, c'est 1
- sinon, et si $H$ a deux colonnes proportionnelles, c'est 2
- sinon,et si une colonne de $H$ est combinaison linéaire de 2 autres, c'est 3
- etc).

(Question subsidiaire : démontrer le théorème.)

NB : Il y a de bons cours en ligne sur les codes correcterus (et la page de wikipedia est très bien aussi).

Jona · May 2009

Le barbu rasé a écrit:

Oui. Pourquoi était-ce en fait évident ?

Je ne sais pas ... Son poids vaut 0 ...?

Sinon pour la distance minimal, ici c'est clairement pas 1 ni 2... Mais ensuite aucune colone n'est combinaison linéaire d'une autre... Que dois-je en déduire ?

Oops, pardon, oui en effet $C_2=C_1+C_3$ Donc la distance minimale est 3.

Jona · May 2009

On en déduit que $C$ est MDS, puisque $3=4-2+1$.

J'ai une dernière question, si j'ai un mot $y_1=(2020)$, comment puis-je le décoder ? (Afin d'obtenir le mot émis)

Massena Power · May 2009

Oui bon, en fait tu veux un cours sur les codes correcteurs d'erreur quoi.

NB : Si tu travailles déjà à partir d'un cours à disposition de tous (poly qu'on peut trouver sur internet ou livre qu'on peut trouver en BU), donne-nous les références afin qu'on puisse te répondre plus efficacement.

Pour décoder un mot $x$, tu calcules le syndrôme $S = H \times {}^tx$.
Et tu regardes :
- Si $S=0$, tu ne détectes pas d'erreur. Le décodage consiste juste à tronquer.
- Si $S$ est la $i^e$ colonne de $H$ multipliée par $k(=1~ou~2)$, tu considères que l'erreur a eu lieu en position $i$, que la $i^e$ lettre $l$ du message codé a été changée en $l+k$. Donc tu retranches $k$ à la $i^e$ lettre de $x$, puis tu tronques.
- Si $S$ n'est pas multiple d'une colonne de $H$, tu es au delà de la capacité de correction, (qui ici vaut 1=E((3-1)/2)). Mais tu peux essayer de décoder quand même : tu essaies d'écrire $S$ comme une combinaison linéaire de $2$ colonnes de $H$. S'il y a une unique façon de le faire, ou s'il y a une façon de le faire qui te paraît plus raisonable que les autres : $S=k_iC_i+k_jC_j$, tu retranches $k_i$ à la $i^e$ lettre du message codé et $k_j$ à la $j^e$ lettre du message codé, puis tu tronques. Cela dit, ici, ça n'est pas vraiment intéressant d'essayer de corriger au delà de la capacité de correction : pourquoi ?

Jona · May 2009

Massena Power a écrit:

Cela dit, ici, ça n'est pas vraiment intéressant d'essayer de corriger au delà de la capacité de correction : pourquoi ?

Parce que le code est MDS ?

Pour mon message, (2020), j'ai appliqué ce que tu as dit. Je trouve comme syndrome : $\begin{pmatrix}2\\ 2\end{pmatrix}$

Ceci n'est pas S=0, donc le message comporte une erreur. On remarque qu'il s'agit de la 1ère colonne de $H$, multiplié par $k=2$. Donc l'erreur se trouve en position 1 dans le message. La première lettre n'est pas "2", mais : 2-2=0.

Notre message est donc, une fois décodé : $(00)$ ? (Tu as dit tronqué, mais dans quel sens ? A droite ou à gauche ? J'ai tronqué à droite ici ...)

Jona · May 2009

Bon je pense avoir bien compris pourquoi on tronque à droite, c'est parce que la matrice G est systématique. J'ai essayé de même de décoder (0201) et (1221), je trouve respectivement (02) et (11). En fait je me posais une question, est-ce que lorsqu'une erreur n'affecte pas les deux première lettres du message codé, cela ne change pas le message ? (exemple avec (0201)) Et si oui, pourquoi ?

Le barbu rasé · May 2009

Ton calcul de syndrôme pour (2020) est faux. Refais-le.

Jona a écrit:

lorsqu'une erreur n'affecte pas les deux première lettres du message codé, cela ne change pas le message ? (exemple avec (0201)) Et si oui, pourquoi ?

Dans le cas d'un code systématique, si toutes les erreurs ont lieu sur les "trits" de contrôle, et qu'on décode sans essayer de corriger le message reçu, on tombe quand même sur le message initial, si c'est ce que tu veux dire.

D'ailleurs, si par exemple on code le mot 00 qui devient 0000, que 2 erreurs se produisent et donnent 0022 et qu'on essaie de corriger, le syndrôme est 2*la premiere colonne de H, donc on va décoder en remplacant la première lettre 0 par 0-2=1, puis tronquer, ce qui va donner 10. Bref, la correction va échouer, ce qui n'est pas surprenant puisque ce nombre de 2 erreurs dépasse la capacité de correction 1 du code. Mais il est raisonnable d'échouer dans ce genre de cas car il est bien plus probable qu'une seule erreur se soit produite plutôt que 2.

Jona · May 2009

Syndrome recalculé : $(12)$

Et donc le message corrigé émis est : $(2020)-(0200)=(2120)$

Donc le mot décodé est : $(21)$

Codes correcteurs d'erreurs

Réponses

Bonjour!

Catégories

In this Discussion