Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Двійкові завадостійкі коди

Читайте также:
  1. Двійкові матричні коди

Характеристика завадостійких кодів

Завадостійке (надмірне) кодування, що ґрунтується на розробці і використанні завадостійких (корегуючих) кодів, широко застосовується в телекомунікаційних мережах (ТКМ) і їх елементах для захисту від спотворень при зберіганні інформації чи її передачі між окремими елементами ТКМ. Воно дозволяє одержати вищі якісні показники роботи систем зв’язку. Його основне призначення − забезпечення малої ймовірності спотворень переданої інформації, не зважаючи на впливи завад на канали її передачі або збоїв в роботі технічних пристроїв.

Завадостійким кодом називається певна n − розрядна сукупність із символів деякого інформаційного об’єкта чи його частини (m інформаційних символів) і контрольної ознаки (k перевірочних символів), які є додатковими, надлишковими. Ці надлишкові символи є непотрібними для відображення інформації, генерованої джерелом, і мають своїм призначенням забезпечення виявлення, а при деяких обставинах і виправлення спотворень, які виникають в інформаційних символах під час їх циркуляції в елементах ТКМ в наслідок впливу завад або збоїв в роботі технічних пристроїв.

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

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

Визначимо кількість перевірочних розрядів, необхідну для виправлення tсп спотворень. Для цього необхідно, щоб за допомогою перевірочних розрядів можна було описати наступні ситуації:

 

спотворення відсутні − − 1 випадок, одиночне спотворення − випадків, двократне спотворення − випадків, ……………………………………….. спотворення кратності tсп - випадків.

Таким чином, загальна кількість спотворень кратності tсп і менш дорівнює звідки мінімальне необхідне число перевірочних розрядів для виправлення спотворень кратності tв і менш визначається з наступної нерівності:

2k звідкіля k ≥ log2 . (1)

Нашим звичайним бажанням є − мати такий код, який дозволяє виправити усі можливі спотворення, тобто tсп = n. Тоді, використовуючи властивості коефіцієнтів бінома Ньютона:

k ≥ log2 = log2 2n = n,

k ≥ m + k,

що є неможливим.

Виходом з цієї ситуації є постановка задачі виявлення або виявлення і виправлення не будь-яких спотворень в початковому коді, а тільки всіх можливих в заданих умовах. Іншими словами відповідний завадостійкий код слід орієнтувати на реальну статистику спотворень в каналі передачі (у ЗП даного типа), коли число спотворених символів tсп = n·Рсп, де Рсп − згадана вище ймовірність спотворення біта в каналі передачі (ЗП).

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

Приклад.Кодова комбінація містить m = 10 інформаційних одиничних елементів. Визначити необхідне число перевірочних одиничних елементів для виправлення будь-якої двократної помилки.

Рішення.Вираз (1) для заданих умов матиме вигляд

k ≥ log2 ( + + ) або 2k ≥ 1 + n + [n (n − 1)]/2. (2)

Згідно з цим виразом складемо таблицю:

k
1 + n + [n (n — 1)]/2
2k

З таблиці видно, що умова (2) виконується лише при k ≥ 8 розрядах.

Відповідь.k = 8 розрядів.

Примітка. З формул (1) і (2) можна визначити нижню межу числа надлишкових розрядів. Практично ж кількість надлишкових розрядів перевищує вказане число.

Існує досить велика кількість різних завадостійких кодів, відмінних один від одного по ряду показників ефективності і , перш за все, по своїх корегуючих можливостях.

До числа показників ефективності − найважливіших характеристик корегуючих кодів відносяться:

значність коду, або довжина базового кодового слова (БКС), яка включає інформаційні символи (m) і перевірочні, або контрольні, символи (k). Звичайно значність коду п є сума n = т + k;

відносна швидкість коду − R, є відношенням числа інформаційних символів в кодовій комбінації m до значності коду n: R = m/n;

надмірність коду Кнадм, є відношенням числа контрольних символів в кодовій комбінації k до значності коду n:

Кнадм = к/n = (n − m)/n = 1 − m/n = 1 − R;

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

На визначенні останніх зупинимося більш детально.

Помилки не виявляються, коли передана кодова комбінація перетвориться в іншу дозволену. Число всіх дозволених комбінацій при m інформаційних розрядів рівне 2m,а при передачі n розрядів – 2n, із яких тільки 2m – дозволені, а решта – неможливі чи заборонені.

Оскільки число всіх заборонених кодових комбінацій рівне 2n - 2m, то ймовірність Рв може бути визначеною з виразу:

Рв = (2n - 2m) / 2n = 1 - 1/2k = 1 - Рнв. (3)

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

Рпп = Рв Рбр(t),

де Рбр(t) − ймовірність безвідмовної роботи пристрою за час передачі кодової комбінації, яка залежить від складності відповідних пристроїв. Таким чином, при збільшенні k (ускладненні пристроїв) зростає значення Рв, але зменшується Рбр(t), тому при збільшенні k більше деякого порогового значення ймовірність правильного прийому кодової комбінації може не підвищитися, а, навпаки, знизитися. Дослідження показують, що це порогове значення можна визначити з нерівності

kпор ≈ 0,4 (m + kпор).

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

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

При завдань коду звичайно указують, які інформаційні одиничні елементи базового кодового слова беруть участь у формувань кожного з до перевірочних розрядів.

Перший спосіб завдання− описовий, коли приводиться словесно − формульний опис процедури розрахунку контрольних символів при відомих інформаційних. Наприклад, для коду з n = 5, m = 3 і k = 2 кожен перевірочний розряд Пi може визначатися за правилом:

Пi = І2 І3, П2 =І1 І2,

де І − інформаційні розряди. Комбінація такого коду записується у вигляді П2ПiІ3І2І1. При завданні коду можна вказати всі дозволені для цього коду комбінації. Для систематичних кодів спосіб завдання коду можна значно спростити.

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

G (5, 3) =

другий стовпець указує, що при формуванні першого перевірочного розряду беруть участь другий і третій інформаційні розряди. Перший стовпець указує, що при нормуванні другого перевірочного розряду беруть участь перший і другий інформаційні розряди. Таким чином, при написанні матриці, що породжує, в канонічній формі спочатку пишуть одиничну матрицю розміром m m, а потім приписують до неї k стовпців, кожний з яких указує правила формування перевірочних розрядів. Тобто матрицю, що породжує, в канонічній формі можна позначити таким чином:

G (n, m) = .

Канонічна форма матриці, що породжує, може бути також записаною у вигляді

G (n, m) = .

При другому способі опису процес кодування математично записується у вигляді добутку матриці − рядка, що відображає передану кодову комбінацію, на матрицю, що породжує. (При виконанні всіх математичних перетворень підсумовування здійснюється по модулю 2). Припустимо, що передана кодова комбінація записана так:

І = .

Тоді процес кодування запишеться у вигляді

F = І G (n, m) = ПkПk−1…П1ІmІm−1Іm−2І2І1,

де Пі (і = 1, 2,...k) – перевірочні, а Іі (і = 1, 2, ..., m) – інформаційні розряди.

В результаті кодування одержимо комбінацію, де перші m розрядів − інформаційні (Іі), а останні k розрядів − перевірочні (Пі). Наприклад, закодуємо кодову комбінацію І = 1011 кодом (7, 4) з матрицею, що породжує

G (7, 4) = .

Для цього перемножимо матриці І і G: F = І G (7, 4). Одержимо

F = = 0101011,

де перші чотири розряди (1011) − інформаційні, а останні три (010) − перевірочні.

При декодуванніна приймальній стороні здійснюється стільки ж перевірок, скільки виконувалося і на передаючій, Кожна перевірка включає, окрім інформаційних розрядів, перевірочні розряди.

Результат цих перевірок указує або тільки на наявність або відсутність помилки, або номер спотвореного розряду.

4. Двійкові коди з перевіркою на парність або на непарність (контроль по модулю 2)

При побудові таких кодів передана послідовність розрядів розбивається на групи — базові кодові слова (БКС). У найпростішому випадку при перевірці в кожному базовому кодовому слові розраховується контрольна ознака (контрольний біт) шляхом складання по модулю 2 всіх двійкових символів БКС. Контрольна ознака (контрольний біт) записується в кінці БКС. При контролі на парність, в результаті цього, число одиниць в БКС доводиться до парного. Так, кодова комбінація 01110 в результаті кодування перетвориться в комбінацію 011101. Перевірочна матриця коду з перевіркою на парність має вигляд
Н (n, m) = ||111...1||.

Варіантом цього способу контролю цілісності є контроль на непарність, коли в кінець БКС як контрольна ознака (контрольного біта) дописується інверсне значення результату складання по модулю 2 всіх двійкових символів даного БКС. В результаті цього, при контролі на непарність, число одиниць в БКС доводиться до непарного. Так, кодова комбінація 01010 в результаті кодування перетвориться в комбінацію 010101.




Дата добавления: 2015-04-12; просмотров: 48 | Нарушение авторских прав

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | <== 37 ==> | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | 101 |


lektsii.net - Лекции.Нет - 2014-2023 год. (0.028 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав