Код Хемминга. Кодирование числовой информации

В своём функционировании любая автоматизированная система сталкивается с проблемой адекватного восприятия данных, чистоты полученной информации, нахождения ошибок, а также их исправлений. Чем серьёзнее задачи, возлагаемые на объект обработки информации, тем с более сложной и чувствительной системой определения сбойных элементов программного обеспечения и ошибок в потоке информации приходится ему работать.

Видео: Лекция 218. Код Хемминга

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

История появления кода начинается в средине 1940-х годов. В это время Ричард Хэмминг осваивал счётную машину Bell Model V, работая в именитых Bell Labs. Тогда это был ультрасовременный механизм, использующий электромеханический принцип действия. В конструкции машинки использовались релейные блоки. Их использование не давало существенного выигрыша в скорости. На осуществление одного оборота требовалось несколько секунд. Ввод данных происходил по средствам перфокарт, и ошибки в процессе их чтения были не редкостью. В будние дни для обнаружения и исправления найденных ошибок использовались специальные коды. Машина информировала оператора свечением лампочек, тот в свою очередь исправлял ошибку и заново запускал процесс вычисления. А вот в выходные дни процесс происходил по другим правилам. Обнаружив ошибку, машина автоматически прекращала выполнение первой программы и переходила к выполнению другой.

Видео: Shortcut for hamming code

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

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

У систематических кодов есть особенность, проверочные символы являются результатом линейных операций над символами информации. При этом в любой разрешенной кодовой комбинации присутствует возможность получения результата из линейных операций, производимых над набором независимых линейно кодовых комбинаций.

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

Если возникает одиночная ошибка, то она изменит четность в общем количестве единиц.

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

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