Федеральное агентство связи
Сибирский Государственный Университет Телекоммуникаций и Информатики
Межрегиональный центр переподготовки специалистов
Контрольная работа
По дисциплине: Теория информации
Выполнил:
Группа: ПБТ-22
Вариант: 6
Проверил: ___________________
Новосибирск, 2013 г
Контрольная работа
Для всех заданий контрольной работы используется набор символов, входящих в ФИО студента. Все задания необходимо выполнить вручную. Все примеры построения кодов и оформления решения задач можно найти в конспекте.
- Построить код Хаффмана для набора букв ФИО. Для оценки вероятностей символов использовать частоты вхождения букв в ФИО. Подсчитать среднюю длину кодового слова построенного кода.
ФИО: ИВАНОВ ПАВЕЛ ЮРЬЕВИЧ
И | В | А | Н | О | П | Е | Л | Ю | Р | Ь | Ч | |
Частота | 2 | 4 | 2 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
Вероятность | 0.11 | 0.22 | 0.11 | 0.06 | 0.06 | 0.06 | 0.11 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 |
Упорядочим по вероятностям:
Н | О | П | Л | Ю | Р | Ь | Ч | И | А | Е | В | |
Вероятность | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 | 0.11 | 0.11 | 0.11 | 0.22 |
Буква | Код |
В | 10 |
Е | 110 |
П | 0000 |
Л | 0001 |
Н | 0010 |
О | 0011 |
Ь | 0100 |
Ч | 0101 |
Ю | 0110 |
Р | 0111 |
И | 1110 |
А | 1111 |
Средняя длина кодового слова построенного кода:
Lср = 0.22 * 2 + 0.11 * 3 + (0.11 * 2 + 0.06 * 8) * 4 = 0.44 + 0.33 + 2.8 = 3.57
- Построить код Фано для набора букв ФИО. Для оценки вероятностей символов использовать частоты вхождения букв в ФИО. Подсчитать среднюю длину кодового слова построенного кода.
ФИО: ИВАНОВ ПАВЕЛ ЮРЬЕВИЧ
Буква | Вероятность | Кодовое слово | Длина | |||
В | 0.22 | 0 | 0 | 0 | 3 | |
Е | 0.11 | 0 | 0 | 1 | 3 | |
А | 0.11 | 0 | 1 | 0 | 3 | |
И | 0.11 | 0 | 1 | 1 | 3 | |
Ч | 0.06 | 1 | 0 | 0 | 0 | 4 |
Ь | 0.06 | 1 | 0 | 0 | 1 | 4 |
Р | 0.06 | 1 | 0 | 1 | 0 | 4 |
Ю | 0.06 | 1 | 0 | 1 | 1 | 4 |
Л | 0.06 | 1 | 1 | 0 | 0 | 4 |
П | 0.06 | 1 | 1 | 0 | 1 | 4 |
О | 0.06 | 1 | 1 | 1 | 0 | 4 |
Н | 0.06 | 1 | 1 | 1 | 1 | 4 |
Средняя длина кодового слова построенного кода:
Lср = 0.22 * 3 + 0.11 * 3 * 3 + 0.06 * 8 * 4 = 0.66 + 0.99 + 1.92 = 3.57
- Построить код Шеннона для набора букв ФИО. Для оценки вероятностей символов использовать частоты вхождения букв в ФИО. Подсчитать среднюю длину кодового слова построенного кода.
ФИО: ИВАНОВ ПАВЕЛ ЮРЬЕВИЧ
Буква | Pi | Qi-1 | Li | Кодовое слово |
В | 1/23≤0.22<1/22 | 0 | 3 | 000 |
Е | 1/24≤0.11<1/23 | 0.22 | 4 | 0011 |
А | 1/24≤0.11<1/23 | 0.33 | 4 | 0101 |
И | 1/24≤0.11<1/23 | 0.44 | 4 | 0111 |
Ч | 1/25≤0.06<1/24 | 0.55 | 5 | 10001 |
Ь | 1/25≤0.06<1/24 | 0.61 | 5 | 10011 |
Р | 1/25≤0.06<1/24 | 0.67 | 5 | 10101 |
Ю | 1/25≤0.06<1/24 | 0.73 | 5 | 10111 |
Л | 1/25≤0.06<1/24 | 0.79 | 5 | 11001 |
П | 1/25≤0.06<1/24 | 0.85 | 5 | 11011 |
О | 1/25≤0.06<1/24 | 0.91 | 5 | 11101 |
Н | 1/25≤0.06<1/24 | 0.97 | 5 | 11111 |
Средняя длина кодового слова построенного кода:
Lср = 0.22 * 3 + 0.11 * 3 * 4 + 0.06 * 8 * 5 = 0.66 + 1.32 + 2.4 = 4.38
- Закодировать первые три буквы своего имени арифметическим кодом. Для оценки вероятностей символов использовать частоты вхождения букв в ФИО.
ФИО: ИВАНОВ ПАВЕЛ ЮРЬЕВИЧ
И | В | А | Н | О | П | Е | Л | Ю | Р | Ь | Ч | |
Частота | 2 | 4 | 2 | 1 | 1 | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
Вероятность | 0.11 | 0.22 | 0.11 | 0.06 | 0.06 | 0.06 | 0.11 | 0.06 | 0.06 | 0.06 | 0.06 | 0.06 |
Вычислим кумулятивные вероятности:
Q0 = 0
Q1 = 0.11
Q2 = 0.33
Q3 = 0.44
Q4 = 0.50
Q5 = 0.56
Q6 = 0.62
Q7 = 0.73
Q8 = 0.79
Q9 = 0.85
Q10 = 0.91
Q11 = 0.97
Q12 = 1
Имя: Павел
Получим границы интервала, соответствующего первому символу кодируемого сообщения (П):
l1 = l0 + r0 * Q6-1 = 0 + 1 * 0.56 = 0.56
h1 = l0 + r0 * Q6 = 0 + 1 * 0.62 = 0.62
r1 = h1 – l1 = 0.62 – 0.56 = 0.06
Для второго символа (А) кодируемого сообщения границы интервала будут следующие:
l2 = l1 + r1 * Q3-1 = 0.56 + 0.06 * 0.33 = 0.5798
h2 = l1 + r1 * Q3 = 0.56 + 0.06 * 0.44 = 0.5864
r2 = h2 – l2 = 0.5864 – 0.5798 = 0.0066
Для третьего символа (В):
l3 = l2 + r2 * Q2-1 = 0.5798 + 0.0066 * 0.11 = 0.580526
h3 = l2 + r2 * Q2 = 0.5798 + 0.0066 * 0.33 = 0.581978
r3 = h3 – l3 = 0.581978 – 0.580526 = 0.001452
Кодом последовательности “ПАВ” будет двоичная запись любой точки из интервала [0.580526, 0.581978), например, 0.580526. Для однозначного декодирования возьмем –log r3 = –log 0.001452 = 10 разрядов (с округлением до большего целого).
Получим код: 1001010010
- Закодировать последовательность из 10 букв ФИО адаптивным кодом Хаффмана (размер окна 6).
ФИО: ИВАНОВ ПАВЕЛ ЮРЬЕВИЧ
Последовательность из 10 букв ФИО: ИВАНОВПАВЕ
Кодируем 7-ой символ (П):
Символы | Вероятности | Кодовые слова |
И | 1/6 | 101 |
В | 1/3 | 0 |
А | 1/6 | 100 |
Н | 1/6 | 111 |
О | 1/6 | 1101 |
П | 0 | 11001 |
Е | 0 | 11000 |
Символ П кодируем кодовым словом 11001
Кодируем 8-ой символ (А):
Символы | Вероятности | Кодовые слова |
И | 0 | 11001 |
В | 1/3 | 0 |
А | 1/6 | 101 |
Н | 1/6 | 100 |
О | 1/6 | 111 |
П | 1/6 | 1101 |
Е | 0 | 11000 |
Символ А кодируем кодовым словом 101
Кодируем 9-ый символ (В):
Символы | Вероятности | Кодовые слова |
И | 0 | 11001 |
В | 1/6 | 101 |
А | 1/3 | 0 |
Н | 1/6 | 100 |
О | 1/6 | 111 |
П | 1/6 | 1101 |
Е | 0 | 11000 |
Символ В кодируем кодовым словом 101
Кодируем 10-ый символ (Е):
Символы | Вероятности | Кодовые слова |
И | 0 | 11001 |
В | 1/3 | 0 |
А | 1/6 | 101 |
Н | 1/6 | 100 |
О | 1/6 | 111 |
П | 1/6 | 1101 |
Е | 0 | 11000 |
Символ Е кодируем кодовым словом 11000
Таким образом, ИВАНОВПАВЕ кодируем так:
101 0 100 111 1101 0 11001 101 101 11000
