Open AccessArticle

Peculiarities of Applying Partial Convolutions to the Computation of Reduced Numerical Convolutions

National Engineering Academy of the Republic of Kazakhstan, Almaty 050010, Kazakhstan

Institute of Communication and Space Engineering, Almaty University of Power Engineering and Telecommunication Named Gumarbek Daukeev, Almaty 050013, Kazakhstan

National Scientific Laboratory for the Collective Use of Information and Space Technologies (NSLC IST), Satbayev University, Almaty 050013, Kazakhstan

Author to whom correspondence should be addressed.

Appl. Sci. 2024, 14(14), 6388; https://doi.org/10.3390/app14146388

Submission received: 31 May 2024 / Revised: 16 July 2024 / Accepted: 19 July 2024 / Published: 22 July 2024

Download

Browse Figures

Versions Notes

Abstract

A method is proposed that reduces the computation of the reduced digital convolution operation to a set of independent convolutions computed in Galois fields. The reduced digital convolution is understood as a modified convolution operation whose result is a function taking discrete values in the same discrete scale as the original functions. The method is based on the use of partial convolutions, reduced to computing a modulo integer

q_{0}

, which is the product of several prime numbers:

q_{0} = p_{1} p_{2} \dots p_{n}

. It is shown that it is appropriate to use the expansion of the number

q_{0}

, to

q = p_{0} p_{1} p_{2} \dots p_{n}

, where

p_{0}

is an additional prime number, to compute the reduced digital convolution. This corresponds to the use of additional digits in the number system used to convert to partial convolutions. The inverse procedure, i.e., reducing the result of calculations modulo q to the result corresponding to calculations modulo

q_{0}

, is provided by the formula that used only integers proved in this paper. The possibilities of practical application of the obtained results are discussed.

Keywords:

partial convolutions; algebraic rings; Galois fields; moving average method; convolution theorem; computation modulo a prime number; idempotent elements

1. Introduction

The convolution operation is widely used in various sciences (optics [1,2], electronics [3,4], etc.).

Digital convolution is the basis of convolutional neural networks (CNN), [5,6]. By digital convolution, hereinafter, we will understand convolution, under the sign of which are functions whose values correspond to a certain finite set of discrete quantities.

It is appropriate to emphasize that CNN [5,6] represent one of the most common varieties of artificial neural networks (ANNs). The last wave of ANN development, demonstrating the ability of CNN to show extraordinary results in the field of pattern classification, is exactly associated with such networks [7]. An important area of application of convolutional neural networks is pattern recognition and computer vision [8,9,10], natural language text processing [11,12], speech recognition in noisy environments [13], etc.

As it was noted in [14,15], for digital signals, there is a wide enough space in the choice of the function serving as a signal model. In particular, in these reports, it was emphasized that functions taking values on the set of real or complex numbers actually represent some mathematical object, allowing for the creation of a signal model. The choice of such an object allowing for the creation of a signal model is ultimately a matter of agreement and convenience [14,15].

In particular, if a signal corresponding to discrete levels lying within a finite range of amplitudes is considered, then any function that can serve as a model of this signal must actually represent a mapping of the current variable (time variable) onto some finite set. Both Galois fields [16,17] and finite algebraic rings [18] can be chosen as such a set. It should be emphasized that such algebraic structures are nowadays more and more widely used in information technologies [19,20,21], and this also applies to non-associative algebras [22].

In this paper we show that it is possible to bring the computation of digital convolutions to computations in Galois fields, in which, in particular, the numerical analog of the classical convolution theorem [15] is valid.

This approach is of interest, in particular, because from the functions taking the values within Galois fields, it is admissible to pass to functions whose values correspond to variables of multivalued (as well as fuzzy) logic [23,24].

Specific computations that are performed in Galois fields or finite algebraic rings can in many cases be reduced to computations modulo integers. At present, circuits of various types allowing for the realization of such an operation are being developed quite actively [25,26,27,28], with cryptography remaining the main field of application here. This question is also reflected in the patent literature [29,30,31,32], where various variants of circuits of multipliers and adders modulo some numbers have been proposed.

It is well known that computations modulo integers allows for operating independently on the components of an integer representation [33,34,35,36].

It can also be used to represent a convolution operation as a set of partial convolutions, each of which corresponds to a particular Galois field.

However, when using digital convolutions, there is a significant nuance. The sampling scales of the original function and the function resulting from the convolution operator are different.

To bring them into a mutually unambiguous correspondence, it is necessary to use an operation that can be interpreted as a transition to the reduced digital convolution.

By the term “reduced digital convolution”, we mean the result of the convolution operation computation reduced to the same sampling scale as the original functions (functions under the convolution sign).

Such operation can be implemented using the usual rounding operation for fractional numbers; however, it is of interest to ensure that the calculation reduced digital convolution in terms of operations modulo integers.

This approach provides a significant reduction in the amount of computation required to bring the result of the convolution operation to the same discretization scale as the discretization scale of the functions under its sign. When using conventional rounding, decimal fractions have to be calculated. The proposed approach allows for operating only with integers. Moreover, this approach allows for the realization of computations directly in the form of electronic circuits, since nowadays, methods allowing for the realization of computations in Galois fields directly in the form of electronic circuits are well enough developed.

In addition, this approach creates prerequisites for the subsequent transition to the use of functions taking values in variables of multivalued logic, etc.

The specific formulation of the problem solved in this paper is presented in Section 3.

The novelty of the work is as follows. We propose an approach based entirely on modulo integer computations, which allows for the result of convolution operation to be brought to the same discretization scale as the discretization scale of original functions.

The proposed approach, among other things, allows for bringing the digital convolution to calculations in Galois fields. Separately, this work for the first time substantiates the method of choosing simple numbers that allow for carrying out this operation in the simplest and most convenient way.

2. Related Works

This work lies in the general trend of modern research aimed at improving the efficiency of computational systems, including those focused on the use of convolutional neural networks. References to specific works are given in Table 1.

One of the important directions here is related to the use of RNS (modular arithmetic), which can be used for neural networks too [37]. Such systems are closely related to fast arithmetic [38,39], i.e., an area of research that has received increasing attention over the last decades [40]. This work solves the problem of bringing the result of convolution operation to the original discretization scale, while preserving the possibility of computation in terms of RNS, i.e., it responds to the above trend.

It is of importance that the latter approach allows for generalization, since RNS can be considered as a special case of finite algebraic rings [24]. A wide variety of rings can be used for representation any set containing a finite number of elements, including non-associative ones [41,42]. This, in particular, justifies the use of the term “partial convolutions”, which implies the possibility of a subsequent transition to the use of finite algebraic rings of various types. A concrete example of using non-trivial algebraic rings for digital signal processing was given in [18]. The generalization of the RNS approach obviously creates additional opportunities for digital signal processing.

Further, some subsets of an algebraic ring used to represent sets containing a finite number of elements in many cases (including the case considered in this paper) can be put in correspondence with Galois fields. Such fields are also increasingly used in information technology, in particular, in cryptography to improve the reliability of encoding [43,44].

Computations in such fields can be realized directly in the form of electronic circuits, and research in this direction is also actively carried out at present [45,46]. More precisely, computations of this kind can be realized on the basis of chips with tunable logic structure, which are also actively used nowadays [47,48]. Reduced convolution operation is therefore of interest, also from the point of view of implementing the corresponding computations (including the implementation of convolutional neural networks) directly by specially programmed chips.

An example in this respect is a very definite problem arising in the processing of satellite video information intended for remote sensing of the Earth. Communication channels have limited bandwidth, so it is important to exclude images in those situations when the Earth surface is covered by clouds [49,50]. To solve this problem, it is expedient to use on-board means of information pre-processing, which can use convolutional neural networks. This particular example demonstrates the importance of the problem solved in this paper. A sufficiently coarse sampling scale can be used to exclude frames with cloud cover. Applying the convolution operation without reduction to the original sampling scale will not only correspond to the excess of accuracy, but will also require additional computational resources. It becomes especially important to overcome this difficulty when the corresponding operations are performed directly by the onboard computer.

The transition to computations in Galois fields has one more aspect. Namely, in this case it is possible to operate with functions taking values on variables of multivalued logic [23,24]. This aspect is important in those cases when, for example, we analyze the relationships between the preceding and following values of time series data, which are also used in different sciences. Provided the system is linear, it can often be assumed that such relationships are given by a convolution operation. The transition to the use of multivalued logics in the future allows us to raise the question of identifying true logical relationships in prediction, but the convolution operation itself should be reduced to logical variables. In this case, the preservation of the discretization scale is essential too, since this corresponds to the use of the same set of logical variable values for both the input and output functions.

Thus, this work, which provides the possibility of reducing the convolution operation to computations in Galois fields of relatively small size (which is ensured, among other things, by bringing the discretization scale of the result to the discretization scale of the original functions), contributes, among other things, to the interdisciplinary integration between the above-mentioned fields of research.

3. Background Section

Consider the usual expression for the convolution operation applied to functions taking discrete values

U_{o u t} (i) = \sum_{j} K (j) U_{i n} (i - j)

(1)

where

K (j)

—convolution operator core,

U_{o u t} (i)

and

U_{i n} (i)

—functions, which we will treat as “output” and “input”, respectively.

Let us assume that the functions

U_{i n} (i)

and

K (j)

are digital, i.e., each of them at each of the index values takes one of

N

discrete values corresponding to the sampling scale arising from the nature of the problem to be solved.

Besides, we will also assume that the function

K (j)

is different from zero only at

M

clock cycles

Then the number of values

N_{1}

, which can be taken by the function

U_{o u t} (i)

, generally speaking, lies within the limits defined by the inequality

0 \leq N_{1} \leq M N^{2}

(2)

One can see that this numerical range differs significantly from the range of variation of the original function

U_{i n} (i)

The reduction of these two ranges to each other can be performed by the operation of division by a suitable number

M_{1}

followed by rounding to an integer.

Operations of this kind, however, cannot be performed using operations only on integers, for example, they cannot be reduced to modulo operations.

Consequently, the problem is to find algebraic operations in terms of integers, allowing for the reduction of the scale of the function

U_{o u t} (i)

to the same scale as the function

U_{i n} (i)

This problem is solved in this paper using the method of partial convolutions.

4. Methods

4.1. Representation of Integer Computations in Terms of Finite Algebraic Rings

The basic method used in this paper is the theory of algebraic rings. The existence of rings

R

which are decomposed into a direct sum of ideals

r_{i}

is proved in this theory

R = r_{1} + r_{2} + \dots + r_{n}

(3)

Each of these ideals is generated by idempotent elements

e_{i}

r_{i} = R e_{i}

(4)

Such elements cancel each other out

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

(5)

Their sum is equal to the unit of the ring

R

\sum_{i}^{n} e_{i} = 1

(6)

The simplest example of rings of this type is generated by a homomorphism of the ring of integers to the ring of residue classes modulo

p

for the case where the number

p

is the product of several prime numbers

p_{i}

P = p_{1} p_{2} \dots p_{N}

(7)

In this case one can represent an arbitrary element of the ring

R

in the form

u = e_{1} u_{1} + e_{2} u_{2} + \dots + e_{N} u_{N}

(8)

where

e_{i}

—idempotent mutually cancelling elements, and

u_{i} = 0, 1, 2, \dots, p_{i}

Idempotent elements are formed by the rule

e_{i} = α_{i} \prod_{i \neq j}^{N} p_{j}

(9)

where

α_{i}

—integer. The choice of these numbers is based on the condition

e_{i} e_{i} = 1

(10)

One can see,

e_{i} p_{i} \equiv 0 m o d P

(11)

since any product of the form (11) contains a multiplier

P = p_{1} p_{2} \dots p_{N}

Indeed, the idempotent element

e_{i}

contains (9) the product of all prime factors of the number

P

except

p_{i}

, and

p_{i}

enters formula (11) directly.

With the choice of integers made,

α_{i}

also holds.

e_{1} + e_{2} + \dots + e_{N} \equiv 1 m o d P

(12)

Note that a special case of the representation (3) is the case when we consider the ring of residual classes modulo an integer.

In this case, the representation in the form (3) corresponds to RNS computations.

To illustrate, consider an example corresponding to the case of the product of three prime numbers 2, 3 and 7. The product of these numbers is 42. We will consider the ring of residue classes modulo 42.

Idempotent mutually cancelling elements can be easily found by the scheme corresponding to formula (9). Let us compose the products

3 \cdot 7 = 21

3 \cdot 2 = 6

2 \cdot 7 = 14

. All these elements will (when calculating modulo 42) cancel each other, since the result of their multiplication by each other will contain the factor

2 \cdot 3 \cdot 7

, i.e., this result will be a multiple of 42.

By direct verification it is also possible to verify that for the case under consideration the following equations holds.

36 \cdot 36 \equiv 36 m o d 42, 28 \cdot 28 \equiv 28 m o d 42, 21 \cdot 21 \equiv 21 m o d 42

(13)

Accordingly, when carrying out calculations modulo 42, the record (8) takes the form

u = 21 \cdot u_{1} + 28 \cdot u_{2} + 36 \cdot u_{3}

(14)

where

u_{1} = 0, 1, u_{2} = 0, 1, 2, u_{3} = 0, 1, \dots, 6

(15)

The relation (12) is also fulfilled

21 + 28 + 36 \equiv 1 m o d 42

(16)

Note also that the representation (8) and its special case (14) can be considered as a representation of numbers not exceeding 42 in a number system with hybrid base.

Indeed, one can see an analogy [51] between the notation (14) and the expression that defines the positional notation of a number, say, in a number system with base 10.

a = a_{0} + 10^{1} \cdot a_{1} + 10^{2} \cdot a_{2} + \dots

(17)

It can be seen that in both cases there is a certain selected set of numbers, which form a representation of any other number as a sequence of symbols from a finite set (digits).

In the case of the notation (17), such a set is formed by the powers of the base number 10. But, such a choice, in general, is not obligatory.

The standard decimal notation

a = \dots a_{2} a_{1} a_{0}

A similar notation can be used from expression (8) or its special case (14). For example, for the representation of (14) one can write down

u = u_{1} u_{2} u_{3}

(18)

where the positions occupied by specific values

u_{i}

can be interpreted as analogues of digits in the traditional number system.

An essential advantage of the considered number system is the possibility of independent operation with analogues of digits of a number.

The operation of addition in decimal (binary, etc.) representation is obviously connected with the fact that the result of adding the lower digits, generally speaking, will affect the result obtained by adding the higher digits.

When using the representation of the form (14), such a problem disappears. The “high” and “low” digits can be handled in a completely independent way.

Consider the product of two numbers written in the form (8)

u^{(1)} u^{(2)} = (e_{1} u_{1}^{(1)} + e_{2} u_{2}^{(1)} + \dots + e_{N} u_{N}^{(1)}) (e_{1} u_{1}^{(2)} + e_{2} u_{2}^{(2)} + \dots + e_{N} u_{N}^{(2)})

(19)

Because

e_{i}

are mutually cancelling idempotent elements, we have

u^{(1)} u^{(2)} = e_{1} u_{1}^{(1)} u_{1}^{(2)} + e_{2} u_{2}^{(1)} u_{2}^{(2)} + \dots + e_{N} u_{N}^{(1)} u_{N}^{(2)}

(20)

In this case, the computation of products

u_{i}^{(1)} u_{i}^{(2)}

is actually performed in the sense of the multiplication operation in the Galois field

G F (p_{i})

, since the multiplication operation is performed modulo

p_{i}

This conclusion is also true for the addition operation.

Expression (20) unambiguously shows that the result of calculating the product of “higher” digits is indeed completely independent of the result of calculating the product of “lower” digits. Moreover, such digits can be interchanged.

Formulas (19) and (20) allow for the passing to partial convolutions.

4.2. Partial Convolutions

Let us choose the above prime numbers

p_{i}

in accordance with next formula

U_{o u t} (i) < p_{1} p_{2} \dots p_{N}

(21)

where

N

—number of digits in hybrid coding.

Then, one can consider that the convolution formula applied to discrete functions (1) is written in terms of elements of rings admitting the representation (8).

With the assumption made, we can substitute into formula (1) the expansion through idempotent elements, and for both

K (j)

, and

U_{i n} (i)

. We have:

U_{o u t} (i) = \sum_{j} (\sum_{m} e_{m} K_{m} (j)) (\sum_{m} e_{m} U_{m, i n} (i - j))

(22)

By reversing the signs of summation, we obtain

U_{o u t} (i) = \sum_{m} e_{m} (\sum_{j} K_{m} (j) U_{m, i n} (i - j))

(23)

when deriving formula (23), it is taken into account that idempotent elements

e_{m}

cancel each other at multiplication (5).

Accordingly, the multiplier at

e_{m}

contains only values with the same index

m

In the last formula, the summation at index

j

is taken in separate brackets to emphasise the following circumstance.

When the functions corresponding to discrete signals are represented in a hybrid number system, the convolution operation is factorised. Each component of the used functions can be operated with in a completely independent way.

Accordingly, in this case we can speak about partial convolutions. We have:

U_{o u t, m} (i) = \sum_{j} K_{m} (j) U_{m, i n} (i - j)

(24)

Note that the operations of addition and multiplication in formula (24), as follows from the above, are performed modulo

p_{m}

, i.e., operation (24) is performed in the Galois field

G F (p_{m})

In particular, the description of any “digitized” system (a system reduced to discrete values) possessing the property of invariance with respect to the shift operation on the current discrete variable is exhausted by operations of this kind.

It is essential that the use of partial convolutions in terms of Galois fields is admissible only when an inequality of the form (2) is satisfied. In this case, the maximum value that can be given by the convolution operation does not exceed the integer modulo which the computation is performed.

Consequently, in this case, the result of operations modulo coincides with the results of operations in the sense of ordinary addition and multiplication of integers.

Here, however, a nuance arises. Indeed, if the original function varied in the range corresponding to integers not exceeding

N_{1}

, the convolution result can vary within a much wider range, formula (2).

Consequently, if the original function was mapped to a hybrid number system containing

N

digits, the number of digits must be increased to adequately represent the convolution result of the form (1).

The solution to this problem serves as the foundation for the proposed approach.

5. Results

5.1. Increasing the Number of Digits in the Hybrid Number System

Let us find a rule according to which a number represented in a hybrid number system with a certain number of digits can be written in a similar system with a larger number of digits.

The number 1 in an arbitrary encoding of the type under consideration is represented by the sum of idempotent elements (an example is formula (16)).

1 \equiv e_{1} + e_{2} + \dots + e_{N} m o d P

(25)

where the comparison is modulo the integer

P

Accordingly, when adding a unit to any number, a unit is added to each of the digits. But for each of the digits the addition is performed modulo the prime number

p_{i}

, which corresponds to the given digit. Hence,

u_{i} (n + 1) \equiv u_{i} (n) + 1 (p_{i})

(26)

Formula (26) allows, among other things, for an explicit switch from writing a number in a decimal number system to writing in a number system with a hybrid base. Namely,

u_{i} \equiv U m o d p_{i}

(27)

i.e., the value of each of the digits is directly the initial number

U

taken modulo

p_{i}

. Thus, formula (27) allows for the reduction of any original function given in the usual numerical form to the form corresponding to the hybrid number system.

The value of the additional digit can also be found using formula (27).

Supplement the hybrid number system formed by the prime numbers

p_{i}

i = 1, 2, . ., N

with one more digit corresponding to the prime number

p_{N + 1}

The number of idempotent elements appearing in the formula (8) will increase by one, thus

e_{i} = {\tilde{α}}_{i} p_{N + 1} \prod_{i \neq j}^{N} p_{j}; i = 1, \dots, N; e_{N + 1} = {\tilde{α}}_{N + 1} \prod_{1}^{N} p_{j}

(28)

In particular, it means that idempotent elements change, but in the formula of the form (8) the values of the components

u_{i}; i = 1, . ., N

remain unchanged.

The fact follows from formula (26). This formula is also applicable to calculate the value of the additional component

u_{N + 1}

Consequently, the operations of calculating partial convolutions in the fields

G F (p_{i}); i = 1, . ., N

remain unchanged when one more digit is added. Its value, as follows from formula (26) is

u_{N + 1} \equiv U m o d p_{N + 1}

(29)

This formula solves the problem of number representation when increasing the number of digits; however, the next question arises. It is necessary to reduce the result of calculations in the system with an increased number of digits to the original sampling scale, in which the considered functions take integer values in the range from 0 to

N_{1}

The most obvious way of reduction to the original scale is given by the formula

U_{o u t} (i) = ⌊\frac{1}{p_{N + 1}} \sum_{j} K (j) U_{i n} (i - j)⌋

(30)

where

⌊a⌋

is floor function symbol.

The formula is obtained from the following considerations.

According to the above assumptions, the functions under the convolution sign change in the range from 0 to

P

. The result of convolution calculation changes in the range from 0 to

P p_{N + 1}

. Therefore, to bring the sampling scale to the original one, the result of convolution calculation should be divided by

p_{N + 1}

However, as noted in Section 2, it is an urgent task to find a method that would allow for the obtainment of the same result as formula (30), but only by algebraic means, i.e., without using fractional numbers.

5.2. Formula for Converting the Result of Calculations Using Partial Convolutions to the Original Sampling Scale

The following lemma is valid.

For two natural numbers

w_{1}

and

w_{2}

w_{1} > w_{2}

and any natural n the following holds.

The value

q

q \equiv (w_{1} - w_{2}) ⌊\frac{n}{w_{1}}⌋ m o d w_{2}

(31)

where

⌊a⌋

is floor function symbol, can also be calculated as

q \equiv (n - g) m o d w_{2}, g \equiv n m o d w_{1}

(32)

The nature of the change in the value of

q

with increasing

n

for the special case

p_{1} = 19

p_{2} = 17

is illustrated by curve 1, Figure 1. The figure emphasizes that the value of q remains constant at each of the intervals corresponding to the number

p_{2} = 17

, i.e., it changes by a jump when the abscissa value becomes a multiple of 17.

This property allows us to prove the lemma under consideration.

Figure 1 also shows the dependence of

q + 3

, where q is calculated by formula (32). The dependence of

q

is presented with a shift by 3 so that the curves do not overlap.

It can be seen that if the artificial shift by 3 is not taken into account, the curves coincide.

Similar curves, but for the case

p_{1} = 11

p_{2} = 8

are presented in Figure 2. This figure also emphasizes that the value of

q

changes by a jump when the value of abscissa becomes a multiple of

p_{1} = 11

. This figure also clearly shows that the specific value of

q

also depends on the value of

p_{2}

, in particular, at the chosen values of

p_{1}

and

p_{2}

the considered function does not have a pronounced periodic character. In the future, this fact will be used to justify the choice of the relationship between the numbers

p_{1}

and

p_{2}

Let us return to the proof of the lemma formulated above.

There is an identity

n - n (m o d w_{1}) = ⌊\frac{n}{w_{1}}⌋ w_{1}

(33)

where the notation

m o d w_{1}

is written out explicitly, because the difference on the left side of (33) is calculated in the sense of the usual operations with integers.

The identity (33) follows from the fact that an arbitrary number

n

can be represented as the sum of the residue of division by an integer

w_{1}

of the integer part of the result of such division

n = n (m o d w_{1}) + ⌊\frac{n}{w_{1}}⌋ w_{1}

(34)

Provided that

w_{1} > w_{2}

, the following equality is also true

(⌊\frac{n}{w_{1}}⌋ w_{1}) \equiv ((w_{1} - w_{2}) ⌊\frac{n}{w_{1}}⌋) m o d w_{2}

(35)

Since the value

⌊\frac{n}{w_{1}}⌋ w_{2}

is known to be divisible by

w_{2}

Hence, applying the operation of taking modulo

w_{2}

to both parts of equality (33), we obtain

((w_{1} - w_{2}) ⌊\frac{n}{w_{1}}⌋) \equiv (n - n (m o d w_{1})) m o d w_{2}

(36)

The lemma is proved.

The most interesting case is when

w_{1} - w_{2} = 1

. Then the left part of equality (36) becomes equal to

⌊\frac{n}{w_{1}}⌋ (m o d w_{2})

Note that if we consider such a range of variation of

n

that

0 < n < w_{1} w_{2}

, then

0 < ⌊\frac{n}{w_{1}}⌋ < w_{2}

takes place. Hence,

⌊\frac{n}{w_{1}}⌋ (m o d w_{2}) = ⌊\frac{n}{w_{1}}⌋

(37)

Hence, in the considered case, the remainder from dividing

n

by the integer

w_{1}

is expressed as

⌊\frac{n}{w_{1}}⌋ = (n - n (m o d w_{1})) (m o d w_{2})

(38)

It can be seen that, in the considered particular case, the proved lemma allows for the reduction of the calculation of the value

⌊\frac{n}{w_{1}}⌋

to the operations of modulo taking.

This allows us to preserve the character of sampling of the scales of the “input” and “output” functions.

Let us obtain specific formulas that allow us to perform this operation.

The initial range of variation of the functions under consideration, whose values are represented in the form (8), is limited by the number

w_{2} = \prod_{1}^{N} p_{j}

To fulfill the condition ensuring the fulfilment of formula (38), the prime number

p_{N + 1}

corresponding to the additional digit must be given by the formula

p_{N + 1} = \prod_{1}^{N} p_{j} + 1

(39)

Examples of prime numbers

p_{N + 1}

represented in the form (39) are given in Table 2.

As Table 2 emphasizes, the using even relatively small numbers

p_{i}

gives possibility to ensure the computation of partial convolutions of practical interest. Indeed, the range of variation of the numbers represented in the form under consideration is quite large (it is bounded by the product

M p_{N + 1}

Proceeding from the above, we will consider the case when

w_{1} = p_{N + 1} = \prod_{1}^{N} p_{j} + 1; w_{2} = \prod_{1}^{N} p_{j}

(40)

To return to the original sampling scale, operation (38) must be applied to the result of the computation using partial convolutions, which is represented in the form.

\tilde{U} = e_{1} u_{1} + e_{2} u_{2} + \dots + e_{N} u_{N} + e_{N + 1} u_{N + 1}, m o d (w_{1} w_{2})

(41)

This notation, in particular, emphasizes that the integer values of

\tilde{U}

vary in the range

0 < \tilde{U} < w_{1} w_{2}

According to formula (33), for an arbitrary integer

s

it is true that

s (m o d w_{1} w_{2}) = s - ⌊\frac{s}{w_{1} w_{2}}⌋ w_{1} w_{2}

(42)

From where

(s (m o d w_{1} w_{2})) m o d w_{1} \equiv s m o d w_{1}

(43)

since

⌊\frac{s}{w_{1} w_{2}}⌋ w_{1} w_{2}

is divisible by

w_{1}

Similarly,

[s (m o d w_{1} w_{2})] (m o d w_{2}) = s (m o d w_{2})

(44)

There are only the values calculated by

m o d w_{2}

m o d w_{1}

in the right part of the formula (38).

Consequently, as follows from formulas (43) and (44), instead of the value

\tilde{U}

given by formula (41), i.e., providing for taking

m o d w_{1} w_{2}

, we can use the value

U

calculated according to the usual rules of addition and multiplication

U = p_{N + 1} \sum_{i} u_{i} {\tilde{α}}_{i} \prod_{j \neq 1}^{N} p_{j} + {\tilde{α}}_{N + 1} \prod_{1}^{N} p_{j} u_{N + 1}

(45)

Or, taking into account (40)

U = w_{1} (\sum_{i} u_{i} {\tilde{α}}_{i} \prod_{j \neq 1}^{N} p_{j}) + e_{N + 1} u_{N + 1}

(46)

Let us apply the

m o d w_{1}

operation to expression (32). Then

U (m o d w_{1}) \equiv (e_{N + 1} u_{N + 1}) (m o d w_{1}) = u_{N + 1}

(47)

where it is taken into account that

e_{i} \equiv 1 m o d p_{i}

(48)

The identity (48) follows directly from (25).

As a result, we obtain the following calculation formula, which solves the problem.

⌊\frac{U}{w_{1}}⌋ \equiv (\sum_{i} u_{i} {\tilde{α}}_{i} \prod_{j \neq 1}^{N} p_{j} - u_{N + 1}) m o d w_{2}

(49)

Let us consider how exactly the obtained formula can be applied to calculate digital convolutions.

6. Discussion

6.1. Justification of the Constructiveness of the Proposed Approach

The advantages of formula (49) over operations of the form (30) are as follows.

The calculations used in formula (49) use only integers. Consequently, the speed of execution of this kind of operation is obviously higher than the speed of execution of operations in which the division operation is used.

Moreover, all of these operations, in principle, can be realized by means of specific adders and multipliers modulo integers. Circuits of this kind of adders and multipliers are known [29,30,31,32] and they continue to be improved. It should also be taken into account that integrated circuits with configurable logic are now known too [52,53].

However, even disregarding the above considerations, the computation by formula (51) is known to have an advantage over operations such as (30). Indeed, the range of variation of each partial convolution in the computation in Galois fields

G F (p_{i})

is organised by the integer

p_{i}

and, hence, all summands appearing in formula (51) will not exceed

w_{1} = 1 + \prod_{1}^{N} p_{j}

. Let us underline, that actual range of the convolution computation (before reduction to the original scale) is

w_{1} w_{2} = (1 + \prod_{1}^{N} p_{j}) \prod_{1}^{N} p_{j}

This is what preserves the original sampling scale when computing the convolution.

Let us consider a concrete example illustrating this advantage.

We will use the ring of modulo 110 residue classes. The elements of such a ring are represented in the form

u \equiv 55 \cdot u_{1} + 66 \cdot u_{2} + 100 \cdot u_{3} m o d 110

(50)

where

u_{1} = 0, 1, u_{2} = 0, 1, \dots, 5, u_{3} = 0, 1, \dots, 10

(51)

The relation (12) is also fulfilled

55 + 66 + 100 \equiv 1 m o d 110

(52)

The prime number 11 is representable in the form (39):

11 = 1 + 2 \cdot 5

. Consequently, formula (50) can be considered as the result of increasing the number of digits in the number system corresponding to the ring of subtraction classes modulo 10. In this ring

u \equiv 5 \cdot u_{1} + 6 \cdot u_{2} m o d 10

(53)

where

u_{1} = 0, 1, u_{2} = 0, 1, \dots, 5,

(54)

It can also be written as

u \equiv 11 \cdot (5 \cdot u_{1} + 6 \cdot u_{2}) + 100 \cdot u_{3} m o d 110

(55)

Accordingly, the calculation formula (49) for the considered particular case takes the following form

⌊\frac{U}{w_{1}}⌋ = (5 \cdot u_{1} + 6 \cdot u_{2} - u_{3}) m o d 10

(56)

where

u_{i}

are the values of the digits of the numbers resulting from the calculation of partial convolutions in the number system corresponding to formula (50).

Let us apply the formula to calculate the convolution of model functions.

As the first of such functions, we will use the function

f_{1}

, shown in Figure 3, curve 1. As the second model function

f_{2}

we will use the rectangle function given by the relation

f_{2} (k) = \{\begin{matrix} 0, |k| > 5 \\ 1, |k| \leq 5 \end{matrix}

(57)

It can be seen that

f_{1}

models a function describing some noisy transient process. Its convolution with the function

f_{2}

corresponds to the moving average calculation, which provides noise filtering. If fractional values are allowed, the convolution of functions

f_{1}

and

f_{2}

is expressed by the usual moving average formula

〈f_{1} (k)〉 = \frac{1}{11} \sum_{i = k - 5}^{i = k + 5} f_{1} (k)

(58)

Formula (60) takes into account that function (59) is different from 0 at 11 clock cycles, including the clock with index 0. Accordingly, the summation starts at clock

k - 5

and ends at clock

k + 5

The calculations according to formula (58) are also presented in Figure 3, curve 2. It can be seen that the result of convolution calculation really gives a function describing the model transient process. The function obtained by applying the convolution operation in the form (58) is indeed quite smooth, i.e., this operation suppresses the noise present in the model function, as one would expect.

The presented simple example, among other things, clearly shows that the operation of reducing the convolution result to the original scale is indeed justified.

In many cases, this is also dictated by physical considerations.

Figure 4 also presents the smoothed model curve obtained from the original function using the moving average method (curve 1).

The same figure shows the result of calculations by formula (51) using partial convolutions.

Specifically, the formula was used

{〈f_{1}〉}_{0} = (5 \cdot 〈f_{1}^{1}〉 + 6 \cdot 〈f_{1}^{2}〉 - 〈f_{1}^{3}〉) m o d 10

(59)

where

〈f_{1}^{1}〉 = (\sum_{i = k - 5}^{i = k + 5} f_{1} (k), m o d 2), m o d 2

(60)

〈f_{1}^{2}〉 = (\sum_{i = k - 5}^{i = k + 5} f_{1} (k), m o d 5), m o d 5

(61)

〈f_{1}^{3}〉 = (\sum_{i = k - 5}^{i = k + 5} f_{1} (k), m o d 11), m o d 11

(62)

Formulas (60)–(62) correspond to calculations in Galois fields. The values of the original function taken modulo the corresponding prime number

p_{i}

are summed up, and then the operation of taking modulo

p_{i}

is applied to the summation result again.

It can be seen that the presented curves coincide with the accuracy up to rounding down, i.e., formula (49) really provides the desired result.

It can also be seen that curve 2, Figure 4, which approximates the smoothed curve with downward rounding accuracy, can indeed be derived from calculations performed in Galois fields.

We emphasize that Figure 4 shows that the result of calculations performed only in Galois fields (in particular, without using fractional values) coincides (with rounding accuracy) with the result obtained by formula (58).

Thus, the used model example serves as a clear demonstration of the adequacy of the proposed methodology of bringing the convolution operation to calculations in Galois fields.

The peculiarities of the methodology used are also vividly illustrated by Figure 5, which shows plots the results of intermediate calculations using formulas (60)–(62).

As can be seen in Figure 5, all the functions presented in this figure, vary within the limits corresponding to a particular prime number

p_{i}

Besides, the behavior of obtained functions is not ordered, yet the utilization of formula (51) enables the desired outcome to be achieved.

Accordingly, this figure serves as another visual illustration of the nature of the technique used. The result of the above convolution is computed using a set of functions, each of which varies within finite limits corresponding to a certain Galois field.

Further, all operations for computing partial convolutions in accordance with the above are de facto performed in Galois fields.

Consequently, the numerical analogue of the convolution theorem [15] applies to each of them.

These functions are direct analogues of the transfer functions used in classical linear circuit theory.

Formally, we can write at once

F [U_{o u t} (i)] = (\sum_{m} [K_{m} (i)] F [U_{m, i n} (i)] {\tilde{α}}_{m} \prod_{j \neq m}^{N} p_{j} - [K_{m + 1} (i)] F [U_{m + 1, i n} (i)]) (m o d w_{2})

(63)

where

F [f (i)]

is a notation for the Galois Field Fourier Transform.

Here, of course, there arises a nontrivial problem of finding an adequate basis representing an analogue of harmonic functions; however, the relation (63) already shows that the proposed approach in the future allows for finding transfer functions for systems of different nature described by digital convolution operations.

6.2. Some Perspectives on the Use of the Proposed Approach

Let us consider the most illustrative example of using the operations proposed in this paper. It is related to the analysis of time series of data, which arise in various scientific disciplines, for example, in meteorology [54], as well as in econometrics [55], etc.

Neural networks as well as various intelligent systems on this base are often used for analyzing such data series (including for forecasting purposes) [56,57,58]. In this respect, convolutional neural networks are obviously of particular interest, since the considered systems, as a rule, possess the property of invariance with respect to the time shift operation.

The proposed approach allows one to reduce any convolution operations to operations in terms of logical variables, which, among other things, is of interest from the point of view of revealing the true causal relations inherent in a particular system.

This example, however, is mainly for illustrative purposes.

Much more important seems to be the next step related to the application of the numerical convolution theorem [18].

Namely, if all operations corresponding to the convolution to the original discretization scale are reduced to convolutions in the sense of Galois fields, then it is acceptable to pass from the convolution to the analog of the transfer function (the Fourier–Galois image of the convolution is the product of the Fourier–Galois images of the functions under its sign).

In the future, this creates prerequisites for the formation of convolutional neural networks with predetermined properties (i.e., neural networks possessing a given analog of the transfer function).

This step, however, requires the formation of appropriate sets of orthogonal basis functions.

Besides, it is appropriate to emphasize that the interest to the practical use of multivalued logics at present is connected not only with the improvement of digital signal processing, but also with the improvement of AI. In particular, as shown in [59], the biological prototype of AI: human intelligence—is not reducible to binary logic. At the same time, there is no doubt that the processing of signals by the human brain also corresponds to the above-mentioned symmetry property. This opens additional perspectives for using the results obtained in this work.

7. Conclusions

Thus, a method that allows us to reduce convolution operation to calculations modulo integer is proposed. In other words, the proposed approach allows us to bring the operation of reduced convolution computation to computations in Galois fields.

In this case, the number of discrete levels of functions under the convolution sign coincides with the number of discrete levels corresponding to the result of the convolution operation.

It makes sense to treat the convolution operation, in which the discretization character of the initial and resulting functions is preserved, as a reduced convolution.

The constructiveness of this approach is demonstrated on a concrete model example.

In constructing this method, RNS-based computations are considered as a special case of computations in finite algebraic rings, which creates prerequisites for its use in the transition to algebraic rings of different varieties.

Further development of this approach implies, among other things, the use of functions taking values corresponding to variables of multivalued logic.

The results are also of interest in terms of creating convolutional neural networks with predetermined properties.

Author Contributions

Conceptualization, Y.V. and I.S.; methodology, I.S.; software, A.K.; validation, Y.V.; formal analysis, D.M.; investigation, A.K.; resources, Y.V. and D.M.; data curation, Y.V.; writing—original draft preparation, I.S.; writing—review and editing, I.S. and Y.V.; visualization A.K. and D.M.; supervision, Y.V.; project administration, Y.V.; funding acquisition, Y.V., I.S. and D.M. All authors have read and agreed to the published version of the manuscript.

Funding

This research has been funded by the Science Committee of the Ministry of Science and Higher Education of the Republic of Kazakhstan (Grant No. AP14870281).

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

The original contributions presented in the study are included in the article, further inquiries can be directed to the corresponding author/s.

Conflicts of Interest

The authors declare no conflicts of interest.

References

Goodman, J.W. Introduction to Fourier Optics, 3rd ed.; Roberts & Co: Englewood, CO, USA, 2005; p. 491. [Google Scholar]
Tyson, R.K. Principles and Applications of Fourier Optics; IOP Expanding Physics; IOP Publishing: Bristol, UK, 2014; p. 117. [Google Scholar]
Darlington, S. A History of Network Synthesis and Filter Theory for Circuits Composed of Resistors, Inductors, and Capacitors. IEEE Trans. Circuits Syst. 1984, 31, 3–13. [Google Scholar] [CrossRef]
Izadian, A. Fundamentals of Modern Electric Circuit Analysis and Filter Synthesis: A Transfer Function Approach; Springer International Publishing: Cham, Switzerland, 2019; p. 115. [Google Scholar] [CrossRef]
Gu, J.; Wang, Z.; Kuen, J.; Ma, L.; Shahroudy, A.; Shuai, B.; Liu, T.; Wang, X.; Wang, G.; Cai, J.; et al. Recent Advances in Convolutional Neural Networks. Pattern Recognit. 2018, 77, 354–377. [Google Scholar] [CrossRef]
Aghdam, H.H.; Heravi, J.E. Guide to Convolutional Neural Networks; Springer International Publishing: Cham, Switzerland, 2017; p. 282. [Google Scholar] [CrossRef]
Krizhevsky, A.; Sutskever, I.; Hinton, G.E. Imagenet classification with deep convolutional neural networks. Adv. Neural Inf. Process. Syst. 2012, 25, 1097–1105. [Google Scholar] [CrossRef]
Monteiro, A.; Oliveira, M.; Oliveira, R.; Silva, T. Embedded Application of Convolutional Neural Networks on Raspberry Pi for SHM. Electron. Lett. 2018, 54, 680–682. [Google Scholar] [CrossRef]
Shichijo, S.; Nomura, S.; Aoyama, K.; Nishikawa, Y.; Miura, M.; Shinagawa, T.; Takiyama, H.; Tanimoto, T.; Ishihara, S.; Matsuo, K.; et al. Application of Convolutional Neural Networks in the Diagnosis of Helicobacter Pylori Infection Based on Endoscopic Images. EBioMedicine 2017, 25, 106–111. [Google Scholar] [CrossRef] [PubMed]
Howard, A.G.; Zhu, M.; Chen, B.; Kalenichenko, D.; Wang, W.; Weyand, T.; Andreetto, M.; Adam, H. MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications. arXiv 2017, arXiv:1704.04861. [Google Scholar] [CrossRef]
Ketkar, N.; Moolayil, J. Convolutional Neural Networks. In Deep Learning with Python; Apress: Berkeley, CA, USA, 2021; pp. 197–242. [Google Scholar] [CrossRef]
Zhang, C.; Zhao, H.; Cao, M. Research on General Text Classification Model Integrating Character-Level Attention and Multi-Scale Features. In Proceedings of the 2021 10th International Conference on Computing and Pattern Recognition, Shanghai, China, 15–17 October 2021; pp. 183–187. [Google Scholar] [CrossRef]
McLaren, M.; Lei, Y.; Scheffer, N.; Ferrer, L. Application of Convolutional Neural Networks to Speaker Recognition in Noisy Conditions. In Proceedings of the Fifteenth Annual Conference of the International Speech Communication Association, Interspeech 2014, Singapore, 14–18 September 2014; pp. 686–690. [Google Scholar] [CrossRef]
Moldakhan, I.; Matrassulova, D.K.; Shaltykova, D.B.; Suleimenov, I.E. Some Advantages of Non-Binary Galois Fields for Digital Signal Processing. Indones. J. Electr. Eng. Comput. Sci. 2021, 23, 871. [Google Scholar] [CrossRef]
Vitulyova, E.S.; Matrassulova, D.K.; Suleimenov, I.E. New Application of Non-Binary Galois Fields Fourier Transform: Digital Analog of Convolution Theorem. Indones. J. Electr. Eng. Comput. Sci. 2021, 23, 1718. [Google Scholar] [CrossRef]
Suleimenov, I.E.; Vitulyova, Y.S.; Matrassulova, D.K. Features of Digital Signal Processing Algorithms Using Galois Fields GF(2n+1). PLoS ONE. 2023, 18, e0293294. [Google Scholar] [CrossRef] [PubMed]
Vitulyova, E.S.; Matrassulova, D.K.; Suleimenov, I.E. Construction of generalized Rademacher functions in terms of ternary logic: Solving the problem of visibility of using Galois fields for digital signal processing. Int. J. Electron. Telecommun. 2022, 237–244. [Google Scholar] [CrossRef]
Matrassulova, D.K.; Vitulyova, Y.S.; Konshin, S.V.; Suleimenov, I.E. Algebraic Fields and Rings as a Digital Signal Processing Tool. Indones. J. Electr. Eng. Comput. Sci. 2022, 29, 206. [Google Scholar] [CrossRef]
Kuo, Y.-M.; Garcia-Herrero, F.; Ruano, O.; Maestro, J.A. RISC-V Galois Field ISA Extension for Non-Binary Error-Correction Codes and Classical and Post-Quantum Cryptography. IEEE Trans. Comput. 2022, 72, 682–692. [Google Scholar] [CrossRef]
Nazarov, L.E. Investigation of Noise Immunity of Optimal Symbol Reception of Frequency-Efficient Signals with Correction Coding in Non-Binary Galois Fields. J. Commun. Technol. Electron. 2023, 68, 960–965. [Google Scholar] [CrossRef]
Jagadeesh, H.; Joshi, R.; Rao, M. Group Secret-Key Generation Using Algebraic Rings in Wireless Networks. IEEE Trans. Veh. Technol. 2021, 70, 1538–1553. [Google Scholar] [CrossRef]
Alcayde, A.; Ventura, J.; Montoya, F.G. Hypercomplex Techniques in Signal and Image Processing Using Network Graph Theory: Identifying Core Research Directions [Hypercomplex Signal and Image Processing]. IEEE Signal Process. Mag. 2024, 41, 14–28. [Google Scholar] [CrossRef]
Suleimenov, I.E.; Vitulyova, Y.S.; Kabdushev, S.B.; Bakirov, A.S. Improving the Efficiency of Using Multivalued Logic Tools. Sci Rep. 2023, 13, 1108. [Google Scholar] [CrossRef]
Suleimenov, I.E.; Vitulyova, Y.S.; Kabdushev, S.B.; Bakirov, A.S. Improving the Efficiency of Using Multivalued Logic Tools: Application of Algebraic Rings. Sci Rep. 2023, 13, 22021. [Google Scholar] [CrossRef] [PubMed]
Tynymbayev, S.; Berdibayev, R.S.; Omar, T.; Gnatyuk, S.A.; Namazbayev, T.A.; Adilbekkyzy, S. Devices for Multiplying modulo Numbers with Analysis of the Lower Bits of the Multiplier. Bull. Natl. Acad. Sci. Repub. Kazakhstan 2019, 4, 38–45. [Google Scholar] [CrossRef]
Sayed-Ahmed, A.; Große, D.; Kühne, U.; Soeken, M.; Drechsler, R. Formal verification of integer multipliers by combining Gröbner basis with logic reduction. In Proceedings of the 2016 Design, Automation & Test in Europe Conference & Exhibition (DATE), Dresden, Germany, 14–18 March 2016; pp. 1048–1053. [Google Scholar]
Munoz-Coreas, E.; Thapliyal, H. Quantum Circuit Design of a T-Count Optimized Integer Multiplier. IEEE Trans. Comput. 2019, 68, 729–739. [Google Scholar] [CrossRef]
Sousa, L.; Antao, S.; Martins, P. Combining Residue Arithmetic to Design Efficient Cryptographic Circuits and Systems. IEEE Circuits Syst. Mag. 2016, 16, 6–32. [Google Scholar] [CrossRef]
Hidenori, E.; Kiyoto, K.; Denki, C. Circuit for Modulo Multiplication and Exponentiation Arithmetic. Patent EP0801345B1, 16 October 2002. [Google Scholar]
Lablans, P. Multi-Value Digital Calculating Circuits, Including Multipliers. Patent US20060031278A1, 9 February 2006. [Google Scholar]
Irkhin, V.P.; Obukhov, A.N.; Gul’bin, S.S. G06F 7/49. Device for Modulo Addition and Subtraction of Numbers. Patent RU2145112C1, 27 January 2000. [Google Scholar]
Pisek, E.; Henige, T.M. Method and Apparatus for Efficient Modulo Multiplication. U.S. Patent 2009/0144353 A1, 4 June 2009. [Google Scholar]
Nakahara, H.; Sasao, T. A Deep Convolutional Neural Network Based on Nested Residue Number System. In Proceedings of the 2015 25th International Conference on Field Programmable Logic and Applications (FPL), London, UK, 2–4 September 2015; pp. 1–6. [Google Scholar] [CrossRef]
Valueva, M.V.; Nagornov, N.N.; Lyakhov, P.A.; Valuev, G.V.; Chervyakov, N.I. Application of the Residue Number System to Reduce Hardware Costs of the Convolutional Neural Network Implementation. Math. Comput. Simul. 2020, 177, 232–243. [Google Scholar] [CrossRef]
Jenkins, W.; Leon, B. The Use of Residue Number Systems in the Design of Finite Impulse Response Digital Filters. IEEE Trans. Circuits Syst. 1977, 24, 191–201. [Google Scholar] [CrossRef]
Aithal, G.; Bhat, K.N.H.; Sripathi, U. Implementation of Stream Cipher System Based on Representation of Integers in Residue Number System. In Proceedings of the 2010 IEEE 2nd International Advance Computing Conference (IACC), Patiala, India, 19–20 February 2010; pp. 210–217. [Google Scholar] [CrossRef]
Dubey, A.; Ahmad, A.; Pasha, M.A.; Cammarota, R.; Aysu, A. ModuloNET: Neural Networks Meet Modular Arithmetic for Efficient Hardware Masking. ACR Trans. Cryptogr. Hardw. Embed. Syst. 2021, 506–556. [Google Scholar] [CrossRef]
Yassine, H.M. Fast Arithmetic Based on Residue Number System Architectures. In Proceedings of the 1991 IEEE International Symposium on Circuits and Systems (ISCAS), Singapore, 11–14 June 1991; Volume 5, pp. 2947–2950. [Google Scholar] [CrossRef]
Bos, J.W.; Friedberger, S. Fast Arithmetic Modulo 2^x p^y ± 1. In Proceedings of the 2017 IEEE 24th Symposium on Computer Arithmetic (ARITH), London, UK, 24–26 July 2017; pp. 148–155. [Google Scholar]
Torabi, Z.; Jaberipur, G.; Belghadr, A. Fast Division in the Residue Number System {2ⁿ+ 1, 2ⁿ, 2ⁿ-1} Based on Shortcut Mixed Radix Conversion. Comput. Electr. Eng. 2020, 83, 106571. [Google Scholar] [CrossRef]
Markov, V.T.; Mikhalev, A.V.; Nechaev, A.A. Nonassociative Algebraic Structures in Cryptography and Coding. J. Math. Sci. 2020, 245, 178–196. [Google Scholar] [CrossRef]
Sanam, N.; Ali, A.; Shah, T.; Farooq, G. Non-Associative Algebra Redesigning Block Cipher with Color Image Encryption. Comput. Mater. Contin. 2021, 67, 1–21. [Google Scholar] [CrossRef]
Liu, P.; Pan, Z.; Lei, J. Parameter Identification of Reed-Solomon Codes Based on Probability Statistics and Galois Field Fourier Transform. IEEE Access 2019, 7, 33619–33630. [Google Scholar] [CrossRef]
Huang, Q.; Tang, L.; He, S.; Xiong, Z.; Wang, Z. Low-Complexity Encoding of Quasi-Cyclic Codes Based on Galois Fourier Transform. IEEE Trans. Commun. 2014, 62, 1757–1767. [Google Scholar] [CrossRef]
Hazzazi, M.M.; Attuluri, S.; Bassfar, Z.; Joshi, K. A Novel Cipher-Based Data Encryption with Galois Field Theory. Sensors 2023, 23, 3287. [Google Scholar] [CrossRef]
Asif, M.; Asamoah, J.K.K.; Hazzazi, M.M.; Alharbi, A.R.; Ashraf, M.U.; Alghamdi, A.M. A Novel Image Encryption Technique Based on Cyclic Codes over Galois Field. Comput. Intell. Neurosci. 2022, 2022, 1912603. [Google Scholar] [CrossRef]
Hiasat, A.; Sousa, L. On the Design of RNS Inter-Modulo Processing Units for the Arithmetic-Friendly Moduli Sets {2ⁿ ^{+ k}, 2ⁿ − 1, 2ⁿ ⁺¹ − 1}. Comput. J. 2019, 62, 292–300. [Google Scholar] [CrossRef]
Ha, J.; Kim, S.; Choi, W.; Lee, J.; Moon, D.; Yoon, H.; Cho, J. Masta: An HE-Friendly Cipher Using Modular Arithmetic. IEEE Access 2020, 8, 194741–194751. [Google Scholar] [CrossRef]
Hu, K.; Zhang, D.; Xia, M. CDUNet: Cloud Detection UNet for Remote Sensing Imagery. Remote Sens. 2021, 13, 4533. [Google Scholar] [CrossRef]
Li, Z.; Shen, H.; Weng, Q.; Zhang, Y.; Dou, P.; Zhang, L. Cloud and Cloud Shadow Detection for Optical Satellite Imagery: Features, Algorithms, Validation, and Prospects. ISPRS J. Photogramm. Remote Sens. 2022, 188, 89–108. [Google Scholar] [CrossRef]
Suleimenov, I.; Vitulyova, Y.; Bakirov, A. Hybrid Number Systems: Application for Calculations in Galois Fields. In Proceedings of the 2022 3rd Asia Conference on Computers and Communications (ACCC), Shanghai, China, 16–18 December 2022; pp. 126–130. [Google Scholar] [CrossRef]
Sadeghi, A.; Shiri, N.; Rafiee, M.; Rahimi, P. A Low-Power Pseudo-Dynamic Full Adder Cell for Image Addition. Comput. Electr. Eng. 2020, 87, 106787. [Google Scholar] [CrossRef]
Özkilbaç, B. Implementation and Design of 32 Bit Floating-Point ALU on a Hybrid FPGA-ARM Platform. J. Brill. Eng. 2019, 1, 26–32. [Google Scholar] [CrossRef]
Yan, B.; Chan, P.W.; Li, Q.; He, Y.; Shu, Z. Dynamic Analysis of Meteorological Time Series in Hong Kong: A Nonlinear Perspective. Intl J. Climatol. 2021, 41, 4920–4932. [Google Scholar] [CrossRef]
Nonejad, N. An overview of dynamic model averaging techniques in time-series econometrics. J. Econ. Surv. 2021, 35, 566–614. [Google Scholar] [CrossRef]
Kumar, G.; Singh, U.P.; Jain, S. Hybrid Evolutionary Intelligent System and Hybrid Time Series Econometric Model for Stock Price Forecasting. Int. J. Intell. Syst. 2021, 36, 4902–4935. [Google Scholar] [CrossRef]
Chatterjee, A.; Bhowmick, H.; Sen, J. Stock Price Prediction Using Time Series, Econometric, Machine Learning, and Deep Learning Models. In Proceedings of the 2021 IEEE Mysore Sub Section International Conference (MysuruCon), Mysuru, India, 16–17 October 2021; pp. 289–296. [Google Scholar] [CrossRef]
Rahman, M.; Shakeri, M.; Khatun, F.; Tiong, S.K.; Alkahtani, A.A.; Samsudin, N.A.; Amin, N.; Pasupuleti, J.; Hasan, M.K. A Comprehensive Study and Performance Analysis of Deep Neural Network-Based Approaches in Wind Time-Series Forecasting. J. Reliab. Intell. Environ. 2023, 9, 183–200. [Google Scholar] [CrossRef]
Gabrielyan, O.A.; Vitulyova, E.; Suleimenov, I.E. Multi-valued logics as an advanced basis for artificial intelligence. Wisdom 2022, 1, 170–181. [Google Scholar] [CrossRef]

Figure 1. Illustration of the lemma proof;

w_{1} = 19

w_{2} = 17

, curve 1 (blue)—calculations of q by formula (31), i.e., through the operation of calculating the integer part of the number, curve 2 (red)—values of the sum q + 3, where q is calculated by formula (32), i.e., using only modulo operations.

Figure 1. Illustration of the lemma proof;

w_{1} = 19

w_{2} = 17

Figure 2. Illustration of the lemma proof;

w_{1} = 11

w_{2} = 9

Figure 2. Illustration of the lemma proof;

w_{1} = 11

w_{2} = 9

Figure 3. Model function

f_{1}

(curve 1, red dots) and the result of applying the moving average calculation operation to it (curve 2, green dots).

Figure 3. Model function

f_{1}

(curve 1, red dots) and the result of applying the moving average calculation operation to it (curve 2, green dots).

Figure 4. Model function

f_{1}

smoothed using the moving average method (curve 1, green dots) and the result of calculating the analogue using formula (51), curve 2, red dots.

Figure 4. Model function

f_{1}

smoothed using the moving average method (curve 1, green dots) and the result of calculating the analogue using formula (51), curve 2, red dots.

Figure 5. Plots of partial convolutions for three digits of number representation modulo 110; (a–c) correspond to partial convolutions in Galois fields

G F (2)

G F (5)

, and

G F (11)

, respectively.

Figure 5. Plots of partial convolutions for three digits of number representation modulo 110; (a–c) correspond to partial convolutions in Galois fields

G F (2)

G F (5)

, and

G F (11)

, respectively.

Table 1. Classification of related works.

Problem Being Discussed	References
Fast arithmetic, Systems of Residual Classes	[37,38,39,40]
Use of non-trivial algebraic structures in information technology	[18,41,42]
Convolutional neural networks	[5,6,7,8,9,10,11,12,13]
Use of Galois fields in information technology	[43,44]
Using Galois fields in the aspect of multivalued logics	[23,24]
Chips with reconfigurable logic	[45,46,47,48]
Applications of computing based on chips with reconfigurable logic structure	[49,50]

Table 2. Multipliers

p_{i}

giving examples of numbers of the form (39). (The symbol “-” means that this multiplier is not included in M).

Table 2. Multipliers

p_{i}

giving examples of numbers of the form (39). (The symbol “-” means that this multiplier is not included in M).

$p_{4}$	$p_{3}$	$p_{2}$	$p_{1}$	$M = p_{1} p_{2} \dots p_{s}$	$p_{N + 1}$	$M p_{N + 1}$
-	-	3	2	6	7	42
-	-	5	2	10	11	110
-	-	11	2	22	23	506
-	5	3	2	30	31	930
-	7	3	2	42	43	1806
-	11	3	2	66	67	4422
-	7	5	2	70	71	4970
-	17	3	2	102	103	10,506
-	13	5	2	130	131	17,030
-	19	5	2	190	191	36,290
7	5	3	2	210	211	44,310
-	31	5	2	310	311	96,410
11	5	3	2	330	331	109,230
-	19	11	2	418	419	175,142

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

© 2024 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Suleimenov, I.; Kadyrzhan, A.; Matrassulova, D.; Vitulyova, Y. Peculiarities of Applying Partial Convolutions to the Computation of Reduced Numerical Convolutions. Appl. Sci. 2024, 14, 6388. https://doi.org/10.3390/app14146388

AMA Style

Suleimenov I, Kadyrzhan A, Matrassulova D, Vitulyova Y. Peculiarities of Applying Partial Convolutions to the Computation of Reduced Numerical Convolutions. Applied Sciences. 2024; 14(14):6388. https://doi.org/10.3390/app14146388

Chicago/Turabian Style

Suleimenov, Ibragim, Aruzhan Kadyrzhan, Dinara Matrassulova, and Yelizaveta Vitulyova. 2024. "Peculiarities of Applying Partial Convolutions to the Computation of Reduced Numerical Convolutions" Applied Sciences 14, no. 14: 6388. https://doi.org/10.3390/app14146388

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Peculiarities of Applying Partial Convolutions to the Computation of Reduced Numerical Convolutions

Abstract

1. Introduction

2. Related Works

3. Background Section

4. Methods

4.1. Representation of Integer Computations in Terms of Finite Algebraic Rings

4.2. Partial Convolutions

5. Results

5.1. Increasing the Number of Digits in the Hybrid Number System

5.2. Formula for Converting the Result of Calculations Using Partial Convolutions to the Original Sampling Scale

6. Discussion

6.1. Justification of the Constructiveness of the Proposed Approach

6.2. Some Perspectives on the Use of the Proposed Approach

7. Conclusions

Author Contributions

Funding

Institutional Review Board Statement

Informed Consent Statement

Data Availability Statement

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI