Завадостійке кодування

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Реферат
По курсу "Теорія інформації та кодування"
Тема:
"Завадостійке кодування"

Зміст
Введення
1. Завадостійкість
2. Виявляють коди
Список літератури

Введення

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

1. Завадостійкість
Завадостійкість - здатність системи здійснювати прийом інформації в умовах наявності перешкод в лінії зв'язку і спотворень у внутрішньо апаратних трактах. Завадостійкість забезпечує надійність і достовірність переданої інформації (даних). Ми будемо в основному розглядати двійкові коди. Двійкові (коди) дані передаються між обчислювальними терміналами, літальними апаратами, супутниками і т. д.
Передача даних в обчислювальних системах чутлива до малої частки помилку, тому що одиночна помилка може істотно порушити процес обчислень.
Найбільш часто помилки з'являються в УВВ, шинах, пристроях пам'яті. УВВ містять велику кількість елементів, помилки обумовлюються старінням елементів, погіршенням якості електричних з'єднань, расфазіровкой сигналів. Значна частина помилок припадає на ВП, внаслідок відмови окремих ІС або всієї ІС, помилок пов'язаних з флуктуацією напруги харчування і т. д.
У системах з багатьма користувачами і поділом за часом довгі виконавчі повідомлення поділяються на пакети.
Повідомлення, подані довгими послідовностями бітів, звичайно розбиваються на більш короткі послідовності бітів, називаються пакетами. Пакети можна передати по мережі як незалежні об'єкти і збирати з них повідомлення на кінцевому пункті. Пакет, забезпечений ім'ям і керуючими бітами на початку і в кінці, називається кадром. Управління лінією передачі даних здійснюється за спеціальним алгоритмом, званому протоколом.
Наявність перешкод ставить додаткові вимоги до методів кодування. Для захисту інформації від перешкод необхідно вводити в тому чи іншому вигляді надмірність: підвищення потужності сигналу; повторення повідомлень; збільшення довжини кодової комбінації і т. д.
Збільшення потужності сигналів призводить до ускладнення і подорожчання апаратури, крім того, в деяких системах передачі інформації є обмеження для передачі потужності, наприклад, супутниковий зв'язок.
Повторна передача повідомлень вимагає наявності буферів для зберігання інформації та наявності зворотного зв'язку для підтвердження достовірності переданої інформації. При цьому, значно падає швидкість передачі інформації, крім того цей метод не завжди м. б. використаний, наприклад, в система реального часу.
Одним з найбільш ефективних методів підвищення достовірності та надійності передачі даних є завадостійке кодування, що дозволяє за рахунок внесення додаткової надмірності (збільшення мінімального кодового відстані) у кодових комбінаціях переданих повідомлень забезпечити можливість виявлення та виправлення одиночних, кратних і групових помилок.
Мінімальна кодова відстань характеризує завадостійкість і надмірність повідомлень. У залежності від величини мінімального кодового відстані існують коди, які виявляють і виправляють помилки.
Кодова відстань - d визначається як кількість одиниць в результаті підсумовування за модулем два двох кодових комбінацій. Мінімальна кодова відстань d 0 - мінімальне з кодових відстаней всіх можливих кодових комбінацій.
Для виявлення r помилок мінімальне кодова відстань дорівнює:
d 0 ³ r +1. (1)

Для виявлення r помилок та виправлення s помилок мінімальне кодова відстань дорівнює:
d 0 ³ r + s +1. (2)
Тільки для виправлення помилок мінімальне кодова відстань дорівнює:
d 0 ³ 2s +1. (3)
2. Виявляють коди
Виявляють коди - це коди, що дозволяють виявити помилку, але не виправити її. Найпростіший спосіб виявлення помилки це додавання до послідовності бітів даних ще одного біта - біту перевірки на парність (непарність) значення, якого дорівнює сумі по модулю два вихідної послідовності бітів. Найчастіше організується перевірка на непарність.
У символьному коді ASCII до семи бітам коду додається восьмий біт перевірки на парність - k 1.
S 1 S 2 S 3 S 4 S 5 S 6 S 7 K 1
1
1
0
1
1
0
1
1
Однобітовий перевірка дозволяє виявити будь-яку одиничну помилку, дві помилки знайти не можна, в загальному випадку виявляється будь непарна кількість помилок.
Внесення надмірності за рахунок збільшення довжини кодової комбінації призводить до зниження швидкості передачі інформації.
Якщо швидкість ідеально використовує канал, то
. (4)
Якщо кодова комбінація довжиною n містить k інформаційних і m контрольних розрядів (n = k + m), то
.
Для коду ASCII n = 8 і k = 7
,
тобто введення одного надлишкового розряду призводить до зменшення пропускної здатності каналу зв'язку на 12,5%.
Найчастіше шуми (блискавки, розрив і т.д.) породжують довгі пакети помилок і ймовірність парного і непарного числа помилок однакова, а значить і однобітовий перевірка не ефективна.
Перевірка на парність по вертикалі і горизонталі. При цьому послідовність бітів даних перебудовується в двомірний масив, і обчислюються біти на парність, як для кожного рядка, так і для кожного стовпця.
При цьому можна виявити кілька помилок, якщо вони не розташовуються в однакових рядках і стовпцях.
Найчастіше використовується при передачі даних коду ASCII, кожен символ можна вважати рядком масиву. Така перевірка може не тільки встановити факт помилки, але і виявити її місце, а значить, є принципова можливість її виправлення, хоча це практично не використовується.
1 0 1 1 0 1 1 1
0 1 0 0 0 1 0 0
1 0 1 0 0 1 0 1
1 1 0 0 1 0 1 0
0 0 0 1 0 1 0 0


1 0 0 0 1 0 0
Після виявлення помилок іноді можна повторити передачу повідомлень, іноді після виявлення помилки робиться друга і навіть третя спроба передачі повідомлення. Така ситуація актуальна в дуплексних каналах, де застосування кодів, що виявляють помилки (Feedback or Backward Error Control), досить, так як сигналізація про помилку викликає повторну передачу від джерела. Це основні методи, використовувані в інформаційних мережах.
Перевірка на парність широко використовується на ЕОМ, як на апаратній, так і на програмному рівні.
Наприклад, при зчитуванні з магнітної стрічки у разі, коли умова на парність не виконується, то проводиться повторне зчитування, тобто якщо відбулася мала втрата намагніченості, то після другої спроби може бути зчитування відбудеться правильно.
Приклад 1. Символи алфавіту джерела кодуються семіразрядним двійковим кодом з вагою кодових векторів (кількістю одиниць в кодової комбінації) w = 3. Визначити необхідну потужність коду і його надмірність.
Рішення: Потужність семіразрядного коду дорівнює N = 2 7 = 128.
Так як для кодування використовуються тільки кодові вектора з вагою три, то кількість таких векторів у семіразрядном коді одно

Надмірність коду дорівнює R = 1 - log 2 K / log 2 N = 0,265.

Список літератури
1. Вернер М. Основи кодування. - М.: Техносфера, 2004.
2. Зюко А.Г., Кловський Д.Д., Назаров М.В., Фінк Л.М. Теорія передачі сигналів. М: Радіо і зв'язок, 2001 р . -368 С.
3. Кнут Дональд, Грехем Роналд, Паташнік Орен Конкретна математика. Підстава інформатики - М.: Світ; Біном. Лабораторія знань, 2006. - С. 703.
4. Лідовскій В.І. Теорія інформації. - М., «Вища школа», 2002. - 120с.
5. Метрологія та радіовимірювань в телекомунікаційних системах. Підручник для ВУЗів. / В. І. Нефьодов, В.І. Халкин, Є.В. Федоров та ін - М.: Вища школа, 2001 р . - 383с.
6. Рудаков О.М. Числа Фібоначчі та простота числа 2127 -1 / / Математичне Просвітництво, третя серія. - 2000. - Т. 4.
7. Стахов О.П. Коди золотої пропорції. -М.: Радіо та зв'язок, 1984.
8. Цапенко М.П. Вимірювальні інформаційні системи. - М.: Енергоатом издат, 2005. - 440С.
Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Реферат
22.8кб. | скачати


Схожі роботи:
Метод словникового кодування Зеева Лемпела Диференціальне кодування
Метод словникового кодування Зеева-Лемпела Диференціальне кодування
Арифметичне кодування Кодування довжин повторень
Кодування
Основи кодування
Кодування інформації
Кодування мовлення
Кодування зображень
Штрихове кодування
© Усі права захищені
написати до нас