Вступ

Елементи теорії кодування

Відстань Хеммінга

Матричне кодування

Групові коди

Досконалі і квазідосконалі коди

Висновки

Література

Вступ

Використання електронно-обчислювальних машин для переробки інформації з'явилося корінним етапом у вдосконаленні систем планування і управління на всіх рівнях народного господарства. Проте при цьому, на відміну від звичайних способів збору і обробки інформації, виникли проблеми перетворення інформації в символи, зрозумілі для машини. Невід'ємним елементом цього процесу є кодування інформації.

У теорії передачі інформації надзвичайно важливим є вирішення проблеми кодування і декодування, що забезпечує надійну передачу по каналах зв'язку з «шумом».

Метою даної роботи є розглянути деякі питання кодування інформації по каналах зв'язку з перешкодами.

Елементи теорії кодування

Передача інформації зводиться до передачі по якомусь каналу зв'язку символів деякого алфавіту. Проте в реальних ситуаціях сигнали при передачі практично завжди можуть спотворюватися, і переданий символ сприйматиметься неправильно. Наприклад, в системі ЕОМ → ЕОМ одна з обчислювальних машин може бути пов'язана з іншою через супутник. Канал зв'язку в цьому випадку фізично реалізується електромагнітним полем між поверхнею Землі і супутником. Електромагнітні сигнали, накладаючись на зовнішнє поле, можуть спотворитися і ослабитися. Для забезпечення надійності передачі інформації в таких системах розроблені ефективні методи, що використовують коди різних типів.

Одна з таких моделей зв’язана з груповими кодами.

Алфавіт, в якому записуються повідомлення, вважаємо за той, що складається з двох символів {0, 1}. Він називається двійковим алфавітом. Тоді повідомлення є кінцева послідовність символів цього алфавіту. Повідомлення, що треба передати, кодується по певній схемі довшою послідовністю символів в алфавіті {0, 1}. Ця послідовність називається кодом або кодовим словом. При прийомі можна виправляти або розпізнавати помилки, що виникли при передачі по каналу зв'язку, аналізуючи інформацію, що міститься в додаткових символах. Прийнята послідовність символів декодується по певній схемі в повідомлення, з великою вірогідністю співпадаюче з переданим.

Блоковий двійковий (m, n) -код визначається двома функціями: E:{0,1}^m - {0, 1}ⁿ і D: {0, 1}ⁿ - {0, 1}^m , де m . n і {0, 1}ⁿ - безліч всіх двійкових послідовностей довжини n. Функція E визначає схему кодування, а функція D - схему декодування. Математичну модель системи зв'язку можна представити у вигляді схеми (мал. 1):

Малюнок 1 – Модель системи зв'язку.

Тут T - «функція помилок» ; E і D вибираються так, щоб композиція D T E була функцією, з великою вірогідністю близькою до тотожної. Двійковий (m, n) -код містить 2^m кодових слів.

Коди діляться на два великі класи: коди з виявленням помилок, які з великою вірогідністю визначають наявність помилки в прийнятому повідомленні, і коди з виправленням помилок, які з великою вірогідністю можуть відновити послане повідомлення.

Відстань Хеммінга

На безлічі двійкових слів довжини m відстанню d(а, b) між словами а і b називають число неспівпадаючих позицій цих слів, наприклад: відстань між словами а = 01101 і b = 00111 рівне 2.

Визначене таким чином поняття називається відстанню Хеммінга. Воно задовольняє наступним аксіомам відстаней:

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.

--> ЧИТАТЬ ПОЛНОСТЬЮ <--