Distancia de Hamming
De Wiki do Pazo da Mercé
Í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.
