Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Ход работы
|
|
Постановка задачи
1. Изучить такие понятия, как: эффективное кодирование, алгоритм Шеннона-Фано, алгоритм Хаффмена;
2. Научиться пользоваться формулами и решить задачи своего варианта.
Ход работы
Задача №1
Построить код Хаффмена для ансамбля сообщений {xi}, i=1..5 при 
с вероятностями
.
Определить характеристики эффективного кода.
Решение:
Таблица кодирования для метода Хаффмана
| X | P | Код | Двоичный код |
| 0, 2 | |||
| 0, 2 | |||
| 0, 2 | |||
| 0, 2 | |||
| 0, 2 |
Т.к. в алфавите 5 символов. Требуется 2^x символов для кодирования, значит x = 3
Избыточность:
Ответ: Таблица кодирования
| Сообщения | x1 | x2 | x3 | x4 | x5 |
| Код |
Средняя длина кодового слова в битах 
. Минимально возможная средняя длина кодового слова 
. Избыточность кода 
.
Задача №2
Ансамбль сообщений {xi}, i=1..5 задан при вектор-строкой вероятностей
.
Закодировать сообщения эффективным кодом Хаффмена и обычным двоичным кодом. Определить характеристики кодов и скорость передачи по каналу при условии, что длительность двоичного символа 
Решение:
Составим матрицу вероятностей:
1/2 1/2 1/2 1/2 1
1/4 1/4 1/4 1/2 0
1/8 1/8 1/4 0 0
1/16 1/8 0 0 0
1/16 0 0 0 0
Построим граф вероятностей:
| 1/2 |
| 1/4 |
0
| 1/8 |
1
1 1 0
| 1/2 |
| 1/16 |
| 1/4 |
| 1/8 |
| 1/16 |
Составим таблицу кодирования для кода Хаффмена:
| Сообщение | Х1 | Х2 | Х3 | Х4 | Х5 |
| Код |
Рассчитаем характеристики кода:
Согласно таблице кодирования длины сообщений можно записать вектор-строкой: n: = (1 2 3 4 4)
Средняя длина кодового слова в битах:
Минимально возможная средняя длина кодового слова:
H(x)=0.5*log(2)+0, 25*log(4)+0.125*log(8)+2*0.0625*log(16)=1.875 bit
Избыточность кода:
R=1-n_(cp min)/n_cp =1-1, 875/2, 8=0.33
Для обычного кода.
Составим таблицу кодирования:
| Сообщение | Х1 | Х2 | Х3 | Х4 | Х5 |
| Код |
Средняя длина кодового слова в битах:
Минимально возможная средняя длина кодового слова:
H(x)=1.875 bit
Избыточность кода:
R=1-n_(cp min)/n_cp =1-1, 875/3=0.625
Задача №3
Сообщение состоит из последовательности трех букв A, B и C, вероятности появления которых не зависят от предыдущего сочетания букв и равны 
, 
, и 
.
Провести кодирование по алгоритму Шеннона-Фано отдельных букв и двухбуквенных сочетаний. Сравнить коды по их эффективности и избыточности.
Решение:
1. Кодирование букв
| Элемент | Вероятность | Деление на группы и подгруппы | Код | |
| A | 0.7 | |||
| B | 0.2 | |||
| C | 0.1 |
2. Кодирование двухбуквенных сочетаний
| Элементы | Вероятность | Деление на группы и подгруппы | Код | |||
| AA | 0.49 | |||||
| AB | 0.14 | |||||
| BA | 0.14 | |||||
| AC | 0.07 | |||||
| CA | 0.07 | |||||
| BB | 0.04 | |||||
| BC | 0.02 | |||||
| CB | 0.02 | |||||
| CC | 0.01 |
3. Эффективность и избыточность кодов:
значит 
и 
значит 
и 
Ответ:
1. Таблица кодирования отдельных букв:
| Сообщения | A | B | C |
| Код |
2. Таблица кодирования двухбуквенных сочетаний
| Сообщения | AA | AB | BA | AC | CA |
| Код |
| Сообщения | BB | BC | CB | CC |
| Код |
Вывод
В ходе работы были изучены такие понятия, как: эффективное кодирование, алгоритм Шеннона-Фано, алгоритм Хаффмена; решены 3 задачи первого варианта с использованием соответствующих формул.
Список использованной литературы
1. Игнатов В. А. Теория информации и передачи сигналов: Учебник для вузов. – М.: Радио и связь, 1991. – 280с.;
2. Дмитриев В.И. Прикладная теория информации: Учеб. Для студ. Вузов по спец. “Автоматизированные системы обработки информации и управления”. - М.: Высш.шк., 1989. -320с.;
3. Каганов В.И. Радиотехнические цепи и сигналы. Компьютеризированный курс: Учебное пособие. – М.: ФОРУМ: ИНФРА-М, 2005. – 432с.
|