Le code Hamming (7,4) remonte à 1950. À l'époque, Richard Hamming travaillait comme mathématicien aux Bell Labs. Chaque vendredi, Hamming réglait les machines à calculer pour effectuer une série de calculs et collectait les résultats le lundi suivant. Grâce à des contrôles de parité, ces machines ont pu détecter des erreurs lors du calcul. Frustré, parce qu'il recevait trop souvent des messages d'erreur, Hamming a décidé d'améliorer la détection des erreurs et a découvert les fameux codes Hamming.

Mécanique du Hamming (7,4)

Le but des codes de Hamming est de créer un ensemble de bits de parité qui se chevauchent de telle sorte qu'une erreur sur un bit (un bit est inversé) dans un bit de données ou un bit de parité puisse être détectée et corrigée. Ce n'est qu'en cas d'erreurs multiples que le code Hamming ne parvient pas à récupérer les données d'origine. Il peut ne pas remarquer du tout d'erreur, ni même le corriger faussement. Par conséquent, dans ce défi, nous ne traiterons que des erreurs mono-bit.

Comme exemple des codes de Hamming, nous examinerons le code de Hamming (7,4). En plus de 4 bits de données, d1, d2, d3, d4il utilise 3 bits de parité p1, p2, p3, qui sont calculés à l'aide des équations suivantes:

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

Le mot de code résultant (données + bits de parité) est de la forme p1 p2 d1 p3 d2 d3 d4.

La détection d'une erreur fonctionne de la manière suivante. Vous recalculez les bits de parité et vérifiez s'ils correspondent aux bits de parité reçus. Dans le tableau suivant, vous pouvez voir que chaque variété d'erreur sur un seul bit produit une correspondance différente des bits de parité. Par conséquent, chaque erreur sur un seul bit peut être localisée et corrigée.

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

Exemple

Laissez vos données être 1011. Les bits de parité sont p1 = 1 + 0 + 1 = 0, p2 = 1 + 1 + 1 = 1et p3 = 0 + 1 + 1 = 0. Combinez les données et les bits de parité et vous obtenez le mot de code 0110011.

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

Disons que lors d'une transmission ou d'un calcul le 6ème bit (= 3ème bit de données) bascule. Vous recevez le mot 0110001. Les prétendues données reçues sont 1001. On calcule à nouveau les bits de parité p1 = 1 + 0 + 1 = 0, p2 = 1 + 0 + 1 = 0, p3 = 0 + 0 + 1 = 1. Correspond uniquement p1aux bits de parité du mot de code 0110001. Une erreur s'est donc produite. En regardant le tableau ci-dessus, nous indique que l'erreur s'est produite dans d3et vous pouvez récupérer les données d'origine 1011.

Défi:

Écrivez une fonction ou un programme qui reçoit un mot (7 bits), l'un des bits peut être incorrect et récupérez les données d'origine. Le format d'entrée (via STDIN, argument de ligne de commande, invite ou fonction) peut être une chaîne "0110001", une liste ou un tableau [0, 1, 1, 0, 0, 0, 1]ou un entier dans MSB 0b0110001 = 49. Comme décrit ci-dessus, l'ordre de l'entrée est p1 p2 d1 p3 d2 d3 d4. La sortie (via la valeur de retour ou STDOUT) doit être du même format, mais dans l'ordre d1 d2 d3 d4. Renvoie / émet uniquement les 4 bits de données.

C'est du code-golf. Par conséquent, le code le plus court l'emporte.

Cas de test:

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>

Octave, 70 66 55 octets

Cette fonction Fconfigure la matrice de décodage H, recherche l'erreur et corrige la position de l'erreur (s'il y en a une). Ensuite, il renvoie les bons bits de données. L'entrée est un vecteur de ligne standard.

@Jakube a suggéré que je devrais utiliser Octave au lieu de Matlab où vous pouvez utiliser des index sur les expressions, ce qui raccourcit encore le tout de 11 octets:

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

Voici la solution la plus courte dans Matlab , car vous ne pouvez pas utiliser directement l'indexation sur les expressions. (Cela fonctionne aussi dans Octave, bien sûr.) A pu remplacer addition / mod2 par xor:

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

Vieux:

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

la taille du codel est de 15. Pas trop préoccupé par la taille, mais il a passé tous les tests.

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

Prenez l'entrée et la sortie sous forme de nombres avec le bit le moins significatif à droite.

Au lieu de tenter une récupération d'erreur, nous essayons simplement de coder tous les messages possibles nde 0 à 15 jusqu'à ce que nous obtenions un codage un peu éloigné de ce qui est donné. La récursivité continue à incrémenter njusqu'à ce qu'elle en trouve une qui fonctionne et la renvoie. Bien qu'il n'y ait pas de terminaison explicite, elle doit se terminer dans 16 boucles.

L'expression (n&8)*14^(n&4)*19^(n&2)*21^n%2*105implémente la matrice de Hamming au niveau du bit.

Pour vérifier une seule erreur, nous xor le message donné avec un calculé pour obtenir e, et vérifier si c'est une puissance de deux (ou 0) avec le bit-trick classique e&~-e==0. Mais, nous ne pouvons pas réellement assigner à la variable edans un lambda, et nous nous référons à elle deux fois dans cette expression, nous faisons donc un hack de la passer comme argument facultatif à la prochaine étape récursive.

JavaScript (ES6), 92 87 81

Fonction obtenant et renvoyant un entier dans MSB.
L'implémentation est simple suite au commentaire @randomra:

• calc p3wrong | p2wrong | p1wrong (ligne 2,3,4)
• l'utiliser comme masque de bits pour retourner le bit incorrect (ligne 1),
• puis retourne juste les bits de données (dernière ligne)

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 dans la console Frefox / FireBug

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

Production

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

Plusieurs caractères sont ASCII non imprimables alors voici une version échappée:

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)

L'entrée et la sortie de la fonction se font sous forme d'entiers.

Je profite du fait que le nombre de messages valides n'est que de 16 et je les code tous en dur. Ensuite, j'essaie de retourner différents bits jusqu'à ce que j'en reçoive un.

Haskell, 152 octets

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

Utilisation: a (1,1,1,1,0,1,1)quelles sorties(1,1,1,1)

Solution simple: si p<x>ne correspond pas, définissez le bit <x>dans un nombre. Si ce nombre est 3, 5, 6ou 7, retournez le correspondant d<y>.

Code machine IA-32, 36 octets

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

Code C équivalent:

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

Le processeur x86 calcule automatiquement la parité de chaque résultat intermédiaire. Il a une instruction dédiéejp qui saute ou non saute selon la parité.

Il n'a pas été spécifié explicitement dans le défi, mais la propriété pratique des codes de brouillage est que vous pouvez interpréter les bits de parité comme un nombre binaire, et ce nombre indique quel bit a été gâché pendant la transmission. En fait, ce nombre est basé sur 1, 0 signifiant qu'il n'y a eu aucune erreur de transmission. Ceci est implémenté en décalant 1 de gauche err_pospuis de droite 1.

Après avoir corrigé l'erreur de transmission, le code organise les bits de données dans l'ordre requis. Le code est optimisé pour la taille, et il peut ne pas être clair au début comment il fonctionne. Pour l' expliquer, je note a, b, c, dles bits de données, et par P, Qet Rles bits de parité. Alors:

    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

Source de l'assembly ( fastcallconvention, avec entrée ecxet sortie 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;