Реши задание на изображении
На фото две отдельные практические работы, поэтому решаю обе видимые части.
Краткий ответ
1. Сжатие алгоритмом Хаффмана
Один из допустимых вариантов кодов:
| Символ | Код |
|---|---|
| М | 11 |
| А | 10 |
| пробел | 010 |
| Р | 000 |
| У | 001 |
| Ы | 0110 |
| Л | 0111 |
Код фразы:
11|10|11|10|010|11|0110|0111|10|010|000|10|11|001
Без разделителей:
111011100101101100111100100001011001
\[ V_{\text{исх}}=42\text{ бит},\qquad V_{\text{сжат}}=36\text{ бит}, \]
\[ K=\frac{42}{36}=\frac76\approx1{,}17. \]
2. Код Хэмминга
Записываем кодовое слово слева направо как \(p_7p_6p_5p_4p_3p_2p_1\):
| Буква | Кодовое слово |
|---|---|
| А | 0000000 |
| Б | 1100001 |
| В | 1010010 |
| Г | 0101101 |
| Д | 1111111 |
Если в тетради записывают биты в порядке \(p_1p_2\dots p_7\), нужно взять обратные последовательности.
Решение
1. Алгоритм Хаффмана
Частоты символов во фразе «МАМА МЫЛА РАМУ»:
| Символ | М | А | пробел | Ы | Л | Р | У |
|---|---|---|---|---|---|---|---|
| Частота | 4 | 4 | 2 | 1 | 1 | 1 | 1 |
Всего символов:
\[ 4+4+2+1+1+1+1=14. \]
Построение дерева Хаффмана:
\[ 1+1=2,\qquad 1+1=2, \]
\[ 2+2=4,\qquad 2+4=6, \]
\[ 4+4=8,\qquad 6+8=14. \]
При одинаковых частотах возможны разные варианты кодов. Главное, чтобы код был префиксным и имел минимальную общую длину.
Длины выбранных кодов:
- М и А — по 2 бита;
- пробел, Р и У — по 3 бита;
- Ы и Л — по 4 бита.
Объём сжатого текста:
\[ V_{\text{сжат}}= 4\cdot2+4\cdot2+2\cdot3+ 1\cdot4+1\cdot4+1\cdot3+1\cdot3=36\text{ бит}. \]
При равномерном кодировании нужно закодировать 7 разных символов:
\[ \left\lceil\log_2 7\right\rceil=3\text{ бита на символ}. \]
Поэтому:
\[ V_{\text{исх}}=14\cdot3=42\text{ бита}. \]
Сжатие достигается потому, что наиболее частые символы М и А получают короткие двухбитовые коды, а редкие символы — более длинные.
2. Код Хэмминга
Четыре информационных бита помещаем в позиции:
\[ p_3,\ p_5,\ p_6,\ p_7. \]
Проверочные биты вычисляем так:
\[ p_1=p_3\oplus p_5\oplus p_7, \]
\[ p_2=p_3\oplus p_6\oplus p_7, \]
\[ p_4=p_5\oplus p_6\oplus p_7. \]
Например, для буквы Б информационный код 0011:
\[ p_3=0,\quad p_5=0,\quad p_6=1,\quad p_7=1. \]
Тогда:
\[ p_1=0\oplus0\oplus1=1, \]
\[ p_2=0\oplus1\oplus1=0, \]
\[ p_4=0\oplus1\oplus1=0. \]
Записываем биты в порядке \(p_7p_6p_5p_4p_3p_2p_1\):
\[ \boxed{1100001}. \]
Итоговая таблица:
| Буква | Информационные биты \(p_3,p_5,p_6,p_7\) | \(p_1,p_2,p_4\) | Код \(p_7\dots p_1\) |
|---|---|---|---|
| А | 0000 | 000 | 0000000 |
| Б | 0011 | 100 | 1100001 |
| В | 0101 | 010 | 1010010 |
| Г | 1010 | 101 | 0101101 |
| Д | 1111 | 111 | 1111111 |
Проверка: в каждом кодовом слове XOR соответствующих битов вместе с проверочным битом равен нулю.
