Код Хэмминга (7,4) восходит к 1950 году. В то время Ричард Хэмминг работал математиком в Bell Labs. Каждую пятницу Хэмминг настраивал вычислительные машины на выполнение серии расчетов и собирал результаты в следующий понедельник. Используя проверки на четность, эти машины смогли обнаружить ошибки во время вычислений. Разочарованный, потому что он получал сообщения об ошибках слишком часто, Хэмминг решил улучшить обнаружение ошибок и обнаружил известные коды Хемминга.

Механика Хэмминга (7,4)

Цель кодов Хэмминга состоит в том, чтобы создать набор битов четности, которые перекрываются так, что однобитовая ошибка (один бит переворачивается) в бите данных или бит четности может быть обнаружена и исправлена. Только в случае множественных ошибок код Хэмминга не может восстановить исходные данные. Он может вообще не заметить ошибку или даже исправить ее неверно. Поэтому в этой задаче мы будем иметь дело только с однобитовыми ошибками.

В качестве примера кодов Хэмминга мы рассмотрим код Хемминга (7,4). В дополнение к 4 битам данных d1, d2, d3, d4используются 3 бита четности p1, p2, p3, которые рассчитываются с использованием следующих уравнений:

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

Результирующее кодовое слово (данные + биты четности) имеет вид p1 p2 d1 p3 d2 d3 d4.

Обнаружение ошибки работает следующим образом. Вы пересчитываете биты четности и проверяете, соответствуют ли они принятым битам четности. В следующей таблице вы можете видеть, что каждое разнообразие однобитовой ошибки приводит к различному соответствию битов четности. Следовательно, каждая однобитовая ошибка может быть локализована и исправлена.

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

пример

Пусть ваши данные будут 1011. Биты четности есть p1 = 1 + 0 + 1 = 0, p2 = 1 + 1 + 1 = 1и p3 = 0 + 1 + 1 = 0. Объедините данные и биты четности, и вы получите кодовое слово 0110011.

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

Скажем, во время передачи или вычисления 6-й бит (= 3-й бит данных) переворачивается. Вы получаете слово 0110001. Предполагаемые полученные данные есть 1001. Вы снова вычислить биты четности p1 = 1 + 0 + 1 = 0, p2 = 1 + 0 + 1 = 0, p3 = 0 + 0 + 1 = 1. Соответствует только p1битам четности кодового слова 0110001. Поэтому произошла ошибка. Глядя на таблицу выше, говорит нам, что произошла ошибка, d3и вы можете восстановить исходные данные 1011.

Вызов:

Напишите функцию или программу, которая получает слово (7 бит), один из битов может быть неправильным, и восстановите исходные данные. Формат ввода (через STDIN, аргумент командной строки, приглашение или аргумент функции) может быть строкой "0110001", списком или массивом [0, 1, 1, 0, 0, 0, 1]или целым числом в MSB 0b0110001 = 49. Как описано выше, порядок ввода такой p1 p2 d1 p3 d2 d3 d4. Вывод (через возвращаемое значение или STDOUT) должен быть в том же формате, но в порядке d1 d2 d3 d4. Вернуть / вывести только 4 бита данных.

Это код-гольф. Поэтому самый короткий код выигрывает.

Тестовые случаи:

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>

Октава, 70 66 55 байт

Эта функция Fустанавливает матрицу декодирования H, находит ошибку и корректирует ее положение (если оно есть). Затем он возвращает правильные биты данных. Ввод является стандартным вектором строки.

@Jakube предложил мне использовать Octave вместо Matlab, где вы можете использовать индексы для выражений, что снова делает все это короче 11 байтов:

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

Ниже приводится самое короткое решение в Matlab , так как вы не можете напрямую использовать индексирование для выражений. (Это работает и в Octave, конечно.) Был в состоянии заменить дополнение / mod2 на xor:

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

Старый:

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

Пит 50х11 = 550

Размер кода равен 15. Не слишком обеспокоен размером, но он прошел все тесты.

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

Возьмите ввод и вывод как числа с младшим значащим битом справа.

Вместо того, чтобы пытаться исправить ошибки, мы просто пытаемся кодировать каждое возможное сообщение nот 0 до 15, пока не получим кодировку, которая находится на расстоянии одного бита от того, что дано. Рекурсия продолжает увеличиваться, nпока не найдет тот, который работает, и не вернет его. Хотя явного завершения нет, оно должно заканчиваться в 16 циклах.

Выражение (n&8)*14^(n&4)*19^(n&2)*21^n%2*105реализует битовую матрицу Хемминга.

Чтобы проверить наличие одной ошибки, мы зашифровываем данное сообщение с вычисленным значением eи проверяем, является ли оно степенью двойки (или 0) с помощью классического бит-трюка e&~-e==0. Но на самом деле мы не можем присвоить переменную eв лямбде, и мы ссылаемся на нее дважды в этом выражении, поэтому мы делаем хак, передавая ее в качестве необязательного аргумента следующему рекурсивному шагу.

JavaScript (ES6), 92 87 81

Функция получает и возвращает целое число в MSB.
Реализация проста после комментария @randomra:

• calc p3wrong | p2wrong | p1wrong (строка 2,3,4)
• используйте его как битовую маску, чтобы перевернуть неправильный бит (строка 1),
• затем вернуть только биты данных (последняя строка)

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

Тест в консоли Frefox / FireBug

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

Выход

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

Несколько символов являются непечатаемыми ASCII, поэтому здесь есть экранированная версия:

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)

Вход и выход в функцию выполняются как целые числа.

Я пользуюсь тем фактом, что количество действительных сообщений составляет всего 16, и жестко их всех кодирую. Затем я пытаюсь переворачивать разные биты, пока не получу один из них.

Haskell, 152 байта

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

Использование: a (1,1,1,1,0,1,1)какие выводы(1,1,1,1)

Простое решение: если p<x>не совпадает, установите бит <x>в число. Если это число 3, 5, 6или 7, флип соответствующий d<y>.

Машинный код IA-32, 36 байтов

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

Эквивалентный код 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;
}

Процессор x86 автоматически вычисляет четность каждого промежуточного результата. Он имеет специальную инструкцию, jpкоторая прыгает или не прыгает в зависимости от четности.

Это не было указано явно в вызове, но удобное свойство кодов Хэмминга заключается в том, что вы можете интерпретировать биты четности как двоичное число, и это число указывает, какой бит был испорчен во время передачи. На самом деле это число основано на 1, причем 0 означает, что ошибок передачи не было. Это реализуется путем смещения 1 влево, err_posа затем вправо 1.

После исправления ошибки передачи код размещает биты данных в нужном порядке. Код оптимизирован по размеру, и поначалу может быть неясно, как он работает. Чтобы объяснить это, я обозначу через a, b, c, dбиты данных, и P, Qи Rбиты четности. Потом:

    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

Источник сборки (fastcall соглашение, с входом ecxи выходом 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;