Matematicamente.it

Sto studiando il codice di hamming, ma vorrei capire alcune cose che non mi sono chaire: perchè vale la formula $2^r>= n+r+1$? Se considero $n = 8$, perchè $r$ deve per forza essere $4$ e non $5$ o $6$? Perchè i bit di parità devono essere memorizzati nelle posizioni che sono potenze di $2$? E perchè per calcolare i bit di parità si usa lo xor anzichè sommare gli $1$ e calcolare i resto della divisione per $2$?
Potreste chiarirmi questi dubbi per favore?

Nessuno che sappia aiutarmi?

Premetto che è un argomento che non conosco e di cui ho appena letto qualcosina, quindi cercherò di risponderti in base a quello che ho capito.

perchè vale la formula $2^r>=n+r+1$?

Dai un'occhiata a pag.20 del seguente pdf:
http://wwwusers.di.uniroma1.it/~reti/Re ... codnof.pdf

Se considero $n=8$, perchè $r$ deve per forza essere $4$ e non $5$ o $6$ ?

Fissato $n$ devi trovare il minimo valore di $r$ che soddisfa la suddetta disequazione, altrimenti ti ritroverai a non poter applicare "normalmente" il codice di hamming.

Perchè i bit di parità devono essere memorizzati nelle posizioni che sono potenze di $2$?

Innanzitutto durante la codifica/decodifica bisogna sapere quali sono i bit di controllo, quindi risulta necessario adottare una convenzione, ed in ogni caso tale convenzione non è casuale, ma funzionale alla codifica di hamming. La rappresentazione in binario di $2^m$ è caratterizzata da un $1$ seguito da $m$ zeri, ciò significa che ciascun bit di ridondanza controllerà uno o più bit della parola (più precisamente i bit la cui codifica in binario della propria posizione nella parola-codice presenta un $1$ nella stessa posizione della potenza di $2$ considerata), ma non gli altri bit di ridondanza.

E perchè per calcolare i bit di parità si usa lo xor anzichè sommare gli $1$ e calcolare i resto della divisione per $2$?

In cosa consisterebbe questo utilizzo dello xor?

Grazie per la risposta chiara. Per l'ultimo punto, quando si implementa l'algoritmo per la codifica, per determinare i bit di parità da inserire nel codice, si fa lo xor tra gli elementi nelle altre posizioni.

Se ho ben capito quello che intendi, la risposta è che i due procedimenti sono equivalenti.
Considera la tabella di verità dello xor:

0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0

Risulta evidente che dati 2 bit, sommare gli $1$ e calcolare il resto della divisione per $2$ o fare lo xor, restituisce lo stesso risultato. L'equivalenza inoltre resta valida anche se i bit considerati sono più di 2, infatti ogni $1$ incontrato a partire dal terzo bit in poi non farà altro che modificare il risultato precedente.

Grazie mille per il chiarimento!