Помехоустойчивое кодирование
При передаче или хранении данных отдельные биты могут измениться из-за помех: \(0\) превращается в \(1\) или наоборот. Помехоустойчивое кодирование добавляет к сообщению контрольную информацию, чтобы обнаружить ошибку, а иногда и восстановить исходные данные.
Тема опирается на избыточное кодирование: к полезным данным добавляются лишние разряды. В заданиях ЕГЭ-8 обычно требуется определить, какие сообщения допустимы, найти ошибку по контрольному разряду или подсчитать число вариантов кодирования.
Основные понятия
Кодовое слово — последовательность символов, которой кодируется сообщение. Например, \(101101\) — одно кодовое слово двоичного кода. Набор всех разрешённых кодовых слов называют кодом.
Помехоустойчивый код — это код, в котором добавлены контрольные символы, позволяющие обнаруживать или исправлять ошибки, возникшие при передаче кодового слова.
Если в принятом слове изменился один или несколько символов, говорят об ошибке. Для сравнения двух двоичных слов используют расстояние Хэмминга — число позиций, в которых символы различаются.
Если минимальное расстояние между любыми двумя разрешёнными кодовыми словами равно \(d_{\min}\), то код обнаруживает до \(d_{\min}-1\) ошибок и исправляет до \(\left\lfloor\frac{d_{\min}-1}{2}\right\rfloor\) ошибок.
Почему обнаруживаются \(d_{\min}-1\) ошибок? Чтобы ошибочное слово стало другим разрешённым словом, нужно изменить хотя бы \(d_{\min}\) позиций. Поэтому меньшее число изменений не приведёт к другому допустимому слову.
Контрольный разряд и проверка чётности
Самый простой способ контроля — добавить один контрольный разряд, или бит чётности. Он выбирается так, чтобы общее число единиц в кодовом слове было чётным либо нечётным.
| Правило | Условие для общего числа единиц | Пример для данных 1011 |
|---|---|---|
| Чётная чётность | Число единиц должно быть чётным | В данных 3 единицы, контрольный бит 1: 10111 |
| Нечётная чётность | Число единиц должно быть нечётным | В данных 3 единицы, контрольный бит 0: 10110 |
Здесь \(\oplus\) означает сложение по модулю \(2\): \(0\oplus0=0\), \(0\oplus1=1\), \(1\oplus1=0\). При проверке нужно пересчитать единицы или выполнить XOR всех разрядов.
Один бит чётности обнаруживает любое нечётное число ошибок в слове, но не обнаруживает изменение чётного числа разрядов. Поэтому он обычно обнаруживает одну ошибку, однако не указывает её позицию и не исправляет её.
Другие методы добавления контрольной информации
Повторение: каждый информационный бит или блок передаётся несколько раз. Например, код \(0\to000\), \(1\to111\). Если принято \(101\), большинство символов равно \(1\), поэтому предполагают исходный бит \(1\). Такой метод исправляет одну ошибку в трёх повторённых разрядах, но сильно увеличивает длину сообщения.
Контрольная сумма: символы сообщения рассматриваются как числа, складываются, а результат или его остаток по модулю передаётся вместе с данными. При приёме сумма вычисляется заново и сравнивается с контрольным значением.
Циклический избыточный код использует деление двоичного сообщения на специальный многочлен. Остаток от деления добавляется к сообщению. В школьных задачах чаще встречается идея контроля остатка, а не само многочленное деление.
Код Хэмминга размещает несколько контрольных битов в позициях с номерами \(1,2,4,8,\dots\). Каждый такой бит проверяет определённую группу позиций. Набор результатов проверок образует двоичное число — номер ошибочной позиции. Поэтому код Хэмминга может исправлять одну ошибку.
Если в условии сказано «число единиц должно быть чётным», нужен бит чётности. Если каждый символ повторяется несколько раз, применяйте правило большинства. Если даны суммы или остатки, пересчитывайте контрольную сумму. Если упомянуты позиции \(1,2,4,8\), ищите код Хэмминга.
В коде используется чётная чётность. Какой контрольный бит нужно добавить к данным 11010?
Алгоритм решения задач
Для задач на контрольный разряд удобно действовать по одному плану:
- Определить, какое правило задано: чётная или нечётная чётность, повторение, сумма или специальная проверка.
- Выделить информационные и контрольные разряды.
- Выполнить проверку: посчитать единицы, сложить числа или сравнить повторяющиеся символы.
- Если обнаружена ошибка, определить, позволяет ли данный код найти её позицию и исправить.
- Проверить ответ обратным действием: исправленное слово должно удовлетворять правилу кода.
Передано слово \(1011010\). Используется код с чётным числом единиц. Определим, есть ли ошибка, если принято слово \(1011110\).
Контроль чётности показывает, что ошибка есть, но не сообщает, какой именно разряд изменился. Например, если изменились сразу два бита, число единиц снова могло стать чётным, и ошибка останется незамеченной.
Идея кода Хэмминга
В простом коде Хэмминга контрольные биты располагаются на позициях, являющихся степенями двойки: \(1,2,4,8,\dots\). Остальные позиции занимают информационные биты. Каждый контрольный бит проверяет позиции, в двоичной записи номера которых на соответствующем месте стоит единица.
| Контрольный бит | Проверяемые позиции |
|---|---|
| Позиция 1 | 1, 3, 5, 7, 9, … |
| Позиция 2 | 2, 3, 6, 7, 10, 11, … |
| Позиция 4 | 4, 5, 6, 7, 12, 13, … |
| Позиция 8 | 8–15, 24–31, … |
После проверки получают синдром. Если результаты проверок, стоящих на позициях \(1,2,4,8\), равны, например, \(1,0,1,0\), то синдром читают как двоичное число \(0101_2=5\); значит, ошибка находится в позиции 5. Нулевой синдром означает, что ошибка не обнаружена.
Не путайте число ошибок с числом изменившихся символов в принятом слове. Бит чётности обнаруживает нечётность числа ошибок, но не исправляет ошибку. При подсчёте единиц не следует учитывать только информационные биты: контрольный разряд тоже входит в проверяемое слово. В коде Хэмминга нумерация позиций обычно начинается с 1, а не с 0.
Что может и чего не может код
Чем больше минимальное расстояние между разрешёнными словами, тем надёжнее код, но тем больше избыточность. Код с одним битом чётности имеет минимальное расстояние \(2\): он обнаруживает одну ошибку, но не исправляет её. Для исправления одной ошибки требуется минимальное расстояние не менее \(3\).
Быстрая проверка
Главное
- Помехоустойчивое кодирование добавляет контрольную информацию для обнаружения и исправления ошибок.
- Бит чётности обнаруживает нечётное число ошибок, но не указывает их позицию и не исправляет их.
- Расстояние Хэмминга — число позиций, в которых различаются два кодовых слова.
- Код с минимальным расстоянием \(d_{\min}\) обнаруживает до \(d_{\min}-1\) ошибок и исправляет до \(\left\lfloor\frac{d_{\min}-1}{2}\right\rfloor\).
- Код Хэмминга использует контрольные позиции \(1,2,4,8,\dots\) и по синдрому может найти одну ошибочную позицию.