ДЕКОДИРОВАНИЕ МАТРОИДНЫХ КОДОВ

May 14, 2012 by admin Комментировать »

Бодян Г. К., Бодян Д. Г., Дунай Л. Ф. Технический университет Молдовы ТУМ Шт. чел Маре, 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, а сложность всех решателей систем линейных уравнений декодера составит величину:

N-C(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)= 12870 (8+1)= 115830. (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.

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

Оставить комментарий

микросхемы мощности Устройство импульсов питания пример приемника провода витков генератора выходе напряжение напряжения нагрузки радоэлектроника работы сигнал сигнала сигналов управления сопротивление усилитель усилителя усиления устройства схема теория транзистора транзисторов частоты