Обучающая программа по информатике (стр. 3 из 11)
Рассмотрим подробно способ нахождения одной ошибки. Если в математическом коде выделен один контрольный разряд, то к каждому двоичному числу добавляется один избыточный разряд. В этот разряд записывается 1 или 0 с таким условием, чтобы сумма цифр по модулю 2 была равна 0 для случая четности или 1 для случая нечетности. Появление ошибки в кодировании обнаруживается по нарушению четности / нечетности. При таком кодировании допускается, что может возникнуть только одна ошибка.
Пример реализации метода четности:
| Число | Контрольный разряд | Проверка |
| 10101011 | 1 | 0 |
| 11001010 | 0 | 0 |
| 10010001 | 1 | 0 |
| 11001011 | 0 | 1 – ошибка |
Можно представить и несколько видоизмененный способ контроля по методу четности / нечетности. Длинное слово разбивается на группы, каждая из которых содержит n разрядов. Контрольные разряды – k, выделяются всем группам по строкам и столбцам согласно следующей схеме:
Увеличение избыточности приводит к тому, что появляется возможность не только обнаружить ошибку, но и исправить ее.
Например: число 1000111011010101110010101 представим по указанной выше схеме, получим:
| 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 |
Теперь, если при передаче было получено число:
| 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 |
Тогда проверка показывает, что ошибка возникла в информации третьей строки и четвертого столбца. Следовательно, разряд, содержащий ошибочную информацию, находится на пересечении третьей строки и четвертого столбца. Ошибку можно устранить, изменив 0 на 1.
1.4. Кодирование по методу Хэмминга
Код Хэмминга – систематический код, то есть состоящий из информационных и корректирующих символов, расположенных по строго определенной системе, имеющих одинаковую длину и всегда занимающих строго определенные места в кодовых комбинациях.
Предложенные Хэммингом регулярные методы построения кодов, корректирующих ошибки, имеют фундаментальное значение. Они демонстрируют инженерам практическую возможность достижения пределов, на которую указывали законы теории информации. Эти коды нашли практическое применение при создании компьютерных систем. Работа Хэмминга привела к решению проблемы более плотной упаковки для конечных полей. Он ввел в научный обиход важнейшие понятия теории кодирования – расстояние Хэмминга между кодовыми комбинациями в векторном пространстве, определяемом для двоичных кодов как количество позиций этих комбинаций с различными символами, и границы Хэмминга для исправляющей способности блочных корректирующих кодов. Граница Хэмминга для двоичных кодов рассчитывается по следующей формуле:
В этом выражении число ошибок e может быть исправлено корректирующим блочным кодом длиной N, имеющим М кодовых комбинаций (CjN – биномиальный коэффициент)[3].
Работа Хэмминга сыграла ключевую роль в последующем развитии теории кодирования и стимулировала обширные исследования, выполненные в последующие годы.
Коды Хэмминга позволяют не только обнаружить наличие ошибки, но и место ее нахождения и, следовательно, дают возможность ее исправить. Однако коды Хэмминга обладают меньшей избыточностью (по сравнению с кодированием по методу четности-нечетности), т.е. количеством дополнительных контрольных разрядов.
При передаче кода может быть искажен или не искажен любой символ. Если длина кода – n символов, то
– полное количество комбинаций кода. По методике Хэмминга можно определить число информационных символов кода, обнаруживающего и корректирующего одиночную ошибку следующим образом: 
, где 
– число информационных символов в коде; 
– число контрольных символов; 
– длина кода Хемминга.Соотношение n,
и для кода Хэмминга можно представить в виде таблицы:Таблица 2.2.a
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| | 0 | 0 | 1 | 1 | 2 | 3 | 4 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 11 |
| | 1 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 5 |
Предположим, что имеется код, содержащий m информационных и k контрольных разрядов. Все разряды, включая контрольные, разбиваются на k групп по определенным правилам, о которых будет сказано ниже. Каждая группа, содержащая один контрольный разряд, проверяется на четность. Пусть были проведены все k проверок. Если результат данной проверки свидетельствует об отсутствии ошибки, то записывается 0, если есть ошибка, то записывается 1. В результате получается последовательность, состоящая из k нулей и единиц. При отсутствии ошибки в коде получается последовательность нулей. Полученное k-разрядное двоичное число может содержать 2k различных комбинаций нулей и единиц. С помощью этой информации нужно определить ошибочный разряд в коде, содержащем m+k разрядов. Для того чтобы это было возможно должно выполняться неравенство:
2k (m+k+1)
Определить максимальное значение m для данного k можно из следующей таблицы.
| n | 1,2,3,4… | 8,…,15 | 16,…31 | … |
| m | 0,0,1,1… | 4,…11 | 11,…26 | … |
| k | 1,2,2,3 | 4…4 | 5…5 | … |
Из таблицы видно, для 16-ти разрядного числа требуется 5 контрольных разрядов. В качестве сравнения, в случае модифицированного метода четности потребовалось бы 8 контрольных разрядов. Позиции контрольных разрядов в методе Хэмминга определены заранее, это разряды 1,2,4,8,… Разряды, входящие в каждую группу проверки представлены в следующей таблице (1-й разряд в каждой группе является контрольным).
| номер группы проверки | проверяемые разряды |
| 1 | 1,3,5,7,9,11,13,15,… |
| 2 | 2,3,6,7,10,11,14,15,18,19,22,23,… |
| 3 | 4,5,6,7,12,13,14,15,20,21,22,23,… |
| 4 | 8,9,10,11,12,13,14,15,24,… |
Из таблицы видно, что если, например код Хэмминга содержит 9 разрядов, включая контрольные, то 1-я группа проверки содержит 1,3,5,7,9 разряды. 2-я группа проверки содержит 2,3,6,7 разряды. 3-группа проверки содержит 4,5,6,7 разряды и 4-я группа – 8,9 разряды. Каждой группе проверки приписывается 1, если проверка на четность обнаруживает ошибку и 0, если ошибки нет. Полученное двоичное число дает номер ошибочного разряда.
Код Хэмминга имеет существенный недостаток: при обнаружении любого числа ошибок он исправляет лишь одиночные ошибки. Например, избыточность семиэлементного кода Хэмминга равна 0,43. При увеличении значности кодовых комбинаций увеличивается число проверок, но уменьшается избыточность кода. К тому же код Хэмминга не позволяет обнаружить групповые ошибки. Длина пакета ошибок представляет собой увеличенную на единицу разность между именами старшего и младшего ошибочных элементов.
Рассмотрим в качестве примера 5-ти разрядное двоичное число 10011. В этом случае, как следует из вышеприведенной таблицы, 1-я группа проверки состоит из 1,3, и 5-го разрядов. 2-я группа проверки состоит из 2 и 3-го разряда. 3-я группа проверки состоит из 4 и 5-го разрядов. Результат проверки на четность 1-й группы дает 0 (101), проверка 2-й группы дает 0 (00), проверка 3-й группы дает 0 (11).
k1 = 1 + 0 + 1 = 0 – нет ошибки;
k2 = 0 + 0 =0 – нет ошибки;
k3 = 1 + 1 = 0 – нет ошибки.
Таким образом, данное число не содержит ошибки. Искусственно введем ошибку, заменив, например, 4-й разряд на 0. В этом случае 1, 2 и 3-я проверки дадут соответственно 0, 0, 1.
k1 = 1 + 0 + 1 = 0 – нет ошибки;
k2 = 0 + 0 =0 – нет ошибки;
k3 = 0 + 1 = 1 – ошибка.
Полученное двоичное число 100 дает номер ошибочного разряда, т.е. 4.
«Внешний вид» машины Поста