Диаграмма Вороного

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

Определения

Рис. 1. Диаграмма Вороного.

Обозначим:

линейный код длины , размерности с кодовым расстоянием над полем .

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

TemplateDifinitionIcon.svg Определение «Определение - Ячейка Вороного»

TemplateDifinitionIcon.svg Определение «Определение - Множество исправляемых ошибок кодового слова»

- кодовое словр;

Множества ошибок всех кодовых слов равны

TemplateTheoremIcon.svg Теорема Утверждение
Если - линейный код, то
Доказательство

Пусть и

не ближайший к

- противоречие, следовательно .


TemplateTheoremIcon.svg Теорема Следствие
Множество исправляемых ошибок линейного кода (не зависит от ):

.

Доказательство

Следует из доказанной выше теоремы.


Синдромы всех ошибок различны

TemplateTheoremIcon.svg Теорема Теорема
Пусть - проверочная матрица линейного кода , исправляющего ошибки из множества Тогда различные ошибки из имеют разные синдромы:
Доказательство
Если и то т.е. но тогда хотя противоречие.


TemplateTheoremIcon.svg Теорема Следствие

Если , но , то такие ошибки неисправимы.

Доказательство

, а, значит:

, тогда:

, что означает, что мы не можем отдать предпочтение ни одному из векторов или . Ошибки неисправимы.


Литература

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