Принципы обнаружения и исправления ошибок с использованием кодов
Способы введения избыточности, позволяющие обнаруживать и исправлять ошибки, можно разделить на два класса, один из которых соответствует блоковым кодам, а другой - сверточным кодам [33]. Обе схемы кодирования применяются на практике. При блоковом кодировании последовательность, составленная из полученных в результате коди-рования источника кодовых слов, разбивается на блоки одинаковой длины. Каждый блок перед отправкой в канал обрабатывается независимо от других. Выходустройства, выполняющего сверточное кодирование, напротив, зависит не только от обрабатываемых в данный момент знаков, но и от предыдущих знаков. Остановимся более подробно на блоковом кодировании.
Как было показано ранее, ошибка в одном лишь разряде может испортить все сообщение. Чтобы избежать таких тяжелых последствий, сообщения, закодированные каким-либо экономным кодом, перед направлением в канал делятся на блоки одинаковой длины и каждый блок передается отдельно. При этом методы, позволяющие обнаруживать и исправлять ошибки, применяются к каждому блоку. Такой прием напоминает разделение большого судна на несколько изолированных друг от друга отсеков, что позволяет при пробоине в одном отсеке сохранить судно и груз в других отсеках.
Рассмотрим схему передачи данных, показанную на рис.7.3.
С кодирующего устройства в канал поступают закодированные блоки (кодовые слова) одинаковой длины 
. В канале в результате действия различных помех в некоторых битах передаваемого сообщения могут происходить ошибки. Процедуру кодирования при передаче и
Рис. 7.3.Схема передачи данных
декодирования при приеме с использованием одной и той же кодовой таблицы иллюстрируем рис.7.4. Предполагается, что появление ошибок описывается моделью дискретного симметричного канала
Рис. 7.4.Использование кодовой таблицы для кодирования и декодирования
В геометрической интерпретации эти блоки можно рассматривать как точки n-мерного пространства 
, где 
. Точки этого пространства представляют собой последовательности чисел 0 и 1 длины . Пространства для 
можно представить в виде угловых точек единичного интервала ( 
), вершин квадрата со стороной, равной 1 ( 
), и вершин куба с ребрами длины 1 ( 
). Эти пространства условно изображены на рис.7.5.
Код, используемый для обнаружения и исправления ошибок, представляет собой некоторое подмножество пространства . В качестве примера можно привести код 
. Кодовые слова этого кода как точки пространства 
изображены на рис. 7.6 белыми кружками. Если представить куб расположенным в трехмерном пространстве, то словам данного кода соответствуют вершины тетраэдра. Более полезным
Рис. 7.5.Геометрическое представление пространства Bn для n = 1, 2 и 3
с практической точки зрения является то, что каждое слово кода содержит четное число единиц. Если при передаче кодового слова через канал произойдет одна ошибка, то число единиц в слове станет нечетным. Проверяя свойство четности числа единиц в слове после получения его из канала на приемном конце, можно обнаружить одну ошибку. В данном случае для кодирования четырех знаков используется 3 двоичных разряда, хотя достаточно двух. Однако благодаря такой избыточности удается обнаружить одну ошибку.
Рис. 7.6.Код в B3, обнаруживающий одну ошибку
В соответствии с общей схемой передачи сообщений в кодирующем и декодирующем устройствах используется одна и та же кодовая таблица и, следовательно, множество кодовых слов. При передаче кодового слова через канал возможны следующие ситуации.
Передавалось и было получено некоторое кодовое слово 
. Эта ситуация, которая показана в верхней части рис.7.7, соответствует отсутствию ошибок при передаче.
Передавалось кодовое слово ci, а получено было сообщение, которое не является кодовым словом. При попытке декодировать это сообщение будет обнаружено, что такого слов в кодовой таблице нет. Это означает, что ошибка, произошедшая при передаче и исказившая кодовое слово, обнаружена. Эта ситуация изображена в средней части рис.7.7.
Рис. 7.7.Возможные варианты передачи кодового слова через канал
В процессе передачи кодовое слово 
может так исказиться из-за ошибок, что оно превратится в другое кодовое слово 
. В этом случае ошибка не обнаруживается, поскольку полученное сообщение также является кодовым словом, и декодированиебудет выполнено неверно. Такая ситуация показана в нижней части рис.7.7.