Згортальні двійкові коди

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

Ці коди можуть мати різну надлишковість, але найпростіше вони реалізуються при m = k, тобто коли n = m + k = 2m = 2k, а відносна швидкість передачі дорівнює

R = m/k = m/2m = 0,5.

У цьому випадку перевірки створюють послідовно пов’язані ланцюги, що й відображено в одній із назв коду «ланцюговий».

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

Передавання	Приймання
…	…
і т. д.

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

і + λ–і = і + λ + 1– (і +1) = і + 2λ + 1– (і +λ + 1) = …= λ.

Кожен контрольний символ порівнюється з відповідним перевірочним:

;

і т. д.

Ознакою відсутності спотворень є те, що усі суми дорівнюють нулю:

…= 0.

Спотвореним може бути як інформаційний, так і перевірочний символ.

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

Наявність двох сум, які дорівнюють одиниці і віддалені (зсунуті) між собою на крок додавання λ, свідчить про спотворення двох перевірочних символів.

Розглянемо приклад послідовного згортального коду з кроком додавання λ = 3 за умови, що перевірочні символи прийнято без спотворень. Нехай із спотворенням прийнято три інформаційних символи. Формування перевірочних і контрольних символів показано на рис. 5.1.

Рис. 5.1. Формування перевірочних і контрольних символів за наявності спотворення в символах з номерами 4, 5, 6

(Увага! Розташування перевірочних символів на цьому рисунку показано умовно і не відповідає вимогам до нього!)

Для заданих умов усі перевірочні символи дорівнюють нулю. У наслідок спотворення символів з номерами 4, 5, 6 серед контрольних символів, які формуються за участю спотворених, з’являються символи, що відрізняються від перевірочних, тобто дорівнюють одиниці.

Порівняємо контрольні елементи з перевірочними, які є прийнятими.

Видно, що утворилися три пари сум, які дорівнюють одиниці і зсунуті на крок додавання λ = 3:

і ; і ; і .

Звідси робимо висновок, що спотворені ті інформаційні символи, номери позицій яких є спільними в кожній парі сум, тобто а₄, а₅, а₅. Значення цих символів слід виправити на протилежні: прийнято 0–повинна бути 1 і навпаки. Отже, виправлено три спотворення, тобто кількість спотворень, що виправляються, дорівнює кроку додавання.

Із цього прикладу можна зробити і побічний висновок: значення λ визначає не лише крок додавання, а й глибину перемежування, тобто кількість окремих незалежних ланцюгів коду. Дійсно, при λ = 3 маємо три незалежних ланцюги:

Рис. 5.2. Формування перевірочних і контрольних символів за наявності спотворення в символах з номерами 1, 4, 5, 6, 12

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

Результат порівняння контрольних і перевірочних символів покажемо для кожного з ланцюгів:

перший ланцюг:
другий ланцюг:
третій ланцюг:

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

Перший ланцюг містить , , , , та відповідні перевірочні символи , , , . За умовою спотвореними є , . У цьому ланцюзі тільки одна із сум дорівнює одиниці:

.

Виходячи з правил виявлення спотворень, можна стверджувати, що спотвореним є перевірочний символ . Однак це суперечить умові прикладу: перевірочні символи прийнято без спотворень. Тобто виявлення спотворених інформаційних символів, які входять до першого ланцюга, не здійснено. Більш того, неправильно буде «виправленим» перевірочний символ .

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

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

.

За рівнянням можна виправити ; рівняння указує на спотворення , що суперечить умові. Отже, спотворення не виявлено і неправильно виправлено . Якщо узяти , можна вважати спотвореним , що є також неправильним.

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

1. Якщо спотворення перевищує можливості коду, код не лише не здатен виявляти та виправляти спотворення, але й вносить додаткові спотворення:

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

3. Місце розташування перевірочних символів визначається двома обставинами: по-перше, групова завада не повинна одночасно охоплювати інформаційні і відповідні перевірочні символи; по-друге, не повинно бути неправильного виправлення інформаційних символів.

Із цих міркувань перевірочні символи розташовуються на відстані 2λ + 1 символів від найближчого свого інформаційного. Наприклад, перевірочний символ , створений з інформаційних та повинен займати [(i + 2λ) + 2λ + 1 ] =
= (і + 4λ +1) позицію.

За таких умов згортальний код виправляє групове спотворення із λ інформаційних символів (див. перший приклад).

З викладеного раніше зрозуміло, що:

1. Інформаційні та перевірочні символи повинні чергуватися. Для визначеності будемо вважати, що інформаційні символи мають непарні номери, а перевірочні – парні.

2. Повинні бути сформованими два (λ = 2) незалежних ланцюги формування перевірочних (а в подальшому і контрольних) символів.

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

Важливою характеристикою згортального коду є мінімально допустима відстань між суміжними груповими спотвореннями, коли ще можна виправляти спотворень (див. рис. 5.3). Ця відстань повинна забезпечувати правильне приймання 2λ інформаційних символів після спотворення та 2λ перевірочних, які охоплюють спотворені інформаційні символи. Тому мінімальна допустима відстань дорівнює 4λ + 1 символів.

Рис. 5.3. Мінімально допустима відстань між груповими спотвореннями

Оскільки в інформаційних повідомленнях, що передаються неперервно, перевірочні та інформаційні символи чергуються: , п, , п, , …, то інформаційні символи, що входять у одну перевірку, рознесені поміж собою на λ інформаційних і λ перевірочних символів. Тобто при кроці додавання λ інформаційних символів згортальний код виправляє групове спотворення з b = 2λ інформаційних і перевірочних символів, а мінімально допустима відстань між груповими спотвореннями дорівнює

М = 4λ +1 = 2b + 1

інформаційних і перевірочних символів.