Кодирование методом Хаффмана

Задание 1

Закодировать  указанное сообщение, используя  адаптивное кодирование  Хаффмена, с упорядоченным деревом и вычислить длину полученного кода.

 

ASDADDS

 

Символ	A	D	S
Число вхождений	2	3	2

 

Разместим таблицу, как показано ниже

 

Символ	D	A	S
Число вхождений	3	2	2

 

Возьмем из последней таблицы символы с наименьшей частотой. В нашем случае это A (2) и S (2).

Сформируем  из «узлов» A и S новый «узел», частота вхождения для которого будет равна сумме частот A и S:

 

3 2  2

D A  S

|  |

------- 4 ------

 

 

3 2  2

D A  S

| |  |

| ------- 4 ------

|  |

----root(7)----

 

Теперь когда наше дерево создано, мы можем кодировать файл. Мы должны всегда начинать из корня (Root). Кодируя первый символ (лист дерева D) Мы прослеживаем вверх по дереву все повороты ветвей и если мы делаем левый поворот, то запоминаем 0-й бит, и аналогично 1-й бит для правого поворота. Так для D, мы будем идти влево (и запомним 0), к самому символу. Код Хаффмана для символа D – 0. Для следующего символа (А) у нас получается –право, лево, что выливается в последовательность 10. Для S – право, право - последовательность 11.

D = 0 (1 бит)

A = 10 (2 бита)

S = 11 (2 бита)

 

Закодированное сообщение:  10 11 0 10 0 0 11. Длина сообщения – 11бит.

 

 

Задание 2

Сложить указанные  числа, используя их представление  в виде чисел с плавающей запятой

10  и  39

10 = 1010 = 1,010*exp₂⁺¹¹ 

 

39 = 100111 = 1,00111*exp₂⁺¹⁰¹

 

знак	смещенный порядок	мантисса
0	1000 0010	010 0000 0000 0000 0000 0000
0	1000 0100	001 1100 0000 0000 0000 0000

 

нормализуем порядок чисел и слаживаем

 

знак	смещенный порядок	мантисса
0	1000 0100	010 1000 0000 0000 0000 0000
+
0	1000 0100	001 1100 0000 0000 0000 0000
=
0	1000 0100	100 0100 0000 0000 0000 0000

 

Переводим в десятичное число:

 

F=(-1)⁰ 2^132-127 (1+4456448//2²³)= 32 * 1.53125 = 49