Page 46 - ISCI’2017

1 General provisions of the algebraic theory of block codes used to describe the theoretical

and code schemes

Let us introduce new terms and definitions of the algebraic coding theory [38-40] used in further at a
consideration of the asymmetric code cryptosystems (theoretical-code schemes), includes the

algorithms of formation and checking of the electronic digital signature (EDS).
Will fix the finite field GF(q) and will consider a vector space Vn as a set n-sequences with

elements from GF(q) with a component wise addition and multiplication to a scalar.

Linear (n, k, d)-code Vk over the field GF(q) is a subspace into Vn, i.e. non-empty set of n-sequences
(code words) with elements from GF(q), where k is a dimension of the linear space, d is the minimal

Hamming weight (number of nonzero elements) wh(c) of a random non-zero code word c of the code
Vk:

d = min w (c ) .
∀ c∈ V k ,c≠ 0 h
Based on a linearity of subspace Vk a set of weights of different non-zero code words matches with
a set of Hamming distances among different code words, i.e. a value d also calls the minimal

Hamming code distances of the code Vk. The value R = k / n calls the relative code rate, and the value

δ = d / n calls the relative minimal code distance.
The main problem of the redundant coding theory has been formulated firstly in K. Shannon’s

publication [41]: will find codes with the with a high relative rate R and with a high minimal distance
d. This problem follows from the follow theorem.

Theorem 1 [41]. Let С(P0) is a bandwidth of the discrete symmetric channel with the error

probability P0. Then for any ε > 0, if R < С(P0) and n is sufficiently large, (n, k, d)-code exists with

relative rate k / n ≥ R, the error probability of which is equal to Perror < ε.
This theorem is proved by the probabilistic methods and doesn’t give to us any mechanism to

building of codes with the high R and δ. The following evaluation (the Gilbert–Varshamov bound) is

valid for linear block codes.
Theorem 2 [40]. If the following equality is performed

d −2
)
i
q n −k ≥ ∑ C n i −1 ( −1 , (1)
q
i =0
then the linear (n, k, d)-code on the field GF(q) exists.
In practice, the asymptotic boundaries often use that give a representation about the limited code
characteristics at the indefinitely high code length. Logarithm of the expression (1), then we obtain

−2

d
i
n − k ≥ log q   ∑ C i n −1 ( −1q )  .
 =0i 
46