Избыточное кодирование
Избыточное кодирование — это добавление к исходным данным специальных лишних символов, которые помогают обнаружить или исправить ошибки при передаче и хранении информации. Благодаря этому данные становятся надёжнее, хотя сообщение увеличивается в размере.
Как это работает
При передаче по каналу связи или хранении в памяти отдельные биты могут измениться: \(0\) превратиться в \(1\) или наоборот. Кодер добавляет контрольные символы по определённому правилу. Декодер проверяет это правило и определяет, соответствует ли полученная последовательность допустимому кодовому слову.
В простейшем случае к группе битов добавляют бит чётности. Он выбирается так, чтобы общее число единиц стало чётным. Если при передаче изменился один бит, проверка обнаружит нарушение правила. Для исправления ошибок применяют более сложные схемы — [[error-correcting-code:помехоустойчивое кодирование]].
Здесь \(k\) — число полезных символов, \(n\) — общее число символов после кодирования, \(R\) — скорость кодирования, а \(r\) — количество избыточных символов. Чем больше избыточность, тем надёжнее обычно код, но тем больше места и времени требуется для передачи. В задачах важно отличать полезные данные от контрольных символов.
Пусть передаётся последовательность \(1011\). В ней три единицы, поэтому для чётного числа единиц добавим бит \(1\): получится \(10111\). Если принято \(10011\), единиц стало четыре, и проверка чётности пройдена; если принято \(10101\), единиц стало три, поэтому ошибка обнаружена.
Избыточное кодирование — это общий принцип добавления лишних символов. [[error-detecting-code:код с обнаружением ошибок]] только сообщает о наличии ошибки, а код с исправлением ошибок дополнительно позволяет восстановить исходные данные. Любой исправляющий код является избыточным, но не всякий избыточный код исправляет ошибки.
Что произойдёт с объёмом сообщения при добавлении контрольных символов?
Главное
- Избыточное кодирование добавляет контрольные символы для повышения надёжности данных.
- Избыточность позволяет обнаруживать ошибки, а специальные коды — также исправлять их.
- Скорость кодирования вычисляется по формуле \(R=\frac{k}{n}\): чем больше лишних символов, тем ниже скорость, но обычно выше устойчивость к ошибкам.