Der Hamming-Code (7,4) stammt aus dem Jahr 1950. Damals arbeitete Richard Hamming als Mathematiker bei Bell Labs. Jeden Freitag stellte Hamming die Rechenmaschinen auf eine Reihe von Berechnungen ein und sammelte die Ergebnisse am folgenden Montag. Mithilfe von Paritätsprüfungen konnten diese Computer Fehler während der Berechnung erkennen. Frustriert, weil er viel zu oft Fehlermeldungen erhielt, beschloss Hamming, die Fehlererkennung zu verbessern, und entdeckte die berühmten Hamming-Codes.

Mechanik der Hamming (7,4)

Das Ziel von Hamming-Codes besteht darin, einen Satz von Paritätsbits zu erzeugen, die sich so überlappen, dass ein Einzelbitfehler (ein Bit wird umgedreht) in einem Datenbit oder einem Paritätsbit erkannt und korrigiert werden kann. Nur wenn mehrere Fehler auftreten, kann der Hamming-Code die ursprünglichen Daten nicht wiederherstellen. Möglicherweise wird ein Fehler überhaupt nicht bemerkt oder sogar falsch korrigiert. Daher werden wir uns in dieser Herausforderung nur mit Einzelbitfehlern befassen.

Als Beispiel für die Hamming-Codes betrachten wir den Hamming-Code (7,4). Zusätzlich zu 4 Datenbits d1, d2, d3, d4werden 3 Paritätsbits verwendet p1, p2, p3, die mit den folgenden Gleichungen berechnet werden:

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

Das resultierende Codewort (Daten + Paritätsbits) hat die Form p1 p2 d1 p3 d2 d3 d4.

Das Erkennen eines Fehlers funktioniert folgendermaßen. Sie berechnen die Paritätsbits neu und prüfen, ob sie mit den empfangenen Paritätsbits übereinstimmen. In der folgenden Tabelle können Sie sehen, dass jede Sorte eines Einzelbitfehlers eine andere Übereinstimmung der Paritätsbits ergibt. Daher kann jeder Einzelbitfehler lokalisiert und korrigiert werden.

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

Beispiel

Lassen Sie Ihre Daten sein 1011. Die Paritätsbits sind p1 = 1 + 0 + 1 = 0, p2 = 1 + 1 + 1 = 1und p3 = 0 + 1 + 1 = 0. Kombinieren Sie die Daten und die Paritätsbits und Sie erhalten das Codewort 0110011.

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

Sagen wir, während einer Übertragung oder einer Berechnung wird das 6. Bit (= 3. Datenbit) umgeschaltet. Du erhältst das Wort 0110001. Die angeblich erhaltenen Daten sind 1001. Sie berechnen die Parity - Bits wieder p1 = 1 + 0 + 1 = 0, p2 = 1 + 0 + 1 = 0, p3 = 0 + 0 + 1 = 1. p1Stimmt nur mit den Paritätsbits des Codeworts überein 0110001. Daher ist ein Fehler aufgetreten. In der obigen Tabelle sehen Sie, dass der Fehler in aufgetreten ist d3und Sie die ursprünglichen Daten wiederherstellen können 1011.

Herausforderung:

Schreiben Sie eine Funktion oder ein Programm, das ein Wort (7 Bits) empfängt, eines der Bits ist möglicherweise falsch, und stellen Sie die ursprünglichen Daten wieder her. Das Eingabeformat (über STDIN, Befehlszeilenargument, Eingabeaufforderung oder Funktionsargument) kann eine Zeichenfolge "0110001", eine Liste oder ein Array [0, 1, 1, 0, 0, 0, 1]oder eine Ganzzahl in MSB sein 0b0110001 = 49. Wie oben beschrieben ist die Reihenfolge der Eingabe p1 p2 d1 p3 d2 d3 d4. Die Ausgabe (über Rückgabewert oder STDOUT) muss dasselbe Format haben, jedoch in der Reihenfolge d1 d2 d3 d4. Nur die 4 Datenbits zurückgeben / ausgeben.

Das ist Code-Golf. Daher gewinnt der kürzeste Code.

Testfälle:

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>

Oktave, 70 66 55 Bytes

Diese Funktion Frichtet die Dekodierungsmatrix ein H, findet den Fehler und korrigiert die Position des Fehlers (falls vorhanden). Dann werden die richtigen Datenbits zurückgegeben. Die Eingabe ist ein Standardzeilenvektor.

@Jakube schlug ich Octave statt Matlab verwenden sollten , wo Sie können Indizes auf Ausdrücke verwenden, die das Ganze wieder kürzer 11 Bytes macht:

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

Das Folgende ist die kürzeste Lösung in Matlab , da Sie die Indizierung für Ausdrücke nicht direkt verwenden können. (Das funktioniert natürlich auch in Octave.) Addition / Mod2 konnte ersetzt werden durch xor:

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

Alt:

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

Piet 50x11 = 550

Die Codelgröße ist 15. Die Größe ist nicht sonderlich wichtig, aber sie hat alle Tests bestanden.

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

Nehmen Sie die Eingabe und Ausgabe als Zahlen mit dem niedrigstwertigen Bit rechts.

Anstatt eine Fehlerbehebung zu versuchen, versuchen wir einfach, jede mögliche Nachricht nvon 0 bis 15 zu codieren, bis wir eine Codierung erhalten, die ein bisschen von dem entfernt ist, was gegeben ist. Die Rekursion wird so lange inkrementiert, nbis eine funktionierende gefunden und zurückgegeben wird. Obwohl es keine explizite Kündigung gibt, muss sie innerhalb von 16 Schleifen enden.

Der Ausdruck (n&8)*14^(n&4)*19^(n&2)*21^n%2*105implementiert die Hamming-Matrix bitweise.

Um nach einem einzelnen Fehler zu suchen, wird die angegebene Nachricht mit einem berechneten Fehler ermittelt eund mit dem klassischen Bit-Trick überprüft, ob es sich um eine Zweierpotenz (oder 0) handelt e&~-e==0. Wir können der Variablen ein einem Lambda jedoch nicht wirklich etwas zuweisen , und wir verweisen in diesem Ausdruck zweimal darauf, sodass wir sie als optionales Argument an den nächsten rekursiven Schritt übergeben.

JavaScript (ES6), 92 87 81

Funktion zum Abrufen und Zurückgeben einer Ganzzahl in MSB.
Die Implementierung ist direkt nach @randomra Kommentar:

• calc p3wrong | p2wrong | p1wrong (Zeile 2,3,4)
• benutze es als Bitmaske, um das falsche Bit zu spiegeln (Zeile 1),
• dann nur die Datenbits zurückgeben (letzte Zeile)

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

Test In der Frefox / FireBug-Konsole

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

Ausgabe

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

Einige Zeichen sind nicht druckbares ASCII, daher ist hier eine maskierte Version:

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)

Die Ein- und Ausgabe der Funktion erfolgt als Ganzzahl.

Ich nutze die Tatsache, dass die Anzahl der gültigen Nachrichten nur 16 beträgt, und codiere sie alle hart. Dann versuche ich, verschiedene Teile umzudrehen, bis ich eine davon bekomme.

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

Verwendung: a (1,1,1,1,0,1,1)welche Ausgänge(1,1,1,1)

Einfache Lösung: Wenn p<x>nicht, Bit <x>in einer Zahl setzen. Wenn diese Zahl ist 3, 5, 6oder 7, Flip das entsprechende d<y>.

IA-32 Maschinencode, 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

Äquivalenter C-Code:

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

Die x86-CPU berechnet automatisch die Parität jedes Zwischenergebnisses. Es gibt eine spezielle Anweisung jp, die abhängig von der Parität springt oder nicht springt.

Es wurde in der Abfrage nicht explizit angegeben, aber die praktische Eigenschaft von Hamming-Codes besteht darin, dass Sie die Paritätsbits als Binärzahl interpretieren können. Diese Zahl gibt an, welches Bit während der Übertragung fehlerhaft war. Tatsächlich basiert diese Zahl auf 1, wobei 0 bedeutet, dass keine Übertragungsfehler aufgetreten sind. Dies wird durch Verschieben von 1 nach links err_posund dann nach rechts umgesetzt 1.

Nach dem Beheben des Übertragungsfehlers ordnet der Code die Datenbits in der erforderlichen Reihenfolge an. Der Code ist für die Größe optimiert und es kann zunächst unklar sein, wie er funktioniert. Um zu erklären, ich bezeichne a, b, c, ddie Datenbits und durch P, Qund Rdie Parity - Bits. Dann:

    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

Assembly-Quelle ( fastcallKonvention, mit Eingabe in ecxund Ausgabe in 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;