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