Способы кодирования источника:

Примитивное кодирование:

При примитивном кодировании символы алфавита источника представляются набором чисел от 0 до (K −1) (K — объём алфавита источника), т.е. нумеруются. При этом номер представляется в виде n-разрядного

m-позиционного кода, где

Примитивные коды являются равномерными, т.е. каждый символ

исходного алфавита содержит фиксированное количество кодовых позиций (кодовая комбинация имеет фиксированную длину).

Примитивный код широко используется в компьютерной технике для

представления символов и знаков текста («набор символов», «кодировка»). Примеры:

1. ASCII (American Standard Code for Information Interchange) — американская стандартная кодировочная таблица: 7-битная таблица для представления печатных символов и некоторых специальных кодов.

2. Национальные 8-битные варианты ASCII — для кириллицы это Windows-1251 (CP1251), КОИ-8, IBM code page 866 (CP866)

Неравномерное кодирование:

Код, комбинации которого имеют различную длину, называют неравномерным. Для неравномерного кода встаёт вопрос однозначности декодирования. Однозначность может быть обеспечена при помощи специального символа-разделителя (как в коде Морзе), однако, это не оптимально. Без разделителя можно обойтись, если ни одно кодовое слово не

является началом другого. Коды, обладающие таким свойством, называют префиксными.

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

один символ источника определяется пределом Шеннона:

m — позиционность кода.

Одним из первых экономных кодов, использующих принцип энтропийного кодирования, является код Шеннона-Фано.

Префиксные коды, неравенство Крафта.

Код, обладающий тем свойством, что никакое кодовое слово не является началом (префиксом) другого кодового слова, называется префиксным. Для построения префиксных кодов используется двоичное дерево.

Для построения кода каждому ребру, выходящему из узла, называемого порождающим, необходимо приписать бит кода (ноль для левого ребра и единицу для правого). Каждый узел i-ого уровня (i=0,…,n) потенциально может породить ровно 2^n-i узлов последнего уровня n. Листья дерева (оконечные узлы) соответствуют символам кодируемого источника причем уровень соответствующего узла в дереве равен длине битового кода R_k .

Неравенство Крафта: Пусть у нас есть n символов, кодовые слова которых имеют длины . Тогда необходимое и достаточное условие существования префиксного кода в r-ичном алфавите для данных символов, состоит в выполнении неравенства: (r – число символов).

Неравенство Крафта легко доказать с помощью дерева декодирования. Рассмотрим случай двоичного алфавита.

Если максимальная длина пути на дереве равна 1, то на нем есть одно или два ребра длины 1. Таким образом, либо 1/2⩽1 — для одного символа источника, либо 1/2+1/2⩽1 — для двух символов источника.

Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше n−1. Докажем, что оно справедливо и для всех деревьев высоты меньше n. Для данного дерева максимальной высоты n ребра из первой вершины ведут к двум поддеревьям, высоты которых не превышают n−1; для этих поддеревьев имеем неравенства K₁⩽1 и K₂⩽1, где K₁, K₂ — значения соответствующих им сумм. Каждая длина l_i в поддереве увеличивается на 1, когда поддерево присоединяется к основному дереву, поэтому возникает дополнительный множитель ½. Таким образом, имеем (½)*K₁+(½)*K₂⩽1.

В случае произвольного недвоичного основания r имеется не более r ребер, исходящих из каждой вершины, то есть не более r поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель 1/r.