Код Хэмминга с примером

Введение

Широкое применение в двоичной системе исчисления получил так называемые коды Хэмминга. Необходимость их использования обусловлена тем, что коды с использованием системы Хэмминга способны осуществлять функцию самоконтроля и саморректировки. Коды, предложенные автором методики, ориентированы на использование в двоичной системе исчисления. В основе использования системы кодов заложен определенный алгоритм, с ним можно закодировать какую-либо информацию, передать ее через сети передачи данных и даже получить сведения об ошибке, возникшей в информационном сообщении. С использованием алгоритма можно не только получать информацию об ошибках при передаче информационных сообщений, но и восстанавливать переданные сведения, которые, к примеру, могли быть искажены из-за помех в сети передачи данных.

Код Хэмминга с примером


Чаще всего при передаче коротких сообщений используется упрощенная версия алгоритма Хэмминга с возможностью автоматического обнаружения и корректирования лишь одной ошибки в пересланном информационном сообщении.
В зависимости от конкретного случая, могут использоваться другие модификации предложенной системы с кодами самоконтроля и самокорректировки. Преимущество использования более совершенных методик заключается в том, что с ними можно автоматически обнаружить и исправить сразу несколько ошибок в пересланном информационном сообщении. В рамках использования системы кодирования Хэмминга выполняется две основных операции — это кодирование пересылаемой информации и ее раскодировка. Первый этап кодирования информационных данных осуществляется путем вставки в исходное сообщение так называемых контрольных битов. Для их исчисления используется специальная формула, на втором этапе входящее сообщение доставляется к пользователю, остается только повторно вычислить контрольные биты. Здесь используется тот же алгоритм, что и в первой части вычислений. При совпадении первичных контрольных кодов и кодов, полученных при открытии сообщения, можно говорить о том, что информационные данные дошли до пользования без каких-либо искажений.
Если же на этапе передачи информации возникает ошибка, то до отправителя доходит сообщение о возникшем конфликте

. При предусмотренной возможности автоматической корректировки ошибка в информационном сообщение устраняется. Приведем конкретный пример из практики кодирования информационных данных. Пусть это будет слово, представленное в двоичной системе исчисления в виде 1001 0001 1101 1110 0000 000. Для выполнения данной операции мы изначально подсчитываем количество символов (число m, в данном случае оно равняется 23). Далее в примере мы берем 5 контрольных кодов (число k, равное 5). На выходе с учетом взятых 5 дополнительных разрядов мы получаем сообщение с количеством символов, равным 28 (число n). Тогда закодированное сообщение можно представить в виде b28 b27 b26 b25 b24 b23 b22 b21 b20 b19 b18 b17 b16 b15 b14 b13 b12 b11 b10 b9 b8 b7 b6 b5 b4 b3 b2 b1. С учетом того, что мы взяли 5 контрольных кодов, в качестве контрольных разрядов можно обозначить b1 b2 b4 b8 b16. Все остальные разряды в этом примере будут информационными.
Далее перед нами появляется задача размещения в оставшиеся информационные разряды разрядов исходного числа в рамках передаваемого сообщения. С учетом их следования по порядку получается, что b3=1 b5=0 b7=1 b9=0 b10=0 b11=0 b12=1 b13=1 b14=1 b15=0 b17=1 b18=1 b19=1 b20=1 b21=0 b22=0 b23=0 b24=0 b25=0 b26=0 b27=0 b28=0. На следующем шаге нам следует обратиться к контрольным разрядам и поиску их значений. Чтобы нам было удобно, воспользуемся несколькими множествами. Допустим, V1=1, 3, 5, 7, 9 и т. д. до 27 - все числа с первым разрядом, равным 1. Во втором множестве V2=2, 3, 6, 7, 10 и т. д. до 27 - все числа со вторым разрядом, равным 1. В третьем множестве V3=4, 5, 6, 7, 12 и т. д. до 28 - все числа с третьим разрядом, равным 1. В четвертом множестве V4=8, 9, 10, 11, 12 и т. д. до 28 - все числа с четвертым разрядом, равным 1. В пятом множестве V5=16, 17, 18, 19, 20 и т. д. до 28 - все числа с пятым разрядом, равным 1.
Далее с использованием второго модуля и информационных разрядов у нас получится, что b1=b3+b5+b7+b9+b11+b13+b15+b17+b19+b21+b23+b25+b27=1 (все разряды из множества V1 за исключением первого); b2=b3+b6+b7+b10+b11+b14+b15+b18+b19+b22+b23+b26+b27=1 (все разряды из множества V2 за исключением первого); b4=b5+b6+b7+b12+b13+b14+b15+b20+b21+b22+b23+b28=1 (все разряды из множества V3 за исключением первого); b8=b9+b10+b11+b12+b13+b14+b15+b24+b25+b26+b27+b28=1 (все разряды из множества V4 за исключением первого); b16=b17+b18+b19+b20+b21+b22+b23+b24+b25+b26+b27+b28=1 (все разряды из множества V5 за исключением первого)