Корректирующие коды

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 16:41, 12 мая 2016.

Исправление ошибок

Существует два способа коррекции ошибок при передаче кодовых слов:

а) Обнаружение и исправление ошибок на стороне получателя.
б) Обнаружение ошибок на стороне получателя и запрос на повторную передачу.

Определение

TemplateDifinitionIcon.svg Определение «Определение - Код исправляющий ошибки»
Пусть , т.е. информационное слово кодируется кодовым вектором , на декодер получателя поступает слово
Если - т.е. если количество произошедших ошибок не превосходит количества ошибок, которое данный код может исправить, то полученное слово можно однозначно раскодировать. Иными словами:

Характеристики кодов

Для каждого кода определяют характеристики:

1)Количество обнаруженных ошибок: s
2)Количество исправленных ошибок: t
3)Количество ошибок, обнаруживаемых в режиме исправления: s'
TemplateDifinitionIcon.svg Определение «Определение - Количество обнаруживающих ошибок »
Если ошибок не было, то
TemplateDifinitionIcon.svg Определение «Определение - Количество обнаруживающих ошибок в режиме исправления »
TemplateDifinitionIcon.svg Определение «Определение - Пусть - код, тогда - кодовое расстояние »
Рисунок 1

Если ошибок произошло не больше чем s, то для обнаружения s ошибок:

.

Для устранения t ошибок, шары не должны пересекаться:

.

Обнаружение 2 ошибок:

Рисунок 2

Если кодовое расстояние = 4, то раскодирование возможно только для одной ошибки:

Рисунок 3

Зависимость характеристик кода от кодового расстояния

TemplateTheoremIcon.svg Теорема Теорема
Доказательство
Рисунок 4
Рисунок 5

1) для (см. Рисунок 4):

- условие, при котором шары не пересекаются.


2) для (см. Рисунок 5):

3) для :

если кодовое расстояние нечётное:
, то .
если кодовое расстояние чётное:


Литература

Мак-Вильямс Ф. Дж, Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. — М. : Связь, 1979. — С. 744, ил.