Pages: [1]   Go Down
Print
Author Topic: hamming cambio formula ridondanza  (Read 2701 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!
Mirkesx
Matricola
*
Offline Offline

Posts: 23


« Reply #6 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).
« Last Edit: 11-07-2019, 11:34:45 by Mirkesx » Logged
Pages: [1]   Go Up
Print
Jump to: