Лабораторная работа № 4 (к § 17) Коды, обнаруживающие и исправляющие ошибки

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

Кодовое слово — последовательность символов, представляющая исходное сообщение после кодирования. Например, при кодировании двоичного сообщения к его битам могут добавиться проверочные биты. Кодовое слово — именно то, что передают или сохраняют, поэтому проверяют его целиком.

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

Ошибка передачи — изменение одного или нескольких символов кодового слова при хранении или передаче. В двоичном коде это может быть замена 0 на 1 или 1 на 0. Ошибка возникает из-за помех или сбоя, а её последствия зависят от того, предусмотрена ли в коде проверка.

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

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

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

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

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

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

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

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

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

Разбор задач

Задача 1. Для сообщения 101101 добавим проверочный разряд, чтобы число единиц стало чётным, а затем проверим принятое слово 1011011. Сначала считаем единицы в исходных данных, чтобы понять, какой разряд требуется. Затем отдельно проверяем принятую последовательность, считая в ней все символы.

1. В сообщении 101101 четыре единицы, то есть их число уже чётное.
2. Добавляем в конец 0: получаем кодовое слово 1011010, в нём по-прежнему четыре единицы.
3. В принятом слове 1011011 пять единиц, поэтому условие чётности нарушено.

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

Задача 2. Каждый бит передали трижды: сообщение 101 превратилось в 111000111. В принятой последовательности 111001111 нужно найти искажение и восстановить сообщение. Поскольку схема повторения состоит из троек, сначала делим последовательность на группы именно по три бита, а затем определяем большинство внутри каждой группы.

1. Разбиваем принятое слово: 111 | 001 | 111.
2. Первая группа содержит три единицы, поэтому декодируем её как 1.
3. Во второй группе два нуля и одна единица, значит, большинство — 0; искажён один из битов группы.
4. Третья группа содержит три единицы, поэтому декодируем её как 1.

Ответ: восстановленное сообщение — 101. Метод с большинством работает, пока в каждой тройке неверно не становится большинство битов.

Задача 3. Закодируем сообщение 1011 кодом Хэмминга (7,4), затем изменим один бит и восстановим слово. Примем, что данные по порядку занимают позиции 3, 5, 6, 7, а проверки на чётность включают свои проверочные разряды.

1. Расставляем данные: позиция 3 — 1, 5 — 0, 6 — 1, 7 — 1; позиции 1, 2 и 4 отводим проверкам.
2. Для группы 1, 3, 5, 7 единиц уже две, поэтому бит 1 равен 0. В группе 2, 3, 6, 7 три единицы, поэтому бит 2 равен 1. В группе 4, 5, 6, 7 две единицы, поэтому бит 4 равен 0.
3. Получаем кодовое слово 0110011. Для примера меняем позицию 6: принимаем 0110001.
4. Проверки групп 1, 3, 5, 7; 2, 3, 6, 7; 4, 5, 6, 7 дают соответственно 0, 1, 1. Записываем результаты в порядке проверок 4, 2, 1: синдром равен 110₂, то есть 6.
5. Меняем бит 6 в принятом слове на 1. Получаем 0110011 и проверяем: все три условия чётности выполнены.

Ответ: исходное сообщение 1011 закодировано словом 0110011; после исправления снова получено это слово. Данные в позициях 3, 5, 6, 7 дают исходное сообщение.

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

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

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

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

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

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

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

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

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