Distancia de Hamming

De Wiki do Pazo da Mercé

(Diferenzas entre revisións)
 
(Non se mostra unha revisión do historial.)
Liña 1: Liña 1:
== Definición ==
== Definición ==
-
A distancia Hamming entre dúas palabras dun código é o número de bits en que difiren ambas.
+
A [http://es.wikipedia.org/wiki/Distancia_de_Hamming distancia de Hamming] entre dúas palabras dun código é o número de bits en que difiren ambas.
Por exemplo, a distancia d entre estas dúas palabras é 3: ''d(010010110, 110110111)=3''
Por exemplo, a distancia d entre estas dúas palabras é 3: ''d(010010110, 110110111)=3''
-
Dúas  palabras serán máis fáciles de distinguir canto maior sexa a súa distancia Hamming, debido a que si a distancia é d, fan falla d bits erróneos para confundir unha palabra con outra. Co cal a eficacia dun código depende da distancia Hamming mínima que poida encontrase entre dúas das súas palabras:
+
Dúas  palabras serán máis fáciles de distinguir canto maior sexa a súa distancia Hamming, debido a que si a distancia é d, fan falla d bits erróneos para confundir unha palabra con outra.  
 +
 
 +
A eficacia dun código depende da distancia Hamming mínima que poida encontrase entre dúas das súas palabras:
* Un código C é capaz de detectar p ou menos erros se dmin >= p+1
* Un código C é capaz de detectar p ou menos erros se dmin >= p+1
Liña 14: Liña 16:
=== Código 1 ===
=== Código 1 ===
 +
 +
Neste código usamos a función de codificación ''f(A,B) = (A, B, A+B)''
 +
 +
{| border="1" cellpadding="5" cellspacing="0"
 +
!Mensaxes
 +
!Palabras do código
 +
|-
 +
|0 0
 +
|0 0 0
 +
|-
 +
|0 1
 +
|0 1 1
 +
|-
 +
|1 0
 +
|1 0 1
 +
|-
 +
|1 1
 +
|1 1 0
 +
|}
 +
 +
As palabras código son: {000, 011, 101, 110}. Podemos calcular que dmin=2, co cal este código detecta erros simples (nun só bit), pero non capaz de corrixilos.
 +
 +
'''Exemplo''':
 +
* O transmisor desexa enviar 01 para iso  codifica como 011 e transmítea.
 +
 +
* O receptor recibe 111.
 +
 +
* A palabra 111 non é unha palabra código, co cal non pode decodificala e así obter a mensaxe orixinal.
 +
 +
* Esta palabra 111 non puido ser transmitida, co cal produciuse un erro nun bit pero o decodificador non pode determinar en cal.
 +
 +
* Non podemos recuperar a mensaxe orixinal; isto implica que temos que solicitar unha retransmisión.
=== Código 2 ===
=== Código 2 ===
 +
 +
Neste código usamos a función de codificación ''f(A,B) = (A, B, A, B, A, B)''
 +
 +
{| border="1" cellpadding="5" cellspacing="0"
 +
!Mensaxes
 +
!Palabras do código
 +
|-
 +
|0 0
 +
|0 0 0 0 0 0
 +
|-
 +
|0 1
 +
|0 1 0 1 0 1
 +
|-
 +
|1 0
 +
|1 0 1 0 1 0
 +
|-
 +
|1 1
 +
|1 1 1 1 1 1
 +
|}
 +
 +
Neste caso dmin=3, co cal o decodificador corrixe erros simples e detecta erros dobres e simples.
 +
 +
Podemos supoñer que os erros ocorren aleatoriamente e independentemente, e que a probabilidade de erro é igual en calquera dos díxitos (é máis probable que se produza un erro que 2, 2 que 3, ...). Usaremos entón a '''decodificación de máxima verosimilitude''': é dicir, para decodificar a palabra recibida buscarase aquela palabra código máis probablemente transmitida, ou sexa a que difira no menor número de díxitos coa palabra recibida.
 +
 +
'''Exemplo''':
 +
 +
* Se y=010111 é a palabra recibida, calcúlase:
 +
 +
.d(000000, 010111)=4
 +
.d(010101, 010111)=1
 +
.d(101010, 010111)=5
 +
.d(111111, 010111)=2
 +
 +
* A menor distancia Hamming entre as palabras código e a palabra recibida prodúcese no 2º caso.
 +
 +
* A palabra código máis probablemente transmitida será: x=010101.
 +
 +
* Neste caso o decodificador detecta e corrixe o erro.

Revisión actual ás 14:22, 13 decembro 2008

Índice

Definición

A distancia de Hamming entre dúas palabras dun código é o número de bits en que difiren ambas.

Por exemplo, a distancia d entre estas dúas palabras é 3: d(010010110, 110110111)=3

Dúas palabras serán máis fáciles de distinguir canto maior sexa a súa distancia Hamming, debido a que si a distancia é d, fan falla d bits erróneos para confundir unha palabra con outra.

A eficacia dun código depende da distancia Hamming mínima que poida encontrase entre dúas das súas palabras:

  • Un código C é capaz de detectar p ou menos erros se dmin >= p+1
  • Un código C é capaz de corrixir p ou menos erros se dmin >= 2*p+1

Exemplos de códigos

Código 1

Neste código usamos a función de codificación f(A,B) = (A, B, A+B)

Mensaxes Palabras do código
0 0 0 0 0
0 1 0 1 1
1 0 1 0 1
1 1 1 1 0

As palabras código son: {000, 011, 101, 110}. Podemos calcular que dmin=2, co cal este código detecta erros simples (nun só bit), pero non capaz de corrixilos.

Exemplo:

  • O transmisor desexa enviar 01 para iso codifica como 011 e transmítea.
  • O receptor recibe 111.
  • A palabra 111 non é unha palabra código, co cal non pode decodificala e así obter a mensaxe orixinal.
  • Esta palabra 111 non puido ser transmitida, co cal produciuse un erro nun bit pero o decodificador non pode determinar en cal.
  • Non podemos recuperar a mensaxe orixinal; isto implica que temos que solicitar unha retransmisión.


Código 2

Neste código usamos a función de codificación f(A,B) = (A, B, A, B, A, B)

Mensaxes Palabras do código
0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
1 1 1 1 1 1 1 1

Neste caso dmin=3, co cal o decodificador corrixe erros simples e detecta erros dobres e simples.

Podemos supoñer que os erros ocorren aleatoriamente e independentemente, e que a probabilidade de erro é igual en calquera dos díxitos (é máis probable que se produza un erro que 2, 2 que 3, ...). Usaremos entón a decodificación de máxima verosimilitude: é dicir, para decodificar a palabra recibida buscarase aquela palabra código máis probablemente transmitida, ou sexa a que difira no menor número de díxitos coa palabra recibida.

Exemplo:

  • Se y=010111 é a palabra recibida, calcúlase: 
.d(000000, 010111)=4
.d(010101, 010111)=1
.d(101010, 010111)=5
.d(111111, 010111)=2
  • A menor distancia Hamming entre as palabras código e a palabra recibida prodúcese no 2º caso.
  • A palabra código máis probablemente transmitida será: x=010101.
  • Neste caso o decodificador detecta e corrixe o erro.
Traído desde "http://centros.edu.xunta.es/iespazodamerce/wiki/index.php/Distancia_de_Hamming"
Crear un libro