Popraw błędy za pomocą Hamminga (7,4)


19

Kod Hamminga (7,4) sięga 1950 roku. Wtedy Richard Hamming pracował jako matematyk w Bell Labs. W każdy piątek Hamming ustawiał maszyny liczące do wykonywania serii obliczeń i zbierał wyniki w następny poniedziałek. Za pomocą kontroli parzystości maszyny te były w stanie wykryć błędy podczas obliczeń. Sfrustrowany, ponieważ zbyt często otrzymywał komunikaty o błędach, Hamming postanowił poprawić wykrywanie błędów i odkrył słynne kody Hamminga.

Mechanika Hamminga (7,4)

Celem kodów Hamminga jest utworzenie zestawu bitów parzystości, które nakładają się na siebie, tak że błąd jednego bitu (jeden bit jest odwracany) w bicie danych lub bit parzystości może zostać wykryty i skorygowany. Tylko w przypadku wystąpienia wielu błędów kod Hamminga nie może odzyskać oryginalnych danych. Może w ogóle nie zauważyć błędu, a nawet poprawić go fałszywie. Dlatego w tym wyzwaniu zajmiemy się tylko błędami jednobitowymi.

Jako przykład kodów Hamminga przyjrzymy się kodowi Hamminga (7,4). Oprócz 4 bitów danych d1, d2, d3, d4wykorzystuje 3 bity parzystości p1, p2, p3, które są obliczane przy użyciu następujących równań:

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

Wynikowe słowo kodowe (dane + bity parzystości) ma postać p1 p2 d1 p3 d2 d3 d4.

Wykrywanie błędu działa w następujący sposób. Ponownie oblicz bity parzystości i sprawdź, czy pasują one do odebranych bitów parzystości. W poniższej tabeli widać, że każda odmiana błędu jednobitowego daje inne dopasowanie bitów parzystości. Dlatego każdy błąd jednobitowy można zlokalizować i poprawić.

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

Przykład

Niech twoje dane będą 1011. Bity kontroli parzystości są p1 = 1 + 0 + 1 = 0, p2 = 1 + 1 + 1 = 1i p3 = 0 + 1 + 1 = 0. Połącz dane i bity parzystości, a otrzymasz słowo kodowe 0110011.

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

Powiedzmy, że podczas transmisji lub obliczeń szósty bit (= trzeci bit danych) odwraca się. Otrzymujesz słowo 0110001. Domniemane otrzymane dane to 1001. Ponownie obliczyć bity parzystości p1 = 1 + 0 + 1 = 0, p2 = 1 + 0 + 1 = 0, p3 = 0 + 0 + 1 = 1. p1Dopasowuje tylko bity parzystości słowa kodowego 0110001. Dlatego wystąpił błąd. Patrząc na powyższą tabelę, mówi nam, że wystąpił błąd d3i możesz odzyskać oryginalne dane 1011.

Wyzwanie:

Napisz funkcję lub program, który odbiera słowo (7 bitów), jeden z bitów może być nieprawidłowy i odzyskuje oryginalne dane. Format wejściowy (przez STDIN, argument wiersza poleceń, monit lub argument funkcji) może być ciągiem "0110001", listą, tablicą [0, 1, 1, 0, 0, 0, 1]lub liczbą całkowitą w MSB 0b0110001 = 49. Jak opisano powyżej, kolejność wprowadzania jest następująca p1 p2 d1 p3 d2 d3 d4. Dane wyjściowe (poprzez wartość zwracaną lub STDOUT) muszą mieć ten sam format, ale w kolejności d1 d2 d3 d4. Zwracaj / wysyłaj tylko 4 bity danych.

To jest golf golfowy. Dlatego wygrywa najkrótszy kod.

Przypadki testowe:

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


1
Czy istnieje konkretny powód, dla którego ostatni bit parzystości jest podawany po pierwszym bicie danych?
xnor

2
@ xnor Matematycznie nie ma znaczenia, w której pozycji znajdują się bity parzystości. Historycznie są one umieszczane na pozycjach potęg dwóch. Np. Hamming (15,11) ma bity parzystości na pozycjach 1, 2, 4 i 8.
Jakube

4
@ xnor Jeśli weźmiesz [is_p3_wrong][is_p2_wrong][is_p1_wrong]pod uwagę podstawę drugą, to podaje pozycję niepoprawnego bitu w słowie. (Na podstawie tabeli w pytaniu.) Prawdopodobnie będzie to przydatne w przypadku niektórych algorytmów.
randomra

Bardzo fajnie :) Kiedy piszesz „Napisz funkcję lub program, który odbiera słowo (7 bitów), jeden z nich może być nieprawidłowy, [...]” Myślę, że masz na myśli jeden z bitów, ale możesz powiedz, że jednym ze słów może być.

@Lembik Sure, wyjaśnił to.
Jakube,

Odpowiedzi:


6

Oktawa, 70 66 55 bajtów

Ta funkcja Fkonfiguruje macierz dekodowania H, znajduje błąd i koryguje pozycję błędu (jeśli taki istnieje). Następnie zwraca odpowiednie bity danych. Dane wejściowe to standardowy wektor wiersza.

@Jakube zasugerował, że powinienem używać Octave zamiast Matlaba, w którym można używać indeksów wyrażeń, co sprawia, że ​​całość znów jest krótsza o 11 bajtów:

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

Poniżej znajduje się najkrótsze rozwiązanie w Matlabie , ponieważ nie można bezpośrednio używać indeksowania wyrażeń. (Działa to również w Octave.) Był w stanie zastąpić dodatek / mod2 xor:

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

Stary:

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

Dziękuję, ale to nie działa, niestety można uzyskać dostęp tylko do zmiennych w ten sposób ...
flawr

1
Nie zainstalowałem Matlaba, użyłem tylko http://octave-online.net/tam, gdzie to działa. Może zmienić język?
Jakube

Och, już podejrzewałem, że oktawa mogłaby to zrobić, ale potem oczywiście zmienię język, dziękuję bardzo!
flawr

14

Pie 50x11 = 550

wprowadź opis zdjęcia tutaj

rozmiar kodu to 15. Nie martwi się zbytnio rozmiarem, ale przeszedł wszystkie testy.


4
Raczej podoba mi się to, biorąc pod uwagę kontekst problemu.

1
@Optimizer „rozmiar kodu” jest zasadniczo współczynnikiem powiększenia programu piet. Tutaj każdy logiczny piksel (lub kodel) został rozszerzony do bloku 15 x 15, aby ułatwić widoczność. To właśnie mam na myśli, a nie „rozmiar kodu”
captncraig,

ah ..... mój zły.
Optymalizator

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

Weź dane wejściowe i wyjściowe jako liczby z najmniej znaczącym bitem po prawej stronie.

Zamiast próbować odzyskać błędy, po prostu próbujemy zakodować każdą możliwą wiadomość nod 0 do 15, aż otrzymamy kodowanie, które jest nieco oddalone od tego, co podano. Rekurencja rośnie, ndopóki nie znajdzie takiej, która działa i zwróci ją. Chociaż nie ma wyraźnego zakończenia, musi kończyć się w ciągu 16 pętli.

Wyrażenie (n&8)*14^(n&4)*19^(n&2)*21^n%2*105implementuje macierz Hamminga bitowo.

Aby sprawdzić pojedynczy błąd, xor lub daną wiadomość obliczamy na jeden, aby uzyskać e, i sprawdzamy, czy jest to potęga dwóch (lub 0) klasycznej sztuczki bitowej e&~-e==0. Ale tak naprawdę nie możemy przypisać zmiennej edo lambda i odwołujemy się do niej dwukrotnie w tym wyrażeniu, więc robimy włamanie do przekazania jej jako opcjonalnego argumentu do następnego rekurencyjnego kroku.


7

JavaScript (ES6), 92 87 81

Funkcja pobierania i zwracania liczby całkowitej w MSB.
Implementacja jest prosta po komentarzu @randomra:

  • calc p3wrong | p2wrong | p1wrong (linia 2,3,4)
  • użyj go jako maski bitowej, aby przerzucić niepoprawny bit (linia 1),
  • następnie zwróć tylko bity danych (ostatnia linia)
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

Przetestuj w konsoli Frefox / FireBug

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

Wynik

["1110000->1000", "1100000->1000", "1111011->1111", "110001->1011", "1011011->1010", "101001->1", "1010000->1000", "100010->10"]

1
Naprawdę podoba mi się twoje kompaktowe rozwiązanie do obsługi bitowej =)
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)

Kilka znaków to niedrukowalne znaki ASCII, więc oto wersja zmiany znaczenia:

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)

Wejścia i wyjścia do funkcji są wykonywane jako liczby całkowite.

Korzystam z faktu, że liczba prawidłowych wiadomości wynosi tylko 16, i wszystkie je koduję. Potem próbuję przerzucać różne bity, dopóki nie dostanę jednego z nich.


3

Haskell, 152 bajty

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

Zastosowanie: a (1,1,1,1,0,1,1)które wyjścia(1,1,1,1)

Proste rozwiązanie: jeśli p<x>nie pasuje, ustaw bit <x>w liczbie. Jeśli liczba ta jest 3, 5, 6lub 7, flip odpowiedni d<y>.


Czy możesz dodać więcej instrukcji na temat wywoływania kodu (na przykład za pomocą kompilatora internetowego, takiego jak ideone.com )? Zawsze dostaję jakieś dziwne błędy (najprawdopodobniej moja wina).
Jakube,

@Jakube: zapisać kod do pliku, powiedzmy hamming.hsi załadować go do ghci Haskell REPL: ghci hamming.hs. Wywołaj funkcję w asposób opisany powyżej. Jedyny znany mi internetowy interpreter haskell ( tryhaskell.org ) wymaga nieco więcej kodu:let a(p,q, ... 2-y in a (1,1,1,1,0,1,1)
nimi

3

Kod maszynowy IA-32, 36 bajtów

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

Równoważny kod C:

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;
}

Procesor x86 automatycznie oblicza parzystość każdego wyniku pośredniego. Posiada dedykowaną instrukcję, jpktóra skacze lub nie, w zależności od parzystości.

Nie zostało to wyraźnie określone w wyzwaniu, ale wygodną właściwością kodów hamujących jest to, że można interpretować bity parzystości jako liczbę binarną, a ta liczba wskazuje, który bit został zepsuty podczas transmisji. W rzeczywistości liczba ta jest oparta na 1, przy czym 0 oznacza brak błędów transmisji. Jest to realizowane przez przesunięcie 1 w lewo, err_posa następnie w prawo o 1.

Po naprawieniu błędu transmisji kod porządkuje bity danych w wymaganej kolejności. Kod jest zoptymalizowany pod kątem rozmiaru i na początku może być niejasne, jak to działa. Aby to wyjaśnić, to oznaczmy przez a, b, c, dbitów danych, a przez P, Qi Rbitów parzystości. Następnie:

    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

Źródło zestawu ( fastcallkonwencja, z wejściem ecxi wyjściem 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;
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.