Page 60 - ISCI’2017

Among universal decoding methods of the linear block codes, which specified by random

generating matrix, special place is occupied the permutation algorithms [38-40]. The main idea of
this decoding is using of different sets of the information multiplicities. Let the generating matrix (19)

represents as canonical kind (4). Single vector-columns in the expression (4) can be selected randomly
with a corresponding formation of single submatrices and systematic placement of k symbols of the

information set. The last (n – k) symbols uniquely calculated by the elements of the information set.
Positions of these (n – k) symbols set of a placement for single vector-columns corresponding to the

*
validation matrix H (6). If will select a placement (n – k) single vector-columns in the expression (6)
such that they covered all t positions non-zero elements of the error vector e, then the code word
calculating by k symbols of the information set, does not consists errors, i.e. the word (19) can be

decoded even without knowledge about special algebraic scheme of the generating (validation) matrix
of used algebraic code.

Thus, particular combination of errors will be corrected when implementing of resettable
decoding, only if the information set, which wholly contains this combination, can be founded. This

set, which is an errors roofing combination, and a validation set, which cover all sets of this type of

error, is called a coating [38]. Decoding task is a task of searching of the validation set, which cover
unknown errors combination. Let us consider boundaries for the number of sets of roofing. Assume

that by means of (n, k, d)-code, all combinations from t or a smaller number errors can be corrected.

Let us consider a combination only from t multiple errors, because all errors of smaller multiplicity
! n
t
will be covered. Common number of errors in all n positions is equal to С = t ( ! n − t )! . Because a
n
volume of the roofing set is equal to (n – k), then the max number of error combinations, which can

(n − k )!
be covered by this set, is equal toС t = . The lowest number of sets, which cam correct
n− k t ( ! n − k − t )!

all combinations from t errors, is limited by the following expression [38]:

! n
C t t ( ! n − t )! n ( ! n − k t − )!
N ≥ n = = . (20)
C n− k (n − k )! (n − t )! (n − k )!
t
t ( ! n − k t − )!
Dependences of the lowest number of roofing sets, which is needed for a correction of all

combinations from t errors of random linear block code, is shown in Fig. 1. Estimations N is presented

by logarithmic scale depending on the relative speed encoding R = k / n and its calculated for
parameters of the separable the binary Goppa codes: n = 2 , k ≥ n – mr, r = deg G(x), d ≥ 2r + 1.
m

60