Принципи побудови каскадних кодів.
Каскадні коди
Каскадні коди будуються за принципом поетапного застосування двох або більше процедур кодування до послідовності інформаційних символів. При цьому символами коду наступного етапу (ступеня) кодування є слова попереднього ступеня коду. Процедура кодування двійковим каскадним кодом зводиться до наступного. Послідовність двійкових символів повідомлення, що передається, розбивається наK k-елементних блоків. Коженk-елементний блок розглядається як символ нового (q-ичного) алфавіту і підлягає кодуванню (N,K)q-ічним кодом. В результаті реалізації процедури кодування (N,K)-кодом доk-елементних блоків додаєтьсяN-Kнадлишковихk-елементних блоків або символівq-ного алфавіту. Передбачається, що ці надлишкові символи мають уявлення у виглядіk-елементних двійкових послідовностей. (N,K)-код отримав назвукоду другого ступеняабозовнішнього коду. Кожен ізN k-елементних символів зовнішнього коду кодується двійковим (n,k)-кодом першого ступеня.
Код першого ступеняназивають такожвнутрішнім кодом. Процедура каскадного кодування пояснюється рис. 9.2. В результаті кодування виходить двійковий блок довжиноюN×n, що є кодовою комбінацією каскадного коду.
Теоретично кодування доведено, що побудований зазначеним способом каскадний код є лінійним і його кодова відстаньDkне менше, ніж добуток кодових відстаней зовнішньої (D) і внутрішньої (d) кодів:
Двійкова інформаційна послідовність, що підлягає кодуваннюкаскадним кодом, надходить у зовнішній кодер, де розбивається наk-елементні блоки, кожен з яких розглядається зовнішнім кодером якq-їчний символ у двійковому поданні. Для кожнихKтакихq-вих символів зовнішній кодер формуєN–Kнадлишковихq-вічних символів, т. е.k-елементних блоків. Інформаційні та надлишковіk-елементні блоки потім надходять у внутрішній кодер, де перетворюються на кодові комбінації двійкового (n,k)-коду. Структура системи каскадного кодування представлена рис.9.3.
Блок довжиниnпередається каналом і надходить у внутрішній декодер. Потік даних, що надходить на вихід внутрішнього декодера, складається зk-елементних блоків, які розглядаються зовнішнім декодером як символи (N,K)-коду. На виході зовнішнього декодера формуютьсяK k-елементних блоків, що надходять до споживача інформації.
Перевагою каскадних кодів є відносно низька складність пристроїв, що кодують і декодують, так як каскадні коди дозволяють виконати процедури кодування і декодування по етапах, застосовуючи на кожному етапі досить короткі в порівнянні з результуючим коди.
Каскадні коди дозволяють реалізувати досить велику кодову відстань, тому їхнє застосування на каналах із перешкодами ефективно.
Поетапна реалізація процедури декодування дозволяє раціонально розподілити функції між внутрішнім та зовнішнім декодерами, реалізуючи виправлення помилок при мінімальній складності їх побудови, коли внутрішній декодер виявляє та частково виправляє помилки, а зовнішній декодер виправляє помилки та стирання.
Інша перевага каскадних кодів полягає в тому, що в силуневеликих довжин внутрішніх та зовнішніх кодів для виправлення помилок та стирань можна використовувати не лише різні конструктивні методи, але й перебірні.
Ефективність використання каскадних кодів підвищується за рахунок деякої декореляції помилок, що з'являються вk-елементних блоках внаслідок поетапної процедури декодування.
2. Режими використання каскадних кодів
Можливі різні алгоритми декодування внутрішнього та зовнішнього кодів. Внутрішній код можна декодувати з виправленням помилок, виявленням помилок, а також з частковим виправленням помилок малих кратностей і виявленням помилок вищих кратностей.
У двох останніх випадках підблоки, в яких виявлені помилки, вважаються стертими, тобто надалі при декодуванні не використовуються. Інформація, що міститься в них, відновлюється при декодуванні зовнішнього коду.
Відповідно до цього зовнішній код може використовуватися для виправлення помилок, не виправлених внутрішнім кодом, для виправлення стирань або для спільного виправлення стирань та помилок. Можливе використання зовнішнього коду у режимі виявлення помилок. При цьому стертий блок можна відновити шляхом використання зворотного зв'язку.
Таким чином, можливі такі режими використання каскадних кодів:
- виправлення помилок внутрішнім та зовнішнім кодами;
- виявлення помилок внутрішнім та виправлення стирань зовнішнім кодами;
- виявлення помилок внутрішнім та виправлення стирань та помилок зовнішнім кодами;
- часткове виправлення та виявлення помилок внутрішнім та виправлення стирань зовнішнім кодами;
- часткове виправлення та виявлення помилок внутрішнім та виправлення стирань та помилок зовнішнім кодами.
Найбільш простий уреалізації другого алгоритму. Він вимагає мінімальної надмірності, особливо у разі формування стирання елементів з оцінки надійності їх прийому, тобто при застосуванні непрямих методів підвищення достовірності. Виправлення стираньq-ічним кодом реалізується значно простіше, ніж виправлення помилок і зводиться до вирішення лінійної однорідної системи рівнянь над полемGF(q). При використанні в якості зовнішнього коду РС-коду зD=N–K+1 можливе виправлення всіх стирань кратності Δ=N–K. Помилкове декодування блоку при цьому відбувається у двох випадках: при невиявленні помилок внутрішнім кодом і при виявленні помилок більш ніж у комбінаціях внутрішнього коду.
Застосування ступінчастої процедури декодування каскадних кодів дозволяє з їх допомогою регулювати введення надмірності в повідомлення, що передається в залежності від стану каналу зв'язку.
Один з таких методів описаний в [5] стосовно системи зі зворотним зв'язком. Прямим каналом передаються блоки внутрішнього (n,k)-коду, які на приймальній стороні перевіряються на наявність помилок і при їх виявленні стираються. ПершіKблоків (n,k)-коду розглядаються як інформаційні елементи PC-коду (N,K>), і по них генеруються перевірочні елементи цього коду, які порівнюються з надлишковими елементами PC-коду, що надходять від передавача, а при їх розбіжності стираються. Як тільки приймачем буде прийнято всьогоKнестертих блоків, відновлюються стерті інформаційні елементи (N,K)-коду і зворотним каналом посилається команда припинення передачі. І тут надмірність скорочується з допомогою неповної передачі надлишкових елементів PC-кода. За відсутності помилок вони взагалі не передаються.Назвемо цей методметодом обмеження надмірності.
Можливий інший метод - метод запиту додаткової надмірності. Він передбачає застосування укорочених PC-кодів. У цьому випадку для кожного наборуKінформаційних блоків передавач формує кілька наборів надлишкових елементів різної тривалості:N1–K, …,Ni–K. Передача починається з (N1,K) PC-коду. Якщо приймачN1 елементів PC-коду прийнявKнестертих елементів, то методом виправлення стирань відновлюютьсяKінформаційних елементів. Якщо при довжиніN1 число нестертих елементів меншеK, то приймач запитує наступний за тривалістю набір надлишкових елементів і т. д. доти, поки на довжині інформаційної та надлишкової частини не буде прийнято нестертимиKелементів PC-коду.
У цьому випадку надмірність скорочується за рахунок повторної передачі лише надмірності PC-коду без повторної передачі інформаційних елементів.
Зазначені переваги каскадних кодів роблять їх перспективними використання у апаратурі передачі.
3. Побудова двійкових каскадних кодів на основі кодів Ріда-Соломона та Боуза-Чоудхурі-Хоквінгема
Двійковий каскадний код може бути побудований на основі PC-коду таким чином:
1. Двійкові інформаційні елементи повідомлення розбиваються наKпідблоківkелементів у кожному. Кожен підблокkелементів записується як елемент поляGF(2k), в результаті чого отримуємо послідовність зKелементівGF(2k).
2.K-елементна послідовність елементівGF(2k) кодується (N,K) PC- кодом надGF(2k). В результаті отримуємокодова комбінація зовнішнього коду.
3. Кожен ізNелементів зовнішнього коду, що є двійковою послідовністю довжиниk, кодується двійковим (n,k)-кодом з мінімальним відстаннюd– внутрішнім кодом.
Чи не знайшли те, що шукали? Скористайтеся пошуком: