hamming cambio formula ridondanza

[thedog]

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 codeworck ne abbiamo solo valide quindi, per creare una codifica con m bit messaggio e r di controllo che ci permette di corregere gli errori singoli , per messaggi legali ho bisogno di n+1 combinazioni di bit dedicate quindi



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???

[cock86]

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)2^m 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 2^m 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) 2^m. 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.



dove n=m+r.

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

[Fantius]

è passato un pò di tempo però mi sta sorgendo un grosso dubbio!!! perchè a due passi è n(n-1) ??

[cock86]

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.

[Fantius]

si penso di aver capito  grazie

[cock86]

ma figurati! 

[Mirkesx]

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).