Неравенство Крафта — различия между версиями
Shersh (обсуждение | вклад) м |
|||
Строка 41: | Строка 41: | ||
*[ftp://remotesensing.ru/InfoTheory_lec05.pdf Теория информации] | *[ftp://remotesensing.ru/InfoTheory_lec05.pdf Теория информации] | ||
* Александр Х. Шень Программирование: теоремы и задачи. {{---}} М.: МЦНМО, 2007. {{---}} С. 208. {{---}} ISBN 978-5-94057-310-4 | * Александр Х. Шень Программирование: теоремы и задачи. {{---}} М.: МЦНМО, 2007. {{---}} С. 208. {{---}} ISBN 978-5-94057-310-4 | ||
+ | |||
+ | == См.также == | ||
+ | *[[Неравенство Макмиллана]] | ||
[[Категория: Дискретная математика и алгоритмы]] | [[Категория: Дискретная математика и алгоритмы]] | ||
[[Категория: Алгоритмы сжатия]] | [[Категория: Алгоритмы сжатия]] |
Версия 18:22, 14 января 2015
При необходимости построить префиксный код с большим числом кодовых слов заданной длины проверка существования такого кода может быть достаточно сложной. Но неравенство Крафта даёт достаточное условие существования префиксных и любых однозначно декодируемых кодов, обладающих заданным набором длин кодовых слов.
Теорема (неравенство Крафта (англ. Kraft's inequality)): |
Для любого префиксного кода , отображающего произвольный алфавит на двоичный алфавит , длины кодовых слов должны удовлетворять неравенству:
|
Доказательство: |
Рассмотрим отрезок на числовой прямой.Разделим его пополам, причем левую половину обозначим , а правую .Затем поделим пополам и обозначим его левую половину , а правую , и, проделав то же самое с , получим , а левую .Будем выполнять эти действия, пока длина индекса полученного отрезка не превосходит .Заметим, что:
Рассмотрим префиксный код префиксом никакого другого кодового слова, то никакие два отрезка не пересекаются. : так как ни одно из кодовых слов не являетсяЕсли на отрезке Отсюда следует, что выбрать некоторое количество непересекающихся отрезков, то очевидно, что сумма их длин не превзойдет , то есть . . |
Следствие
Можно обобщить неравенство Крафта для случаев, когда кодирующим алфавитом является k-ичный. В доказательстве изменятся некоторые пункты:
- отрезок придется делить не на , а на равных частей,
- соответственно неравенство примет вид: .
Источники информации
- Википедия — Неравенство Крафта
- Теория информации
- Александр Х. Шень Программирование: теоремы и задачи. — М.: МЦНМО, 2007. — С. 208. — ISBN 978-5-94057-310-4