Исследование эффективности статистического (экономного) кодирования

Размещено на http://allbest.ru

Самостоятельная работа

по дисциплине: «Теория электрической связи»

Исследование эффективности статистического (экономного) кодирования

Выполнила:

Студент группы

CTTS-1902

Абдижаббар Диляра

Принял:

Омаров Алмас Тургалиевич

Алматы-2021

Задание на СРС № 2

по дисциплине «Теория электрической связи»

Исследование эффективности статистического

(экономного) кодирования.

Исследовать эффективность статистического (экономного) двоичного кодирования и рассчитать выигрыш от него.

1. Возвести в куб каждую цифру номера студенческого билета (или ID) и составить последовательность десятичных цифр, состоящих из цифр номера и возведенных в куб цифр номера студенческого билета. № 28066

Получим такую последовательность знаков (десятичных цифр):

2, 8, 0, 6, 6, 8, 5, 1, 2, 0, 2, 1, 6, 2, 1, 6;

Здесь 2, 8, 6, 6цифры номера студенческого билета; 8>8=2³, 5, 1, 2>512=8³ , 2, 1, 6>216=6³ , 2, 1, 6>216=6³ .

2. Рассчитать вероятности появления знаков (цифр) в составленной последовательности и составить алфавит источника: встречающиеся в последовательности знаки с указанием вероятностей их появления.

Сумма вероятностей всех знаков должна быть равна единице: ?Р_i=1. В случае незначительного отклонения от этого значения из-за округления, подправить значения вероятности некоторых знаков.

3. Рассчитать энтропию источника (среднее количество информации в одном знаке).

статистический двоичный кодирование

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

5. Составить кодовую таблицу для кода Шеннона-Фано. Определить среднюю длину кодовой комбинации знака и избыточность кода. Полученную в задании последовательность знаков закодировать кодом Шеннона-Фано и рассчитать количество элементов в двоичной последовательности.

6. Составить кодовую таблицу для кода Хаффмена. Определить среднюю длину кодовой комбинации знака и избыточность кода. Полученную в задании последовательность знаков закодировать кодом Хаффмена и рассчитать количество элементов в двоичной последовательности.

7. Сравнить эти коды между собой и сделать выводы по их эффективности. Рассчитать выигрыш даваемый кодами Шеннона-Фано и Хаффмена по сравнению с равномерным кодом для полученной в задании двоичной последовательности.

Все расчеты проводить с округлением результата до сотых долей.

Методические указания к СРС № 2.

Для выполнения задания можно воспользоваться литературой [1, с. 146-155, пример 5.2; 2, 18-37 с.].

Расчет вероятности появления знаков (цифр) в последовательности определяется отношением их количества в последовательности к общему количеству знаков последовательности.

Например, общее количество знаков в приведенной выше последовательности: N_общ=22, количество знаков «5» в последовательности: N_«5»=3. Тогда, вероятность появления знака «5»: P_«5»=N_«5»/N_общ=3/22=0,136. Вероятность появления знака «0»: P_«0»=0, т. к. его нет в последовательности (N_«0»=0). Так нужно сделать для всех знаков, встречающихся в последовательности.

Энтропия источника (знака) определяется по формуле:

Н_зн. = P_i•I_i бит/знак, (1)

где P_i - вероятность появления i-го знака алфавита; I_i = - log₂ P_i - количество информации в i-м знаке.

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

Средняя длина кодовой комбинации для равномерного кода равна самой длине кодовых комбинаций и определяется объемом алфавита источника (количеством знаков источника):

l_ср. = l ? log₂ N_зн, элементов (2)

где N_зн - количество знаков источника.

Округление до целого значения всегда проводить в большую сторону.

Средняя длина кодовой комбинации для неравномерного кода:

l_ср. = P_i•l_i элемент, (3)

где P_i - вероятность появления i-го знака алфавита; l_i- длина кодовой комбинации i-го знака; N_зн- объем алфавита источника (количество знаков источника).

Значение l_ср. необходимо стараться приблизить к энтропии источника.

Избыточность кода определяется по формуле:

? = |(Н_зн- l_ср.)/Н_зн| (4)

Выигрыш экономного кодирования по сравнению с равномерным кодированием определяется отношением средних длин кодовых комбинаций кодов:

В= l_{ср.равн.}/ l_{ср.эконом} (5)

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

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

Составление кодовой таблицы кода Шеннона-Фано производится следующим образом [1- с.151-153, пример 5.2]:

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

- все эти знаки разбивают на две группы: верхнюю и нижнюю так, чтобы суммарные вероятности знаков этих групп были как можно ближе друг к другу;

- для знаков верхней группы в качестве первого символа кодового слова используется «1», а для нижней- «0»;

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

в качестве второго символа кодового слова используется «1» или «0» в зависимости от принадлежности букв верхней или нижней подгруппе;

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

Чем более вероятен знак (цифра), тем быстрее он образует самостоятельную группу и тем более коротким кодовым словом он будет закодирован.

Код Хаффмена считается более оптимальным по минимуму средней длины кодового слова (более эффективным) кодом чем код Шеннона-Фано. Он также является неравномерным, префиксным однозначно декодируемым кодом. При кодировании, в коде Хаффмена происходит сжатие множества из N_зн знаков источника в подмножество из (N_зн -1) знаков и промежуточного знака, далее из (N_зн -2) знаков и промежуточных знаков, ... из 1 промежуточного знака.

Составление кодовой таблицы кода (построение кода) Хаффмена производится следующим образом [1- с.153-155]:

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

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

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

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

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

- проводя линии, объединяющие знаки и образующие последовательные подмножества получаем дерево;

- соответствующие знакам кодовые слова можно составить в обратном порядке, по путям формирования промежуточных знаков (групп знаков); на стыках объединения двух знаков (групп знаков) приписываем ветвям, которые идут вниз, «0», а которые вверх- «1»; и так доходим до каждого конкретного знака.

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

D(l)= P_i•(l_i- l_ср.)² (6)

Список литературы.

1. Передача дискретных сообщений / В.П. Шувалов и др. Под ред. В.П. Шувалова.- М.: Радио и связь, 1990.

2. Аршинов М.Н., Садовский Л.Е. Коды и математика.-М.: Наука, 1983.

Размещено на Allbest.ru