ім. О.С. ПОПОВА

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

УДК 621.396.275

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

СІМЕЙ КОДІВ РІДА-СОЛОМОНА

Спеціальність 05.12.13 – Радіотехнічні пристрої та засоби

телекомунікацій

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

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

ОДЕСА–2004

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

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

Науковий керівник: кандидат технічних наук,

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

Офіційні опоненти: доктор технічних наук,

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

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

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

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

Захист відбудеться 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. Установлено, що РС-коди побудовані як на основі ПП, так і ДПФГ над довільними полями Галуа, є вкладеними: |

. | ()

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

, , , | ()

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

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

, , | ()

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

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

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

, , , , | ()

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

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

Властивість 3. Встановлено, що довільний -код складається точно з |

()

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

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

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

, , | ()

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

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

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

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

, | ()

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

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

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

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

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

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

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

АЛГОРИТМ А4.1:

Крок 1. Розрахувати і помістити в регістри пам'яті всі БКС відповідно до співвідношень - .

Крок 2. Представити номер переданого повідомлення у виді трьох параметрів — , як це пояснюється за допомогою правила на рис. та співвідношень .

Крок 3. Провести кодування -го повідомлення в кодове слово -коду відповідно до співвідношення .

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

Рис. | . | Узагальнена схема неалгебраїчного кодера -кодів

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

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

АЛГОРИТМ А4.2:

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

, , , , | ()

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

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

, — ПКС коду.

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

. | ()

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

, . | ()

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

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

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

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

АЛГОРИТМ А4.3:

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

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

, . | ()

Рис. | . | Структурна схема парціального декодера -кодів

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

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

Рис. | . | Структурна схема декодера в цілому

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

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

Рис. | . | Структурна схема повного ККД-декодера в цілому

ансамбля сигналів, побудованих на базі -коду

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

Рис. | . | Зовнішній вигляд модема М505Е

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

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

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

. | ()

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

. | ()

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

Дослідження енергетичної і частотної ефективності СПД із ШПС і -кодами і -кодами показали, що характер обміну енергетичної і частотної ефективності при переході від кодів Ріда-Соломона до кодів Віленкіна-Крестенсона носить нелінійний характер і дозволяє за рахунок погіршення енергетичної ефективності в середньому на 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 за рабочей полосой частот аналоговой системы передачи. Модем успешно прошел стендовые испытания.

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

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

Підписано до друку 6.09.04. Формат 60х84/16. Папір Business.

Гарнітура Таймс. 0,9 ум. друк. арк. Тираж 120 пр.

Одеський національний політехнічний університет

66044, Одеса, пр. Шевченка, 1