Принципи завадостійкого кодування за допомогою циклічних кодів. Колєнов С.О

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

Операція, в результаті дії якої здійснюється перетворення прийнятого коду до повідомлення, називається декодуванням.

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

Якщо - число всіх можливих комбінацій кодів, - число дозволених комбінацій, то число заборонених комбінацій: .

Надлишковість .

Різниця між комбінаціями рівномірного коду прийнято характеризувати кодовою відстанню Хеммінга (d), рівним найменшому числу символів, якими комбінації Аi іАj відрізняються одна від одної. Дозволена комбінація повинна максимально відрізнятись від забороненої.

Приклад: є дві послідовності:

. Вага комбінації W=3 (кількість одиниць в коді).

. Вага комбінації W=2

Щоб знайти мінімальну кодову відстань між кодами і , треба просумувати їх за модулем 2. Отримаємо і мінімальна кодова відстань це вага цієї комбінації: d=3.

Чим більше d, тим стійкіша система до помилок.

Помилку завжди можна знайти, якщо її кратність g, тобто число спотворених символів кодової комбінації, менше кодової відстані. При g> d помилки теж можуть бути виявлені, але є ймовірність, що помилкова комбінація збігається з якою-небудь дозволеною комбінацією. Мінімальна кодова відстань, при якому виявляться будь-які поодинокі помилки, дорівнює d = 2.

Для того щоб помилка була виправлена​​, необхідно, щоб її кратність задовольняла нерівності

Мінімальна кодова відстань, при якій можливе виправлення будь-яких поодиноких помилок, дорівнює трьом, тобто d = 3

ЦИКЛІЧНІ КОДИ

Недоліком більшості лінійних кодів є складність процедури декодування.
Спрощення алгоритмів і пристроїв декодування можливо, якщо накласти на код крім властивості лінійності ще деякі обмеження і використовувати ці обмеження при декодуванні. Таким обмеженням може бути, наприклад, властивість циклічності. Лінійні коди, що задовольняють цьому обмеженню, називаються циклічними.
Циклічним кодом називається такий код, який разом з кожним кодовим словом (a0, a1, ..., an-1) містить також і його циклічну перестановку (a1, a2, ..., a0). При такому визначенні для завдання коду досить задати лише одне кодове слово. Решта кодові слова утворюються з вихідного шляхом циклічного зсуву і складанням всіх лінійних комбінацій циклічного зсуву.

Початкове кодове слово прийнято ставити у вигляді породжує полінома (генераторного полінома) q (x) ступеня r. Наприклад, q(x)=1+x+x³ або у двійковій запису 1101.
Для того щоб поліном був генераторним поліномом циклічного коду, необхідно, щоб він був дільником полінома виду xⁿ+1, де n-значність коду – кількість символів в коді, яким передається одна літера алфавіту наприклад. При розподілі поліномів дії проводяться за правилами арифметики по модулю два, в которойвичітаніе рівносильно додаванню.
Для побудови циклічного коданеобходімо знати розкладання полінома xⁿ+1 на множники.
Якщо n=2^m-1, то многочлен xⁿ+1 представляється як добуток непріводімих многочленів мірою не вище m. Кожен з цих многочленів, а також їхні твори можуть бути використані як породжують поліноми циклічного коду.

Приклад. Нехай n=2³-1=7

Поліном x⁷+1 розкладається на такі множники:

x⁷+1=(x+1)(x³+x+1)(x³+x²+1), які можна використати, як породжуючі поліноми:

q1(x) =x+1 породжує код (7, 6), де перше число – повна к-сть символів в коді, друге – кількість інформаційний символів;

q2(x) =x³+x+1 породжує код (7, 4);

q3(x) =x³+x²+1 породжує код (7, 4);

q1(x) q2(x) и q1(x) q3(x) породжують код (7, 3).

Породжуюча матриця циклічного коду в якості рядків має вектори q(x), xq(x),..., x^k-1q(x):

де q0, ..., qr – коефіцієнти генераторного поліному.

Перевірочна матриця будується на основі поліному

ступеня k і має вигляд

где h0, h1, … - коефіцієнти перевірочного поліному h(x).

При такій побудові коду множення повідомлення на породжує матрицю еквівалентно множенню повідомлення, представленого у вигляді полінома, на генераторний поліном. Дійсно, нехай повідомлення має вигляд a (x) = a0 + a1x + a2x2 + ..., a ∈ 0,1.

Тоді (a0 a1…) G = [a0q0, (a0q1+ a1q0), (a0q2+ a1q1+ a2q0) …], що еквівалентно множенню поліномів:

a(x) q(x) = a0q0, (a0q1+ a1q0) x+…

З способу кодування випливає, що будь-яке кодове слово має ділитися на q (x). Нехай, наприклад, генераторний поліном дорівнює q (х)= 1+x+x³. Цей поліном є дільником поліному x⁷+1, т.е. n=7, а h(х) = 1+x+x²+x⁴.

Нехай передається повідомлення 1010, тобто v(х) = 1+x². Після кодування отримаємо наступне кодове слово:

т.е. 1110010. Аналогічно можна знайти інші кодові слова. Наприклад, повідомленням 0001 відповідає код 0001101, повідомлення 1111 - 1001011.
Розглянутий спосіб кодування не дозволяє розділити інформаційні й перевірочні символи, а код, який при цьому виходить, називається нероздільним кодом. Використання нероздільних кодів з багатьох причин незручно. Циклічний нероздільний код можна зробити разделіми наступним чином. Допишемо до інформаційної послідовності nk нулів, що еквівалентно множенню її полінома на x^n-k, після чого поділимо на генераторний поліном:

е R-деякий залишок. Помножимо обидві частини на q (x) і перенесемо залишок у ліву частину:

Так як c - ціле, то v (x) xr + R (x) ділиться на q (x) і, отже, є кодовим словом. Таким чином, для того щоб закодувати повідомлення, необхідно приписати до інформаційних символам залишок від ділення v(x)x^n-k/q(x). Можна показати, що при такому способі кодування безліч кодових слів залишається тим же самим, а змінюється тільки таблиця відповідності повідомлень і кодових слів.

Приклад. Повідомлення v (x) = 0001.

Залишок 101. Кодове слово 1010001.

Білет №21

Поиск по сайту: