Corregir errores con Hamming (7,4)

19

El código Hamming (7,4) se remonta a 1950. En aquel entonces, Richard Hamming trabajó como matemático en los Laboratorios Bell. Todos los viernes, Hamming configuró las máquinas de cálculo para realizar una serie de cálculos y recolectó los resultados el lunes siguiente. Mediante el uso de verificaciones de paridad, estas máquinas pudieron detectar errores durante el cálculo. Frustrado, porque recibió mensajes de error con demasiada frecuencia, Hamming decidió mejorar la detección de errores y descubrió los famosos códigos de Hamming.

Mecánica del Hamming (7,4)

El objetivo de los códigos de Hamming es crear un conjunto de bits de paridad que se superpongan de tal manera que se pueda detectar y corregir un error de un solo bit (se invierte un bit) en un bit de datos o un bit de paridad. Solo si se producen varios errores, el código de Hamming no puede recuperar los datos originales. Es posible que no note ningún error, o incluso que lo corrija falsamente. Por lo tanto, en este desafío solo trataremos con errores de un solo bit.

Como ejemplo de los códigos de Hamming, veremos el código de Hamming (7,4). Además de 4 bits de datos d1, d2, d3, d4, utiliza 3 bits de paridad p1, p2, p3, que se calculan utilizando las siguientes ecuaciones:

p1 = (d1 + d2 + d4) % 2
p2 = (d1 + d3 + d4) % 2
p3 = (d2 + d3 + d4) % 2

La palabra de código resultante (datos + bits de paridad) tiene la forma p1 p2 d1 p3 d2 d3 d4.

La detección de un error funciona de la siguiente manera. Vuelve a calcular los bits de paridad y comprueba si coinciden con los bits de paridad recibidos. En la siguiente tabla puede ver que cada variedad de un error de un solo bit produce una coincidencia diferente de los bits de paridad. Por lo tanto, cada error de un solo bit puede ser localizado y corregido.

error in bit | p1 | p2 | d1 | p3 | d2 | d3 | d4 | no error
-------------|---------------------------------------------
p1 matches   | no | yes| no | yes| no | yes| no | yes
p2 matches   | yes| no | no | yes| yes| no | no | yes
p3 matches   | yes| yes| yes| no | no | no | no | yes

Ejemplo

Deja que tus datos sean 1011. Los bits de paridad son p1 = 1 + 0 + 1 = 0, p2 = 1 + 1 + 1 = 1y p3 = 0 + 1 + 1 = 0. Combine los datos y los bits de paridad y obtendrá la palabra de código 0110011.

data bits   |   1 011
parity bits | 01 0
--------------------
codeword    | 0110011

Digamos que durante una transmisión o un cálculo, el sexto bit (= tercer bit de datos) se voltea. Recibes la palabra 0110001. Los supuestos datos recibidos son 1001. Se calculan los bits de paridad de nuevo p1 = 1 + 0 + 1 = 0, p2 = 1 + 0 + 1 = 0, p3 = 0 + 0 + 1 = 1. Solo p1coincide con los bits de paridad de la palabra de código 0110001. Por lo tanto, se produjo un error. Mirando la tabla anterior, nos dice que ocurrió el error d3y puede recuperar los datos originales 1011.

Desafío:

Escriba una función o un programa que reciba una palabra (7 bits), uno de los bits podría estar equivocado y recupere los datos originales. El formato de entrada (a través de STDIN, argumento de línea de comando, argumento de solicitud o función) puede ser una cadena "0110001", una lista o una matriz [0, 1, 1, 0, 0, 0, 1]o un entero en MSB 0b0110001 = 49. Como se describió anteriormente, el orden de la entrada es p1 p2 d1 p3 d2 d3 d4. La salida (a través del valor de retorno o STDOUT) debe ser del mismo formato, pero en el orden d1 d2 d3 d4. Solo devuelve / emite los 4 bits de datos.

Este es el código de golf. Por lo tanto, el código más corto gana.

Casos de prueba:

1110000 -> 1000  # no error
1100000 -> 1000  # error at 1st data bit
1111011 -> 1111  # error at 2nd data bit
0110001 -> 1011  # error at 3rd data bit (example)
1011011 -> 1010  # error at 4th data bit
0101001 -> 0001  # error at 1st parity bit
1010000 -> 1000  # error at 2nd parity bit
0100010 -> 0010  # error at 3rd parity bit

Mostrar fragmento de código

code-golf error-correction coding-theory Jakube
fuente
1
¿Hay alguna razón particular por la que se proporciona el último bit de paridad después del primer bit de datos?
xnor
2
@xnor Matemáticamente no hace ninguna diferencia, en qué posición están los bits de paridad. Históricamente se colocan en las posiciones de poderes de dos. Por ejemplo, Hamming (15,11) tiene los bits de paridad en las posiciones 1, 2, 4 y 8.
Jakube
44
@xnor Si toma la [is_p3_wrong][is_p2_wrong][is_p1_wrong]base dos, le da la posición del bit incorrecto en la palabra. (Basado en la tabla de la pregunta). Esto probablemente será útil para algunos algoritmos.
randomra
Muy agradable :) Cuando escribes "Escribe una función o un programa que recibe una palabra (7 bits), uno de ellos puede estar equivocado," [...] "Creo que quieres decir que uno de los bits puede estar equivocado, pero tú De hecho decir una de las palabras podría ser.
@Lembik Claro, lo aclaró.
Jakube

Respuestas:

6

Octava, 70 66 55 bytes

Esta función Festá configurando la matriz de decodificación H, encontrando el error y corrigiendo la posición del error (si existe). Entonces está devolviendo los bits de datos correctos. La entrada es un vector de fila estándar.

@Jakube sugirió que debería utilizar Octave en lugar de Matlab donde se puede utilizar índices en las expresiones, lo que hace todo de nuevo más cortos 11 bytes:

F=@(c)xor(c,1:7==bi2de(mod(c*de2bi(1:7,3),2)))([3,5:7])

La siguiente es la solución más corta en Matlab , ya que no puede usar directamente la indexación en expresiones. (Esto también funciona en Octave, por supuesto). Pude reemplazar la suma / mod2 con xor:

f=@(c)c([3,5:7]);F=@(c)f(xor(c,1:7==bi2de(mod(c*de2bi(1:7,3),2))))

Antiguo:

f=@(c)c([3,5:7]);F=@(c)f(mod(c+(1:7==bi2de(mod(c*de2bi(1:7,3),2))),2))
falla
fuente
Gracias, pero esto no funciona, desafortunadamente solo puedes acceder a las variables de esa manera ...
error
1
No tengo instalado Matlab, solo lo utilicé http://octave-online.net/, donde funciona. Tal vez cambiar el idioma?
Jakube
Oh, ya sospechaba que la octava podría hacerlo, pero luego cambiaré el idioma, por supuesto, ¡muchas gracias!
falla
14

Piet 50x11 = 550

ingrese la descripción de la imagen aquí

el tamaño del codel es 15. No le preocupa demasiado el tamaño, pero pasó todas las pruebas.

captncraig
fuente
44
Prefiero esto dado el contexto del problema.
1
@Optimizer "codel size" es esencialmente el factor de aumento de un programa piet. Aquí, cada píxel lógico (o códec) se ha expandido a un bloque de 15x15 para facilitar la visibilidad. Eso es lo que quiero decir, no el "tamaño del código"
captura
ah ..... mi mal.
Optimizador
8

Python, 79

f=lambda x,n=0,e=3:e&~-e and f(x,n+1,(n&8)*14^(n&4)*19^(n&2)*21^n%2*105^x)or~-n

Tome la entrada y la salida como números con el bit menos significativo a la derecha.

En lugar de intentar la recuperación de errores, solo intentamos codificar cada mensaje posible nde 0 a 15 hasta que obtengamos una codificación que esté un poco lejos de lo que se proporciona. La recursión sigue incrementándose nhasta que encuentra una que funciona y la devuelve. Aunque no hay una terminación explícita, debe terminar dentro de 16 bucles.

La expresión (n&8)*14^(n&4)*19^(n&2)*21^n%2*105implementa la matriz de Hamming bit a bit.

Para verificar un solo error, revisamos el mensaje dado con uno calculado para obtenerlo e, y verificamos si es una potencia de dos (o 0) con el clásico truco de bits e&~-e==0. Pero, en realidad no podemos asignar a la variable edentro de una lambda, y nos referimos a ella dos veces en esta expresión, por lo que hacemos un truco para pasarla como un argumento opcional al siguiente paso recursivo.

xnor
fuente
7

JavaScript (ES6), 92 87 81

Función de obtener y devolver un número entero en MSB.
La implementación es sencilla siguiendo el comentario de @randomra:

  • calc p3wrong | p2wrong | p1wrong (línea 2,3,4)
  • Úselo como una máscara de bits para voltear el bit incorrecto (línea 1),
  • luego devuelve solo los bits de datos (última línea)
F=w=>(w^=128>>(
  (w^w*2^w*4^w/2)&4|
  (w/8^w^w*2^w/16)&2|
  (w/16^w/4^w^w/64)&1
))&7|w/2&8

Prueba en la consola de Frefox / FireBug

;[0b1110000,0b1100000,0b1111011,0b0110001,
0b1011011,0b0101001,0b1010000,0b0100010]
.map(x=>x.toString(2)+'->'+F(x).toString(2))

Salida

["1110000->1000", "1100000->1000", "1111011->1111", "110001->1011", "1011011->1010", "101001->1", "1010000->1000", "100010->10"]
edc65
fuente
1
Realmente me gusta su solución compacta de operación bit a bit =)
falla
4

Pitón 2, 71

f=lambda i,b=3:i&7|i/2&8if chr(i)in'\0%*3<CLUZfip'else f(i^b/2,b*2)

Varios caracteres son ASCII no imprimibles, así que aquí hay una versión con escape:

f=lambda i,b=3:i&7|i/2&8if chr(i)in'\0\x0f\x16\x19%*3<CLUZfip\x7f'else f(i^b/2,b*2)

La entrada y salida a la función se realizan como enteros.

Aprovecho el hecho de que la cantidad de mensajes válidos es solo 16 y los codifico todos. Luego trato de voltear diferentes bits hasta que obtengo uno de esos.

Feersum
fuente
3

Haskell, 152 bytes

a(p,q,d,r,e,f,g)=b$(d+e)#p+2*(d+f)#q+4*(e+f)#r where b 3=(1-d,e,f,g);b 5=(d,1-e,f,g);b 6=(d,e,1-f,g);b 7=(d,e,f,g-1);b _=(d,e,f,g);x#y=abs$(x+g)`mod`2-y

Uso: a (1,1,1,1,0,1,1)que salidas(1,1,1,1)

Solución directa: si p<x>no coincide, establezca el bit <x>en un número. Si este número es 3, 5, 6o 7, darle la vuelta al correspondiente d<y>.

nimi
fuente
¿Puedes agregar más instrucciones sobre cómo llamar a tu código (por ejemplo, usando un compilador en línea como ideone.com )? Siempre recibo algunos errores extraños (muy probablemente es mi culpa).
Jakube
@Jakube: guardar el código en un archivo, por ejemplo hamming.hs, y cargarlo en la ghci Haskell REPL: ghci hamming.hs. Llame a la función acomo se describe anteriormente. El único intérprete de haskell en línea que conozco ( tryhaskell.org ) requiere más código:let a(p,q, ... 2-y in a (1,1,1,1,0,1,1)
nimi
3

Código de máquina IA-32, 36 bytes

Hexdump:

33 c0 40 91 a8 55 7a 02 d0 e1 a8 66 7a 03 c0 e1
02 a8 78 7a 03 c1 e1 04 d0 e9 32 c1 24 74 04 04
c0 e8 03 c3

Código C equivalente:

unsigned parity(unsigned x)
{
    if (x == 0)
        return 0;
    else
        return x & 1 ^ parity(x >> 1);
}

unsigned fix(unsigned x)
{
    unsigned e1, e2, e3, err_pos, data;
    e1 = parity(x & 0x55);
    e2 = parity(x & 0x66);
    e3 = parity(x & 0x78);
    err_pos = e1 + e2 * 2 + e3 * 4;
    x ^= 1 << err_pos >> 1;
    data = x;
    data &= 0x74;
    data += 4;
    data >>= 3;
    return data;
}

La CPU x86 calcula automáticamente la paridad de cada resultado intermedio. Tiene una instrucción dedicadajp que salta o no salta dependiendo de la paridad.

No se especificó explícitamente en el desafío, pero la propiedad conveniente de los códigos hamming es que puede interpretar los bits de paridad como un número binario, y este número indica qué bit se echó a perder durante la transmisión. En realidad, este número se basa en 1, con 0, lo que significa que no hubo errores de transmisión. Esto se implementa desplazando 1 hacia la izquierda err_posy luego hacia la derecha 1.

Después de corregir el error de transmisión, el código organiza los bits de datos en el orden necesario. El código está optimizado para el tamaño, y al principio puede no estar claro cómo funciona. Para explicarlo, denotamos por a, b, c, dlos bits de datos, y por P, Qy Rlos bits de paridad. Luego:

    data = x;     // d  c  b  R  a  Q  P
    data &= 0x74; // d  c  b  0  a  0  0
    data += 4;    // d  c  b  a ~a  0  0
    data >>= 3;   // d  c  b  a

Fuente de ensamblaje (fastcall convención, con entrada ecxy salida eax):

    xor eax, eax;
    inc eax;
    xchg eax, ecx;

    test al, 0x55;
    jp skip1;
    shl cl, 1;

skip1:
    test al, 0x66;
    jp skip2;
    shl cl, 2;

skip2:
    test al, 0x78;
    jp skip3;
    shl ecx, 4;

skip3:
    shr cl, 1;
    xor al, cl;

    and al, 0x74;
    add al, 4;
    shr al, 3;

    ret;
anatolyg
fuente