Бодян Г. К. Технічний Університет Молдови Шт. чел Маре, 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 = результуюче кодове слово, А = [ау], «уе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р.