Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Reti di Calcolatori, 9 CFU => Topic started by: thedog on 05-07-2011, 13:56:57



Title: hamming cambio formula ridondanza
Post by: thedog on 05-07-2011, 13:56:57
salve colleghi il mio dubbio e il seguente nella formula relativo alla ridondanza, che se non erro e per distanza hamming=3 come devo cambiarla per una distanza maggiore tipo 5??? cioè

con hammin per corregere e errori bisogna avere d=2e+1 mentre per rilevarli d=e+1 e fino a qui ok
ora considerando che avendo m bit dati e r bit di ridondanza sappiamo che la lunghezza tot della codeword e n=m+r
quindi per 2^m codeworck ne abbiamo solo 2^n valide quindi, per creare una codifica con m bit messaggio e r di controllo che ci permette di corregere gli errori singoli , per 2^m messaggi legali ho bisogno di n+1 combinazioni di bit dedicate quindi

(n+1)2^m \le 2^n

che poi sostituendo a n=m+r viene modificata....

ora se non ricordo male tale formula è per d=3 ovvero la minima distanza per corregere 1 errore, ricordo che il prof aveva detto che nel caso in cui d fosse superiore si doveva cambiare la formula...
Qualcuno potrebbe darmi una mano a capire come???


Title: Re:hamming cambio formula ridondanza
Post by: cock86 on 05-07-2011, 22:53:54
prima una piccola domanda. Ti è chiaro a cosa servono questi calcoli?(te lo chiedo così in caso potrei provare a spiegarti)
Tornando a noi (n+1)2m sono il numero di parole in un codice a distanza di hamming pari a 3 (come dici tu). Questo viene dalle codeword lecite e da tutte le parole che stanno a distanza uno da una parola lecita. Se invece per esempio dovremmo correggere due errori, utilizzeremo un codice a distanza 5. Le codeword lecite saranno ancora 2m mentre quelle che vi stanno intorno questa volta saranno di più, per la precisione ancora n saranno le parole ad un passo, a due passi (cioè ad un passo da ognuna di queste) saranno (n-1)n, quindi sommiamo la parola lecita, più quelle ad un passo, più quelle a due passi, e viene fuori 1+n+(n(n-1)), queste dobbiamo moltiplicarle per il numero di parole lecite (come detto prima) 2m. Verrà fuori una disequazione simile alla precedente (da risolvere), ma che sta volta serve per i codici a distanza uguale 5 per la rilevazione di due errori.

1+n+(n(n-1))2^m \le 2^n

dove n=m+r.

I calcoli poi continuano come nella prima.
Ovviamente lo stesso vale per i codici a distanza maggiore.


Title: Re:hamming cambio formula ridondanza
Post by: Fantius on 16-02-2012, 11:22:07
è passato un pò di tempo però mi sta sorgendo un grosso dubbio!!! perchè a due passi è n(n-1) ??


Title: Re:hamming cambio formula ridondanza
Post by: cock86 on 16-02-2012, 11:59:11
Perché al primo passo ne abbiamo n a distanza 1, per ognuna di queste n ce n'è saranno altre n a distanza 1 da quest'ultima, ma una di queste n, una è quella da cui iniziamo, per cui è a distanza 0 (dalla parola iniziale) e non 2 quindi non si conta, da qui viene n-1, per cui consideriamo n-1 per ogni n. Viene quindi n(n-1) a distanza 2. Spero di essere stato chiaro. Anche perché è passato un pò di tempo e i ricordi nella mia testa non sono lucidissimi.


Title: Re:hamming cambio formula ridondanza
Post by: Fantius on 16-02-2012, 12:21:27
si penso di aver capito  .smile grazie


Title: Re:hamming cambio formula ridondanza
Post by: cock86 on 16-02-2012, 12:33:42
ma figurati!  .wink


Title: Re:hamming cambio formula ridondanza
Post by: Mirkesx on 11-07-2019, 11:12:06
Lo so che faccio necroposting, ma prima che qualche collega (come il sottoscritto) si imbatta in questo topic e legga quello che c'è scritto volevo fare una precisazione.

La logica di risoluzione di cock86 mi ha aiutato a capire come rispondere allo stesso quesito che si poneva Fantius, però è errato dire che le codewords a distanza due sono n*(n-1) questo perchè si conterebbero diverse codewords errate già contate precedentemente (esattamente ne contiamo il doppio).

La formula più corretta sarebbe n*(n-1)/2 ovvero combinazioni semplici di n elementi di classe 2 (o n-2 se preferite). Ogni volta che si fa il conto bisogna ignorare le codewords già contate precedentemente e con le combinazioni andiamo sul sicuro.

Si potrebbe generalizzare dicendo che:

1 parola corretta (Cn,0) ha n parole con distanza hamming = 1 (Cn,1), n(n-1)/2 parole con distanza hamming = 2 (Cn,2) e cosi via. Nel caso di risoluzione del doppio errore, la formula per il calcolo dei bit di ridondanza diventerebbe:

(Cn,0 + Cn,1 + Cn,2) * 2^m <= 2^n -> [1 + n + n*(n-1)/2 ]*2^m <= 2^n

Si sostituisce n = m + r e si svolgono i conti se si vuole esplicitare m e r.

Potete provare con la codifica a d=5 (minimo per correggere 2 errori) che consta delle due sole codewords 00000 e 11111. Quindi m = 1 e r = 4, perchè avremo 2 sole parole corrette e la restante parte parole non corrette.
n = 5 ovviamente. Ma è corretto dire che r deve essere 4?

Se sostituiamo alla formula su menzionata risulterà 32 <= 32 che è vera, confermando il ragionamento.

Se si provasse a scrivere tutte le possibili combinazioni di codici errati partendo da una codeword corretta (fino a distanza 2) si constaterebbe che le parole a distanza 2 non ripetute sono 10 (esattamente C5,2).