Если дан код и надо определить, взаимно однозначны ли элементарные его коды:

• Если длины одинаковы, то сразу взаимно однозначный.
• Если префиксный, то взаимно однозначный.
• Нарисуем двоичное дерево кодов:
  • Закрасим вершину, которая является элементарным кодом
  • Промежуточные просто белые
  • Если в какую-то чёрную вершину можно попасть только через белые, то префиксный ⇒ взаимно однозначный

Длина кодов

Если длины кодов одинаковые, то очевидно, что кодирование взаимно однозначное.

Из разной длины тоже может быть взаимно однозначным, если он является префиксным, об этом ниже.

Префиксный код

Если код является префиксным, то он является взаимно однозначным.

Обратное неверно.

Неравенство Крафта-Макмиллана

Кратко: суммируем дроби вида

$$ \frac{1}{q^{|u_i|}} \newline \text{, где q - мощность алфавита кодирования} \newline u_i \text{ есть iый элементарный код} $$

Мокеев Д.Б. - Лекции по дискретной математике

Обратите внимание, что это условие необходимое, но не достаточное. То есть, неравенство может быть выполнено и для тех, которые не являются взаимно однозначными.

Неравенство (теорема) Крафта

Мокеев Д.Б. - Лекции по дискретной математике

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