[distance minimum de Cn]

par **charlix** » 07 Déc 2006, 17:44

bonjour,

je suis en train de réaliser un probleme sur la distance de hamming en informatique, et les mathématiques me sont obligatoire.

Je vous explique mon probleme, en considerant un alphabet A de cardinal a N*-{1} et un code n_aire : Cn, je dois demontrer qu'il existe un entier naturel dm = min (d[(x,y)]) avec x different de y .
d[(x,y)] est la distance de hamming et est égale à la somme des ei avec i [1,n] et biensur ei est égale a 0 si x=y sinon 1. donc dans le cadre de ma question c'est égal à 1 car x different de y.

Mais le probleme est que je ne sais pas du tout comment le demontrer alors que c'est logique.

merci d'avance

par **tize** » 07 Déc 2006, 21:47

Bonsoir,
pourrais tu, étant donné que je ne connais pas grand chose aux alphabets, donner un peu plus d'explication (ei ?, n-aire...). Peut être on pourra t'aider...

par **charlix** » 08 Déc 2006, 01:06

En faite l'alphabet A est juste un mot de bit composer de 0 et de 1.
Et le code n-aire Cn sur A siginfie que A est inclu dans A puissance n et cet alphabet A est de cardianl fini a.

Et ce que j'ai voulu dire pour ei (probleme de correspondance clavier maths) e indice i.

Apres je ne c pas si vous comprenez mon soucis.

par **fred** » 08 Déc 2006, 09:48

charlix a écrit:bonjour,

je suis en train de réaliser un probleme sur la distance de hamming en informatique, et les mathématiques me sont obligatoire.

Je vous explique mon probleme, en considerant un alphabet A de cardinal a N*-{1} et un code n_aire : Cn, je dois demontrer qu'il existe un entier naturel dm = min (d[(x,y)]) avec x different de y .
d[(x,y)] est la distance de hamming et est égale à la somme des ei avec i [1,n] et biensur ei est égale a 0 si x=y sinon 1. donc dans le cadre de ma question c'est égal à 1 car x different de y.

Mais le probleme est que je ne sais pas du tout comment le demontrer alors que c'est logique.

merci d'avance

La distance de Hamming est une distance au sens mathématique du terme :

elle est symétrique, d(a,b) = d(b,a);
elle sépare les éléments, ;
elle vérifie l'inégalité triangulaire, .

par **charlix** » 08 Déc 2006, 13:10

Ouai tu as tout a fait raison Fred, mais cela je le savais deja et ça ne me fait pas avancer pour ce qui ai de la distance minimum car c'est ça mon probleme.

par **tize** » 08 Déc 2006, 13:18

Salut Charlix

j'avais bien compris que ei était

mais ce que je ne comprends pas, c'est ce que cela représente (par rapport à x et y ?)

par **charlix** » 08 Déc 2006, 14:00

Salut Tize,

en faite ei c'est juste égale à 0 ou 1. Ca importe peu ,c'etait pour expliquer la distance sous forme d'une somme des ei de 1 à n. Pour tout (x,y) (A puissance n)² d[(x,y)]=somme des ei pour i[1,n] mais dans mon cas x different y donc ei=1.

par **tize** » 08 Déc 2006, 14:22

Bon, j'ai toujours pas compris ces histoires de ei et leur lien avec x et y mais de toute façon tu veux montrer qu'il existe un entier naturel dm = min (d[(x,y)]) avec x different de y et d[(x,y)] est une somme fini de 0 et de 1, donc d[(x,y)] appartient toujours aux entiers naturel :

! Toutes les valeurs prisent par d[(x,y)] : {d[(x,y)] ; (x,y) dans A^2} est donc un sous ensemble de

qui est de bon ordre, propriété qui veut dire que tout sous ensemble admet un plus petit élément, ce qui répond à ta question ...

par **maturin** » 08 Déc 2006, 14:31

explication sur la distance de hamming
on prends 2 séquences :
02110140 et 10130120 (là mon alphabet est 0,1,2,3,4)

alors la distance de hamming entre ces 2 séquences est le nombre de bit différent (dans l'exmple d=4)
Les ei représente les bits (on peut écrire le nombre binaire sous forme d'un vecteur)

le code n_aire est un ensemble de sequences (ensemble de vecteur)

il s'agit de trouver la distance minimum qu'il y a entre 2 sequence du code.

Ce que je comprends pas c'est ta question, il existe forcément un minimum, suffit de les calculer tous et de prendre le plus petit. 9a marche même avec un code infini vu que l'ensemble des distance reste un ensmble minoré par 0.

Sinon pour l'histoire cette ditasnce du code sert à connaitre la puissance du code correcteur. En gros le but est qu'en transmettant une séquence on peut se permettre d'avoir Partie_entiere((dm+1)/2) bit qui change et on saura quand même quelle séquence on a envoyé.
Ex:
si on prend les sequences 000 et 111
si lors de la transmission 1 bit change et si on receptionne 010 on comprendra que l'émetteur a voulu envoyer 000.
ce code a donc une capacité de correction de 1.

Enfin tout ça c'est basé sur de lointain souvenir...

par **charlix** » 08 Déc 2006, 14:53

merci Tize je ne connaisais pas cette propriété.

merci pour vos réponses je tiens le bon bout

par **tigrooo** » 11 Déc 2006, 20:45

Lol bienvenue a l'utbm, et précisement en MT42 :we:

Dans d[(x,y)], x et y sont des mots de cardianl pas forcement egal a 1, donc rien ne dis que c'est egal a 1. Et je ne pense pas que ca soit un théormee a demontrer ... C'est juste un fait, et on dis que l'on nomme distance minimum cette valeur rien de plus.

Vise plutot l'exercice 6 a mon avis pour cette proposition :++:

[distance minimum de Cn]

[distance minimum de Cn]

Qui est en ligne