Бодян Г. К., Бодян Д. Г., Дунай Л. Ф. Технічний університет Молдови ТУМ Шт. чел Маре, 168, Кишинів – MD2012, Р. Молдова Тел.: + (37322) 237505; e-mail: gbodean@mail.md

Анотація – Описана технологія декодування мат-роідние (М-коду), досліджено складність завдання і процедури декодування, представлені схемні рішення процесу декодування М-кодів.

I. Вступ

Блок-схема кодера матроідного (М-) коду представлена ​​в роботі [1]. Там же, в загальних рисах, описаний алгоритм декодування М-коду. Таким чином, рішення задачі декодування М-коду тільки задекларовано, але не розглянута детально.

Нагадаємо суть проблеми. Довжина п прийнятого слова v дорівнює: n = 2t + k, де к – число вихідних т-розрядних символів, t – число помилкових символів. Наприклад, якщо к = 8 і t = 8, то п = 24. У загальному випадку, декодер повинен знайти коректне рішення серед

С *, тобто С94 = 735471, систем (з к = 8) лінійних

рівнянь. На перший погляд завдання видається складно розв’язати. (З’являється “спокуса” віддати перевагу кодами Ріда-Соломона).

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

II. Основна частина

Матроідние коди відносяться до класу лінійних кодів. Кодування і декодування слів коду виконується (або повинна виконуватися) асинхронно (за один такт). Загальна схема “матроідного” кодування і декодування представлена ​​на малюнку 1.

На вхід кодера подається вихідний вектор а (х), що містить до символів розрядності т. Кодер виконує лінійне перетворення виду:

v(x)=a(x)»Uk.n,                                 (1)

де U – матриця КХП однорідного матроіда.

Перетворення (1) легко здійснимо і детально описано в [1]. На виході кодера формується асинхронно вектор v (x), який надсилається по комунікаційному каналу (лінії зв’язку) одержувачу. Прийнятий вектор v ‘(x), можливо містить помилки, надходить на вхід “решателя” System Solver. Цей решатель являє собою комбінаційну схему, яка містить блоки множення (мультиплікатори) і підсумовування по модулю р (х), де р (х) – породжує поліном розширеного поля Галуа

Для до обраних

1=1

символів прийнятого вектора v ‘(x) вирішується відповідна система лінійних рівнянь. В результаті виходить рішення а (х) – обчислені значення компонент вихідного вектора а (х).

Отриманий таким чином вектор а (х) “пропускається” через кодер, на виході якого формується обчислене значення вектора v (x). Обчислений і

прийнятий вектора відповідно v (x) і v ‘(x) порівнюються (також асинхронна операція!), на підставі чого приймається рішення: чи є обчислений вектор а (х) коректним, або отримана інформація помилкова і слід виконати повну процедуру відновлення вихідних даних?

Процедура повного відновлення – блок Restore на діаграмі рис.1, передбачає вирішення

N = С1 п систем лінійних рівнянь. Серед N рішень можуть бути коректні і помилкові. Блок Restore повинен вибрати коректне рішення, тобто

обчислений вектор а (х), та видати його на вихід

декодера. З ростом п величина Л /, з точки зору апаратних витрат, стає неприйнятно великий. Наприклад, для к = 8 і t = 8, маємо N = С * 4 = 735471 рішень систем лінійних рівнянь.

Рішення системи лінійних рівнянь являє собою значення / (-значного вектора а (х) =, адо), Де tf, = f (v ‘), М, …, к. Апаратна

реалізація (одного) лінійного перетворення tf (.) = f (v ‘) являє собою / (-входові комбінаційне пристрій, що виконує до множень по модулю р (х) і підсумовування по модулю р (х) результатів творів. Тоді складність одного перетворювача складе величину:

с (/ < ) = / <(мультиплікаторів) +1 (суматор), (2) а складність пристрою обчислення компонент к-розрядного вектора а (х) складе величину:

С (к) = к-с (к) = / с2 (Мультиплікаторів) + / < (суматор).

Для аналізованого прикладу, маємо С (8) = 64 +8, а складність всіх решателей систем лінійних рівнянь декодера складе величину:

NC (k) або 735471-73 = 52953912. (3)

Це досить значне значення навіть для сучасного рівня розвитку СВЧ техніки. У той же час, складність процедури відновлення багато в чому залежить від способу розв’язання систем лінійних рівнянь.

Крім зазначеної проблеми складності реалізації решателей декодера, слід виділити, також, завдання вибору коректних рішень. Прийнятий вектор v ‘(x) може містити помилку кратності е, де ee {1, …, f}. В цьому випадку, з усього безлічі рішень Л /, коректними виявляться тільки

N(e) = Ck„_e                                                        (4)

систем лінійних рівнянь. Для к = 8, п = 24 і е = 8 маємо N (8) = Cj86 = 12870, яку множимо на кількість суматорів-мультиплікаторів:

Л / (8)-С (8) = 12870-72 = 926640. (5)

В цьому випадку величина (5) на кілька порядків менше величини (3).

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

0 (k) = N (k} c (k) або 0 (8) = 12 870 (8 +1) = 115 830. (6)

Далі, пристрій вибору коректного рішення порівнює обчислені значення всіх 0 (к) компонент Я (.) і приймає рішення: продовжити аналіз або вважати отримане значення Д (.) істинним.

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

У доповіді наводиться процедура (послідовно-) паралельного пошуку справжніх рішень

серед Ck„_t можливих. Така процедура може

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

III. Висновок

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

III. Список літератури

декодування матроідного коду, що виправляє пакети помилок. Матеріали Міжнародної Кримської конференції «СВЧ-техніка і телекомунікаційні технології», Севастополь, вересень 8-12, 2003 р.

[1] Бодян Г. К., БодянД. Г., чорніли Д. П. Кодування і

MATROID CODES DECODING

Bodyan Gh. С., Bodyan D. Gh., Dunai L. T.

Technical University of Moldova TUM, 168, St. cel Mare, Kishinau- MD2012, R. Moldova phone: (37322) 237505 e-mail: gbodean@mail.md

Abstract -Algorithm of matroid (M-) code decoding is described. The complexity of decoding procedure is analyzed. An optimal decoding algorithm is proposed.

I.  Introduction

In [1] was described the matroid code encoding. In this work the M-code decoding is analyzed. Length n of matroid codeword v (x) is equal to n = 2t + k, where t is the number of erroneous symbols, к – number of original symbols. For example, if k=8 and f=8 then /7=24. To find the original codeword a(x) is

need to solve up to f *] = C * systems of до linear equations (for

W

above example, C*4 = 735471 ). In this work the main diagram

of matroid code decoding is described and theoretically analyzed. Important results for practice are obtained.

II.  Main part

M-codes are linear codes. Matroid code encoding and decoding diagram are shown in Figure 1. Encoder performs matrix multiplication (1), where U is the uniform matroid matrix. The System Solver gets the transmitted vector v ‘(x), that can contain errors. System-Solver solves a system of linear equations for до selected components of v ‘(x). A solution a (x) comes on out as a result. This solution is encoded and vector v(x) is compared with received vector v’(x). If v(x) = v'(x) then a(x) is accepted as original sequence a(x). Otherwise the Restore- block tries to find the correct solution. For this is need to solve

N = Ckn systems of linear equations. Among N solutions can be erroneous and correct solutions. As n grows N becomes unacceptable for engineers. In fact, the complexity of the one block of linear transformation that performs calculus of the one components a(.) of vector a(x) is equal (2) and the complexity of the hole solver is equal to C(k)= /f2(multipliers)+/((adders). The complexity of all decoder’s solvers is given by (3).

From the other hand, if received vector v’(x) has an e-uple error, then Restore-block must select only N(e) correct solutions

(4)    . In this case, complexity of the value A/(e)-C(e) is still big; see, for example, (5). Further decreasing of the solver complexity can be provided by cutting obtained solution, namely, by analyzing only solution for one component a(.} of a(x) . The complexity of solver, in this case, is given by (6).

Generally, next affirmation can be made: is needed and sufficient to find Ckn_t identical solutions to restore original data.

The described M-code decoding procedure was implemented in a demo-software that allows visualization of the encoding and decoding noises pictures.

III.  Conclusion

In conclusion, an efficient algorithm of matroid code decoding was proposed. This algorithm allows implementing of the M- code decoder with minimal hardware overhead.

Джерело: Матеріали Міжнародної Кримської конференції «СВЧ-техніка і телекомунікаційні технології»