A voir également:
- Algorithme Reed Solomon
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
- Logiciel algorithme euromillion - Télécharger - Loisirs créatifs
- Code ascii algorithme - Guide
- Algorithme euromillion excel gratuit - Forum Algorithmes / Méthodes
- Algorithme qui calcule le carré d'un nombre - Forum Algorithmes / Méthodes
1 réponse
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 020
25 févr. 2012 à 22:18
25 févr. 2012 à 22:18
Ça fait beaucoup de mots pour pas dire grand chose au final... Je vais cependant essayer de répondre au mieux ;)
Une des bases de la détection d'erreur c'est le bit de parité.
Par exemple pour un caractère ASCII (le vrai, à 7 bits, pas l'ANSI), on rajoutait un 8è bit de contrôle qui valait 0 si la somme des bits était paire, ou 1 sinon.
Exemple : 0000000.0, 0000001.1, 0000010.1, etc...
Ici la détection d'erreur se base sur l'idée qu'on a jamais plus d'une erreur sur un octet.
Quand on envoi un octet on rajoute le bit de parité, et quand on le reçoit, on le vérifie.
Si il y a une erreur on le verra tout de suite car la somme sera fausse, dans ce cas l'un des 8 bits transmis a une mauvaise valeur (mais on ne sait pas laquelle).
Les codes détecteurs-correcteurs, reprennent cette idée, mais en plus sophistiqués.
En effet ils vont placer log2(n) bits de parité calculant différente valeurs des n bits du message, de sorte que si une erreur intervient on puisse identifier sa position.
La magie étant que si une erreur intervient elle sera détectée par un ou plusieurs bits de parité qui mis bout à bout vont donner la position erronée...
Exemple : avec 7 bits de donnée, et 3 bits de parité.
Le bit de parité k sera calculé avec tous les bits qui ont 1 sur leur bit de position k.
le bit 1 (001) sera utilisé pour le bit de contrôle 3
le bit 2 (010) sera utilisé pour le bit de contrôle 2
le bit 3 (011) sera utilisé pour les bits de contrôle 2 et 3
le bit 4 (100) sera utilisé pour le bit de contrôle 1
le bit 5 (101) sera utilisé pour les bits de contrôle 1 et 3
le bit 6 (110) sera utilisé pour les bits de contrôle 1 et 2
le bit 7 (111) sera utilisé pour les bits de contrôle 1, 2 et 3
Lorsque l'on compare les bits de contrôle que l'on a reçu avec le message, et celle que l'on calcule nous même sur le message (potentiellement endommagé), la différence nous indique exactement où est l'erreur (en supposant qu'il n'y en a qu'une). Ensuite comme un bit ne peut prendre que deux valeurs (0 ou 1) il suffit d'inverser le bit pour le corriger.
Exemple : j'ai reçu le code de contrôle 101, mais je calcule 011, ce qui signifie que l'erreur a entraîné une erreur à la fois sur le premier et le deuxième bit de parité, mais pas le troisième, c'est donc le bit 6 qui est erroné car c'est le seul qui est calculé par ces deux là et pas le troisième. Remarque : avec le ou exclusif on peut faire 101+011=110 ce qui ô magie nous donne 6 aussi !
Ça c'était un algo assez simple, mais qui n'autorise qu'une seule erreur dans le message. Et il y a des grosses pointures qui s'amusent avec d'autres méthodes comme dans l'algo de Reed-Solomon, pour pouvoir repérer et corriger plusieurs erreurs d'un coup. Mais le principe de base est le même : on rajoute des données au message, on l'envoie, on récupère le message, et on compare le contrôle reçu et le contrôle calculé sur les données reçues.
Remarque : il est en général intéressant d'envisager que l'erreur peut également venir des bits de contrôle et pas seulement du message...
Une des bases de la détection d'erreur c'est le bit de parité.
Par exemple pour un caractère ASCII (le vrai, à 7 bits, pas l'ANSI), on rajoutait un 8è bit de contrôle qui valait 0 si la somme des bits était paire, ou 1 sinon.
Exemple : 0000000.0, 0000001.1, 0000010.1, etc...
Ici la détection d'erreur se base sur l'idée qu'on a jamais plus d'une erreur sur un octet.
Quand on envoi un octet on rajoute le bit de parité, et quand on le reçoit, on le vérifie.
Si il y a une erreur on le verra tout de suite car la somme sera fausse, dans ce cas l'un des 8 bits transmis a une mauvaise valeur (mais on ne sait pas laquelle).
Les codes détecteurs-correcteurs, reprennent cette idée, mais en plus sophistiqués.
En effet ils vont placer log2(n) bits de parité calculant différente valeurs des n bits du message, de sorte que si une erreur intervient on puisse identifier sa position.
La magie étant que si une erreur intervient elle sera détectée par un ou plusieurs bits de parité qui mis bout à bout vont donner la position erronée...
Exemple : avec 7 bits de donnée, et 3 bits de parité.
Le bit de parité k sera calculé avec tous les bits qui ont 1 sur leur bit de position k.
le bit 1 (001) sera utilisé pour le bit de contrôle 3
le bit 2 (010) sera utilisé pour le bit de contrôle 2
le bit 3 (011) sera utilisé pour les bits de contrôle 2 et 3
le bit 4 (100) sera utilisé pour le bit de contrôle 1
le bit 5 (101) sera utilisé pour les bits de contrôle 1 et 3
le bit 6 (110) sera utilisé pour les bits de contrôle 1 et 2
le bit 7 (111) sera utilisé pour les bits de contrôle 1, 2 et 3
Lorsque l'on compare les bits de contrôle que l'on a reçu avec le message, et celle que l'on calcule nous même sur le message (potentiellement endommagé), la différence nous indique exactement où est l'erreur (en supposant qu'il n'y en a qu'une). Ensuite comme un bit ne peut prendre que deux valeurs (0 ou 1) il suffit d'inverser le bit pour le corriger.
Exemple : j'ai reçu le code de contrôle 101, mais je calcule 011, ce qui signifie que l'erreur a entraîné une erreur à la fois sur le premier et le deuxième bit de parité, mais pas le troisième, c'est donc le bit 6 qui est erroné car c'est le seul qui est calculé par ces deux là et pas le troisième. Remarque : avec le ou exclusif on peut faire 101+011=110 ce qui ô magie nous donne 6 aussi !
Ça c'était un algo assez simple, mais qui n'autorise qu'une seule erreur dans le message. Et il y a des grosses pointures qui s'amusent avec d'autres méthodes comme dans l'algo de Reed-Solomon, pour pouvoir repérer et corriger plusieurs erreurs d'un coup. Mais le principe de base est le même : on rajoute des données au message, on l'envoie, on récupère le message, et on compare le contrôle reçu et le contrôle calculé sur les données reçues.
Remarque : il est en général intéressant d'envisager que l'erreur peut également venir des bits de contrôle et pas seulement du message...
26 févr. 2012 à 20:11
Bon...
C'est bon j'ai compris.
J'ai relus 6 fois pour comprendre. Faut dire que je suis très terre à terre et donc je n'interprète pas automatiquement les notions 0+1=1; 1+1=0 ou 0+0=0. Surtout quand il faut jouer avec chaque Bits pour retrouver la séquence manquante. Ca me rappel les allèles dans la biologie. Je déteste la biologie!
C'est comme si l'exemple que tu me donne était un paquet et qu'il y en avait des millions de collés les uns aux autres. Et que l'ensemble formait, en très simplifié, l'algorithme Reed Solomon?
Par contre ce que je ne saisis pas c'est: Un paquet peut réparer sa donnée, mais comment ce même paquet peut réparer une autre donnée?
Avec Quickpar, si j'envoie une donnée, par exemple une photo. Je ne sais pas ce que donne une photo binarisée, je suppose qu'il y à la taille et par la suite les séries de code binarisés qui donne la couleur du pixel suivit du fait de continuer la ligne ou d'effectuer un retour. Ca c'est ce que j'imagine, mais j'en sais rien en fait.
Si je continue dans ma logique, en suivant ton exemple, il sera possible de dire si la photo fait X taille, qu'il y a le même nombre de paquets qui peuvent à la fin réparer la photo si il manque une information de ci, de là.
Par contre ce que je n'arrive pas à comprendre, c'est qu'à ce moment là, il faudrait avoir autant de paquets que de bits qui font la totalité de la photo?
Il faut un exemple:" a ". Pour réparer " a ", j'ai besoin du paquet de 7 bits de donnée, et 3 bits de parité. C'est rien qu'un exemple. Je peux donc réparer " a ". Pour cela mon paquet pèse le poids de " a " en réel ou est ce que le paquet pèse le poids de 7 Bits de données?
Si l'algorithme crée un paquet pour " a " du mot " mais ", comment arrivera t-il à retrouver les autres lettres du mot?
Avec une photo, si je réalise un part sous Quickpar de 100ko alors que la photo fait 2000ko, il sera possible de réparer n'importe quel endroit de cette photo.
Comprends tu ce que je trouve totalement incompréhensible?
Merci =)
26 févr. 2012 à 21:07
On fait l'hypothèse que sur un bloc de n bits, on ne peut pas avoir plus d'une erreur, en effet le taux d'erreur est souvent assez faible, et avoir deux erreurs est peu probable si on choisit bien la valeur de n. En fait une fois cette taille n déterminé on va découper le message (même très grand) en petits blocs de taille n, et pour chacun, ajouter log2(n) bits de parité. Comme ça chaque bloc va pouvoir se corriger soi même, en supposant donc que s'il y a deux erreurs, elles seront sur deux blocs différents.
Ce qui se passe c'est donc que l'on rajoute des données, ici pour des données de taille M=k.n, on aura k blocs de tailles n, avec chacun log2(n) bits de parité supplémentaire, et donc le message que l'on transmettra sera non plus M, mais M+k.log2(n), qui est donc plus grand.
Si je reprends tes chiffres : 100ko de contrôle pour 2000ko, en imaginant (ce qui n'est pas le cas), que l'on ai ces valeurs sur l'algo précédent, ça veut dire que k.n=2000 ko, et k.log2(n)=100ko, ce qui nous donne k=182000 et n=90.
La photo, sera donc découpés en 182 000 blocs de 90 bits, et en supposant qu'il n'y aura jamais plus d'une erreur sur le même bloc on pourra donc corriger jusqu'à 182 000 erreurs de transmission sur cette image. Mais honnêtement, si tu as 182 000 erreurs sur une image de 2Mo c'est que tu as de gros problème sur le réseau !!
Mais comme je l'ai dit et je le répète, c'est algorithme est très simple, et Reed-Solomon, permet de faire encore mieux puisqu'il permet de détecter et corriger plusieurs erreurs sur le même bloc, donc la correction se fera encore mieux.
Remarque : tu parles du format d'images, en effet, une image a généralement des informations sur son format, sa taille, puis une série d'octets pour les composantes Rouge, Vert, Bleu, de chaque pixel, c'est le cas du format BMP, d'autres formats comme PNG, préfèrent déclarer au départ une palette de couleurs, puis ne faire que des références à cette palette. D'autres encore font tout autrement, comme par exemple le format JPG. Mais en fait on s'en moque. Nous on va faire abstraction de ce format d'image. Que tu envoies, un email, une image, un programme etc... tout est composé d'octets, et on fait du traitement directement sur les bits, sans savoir ce qu'ils représentent.
Modifié par krazykat le 28/02/2012 à 00:24
182000 erreurs xDDD Mrd.
Je suis perplexe. Je crois comprendre ce que tu me dit, mais finalement je reste bloqué sur plusieurs choses:
- Avant de passer pour un gars qui n'écoute pas, tu peux me rappeler ce qu'est log2(n). Me donne pas une définition mais plutôt à quoi ça correspondrait dans une formule. Merci =)
- Comment tu trouves 182000 et 90?
- J'ai compris la simplicité de cet algorithme, mais je ne saisi toujours pas comment il est possible de réparer 1 erreur à n'importe quel endroit de la séquence avec un pansement créé pas forcément avec le morceau manquant?...
Attends... Le Bit ne sais pas ce que représente la donnée finale sur la séquence à réparer?
Ca voudrait alors dire que si QuickPar donne X Bits 1 et 0 à Monsieur Pansements, il n'aurait qu'à donner les Bits 1 et 0 que demanderait Monsieur Erreur pour réparer les séquences manquantes. Et en fait il y aurait un programme qui gèrerait le tout en disant ou est l'erreur et ce dont elle à besoin pour être réparée ou comment passer de 0 à 1 ou de 1 à 0 pour que la séquence d'origine soit la même que celle du départ:
Séquence: Vérificateur de la séquence grâce à un discriminateur: On crée des Bits 0 et 1 que l'on place dans une boite: Transfert de la séquence et du discriminateur: Monsieur Erreur vérifie si la séquence est identique à celle du départ grâce au discriminateur: Si il y a des erreurs, Monsieur Pansement pioche dans la boite de Bits 0 et 1 pour les placer là ou il faut pour remettre les séquences en place comme tu me l'a montré dans l'exemple (Exemple : avec 7 bits de donnée, et 3 bits de parité).
Je suis dans le vrais, ou j'ai rien compris !?
Si c'est ça, je me demande pourquoi les programmeurs ne créeraient pas un programme qui génèrerait automatiquement des Bits 0 et 1, ce qui éviterait de perdre du temps à la création de ces Bits. Mais je dois être dans le faut là je pense! En fait je sais pas...
Faut être patient, je ne suis pas vieux, j'ai 36 ans. Mais tu sais ce qu'on dit. Plus on vieillis et plus le cerveau est réfractaire à l'apprentissage des langues et donc les formules matheuses et binaires, c'est un peu pareil :°)
J'ai un ami programmeur. Quand je discute avec lui, je sens souvent qu'il se force à faire simple et que ça le gène car il n'est pas habitué, alors que moi je fume du ciboulot. Ca ne m'empêche pas que l'on s'entende très bien, mais c'est pour dire que je ne (grossièreté supprimée par la modération) Je cherche vraiment à comprendre et je réfléchis à toutes les phrases que tu me marque. Ok? =)
27 févr. 2012 à 20:10
C'est étrange ça, j'ai écris une réponse hier soir à la suite du message, elle a été enregistrée et je regarde ce soir et il n'y a plus ma réponse !?
???
Bon.
Je vais donc la réécrire, mais pas de la même façon alors car je ne me souviens plus de ce que je t'ai écris hier.
182000 erreurs sur 2 mo c'est sure qu'il y a surement un problème :D
Au risque de passer pour un gars qui n'écoute pas, tu peux me dire ce que représente log2(n). Pas avec une définition, mais dans un calcule?
Comment obtiens tu 182000 et 90?
***
Je crois avoir compris, mais il vas falloir que tu me dise si c'est bon ou pas:
Si on traite les Bits sans savoir ce qu'ils représentent, ça veux dire que si l'on possède une boite de Bits 1 et 0, il suffira de piocher dans la boite pour remettre les Bits là ou ils manquent?
Une séquence: Segmentation de la séquence: Un logiciel discriminatoire qui indique le nombre de bits par morceaux de séquence: Un logiciel qui crée des Bits 1 et 0 et qui les placent dans une boite: La séquence, la référence de discrimination et la boite de Bits sont envoyés: Un logiciel vérifie que les morceaux segmentés de la séquence soient identique à la référence de discrimination: Un logiciel pioche dans la boite de Bits 0 et 1 pour les remettre en place dans les segmentations comme tu me l'a fais voir avec l'exemple "Exemple : avec 7 bits de donnée, et 3 bits de parité": Les segments sont recollés ensembles pour avoir la séquence originale.
C'est à peut près ça ou pas?
***
Je vais sauvegarder cette réponse au cas ou elle soit encore effacée demain.
Merci
=)
27 févr. 2012 à 20:54
Je crois qu'on ne s'est pas compris sur ce qu'était une erreur, je n'en ai pas parlé mais c'est vrai que ce n'est pas forcément évident, en fait une erreur c'est "juste" un 0 qui est transformé en 1 (ou l'inverse), il n'y a jamais de trous dans le message.
Le principe, la "séquence", doit être décomposé en deux :
* L'émetteur possède le message, il calcule la somme de contrôle, et envoie le message et le contrôle (englobé dans le message, ou séparé, selon la méthode)
* Le récepteur reçoit un message (avec éventuellement des bits erronés), et la somme de contrôle calculée par l'émetteur. Il calcule lui même la somme de contrôle du message reçu, et en la comparant avec la somme de contrôle reçu, le récepteur peut déterminer s'il y a erreur et les corriger (au moins en théorie ^^).
Exemple : j'envoie les lettres 'K' et 'X', en ASCII sur 7 bits, c'est à dire en binaire : 1001011 et 1011000 ce qui me donne les bits de contrôles 000, et 110.
Donc l'émetteur va envoyer 10010111011000 et le contrôle 000110.
Imaginons que le récepteur recoive 10110111011001 (c'est à dire avec deux erreurs, mais le récepteur ne le sait pas encore). En calculant les bits de contrôle sur le message recu, il obtient : 101111. En faisant la différence par rapport au contrôle reçu il obtient 101 et 001, il sait donc que le 5è bit du premier bloc est faux ainsi que le 1er du deuxième bloc. Il corrige donc le message tout seul, et me redonne mon message : "KX"