Зміст
Вступ
Елементи теорії кодування
Відстань Хеммінга
Матричне кодування
Групові коди
Досконалі і квазідосконалі коди
Висновки
Література
Вступ
Використання електронно-обчислювальних машин для переробки інформації з'явилося корінним етапом у вдосконаленні систем планування і управління на всіх рівнях народного господарства. Проте при цьому, на відміну від звичайних способів збору і обробки інформації, виникли проблеми перетворення інформації в символи, зрозумілі для машини. Невід'ємним елементом цього процесу є кодування інформації.
У теорії передачі інформації надзвичайно важливим є вирішення проблеми кодування і декодування, що забезпечує надійну передачу по каналах зв'язку з «шумом».
Метою даної роботи є розглянути деякі питання кодування інформації по каналах зв'язку з перешкодами.
Елементи теорії кодування
Передача інформації зводиться до передачі по якомусь каналу зв'язку символів деякого алфавіту. Проте в реальних ситуаціях сигнали при передачі практично завжди можуть спотворюватися, і переданий символ сприйматиметься неправильно. Наприклад, в системі ЕОМ → ЕОМ одна з обчислювальних машин може бути пов'язана з іншою через супутник. Канал зв'язку в цьому випадку фізично реалізується електромагнітним полем між поверхнею Землі і супутником. Електромагнітні сигнали, накладаючись на зовнішнє поле, можуть спотворитися і ослабитися. Для забезпечення надійності передачі інформації в таких системах розроблені ефективні методи, що використовують коди різних типів.
Одна з таких моделей зв’язана з груповими кодами.
Алфавіт, в якому записуються повідомлення, вважаємо за той, що складається з двох символів {0, 1}. Він називається двійковим алфавітом. Тоді повідомлення є кінцева послідовність символів цього алфавіту. Повідомлення, що треба передати, кодується по певній схемі довшою послідовністю символів в алфавіті {0, 1}. Ця послідовність називається кодом або кодовим словом. При прийомі можна виправляти або розпізнавати помилки, що виникли при передачі по каналу зв'язку, аналізуючи інформацію, що міститься в додаткових символах. Прийнята послідовність символів декодується по певній схемі в повідомлення, з великою вірогідністю співпадаюче з переданим.
Блоковий двійковий (m, n) -код визначається двома функціями: E:{0,1}m - {0, 1}n і D: {0, 1}n - {0, 1}m, де m . n і {0, 1}n - безліч всіх двійкових послідовностей довжини n. Функція E визначає схему кодування, а функція D - схему декодування. Математичну модель системи зв'язку можна представити у вигляді схеми (мал. 1):
Малюнок 1 – Модель системи зв'язку.
Тут T - «функція помилок» ; E і D вибираються так, щоб композиція D T E була функцією, з великою вірогідністю близькою до тотожної. Двійковий (m, n) -код містить 2m кодових слів.
Коди діляться на два великі класи: коди з виявленням помилок, які з великою вірогідністю визначають наявність помилки в прийнятому повідомленні, і коди з виправленням помилок, які з великою вірогідністю можуть відновити послане повідомлення.
Відстань Хеммінга На безлічі двійкових слів довжини m відстанню d(а, b) між словами а і b називають число неспівпадаючих позицій цих слів, наприклад: відстань між словами а = 01101 і b = 00111 рівне 2.
Визначене таким чином поняття називається відстанню Хеммінга. ............
