Теория информации

1.3.2. Префиксные коды. Средняя длина кода Понятие. Префиксные коды - это такие коды, в которых ни одна более короткая комбинация не является началом более длинной комбинации, а это позволяет производить однозначное декодирование, даже если последовательность кодов не содержит разделителей между кодами. Большинство кодов применяются для передачи и хранения информации без учета статистических характеристик поступающих сообщений. Учитывая статистические свойства источника сообщений, можно минимизировать среднюю длину кодовых сообщений. Рассмотрим примеры кодирования . Понятно, что кодирование информации допускается тогда, когда возможно последующее однозначное декодирование: Символ Код1 Код2 Код3 Код4 x 1 0 0 0 0 x 2 0 00 01 10 x 3 1 1 011 110 x 4 11 11 0111 111 Видно, что код 1 не дает однозначного декодирования. Код 2, хотя и выражен более тонким образом, обладает тем же недостатком, так как при передаче последовательности x 1 x 1, она будет закодирована в 00, что совпадает с кодовым словом для x 3 . Коды 1 и 2 не являются, таким образом, различимыми. Код 3 также не позволяет производить однозначное декодирование. Определение. Однозначно декодируемыми являются только коды обладающие свойством префикса. Коды 1,2,3 не обладают свойством префикса, а код 4 обладает. Пример 1.17 , код 0111100 декодируется в последовательность символов x 1 x 4 x 2 x 1 . Разобьем дерево на уровни и тогда каждому коду можно присвоить определённый вес: