Помехоустойчивое (корректирующее) кодирование

Оосновные понятия

Помехоустойчивое кодирование используется в различных системах связи, в сетях ЭВМ, в бытовой и профессиональной аудио- и видеотехнике.

Любой помехоустойчивый код является избыточным.

Избыточные коды – коды, в которых для передачи информации используются не все возможные кодовые слова. Используемые кодовые слова называются разрешенными. Их число – мощность кода . Неиспользуемые кодовые слова считаются запрещенными.

Пример 2.1:

Рассмотрим трехразрядный (n =3) двоичный (m =2) код.

Безызбыточный код	Избыточный код
Разрешенные кодовые слова	Запрещенные кодовые слова

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

Пример 2.2:

Безызбыточный код	Избыточный код
Нет возможности контролировать ошибки.	Есть возможность контролировать ошибки.

Корректирующая способность кода – способность кода контролировать (обнаруживать и исправлять) ошибки. Она определяется кодовым расстоянием.

Кодовое расстояние – минимальное расстояние Хэмминга для заданного кода:

.

Расстояние Хэмминга – степень различия между -ым и -ым кодовыми словами:

.

Определяется числом несовпадающих в них разрядов.

Задача 2.1:

Определить для избыточного кода из примера 2.1.

Решение:

;

;

;

;

;

;

.

Методы декодирования помехоустойчивых кодов:

- декодирование с обнаружением ошибок – обеспечивает стирание или особую отметку той части сообщения, в которой обнаружены ошибки;

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

Существует также смешанное декодирование. Один и тот же код можно использовать при различных методах декодирования.

Правила для определения корректирующей способности кодов:

1. Для обнаружения ошибок кратности кодовое расстояние должно удовлетворять соотношению:

.

2. Для исправления ошибок кратности и одновременного обнаружения ошибок кратности () кодовое расстояние должно удовлетворять соотношению:

.

Задача 2.2:

Определить корректирующую способность кода, имеющего . То же для кода с .

Решение:

Формулы для определения обнаруживающей и исправляющей способности кода:

,

.

Для кода с (из правила 1: ) или и (из правила 2: ).

Для кода с (из правила 1: ) или и (из правила 2: ).