Prospects for Using Finite Algebraic Rings for Constructing Discrete Coordinate Systems

1. Introduction

Algebraic extensions of Galois fields based on irreducible polynomials and providing the formation of

G F (p^{n})

fields are increasingly used in practice. They play an important role in cryptography, coding theory, and digital signal processing. For example, in cryptography, operations in

G F (2^{8})

are used in encryption algorithms such as AES, as well as in the construction of elliptic curves, which ensures compact keys and a high degree of security [1,2,3]. In coding theory, Galois fields are used to develop error-correcting codes such as Reed–Solomon and BCH codes, which ensure reliable data transmission even under significant interference [4].

Modern research is focused on the development of algorithms for working with Galois fields

G F (p^{n})

, including calculations in fields with large characteristics, which is especially important for applications in cryptography and computer algebra. For example, the ALDES/SAC2 systems implement algorithms for performing operations in large fields, such as

G F (3^{30})

and

G F (7^{17})

, which makes it possible to efficiently implement computations [5,6]. Generators have been developed for creating hardware descriptions (VHDL) of multipliers applicable in digital systems. These tools make it possible to simplify the design of high-performance cryptographic circuits [6,7]. Theoretical studies of structures associated with such extensions are also ongoing [8].

Such extensions are of interest for digital image processing, including volumetric images. Indeed, in the digital processing of planar images, they are divided into pixels, and in similar processing of volumetric images, into voxels [9]. In many problems of practical interest, the image size, and therefore the number of pixels (or voxels), is limited. An obvious example is the images displayed on the screen in existing standards [10,11]. In such cases, it is permissible to use discrete coordinates in terms of Galois fields. Indeed, the location of a single pixel of a particular image can be uniquely described through an element of the Galois field

G F (p^{2})

, represented in the form
where

u_{1}

and

u_{2}

are the elements of the main field

G F (p)

θ

is the root of the irreducible equation (an equation of the second degree that has no solution in the main field), and it is also assumed that

l_{1, 2} < p

, where

l_{1, 2}

is the number of pixels in the image under consideration horizontally and vertically.

A similar approach can be used in other cases when a finite section of the plane is analyzed (for example, for the purposes of monitoring agricultural lands [12,13], soil conditions [14], forests [15], and environmental monitoring [16]).

Formula (1) can be considered as a discrete analogue of the representation of a complex value:

This representation of the coordinates of a point on a plane is known to be widely used in many problems of hydrodynamics [17,18], electrostatics [19,20], etc. However, there is a significant nuance. A representation similar to (1) also exists for the “three-dimensional” case

$u = u_{1} + θ u_{2} + θ^{2} u_{3}$

(3)

where $θ$ is the root of an irreducible equation of the third degree.

At the same time, there is no analogue of formula (2) for the three-dimensional case. There are only “four-dimensional” complex numbers—Hamilton quaternions [21]. The advantages of representation (3) are obvious: starting from it, one can try to develop a discrete analogue of the theory of functions of a complex variable for the three-dimensional case. This formulation of the question is justified by the following considerations. As noted in [22], the model of a digital signal can, among other things, comprise functions that take values in Galois fields. Indeed, if a digital (discrete) signal changes in a finite range of amplitudes, then the number of its levels is obviously finite. Consequently, any planar digital image can be described through a function whose domain of definition is the field

G F (p^{2})

and which takes values in the same field. The same is true for three-dimensional images: it is sufficient to move to the fields

G F (p^{3})

. Note also that it is possible to represent any functions of this type in the form of explicit algebraic expressions [23].

For many problems that are important from a practical point of view, the algebraic representation of coordinate transformations is also of interest. Such problems arise, for example, in the development of control algorithms for UAV swarms [24,25,26], which are increasingly used for both civilian [27,28,29] and military [30,31,32] purposes. To control a swarm of UAVs, it is often necessary to recalculate the coordinates of each drone relative to the reference point (e.g., the leading drone) between the above-mentioned coordinate systems [33,34]. In this case, it is often necessary to ensure the transition from the global coordinate system (e.g., GPS in the latitude and longitude format) to a local one, for example, NED (North–East–Down) and ENU (East–North–Up), and it is necessary to distinguish between the local coordinate system of the swarm leader, the local coordinate system of the swarm center, or an individual drone (Body Frame) [35,36,37]. It is significant that in this case, such three-dimensional coordinate systems as the Global Rectangular system (ECEF—Earth-Centered, Earth-Fixed) and the Global Geographic system (LLA—Latitude, Longitude, Altitude) [38,39] are used.

To describe coordinate transformations, non-trivial algebraic structures such as Clifford algebra [33] and Hamiltonian quaternions [40] are used, which provide a compact and stable representation of rotation. Quaternions can be used both to describe the UAV orientation [40] and directly in control, for example, to find the orientation error [41], correct the angular velocity [42], or control the rotation, including for UAV stabilization [43]. The advantage of using quaternions is that they allow one to remove the difficulties associated with the “Gimbal Lock” problem (Euler angle singularity) [44]. Note that in practice, UAV coordinates are always specified with finite accuracy; therefore, it is permissible to use a discrete coordinate grid (discrete Cartesian coordinates). This significantly expands the list of algebraic structures that can be used for the above purposes. In particular, finite algebraic rings can be used, the advantages of which are as follows.

The classical form of representation of the coordinates of a point in a multidimensional space is the representation through orthogonal basis vectors

e_{i}

$u = u_{1} e_{1} + u_{2} e_{2} + u_{3} e_{3}$

(4)

where $e_{i} e_{j} = 0; i \neq j$ .

In the theory of algebraic rings, it is proved that there exist rings that can be represented as a direct sum of algebraic ideals [45]. In this case, each element of the ring can be represented as

$r = r_{1} e_{1} + r_{2} e_{2} + \dots + r_{n} e_{n}$

(5)

where $e_{i}$ are idempotent elements with the following properties:

$e_{i} e_{j} = 0; i \neq j,$

(6)

$e_{1} + e_{2} + \dots + e_{n} = 1$

(7)

Comparison of formulas (4) and (5), which include elements that cancel each other, shows that a deep analogy can be established between algebraic rings and discrete vector spaces, and a deeper analogy than, say, between a two-dimensional vector space and complex numbers. Namely, unlike structures such as complex numbers or Galois fields, zero divisors appear in algebraic rings, which allows us to specify an analog of basis vectors that cancel each other when calculating the scalar product, as well as analogs of vector subspaces, which are ideals of the form

r_{i} e_{i}

. There is, however, an important nuance: in the case where, for example, residue number systems, RNSs [46,47,48], are used, ideals of the form

r_{i} e_{i}

contain a different number of elements. Accordingly, the above analogy is not complete.

Consequently, we can pose the question of finding an algebraic discrete analogue of formula (4), in which the role of basis vectors is played by idempotent elements. It is also desirable to ensure that all algebraic ideals of the form

r_{i} e_{i}

have the same number of elements. Such an approach, we emphasize once again, is of interest for numerous problems in which the coordinate grid can be reduced to a digital (discrete) form. In addition to the already mentioned problems, such an approach is of interest for constructing convolutional neural networks, which are currently finding an increasingly wide range of applications [49,50,51]. As shown in [52], it is the use of finite algebraic structures that allows us to significantly modernize the operation of calculating digital convolutions.

In digital image processing using neural networks, problems are often encountered that require taking symmetry considerations into account. This is especially true for neural networks that allow the image under study to be represented as a set of fairly simple geometric elements. Such neural networks are widely used in practice and have proven themselves to be effective [53,54,55,56,57]. In this case, simple geometric elements can usually be brought to each other by means of coordinate transformations (including the operation of stretching along the coordinate axes). Coordinate transformations, as is known, have been and remain one of the main tools for studying the symmetry properties of not only flat but also spatial figures (symmetry corresponds to the invariance of a figure under a certain coordinate transformation). Since images (both flat and volumetric) are currently usually specified in discrete form, the development of a description of coordinate transformations in terms of finite algebraic structures is of interest from this point of view as well.

In this paper, we propose a specific algorithm for constructing representations of the form (5), intended for displaying digital (discrete) coordinates, based on the non-standard method of algebraic extensions proposed in [58]. The difference is that in the cited work, this method was applied to a two-dimensional space. In this paper, it is extended to the three-dimensional case. This requires the development of a non-trivial mathematical apparatus that allows solving systems of nonlinear equations whose coefficients belong to the main Galois field.

3. Results

3.1. General Approach

Relation (6) can be used to find idempotent elements directly. We obtain the corresponding equations following the approach proposed in [58].

In accordance with the methodology [58], we assume that it is permissible to pass from the basic Galois field to its non-standard algebraic extension using some formal additional solution

i

of the reducible equation of the form

$i^{3} = k_{0} + k_{1} i + k_{2} i^{2}$

(9)

We emphasize that an equation of the form (9) is used, which has a solution in the field under consideration. Our task is to find conditions under which it can have additional formal solutions. Equation (9) is of the third order, which corresponds to finding an extension that can be put in correspondence with a discrete three-dimensional space.

In accordance with [63], the element

i

will be treated as a logical imaginary unit of the second kind. It is assumed that, using the element

i

, it is possible to construct three elements

g_{n}

n = 1, 2, 3

, satisfying condition (6), in the following form (for now, the elements

g_{n}

are considered, not

e_{n}

, since they can differ from each other by a factor):

$g_{n} = 1 + a_{n} i + b_{n} i^{2}$

(10)

The element $i$ is, strictly speaking, an abstraction, but the same is true for the algebraic elements by which extensions of Galois fields are constructed using the traditional method. In particular, this means that the meaning of the element $i$ is given by the rules for operating with such an element. Let us establish these rules, while simultaneously clarifying the conditions under which relations (6) are satisfied. Let us emphasize that to establish the rules for operating with the element $i$ , it is sufficient to find the coefficients $k_{m}$ in formula (9), under which operations with i as a logical imaginary unit of the second kind will make sense.

Multiplying the elements

g_{1}

and

g_{2}

by each other, we obtain

$g_{1} g_{2} = (1 + a_{1} i + b_{1} i^{2}) (1 + a_{2} i + b_{2} i^{2}) = c_{012} + c_{112} i + c_{212} i^{2}$

(11)

$g_{1} g_{2} = 1 + (a_{1} + a_{2}) i + (a_{1} a_{2} + b_{1} + b_{2}) i^{2} + (a_{2} b_{1} + a_{1} b_{2}) i^{3} + b_{1} b_{2} i^{4}$

(12)

Considering formula (9), as well as condition (6), we have

$c_{012} = 1 + (a_{2} b_{1} + a_{1} b_{2}) k_{0} + b_{1} b_{2} k_{2} k_{0} = 0$

(13)

$c_{112} = a_{1} + a_{2} + (a_{2} b_{1} + a_{1} b_{2}) k_{1} + b_{1} b_{2} (k_{0} + k_{2} k_{1}) = 0$

(14)

$c_{212} = a_{1} a_{2} + b_{1} + b_{2} + (a_{2} b_{1} + a_{1} b_{2}) k_{2} + b_{1} b_{2} (k_{1} + k_{2}^{2}) = 0$

(15)

Three more such equations are obtained by considering two other pairs by replacing indices. Consequently, the system of equations that ensures the fulfillment of requirements (6) when representing elements $e_{n}$ in the form (10) contains nine equations for nine unknowns.

Let us show that there is a very specific type of Galois field for which this system of equations has a non-trivial solution. These are the fields $G F (p)$ , such that $p - 1$ is divisible by three.

In this case, the solutions of the system under consideration correspond to the following values of the sought parameters:

$k_{0} = 1; k_{1} = 0; k_{2} = 0$

(16)

where $m$ is an integer and $q_{0}$ is a primitive root of the equation

Recalling that all non-zero elements of the field

G F (p)

satisfy the equation

The use of the minus sign in formula (20) is legitimate, among other things, because, for the elements of the field

G F (p)

it is permissible to use a representation containing negative numbers [59], for example

$G F (7) = - 3, - 2, - 1, 0, 1, 2, 3$

(21)

From Equation (20) we can go to Equation (19) if

p - 1

is divisible by three. Indeed

${(x^{\frac{p - 1}{3}})}^{3} - 1 = 0$

(22)

Recall that the integer powers of the primitive root of the equation exhaust all possible solutions of the equation of the form (19) or (20). In particular, this means that there are three different solutions of equation (19)

q_{1}

q_{2}

q_{3}

, which are elements of the field under consideration, and the sum of these three elements when added modulo

p

is identically equal to zero:

Indeed, the solutions of Equation (19) form a group under multiplication, and there exists an element

q_{0}

such that

$q_{n} = q_{0}^{n}; n = 0, 1, 2$

(24)

Hence

$q_{1} + q_{2} + q_{3} = 1 + q_{0} + q_{0}^{2}$

(25)

The identity holds

$(1 + q_{0} + q_{0}^{2}) (1 - q_{0}) = 1 - q_{0}^{3} = 0$

(26)

From which follows (23), since

1 - q_{0} \neq 0

. Using formula (23), it can be shown that the set of parameters specified by formulas (16)–(18) actually corresponds to the solution of the system of nine equations generated by conditions (6). Indeed, in the case when equalities (16) are satisfied, the first three equations from the considered system of equations take the form

$c_{012} = 1 + (a_{2} b_{1} + a_{1} b_{2}) = 0$

(27)

$c_{112} = a_{1} + a_{2} + b_{1} b_{2} = 0$

(28)

$c_{212} = a_{1} a_{2} + b_{1} + b_{2} = 0$

(29)

The remaining six equations are obtained by rearranging the indices. Substituting expressions (17) into formulas (27)–(29), we obtain

$c_{012} = 1 + (b_{2}^{2} b_{1} + b_{1}^{2} b_{2}) = 0$

(30)

$c_{112} = b_{1}^{2} + b_{2}^{2} + b_{1} b_{2} = 0$

(31)

$c_{212} = b_{1}^{2} b_{2}^{2} + b_{1} + b_{2} = 0$

(32)

It is easy to verify that, in this case, the expressions (18) really ensure the fulfillment of the system of equations under consideration. Indeed, in this case

$c_{012} = c_{112} = c_{212} = 1 + q_{0}^{2} + q_{0}^{1} = 0$

(33)

Thus, expressions (16)–(18) define elements that mutually cancel each other. Expressions for these elements can be specified directly:

$g_{2} = 1 + q_{0}^{2} i + q_{0} i^{2}$

(35)

$g_{3} = 1 + q_{0} i + q_{0}^{2} i^{2}$

(36)

When deriving formula (36), it was considered that for the values of

k_{n}

specified by formula (18), the following holds:

Summing up expressions (34)–(36), by virtue of (23) we obtain

It is important that this result does not depend on the choice of the field

G F (p)

; it is only necessary that

p - 1

be divisible by 3. Consequently, to ensure that relation (7) is satisfied, it is sufficient to multiply the obtained elements

g_{i}

by the normalization factor

3^{- 1}

, which is also the same for all fields of the type under consideration.

It is worth emphasizing that the resulting elements automatically become idempotent. Indeed, multiplying (7) by

e_{i}

, we obtain

$e_{i} (e_{1} + e_{2} + e_{3}) = e_{i}$

(40)

From which we obtain the following:

Thus, for a three-dimensional space, it is possible to propose an analog of a basis in which the role of basis vectors is played by idempotent elements of a finite algebraic ring, and the role of coordinates is played by elements of the Galois field

G F (p)

, where

p - 1

is divisible by three. We emphasize that the proposed approach differs from existing methods of constructing algebraic rings in that the analogy between an algebraic ring of the type under consideration and a discrete vector space becomes complete. It follows from formula (5) that an arbitrary element of the ring

z

can be represented in the form

$z = z_{1} e_{1} + z_{2} e_{2} + \dots + z_{n} e_{n}$

(42)

where $z_{i}$ are elements belonging to the main field $G F (p)$ , i.e., the number of elements corresponding to each of the coordinate analogues is the same, which is not the case, for example, for RNS [46,47,48].

For solving applied problems in which finite regions of space are considered, the latter limitation is not essential, since it is always possible to choose a field whose number of elements slightly exceeds the maximum discrete coordinate number.

3.2. Specific Examples

Let us consider, for clarity, specific examples of solutions to equations that allow us to construct idempotent elements capable of playing the role of basis vectors in three-dimensional space.

For illustration, Table 1 and Table 2 present variants of solutions that correspond to formulas (16)–(18) for the cases of fields

G F (7)

and

G F (13)

, respectively. The tables show that, as expected, solutions of this type correspond only to permutation of indices. The first six columns of Table 1 contain quantities whose third power in the field

G F (7)

gives one, and similarly for Table 2.

Note that another type of solution to the system of equations generated by conditions (6) corresponds to the equation

In this case, the solutions of the system of equations under consideration are given by the following formulas:

$k_{0} = - 1; k_{1} = 0; k_{2} = 0$

(44)

Let us prove this statement. When substituting (44) into the initial system of equations generated by conditions (6), the following relations are formed:

$c_{012} = 1 - (a_{2} b_{1} + a_{1} b_{2})$

(47)

$c_{112} = a_{1} + a_{2} - b_{1} b_{2}$

(48)

$c_{212} = a_{1} a_{2} + b_{1} + b_{2}$

(49)

Six more equations from this system are obtained by permutations of indices. Substituting expressions (45) into (47)–(49), we obtain that the problem is reduced to the previous one:

$c_{012} = 1 + (b_{2}^{2} b_{1} + b_{1}^{2} b_{2}) = 0$

(50)

$c_{112} = - (b_{1}^{2} + b_{2}^{2} + b_{1} b_{2}) = 0$

(51)

$c_{212} = b_{1}^{2} b_{2}^{2} + b_{1} + b_{2} = 0$

(52)

The only difference is the common minus sign in formula (51), which does not affect the final result. For clarity, possible solutions corresponding to formulas (44)–(46) are presented in Table 3 and Table 4 for specific Galois fields

G F (7)

and

G F (13)

, respectively. In this case, the solution options also differ from each other by the permutation of the coefficients.

A natural question arises as to how correct it is to use an additional algebraic element, interpreted as a logical imaginary unit of the second kind. To answer this question, it is advisable to use a matrix representation, simultaneously illustrating the nature of the results obtained using specific examples.

3.3. Justification of the Correctness of the Non-Standard Method of Algebraic Extensions

Let us emphasize once again that the element $i$ that we use, interpreted as a logical imaginary unit of the second kind, is an abstraction. It is defined only by the rules of operation. For greater clarity, however, it makes sense to consider the question of what other form this element can be represented in, as well as the elements that are constructed with its help. In this section, it is proved that the above elements can be put in accordance with the matrices defined over the main Galois field, starting from which we construct algebraic rings. This will not only make the elements under consideration visual but also demonstrate the correctness of their use.

Let us start with specific examples of constructing idempotent elements

e_{i}

obtained by extending specific Galois fields. Specifically, in the field

G F (7)

, idempotent elements of the obtained type are displayed as

$e_{1} = 3^{- 1} (1 + 3 i + 2 i^{2}) = - 2 + i + 3 i^{2}$

(53)

$e_{2} = 3^{- 1} (1 - i + i^{2}) = - 2 + 2 i - 2 i^{2}$

(54)

$e_{3} = 3^{- 1} (1 - 2 i - 3 i^{2}) = - 2 - 3 i - i^{2}$

(55)

since in the field $G F (7)$ we have $3^{- 1} = - 2$ .

This case corresponds to solutions corresponding to the equation

A direct check can verify that these elements are indeed idempotent. For example, in the field

G F (7)

$e_{3}^{2} = (- 2 - 3 i - i^{2}) (- 2 - 3 i - i^{2}) = - 3 - 2 i - i^{2} - i^{3} + i^{4} = - 2 - 3 i - i^{2} = e_{3}$

(57)

This example is, of course, of a particular nature, but it allows us to demonstrate the correctness of using the element

i

by a method that allows an elementary generalization to all Galois fields of the type under consideration. Traditional algebraic extensions of Galois fields allow representations through matrices defined over the main Galois field. Similarly, a matrix representation can be used to represent the element

i

and those generated by it. Consider the product of the element

i

by an arbitrary element obtained with its help:

$i a = i (a_{1} + a_{2} i + a_{3} i^{2}) = a_{3} + a_{1} i - a_{2} i^{2}$

(58)

$i^{2} a = i^{2} (a_{1} + a_{2} i + a_{3} i^{2}) = - a_{2} - a_{3} i + a_{1} i^{2}$

(59)

Transformation (58) can be considered as a transformation of a vector whose components are the quantities

a_{i}

. Such a transformation can be displayed by a matrix

$i \leftrightarrow (\begin{matrix} 0 & 0 & - 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix})$

(60)

Likewise,

$i^{2} \leftrightarrow (\begin{matrix} 0 & 0 & - 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}) (\begin{matrix} 0 & 0 & - 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}) = (\begin{matrix} 0 & - 1 & 0 \\ 0 & 0 & - 1 \\ 1 & 0 & 0 \end{matrix}),$

(61)

Moreover, the last representation could also be obtained immediately based on formula (59). Substituting the obtained matrix representations into formulas (10) and (39) and also taking into account the specific values of the coefficients for the case under consideration, we obtain a matrix representation of idempotent elements for the case of the field

G F (7)

$e_{1} \leftrightarrow - 2 (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) + (\begin{matrix} 0 & 0 & - 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}) + 3 (\begin{matrix} 0 & - 1 & 0 \\ 0 & 0 & - 1 \\ 1 & 0 & 0 \end{matrix}) = (\begin{matrix} - 2 & - 3 & - 1 \\ 1 & - 2 & - 3 \\ 3 & 1 & - 2 \end{matrix})$

$e_{2} \leftrightarrow - 2 (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) + 2 (\begin{matrix} 0 & 0 & - 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}) - 2 (\begin{matrix} 0 & - 1 & 0 \\ 0 & 0 & - 1 \\ 1 & 0 & 0 \end{matrix}) = (\begin{matrix} - 2 & 2 & - 2 \\ 2 & - 2 & 2 \\ - 2 & 2 & - 2 \end{matrix})$

(62)

$e_{3} \leftrightarrow - 2 (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) - 3 (\begin{matrix} 0 & 0 & - 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}) - (\begin{matrix} 0 & - 1 & 0 \\ 0 & 0 & - 1 \\ 1 & 0 & 0 \end{matrix}) = (\begin{matrix} - 2 & 1 & 3 \\ - 3 & - 2 & 1 \\ - 1 & - 3 & - 2 \end{matrix})$

The fact that these matrices, defined over the field $G F (7)$ , are indeed idempotent and mutually annihilating can be verified directly by verification. Note that the matrix representation of the obtained algebraic elements is far from necessarily of practical interest. However, the very fact that additional formal solutions of the equation being reduced can be assigned specific matrices proves the correctness of their use.

4. Discussions

The proposed approach creates a basis for solving geometric problems in three-dimensional space in digital form. This approach is applicable to solving any geometric problems, including those related to coordinate transformations, in which the coordinates are specified with a certain accuracy, and the area to which the problem being solved relates is limited in space.

This is directly proved by formula (42), which is a complete analogue of formula (4), which expresses a vector in a multidimensional space through basis vectors and coordinate values. In formula (42), the role of basis vectors is played by idempotent elements of the ring constructed in this work, and the variables corresponding to coordinates in the chosen basis take values in the main Galois field.

Problems of a geometric nature that can be solved using the proposed approach are relevant, among other things, for improving methods of physical protection of information when transmitting commands to swarms of unmanned vehicles. It should be noted that the development of physical methods for protecting information is becoming increasingly important [64,65,66], including due to the improvement of electronic warfare methods. The method proposed in [67] is based on identifying the location of a radio signal source interpreted as “friend”. Such a problem can be solved, including by determining the propagation time of a radio signal from a specific source to the elements of a UAV group. Geometrically, as in the case considered in [68], it comes down to finding the intersection point of hyperbolas (or hyperboloids, if the problem is solved in three-dimensional space). Problems of this kind can be solved in various ways [69,70,71]; however, to ensure information security by identifying the location of the signal source, high accuracy is not required, which allows the use of a sufficiently coarse discrete grid [72]. This allows us to raise the question of using finite algebraic structures to construct coordinate systems.

We emphasize that attention to this example is determined not only by demonstrating the relevance of the approach being developed. This example, among other things, demonstrates the importance of further development of the proposed approach, and specifically from the point of view of logical-algebraic problems.

Further development of the proposed approach, of course, requires solving several other problems. One of them is related to the question of how one should calculate the discrete distance between two points, provided that their coordinates are specified in a form corresponding to formula (5), i.e., it is necessary to answer the question of what should be understood by distance when the position of a point in a discrete three-dimensional space is specified through the elements of the ring constructed in this work.

We will show that this and similar problems can be solved by using the analogy between functions taking values in Galois fields $G F (p)$ and functions of multivalued logic. We emphasize that the components of the analog of a three-dimensional vector in the case under consideration take values in the main Galois field. Consequently, for a given choice of idempotent elements (analogs of basis vectors), the position of a point in a discrete space is specified through a set of two or three variables taking values in the main field. Consequently, determining the distance in the case under consideration is reduced to finding a function taking values in the Galois field, the arguments of which also take values in the main Galois field.

Such a function can be constructed based on the results of [23], in which it was shown that it is possible to specify a specific algebraic expression for an arbitrary function of multivalued logic, provided that the number of values of the variables of such logic corresponds to the number of elements of the Galois field. For the case of two variables, such a function is written in the following form:

$F (x, y) = \sum_{m, n} F (x_{n}, y_{m}) g (x - x_{n}) g (y - y_{m}),$

(63)

where $g (x - x_{n})$ is the algebraic δ-function:

$g (x - x_{n}) = 1 - {(x - x_{n})}^{p - 1} = \{\begin{matrix} 1, x = x_{n} \\ 0, x \neq x_{n} \end{matrix},$

(64)

This allows us to specify a function describing the distance between points whose coordinates correspond to elements of the Galois field in the form of an analogue of the truth table and then use the relation (63). For clarity, Figure 1 shows a fragment of an analogue of the truth table for the case of the field

G F (31)

. The values given in this table correspond to discrete distances (true geometric distances rounded to integer values).

The values presented in this table can also be interpreted as elements of the Galois field corresponding to discrete distances. For this, it is sufficient to choose

p

so that

p > \sqrt{2} N

for the two-dimensional case and

p > \sqrt{3} N

for the three-dimensional case (

N

is the maximum number of the discrete coordinate, if it is counted from zero). This allows us to use formula (63) or its equivalent, which solves the problem. Similarly, using relation (63), we can obtain formulas for other geometric characteristics if necessary. Moreover, the proposed approach allows for further development due to the representation of linear operators through elements of algebraic structures. A similar problem has already been solved in [72], where it was shown that there is a large class of fields

G F (p)

that simultaneously admit algebraic extensions both by the classical method and by the method proposed by us (i.e., using both irreducible and reducible algebraic equations). This approach allows us to represent arbitrary operators corresponding to 2 × 2 matrices (including operators corresponding to Galois transformations of plane coordinates) through algebraic elements formed by simultaneously using extensions of both types. The results presented in this paper allow us to implement a similar approach at the next stage of research for operators corresponding to 3 × 3 matrices, including operators describing transformations of three-dimensional coordinates.

Coordinate transformations are of interest for several practical applications, including for the method mentioned above, physical protection of information when controlling a group of UAVs in a line-of-sight zone, based on the definition of the operator’s coordinates. This ultimately comes down to solving a geometric problem like that used in the “hyperbola method” [68]. The difference lies in the nature of the problem solution. In one case, the coordinates of the signal source are determined in terms of continuously changing coordinates, and in the other case, discrete ones. This is acceptable, since to identify the source of a signal interpreted as “one’s own”, its coordinates can be determined with a low accuracy. We emphasize that, in this case, the “accuracy” with which the operator’s coordinates should be determined is determined by the nature of the use of the UAV swarm. A clear example proving this statement is related to the nature of the use of UAVs during the current military conflicts. Namely, drones controlled via fiber optics are increasingly being used. On the one hand, this automatically implies relatively short distances over which the control signal is transmitted. On the other hand, this implies that there is a fairly large distance between the drone operator and the location of any electronic warfare equipment used by the opposing side. As a rule, they are separated by the line of combat contact. Consequently, the accuracy of determining the operator’s coordinates can indeed be made quite low; it is enough to determine the area of his location, for example.

We also note that the transition to controlling groups of unmanned vehicles using algorithms formulated in terms of finite algebraic structures is also of interest from the point of view of increasing the efficiency of computing systems, including onboard [73]. There is no doubt that computing systems built on calculations reduced to operations on integers have significant advantages over analogs forced to use fractional values in floating-point arithmetic, which requires additional processing for normalization and control of the accuracy of calculations [74,75,76]. Systems of this kind are currently being actively developed, for example, systems using residual classes (residue number system) [77,78], integer arithmetic in digital signal processors (DSP) [79,80], specialized processors for cryptography (e.g., hardware accelerators RSA and ECC) [81,82], as well as deep learning accelerators working with weight quantization (e.g., TPU and neuromorphic processors) [83,84]. It should be emphasized that computing systems directly based on operations in Galois fields (for example, systems that perform calculations modulo an integer [85,86]) are also being actively developed at the present time [87,88]. Not only do they obviously outperform algorithms that require fractional calculations in terms of performance, but they can also be used in the future to develop AI coupled with swarms of UAVs. Namely, as noted in [89], each command executed by a UAV can be assigned to a specific value of a variable of multi-valued logic, which, in turn, can be assigned to some non-zero element of a Galois field. This, among other things, makes it possible to reduce multi-valued logic operations to algebraic ones, and then use the potential of computing systems created based on neuromorphic materials [90,91] to implement specific forms of AI, the relevance of which was also substantiated in [92]. One of these specific forms of AI can be implemented for groups of unmanned vehicles. It is obvious that AI built on the use of Galois fields will be complementary to the representation of coordinate systems through such fields.

Source link

Ibragim Suleimenov www.mdpi.com

Greenberg News

Prospects for Using Finite Algebraic Rings for Constructing Discrete Coordinate Systems

1. Introduction

3. Results

3.1. General Approach

3.2. Specific Examples

3.3. Justification of the Correctness of the Non-Standard Method of Algebraic Extensions

4. Discussions

Greenberg

1. Introduction

3. Results

3.1. General Approach

3.2. Specific Examples

3.3. Justification of the Correctness of the Non-Standard Method of Algebraic Extensions

4. Discussions

Related Posts

A Meanline Code for Outboard Dynamic-Inlet Waterjet Axial-Flow Pumps Design

IJGI, Vol. 14, Pages 124: End-to-End Vector Simplification for Building Contours via a Sequence Generation Model

A Comprehensive Survey on Advanced Control Techniques for T-S Fuzzy Systems Subject to Control Input and System Output Requirements

Greenberg