Page 49 - ISCI’2017

Single vector-columns in the matrices G* and H* can be selected optionally with the relevant

formation of the single submatrices and systematic placement of information symbols in the code
word.

The main aim of the redundant information coding is an error control (detection and correction),
which occurred when transmitting a message over a channel with noises [38-40]. For the error control,

encoder introduces a redundancy (a parity part of a long r = n – k) into the transmitted data. On the
receiving side, analyzing the properties of parity part and its compliance with the transmitted data,

the decoder reduces an influence of errors occurring during transmission.

Let us denote the error vector, which acting on the transmitted code word c, as n-sequence e = (e0,
*
e1, …, en-1) with the elements from the field GF(q). Distorted code word denoted by the vector c = c
+ e = (c0 + e0, c1 + e1, …, cn-1 + en-1).
Syndrome in the coding theory called the vector s = (s0, s1, …, sn-k-1) with the elements from the

field GF(q), which characterized by impact of the error vector to random code word:

T
T
T
T
s = * H = cH + eH = eH , (7)
c
i.e. a volume of the vector s depends only on the error vector e = (e0, e1, …, en-1) and independent on
the selected code word c = (c0, c1, …, cn-1).
Thus, decoding process consists of the syndrome analysis: at s = 0 will made a decision about the
absence of errors; but at s ≠ 0 will made a decision about a distortion of the code word by non-zero

error vector. Further actions depend on the adopted strategy: in the error detection systems with recall,
a request for retransmission of the code word is currying out; a vector e = (e0, e1, …, en-1) search is

performing in systems with forward error correction by the calculated volume s ≠ 0.

It should be noted that for large n and k, the vector e search task by the non-zero syndrome s for
random selected linear code Vk in the space Vn is extremely complex mathematical problem. In

general, this problem belongs to the class of NP-complex problems [37]. However, for the algebraic

codes with the specific structure of the matrices G and H, encoding (a problem of error vector e search
and/or a recovery of the faultless code word c) is polynomial solvable problem.

Algebraic coding based on using of the special algebraic equations, which allow to unambiguously
present information and code words, error vectors and syndromes and to reduce decoding problem to

a solution of linear equations system. Really, each vector from space Vn can be presented by a
polynomial from a formal variable x of a degree not above n – 1. At the same, vector elements are

identified with the polynomial coefficients, and the set of polynomials has the structure of a vector

space, which identical to the structure of space Vn, as well as the structure of the ring of polynomials
n
in modulus binomial x – 1. We consider the following polynomials:
- informational polynomial (xi ) = xi 0 0 + xi 1 1 + ...+ i k − 1 x k − 1 (corresponds to the vector i);

49