Білоруський державний університет інформатики і радіоелектроніки
кафедра РЕЗ
реферат на тему:
«Класифікація завадостійких кодів. Особливості практичного кодування »
МІНСЬК, 2009
КОРОТКА КЛАСИФІКАЦІЯ Завадостійке КОДІВ
Рис 1. Класифікація завадостійких кодів
До теперішнього часу розроблено багато різних завадостійких кодів, що відрізняються один від одного підставою, відстанню, надлишковістю, структурою, функціональним призначенням, енергетичною ефективністю, кореляційними властивостями, алгоритмами кодування і декодування, формою частотного спектру. На малюнку, представленому вище, наведені типи кодів, що розрізняються за особливостями структури, функціональним призначенням, фізичним властивостям коду як сигналу.
Найбільш важливий підклас безперервних кодів утворюють сверточних коди, що відрізняються від інших безперервних кодів методом побудови і більш широкою сферою застосування.
У загальному випадку, чим довше код при фіксованій надмірності, тим більше відстань і тим вище завадостійкість коду. Однак довгі коди складно реалізуються. Складові коди дають компромісне рішення задачі; з них основне значення мають каскадні коди та коди твори. Як правило, каскадний код складається з двох ступенів (каскадів): внутрішньої і зовнішньої. По лінії зв'язку сигнали передають внутрішнім кодом n вт, символьні слова якого є символами зовнішнього коду довжини n вш. Підстава зовнішнього коду одно q вт k.
Коди твори будують у вигляді матриці, в якому рядки суть слова одного коду, а стовпці - того ж або іншого коду.
При формуванні каскадного коду вхідні інформаційну послідовність символів розбивають на блоки по k вт символів у кожному, кожен блок зіставляють з інформаційним символом зовнішнього коду з алфавіту, що містить q вт k значень символів. Потім k вш інформаційних символів зовнішнього коду перетворять в блоки з n вш символів зовнішнього коду і, нарешті, блоки з k вт інформаційних символів внутрішнього коду преоб-роззують в блоки з n вт символів внутрішнього коду. Можливі різні варіанти: зовнішній і внутрішній коди - блокові, зовнішній блочний - внутрішній сверточних, зовнішній сверточних - внутрішній блоковий, зовнішній і внутрішній сверточних.
Один з найбільш поширених методів формування коду твору полягає в послідовній запису за k 1 символів вхідний інформаційної послідовності в k 2 рядків матриці (наприклад, в осередки пам'яті ОЗУ), додаванні надлишкових символів по n 1-k 1 у кожен рядок і по n 2 - k 2 в кожен стовпець, після чого в послідовність символів коду зчитують по рядках або стовпцях з матриці. Фізичним аналогом коду твору є, зокрема, частотно-часової код, у якого рядка розташовуються уздовж осі часу, а стовпці - по осі частот.
Параметри складових кодів: каскадних - n = n вш n вт, k = k вш k вт, d = d вш d вт; твори - n = n 1 n 2, k = k 1 k 2, d = d 1 d 2.
Похідні коди будують на основі деякого вихідного коду, до якого або додають символи, збільшуючи відстань (розширений код), або скорочують частина інформаційних символів без зміни відстані (укорочений код), або викидають (виколюють) деякі символи (виколоті, або перфорований код). Код Хеммінга дає приклад процедури розширення, збільшує відстань коду з 3 до 4. Необхідність у виколювання виникає в результаті побудови на основі вихідного коду іншого, менш потужного, більш короткого коду з тим же відстанню.
При більш широкому трактуванні терміна "похідний код" до цього класу можна віднести всі коди, отримані з вихідного додаванням або виключенням як символів, так і слів.
Формально розподіл кодів на виконавчі і Недвійкова носить штучний характер; за аналогією слід виділяти трійчастий, четверичная та інші коди більшої підстави. Виправдовується такий розподіл ускладненням алгоритмів побудови, кодування і декодування Недвійкова кодів.
За інших рівних умов бажано, щоб інформаційні та надлишкові символи розташовувалися окремо. У систематичних кодах це умова виполняется.В циклічних кодах кожне слово містить всі свої циклічні перестановки. Всі n циклічних перестановок (слова довжини n) утворюють цикл. У квазіцікліческіх кодах цикл утвориться на числі символів n-1 або, рідше, n-2. Циклічні коди важливі як з точки зору математичного опису, так і для побудови та реалізації коду.
Помилки в каналах зв'язку мають саме різне розподіл, однак для вибору завадостійкого коду доцільно розділити всі можливі конфігурації помилок на незалежні (некорельованих) і пакети (корельовані помилки). На практиці доводиться враховувати якість інтервалів між пакетами: вони можуть бути вільними від помилок або ж містити випадкові незалежні помилки.
Під кореляційними увазі коди, що володіють хорошими кореляційними властивостями, важливими при передачі сигналів входження в зв'язок, для підвищення захищеності від деяких видів перешкод, вилучення сигналів з інтенсивних шумів, забезпечення многостанционного доступу, побудови асинхронно-адресних систем зв'язку. Кореляційні коди включають в себе пари протилежних сигналів з хорошою функцією автокореляції (метод внутріімпульсной модуляції), імпульсно-інтервальні коди, що мають на фіксованому інтервалі часу постійне для всіх слів коду число імпульсів з пеперекривається (при будь-якому взаємному зсуві слів в часі) значеннями інтервалів між імпульсами , ансамблі сигналів з хорошими взаімокорреляціоннимі властивостями.
Особливий клас утворюють частотно-компактні коди, призначені для зосередження енергії сигналу в можливо більш вузькій смузі частот. Настільки загальна постановка задачі розуміється в різних системах зв'язку по-різному: в дротяних лініях і лінійних трактах, що містять смугасто-обмежують фільтри з крутими фронтами, необхідно основну енергію сігналa "відсунути" від крайніх частот до центру смуги пропускання метою зменшення міжсимвольні спотворень; в мережах радіозв'язку з жорсткими обмеженнями щодо електромагнітної сумісності радіозасобів від коду вимагається значно (на десятки децибел) зменшити рівень позасмугових випромінювань. Побудова кодування і декодування частотно-компактних кодів істотно залежать від методу модуляції.
Арифметичні коди служать для боротьби з помилками при виконанні арифметичних операцій в процесорі ЕОМ.
Далі розглядаються два типи кодів: блокові і деревоподібні. Визначальний відмінність між кодерами для кодів цих двох типів полягає в наявності або відсутності пам'яті. Кодер для блокового коду є пристроєм без пам'яті, що відображає послідовності з k вхідних символів в послідовності з n вихідних символів. Термін "без пам'яті" вказує, що кожний блок з n символів залежить тільки від відповідного блоку з k символів і не залежить від інших блоків. Це не означає, що кодер не містить елементів пам'яті. Важливими параметрами блокового коду є n, k, R = k / n і d min. На практиці значення k лежать між 3 і декількома сотнями, a R = = 1 / 4 ... 7 / 8. Значення, що лежать поза цими межами, є можливими, але часто призводять до деяких практичних труднощів. Вхідні і вихідні послідовності зазвичай складаються з двійкових символів, але іноді можуть складатися з елементів деякого алфавіту більшого об'єму. Кодер для деревовидного коду є пристроєм з пам'яттю, в яке надходять набори з m двійкових вхідних символів, а на виході з'являються набори з n двійкових вихідних символів. Кожен набір n вихідних символів залежить від поточного вхідного набору і від v попередніх вхідних символів. Таким чином, пам'ять кодера повинна містити v + m вхідних символів. Параметр v + m часто називають довжиною кодового обмеження даного коду і позначають k = v + m (не слід плутати з параметром k для блокового коду). Зазначимо, що позначення часто не узгоджуються один з одним. Деякі автори називають довжиною кодового обмеження параметр k, у той час як інші - параметр v. Тут довжиною кодового обмеження будемо називати величину v, оскільки це призводить до меншої плутанини для кодів з m> 1. Параметр k = v + m майже не буде використовуватися. Деревоподібні коди характеризуються також швидкістю R = m / n і вільним відстанню d св. Точне визначення d св більш громіздко, ніж визначення d min для блокових кодів, однак параметр d св, по суті, містить ту ж інформацію про код, що і d min. Типові значення параметрів деревовидних кодів такі: m, n = 1 ... 8, R = 1 / 4 ... 7 / 8, v = 2 ... 60.
При іншому підході коди можна розділити на лінійні та нелінійні. Лінійні коди утворюють векторний простір і мають наступним важливим властивістю: два кодових слова можна скласти, використовуючи відповідне визначення суми, і одержати третє кодове слово. Що стосується звичайних двійкових кодів ця операція є посимвольним складанням двох кодових слів за модулем 2 (тобто 1 +1 = 0, 1 +0 = 1, 0 +0 = 0). Це властивість приводить до двох важливих наслідків. Перше з них полягає в тому, що лінійність істотно спрощує процедури кодування та декодування, дозволяючи висловити кожне кодове слово у вигляді "лінійної" комбінації невеликого числа виділених кодових слів, так званих базисних векторів. Друга властивість полягає в тому, що лінійність істотно спрощує завдання обчислення параметрів коду, оскільки відстань між двома кодовими словами при цьому еквівалентно відстані між кодовим словом, що складається цілком з нулів, і деяким іншим кодовим словом. Таким чином, при обчисленні параметрів лінійного коду досить розглянути, що відбувається при передачі кодового слова, що складається цілком з нулів. Обчислення параметрів спрощується ще й тому, що відстань Хеммінга між даними кодовим словом і нульовим кодовим словом дорівнює числу ненульових елементів даного кoдового слова. Це число часто називають вагою Хеммінга даного слова, і список, що містить число кодових слів кожного ваги, можна використовувати для обчислення характеристик коду за допомогою адитивної кордону. Такий список називають спектром коду.
Лінійні коди відрізняються від нелінійних замкнутістю кодового безлічі щодо деякого лінійного оператора, наприклад складання або множення слів коду, розглянутих як вектори простору, що складається з кодових слів - векторів. Лінійність коду спрощує його побудову та реалізацію. При великій довжині практично можуть бути використані тільки лінійні коди. Разом з тим часто нелінійні коди мають кращими параметрами в порівнянні з лінійними. Для відносно коротких кодів складність побудови та реалізації лінійних і нелінійних кодів приблизно однакова.
Як лінійні, так і нелінійні коди утворюють великі класи, які містять багато різних конкретних видів завадостійких кодів. Серед лінійних блокових найбільше значення мають коди з одного перевіркою на парність, M-коди (симплексних), ортогональні, біортогональние, Хеммінга, Боуза-Чоудхурі-хоквінгема, Голі, квадратично-вичетние (KB), Ріда-Соломона. До нелінійним відносять коди з контрольною сумою, інверсні, Нордстрома-Робінсона (HP), з постійною вагою, з перестановки з повторенням і без повторення символів (повні коди ортогональних таблиць, проективних груп, груп Матьє та інших груп перестановок).
Майже всі схеми кодування, які застосовуються на практиці, засновані на лінійних кодах. Подвійні лінійні блокові коди часто називають груповими кодами, оскільки кодові слова складають математичну структуру, яка називається групою. Лінійні деревоподібні коди зазвичай називають сверточних кодами, оскільки операцію кодування можна розглядати як дискретну згортку вхідної послідовності з імпульсним відгуком кодера.
Нарешті, коди можна розбити на коди, що виправляють випадкові помилки, і коди, що виправляють пакети помилок. В основному ми будемо мати справу з кодами, призначеними для виправлення випадкових, або незалежних, помилок. Для виправлення пакетів помилок було створено багато кодів, що мають хороші параметри. Однак при наявності пачок помилок часто виявляється більш вигідним використовувати коди, що виправляють випадкові помилки, разом з пристроєм перемежения відновлення. Такий підхід містить у собі процедуру перемішування порядку символів в закодованій послідовності перед передачею і відновленням вихідного порядку символів після прийому з тим, щоб рандомізовані помилки, об'єднані в пакети.
Особливості практичного кодування
Припустимо, що все що представляють інтерес дані можуть бути представлені у вигляді двійкової (закодованою двійково) інформації, тобто у вигляді послідовності нулів та одиниць. Завдання формулюється стандартно. Ця двійкова інформація підлягає передачі по каналу, схильній до випадкових помилок. Завдання кодування полягає в такому додаванні до інформаційних символів додаткових символів, щоб на приймачі ці спотворення могли бути знайдені і виправлені. Інакше кажучи, послідовність символів даних представляється у вигляді деякої довшої послідовності символів, надмірність якої достатня для захисту даних.
Двійковий код потужності М і довжини n представляє собою безліч з М двійкових слів довжини n, званих кодовими словами. Зазвичай М = 2 k, де k - деяке ціле число; такий код називається двійковим (n, k)-кодом.
Наприклад, можна побудувати наступний код: 10101 10010 01110 11111 Це дуже бідна (і дуже маленький) код з M = 4 і n = 5, але він задовольняє наведеним вище визначенням. Даний код можна використовувати для представлення 2-бітових двійкових чисел, використовуючи наступне (довільна) відповідність:
00 <-> 10101, 01 <-> 10010, 10 <-> 01110, 11 <-> lllll.
Якщо отримано одне з чотирьох 5-бітових кодових слів, то вважаємо, що відповідні йому два біта є правильною інформацією. Якщо сталася помилка, то ми отримаємо 5-бітове слово, що відрізняється від кодових слів. Тоді спробуємо знайти найбільш ймовірно передане слово і візьмемо його в якості оцінки вихідних двох бітів інформації. Наприклад, якщо ми прийняли 01100, то вважаємо, що передавалося 01110, і, отже, інформаційне слово дорівнювало 10.
У наведеному прикладі код не є хорошим, так як він не дозволяє виправляти багато конфігурацій помилок. Бажано вибирати коди так, щоб кожне кодове слово по можливості більше відрізнялося від кожного іншого кодового слова; зокрема, це бажано в тому випадку, коли довжина блоку велика.
Mожет здатися, що досить визначити вимоги до "хорошої кодом" і потім зробити машинний пошук по безлічі всіх можливих кодів. Але скільки кодів існує для даних n і k? Кожне кодове слово являє собою послідовність n двійкових символів, і всього є 2 k таких слів, отже, код описується n2 k двійковими символами. Всього існує 2 n2k способів вибору цих двійкових символів, отже, число різних (n, k)-кодів одно цього числа. Звичайно, дуже багато хто з цих кодів не представляють інтересу (як у випадку, коли два кодових слова рівні), так що треба або перевіряти це по ходу пошуку, або розвинути деяку теорію, що дозволяє виключити такі коди.
Наприклад, виберемо (n, k) = (40,20) - код, дуже помірний за сучасними стандартами. Тоді число таких кодів перевершить величину 10 10000000 - неймовірно велика кількість! Отже, неорганізовані процедури пошуку безсилі.
У загальному випадку блокові коди визначаються над довільним кінцевим алфавітом, скажімо над алфавітом із q символів {0, 1, 2, ..., q - 1}. На перший погляд введення алфавітів, відмінних від двійкового, може здатися зайвим узагальненням. З міркувань ефективності, однак, багато сучасних канали є Недвійкова, і коди для цих каналів мають бути Недвійкова. Насправді коди для Недвійкова каналів часто виявляються досить хорошими, і сам цей факт може служити причиною для використання Недвійкова каналів. Двійкові дані джерела тривіальним чином представляються символами q-ічного алфавіту, особливо якщо q дорівнює ступеня двійки, як це зазвичай і буває на практиці.
Визначення. Блоковий код потужності М над алфавітом із q символів визначається як множина з М (q-ічних послідовних довжини q, званих кодовими, словами.
Якщо q = 2, то символи називаються бітами. Зазвичай М = q k для деякого цілого k, і ми будемо цікавитися тільки цим випадком, називаючи код (n, k)-кодом. Кожній послідовності з k q-ічних символів можна зіставити послідовність з n q-ічних символів, що є кодовим словом.
Є два основні класи кодів: блокові коди і деревоподібні коди; вони ілюструються рис. 1. Блоковий код задає блок з k інформаційних символів n-символьним кодовим словом. Швидкість R блокового коду визначається рівністю R = k / n. (Швидкість - величина безрозмірна або, можливо, вимірюється в одиницях біт / біт або символ / символ. Її слід відрізняти від іншого званого тим же терміном швидкість поняття, що вимірює канальну швидкість в біт / с. Використовується й інше визначення швидкості: R = (k / n) log e q, одиницею якого є нат / символ, де один нат дорівнює log 2 e бітів. Прийнято також визначення R = (k / n) log 2 q, в якому швидкість вимірюється в одиницях біт / символ.)
Рис. 2. Основні класи кодів.
Деревоподібний код більш складний. Він відображає нескінченну послідовність інформаційних символів, що надходить зі швидкістю k 0 символів за один інтервал часу, в безперервну послідовність символів кодового слова зі швидкістю n 0 символів за один інтервал часу. Cосредоточім увагу на блокових кодах.
Якщо повідомлення складається з великого числа бітів, то в принципі краще використовувати один кодовий блок великої довжини, ніж послідовність кодових слів з більш короткого коду. Природа статистичних флуктуацій така, що випадкова конфігурація помилок зазвичай має вигляд серії помилок. Деякі сегменти цієї конфігурації містять більше середнього числа помилок, а деякі менше. Отже, при одній і тій же швидкості більш довгі кодові слова набагато менш чутливі до помилок, чим більш короткі кодові слова, але, звичайно, відповідні кодер і декодер можуть бути більш складними. Наприклад, припустимо, що 1000 інформаційних бітів передаються за допомогою (уявного) 2000-бітового двійкового коду, здатного виправляти 100 помилок. Порівняємо таку можливість з передачею одночасно 100 бітів за допомогою 200-бітового коду, що виправляє 10 помилок на блок. Для передачі 1000 бітов необхідно 10 таких блоків. Друга схема також може виправляти 100 помилок, але лише тоді, коли вони розподілені приватним чином - по 10 помилок у 200-бітових подблока. Перша схема може виправляти 100 помилок незалежно від того, як вони розташовані всередині 2000-бітового кодового слова. Вона суттєво ефективніше.
Ці евристичні міркування можна обгрунтувати теоретично, але тут ми до цього не прагнемо. Ми тільки хочемо обгрунтувати той факт, що хорошими є коди з великою довжиною блоку і що дуже хорошими кодами є коди з дуже великою довжиною блоку. Такі коди може бути дуже важко знайти, а будучи знайденими, вони можуть зажадати складних пристроїв для реалізації операцій кодування і декодування.
Про блоковому коді судять за трьома параметрами: довжині блоку n, інформаційної довжині k і мінімального відстані d *. Мінімальна відстань є мірою відмінності двох найбільш схожих кодових слів. Мінімальна відстань вводиться двома наступними визначеннями.
Визначення. Відстанню по Хеммінга між двома q-ічнимі послідовностями х і у довжини n називається число позицій, в яких вони різні. Це відстань позначається через d (х, у).
Наприклад, візьмемо х = 10101 і в = 01100; тоді маємо d (10101, 01100) = 3. В якості іншого прикладу візьмемо х = 30102 і в = 21103; тоді d (30102, 21103) = 3.
Визначення. Нехай C = {з i, i = 0, ..., М - 1} - код. Тоді мінімальна відстань коду C одно найменшому від усіх відстаней по Хеммінга між різними парами кодових слів, тобто
d * = min d (c i, з j).
(N, k)-код з мінімальним відстанню d * називається також (n, k, d *)-кодом.
У коді C, обраному в прикладі, d (10101, 10010) = 3, d (10010, 01110) = 3, d (10101, 01110) = 4, d (10010, 11111) == 3, d (10101, 11111 ) = 2, d (01110, 11111) = 2; отже, для цього коду d * = 2.
Припустимо, що передано кодове слово і в каналі відбулася одиночна помилка. Тоді прийняте слово знаходиться на рівному 1 відстані по Хеммінга від переданого слова. У випадку, коли відстань до кожного іншого кодового слова більше ніж 1, декодер виправить помилку, якщо покладе, що дійсно переданим словом було найближчим до прийнятого кодове слово.
У більш загальному випадку якщо відбулося t помилок і якщо відстань від прийнятого слова до кожного іншого кодового слова більше t, то декодер виправить ці помилки, прийнявши найближчим до прийнятого кодове слово як дійсно переданого. Це завжди буде так, якщо
d *> = 2t + 1.
Іноді вдається виправляти конфігурацію з t помилок навіть тоді, коли ця нерівність не задовольняється. Однак якщо d * <2t + 1, то виправлення будь-яких t помилок не може бути гарантовано, тому що тоді воно залежить від того, яке слово передавалося і яка була конфігурація з t помилок всередині блоку.
Геометрична ілюстрація дається на рис. 3.4.
Рис. 3.4. Сфери декодування.
У просторі всіх (q-ічних n-послідовностей вибрано деякий безліч n-послідовностей, оголошених кодовими словами. Якщо d * - мінімальна відстань цього коду, а t - найбільше ціле число, яке задовольняє умові d *> = 2t + 1, то навколо кожного кодового слова можна описати непересічні сфери радіуса t. Прийняті слова, що лежать всередині сфер, декодуються як кодове слово, яке є центром відповідної сфери. Якщо сталася не більше t помилок, то прийняте слово завжди лежить всередині відповідної сфери і декодується правильно.
Деякі прийняті слова, що містять більше t помилок, потраплять всередину сфери, описаної навколо іншого кодового слова, і будуть декодовані неправильно. Інші прийняті слова, що містять більше t помилок, потраплять в проміжні між сферами декодування області. У залежності від застосування останній факт можна інтерпретувати одним із двох способів.
Неповний декодер декодує тільки ті прийняті слова, які лежать всередині сфер декодування, описаних навколо кодових слів. Решта прийняті слова, що містять більше дозволеної кількості помилок, декодер оголошує нерозпізнаних. Такі конфігурації помилок при неповному декодуванні називаються Помилки, що не. Більшість використовуваних декодерів є неповними декодерами. Повний декодер декодує кожне прийняте слово найближчим кодове слово. Геометрично це представляється наступним чином: повний декодер розрізає проміжні області на шматки і приєднує їх до сфер так, що кожна точка потрапляє в найближчу сферу. Зазвичай деякі крапки перебувають на рівних відстанях від кількох сфер; тоді одна з цих сфер довільно оголошується найближчій. Якщо відбувається більш t помилок, то повний декодер часто декодує неправильно, але бувають і випадки потрапляння в правильне кодове слово. Повний декодер використовується в тих випадках, коли краще вгадувати повідомлення, ніж взагалі не мати ніякої його оцінки. Можна також розглядати канали, в яких крім помилок відбуваються і стирання. Це означає, що конструкцією приймача передбачено оголошення символу стертим, якщо він отриманий ненадійно або якщо приймач розпізнав наявність інтерференції або збій. Такий канал має вхідний алфавіт потужності q вихідний алфавіт потужності q + 1; додатковий символ називається стиранням. Наприклад, стирання символу 3 в повідомленні 12345 призводить до слова 12-45. Це не слід плутати з іншого операцією, званої викиданням, яка дає 1245.
B таких каналах можуть використовуватися коди, контролюючі помилки. У разі коли мінімальна відстань коду одно d *, будь-яка конфігурація з р стирок може бути відновлена, якщо d *> = р + 1. Далі, будь-яка конфігурація з v помилок і р стирок може бути декодована за умови, що
d *> = 2v + 1 + р.
Для доказу викинемо з усіх кодових слів ті р компонент, в яких приймач справив стирання. Це дасть новий код, мінімальна відстань якого не менше d * - р; отже, v помилок можуть бути виправлені за умови, що виконується виписане вище нерівність. Таким чином, можна відновити вкорочене кодове слово з р стертими компонентами. Нарешті, так як d *> р + 1, існує тільки одне кодове слово, що збігається з отриманим в нестертих компонентах; отже, вихідне кодове слово може бути відновлено.
ЛІТЕРАТУРА
1. Лідовскій В.І. Теорія інформації. - М., «Вища школа», 2002р. - 120с.
2. Метрологія та радіовимірювань в телекомунікаційних системах. Підручник для ВУЗів. / В. І. Нефедов, В. І. Халкин, Є. В. Федоров та ін - М.: Вища школа, 2001 р . - 383с.
3. Цапенко М.П. Вимірювальні інформаційні системи. -. - М.: Енергоатом издат, 2005. - 440С.
4. Зюко А.Г. , Кловський Д.Д., Назаров М.В., Фінк Л.М. Теорія передачі сигналів. М: Радіо і зв'язок, 2001 р . -368 С.
5. Б. Скляр. Цифрова зв'язок. Теоретичні основи та практичне застосування. Вид. 2-е, испр.: Пер. з англ. - М.: Видавничий дім «Вільямс», 2003 р . - 1104 с.
кафедра РЕЗ
реферат на тему:
«Класифікація завадостійких кодів. Особливості практичного кодування »
МІНСЬК, 2009
КОРОТКА КЛАСИФІКАЦІЯ Завадостійке КОДІВ
Рис 1. Класифікація завадостійких кодів
До теперішнього часу розроблено багато різних завадостійких кодів, що відрізняються один від одного підставою, відстанню, надлишковістю, структурою, функціональним призначенням, енергетичною ефективністю, кореляційними властивостями, алгоритмами кодування і декодування, формою частотного спектру. На малюнку, представленому вище, наведені типи кодів, що розрізняються за особливостями структури, функціональним призначенням, фізичним властивостям коду як сигналу.
Найбільш важливий підклас безперервних кодів утворюють сверточних коди, що відрізняються від інших безперервних кодів методом побудови і більш широкою сферою застосування.
У загальному випадку, чим довше код при фіксованій надмірності, тим більше відстань і тим вище завадостійкість коду. Однак довгі коди складно реалізуються. Складові коди дають компромісне рішення задачі; з них основне значення мають каскадні коди та коди твори. Як правило, каскадний код складається з двох ступенів (каскадів): внутрішньої і зовнішньої. По лінії зв'язку сигнали передають внутрішнім кодом n вт, символьні слова якого є символами зовнішнього коду довжини n вш. Підстава зовнішнього коду одно q вт k.
Коди твори будують у вигляді матриці, в якому рядки суть слова одного коду, а стовпці - того ж або іншого коду.
При формуванні каскадного коду вхідні інформаційну послідовність символів розбивають на блоки по k вт символів у кожному, кожен блок зіставляють з інформаційним символом зовнішнього коду з алфавіту, що містить q вт k значень символів. Потім k вш інформаційних символів зовнішнього коду перетворять в блоки з n вш символів зовнішнього коду і, нарешті, блоки з k вт інформаційних символів внутрішнього коду преоб-роззують в блоки з n вт символів внутрішнього коду. Можливі різні варіанти: зовнішній і внутрішній коди - блокові, зовнішній блочний - внутрішній сверточних, зовнішній сверточних - внутрішній блоковий, зовнішній і внутрішній сверточних.
Один з найбільш поширених методів формування коду твору полягає в послідовній запису за k 1 символів вхідний інформаційної послідовності в k 2 рядків матриці (наприклад, в осередки пам'яті ОЗУ), додаванні надлишкових символів по n 1-k 1 у кожен рядок і по n 2 - k 2 в кожен стовпець, після чого в послідовність символів коду зчитують по рядках або стовпцях з матриці. Фізичним аналогом коду твору є, зокрема, частотно-часової код, у якого рядка розташовуються уздовж осі часу, а стовпці - по осі частот.
Параметри складових кодів: каскадних - n = n вш n вт, k = k вш k вт, d = d вш d вт; твори - n = n 1 n 2, k = k 1 k 2, d = d 1 d 2.
Похідні коди будують на основі деякого вихідного коду, до якого або додають символи, збільшуючи відстань (розширений код), або скорочують частина інформаційних символів без зміни відстані (укорочений код), або викидають (виколюють) деякі символи (виколоті, або перфорований код). Код Хеммінга дає приклад процедури розширення, збільшує відстань коду з 3 до 4. Необхідність у виколювання виникає в результаті побудови на основі вихідного коду іншого, менш потужного, більш короткого коду з тим же відстанню.
При більш широкому трактуванні терміна "похідний код" до цього класу можна віднести всі коди, отримані з вихідного додаванням або виключенням як символів, так і слів.
Формально розподіл кодів на виконавчі і Недвійкова носить штучний характер; за аналогією слід виділяти трійчастий, четверичная та інші коди більшої підстави. Виправдовується такий розподіл ускладненням алгоритмів побудови, кодування і декодування Недвійкова кодів.
За інших рівних умов бажано, щоб інформаційні та надлишкові символи розташовувалися окремо. У систематичних кодах це умова виполняется.В циклічних кодах кожне слово містить всі свої циклічні перестановки. Всі n циклічних перестановок (слова довжини n) утворюють цикл. У квазіцікліческіх кодах цикл утвориться на числі символів n-1 або, рідше, n-2. Циклічні коди важливі як з точки зору математичного опису, так і для побудови та реалізації коду.
Помилки в каналах зв'язку мають саме різне розподіл, однак для вибору завадостійкого коду доцільно розділити всі можливі конфігурації помилок на незалежні (некорельованих) і пакети (корельовані помилки). На практиці доводиться враховувати якість інтервалів між пакетами: вони можуть бути вільними від помилок або ж містити випадкові незалежні помилки.
Під кореляційними увазі коди, що володіють хорошими кореляційними властивостями, важливими при передачі сигналів входження в зв'язок, для підвищення захищеності від деяких видів перешкод, вилучення сигналів з інтенсивних шумів, забезпечення многостанционного доступу, побудови асинхронно-адресних систем зв'язку. Кореляційні коди включають в себе пари протилежних сигналів з хорошою функцією автокореляції (метод внутріімпульсной модуляції), імпульсно-інтервальні коди, що мають на фіксованому інтервалі часу постійне для всіх слів коду число імпульсів з пеперекривається (при будь-якому взаємному зсуві слів в часі) значеннями інтервалів між імпульсами , ансамблі сигналів з хорошими взаімокорреляціоннимі властивостями.
Особливий клас утворюють частотно-компактні коди, призначені для зосередження енергії сигналу в можливо більш вузькій смузі частот. Настільки загальна постановка задачі розуміється в різних системах зв'язку по-різному: в дротяних лініях і лінійних трактах, що містять смугасто-обмежують фільтри з крутими фронтами, необхідно основну енергію сігналa "відсунути" від крайніх частот до центру смуги пропускання метою зменшення міжсимвольні спотворень; в мережах радіозв'язку з жорсткими обмеженнями щодо електромагнітної сумісності радіозасобів від коду вимагається значно (на десятки децибел) зменшити рівень позасмугових випромінювань. Побудова кодування і декодування частотно-компактних кодів істотно залежать від методу модуляції.
Арифметичні коди служать для боротьби з помилками при виконанні арифметичних операцій в процесорі ЕОМ.
Далі розглядаються два типи кодів: блокові і деревоподібні. Визначальний відмінність між кодерами для кодів цих двох типів полягає в наявності або відсутності пам'яті. Кодер для блокового коду є пристроєм без пам'яті, що відображає послідовності з k вхідних символів в послідовності з n вихідних символів. Термін "без пам'яті" вказує, що кожний блок з n символів залежить тільки від відповідного блоку з k символів і не залежить від інших блоків. Це не означає, що кодер не містить елементів пам'яті. Важливими параметрами блокового коду є n, k, R = k / n і d min. На практиці значення k лежать між 3 і декількома сотнями, a R = = 1 / 4 ... 7 / 8. Значення, що лежать поза цими межами, є можливими, але часто призводять до деяких практичних труднощів. Вхідні і вихідні послідовності зазвичай складаються з двійкових символів, але іноді можуть складатися з елементів деякого алфавіту більшого об'єму. Кодер для деревовидного коду є пристроєм з пам'яттю, в яке надходять набори з m двійкових вхідних символів, а на виході з'являються набори з n двійкових вихідних символів. Кожен набір n вихідних символів залежить від поточного вхідного набору і від v попередніх вхідних символів. Таким чином, пам'ять кодера повинна містити v + m вхідних символів. Параметр v + m часто називають довжиною кодового обмеження даного коду і позначають k = v + m (не слід плутати з параметром k для блокового коду). Зазначимо, що позначення часто не узгоджуються один з одним. Деякі автори називають довжиною кодового обмеження параметр k, у той час як інші - параметр v. Тут довжиною кодового обмеження будемо називати величину v, оскільки це призводить до меншої плутанини для кодів з m> 1. Параметр k = v + m майже не буде використовуватися. Деревоподібні коди характеризуються також швидкістю R = m / n і вільним відстанню d св. Точне визначення d св більш громіздко, ніж визначення d min для блокових кодів, однак параметр d св, по суті, містить ту ж інформацію про код, що і d min. Типові значення параметрів деревовидних кодів такі: m, n = 1 ... 8, R = 1 / 4 ... 7 / 8, v = 2 ... 60.
При іншому підході коди можна розділити на лінійні та нелінійні. Лінійні коди утворюють векторний простір і мають наступним важливим властивістю: два кодових слова можна скласти, використовуючи відповідне визначення суми, і одержати третє кодове слово. Що стосується звичайних двійкових кодів ця операція є посимвольним складанням двох кодових слів за модулем 2 (тобто 1 +1 = 0, 1 +0 = 1, 0 +0 = 0). Це властивість приводить до двох важливих наслідків. Перше з них полягає в тому, що лінійність істотно спрощує процедури кодування та декодування, дозволяючи висловити кожне кодове слово у вигляді "лінійної" комбінації невеликого числа виділених кодових слів, так званих базисних векторів. Друга властивість полягає в тому, що лінійність істотно спрощує завдання обчислення параметрів коду, оскільки відстань між двома кодовими словами при цьому еквівалентно відстані між кодовим словом, що складається цілком з нулів, і деяким іншим кодовим словом. Таким чином, при обчисленні параметрів лінійного коду досить розглянути, що відбувається при передачі кодового слова, що складається цілком з нулів. Обчислення параметрів спрощується ще й тому, що відстань Хеммінга між даними кодовим словом і нульовим кодовим словом дорівнює числу ненульових елементів даного кoдового слова. Це число часто називають вагою Хеммінга даного слова, і список, що містить число кодових слів кожного ваги, можна використовувати для обчислення характеристик коду за допомогою адитивної кордону. Такий список називають спектром коду.
Лінійні коди відрізняються від нелінійних замкнутістю кодового безлічі щодо деякого лінійного оператора, наприклад складання або множення слів коду, розглянутих як вектори простору, що складається з кодових слів - векторів. Лінійність коду спрощує його побудову та реалізацію. При великій довжині практично можуть бути використані тільки лінійні коди. Разом з тим часто нелінійні коди мають кращими параметрами в порівнянні з лінійними. Для відносно коротких кодів складність побудови та реалізації лінійних і нелінійних кодів приблизно однакова.
Як лінійні, так і нелінійні коди утворюють великі класи, які містять багато різних конкретних видів завадостійких кодів. Серед лінійних блокових найбільше значення мають коди з одного перевіркою на парність, M-коди (симплексних), ортогональні, біортогональние, Хеммінга, Боуза-Чоудхурі-хоквінгема, Голі, квадратично-вичетние (KB), Ріда-Соломона. До нелінійним відносять коди з контрольною сумою, інверсні, Нордстрома-Робінсона (HP), з постійною вагою, з перестановки з повторенням і без повторення символів (повні коди ортогональних таблиць, проективних груп, груп Матьє та інших груп перестановок).
Майже всі схеми кодування, які застосовуються на практиці, засновані на лінійних кодах. Подвійні лінійні блокові коди часто називають груповими кодами, оскільки кодові слова складають математичну структуру, яка називається групою. Лінійні деревоподібні коди зазвичай називають сверточних кодами, оскільки операцію кодування можна розглядати як дискретну згортку вхідної послідовності з імпульсним відгуком кодера.
Нарешті, коди можна розбити на коди, що виправляють випадкові помилки, і коди, що виправляють пакети помилок. В основному ми будемо мати справу з кодами, призначеними для виправлення випадкових, або незалежних, помилок. Для виправлення пакетів помилок було створено багато кодів, що мають хороші параметри. Однак при наявності пачок помилок часто виявляється більш вигідним використовувати коди, що виправляють випадкові помилки, разом з пристроєм перемежения відновлення. Такий підхід містить у собі процедуру перемішування порядку символів в закодованій послідовності перед передачею і відновленням вихідного порядку символів після прийому з тим, щоб рандомізовані помилки, об'єднані в пакети.
Особливості практичного кодування
Припустимо, що все що представляють інтерес дані можуть бути представлені у вигляді двійкової (закодованою двійково) інформації, тобто у вигляді послідовності нулів та одиниць. Завдання формулюється стандартно. Ця двійкова інформація підлягає передачі по каналу, схильній до випадкових помилок. Завдання кодування полягає в такому додаванні до інформаційних символів додаткових символів, щоб на приймачі ці спотворення могли бути знайдені і виправлені. Інакше кажучи, послідовність символів даних представляється у вигляді деякої довшої послідовності символів, надмірність якої достатня для захисту даних.
Двійковий код потужності М і довжини n представляє собою безліч з М двійкових слів довжини n, званих кодовими словами. Зазвичай М = 2 k, де k - деяке ціле число; такий код називається двійковим (n, k)-кодом.
Наприклад, можна побудувати наступний код: 10101 10010 01110 11111 Це дуже бідна (і дуже маленький) код з M = 4 і n = 5, але він задовольняє наведеним вище визначенням. Даний код можна використовувати для представлення 2-бітових двійкових чисел, використовуючи наступне (довільна) відповідність:
00 <-> 10101, 01 <-> 10010, 10 <-> 01110, 11 <-> lllll.
Якщо отримано одне з чотирьох 5-бітових кодових слів, то вважаємо, що відповідні йому два біта є правильною інформацією. Якщо сталася помилка, то ми отримаємо 5-бітове слово, що відрізняється від кодових слів. Тоді спробуємо знайти найбільш ймовірно передане слово і візьмемо його в якості оцінки вихідних двох бітів інформації. Наприклад, якщо ми прийняли 01100, то вважаємо, що передавалося 01110, і, отже, інформаційне слово дорівнювало 10.
У наведеному прикладі код не є хорошим, так як він не дозволяє виправляти багато конфігурацій помилок. Бажано вибирати коди так, щоб кожне кодове слово по можливості більше відрізнялося від кожного іншого кодового слова; зокрема, це бажано в тому випадку, коли довжина блоку велика.
Mожет здатися, що досить визначити вимоги до "хорошої кодом" і потім зробити машинний пошук по безлічі всіх можливих кодів. Але скільки кодів існує для даних n і k? Кожне кодове слово являє собою послідовність n двійкових символів, і всього є 2 k таких слів, отже, код описується n2 k двійковими символами. Всього існує 2 n2k способів вибору цих двійкових символів, отже, число різних (n, k)-кодів одно цього числа. Звичайно, дуже багато хто з цих кодів не представляють інтересу (як у випадку, коли два кодових слова рівні), так що треба або перевіряти це по ходу пошуку, або розвинути деяку теорію, що дозволяє виключити такі коди.
Наприклад, виберемо (n, k) = (40,20) - код, дуже помірний за сучасними стандартами. Тоді число таких кодів перевершить величину 10 10000000 - неймовірно велика кількість! Отже, неорганізовані процедури пошуку безсилі.
У загальному випадку блокові коди визначаються над довільним кінцевим алфавітом, скажімо над алфавітом із q символів {0, 1, 2, ..., q - 1}. На перший погляд введення алфавітів, відмінних від двійкового, може здатися зайвим узагальненням. З міркувань ефективності, однак, багато сучасних канали є Недвійкова, і коди для цих каналів мають бути Недвійкова. Насправді коди для Недвійкова каналів часто виявляються досить хорошими, і сам цей факт може служити причиною для використання Недвійкова каналів. Двійкові дані джерела тривіальним чином представляються символами q-ічного алфавіту, особливо якщо q дорівнює ступеня двійки, як це зазвичай і буває на практиці.
Визначення. Блоковий код потужності М над алфавітом із q символів визначається як множина з М (q-ічних послідовних довжини q, званих кодовими, словами.
Якщо q = 2, то символи називаються бітами. Зазвичай М = q k для деякого цілого k, і ми будемо цікавитися тільки цим випадком, називаючи код (n, k)-кодом. Кожній послідовності з k q-ічних символів можна зіставити послідовність з n q-ічних символів, що є кодовим словом.
Є два основні класи кодів: блокові коди і деревоподібні коди; вони ілюструються рис. 1. Блоковий код задає блок з k інформаційних символів n-символьним кодовим словом. Швидкість R блокового коду визначається рівністю R = k / n. (Швидкість - величина безрозмірна або, можливо, вимірюється в одиницях біт / біт або символ / символ. Її слід відрізняти від іншого званого тим же терміном швидкість поняття, що вимірює канальну швидкість в біт / с. Використовується й інше визначення швидкості: R = (k / n) log e q, одиницею якого є нат / символ, де один нат дорівнює log 2 e бітів. Прийнято також визначення R = (k / n) log 2 q, в якому швидкість вимірюється в одиницях біт / символ.)
Рис. 2. Основні класи кодів.
Деревоподібний код більш складний. Він відображає нескінченну послідовність інформаційних символів, що надходить зі швидкістю k 0 символів за один інтервал часу, в безперервну послідовність символів кодового слова зі швидкістю n 0 символів за один інтервал часу. Cосредоточім увагу на блокових кодах.
Якщо повідомлення складається з великого числа бітів, то в принципі краще використовувати один кодовий блок великої довжини, ніж послідовність кодових слів з більш короткого коду. Природа статистичних флуктуацій така, що випадкова конфігурація помилок зазвичай має вигляд серії помилок. Деякі сегменти цієї конфігурації містять більше середнього числа помилок, а деякі менше. Отже, при одній і тій же швидкості більш довгі кодові слова набагато менш чутливі до помилок, чим більш короткі кодові слова, але, звичайно, відповідні кодер і декодер можуть бути більш складними. Наприклад, припустимо, що 1000 інформаційних бітів передаються за допомогою (уявного) 2000-бітового двійкового коду, здатного виправляти 100 помилок. Порівняємо таку можливість з передачею одночасно 100 бітів за допомогою 200-бітового коду, що виправляє 10 помилок на блок. Для передачі 1000 бітов необхідно 10 таких блоків. Друга схема також може виправляти 100 помилок, але лише тоді, коли вони розподілені приватним чином - по 10 помилок у 200-бітових подблока. Перша схема може виправляти 100 помилок незалежно від того, як вони розташовані всередині 2000-бітового кодового слова. Вона суттєво ефективніше.
Ці евристичні міркування можна обгрунтувати теоретично, але тут ми до цього не прагнемо. Ми тільки хочемо обгрунтувати той факт, що хорошими є коди з великою довжиною блоку і що дуже хорошими кодами є коди з дуже великою довжиною блоку. Такі коди може бути дуже важко знайти, а будучи знайденими, вони можуть зажадати складних пристроїв для реалізації операцій кодування і декодування.
Про блоковому коді судять за трьома параметрами: довжині блоку n, інформаційної довжині k і мінімального відстані d *. Мінімальна відстань є мірою відмінності двох найбільш схожих кодових слів. Мінімальна відстань вводиться двома наступними визначеннями.
Визначення. Відстанню по Хеммінга між двома q-ічнимі послідовностями х і у довжини n називається число позицій, в яких вони різні. Це відстань позначається через d (х, у).
Наприклад, візьмемо х = 10101 і в = 01100; тоді маємо d (10101, 01100) = 3. В якості іншого прикладу візьмемо х = 30102 і в = 21103; тоді d (30102, 21103) = 3.
Визначення. Нехай C = {з i, i = 0, ..., М - 1} - код. Тоді мінімальна відстань коду C одно найменшому від усіх відстаней по Хеммінга між різними парами кодових слів, тобто
d * = min d (c i, з j).
(N, k)-код з мінімальним відстанню d * називається також (n, k, d *)-кодом.
У коді C, обраному в прикладі, d (10101, 10010) = 3, d (10010, 01110) = 3, d (10101, 01110) = 4, d (10010, 11111) == 3, d (10101, 11111 ) = 2, d (01110, 11111) = 2; отже, для цього коду d * = 2.
Припустимо, що передано кодове слово і в каналі відбулася одиночна помилка. Тоді прийняте слово знаходиться на рівному 1 відстані по Хеммінга від переданого слова. У випадку, коли відстань до кожного іншого кодового слова більше ніж 1, декодер виправить помилку, якщо покладе, що дійсно переданим словом було найближчим до прийнятого кодове слово.
У більш загальному випадку якщо відбулося t помилок і якщо відстань від прийнятого слова до кожного іншого кодового слова більше t, то декодер виправить ці помилки, прийнявши найближчим до прийнятого кодове слово як дійсно переданого. Це завжди буде так, якщо
d *> = 2t + 1.
Іноді вдається виправляти конфігурацію з t помилок навіть тоді, коли ця нерівність не задовольняється. Однак якщо d * <2t + 1, то виправлення будь-яких t помилок не може бути гарантовано, тому що тоді воно залежить від того, яке слово передавалося і яка була конфігурація з t помилок всередині блоку.
Геометрична ілюстрація дається на рис. 3.4.
Рис. 3.4. Сфери декодування.
У просторі всіх (q-ічних n-послідовностей вибрано деякий безліч n-послідовностей, оголошених кодовими словами. Якщо d * - мінімальна відстань цього коду, а t - найбільше ціле число, яке задовольняє умові d *> = 2t + 1, то навколо кожного кодового слова можна описати непересічні сфери радіуса t. Прийняті слова, що лежать всередині сфер, декодуються як кодове слово, яке є центром відповідної сфери. Якщо сталася не більше t помилок, то прийняте слово завжди лежить всередині відповідної сфери і декодується правильно.
Деякі прийняті слова, що містять більше t помилок, потраплять всередину сфери, описаної навколо іншого кодового слова, і будуть декодовані неправильно. Інші прийняті слова, що містять більше t помилок, потраплять в проміжні між сферами декодування області. У залежності від застосування останній факт можна інтерпретувати одним із двох способів.
Неповний декодер декодує тільки ті прийняті слова, які лежать всередині сфер декодування, описаних навколо кодових слів. Решта прийняті слова, що містять більше дозволеної кількості помилок, декодер оголошує нерозпізнаних. Такі конфігурації помилок при неповному декодуванні називаються Помилки, що не. Більшість використовуваних декодерів є неповними декодерами. Повний декодер декодує кожне прийняте слово найближчим кодове слово. Геометрично це представляється наступним чином: повний декодер розрізає проміжні області на шматки і приєднує їх до сфер так, що кожна точка потрапляє в найближчу сферу. Зазвичай деякі крапки перебувають на рівних відстанях від кількох сфер; тоді одна з цих сфер довільно оголошується найближчій. Якщо відбувається більш t помилок, то повний декодер часто декодує неправильно, але бувають і випадки потрапляння в правильне кодове слово. Повний декодер використовується в тих випадках, коли краще вгадувати повідомлення, ніж взагалі не мати ніякої його оцінки. Можна також розглядати канали, в яких крім помилок відбуваються і стирання. Це означає, що конструкцією приймача передбачено оголошення символу стертим, якщо він отриманий ненадійно або якщо приймач розпізнав наявність інтерференції або збій. Такий канал має вхідний алфавіт потужності q вихідний алфавіт потужності q + 1; додатковий символ називається стиранням. Наприклад, стирання символу 3 в повідомленні 12345 призводить до слова 12-45. Це не слід плутати з іншого операцією, званої викиданням, яка дає 1245.
B таких каналах можуть використовуватися коди, контролюючі помилки. У разі коли мінімальна відстань коду одно d *, будь-яка конфігурація з р стирок може бути відновлена, якщо d *> = р + 1. Далі, будь-яка конфігурація з v помилок і р стирок може бути декодована за умови, що
d *> = 2v + 1 + р.
Для доказу викинемо з усіх кодових слів ті р компонент, в яких приймач справив стирання. Це дасть новий код, мінімальна відстань якого не менше d * - р; отже, v помилок можуть бути виправлені за умови, що виконується виписане вище нерівність. Таким чином, можна відновити вкорочене кодове слово з р стертими компонентами. Нарешті, так як d *> р + 1, існує тільки одне кодове слово, що збігається з отриманим в нестертих компонентах; отже, вихідне кодове слово може бути відновлено.
ЛІТЕРАТУРА
1. Лідовскій В.І. Теорія інформації. - М., «Вища школа», 2002р. - 120с.
2. Метрологія та радіовимірювань в телекомунікаційних системах. Підручник для ВУЗів. / В. І. Нефедов, В. І. Халкин, Є. В. Федоров та ін - М.: Вища школа,
3. Цапенко М.П. Вимірювальні інформаційні системи. -. - М.: Енергоатом издат, 2005. - 440С.
4. Зюко А.Г. , Кловський Д.Д., Назаров М.В., Фінк Л.М. Теорія передачі сигналів. М: Радіо і зв'язок,
5. Б. Скляр. Цифрова зв'язок. Теоретичні основи та практичне застосування. Вид. 2-е, испр.: Пер. з англ. - М.: Видавничий дім «Вільямс»,