1.4.1 Коды, обнаруживающие ошибку

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

Например, для передачи слова «лето» можно передавать «лл ее тт оо».

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

Однако цель такого способа кодирования состоит не в исправлении ошибки, а в фиксации факта искажения и повторной передаче сообщения (части сообщения) в этом случае.

Недостаток такого способа обеспечения надежности состоит в том, что избыточность сообщения оказывается очень большой – очевидно, L=2.

Поскольку ошибка должна быть только обнаружена, можно предложить другой способ кодирования. Пусть имеется цепочка информационных бит длиной k_i. Добавим к ним один контрольный бит (k_c = 1), значение которого определяется тем, что новая кодовая цепочка из (k_i+1) должна содержать четное количество единиц – по этой причине такой контрольный бит называется битом четности.

Например, для информационного байта 01010100 бит четности будет иметь значение «1», а для байта 11011011 – «0».

В случае одиночной ошибки передачи число единиц перестает быть четным, что и служит свидетельством сбоя.

Например, если получена цепочка 110110111 (контрольный бит подчеркнут) ясно, что передача произведена с ошибкой.

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

.

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

Поэтому обычно k_i = 8 или 16, и, следовательно, L = 1,125 и (1,0625).

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

1.4.2 Коды, исправляющие одиночную ошибку

По аналогии с предыдущим пунктом можно было бы предложить простой способ установления ошибки – передавать каждый символ трижды, например «лллееетттооо», тогда при получении сообщения «лвлееетттооо», ясно, что ошибка буква в и ее надо заменить на «л». Конечно, при этом предполагается, что вероятность появления парной ошибки невелика. Избыточность L = 3, что слишком много.

Первым исследователем кодов, исправляющих ошибки, стал Р.В.Хемминг (40-е годы ХХ века). Для того чтобы понять, как работают такие коды, определим сначала расстояние Хемминга между двумя кодами как число различающихся разрядов.

Так, для кодов приведенных в таблице 1.2, расстояние Хемминга между символами А и Б равно 4, а расстояние Хемминга между Б и В равно 3.

Таблица 1.2 Пример кодовой таблицы

Символ	Код	Символ	Код
А Б В Г	000000 001111 010011 011100	Д Е Ж З	100110 101001 110101 111010

Важное свойство приведенной системы кодирования состоит в том, что расстояние Хемминга между любыми двумя кодами больше или равно 3. Поэтому, если один бит в коде будет изменен, ошибку можно будет обнаружить, так как результат не будет допустимым кодом. (Для того чтобы код выглядел как другой допустимый код, необходимо изменить, по меньшей мере, 3 бита).

Кроме того, если появится ошибка в коде, можно понять, как выглядел исходный код. Расстояние Хемминга между исходным кодом и измененным будет равно 1, а между ним и другими допустимыми кодами – по меньшей мере, 2.

Для того, чтобы расшифровать сообщение, необходимо просто сравнить каждый полученный код с кодами в таблице до тех пор, пока не найдем код, находящийся на расстоянии, равном 1, от исходного кода. Это и будет правильный символ.

Например, предположим, получен код 010100. Если сравнить его с другими кодами, то получим следующую таблицу расстояний (таблица 1.3).

Символ	Код символа	Расстояние между полученным кодом и кодом символа
А Б В Г Д Е Ж З	000000 001111 010011 011100 100110 101001 110101 111010	2 4 3 1 3 5 2 4

Таблица 1.3 Расстояние по Хеммингу

Следовательно, можно сделать вывод, что был послан символ Г, так как между его кодом и полученным кодом наименьшее расстояние.

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

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

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

1 2 3 4 5 6 7 8 9 10 11 12

0

0

0

1

1

1

0

1

1

1

0

1

7 6 5 4 3 2 1 0

Каждый проверочный бит контролирует определенные информационные биты:

1 - 1, 3, 5, 7, 9, 11 …;

2 - 2, 3, 6, 7, 10, 11, 14, 15…;

4 - 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23…;

8 - 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26… .

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

Принципы выделения контролируемых битов: для любого номера проверочного бита (n), начиная с него, проверяется n бит подряд, затем – группа n непроверяемых бит, далее происходит чередование групп.

Пример 4.

Полученная последовательность

Исходная последовательность

1 2 3 4 5 6 7 8 9 10 11 12

0	0	0	1	0	1	0	1	1	1	0	1
0	0	0	1	1	1	0	1	1	1	0	1

Анализируем состояние контрольных битов

Бит 1 (1,3, 5, 7, 9, 11) – неверно, то есть ошибка находится в нечетном бите.

Бит 2 (2, 3, 6, 7, 10, 11) – верно, то есть ошибка не в 3-м, 7, 11 бите, а в 5 или 9.

Бит 4 (4, 5, 6, 7, 12) – неверно, то есть ошибка – в 5 бите.

Таким образом, однозначно устанавливается, что ошибочным является 5-ый бит. Остается его исправить на противоположный (исправить ошибку), и восстановить правильную последовательность.

Номер бита, содержащего ошибку, 5 – равен сумме номеров контрольных битов, указавших на ее существование (1 и 4) – это не случайное совпадение, а общее свойство кодов Хемминга.

Алгоритм проверки и исправления последовательности бит в представлении Хемминга:

1. провести проверку всех битов четности;

2. если все биты четности верны, перейти к п.5;

3. вычислить сумму номеров всех неправильных битов четности;

4. инвертировать содержимое бита, номер которого равен сумме п.3;

5. исключить биты четности, передать правильный информационный код.

Избыточность кода Хемминга для различных длин передаваемых последовательностей приведена ниже:

Число информационных битов	Число контрольных битов	Избыточность
8	4	1,5
16	5	1,31
32	6	1,06

Следовательно, выгоднее передавать и хранить более длинные последовательности битов.