Зміст
Вступ
Елементи Теорії кодування
Відстань Хеммінга
матричного кодування
Групові коди
Досконалі и квазідосконалі коди
Висновки
Література
Вступ
Використання електронно-обчислювальних машин для переробки ІНФОРМАЦІЇ з'явилося коріннім етапом у вдосконаленні систем планування и управління на всех рівнях народного господарства. Прото при цьом, на відміну від Звичайний способів збору и ОБРОБКИ ІНФОРМАЦІЇ, вініклі проблеми Перетворення ІНФОРМАЦІЇ У символі, зрозумілі для машини. Невід'ємнім елементом цього процеса є кодування ІНФОРМАЦІЇ.
У Теорії передачі ІНФОРМАЦІЇ Надзвичайно ВАЖЛИВО є Вирішення проблеми кодування и декодування, что Забезпечує надійну передачу по каналах зв'язку з В«шумомВ».
Метою даної роботи є Розглянуто деякі питання кодування ІНФОРМАЦІЇ по каналах зв'язку з Перешкоди.
Елементи Теорії кодування
Передача ІНФОРМАЦІЇ зводіться до передачі по якомусь каналу зв'язку сімволів Деяк алфавіту. Прото в реальному сітуаціях сигналі при передачі практично всегда могут спотворюватіся, и надіс символ спрійматіметься неправильно. Наприклад, в Системі ЕОМ в†’ ЕОМ одна з обчислювальних машин может буті пов'язана з іншою через супутник. Канал зв'язку в цьом випадка фізічно реалізується електромагнітнім полем между поверхнями Землі и супутником. Електромагнітні сигналі, накладаючісь на Зовнішнє поле, могут спотворітіся и ослабітіся. Для забезпечення надійності передачі ІНФОРМАЦІЇ в таких системах розроблені ефектівні методи, что Використовують коди різніх тіпів.
Одна з таких моделей зв'язана з груповий кодами.
алфавіт, в якому запісуються ПОВІДОМЛЕННЯ, Вважаємо за тією, что Складається з двох сімволів {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 - Модель системи зв'язку. br/>
Тут T - В«функція помилок В»; E и D вібіраються так, щоб композиція DTE булу функцією, з великою вірогідністю близьким до тотожної. Двійковій (m, n)-код містіть 2 m Кодові слів.
Коді діляться на два Великі класи: коди з виявленості помилок, Які з великою вірогідністю візначають наявність помилки в прийнятя Повідомленні, и коди з Виправленому помилок, Які з великою вірогідністю могут відновіті послань ПОВІДОМЛЕННЯ.
Відстань Хеммінга
На безлічі двійковіх слів Довжина m відстанню d (а, b) между словами а і b назівають число неспівпадаючіх позіцій ціх слів, Наприклад: відстань между словами а = 01101 и b = 00111 рівне 2. p> визначеня таким чином Поняття назівається відстанню Хеммінга. Воно задовольняє Наступний аксіомам відстаней:
1) d (а, b) 0 и d (а, b) = 0 тоді и Тільки тоді, коли а = b;
2) d (а, b) = d (b, а);
3) d (а, b) + d (b, з) d (а, з) (нерівність трикутника).
Вагою w (a) слова а назівають число одиниць среди его координат. Тоді відстань между словами а і b є вага їх суми а b: d (а, b) = w (а b), де символом позначені Операція покоординатного складання за модулем 2.
Інтуїтівно зрозуміло, что код тім краще прістосованій до Виявлення и виправлення помилок, чім больше розрізняються кодові слова. Поняття відстані Хеммінга дозволяє це уточніті.
Теорема. Для того, щоб код дозволялось віявляті помилки (або Менша) позіціях, звітність, и Достатньо, щоб найменша відстань между кодове слово булу k + 1.
Доведення цієї теореми аналогічно доказу Наступний Твердження.
Теорема. Для того, щоб код дозволялось віправляті ВСІ помилки (або Менша) позіціях, звітність, и Достатньо, щоб найменша відстань между кодове слово булу 2k + 1.
У математічній МОДЕЛІ кодування и декодування ЗРУЧНИЙ розглядаті рядки помилок. Дани ПОВІДОМЛЕННЯ a = a 1 a 2 ... a m кодується кодовий словом b = b 1 b 2 ... b n .. При передачі канал зв'язку додає до ньо...
