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

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

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

Таким образом, выполнение условия необходимо для префиксно свободной системы изкодовых слов над -буквенным алфавитом с длинами .