- •Теорія інформації та кодування
- •Загальні положення, які необхідно знати для успішного вирішення задач теорії інформації та кодування
- •Тема 1 Кількісна оцінка інформації
- •Математичні основи теорії інформації. Міра Хартлі. Ентропія.
- •Оскільки основа логарифма дорівнює основі системи числення, для перевірки правильності розрахунків можна визначити всі можливі комбінації двійкового коду довжиною 4 біта:
- •Як видно, обидва варіанти рішення дали однаковий результат. Завдання для закріплення матеріалу заняття 1
- •Кількісна оцінка інформації в системах з нерівномірним розподілом імовірностей
- •Завдання для закріплення матеріалу заняття 2
- •Тема 2 Надлишковість повідомлень та оптимальне кодування
- •Оцінка недовантаження та надлишковості повідомлень
- •Згідно з формулою (3.1) визначаємо абсолютне недовантаження двійкового шестирозрядного повідомлення:
- •Завдання для закріплення матеріалу заняття 3
- •Оптимальне кодування повідомлень (стиск інформації)
- •Завдання для закріплення матеріалу заняття 4
- •Тема 3 Перешкодостійке кодування
- •Основи перешкодостійкого кодування. Оцінка перевіряючої та корегуючої здатності кодів
- •Завдання для закріплення матеріалу заняття 5
- •Паритетні коди. Кодування за парністю та непарністю повідомлень і блоків даних
- •Завдання для закріплення матеріалу заняття 6
- •Код Хеммінга
- •Завдання для закріплення матеріалу заняття 7
- •Циклічні коди
- •Завдання для закріплення матеріалу заняття 8
- •Значення двійкових логарифмів цілих та дробових чисел
- •Значення десяткових логарифмів цілих та дробових чисел
- •Приклади мінімальних неприводимих в полі двійкових чисел многочленів
- •Перелік використаних джерел
- •Додаткова література
Завдання для закріплення матеріалу заняття 3
Завдання 1. Визначити абсолютне недовантаження двійкового чотирьохрозрядного повідомлення, якщо в ньому міститься 3.5 біта інформації. Імовірності надходження повідомлень вважати однаковими.
Завдання 2. Визначити абсолютне недовантаження двійкового трьохрозрядного повідомлення, якщо в ньому міститься 2.8 біта інформації. Імовірності надходження повідомлень вважати однаковими.
Завдання 3. Визначити абсолютне недовантаження на символ повідомлення, якщо його символи закодовані трьохрозрядними двійковими кодовими комбінаціями, на кожну з яких припадає 2.7 біта інформації. Імовірності появи символів в повідомленні вважати однаковими.
Завдання 4. Визначити абсолютне недовантаження на символ повідомлення, якщо його символи закодовані чотирьохрозрядними двійковими кодовими комбінаціями, на кожну з яких припадає 2.2 біта інформації. Імовірності появи символів в повідомленні вважати однаковими.
Завдання 5. Визначити абсолютне недовантаження на символ алфавіту з 128 якісними ознаками, якщо його символи представлені двійковими кодовими комбінаціями довжиною 1 байт (8 двійкових розрядів). Імовірності появи символів в повідомленні вважати однаковими.
Завдання 6. Визначити абсолютне недовантаження на символ алфавіту з 128 якісними ознаками, якщо його символи представлені двійковими кодовими комбінаціями довжиною 2 байти (16 двійкових розрядів). Імовірності появи символів в повідомленні вважати однаковими.
Завдання 7. 84 повідомлення системи планується закодувати двійковим кодом з рівною довжиною кодових комбінацій. Визначити мінімальну необхідну розрядність кодових комбінацій та абсолютне недовантаження закодованих повідомлень. Імовірності надходження повідомлень вважати однаковими.
Завдання 8. 64 повідомлення системи планується закодувати двійковим кодом з рівною довжиною кодових комбінацій. Визначити мінімальну необхідну розрядність кодових комбінацій та абсолютне недовантаження закодованих повідомлень. Імовірності надходження повідомлень вважати однаковими.
Завдання 9. 68 повідомлень системи планується закодувати двійковим кодом з рівною довжиною кодових комбінацій. Визначити мінімальну необхідну розрядність кодових комбінацій та абсолютне недовантаження закодованих повідомлень. Імовірності надходження повідомлень вважати однаковими.
Завдання 10. Визначити інформаційну надлишковість повідомлень, якщо вони представлені трьохрозрядними двійковими кодовими комбінаціями, на кожну з яких припадає 2.3 біта інформації. Імовірності надходження повідомлень вважати однаковими.
Завдання 11. Визначити інформаційну надлишковість повідомлень, якщо вони представлені чотирьохрозрядними двійковими кодовими комбінаціями, на кожну з яких припадає 1.7 біта інформації. Імовірності надходження повідомлень вважати однаковими.
Завдання 12. Визначити інформаційну надлишковість повідомлень, якщо вони представлені чотирьохрозрядними двійковими кодовими комбінаціями, на кожну з яких припадає 1 діт інформації. Імовірності надходження повідомлень вважати однаковими.
Завдання 13. Визначити інформаційну надлишковість повідомлень, якщо вони представлені двохрозрядними двійковими кодовими комбінаціями, на кожну з яких припадає 0.5 діт інформації. Імовірності надходження повідомлень вважати однаковими.
Завдання 14. Визначити інформаційну надлишковість повідомлень про 75 станів системи, якщо вони представлені двійковими кодовими комбінаціями довжиною 1 байт (8 двійкових розрядів). Імовірність знаходження системи в будь-якому з можливих станів вважати однаковою.
Завдання 15. Визначити абсолютне недовантаження на літеру та надлишковість повідомлень, які складаються з літер А, Б, В та Г, якщо літери закодовані кодовими комбінаціями двійкового коду 00, 01, 10 та 11 відповідно, а імовірності появи літер дорівнюють: рА=0.25; рБ=0.5; рВ=0.125; рГ=0.125. Визначити, як зміняться зазначені показники, якщо літерам повідомлень співставити кодові комбінації нерівномірного коду 10, 0, 110 та 111 відповідно.
Завдання16. Повідомлення побудовані з алфавіту, імовірності появи символів якого дорівнюють: рА=0.2; рБ=0.3; рВ=рГ=0.25. Визначити інформаційну надлишковість повідомлень, якщо їм співставлені кодові комбінації 0, 10, 110 та 111 відповідно.
Завдання 17. Для кодування повідомлень пропонується використовувати один з трьох запропонованих способів кодування. Необхідно визначити, який з способів характеризується найменшими показниками абсолютного недовантаження на літеру та інформаційної надлишковості, якщо імовірності появи літер повідомлень А, Б, В, Г та Д дорівнюють: рА=0.4; рБ=0.3; рВ=0.15; рГ=0.1; рД=0.05. Запропоновані способи кодування передбачають співставлення літерам повідомлень наступних кодових комбінацій:
А=111, Б=001, В=101, Г=100, Д=000;
2) А=0111, Б=0110, В=010, Г=1, Д=01;
3) А=1, Б=01, В=010, Г=0110, Д=0111.
Завдання 18. Порівняти показники абсолютного недовантаження та інформаційної надлишковості для рівномірного та нерівномірного способу кодування 5 повідомлень, якщо при першому способі кодування повідомленням співставляються кодові комбінації мінімальної довжини, а при другому – кодові комбінації 00, 01, 10, 110 та 111. Імовірності надходження повідомлень вважати однаковими.
Завдання 19. Оцінити інформаційну надлишковість для рівномірного та нерівномірного способу кодування 12 повідомлень, якщо при першому способі кодування всім повідомленням співставляються чотирьохрозрядні кодові комбінації однакової довжини, а при другому - по чотири кодові комбінації з трьох, чотирьох та п’яти двійкових розрядів. Імовірності надходження повідомлень вважати однаковими.
Завдання 20. Визначити, яку середню довжину повинні мати кодові комбінації літер повідомлення (в двійковому коді) для повного усунення абсолютного недовантаження на літеру, якщо імовірності появи останніх дорівнюють 0.4, 0.3, 0.2 та 0.1 .
Завдання 21. Визначити, яку середню довжину повинні мати кодові комбінації двійкового коду для повного усунення інформаційної надлишковості, якщо імовірності надходження п’яти можливих повідомлень дорівнюють 0.5, 0.125, 0.125, 0.125 та 0.125 .
Завдання 22. Визначити, яку середню довжину повинні мати кодові комбінації двійкового коду для повного усунення інформаційної надлишковості, якщо імовірності надходження можливих повідомлень дорівнюють 0.4, 0.4, 0.1 та 0.1 .
Заняття 4