Algorithme Reed Solomon

Fermé
cdbvs - 25 févr. 2012 à 20:37
 cdbvs - 19 mars 2012 à 19:27
Salut à tous et à toutes.



Ma question sera très simple. Seulement, la réponse que je demande est tellement simple que je ne sais pas si vous pourrez vraiment m'aider, vu la complexité de cette question =)


Je suis une brelle infâme en math et en programmation. Je suis même comme qui dirait plus nul que nul, à peine réalisé une broutille à 2 balles sous Basic Locomotive, c'est tout dire, hein ;)


Comme tous les ignards, je suis toujours béat d'admiration face à ce que je ne comprends pas et dont le fonctionnement me paraît magique. A cela près que ça a été conçu par l'esprit des être humains, surhumains, dotés de supers pouvoirs intellectuels et donc que ce n'est pas de la magie, mais bien une réalité.


J'utilisais QuickPar quand je surfais sur les services de news et puis j'ai arrêté les news groups et donc aussi l'utilisation de QuickPar. J'y reviens de temps à autre uniquement pour avoir des sécurités sur certains dossiers auxquels je tiens et que je souhaite le plus sauvegarder en créant des parts de réparations inclus avec le support.


Ma question est de comprendre le principe de fonctionnement de l'algorithme Reed Solomon, pas de la manière dont il est expliqué sur toutes les pages de Google, mais d'une manière imagé. J'ai souvent eu à me confronter à ce problème dans ma vie, de ne pas pouvoir comprendre un principe de fonctionnement si il ne m'est pas décrit par dessin, surtout pour les choses supères abstraites comme cet algorithme et les Corps de Galois qui servent à le mettre en application. J'ai bien survolé des pages sur internet, mais je suis toujours largué dès les premières lignes. Normal je dirais, mais c'est une situation frustrante, surtout sur internet.


Quand on regarde Wikipédia. Je sais, mais j'ai pas d'autre exemples assez simplifiés. Quand on regarde donc sur Wikipédia, on capte queue d'ale quand on est un blaireau. Et encore. Même si on est pas une merde dans tout. Je précise au cas ou =)


Ce que je ne comprends pas c'est qu'un fichier de X taille puisse être réparé n'importe ou dans sa structure avec un patch inférieur à lui. C'est mon esprit qui ne comprend pas, voyez. Comment il est possible de réparer une structure abimée à tel endroit avec un seul morceau qui sera compatible avec l'ensemble de la structure. Si j'ai un morceau de peau en trop de ma voute plantaire et qu'il vienne à me manquer un bout à la bits (je ne sais pas si on à le droit aux vulgarités), j'aurais un membre bien rude et qui sentira le pied à la fin :D Mdr.


Vous comprenez ou je veux en venir?
Que Wikipédia me fasse sa Description intuitive, qui n'est pas plus intuitive pour une personne qui n'y comprends rien qu'un cours simplifié des menaces du tabagisme pour les plants de Solanum lycopersicum pour ceux qui n'y comprennent rien, ne pourra donc pas leurs servir, même si on essaie d'expliquer simplement. Voyez?


Pour cette réponse, un fumeur doit se laver avant de toucher un plant de tomate, sinon le plant va crever d'une maladie biologique extrêmement violente et presque imparable.



Par contre me faire une description abstraite, en couleur =), en plus d'un seul bloc, sans expliquer le principe de fonctionnement, du moins, moi je vois queue d'ale, c'est tuant.


Comment la création d'une petite information provenant d'une longue suite de données peut réparer cette dernière à n'importe quel endroit de sa suite. Ou si dans la phrase:" Salut, comment ça vas", comment en récupérant 3 ou 4 lettres, il sera possible au logiciel de réparer les lettres manquantes?



Voilà, faite moi une formule imagée avec une phrase, ce sera plus simple pour moi de comprendre le principe.



Voilà.
Merci pour votre aide car là je me sent largué, mais largué, d'une force!!!
Comme si un joueur sous Pong se réveillait aujourd'hui avec les jeux de simulations actuel. Le mec nous retaperait un coma rien que pour le fun.
A voir également:

1 réponse

KX Messages postés 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 3 018
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...
1
Salut KX, c'est Cdbvs.


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 =)
0
KX Messages postés 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 3 018 > cdbvs
26 févr. 2012 à 21:07
Avant tout il faut bien comprendre que l'exemple que j'ai donné n'est pas l'algorithme de Reed-Salomon mais d'un autre plus simple (et dont le nom m'échappe), je vais continuer d'expliquer avec cet algorithme (parce que je ne crois pas que tu comprendrais mieux en parlant de Reed-Solomon ^^)

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.
0
Salut KX, c'est Cdbvs.


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? =)
0
Salut KX, c'est Cdbvs.


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
=)
0
KX Messages postés 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 3 018 > cdbvs
27 févr. 2012 à 20:54
"il suffira de piocher dans la boite pour remettre les Bits là ou ils manquent ?"
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"
0