Міністерство освіти та науки україни кременчуцький державний політехнічний інститут кодування інформації
МЕТОДИЧНІ ВКАЗІВКИ ЩОДО ВИКОНАННЯ
РОЗРАХУНКОВО-ГРАФІЧНОЇ РОБОТИ З ДИСЦИПЛІНИ
“ТЕОРІЯ ІНФОРМАЦІЇ ТА КОДУВАННЯ”
ДЛЯ СТУДЕНТІВ СПЕЦІАЛЬНОСТІ
7.091501“Комп’ютерні системи та мережі”
ДЕННОЇ ФОРМИ НАВЧАННЯ
КРЕМЕНЧУК-2000
КОДУВАННЯ ІНФОРМАЦІЇ. Методичні вказівки до виконання розрахунково-графічної роботи з курсу «Теорія інформації та кодування» » для студентів спеціальності 7.091501 “Комп’ютерні системи та мережі” денної форми навчання.
Укладач: к.т.н., доцент М. І. Гученко
Кафедра комп’ютерної техніки та програмування
Затверджено методичною радою Кременчуцького державного політехнічного інституту, протокол №______від « » 2000р.
Голова методичної ради проф. Л.І. Пирогов
ЗМІСТ
Вступ………………………………………………………………………… 4
Кодування інформації ……………………………………………………… 5
Нерівномірні та рівномірні коди …………………………………………… 5
Префіксні коди ………………………………………………………………. 6
Надлишкові коди ……………………………………………………………. 9
Література …………………………………………………………………… 24
ВСТУП
Даний методичний посібник призначений для студентів, що вивчають дисципліну “ Теорія інформації та кодування ”.
У посібнику в стислій та доступній формі викладені основні задачі кодування, алгоритми побудови найбільш відомих ефективних та завадостійких кодів. Показані механізми знаходження та виправлення помилок.
Виклад ілюструється численними прикладами.
КОДУВАННЯ ІНФОРМАЦІЇ
Для передачі повідомлення по лінії зв’язку його треба закодувати.
Символи, при допомозі яких записується повідомлення, що передається, складають первинний алфавіт.
Символи, з яких складається повідомлення після кодування, називаються вторинним алфавітом.
Правило, що встановлює однозначну відповідність між символами первинного та вторинного алфавітів, називається кодом.
Комбінація символів вторинного алфавіту, яка відповідає одному символу первинного алфавіту називається кодовим словом ( кодовою комбінацією або кодовим вектором).
Основою коду (mod) називається кількість символів алфавіту, на якому побудований код.
Приклад:
для кодової комбінації 01011101010 - mod = 2;
Головними задачами, що вирішуються при кодуванні є:
Зменшення об’єму повідомлення ( коди, які дозволяють це зробити, називаються ефективними);
Знаходження та виправлення помилок, які виникають під впливом завад під час передачі по лінії зв’язку ( завадостійкі коди);
Захист інформації від несанкціонованого доступу (шифри).
Існує велика кількість кодів з різними властивостями.
Коди можуть бути утворені різноманітними способами з допомогою поліномів, матриць, графів і т.д.
НЕРІВНОМІРНІ ТА РІВНОМІРНІ КОДИ.
Коди, в яких повідомлення представляються кодовими словами з нерівною кількістю символів, називаються нерівномірними.
Нерівномірний код в системі числення з основою p, який складається з n знаків, може бути записаний у вигляді полінома:
an-1pn-1 + an-2pn-2+... + a2p2 + a1p1 + a0p0 (1)
В практиці широко застосовуються двійкові коди, алфавіт яких (вторинний) складається з двох символів 0 і 1 ( позначається B{0,1}).
Прикладом нерівномірного коду є простий двійковий код.
-
Символи первинного алфавіту
Кодові комбінації
a1
0
a2
1
a3
10
a4
11
a5
100
a6
101
a7
110
a8
111
a9
1000
….
…..
Якщо комбінації нерівномірного коду доповнити такого кількістю нулів, щоб число символів у кожній кодовій комбінації дорівнювало числу символів у найдовшому слові, то отримаємо рівномірний код.
-
Символи первинного алфавіту
Кодові комбінації
a1
0000
a2
0001
a3
0010
a4
0011
a5
0110
a6
0100
a7
0101
a8
0111
a9
1000
….
…..
Значністю коду називається кількість символів у кодовій комбінації.
Приклад:
значність комбінації 01011101010 дорівнює 11;