Файл: Толстоусов, Г. Н. Прикладная теория информации учеб. пособие.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.10.2024
Просмотров: 75
Скачиваний: 0
|
|
к - Ш } ~ н(м |
(10. 2) |
|
|
|
П(р У(г ) ~ &ут ■ |
равном т . |
|
Будем вычислять все логарифмы при основании, |
||||
Тогда |
(10.2) |
примет |
вид |
|
|
|
|
«ср Н(Х) . |
|
В |
общем |
случае, |
когда нельзя провести деления |
на равнове |
роятные группы, для сродней длины кодовой комбинации имеем со отношение (Ю Л ), где при вычислении энтропии основание лога рифма равно пг (числу сигналов передатчика).
Уточним соотношение (Ю Л ). Найдем ограничение сверху для значения , Для этого рассмотрим процедуру составления оп тимального неравномерного двоичного кода, предложенную К.Шен ноном.
1. Все сообщения располагаются в порядке убывания вероят ностей.
2. Вероятности квждого сообщения записываются в двоичной ' системе счисления.- Оставляется старшая единица и предшествую щие ей до запятой нули. Остальные цифры отбрасываются. Получен ное число назовем оценкой.
3. Кодовой комбинацией сообщения является сумма сценок предыдущих сообщений. Если разрядность кодовой комбинации со общения меньше разрядности оценки этого сообщения, она дополня ется нулями так, чтобы указанные разрядности совпадали. Послед няя кодовая комбинация нулями не дополняется.
|
|
|
|
Таблица |
10.2 |
I |
Рі |
Рі |
Pc |
|
К о д |
2 |
3 |
ф |
5 |
6 |
|
■*, |
0,5625 |
0,Ю 0І |
I |
0 |
0 |
х } |
0,1875 |
0,0011 |
001 |
I |
100 |
0,1875 |
0,0011 |
001 |
ЮІ |
IOI |
|
|
0,0625 |
0,0001 |
0001 |
ІЮ |
по |
Д4
В табл. 10.2 показана процедура построения кода для четы рех сообщений X f—Хч. В графе 2 указаны вероятности сообща - ний. В графе 3 эти вероятности указаны в двоичной системе. В графе 4 приведена оценка. Поскольку все вероятности меньше еди ницы, цифра "О" до запятой как признак кодовой комбинации явля ется лишней. Так как кодовые комбинации образуются сложением оценок, то в оценках достаточно оставить одну старшую единицу, чтобы кодовые комбинации отличались друг от друга. В графе 5 указаны суммы оценок предыдущих сообщений.' Для сообщения осг разрядность суммы меньше разрядности оценки и сумма должна
быть дополнена нулями. Действительно, код |
" I й не |
может быть |
кодом сообщения х^ , так как он будет |
началом |
по крайней |
мере следующей кодовой комбинации. Этого не произойдет, если разрядности оценки и кодовой комбинации будут совпадать. В гра фе б указаны коды сообщений. Заметим, что код Шеннона моаѳт иметь несколько большую среднюю длину кодовой комбинации по сравнению с кодом Фано, Оценим среднюю длину кодовой комбина ции. Для вероятности каждого сообщения справедливо неравенство
|
-f |
/ |
|
|
('0.5} |
|
|
I G ’ |
|
|
|
|
|
|
|
|
|
где 4 |
- номер позиции |
старшей единицы. |
хй в |
|
|
Длина кодовой комбинации |
сообщения |
соответст- |
|||
вии с процедурой построения кода |
Шеннона равна 6С . Например, |
||||
согласно |
табл. 10.2 |
|
|
|
|
Длина кодовой комбинации сообщения |
равна |
трем. |
|||
Неравенство (10.3) |
приводится к следующему виду: |
||||
Умножая все части неравенства на вероятность сообщения Рі и суммируя неравенства почленно для всех сообщений, полу
чим
45
Учитывая, что средняя длина кодовой комбинации равна
П,
подучим
кср Н(JC)^ ~У.
Следовательно, средняя длина ограничена значениями
H(Xb -I > Кср * H(X) . Ü°-s)
В худшем случае составления оптимального кода, когда со стояния делятся на группы, сильно отличающиеся по вероятности,
средняя длина кодовой |
комбинации превышает величину энтропии |
|
не более, чем на один |
разряд. Однако при кодировании блоков со |
|
общений средняя длина |
оптимального кода макет быть приближена |
|
сколь угодно близко к |
энтропии |
источника. |
Пусть кодируются |
блоки из |
М независимых сообщений. Тог |
да энтропия блока |
|
|
Средняя длина кодовой комбинации Kqo(A/), кодирующей блок из /V сообщений, согласно (10.5) ограничена следующими значе ниями:
|
|
Hj-+ У > |
|
(hl) Ъ Hj- . |
|
|
|
Разделим |
все |
части неравенства |
на |
N |
. Учитывая соотно |
||
шение (10 .6), |
получим |
|
|
|
|
|
|
Н(Х) + ^ > 2 з $ £ * Н ( Х ) . |
(Ю.7) |
||||||
Приходящаяся на одно |
сообщение |
средняя длина |
|||||
|
|
|
_ |
Kcp(/Zl |
|
|
|
|
|
пср- |
д / |
• |
|
|
|
Выбирая |
А/ |
большим, |
вместо (10.7) |
можно записать |
|||
|
|
кср = Н(Х.) + £ , |
|
|
(ш ) |
||
46
где £ - сколь угодно малая величина.
Таким образом, энтропия источника определяет количество сигналов передатчика, необходимых в среднем для кодирования од ного сообщения источника.
В процессе составления оптимального кода по методу Фано необходимо разбивать состояния источника на примерно равноверо ятные группы и подгруппы. При этом на различных этапах деления часто появляется неопределенность. Можно сделать большей по ве роятности как верхнюю, так и нижнюю подгруппы. При этом средняя длина кода может оказаться разной. Построенный таким образом код может оказаться не самым лучшим.
От указанного недостатка свободна методика Хаффмена. Она гарантирует однозначное построение кода с наименьшей для данно го источника средней длиной кода. Для двоичного кода методика следующая.
1. Все сообщения располагаются в порядке убывания вероят ностей.
2 . Два последних сообщения объединяются в одно вспомога тельное, которому приписывается суммарная вероятность. Оставши еся сообщения и вспомогательное располагаются в порядке убыва ния вероятностей в дополнительном столбце.
3. Два последних сообщения дополнительного столбца объеди няются и т .д . Процесс продолжается до тех пор, пока не получим единственное вспомогательное сообщение.
4 . Построение кодовой комбинации начинается с предпослед него дополнительного столбца. Верхнему состоянию, входящему в объединение, приписывается сигнал 0, нижнему - I . В следующем слева столбце состояниям, входящим в объединение, добавляется
сигнал 0 (для верхнего состояния) и I |
(для нижнего). |
|
|||
Методика Хаффмена поясняется примером. Процесс объединения |
|||||
сообщений |
во вспомогательные показан |
в табл. 10.3, |
а процесс |
||
составления кода на рис. 10.I . |
|
|
|
||
Таким образом, получены следующие кодовые комбинации: |
|||||
X ,- 00; |
X j - 01; |
.£ ,- 1 1 ; |
х у -Ю 0 ; |
-?■- |
Ю І. |
Сравнивая результаты, |
изложенные |
в § 9 и 10, |
можно |
сделать |
|
следующий вывод. Если кодировать сообщение, не обращая внимания на статистические свойства источника, т .е . рассматривая все со общения равноправными или равновероятными, то длина кодовой
4?
комбинации
где гь - |
|
K = fymn = Hrru^ |
(М ) |
число |
сообщений; |
|
|
пь - |
число |
сигналов передатчика. |
|
|
|
Таблица |
10.3 |
При опти мальном кодиро вании, учитыва ющем статистиче ские свойства источника, сред няя длина кодо вой комбинации мокет быть сде лана равной эн тропии источни ка -
Ку = Н(Х) . |
Ш іо) |
Таким образом, достигаемый при оптимальноі кодировании выигрыш
и
rrmcLX-нет (іО.11) mjx-x
^8