J tech 120. indd

Keywords: information, coding, Kraft — McMillan inequality, data compression, effectively coding, prefix code
Введение
Известно много алгоритмов кодирования инфор-
мации, основанных на различных принципах. Например, 
методы Шеннона-Фано, Хаффмана, Лемпела-Зива, 
арифметическое кодирование, Гилберта-Мура, «Стопка 
книг» и другие. Из них метод Хаффмана оптимален в от-
ношении минимизации средней длины кодового слова. В 
настоящей статье разработан новый метод кодирования 
и упаковки информации на основе неравенства Крафта. 
Этот метод имеет ряд преимуществ по сравнению с ме-
тодом Хаффмана:
— алгоритм достаточно прост и нагляден, не требует 
сложных математических расчётов;
— кодирование информации этим методом не является 
однозначным, а имеет много вариантов кода, что по-
зволяет обеспечить дополнительную защиту инфор-
мации.
Тестирование показало, что при условии выполнения 
неравенства Крафта для всех длин кодовых слов, мини-
мальная средняя длина кодового слова по разработан-
ному алгоритму такая же, как и по методу Хаффмана, 
а значит разработанный метод можно считать опти-
мальным.
Описание метода кодирования на основе 
неравенства Крафта
В теории кодирования, неравенство Крафта даёт не-
обходимое и достаточное условие существования разде-
лимых и префиксных кодов, обладающих заданным на-
бором длин кодовых слов.

---

2
Те
хника.
 Те
хнологии.
 Инж
енерия 
№ 
2 (12) 
2019
Теорема Крафта: Если целые числа 
N
i
l
l
l
,...,
,...,
1
удовлетворяют неравенству:
1
1
≤
∑
=
−
N
i
l
Y
i
m
(1)
то существует код, обладающий свойством префикса 
с алфавитом объема, длины кодовых слов в котором 
равны этим числам. Обратно, длины кодовых слов лю-
бого кода, обладающего свойством префикса, удовлет-
воряют указанному неравенству.
Пусть заданы кодируемый и кодирующий алфавиты, 
состоящие из n и d символов, соответственно, и заданы 
желаемые длины кодовых слов 
N
i
l
l
l
,...,
,...,
1
, тогда не-
обходимым и достаточным условием существования раз-
делимого и префиксного кодов, обладающих заданным 
набором кодовых слов, является выполнение неравен-
ства (1).