Применение сверточного кода в цифровых системах связи

Кодер загорткового коду містить тактовий регістр пам’яті для збереження визначеного числа інформаційних символів і перетворювач вхідної інформаційної послідовності у вихідну кодову послідовність. Структурна схема кодера ЗК (7.5) зображена на малюнку 1.1.

 

Мал.1.1 – Структурна схема кодера

Послідовність кодування детально розписана в  таблиці 1.

Таблиця 1 - Процес кодування послідовності  інформаційних бітів 01101000

 

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

Кодові  грати цього коду показані на мал. 1.1. При його складанні враховано, що кодер містить пам'ять у  вигляді дворозрядного регістра. Кожному з чотирьох можливих станів цього регістра відповідає один з  чотирьох вузлів решітки. Тому лівий символ в позначенні вузла дорівнює останньому інформаційному біту, вже записаному в регістр. При записі в регістр чергового інформаційного символу регістр міняє стан на одне з двох сусідніх. Цей перехід позначений ребрами грат. Порядок вузлів вибраний таким, що при нульовому поточному інформаційному символі (а=0) перехід в наступний стан відповідає верхньому ребру, а при = 1 - нижньому.

Рисунок 1.1 - Кодові грати

 

Кожній  інформаційній послідовності відповідає певний шлях на кодових гратах і  кодова послідовність. Наприклад, вхідним  інформаційним бітам 01100 відповідає кодове слово 00 11 01 01 11, якому відповідає на мал. 1.1 шлях, відмічений жирною лінією.

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

Алгоритм Вітербі реалізує оптимальне (максимально правдоподібне) декодування  як рекурентний пошук на кодових гратках шляху, найближчого до послідовності, що приймається. На кожній ітерації алгоритму Вітербі зіставляються два шляхи, що ведуть в даний стан (вузол гратки). Найближчий з них до прийнятої послідовності зберігається для подальшого аналізу. Нехай передається нульове кодове слово, а в каналі виникла трикратна помилка, так що прийнята послідовність має вигляд 10 10 00 00 10 00 ... 00 .... Результати пошуку найближчої дороги після прийому 14 елементарних блоків показані на рисунку 1.2.

 

Рисунок 1.2 - Приклад роботи алгоритму Вітербі

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ТЕОРЕТИЧНА  ЧАСТИНА

2.1.

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

При використанні згорткових кодів потік даних розбивається на менші блоки довжиною k символів (в окремому випадку k₀=1), які називаються кадрами інформаційних символів.

Кадри інформаційних символів кодуються кадрами кодових символів довжиною n_o символів. При цьому кодування кадру інформаційних символів в кадр кодового слова проводиться з урахуванням попередніх m кадрів інформаційних символів. Процедура кодування, таким чином, пов'язує між собою послідовні кадри кодових слів. Передана послідовність стає одним напівнескінченних кодовим словом. 
Розвиток теорії і практики згорткових кодів помітно відрізняється від розвитку блокових кодів. При побудові блокових кодів і методів їх декодування широко використовувалися алгебраїчні методи. У разі згорткових кодів це не так. Більшість хороших згорткових кодів було знайдено шляхом перегляду за допомогою ЕОМ великого числа кодів і подальшого вибору кодів з хорошими властивостями. Декодування згорткових кодів проводиться методами, близькими до методів максимального правдоподібності, причому в цьому випадку вони реалізуються досить просто.

Основними характеристиками згорткових кодів є величини:

-   k₀ - розмір кадру інформаційних символів;

-   n₀ - розмір кадру кодових символів;

-   m - довжина пам’яті коду;

-   k = (m+1) • k₀ - інформаційна довжина слова;

-   n = (m+1) • n₀ - кодова довжина блоку.

 

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

Нарешті, згортковий код має ще один важливий параметр - швидкість R=k/n, яка характеризує ступінь надмірності коду, що вводиться для забезпечення виправляють властивостей коду.

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

Можливі різні способи опису згорткових кодів, наприклад, за допомогою породжує матриці. Правда, в силу нескінченності кодованої послідовності і породжує матриця буде мати нескінченні розміри. Точніше, вона буде складатися з нескінченного числа матриць G для звичайного блочного коду, розташованих уздовж головної діагоналі підлозі нескінченно і матриці. Вся інша її частина заповнюється нулями. 
На малюнку 2.1 представлена найпростіша схема кодера для згорткового коду

з відносною швидкістю R = 1/2.

Рисунок 2.1 - Схема кодера для згорткового коду з відносною швидкістью R=1/2.

 

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

Одним із способів подання простих кодуючих пристроїв є діаграма стану; таке подання кодера показано на малюнку 2.2. Стан показане в рамках діаграми, представляє собою можливе вміст К-1 крайніх правих розрядів регістра, а шлях між станами - кодові слова гілок на виході, що є результатом переходів між такими станами. Стани регістра вибрані наступними: а=00, b=10, c=01, d=11; діаграма показана на рис. 2.2, ілюструє всі можливі зміни станів для кодера показаного на рис. 2.2. Існує всього два вихідних з кожного стану переходу, що відповідають двом можливим вхідним бітам. Далі для кожного шлях між станами записано кодове слово на виході, пов'язане з переходами між станами. При зображенні шляхів, суцільною лінією прийнято позначати шлях, пов'язаний з нульовим вхідним бітом, а пунктирною лінією - шлях, пов'язаний з одиничним вхідним бітом. Зазначимо, що за один перехід неможливо перейти з даного стану в будь-яке довільне. Так як за одиницю часу переміщається тільки два можливих переходу між станами, до яких регістр може переходити за час проходження кожного біта. Наприклад, якщо стан кодера - 00, то при наступному зміщенні можливе виникнення тільки станів 00 або 10.

 

Кодування по таблиці станів кодера: 
 В якості вихідного значення візьмемо число - 08. Закодуємо дані цифри в двійковій-десятковому коді і якщо перший символ 0, виправимо його на 1.

   0        8

1000  1000

Зазвичай кодер для згорткових кодів будуватися на базі k-розрядного регістра зсуву (k - кодове обмеження), суматорів по модулю 2 і вихідного ключа-комутатора.

Схема кодера показана на малюнку 2.1.

Побудуємо таблицю станів кодера:

Таблиця 2.1 – Конфігурації помилок в кадрах

Такти	U	S1	S2	S3	V1	V2
0		0	0	0
1	1	1	0	0	1	1
2	0	0	1	0	1	0
3	0	0	0	1	1	1
4	0	0	0	0	0	0
5	1	1	0	0	1	1
6	0	0	1	0	1	0
7	0	0	0	1	1	1
8	0	0	0	0	0	0

V1 = S1 + S2 + S3;

V2 = S1 + S3.

Кодування по таблиці станів здійснюється наступним чином. За розрядами вхідної кодової комбінації (U) визначається стан кодера (S1, S2, S3) на кожному такті, а по ним розряди на виході кодера (V1, V2). Таким чином, з таблиці отримуємо:

Вхід     1 0  0   0  1  0  0  0

Вихід 1110110011101100

Кодування по спрямованому графу:

Побудуємо спрямований граф:

Малюнок 2.2 – Діаграма станів кодера (степень кодування R=1/2).

Закодуємо з даного графу ту ж саму послідовність, що і в таблиці станів кодера. Для цього, починаючи з початкового стану (S1 = 0, S2 = 0), необхідно переміщатися по стрілках в залежності від того, які значення кодера U (0 або 1) надходять на вхід (тобто розряди вихідної кодової послідовності) до відповідного стану S1 і S2. Кожен такий перехід відповідає отриманню деякої кодової комбінації вихідних розрядів (V1 і V2) сукупність яких і буде представляти собою вихідну кодову послідовність, тобто вихід кодера. Таким чином, отримуємо:

Вхід    1   0  0  0  1  0  0  0

Вихід 1110110011101100.

 

2.2  Синдромное декодування згорткових кодів

 

Припустимо, що нами прийнята напівнескінченна послідовність r, що складається зі слова згортального коду і вектора помилки:

r = U + e.        (2.1)

Аналогічно тому, як це робиться для блокових кодів, можна обчислити синдром прийнятої послідовності:

S = r•H = e•H.                                             (2.2)

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

Малюнок 2.3 - Схема декодера для згорткового (12,9)-кода Вайнера-Еша.

 

Виправлення помилок за допомогою даного декодера проводиться на сегментах з трьох кодових кадрів - п = 12.

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