давно
Старший Модератор
312929
1973
15.02.2019, 14:44
общий
это ответ
Здравствуйте, sanik9394!
В коде Хэмминга чередуются контрольные и информационные биты, причём контрольные биты находятся во всех позициях с номерами, равными степени двойки, то есть в позициях 1, 2, 4, 8, 16 и т.д. Запишем наше сообщение в виде таблицы:
[table]
[row][col]И11[/col][col]И10[/col][col]И9[/col][col]К8[/col][col]И7[/col][col]И6[/col][col]И5[/col][col]К4[/col][col]И3[/col][col]К2[/col][col]К1[/col][/row]
[row][col]1[/col][col]0[/col][col]0[/col][col]1[/col][col]0[/col][col]1[/col][col]1[/col][col]1[/col][col]1[/col][col]0[/col][col]1[/col][/row]
[/table]
Здесь контрольные биты обозначены буквой К, а остальные - буквой И.
Для каждого контрольного бита с номером 2[sup]n-1[/sup], n=1,2,3,... подсчитывается контрольная сумма по следующему правилу: суммируются n битов, начиная с контрольного, потом n битов пропускаются, снова добавляются n битов и т.д. до конца сообщения (сложение ведётся по модулю 2). При отсутствии ошибок все суммы должны равняться нулю. Это выглядит так:
для бита К[sub]1[/sub]: К[sub]1[/sub]+И[sub]3[/sub]+И[sub]5[/sub]+И[sub]7[/sub]+И[sub]9[/sub]+И[sub]11[/sub]+И[sub]13[/sub]+И[sub]15[/sub]+...=0;
для бита К[sub]2[/sub]: (К[sub]2[/sub]+И[sub]3[/sub])+(И[sub]6[/sub]+И[sub]7[/sub])+(И[sub]10[/sub]+И[sub]11[/sub])+(И[sub]14[/sub]+И[sub]15[/sub])+...=0;
для бита К[sub]4[/sub]: (К[sub]4[/sub]+И[sub]5[/sub]+И[sub]6[/sub]+И[sub]7[/sub])+(И[sub]12[/sub]+И[sub]13[/sub]+И[sub]14[/sub]+И[sub]15[/sub])+...=0;
для бита К[sub]8[/sub]: (К[sub]8[/sub]+И[sub]9[/sub]+И[sub]10[/sub]+И[sub]11[/sub]+И[sub]12[/sub]+И[sub]13[/sub]+И[sub]14[/sub]+И[sub]15[/sub])+(И[sub]16[/sub]+И[sub]17[/sub]+И[sub]18[/sub]+И[sub]19[/sub]+И[sub]20[/sub]+И[sub]21[/sub]+И[sub]22[/sub]+И[sub]23[/sub])+...=0
и т.д (скобками выделены группы подряд идущих битов, участвующих в сложении). Можно заметить, что каждый информационный бит входит лишь в некоторые из этих сумм, причём его номер равен сумме номеров соответствующих контрольных битов (например, бит И[sub]3[/sub] входит в контрольные суммы для К[sub]1[/sub] и К[sub]2[/sub], бит И[sub]13[/sub] - в контрольные суммы для К[sub]1[/sub], К[sub]4[/sub] и К[sub]8[/sub] и т.д.). Следовательно, при однократной ошибке в каком-то из битов содержащие его контрольные суммы станут равными единице, а остальные останутся нулевыми, что позволит однозначно определить ошибочный бит.
В данном случае имеем:
К[sub]1[/sub]+И[sub]3[/sub]+И[sub]5[/sub]+И[sub]7[/sub]+И[sub]9[/sub]+И[sub]11[/sub]=1+1+1+0+0+1=0;
К[sub]2[/sub]+И[sub]3[/sub]+И[sub]6[/sub]+И[sub]7[/sub]+И[sub]10[/sub]+И[sub]11[/sub]=0+1+1+0+0+1=1;
К[sub]4[/sub]+И[sub]5[/sub]+И[sub]6[/sub]+И[sub]7[/sub]=1+1+1+0=1;
К[sub]8[/sub]+И[sub]9[/sub]+И[sub]10[/sub]+И[sub]11[/sub]=1+0+0+1=0.
то есть контрольные суммы верны для битов К[sub]1[/sub] и К[sub]8[/sub] и ошибочны для К[sub]2[/sub] и К[sub]4[/sub]. Следовательно, ошибочным является бит И[sub]6[/sub]=1 (6=2+4) и его правильное значение - И[sub]6[/sub]=0. С учётом исправления переданный код Хэмминга примет вид:
[table]
[row][col]И11[/col][col]И10[/col][col]И9[/col][col]К8[/col][col]И7[/col][col]И6[/col][col]И5[/col][col]К4[/col][col]И3[/col][col]К2[/col][col]К1[/col][/row]
[row][col]1[/col][col]0[/col][col]0[/col][col]1[/col][col]0[/col][col]0[/col][col]1[/col][col]1[/col][col]1[/col][col]0[/col][col]1[/col][/row]
[/table]
Отбрасывая контрольные биты, получаем число 1000011[sub]2[/sub] = 67[sub]10[/sub].