Systems of Discrete Walsh-Like Sequential Functions
ANATOLY BELETSKY
Department of Electronics
National Aviation University,
Kyiv-03058, av. Cosmonaut Komarov, 1,
UKRAINE
Abstract: - In this paper the algorithm for constructing the discrete (0,1)-sequent functions constituting the whole
symmetric systems of orthogonal equidistant functions on the example of the eighth-order systems developed.
Discrete sequential functions form by replacing their piecewise constant values +1 or -1 in the time domain (from
the original space) with numerical values 0 and 1 in the image space. We refer to Walsh-like functions as (0,1)-
sequent functions in which the number of zeros and ones in each half of the definition interval is not necessarily
the same as in classical Walsh functions. By the directed search method, each of the 30 formed whole groups of
equidistant sequent functions unfolds, like the group of classical Walsh functions of the eighth order, into 28
symmetric systems of sequent functions. The main result achieved in this work should consider an expansion of
the set of Walsh-like systems of the eighth order by more than an order of magnitude. The algorithm's simplicity
for synthesizing such systems of sequential functions and the high speed of spectral processing of discrete signals
provided by the proposed bases open the Walsh-like systems for broad prospects of application in various fields
of science and technology.
Key-Words: - The sequential functions and systems, the method of a directed enumeration.
Received: May 29, 2021. Revised: May 16, 2022. Accepted: July 7, 2022. Published: August 1, 2022.
1 Introduction
The theory and technique of spectral analysis of
signals mainly focus on signals of sinusoidal forms.
Also, non-sinusoidal signals (functions) use in
information transmission systems, radiolocation,
and other applications [1-3]. A typical example of
non-sinusoidal functions is the Walsh function [4].
Their distinctive feature is that the Walsh functions
take piecewise constant values to equal
1
or
1
in
the original space.
Spectral analysis of discrete signals is usually
performed based on discrete exponential functions
formed by temporal discretization of complex-
valued harmonic signals. It knew [5] that discrete
Fourier transform (DFT) bases have some
requirements, the most important of which are the
following. First, it is desirable in the form of basic
transform functions to be as close as possible to the
state of the analyzed signal. And secondly, the basis
function systems must support such a speed of the
DFT processors that enables real-time signal
processing.
Thus, the choice of a system of basic functions
determines by the requirements of convenience
calculations. And finally, by the labor intensity of
algorithms of realization of the sought
transformation. Based on these considerations, the
use of fundamental bases of Walsh systems and their
extension, Walsh-like sequential systems (the
definition of such systems is given further in the
text), seems relevant and promising for the digital
processing of broadband signals.
Put together and numbered orthogonal Walsh
functions of different orders form a system. Let us
introduce the notation
()k,tW
for discrete Walsh
systems, where
k
is the function’s order and
t
is
the normalized time (argument), whereby
, 0, 1k t N
. An example of the Walsh functions
()k,th
ordered by Adamar depict in Fig. 1.
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS,
COMPUTATIONAL SCIENCE AND SYSTEMS ENGINEERING
DOI: 10.37394/232026.2022.4.8
Anatoly Beletsky
E-ISSN: 2766-9823
60
Volume 4, 2022
Figure 1. Walsh-Adamar function systems
Replacing the piecewise constant functions
()k,tw
with their discrete values
1
and
1
, we
arrive at the matrix forms of Walsh systems in the
original space. Below is a sequence of matrices
N
P
of Paley’s first (degenerate), second, and fourth
orders of Walsh systems.
1 2 4
0 1 2 3
01 0 1111
0 1 1 1 1 1 1 1
1 ; ( , ) ; ( , ) .
1 1 1 2 1 1 1 1
3 1111
t
t
p k t p k t
k
k
P P P
(1)
A more convenient way to represent systems of
Walsh functions is to represent them as square
matrices in which each row is a Walsh function. For
simplicity, instead of element values
1
and
1
,
write only their signs
and
. So, for example, a
system of Walsh-Paley functions of the eighth order
looks like this:
8
0 1 2 3 4 5 6 7
0
1
2
3
( , ) .
4
5
6
7
t
p k t
k
P
(2)
The Paley matrices
N
P
(1) or (2) at an arbitrary
but binary-degree ordering
2n
N
,
1, 2,n
, can
construct directly using a simple mnemonic rule [6],
the essence of which reduce to the following
transformations. At the initial formation stage
N
P
,
each row of the previous Paley matrix
/2N
P
writes
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS,
COMPUTATIONAL SCIENCE AND SYSTEMS ENGINEERING
DOI: 10.37394/232026.2022.4.8
Anatoly Beletsky
E-ISSN: 2766-9823
61
Volume 4, 2022
twice. Then to the first of them (row), the same
elements are attributed to the right, i.e., the details of
the right half of the row repeat the elements of the
left half of the row, and of the second one, the
opposite (complementary) elements attributed. The
above method of forming Walsh-Paley systems is
implemented in the image space using the code tree
shown in Fig. 2.
Figure 2. Repeatedly-complementary algorithm
synthesis of Walsh-Paley function system
We come to the image space by replacing the
discrete values of the Walsh functions
1
and
1
in
matrices (1) or the
and
signs in matrices (2)
with numbers 0 and 1. The matrix Walsh-Paley
system of the eighth order in the space of images is
represented below by the following relation
8
0 1 2 3 4 5 6 7
0 00000000
1 00001111
2 0 0 1 1 0 0 1 1
3 00111100
( , ) .
4 0 1 0 1 0 1 0 1
5 0 1 0 1 1 0 1 0
6 0 1 1 0 0 1 1 0
7 0 1 1 0 1 0 0 1
t
p k t
k
P
(3)
The translation of Walsh matrices from the
original area, for example, matrix (2), into the space
of images, matrix (3), is accompanied by a change
in the operation of element-by-element
multiplication of the two discrete Walsh functions
i
uu
and
j
vv
,
, 0, 1i j N
, to the
operation of their element-by-element addition
modulo 2. Such operations perform, in particular,
when calculating the scalar product of these
functions
(),uv
to confirm their orthogonality,
given by condition
( ) 0,uv
.
Sequent analysis, a generalization and alternative
to spectral harmonic analysis, was formed as an
independent discipline at the turn of the 1970s-80s,
primarily due to the actual results obtained in the
works of H. Hartmut [7, 8]. The success of
sequential analysis basis on the fact that instead of
sinusoidal signals, Walsh functions and other non-
sinusoidal waves use. To date, a sufficiently large
number of publications devoted to the theory and
application of sequential analysis in various fields of
science and technology have appeared, among
which we will distinguish a textbook [9],
dissertations [10, 11], journal articles [12, 13], etc.
This paper aims to develop algorithms for
synthesizing Walsh-like discrete sequential
functions that form complete symmetric systems of
orthogonal equidistant functions
( , )kts
,
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS,
COMPUTATIONAL SCIENCE AND SYSTEMS ENGINEERING
DOI: 10.37394/232026.2022.4.8
Anatoly Beletsky
E-ISSN: 2766-9823
62
Volume 4, 2022
0, 1,Nkt
, on the example of the eighth-order
systems, i.e., for
3
2N
.
The completeness of a system of discrete
sequential functions means that it cannot augment
with any new function that would be orthogonal to
all other system functions simultaneously. An
equidistance of
N
bit sequential functions means
that any pair of functions of the system, such as the
functions
1
s
and
2
s
, is at a Hamming distance
d
equal to
/2N
, i.e.,
12
( , ) / 2dNss
.
2 General ratios
We will refer to Walsh-like functions such that the
number of zeros and ones in each half of the
definition interval is not necessarily the same as, for
example, in representations of classical Walsh
functions. In the future, for brevity, we will also call
sequent function sequences. Thus, apart from zero
bytes, the only type of binary (binary) code
combinations (codes) considered in this paper are
uniform (codes of the same length) eight-bit sequent
functions (sequents) with a weight (number of units
in a code) equal to four.
Let us form a complete set of sequent functions of
the eighth order, including into the set only those
functions which begin with zero. It means that the
number 0 is placed in the senior (left) bit of each
sequent, and three zeros and four ones place in the
remaining minor seven bits. Hence, the complete set
of such non-zero functions
8
L
contains 35
sequences of the eighth order. All these functions are
summarized (together with the zero sequent) in
Table 1.
Table 1. The set of sequent functions of the eighth order
Number of
sequent
Number of the digit
Number of
sequent
Number of the digit
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
0
0
0
0
0
0
0
0
18
0
1
0
1
1
0
0
1
1
0
1
1
1
1
0
0
0
19
0
0
1
1
1
0
0
1
2
0
1
1
1
0
1
0
0
20
0
1
1
0
0
1
0
1
3
0
1
1
0
1
1
0
0
21
0
1
0
1
0
1
0
1
4
0
1
0
1
1
1
0
0
22
0
0
1
1
0
1
0
1
5
0
0
1
1
1
1
0
0
23
0
1
0
0
1
1
0
1
6
0
1
1
1
0
0
1
0
24
0
0
1
0
1
1
0
1
7
0
1
1
0
1
0
1
0
25
0
0
0
1
1
1
0
1
8
0
1
0
1
1
0
1
0
26
0
1
1
0
0
0
1
1
9
0
0
1
1
1
0
1
0
27
0
1
0
1
0
0
1
1
10
0
1
1
0
0
1
1
0
28
0
0
1
1
0
0
1
1
11
0
1
0
1
0
1
1
0
29
0
1
0
0
1
0
1
1
12
0
0
1
1
0
1
1
0
30
0
0
1
0
1
0
1
1
13
0
1
0
0
1
1
1
0
31
0
0
0
1
1
0
1
1
14
0
0
1
0
1
1
1
0
32
0
1
0
0
0
1
1
1
15
0
0
0
1
1
1
1
0
33
0
0
1
0
0
1
1
1
16
0
1
1
1
0
0
0
1
34
0
0
0
1
0
1
1
1
17
0
1
1
0
1
0
0
1
35
0
0
0
0
1
1
1
1
Let us compare each non-zero sequent function
ˆi
s
,
1, N
iL
, from Table 1 with a set of sequents
,j i j
sS
, distant from
ˆi
s
the Hamming distance
d
,
equal to
/2N
, i.e., in our case
( , ) 4
ij
dss
. Let us
summarize the functions
ˆi
s
(called forming
sequents) and the sets
,ij
S
in Table 2. The left
column of Table 2 shows the numbers of functions
ˆi
s
, and the top row shows the numbers of the
sequents that form the sets
,ij
S
. Each set
,ij
S
also
includes the zero sequent
0{0,0,0,0,0,0,0,0}s
,
not shown in Table 2.
Let us pay attention to such features in Table 2.
First, Table 2 is symmetric to the main diagonal.
Second, each row of Table 2 includes, in addition to
the forming sequent (the light diagonal element
highlighted by the bold frame), 18 sequents
j
s
distant from the forming element at the Hamming
distance
ˆ
( , ) 4
kj
dss
. Finally, thirdly, the whole set
of Table rows
i
S
can be divided into 10 non-
intersecting subsets
l
,
1,10l
. At the same time,
the
l
th subset includes consecutive rows
i
S
,
containing the same number
l
n
of sequents
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS,
COMPUTATIONAL SCIENCE AND SYSTEMS ENGINEERING
DOI: 10.37394/232026.2022.4.8
Anatoly Beletsky
E-ISSN: 2766-9823
63
Volume 4, 2022
arranged on the left side of the
ˆk
s
forming sequents.
For example, subset
1
generated by the sequents
ˆj
s
,
1, 5j
, with
10n
. The second subset
2
is
formed by the sequents
ˆj
s
,
6, 9j
, for which
24n
, etc. Information about the numerical
characteristics of the subsets gives in Table 3.
Table 2. The set of sequent functions distant from the forming sequents at the Hamming distance
Table 3. Composition of Subsets
l
of Sequential Functions
Sequent subset number
()l
1
2
3
4
5
6
7
8
9
10
Sequents
ˆk
s
1-5
6-9
10-12
13-15
16-19
20-22
23-25
26-28
29-31
31-35
l
n
0
3
5
6
9
11
12
15
16
18
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS,
COMPUTATIONAL SCIENCE AND SYSTEMS ENGINEERING
DOI: 10.37394/232026.2022.4.8
Anatoly Beletsky
E-ISSN: 2766-9823
64
Volume 4, 2022
As the results of elementary calculations have
shown, the forming sequents
ˆk
s
, together with the
zero-sequent function
0
s
and 18 sequents, which are
in the rows of Table 2, form six complete equidistant
code combinations (we will call them groups for
brevity). Each row in Table 1 corresponds to six
groups with eight equidistant sequents. The groups
of Sequent equidistant functions
,ij
SF
formed by
the forming, for example, sequents
ˆi
s
of the subset
1
, are given in Table 4.
Table 4. Composition of groups formed by the forming sequents of a subset
1
Group
s ппы
Sequents of groups
1, j
SF
0
1
10
11
12
13
14
15
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
2, j
SF
0
2
7
8
9
13
14
15
17
18
19
23
24
25
26
27
28
32
33
34
1
2
3
4
5
6
3, j
SF
0
3
6
8
9
11
12
15
16
18
19
21
22
25
26
29
30
32
33
35
1
2
3
4
5
6
4, j
SF
0
4
6
7
9
10
12
14
16
17
19
20
22
24
27
29
31
32
34
35
1
2
3
4
5
6
5, j
SF
0
5
6
7
8
10
11
13
16
17
18
20
21
23
28
30
31
33
34
35
1
2
3
4
5
6
Sequents
j
s
included groups
,ij
SF
marked by
gray cells in the rows of Table 4. And their
corresponding numbers of sequential functions are
in the black rows of Table 4 located directly above
the sequents, and the row element containing the
number
i
of the forming sequents
ˆi
s
lightened. The
left column of Table 4 shows the numbers
1,6j
of
groups
,ij
SF
formed by the sequents of
ˆi
s
,
1,5i
,
that make up the subset of
1
.
Table 4 contains all groups
SF
of equidistant
functions generated by formative elements
ˆi
s
of the
first subset of sequents
1
, which characterizes by
the peculiarity that in the rows of Table 2 to the left
of the sequents
15
ˆˆ
ss
, there are no other sequents
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS,
COMPUTATIONAL SCIENCE AND SYSTEMS ENGINEERING
DOI: 10.37394/232026.2022.4.8
Anatoly Beletsky
E-ISSN: 2766-9823
65
Volume 4, 2022
s
. The 30 groups, summarized in Table 3 and
corresponding to a subset of sequential functions
1
, constitute a complete set of sequential
equidistant byte functions. That means — the group
of functions formed by any
ˆj
s
,
6 35j
, absorbed
by one of the groups
,ij
SF
subset
1
.
Let us confirm this statement with concrete
examples. For this purpose, let us choose, for
example, the sequents forming
17
ˆ
s
and
33
ˆ
s
, and
their corresponding complete groups of equidistant
functions presented in Table 5.
Table 5. Composition of groups of sequential functions formed by the elements
17
ˆ
s
and
33
ˆ
s
Groups
The sequential of groups
17, j
SF
0
2
4
5
6
8
9
10
13
14
17
21
22
25
27
28
31
32
33
35
1
2
3
4
5
6
33, j
SF
0
2
3
5
6
7
9
11
13
15
16
17
19
21
23
25
27
29
31
33
1
2
3
4
5
6
From the data comparison, we can easily see that
any group in Table 5 is in one of the rows of Table
4. The correspondence between groups
17, j
SF
,
33, j
SF
,
1, 6j
, and group
( , )ij
subset
1
showed in Table 6.
Table 6. Composition of sequent function groups,
formed by the elements
17
ˆ
s
and
33
ˆ
s
17, j
SF
1
2
3
4
5
6
( , )ij
2,3
2,5
4,1
4,6
5,1
5,6
33, j
SF
1
2
3
4
5
6
( , )ij
2,2
2,5
3,2
3,5
5,1
5,3
In the same way, the redundancy of groups
generated by sequences
ˆk
s
for all
6 35k
establish.
Let us pay attention to the mosaic of rectangular
squares in Table 3. The coloring of all the sites turns
out to be the same. And this provides an opportunity
to significantly reduce the labor intensity of
calculating the composition of groups A of subset В.
Suppose a site mosaic maiden for group
1, j
SF
, in
which the sequent is
1
ˆ
s
. To calculate the sequences
of any group
,ij
SF
generated by
ˆi
s
,
1i
, replace
the top string
1
S
in group
,ij
SF
with the string
i
S
.
3 Synthesis of symmetric sequential
systems
In applications, it often may be interesting not the
complete systems of sequent functions themselves,
but some orderings of them, such as, for example,
systems of functions forming symmetric bases. Such
bases are particularly interesting for spectral
analysis of signals or solving other problems of
discrete signal processing. In this section of the
work, we consider the problem of construction
(synthesis) of symmetric sequential bases from the
complete set of equidistant sequential groups
,.
ij
SF
.
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS,
COMPUTATIONAL SCIENCE AND SYSTEMS ENGINEERING
DOI: 10.37394/232026.2022.4.8
Anatoly Beletsky
E-ISSN: 2766-9823
66
Volume 4, 2022
Different approaches to the solution of the
problem are possible. The synthesis of a symmetric
system based on sequent functions basis on the
method of direct enumeration [14, 15]. This method
allows you to discard unacceptable options in
advance. Let us choose from Table 3 as the initial set
of sequences for the complete eighth-order group
1,1 0 1 10 15 21 24 28 29
ˆ
, , , , , , ,SF s s s s s s s s
.
Using the data in Table 1, we compose a matrix
of group elements
1,1
SF
, denoting it by
( , )ktS
,
which is not symmetric.
0 1 2 3 4 5 6 7
0 0 00000000
1 1 0 1 1 1 1 0 0 0
2 10 0 1 1 0 0 1 1 0
3 15 0 0 0 1 1 1 1 0
( , ) .
4 21 0 1 0 1 0 1 0 1
5 24 0 0 1 0 1 1 0 1
6 28 0 0 1 1 0 0 1 1
7 29 0 1 0 0 1 0 1 1
t
kt
kn
S
(4)
In matrix (4), the parameter
k
is the basis of
function order, coinciding with the order number of
the functions in the system;
t
the function's
argument (discrete normalized time);
n
is the
number of the sequent in Table 1.
In any sequential system in image space, the
basis of the zero-order function cannot be rearranged
on any other line. The reason is that such a
permutation leads to the loss of the symmetry of
matrix
( , )
iktS
. Since all sequents begin with zero,
the left column of the matrix is zero by definition,
i.e., it consists of only zeros. For this reason, the zero
rows of a matrix are "doomed" to occupy its top row.
Otherwise, the symmetry condition is violated: each
column must coincide with the corresponding matrix
row (by the number) in any symmetric matrix.
The following (first) row of matrix
( , )
iktS
can
contain any of the remaining rows (basis functions)
of the matrix (4). Let us choose such a basic function
of the first order, i.e., a sequent
1
s
, which results in
the first two rows and two columns of the matrix to
formed
1( , )ktS
, namely
1
0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0 0
1 1 0 1 1 1 1 0 0 0
2 ,21,29 (0 1)
3 0 1
( , ) .
4 0 1
5 0 0
6 0 0
7 0 0
t
kt
kn
10
S
(5)
The possibility of choosing the next (second) row
is limited by the condition of maintaining the
symmetry of the matrix. To observe this condition,
from the remaining rows of the matrix (4), we need
to choose only those whose initial elements coincide
with the initial elements of the second row of the
matrix (5), enclosed in parentheses. The bracketed
elements correspond to sequents
10
s
,
21,s
29
s
and
matrices (4), whose numbers (10, 21, and 29) write
in (5) to the left of the parentheses. Placing in the
second row of the matrix
1( , )ktS
the basis function
(sequent)
10
s
(the number of this sequent marked in
bold in matrix
1( , )ktS
) and continuing the
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS,
COMPUTATIONAL SCIENCE AND SYSTEMS ENGINEERING
DOI: 10.37394/232026.2022.4.8
Anatoly Beletsky
E-ISSN: 2766-9823
67
Volume 4, 2022
synthesis procedure similarly, we come to a
symmetric basis
1
0 1 2 3 4 5 6 7
0 0 00000000
1 1 0 1 1 1 1 0 0 0
2 ,21,29 0 1 1 0 0 1 1 0
3 ,29 0 1 0 1 0 1 0 1
( , ) .
4 29 0 1 0 0 1 0 1 1
5 28 0 0 1 1 0 0 1 1
6 24 0 0 1 0 1 1 0 1
7 15 0 0 0 1 1 1 1 0
t
kt
kn
10
21
S
(6)
Let us turn to the matrix (6). In this matrix, in
place of the third row, we can use not only the sequent
21
s
but also the sequent
29
s
and, as a result
of further substitutions, we obtain
2
0 1 2 3 4 5 6 7
0 0 00000000
1 1 0 1 1 1 1 0 0 0
2 ,21,29 0 1 1 0 0 1 1 0
3 29 0 1 0 0 1 0 1 1
( , ) .
4 21 0 1 0 1 0 1 0 1
5 24 0 0 1 0 1 1 0 1
6 28 0 0 1 1 0 0 1 1
7 15 0 0 0 1 1 1 1 0
t
kt
kn
10
S
(7)
By the example of matrices (6) and (7), we
convince that in the binary image space, the set of
sequent functions of the basis closed under the
operation of digit addition modulo 2. In contrast, in
the original area, the sequent functions of basis
matrices are closed under the operation of the
element-by-element multiplication of functions.
If a deadlock occurs at any stage of synthesis,
proceed as follows. In the row of the synthesized
matrix containing at least two alternative sequent
numbers
i
s
, the nearest to the "deadlock" row, the
left sequent replaces by its neighbor to the right,
which may (or may not) resolve the emerging
deadlock. If the "deadlock" problem persists with
the proposed substitution, select another possible
sequent substitution, or go to another first-order
sequent function.
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS,
COMPUTATIONAL SCIENCE AND SYSTEMS ENGINEERING
DOI: 10.37394/232026.2022.4.8
Anatoly Beletsky
E-ISSN: 2766-9823
68
Volume 4, 2022
0 1 2 3 4 5 6 7
00 0 0 0 0 0 0 0 0
110 0 1 1 0 0 1 1 0
2,29 0 1 0 1 0 1 0 1
328 0 0 1 1 0 0 1 1 .
4(0 0 0 0)
50 1 1 0
60 1 0 1
70 0 1 1
t
kn
21
In the example under consideration, the deadlock successfully resolves, which leads to a symmetric basis
8
0 1 2 3 4 5 6 7
0 0 00000000
1 10 0 1 1 0 0 1 1 0
2 29 0 1 0 0 1 0 1 1
3 15 0 0 0 1 1 1 1 0
( , ) .
4 28 0 0 1 1 0 0 1 1
5 21 0 1 0 1 0 1 0 1
6 1 0 1 1 1 1 0 0 0
7 24 0 0 1 0 1 1 0 1
t
kt
kn
S
Based on the considered algorithm of the directed
search of basic functions, we come to the complete
set consisting of 28 permutations of the sequent
i
s
group
1,1
SF
(Table 7), each of which generates a
symmetric system of sequent functions (an
orthogonal basis that has the property of
completeness).
Table 7. Transpositions of equidistant sequents of a group
1,1
SF
, generating a symmetric basis
Number
of basis
Sequent number
Number
of basis
Sequent number
1
0
1
10
21
29
28
24
15
15
0
21
24
29
28
10
15
1
2
0
1
10
29
21
24
28
15
16
0
21
28
1
15
29
24
10
3
0
1
21
10
29
28
15
24
17
0
24
1
28
10
29
15
21
4
0
1
29
21
10
15
24
28
18
0
24
10
15
21
1
28
29
5
0
10
1
24
28
21
29
15
19
0
24
21
28
29
10
15
1
6
0
10
1
28
24
29
21
15
20
0
24
29
15
1
21
28
10
7
0
10
21
24
15
1
29
28
21
0
28
1
10
24
15
21
29
8
0
10
29
15
28
21
1
24
22
0
28
10
29
15
24
1
21
9
0
15
24
21
10
1
29
28
23
0
28
21
1
15
24
29
10
10
0
15
24
29
1
10
21
28
24
0
28
29
21
24
15
10
1
11
0
15
28
1
21
29
10
24
25
0
29
15
24
1
28
10
21
12
0
15
28
10
29
21
1
24
26
0
29
15
28
10
24
1
21
13
0
21
15
1
28
10
24
29
27
0
29
24
15
1
28
21
10
14
0
21
15
10
24
1
28
29
28
0
29
28
24
21
15
10
1
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS,
COMPUTATIONAL SCIENCE AND SYSTEMS ENGINEERING
DOI: 10.37394/232026.2022.4.8
Anatoly Beletsky
E-ISSN: 2766-9823
69
Volume 4, 2022
The classical Walsh functions occupy the last
row in Table 4, forming the 30-th group of
sequential functions
5,6
SF
. Group
5,6
SF
, as well as
all other groups belonging to the subset
1
, has its
own 28 symmetric bases. Hence, there exist a total
of bases of Walsh-like sequent byte functions.
4 Spectral applications
Let's call the input frequency scale of the DFT
processor the abscissa axis
X
of the Cartesian
coordinate system on which the normalized
frequencies
m
of the input complex-exponential
signal locate
2
( ) exp
m
x t j mt
N
;
, 0, 1m t N
;
2k
N
. (8)
Let's call the output frequency scale the
Y
ordinate axis intended for placing the numbers of
k
th output channels of the processor, from which
the
k
th complex harmonic takes
1
0
( ) ( ) ( , )
N
mm
t
k x t k t
X
. (9)
We will say that some basis provides the
frequency scales of the DFT processor with linear
connectivity if the harmonics (9) of the discrete
signal (8) with maximum amplitude located on the
bisector of the right angle formed by the coordinates
m and k. As an example of a basis delivering linear
connectivity to the frequency scales of a DFT
processor, we can cite the basis of discrete
exponential functions (DEF). Similar bases also
exist in Walsh systems [16]. In particular, in the set
of classical Walsh systems, they are called Walsh-
Cooley bases (
C
), and in the set of sequent Walsh-
like systems, they are the Walsh-Tukey bases (
T
).
Below are the 16-order matrices corresponding to
the systems C and T, respectively.
16
0000000000000000
0000111111110000
0011110000111100
0011001111001100
0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0
0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 1 0
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
0
1
2
3
4
5
6
7
( , ) 8
9
10
11
12
13
14
15
t
c k tС
1 0 1 0 1 0 0 1 0 1
0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1
0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0011110011000011
0000111100001111
0000000011111111
, (10)
k
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS,
COMPUTATIONAL SCIENCE AND SYSTEMS ENGINEERING
DOI: 10.37394/232026.2022.4.8
Anatoly Beletsky
E-ISSN: 2766-9823
70
Volume 4, 2022
16
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
0 0000000000000000
1 0111111110000000
2 0111100001111000
3 0110000110011110
4 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
5 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1
6 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1
7 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1
( , ) 8 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
9 0 0 1 0 1 0
10
11
12
13
14
15
t
kt
T(11).
1 0 1 1 0 1 0 1 0 1
0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1
0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0001100111100110
0001111000011110
0000011111111000
k
The amplitude and phase characteristics of the 16-point DFT processor in the Walsh-Cooley and Walsh-Tukey
function bases calculated by formulas (8)-(11) are shown in Fig. 3 and in Table 8, respectively.
Figure 3. Amplitude-frequency characteristics of complex 16-point DEFs in Cooley and Tukey bases
10,25 10,44
8
11,28
8
10,44 10,25
16
10,25 10,44
8
11,28
8
10,44 10,25
0
2
4
6
8
10
12
14
16
18
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
RESPONSE AMPLITUDE
INPUT FREQUENCY
Spectrum of DEF amplitudes in
Walsh-Cooley-Tukey bases
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS,
COMPUTATIONAL SCIENCE AND SYSTEMS ENGINEERING
DOI: 10.37394/232026.2022.4.8
Anatoly Beletsky
E-ISSN: 2766-9823
71
Volume 4, 2022
Table 8. Phase-frequency characteristics of complex 16-point DFTs in Cooley and Tukey bases
Basis
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
k
Cooley
− 0.20
− 0.39
− 0.65
− 0.79
− 0.92
− 1.18
− 1.37
0
− 0.20
− 0.39
− 0.65
− 0.79
− 0.92
− 1.18
− 1.37
Tukey
− 1.37
− 1.18
− 0.92
− 0.79
− 0.65
− 0.39
− 0.20
0
− 1.37
− 1.18
− 0.92
− 0.79
− 0.65
− 0.39
− 0.20
The above data shows that the amplitude
spectra of signals in the Walsh-Cooley and
Walsh-Tukey bases coincide, while the phase
spectra are opposite. If in some m-output channel
of the DFT point processor, the response phase in
the Walsh-Cooley basis is equal to
()
ck
, then in
the Walsh-Tukey bases
( ) ( )
c
k N k
.
5 Results and discussion
The main results achieved by this study are as
follows. First, the set of groups
,ij
SF
,
1, 6j
, of
arbitrary degree order
N
, is replenished only by
those sequents
ˆi
s
, to the left of which there are
no other sequents (except for
0
s
), and this rule
does not depend on
N
. Second, for a subset of
sequent
1
of the eighth order, the young
sequent
1
ˆ
s
is eight digits apart from the sequent
closest
s
to its right; the next sequent
2
ˆ
s
is apart
by the sequent nearest to its right at four digits,
and so on. And finally, thirdly, the following
feature of Walsh-like systems of sequential
functions is noticed. As it turned out, each of 29
equidistant sequent groups, not taking into
account the 30-th group, which unites the
classical Walsh functions, corresponds to 28
symmetric systems, i.e., to the same number as
the set of classical Walsh functions of length
8.N
It knows [14, 15] that Walsh systems of
order
2n
N
, where
n
is a natural number, are
uniquely defined by the so-called indicator
matrices (IM) of
n
order. IM is right-sided
symmetric binary matrices in the ring of
subtractions modulo 2 (i.e., symmetrical to the
auxiliary diagonal). But if one-to-one mappings
exist between IMs and their corresponding
systems for classical Walsh systems (of arbitrary
order), then such correspondence for sequent
systems should specify.
6 Future research
Briefly formulated above, the main results of the
work predetermine, at least, such directions for
further research:
1. Generalize the results for sequent systems
of arbitrary binary degree order exceeding eight.
2. Confirm (or disprove) the hypothesis about
the existence of a relationship between indicator
matrices and their corresponding symmetric
Walsh-like systems of sequential functions.
3. Evaluate the feasibility of using one-
dimensional (as well as two-dimensional) FFTs
on the bases of sequential functions for various
applications.
7 Conclusions
The main result achieved by this paper should be
considered an expansion by more than an order of
magnitude (more precisely, by a factor of 30) of
the set of Walshe-like systems of the eighth order.
The algorithm's simplicity for synthesizing
Walshe-like systems of sequential functions and
the high speed of spectral processing of discrete
signals provided by the proposed bases open up
to such systems (bases) a broad prospect of
application in various fields of science and
technology.
References
[1] R. Hamming, Coding and Information
Theory, Prentice-Hall, Englewood Cliffs,
1980.
[2] M. Bord, Information Theory and Coding,
U.T. Pres, Cluj-Napoca, 2007.
[3] M. J. McEliece, The Theory of
Information and Coding, 2nd edn.
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS,
COMPUTATIONAL SCIENCE AND SYSTEMS ENGINEERING
DOI: 10.37394/232026.2022.4.8
Anatoly Beletsky
E-ISSN: 2766-9823
72
Volume 4, 2022
Cambridge University Press,
Cambridge, 2002.
[4] A. M. Trakhtman and V. A. Trakhtman,
Fundamentals of the theory of discrete
signals on finite intervals, Moscow: Sov.
Radio, 1975, 208 p.
[5] A. M. Trakhtman, Introduction to the
generalized theory of spectral analysis,
Moscow: Sov. Radio, 1975, 208 p.
[6] S. Kachmazh and G. Shteingauz, The Theory
of Orthogonal Series, Moscow: Fizmathgiz,
1958, 542 p.
[7] H. F. Harmuth, Transmission of Information
by Orthogonal Function, New York:
Springer, 1970, 322 p.
[8] H. F. Harmuth, Theory of Sequential
Analysis: Foundations and Applications,
Moscow: Mir, 1980, 574 p.
[9] Р. R. Gabdullin, L. F. Kopaevich and A.V.
Ivanov, Sequent Stratigraphy, Moscow:
MAKS Press, 2008, 114 p.
[10] B. V. Kostrov. Theory and methodology
of application of sequential analysis for
aerospace image processing, Ryazan: State
Radio Engineering University, 2012, 312 p.
[11] В. A. Sablina. Development and
Research of Image Restoration Algorithms by
Sequential Analysis Methods, Ryazan: State
Radio Eng. University, 2009, 152 p.
[12] B. V. Kostrov, V. K. Zlobin, V. A.
Sablina, Place and role of sequential analysis
in aerospace image processing,
Radiotekhnika, 3, 2012, p.p. 64-75.
[13] V. K. Zlobin, B. V. Kostrov, V. A.
Sablina, Algorithm of Sequential Filtering of
Group Interferences on an Image, Ryazan:
Vestnik of the Russian State Radio Eng.
University, 4 (issue 30), 2009, p.p. 3-7.
[14] А. Ja. Beletsky, O. A. Beletsky, O. G.
Kucher, Synthesis of symmetric Walsh
matrices by conjugate permutation of basis
functions, Kyiv: Ukrainian National
University Press, 2001, p.p. 141-146.
[15] А. Beletsky, Discrete orthogonal bases
of Vilenkin-Krestenson functions, Palmarium
Academic Publishing, Germany, 2015, 232 p.
[16] А. Beletsky, Optimal Walsh and Walsh-
like bases discrete fourier transform,
Ukrainian information security research
journal, 2018, Vol.20 (2), p.p. 104-119.
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
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS,
COMPUTATIONAL SCIENCE AND SYSTEMS ENGINEERING
DOI: 10.37394/232026.2022.4.8
Anatoly Beletsky
E-ISSN: 2766-9823
73
Volume 4, 2022
