Основной характеристикой дискретного канала связи является скорость передачи данных. При избыточности переданного сообщения скорость передачи уменьшается. Для исключения избыточности сообщения используют математические и программные средства компрессии данных без потери содержания информации, в том числе оптимальное кодирование.
Оптимальное кодирование применяют для того, чтобы:
· сжимать данные (компрессия);
· снижать время передачи данных при той же скорости передачи;
· уменьшить возможные потери и искажения данных;
· архивировать данные, эффективно использовать память.
Основная идея оптимального кодирования лежит в том, что символам сообщения, которые имеют большую вероятность, присваивают короткие бинарные коды, то есть образуются бинарные кодовые слова разной длины – неравномерные коды. Оптимальным неравномерным кодом (ОНК) называется такой код, для которого средняя длина кода есть минимальной.
Такая идея сжатия была применена в азбуке Морзе, где наиболее встречающимся символам соответствовали наиболее короткие коды. Сам алфавит состоял из точек и тире.
Равномерный двоичный код (РДК), корневое бинарное дерево РДК, длина кода РДК, сообщение в РДК
Составление сообщения
Нам дано сообщение:
Х= "Остановите землю, я сойду"
Длина сообщения Lx=24 [символа]
Алфавит сообщения
Найдём алфавит нашего сообщения:
A={о,с,т,а,н,в,и,е,з,м,л,ю,я,с,й,д,у,_. }
Длина алфавита La=21 [символ]
Вероятности
На данном этапе вычисления РДК нам требуется вычислить вероят-ности появления каждого символа в алфавите сообщения. Для этого мы воспользуемся формулой:
pi = vi/ ls
где vi - количество раз, которое символ встречается в сообщении.
Сумма vi должна соответствовать длине исходного сообщения.
Таблица данных, РДК
Таким образом, наше сообщение будет выглядеть:
SРДК=00001000110010001001001100000100111010000010000101000100101000100101011011000110100010011100001000011000001011111000010001
6.1.6 Длина сообщения
Длина сообщения, записанного в РДК равна:
lsрдк = ls · lрдк
где lрдк = 5 бит.
Таким образом, длина сообщения:
lsрдк = 24·5 = 120 бит
Оптимальный неравномерный код ОНК Шеннона-Фано, алгоритм расчета ОНК, средняя длина, энтропия, коэффициент сжатия, коэффициент эффективности, сообщение в ОНК, критерий Фано, корневое бинарное дерево ОНК Шеннона-Фано
Расчёт ОНК
Оптимальный неравномерный код (ОНК) мы будем рассчитывать по методу Шеннона-Фано, который ещё называют методом бисекции.
Для вычисления ОНК вся работа разбивается на несколько этапов.
Предварительный шаг: вероятности появления символа в сообщении ранжируются по убыванию.
Шаг первый: все вероятности разбиваются на две равновероятные группы. Символам верхней секции назначим 0, символам нижней секции – 1. Первый бит ОНК вычислен.
Шаг второй: каждую группу делим на две равновероятные подгруппы. Верхним подгруппам присваивается 0, нижним – 1. и т. д.
Деление заканчивается, когда в подгруппе остаётся один символ.
Нахождение ОНК
Критерий Фано однозначного декодирования ОНК: ни одно слово ОНК не является началом другого слова ОНК. Это ещё называется свойством префиксности.
Критерий Фано позволяет однозначно декодировать сжатое сообщение SОНК . Сообщение в ОНК будет выглядеть:
SОНК=111101100101010111111011010110010011000110010011000010000011001010010010011010111100010001100000
Характеристики ОНК
1. Средняя длина ОНК
Lcp.онк= 4.23 [бит]
2. Энтропия ОНК
H(A)= 1,18 [бит/символ]
3. Максимальная энтропия
Hmax= log 17= 4,08 [бит/символ]
4. Относительная энтропия
5. Информационная избыточность
6. Абсолютная недогруженость
7. Коэффициент сжатия
Кс = 1- Lcp.онк/ LРДК = 0,15 = 15 %
8. Коэффициент эффективности Кэ
Кэ=Н/ Lcp.онк = 0,27
Эффективность ОНК тем выше, чем больше средняя длина ОНК стремится к энтропии.
Дата: 2019-12-22, просмотров: 516.
