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

function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){$.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(e){answers.push.apply(answers,e.items);if(e.has_more)getAnswers();else process()}})}function shouldHaveHeading(e){var t=false;var n=e.body_markdown.split("\n");try{t|=/^#/.test(e.body_markdown);t|=["-","="].indexOf(n[1][0])>-1;t&=LANGUAGE_REG.test(e.body_markdown)}catch(r){}return t}function shouldHaveScore(e){var t=false;try{t|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(n){}return t}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading);answers.sort(function(e,t){var n=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0],r=+(t.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0];return n-r});var e={};var t=0,c=0,p=-1;answers.forEach(function(n){var r=n.body_markdown.split("\n")[0];var i=$("#answer-template").html();var s=r.match(NUMBER_REG)[0];var o=(r.match(SIZE_REG)||[0])[0];var u=r.match(LANGUAGE_REG)[1];var a=getAuthorName(n);t++;c=p==o?c:t;i=i.replace("{{PLACE}}",c+".").replace("{{NAME}}",a).replace("{{LANGUAGE}}",u).replace("{{SIZE}}",o).replace("{{LINK}}",n.share_link);i=$(i);p=o;$("#answers").append(i);e[u]=e[u]||{lang:u,user:a,size:o,link:n.share_link}});var n=[];for(var r in e)if(e.hasOwnProperty(r))n.push(e[r]);n.sort(function(e,t){if(e.lang>t.lang)return 1;if(e.lang<t.lang)return-1;return 0});for(var i=0;i<n.length;++i){var s=$("#language-template").html();var r=n[i];s=s.replace("{{LANGUAGE}}",r.lang).replace("{{NAME}}",r.user).replace("{{SIZE}}",r.size).replace("{{LINK}}",r.link);s=$(s);$("#languages").append(s)}}var QUESTION_ID=45684;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:&lt;(?:s&gt;[^&]*&lt;\/s&gt;|[^&]+&gt;)[^\d&]*)*$)/;var NUMBER_REG=/\d+/;var LANGUAGE_REG=/^#*\s*([^,]+)/

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src=https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js></script><link rel=stylesheet type=text/css href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><div id=answer-list><h2>Leaderboard</h2><table class=answer-list><thead><tr><td></td><td>Author<td>Language<td>Size<tbody id=answers></table></div><div id=language-list><h2>Winners by Language</h2><table class=language-list><thead><tr><td>Language<td>User<td>Score<tbody id=languages></table></div><table style=display:none><tbody id=answer-template><tr><td>{{PLACE}}</td><td>{{NAME}}<td>{{LANGUAGE}}<td>{{SIZE}}<td><a href={{LINK}}>Link</a></table><table style=display:none><tbody id=language-template><tr><td>{{LANGUAGE}}<td>{{NAME}}<td>{{SIZE}}<td><a href={{LINK}}>Link</a></table>

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

Pie 50x11 = 550

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

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.

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"]

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.

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>.

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;