Esercizio correzione codifica Hamming
Salve a tutti,
il mio problema è data la seguente codifica di Hamming ricevuta da un destinatario di verificarne la presenza di errori ed effettuarne la correzione.(Parità pari)
Sequenza ricevuta: 10110011001101
A me tornano che ci sono errori...
Grazie per l'aiuto!
il mio problema è data la seguente codifica di Hamming ricevuta da un destinatario di verificarne la presenza di errori ed effettuarne la correzione.(Parità pari)
Sequenza ricevuta: 10110011001101
A me tornano che ci sono errori...
Grazie per l'aiuto!
Risposte
"Frastolo":
A me tornano che ci sono errori...
ok, se mostri il procedimento ti si dice se è corretto o meno.
Allora io lo risolvo cosi:
Siano: n=lunghezza messaggio originale(non codificato), m=lunghezza del messaggio ricevuto(codificato), k=n° di bit per le parità.
Io vado a ritroso cioè mi trovo il k minimo che il codificatore avrebbe messo sapendo che per codificare k andava scelto secondo questa relazione: n+1 <= 2^(k) -k e ricordando che m=n+k conosco quindi m e allora n=m-k e risostituendo nella disuguaglianza trovo che k=4.
Ora trovato k so che nel messaggio codificato le posizioni che vanno da 2^0 a 2^(k-1) cioè le posizioni 1,2,4,8 sono quelle relative ai bit di parità e quindi mi estrapolo dal messaggio codificato il messaggio originale(che potrebbe avere errori perchè è stato trasmesso).
A questo punto calcolo a partire dal messaggio estrapolato i bit di parità che il codificatore avrebbe usato per codificare il messaggio che mi sono estratto. Se i bit di parità sono uguali allora da come ho capito non ci sono errori altrimenti si.
Fino a qui è corretto il ragionamento?
Siano: n=lunghezza messaggio originale(non codificato), m=lunghezza del messaggio ricevuto(codificato), k=n° di bit per le parità.
Io vado a ritroso cioè mi trovo il k minimo che il codificatore avrebbe messo sapendo che per codificare k andava scelto secondo questa relazione: n+1 <= 2^(k) -k e ricordando che m=n+k conosco quindi m e allora n=m-k e risostituendo nella disuguaglianza trovo che k=4.
Ora trovato k so che nel messaggio codificato le posizioni che vanno da 2^0 a 2^(k-1) cioè le posizioni 1,2,4,8 sono quelle relative ai bit di parità e quindi mi estrapolo dal messaggio codificato il messaggio originale(che potrebbe avere errori perchè è stato trasmesso).
A questo punto calcolo a partire dal messaggio estrapolato i bit di parità che il codificatore avrebbe usato per codificare il messaggio che mi sono estratto. Se i bit di parità sono uguali allora da come ho capito non ci sono errori altrimenti si.
Fino a qui è corretto il ragionamento?
ho letto velocemente, ma mi sembra ok. Piccola nota, considera che il codificatore ricevente, i patter a potenza di due, sono direttamente nell'hardware.
Mostra il procedimento e vediamo i calcolini, così si vede se è tutto chiaro.
Mostra il procedimento e vediamo i calcolini, così si vede se è tutto chiaro.
Messaggio da decodificare: 10110011001101
M=14 ; n=10 ; k=4
I bit di parità del nel messaggio ricevuto sono alle posizioni:1,2,4,8 e sono p1=1 ; p2=0 ;p3=1;p4=1
Il messaggio ricevuto si trovo nelle restanti posizioni e vale perciò: 1001001101
Ricalcolo le parità del messaggio ricevuto(1001001101) cioè i nuovi p1x,p2x,p3x,p4x.
Mi scrivo in binario le posizioni dei bit del messaggio ricevuto e le posizioni dei p1x dentro al messaggio codificato:
POSIZIONI BIT MESSAGGIO
valore in binario; posizione(decimale); valore
0001; 1; 1
0010; 2; 0
0011; 3; 0
0100; 4; 1
0101; 5; 0
0110; 6; 0
0111; 7; 1
1000; 8; 1
1001; 9; 0
1010; 10; 1
POSIZIONI BIT PARITA'
valore in binario; posizione(decimale)
0001; 1
0010; 2
0100; 4
1000; 8
Calcolo i vari px elencando i vari bit del messaggio che mi andranno a contribuire nel calcolo della parità di px:
px1= posizioni{1,3,5,7,9}=valori 10010 ->px1=0
px2= posizioni{2,3,6,7,10}= valori 00011 ->px2=0
px3= posizioni{4,5,6,7}= valori 1001->px3=0
px4= posizioni{8,9,10}=valori 101 ->px4=0
Ora i bit di parità pi sono diversi da quelli ricalcolati pxi (i=1,2,3,4) e quindi deduco che è avvenuta una alterazione del messaggio durante la trasmissione.
M=14 ; n=10 ; k=4
I bit di parità del nel messaggio ricevuto sono alle posizioni:1,2,4,8 e sono p1=1 ; p2=0 ;p3=1;p4=1
Il messaggio ricevuto si trovo nelle restanti posizioni e vale perciò: 1001001101
Ricalcolo le parità del messaggio ricevuto(1001001101) cioè i nuovi p1x,p2x,p3x,p4x.
Mi scrivo in binario le posizioni dei bit del messaggio ricevuto e le posizioni dei p1x dentro al messaggio codificato:
POSIZIONI BIT MESSAGGIO
valore in binario; posizione(decimale); valore
0001; 1; 1
0010; 2; 0
0011; 3; 0
0100; 4; 1
0101; 5; 0
0110; 6; 0
0111; 7; 1
1000; 8; 1
1001; 9; 0
1010; 10; 1
POSIZIONI BIT PARITA'
valore in binario; posizione(decimale)
0001; 1
0010; 2
0100; 4
1000; 8
Calcolo i vari px elencando i vari bit del messaggio che mi andranno a contribuire nel calcolo della parità di px:
px1= posizioni{1,3,5,7,9}=valori 10010 ->px1=0
px2= posizioni{2,3,6,7,10}= valori 00011 ->px2=0
px3= posizioni{4,5,6,7}= valori 1001->px3=0
px4= posizioni{8,9,10}=valori 101 ->px4=0
Ora i bit di parità pi sono diversi da quelli ricalcolati pxi (i=1,2,3,4) e quindi deduco che è avvenuta una alterazione del messaggio durante la trasmissione.
un calcolo veloce per sapere $k$ è con l'uguaglianza $k = \lceil \log_2(M) \rceil$.
le posizioni del messaggio le alteri così facendo, perchè la posizione $8$ della codeword è differente dal posizione $8$ del messaggio, sono slot differenti.
stranemente sembra tornare il tuo procediemento, ma non si suddivide così, almeno non lo farei così.
1 controlla: 1-3-...-9-11-13
e non capisco perchè usi solo il sottoinsieme del messaggio e non tutta la codeword. Forse te ricalcoli dall'inizio e non fai il controllo inverso. Ma il risultato che trovi significa che non ci sono stati errori di trasmissione.
vedi meglio il tutto in forma tabellare. Le potenze di due sono dei pattern, e conti gli $1$ della codeword in presenza di un $1$ nel pattern (in realtà si potrebbe fare con degli XOR, perchè ci sono della varianti più legate alla circuiteria, ma il fine è lo stesso).
come vedi i bit di controllo con i bit del messaggio, sommati sono pari significa che NON ci sono errori. Difatti se ricalcoli il messaggio trovi la codeword originale.
POSIZIONI BIT MESSAGGIO
valore in binario; posizione(decimale); valore
0001; 1; 1
0010; 2; 0
0011; 3; 0
0100; 4; 1
0101; 5; 0
0110; 6; 0
0111; 7; 1
1000; 8; 1
1001; 9; 0
1010; 10; 1
POSIZIONI BIT PARITA'
valore in binario; posizione(decimale)
0001; 1
0010; 2
0100; 4
1000; 8
le posizioni del messaggio le alteri così facendo, perchè la posizione $8$ della codeword è differente dal posizione $8$ del messaggio, sono slot differenti.
stranemente sembra tornare il tuo procediemento, ma non si suddivide così, almeno non lo farei così.
1 controlla: 1-3-...-9-11-13
e non capisco perchè usi solo il sottoinsieme del messaggio e non tutta la codeword. Forse te ricalcoli dall'inizio e non fai il controllo inverso. Ma il risultato che trovi significa che non ci sono stati errori di trasmissione.
vedi meglio il tutto in forma tabellare. Le potenze di due sono dei pattern, e conti gli $1$ della codeword in presenza di un $1$ nel pattern (in realtà si potrebbe fare con degli XOR, perchè ci sono della varianti più legate alla circuiteria, ma il fine è lo stesso).
| # | C | 1 | 2 | 4 | 8 |
| 1 | 1 | 0 | 0 | 0 | 2 |
| 0 | 1 | 0 | 0 | 3 | 1 |
| 1 | 0 | 0 | 4 | 1 | 0 |
| 1 | 0 | 5 | 0 | 1 | 0 |
| 0 | 6 | 0 | 0 | 1 | 1 |
| 7 | 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 9 |
| 1 | 0 | 0 | 1 | 10 | 0 |
| 1 | 0 | 1 | 11 | 1 | 1 |
| 0 | 1 | 12 | 1 | 0 | 0 |
| 1 | 13 | 0 | 1 | 0 | 1 |
| 14 | 1 | 0 | 1 | 1 | 1 |
| 4 | 4 | 4 | 4 |
come vedi i bit di controllo con i bit del messaggio, sommati sono pari significa che NON ci sono errori. Difatti se ricalcoli il messaggio trovi la codeword originale.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo