Corrija erros usando o Hamming (7,4)

19

O código de Hamming (7,4) remonta a 1950. Na época, Richard Hamming trabalhava como matemático no Bell Labs. Toda sexta-feira, Hamming preparava as máquinas de calcular para realizar uma série de cálculos e coletava os resultados na segunda-feira seguinte. Usando verificações de paridade, essas máquinas foram capazes de detectar erros durante o cálculo. Frustrado, porque ele recebia mensagens de erro com muita frequência, Hamming decidiu melhorar a detecção de erros e descobriu os famosos códigos de Hamming.

Mecânica do Hamming (7,4)

O objetivo dos códigos Hamming é criar um conjunto de bits de paridade que se sobreponham, de modo que um erro de bit único (um bit seja invertido) em um bit de dados ou um bit de paridade possa ser detectado e corrigido. Somente se ocorrerem vários erros, o código Hamming falhará na recuperação dos dados originais. Pode não notar um erro, ou mesmo corrigi-lo falsamente. Portanto, neste desafio, lidaremos apenas com erros de bit único.

Como um exemplo dos códigos de Hamming, veremos o código de Hamming (7,4). Além de 4 bits de dados, d1, d2, d3, d4ele usa 3 bits de paridade p1, p2, p3, calculados usando as seguintes equações:

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

A palavra de código resultante (dados + bits de paridade) é da forma p1 p2 d1 p3 d2 d3 d4.

A detecção de um erro funciona da seguinte maneira. Você recalcula os bits de paridade e verifica se eles correspondem aos bits de paridade recebidos. Na tabela a seguir, você pode ver que toda variedade de erro de um bit gera uma correspondência diferente dos bits de paridade. Portanto, todo erro de bit único pode ser localizado e corrigido.

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

Exemplo

Deixe seus dados estarem 1011. Os bits de paridade são p1 = 1 + 0 + 1 = 0, p2 = 1 + 1 + 1 = 1e p3 = 0 + 1 + 1 = 0. Combine os dados e os bits de paridade e você obterá a palavra de código 0110011.

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

Digamos que durante uma transmissão ou um cálculo o sexto bit (= terceiro bit de dados) vire. Você recebe a palavra 0110001. Os supostos dados recebidos são 1001. Você calcula os bits de paridade de novo p1 = 1 + 0 + 1 = 0, p2 = 1 + 0 + 1 = 0, p3 = 0 + 0 + 1 = 1. p1Corresponde apenas aos bits de paridade da palavra de código 0110001. Portanto, ocorreu um erro. Observando a tabela acima, informamos que ocorreu o erro d3e você pode recuperar os dados originais 1011.

Desafio:

Escreva uma função ou programa que receba uma palavra (7 bits), um dos bits pode estar errado e recupere os dados originais. O formato de entrada (via STDIN, argumento de linha de comando, argumento de prompt ou função) pode ser uma sequência de caracteres "0110001", uma lista ou uma matriz [0, 1, 1, 0, 0, 0, 1]ou um número inteiro no MSB 0b0110001 = 49. Como descrito acima, a ordem da entrada é p1 p2 d1 p3 d2 d3 d4. A saída (via valor de retorno ou STDOUT) deve ser do mesmo formato, mas na ordem d1 d2 d3 d4. Somente retorne / produza os 4 bits de dados.

Isso é código-golfe. Portanto, o código mais curto vence.

Casos de teste:

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 snippet de código

code-golf error-correction coding-theory Jakube
fonte
11
Existe uma razão específica para o último bit de paridade ser dado após o primeiro bit de dados?
xnor
2
@xnor Matematicamente, não faz diferença, em que posição estão os bits de paridade. Historicamente, eles são colocados nas posições de poderes de dois. Por exemplo, o Hamming (15,11) tem os bits de paridade nas posições 1, 2, 4 e 8. #
Jakube 13/02/15
4
@xnor Se você usar a [is_p3_wrong][is_p2_wrong][is_p1_wrong]base dois, indica a posição do bit incorreto na palavra. (Com base na tabela da pergunta.) Isso provavelmente será útil para alguns algoritmos.
Aleatório
Muito bom :) Quando você escreve "Escreva uma função ou programa, que recebe uma palavra (7 bits), um deles pode estar errado, [...]" Acho que você quer dizer que um dos bits pode estar errado, mas você na verdade, diga que uma das palavras pode ser.
@Lembik Claro, esclareceu.
Jakube

Respostas:

6

Oitava, 70 66 55 bytes

Esta função Festá configurando a matriz de decodificação H, localizando o erro e corrigindo a posição do erro (se houver). Em seguida, ele retorna os bits de dados corretos. Entrada é um vetor de linha padrão.

@Jakube sugeriu que eu deveria usar o Octave em vez do Matlab, onde você pode usar índices em expressões, o que torna a coisa toda novamente mais curta: 11 bytes:

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

A seguir, é a solução mais curta no Matlab , pois você não pode usar diretamente a indexação em expressões. (Isso funciona no Octave também, é claro.) Foi capaz de substituir a adição / mod2 por xor:

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

Velho:

f=@(c)c([3,5:7]);F=@(c)f(mod(c+(1:7==bi2de(mod(c*de2bi(1:7,3),2))),2))
flawr
fonte
Obrigado, mas isso não funciona, infelizmente, você pode apenas variáveis de acesso dessa forma ...
flawr
11
O Matlab não está instalado, eu só usei http://octave-online.net/, onde funciona. Talvez mude o idioma?
Jakube 16/02
Ah, eu já suspeitava que a oitava pudesse fazê-lo, mas depois vou mudar o idioma, é claro, muito obrigado!
flawr
14

Piet 50x11 = 550

insira a descrição da imagem aqui

o tamanho do codel é 15. Não está muito preocupado com o tamanho, mas passou em todos os testes.

captncraig
fonte
4
Eu gosto disso, considerando o contexto do problema.
11
@Optimizer "codel size" é essencialmente o fator de ampliação de um programa de piet. Aqui, cada pixel lógico (ou codel) foi expandido para um bloco de 15x15 para facilitar a visibilidade. Isso é o que eu quero dizer, não "tamanho do código"
captncraig
ah ..... meu mal.
Optimizer
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 entrada e saída como números com o bit menos significativo à direita.

Em vez de tentar a recuperação de erros, apenas tentamos codificar todas as mensagens possíveis nde 0 a 15 até obter uma codificação um pouco distante do que é fornecido. A recursão continua aumentandon até encontrar uma que funcione e a retorne. Embora não exista terminação explícita, ela deve terminar em 16 loops.

A expressão (n&8)*14^(n&4)*19^(n&2)*21^n%2*105 implementa a matriz de Hamming bit a bit.

Para verificar um único erro, xoramos a mensagem fornecida com uma computada para obter ee verificamos se é uma potência de dois (ou 0) com o truque de bits clássico e&~-e==0. Mas, na verdade, não podemos atribuir à variável edentro de um lambda, e nos referimos a ela duas vezes nesta expressão; portanto, tentamos transmiti-la como um argumento opcional para a próxima etapa recursiva.

xnor
fonte
7

JavaScript (ES6), 92 87 81

Função obtendo e retornando um número inteiro no MSB.
A implementação é direta após o comentário do @randomra:

  • calc p3wrong | p2wrong | p1wrong (linha 2,3,4)
  • use-o como uma máscara de bit para inverter o bit incorreto (linha 1),
  • então retorne apenas os bits de dados (última linha)
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

Teste no console do Frefox / FireBug

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

Resultado

["1110000->1000", "1100000->1000", "1111011->1111", "110001->1011", "1011011->1010", "101001->1", "1010000->1000", "100010->10"]
edc65
fonte
11
Eu realmente gosto de sua solução compacta operação bit a bit =)
flawr
4

Python 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)

Vários caracteres são ASCII não imprimíveis, então aqui está uma versão de 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)

A entrada e saída da função são feitas como números inteiros.

Estou aproveitando o fato de que o número de mensagens válidas é de apenas 16 e codificando todas elas. Então tento inverter diferentes bits até obter um desses.

feersum
fonte
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)quais saídas(1,1,1,1)

Solução simples: se p<x>não corresponder, defina o bit <x>em um número. Se este número é 3, 5, 6ou 7, virar o correspondente d<y>.

nimi
fonte
Você pode adicionar mais instruções sobre como chamar seu código (por exemplo, usando um compilador online como ideone.com )? Eu sempre recebo alguns erros estranhos (muito provavelmente minha culpa).
Jakube
@Jakube: salvar o código em um arquivo, digamos, hamming.hse carregá-lo no ghci Haskell REPL: ghci hamming.hs. Chame a função acomo descrito acima. O Haskell apenas online intérprete eu sei de ( tryhaskell.org ) requer um pouco mais de 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;
}

A CPU x86 calcula automaticamente a paridade de cada resultado intermediário. Tem uma instrução dedicadajp que salta ou não, dependendo da paridade.

Não foi especificado explicitamente no desafio, mas a propriedade conveniente dos códigos hamming é que você pode interpretar os bits de paridade como um número binário, e esse número indica qual bit foi estragado durante a transmissão. Na verdade, esse número é baseado em 1, com 0 significando que não houve erros de transmissão. Isso é implementado deslocando 1 para a esquerda err_pose depois para a direita 1.

Após corrigir o erro de transmissão, o código organiza os bits de dados na ordem necessária. O código é otimizado para o tamanho e pode não estar claro a princípio como ele funciona. Para explicar isso, eu por denotar a, b, c, dos bits de dados, e por P, Qe Ros bits de paridade. Então:

    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

Origem da montagem ( fastcallconvenção, com entrada ecxe saída 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
fonte