ншого мінімізувати ймовірність помилки при декодуванні одержувачем. Для вибору типу кодування важливу роль відіграє так зване відстань Хеммінга. Нехай А і Б два двійкові кодові послідовності рівної довжини. Відстань Хеммінга між двома цими кодовими послідовностями дорівнює числу символів, якими вони відрізняються. Наприклад, відстань Хеммінга між кодами 00111 і 10101 одно 2.
. 1.2 Принципи завадостійкого кодування
У теорії завадостійкого кодування важливим є питання про використання надмірності для коригування виникають при передачі помилок. Тут зручно рас дивитися блокові коди, в яких завжди є можливість виділити окремі кодові комбінації. Для рівномірних кодів, які в подальшому тільки й будуть вивчатися, число можливих комбінацій одно M=2n, де n - значность коду.
У звичайному некорректірующем коді без надмірності, на приклад, в коді Бодо, число комбінацій М вибирається рівним числу повідомлень алфавіту джерела М0, і всі комбінації використовуються для передачі інформації. Коригувальні коди будуються так, щоб число комбінацій М перевищувала кількість комбінацій джерела М0. Однак у цьому випадку лише М0 комбінацій із загального числа використовуються для передачі інформації. Ці комбінації називаються дозволеними, а решта M - М0комбінаціі звуться заборонених. На приймальному кінці в декодер відомо, які комбінації є дозволеними і які - забороненими. Тому якщо передана дозволена комбінація в результаті помилки перетвориться в деяку заборонену комбінацію, то така помилка буде виявлена, а за певних умов - виправлена. Природно, що помилки, що призводять до утворення іншої дозволеної комбінації, не виявляються.
Різниця між комбінаціями рівномірного коду прийнято характеризувати відстанню, рівним числу символів, якими відрізняються комбінації одна від одної. Відстань між двома комбінаціями і визначається кількістю одиниць в сумі цих комбінацій по модулю два.
. 1.3 Методи виявлення помилок
Велика частина протоколів канального рівня виконує тільки одну задачу - виявлення помилок, вважаючи, що коригувати помилки, тобто повторно передавати дані, повинні протоколи верхніх рівнів. Однак існують протоколи канального рівня, які самостійно вирішують завдання відновлення спотворених або втрачених кадрів.
Але не можна вважати, що один протокол краще іншого тому, що він відновлює помилкові кадри, а інший протокол - ні. Кожен протокол повинен працювати в тих умовах, для яких він розроблений.
Всі методи виявлення помилок засновані на передачі службової надлишкової інформації, за якою можна судити з деяким ступенем ймовірності про достовірність прийнятих даних. Цю службову інформацію прийнято називати контрольною сумою. Контрольна сума обчислюється як функція від основної інформації, причому необов'язково тільки шляхом підсумовування. Приймаюча сторона повторно обчислює контрольну суму кадру за відомим алгоритмом і в разі її збігу робить висновок про те, що дані були передані правильно.
. 1.4 Коди Хеммінга
Код Хеммінга являє собою блоковий код, який дозволяє виявити і виправити помилково переданий біт в межах переданого блоку. Зазвичай код Хеммінга характеризується двома цілими числами, наприклад, (11,7) при надсиланні 7-бітних ASCII-кодів. Такий запис говорить, що при передачі 7-бітного коду використовується 4 контрольних біта (7 + 4=11). При цьому передбачається, що мала місце помилка в одному бите і що помилка у двох або більше бітах істотно менш вірогідна. З урахуванням цього виправлення помилки здійснюється з певною ймовірністю. Наприклад, нехай можливі наступні правильні коди (всі вони, крім першого і останнього, відстоять один від одного на відстань 4:
При одержанні коду 00000111 не важко припустити, що правильне значення отриманого коду одно 00001111. Інші коди відстоять від отриманого на більшу відстань Хеммінга.
. 1.5 Циклічні коди
До числа ефективних кодів, що виявляють поодинокі, кратні помилки і пачки помилок, відносяться циклічні коди (CRC - Cyclic Redundance Code). Вони високо надійні і можуть застосовуватися при блокової синхронізації, при якій виділення, наприклад, біта непарності, було б важко.
Один з варіантів циклічного кодування полягає в множенні вихідного коду на утворює поліном g (x), а декодування - в розподілі на g (x). Якщо залишок від ділення не дорівнює нулю, то сталася помилка. Сигнал про помилку надходить на передавач, що викликає повторну передачу.
Утворюючий поліном є двійкове представлення одного з простих множників, на які розкладається число Xn - 1, де Xn позначає одиницю в n-му розряді, n дорівнює числу розрядів кодової групи. ...
