Принципи побудови завадостійких кодів - Цілісність і доступність інформації

Найчастіше як передумову при введенні кодів розглядають деякий початковий набір з m двійкових символів "0"и "1" (двійковий вектор), званий часто базовим кодовим словом (БКС). Зрозуміло, що число можливих БКС при цьому рівно числу можливих кодових комбінацій N0 = 2M. Кожне таке БКС можна розглядати як представлене в двійковій системі числення число А, діапазон представлення яких (робочий діапазон коду) знаходиться в межах від 0 до 2M, тобто А [0, 2M]. Для такого коду будь-яке випадкове викривлення можна розглядати у вигляді суми (як правило, порозрядної, по модулю 2) початкового коду і двійкового m символьного випадкового вектора Е. У звичного (не завадостійкого, не надлишкового) коду така сума є новим двійковим вектором з того ж набору можливих кодових комбінацій. Знайти при цьому викривлення неможливо.

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

А [0, 2N],

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

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

R (А) = F (A) mod (M).

0 2M 22m (M - 1) 2M 2N

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

Підкреслимо знов, що алгоритми розрахунку і модуля М і функціонала F (A) визначається алгоритмом побудови даного коду.

При такій постановці правомочно вважати контрольну ознаку лишком r (А).

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

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

Таке базове кодове слово можна вважати також представленням початкового числа А в системі числення в залишкових класах по двох основах р1 = 2M і р2 = М: де значення А в круглих дужках А = А mod (2M) = А, оскільки за умовою А < 2M.

Відомо, що при такому представленні і

М = 2K > 2M, (2)

Будь-яке викривлення в першому з символів (тобто в початковому числі А) переводить початкове число А з робочого діапазону [0, 2M] в контрольний [2M + 1, 2N], що може бути легко знайденим, а за певних умов така викривлення може бути і виправленою. Дійсно, викривлення в першому символі (тобто в початковому числі А) має в уявленні (1) вигляд Е/ = (Е, 0), тобто є числом кратним М, отже, числом вигляду Е = s М, де s = 1, 2, ..., (2M - 1). Тоді при будь-якому значенні М викривлене число В = A + s-М > 2M, тобто знаходиться в контрольному діапазоні.

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

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

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

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

Викривлення відсутня ? ? 1 випадок,

Одиночна викривлення ? випадків,

Двократна, викривлення ? випадків,

Викривлення кратності tВ - випадків.

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

2K ?

Звідкіля

K ? log2 . (3)

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

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

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

K ? log2 (С0П + С1П + С2N) або 2K ? 1 + n + [n (n ? 1)]/2. (4)

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

K

4

5

6

7

8

1 + n + [n (n ? 1)]/2

106

121

137

154

172

2k

16

32

64

128

256

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

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

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

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

Отже, при передачі якої-небудь кодової комбінації можливе число випадків невиявлення викривлень буде рівним

NНв = 2M. (5)

Оскільки число всіх можливих варіантів викривлень дорівнює 2N, де n кількість розрядів в кодовій комбінації, той вираз для визначення величини РНв матиме вигляд:

РНв = (2M 1)/2N = 1/(2N?m) 1/2N = 1/2K 1/2N, (6)

Де k = (n m) кількість надлишкових розрядів. З урахуванням того, що, як правило, n >> k, то величиною 1/2N можна знехтувати і вважати РНв ? 1/2K.

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

РВ = (2Nm) / 2N = 1 1/2K = 1 РНв. (7)

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

РПп = РВ РБр(t),

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

KПор ? 0,4 (m + kПор).

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

Похожие статьи




Принципи побудови завадостійких кодів - Цілісність і доступність інформації

Предыдущая | Следующая