19

2

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&]*(?:<(?:s>[^&]*<\/s>|[^&]+>)[^\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>`

1Is there a particular reason the last parity bit is given after the first data bit? – xnor – 2015-02-13T20:36:21.687

2@xnor Mathematically it doesn't make any difference, at which position the parity bits are. Historically they are placed on the positions of powers of two. E.g. the Hamming(15,11) has the parity bits at the positions 1, 2, 4 and 8. – Jakube – 2015-02-13T20:41:17.060

4@xnor If you take

`[is_p3_wrong][is_p2_wrong][is_p1_wrong]`

in base two it gives the position of the incorrect bit in the word. (Based on the table in the question.) This probably will be useful for some algorithms. – randomra – 2015-02-13T21:27:35.267Very nice :) When you write "Write a function or a program, that receives a word (7 bits), one of them might be wrong,[...]" I think you mean one of the bits might be wrong but you actually say one of the words might be. – None – 2015-02-13T21:47:21.237

@Lembik Sure, clarified it. – Jakube – 2015-02-13T21:49:55.347

Added the leaderboard snippet, I hope this is ok! – flawr – 2015-02-16T22:02:38.037

@flawr Sure, thanks. – Jakube – 2015-02-16T22:59:23.840