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

Анотація – Отримано аналітичні вирази для розрахунку характеристик матроідних кодів та визначено межі їх існування.

I. Вступ

В роботі [1] запропоновано підхід до побудови нового класу лінійних кодів, названий матроідное кодування. Матроідние коди дозволили розсунути межі існування лінійних кодів. Так, в

[2] на стор.72 представлений список кодів Хеммінга з параметрами (л, к), а в коментарі до нього наводиться сумнів з приводу існування лінійних кодів заданої коректує здібності t в розширеному поле Галуа GFk(2m), Де до – розмірність поля або число ступенів свободи (фактично число оригінальних, вихідних символів), 2т – Характеристика поля, т – розрядність символу.

Матроідний код, заданий матрицею U (2,4,2), дозволяє виявити і скоригувати одиночну помилку, тобто t = 1. Під помилкою розуміється символ відмітний від переданого.

Узагальнений аналіз коригувальної здатності М-коду показав, що між характеристиками л, к і t існує наступна залежність:

л = 2t + к або л = 2t + до + 1, (2)

причому t, для фіксованого к, є функція від т.

Для пошуку однорідних матроідов в поле Галуа GFk(2m) Була розроблена спеціалізована програма, написана на мові Delphi. На малюнку 1 представлений інтерфейс цієї програми. Результати пошуку однорідних матроідов, за допомогою розробленої програми, представлені в таблиці 3. Символом V відзначений факт наявності соответствующе-

Кодові слова (вектора) лінійного блокового коду мають чітко виділену інформаційну і контрольну частини. Відмітна особливість слів матроідного коду – відсутність такого поділу. В цьому випадку, будь підмножина з к символів переданого слова довжини л (п> к) може бути використано декодером для відновлення вихідної послідовності.

У даній роботі представлені нові результати з дослідження характеристик матроідних (М-) кодів, а саме, визначено залежність довжини коду л від характеристик t і к, встановлені (нижня і верхня) межі існування М-кодів над полем GP (2m) Для фіксованих значень t і до, наведено приклади матроідов для різних характеристик, в тому числі, важливого для практики випадку, / 77 = 8.

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

Нагадаємо, що для побудови М-кодів використовується однорідний матроід, який являє собою сімейство лінійно незалежних підмножин однакового рангу к. Приклад такого матроіда, побудованого над полем GF2(22) З породжує поліномом р (х) = 1 + х + х2, Є матриця виду IЦк, п, / 77):

Кодові слова v (x) формуються шляхом множення вихідного вектора а (х) на матрицю Щк, п, т), тобто v = a U. Враховуючи, що операції множення і складання виконуються по модулю р (х) – див таблицю 1, отримуємо список векторів, представлений в таблиці 2. Символи таблиць 1 і 2 мають одну і ту ж розрядність / 77, рівну 2.

Puc. 1. Інтерфейсна частина програми пошуку однорідних матроідов.

Fig. 1. Interface of the matroid searching software

Цікаво зауважити, що кількість нулів і одиниць в слові v (x), крім першого і останнього (див. таблицю

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

Таблиця 1. Table 1.

+

0

1

2

3

0

0

1

2

3

1

1

0

3

2

2

2

3

0

1

3

3

2

1

0

0

1

2

3

0

0

0

0

0

1

0

1

2

3

2

0

2

3

1

3

0

3

1

2

Таблиця 2. Table 2.

a(x)

v(x)

00

0000

01

0312

02

0123

03

0231

10

1111

11

1203

12

1032

13

1320

20

2222

21

3130

22

2301

23

2031

31

3021

32

3210

33

3102

30

3333

го однорідного матроіда, а символом 0 – відсутність такого.

CORRECTING ABILITY AND BOUNDS OF MATROID CODES

Таблиця 3.

т

до

2

3

4

5

6

7

8

2

V

V

V

V

V

V

V

3

V

V

V

V

V

V

V

4

0

V

V

V

V

V

V

5

0

V

V

V

V

V

V

6

0

V

V

V

V

V

V

7

0

V

V

V

V

V

V

8

0

0

V

V

V

V

V

Залежність t від m, наприклад для k = 2, представлена ​​(частково) в таблиці 4.

Таблиця 4.

т

2

3

3

4

4

4

4

5

5

6

6

t

1

2

3

4

5

6

7

8

15

16

31

п

4

6

8

10

12

14

16

18

32

34

64

Дані таблиці 4 необхідно інтерпретувати наступним чином: для забезпечення більшої коректує здібності t необхідно переходити до полів більш високого ступеня т.

Верхня межа існування матроідов U (к, т, п) для фіксованого до визначається періодом Ейлера над розширеним полем Галуа GFk(2m)\

Гоаніци існування М-кодів над GFk(2m) Bounds of matroid codes over GFk(2m)

Наприклад, ср (/ < = 2, т = 4) = 17.

Серед такого розмаїття матроідних кодів вибір залишається за розробником. В якості міри ефективності коду може бути використана величина R = k / n – швидкість коду [3]. При фіксованому t із зростанням до збільшується і значення швидкості R. Очевидно, що при однаковій швидкості R слід віддавати перевагу кодами з більшою коректує здатністю t. У таблиці 5 наведені характеристики матроідних кодів з однаковою швидкістю Я? = 1/3.

Таблиця 5.

к, t

2

3

4

5

6

7

8

п

6

9

12

15

18

21

24

III. Висновок

Таким чином, отримані характеристики матроідних кодів, досліджено межі їх існування, розроблено програмне забезпечення для пошуку М-кодів.

Bodyan Gh. С.

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

Abstract -Analytical expressions to estimate the matroid codes parameters are obtained and bounds of matroid codes existence are found.

I. Introduction

Proposed in [1] was the technique to construct the new class of linear codes, named matroid coding. Matroid codes allow enlarging the bounds of linear codes. So, in [2] on page 72, the list of Hamming codes with parameters (n, k) are presented. Comments to this list doubts the existence of linear codes with the correcting capability (ability) over Galois field extension GF*(2m), Where до is degree of field, i.e. number of original symbols, 2m – characteristics of field, m – bit codeword size.

Linear block codewords consist of information and control parts. Absences of such sharing (division) are distinctive particularities of matroid codes. In this case, any /(symbols from n of the received codeword can be used to restore the original sequence.

New results about matroid (M-)codes parameters are presented in this work. Were established the dependences of the codeword length n from parameters t and k. Low and upper bounds of M-code existences over field GF*(2m) For t and до fixed are found.

II. Main part

Uniform matroid U(k,n) is used to generate M-codes. Example of such matroid over GF2(22) with p(x)=1+x+x2 is given in

(1)    .       Codewords v(x) obtained by multiplication of the original vector a(x) on matrix U(k,n,m) are given in Table 2. The resulted codewords have correcting ability M. Error is a codeword symbol that differs from the transmitted one.

Dependences for M-code parameters n, до and t are given in

(2)   ,        where f=f(/n) for k= fix. Software was elaborated for matroid codes searching. The interface of this software is presented in Figure 1. Results of matroid codes searching are given in Table

3,    where symbol V means the existence of uniform matroid, 0 – absences of such matroid. The dependences t=f(m) for k=2 is given in Table 4. In this case the upper bound of matroids existences is given by Euler period (3).

The rate R=kln is other parameter of error controlling code. For R= 1/3 the parameters of matroid code are given in Table 5. Selection of needed matroid code is up to the code designer.

III. Conclusion

In conclusion, parameters of matroid codes are found, bound of M-codes existences are analyzed, software to search the matroid codes was elaborated.

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

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

[2] Блейхут Р. Теорія і практика кодів, контролюючих помилки. – М.: Мир, 1986.

[3] Кларк Дж., мл., Кейн Дж. Кодування з виправленням помилок в системах цифрового зв’язку: Пер. з англ. – М.: Радіо і зв’язок, 1987.

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