[Algoritmi] Chiarimenti sul codice di hamming

Messaggioda ZfreS » 13/11/2019, 16:41

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?
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1925 di 4589
Iscritto il: 22/10/2016, 17:52

Re: [Algoritmi] Chiarimenti sul codice di hamming

Messaggioda ZfreS » 21/11/2019, 09:52

Nessuno che sappia aiutarmi?
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1941 di 4589
Iscritto il: 22/10/2016, 17:52

Re: [Algoritmi] Chiarimenti sul codice di hamming

Messaggioda Super Squirrel » 21/11/2019, 14:58

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?
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 382 di 1486
Iscritto il: 16/05/2013, 22:05

Re: [Algoritmi] Chiarimenti sul codice di hamming

Messaggioda ZfreS » 21/11/2019, 17:40

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.
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1942 di 4589
Iscritto il: 22/10/2016, 17:52

Re: [Algoritmi] Chiarimenti sul codice di hamming

Messaggioda Super Squirrel » 21/11/2019, 18:39

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.
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 383 di 1486
Iscritto il: 16/05/2013, 22:05

Re: [Algoritmi] Chiarimenti sul codice di hamming

Messaggioda ZfreS » 21/11/2019, 21:13

Grazie mille per il chiarimento!
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1943 di 4589
Iscritto il: 22/10/2016, 17:52


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite