2015-03-22
5637
С = lcp: 
= 27,4 знак/сек.
Задача 5.52. Методом Хаффмена построить оптимальный код для алфавита, приведенного в предыдущей задаче. Определить емкость канала связи для передачи сообщений в полученном коде.
Задача 5.53. Дан алфавит со следующим распределением вероятностей: р1 = 0 4; р2 = 0,18; р3 = 0,1; р4 = 0,1; р5= 0. 07, р6= 0 06; р7= 0,05; р8 = 0,04. Построить оптимальные коды методом Шеннона – Фано и методом Хаффмена. Определить, какой код требует меньшей емкости канала связи.
Задача 5.54. Определить необходимую пропускную способность канала связи для передачи сообщений оптимальными кодами, построенными по методике Шеннона – Фано и Хаффмена для алфавита со следующим распределением вероятностей: р1 = 0,6; р2 = = 0,08; р3 = 0,07; р4= 0,06; р5 = 0,05; р6 = 0,05; р7 = 0,05; р8 = 0,04.
Задача 5.55. Символы алфавита А, В, С встречаются в сообщениях с вероятностями 0,7; 0,2 и 0,1. Определить емкость канала связи, необходимую для передачи сообщений, кодируемых ОНК двусимвольными блоками, если на выходе источника сообщений символы вырабатываются со скоростью двадцать знаков в секунду.
|
|
|
Решение.
Задача 5.56. Алфавит состоит ив трех букв А, В, С c вероятностями, соответственно, рA = 0,5; рВ = 0,3; рc = 0,2. Построить ОНК дли передачи сообщений, если кодировать по одному, по два и по три символа в блоке. Сравнить эффективность полученных кодов.
Р е ш е н и е.
| Случай кодирова-ния | Буквы | Блоки | Вероятности | Коды | 
| 
|
| I | A,B,C | A B C | 0.5 0.3 0.2 | 0.5 0.6 0.4 | ||
| II | A,B,C | AA | 0,25 | 0,25 | ||
| AB | 0,15 | 0,45 | ||||
| BA | 0,15 | 0,6 | ||||
| AC | 0,1 | 0,4 | ||||
| CA | 0,1 | 0,4 | ||||
| BB | 0,09 | 0,36 | ||||
| BC | 0,06 | 0,24 | ||||
| CB | 0,06 | 0,3 | ||||
| CC | 0,04 | 0,2 | ||||
| III | A,B,C | AAA | 0,125 | 0,375 | ||
| AAB | 0,075 | 0,3 | ||||
| ABA | 0,075 | 0,3 | ||||
| BAA | 0,75 | 0,3 | ||||
| AAC | 0,05 | 0,2 | ||||
| ACA | 0,05 | 0,2 | ||||
| CAA | 0,045 | 0,2 | ||||
| ABB | 0,045 | 0,18 | ||||
| BAB | 0,045 | 0,225 | ||||
| BBA | 0,03 | 0,225 | ||||
| ABC | 0,03 | 0,15 | ||||
| BAC | 0,03 | 0,15 | ||||
| BCA | 0,03 | 0,15 | ||||
| CBA | 0,03 | 0,15 | ||||
| CAB | 0,03 | 0,15 | ||||
| ACB | 0,03 | 0,15 | ||||
| BBB | 0,027 | 0,135 | ||||
| CAC | 0,02 | 0,12 | ||||
| CCA | 0,02 | 0,12 | ||||
| ACC | 0,02 | 0,1 | ||||
| BBC | 0,018 | 0,108 | ||||
| BCB | 0,018 | 0,108 | ||||
| CBB | 0,018 | 0,108 | ||||
| CCB | 0,012 | 0,072 | ||||
| CBC | 0,012 | 0,072 | ||||
| BCC | 0,012 | 0,084 | ||||
| CCC | 0,008 | 0,056 |
| Случай кодирования | 
| Н |
| I | 1.5 | 1.485476 бит/символ |
| II | 3.2 | 2.90952 бит/символ |
| III | 4.488 | 4.471423 бит/символ |
|
|
|
Задача 5.57. Какой вид имеет комбинации оптимального неравномерного кода при блочном кодировании сообщений, составленных из алфавита A,B,C,D если вероятности появления букв алфавита рA = рВ= рc = рD= 0,25?
Задача 5.58. Построить код Хаффмена для передачи сообщений при помощи трех частот f1, f2, f3, если символы первичного алфавита встречаются в сообщениях со следующими вероятностями: А=0,24; Б=0,18; В=0,38; Г=0,1; Д=0,06; Е=0,02; Ж=0,02.
Решение:
Полученные коды легко декодируютея, так как в нервом слу- чае ни один код не начинается f1, и f2 кроме одного одноразрядного кода, а во втором случае ни один код не начинаетея f3 и f2, кроме соответствующего одноразрядного кода.
Задача 5.59. Построить код Хаффмена для передачи сообщений следующего исходного алфавита: А1 = 0,03; А2 = 0,02; А3 = 0,13; А4 = 0,18; А5 = 0 13; А6 = 0,15; А7 = 0 16; А8 = 0,11 А9 = 0,02; А10= 0,07, если число качественных признаков вторичного алфавита т, = 3.
Задача 5.60. Не прибегая к упорядочиванию символов первичного алфавита в порядке убывания вероятностей, построить ОНК. Вероятности появления в сообщениях букв первичного алфавита следующие: А1 = 0,01; А2= 0,07; А3 = 0,04; А4= 0,49; А5 = 0,02; А6 = 0,14; А7 = 0,02; А 8= 0,07; А9= 0,14.
Задача.5.61. убедиться в правильности построения кода предыдущей задачи.
Контрольные задачи
1. Методом Шеннона – Фано построить оптимальный код для передачи 100 сообщений при помощи 10 качественных признаков вторичного алфавита.
2. Первичный алфавит состоит из 9 букв. Построить оптимальный код во вторичном алфавите с числом качественных признаков т2 = 3 для случаев:
а) символы первичного алфавита появляются на выходе источника сообщений с равной вероятностью;
б) символы первичного алфавита появляются на выходе источника сообщений с вероятностями р1 = р2 = р3 = 0,1; р4 = 0,2; р5 = 0,3; р6 = р7 = р8 = р9 = 0 05.
Проверить соблюдение условия оптимальности. Сравнить аналогичную ситуацию для вторичного алфавита с т2 = 2. Сделать вы- воды.
3. Первичный алфавит – английский. Коды, представленные во вторичном алфавите, являются девятиразрядными двоичными комбинациями, из которых 5 несут информационную нагрузку, а 4 служат для обнаружения и исправления ошибок, Определить:
а) абсолютную информационную избыточность;
б) относительную информационную избыточность;
в) абсолютную и относительную корректирующие избыточности.
4. Чему равна общая и частная избыточность некоторого 32-буквенного алфавита, если известно, что его энтропия с учетом неравновероятности букв уменьшается на 0,98 бит/символ, а с учетом взаимозависимости – на 0,4 бит/символ
5. Определить избыточность двоичного кода в первых 5 кодах трехзначных двоичных кодов; в первых 9 кодах четырехзначных двоичных кодов; в первых 17 кодах пятизначных двоичных кодов; в первых 33 кодах шестизначных двоичных кодов.
6. Символы первичного алфавита встречаются в тексте с вероятностями: р1 = 0,14; р2 = 0,01; р3= 0,49; р4= 0,02; р5 = 0,14; р6 = 0,02; р7 = 0,07; р8 = 0,04; р9 = 0,07. Не упорядочивая первичный алфавит, построить оптимальный код.
7. Числосимволов алфавита т = 6. Вероятности появления букв алфавита в текстах рА = 0,24; рВ = 0,28; РG = 0,05; рd = 0,22; рe = = 0,15; рF = 0,06. Определить, насколько недогружены символы сообщений, построенных из этого алфавита.
8. Число качественных признаков первичного алфавита т1= 8, вторичного – т2 = 2. Определить коэффициент сжатия и избытокчность от округления при посимвольном кодировании и при кодировании блоками по два, три, четыре символа в блоке.
9. Для повышения помехоустойчивости сообщений, передаваемых при помощи четырехзначного двоичного кода на все сочетания, к нему добавили 3 корректирующих разряда. Определить избыточность вновь образованного кода.
10. Какое количество элементарных символов на букву сообщения необходимо при передаче русских текстов без учета неравно- мерности появления букв, с учетом одно-, двух- и трехбуквенных сочетаний (см. приложение 5, табл. 1)?
|
|
|
11. Первичный алфавит состоит из 26 символов. Вероятность появления каждого последующего символа в два раза меньше вероятности предыдущего, Какой вид имеют вторая, тринадцатая и двадцать шестая комбинации оптимального кода для данного первичного алфавита?
12. Определить коэффициенты статистического сжатия и относительной эффективности оптимального кода для алфавита со следующими вероятностями появления букв в сообщениях: А1 = 0,01; А2 = 0,07; А3 = 0,14; А4 =0,49; А5 = 0,14; А6 = 0,07; А7 = 0,02; А8 =0,04; А9 =0,02.
13. Первичный алфавит состоит из двух качественных признаков 0 и 1 с вероятностями появления в сообщениях 
. Построить ОНК для передачи сообщений по два и три символа в блоке. Сравнить эффективность полученных кодов с эффективностью кода при побуквенном кодировании.
14. Первичный алфавит имеет следующие вероятности появления букв в текстах: А1 = 0,02; А2 = 0,5; А3 = 0,03; А4 = 0,15; А5 =0,04; А6 = 0,12, А7 = 0,04, А8 = 0,1. Построить ОНК методом Шеннона – Фано и методом Хаффмена. Сравнить эффективность полученных кодов.
15. Определить емкость канала связи для передачи сообщений, если известно, что на выходе источника сообщений символы вырабатываются со скоростью 50 знаков в секунду и закодированы оптимальным кодом, который построен для двусимвольных блоков, составленных из трехбуквенного первичного алфавита со следующими вероятностями появления букв в сообщениях: А = 0,6; В = 0,3; С = 0,1.
