Forum de mathématiques - Bibm@th.net

Scytale

Membre

Inscription : 30-12-2024

Messages : 9

Codage

Bonjour,

Je bloque sur une question d'un exercice concernant les codages linéaires.

L'énoncé me donne uniquement la liste de syndromes et les message correcteur :

Syndromes | Message correcteur :
00 | 0000
01 | 0001
10 | 0010
11 | 1000

On me demande de fournir la matrice de contrôle H correspondante.

Bien entendu, depuis la une matrice génératrice je sais parfaitement comment créer la matrice de contrôle H ainsi que sa transposée afin de pouvoir corriger des mots qui ne sont pas des mots-codes.

Au vu de cette liste de syndromes, je comprends que c'est un codage B² vers B⁴ et donc la matrice H sera une matrice de 2 lignes et 4 colonnes.

Au vu de la composition de la matrice H : Transposée de la matrice de parité juxtaposant une matrice identité, je peux déduire que les deux dernières colonnes seront :
\begin{bmatrix}
. & . & 1 & 0\\
. & . & 0 & 1
\end{bmatrix}

Mais je ne comprends pas comment je peux trouver la matrice de parité à partir de la liste des syndromes ...

Je vous remercie d'avance pour votre éclaircissement.

Scytale

Membre

Inscription : 30-12-2024

Messages : 9

Re : Codage

Bonjour,

Je me permets de revenir sur le sujet car après quelques recherches, apparement chaque colonne de la matrice de contrôle H représente un syndrome qui représente une correction au i-ème bit.

Donc selon moi la première colonne devrait être 11 et on aurait donc la matrice de controle suivante :

\begin{bmatrix}
1 & . & 1 & 0\\
1 & . & 0 & 1
\end{bmatrix}

Il me reste donc la deuxième colonne à trouver mais je n'ai aucune idée de la valeur de celle-ci car on ne peut pas mettre de vecteur nul dans la matrice de contrôle.. Des idées ?

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 425

Re : Codage

Bonjour,
Pourrais-tu donner l'énoncé complet ?
Un code binaire de longueur 4 et dimension 2 ne peut pas corriger une erreur.

Scytale

Membre

Inscription : 30-12-2024

Messages : 9

Re : Codage

Bonjour,

Tout d'abord, merci d'avoir pris le temps de me répondre.

Voici l'énoncé complet :

Soit la liste des syndromes suivante définie pour une fonction de codage linéaire systématique.

Syndrome  Message
00  0000
01  0001
10 0010
11 1000

1) Proposez une matrice de contrôle H qui pourrait mener à cette liste de syndromes. Expliquez votre démarche.
2) En fonction, donnez la matrice génératrice G et le tableau standard.
3) Combien d'erreurs peuvent être détectées certainement ? pourquoi ?

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 425

Re : Codage

Je trouve cet énoncé très bizarre. Mais bon, peut-être qu'il se justifie bien dans le contexte du cours.
La distance minimale d'un code satisfaisant aux conditions ne peut pas dépasser 2 (un code binaire de longueur 4 et dimension 2 ne peut pas corriger à coup sûr une erreur). On peut mettre n'importe quelle deuxième colonne non nulle dans la matrice de parité, la distance minimum sera alors 2. Le code pourra détecter une erreur sur un bit, mais pas toujours la corriger correctement.

Scytale

Membre

Inscription : 30-12-2024

Messages : 9

Re : Codage

Bonjour,

Merci pour votre retour et vos réponses, cela m'est d'une grande aide.

Si vous me le permettez j'ai deux dernières question sur votre réponse :

1) Lorsque vous me dites "n'importe quelle colonne non nulle", sommes-nous bien d'accord que dès lors je peux mettre soit le vecteur (1,1) ou (1,0) ou (0,1) ? Car ce sont les syndromes.

2) Sommes-nous d'accord que la raison pour laquelle nous ne pouvons pas mettre le vecteur (0,0) est que la condition nécessaire et suffisante, pour qu'un codage linéaire permette de corriger de façon certaine toutes les erreurs de poids 1, est que la transposée de la matrice H ait toutes ses lignes distinctes et non nulles ? Je veux être certain de bien comprendre et m'assurer qu'il n'y a pas une autre raison valable qui m'échapperait.

Merci pour votre aide sur le sujet.

Dernière modification par Scytale (01-01-2025 22:57:23)

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 425

Re : Codage

Si une colonne de la matrice de contrôle est nulle, alors la distance minimale du code est 1. Le code ne permet donc même pas de détecter une erreur de poids 1 à coup sûr. Si aucune colonne n'est nulle, la distance minimale est 2 et le code permet de détecter une erreur de poids 1 à coup sûr.
Je répète une nouvelle fois (puisqu'il semble que tu ne l'as pas bien compris) qu'un code binaire de longueur 4 et de dimension 2 ne permet JAMAIS de corriger à coup sûr une erreur de poids 1.  En effet, sa distance minimale ne peut pas être strictement plus grande que 2.