ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.10.2024
Просмотров: 63
Скачиваний: 0
сообщением, чтобы на входе линии связи кодовые симво лы встречались одинаково часто.
Задача 11. Для передачи 8 равновероятных |
сообще |
|||||
ний используется двоичный код. Длительности |
кодовых |
|||||
символов одинаковы и равны 10“ Gс. Сообщения кодиру |
||||||
ются в соответствии с табл. 12. |
|
|
||||
|
|
Т а б л и ц а 12 |
Показать, |
что вероятности по |
||
|
|
явления кодовых символов оди |
||||
Сооб |
|
Сооб |
|
наковы. |
Вычислить |
скорость |
Код |
Код |
передачи сообщений. |
|
|||
щение |
щение |
|
||||
Р е ш е н и е. По формуле
*1 |
111 |
Хь |
011 |
А'о |
ПО |
Xq |
010 |
*3 |
101 |
|
001 |
-V» |
100 |
*8 |
000 |
£ |
Р { хдМц |
т = - ¥ |
-------------• |
2 |
ңхл N |
/=1 |
|
где Mfj— число кодовых символов уу |
в і-й кодовой ком |
|||||||||
бинации; |
— число всех |
кодовых |
символов в/-й кодо |
|||||||
вой |
комбинации; у і = |
0; |
у2= 1 ; |
находим |
вероятность |
|||||
встретить единицу на входе линии связи: |
|
|
||||||||
|
|
|
0,125(34-2 + 2 + 1 4-2-М -И ) |
_ |
1 |
|||||
|
|
|
0,125(3 + 3+ 3+3 + 3 + 3 + 3+ 3) |
2 |
||||||
Таким образом, |
Р( 1) = Р { 0) = 1/2. |
|
|
|
|
|||||
Скорость передачи найдем по формуле (3.21) преды |
||||||||||
дущей задачи: |
|
|
|
|
|
|
|
|
||
|
|
|
2 — 106lo g 2 = 10б |
(бпт/с). |
|
|
||||
Эта |
скорость передачи |
максимальна |
(см. |
замечание к |
||||||
предыдущей задаче), т. е. І — С. |
|
|
|
задачи изменим |
||||||
Задача 12. В условиях предыдущей |
||||||||||
вероятности появления сообщений: |
|
|
|
|
||||||
|
Р(Хі) = Р(х2) = |
0,25; Р(хъ) = |
Р(х<) =0,125; |
|||||||
|
|
Р (х5) = |
Р(х6) —Р ( х 7) = |
Р (хв) = |
0,0625, |
|||||
оставив все остальное без изменений. |
|
|
|
|||||||
Р е ш е н и е . |
По формуле (3.19) |
предыдущей задачи |
||||||||
|
|
|
0,25-5+0,125-3 + 0,0625-4 |
__ 0 fiOE- |
||||||
|
|
— 0,25-6+0,125-6+0,0625-12 |
|
’ |
’ |
|||||
|
|
|
Я(0) = |
1—Р(1) =0,375. |
|
|
||||
70
Скорость передачи сообщений определим по формуле
7 = Н(Х)
<-> ’
где < 0 > — средняя длительность сообщения:
< " > = 2 |
р (х ‘)= з ѵ |
/=1
Так как энтропия источника сообщений
Н(Х) =» — V Р(хі) log P(x'i) = 2,75 (бит), 1-1
ТО
7 = ~О *0 — 0,917-10° = 917000 (бит/с).
Таким образом, скорость передачи сообщений уменьши лась с 106 бит/с до 917000 бит/с. Это произошло потому, что при кодировании мы не учитывали изменившуюся статистику сообщений. Как ее учесть, чтобы скорость пе редачи сообщений стала максимально возможной, пока жем в следующем параграфе.
§3. Экономное кодирование сообщений
вотсутствие шума
Под кодированием будем понимать представление а различных сообщений xt , выдаваемых источником, в не котором стандартном кодовом алфавите, содержащем т различных символов. Если т < п , каждому возможному сообщению источника необходимо ставить в соответствие некоторую последовательность символов кодового алфа вита, которую назовем к о д о в ы м с л о в о м.
Если среди кодовых слов, сопоставляемых п сообще ниям источника, нет одинаковых и ни одно более длинное кодовое слово не содержит в начале себя более короткое, такие кодовые слова назовем н е п е р е к р ы в а е м ы м и. Если кодовые слова непер,екрываемы, по произвольной по следовательности кодовых слов взаимнооднозначно выде: ляется соответствующая ей последовательность сообще ний источника. Другими словами, в отсутствие шумов взаимная однозначность операций кодирования и декоди рования достигается при условии неперекрываемости ко довых слов.
Операция кодирования тем более экономична, чем меньшей длины кодовые слова сопоставляются сообще ниям. Поэтому за характеристику экономичности кода примем среднюю длину кодового слова
L = 2 Ѵ-і Р(хі)> ■
/=1
где \}<і — длина кодового слова, сопоставляемая .ѵ/ сооб щению.
Общие положения теории информации позволяют ука зать оптимальные границы для средней длины L кодовых слов, которые ни при каком кодировании не могут быть уменьшены. Установим эти оптимальные границы для L из следующих соображений. Во-первых, количество ин формации, несомое кодовым словом, не должно быть меньше количества информации, содержащегося в соот ветствующем сообщешіи, иначе при кодировании будут происходить потери в передаваемой информации. Во-вто рых, кодирование будет тем более экономичным, чем большее количество информации будет содержать в себе каждый кодовый символ; это количество информации максимально, когда все кодовые символы равновероят ны, и равно logm. При этом і-е кодовое слово будет нести
количество информации, |
равное |
logm: |
||
Таким образом, |
|
|
|
|
— lo g Р(Х[)^Щ logm, |
||||
откуда |
— log P(Xj) |
|
||
> |
(3.22) |
|||
|
log т |
|||
|
|
|
||
Умножив обе части последнего |
равенства на Р(хі) и |
|||
просуммироівав по -всем і от 1 до п, получим |
||||
|
^min |
Н{Х) |
|
|
|
log т * |
|||
Так как правая часть неравенства (3.22), как правило, не является целым числом, для достижения знака равенст-. ва в нем (с учетом экономности кода) необходимо, чтобы
log P(Xj) " |
+ |
1, |
(3.23) |
|
log т |
||||
|
72
где квадратными скобками обозначена целая часть числа, стоящего в них. Усредняя (3.23), получаем
- щ х у
LШІП< log т
Таким образом,
ЩХ) / / |
. ^ |
н(Х) |
|
(3.24) |
|
log т ^ |
min ^ |
log т |
' |
||
|
Осталось, однако, невыясненным, будут ли кодовые слова, удовлетворяющие неравенствам (3.24), неперекрываемы. Поэтому докажем последнее неравенствострого. _
Теорема Крафта. Если. |
\><п— длины кодовых |
|
слов, соответствующих сообщениям х\, х2, |
хп, то необ |
|
ходимым и достаточным условием существования иеперекрываемых кодовых слов с заданными-длинами является выполнение неравенства
|
|
У, nC*k < 1 , |
|
|
(3.25> |
|
|
|
k=i |
X |
|
|
|
где m — число |
различных символов |
в |
кодовом алфа |
|||
вите. |
|
|
|
что |
если |
кодовые- |
Н е о б х о д и м о с т ь . Докажем, |
||||||
слова с заданными длинами |
[xt, ..., |
неперекрываемьц |
||||
то неравенство |
(3.25) справедливо. Для этого обозначим |
|||||
через К число кодовых слов |
(среди заданных) |
длиной в- |
||||
k символов. |
|
|
|
|
|
|
І і < т \ |
|
|
|
|
|
|
/2 < |
(пь— 1\) т — т2 — Іхт\ |
|
|
|
||
h < |
\(т |
— /2] т = пь3 — Ілт2 — 12пь\ |
-(3.26) |
|||
./г</7гг — lxmr 1 — l2mr 2 — ... — /г_і/7г.
Эти условия являются необходимыми и достаточными для неперекрываемости кодовых слов. Разделив послед нее неравенство на тг, получим
2 k m ~ k < ! . |
(3.27)' |
Распишем сумму, |
стоящую в левой |
части |
неравенства |
|||||
(3.27): |
|
|
|
|
|
|
|
|
|
2 1кп Г к = Іігпх+ |
l2m2 -f- ... -f lrmr = |
|
|||||
|
k=l |
|
|
|
|
|
|
|
= w -f" • • • Ч- ^ “b in2-f* |
... -)- ш2 -p .• • |
rnr —(—... —|—tnr = |
||||||
'------------------ - |
4 |
s |
' |
4 |
.I—V |
/ |
||
11 |
раз |
/2 |
раз |
|
|
lr раз |
|
|
|
|
= 2 |
т~"к ’ |
|
|
(3.28) |
||
г |
|
/ѵ*= |
1 |
|
|
|
|
|
4 = п — число кодовых слов (в последней сум- |
||||||||
так как 2 |
||||||||
k=\ |
|
|
|
|
|
(3.28) |
||
ме возможны одинаковые слагаемые). Подставив |
||||||||
в (3.27), получим |
|
|
|
|
|
|
||
|
|
V m-'uk < 1 , |
|
|
(3.29) |
|||
|
|
k—\ |
|
|
|
|
|
|
что и требовалось доказать. |
|
|
|
|
||||
Д о с т а т о ч н о с т ь . |
Дано неравенство |
(3.25); |
требу |
|||||
ется доказать, что всегда можно найти кодовые слова с длинами [аь которые неперекрываемы.
Легко перейти от неравенства (3.29) к неравенству (3.27). Фиксируя в (3.27) верхний предел суммы /*= 1, по
лучаем /і//г_1< 1 или |
При /*=2 из (3.27) получим |
второе неравенство (3.26): |
|
Ілт~{ + 12т~2< 1
или
U К гіі2 — l\tn = т(т — /і).
Аналогично получим остальные неравенства (3.26), кото рые указывают на неперекрываемость заданных кодовых слов.
Теорема Шеннона. |
При кодировании сообщений хІ5 |
х2, .... х п в алфавите, |
насчитывающем т символов, при |
условии отсутствия шумов, средняя длина кодового сло ва не может быть меньше, чем Н(X)/log т, где Н(Х) — энтропия сообщений. Если вероятности сообщений не яв ляются целочисленными отрицательными степенями числа т, точное достижение указанной границы невозможно, но при кодировании достаточно длинными группами к этой границе можно сколь угодно приблизиться.
74
Д о к а з а т е л ь с т в о . Так как для любых двух рас пределений вероятностей р(хк ) и q(xk) выполняется не равенство
(3.30)
k=i
то, взяв в качестве
|
п |
—'j-, І |
|
|
|
V |
т |
|
|
получим из (3.30): |
j= 1 |
|
||
|
|
|
||
п |
|
п |
///. '4 |
|
2 р{Хк) Іоgp{xk).<C— 2 |
||||
р Ы log-^ |
||||
/г=1 |
|
Л=1 |
!1/ |
|
|
|
|
у=1 |
|
/J |
|
// |
|
|
= log 2 |
"г ”'/ + 1о^ т |
!х* = |
||
/=1 |
пг |
/е==1 |
|
|
= |
+ L log т. |
|||
log V |
||||
У=і В правой части последнего равенства под знаком лога
рифма стоит сумма, которая на основании (3.25) меньше единицы. Поэтому
H(X)^L log in
или
Н( X)
log т ’
Если вероятности появления сообщений являются цело-. численными отрицательными степенями числа т, т. е.
Р(хк) |
= т ,’7'1 |
(3.31) |
|
энтропия таких сообщений |
|
||
|
п |
|
|
log Р{хк) — — ^ |
птГ^ь log m~v'b=L login, |
||
/ѵ’ = 1 |
k=i |
|
|
откуда |
П(Х) |
|
|
J |
(3.32) |
||
~~ |
log m * |
||
|
|||
75