Схемна реалізація кодерів та декодерів кодів БЧХ та Ріда-Соломона

Схемна реалізація кодеров та декодерів кодів БЧХ та Ріда-Соломона

1. Загальні основи кодування

Завдання кодування полягає у формуванні по інформаційних словах a(x) кодових слів ?(x) циклічного (n,k)- коду, що по своїй структурі може бути несистематичним і систематичним.

Формування кодових слів несистематичного коду полягає в множенні багаточлена a(x), що відображає інформаційну послідовність довжини k, на породжуючий багаточлен, тобто u(x)=a(x)g(x).

Формування кодових слів систематичного коду полягає в перетворенні інформаційної послідовності a(x) відповідно до виразу ?(x)=a(x)?xr+r(x). Перевірочна послідовність r(x) визначається двома способами: при використанні "класичного" способу кодування ; при використанні способу кодування, рекомендованого МККТТ , де x(1) r-1 - одиничний багаточлен ступеня (r-1). Зазначені вище математичні операції виконують кодери несистематичного й систематичного кодів, схеми яких показані, відповідно на рисунках 1 і 2.

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

де gi - коефіцієнти, які можуть приймати значення 0 або 1.

Регістри містять n-k розрядів, n-k суматорів по mod2, n-k+1 умовних зв'язків у кодері на рисунку 1 і n-k умовних зв'язків у кодере на рисунку 2. Наявність зв'язків у схемі регістрів визначається одиничним значенням коефіцієнтів gi у багаточлені g(x).

Якщо в багаточлені g(x) коефіцієнт gi=1, то i-й зв'язок і відповідний суматор входять у схему, у противному випадку i-й зв'язок і відповідний суматор виключаються. Робота кодера несистематичного коду завершується за n тактів. За перші k тактів на вхід кодера надходить інформаційне слово, а потім n-k нульових елементів.

У кодері систематичного коду за перші k тактів на вхід і одночасно на вихід надходить інформаційне слово a(x).

Протягом цього часу замкнутий зворотний зв'язок через И1 і у регістрі формується залишок r(x), елементи якого надходять на вихід через И2 за наступні n-k тактів.

Приклад. На рисунку 3 представлена схема кодера систематичного (7,4) - коду, що відповідає породженому багаточлену g(x)=x3+x2+1, у якому g0=g2=g3=1, а g1=0.

У кодері, що працює "класичним" способом, початковий стан розрядів регістра нульове, а в кодері, що працює способом МККТТ, одиничне.

На рисунках 4 і 5 наведені схеми декодерів, відповідно, несистематичного і систематичного кодів з виявленням помилок.

Основою декодерів є регістри зсуву зі зворотними зв'язками, структура яких, як і у кодерах, визначається обраним багаточленом g(x).

У декодері несистематичного коду за перші n-k тактів відбувається заповнення регістра символами, що надійшов з каналу зв'язку кодового слова, а потім протягом наступних k тактів здійснюється процес ділення, видачі через И1 на вихід інформаційного слова і формування залишку r(x) від ділення.

Після цього сформований залишок зчитується через елемент АБО. У декодері систематичного коду за перші k тактів інформаційні символи кодового слова надходять одночасно в регістр, а через елемент И1 на вихід декодера.

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

У схемі декодера систематичного коду, робота якого заснована на формуванні залишку у випадку відсутності помилки в прийнятому кодовому слові, замість елемента АБО передбачається елемент ТА-НІ, вхідна частина якого настроюється на R0(x).

2. Згорткові коди. Алгоритми кодування

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

Ціле число К є параметром, називаним довжиною кодового обмеження (constraint length); воно вказує число розрядів k-кортежу в кодуючому регістрі зсуву.

Важлива особливість згорткових кодів, на відміну від блокових, полягає в тому, що кодер має пам'ять -- k-кортежі, одержувані при згортковому кодуванні, є функцією не тільки одного вхідного k-кортежу, але і попередніх K-1 вхідних к-кортежів.

На практиці п и к -- це невеликі цілі числа, а К змінюється з метою контролю потужності і складності коду.

Будемо розглядати тільки найбільш часто використовувані двійкові згорткові кодери, для яких до к= 1, тобто ті кодуючи пристрої, у яких біти повідомлення зсуються по одному біту за раз, хоча узагальнення на алфавіти більш високих порядків не викликає ніяких утруднень. Як модель будемо використати згортковий кодер, показаний на рис. 6.

На цьому малюнку зображений згортковий кодер (2, 1) з довжиною кодового обмеження К = 3. У ньому є n =2 суматорів по модулю 2; отже, ступінь кодування коду k/n дорівнює 1/2.

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

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

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

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

Одиниця на i-й позиції вектора вказує на те, що відповідний розряд у регістрі зсуву пов'язаний із суматором по модулю 2, а нуль у даній позиції вказує, що зв'язку між розрядом і суматором по модулі 2 не існує. Для кодера на рис. 6 можна записати вектор зв'язку g1, для верхніх зв'язків, a g2 -- для нижніх.

g1= 111

g2 = 101.

Приклад кодування наведений на рисунку 7

Рисунок 7 - Приклад кодування

3. Згорткові коди. Алгоритми декодування

Декодування згорткових кодів ґрунтується на використанні решітчастих діаграм. Решітчаста діаграма для згорткового кодера, зображеного на рис. 6, показана на рис. 8

Рисунок 8 - Решітчаста діаграма кодера (ступінь кодування 1/2, К = 3)

При зображенні решітчастої діаграми скористалися позначеннями: безперервна лінія позначає вихідні дані, що генерируються вхідним нульовим битому, а пунктирна -- вихідні дані, що генерируються вхідним одиничним бітом.

Вузли решітки представляють стани кодера:

перший ряд вузлів відповідає стану а - 00,

другий і наступні -- станам b = 10, с -- 01, d =11.

У кожен момент часу для подання 2K-1 можливих станів кодера решітка вимагає 2К-1 вузлів.

У нашому прикладі після досягнення глибини решітки, рівної трьом (у момент часу t4), решітка має фіксовану періодичну структуру.

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

Також з кожного стану можна перейти в один із двох станів. Із двох вихідних галузей одна відповідає нульовому вхідному біту, а інша -- одиничному вхідному біту.

Один стовпець часового інтервалу сформованої решітчастої структури кодування повністю визначає код. Кілька стовпців показані винятково для візуалізації послідовності кодових символів як функції часу. Стан згорткового кодера відповідає стану крайніх правих К- 1 розрядів у регістрі кодера.

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

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

Перевага декодування Вітербі, у порівнянні з декодуванням по методу "грубої сили", полягає в тім, що складність декодера Витерби не є функцією кількості символів у послідовності кодових слів. Алгоритм містить у собі обчислення міри подоби (або відстані), між сигналом, отриманим у момент часу t1 і всіма шляхами ґрат, що входять у кожен стан у момент часу tx.

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

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