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

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

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

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

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

Пример 2.1:

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

Безызбыточный код	Избыточный код
	Разрешенные кодовые слова	Запрещенные кодовые слова
000 001 010 011 100 101 110 111	000 010 100 110	001 011 101 111

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

Пример 2.2:

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

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

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

.

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

.

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

Задача 2.1:

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

Решение:

;

;

;

;

;

;

.

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

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

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

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

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

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

.

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

.

Задача 2.2:

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

Решение:

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

,

.

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

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