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

Згортальні (рекурентні, ланцюгові) коди уперше були запропоновані вченими СРСР Фінком Л.М. та Шляпноберским В.І. у 1955 році, і в 1959 році американським вченим Хагельбаргером Д.В. Ці коди належать до класу неперервних, оскільки як операції кодування, так і операції декодування здійснюються неперервно над послідовністю символів, яка не розділяється на блоки. Кожні n символів складаються, як і в інших кодах, із m інформаційних і k перевірочних. Достоїнством кодів є можливість виявляти і виправляти групові спотворення.

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

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

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

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

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

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

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

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

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

;
і т.д.

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

…= 0.

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

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

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

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

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

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

 

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

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

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

і ; і ; і .

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

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

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

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

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

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

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

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

.

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

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

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

.

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

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

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

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

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

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

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

Розглянемо приклад формування інформаційної послідовності для кроку додавання λ = 2 номерів символів. Із викладеного раніше зрозуміло, що:

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

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

В таблиці 1 наведено розподіл номерів символів послідовності між інформаційними та перевірочними (контрольними) та розподіл номерів інформаційних символів між ланцюгами.

Таблиця 1

Номери символів інформаційної послідовності
Номери інформаційних символів першого ланцюгу                          
Номери інформаційних символів другого ланцюгу                            
Номери перевірочних символів                      

Взаємне розташування інформаційних і перевірочних символів для наведеного прикладу представлено на рис. 3.

Рис. 3. Взаємне розташування інформаційних і перевірочних символів при
λ = 2

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

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

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

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

М = 4λ +1 = 2b + 1

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