Page 47 - ISCI’2017

To aspire n → ∞, then we obtain the asymptotic Gilbert–Varshamov bound:

R ≤1 − H q ( ) δ , (2)

 q −1 
where Hq(x) is q-ary entropy function on the interval 0 ,  , at that

 q 
−
q 1
H ( ) x = x log (q − ) 1 − x log (x ) − 1 ( − ) x log 1 ( − ) x , 0 < x ≤ .
q
q
q
q
q
Thus, error-correcting coding problem consists of searching of regular algorithms for a building
of the linear (n, k, d)-block codes, the parameters of which are satisfy to the code boundary (1) or/and
the asymptotic code boundaries of which are satisfy to expression (2).

Linear code Vk (as the linear subspace into Vn) defines by a set of basis (linearly independent)

vectors
(g 0 , 0 , g 1 , 0 ,..., g , 0 −n 1 ) ,

(g 0 , 1 , g 1 , 1 ,..., g , 1 − 1 ),
n
…
(g k − 0 , 1 , g k − 1 , 1 ,..., g k − , 1 −n 1 ),

which are usually presenting in a matrix kind via generating matrix

 g g ... g 
 0 , 0 1 , 0 , 0 n −1 

G =   g 0 , 1 g 1 , 1 ... g , 1 n −1  ,

 ... ... ... ... 
 g g ... g 
 k − 0 , 1 k − 1 ,1 k − , 1 n −1 
of the rank rank (G) = k and a dimensionality k × n.

Random code word c = (c0, c1, …, cn-1) of code Vk is a linear combination of rows from the matrix

G. The encoding consists in a comparing of each information word i = (i0, i1, …, in-1) with the symbols

from the field GF(q) to some code word (c0, c1, …, cn-1). The simplest method of coding given by the
expression

c = iG . (3)

Matrix G conveniently reduced to canonical form by linear operations on the rows

 1 0 ... 0 g * g * ... g * 
 * k , 0 * , 0 k+1 * , 0 n−1 
G =  0 1 ... 0 g k , 1 g , 1 k+1 ... g , 1 n−1  = I P , (4)
*


 ... ... ... ... ... ... ... ... 
 0 0 ... 1 g * g * ... g * 
 k−1 k , k− ,1 k+1 k− ,1 n 
−1
47