ABSTRACT

Many problems of discrete optimization are connected with partition of the n-dimensional space into certain subsets, and the requirements needed for these subsets can be geometrical—for instance, their sphericity—or they can be connected with certain metrics—for instance, the requirement that subsets are Dirichlet’s regions with Hamming’s metrics [1]. Often partitions into some subsets are considered, on which a functional is optimized [2]. In the present work, the partitions of the n-dimensional space into subsets with “zero” limitation are considered. Such partitions allow us to construct the set of the group codes, V, and the set of the channels, A, between the arbitrary elements, V and A, having correcting relation between them. Descriptions of some classes of both perfect and imperfect codes in the additive channel are presented, too. A way of constructing of group codes correcting the errors in the additive channels is presented, and this method is a further generalization of Hamming’s method of code construction.

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 B^r 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, B⁴, 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:

orwhere is any regular null-matrix.

5) Let, then the regular null-matrices are as follows:

andwhere 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].

REFERENCES