Алгоритми кореляційного декодування сімей кодів Ріда-Соломона

Размещено на http://www.allbest.ru/

ОДЕСЬКА НАЦІОНАЛЬНА АКАДЕМІЯ ЗВ'ЯЗКУ ім. О.С. ПОПОВА

МИЦ СЕРГІЙ ВАЛЕРІЙОВИЧ

УДК 621.396.275

АЛГОРИТМИ КОРЕЛЯЦІЙНОГО ДЕКОДУВАННЯ СІМЕЙ КОДІВ РІДА-СОЛОМОНА

Спеціальність 05.12.13 - Радіотехнічні пристрої та засоби телекомунікацій

Автореферат дисертації на здобуття наукового ступеня

кандидата технічних наук

ОДЕСА-2004

Дисертацією є рукопис

Робота виконана на кафедрі “Радіотехнічні системи” Одеського національного політехнічного університету Міністерства освіти і науки України.

Науковий керівник: кандидат технічних наук, професор кафедри “Радіотехнічні системи” Одеського національного політехнічного університету Мазурков Михайло Іванович.

Офіційні опоненти: доктор технічних наук, професор кафедри “Документальний електрозв'язок” Одеської національної академії зв'язку Рудий Євген Михайлович;

кандидат технічних наук, інженер електрозв'язку ЗАТ “Київстар Дж. Ес. Ем.” Прокопов Cергій Дмитрович.

Провідна установа: Національний технічний університет України “Київський політехнічний інститут”.

Захист відбудеться 12 жовтня 2004 р. о 10 годині на засіданні спеціалізованої вченої ради Д 41.816.02 в Одеській національній академії зв'язку ім. О.С. Попова за адресою: 65029, м. Одеса, вул. Кузнечна, 1.

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

Автореферат розісланий 7 вересня 2004 р.

Вчений секретар спеціалізованої вченої ради Д 41.816.02, д.т.н., проф. В.М. Плотніков

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

циклічний код алгоритм декодування

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Тема дослідження дисертаційної роботи відповідає науковому напрямку проектів ТОВ “УКРЗВ'ЯЗОК” і СПКБ “Дискрет”, а також науковим планам кафедри “Радіотехнічні системи” Одеського національного політехнічного університету (ОНПУ). Основні результати роботи впроваджені:

1. В ОКР модемів М505E і М2001 ТОВ “УКРЗВ'ЯЗОК”.

2. В ОКР за контрактом № 2-10/15-02/1256/д (Розробка і виготовлення вимірювальної апаратури для космічного наукового експерименту “Обстановка-1”) СПКБ “Дискрет”.

3. У навчальний процес кафедри “Радіотехнічні системи” ОНПУ для підготовки фахівців з напрямку “Радіотехніка”.

Мета і задачі дослідження. Метою роботи є побудова регулярних алгоритмів і економічних схем кореляційного декодування сімей РС-кодів, на основі урахування нових структурних властивостей частотно-часової циклічності цих кодів.

Основні задачі дисертаційної роботи:

1. Дослідження алгебраїчної частотно-часової структури кодів Ріда-Соломона і розробка моделі їхнього представлення у вигляді сімей багатопараметричних дискретних функцій.

2. Дослідження структурних властивостей РС-кодів на основі швидких ортогональних перетворень над полями Галуа з метою побудови економічних схем їхніх кодеків.

3. Розробка регулярних алгоритмів синтезу базових і породжуючих кодових слів для побудови суміжних класів кодів Ріда-Соломона.

4. Побудова й аналіз дистанційних властивостей сімей еквівалентних класів кодів Ріда-Соломона.

5. Розробка алгоритмів і економічних структурних схем неалгебраїчного кодування і кореляційного декодування на основі урахування властивостей частотно-часової циклічності РС-кодів.

6. Дослідження ефективності спільного застосування сімей кодів Ріда-Соломона з кореляційним декодуванням і ортогональними ШПС.

7. Оцінка складності технічної реалізації кодеків розрізнення ансамблів ШПС на основі сімей РС-кодів і розробка практичних рекомендацій для застосування побудованих схем кодеків кореляційного декодування.

Об'єкт дослідження: зменшення складності технічної реалізації кодеків кореляційного декодування сімей кодів Ріда-Соломона.

Предмет дослідження: алгоритми та економічні схеми кореляційного декодування на основі обліку нових властивостей частотно-часової циклічності сімей РС-кодів.

Методи дослідження. Методи теорії алгебраїчних полів Галуа і теорії чисел дозволили розкрити регулярну структуру частотно-часової циклічності РС-кодів і встановити, що довільний РС-код можна представити у вигляді сімей трипараметричних дискретних функцій, при цьому задача декодування зводиться до максимального-правдоподібного оцінювання цих трьох параметрів. Метод математичного моделювання дозволив розкрити і вивчити структурні і дистанційні властивості РС-кодів і їхніх сімей. Використовуючи метод математичної індукції, отримані властивості сформульовано в загальному вигляді. На основі байєсівського методу прийняття рішень розрахована завадостійкість і ефективність спільного застосування ШПС і РС-кодів.

Наукова новизна отриманих результатів

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

2. Побудовано еквівалентні коди Ріда-Соломона і коди, задані дискретним перетворенням Віленкіна-Крестенсона над полями Галуа і встановлено їхні структурні і дистанційні властивості.

3. Уведено розбивку потужності коду Ріда-Соломона на непересічні парціальні підкоди з метою зменшення складності технічної реалізації кодеків і розроблено регулярний алгоритм рекурентного синтезу безлічі БКС і ПКС для побудови кожного парціального коду.

4. Побудовано регулярні алгоритми неалгебраїчного кодування РС-кодів на основі безлічі БКС та імовірнісного декодування РС-кодів на основі безлічі ПКС.

5. Розроблено регулярний алгоритм і економічні схеми ковзного кореляційного декодування (ККД) РС-кодів на основі знайдених структурних властивостей частотно-часової циклічності.

6. Проведено оцінку складності технічної реалізації кодеків розрізнення ансамблів ШПС на основі сімей РС-кодів і розроблені практичні рекомендації для їхнього застосування.

Практичне значення отриманих результатів

1. Розроблено принципи побудови, алгоритми роботи й економічні структурні схеми кодеків шумоподібних сигналів, кодованих кодами Ріда-Соломона. Порівняно з класичною схемою трансверсального багатоканального фільтра запропонована схема ККД-декодера в цілому ансамбля ШПС на базі -кодів над розширеним полем Галуа дозволяє за рахунок збільшення кількості елементів пам'яті в разів знизити число узгоджених з окремим ШПС фільтрів у раз і число двовходових суматорів у разів. Запропонований алгоритм декодування -кодів має лінійну складність технічної реалізації, а повний декодер працює з максимальним рівнем паралелізму.

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

3. З використанням матеріалів дисертації виконана практична розробка модемів М505Е та М2001 у рамках проектів ТОВ “УКРЗВ'ЯЗОК”, що успішно пройшли польові випробування в Україні, Болгарії та США, що підтверджено відповідними протоколами випробувань.

Індивідуальний внесок здобувача складається в дослідженні структурних властивостей РС-кодів і їхніх сімей, розробці алгоритмів неалгебраїчного синтезу РС-кодів і схем кодеків, що працюють за критерієм максимуму правдоподібності, аналізу завадостійкості СПД із ШПС. Запропоновані в роботі алгоритми і схеми були доведені здобувачем до практичного застосування в розробці модемів М505Е и М2001 у рамках проектів ТОВ “УКРЗВ'ЯЗОК”.

Апробація результатів дисертації. Матеріали дисертації доповідалися:

1. На Міжнародній молодіжній науковій конференції “XXV Гагарінські читання”, м. Москва, 6-10 квітня 1999 р.

2. На Всеукраїнській молодіжній науково-практичній конференції “Людина i космос”, м. Дніпропетровськ, 19-21 травня 1999 р.

3. На IV міжнародній конференції по телекомунікаціях “НТК - Телеком - 99”, м. Одеса, 14-17 вересня 1999 р.

4. На II Всеукраїнській молодіжній науково-практичній конференції з міжнародною участю “Людина i космос”, м. Дніпропетровськ, 12-14 квітня 2000 р.

5. На III Міжнародній молодіжній науково-практичній конференції “Людина i космос”, м. Дніпропетровськ, 18-20 квітня 2000 р.

6. На II Міжнародній науково-практичній конференції “Сучасні інформаційні й електронні технології”, м. Одеса, 28-31 травня 2001 р.

7. На III Міжнародній науково-практичній конференції “Сучасні інформаційні й електронні технології”, м. Одеса, 19-23 травня, 2003 р.

Публікації. З теми дисертації автором опубліковано усього 11 наукових праць. Основний зміст дисертаційної роботи опубліковано в 4 статтях у наукових журналах та в 7 статтях праць конференцій. Обсяг і структура дисертації. Дисертація складається з вступу, п'яти розділів, висновків та п'яти додатків. Загальний обсяг дисертаційної роботи становить 189 сторінок, з яких 148 сторінки основного тексту, 7 сторінок з таблицями, 25 сторінок додатків. Список використаної літератури на 9 сторінках включає 99 найменувань.

ЗМІСТ РОБОТИ

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

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

,

де -- степінь розширення простого поля, а -- просте число, є циклічним кодом з породжуючим поліномом (ПП) вигляду

(1)

Де -- мінімальна кодова відстань -коду;

-- число перевірочних символів;

-- один з первісних елементів ;

, -- цілочисельні параметри: , .

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

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

На підставі проведеного аналізу стану питання сформульована мета роботи і задачі досліджень.

У другому розділі встановлені і доведені нові й узагальнені відомі структурні і дистанційні властивості кодів Ріда-Соломона, що задаються породжуючим поліномом і дискретним перетворенням Фур'є над простими і розширеними полями Галуа (ДПФГ).

Властивість 1. Установлено, що РС-коди побудовані як на основі ПП, так і ДПФГ над довільними полями Галуа, є вкладеними:

. (2)

Уведено нове поняття циклічності коду за частотою і доведена частотно-часова циклічність довільного РС-коду. Довільний лінійний -код назвемо циклічним за частотою, якщо разом з кожним кодовим словом , , він містить також усі кодові слова вигляду

, , , (3)

Де -- знак операції додавання елементів над у полі .

Властивість 2. Довільний -код є одночасно циклічним за часом і циклічним за частотою, тобто разом з кожним дозволеним словом РС-код містить усі кодові слова вигляду

, , (4)

Де -- оператор циклічного зрушення за часом на величину ;

-- величина зрушення за частотою кожного елемента кодового слова.

Парціальним циклічним за частотою -кодом, де для кожного , назвемо код

, , , , (5)

Де -- знак операції множення елементів у полі .

Вихідне слово , назвемо базовим кодовим словом, або, скорочено, БКС, а всі кодові слова вигляду , -- породжуючими кодовими словами, або, скорочено, ПКС.

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

(6)

Третій розділ присвячено дослідженню структурних і дистанційних властивостей нового класу лінійних кодів, заданого перетворенням Віленкіна-Крестенсона (ПВК) над полями Галуа. Цей клас кодів позначимо скорочено як -коди.

Як і для кодів Ріда-Соломона формування -коду здійснюється за правилом:

, , (7)

Де -- -ковий вектор-рядок кодового слова довжини ;

-- - ковий вектор-рядок інформаційного слова довжини ;

-- потужність коду.

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

, (8)

Де -- матриця оберненого перетворення Фур'є порядку ;

-- символ, що означає -й кронекерівський степінь;

-- один з первісних елементів поля .

Властивість 5. У силу лінійності співвідношень (7) і (8) -коди є лінійними й в окремому випадку, при , являють собою клас добре відомих кодів Ріда-Соломона. В іншому окремому випадку, коли кратно -коди попадають в інший відомий клас кодів прямих добутків, для якого кодами-співмножниками є -коди.

Властивість 6. Показано, що для -кодів, як і для -кодів, справедлива властивість вкладеності і циклічності за частотою. Строга циклічність за часом -кодів переходить у багапетлевий циклічний зсув (-зсув) -кодів.

У четвертому розділі розроблено алгоритми та економічні схеми кодеків імовірнісного і кореляційного декодування кодів Ріда-Соломона. Проводиться оцінка складності технічної реалізації запропонованих схем кодеків.

На основі знайдених структурних властивостей 1, 2, 4 і розроблених алгоритмів А2.1 і А2.2 синтезу БКС, представимо роботу кодера у вигляді процедур, які позначимо як

АЛГОРИТМ А4.1:

Крок 1. Розрахувати і помістити в регістри пам'яті всі БКС відповідно до співвідношень Ошибка! Источник ссылки не найден. - Ошибка! Источник ссылки не найден..

Крок 2. Представити номер переданого повідомлення у виді трьох параметрів -- , як це пояснюється за допомогою правила на рис. Ошибка! Источник ссылки не найден. та співвідношень Ошибка! Источник ссылки не найден..

Крок 3. Провести кодування -го повідомлення в кодове слово -коду відповідно до співвідношення Ошибка! Источник ссылки не найден..

Приведений алгоритм роботи реалізується за допомогою узагальненої схеми кодера представленої на рис. 2, де прийняті такі позначення: ДП -- джерело повідомлень; ЛП -- лічильно-розв'язальний пристрій, що реалізує співвідношення Ошибка! Источник ссылки не найден.; ПС -- пристрій синхронізації; РП -- регістр пам'яті базових кодових слів , ; БПм -- блок перемножування вектора на скаляр ; БПс -- блок підсумовування координат вектора з числом .

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

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

АЛГОРИТМ А4.2:

Крок 1. За законами додавання і множення в алгебраїчному полі розрахувати безліч , поелементних різниць вигляду

, , , , (9)

Де , -- прийняте в умовах завад кодове слово;

-- знак операції віднімання елементів у полі ;

, -- ПКС коду.

Крок 2. Для кожного , знайти параметр -- максимальне число однакових різниць у ланцюжках виду:

. (10)

Крок 3. Знайти параметр

, . (11)

Крок 4. Провести декодування , де параметр відповідає максимальному значенню виразу (11); параметр такому, котре зустрічається в , максимальну кількість разів.

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

На рис. 3 представлена структурна схема декодера, що реалізує розроблений алгоритм декодування в цілому кодів Ріда-Соломона.

На підставі сформульованих у розд. 2 властивостей вкладеності, частотно-часової циклічності, трипараметричності РС-кодів і розроблених алгоритмів А2.1, А2.2 і А4.2 у роботі розроблено алгоритм роботи декодера в цілому кодів Ріда-Соломона, що реалізує процедуру декодування за критерієм максимальної правдоподібності, чи, що те ж, за критерієм мінімуму відстані Хеммінга. Зазначену процедуру позначимо як

АЛГОРИТМ А4.3:

Крок 1. Провести парціальне декодування прийнятого кодового слова в кожному парціальному декодері відповідно до алгоритму 4.2, знайти максимально-правдоподібні значення параметрів ( , ) і відповідні їм значення числа збігів , .

Крок 2. Провести декодування в цілому, для цього знайти максимально правдоподібне значення параметра з умови:

, . (12)

Зазначений алгоритм декодування реалізується за допомогою узагальненої схеми декодера, де прийняті наступні позначення: ПДn -- -й парціальний декодер, реалізуючий процедуру декодування А4.3; РС -- розв'язальна схема, що реалізує добір максимуму; ДДП -- декодер джерела повідомлень, що на основі знайдених трьох параметрів (, , ) видає номер максимально правдоподібного повідомлення ; ОП -- одержувач повідомлення.

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

За аналогією з відомим рекурентным алгоритмом ковзного кореляційного декодування циклічних кодів у роботі побудовано алгоритм ковзного кореляційного декодування і структурна схема декодера в цілому кодів Ріда-Соломона.

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

Отримані алгоритми неалгебраїчного кодування і кореляційного декодування були використані в ОКР високочастотного модема M505E, зовнішній вигляд якого наведений на рис. 6. Модем M505E призначений для організації високошвидкісної передачі цифрових потоків кбіт/с (Х.21), Т1, Е1 чи Е2 по кабельних та радіорелейних системах зв'язку, у тому числі і тропосферних, c модуляцією піднесучої, розташованої вище спектра сигналів бакатоканальної телефонії чи телебачення, або в основній смузі частот стандартних вторинних чи третинних групових трактів.

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

П'ятий розділ присвячений дослідженню завадостійкості та ефективності СПД зі спільним застосуванням ШПС і сімей кодів Ріда-Соломона; пошуку кодів, оптимальних за критерієм мінімуму смуги частот, займаною системою з кодуванням.

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

(13)

Визначено робоче співвідношення для частотної ефективності -кової СПД з ортогональними сигналами і -кодами:

. (14)

За методом А.Г. Зюко побудовані -, - діаграми для СПД з ортогональними ШПС різного об'єму без кодування і з використанням РС- і ВК-кодів.

Дослідження енергетичної і частотної ефективності СПД із ШПС і -кодами і -кодами показали, що характер обміну енергетичної і частотної ефективності при переході від кодів Ріда-Соломона до кодів Віленкіна-Крестенсона носить нелінійний характер і дозволяє за рахунок погіршення енергетичної ефективності в середньому на 1 дБ одержати збільшення частотної ефективності в середньому на 4 дБ.

У розвиток робіт Л.Е. Варакіна в дисертації наведені параметри оптимальних РС-кодів для . Уперше знайдені параметри оптимальних -кодів.

Досліджено характер обміну між - і -ефективностями -кодів. Обмін носить нелінійний характер і в середньому при зменшенні основи системи числення за рахунок погіршення на 5 дБ -ефективності відбувається збільшення -ефективності в середньому на 7,5 дБ.

ВИСНОВКИ

1. Встановлено ряд нових структурних властивостей алгебраїчної частотно-часової структури РС-кодів. Показано, що коди Ріда-Соломона над довільними полями Галуа є вкладеними:

.

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

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

Розроблені рекурентний алгоритм А2.1 синтезу множини БКС у часовій області і рекурентный алгоритм А2.2 синтезу множини БКС у частотній області.

Знайдені властивості показують, що коди Ріда-Соломона доцільно розглядати як трипараметричні.

2. На основі властивостей 1, 2, 4 розроблено алгоритм А4.1 ефективного кодування кодів Ріда-Соломона як трипараметричних і запропонована узагальнена схема кодера РС-кодів. Для формування кожного кодового слова потрібно не більш ніж операцій додавання і множення, тоді як прямий метод вимагає множення інформаційного вектора на породжуючу матрицю, тобто операцій.

3. За аналогією з відомим алгоритмом декодування -кодів запропоновано алгоритм А4.2 і структурна схема декодера парціального коду. На його основі, завдяки знайденій властивості трипараметричності РС-кодів, запропоновані алгоритм А4.3 імовірнісного декодування і структурна схема декодера в цілому кодів Ріда-Соломона. Обчислювальні витрати алгоритму в разів менше порівняно з декодуванням за методом повного перебору. Усі парціальні декодери ідентичні за структурою і мають лінійну складність технічної реалізації, а повний декодер працює з максимальним рівнем паралелізму.

4. Розроблено алгоритм ковзного кореляційного декодування і структурна схема декодера в цілому кодів Ріда-Соломона. Порівняно з класичною схемою трансверсального багатоканального фільтра схема ККД-декодера в цілому ансамбля ШПС на базі -кодів дозволяє, за рахунок збільшення кількості елементів пам'яті в разів, знизити число узгоджених з окремим ШПС фільтрів у разів і число двовходових суматорів у разів. Запропоновано алгоритм декодування -кодів має лінійну складність технічної реалізації, а повний декодер працює з максимальним рівнем паралелізму, при цьому арифметична частина декодера складається з однотипних модулів -- двовходового суматора та елемента пам'яті.

5. Уведено правило кодування і оцінені параметри нового класу -ічних лінійних кодів, заданих перетворенням Віленкіна-Крестенсона над простими полями Галуа. Встановлено, -коди є лінійними й в окремому випадку, при , являють собою клас добре відомих кодів Ріда-Соломона. В іншому окремому випадку, коли кратно -коди попадають в інший відомий клас кодів прямих добутків, для якого кодами-співмножниками є -коди. Показано, що для -кодів, як і для -кодів, справедлива властивість вкладеності і циклічності по частоті. Отримано аналітичні вирази для мінімальної кодівої відстані -кодів та вагової функції довільного -коду.

6. Проведено дослідження завадостійкості, енергетичної і частотної ефективності СПД із ШПС та сім'ями РС-кодів. Показано, що характер обміну енергетичної і частотної ефективності при переході від кодів Ріда-Соломона до кодів Віленкіна-Крестенсона носить нелінійний характер і дозволяє за рахунок погіршення енергетичної ефективності в середньому на 1 дБ одержати збільшення частотної ефективності в середньому на 4 дБ.

У продовженні робіт Л.Е. Варакіна приведені параметри оптимальних РС-кодів для . Уперше знайдено параметри запропонованих -кодів.

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

7. Для -коду над розроблені в роботі алгоритми неалгебраїчного кодування А4.1 і кореляційного декодування А4.2 і А4.3 знайшли впровадження у високочастотному модемі М505Е для режиму роботи модему з ФМ-4 за робочою смугою частот аналогової системи передачі. Модем успішно пройшов випробування в Україні, у Болгарії та у США, що підтверджено відповідними протоколами іспитів.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Мазурков М.И., Миц С.В., Чечельницкий В.Я. Алгоритм рекуррентного декодирования в целом кодов Рида-Соломона // Радиоэлектроника (Изв. вузов).-- 2003.-- №6.-- С 3438.

2. Мазурков М.И., Миц С.В. Метод вероятностного декодирования циклических кодов Рида-Соломона // Радиоэлектроника (Изв. вузов).-- 1999.-- №7.-- С 17-23.

3. Миц С.В. Основные параметры кодов кронекеровских степеней // Труды ОПУ.-- 2000.-- Вып. 2.-- С. 165-168.

4. Миц С.В. Определение минимального кодового расстояния и весового спектра кодов Виленкина-Крестенсона // Труды ОПУ.-- 2002.-- Вып. 1.-- С. 164-166.

5. Миц С.В. Вероятностный метод декодирования кодов Рида-Соломона // Труды международной молодёжной научной конференции “XXV Гагаринские чтения”.-- Москва: МАТИ, 1999.-- С. 160-161.

6. Миц С.В. Структурные особенности кодов Рида-Соломона // Труды всеукраинской молодёжной научно-практической конференция “Людина i космос”.-- Днепропетровск: НЦАОМУ, 1999.-- С. 191.

7. Мазурков М.И., Миц С.В. Классы линейных кодов на основе преобразования Виленкина-Крестенсона в конечных полях // Труды IV-ой международной конференции по телекоммуникациям “НТК-Телеком-99”.-- Одесса: УГАС, 1999.-- С. 54-58.

8. Миц С.В. Структурные и дистанционные свойства классов линейных кодов на основе преобразования Виленкина-Крестенсона в простых полях // Труды IV-ой международной конференции по телекоммуникациям “НТК-Телеком-99”.-- Одесса: УГАС, 1999.-- С. 58-61.

9. Миц С.В., Мазурков М.И. Минимальное кодовое расстояние кодов на основе преобразования Виленкина-Крестенсона // Труды II Всеукраинской молодёжной научно-практической конференции с международным участием “Людина i космос”.-- Днепропетровск: НЦАОМУ, 2000.-- С. 307.

10. Мазурков М. И. Миц С. В. Весовой спектр кодов заданных преобразованием Виленкина-Крестенсона // Труды второй международной научно-практической конференции “Современные информационные и электронные технологии”.-- Одесса: ОНПУ, 2001.-- С. 56-57.

11. Мазурков М. И. Миц С. В. Корреляционное декодирование кодов Рида-Соломона // Труды четвертой международной научно-практической конференции “Современные информационные и электронные технологии”.-- Одесса: ОНПУ, 2003.-- С. 87.

АНОТАЦІЇ

Миц С.В. Алгоритми кореляційного декодування сімей кодів Ріда-Соломона.

Дисертація на здобуття наукового ступеня кандидата технічних наук за фахом 05.12.13 - Пристрої радіотехніки та засобів телекомунікацій. - Одеська національна академія зв'язку ім. А.С. Попова, Одеса, 2004.

Дисертація присвячена синтезу нових алгоритмів і схем кореляційного декодування на основі властивостей частотно-часової циклічності сімей кодів Ріда-Соломона (-кодів), що допускають зменшення складності технічної реалізації їх кодеків. Запропоновано трьохпараметричне трактування кодів Ріда-Соломона. Розроблено алгоритм неалгебраїчного кодування й імовірнісного декодування кодів Ріда-Соломона як трьохпараметричних та запропоновані узагальнені схеми кодера та декодера в цілому -кодів. Розроблено алгоритм ковзного кореляційного декодування й структурна схема декодера в цілому кодів Ріда-Соломона. Розроблено новий клас кодів Віленкіна-Крестенсона (-кодів) і вперше знайдені параметри оптимальних -кодів. Розроблені в роботі алгоритми впроваджені у високочастотному модемі М505Е.

Ключові слова: коди Ріда-Соломона, коди Віленкина-Крестенсона, еквівалентні коди, апаратурна складність кодеків.

Mits S.V. Correlation decoding algorithms of Reed-Solomon codes families.

The dissertation seeking Ph.D. degree in the speciality 05.12.13 - Radio engineering devices and tools of telecommunications. -- Odessa national academy of communication by A.S.Popov, Odessa, 2004.

The dissertation is devoted to synthesis of algorithms and circuits of correlation decoding on the basis of time-and-frequency cyclicity properties of Reed-Solomon codes families (-codes). The three-parametrical treatment of Reed-Solomon codes is offered. The algorithm of nonalgebraic coding and probabilistic decoding of Reed-Solomon codes as three-parametrical is developed and the generalized circuits of the coder and the decoder as a whole of -codes are offered. The algorithm of sliding correlation decoding and the block diagram of the decoder as a whole Reed-Solomon codes is developed. The new class of Vilenkin-Chrestenson codes (-codes) is developed and for the first time parameters of optimum -codes are found. The algorithms developed in work are introduced in high-frequency modem M505E.

Key words: Reed-Solomon codes, codes Vilenkin-Chrestenson, equivalent codes, codecs hardware complexity.

Миц С.В. Алгоритмы корреляционного декодирования семейств кодов Рида-Соломона.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.12.13 - Устройства радиотехники и средств телекоммуникаций. - Одесская национальная академия связи им. А.С. Попова, Одесса, 2004.

Диссертация посвящена синтезу алгоритмов и схем корреляционного декодирования на основе свойств частотно-временной цикличности семейств кодов Рида-Соломона (-кодов), допускающие уменьшение сложности технической реализации кодеков систем передачи данных (СПД) с шумоподобными сигналами (ШПС).

Показано, что произвольный -код вне зависимости от вида построения являются вложенным, циклическим по времени и циклическим по частоте кодом.

Введено новое понятие парциального кода. Установлено, что произвольный -код вне зависимости от вида построения состоит ровно из парциальных, непересекающихся циклических по частоте кодов. В рамках каждого парциального подкода выделено базовое кодовое слово (БКС), на основе которого синтезируется вся мощность парциального кода.

Разработаны рекуррентный алгоритм А2.1 синтеза множества БКС во временной области и рекуррентный алгоритм А2.2 синтеза множества БКС в частотной области.

Найденные структурные свойства позволили сформулировать важнейшее свойство трехпараметричности кодов Рида-Соломона, разработать алгоритм А4.1 неалгебраического кодирования кодов Рида-Соломона как трехпараметрических и предложить обобщенную схему кодера -кодов. Отметим, что для формирования каждого кодового слова требуется не более чем операций сложения и умножения, тогда как прямой метод требует умножения на информационного вектора на порождающую матрицу.

Предложен алгоритм А4.2 декодирования парциального кода и разработана структурная схема парциального декодера. На его основе предложен алгоритм А4.3 вероятностного декодирования произвольного -кода и разработана структурная схема декодера в целом кодов Рида-Соломона. Вычислительные затраты алгоритма в раз меньше по сравнению с декодированием по методу полного перебора.

Разработан алгоритм скользящего корреляционного декодирования (CКД) и структурная схема декодера в целом кодов Рида-Соломона. По сравнению с классической схемой трансверсального многоканального фильтра схема CКД-декодера в целом ансамбля ШПС на базе -кодов позволяет, за счет увеличения количества элементов памяти в раз, снизить число согласованных с отдельным ШПС фильтров в раз и число двухвходовых сумматоров в раз.

Введено правило кодирования и оценены параметры нового класса p-ичных линейных кодов, заданных преобразованием Виленкина-Крестенсона над простыми полями Галуа (-коды). Установлено, что -коды являются линейными и в частном случае, при , представляют собой класс хорошо известных кодов Рида-Соломона. В другом частном случае, когда кратно -коды попадают в другой известный класс кодов прямых произведений, для которого кодами-сомножителями являются -коды. Показано, что для -кодов, как и для -кодов, справедливо свойство вложенности и цикличности по частоте. Получено аналитическое выражение для минимального кодового расстояния -кодов и для весовой функции произвольного -кода.

Проведены исследования помехоустойчивости, энергетической и частотной эффективности СПД с ШПС и семействами -кодов. Показано, что характер обмена энергетической и частотной эффективности при переходе от кодов Рида-Соломона к кодам Виленкина-Крестенсона носит нелинейный характер и позволяет за счет ухудшения энергетической эффективности в среднем на 1 дБ получить увеличение частотной эффективности в среднем на 4 дБ. В продолжении работ Л.Е. Варакина приведены параметры оптимальных -кодов для . Впервые найдены параметры оптимальных -кодов.

Найдены условия целесообразного практического применения полученных в работе корреляционных алгоритмов декодирования и при построении каскадных систем кодирования с применеием низкоскоростных кодов на одной или нескольких ступенях кодирования, при разработке космических систем связи, когда отсутствует ограничение на полосу частот, занимаемую системой с кодирование, а также в кабельных системах связи при работе за основной рабочей полосой частот канала. Разработанные в работе алгоритмы неалгебраического кодирования А4.1 и корреляционного декодирования А4.2 и А4.3 нашли внедрение в высокочастотном модеме М505Е для режима работы модема с ФМ-4 за рабочей полосой частот аналоговой системы передачи. Модем успешно прошел стендовые испытания.

Таким образом, проведенные в настоящей диссертационной работе разработки алгоритмов показали, что декодированием семейств -кодов может осуществляться корреляционным методом. Существенное уменьшение аппаратурной сложности кодека для низкоскоростных кодов, подтверждает целесообразность практического использования предложенных алгоритмов для построения экономичных схем кодеков СПД.

Ключевые слова: коды Рида-Соломона, коды Виленкина-Крестенсона, эквивалентные коды, аппаратурная сложность кодеков.

Размещено на Allbest.ur

...