DISTANZA DI HAMMING
Qualcuno sa spiegarmi, in modo più semplice possibile, come si calcola la distanza di Hamming?Perchè tra due parole 11110001 e 00110000 la distanza è 3, mentre tra altre due parole 0000000000 e 0000011111 la distanza è 5?
Come si calcola questa distanza?
Non capisco quando fa riferimento al bit di parità che si può correggere l'errore....
Grazie a tutti.... Ciao!!!
Risposte
Devi contare il numero di bit diversi (nella stessa posizione) tra due stringhe binarie e i conti tornano..
Nel primo caso, ci sono da aggiungere tre 1 alla seconda stringa per renderla uguale alla prima (o aggiungere tre 0 alla prima, per renderla uguale alla prima
).
Nel primo caso, ci sono da aggiungere tre 1 alla seconda stringa per renderla uguale alla prima (o aggiungere tre 0 alla prima, per renderla uguale alla prima
).
"Crook":
Devi contare il numero di bit diversi (nella stessa posizione) tra due stringhe binarie e i conti tornano..
Nel primo caso, ci sono da aggiungere tre 1 alla seconda stringa per renderla uguale alla prima (o aggiungere tre 0 alla prima, per renderla uguale alla prima
Quindi, in pratica devo confrontare le due stringhe, vedere come sono diverse e aggiungere nell'una o nell'altra quello che manca per renderle uguali? Quello che aggiungo è la distanza?
E il discorso dei bit di parità?
Si chiama distanza di Hamming, tra $x,y$, essendo $ x = ( x_1,x_2...x_n )$ e $ y=(y_1,y_2...y_n) $la quantità $ d(x,y) = sum_1^n |x_k-y_k|$.Poichè le componenti dei vettori valgono 1 oppure 0 , la quantità $|x_k-y_k|$ vale 0 se le due componeneti coincidono e 1 in caso contrario; questa differenza coincide con la somma modulo 2 di tra $x_k $ e $ y_k$ :
$|x_k-y_k| =(x_k+y_k ) $mod 2..
In conclusione $d(x,y)$ conta quanti sono gli indici k ( e quindi quante sono le posizioni ) in corrispondenza dei quali $x_k, y_k $ sono diversi tra di loro.
Quindi nell'ultimo esempio che fai la distanza vale 5 perchè le prime 5 cifre sono uguali , mentre le seconde 5 cifre sono diverse.
$|x_k-y_k| =(x_k+y_k ) $mod 2..
In conclusione $d(x,y)$ conta quanti sono gli indici k ( e quindi quante sono le posizioni ) in corrispondenza dei quali $x_k, y_k $ sono diversi tra di loro.
Quindi nell'ultimo esempio che fai la distanza vale 5 perchè le prime 5 cifre sono uguali , mentre le seconde 5 cifre sono diverse.
"Camillo":
Si chiama distanza di Hamming, tra $x,y$, essendo $ x = ( x_1,x_2...x_n )$ e $ y=(y_1,y_2...y_n) $la quantità $ d(x,y) = sum_1^n |x_k-y_k|$.Poichè le componenti dei vettori valgono 1 oppure 0 , la quantità $|x_k-y_k|$ vale 0 se le due componeneti coincidono e 1 in caso contrario; questa differenza coincide con la somma modulo 2 di tra $x_k $ e $ y_k$ :
$|x_k-y_k| =(x_k+y_k ) $mod 2..
In conclusione $d(x,y)$ conta quanto sono gli indici k ( e quindi quante sono le posizioni ) in corrispondenza dei quali $x_k, y_k $ sono diversi tra di loro.
Quindi nell'ultimo esempio che fai la distanza vale 5 perchè le prime 5 cifre sono uguali , mentre le seconde 5 cifre sono diverse.
Quindi in praitca devo fare quanto ho scritto sopra....... devo confrontare le due stringhe, vedere come sono diverse e aggiungere nell'una o nell'altra quello che manca per renderle uguali? Quello che aggiungo è la distanza?
E il discorso dei bit di parità in cosa consiste? Perchè si riferisce ai bit di parità per correggere gli errori... quando si possono correggere?
"gio80":
Quello che aggiungo è la distanza?
Il numero di bit che devi aggiungere è la distanza.
"gio80":
E il discorso dei bit di parità in cosa consiste? Perchè si riferisce ai bit di parità per correggere gli errori... quando si possono correggere?
Non ho capito la domanda...
"Crook":
[quote="gio80"]
Quello che aggiungo è la distanza?
Il numero di bit che devi aggiungere è la distanza.
"gio80":
E il discorso dei bit di parità in cosa consiste? Perchè si riferisce ai bit di parità per correggere gli errori... quando si possono correggere?
Non ho capito la domanda...[/quote]
Penso che sia riferito sempre al bit di parità, ma non riesco a capire.... comunque in questa stringa 0000000000 e 0000011111 dopo aver detto che ha distanza 5 aggiunge .......... "può correggere errori doppi. Se arriva la parola codice 0000000111 il ricevente sa che l'originale doveva essere 0000011111, se gli errori verificatisi erano al massimo doppi. Tuttavia un errore triplo che modifica per esempio la parola 0000000000 nella parola 0000000111 non può essere corretto"... non ho capito questo passaggio della correzione....
Se la distanza di Hamming tra codici legittimi è pari almeno a d=2t+1, allora è correggibile l'errore sino all'ordine t di errori.
In questo caso la distanza è 5, quindi si possono correggere stringhe con al massimo due errori.
In questo caso la distanza è 5, quindi si possono correggere stringhe con al massimo due errori.
"Crook":
Se la distanza di Hamming tra codici legittimi è pari almeno a d=2t+1, allora è correggibile l'errore sino all'ordine t di errori.
In questo caso la distanza è 5, quindi si possono correggere stringhe con al massimo due errori.
Benissimo... grazie....ma anche se la distanza è 3 si possono correggere due errori massimo?
No, perché 3=2t+1, quindi solo un errore (t=1) è correggibile. Comunque, il discorso è un po' più complicato di quello che sembra. Forse dovresti cercare informazioni un po' più approfondite..
"Crook":
No, perché 3=2t+1, quindi solo un errore (t=1) è correggibile. Comunque, il discorso è un po' più complicato di quello che sembra. Forse dovresti cercare informazioni un po' più approfondite..
In effetti abbastanza complicato... comunque ora ho capito il meccanismo e per me, credimi, è già tanto.... GRAZIE INFINITE!!! ....
Ancora grazie.... buona domenica....
"gio80":
Quindi, in pratica devo confrontare le due stringhe, vedere come sono diverse e aggiungere nell'una o nell'altra quello che manca per renderle uguali? Quello che aggiungo è la distanza?
sì, e se ti piace giocherellare con i bit, la puoi vadere anche in un altro modo:
fai l'exclusive-or delle due stringhe; il numero dei bit "1" del risultato è la distanza di Hamming
tony
"tony":
[quote="gio80"]Quindi, in pratica devo confrontare le due stringhe, vedere come sono diverse e aggiungere nell'una o nell'altra quello che manca per renderle uguali? Quello che aggiungo è la distanza?
sì, e se ti piace giocherellare con i bit, la puoi vadere anche in un altro modo:
fai l'exclusive-or delle due stringhe; il numero dei bit "1" del risultato è la distanza di Hamming
tony[/quote]
Lo nomina anke il mio libro l'exclusive-or.... ma non so come si fa.....
Operazione xor tra due bit a e b, con $ain{0;1},bin{0;1}$ e il risultato $c in {0;1}$:
$c = a o+ b = |a-b|$
In generale, date due sequenze di bit ${a_k}$ e ${b_k}$ lunghe N simboli si definisce distanza di Hamming:
$d_H = sum_(k=1)^N |a_k-b_k|$
che come vedi equivale a contare gli uni nella sequenza xorata.
$c = a o+ b = |a-b|$
In generale, date due sequenze di bit ${a_k}$ e ${b_k}$ lunghe N simboli si definisce distanza di Hamming:
$d_H = sum_(k=1)^N |a_k-b_k|$
che come vedi equivale a contare gli uni nella sequenza xorata.
"gio80":
Lo nomina anke il mio libro l'exclusive-or.... ma non so come si fa.....
Scusa il ritardo, e permettimi di esternare una perplessità:
dici di non conoscere l'exclusive or (XOR), ma sembra, dal tuo problema, che tu stia studiando roba tipo "error detection" o, peggio ancora, "error correction" in codici.
Roba, per me, definibile "advanced", moolto "advanced".
Ebbene, se è così, è strano che il tuo percorso didattico non ti abbia fatto attraversare regioni in cui potessi assaggiare e digerire concetti tipo "and", "or", "exclusive or" (per non parlar di "nand").
Strane scorciatoie degli insegnamenti odierni !
Un modo, per "ragazzi pratici", di definire l' XOR tra due bit:
c = a XOR b
b
| 0 1
--+------
0 | 0 1
a |
1 | 1 0
cioè, come suggerisce il nome, c = (a OR b), ESCLUDENDO (a AND B)
tony
"tony":
[quote="gio80"]Lo nomina anke il mio libro l'exclusive-or.... ma non so come si fa.....
Scusa il ritardo, e permettimi di esternare una perplessità:
dici di non conoscere l'exclusive or (XOR), ma sembra, dal tuo problema, che tu stia studiando roba tipo "error detection" o, peggio ancora, "error correction" in codici.
Roba, per me, definibile "advanced", moolto "advanced".
Ebbene, se è così, è strano che il tuo percorso didattico non ti abbia fatto attraversare regioni in cui potessi assaggiare e digerire concetti tipo "and", "or", "exclusive or" (per non parlar di "nand").
Strane scorciatoie degli insegnamenti odierni !
Un modo, per "ragazzi pratici", di definire l' XOR tra due bit:
c = a XOR b
b
| 0 1
--+------
0 | 0 1
a |
1 | 1 0
cioè, come suggerisce il nome, c = (a OR b), ESCLUDENDO (a AND B)
tony[/quote]
non so cosa dirti.... io ho fatto una scuola superiore non a indirizzo informtatico.... adesso, al primo anno di informatica abbiamo programmazione che è un corso dove si inizia da zero, come se nessuno sapesse niente di programmazione e stiamo facendo programmini semplici.... e archittetura degli elaboratori abbiamo questo programma... l'exclusive or il mio libro lo nomina, ma probabilmente lo da per scontato, perchè lo nomina solo....
In parole semplici, per fare l'exclusive-or fra due sequenze ne metti una sopra l'altra, poi confronti bit a bit: se sono diversi, sotto metti 1, altrimenti 0. Per esempio:
0 0 0 0 1 1 0 1 1 1 0 1 0 1 1 1 SEQ1
0 0 1 0 1 0 0 0 1 0 0 0 1 1 0 0 SEQ2
0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 Sequenza "xorata"
In pratica l'operazione di XOR tra due bit rende 1 se e solo se questi sono diversi... fatto questo, conti gli uno della sequenza ottenuta, e il gioco è fatto
hai la distanza di Hamming.
P.S.: Tony in realtà questa roba io l'ho fatta, almeno accennata, al primo anno. Per il resto comunque mi pare strano pure a me non abbiano rifatto una breve carrellata sulle porte logiche prima...
0 0 0 0 1 1 0 1 1 1 0 1 0 1 1 1 SEQ1
0 0 1 0 1 0 0 0 1 0 0 0 1 1 0 0 SEQ2
0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 Sequenza "xorata"
In pratica l'operazione di XOR tra due bit rende 1 se e solo se questi sono diversi... fatto questo, conti gli uno della sequenza ottenuta, e il gioco è fatto
hai la distanza di Hamming.P.S.: Tony in realtà questa roba io l'ho fatta, almeno accennata, al primo anno. Per il resto comunque mi pare strano pure a me non abbiano rifatto una breve carrellata sulle porte logiche prima...
"lore":
In parole semplici, per fare l'exclusive-or fra due sequenze ne metti una sopra l'altra, poi confronti bit a bit: se sono diversi, sotto metti 1, altrimenti 0. Per esempio:
0 0 0 0 1 1 0 1 1 1 0 1 0 1 1 1 SEQ1
0 0 1 0 1 0 0 0 1 0 0 0 1 1 0 0 SEQ2
0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 Sequenza "xorata"
In pratica l'operazione di XOR tra due bit rende 1 se e solo se questi sono diversi... fatto questo, conti gli uno della sequenza ottenuta, e il gioco è fatto
P.S.: Tony in realtà questa roba io l'ho fatta, almeno accennata, al primo anno. Per il resto comunque mi pare strano pure a me non abbiano rifatto una breve carrellata sulle porte logiche prima...
Ti ringrazio, così è molto chiaro tutto..... Le porte logiche le stiamo facendo adesso, forse lo faremo tra poco l'exclusive-or allora.... Cmq grazie...e ciao
(anke io sono al primo anno di informatica)
(anke io sono al primo anno di informatica)
Già
... vedo infatti che hai diversi corsi simili ai miei... fai ingegneria o scienze informatiche? (io sono al secondo anno di scienze informatiche...)Comunque fra poco queste cose le saprai alla nausea
in ogni caso, chiedi per qualsiasi dubbio.... ciao
Già ... vedo infatti che hai diversi corsi simili ai miei... fai ingegneria o scienze informatiche? (io sono al secondo anno di scienze informatiche...)
Comunque fra poco queste cose le saprai alla nausea in ogni caso, chiedi per qualsiasi dubbio.... ciao[/quote]
Sono al primo anno di informatica (facoltà di matematica).... tu dove studi? Io Bologna....
Grazie.... ciao
... vedo infatti che hai diversi corsi simili ai miei... fai ingegneria o scienze informatiche? (io sono al secondo anno di scienze informatiche...)Comunque fra poco queste cose le saprai alla nausea
in ogni caso, chiedi per qualsiasi dubbio.... ciao[/quote]Sono al primo anno di informatica (facoltà di matematica).... tu dove studi? Io Bologna....
Grazie.... ciao
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo