Методы выявления и устранения ошибок данных при передаче

 

Обнаружение ошибок в технике связи — действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) — процедура восстановления информации после чтения её из устройства хранения или канала связи.

 

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

 

В системах связи возможны несколько стратегий борьбы с ошибками:

· обнаружение ошибок в блоках данных и автоматический запрос повторной передачи повреждённых блоков — этот подход применяется в основном на канальном и транспортном уровнях;

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

· исправление ошибок (англ. forward error correction) применяется на физическом уровне.

Типы кодов: блоковые и свёрточные.

 

Блоковые коды

 

Пусть кодируемая информация делится на фрагменты длиной k бит, которые преобразуются в кодовые слова длиной n бит. Тогда соответствующий блоковый код обычно обозначают . При этом число  называется скоростью кода.

 

Если исходные k бит код оставляет неизменными, и добавляет n − k проверочных, такой код называется систематическим, иначе несистематическим.

 

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

· способность исправлять как можно большее число ошибок,

· как можно меньшая избыточность,

· простота кодирования и декодирования.

 

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

 

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

 

Расстоянием Хемминга (метрикой Хемминга) между двумя кодовыми словами называется количество отличных бит на соответствующих позициях.

 

Корректирующая способность определяет, сколько ошибок передачи кода можно гарантированно исправить. То есть вокруг каждого кодового слова A имеем t-окрестность At, которая состоит из всех возможных вариантов передачи кодового слова A с числом ошибок не более t. Никакие две окрестности двух любых кодовых слов не пересекаются друг с другом, так как расстояние между кодовыми словами (то есть центрами этих окрестностей) всегда больше двух их радиусов.

 

Свёрточные коды

Свёрточные коды, в отличие от блоковых, не делят информацию на фрагменты и работают с ней как со сплошным потоком данных.

 

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

 

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

 

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

 

Коды обнаружения

Циклический избыточный код (CRC)

 

Алгоритм CRC базируется на свойствах деления с остатком двоичных многочленов. Значение CRC является, по сути, остатком от деления многочлена, соответствующего входным данным, на некий фиксированный порождающий многочлен.

Бит чётности

 

Бит чётности или контрольный разряд формируется при выполнении операции «Исключающее-ИЛИ» поразрядно. Рассмотрим схему, использующую девятибитные кодовые слова, состоящие из восьми бит данных, за которыми следует, бит чётности.

Число 10111101 содержит 6 '1' битов. Бит чётности будет 0, получаем кодовое слово 101111010.

Число 01110011 содержит 5 '1' битов. Бит чётности будет 1, получаем кодовое слово 011100111.

Число 00000000 не содержит '1' битов. Бит чётности будет 0, получаем кодовое слово 000000000.

 

Пустой или несуществующий поток битов также имеет ноль единичных битов, поэтому бит чётности будет 0.

 

⇐ Предыдущая234567891011Следующая ⇒

Поделиться: