Білоруський державний університет інформатики і радіоелектроніки
кафедра РЕЗ
реферат на тему:
«Основні параметри завадостійкого кодування. Основні параметри завадостійких кодів »
МІНСЬК, 2009
ОСНОВНІ ПРИНЦИПИ Завадостійке КОДУВАННЯ
Кодування з виправленням помилок, по суті, являє собою метод обробки сигналів, призначений для збільшення надійності передачі по цифрових каналах. Хоча різні схеми кодування дуже несхожі один на одного і засновані на різних математичних теоріях, всім їм притаманні два загальні властивості. Одне з них - використання надмірності. Закодовані цифрові повідомлення завжди містять додаткові, або надлишкові, символи. Ці символи використовують для того, щоб підкреслити індивідуальність кожного повідомлення. Їх завжди вибирають так, щоб зробити малоймовірною втрату повідомленням його індивідуальності через спотворення при впливі перешкод досить багато символів. Друга властивість полягає в усередненні шуму. Ефект усереднення досягається за рахунок того, що надлишкові символи залежать від декількох інформаційних символів. Для розуміння процесу кодування корисно розглянути кожне з цих властивостей окремо.
Розглянемо спочатку двійковий канал зв'язку з перешкодами, що приводять до того, що помилки з'являються незалежно в кожному символі і середня ймовірність помилки дорівнює Р = 0,01. Якщо потрібно розглянути довільний блок з 10 символів на виході каналу, то дуже важко виявити символи, які є помилковими. Разом з тим якщо вважати, що такий блок містить не більше трьох помилок, то ми будемо неправі лише два рази на мільйон блоків. Крім того, ймовірність, що ми опинимося рацію, зростає зі збільшенням довжини блоку. При збільшенні довжини блоку частка помилкових символів в блоці прагне до середньої частоти помилок в каналі, а також, що дуже важливо, частка блоків, кількість помилок в яких істотно відрізняється від цього середнього значення, стає дуже малою. Прості обчислення допомагають зрозуміти, наскільки правильним є це твердження. Розглянувши, наприклад, той же канал, обчислимо ймовірність того, що частка помилкових символів перевищує значення p, і побудуємо графік цієї функції для декількох значень довжини блоку.
Рис. 1. Імовірність того, що частка помилкових символів e / N в блоці довжиною N перевищує р при ймовірності Р e = 0,01
Криві на рис.1 показують, що при обробці символів блоками, а не одного за іншим можна зменшити загальну частоту помилок. При цьому буде потрібно, щоб існувала схема кодування, нечутлива до помилок в деякій частці символів блоку і не призводить при цьому до втрати повідомленням своєї індивідуальності, тобто не призводить до помилкового блоку. З графіків для різних довжин блоків видно, яку саме частку помилок потрібно виправляти, щоб отримати задану ймовірність помилки блоку. Він показує також, що при фіксованій ймовірності помилки блоку частка помилок, які потрібно виправляти, зменшується при зростанні довжини блоку. Сказане свідчить про резерви поліпшення характеристик при усередненні шуму і про те, що ці резерви зростають при збільшенні довжини блоку. Таким чином, довгі блокові коди ефективніше коротких. Після того як встановлено доцільність виправлення помилок у символах, виникає наступне логічне запитання: як це зробити? Ключ лежить у надмірності. Після деяких роздумів читач зрозуміє, що при виправленні помилок у повідомленні, що подається послідовністю із n двійкових символів, дуже важливо врахувати, щоб не всі 2 n можливих послідовностей представляли повідомлення. У самому справі, коли кожна з можливих прийнятих послідовностей n символів представляє деяке повідомлення, немає ніяких підстав вважати, що одна послідовність є більш правильною, ніж будь-яка інша. Продовжуючи міркувати таким же способом, можна ясно побачити, що для виправлення всіх наборів з t-менш помилок необхідно і достатньо, щоб кожна послідовність, що представляє повідомлення, відрізнялася від послідовності, що представляє будь-яке інше повідомлення, не менш ніж у 2t +1 місцях. Наприклад, для виправлення всіх одиночних або всіх подвійних помилок у символах потрібно, щоб кожні дві послідовності, що представляють різні повідомлення, відрізнялися не менше ніж у п'яти символах. Кожна прийнята послідовність, що містить два помилкових символу і, отже, відрізняється від надісланої послідовності рівно у двох місцях, буде завжди відрізнятиметься від усіх інших послідовностей, що представляють повідомлення, не менш ніж у трьох місцях. Кількість позицій, в яких дві послідовності відрізняються один від одного, будемо називати відстанню Хеммінга d між цими двома послідовностями. Найменше значення d для всіх пар кодових послідовностей називається кодовою відстанню і позначається d min. Оскільки d min завжди має бути на одиницю більше подвоєного числа виправляє помилок, можна написати t = [(d min-l) / 2], де [] позначає цілу частину. Параметр t вказує, що всі комбінації з t-менш помилок у будь-яку прийняту послідовності можуть бути ісправлени.Імеются моделі каналів, в яких значення t може бути більше вказаного.
Приклад. Розглянемо код, що складається з чотирьох кодових слів 00000, 00111,11100 і 11011. Кожне кодове слово використовується для представлення одного з чотирьох можливих повідомленні. Оскільки код включає лише невелику частку всіх 32 можливих послідовностей з п'яти символів, ми можемо вибрати кодові слова таким чином, щоб кожні два з них відрізнялися один від одного не менше ніж у трьох позиціях. Таким чином, кодова відстань дорівнює трьом і код може виправляти одиночну помилку в будь-якій позиції. Щоб провести процедуру декодування при цьому коді, кожної з 28 неприпустимих послідовностей потрібно поставити у відповідність найближчу до неї допустиму послідовність. Цей процес веде до створення таблиці декодування, яка будується наступним чином. Спочатку під кожним кодовим словом виписуємо всі можливі послідовності, що відрізняються від нього в одній позиції. У результаті отримуємо частину табл. 1, укладену між лініями. Зауважимо, що після побудови цієї частини залишилося воcемь послідовностей. Кожна з цих послідовностей відрізняється від кожного кодового слова не менш ніж у двох позиціях. Однак на відміну від інших послідовностей ці вісім послідовностей не можна однозначно розмістити у таблиці. Наприклад, послідовністю можна помістити або в перший, або в четвертий стовпець. При використанні цієї таблиці в процесі декодування потрібно знайти стовпець, в якому міститься ухвалена послідовність, і а як вихідний послідовності декодера взяти кодове слово, що знаходиться у верхній частині цього стовпця.
Таблиця 1. Таблиця декодування для коду з чотирма словами
Причина, по якій таблиця декодування повинна будуватися саме таким чином, дуже проста. Імовірність появи фіксованої комбінації з i помилок дорівнює Р t e (1-Р e) 5-i Зауважимо що при Р e <1 / 2 (1-Р e) 5 P e (1-Р e) 4 Р e 2 (1 -Р e) 3 ...
Таким чином, поява фіксованого одиночної помилки більш імовірно, ніж фіксованої комбінації двох помилок, і т. д. Це означає, що декодер, який декодує кожну прийняту послідовність у найближче до неї по відстані Хеммінга кодове слово, вибирає в дійсності те кодове слово, ймовірність передачі якого максимальна (у припущенні, що всі кодові слова різновірогідні). Декодер, реалізує це правило декодування, є декодером максимального правдоподібності, і у вказаних припущеннях він мінімізує ймовірність появи помилки декодування прийнятої послідовності. У цьому сенсі такий декодер є оптимальним. Це поняття дуже важливо, оскільки декодери максимального правдоподібності часто використовуються для коротких кодів. Крім того, параметри декодера максимального правдоподібності можуть служити еталоном, з яким порівнюються параметри інших, неоптимальних декодерів. Якщо декодування ведеться за допомогою таблиці декодування, то елементи таблиці можна розташувати так, щоб отримати декодування по максимуму правдоподібності. На жаль, обсяг таблиці зростає експоненціально з ростом довжини блоку, так що використання таблиці декодування для довгих кодів недоцільно. Проте таблиця декодування часто виявляється корисною для з'ясування важливих властивостей блокових кодів.
Безліч кодових слів в таблиці декодування є підмножиною (першим рядком таблиці декодування) безлічі всіх 2 n послідовностей довжиною n. У процесі побудови таблиці декодування безліч всіх послідовностей довжиною n розбивається на непересічні підмножини (стовпці таблиці декодування). У разі коли код виправляє t помилок, число N e послідовностей довжиною n в кожному підмножині задовольняє нерівності
N e> = 1 + n + C n 2 +...+ C n t, (2)
де C n i - i-й біноміальний коефіцієнт.
Нерівність (2) випливає безпосередньо з того, що є рівно n різних послідовностей, що відрізняються від даної послідовності в одній позиції, C n 2 послідовностей, що відрізняються в двох позиціях, і т. д. Як і в наведеному вище простому прикладі, після розміщення всіх послідовностей, що відрізняються від кодових в t-менш позиціях, майже завжди залишаються нерозміщені послідовності [звідси нерівність в (2)]. Тепер можна зв'язати надмірність коду c числом помилок, які їм виправляються Зауважимо спочатку, що число всіх можливих послідовностей дорівнює 2 n. Кожен стовпець таблиці декодування містить N e таких послідовностей, тому загальне число кодових слів повинно задовольняти нерівності
N e <= <2 n / (1 + n + C n 2 +...+ C n t), (3)
Це нерівність називається кордоном Хеммінга або кордоном сферичної упаковки. Рівність в (3) досягається тільки для так званих досконалих кодів. Ці коди виправляють всі набори з t-менш помилок і не виправляють ніяких інших наборів. Число відомих досконалих кодів дуже невелика, так що рівність в (1.3) досягається в дуже рідкісних випадках.
Процес кодування полягає в тому, що набори k інформаційних символів відображаються в кодові послідовності, що складаються з n символів. Будь-яке таке відображення будемо називати (n, k)-кодом, хоча зазвичай така назва застосовується тільки до лінійним кодами (які обговорюються пізніше). Оскільки число послідовностей довжиною k дорівнює 2 k, нерівність (3) можна переписати таким чином:
2 k <= 2 n / (1 + n + C n 2 +...+ C n t), (4)
Міра ефективності коду визначається відношенням R = k / n (5)
і називається швидкістю коду. Частка надлишково переданих символів дорівнює 1-R.
Відображення, що виникає при кодуванні, можна задавати таблицею кодування. Наприклад, код з чотирма кодовими словами задається табл. 2.
Таблиця 2. Таблиця пошуку при декодуванні
Частина кодової послідовності, укладена між штриховими лініями, збігається з вхідними послідовністю. Тому кожної кодової послідовності, легко однозначно зіставити вхідну послідовність. Не всі блокові коди мають цією властивістю. Ті, які ним володіють, називаються систематичними кодами. Поняття надлишкових символів для систематичних кодів стає абсолютно ясним, і надмірними символами в табл. 1 є символи на позиціях 1, 4 і 5. Коди, що не володіють зазначеним властивістю, називаються несистематично.
Існує багато хороших конструктивних методів кодування, що дозволяють виправляти кратні помилки і приводять до помітного зменшення частоти появи помилкових символів. Ці коди легко будуються і за допомогою сучасних напівпровідникових пристроїв відносно просто декодуються. Наприклад, існує блоковий код довжиною 40, що містить 50% надлишкових символів і дозволяє виправляти чотири випадкові помилки. На рис. 1 показано, що при Р e = 0,01 цей код має ймовірність помилки блоку, меншу 10 -4. Якщо цього недостатньо, розробник збільшує надмірність, щоб виправляти більше число помилок, або переходить до кодів з більшою довжиною блоку і отримує виграш за рахунок більшого усереднення. У кожному випадку потрібно брати до уваги виникають додаткові витрати. Однак обидві зазначені можливості припустимі і можуть представляти практично прийнятні альтернативи. Перш ніж йти далі, зробимо невеликий відступ, яке не має великого практичного значення, але привертає увагу фахівців з теорії кодування протягом багатьох років. Форма кривих, зображених на рис. 1, дозволяє припустити, що якщо є схема, що виправляє фіксовану частку t / n помилкових символів в блоці (в нашому випадку t / n незначно перевищує 0,01), то, вибираючи довжину блоку досить великий, можна зробити частку помилок як завгодно малою. На жаль, це виявляється дуже важким завданням. Більшість конструктивних процедур може забезпечити постійне ставлення t / n лише при зростаючій частці надлишкових символів (іншими словами, R-> 0 при n-> oo). Таким чином, втрата ефективності виникає через те, що частка корисних повідомлень стає дуже малою при великій довжині блоку. Частково це завдання було вирішено Юстесеном в 1972 р . Юстесен показав, що можна побудувати клас асимптотично хороших (у зазначеному тут сенсі) кодів і вказати для них процедуру декодування. Проте, наскільки відомо, ці коди не застосовувалися в жодній з існуючих систем зв'язку.
Основні параметри завадостійких кодів
Проблема підвищення вірності обумовлена не відповідністю між вимогами, що висуваються при передачі даних і якістю реальних каналів зв'язку. У мережах передачі даних потрібно забезпечити вірність не гірше 10 -6 - 10 -9, а при використанні реальних каналів зв'язку і простого (первинного) коду зазначена вірність не перевищує 10 -2 - 10 -5.
Одним із шляхів вирішення завдання підвищення вірності в даний час є використання спеціальних процедур, заснованих на застосуванні завадостійких (коригувальних) кодів.
Прості коди характеризуються тим, що для передачі інформації використовуються всі кодові слова (комбінації), кількість яких дорівнює N = q n (q - підстава коду, а n - довжина коду). У загальному випадку вони можуть відрізнятися один від одного одним символом (елементом). Тому навіть один помилково прийнятий символ призводить до заміни одного кодового слова іншим і, отже, до неправильного прийому повідомлення в цілому.
Завадостійким називаються коди, що дозволяють виявляти і (або) виправляти помилки в кодових словах, які виникають при передачі по каналах зв'язку. Ці коди будуються таким чином, що для передачі повідомлення використовується лише частина кодових слів, які відрізняються один від одного більш ніж в одному символі. Ці кодові слова називаються дозволеними. Всі інші кодові слова не використовуються і відносяться до числа заборонених.
Застосування завадостійких кодів для підвищення вірності передачі даних пов'язано з вирішенням завдань кодування і декодування.
Завдання кодування полягає в отриманні при передачі для кожної k - елементної комбінації з безлічі q k відповідного їй кодового слова довжиною n з безлічі q n.
Завдання декодування полягає в отриманні k - елементної комбінації з прийнятого n - розрядного кодового слова при одночасному виявленні або виправлення помилок.
Основні параметри завадостійких кодів:
Довжина коду - n;
Довжина інформаційної послідовності - k;
Довжина перевірочної послідовності - r = nk;
Кодова відстань коду - d 0;
Швидкість коду - R = k / n;
Надмірність коду - R ;
Імовірність виявлення помилки (спотворення) - Р ГО;
Ймовірність не виявлення помилки (спотворення) - Р АЛЕ.
Кодова відстань між двома кодовими словами (відстань Хеммінга) - це число позицій, в яких вони відрізняються один від одного.
Кодова відстань коду - це найменша відстань Хеммінга між різними парами кодових слів.
Основні залежності між кратністю виявлених помилок t 0, виправляє помилок t u, виправленням стирок t c і кодовим відстанню d 0 коду:
Стиранням називається "втрата" значення переданого символу в деякій позиції кодового слова, яка відома.
Код, в якому кожне кодове слово починається з інформаційних символів і закінчується перевірочними символами, називається систематичним.
Граничні співвідношення між параметрами завадостійких кодів
Однією з найважливіших завдань побудови завадостійких кодів з заданими характеристиками є встановлення співвідношення між його здатністю виявляти чи виправляти помилки і надмірністю.
Існують граничні оцінки, що зв'язують d 0, n і k.
Кордон Хеммінга, яка близька до оптимальної для високо швидкісних кодів, визначається співвідношеннями:
для q-ного коду
для двійкового коду
Кордон Плоткіна, яку доцільно використовувати для низькошвидкісних кодів визначається співвідношеннями:
для q-ного коду
для двійкового коду
Межі Хеммінга і Плоткіна є верхніми межами для кодового відстані при заданих n і k, які задають мінімальну надмірність, при якій існує перешкодостійкий код, що має мінімальну кодова відстань і гарантійно виправляє t u - кратні помилки.
Кордон Варшамова-Гільберта (нижня межа), що визначається співвідношеннями:
і 
показує, при якому значенні nk визначено існує код, гарантійно виправляє помилки кратності t u.
ЛІТЕРАТУРА
1. Лідовскій В.І. Теорія інформації. - М., «Вища школа», 2002р. - 120с.
2. Метрологія та радіовимірювань в телекомунікаційних системах. Підручник для ВУЗів. / В. І. Нефедов, В. І. Халкин, Є. В. Федоров та ін - М.: Вища школа, 2001 р . - 383с.
3. Цапенко М.П. Вимірювальні інформаційні системи. -. - М.: Енергоатом издат, 2005. - 440С.
4. Зюко А.Г. , Кловський Д.Д., Назаров М.В., Фінк Л.М. Теорія передачі сигналів. М: Радіо і зв'язок, 2001 р . -368 С.
5. Б. Скляр. Цифрова зв'язок. Теоретичні основи та практичне застосування. Вид. 2-е, испр.: Пер. з англ. - М.: Видавничий дім «Вільямс», 2003 р . - 1104 с.
кафедра РЕЗ
реферат на тему:
«Основні параметри завадостійкого кодування. Основні параметри завадостійких кодів »
МІНСЬК, 2009
ОСНОВНІ ПРИНЦИПИ Завадостійке КОДУВАННЯ
Кодування з виправленням помилок, по суті, являє собою метод обробки сигналів, призначений для збільшення надійності передачі по цифрових каналах. Хоча різні схеми кодування дуже несхожі один на одного і засновані на різних математичних теоріях, всім їм притаманні два загальні властивості. Одне з них - використання надмірності. Закодовані цифрові повідомлення завжди містять додаткові, або надлишкові, символи. Ці символи використовують для того, щоб підкреслити індивідуальність кожного повідомлення. Їх завжди вибирають так, щоб зробити малоймовірною втрату повідомленням його індивідуальності через спотворення при впливі перешкод досить багато символів. Друга властивість полягає в усередненні шуму. Ефект усереднення досягається за рахунок того, що надлишкові символи залежать від декількох інформаційних символів. Для розуміння процесу кодування корисно розглянути кожне з цих властивостей окремо.
Розглянемо спочатку двійковий канал зв'язку з перешкодами, що приводять до того, що помилки з'являються незалежно в кожному символі і середня ймовірність помилки дорівнює Р = 0,01. Якщо потрібно розглянути довільний блок з 10 символів на виході каналу, то дуже важко виявити символи, які є помилковими. Разом з тим якщо вважати, що такий блок містить не більше трьох помилок, то ми будемо неправі лише два рази на мільйон блоків. Крім того, ймовірність, що ми опинимося рацію, зростає зі збільшенням довжини блоку. При збільшенні довжини блоку частка помилкових символів в блоці прагне до середньої частоти помилок в каналі, а також, що дуже важливо, частка блоків, кількість помилок в яких істотно відрізняється від цього середнього значення, стає дуже малою. Прості обчислення допомагають зрозуміти, наскільки правильним є це твердження. Розглянувши, наприклад, той же канал, обчислимо ймовірність того, що частка помилкових символів перевищує значення p, і побудуємо графік цієї функції для декількох значень довжини блоку.
Рис. 1. Імовірність того, що частка помилкових символів e / N в блоці довжиною N перевищує р при ймовірності Р e = 0,01
Криві на рис.1 показують, що при обробці символів блоками, а не одного за іншим можна зменшити загальну частоту помилок. При цьому буде потрібно, щоб існувала схема кодування, нечутлива до помилок в деякій частці символів блоку і не призводить при цьому до втрати повідомленням своєї індивідуальності, тобто не призводить до помилкового блоку. З графіків для різних довжин блоків видно, яку саме частку помилок потрібно виправляти, щоб отримати задану ймовірність помилки блоку. Він показує також, що при фіксованій ймовірності помилки блоку частка помилок, які потрібно виправляти, зменшується при зростанні довжини блоку. Сказане свідчить про резерви поліпшення характеристик при усередненні шуму і про те, що ці резерви зростають при збільшенні довжини блоку. Таким чином, довгі блокові коди ефективніше коротких. Після того як встановлено доцільність виправлення помилок у символах, виникає наступне логічне запитання: як це зробити? Ключ лежить у надмірності. Після деяких роздумів читач зрозуміє, що при виправленні помилок у повідомленні, що подається послідовністю із n двійкових символів, дуже важливо врахувати, щоб не всі 2 n можливих послідовностей представляли повідомлення. У самому справі, коли кожна з можливих прийнятих послідовностей n символів представляє деяке повідомлення, немає ніяких підстав вважати, що одна послідовність є більш правильною, ніж будь-яка інша. Продовжуючи міркувати таким же способом, можна ясно побачити, що для виправлення всіх наборів з t-менш помилок необхідно і достатньо, щоб кожна послідовність, що представляє повідомлення, відрізнялася від послідовності, що представляє будь-яке інше повідомлення, не менш ніж у 2t +1 місцях. Наприклад, для виправлення всіх одиночних або всіх подвійних помилок у символах потрібно, щоб кожні дві послідовності, що представляють різні повідомлення, відрізнялися не менше ніж у п'яти символах. Кожна прийнята послідовність, що містить два помилкових символу і, отже, відрізняється від надісланої послідовності рівно у двох місцях, буде завжди відрізнятиметься від усіх інших послідовностей, що представляють повідомлення, не менш ніж у трьох місцях. Кількість позицій, в яких дві послідовності відрізняються один від одного, будемо називати відстанню Хеммінга d між цими двома послідовностями. Найменше значення d для всіх пар кодових послідовностей називається кодовою відстанню і позначається d min. Оскільки d min завжди має бути на одиницю більше подвоєного числа виправляє помилок, можна написати t = [(d min-l) / 2], де [] позначає цілу частину. Параметр t вказує, що всі комбінації з t-менш помилок у будь-яку прийняту послідовності можуть бути ісправлени.Імеются моделі каналів, в яких значення t може бути більше вказаного.
Приклад. Розглянемо код, що складається з чотирьох кодових слів 00000, 00111,11100 і 11011. Кожне кодове слово використовується для представлення одного з чотирьох можливих повідомленні. Оскільки код включає лише невелику частку всіх 32 можливих послідовностей з п'яти символів, ми можемо вибрати кодові слова таким чином, щоб кожні два з них відрізнялися один від одного не менше ніж у трьох позиціях. Таким чином, кодова відстань дорівнює трьом і код може виправляти одиночну помилку в будь-якій позиції. Щоб провести процедуру декодування при цьому коді, кожної з 28 неприпустимих послідовностей потрібно поставити у відповідність найближчу до неї допустиму послідовність. Цей процес веде до створення таблиці декодування, яка будується наступним чином. Спочатку під кожним кодовим словом виписуємо всі можливі послідовності, що відрізняються від нього в одній позиції. У результаті отримуємо частину табл. 1, укладену між лініями. Зауважимо, що після побудови цієї частини залишилося воcемь послідовностей. Кожна з цих послідовностей відрізняється від кожного кодового слова не менш ніж у двох позиціях. Однак на відміну від інших послідовностей ці вісім послідовностей не можна однозначно розмістити у таблиці. Наприклад, послідовністю можна помістити або в перший, або в четвертий стовпець. При використанні цієї таблиці в процесі декодування потрібно знайти стовпець, в якому міститься ухвалена послідовність, і а як вихідний послідовності декодера взяти кодове слово, що знаходиться у верхній частині цього стовпця.
Таблиця 1. Таблиця декодування для коду з чотирма словами
| 00000 10000 01000 00100 00010 00001 | 11100 01100 10100 11000 11110 11101 | 00111 10111 01111 00011 00101 00110 | 11011 01011 10011 11111 11001 11010 |
| 10001 10010 | 01101 01110 | 10110 10101 | 01010 01001 |
Таким чином, поява фіксованого одиночної помилки більш імовірно, ніж фіксованої комбінації двох помилок, і т. д. Це означає, що декодер, який декодує кожну прийняту послідовність у найближче до неї по відстані Хеммінга кодове слово, вибирає в дійсності те кодове слово, ймовірність передачі якого максимальна (у припущенні, що всі кодові слова різновірогідні). Декодер, реалізує це правило декодування, є декодером максимального правдоподібності, і у вказаних припущеннях він мінімізує ймовірність появи помилки декодування прийнятої послідовності. У цьому сенсі такий декодер є оптимальним. Це поняття дуже важливо, оскільки декодери максимального правдоподібності часто використовуються для коротких кодів. Крім того, параметри декодера максимального правдоподібності можуть служити еталоном, з яким порівнюються параметри інших, неоптимальних декодерів. Якщо декодування ведеться за допомогою таблиці декодування, то елементи таблиці можна розташувати так, щоб отримати декодування по максимуму правдоподібності. На жаль, обсяг таблиці зростає експоненціально з ростом довжини блоку, так що використання таблиці декодування для довгих кодів недоцільно. Проте таблиця декодування часто виявляється корисною для з'ясування важливих властивостей блокових кодів.
Безліч кодових слів в таблиці декодування є підмножиною (першим рядком таблиці декодування) безлічі всіх 2 n послідовностей довжиною n. У процесі побудови таблиці декодування безліч всіх послідовностей довжиною n розбивається на непересічні підмножини (стовпці таблиці декодування). У разі коли код виправляє t помилок, число N e послідовностей довжиною n в кожному підмножині задовольняє нерівності
N e> = 1 + n + C n 2 +...+ C n t, (2)
де C n i - i-й біноміальний коефіцієнт.
Нерівність (2) випливає безпосередньо з того, що є рівно n різних послідовностей, що відрізняються від даної послідовності в одній позиції, C n 2 послідовностей, що відрізняються в двох позиціях, і т. д. Як і в наведеному вище простому прикладі, після розміщення всіх послідовностей, що відрізняються від кодових в t-менш позиціях, майже завжди залишаються нерозміщені послідовності [звідси нерівність в (2)]. Тепер можна зв'язати надмірність коду c числом помилок, які їм виправляються Зауважимо спочатку, що число всіх можливих послідовностей дорівнює 2 n. Кожен стовпець таблиці декодування містить N e таких послідовностей, тому загальне число кодових слів повинно задовольняти нерівності
N e <= <2 n / (1 + n + C n 2 +...+ C n t), (3)
Це нерівність називається кордоном Хеммінга або кордоном сферичної упаковки. Рівність в (3) досягається тільки для так званих досконалих кодів. Ці коди виправляють всі набори з t-менш помилок і не виправляють ніяких інших наборів. Число відомих досконалих кодів дуже невелика, так що рівність в (1.3) досягається в дуже рідкісних випадках.
Процес кодування полягає в тому, що набори k інформаційних символів відображаються в кодові послідовності, що складаються з n символів. Будь-яке таке відображення будемо називати (n, k)-кодом, хоча зазвичай така назва застосовується тільки до лінійним кодами (які обговорюються пізніше). Оскільки число послідовностей довжиною k дорівнює 2 k, нерівність (3) можна переписати таким чином:
2 k <= 2 n / (1 + n + C n 2 +...+ C n t), (4)
Міра ефективності коду визначається відношенням R = k / n (5)
і називається швидкістю коду. Частка надлишково переданих символів дорівнює 1-R.
Відображення, що виникає при кодуванні, можна задавати таблицею кодування. Наприклад, код з чотирма кодовими словами задається табл. 2.
Таблиця 2. Таблиця пошуку при декодуванні
| Вхідна послідовність | Кодова послідовність |
| 00 01 10 11 | 00100 01111 11011 10000 |
Існує багато хороших конструктивних методів кодування, що дозволяють виправляти кратні помилки і приводять до помітного зменшення частоти появи помилкових символів. Ці коди легко будуються і за допомогою сучасних напівпровідникових пристроїв відносно просто декодуються. Наприклад, існує блоковий код довжиною 40, що містить 50% надлишкових символів і дозволяє виправляти чотири випадкові помилки. На рис. 1 показано, що при Р e = 0,01 цей код має ймовірність помилки блоку, меншу 10 -4. Якщо цього недостатньо, розробник збільшує надмірність, щоб виправляти більше число помилок, або переходить до кодів з більшою довжиною блоку і отримує виграш за рахунок більшого усереднення. У кожному випадку потрібно брати до уваги виникають додаткові витрати. Однак обидві зазначені можливості припустимі і можуть представляти практично прийнятні альтернативи. Перш ніж йти далі, зробимо невеликий відступ, яке не має великого практичного значення, але привертає увагу фахівців з теорії кодування протягом багатьох років. Форма кривих, зображених на рис. 1, дозволяє припустити, що якщо є схема, що виправляє фіксовану частку t / n помилкових символів в блоці (в нашому випадку t / n незначно перевищує 0,01), то, вибираючи довжину блоку досить великий, можна зробити частку помилок як завгодно малою. На жаль, це виявляється дуже важким завданням. Більшість конструктивних процедур може забезпечити постійне ставлення t / n лише при зростаючій частці надлишкових символів (іншими словами, R-> 0 при n-> oo). Таким чином, втрата ефективності виникає через те, що частка корисних повідомлень стає дуже малою при великій довжині блоку. Частково це завдання було вирішено Юстесеном в
Основні параметри завадостійких кодів
Проблема підвищення вірності обумовлена не відповідністю між вимогами, що висуваються при передачі даних і якістю реальних каналів зв'язку. У мережах передачі даних потрібно забезпечити вірність не гірше 10 -6 - 10 -9, а при використанні реальних каналів зв'язку і простого (первинного) коду зазначена вірність не перевищує 10 -2 - 10 -5.
Одним із шляхів вирішення завдання підвищення вірності в даний час є використання спеціальних процедур, заснованих на застосуванні завадостійких (коригувальних) кодів.
Прості коди характеризуються тим, що для передачі інформації використовуються всі кодові слова (комбінації), кількість яких дорівнює N = q n (q - підстава коду, а n - довжина коду). У загальному випадку вони можуть відрізнятися один від одного одним символом (елементом). Тому навіть один помилково прийнятий символ призводить до заміни одного кодового слова іншим і, отже, до неправильного прийому повідомлення в цілому.
Завадостійким називаються коди, що дозволяють виявляти і (або) виправляти помилки в кодових словах, які виникають при передачі по каналах зв'язку. Ці коди будуються таким чином, що для передачі повідомлення використовується лише частина кодових слів, які відрізняються один від одного більш ніж в одному символі. Ці кодові слова називаються дозволеними. Всі інші кодові слова не використовуються і відносяться до числа заборонених.
Застосування завадостійких кодів для підвищення вірності передачі даних пов'язано з вирішенням завдань кодування і декодування.
Завдання кодування полягає в отриманні при передачі для кожної k - елементної комбінації з безлічі q k відповідного їй кодового слова довжиною n з безлічі q n.
Завдання декодування полягає в отриманні k - елементної комбінації з прийнятого n - розрядного кодового слова при одночасному виявленні або виправлення помилок.
Основні параметри завадостійких кодів:
Довжина коду - n;
Довжина інформаційної послідовності - k;
Довжина перевірочної послідовності - r = nk;
Кодова відстань коду - d 0;
Швидкість коду - R = k / n;
Надмірність коду - R ;
Імовірність виявлення помилки (спотворення) - Р ГО;
Ймовірність не виявлення помилки (спотворення) - Р АЛЕ.
Кодова відстань між двома кодовими словами (відстань Хеммінга) - це число позицій, в яких вони відрізняються один від одного.
Кодова відстань коду - це найменша відстань Хеммінга між різними парами кодових слів.
Основні залежності між кратністю виявлених помилок t 0, виправляє помилок t u, виправленням стирок t c і кодовим відстанню d 0 коду:
Стиранням називається "втрата" значення переданого символу в деякій позиції кодового слова, яка відома.
Код, в якому кожне кодове слово починається з інформаційних символів і закінчується перевірочними символами, називається систематичним.
Граничні співвідношення між параметрами завадостійких кодів
Однією з найважливіших завдань побудови завадостійких кодів з заданими характеристиками є встановлення співвідношення між його здатністю виявляти чи виправляти помилки і надмірністю.
Існують граничні оцінки, що зв'язують d 0, n і k.
Кордон Хеммінга, яка близька до оптимальної для високо швидкісних кодів, визначається співвідношеннями:
для q-ного коду
для двійкового коду
Кордон Плоткіна, яку доцільно використовувати для низькошвидкісних кодів визначається співвідношеннями:
для q-ного коду
для двійкового коду
Межі Хеммінга і Плоткіна є верхніми межами для кодового відстані при заданих n і k, які задають мінімальну надмірність, при якій існує перешкодостійкий код, що має мінімальну кодова відстань і гарантійно виправляє t u - кратні помилки.
Кордон Варшамова-Гільберта (нижня межа), що визначається співвідношеннями:
показує, при якому значенні nk визначено існує код, гарантійно виправляє помилки кратності t u.
ЛІТЕРАТУРА
1. Лідовскій В.І. Теорія інформації. - М., «Вища школа», 2002р. - 120с.
2. Метрологія та радіовимірювань в телекомунікаційних системах. Підручник для ВУЗів. / В. І. Нефедов, В. І. Халкин, Є. В. Федоров та ін - М.: Вища школа,
3. Цапенко М.П. Вимірювальні інформаційні системи. -. - М.: Енергоатом издат, 2005. - 440С.
4. Зюко А.Г. , Кловський Д.Д., Назаров М.В., Фінк Л.М. Теорія передачі сигналів. М: Радіо і зв'язок,
5. Б. Скляр. Цифрова зв'язок. Теоретичні основи та практичне застосування. Вид. 2-е, испр.: Пер. з англ. - М.: Видавничий дім «Вільямс»,