# КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ МАТРОИДНОГО КОДА, ИСПРАВЛЯЮЩЕГО ПАКЕТЫ ОШИБОК

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

Аннотация Определены функции кодера и декодера матроидного кода. Разработана методика оптимизации вычислений и распознавания ошибки, рассмотрены особенности кодирования и декодирования матроидного кода.

I.   Введение

Матрица (1) является конструктивной основой для построения кодера М-кода над GF3(24). Имеем: ИЛИ

Fig. 2. Diagram of sequential-concurrent M-code decoding

Bodean Gh. C., Bodean D. Gh., Chernelev D. P.

Technical University of Moldova

St. cel Mare, 168, KishinauMD2012, R. Moldova phone: (3732) 237505 e-mail: gbodean&.mail.md

Puc. 2. Диаграмма последовательнопараллельного декодирования М-кода

Abstract Encoder and decoder algorithms of the matroid code are defined. The methods of calculus optimization and error recognition are elaborated. The features of the matroid code encoding/decoding are analyzed.

I.   Introduction

Matroid codes were in , where a stochastic method of construction of the important variety of such codes matrands. are considered. Also, it was shown that applications of matroid coding allows reaching the theoretical boundary of effective restoring of the lost data asymptotically. Present work deals with the tasks of encoder/decoder elaboration for the matroid (M-) code in its “pure” form.

II.   Main part

The functioning of M-code encoder (or M-coder) is defined by v= x • A: the source codeword x of length k is applied to encoder; M-coder performs a matrix multiplication x by A over extended Galois field GF*(2m); the output is a vector v of length /7=2k Vectors x and v consist of symbols that contain m bits and kx-n matrix A represents a corresponding uniform matroid Uj,of rank k.

For k=3 and m=4 a M-coding example is analyzed. Table 1 defines the multiplication modulo p(x), where p(x) is a field generator polynomial over GF(2) and the polynomials over GF(24) are shown in the decimal format. The sum mod p(x) is performed as XOR bit-by-bit operation.

Matrix A given by (1) defines a uniform matroid generated by a polynomial g(x) over GF3(24). In this case the algorithm of functioning of M-coder will be defined by system (2). Fig. 1 shows the block diagram of such M-coder. The edges on Fig. 1 are marked by the multiplication coefficient, i.e. elements of the field GF(24). A method of optimal multiplication implementation was elaborated. As a result the multiplication scheme consists of some XOR gates. For the example above the multiplication of the vector’s x component x=(xb x2, x3t x4) by 2 mod p(x) will be performed as follows: xi<-x4, x2<-x^ XOR x4, x3<-x2, x4<-x3.

The aim of M-code decoding is error recognition and original data restoration. A sequential-concurrent decoding algorithm is proposed (see Fig. 2). The basis of the scheme on Fig.

2   is the corresponding Boolean lattice. Such a way of error recognition scheme allows performing all operations in an asynchronous mode. Each edge in Fig. 2 means a transition if an error was found. From diagram in Fig. 2 results that single errors are most difficult to detect (see interrupted edges).

III.   Conclusion

Efficient schemes of the matroid code encoding/decoding are proposed and analyzed in this paper. Encoding and decoding are asynchronously performed in real time.

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