Codice di Hamming: differenze tra le versioni

Versione delle 15:07, 3 nov 2010

Versione attuale delle 17:58, 28 giu 2025

(44 versioni intermedie di 32 utenti non mostrate)

Riga 1:

{{F|teorie dell'informatica|arg2=telecomunicazioni|febbraio 2013}}

Nelle [[telecomunicazioni]] il '''codice di Hamming''' è un [[Forward Error Correction|codice correttore]]

[[codice lineare|lineare]] che prende il nome dal suo inventore [[Richard Hamming]]. Il codice di Hamming può rivelarerilevare e correggere gli errori di un singolo bit. In altre parole, la [[distanza di Hamming]] tra le code-word trasmesse e ricevute deve essere zero o uno per una comunicazione affidabile. In alternativa, il codice può rivelare (ma non correggere) errori singoli e doppi.

Il codice di Hamming fa parte dei [[codice lineare|codici lineari]], ed i suoi parametri sono <math>\left[\frac{q^m-1}{q-1},\frac{q^m-1}{q-1}-m,3\right]</math>, dove ''q'' è la grandezza dell'alfabeto utilizzato (ad esempio 2 se è binario) e ''m'' è il numero di bit usati.

Il [[bit di parità|codice di parità]] consente la rivelazionerilevazione dell'errore ma non la sua correzione. Aumentando la ridondanza nel messaggio (aggiunta di bit per la rivelazione e la correzione degli errori) è possibile conoscere anche la posizione del bit errato e quindi correggerlo. Il codice di Hamming fornisce questa possibilità.

Se un codice contiene ''N'' informazioni distinte, la rappresentazione in forma binaria di ciascuna di esse avviene utilizzando una parola di ''n'' bit in modo che si verifichi: <math> 2^n \ge \ N</math>.

Se, <math>2^n\ = \ N</math>, un errore in uno o più bit porta ad una configurazione binaria diversa che corrisponde, però, sempre ad un dato appartenente allo stesso codice: in pratica non si riesce a comprendere se vi è stato un errore o meno.

Riga 46 ⟶ 47:

|-

|-

|}

Si noti che se si verifica un errore il numero di 1 presentepresenti nel codice si altera. Anche questo tipo di codifica individua la presenza ma non la posizione dell'errore.

== Metodo di costruzione del codice ==

Si noti che se si verifica un errore il numero 1 presente nel codice si altera. Anche questo tipo di codifica individua la presenza ma non la posizione dell'errore.

==Metodo di costruzione del codice==

Legenda:

* <math>n</math>, il numero di bit del messaggio originale;

* <math>k</math>, il numero di "check" bit (di ridondanza) aggiunti al messaggio originale;

* <math>m=n+k</math>, il numero di bit del messaggio finale (cioè il messaggio dopo la codifica con Hamming).

# Trovare ilun valore di K : <math>n+1 \le 2^k - k</math>;

# Posizionare i K bit trovati, all'interno del messaggio originale, secondo le potenze del 2 (<math>2^0=1; 2^1=2; 2^2=4; 2^3=8;....</math>, si considerano le potenze in base al valore di K, se K è uguale a tre si prenderanno in considerazione le potenze fino a <math>2^2=4</math>);

# Trovare il valore dei K:

#* Codificare in binario le posizioni dei bit del messaggio finale (ad es. per un messaggio a 6 bit, si numereranno le posizioni dalla prima - 001- alla sesta - 110);

#* Si controllano le posizioni in binario di ogni K, facendo attenzione a quale posizione occupa il bit 1 (ad es. nella posizione 1 occupa la posizione più a destra; nella posizione 2, invece, la posizione centrale), e quali ''digit'' del messaggio possiedono un 1 nella stessa posizione;

#* Si prendono in considerazione i digit trovati e si trova il bit di parità (es. digit1=1, digit2=0,digit3=0; bit di parità=1), il bit di parità corrisponderà al valore di K.

== Rilevazione e correzione dell'errore ==

Una volta codificato il messaggio secondo Hamming, questi arriva al ricevitore il quale lo controlla prima di utilizzarlo dato che a causa dei rumori di segnale il messaggio può subire delle modifiche.

Riga 75 ⟶ 74:

Messaggio corretto:

Messaggio Originale: '''10'''

{| align=center border=1

! K!! Bit di Parità

Riga 89 ⟶ 88:

|-

|-

|}

Si ottiene cosicosì il messaggio codificato: 11'''1'''0'''0'''

''Ricevitore''

Riga 109 ⟶ 107:

|-

|-

|}

Ottenuti i valori dei K, si esegue l'operazione logica XOR fra i K corrispondenti del messaggio del ricevitore e quelli della sorgente. Si otterrà cosicosì una sequenza verticale di numeri binari.

''Esempio:''

Riga 124 ⟶ 121:

I risultati ottenuti vengono poi letti dal basso verso l'alto ottenendo la posizione in binario del bit errato (nel nostro caso otteniamo 011 (3dec))

== Voci correlate ==

* [[codice Hamming(7,4)]]

* [[distanza di Hamming]]

Riga 130 ⟶ 127:

== Altri progetti ==

{{interprogetto|commonspreposizione=Hamming codessul}}

== Collegamenti esterni ==

* {{Collegamenti esterni}}

* {{FOLDOC|Hamming code|Hamming code}}

{{Portale|matematica|informatica}}

{{Portale|matematica}}

[[Categoria:Teoria dei codici]]

[[Categoria:Logica matematica]]

[[ca:Codi de Hamming]]

[[cs:Hammingův kód]]

[[de:Hamming-Code]]

[[en:Hamming code]]

[[es:Código Hamming]]

[[eu:Hamming kode]]

[[fa:کد همینگ]]

[[fr:Code de Hamming]]

[[he:קוד המינג]]

[[ja:ハミング符号]]

[[ko:해밍 부호]]

[[nl:Hamming-code]]

[[pl:Kod Hamminga]]

[[pt:Código de Hamming]]

[[ru:Код Хэмминга]]

[[simple:Hamming code]]

[[tr:Hamming kodu]]

[[vi:Mã Hamming]]

[[zh:汉明码]]