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

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

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

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

Бит чётности — проверочный бит, который добавляют так, чтобы общее число единиц в выбранной группе было чётным или нечётным. Например, при чётной чётности к группе с нечётным числом единиц добавляют 1. Такая проверка нужна для обнаружения некоторых искажений, но сама по себе обычно не показывает, какой именно бит изменился.

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

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

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

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

Чтобы исправлять ошибки, применяют несколько проверок, охватывающих разные группы битов. Код Хэмминга размещает проверочные биты в позициях 1, 2, 4, 8 и далее, то есть в позициях, являющихся степенями двойки. Каждый такой бит проверяет позиции, в двоичной записи номера которых на соответствующем месте стоит 1. Благодаря перекрытию групп один неверный бит влияет на определённый набор проверок.

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

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

Сравнение возможностей кодов

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

Разбор задач

Задача. Для передачи четырёх информационных битов 1011 построим код Хэмминга с чётной чётностью. Используем семь позиций: 1, 2 и 4 отведём под проверочные биты, а информационные биты поместим в позиции 3, 5, 6 и 7. Нужно определить передаваемое кодовое слово и исправить его, если получатель принял 0110011.

1. Сначала распределяем данные по позициям, не занятым проверками. Получаем: позиция 3 — 1, позиция 5 — 0, позиция 6 — 1, позиция 7 — 1. Проверочные позиции 1, 2 и 4 пока оставляем пустыми.

2. Для бита позиции 1 проверяем позиции 1, 3, 5 и 7. Среди уже заполненных там битов стоят 1, 0 и 1, то есть две единицы. Чётность уже чётная, поэтому в позицию 1 записываем 0.

3. Для бита позиции 2 проверяем позиции 2, 3, 6 и 7. Из данных в этой группе находятся три единицы: в позициях 3, 6 и 7. Чтобы общее число стало чётным, в позицию 2 ставим 1.

4. Для бита позиции 4 проверяем позиции 4, 5, 6 и 7. В позициях 5, 6 и 7 находятся 0, 1 и 1, то есть уже две единицы. Значит, в позицию 4 записываем 0; кодовое слово по позициям 1–7 равно 0110011.

5. Проверяем принятое слово 0110011. Группа для позиции 1 содержит позиции 1, 3, 5 и 7: значения 0, 1, 0, 1 дают чётную сумму. Группа для позиции 2 также проходит проверку: в позициях 2, 3, 6 и 7 стоят 1, 1, 1, 1.

6. Группа для позиции 4 содержит позиции 4, 5, 6 и 7, где стоят 0, 0, 1, 1, — проверка тоже проходит. Все результаты равны нулю, поэтому синдром равен 000 и одиночная ошибка не выявлена. Полученное слово совпадает с рассчитанным кодовым словом.

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

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

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

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

• Неверно составлять группы проверок. Бит в позиции 1 проверяет позиции, в двоичном номере которых младший разряд равен 1, а бит в позиции 2 отвечает за следующий разряд. Чтобы не ошибиться, выпишите номера позиций в двоичном виде и проверьте принадлежность каждой группы.

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

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

Коды с проверочными битами опираются на двоичную систему счисления: именно в двоичном виде номера позиций помогают распределить проверки в коде Хэмминга. Чётность связана с арифметикой по модулю 2, где 1 ⊕ 1 = 0, а сложение единиц определяется их чётностью. Представление информации в виде битов объясняет, почему достаточно изменить один разряд, чтобы данные исказились.

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

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

• Проверочные биты добавляют к данным, чтобы обнаруживать или исправлять искажения.
• Бит чётности находит некоторые ошибки, но обычно не указывает их позицию; чётное число изменений может остаться незамеченным.
• Расстояние Хэмминга — число различающихся позиций; минимальное расстояние кода определяет предел обнаружения и исправления ошибок.
• В коде Хэмминга проверочные позиции — степени двойки, а набор результатов проверок образует синдром.
• При одиночной ошибке синдром указывает позицию неверного бита, но несколько ошибок могут нарушить работу исправления.