2.2. Основные характеристики эффективных кодов

Коэффициент относительной эффективности

,

(2.1)

где энтропия источника сообщений;

- средняя длина кодового слова.

Коэффициент статистического сжатия

.

(2.2)

2.3. Задачи к разделу 2

1. Дискретный источник выдает символы из ансамбля с вероятностями, приведенными в табл. 1.1. Закодировать символы данного ансамбля кодом Хаффмена, кодом Шеннона-Фано и равномерным кодом. Определить среднюю длину кодовой комбинации и сравнить с энтропией сообщения. Показать, какой код является наиболее эффективным.

2. Используя коды Хаффмена и Шеннона-Фано, закодировать сообщения:

а) a b a b c d d a a e;

б) a b b b c d d a a e;

в) a b c d e f g h i a b c d e f g h a b c.

г) a a a b b b c d d e e e e e f;

д) a а а а а b b b b b c d e f g.

Вычислить коэффициенты статистического сжатия и относительной эффективности.

3. Построить троичный код методом Хаффмена или Шеннона-Фано для передачи 10 сообщений с вероятностями появления:

а) 1/32, 1/8, 3/32, 1/16, 3/32, 1/16, 1/8, 3/32, 1/4, 1/16;

б) 1/32, 1/32, 1/32, 3/32, 1/8, 1/8, 1/8, 1/8, 1/16, 1/4;

в) 1/32, 1/32, 1/32, 1/32, 1/8, 1/8, 1/8, 1/16, 1/16, 1/16, 1/16, 1/4;

г) 1/32, 1/16, 1/32, 1/8, 1/8, 1/8, 1/16, 1/16, 1/16, 1/16, 1/4;

д) 1/32, 1/32, 1/32, 1/32, 1/4, 1/8, 1/16, 1/16, 1/16, 1/16, 1/4.

4. Найти код Лемпела-Зива для двоичной последовательности источника:

а) 000100100000011;

б) 101100111000111;

в) 111110000011111;

г) 110000011000001;

д) 010011111000001;

е) 100010000011000;

ж) 100000000000010;

з) 1111111110000011;

и) 1010101010111111;

к) 1101111110000011;

Определить коэффициент сжатия.

3. Помехоустойчивое Кодирование

3.1. Основные характеристики помехоустойчивых кодов

Для помехоустойчивыми кодов общее количество кодовых комбинаций удовлетворяет неравенству

,

(3.1)

где - основание кода, - количество элементов в кодовой комбинации.

Количество разрешенных кодовых комбинаций, используемых для кодирования, равно

.

(3.2)

Количество запрещенных кодовых комбинаций:

(3.3)

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

Избыточность равномерного блочного кода:

.

(3.4)

Относительная скорость кода:

1- .

(3.5)

Кодовое расстояние между двумя кодовыми комбинациями есть число одноименных разрядов в этих кодовых комбинациях с различными символами.

Для бинарных кодов кодовое расстояние определяется подсчетом числа единиц суммы по модулю два двух кодовых комбинаций.

Коэффициент ложных переходов определяет вероятность ложного перехода одной кодовой комбинации в другую под влиянием помех кратности :

,

(3.6)

где - общее число кодовых векторов, отстоящих друг от друга на кодовое расстояние .

Количество обнаруживаемых ошибок:

(3.7)

Количество исправляемых ошибок:

, для - четного; , для - нечетного.

(3.8)