ОБ ОДНОМ МЕТОДЕ ПОМЕХОЗАЩИЩЕННОГО КОДИРОВАНИЯ

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

Бодян Г. К. Технический Университет Молдовы Шт. чел Маре, 168, Кишинев MD2012, Молдова Тел.: (3732)237505; e-mail: gbodean@mail.md

Аннотация Матроидный (М-) код новый класс (линейных) корректирующих кодов, который способен восстановить исходные данные при потере (искажении) до половины переданных символов. Построение М-кода относится к задачам полиномиальной сложности. Предложен метод построения М-кода, основанный на поиске однородных (U-) матроидов среди циклоклассов сопряженных элементов векторного пространства над расширенным полем Галуа. Установлены границы существования U-матроидов.

I.  Введение

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

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

Корректирующая способность (эффективность) р кодов определяется числом исправленных ошибочных символов. Для линейных блоковых кодов установлен теоретический предел эффективности [1]: р<(п-к)/2, где п длина вектора, к количество информационных символов (в слове).

В данной работе представлен метод помехоустойчивого кодирования с р<1/2. Метод, названный матроидное кодирование (или М-код), предусматривает линейное преобразование исходных символов, формирование выходного вектора, анализ полученного кода, распознавание ошибки и восстановление (если это возможно) исходных данных.

II.  Основная часть

Для характеризации матроида воспользуемся понятием F-представимости [2]. Пусть S={1,2,…,n}, \/=Fkнабор векторов-солбцов длины к над полем F. Определим отображение cp:S->\/, которое можно представить матрицей А размерности кхп, при этом столбцы матрицы А есть ср(1),…, ср(л). Говорят, что матроид М от S представим над полем F (или Fпредставим), если отображение ср сохраняет ранг.

С точки зрения помехозащищенного кодирования представляет интерес F-представимость максимального ранга, т.е. случай однородного (U-) матроида ранга к. Причем представление U-матроидов должно быть реализовано над расширенным полем многочленов GFk(2m), где к размерность поля, 2т характеристика поля, т разрядность символов. Тогда матрица А будет определять линейное преобразование вида

где х= <*1, …, хк> вектор исходных символов, v=<vi,…,v„> результирующее кодовое слово, А= [ау], «уеGF(2m), /=1,…,/с;У= 1 ,…,л.

В случае U-представимости преобразование (1) задает систему линейных уравнений, в которой любая подсистема из к уравнений образует линейнонезависимый базис.

Теперь возникает вопрос: каково должно быть соотношение между йл? Очевидно, что для восстановления всех к информационных символов необходимо иметь, по крайней мере, еще к дополнительных базисных уравнений.

Таким образом, задача построения М-кода сводится к поиску однородного матроида U* над полем GFk(2m). Приведем пример. Пусть к=2 и /77=2. Нетрудно показать, что матрица

представляет однородный матроид, т.е. любое подмножество ранга 2 матрицы (2) есть базис в векторном пространстве над GF2(2 ). Это означает, что в системе уравнений

все подсистемы ранга 2 являются линейнонезависимыми. В общем случае, для заданного матроида и* могут бытьсистем линейнонезависимых уравнений (ПЗУ). Все операции в (3) выполняются по модулю д(х)а, элементы расширенного поля GF(2m) с характеристическим полиномомДля

приведенного примера характеристическим является полином р{х)= 1+х+-х2, а д(х), называемый генератором поля (или кода), выбирают среди неприводимых

(примитивных) полиномов вида

Величина к является важной характеристикой матроидного кода. Она определяет его эффективность (корректирующую способность) р. Код, сгенерированный системой (3), способен восстановить до 2 ошибочных символов. Для этого (декодером) применяется одна из с 4 = 6 подсистем ПЗУ.

Другой оценкой корректирующего кода является скорость передачи информации R, определяемая отношением kJn, которая для М-кода постоянна и равна /4. Следует отметить, что для кодов, корректирующих пакеты ошибок, характерны меньшие значения, как для корректирующей способности р, так и для скорости передачи R [1, 3].

Одна из основных проблем построения матроидного кода является поиск однородных матроидов U* над GFk(2m). Действительно, для нахождения LJматроидов ранга к потребуется, в общем, перебрать

С(к,т)=С^пк комбинаций векторов. Например,

для фиксированного т=4 имеем следующие значения переборной сложности: С(2, 4)« 1.75108, С(3, 4)« 6.5351018 и С(4, 4)« 8.436-1033. Для практически важных случаев, т.е. больших т и к, поиск однородных матроидов переборным методом становится нецелесообразным (из-за полиномиальной сложности задачи поиска)!

Один из подходов уменьшения "переборной сложности” использование технологии жадных алгоритмов. Применительно к задаче поиска Uматроида “жадность” будет проявляться в (локальном) поиске нормальных базисов ограниченной длины [4]. Распространим понятие нормального базиса на поле многочленов GFk(2m) и назовем такой базис расширенным. Расширенный нормальный базис (РНБ) имеет вил:

где у порождающий (примитивный) элемент поля GFk(2m). Тогда задача поиска однородного матроида сводится к задаче поиска РНБ, сложность которой определяется мощностью семейства цикпоклассов вида (4).

В нижеприведенной таблице представлены значения числа циклокпассов для тех случаев, когда в соответствующем векторном пространстве над GFk(2m) существует РНБ. Символ 0 указывает на отсутствие РНБ, а символом V отмечены случаи наличия РНБ в ограниченном диапазоне циклокпассов (из-за нехватки ресурсов ЭВМ).

Число циклоклассов и границы существования однородных матроидов над GFk(2m)

Numbers of cycloclasses and the bounds of uniform matroids over GFk(2m)

2

3

4

5

6

7

2

4

27

104

426

1709

6835

3

12

170

1235

10099

80941

646410

4

0

0

15725

258281

4146454

66199674

5

0

0

0

6908009

222056530

V

6

0

0

0

0

V

V

7

0

0

0

0

0

V

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

III.  Заключение

В работе представлен метод построения матроидного кода, позволяющий восстановить исходное сообщение при потере до половины переданной информации.

IV. Список литературы

[1]   Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.: Мир, 1976.

[2]  Айгнер М. Комбинаторная теория. М.: Мир, 1982.

[3]   MacWilliams F.J. and Sloane N.J.A. The Theory of Error Correcting Codes. North Holland, 1996.

[4]   Mymmep B.M. Основы помехоустойчивой телепередачи информации. Л.: Энергоатомиздат, 1990.

A TECHNIQUE OF ERROR-CORRECTING CODING

Bodean G. C.

Moldova Technical University 168 St. cel Mare, Chi§inau, Moldova, MD2012 phone (3732) 237505 e-mail: gbodean@mail.md

Abstract The matroid (M-) code is a new type of errorcorrecting codes capable of restoring the original data despite half of the transmitted symbols being lost or distorted. M-coding is a complicated problem. A technique is suggested based on searching for uniform (U-) matroids among cycloclasses of the vector space transforms over the extended Galois field. The bounds of the U-matroid existence have been established.

I.  Introduction

Error-correcting coding is widely used to restore the damaged data. For this purpose data streams are broken into series of codewords which consist of data and check symbols. Each symbol is a sequence of m bits. The efficiency (correcting capability) p of an error-correcting code (ECC) is determined by the number of erroneous symbols that have been corrected. An important division of ECCs are block codes. The efficiency of a linear block code has the following theoretical limits [1]: p<(nk)!2, where n is the codeword length and k is the number of information symbols.

The present paper deals with the development of a new ECC technique with p<%. This technique, called matroid or Mcoding, is based on a linear transformation of the original symbols, output vector generation, analysis of the codewords obtained, error recognition and restoration of the original data.

II.  Main part

A notion of F-representability is used to define matroids [2]. For the ECC purposes, the F-representability of the maximal rank is of prime interest, i. e. the case of a k-rank uniform (U-) matroid. U-matroids should be represented over the extended Galois field GF*(2m), in which case the matrix A would define the linear transformation (1) with the original codeword x and the output vector v.

The expression (1) defines a system of linear equations where any subsystem of k equations is a linear-independent basis. The number n of equations in (1) is taken as equal to double k, i. e. n=2k, in order to achieve a maximum efficiency of p=1 /2.

Hence the tasks of M-coding are reduced to searching for a uniform matroid \J(k,2k) or Uk over GFk(2m). As an example of the obtained U2 matroid see (2) and (3) where the operations are performed modulo polynomial p(x) over GF(2) and the vectors are generated by polynomials g(x) over GF(2m). The combination of

Ck2k linear-independent subsystems (LIS) generally has a Uk

matroid. The value k defines the matroid code efficiency. Another important ECC feature is the rate R which has a constant value and for the M-code equals %. The known duster-correcting codes have smaller values of p and R [1, 3]; however, such performance is difficult to achieve. This is because the search for a Uk-matroid is a complicated task, i. e. it is NP-complete.

The technology of greedy algorithms should provide a way to decrease the enumerative complexity. The uniform matroids should be found among the cycloclasses of the length n. These cycloclasses are defined by (4), in which case the searching complexity is reduced drastically compared to enumeration procedures. The table above shows the cydoclass values for the vector spaces where uniform matroids are found; the symbol 0 denotes the absence of U-matroids, and the symbol V denotes occurrences of such matroids within a restricted range of cycloclasses (due to insufficient computer resources).

III.  Conclusion

A technique for the matroid coding allowing for the restoration of original message even with up to half of the transmitted data being lost is described and analyzed in this work.

Аннотация Представлены результаты исследования метода многоканальной демодуляции. Приведены результаты экспериментальных исследований итерационного многоканального демодулятора.

I.  Введение

Мобильные системы третьего поколения базируются на принципах кодового разделения каналов. Однако теоретические приделы скорости передачи данных (до 2 Мбит/с) и высокую эффективность использования радиочастотного ресурса при использовании традиционного метода демодуляции достигнуть невозможно.

Одним из наиболее перспективных методов повышения пропускной способности мобильных систем третьего поколения является многоканальная демодуляция [1, 2]. Исследованиям этого перспективного метода посвящена эта статья.

II.  Теория

Все работающие мобильные станции излучают сигналы, которые на вход базовой станции приходят как суммарный асинхронный сигнал y(t), поскольку расстояние «мобильная станция база» для каждого абонента различно и сигналы его проходят за разное время. Поэтому на входе базовой станции получаем [2]:

где Sk(t) расширяющий кодовый сигнал, соответствующий k-му абоненту системы, 9k(t) = +l, к=1 …К двоичный информационный символ, соответствующий к-му абоненту, К число активных абонентов в соте, тк временная задержка сигнала к-го абонента.

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

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

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

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