Pages: [1]   Go Down
Print
Author Topic: Aiuto Distanza Hamming  (Read 2708 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
invochevirtual
Matricola
*
Offline Offline

Posts: 46


« on: 29-09-2011, 08:56:25 »

Buongiorno a tutti!
Scusate! Mi potreste dire il perché per rilevare gli errori ci vuole una distanza d+1 mentre per correggerli 2d+1?
cerco una spiegazione migliore rispetto a quello del libro! perché francamente nn l'ho capito!
Logged
esteta84
Apprendista Forumista
**
Offline Offline

Posts: 284



« Reply #1 on: 29-09-2011, 12:34:30 »

Il libro tratta alcuni argomenti in maniera penosa 
Logged
thedog
Apprendista Forumista
**
Offline Offline

Posts: 160


WWW
« Reply #2 on: 29-09-2011, 13:27:54 »

Buongiorno a tutti!
Scusate! Mi potreste dire il perché per rilevare gli errori ci vuole una distanza d+1 mentre per correggerli 2d+1?
cerco una spiegazione migliore rispetto a quello del libro! perché francamente nn l'ho capito!

intanto è proprio sbagliato quello che hai scritto perche per correggere "e" errori si ha bisogno di una distanza d=2e+1 che è diversa da 2d+1... cioè e=(d-1)/2
mentre per trovare "e" errori occorre una distanza d=e+1 ovvero e=d-1(e non d+1)

se non ricordo male considerando le codeword come insiemi a distanza 1 si hanno quelli facendo parte dello stesso insieme a d=2 avremo 2 insiemi uniti dove una codeword la leggeremo 2 volte mentre a d=3 avremo insiemi separati e facili da identificare e coreggere.
Quindi per questo è necessaria una distanza minima d=2 per rilevare un errore mentre per correrggelo si ha bisogno di una distanza minima di d=3

se guardi le slide trovi spiegato tutto....
« Last Edit: 29-09-2011, 13:31:38 by thedog » Logged
invochevirtual
Matricola
*
Offline Offline

Posts: 46


« Reply #3 on: 29-09-2011, 21:23:45 »

Buongiorno a tutti!
Scusate! Mi potreste dire il perché per rilevare gli errori ci vuole una distanza d+1 mentre per correggerli 2d+1?
cerco una spiegazione migliore rispetto a quello del libro! perché francamente nn l'ho capito!

intanto è proprio sbagliato quello che hai scritto perche per correggere "e" errori si ha bisogno di una distanza d=2e+1 che è diversa da 2d+1... cioè e=(d-1)/2
mentre per trovare "e" errori occorre una distanza d=e+1 ovvero e=d-1(e non d+1)

se non ricordo male considerando le codeword come insiemi a distanza 1 si hanno quelli facendo parte dello stesso insieme a d=2 avremo 2 insiemi uniti dove una codeword la leggeremo 2 volte mentre a d=3 avremo insiemi separati e facili da identificare e coreggere.
Quindi per questo è necessaria una distanza minima d=2 per rilevare un errore mentre per correrggelo si ha bisogno di una distanza minima di d=3

se guardi le slide trovi spiegato tutto....

grazie xd
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.475


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #4 on: 29-09-2011, 22:22:31 »

Questa cosa era nell'esame di oggi di Teoria dei Codici  !

Non penso che sia richiesto questo livello di esplicitazione , ma visto che ho questo teorema ancora fresco in testa, lo scriverò .

Def. Poniamo \fs{3}\mathbb{F}_2=\{{0, 1}\}

Def. Siano \fs{3}\vec{x},\vec{y}\in{\mathbb{F}_2}^n

Poniamo \fs{3}d(\vec{x}, \vec{y})=|\{i:x_i\not{=}y_i\}| e chiamiamo \fs{3}d distanza di Hamming

Def. Sia \fs{3}C\subset{\mathbb{F}_2}^n codice lineare (i codici di Hamming sono esempi di codici lineari)
Poniamo \fs{3}d(C)=\min\{{d(\vec{x}, \vec{y}): \vec{x}, \vec{y}\in{\mathbb{F}_2}^n, \vec{x}\not{=}\vec{y}}\}

cioè \fs{3}d(C) è la distanza minima fra tutte le distanze calcolate su parole 2 a 2 diverse e del codice.

Def. Sia \fs{3}C\subset {\mathbb{F}_2}^n codice lineare
e siano \fs{3}\vec{x}\in C parola trasmessa e \fs{3}\vec{y}\in C parola ricevuta (attraverso un canale rumoroso, cioè che lascia i bit trasmessi soggetti a errore)
Allora il decoder ottimale è una funzione che manda la parola \fs{3}\vec{y}\in{\mathbb{F}_2}^n nella parola \fs{3}\vec{x'}\in C tale che:

\fs{3}d(\vec{y}, \vec{x'})=\min{\{d(\vec{y}, \vec{z}): \vec{z}\in C}\}

Teorema Sia \fs{3}C\subset {\mathbb{F}_2}^n codice lineare
e siano \fs{3}\vec{x}\in C parola trasmessa e \fs{3}\vec{y}\in C parola ricevuta (attraverso un canale rumoroso, cioè che lascia i bit trasmessi soggetti a errore)

Sia \fs{3}e=d(\vec{y}, \vec{x}) il numero di bit cambiati in trasmissione (errore) e valga \fs{3}e\leq\frac{d(C)-1}{2}, equivalentemente detto \fs{3}2\cdot e\leq d(C)-1

Allora \fs{3}\vec{x'} ottenuto dal decoder ottimale è tale che: \vec{x'}=\vec{x}

Dim.

Ricordiamo che \fs{3}e=d(\vec{y}, \vec{x})

e consideriamo che \fs{3}d(\vec{y}, \vec{x'})=\min{\{d(\vec{y}, \vec{z}): \vec{z}\in C}\}\leq d(\vec{y}, \vec{x})

poiché essendo che \fs{3}\vec{x}\in C, allora \fs{3}d(\vec{y}, \vec{x})\in{\{d(\vec{y}, \vec{z}): \vec{z}\in C}\} e qualsiasi elemento di un insieme ordinato è maggiore o uguale al minimo di tale insieme.

Stimiamo, allora, il valore \fs{3}d(\vec{x}, \vec{x'})

\fs{3}d(\vec{x}, \vec{x'})\leq_1 d(\vec{x}, \vec{y})+d(\vec{y}, \vec{x'})=_2 e+d(\vec{y}, \vec{x'})\leq_3 e+e=2\cdot e\leq d(C)-1<d(C)

\fs{3}\leq_1: applicazione della proprietà triangolare delle distanze (e la distanza di Hamming è una distanza valida), che dice che la distanza tra due elementi è minore o uguale della somma delle distanze di tali elementi rispetto a un terzo elemento qualsiasi.
\fs{3}=_2: \fs{3}d(\vec{y}, \vec{x})=e
\fs{3}\leq_3: poiché valeva \fs{3}d(\vec{y}, \vec{x'})=\leq d(\vec{y}, \vec{x})=e\;\Rightarrow\; d(\vec{y}, \vec{x'})\leq e

Compattando la catena di diseguaglianze, leggiamo \fs{3}d(\vec{x}, \vec{x'})<d(C)

ma \fs{3}d(C) era la distanza minima fra parole diverse del codice, perciò se la distanza tra queste due parole è minore di questa distanza minima, allora queste parole \fs{3}\vec{x} e \fs{3}\vec{x'} sono necessariamente uguali, cioè \fs{3}\vec{y} viene corretta nella parola \fs{3}\vec{x'}=\vec{x}\in C che era la parola originariamente trasmessa e su cui si sono verificati, al più, \fs{3}\frac{d(C)-1}{2} errori.

Tutte queste considerazioni si possono fare anche se il campo su cui il codice lineare non è \fs{3}\mathbb{F}_2 ma un qualsiasi campo finito.



EDIT: ho tolto due definizioni e un teorema non dimostrato che in effetti non usavo boh
« Last Edit: 29-09-2011, 22:24:57 by reversengineer » Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
esteta84
Apprendista Forumista
**
Offline Offline

Posts: 284



« Reply #5 on: 30-09-2011, 10:52:54 »

The dog... ne le slide, ne il libro spiega da quale concetto sono derivate le formule relative al rilevamento e alla correzione degli errori (rispettivamente d=e+1;             d=2*e+1) però ti assicuro che il prof. le ha spiegate in aula
Logged
thedog
Apprendista Forumista
**
Offline Offline

Posts: 160


WWW
« Reply #6 on: 01-10-2011, 12:38:48 »

The dog... ne le slide, ne il libro spiega da quale concetto sono derivate le formule relative al rilevamento e alla correzione degli errori (rispettivamente d=e+1;             d=2*e+1) però ti assicuro che il prof. le ha spiegate in aula
Estate84 guarda le slide dove c'è scritto ridondanza con disegnati gli insiemi se fai attenzione nel primo c'è scritto d=1 glia ltri son quelli che ho scritto.
 si non c'è scritto esplicitamente ma a lezione il prof l'ha spiegati riferendosi a tale slide se non ricordo male infatti li ho appuntati in tale slide per ricordare e capire...
Logged
Pages: [1]   Go Up
Print
Jump to: