- •Теорія інформації та кодування
- •Загальні положення, які необхідно знати для успішного вирішення задач теорії інформації та кодування
- •Тема 1 Кількісна оцінка інформації
- •Математичні основи теорії інформації. Міра Хартлі. Ентропія.
- •Оскільки основа логарифма дорівнює основі системи числення, для перевірки правильності розрахунків можна визначити всі можливі комбінації двійкового коду довжиною 4 біта:
- •Як видно, обидва варіанти рішення дали однаковий результат. Завдання для закріплення матеріалу заняття 1
- •Кількісна оцінка інформації в системах з нерівномірним розподілом імовірностей
- •Завдання для закріплення матеріалу заняття 2
- •Тема 2 Надлишковість повідомлень та оптимальне кодування
- •Оцінка недовантаження та надлишковості повідомлень
- •Згідно з формулою (3.1) визначаємо абсолютне недовантаження двійкового шестирозрядного повідомлення:
- •Завдання для закріплення матеріалу заняття 3
- •Оптимальне кодування повідомлень (стиск інформації)
- •Завдання для закріплення матеріалу заняття 4
- •Тема 3 Перешкодостійке кодування
- •Основи перешкодостійкого кодування. Оцінка перевіряючої та корегуючої здатності кодів
- •Завдання для закріплення матеріалу заняття 5
- •Паритетні коди. Кодування за парністю та непарністю повідомлень і блоків даних
- •Завдання для закріплення матеріалу заняття 6
- •Код Хеммінга
- •Завдання для закріплення матеріалу заняття 7
- •Циклічні коди
- •Завдання для закріплення матеріалу заняття 8
- •Значення двійкових логарифмів цілих та дробових чисел
- •Значення десяткових логарифмів цілих та дробових чисел
- •Приклади мінімальних неприводимих в полі двійкових чисел многочленів
- •Перелік використаних джерел
- •Додаткова література
Тема 2 Надлишковість повідомлень та оптимальне кодування
Заняття 3
Оцінка недовантаження та надлишковості повідомлень
Характерну для повідомлень природну надлишковість поділяють на семантичну надлишковість та статистичну надлишковість.
Семантична надлишковість характеризує лаконічність виразу змісту повідомлення. Якщо текст повідомлення можна навести в більш стислому вигляді без втрати змісту, це свідчить про наявність семантичної надлишковості. Наприклад, повідомлення “Приїжджаю завтра. Зустрічайте.” можна замінити скороченим повідомленням “Зустрічайте завтра.”, що дозволить зберегти зміст повідомлення та усунути семантичну надлишковість. Про відсутність семантичної надлишковості в повідомленні можна говорити лише в тому випадку, якщо будь-яке скорочення тексту такого повідомлення призводить до втрати можливості повного відтворення інформаційного змісту повідомлення (нагадаємо, що повідомлення або частина повідомлення, які не знімають невизначеності, не мають інформаційного навантаження, тобто характеризуються повною семантичною надлишковістю).
Оскільки з точки зору теорії інформації та кодування інформація розглядається без урахування змісту, усунення семантичної надлишковості не відноситься до класичних задач теорії інформації. При вирішенні задач теорії інформації будемо вважати, що семантична надлишковість в повідомленнях повністю відсутня (тобто, усувається на етапі підготовки інформації).
Для пояснення природи виникнення статистичної надлишковості згадаємо приклад 1.3. Згідно з цим прикладом розрядність повідомлень, необхідна для кодування 33 станів обчислювальної системи (при рівній імовірності знаходження системи в кожному з станів) двійковим кодом, склала 6 розрядів, в той час як кількість інформації в одному такому повідомленні приблизно дорівнювала 5.02 біт. Очевидно, що при передачі кожного з таких повідомлень 0.98 біта не буде нести інформаційного навантаження, тобто будуть надлишковими.
В розглянутих випадках прийнято говорити про недовантаження повідомлення, абсолютне значення якого визначається за формулою:
D = ( Нмакс – Н ) біт/повідомлення , (3.1)
де Нмакс – максимальна можлива ентропія на одне повідомлення визначеної розрядності (визначає потенціальні можливості повідомлень в перенесенні інформації); Н – фактичне значення ентропії на повідомлення (визначає фактично використані можливості повідомлень в перенесенні інформації).
Для пояснення суті наведеного виразу розглянемо приклад 3.1 (умова задачі базується на прикладі 1.3).
Приклад 3.1. Визначити абсолютне недовантаження двійкового шестирозрядного повідомлення, якщо в ньому міститься 5.02 біт інформації (імовірності надходження повідомлень вважати однаковими).
Розв’язок.
Визначимо максимальну кількість можливих значень, які можуть приймати шестирозрядні двійкові повідомлення. Для цього скористаємось формулою (1.1), враховуючи, що в нашому випадку m=2 та n=6:
N = 26 = 64 .
Максимальну ентропію на одне повідомлення (за умови однакової імовірності надходження повідомлень) визначаємо згідно з формулою (1.6):
Нмакс=log2 64 = 6 біт/повідомлення .
Фактична ентропія на повідомлення за умови рівних імовірностей надходження повідомлень дорівнює кількості інформації, яка випадає на одне повідомлення, тобто:
Н = 5.02 біт/повідомлення.