Дз 2. Коды Хаффмана и Шеннона-Фано
.doc-
Определить, какие из следующих кодов могут быть декодированы однозначно:
a) 11 – 010 – 0111 – 10 – 001;
b) 010 – 1101 – 0101 – 101 – 111;
c) 100 – 1010 – 010 – 1100 – 111;
d) 0 – 1100 – 0111 – 111 – 1011.
-
Составить равномерный четверичный код для передачи слов некоторого 24 буквенного алфавита. Чему равны объем и количество информации при передаче 6-буквенного слова в этом коде, если вероятности появления букв одинаковы?
-
Чему равен объем информации при передаче 18 кодовых слов 4-разрядного равномерного двоичного кода? Какое количество информации передано, если данное сообщение является кодировкой текста, составленного из 12-буквенного равновероятного алфавита?
-
Алфавит обладает избыточностью 25% и состоит из 64 букв. Объем информации при передаче некоторого сообщения этого алфавита в равномерном двоичном коде минимальной разрядности равен 60 двоичным разрядам. Какое количество информации передано в этом сообщении?
-
Энтропия некоторого алфавита равна 4,5 бит/символ, а избыточность составляет 25%. Передаваемое сообщение несет 36 бит информации. Какой минимальный объем информации необходим для передачи этого сообщения в равномерном двоичном коде?
-
Избыточность некоторого 24-буквенного алфавита составляет 20%. Для кодирования используется равномерный двоичный код минимальной разрядности. Какое количество и какой объем информации содержится в сообщении, соответствующем 5-буквенному слову исходного алфавита?
-
Закодировать по методу Шеннона-Фано алфавит, состоящий из четырех символов A, B. C и D, если вероятности появления каждого сообщения равны: p(A)=0,28; p(B)=0,14; p(C)=0,48; p(D)=0,10. Определить экономность кода, то есть количество информации, приходящейся на один символ.
-
Для алфавита с символами a, b, c, d, e, f и вероятностями использования в сообщениях этих символов, равными
p(a)=0,09; p(b)=0,27; p(c)=0,08; p(d)=0,15, p(e)=0,1; p(f)=0,31,
найти двоичный код Шеннона-Фано и определить эффективность кодирования.
-
Построить двоичный неравномерный код методом Шеннона-Фано для алфавита A={a1, a2, a3, a4, a5, a6, a7, a8}, если вероятности появления букв равны: p1=0.052, p2=0.011, p3=0.098, p4=0.04, p5=0.03, p6=0.5, p7=0.19, p8=0.25.
-
Закодировать двоичным кодом Шеннона-Фано следующие множества сообщений:
а) семь сообщений с вероятностями
p1=p2=1/4; p3=p4=p5=1/8; p6=p7=1/16;
б) десять сообщений с вероятностями
p1=p2=0,22; p3=p4=p5=p6=0,1; p7=p8=p9=p10=0,04.
Найти среднюю длину каждого из полученных кодов.
Выяснить, каков выигрыш по сравнению с равномерным кодированием.
-
Закодировать троичным кодом Фано следующие множества сообщений:
а) 9 сообщений с вероятностями
1/3, 1/9, 1/9, 1/9, 1/9, 1/9, 1/27, 1/27, 1/27;
б) 10 сообщений с вероятностями
0,2; 0,15; 0,15; 0,1; 0,1; 0,1; 0,05; 0,05; 0,05; 0,05.
-
Закодировать двоичным кодом Хаффмана множество сообщений, имеющих вероятности: p1=0,25; p2=0,2; p3=p4=p5=0,15; p6=0,1.
-
Построить двоичный неравномерный код методом Хаффмана для алфавита A={a1, a2, a3, a4, a5, a6, a7, a8}, если вероятности появления букв равны: p1=0.052, p2=0.011, p3=0.098, p4=0.04, p5=0.03, p6=0.5, p7=0.19, p8=0.25.
-
Первичный алфавит содержит 8 знаков с вероятностями:
Пробел |
? |
& |
* |
+ |
% |
# |
! |
0,25 |
0,18 |
0,15 |
0,12 |
0,1 |
0,08 |
0,07 |
0,05 |
Построить коды Шеннона-Фано и Хаффмана, сравнить их избыточности.
-
Сравнить коды Шеннона-Фано и Хаффмана для множества сообщений с вероятностями p1=0,25; p2=p3=p4=p5=0,125; p6=p7=p8=p9=0,0625.
-
Пусть первичный алфавит состоит из двух знаков a и b с вероятностями, соответственно, 0,75 и 0,25. Сравнить избыточность кода Хаффмана при алфавитном и блочном двухбуквенном кодировании.