§ 17. Коды, обнаруживающие и исправляющие ошибки

Определения и обозначения

Ошибка передачи — изменение одного или нескольких символов исходного сообщения при хранении или передаче. Например, вместо бита 0 может быть получен бит 1. Этот термин нужен, чтобы отличать сбой в канале или памяти от ошибки при составлении самого сообщения.

Кодовое слово — последовательность символов, полученная после кодирования сообщения и предназначенная для передачи. В неё могут входить как исходные данные, так и добавленные для контроля разряды. Кодовые слова нужны, чтобы задавать правила, по которым получатель проверяет сообщение.

Контрольный разряд — символ, добавленный к данным для проверки заранее установленного условия, например чётности числа единиц. Получатель пересчитывает значение условия и сравнивает его с требуемым. Такой разряд помогает заметить часть ошибок, хотя сам по себе не всегда показывает, где именно возникло искажение.

Расстояние Хэмминга — число позиций, в которых различаются два кодовых слова. Например, у слов 101 и 111 расстояние равно единице: различается только вторая позиция. Минимальное расстояние между всеми допустимыми словами позволяет оценить, сколько ошибок код обнаруживает и сколько способен исправить.

Как это устроено

Избыточные символы добавляют потому, что по одним только исходным данным часто невозможно понять, изменился ли бит: полученное слово может выглядеть вполне допустимым. Дополнительные разряды задают связи между битами, которые должны выполняться у правильного слова. Если после передачи связь нарушилась, получатель замечает искажение; если код содержит достаточно проверочной информации, можно также определить верный вариант. За надёжность приходится платить увеличением длины сообщения.

В коде с повторением каждый символ передают несколько раз: например, 0 становится 000, а 1 — 111. При декодировании группу делят на тройки и выбирают значение, встретившееся чаще, потому что одна случайная перемена бита не меняет большинство. Для троек это исправляет одиночную ошибку в каждой группе. Однако объём данных утраивается, а при двух искажениях из трёх голосование уже может выбрать неправильный бит.

Для проверки на чётность к данным приписывают разряд так, чтобы общее число единиц стало чётным; можно заранее договориться и о нечётном числе. Получатель пересчитывает единицы, поскольку одиночное изменение бита меняет чётность и выдаёт ошибку. Если изменились два бита, чётность может снова оказаться прежней: изменения взаимно сохраняют общий признак. Поэтому такая проверка обнаруживает любое нечётное число ошибок, но не гарантирует обнаружение чётного.

Возможности кода связаны с минимальным расстоянием d — наименьшим расстоянием между любыми двумя разными допустимыми словами. Если искажено меньше d разрядов, принятое слово не может превратиться в другое допустимое слово, поэтому можно обнаружить до d − 1 ошибок. Для исправления нужно выбрать ближайшее допустимое слово; оно определяется однозначно, если число ошибок не больше ⌊(d − 1)/2⌋. Например, при d = 3 код обнаруживает до двух ошибок и исправляет одну.

В семибитном коде Хэмминга контрольные разряды занимают позиции 1, 2 и 4 — степени двойки; остальные позиции отводятся данным. Каждая проверка включает те разряды, в номере позиции которых соответствующий двоичный разряд равен 1. Полученные результаты собирают в синдром: его значение указывает номер ошибочной позиции, если произошла одиночная ошибка. Тогда достаточно изменить бит в указанной позиции; нулевой синдром означает, что проверки не выявили ошибки.

Сравнение кодов, обнаруживающих и исправляющих ошибки

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

Разбор задач

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

1. В слове 101 две единицы, а это уже чётное число.
2. Поэтому контрольный разряд равен 0: после добавления число единиц останется равным двум.
3. Получаем кодовое слово 1010. Если при передаче изменится один разряд, число единиц станет нечётным либо, при замене 1 на 0, уменьшится на единицу и тоже станет нечётным.

Ответ: кодовое слово — 1010. Искажение одного разряда проверка обнаружит, потому что чётность изменится. Само правило при этом не сообщает, какой именно разряд нужно исправить.

Задача 2. Сообщение 10 передали кодом повторения: каждый бит заменили тремя одинаковыми битами. Получено слово 101000. Нужно восстановить исходное сообщение. При решении важно сначала отделить группы, относящиеся к разным исходным битам, и лишь затем выбирать значение большинства в каждой группе.

1. Длина принятого слова равна шести битам, поэтому делим его на тройки: 101 и 000.
2. В первой тройке два бита равны 1 и один бит равен 0, значит, большинство указывает на исходный бит 1.
3. Во второй тройке все три бита равны 0, поэтому исходный бит — 0. Соединяем результаты голосования в прежнем порядке.

Ответ: восстановленное сообщение — 10. Первая тройка содержит одиночное искажение, которое не изменило большинство. Во второй тройке искажения нет.

Задача 3. В принятом семибитном кодовом слове Хэмминга результаты контрольных проверок образовали двоичное число 101. Определить позицию ошибки и исправить слово. Позиции контрольных битов — 1, 2 и 4, поэтому синдром читают как номер позиции в двоичной записи; здесь подразумевается обычный порядок разрядов, в котором 101 означает пять.

1. Переводим синдром 101 из двоичной системы в десятичную: 1 × 4 + 0 × 2 + 1 × 1 = 5.
2. Значит, проверки указывают на ошибку в пятой позиции принятого слова.
3. Меняем пятый бит на противоположный: 0 заменяем на 1 или 1 на 0. Остальные шесть битов оставляем без изменений.
4. Повторно выполняем проверки. Если одиночная ошибка исправлена и других ошибок нет, синдром становится нулевым.

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

Типичные ошибки

Считать, что контрольный разряд всегда исправляет ошибку. Его нередко принимают за универсальное средство, потому что он позволяет проверить сообщение. Но обычная проверка чётности только сообщает, что условие нарушено, и не показывает, какой бит изменить. Проверяйте себя вопросом: указано ли в коде, как определить позицию ошибки?

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

Путать число контрольных разрядов с числом исправляемых ошибок. Большее число добавленных битов само по себе не говорит, сколько сбоев можно исправить: имеют значение правила кода и расстояние между допустимыми словами. Ошибку допускают, когда оценивают код только по длине контрольной части. Сначала определите минимальное расстояние d, затем примените формулу ⌊(d − 1)/2⌋.

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

Связь с другими темами

Для работы с кодами ошибок нужны двоичная система счисления и понимание операций с битами. Тема также связана с передачей сообщений по каналу, где возможны искажения. В теории информации избыточность рассматривают как плату за достоверность: контрольные данные не несут новых сведений о сообщении, но помогают проверить его или восстановить. Такие методы применяют в сетевых протоколах, памяти компьютеров, QR-кодах, на дисках, в спутниковой и мобильной связи.

Что запомнить

• Избыточность позволяет обнаруживать и исправлять ошибки передачи.
• Кодовое слово содержит данные и контрольную информацию.
• Проверка чётности обнаруживает нечётное число ошибок, но не гарантирует обнаружение чётного числа ошибок.
• Минимальное расстояние d позволяет обнаружить до d − 1 ошибок.
• Минимальное расстояние d позволяет исправить до ⌊(d − 1)/2⌋ ошибок.
• В коде Хэмминга синдром указывает позицию одиночной ошибки.
• Чем выше помехоустойчивость кода, тем больше избыточность и объём передаваемых данных.