Обнаружение и исправление одиночных ошибок путем использования дополнительных разрядов

Рассмотрим возможность использования дополнительных (контрольных) разрядов для обнаружения и исправления ошибок. Эта возможность заключается в том, что к n информационным разрядам добавляется один контрольный разряд. В него записывается 0 или 1 таким образом, чтобы для каждого из передаваемых чисел сумма разрядов по модулю 2 была бы равна 0 (кодирование по методу четности) или 1 (нечетности).Появление ошибки в числе обнаружится по нарушению четности или нечетности. При этом виде кодирования допускается возможность выявления только одиночной ошибки. Чтобы одна комбинация разрядов числа превратилась в другую без выявления ошибки, необходимо изменение четного (2, 4, 6 и так далее) числа разрядов одновременно. Пример реализации метода контроля по методу четности-нечетности приведен в табл. 5.

Рассмотренный способ контроля по методу четности-нечетности может быть видоизменен для локализации (выявления места) ошибки в числе. Длинное число разбивается на группы разрядов, каждая из которых содержит k разрядов.

Таблица 5

Контрольные разряды выделяются всем группам по строкам и по столбцам согласно следующей схеме:

Если ошибка произошла в разряде a_s (единица изменилась на ноль или наоборот), то при проверке на четность (нечетность) сумма по i-й строке и j-му столбцу (на пересечении которых находится элемент a_s) изменится. Следовательно, можно зафиксировать нарушение четности (нечетности) по этой строке и столбцу. Это не только позволит обнаружить ошибку, но и локализовать ее место. Изменив значение разряда a_s на противоположное, можно исправить возникшую ошибку.

Контроль по методу четности-нечетности используется для контроля записи и считывания информации, а также для выполнения арифметических операций.

Коды Хемминга

Американский ученый Р. Хемминг предложил способ кодирования информации, позволяющий не только обнаруживать, но и исправлять ошибки при передаче одиночного слова любой разрядности. Эти коды – систематические. Пусть разрядность слова равна m. Для контроля информации требуется k дополнительных разрядов. Число k выбирается согласно следующим правилам.

1. Контролирующее число k выбирается так, чтобы оно имело количество комбинаций, достаточное для распознавания одной из m+k позиций или для сигнализации отсутствия ошибки. Полученное таким образом число описывает n=m+k+1 событий. Следовательно, необходимо, чтобы выполнялось неравенство 2^k≥(m+n+1).

2. (m+k)-разрядные позиции нумеруются от единицы до (m+k), начиная от младшей значащей. Контрольные разряды k обозначаются P₀, P₁, P₂, …,P_k-1 и помещаются в разряды, имеющие номера 1,2,4,8, …,2^k-1 (m+k)-разрядного числа. Остальные m разрядов могут быть размещены в любом порядке между контрольными разрядами.

3. Контрольные разряды P₀, P₁, P₂, …,P_k-1 выбраны таким образом, чтобы для определенных разрядов слова служить в качестве контрольных избыточных разрядов.

P₀ выбрано с таким расчетом, чтобы в позициях 1, 3, 5, 7, 9, 11 … число единиц каждого слова было четным, P₁ выбрано для того, чтобы выполнялось условие четности в разрядах 2, 3, 6, 7, 10, 11, 14, 15 …, аналогично P₂ контролирует позиции 4,5,6,7,12,13,14,15,20… и P_{3 −} для разрядов 8, 9,10,11,12,13, 14,15,24,25… .

На основании рассмотренных правил в табл. 6 показаны семиразрядные коды. Контрольные разряды обозначены P₀, P₁ и P₂ и помещены в позициях 1, 2 и 4.

Операция обнаружения и исправления ошибок выполняется путем нахождения k-разрядного контрольного числа. При этом младший значащий разряд контрольного числа находится посредством проведения контроля на четность над разрядами 1,3,5,7,9… . Если контроль показывает правильность передачи, то пишется нуль, иначе − единица. Следующий разряд контрольного числа

Таблица 6

определяется путем проверки на четность разрядов 2,3,7,10,11,14,15,… . Остальные разряды контрольного числа находятся аналогично.

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

Пусть, например, передается число шесть 0110011, а принимается в виде 0110111, то есть произошла ошибка в третьем разряде. Выполняя контроль на четность с помощью разрядов P₀, P₁ и P₂, находим:

Контрольное число

P₀ (1, 3, 5, 7) = (1, 1, 1, 0) нечетность 1

P₁ (2, 3, 6, 7) = (1, 1, 1, 0) нечетность 1

P₂ (4, 5, 6, 7) = (0, 1, 1, 0) четность 0

Полученное контрольное число равно 011, что соответствует ошибке в третьем разряде.

Таким образом, дополнительный разряд P_i выбран так, чтобы проверять четность той совокупности разрядных позиций, чьи контрольные числа содержат единицу в позиции 2ⁱ.