Асимптотические границы

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

Параметры линейных кодов

TemplateDifinitionIcon.svg Определение «Определение - Параметры линейных кодов»

Есть параметры линейных кодов: , где - длина, - размерность, - кодовое расстояние.

Энтропия Шеннона

TemplateDifinitionIcon.svg Определение «Определение - Энтропия Шеннона»
Энтропия Шеннона -

;

, следовательно:

,

, следовательно, .

Таким образом функция будет иметь вид:

Рис. 1

Теоремы Шеннона

TemplateTheoremIcon.svg Теорема Теорема Шеннона
Существует - пропускная способность канала;, то существует код, такой что сообщение может быть передано с вероятностью ошибки раскодирования . Следовательно .
Доказательство

Без доказательства. Сам Шеннон свою теорему строго не доказывал. Он вывел ее из инженерных соображений. Можно прочитать доказательство на Википедии.


Идея: Существует константа, зависящая от , до которой мы можем повысить .

TemplateTheoremIcon.svg Теорема Обратная теорема Шеннона
Если , то нельзя понизить вероятность ошибки никаким кодированием.
Доказательство

Без доказательства. Сам Шеннон свою теорему строго не доказывал. Он вывел ее из инженерных соображений. Можно прочитать доказательство на Википедии.


Границы

Определения

TemplateDifinitionIcon.svg Определение «Определение - Скорость кода»

Скорость кода - .

TemplateDifinitionIcon.svg Определение «Определение - Относительное кодовое расстояние»

Относительное кодовое расстояние - .

TemplateDifinitionIcon.svg Определение «Определение - Асимптотически хороший код»

Бесконечное семейство , состоящее из -кодов, называется асимптотически хорошим, если существуют такие константы , не зависящие от , что

,

.

Оценка для мощности шара

TemplateTheoremIcon.svg Теорема Теорема - оценка мощности шара

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

Таким образом .


Сами границы

Асимптотические границы
Таблица границ:
Границы (n,k,d) линейный код (n,M,d) любой код
Хемминга ,
,
если левая и правая части равны,
то код совершенный.
Плоткина
Синглтона
Грайсмера

Литература

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