Correct errors using Hamming(7,4)

Question

The Hamming(7,4) code goes back to 1950. Back then Richard Hamming worked as a mathematician at Bell Labs. Every Friday Hamming set the calculating machines to perform a series of calculation, and collected the results on the following Monday. Using parity checks, these machines were able to detect errors during the computation. Frustrated, because he received error messages way too often, Hamming decided to improve the error detection and discovered the famous Hamming codes.

Mechanics of the Hamming(7,4)

The goal of Hamming codes is to create a set of parity bits that overlap such that a single-bit error (one bit is flipped) in a data bit or a parity bit can be detected and corrected. Only if there occur multiple errors, the Hamming code fails of recovering the original data. It may not notice an error at all, or even correct it falsely. Therefore in this challenge we will only deal with single-bit errors.

As an example of the Hamming codes, we will look at the Hamming(7,4) code. Additionally to 4 bits of data d1, d2, d3, d4 it uses 3 parity bits p1, p2, p3, which are calculated using the following equations:

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

The resulting codeword (data + parity bits) is of the form p1 p2 d1 p3 d2 d3 d4.

Detecting an error works the following way. You recalculate the parity bits, and check if they match the received parity bits. In the following table you can see, that every variety of a single-bit error yields a different matching of the parity bits. Therefore every single-bit error can be localized and corrected.

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

Example

Let your data be 1011. The parity bits are p1 = 1 + 0 + 1 = 0, p2 = 1 + 1 + 1 = 1 and p3 = 0 + 1 + 1 = 0. Combine the data and the parity bits and you get the codeword 0110011.

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

Lets say during a transmission or a computation the 6th bit (= 3rd data bit) flips. You receive the word 0110001. The alleged received data is 1001. You calculate the parity bits again p1 = 1 + 0 + 1 = 0, p2 = 1 + 0 + 1 = 0, p3 = 0 + 0 + 1 = 1. Only p1 matches the parity bits of the codeword 0110001. Therefore an error occurred. Looking at the table above, tells us that the error occurred in d3 and you can recover the original data 1011.

Challenge:

Write a function or a program, that receives a word (7 bits), one of the bits might be wrong, and recover the original data. The input (via STDIN, command-line argument, prompt or function argument) format may be a string "0110001", a list or an array [0, 1, 1, 0, 0, 0, 1] or an integer in MSB 0b0110001 = 49. As described above, the order of the input is p1 p2 d1 p3 d2 d3 d4. The output (via return value or STDOUT) has to be of the same format, but in the order d1 d2 d3 d4. Only return/output the 4 data bits.

This is code-golf. Therefore the shortest code wins.

Test cases:

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>

Answer 1

Octave, 70 66 55 bytes

This function F is setting up the decoding matrix H, finding the error and correcting the position of the error (if there is one). Then it is returning the right data bits. Input is a standard row vector.

@Jakube suggested I should use Octave instead of Matlab where you can use indices on expressions, which makes the whole thing again shorter 11 bytes:

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

Following is the shortest solution in Matlab, as you cannot directly use indexing on expressions. (This works in Octave too, of course.) Was able to replace addition/mod2 with xor:

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

Old:

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

Answer 2

Piet 50x11 = 550

codel size is 15. Not too concerned about size, but it passed all the tests.

Answer 3

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

Take input and output as numbers with the least significant bit on the right.

Instead of attempting error recovery, we just try encoding every possible message n from 0 to 15 until we get an encoding that's one bit away from what's given. The recursion keeps incrementing n until it finds one that works and returns it. Though there's no explicit termination, it must end within 16 loops.

The expression (n&8)*14^(n&4)*19^(n&2)*21^n%2*105 implements the Hamming matrix bitwise.

To check for a single error, we xor the given message with a computed one to get e, and check if it's a power of two (or 0) with the classic bit-trick e&~-e==0. But, we can't actually assign to the variable e within a lambda, and we refer to it twice in this expression, so we do a hack of passing it as an optional argument to the next recursive step.

Answer 4

JavaScript (ES6), 92 87 81

Function getting and returning an integer in MSB.
The implementation is straightforwrd following @randomra comment:

• calc p3wrong|p2wrong|p1wrong (line 2,3,4)
• use it as a bit mask to flip the incorrect bit (line 1),
• then return just the data bits (last line)

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

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

Output

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

Answer 5

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)

Several characters are unprintable ASCII so here is an escaped 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)

Input and output to the function are done as integers.

I'm taking advantage of the fact that the number of valid messages is only 16, and hard-coding them all. Then I try flipping different bits until I get one of those.

Answer 6

IA-32 machine code, 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

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

x86 CPU automatically calculates the parity of each intermediate result. It has a dedicated instruction jp that jumps or not jumps depending on the parity.

It wasn't specified explicitly in the challenge, but the convenient property of hamming codes is that you can interpret the parity bits as a binary number, and this number indicates which bit was spoiled during transmission. Actually, this number is 1-based, with 0 meaning there were no transmission errors. This is implemented by shifting 1 left by err_pos and then right by 1.

After fixing the transmission error, the code arranges the data bits in the needed order. The code is optimized for size, and it may be unclear at first how it works. To explain it, I denote by a, b, c, d the data bits, and by P, Q and R the parity bits. Then:

    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 source (fastcall convention, with input in ecx, and output 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;

Answer 7

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

Usage: a (1,1,1,1,0,1,1) which outputs (1,1,1,1)

Straightforward solution: if p<x> does not match, set bit <x> in a number. If this number is 3, 5, 6 or 7, flip the corresponding d<y>.