ИННОВАЦИИ БИЗНЕСУ

Результат выполнения научно-исследовательской работы.

Пусть имеется система из кодовых слов над -буквенным алфавитом с длинами букв. Обозначим: ; ряд и его частичную сумму ; - количество последовательностей кодовых слов длиной букв; - количество последовательностей кодовых слов длиной букв; ряд и его частичную сумму .

Теорема 1. . (1)

Доказательство. Заметим, что есть производящая, для подсчёта , функция: . Тогда .

Следствие 1. Ряд сходится только если , и предел суммы ряда равен : . (2)

Доказательство. Ряд сходится и только при .

Лемма 1. , где , . (3)

Доказательство. Заметим, что после раскрытия скобок содержит слагаемые вида : 1) для всех комбинаций длин , дающих в сумме ; 2) некоторую часть, но, в общем случае, не все, комбинации, дающие в сумме ; и не содержит 3) ни одного слагаемого с показателем большим . Поэтому , где , что доказывает . Поскольку все коэффициенты , входящие в выражение для , не превышают : , , то , и, значит, .

Лемма 2. Если все последовательности кодовых слов с длинами не превосходящими могут быть однозначно декодированы, то . (4)

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

Теорема 2. Для того, чтобы система кодовых слов над -буквенным алфавитом с длинами букв допускала однозначное декодирование всех последовательностей, длина которых не превосходит букв, при любом , необходимо, чтобы длины кодовых слов системы удовлетворяли неравенству Крафта .

Доказательство. Положим , где . Комбинируя (3) и (4) получим: . Так как , то требуется , и, следовательно, .