Сверточних код

Сверточних код - це коригувальний помилки код, в якому

(A) на кожному такті роботи кодера k символів вхідний полубесконечной послідовності перетворяться в n> k символів вихідний, і

(B) у перетворенні також беруть участь m попередніх символів;

(C) виконується властивість лінійності (якщо двом кодуються послідовностям \ Mathbf x і \ Mathbf y відповідають кодові послідовності \ Mathbf X і \ Mathbf Y , То кодованого послідовності a \ mathbf x + b \ mathbf y відповідає a \ mathbf X + b \ mathbf Y ).

Сверточних код є окремим випадком деревовидних і гратчастих кодів.


1. Історія виникнення

В 1955 Л. М. Фінком, який в той час був завідувачем кафедрою Ленінградської академії зв'язку, було запропоновано перший рекурентний код.

В 1959 західний фахівець Хегельбергер (Hegelbeger), що не мав уявлення про роботу радянських вчених у галузі кодування, "знову відкрив" рекурентний код і назвав його своїм ім'ям.

Сам Фінк в своїй монографії "Теорія передачі дискретних повідомлень" писав: "У цьому коді послідовність кодових символів не поділяється на окремі кодові комбінації. В потік інформаційних символів включаються коригуючі символи так, що між кожними двома інформаційними символами поміщається один коригувальний. Позначаючи інформаційні символи через a i, а корректірущіе через b i отримуємо таку послідовність символів:

a 1 b 1 a 2 b 2 a 3 b 3...... a k b k a k +1 b k +1.....

Інформаційні символи визначаються переданим повідомленням, а коригувальні формуються за таким правилом:

b i = (a ks + a k + s +1) mod 2, (1.1)

де s - довільне ціле число, зване кроком коду (s = 0,1,2 ...). Очевидно, що при помилковому прийомі деякого коригуючого символу b i співвідношення (1.1) в прийнятій послідовності не буде виконано для i = k. У разі ж помилкового прийому інформаційного символу a i співвідношення (1.1) не буде виконуватися при двох значеннях k i, а саме при k 1 = i - s - 1 і при k 2 = i + s. Звідси легко вивести правило виправлення помилок при декодуванні. У прийнятій кодовій послідовності для кожного b k перевіряється співвідношення (1.1). Якщо воно не виконується при двох значеннях k (k = k 1 і k = k 2), і при цьому

k 2 - k 1 = 2s +1, (1.2)

то інформаційний елемент a k 1 + s +1 повинен бути замінений на протилежний.

Очевидно, що надмірність коду дорівнює 1/2. Він дозволяє виправляти всі помилково прийняті символи, крім деяких невдалих поєднань. Так, якщо s = 0, він забезпечує правильне декодування, коли між двома помилково прийнятими символами є не менше трьох (а в деяких випадках двох) правильно прийнятих символів (при цьому враховуються як інформаційні, так і перевірочні символи). "


2. Загальна схема нерекурсівние кодера

Схема кодера нерекурсівние згортальної коди представлена ​​на Рис.1. Він складається з kq -Ічних регістрів зсуву з довжинами m_1. m_2, ..., m_k . Деякі (може і всі) входи регістрів і виходи деяких осередків пам'яті з'єднані з декількома n суматора за модулем q . Число суматорів більше числа регістрів зсуву: n> k

Рис.1. Загальна схема кодування сверточних кодом

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

  • Сумарна довжина m = \ sum_ {i = 1} ^ k m_i всіх регістрів зсуву називається кодовою обмеженням, а максимальна довжина w = \ max \ {m_1, ..., m_k \} - Затримкою.
  • Значення регістрів зсуву в кожен момент часу називається станом кодера.

3. Двійкові сверточних кодери

Для наочності представлення будемо описувати сверточное кодування по дії відповідного кодує пристрої.

Сверточних кодер - це пристрій, що приймає на кожному такті роботи в загальному випадку k вхідних інформаційних символів, і видає на вихід кожного такту n вихідних символів. Число R = \ frac {k} {n} називають відносною швидкістю коду. k - число інформаційних символів, n - число переданих в канал зв'язку символів за один такт надходження на кодер інформаційного символу. Вихідні символи розглянутого такту залежать від m інформаційних символів, що надходять на цьому й попередніх тактах, тобто вихідні символи згортальної коди однозначно визначаються його вхідними символами і станом, що залежить від m - k попередніх інформаційних символів. Основними елементами згортальної коди є: регістр зсуву, суматор за модулем 2, комутатор.

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

Суматор за модулем 2 здійснює складання надходять на нього символів 1 і 0. Правило додавання по модулю 2 таке: сума двійкових символів дорівнює 0, якщо число одиниць серед вступників на входи символів парно, і дорівнює 1, якщо це число непарне.

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

Систематичний сверточних код - це код, що містить у своїй вихідний послідовності кодових символів породила її послідовність інформаційних символів. Інакше код називають несистематичним.


4. Параметри і характеристики сверточних кодів

При сверточное кодування перетворення інформаційних послідовностей у вихідні та кодові відбувається безперервно. Кодер двійкового згортальної коди містить зсувний регістр з m розрядів і суматори за модулем 2 для освіти кодових символів у вихідний послідовності. Входи суматорів з'єднані з певними розрядами регістра. Комутатор на виході встановлює черговість посилки кодових символів в канал зв'язку. Тоді структуру коду визначають нижченаведені характеристики.

1. Число інформаційних символів, що надходять за один такт на вхід кодера - k.

2. Число символів на виході кодера - n, відповідних k, що надійшли на вхід символам протягом такту.

3. Швидкість коду визначається відношенням R = k / n і характеризує надмірність, вводимую при кодуванні.

4. Надмірність коду \ Vartheta = 1 - R

5. Пам'ять коду (вхідна довжина кодового обмеження або інформаційна довжина кодового слова), визначається максимально ступенем породжує многочлена у складі породжує матриці G (X):

l = k \ underset {i, j} {\ max} \ mathcal {b} \ deg g _ {i, j} (x) +1 \ mathcal {c}

6. Маркування згортальної коди позначається в більшості випадків (n, k, l), але можливі і варіації.

7. Вага w двійкових кодових послідовностей визначається числом "одиниць", що входять в цю послідовність або кодові слова.

8. Кодова відстань d показує ступінь відмінності між i-й і j-й кодовими комбінаціями за умови їх однакової довжини. Для будь-яких двох двійкових кодових комбінацій кодова відстань дорівнює числу незбіжних в них символів. У загальному вигляді кодова відстань може бути визначене як сумарний результат складання по модулю 2 однойменних розрядів кодових комбінацій d_ {i, j} = \ sum_ {k = 1} ^ L k_ {i, k} \ oplus k_ {j, k} , Де k_ {i, j} і k_ {jk} - K-е символи кодових комбінацій i і j; L-довжина кодової комбінації.

9. Мінімальна кодова відстань d_ {min} - Це найменше відстань Хеммінга для набору кодових комбінацій постійної довжини. Для його знаходження необхідно перебрати всі можливі пари кодових комбінацій. Тоді отримуємо d_ {min} = \ min d_ {ij} . Але! Це визначення справедливо для блокових кодів мають постійну довжину. Сверточних коди є безперервними і характеррізуются багатьма мінімальними відстанями, обумовленими довжинами початкових сегментів кодових послідовностей, між якими береться мінімальна відстань. Число символів в прийнятій для обробки довжині сегменти L визначає на приймальній стороні число осередків в декодер.


5. Загальний вигляд двійкового згортальної кодера

Нехай регістр зсуву містить m комірок, тобто пам'ять коду дорівнює m, комутатор виробляє один цикл опитування, проходячи значення 1 \ le k <m інформаційних символів, де m кратно k, при цьому за один цикл він опитує n \ Geq 2 виходів кодера. Кількість вихідних кодових символів, на яке впливає зміна одного вхідного інформаційного символу одно I_ {all} = \ frac {mn} {k} . Величина I all називається повною довгою кодового обмеження.

Оскільки коригуючі властивості конкретного згортальної коди визначаються довжиною кодового обмеження і вибором зв'язків зрушується регістру на суматор по модулю 2 ( XOR), то для завдання структури згортальної кодера необхідно вказати які розряди регістра зсуву пов'язані з кожним з суматори за модулем 2 ( XOR).

Зв'язок j-го суматора за модулем 2 описується j-ой породжує послідовністю:

g j = (g j0, g j1, g j2,..., g jm-1), (4.1)

де g_ {ij} = \ begin {cases} 1, & \ text {if stage i of register tied with XOR gate} \ \ 0, & \ text {in other cases} \ end {cases} (4.2)

Типові параметри сверточних кодів: k, n = 1,2, ..., 8; R = k / n = 1/4, ..., 7/8; m = 2, ..., 10.


6. Спосіб завдання сверточних кодів

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

Детальну інформацію про циклічних кодах читач зможе знайти в навчальному посібнику Сагаловіча Ю. Л. "Введення в алгебраїчні коди" [1] в розділах 4 і 5.

Породжує многочлен повністю визначає структуру двійкового кодера згортальної коди. На відміну від блокових кодів, кожен з яких описується лише одним породжує многочленом, сверточних код описується кількома породжують многочленами. Кількість многочленів, якими описується сверточних код визначається кількістю вихідних символів n. Уявімо послідовність інформаційних символів, що надходять на вхід кодера у вигляді многочлена: A (X) = a_ {0} + a_ {1} X + a_ {2} X ^ 2 + ... , Де X i - символ оператора затримки на i тактів роботи зрушується регістру, a i ​​= {0,1} - інформаційні двійкові символи. Многочлени, що описують n послідовностей кодових символів, що надходять на вхід комутатора кодера а потім в канал зв'язку, мають вигляд: B_ {j} (X) = b_ {0} ^ j + b_ {1} ^ jX + b_ {2} ^ jX ^ 2 + ... , Де b_ {i} ^ j = \ left \ {{0, 1} \ right \} двійкові кодові символи на j-му вході комутатора кодера.

j-й породжує многочлен згортальної коди має вигляд: G_ {j} (X) = g_ {0} + g_ {1} X + g_ {2} X ^ 2 + ... g_ {m-1} X ^ {m-1} , Де g_ {i} = {0, 1} двійкові коефіцієнти, що дорівнюють 1, якщо i-а осередок зрушується регістру через схему підсумовування пов'язана з j-им комутатором кодера, і рівні 0 у противному випадку. Причому, в силу лінійності згортальної коди і прийнятих позначень одержуємо: B_j (X) = G_j (X) A (X) .

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

У загальному випадку послідовність коефіцієнтів j-ого провадить многочлена буде мати вигляд G ^ j = {g_0 ^ j, g_1 ^ j, ... , G_ {m-1} ^ j} і збігається з породжує послідовністю коду (4.1). Тоді, якщо A = {a_0, a_1, a_2, ...} - Послідовність кодованих символів, а B_ {j} = {b_ {0} ^ j, b_ {1} ^ j, b_ {2} ^ j, ...} - Послідовність кодових символів на j-му вході комутатора кодера, то для будь-якого з них, що з'являється в \ Mu -Й момент часу ( \ Mu = 0, 1, 2 ... ), Можна записати:

b_ {\ mu} ^ {j} = \ sum ^ {m-1} _ {i = 0} {a_ {\ mu-i} g_i ^ j} Таким чином, кожен кодовий символ вихідний послідовності кодера згортальної коди визначається згорткою кодованого інформаційної та породжує послідовності, що і обумовлює назву сверточних кодів. Сверточних коди є окремим випадком ітеративних або рекурентних кодів.


7. Застосування

Сверточних коди використовуються для надійної передачі даних: відео, мобільного зв'язку, супутникового зв'язку. Вони використовуються разом з кодом Ріда - Соломона і іншими кодами подібного типу. До винаходу турбо-кодів такі конструкції були найбільш дієвими і задовольняли межі Шеннона. Так само сверточное кодування використовується в протоколі 802.11a на фізичному MAC-рівні для досягнення рівномірного розподілу 0 і 1 після проходження сигналу через скремблер, внаслідок чого кількість переданих символів збільшується в два рази і, отже, ми можемо добитися сприятливого прийому на приймаючому пристрої.


Література

  1. Галлагер Р. Теорія інформації та надійний зв'язок. - М .: Радянське радіо, 1974. - 720 с.
  2. Морелос-Сарагоса Р. Мистецтво завадостійкого кодування. Методи, алгоритми, застосування / пер. з англ. В. Б. Афанасьєва . - М .: Техносфера, 2006. - 320 с. - (Світ зв'язку). - 2000 прим. - ISBN 5-94836-035-0
  3. Фінк Л. М. Теорія передачі дискретних повідомлень. - М .: Сов. радіо, 1963. - 576 с.
  4. Нікітін Г. І. сверточних коди: Навчальний посібник. - СПб. : Сов. радіо, 2001. - 78 с.
  5. Сагаловіч Ю. Л. Введення в алгебраїчні коди: Навчальний посібник. - М .: МФТІ, 2007. - 262 с. - ISBN 5-7417-0191-4