Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Код хэмминга

Автор: chipset 7.4.2005, 21:49

Код хэмминга предназначен для исправления ошибок разрядностью N и исправлению ошибок разрядностью N+1.

Пусть количество сообщений, которые мы хотим передавать равняется 16. Для безызбыточного кодирования сообщений достаточно 4 двоичных разрядов. Для обнаружения и исправления одиночной ошибки мы можем добавить 8 дополнительных разрядов к передаваемому слову (передавая сообщение трижды), что, однако не такой способ кодирования не является эффективным.

Код хэмминга предлагает добавление всего 4 дополнительных разрядов к кодируемому слову. Итак, пусть сообщение записано 4 разрядами a1,a2,a3,a4. Добавим к нему три дополнительных вычисляемых разряда:
a5=a2 ^ a3 ^ a4
a6=a1 ^ a3 ^ a4
a6=a1 ^ a2 ^ a4
Для проверки наличия ошибки при передаче слова a1a2a3a4a5a6a7 при передаче символов a4,a5,a6,a7 следует получить сумму
s1=a4 ^ a5 ^ a6 ^ a7
Если данная сумма равна 1, то ошибка была допущена. В случае "да" проверим не допущена ли ошибка в символах a6, a7, в случае нет - в символах a2, a3. В обоих случаях ответ дает следующая сумма:
s2=a2 ^ a3 ^ a6 ^ a7
Ниже приведена таблица диагностики ситуации, исходя из значений сумм s1 и s2.

s1  s2
0   0   нет ошибки или a1
0   1   a2 или a3
1   0   a4 или a5
1   1   a6 или a7

В каждом из этих случаев осталось выбрать только один вариант. Это можно сделать при помощи вычисления суммы:
s3=a1 ^ a3 ^ a5 ^ a7
Таким образом мы имеем 3 проверочных отношения:
s1=a4 ^ a5 ^ a6 ^ a7
s2=a2 ^ a3 ^ a6 ^ a7
s3=a1 ^ a3 ^ a5 ^ a7
которые позволяет убедится в наличии ошибки и точно указать ее место, причем в случае возникнования одиночной ошибки двоичное число s1s2s3 указывает разряд в котором произошла ошибка. Для обнаружения двойной ошибки следует только добавить еще один проверочный разряд a0 и условие, указывающее на наличие двойной ошибки:
s0=a0 ^ a1 ^ a2 ^ a3 ^ a4 ^ a5 ^ a6 ^ a7

Код


typedef unsigned char byte;
typedef unsigned short word;
byte getbit(byte v,int nbit)
{
       if (nbit) v>>=nbit;
       v&=1;
       return v;
}
byte setbit(byte v, int nbit, byte b)
{
       if (nbit) b<<=nbit;
       v|=b;
       return v;
}
byte half_make_hamming(byte v)
{
       byte    h;
       h=v&0xf;
       h=setbit(h,4,getbit(v,1)^getbit(v,2)^getbit(v,3));
       h=setbit(h,5,getbit(v,0)^getbit(v,2)^getbit(v,3));
       h=setbit(h,6,getbit(v,0)^getbit(v,1)^getbit(v,3));
       h=setbit(h,7,getbit(v,0)^getbit(v,1)^getbit(v,2)^getbit(v,3)^getbit(h,4)^getbit(h,5)^getbit(h,6));
       return h;
}
byte half_check_hamming(byte v)
{
       byte    s1,s2,s3,s4;
       byte    pos;
       s1=getbit(v,3)^getbit(v,4)^getbit(v,5)^getbit(v,6);
       s2=getbit(v,1)^getbit(v,2)^getbit(v,5)^getbit(v,6);
       s3=getbit(v,0)^getbit(v,2)^getbit(v,4)^getbit(v,6);
       s4=getbit(v,0)^getbit(v,1)^getbit(v,2)^getbit(v,3)^getbit(v,4)^getbit(v,5)^getbit(v,6)^getbit(v,7);
       pos=(s1<<2)|(s2<<1)|(s3);
       if ((s4==0)&&(pos!=0)) pos=0xff;
       else
       {
               if (pos)
               {
                       pos--;
                       if (pos) pos=1<<pos;
                           else pos=1;
               }
       }
       return pos;
}