Теория передачи сигналов (2 часть)
.pdf
Стафеев Алексей Валерьевич
К.т.н., доцент
1
Теория
передачи
сигналов
Второй семестр
2
Статистическое кодирование источника информации
1.Алгоритм статистического кодирования Шеннона - Фано.
2.Алгоритм статистического кодирования Хаффмана.
3.Статистическое кодирование источника при группировании символов.
4.Префиксные коды.
5.Неравенство Крафта.
6.Недостатки системы эффективного кодирования.
7.Контрольные вопросы.
3
Уменьшение избыточности статистическим кодированием. Коды Шеннона—Фано и Хаффмана
Статистическое кодирование используется для исключения (существенного уменьшения) избыточности сообщений, обусловленной неравновероятностью элементов. Уменьшение избыточности сообщений называют также
сжатием.
( ) < 1 |
( ) ≈ 1 |
ИИ 
КИ
Исходное |
Сжатое |
сообщение |
сообщение |
(Значение энтропии соответствует двоичному сообщению)
4
|
|
Пример |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
Задано буквенное сообщение: |
|
|
|
|
«аттестат» |
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Алфавит: (а, т, е, с); |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Число букв алфавита: |
= 4; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Длина сообщения: |
= 8. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Вероятности |
|
|
|
( ) 2 |
|
|
|
(т) |
4 |
|||||||||||||||||||
|
(а) = |
|
|
|
= |
|
|
; т = |
|
|
|
|
|
= |
|
|
; |
|||||||||||
появления букв: |
|
|
|
8 |
|
|
|
8 |
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
е = |
е |
= |
1 |
; (с) = |
(с) |
= |
1 |
. |
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
8 |
|
|
|
|
|
|
|
|
8 |
|
||||||||||||
Проверка: |
|
|
|
|
|
|
2 |
4 |
1 |
|
1 |
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
а + т + е + с = 8 + 8 + 8 + 8 = 1 |
||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||
5
Пример
Определим энтропию:
= − (а) log2 а − (т) log2 т − (е) log2 е |
− (с) log2 с |
|||||||||||||||||
= − |
2 |
log2 |
2 |
− |
4 |
log2 |
4 |
− |
1 |
log2 |
1 |
− |
1 |
log2 |
1 |
= 1.75, |
бит/букву |
|
|
8 |
8 |
8 |
8 |
8 |
|
|
|||||||||||
8 |
|
|
|
|
|
|
8 |
8 |
|
|
||||||||
Количество информации: |
= = 8 1.75 = 14, |
бит |
||||||||||||||||
Максимальная энтропия:
0 = = log2 = log2 4 = 2 , бит/букву
6
Пример
Избыточность сообщения:
= 0 − = 2 − 1.75 = 0.125 (12.5%)0 2
- показывает, какая часть сообщения является избыточной по сравнению с соответствующим ему оптимальным.
Коэффициент сжатия:
1.75сж = 0 = 2 = 0.875
- показывает, насколько данное сообщение отличается от соответствующего ему оптимального.
7
Пример
Произведём кодирование букв сообщения равномерным двоичным кодом. Для этого требуется = log2 4 = 2 двоичных символа на букву.
Кодирование может быть выполнено так:
|
А |
Т |
|
Т |
Е |
С |
|
Т |
А |
Т |
|
|
|
|
|
|
|
|
|
|
|
|
00 |
01 |
|
01 |
10 |
11 |
|
01 |
00 |
01 |
|
|
|
|
|
|
|
|
|
|
|
Длина двоичного сообщения с |
|
рав=16 бит. |
||||||||
равномерным кодом: |
|
|
|
|||||||
Количество двоичных разрядов, приходящихся на каждую букву исходного сообщения:
qа= qт=qе= qс=2
8
Пример
На кодирование всего сообщения теперь потребуется символов двоичного алфавита (бит).
Средняя длина одной буквы исходного сообщения после кодирования равномерным кодом:
|
= |
бит/букву |
ср |
|
|
|
=1 |
|
ср = 2 |
2 |
+ |
4 |
+ |
1 |
+ |
1 |
= 2, бит/букву |
||
|
|
|
|
|
||||||
8 |
8 |
8 |
8 |
|||||||
|
|
|
|
|
||||||
9
Пример
Остаточная избыточность после кодирования равномерным кодом (результат кодирования):
|
= |
ср − |
= |
2 − 1,75 |
= 0,125 − или 12.5 %. |
|
|
||||
ост |
|
ср |
2 |
|
|
|
|
|
|||
ост = – изменений не произошло.
Lср – имеет физический смысл энтропии, полученной после кодирования.
H – имеет физический смысл минимального среднего количества двоичных разрядов, необходимых для кодирования букв сообщения.
При «идеальном» статистическом кодировании Lср → H.
10