4.7. Неравенство Макмиллана

Неравенство Крафта применимо к мгновенным кодам, которые являются частным случаем однозначно декодируемых кодов. Макмиллан показал, что такое же неравенство справедливо для однозначно декодируемых кодов. Основная идея доказательства необходимости состоит в том, что число, превышающее 1, очень быстро возрастает с увеличением степени, в которую оно возводится. Если рост можно ограничить, то это означает, что число не превышает 1. Доказательство достаточности следует из того, что его можно провести для мгновенных кодов, являющихся частными случаями однозначно декодируемых кодов.

Доказательство необходимости начинается с рассмотрения выражения

Разложив выражение в скобках, получим сумму многих членов, каждый из которых включает в некоторой степени; показатель степени изменяется от наименьшего значения до

наибольшего где — наибольшая длина кодового слова. Таким образом, получаем выражение

где число кодовых слов (с основанием ) длины Поскольку код обладает однозначным декодированием, не может быть больше, чем где число различных последовательностей длины составленных из букв кодового алфавита с основанием Поэтому получаем неравенство

появляется потому, что нужно учесть как первый, так и последний член в сумме). Это — искомое неравенство, поскольку для любого при достаточно большом имеем Поскольку можно выбрать достаточно большим, получаем, что число К (сумма Крафта) не превышает 1.

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