1. Introduction
Let 
be a Galua field of two elements and 
be a linear vector space on that field. We consider the family of the subsets, 
, satisfying the following conditions for all
:
1) 
2)
(1)
3) 
4) 
(summation is with respect to
).
The first three properties are usual for partition of the subset, 
, and the last “non-zero” one reflects the specificity of the further usage for constructing of the correcting codes.
The case,
(2)
is particularly important, because it leads to constructing of the perfect codes.
Below, the term, partition of the set, 
, is used in the sense of (1), i.e. it is the partition into “zero” subsets.
The problems of existence, constructing and partition of 
for the given 
and п have not only combinatorial-set interest, but also that in connection with correcting code construction. It is worthy to note that in correcting code theory the decoding regions form partitions of the space, 
, if decoding region pairs do not overlap each other. Consequently, some code classes—particularly, the perfect codes in the additive channel—make it possible to construct the partitions,
. Below, in the examples with 
we leave out the subset, 
, which is the zero vector,
.
Example 1. 
is the partition of
, if:
Example 2. 
is the partition of the space, 
, if:
Example 3. 
is the partition of the space, 
, if:
It is seen from the above examples that the space, 
, can be partitioned in many ways with respect both to the number and the power of the subsets.
From the partition, 
, of the set, 
, one can obtain the partition, 
, taking the subset,
, away from
.
We present (without proof) the following lemma that describes some trivial properties of the partition,
.
Lemma 1. For every 
the following takes place:
a)
;
b)
;
c)
;
d)
.
If 
for
, we will take 
Then we consider the partitions, 
, taking into account that the necessary condition of their existence is the evenness of the number, 
, if 
is odd.
The following construct of the direct product allows building new partitions out of the given ones:
Lemma 2. If 
and 
are the partitions of the sets, 
and
, respectively, then there are 
partitions of the subset,
.
Proof.
Let:
where:
Let us represent the direct product-set, 
, in the form of the matrix:
(3)
For every pair,
. We define the sets, 
, in the following way:
a) For every 
the set, 
, contains only one element of any line and any column of matrix (3), and it satisfies the following condition: no pair of all the sets, 
, is overlapped and every one of these sets has the power, s; that is:
b) 
c) 
Let us consider the set:
From definition of 
and if
and those of
if 
we have:
(summation is with respect to
)and as:
Then 
is a partition of the space,
.
Theorem 1. If 
is a divisor of
, and 
is a divisor of 
for any positive integer, 
, then
and 
are partitions of the space,
.
Proof. It follows from the theorem’s condition that
. Let us apply induction method with respect to
.
For 
we present 
in the form,
, where
. Then we have the trivial partition, 
, of
.
Let us assume that for 
there is the partition, 
of the space,
.
Applying Lemma 2 with respect to the partition,
, of Br and 
of
, we obtain the partition, 
, for
. Consequently, there exists the partition,
of
, where
.
We consider 
where
, and 
is defined in the following way:
It is easy to prove that 
satisfies conditions (1) and (2) and, consequently is a partition of
.
Q.E.D.
Now we prove the existence of the partition, 
where
.
The statement holds true for
. Let us assume that the statement holds true for all 
as well, and prove it for
.
We present
, where
As 
is an integer, and
, then
is an integer. Consequently, 
also is an integer. As
, according to the assumption, there exists the following partition of the space,
:
We consider
, where
As: 
and
, then it is enough to prove that
. We write:
That is, 
is a partition of
.
Q.E.D.
Now we are going to describe the construction of the group code set algorithm and that of the channel sets, using the partition of the set from the ND space into “zero” subsets. It is proved that any code of the constructed set corrects all errors of every additive channel in the set of the respective channels.
An additive channel is given by the set of vectors of errors,
; any vector, 
, at the exit of such a channel has the form:
, where 
is the initial vector, 
, and 
is the addition operation with respect to 
[3].
The neighbourhood of the order of 
of the vector, 
, with respect to 
is defined in the following form [4]:
As 
does not depend on
, we use the denotation: 
The code, V, corrects the errors of the additive channel, 
, if the following conditions are provided:
where 
Classical boundaries of Hamming and VarshamovGilbert for the power of the code, V, correcting the errors of the additive channel, A, have the following form [5]:
.
The main task for the given channel, 
, is the construction of the maximum volume code correcting the errors of the channel,
.
The code 
is called perfect for the additive channel, 
, if the following condition is satisfied:
(4)
The code, 
, is called quasi-perfect for the channel, 
, if for any оf
, the code, 
, is perfect for the channel,
.
In other words, the quasi-perfect code, 
, for the channel, 
, satisfies the conditions:
1) 
2)
, where
.
We denote by 
the group code, from
, of the order, 
, correcting all the errors of the additive channel,
.
We define the product of the Boolean matrix,
, or the dimension, 
, and the vector,
, in the following way:
where 
(summation is with respect to
).
Any (0,1) matrix, H, having the dimension, 
, is called checking for the code, 
, if for all code vectors and only for them the following equality takes place:
where all operations are carried out with respect to mod 2 ([6]).
To build the code, V, correcting the errors of the additive channel we use the following construct connected with the partitions presented above. First we build the additive channel, then the group code correcting the errors of that channel.
Let 
be the negative integers and there be the set, 
, where
.
We consider the matrices, 
, of the following form:
Here 
is the unit matrix of the order, 
, and 
is the logic negation of
.
We build the channel, 
, where
is composed of the vectors,
, where
, and is from all lines of the Boolean matrix given in the following way:
. (5)
Example 4. We build a channel for the case:
Using the definitions of the numbers, 
, and the vectors, 
, we obtain:
As
; then the channels, 
, have the following form:
NB 1. The block, 
, for constructing the channel is defined in two ways for all
; conesquently the set, 
, of such channels has the following power:
Let
It is obvious that 
and the above described channel, 
, has the power:
(6)
Let 
be one of the partitions described above. We transform the family, 
, in the following way: we take from each 
a vector, 
, and throw it away, keeping all other vectors in their former form. We denote the obtained family by
, where:
NB 2. The set, 
, depends on the choice of the vector, 
, from
, and the checking matrix,
defines the code,
one to one; consequently, the set of the codes,
has the power:
We consider the group code, 
from 
having the checking matrix, 
, 
, and the additive channel,
.
We prove that the group code, 
, having 
as its checking matrix corrects all errors of the channel, 
, i.e. 
To prove this it is enough to show that for any
, 
takes place:
.
Let
, where
for all
. It is easy to show that:
(7)
Hence, taking into account that
has the dimension:
, and the column numbers of the sub-matrix, 
, coincide with those of matrix (5), where the block, 
, is located, we obtain:
(8)
We have from the definition of the channel,
:
a) There exists an 
from
, such that for all 
the vector, 
, is zero;
b) There exists a 
from
, such that for all 
the vector, 
is zero.
Hence, we obtain, taking (8) into account, that there exists a pair, 
, for which:
(9)
It follows from the construction of the matrix, 
, that all the columns are different; consequently, for any vector, 
, the equality, 
, takes place if the 
-weight of the Hamming vector, 
, is more than two х. Therefore, we consider 
for which 
.
The following cases are possible:
a) The vectors, 
, are the lines of matrix (5). Then we obtain from (7):
Hence, taking (9) into account, we obtain that there exist such vectors, 
that:
We obtain, applying Lemma 1: 
i.e. 
b) Only one of the vectors, 
, is a column of matrix (5). Then we have from (7):
Hence, taking (9) into account, we obtain that there exist the vectors, 
such that:
Applying Lemma 1, we get: 
i.e. 
c) Both vectors are not the lines of matrix (5). Then we have from (7):
Taking (9) into account, we get that there exist such vectors,
тthat:
Again, applying Lemma 1, we get that for any vectors, 
, takes place:
, т.е.
.
consequently,
. As a result, we have that every code, 
, corrects the errors of any channel, 
, of the set,
. Furthermore, if 
is a partition of
, the following takes place:
. Hence we have, taking (6) into account, that the code, 
, satisfies the condition (4), that is, it is perfect. In result, we get the following statement.
Theorem 2. If 
then every group code, 
corrects all errors of any channel, 
i.e.
.
Corollary 1. If 
is a partition of
, then every group code,
, corrects the errors of any channel,
and it is perfect.
NB 3. If
, then the above described method of building of group codes is the Hamming method of group codes correcting the errors of the channel,
.
Let us choose 
in the above described algorithm of constructing the set of channels, taking into account the following condition:
We build the set of channels,
in the following way;
any channel, 
is composed of the vectors, 
where
being of all lines of the Boolean matrix given in the following way:
Here 
is a matrix of 
dimension, having the form:
It is obvious that the above described procedure of constructing uniquely defines the set, 
, of the nonzero channels for which: 
Consequently, the following holds true.
Corollary 2. If 
is a partition of the space, 
, then the perfect code, т
corrects the errors of the zero channel,
.
Corollary 3. The perfect code, 
, uniquely defines the partition:
of the space, 
, if 
is the zero channel.
Example 5. We consider the partition, 
where:
Choosing
, we get the checking matrix,
:
.
Consequently, the corresponding perfect code:
corrects the errors of the zero channel, 
, of the following form:
In result, we get the code,
. As all 
for 
are zero sets and they partition the
, we get the partition,
.
Now we can get the following perfect code and the partition from the above partition in a similar way.
Consequently, Corollaries 1 and 2 and 3 allow us to build the sequence of the partitions of the space and, the sequence of the perfect codes, as well.
Example 6. We have from Example 1 the partition, 
of the space,
.
Using this partition for
, we get the matrix, 
:
Which is the checking matrix of the perfect code, 
, where the channel, 
, has the form:
Example 7. We use the partition,
as in the preceding example and we build the 
for 
:
Then we build the matrix,
:
which is the checking matrix of the code, 
, where 
is one of the channels in the set,
. For instance:
Corollary 4. If 
is a partition of the space, 
, and for some integer, 
, takes place
then the group code with the checking matrix, 
is 1-quasi-perfect.
Example 8. We consider the partition, 
, of the space, 
of example 1.
For 
and 
we build
:
Then we build the matrix, 
Which is the checking matrix of the code, 
, where 
is one of the channels in the set,
. For instance:
Now we are going to consider the case, 
The interest in this case is due to the following circumstances. According to Theorem 1, existence of a partition in 
depends only on the parameters, n and s, and this simplifies the algorithm of both code and communication channel described in §2. Besides, in the case, 
, classification of building both codes and channels is simplified as well.
It follows from theorem 1 and theorem 2 (§1, §2) the following.
Theorem 3. If 
a divisor of
, and 
is a divisor of
, for any positive integer, 
, and if
, then there exist the perfect codes,
, for 
and for
where 
The proof is similar to the one for Theorem 2.
In the following two examples, we build two different channels and the codes corresponding to both, using the parameter,
.
Example 9. Using the partition, 
of the space, 
we have from example two:
For
, we get the checking matrix,
.
which is the checking matrix for the perfect code, 
, where the channel, 
, has the following form:
Example 10. Using the partition,
, of the space, B4, we build from example the 
for the set,
, and for the vectors,
Then we build the matrix,
:
which is the checking matrix for the perfect code,
.
We consider the channel,
:
At the end of the present paper we consider the group perfect codes built through the partition, 
, for
and correcting the errors of the channel,
, in the space,
.
Example 11. We consider the partition,
for 
and
. We take the case,
.
.
is the checking matrix of the group perfect code, 
, where 
has the following form:
Let us have a closer look at the group perfect code,
, where
, of course, for the case that the 
is a partition of the space,
. Then for
, the channel,
has the following form:
Taking this and Corollary 4 into account, we get:
The perfect code, 
is a quasi-perfect code in the additive channel:
2. Addenda Zero Matrices
In this addenda, we consider the connection between the zero sets and the deadlock tests [7]. For the further discussion, it is more convenient to consider the set of vectors as a matrix having those vectors as its lines of the given set.
Let 
be the space of the 
matrices on Galua field.
Definition. The matrix, 
, is called null-matrix if the sum of its lines is a zero vector. Moreover, the matrix, 
, is called regular if all its columns are different. It is obvious that the regular matrix corresponds to the subset of power, 
, in
.
Problem 1. Describe the set, 
, of regular matrices.
Problem 2. Find the number of the null-matrices.
Problem 3. Describe the partition of
, through the zero subsets.
Examples.
1) If
, then the 
is the regular nullmatrix.
2) If
, then there doesn’t exist a regular nullmatrix.
3) If
, then the following matrices are regular null-matrices:
where 
is any regular null-matrix of
.
4) If
, then:
or
where 
is any regular null-matrix
.
5) Let
, then the regular null-matrices are as follows:
and
where 
is an arbitrary null-matrix in
.
Now we consider the following set of matrices,
:
.
We introduce in 
partial order, requiring:
If the matrix 
can be obtained from
, taking away some set of columns.
Definition. The matrix, 
in the class, 
, is called extreme (or deadlock) if for 
it follows that
.
Examples.
6) We describe all extreme matrices in
:
Definition. The two matrices, 
and 
in 
are called equivalent if 
can be obtained from 
by permutation of lines and columns (this equivalency is denoted by:
).
Examples.
7) The matrices, 
and 
in example 6 are equivalent, because 
is obtained from 
by the permutation of the 2nd and 3rd columns.
In connection of the above definition, we use the following coding of the matrices of
. We numerate all the columns of the length
, choosing, for instance, the lexicographical order.
Let the corresponding numeration be,
. Then we put a vector of the length, 
into correspondence with
. We get
, where 
is the number of the columns equal to 
in the matrix,
. We call the vector, 
, column vector of the matrix,
. Then the following is obvious:
Statement. If the matrices, 
and 
are equivalent, then
.
Now we describe all extreme matrices for a fixed m. We denote the set of all such matrices by
. The elements of the class, 
, have the following properties:
1) If 
, then
.
This property follows the fact that all the lines of the matrix, 
are different.
2) If
, then for 
we have: 
Indeed, if
? then there are identical columns in the matrix,
. But then we can take one of them away, and the lines in the obtained matrix will again be different, and this means that 
.
3) If
, there is neither regular, nor unit columns in the matrix,
.
This statement is proved similar to the preceding one.
4) Each of the columns of the matrix, 
, has even number of units..
This follows the fact that the matrix is a null-matrix.
The significance of the introduced definitions and the above results is that they make possible to obtain any matrix just adding some null-matrix to
. This is due to the fact that taking away columns out of any matrix, 
leads to a matrix,
.
Conclusion. Obtaining the matrices, 
out of the matrix, 
, is a problem of building deadlock tests for the given matrix, 
[7].