Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Принципи побудови завадостійких кодів

Найчастіше як передумову при введенні кодів розглядають деякий початковий набір чи вектор із m b – розрядних символів (у випадку двійкових символів b =1 і тоді такими символами є “0”и “1”), званий часто базовим кодовим словом (БКС). Зрозуміло, що кількість можливих БКС при цьому дорівнює кількості можливих кодових комбінацій N 0 = 2 bm. Кожне таке БКС можна розглядати як представлене в деякій системі числення (при b =1 у двійковій системі числення) число А, діапазон представлення яких (робочий діапазон коду) знаходиться в межах від 0 до 2 bm, тобто А Î [0, 2 bm). Для такого коду будь-яке випадкове спотворення можна розглядати у вигляді суми (часто, порозрядної, по модулю 2) початкового коду і двійкового m символьного випадкового вектора Е.:

,

де .

На числовій вісі ці вектори, як числа із діапазону [0, 2 bm), можуть мати представлення, наведене на рис. 1.

 


0 А Е 2 bm

Рис. 1. Діапазон представлення ненадлишкових чисел

У звичного (не завадостійкого, не надлишкового) коду така сума є новим двійковим вектором з того ж набору можливих кодових комбінацій. Знайти при цьому спотворення неможливо.

Завадостійкий код відрізняється від звичного коду тим, що в БКС, окрім початкового набору з m символів вводиться k додаткових, надлишкових, які передаються в канал (записуються в ЗП) разом з початковим набором. Кількість, правила формування і місця розташування цих надлишкових символів визначаються видом і властивостями завадостійкого коду. Надлишкові символи звичайно прийнято називати контрольними або перевірочними, а їх сукупність − контрольною ознакою (ознакою цілісності). Введення k надлишкових символів є рівносильним збільшенню діапазону представлення чисел в 2 bk разів, так що діапазон можливих представлень чисел в розширеному діапазоні

А Î [0, 2 bn),

де n = m + k. Для такого коду, як і раніше, будь-яке випадкове спотворення можна розглядати також у вигляді у вигляді суми по деякому модулю (наприклад, порозрядної по модулю 2 або простої суми по іншому модулю) початкового n символьного коду і двійкового n символьного випадкового вектору Е.

Процес завадостійкого кодування при цьому зводиться до наступного. Кожен перевірочний символ (або контрольна ознака в цілому) визначається (розраховується) як деяка функція (у деяких кодах, наприклад в кодах Хеммінга (див. нижче), як сукупність функцій) від початкового БКС або від сукупності його певних інформаційних символів. Які, конкретно, інформаційні символи беруть участь у формуванні цього перевірочного символу (або контрольної ознаки в цілому) і по якому закону він формується, визначається алгоритмом побудови даного коду. Дуже часто значення розрядів кожного перевірочного символу вибирається так, щоб порозрядна сума по модулю 2 цих розрядів інформаційних і даного перевірочного символів дорівнювала 0. Перевірочні символи, у принципі, можуть розташовуватися в кодовій комбінації на будь-якому місці. Для визначеності вважатимемо, що вони розміщуються в кінці початкового коду (повідомлення) . При цьому вимагають, щоб правильні, (не спотворені) числа в новому, розширеному діапазоні, як і раніше, відповідали вимозі А Î [0, 2 bm ]. Цей розширений діапазон має вигляд, представлений на рис. 2.

 
 

 


0 2 bm 22 bm (2 k – 1) 2 bm 2 bn

Рис. 2. Діапазони представлення чисел

 

Сукупність початкового числа А і його контрольної ознаки r (А) прийнято називати базовим кодовим словом (БКС) і, за певних умов, - завадостійким кодом і можна записати як:

А = (А, r (А)). (1)

 

Як і для більшості відомих кодів, будемо вважати, що спотворення можливе в одному із символів інформаційного об’єкта. В разі виникнення такого спотворення відповідний вектор та спотворене повідомлення, як число, із досить великою імовірністю будуть перевищувати величину робочого діапазону: , . Останнє як раз і свідчить про наявність спотворень в початковому числі А.

Після читання за тими ж правилами здійснюється перевірки. У кожну перевірку включаються як інформаційні, так і перевірочні символи. Якщо прийнята кодова комбінація залишилася в тій же підмножині, що і передана, то базове кодове слово не містить спотворення. Якщо ж комбінація в результаті спотворень переходить в іншу підмножину, тоді базове кодове слово містить спотворення. В результаті визначається факт наявності, а за певними умовами, місце і величина (характер) спотворення, що дає змогу його виправлення. Для цього достатньо визначити, в якому діапазоні (підмножині) знаходиться прийняте (зчитане) базове кодове слово.

<== предыдущая лекция | следующая лекция ==>
Задачі забезпечення цілісності і доступності інформаційних об’єктів в обчислювальних мережах. Методи захисту від спотворень | Завадостійке кодування та декодування. Загальний підхід щодо формування надлишкових символів
Поделиться с друзьями:


Дата добавления: 2014-01-04; Просмотров: 600; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.012 сек.