Pages: [1]   Go Down
Print
Author Topic: hamming cambio formula ridondanza  (Read 2240 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
thedog
Apprendista Forumista
**
Offline Offline

Posts: 160


WWW
« 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???
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #1 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.
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Fantius
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 378



« Reply #2 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) ??
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #3 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.
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Fantius
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 378



« Reply #4 on: 16-02-2012, 12:21:27 »

si penso di aver capito  grazie
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #5 on: 16-02-2012, 12:33:42 »

ma figurati! 
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Pages: [1]   Go Up
Print
Jump to: