Varieties of Systems of DEF Generated by Isomorphic Transformations
ANATOLY BELETSKY, DMYTRO POLTORATSKYI
Department of Electronics,
National Aviation University,
1, Pr. Lyubomyra Guzara, Kyiv,
UKRAINE
Abstract: - Despite more than a century of origin and development, the theory of discrete exponential function
(DEF) systems continues to attract the attention of mathematicians and application specialists in various fields
of science and technology. One of the most successful applications of the DEF systems is the spectral
processing of discrete signals based on fast Fourier transform (FFT) algorithms in the DEF bases. The
construction of structural schemes of FFT algorithms is preceded, as a rule, by the factorization of the DEF
matrices. The main problem encountered when factorizing DEF matrices is that the elements of such matrices
are the degrees of phase multipliers, which are complex-valued quantities. In this connection, the computational
complexity of factorization of DEF matrices may be too large, especially when the number of components of
the matrix order decomposition is large. In this paper, we propose a relatively simple method of mutually
unambiguous transition from complex-valued DEF matrices to matrices whose elements are natural numbers
equal to the degree indices of phase multipliers in the canonical DEF matrices. Through this bijective
transformation, the factorization of DEF matrices becomes significantly more manageable, streamlining the
overall process of factorization.
Key-Words: - discrete exponential functions, mother and daughter systems of DEF, isomorphic
transformations, factorization of DEF matrices, synthesis of DEF systems, interrelation of
DEF systems.
Received: July 27, 2023. Revised: October 25, 2023. Accepted: November 7, 2023. Published: November 29, 2023.
1 Introduction
Discrete exponential function (DEF) systems are a
fundamental concept that plays a crucial role in
signal and data processing and analysis. Various
scientific and technological domains, including
telecommunications, medical diagnostics, radio
communications, geophysics, environmental
research, and many others, widely use DEF systems.
The genuinely revolutionary role of the DEF
systems played in the formation and development of
the theory and practical applications of the discrete
Fourier transform (DFT), which had a significant
influence on the formation of algorithmic and
software of modern information processing tools.
The initial steps in developing the DEF algorithms
were at the dawn of the XIX century. The first
mentions of the DFT systems appeared in the, [1],
published in 1801. In his dissertation, Gauss
outlines a method for computing the DFT, although
he did not use that name. Another important work
was a paper by, [2], published in 1815. This paper
developed a method similar to the DFT and was
used to solve problems involving probability.
Undoubtedly, the author made an invaluable
contribution to the formation of the Fourier
transform theory of the theory himself (20s of the
XIX century). However, he concentrated his
attention on the continuous transformation.
The first references to DEF systems appeared in
the works, [3], [4]. In the modern sense, the DEF
algorithm was formulated and optimized to the Fast
Fourier Transform (FFT) jointly by, [5]. This work
remains one of the key publications in FFT and
eventually became known as the Cooley-Tukey
Algorithm. Among the numerous areas of
applications of the FFT algorithms, let us highlight
spectral signal processing, [6], [7], [8], [9],
computer vision, [10], data transmission in
telecommunication systems, [11], medical
information processing, [12], time series analysis,
[13], quantum computing, [14], geophysics and
geodesy, [15], and many others.
Note that the FFT algorithm applies only to
such discrete sequences of samples of a continuous
signal whose sampling volume, denoted by N, is a
composite number. The simplicity of the FFT tree
becomes particularly pronounced when N is a power
of two, denoted as
2n
N
, where n is a natural
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.99
Anatoly Beletsky, Dmytro Poltoratskyi
E-ISSN: 2224-2880
904
Volume 22, 2023
number. Building an FFT tree in the DEF basis for a
composite N not equal to degree two can be
computationally challenging, especially for large
dimensions N. One effective strategy to solve this
challenge is to pre-factorize the DEF matrices.
However, because the elements of the DEF
matrices are complex-valued quantities, the positive
effect of the factorization may not be so impressive.
The primary purpose of this study is to develop
a method of mutually unambiguous transition from
complex-valued representations of the DEF matrices
to matrices whose elements are natural numbers.
Achievement of this goal will considerably simplify
both the construction of FFT trees in the DEF bases
and the factorization of the DEF matrices of large
orders.
2 Basic Relations
The non-canonical system of the DEF of N-order is a
matrix
( , ) kt
Ne k t E
,
, 0, 1k t N
, (1)
in which
( , )e k t
are basis functions of the k-order of
the discrete argument (time) t, and
2
exp jN
(2)
— phase multiplier (PM).
Taking into account the periodicity of FM (2),
you can reduce the matrix (1) to the canonical form
()
( , ) N
kt
Ne k t E
,
, 0, 1k t N
, (3)
where
()
m
x
is a modular arithmetic function equal
to the value of the number
x
modulo
m
.
Using the relation (3), let us compose, as an
example, the six-order canonical DEF matrix
0 0 0 0 0 0
0 1 2 3 4 5
024024
60 3 0 3 0 3
042042
0 5 4 3 2 1
0 1 2 3 4 5
0
1
2.
3
4
5
t
k
E
(4)
We will number the rows and columns of the
matrices (and the numbering of the elements of
basic functions) by natural numbers starting from
zero.
From the complex-valued matrix (4), we easily
pass to a matrix with integer non-negative elements.
For this purpose, it is enough to keep in its rows
only the values of the degree indices of the phase
multipliers. As a result of the proposed reduction,
we arrive at the matrix
(1)
6
0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 1 2 3 4 5
2 024024
( , ) ,
3 0 3 0 3 0 3
4 042042
5 0 5 4 3 2 1
t
e k t
k
E
(5)
which is isomorphic to the matrix (4). The
isomorphism arises from the bijective mapping
qq
, where q is a natural number. Elementary
analysis of the matrix (5) leads to the relation
( , ) ( ) , , 0, 1
N
e k t kt k t N
, (6)
which we will call the generalized basis of the DEF
in the isomorphic image space.
3 Synthesis of Symmetric DEF
Systems
The synthesis of symmetric DEF systems represents
an essential aspect of the theory and practice of
signal processing and control systems. Discrete
exponential functions are widely used to analyze
and model dynamic systems. Symmetric DEF
systems have specific mathematical properties that
make them particularly attractive for several
applications. Symmetry in the context of DEF
systems means that their characteristics are
preserved for particular operations, such as
reflection or rotation. This property facilitates the
analysis and control of such systems, making them
more predictable and stable.
You can obtain symmetric DEF systems
through specific arrangements of matrix row
permutations (6), which we will hereafter refer to as
the mother matrices. Let us take into account that
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.99
Anatoly Beletsky, Dmytro Poltoratskyi
E-ISSN: 2224-2880
905
Volume 22, 2023
you cannot rearrange the upper row of the mother
matrix (the zero-order basis function) to any other
row to any other row since it leads to the loss of
symmetry of the matrix. Consequently, there are (N-
1)! different ways of permutations of basic functions
( , )e k t
, some of which (let us denote their number
by
N
L
) lead to the formation of the symmetric DEF
systems.
Let us introduce some simple terminological
definitions applicable to further presentation of the
material.
Definition 1. A primitive is called such a basis
function
( , )e k t
of an N-order DEF matrix in the
isomorphic image space that contains a complete
system of deductions modulo N, i.e., a set of non-
negative integers from zero to N-1.
For example, the basic functions
(1, )et
(5, )et
are primitive in the matrix (5).
Definition 2. The basis function
( , )e k t
, located
in the first line of the DEF system, will be called the
forming (generating) function of the system.
The constitutive function of the DEF mother
system is the function
(1, )et
.
Definition 3. All symmetric DEF systems that
are not mother systems will be called daughter DEF
systems.
The definitions formulated above form the basis
of the following fundamental proposition.
Statement 1. Only primitive basis functions can
serve as the forming functions of the symmetric
systems DEF.
Proof. Consider the mother system of the fourth-
order DEF, whose matrix in the image space has the
form
(1)
4
0 1 2 3
0 0 0 0 0
1 0 1 2 3 .
2 0 2 0 2
3 0 3 2 1
t
k
E
(7)
Let us illustrate the outcomes obtained when we
try to apply as a forming basis function the only one
of the three non-zero functions of the matrix (7) that
is not primitive, i.e., the function
(2, ) (0, 2, 0, 2).et
Due to the inherent symmetry of
matrices, where the elements in columns align with
those in the corresponding rows, we can deduce the
following intermediate result
0 1 2 3
0 0000
1 0 2 0 2 .
2 0 0
3 0 2
t
k
The line highlighted by the arrow does not
correspond to any of the basic functions of the
matrix (7). Any basis function of N-order that is not
primitive leads to a similar situation (two zeros in
any row of the matrix), which completes the proof
of Statement 1.
We give the following statement (quite obvious
and not requiring proof) to support the
systematization of the presentation of the material.
Statement 2: Any primitive basis function of the
DEF system placed in the first row of the
synthesizable matrix, uniquely determines the order
of the basic functions placed in all other rows of the
DEF matrix.
Let us illustrate the application of Statement 2
by using the synthesis of the six-order daughter
matrix of the DEF. Let us choose for this purpose
from the mother system (5) the primitive basis
function
(5, ) (0,5, 4, 3, 2,1)et
. Placing in the
second row and the second column of the matrix (5)
instead of the elements of the function
(1, )et
the
elements of the function
(5, )et
, we obtain such an
incomplete matrix
(2)
6
0 1 2 3 4 5
0 000000
1 0 5 4 3 2 1
2 0 4 .
3 0 3
4 0 2
5 0 1
t
k
E
(8)
Filling the empty cells of the matrix
(2)
6
E
in (8)
becomes a trivial problem, allowing two solution
variants. In the first of them, you replace the
underdetermined rows of the daughter matrices with
the corresponding rows of the mother system. The
second variant assumes the direct calculation of
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.99
Anatoly Beletsky, Dmytro Poltoratskyi
E-ISSN: 2224-2880
906
Volume 22, 2023
missing elements
,kt
a
in the rows of the daughter
matrix by the formula
,()
k t N
a kt
,
2, 1tN
,
where k is the value of the right element of the
row of the daughter matrix.
And to conclude the paragraph, we will also
conclude with an unproven statement
Statement 3. The number
N
L
of the symmetric
DEF systems coincides with the value of the Euler
function from the order N of the DEF matrices, i.e.,
( ).
N
LN
4 Interrelation of DEF Systems
The totality of mother and daughter symmetric
systems of the DEF of N-order are structurally
interconnected. That is, if the structural form of at
least one DEF system (matrix) is known, we
calculate the structural forms of the other systems
uniquely.
Definition 4. By the structural form of the DEF
systems, we will understand the sequence of order
basis functions in the DEF matrices.
A simple relation defines the relationship
between the mother system of the DEF and the
daughter system. Let
a
be the value of the first
element of the first-order basis function of the DEF
daughter system and let
( , )e k t
and
( , )d k t
be the
basis functions of the mother and daughter systems,
respectively. Then, as empirically established,
( , ) (( ) , )
N
d k t e ak t
,
, 0, 1k t N
,
and the coefficient
1a
is mutually simple with N.
In total, there are only three groups of the DEF
systems consisting of a mother and one daughter
matrix. These are the systems whose order N is 3, 4,
and 6, and the numbers
a
correspond to the values
2, 3, and 5 respectively, i.e.,
1aN
.
If the order N of the systems DEF is a prime
number, then N-1 symmetric DEF matrices
correspond to each. In particular, Fig. 1 shows the
transition algorithm between the DEF systems of
simple seven-order
Fig. 1: Interconnection graph of the seven-order
DEF systems
Fig. 2 shows the interconnection of composite-
order DEF systems
9N
.
Fig. 2: Interconnection graph of the ninth-order DEF
systems
Similarly, you can establish the interconnection
of the DEF systems of arbitrary order.
5 Factorization of the DEF Matrices
The necessity to perform the procedure of
factorization of the DEF matrices is related to the
problem of constructing algorithms (structural
schemes) of FFT on a given basis. Only matrices
whose order N is a composite number can be
factorized, i.e., provided that
1
i
kl
i
i
Nn
, (9)
where
i
n
are prime numbers, k is the number of
different prime factors forming the composite
number N, and the degree
i
l
are natural numbers
that determine the multiplicity of the prime numbers
i
n
.
The representation (9) corresponds to the
factorized DEF matrix of N-order
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.99
Anatoly Beletsky, Dmytro Poltoratskyi
E-ISSN: 2224-2880
907
Volume 22, 2023
1
k
Ni
i
EF
. (10)
Matrices
i
F
by analogy with simple numbers we
will call simple matrices.
A remarkable feature of
i
F
matrices is that they
include many zero elements. Such matrices are
called strongly sparse matrices.
Definition 5. To strongly sparse matrices
i
F
,
generated by factorization of the DEF matrices in
isomorphic space and corresponding to prime
numbers
i
n
, we will refer to matrices, each row, and
each column, which contain
i
n
non-zero elements.
Later in this paragraph, we will clarify how the
term "non-zero element" should be understood.
Let
x
be the vector column of the input signal
values,
N
E
be the transformation matrix, and
y
be
the vector column of output signals, i.e.,
N
y E x
. (11)
Regarding spectral analysis, we can expect that
the spectrum of the discrete signal
x
is on the basis
N
E
. Taking into account factorization (10), let us
represent the spectrum (11) in the form
1
k
i
i
y F x
. (12)
Suppose that we organize the procedure of
matrix transformations (12) to exclude operations of
calculating products on zero elements of matrices
.
i
F
In this case, the determination of the vector
y
by formula (12) is more efficient than the
calculation by formula (11), and the effectiveness
increases rapidly with increasing matrix size N and
the number of its zero elements.
There are many ways of factorization of
composite matrices, [16], which lead to different
structural schemes of FFTs. We will mainly follow
the work of, [17], relying on isomorphic
representations of the DEF matrices. From now on,
we give practical techniques for the factorization of
composite DEF matrices considered in the order of
increasing their dimensionality N.
So, let's turn to the fourth-order DEF mother
system.
(1)
4
0 0 0 0
0 1 2 3
0 2 0 2
0 3 2 1
E
. (13)
Let us make some clarifications concerning
matrix (13). You should consider that the zero
elements of this (as well as all subsequent) the DEF
matrices are not zero in the usual sense. These zero
means that in the place of these elements, there are
numbers, corresponding to the values of the phase
multipliers
in the zero degree. Naturally, this
number is one. When in the factorized matrix, there
should be an arithmetic zero in place of an element
to eliminate possible ambiguity, we will put a dash
in this place.
Let's write the matrix
(1)
4
E
as a product of
(1)
4 1 2
E F F
. (14)
Matrices
1
F
and
2
F
correspond to numbers 2,
which are elements of the decomposition of order N
of the matrix (13) equal to four.
Let's choose the elements of the left half of the
matrix rows (13) as the elements of the matrix
1
F
.
In the matrix
1
F
, we keep the initial position of the
selected elements of the mother system
(1)
4
E
for
even rows (the numbering of matrix rows is
performed from top to bottom by a sequence of
numbers from 0 to N-1) and shift the elements of
odd rows to the right by
/2N
, i.e., by two positions.
We make such shifts so that each row and each
column of the matrix
1
F
(according to Definition 5)
contains two non-empty elements. We arrive at the
matrix
1
00
01
02
03
F
. (15)
The matrix
2
F
should formed in such a way that
the equality (14) holds. As we can see from the
upper line of matrix (15), we obtain the zero-order
basis function of the system
(1)
4
E
in (13) by
selecting these the first two lines of the matrix
2
F
0 0 0
1 0 0
. (16)
Obviously, by multiplying the zero row of the
matrix (15) by the matrix (16), and the matrix
elements marked with a dash do not participate in
the multiplication operation, we obtain the zero-
order basis function of the system
(1)
4
E
.
Here, it is appropriate to remind you that in the
isomorphic mapping, we formally perform the
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.99
Anatoly Beletsky, Dmytro Poltoratskyi
E-ISSN: 2224-2880
908
Volume 22, 2023
matrix product operation using the same rules as in
the usual matrix calculus. Only needs to replace the
operation of elementwise product with the operation
of elementwise addition modulo N. Let us explain
the method of such replacement by the following
example. Let N = 4 and
1
01
02
03
ab
M
;
2
cd
ef
M
.
Then, the process of forming the upper row of
the product of matrices
1
M
and
2
M
(in isomorphic
space) reduces to calculating the four elements
using the formulas
4 4 4 4
( ) ; ( ) ; ( ) ; ( )a c b e a d b f
.
To obtain the first-order basis function of the
system
(1)
4
E
, you can multiply (according to the
scheme described above) the first row of the matrix
(13) by the matrix
2 0 2
3 0 2
, (17)
containing the second and third rows of the matrix
2
F
.
Combining matrices (16) and (17), we obtain
2
0 0 0
1 0 0 .
2 0 2
3 0 2
F
(18)
It is easy to check that the product of the
matrices (15) and (18) leads to the matrix (13),
which completes the factorization procedure of the
fourth-order DEF mother system.
We proceed to factorization of the six-order DEF
matrix
(1)
6
0 0 0 | 0 0 0
0 1 2 | 3 4 5
024|024
0 3 0 | 3 0 3
042|042
0 5 4 | 3 2 1
E
. (19)
We decompose the order
126N n n
of this
matrix into two simple factors 2 and 3, and their
order in the product determines the type of factored
matrices
1
F
and
2
F
, forming the matrix
(1)
6 1 2
E F F
. (20)
Assuming
13n
and
22n
, then in the matrix
1
F
, each row should contain three consecutive
significant elements, and if
12n
, then in the
matrix
1
F
, each row should contain two consecutive
significant elements. The matrix
2
F
is constructed
depending on the form of the matrix
1
F
.
Consequently, there are at least two variants of
factorization of the six-order DEF matrix. Let us
consider both of these variants.
So, let us assume
13n
. That means that in each
row of the matrix
1
F
, it is necessary to place the
first three elements of the corresponding basis
functions of the system
(1)
6
E
. These elements are in
the left part relative to the dashed line in the matrix
(19). In addition, recall that the significant elements
of odd rows (odd-order basis functions) should shift
by three positions to the right. We obtain
1
000
0 1 2
0 2 4
0 3 0
0 4 2
0 5 4
F
. (21)
To satisfy the equality (20), the matrix
2
F
should
have the form
2
00
00
00
03
03
03
F
. (22)
Multiplying matrices (21) and (22), we obtain the
matrix (19), which is evidence of the correctness of
the factorization procedure of the six-order DEF
matrix
(1)
6
E
.
Matrices similar to the matrix (21) are called
row-factorized matrices. Their distinctive feature is
that the significant elements densely fill some parts
of the rows of this matrix. Matrices similar to the
matrix (22) will be called diagonal-factorized
matrices. Their distinctive feature is that the
significant elements of this matrix densely fill some
of its diagonals.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.99
Anatoly Beletsky, Dmytro Poltoratskyi
E-ISSN: 2224-2880
909
Volume 22, 2023
Now, let us turn to the second variant of
factorization of the six-order DEF matrix. In this
variant
12n
and
23n
. This ranking of prime
numbers
i
n
means that in the matrix
1
F
, each row
and each column must contain two significant
elements, and the elements of the rows are
composed of the first two elements of the
corresponding basis functions of the system
(1)
6
E
.
The matrix corresponds to the formulated conditions
1
00
01
02
03
04
05
F
. (23)
From comparing matrices (23) and (19), we
easily arrive at the algorithm for forming a matrix
1
F
. The elements of the rows of the matrix
1
F
are
formed from the elements of the first two columns
of the matrix
(1)
6
E
due to their shift to the right by
two positions (for the first and fourth rows) and four
positions (for the second and fifth rows).
Since the matrix
2
F
corresponds to a prime
number
23n
, each row and each column of the
six-order matrix
2
F
must contain three significant
elements. As follows from the form of the upper
row of the matrix (23), in to form the zero-order
basis function of the system
(1)
6
E
, the first two rows
of the matrix
2
F
should give the form of
000
0
1000
. (24)
Indeed, by multiplying the zero row of the matrix
(23) successively by the columns of the matrix (24),
we obtain the required zero basis function of the
system
(1)
6
E
in (19).
The first row of the matrix (23), which has the
form
( 0 1 )
, can form the first-order basis
function of the system
(1)
6
E
only as a result of its
multiplication by the columns of the second and
third rows of the matrix
2
F
since only the second
and third elements of the first row of the matrix (23)
are significant. You can easily see that you should
choose these rows (second and third) of the matrix
2
F
as follows
0
224
3024
. (25)
Finally, to form the second-order basis function
of the system
(1)
6
E
, it suffices to multiply the second
row of the matrix (23), i.e., the row
( 0 2),
by the fourth and fifth rows of the
matrix
2
F
, which should be of the form
0
442
4042
. (26)
Combining matrices (24) (26), we obtain
2
000
000
0 2 4
0 2 4
0 4 2
0 4 2
F
. (27)
As it is easy to check, the product of matrices
(23) and (27) modulo
6N
leads to the matrix (19).
Thus, we confirm that the second variant of the
factorization of the system
(1)
6
E
is also correct.
The acquired experience of factorization of DEF
matrices can transfer to the solution of problems of
factorization of matrices of eighth and higher orders.
Let us formulate the basic empirical rules of
factorization of the DEF matrices of arbitrary order,
taking as an example the mother system of DEF of
the eighth order, which in the isomorphic
representation has the form:
(1)
8
00000000
0 1 2 3 4 5 6 7
0 2 4 6 0 2 4 6
0 3 6 1 4 7 2 5
0 4 0 4 0 4 0 4
0 5 2 7 4 1 6 3
0 6 4 2 0 6 4 2
0 7 6 5 4 3 2 1
E
. (28)
STEP 1. Display the composite number N,
determining the order of the DEF matrix, as a
product of prime numbers
i
n
, arranging them from
left to right in ascending order of indices
12
... k
N n n n
,
where k is the number of multipliers.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.99
Anatoly Beletsky, Dmytro Poltoratskyi
E-ISSN: 2224-2880
910
Volume 22, 2023
For the eighth order of the matrix (28), we have
1 2 3 2n n n
.
STEP 2. Let us represent the order of the matrix
N as a product of
k
N n n
, (29)
where
1 2 1
... k
n n n n
.
The format (29) makes it possible to factorize the
matrix
(1)
8
E
in this sequence. According to (29), let
us write the number 8 as a product of the factors 4
and 2. To number 4 corresponds to a partially
factored matrix, which we denote
F
, and to number
2 corresponds to a matrix, which we denote
3
F
. The
product of the matrices
F
and
3
F
must be equal to
the matrix (28), i.e.,
(1)
83
E F F
.
Since the matrix
F
corresponds to the number
4n
, it means that each line of the matrix contains
the four first significant elements of the
corresponding basis functions of the system (28),
and the odd lines should shift four positions to the
right, and the vacated elements should fill with
dashes. After performing the above operations, we
arrive at the matrix
0000
0 1 2 3
0 2 4 6
0 3 6 1
0 4 0 4
0 5 2 7
0 6 4 2
0 7 6 5
F
. (30)
Concerning the matrices
F
,
3
F
and
(1)
8
E
, we
can make the following considerations. First, since
the matrix
3
F
corresponds to the multiplier
32n
,
it means that all rows and columns of the matrix
contain two significant elements each, and you must
space these elements diagonally. Second, since the
first four elements in the upper row of the matrix
F
are substantial, the first four rows of the matrix
3
F
,
whose form is uniquely determined by the relation
0 0 0
1 0 0
2 0 0
3 0 0
. (31)
Finally, the first-order basis function of the
system
(1)
8
E
can formed by multiplying the first row
of the matrix (30) by the column of the matrix
composed of the last four rows of the matrix
3
F
.
These rows should look as follows
4 0 4
5 0 4
6 0 4
7 0 4
. (32)
The union of rows of the matrices (31) and (32)
forms a diagonal factorized matrix
3
00
00
00
00
04
04
04
04
F
. (33)
It is easy to check that the product of matrices
(30) and (33) leads to matrix (28), as it should.
STEP 3. Since the matrix
F
corresponds to the
composite number
4n
, you can represent in the
form of factors
12
n n n
,
and
12
2nn
.
Consequently, we can subject the matrix
F
to
deeper factorization and write as a product of
12
F F F
,
where
1
F
is a row-factorized matrix and
2
F
is a
diagonal-factorized matrix. Each row and each
column of the eighth-order matrices
1
F
and
2
F
contain two significant elements (since they
correspond to prime factors equal to two).
Let us compose the matrix
1
F
, forming it from
the row elements of the matrix
(1)
8
E
, given by
system (28), or the matrix
F
, represented by
relation (30). From the significant elements of the
rows of the matrix
(1)
8
E
(or
F
) in the matrix
1
F
, we
will keep only the first two elements, shifting the
remaining ones to the right by two positions relative
to the position of the significant elements of the
previous row. As a result, we come to the matrix
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.99
Anatoly Beletsky, Dmytro Poltoratskyi
E-ISSN: 2224-2880
911
Volume 22, 2023
1
00
01
02
03
04
05
06
07
F
. (34)
That is not the only variant of representation of
the row-factored matrix
1
F
. For example, we can
suggest the following variant
'
1
00
01
02
03
04
05
06
07
F
.
Let us take the variant (34) as more regular. You
should construct the matrix
2
F
so that the product
of the matrices
1
F
and
2
F
equals the matrix
F
. It
is easy to check that this is the matrix
2
00
00
02
02
04
04
06
06
F
. (35)
Each row and each column of matrices (34) and
(35) contain two significant elements, and their
product is equal to the matrix (30), which completes
the procedure of factorization of the system
(1)
8
E
.
Let us consider a factorization scheme for an odd
ninth-order isomorphic DEF matrix
(1)
9
000000000
0 1 2 3 4 5 6 7 8
0 2 4 6 8 1 3 5 7
036036036
0 4 8 3 7 2 6 1 5
0 5 1 6 2 7 3 8 4
0 6 3 0 6 3 0 6 3
075318642
0 8 7 6 5 4 3 2 1
E
. (36)
Following the above methodology, the
factorization of the ninth-order DEF matrix is
reduced to the compilation of two sparse matrices
corresponding to the factors of the composite
number 9, equal to
13n
and
23n
. The matrix
1
F
is row-factorized, i.e.,
1
000
0 1 2
0 2 4
0 3 6
0 4 8
0 5 1
0 6 3
0 7 5
0 8 7
F
. (37)
The diagonal-factorized matrix
2
F
has the form
2
000
000
000
0 3 6
0 3 6
0 3 6
0 6 3
0 6 3
0 6 3
F
. (38)
The product of matrices (37) and (38) modulo
9m
leads to the system (36), as it should be.
Following the above methodology, one can easily
solve the factorization problem of the DEF systems
of arbitrary order N.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.99
Anatoly Beletsky, Dmytro Poltoratskyi
E-ISSN: 2224-2880
912
Volume 22, 2023
6 Further Research
At least we can indicate such directions for further
research:
Development of the FFT algorithms in
composite-order DEF bases for handling
signals such as audio, images, time series,
etc.
Study the possibility of practical
applications of the developed algorithm for
factorization of the DEF matrices in natural
systems and technologies, such as radio
communication, medical diagnostics, image
processing, etc.
7 Conclusion
The computation of the vector-matrix product is the
basis for many procedures of digital signal
processing, a classic example of which is the
operations of determining the spectrum of discrete
signals in the DEF basis. As the DEF matrices
comprise complex-valued elements, the
computational cost of multiplying a vector of
sampled values from a continuous signal potentially
complex itself by a complex-valued matrix is
substantial. The factors outlined herein contribute to
the computational efficiency realized in this paper.
First, due to the isomorphic replacement of the DEF
matrices with complex-valued elements by matrices
with non-negative integer elements, resulting in a
transition to real matrices. Secondly, due to the
factorization of real matrices, i.e., their
representation is a set of strongly discharged
matrices multiplier with consecutive multiplication
of the vector of input signal samples by each of the
matrices. The reduction in the required
computational resources for the realization of
vector-matrix operations by the proposed algorithm
will increase with the orders of the DEF matrices.
References:
[1] Carl Gauss, Disquisitiones arithmetical,
file:///C:/Users/abeln/Downloads/h284_gauss
_1801.pdf
[2] Gustav Pitagali, Memoir on the Application of
Analysis to the Probability of Majority
Decisions, 1815, ChatGPT-3.5
[3] Norbert Wiener, Generalized harmonic
analysis, Acta Math. 55: 117-
258 (1930). DOI: 10.1007/BF02546511
[4] Harry Nyquist, Certain Topics in Telegraph
Transmission Theory, Trans. of the American
Institute of Electrical Engineers, Vol. 47, 2,
April 1928, pp. 617 – 644.
[5] James W. Cooley and John W. Tukey, An
Algorithm for the Machine Calculation of
Complex Fourier Series, Mathematics of
Computation, Vol. 19, No 90, 1965, pp. 297 –
301.
[6] L. Rabiner, L., B. Gold, Theory and
application of digital signal processing, New
Jersey, Prentice-hall, 1975.
[7] John G. Proakis and Dimitris G. Manolakis,
Digital Signal Processing. Principles,
Algorithms, and Applications, Pearson, 2006,
1004 p.
[8] Alan V. Oppenheim and Ronald W. Schafer,
Discrete-Time Signal Processing, Pearson Ed.
Lim., 2014, 1042 p.
[9] Rafael C. Gonzalez and Richard E. Woods,
Digital Image Processing. Global Edition,
Pearson, 2017, 1024 p.
[10] B.P. Lathi and Zhi Ding, Modern Digital and
Analog Communication Systems, Oxford,
2018, 927 p.
[11] D. B. Reddy, Biomedical Signal Processing:
Principles and Techniques, McGraw-Hill
Education (India) Pvt Limited, 2005, 411 p.
[12] Robert H. Shumway and David S. Stoffer,
Time Series Analysis and Its Applications,
Springer, 2017, 562 p.
[13] Michael A. Nielsen and Isaac L. Chuang,
Quantum Computation and Quantum
Information, Cambridge University Press,
2016, 676 p.
[14] W. M. Telford, L. P. Geldart, and R. E.
Sheriff, Applied Geophysics, Cambridge
University Press 2010. 770 p.
[15] Yicong Zhou, Weijia Cao, Licheng Liu,
Sos Agaian and Philip Chen, Fast Fourier
transform using matrix decomposition,
Information Sciences, Vol. 291, 2015, pp.
172-183.
[16] Anatoly Beletsky, Discrete orthogonal bases
of Vilenkin-Crestenson functions.
Fundamentals of the theory, Palmarium
Academic Publishing, 2015, 232 p. ISBN
978-3-659-60300-6
[17] Ponomarev A.V. Fundamentals of the Theory
of Two-Dimensional Digital Signal
Processing in the Fourier Bases with Varying
Parameters. Digital Signal Processing, No. 2,
2019, pp. 12-20. (In Ru).
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.99
Anatoly Beletsky, Dmytro Poltoratskyi
E-ISSN: 2224-2880
913
Volume 22, 2023
Contribution of Individual Authors to the
Creation of a Scientific Article (Ghostwriting
Policy)
The authors equally contributed to the present
research, at all stages from the formulation of the
problem to the final findings and solution.
Sources of Funding for Research Presented in a
Scientific Article or Scientific Article Itself
No funding was received for conducting this study.
Conflict of Interest
The authors have no conflicts of interest to declare
that are relevant to the content of this article.
Creative Commons Attribution License 4.0
(Attribution 4.0 International, CC BY 4.0)
This article is published under the terms of the
Creative Commons Attribution License 4.0
https://creativecommons.org/licenses/by/4.0/deed.en
_US
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.99
Anatoly Beletsky, Dmytro Poltoratskyi
E-ISSN: 2224-2880
914
Volume 22, 2023
