Дз 2. Коды Хаффмана и Шеннона-Фано

1. Определить, какие из следующих кодов могут быть декодированы однозначно:

a) 11 – 010 – 0111 – 10 – 001;

b) 010 – 1101 – 0101 – 101 – 111;

c) 100 – 1010 – 010 – 1100 – 111;

d) 0 – 1100 – 0111 – 111 – 1011.

2. Составить равномерный четверичный код для передачи слов некоторого 24 буквенного алфавита. Чему равны объем и количество информации при передаче 6-буквенного слова в этом коде, если вероятности появления букв одинаковы?

3. Чему равен объем информации при передаче 18 кодовых слов 4-разрядного равномерного двоичного кода? Какое количество информации передано, если данное сообщение является кодировкой текста, составленного из 12-буквенного равновероятного алфавита?

4. Алфавит обладает избыточностью 25% и состоит из 64 букв. Объем информации при передаче некоторого сообщения этого алфавита в равномерном двоичном коде минимальной разрядности равен 60 двоичным разрядам. Какое количество информации передано в этом сообщении?

5. Энтропия некоторого алфавита равна 4,5 бит/символ, а избыточность составляет 25%. Передаваемое сообщение несет 36 бит информации. Какой минимальный объем информации необходим для передачи этого сообщения в равномерном двоичном коде?

6. Избыточность некоторого 24-буквенного алфавита составляет 20%. Для кодирования используется равномерный двоичный код минимальной разрядности. Какое количество и какой объем информации содержится в сообщении, соответствующем 5-буквенному слову исходного алфавита?

7. Закодировать по методу Шеннона-Фано алфавит, состоящий из четырех символов A, B. C и D, если вероятности появления каждого сообщения равны: p(A)=0,28; p(B)=0,14; p(C)=0,48; p(D)=0,10. Определить экономность кода, то есть количество информации, приходящейся на один символ.

8. Для алфавита с символами 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,

найти двоичный код Шеннона-Фано и определить эффективность кодирования.

9. Построить двоичный неравномерный код методом Шеннона-Фано для алфавита A={a₁, a₂, a₃, a₄, a₅, a₆, a₇, a₈}, если вероятности появления букв равны: p₁=0.052, p₂=0.011, p₃=0.098, p₄=0.04, p₅=0.03, p₆=0.5, p₇=0.19, p₈=0.25.

10. Закодировать двоичным кодом Шеннона-Фано следующие множества сообщений:

а) семь сообщений с вероятностями

p₁=p₂=1/4; p₃=p₄=p₅=1/8; p₆=p₇=1/16;

б) десять сообщений с вероятностями

p₁=p₂=0,22; p₃=p₄=p₅=p₆=0,1; p₇=p₈=p₉=p₁₀=0,04.

Найти среднюю длину каждого из полученных кодов.

Выяснить, каков выигрыш по сравнению с равномерным кодированием.

11. Закодировать троичным кодом Фано следующие множества сообщений:

а) 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.

12. Закодировать двоичным кодом Хаффмана множество сообщений, имеющих вероятности: p₁=0,25; p₂=0,2; p₃=p₄=p₅=0,15; p₆=0,1.

13. Построить двоичный неравномерный код методом Хаффмана для алфавита A={a₁, a₂, a₃, a₄, a₅, a₆, a₇, a₈}, если вероятности появления букв равны: p₁=0.052, p₂=0.011, p₃=0.098, p₄=0.04, p₅=0.03, p₆=0.5, p₇=0.19, p₈=0.25.

14. Первичный алфавит содержит 8 знаков с вероятностями:

Пробел	?	&	*	+	%	#	!
0,25	0,18	0,15	0,12	0,1	0,08	0,07	0,05

Построить коды Шеннона-Фано и Хаффмана, сравнить их избыточности.

15. Сравнить коды Шеннона-Фано и Хаффмана для множества сообщений с вероятностями p₁=0,25; p₂=p₃=p₄=p₅=0,125; p₆=p₇=p₈=p₉=0,0625.

16. Пусть первичный алфавит состоит из двух знаков a и b с вероятностями, соответственно, 0,75 и 0,25. Сравнить избыточность кода Хаффмана при алфавитном и блочном двухбуквенном кодировании.