Synthesis of Singular Systems Walsh and Walsh-like

Functions of Arbitrary Order

ANATOLY BELETSKY MIKOLAJ KARPINSKI

Department of Electronics Department of Cyber Security

National Aviation University University of the National Education Commission

1, Ave. Liubomyra Huzara, Kyiv 2, St. Podchorazych, Krakow

UKRAINE POLAND

ARSEN KOVALCHUK DMYTRO POLTORATSKYI

Department of Electronics Department of Electronics

National Aviation University National Aviation University

1, Ave. Liubomyra Huzara, Kyiv 1, Ave. Liubomyra Huzara, Kyiv

UKRAINE UKRAINE

Abstract: - Functionally complete systems of Walsh functions (bases), a particular case of alternating piecewise

constant sequential functions, are widely used in various scientific and technological fields. As applied to the

tasks of spectral analysis of discrete signals, the most interesting are those Walsh bases that deliver linear

coherence of the frequency scales of fast Fourier transform (FFT) processors. By the frequency scales of an

FFT processor, we mean the scale on which the normalized frequencies of the input signal are arranged (input

scale) and the scale on which the signal's spectral components are arranged (output scale). The frequency scales

of the FFT processor are considered linearly coherent if the processor responses with maximum amplitudes and

phases of the same sign are located on the bisector of the Cartesian coordinate system formed by the frequency

scales of the processor. None of the known Walsh bases ordered by Hadamard, Kaczmage, or Paley provide

linear coherence of the frequency scales of the FFT processor. In this study, we develop algorithms to

synthesize two systems, called Walsh-Cooley and Walsh-Tukey systems, which turn out to be the only ones in

the set of classical Walsh systems and sequents Walsh-like systems, respectively, that deliver linear coherence

to the frequency scales of FFT processors.

Key-Words: - Walsh function systems, Sequential Walsh-like functions, Linear connectivity of frequency scales

of the DFT processor, Walsh-Cooley and Walsh-Tukey function bases.

Received: July 25, 2023. Revised: May 23, 2024. Accepted: June 22, 2024. Published: July 23, 2024.

1 Introduction

In the theory and practice of spectral analysis of

discrete signals on finite intervals [1, 2], noise-

resistant coding and compression of audio and video

data [3, 4, 5], cryptography protection of information

[6, 7], in cellular communication channels [8] and

other fields of science and technology [9, 10, 11]

functionally complete systems of Walsh functions

(for simplicity

Walsh systems), which are a

particular case of systems of alternating piecewise

constant sequential functions [12], are widely used.

These publications cover a range of applications,

from signal processing, machine learning, encryption,

and medical diagnostics. These can involve advanced

mathematical functions like those discussed in

synthesizing singular systems using Walsh and

Walsh-like functions.

A Walsh system is a set of orthogonal functions

taking values +1 and

over the entire domain of

definition

, where nis a natural number. The

number of features included in a Walsh system is

usually equal to the number of samples Nof the

signal since, in discrete spectral analysis, the number

of harmonics must also be equal to N. The

convenient way to represent these systems is to show

them in square matrices (we will also call them

International Journal of Computational and Applied Mathematics & Computer Science

DOI: 10.37394/232028.2024.4.8

Anatoly Beletsky, Mikolaj Karpinski,

Arsen Kovalchuk, Dmytro Poltoratskyi

E-ISSN: 2769-2477

Volume 4, 2024

Walsh matrices), in which each row is a Walsh

function, and for simplicity, instead of the values of

the elements

and

, write only their signs

. The rows of Walsh matrices are numbered from

top to bottom, and the columns from left to right,

starting from zero. The row number determines the

order of the Walsh function in the system and is

further denoted by the symbol k.

The completeness of Walsh systems implies that

on the definition interval N, it is impossible to

introduce any additional function that would be

orthogonal simultaneously to all other functions

already included in the system [3]. A complete

system of Walsh functions forms a basis of Walsh

space, each function being called a basis function of

the system of the corresponding order. Walsh

systems are formed from basis functions in such a

way that they (functions) form a symmetric matrix of

order N. Matrix symmetry is achieved by the

appropriate ordering of Walsh basis functions.

So far, only three orderings have found use: by

Hadamard, Walsh, and Paley [13]. The enumerated

Walsh systems will be called canonical systems.

Hadamard proposed the first ordering in 1893 in

connection with studies on the theory of

determinants [14]. For example, the Walsh-

Hadamard system (matrix)

of the eighth order

has the form.

0 1 2 3 4 5 6 7

3, (1)

++++++++

+ - + - + - + -

+ + - - + + - -

+ - - + + - - +

=++++----

+ - + - - + - +

++----++

+ - - + - + + -

where the parameters

, 0, 1k t N= -

, define the order

kof the basis function

( , )h k t

, coinciding with the

matrix’s row number and the normalized discrete

time t, respectively.

The simplicity of forming Hadamard-ordered

Walsh function systems [15, 16] has made them

particularly convenient for implementing the fast

Fourier transform (FFT) algorithm using the Cooley-

Tukey scheme [17].

In 1923, Walsh proposed a system in which the

Hadamard basis functions

{ }

( , )

Nw k t=W

, were

ordered by the number of sign changes [18]. Later

(1948), the

systems were called Walsh-

Kaczmage systems [19]. In particular

0 1 2 3 4 5 6 7

++++++++

++++----

++----++

+ + - - + + - -

=+ - - + + - - +

+ - - + - + + -

+ - + - - + - +

+ - + - + - + -

Finally, in 1932, Paley developed [20] another

way of ordering the Hadamard basis functions, which

was reduced to the binary-inverse permutation (BIP)

of binary numbers of Walsh-Hadamard functions.

Subjecting the basis functions of the matrix (1) to

BIP, we arrive at the system of Walsh-Paley

functions of the eighth order.

0 1 2 3 4 5 6 7

3. (2)

++++++++

++++----

+ + - - + + - -

++----++

=+ - + - + - + -

+ - + - - + - +

+ - - + + - - +

+ - - + - + + -

Matrices

of arbitrary order

, can be

compiled using a simple recurrence rule [3], the

essence of which is reduced to the following

transformations. Each row of the matrix

/2N

written twice, and then to the first of them (let us call

it even), the elements of the same row are assigned

from the right, i.e., the elements of the right half of

the even row repeat the elements of its left half, and

to the second (odd row) －the opposite

(complementary) elements. Let us call the above

method of forming Walsh-Paley function systems a

International Journal of Computational and Applied Mathematics & Computer Science

DOI: 10.37394/232028.2024.4.8

Anatoly Beletsky, Mikolaj Karpinski,

Arsen Kovalchuk, Dmytro Poltoratskyi

E-ISSN: 2769-2477

Volume 4, 2024

repeated-complementary algorithm or, for short, an

R.C. algorithm.

In many applications, the Walsh-Paley systems

proved preferable to the previously obtained

Hadamard and Kaczmage systems. For this reason,

the Walsh-Paley function systems

are reference

systems in the sense that by the appropriate

permutation of the numbers kof basis functions of

these systems, one can obtain the matrices of all

remaining classical Walsh systems [21], the total

number of which

the relation determines.

( )

2 (mod 2)

L i

= -

. (3)

For some values of n, the estimates

calculated

in formula (3) are given in Table 1.

Table 1. Number of symmetric

systems of Walsh functions

448

13ˈ888

128

256

888ˈ832

112ˈ881ˈ664

28ˈ897ˈ705ˈ984

Along with the most common way of representing

the elements of Walsh matrices in the form + and

coded matrices are often used. In these matrices, the

"plus" sign is replaced by the digit 0 and the "minus"

by the digit 1, thus transferring Walsh systems from

the space of originals to the space of images. As a

result of such substitution, the matrix (2), for

example, takes the form (4).

0 1 2 3 4 5 6 7

0 00000000

1 00001111

2 0 0 1 1 0 0 1 1

3 00111100 . (4)

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

The transition from the original space to the image

space is accompanied by replacing the bitwise

multiplication operations by modulo 2 bitwise

addition operations.

The main disadvantage of the R.C. algorithm for

synthesizing systems of Paley functions is that the

calculation of the matrix of the order

2n+

must

precede the computation of the matrix of the order

. An alternative to the recurrent R.C. algorithm is

the empirically established [21] algorithm for direct

computation of basis functions of Paley systems,

hereafter referred to as the D.C. algorithm. The

essence of the estimation scheme of the D.C.

algorithm for the system of Paley basis functions in

image space is as follows. Irrespective of the

ordering method, the elements of the null order

functions in any Walsh system are equal to 0, i.e.,

( )

0, 0p t =

. (5)

The elements of the first-order basis functions,

called generating functions of Walsh-Paley systems,

are defined by the expression

( )

0, 0, / 2 1

1, / 2, 1

t N

p t

t N N

= -

. (6)

Expressions (5) and (6) are the initial conditions

of the Walsh-Paley system synthesis algorithm,

which directly follow from the matrix (4), and if

, then the relations hold:

( ) ( )

( )

2 , , 2 N

p k t p k t=

(7)

– even and

( ) ( ) ( )

2 1, 2 , 1,p k t p k t p t+ =

– odd basis functions.

In the right part of equality (7), the notation

( )

means calculating the remainder of a number

2tmodulo N.

The systems of Walsh functions, which we denote

{ }

( , ) ,k tj

are widely used as bases for the discrete

Fourier transform (DFT). The spectrum

( )

the complex discrete signal

( )

x t

, formed by the

DFT processor in Walsh function basis, is defined by

the relation

( ) ( ) ( , ), (8)

m m

k x t k t

= j

International Journal of Computational and Applied Mathematics & Computer Science

DOI: 10.37394/232028.2024.4.8

Anatoly Beletsky, Mikolaj Karpinski,

Arsen Kovalchuk, Dmytro Poltoratskyi

E-ISSN: 2769-2477

Volume 4, 2024

in which N sample volume, m  normalized input

signal frequency, k  signal harmonic number, and t

signal reference number (discrete time).

The amplitude-frequency and phase-frequency

characteristics (AFC and PFC) of DPF processors are

usually computed concerning a discrete exponential

signal (DES)

( ) exp

x t j mt

, 0, 1m t N= -

. (9)

For small values of N, spectrum estimation is

solved quite simply using the graph-analytical

method of calculation, the essence of which is shown

in Fig. 1 for the eight-point DPF based on Walsh-

Paley functions (2) when calculating, for example,

the harmonic

1(1)X

Fig. 1. To the definition of the harmonic

1(1)X

in the basis of Walsh-Paley functions

The points in Fig. 1 mark the vectors of input

signals involved in the formation of the response

1(1)X

in the first output channel of the processor,

and the digits in the vicinity of these points indicate

the value of the time reference tof the first order

basis function

(1, )p t

. According to the matrix (2),

the vectors of the first four samples of signal

1( )x t

are taken with a +sign and the remaining

( 4, 7)t=

with a  sign.

FFT processors realized according to the Cooley-

Tukey scheme in different Walsh bases provide the

following characteristics of the spectrum of signal (9)

at integer frequencies. Firstly, the spectrum consists

of a set of pairs of harmonics, and in each pair, the

harmonics have the same amplitudes but opposite

signs of initial phases. Secondly, for all the above

Walsh bases, if an "even" signal (i.e., the frequency

mis even) is fed to the input of the FFT processor,

then only the even output channels of the processor

"ring," and vice versa.

The harmonics of the discrete complex-

exponential signal, whose sample size is eight, in the

Walsh-Paley function basis are given in Table 2 for

"odd" and Table 3 for "even" harmonics. The

complex values

of the harmonics are denoted as

follows:

( , )z a b=

, where

and

are the real and

imaginary components of the vector

, respectively.

Table 2. Odd harmonics of the

complex-exponential signals (9)

Table 3: The even harmonics of the

complex-exponential signal (9)

(0)

(2)

(4)

(6)

4(1, 1)

4(1,

1) -1)

4(1, 1)

Similar discrete complex-exponential signals

spectrum calculations can be performed for an

arbitrary Walsh basis.

Let us introduce the concepts of the frequency

scales of the FFT processor (as well as FFT). The

abscissa axis Xof the Cartesian coordinate system,

on which we place the normalized frequencies mof

the input signal

( )

x t

, lets us call the input

frequency scale of the processor. The ordinate axis Y,

on which we will put the number of koutput

channels of the processor, is designed to capture the

harmonic of the signal

( )

x t

, we will call the output

frequency scale of the processor.

(1)

(3)

2(1, 1 2)+

2(1, 2 1)-

2(1 2, 1)+ -

2(1 2, 1)-

2(1, 1 2)-

2(1, 1 2)- -

2(1 2, 1)- -

2(1 2, 1)+

1(5)X

1(7)X

2(1, 1 2)-

2(1, 1 2)- -

2(1 2, 1)- -

2(1 2, 1)+

2(1, 1 2)+

2(1, 2 1)-

2(1 2, 1)+ -

2(1 2, 1)-

International Journal of Computational and Applied Mathematics & Computer Science

DOI: 10.37394/232028.2024.4.8

Anatoly Beletsky, Mikolaj Karpinski,

Arsen Kovalchuk, Dmytro Poltoratskyi

E-ISSN: 2769-2477

Volume 4, 2024

Selecting from the tables containing the complex

spectrum of the signal (9), harmonics with maximum

amplitude and positive phase, we plot the

relationship between the frequency scales mand kof

the eight-point DPF processors in Walsh bases

ordered by Hadamard, Kaczmage, and Paley (Fig. 2).

Hadamard Basis Kaczmage Basis Paley Basis

Fig. 2. Ratio of frequency scales of DFT processors in canonical Walsh bases

For plotting in Fig. 2, we chose harmonics with

positive phases because none of the harmonics with

negative phases in the canonical Walsh bases falls on

the bisector of the coordinate axes (m,k), which

significantly distorts the trajectory of the location of

points on the plane (X,Y), far from linear.

We will say that a specific basis provides the

frequency scales of the DFT processor with linear

coherence if the harmonics of the discrete complex-

exponential signal with maximum amplitude and

unchanging in sign phase are located on the bisector

of the right angle formed by the coordinate axes m

and k. Alternatively, in other words, the frequency

scales of the DFT processor are linearly coherent if,

when samples of a complex-exponential signal are

input to the input of the DFT processor, the

maximum "ringing" will be in the output channel

whose number kcoincides with the frequency of the

input signal m. Linear coherence to the frequency

scales of the DFT processor is provided, for example,

by the basis of discrete exponential functions (DEF).

2 Statement of the Research Problem

As follows from the graphs presented in Fig. 2, none

of the three canonical Walsh bases, ordered by

Hadamard, Kaczmage, or Paley, provide linear

coherence to the frequency scales of DFT processors,

which complicates their application in spectrum

analysis oriented to the measurement of the

frequency of input signals. The mentioned

disadvantage of the canonical Walsh function

systems was the starting point that predetermined the

most critical problem solved in this study, namely,

the development of algorithms for the synthesis of

Walsh and Walsh-like bases (the definition of

Walsh-like bases is given in Section 4) that deliver

linear coherence to the frequency scales of DFT

processors. Such Walsh systems will be called

singular.

3 Walsh-Cooley singular systems

Let us try to understand the reason for the nonlinear

coherence of the frequency scales of FFT processors

in the canonical Hadamard, Kaczmage, and Paley

bases. For this purpose, we turn (see Fig. 3) to the

tree of an eight-point FFT on the Cooley-Tukey

scheme.

Fig. 3. Directed graph of the eight-point FFT

the algorithm in the DEF basis

To give the harmonics kof the spectrum

( )k

natural linearly increasing ordering, the sample

numbers tof the input signal

( )x t

must be subjected

to BIP.

International Journal of Computational and Applied Mathematics & Computer Science

DOI: 10.37394/232028.2024.4.8

Anatoly Beletsky, Mikolaj Karpinski,

Arsen Kovalchuk, Dmytro Poltoratskyi

E-ISSN: 2769-2477

Volume 4, 2024

The symbol

in Fig. 3 denotes the FFT

processor’s complex phase multipliers (PM) in the

DEF basis, the degrees of which are defined by the

expression

exp , 0, 1

lj l l N

Y = - = -

The set of multipliers

0, 3l=

, used in the

third step of the eight-point FFT tree (Fig. 4), is

covered by an arc. The light circle highlights the PM

included in the set, and the arc's arrow rests on the

vector of the multiplier not included in this set.

Fig. 4. Phase multipliers of the DEF basis

for the eight-point DFT

To ensure the transition to the Walsh function

basis, we approximate the PM of the DEF system

located in the lower complex half-plane by values

, and in the upper half-plane by values

, as

shown in Fig. 5.

Fig. 5. Approximation of DEF phase multipliers

If the numbers tof time samples of the signal

( ),x t

fed to the input of the FFT processor form a

natural sequence (see Fig. 6), then the output of the

processor’s spectrum based on Walsh-Hadamard

functions (H) is formed. If the numbers tare

subjected to BIP, the processor forms a spectrum in

the Walsh-Paley function basis (P). Finally, if, in

addition to BIP, the numbers of samples of the input

signal are transformed by the inverse Gray code, then

we obtain a spectrum in the Walsh-Kaczmage

function basis (W).

Fig. 6. Directed graph of the eight-point FFT the

algorithm

The + sign in the butterfly operators means that

the weight of the lower edge of the operator is +1,

and thus, the operator performs the transformation

shown in Fig. 7.

Fig. 7. "Butterfly" operator

From the analysis of the approximation of the

complex phase multipliers shown in Fig. 5, from the

engineering point of view, the proposed

approximation can hardly be recognized as rational.

More appropriate should be considered the

approximation in which the multipliers located in the

right (positive concerning the abscissa axis) complex

half-plane are replaced by positive units, and the

PMs from the left (negative) half-plane are replaced

by negative units.

This kind of PMs approximation can be achieved,

as shown in Fig. 8, by rotating the unit circle on the

complex plane counterclockwise by the angle

/ 2p

In this case, the position of the coordinate axes and

the arc encompassing the phase multipliers of the last

step of the FFT tree should remain unchanged.

International Journal of Computational and Applied Mathematics & Computer Science

DOI: 10.37394/232028.2024.4.8

Anatoly Beletsky, Mikolaj Karpinski,

Arsen Kovalchuk, Dmytro Poltoratskyi

E-ISSN: 2769-2477

Volume 4, 2024

Fig. 8. Modified approximation

phase multipliers of the DEF

The butterfly operator with negative PM (let us

call it the inverse operator) realizes the

transformation shown in Fig. 9.

Fig. 9: Inverse operator "butterfly"

Let us make a tree of the eight-point FFT

algorithm (Fig. 10), the sequence of phase

multipliers in the third stage of the transformation,

which

( , , , )+ + - -

is chosen based on the

approximation presented in Fig. 8.

Fig. 10. Tree of the modified FFT algorithm

Following the transformations shown in Figs. 9

and 10, we easily arrive at the Walsh system

(denoted by

), which we will call the Walsh-

Cooley system of functions, thus paying tribute to

the positive influence of the Cooley-Tukey algorithm

on the emergence of a new way of ordering the basis

functions of Walsh systems. The Walsh-Cooley

system was first reported at the International

Conference in Wroclaw [22] in 2000. The eighth-

order matrix

of the Walsh-Cooley system is

represented by the expression (10):

0 1 2 3 4 5 6 7

0 00000000

1 0 1 0 1 0 1 0 1

2 0 0 1 1 0 0 1 1

3 0 1 1 0 0 1 1 0 . (10)

4 00001111

5 0 1 0 1 1 0 1 0

6 00111100

7 0 1 1 0 1 0 0 1

The Walsh-Cooley functions

( , )c k t

in the image

space are calculated by formulas similar to formulas

(4)  (6) for the basis functions

( , )p k t

of Walsh-

Paley systems and differ from the latter only by the

values of the first order functions. In particular,

0, 0, 1 and , 1,

4 4

(1, ) 3

1, , 1.

4 4

N N

t t N

c t N N

= - = -

= -

And if

, then

(2 , ) ( , (2 ) )

c k t c k t=

(11)

 for even functions and

(2 1, ) (2 , ) (1, )c k t c k t c t+ =

 for odd functions.

Perhaps one of the first mathematicians to point

out that Walsh function systems are somehow related

to Gray's codes was Dr. C. Yen, a professor at the

University of Sydney. In particular, he found [23]

that if the binary numbers of the rows (basis

functions) of the matrix of the Walsh-Paley system

(P) are rearranged according to the law of Gray's

inverse transformation (coding), we come to the

Walsh system ordered at Kaczmage (W). Naturally,

rearranging the strings of the Walsh-Kaczmage

system by the direct Gray code restores the Walsh-

International Journal of Computational and Applied Mathematics & Computer Science

DOI: 10.37394/232028.2024.4.8

Anatoly Beletsky, Mikolaj Karpinski,

Arsen Kovalchuk, Dmytro Poltoratskyi

E-ISSN: 2769-2477

Volume 4, 2024

Paley system. It was noted above that the DIP of the

basis functions of the Walsh-Hadamard system

transforms it into the Walsh-Paley system and vice

versa. The complete picture of the interrelation of the

systems P,H, and Wby Yen is presented in Fig. 11,

in which, for simplicity, the DIP operation is denoted

by symbol 1, and the operations of the direct and

inverse Gray transformations by symbols 2 and 3,

respectively.

Fig. 11. Relationship of function numbers

of Walsh's canonical system

According to Fig. 11, to transform the system W

into H, the numbers of basis functions of the system

Wmust first be rearranged according to the law of

the direct Gray code 2 and thus transform the system

Winto the system P, and then perform DIP over the

numbers of functions of the system Pusing operator

1. Consequently, the system of functions Wis

transformed into Husing code 21, which belongs to

a subset of the so-called composite Gray codes

(CGC). The inverse transformation of the system of

functions Winto His performed using the code

inverse to CGC 21, i.e., using the code .

Gray's codes, proposed in 1953 in response to the

requests of engineering practice concerning the

construction of optimal converters of the

"angle -code" type according to the criterion of

minimum ambiguity error [10], at the dawn of their

appearance, attracted the attention not only of

mathematicians but also a wide range of developers

of various electronic equipment. As noted above, the

canonical Walsh systems are interconnected by

classical Gray operators. In contrast, the new Walsh-

Cooley system falls out of this chain of

interconnection. The possibility of constructing

codes inverse in the direction of formation to the

classical Gray codes was out of the researchers' field

of view. In the known (classical) scheme (Fig. 12),

the formation process of direct and inverse Gray

codes develops in the direction from left to right. On

this basis, let us call the classical method of Gray

transformation left-sided. In this case, the

transformed number’s high (left) digit remains

unchanged in both forward and reverse

transformations.

At the same time, it is possible to propose a

scheme of the Gray transformation [21], reversed to

the direction of the classical (left-sided)

transformation. In such a class of transformations,

(a) (b)

Fig. 12: Graphs of the forward (a) and backward (b) Gray's left-sided transform

which is called right-sided (Figure 13); the value of

the transformed number’s lower (right) digit remains

unchanged in the forward and reverse

transformations, denoted by symbols 4 and 5,

respectively.

(a) (b)

Fig. 13. Graphs of forward (a) and backward (b) Gray's right-sided transform

International Journal of Computational and Applied Mathematics & Computer Science

DOI: 10.37394/232028.2024.4.8

Anatoly Beletsky, Mikolaj Karpinski,

Arsen Kovalchuk, Dmytro Poltoratskyi

E-ISSN: 2769-2477

Volume 4, 2024

From the comparison of Figs. 12 and 13, we see

that we arrive at the right-sided Gray transform by

expanding the graphs of the left-sided transform by

180°

for the vertical axis of symmetry. The

fundamental difference between left- and right-sided

Gray codes is as follows. If, during the left-sided

Gray transformation, the Hemming distance between

adjacent code combinations remains constant and

equal to one, then, during the right-sided

transformation the noted property of classical Gray

codes is violated, which can be traced by Table 4.

Table 4: Towards a comparison

of Gray's transformations

Dec

Bin

000

001

011

010

011

110

011

010

101

100

110

100

101

111

110

101

010

111

100

001

Let us summarize Gray's simple operators in

Table 5, including also the operator 0, which is a unit

matrix, and the operators of cyclic shifts by one digit

to the right, denoted by the numerical symbol 6, and

to the left, which we will indicate by the symbol 7.

Table 5: The operators of simple Gray

transformations

Design.

operator

The operation to be performed

0(е)

Saving the source code

Inverse code rearrangement

Gray's direct left-sided transform

Gray's inverse left-sided transform

Gray's direct right-sided transform

Gray's inverse right-sided transform

tra

Cyclic shift one digit to the right

Cyclic shift one digit to the left

The listed operators of simple Gray

transformations can be represented in matrix form,

and the order nof these matrices coincides with the

degree of two in the expression

,2n

by which

the order of Walsh matrices is given. In particular,

the matrices of simple Gray transform operators

accompanying Walsh systems of the eighth order are

presented in Table 6.

Table 6. Matrix forms of simple Gray operators

1 0 0

0 0 1 0

0 0 1

1 0 1 0

1 0 0

1 1 0

2 0 1 1

0 0 1

1 1 1

3 0 1 1

0 0 1

1 0 0

4 1 1 0

0 1 1

1 0 0

5 1 1 0

1 1 1

0 1 0

6 0 0 1

1 0 0

0 0 1

7 1 0 0

0 1 0

We come to the following conclusions from the

data analysis in Table 6. First, the matrices of simple

Gray operators are right-sided symmetric,i.e.,

symmetric concerning the auxiliary diagonal, and the

operators 0 and 1 correspond to bilaterally symmetric

matrices. Second, the pairs of Gray matrices

(operators) located in the rows of Table 6 (except for

the operators of the first row) are mutually inverse,

which means that

0 1 1=

. The multiplication

operation is performed over the field

According to (7), there are 28 symmetric Walsh

systems of the eighth order. In contrast, using

classical Gray codes, it is possible to connect, as

shown in Fig. 10, only three systems ordered by

Hadamard, Kaczmage, and Paley. The reason for the

incompleteness of the interconnection graph to cover

all Walsh systems of fixed order Nis that the

approach proposed by S. Yen, based on the use of

only classical (left-sided) Gray transformations,

turned out to be a dead end.

All Walsh systems of order Nconsist of the same

complete set of basis functions and differ from each

other only by the ways of their ordering.

The problems related to the development of

algebraic methods for ordering basis functions

symmetrizing Walsh systems became solvable only

after the introduction of right-sided Gray

transformations [21]. Fig. 14, a development of the

scheme for transforming Walsh systems according to

C. Yen (see Fig. 11), is the simplest example

International Journal of Computational and Applied Mathematics & Computer Science

DOI: 10.37394/232028.2024.4.8

Anatoly Beletsky, Mikolaj Karpinski,

Arsen Kovalchuk, Dmytro Poltoratskyi

E-ISSN: 2769-2477

Volume 4, 2024

illustrating the application of the direct right-sided

Gray transform operator (operator 4).

Fig. 14. Tree of the interrelation

of the fourth order Walsh systems

The complete graph of the systems of Walsh

functions of the eighth order is shown in Fig. 15.

Fig. 15: The complete graph of Paley-connected

of the eighth order Walsh systems

The large Latin letters in the graph nodes denote the

invariant fundamental Walsh systems, named so

because the algorithm for their synthesis does not

depend on the order Nof the Walsh systems. The

numbers in the nodes of the contours denote the

numbers of systems that, together with the invariant

systems, constitute the complete set of classical Walsh

systems of the eighth order. The directed edges

connect the tree nodes, each assigned a weight equal

to a simple or symmetric composite Gray code.

Let us briefly explain how, based on the eighth-

order Walsh-Paley matrix Pgiven by expression (4),

we can obtain, for example, the Walsh matrix

number 15 (denoted by

). The matrices Pand

are related by the CGC

(242)=G

. Based on

the data in Table 6, we have

1 1 0 1 0 0 1 1 0

242 0 1 1 1 1 0 0 1 1

0 0 1 0 1 1 0 0 1

= =

0 1 1

1 1 1 ,

0 1 0

which leads to the value

0 0 1

1 0 0

1 1 0

The numbers

of the basis functions of the

system

are related to the numbers

of the

basis functions of the Walsh-Paley system by the

relation

15 p

k k=G

By successively searching the states of three-bit

numbers

, we arrive at the values of the row

numbers of the matrix

(see Table 7), in which

rows of matrix Pare moved.

Table 7. Rearrangement of rows

of the matrix Pto the rows of the matrix

The matrix

has the form

International Journal of Computational and Applied Mathematics & Computer Science

DOI: 10.37394/232028.2024.4.8

Anatoly Beletsky, Mikolaj Karpinski,

Arsen Kovalchuk, Dmytro Poltoratskyi

E-ISSN: 2769-2477

Volume 4, 2024

0 1 2 3 4 5 6 7

0 00000000

1 0 1 0 1 0 1 0 1

2 00111100

3 0 1 1 0 1 0 0 1 .

4 0 0 1 1 0 0 1 1

5 0 1 1 0 0 1 1 0

6 00001111

7 0 1 0 1 1 0 1 0

The considered example explaining the algorithm

of calculating the matrix

leads to the following

constructive conclusion. Each matrix Wof a Walsh

system of order

corresponds to a uniquely

related matrix of order n, which we will call an

indicator matrix (IM) and denote by J. The IMs of

Walsh systems are binary right-sided symmetric

matrices that are non-degenerate over the field

The number

of IMs of size ncoincides with the

number of Walsh systems of order Nand is

determined by expression (3). Knowing the IM J,

one can easily find the matrix Wcorresponding to it.

For this purpose, it is enough to use the formula

w p

k k=J

, (12)

where

rows of the Walsh-Paley matrix Pare

transferred to

rows of the matrix W.

Naturally, the Cooley-Tukey FFT tree remains

unchanged regardless of the basis realized by the

FFT processor. At the same time, for the processor to

form the signal spectrum on one or another basis, the

time samples of the signal at the input of the

processor must be subjected to a permutation

depending on the chosen transformation basis (see,

for example, Fig. 6). Using the relation (12), let us

show what permutations should be subjected to the

numbers of the signal samples at the input of the FFT

processor to obtain the spectrum of the signal in the

Walsh-Cooley function basis. For this purpose, let us

refer to Fig. 15. As we can see, the transition from

the Walsh-Paley system (P) to the Walsh-Cooley

system (C) is carried out as a result of the

rearrangement of row numbers of the Walsh-Paley

matrix by the inverse Gray's transformation right-

sided (whose numerical symbol is 5). The latter

means that the IM of the Walsh-Cooley system

(see Table 6) the matrix

1 0 0

5 1 1 0

1 1 1

c= =J

. (13)

Substituting matrix (13) into formula (12) and

taking into account that the sequence of numbers

is formed by DIP of the sequence of natural

numbers

, we come to the summary Table 8 of

permutations of the signal samples at the input of the

eight-point FFT processors, providing the formation

of DES spectra (8) in the corresponding bases.

Table 8: Rearrangement of signal count numbers

at the input of FFT processors in basis H,P, and C

Among the numerous Walsh systems, the Walsh-

Cooley systems are the only ones that provide

delivers linear coherence to the frequency scales of

the DFT processor. As a consequence, the frequency

of the input signal can be unambiguously determined

by the number of processor output channels in which

the response with maximum modulus and negative

phase is observed. None of the remaining Walsh

systems provides similar linear coherence to the

frequency scales of DFT processors. This is the

uniqueness of Walsh-Cooley systems.

Let us use the graph-analytical method of

calculating the harmonics of the complex-

exponential signal (11) in the Walsh-Cooley function

basis (10), assuming the sample size to be eight. An

example of harmonic calculation

1(1)X

is shown in

Fig. 16.

Fig. 16. Harmonic definition

1(1)X

Summing up the marked vectors and

distinguishing the real and imaginary parts, we

obtain:

1(1) 2(1 2, 1)X= + -

International Journal of Computational and Applied Mathematics & Computer Science

DOI: 10.37394/232028.2024.4.8

Anatoly Beletsky, Mikolaj Karpinski,

Arsen Kovalchuk, Dmytro Poltoratskyi

E-ISSN: 2769-2477

Volume 4, 2024

The results of similar calculations of harmonics of

"even" signals are summarized in Table 9 and of

"odd" signals  in Table 10.

Table 9: Harmonics of "even"

signals in the Walsh-Cooley basis

(0)

(2)

(4)

(6)

4(1,

4(1, 1)

4(1, 1) 1)

4(1,

Table 10. Harmonics of "odd"

signals in Walsh-Cooley basis

(1)

(3)

2(1 2, 1)+ -

2(1 2, 1)-

2(1, 1 2)-

2(1 2, 1)- -

2(1 2,1)+

2(1, 1 2)+

2(1, 2 1)-

1(5)X

1(7)X

2(1 2, 1)- -

2(1 2,1)+

2(1, 1 2)+

2(1, 2 1)-

2(1 2, 1)+ -

2(1 2, 1)-

2(1, 1 2)-

2(1, (1 2))- +

The analysis of Tables 9 and 10 shows that on the

main diagonals of the matrices of spectra, there are

harmonics with maximum modulo and negative

phases. The harmonics

0(0)X

and

4(4)X

are

natural, and their phases are equal to zero.

4 Walsh-Tukey singular systems

At least these properties are characteristic of classical

Walsh systems:

1. The weight of each basis function of the system,

except for the null order function (let us call it the

zero function), is equal to N/ 2;

2. All non-zero basis functions in both the left and

right halves contain the same number, equal to N/ 4,

of 0 and 1 elements except for the function whose

left half consists of only zeros and whose right half

consists of only ones;

3. The Hemming distance between any pair of

basis functions included in the system is N/ 2.

The so-called Walsh-like systems of (0,1)-

sequential functions are alternatives to the classical

Walsh systems. We will refer to Walsh-like systems

that preserve the first and third properties of classical

Walsh systems mentioned above but in which the

second property is not satisfied for all basis functions.

Or, in other words, to Walsh-like systems, we will

refer to such (0, 1)-sequent systems [12], in whose

basis functions the number of zeros and ones in each

half of the definition interval is not necessarily the

same as in the classical Walsh functions.

Let us estimate the number of symmetric

orthogonal Walsh-like systems

(0,1) -

of the eighth

order [24]. Let us form the set of sequential

functions, including only those that begin with zero,

i.e., the sequential left digit contains the digit 0, and

the remaining lower seven digits contain three zeros

and four ones. Hence, the complete

set contains

35 non-zero eighth-order sequents, which is

determined by the number of seven-by-three

combinations. All these functions are summarized in

Table 11.

Table 11. Set of sequential functions of the eighth order

Discharge number

International Journal of Computational and Applied Mathematics & Computer Science

DOI: 10.37394/232028.2024.4.8

Anatoly Beletsky, Mikolaj Karpinski,

Arsen Kovalchuk, Dmytro Poltoratskyi

E-ISSN: 2769-2477

Volume 4, 2024

Let us match to each sequential function from

Table 11 a set of sequents (highlighted by shading)

separated from the forming sequents located in the

diagonal elements of Fig. 17 by the Hamming distance

d= 4.

Fig. 17: Set of functions distant from the forming sequent at Hamming distance

4d=

International Journal of Computational and Applied Mathematics & Computer Science

DOI: 10.37394/232028.2024.4.8

Anatoly Beletsky, Mikolaj Karpinski,

Arsen Kovalchuk, Dmytro Poltoratskyi

E-ISSN: 2769-2477

Volume 4, 2024

The left column of Fig. 17 shows the numbers of

the forming sequents, and the top row shows the

numbers of sequents that are the Hamming distances

away from the forming sequents, equal to 4.

In the following, we will stick to the following

notations: the lowercase letter

will denote a

specific j-th sequent,

0, N

j L=

, representing an N-bit

vector (in this article, it is a byte), and the uppercase

letter

i-S

the set of all sequents located in the

shaded elements of the i-th row of the table in Fig. 17,

1,35i=

, including the zero sequent not shown in this

figure

. Let, in addition,

€

i-s

be a sequent forming

the complete group of functions for which we

introduce the symbol

,i j

(Sequence Full).

Let us note such features of Fig. 17. Firstly, the

table is symmetric concerning the main diagonal.

Second, each table row, except for the forming

sequent

€

(the light diagonal element of the table,

highlighted by the bold frame), includes 18 sequents

, separated from the forming element

€

by the

Hamming distance

€

( , ) 4

k j

d=s s

. Finally, third, the

entire set

of rows

of the table can be

partitioned into ten non-overlapping subsets

1,10l=

, with l-th subset including consecutive rows

containing the same number

of sequents to the

left of the sequent

€

. For example, the subset

generated by the sequents

€j

1, 5j=

, with

10n=

; a

second subset

is formed by the sequents

€j

6, 9j=

, for which

23n=

, etc.

Information about the subsets

is contained in

Table 12

Table 12. Composition of subsets of

sequential functions

Numbers of lsubsets of the sequent

# sequent

€

1-5

6-9

10-12

13-15

16-19

20-22

23-25

26-28

29-31

32-35

The forming sequents

€

, together with the zero

sequential function

and 18 sequents located in the

rows of the table in Fig. 17, form six complete

groups of pairwise equidistant code combinations.

The groups of sequential functions

i j

formed by

the forming sequents

€

of the subset

1,W

are given

in Table 13.

Table 13. Composition of groups formed by the forming sequences of the subset

1, j

Group Sequences

2, j

3, j

International Journal of Computational and Applied Mathematics & Computer Science

DOI: 10.37394/232028.2024.4.8

Anatoly Beletsky, Mikolaj Karpinski,

Arsen Kovalchuk, Dmytro Poltoratskyi

E-ISSN: 2769-2477

Volume 4, 2024

4, j

5, j

Sequent

, included in the groups

,i j

, are

marked with gray cells in the rows of Table 13, and

their corresponding jfunction numbers are in the

black rows of the table above the sequences, with the

row element containing the number iof the forming

sequent

€

, lightened. The left column of Table 13

contains the numbers of

1,6j=

groups

,i j

formed by the sequents

€

1,5i=

, constituting a

subset of

. The 30 groups summarized in Table 13,

corresponding to the subset of sequential functions

, constitute the complete set of groups of pairwise

equidistant sequential functions. That means, in

particular, that the group of functions formed by any

sequent

€j

6 35j

, is absorbed by one of the

groups of the subset

,i j

. Let us confirm

the above statement. For this purpose, let us choose,

for example, as forming sequents

€

and

€

whose complete groups of equidistant functions are

presented in Table 14.

Table 14. Composition of sequential function groups formed by the elements

€

and

€

Groups

Group Sequences

17, j

33, j

From the data comparison, we can easily see that

any group from Table 14 is in one of the rows of

Table 13. The correspondence between the groups

17, j

33, j

1, 6j=

, and the groups

( , )i j

of the

subset

is shown in Table 15.

Table 15. Correspondence of groups of sequential

functions, formed by the elements

€

and

€

17, j

( , )i j

2,3

2,5

4,1

4,6

5,1

5,6

33, j

( , )i j

2,2

2,5

3,2

3,5

5,1

5,3

International Journal of Computational and Applied Mathematics & Computer Science

DOI: 10.37394/232028.2024.4.8

Anatoly Beletsky, Mikolaj Karpinski,

Arsen Kovalchuk, Dmytro Poltoratskyi

E-ISSN: 2769-2477

Volume 4, 2024

Let us notice the mosaic of rectangular squares

(Table 13), in which the groups of equidistant

sequents of the subset

are placed. The coloring of

all the squares turns out to be the same, which

provides an opportunity to significantly reduce the

labor intensity of the computation of the composition

of the groups of the subset

. Indeed, suppose that

a site mosaic is composed for groups

1, j

for

which the constituent is a sequent of

€

. To compute

the sequents of any groups

,i j

, is enough to

replace the top line

in the group pad

1, j

line

, composed of the sequents of the i-th line of

Table 13, excluding all its empty elements.

Generating basis function

(1, )t

of Walsh-like

systems of order Nis defined by the expression

( /2) ( /2 1)

(1, ) 01 0 , 0, 1

N N

t t N

= = -

, (14)

where

( )

times

a a a a=K

14243

When forming the Walsh-Tukey systems, we will

consider such features of these systems.

First, the even basis functions

(2 , )k t

are

defined in a way similar to the way of calculating the

even basis functions in Walsh-Cooley systems, i.e.

(2 , ) ( , (2 ) )

k t k t

t t

. (15)

Second, the elements of the left and right halves

of odd basis functions are mutually complementary,

i.e.

(2 1, / 2) (2 1, ),

0, / 2 1

k t N k t

t N

t t

+ + « +

= -

, (16)

where

denotes the function complementary to the

function

Based on expressions (14) and (15), let us

compose the partially unfilled matrix

of the

Walsh-Tukey system of the eighth order.

(1)

3 5 6 7

00000000

01111000

0 1 1 0 0 1 1 0

3 0 1 0 1 . (17)

0 1 0 1 0 1 0 1

5 0 0 1 1

6 0 0 1 0

7 0 0 0 1

0 1 2 4

The numbers of rows and columns to be filled in

at the first stage of matrix formation are marked in

bold in (18)

(1)

8.T

Using the relation (16), we restore

some of the missing elements in the matrix (17) and,

thus, come to the matrix, in which the numbers of

those rows and columns are highlighted, which

underwent changes during the second stage of

transformation.

(2)

0 1 2 4

0 00000000

1 01111000

2 0 1 1 0 0 1 1 0

0 1 0 1 0 1 . (18)

4 0 1 0 1 0 1 0 1

0 0 1 0 1 1 0 1

0 0 1 1 0 0 1 1

000 111

3 5 6 7

As a result of the second stage of transformation,

the fifth and sixth rows (as well as columns) of

matrix (18) turned out to be filled. The uncertainty

concerning the empty elements in the third and

seventh rows of the matrix (18) is easily resolved in

this way. Let us construct (see Fig. 18) a system

consisting of eight vectors corresponding to the input

signal samples on the complex plane, the normalized

frequency of which equals three. Let us mark the

vectors with the elements of the third row of the

matrix (18), thus calculating the harmonic

3(3).

International Journal of Computational and Applied Mathematics & Computer Science

DOI: 10.37394/232028.2024.4.8

Anatoly Beletsky, Mikolaj Karpinski,

Arsen Kovalchuk, Dmytro Poltoratskyi

E-ISSN: 2769-2477

Volume 4, 2024

Figure 18: To calculate the harmonic

3(3)

According to Fig. 18, the maximum of the

harmonic

3(3)

can only be under the condition that

the third and seventh elements of the third row of the

matrix (19) are 0 and 1, respectively, which

completes the formation of the matrix

, which will

take the form

0 1 2 4

0 00000000

1 01111000

2 0 1 1 0 0 1 1 0

0 1 0 0 1 0 1 1 . (19)

4 0 1 0 1 0 1 0 1

0 0 1 0 1 1 0 1

0 0 1 1 0 0 1 1

00011110

3 5 6 7

From the comparison of the Walsh-Cooley (10)

and Walsh-Tukey (19) matrices, one can easily

establish both similarities and differences in the

algorithms forming the non-zero basis functions of

the systems (see Table 16).

Table 16. Comparison of methods of formation

of the eighth-order basis functions

( , )c k t

( , )k t

00111100

01111000

(2, ) (1, (2 ) )f t f t=

(1 2)

(1 6)

(4, ) (2, (2 ) )f t f t=

(1 4)

(6, ) (3, (2 ) )f t f t=

(1 6)

(1 2)

In Table 16, the symbol fdenotes the basis

functions cor

, and the expression

(1 )l

denotes

the bitwise sum of functions of the first- and l-th

orders. The same for the Walsh-Cooley and Walsh-

Tukey systems is the method of recurrent

computation of even order basis functions, since their

definition formulas (11) and (16) are equivalent.

The difference manifests itself in the fact that if in

the Walsh-Cooley system, when calculating odd

basis functions

(2 1, )с k t+

0k>

, the first order

function

(1, )с t

is bitwise summed with the functions

(2 , )с k t

of even order, then in the Walsh-Tukey

system the sequence of even functions participating

in bitwise addition operations at the stages of

function definition

(2 1, )k tt +

, is inverse to the

sequence of even functions in the Walsh-Cooley

system.

Based on relations (15) and (16) and relying on

the rules given in Table 16, it is no problem to arrive

at an algorithm (see Fig. 19) for synthesizing systems

of Walsh-Tukey functions of arbitrary orders.

Fig. 19. The block diagram of the algorithm

synthesis of Walsh-Tukey function systems

Following the proposed synthesis algorithm, the

matrix of the Walsh-Tukey system of arbitrary

degree can be easily generated. As empirically

established, the formation of matrices

of order

takes n-2 computation cycles.

The amplitude and phase characteristics of the

16-point discrete Fourier transform processor in the

Walsh-Cooley and Walsh-Tukey function bases are

shown in Fig. 20 and Table 17, respectively.

International Journal of Computational and Applied Mathematics & Computer Science

DOI: 10.37394/232028.2024.4.8

Anatoly Beletsky, Mikolaj Karpinski,

Arsen Kovalchuk, Dmytro Poltoratskyi

E-ISSN: 2769-2477

Volume 4, 2024

Table 17. Phase-frequency characteristics of 16-point

DFT processors in Walsh-Cooley and Walsh-Tukey bases

Basis

k®

Cooley

- 0.20

- 0.39

- 0.65

- 0.79

- 0.92

- 1.18

- 1.37

- 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

- 1.37

- 1.18

- 0.92

- 0.79

- 0.65

- 0.39

- 0.20

Fig. 20: Amplitude-frequency characteristics of 16-point

DFT processors in Walsh-Cooley and Walsh-Tukey bases

As Fig. 20 and Table 17 show, the amplitude

spectra of discrete complex-exponential signals in

the Walsh-Cooley and Walsh-Tukey bases coincide.

In contrast, the phase spectra are opposite: so if in

some k-th output channel of an N-point DFT

processor, the phase response in the Walsh-Cooley

basis is

ckj ( )

, then in the Walsh-Tukey basis

k Н k

j ( ) = j ( - )

5 Discussion and Further Research

Let us note the peculiarities that can be drawn from

comparing the data in Table 13 and Figure 17.

First, the number of groups of equidistant

(according to Hamming) code combinations placed

in Table 13 (and there are five groups for N= 8)

coincides with the number of diagonal elements in

the upper part of Fig. 17, to the left of which there is

not a single non-zero sequent.

Second, the Hamming distance between the fifth

boundary sequent

€

, which closes Table 11, and the

nearest to it sixth sequent

€

is four,

i.e.,

5 6

€ €

( , ) 4.d=s s

The above numerical

characteristics make it possible to outline approaches

to constructing an algorithm for synthesizing the

complete set of sequent Walsh-like systems of

arbitrary order

2 ,

, which includes such

basic computational steps.

At the first stage of the sliding window mode for

the chosen order Nof the matrices of the Walsh-like

function systems, we find the minimum value of Mat

which equality

€ €

( , ) / 2

M M

d N

+=s s

is achieved. The

parameter Mdetermines the number of sequents

€i

1,i M=

, each of which forms functions

,i j

1,j R=

, where Ris the number of complete sets of

equidistant sequents generated by each forming

sequent

€i

. In particular, for N= 8, according to

Table 13, M= 5 and R= 6. All remaining sequents

€i

i M>

, can be excluded from further

International Journal of Computational and Applied Mathematics & Computer Science

DOI: 10.37394/232028.2024.4.8

Anatoly Beletsky, Mikolaj Karpinski,

Arsen Kovalchuk, Dmytro Poltoratskyi

E-ISSN: 2769-2477

Volume 4, 2024

consideration, since, as it was shown earlier, none of

them gives rise to any new Walsh-like systems.

In the second step, all sequents that are distant

from any selected parent sequent

€i

by the

Hamming distance

/ 2d N=

are determined. Finally,

in the third step, the composition of pairwise

equidistant sequents generated by sequents

€i

1,i M=

, is instantiated from the set of sequents

selected in the second computational step.

Given the above, it seems appropriate to outline

such directions for further research.

1. Obtain analytical estimates of the number of

symmetric systems of Walsh-like functions of

arbitrary order N.

2. Find out whether there are indicator matrices

for the systems of Walsh-like functions similar to

those by which the classical Walsh systems are

interconnected.

3. Develop methods for constructing FFT

algorithms on the basis of Walsh-like functions.

4. Identify areas of practical applications of

systems of Walsh-like functions.

6 Conclusion

The main scientific results achieved by the present

study are as follows.

First, based on the Cooley-Tukey FFT algorithm,

an FFT basis called the Walsh-Cooley basis has been

developed, which is unique in that it is the only one

in the set of classical Walsh bases that delivers linear

coherence to the frequency scales of FFT processors.

None of the canonical Walsh bases ordered by

Hadamard, Kaczmage, or Paley provides such

coherence to frequency scales, which brings specific

difficulties in realizing such devices, for example,

spectrometers.

Second, an algorithm has been developed to

synthesize new Walsh-like systems that retain all the

properties of classical Walsh systems but

significantly exceed the latter in power. For example,

there are 28 classical Walsh systems of the eighth

order in total, whereas there are 840 Walsh-like

systems. The basis functions forming Walsh-like

(and classical) systems constitute bases with all the

properties necessary for constructing fast Fourier

transform algorithms. Namely, the systems are

complete, orthogonal, symmetric, and involution,

i.e., such that they allow fast and efficient transformation

of signals between time and frequency domains and

provide good separation of different signal frequency

components.

Third, in the set of Walsh-like bases of arbitrary

degree order, a single basis exists called the Walsh-

Tukey basis. Like the Walsh-Cooley basis, it

provides linear coherence of frequency scales to FFT

processors. The spectra of discrete complex-

exponential signals in these bases are such that their

AFCs coincide, and their PFCs are inverted relative

to each other.

The developed Walsh-Cooley and Walsh-Tukey

functions systems have certain advantages over the

canonical Walsh systems and on this basis, in our

opinion, can replace the latter in many applications.

References:

[1] Karpovsky M. G., Moskaliev E. S.,Spectral

methods of analysis and synthesis of discrete

devices. Leningrad, Energizer, 1973.

[2] Xinyi Li, Shan Yu, et al., Nonparametric

Regression for 3D Point Cloud Learning. JMLR,

25(102), 2024, pp. 1 − 56.

[3] Trakhtman A. M., Trakhtman V. A.,

Fundamentals of the Theory of Discrete Signals

on Finite Intervals. Moscow: Sov. Radio, 1975.

[4] Richard E. Blahut, Theory and Practice of

Error-Controlling Codes. Publisher, Addison-

Wesley Publishing Company, 1983.

[5] Vasilii Feofanov, Emilie Devijver, Massih-

Reza Amini, Multi-class Probabilistic Bounds

for Majority Vote Classifiers with Partially

Labeled Data. JMLR, 25(104), 2024, pp. 1 − 47.

[6] Anatoly Beletsky, Cryptography applications

of indicator matrices of Walsh function systems.

Ukr. Inf. Sec. Res. J., Vol. 18, No. 1, 2016, pp. 5

−20.

[7] Bechir Alaya, Lamri Laouamer, Nihel Msilini,

Homomorphic Encryption Systems Statement:

Trends and Challenges. Computer Science

Review,Volume 36, May 2020, 100235.

[8] Nikitin G. I., Application of Walsh functions in

cellular communication systems with code

division of channels. St. Petersburg: SPbSUAP,

2003.

[9] Zalmanzon L. A., Fourier, Walsh, Haar

transformations and their application in control,

communication and other fields. Moscow: Nauka,

1989.

[10] Loginov V. P., Fourier functions and their

applications. Zarubezhnaya Radioelectronika.

Vol. 4, 1973, pp. 73 −101.

[11] John R. Turner and Rose M. Baker, Complexity

Theory: An Overview with Potential

Applications for the Social Sciences. Systems,

2019, 7, pp. 1 − 23.

International Journal of Computational and Applied Mathematics & Computer Science

DOI: 10.37394/232028.2024.4.8

Anatoly Beletsky, Mikolaj Karpinski,

Arsen Kovalchuk, Dmytro Poltoratskyi

E-ISSN: 2769-2477

Volume 4, 2024

[12] Harmuth H., Theory of sequential analysis:

bases and applications. New York: Academic,

1977.

[13] Artemyev M. Yu., Gaev G. P., Krenkel T. E.,

Skotnikov A. P., Algorithm of formation of

symmetric systems of Walsh functions, Radio

Engineering and Electronics. Vol. 7, 1978. pp.

1432 −1440.

[14] Hadamard M. J., Resolutiond'une question

relative aux determinants. Bull.Sc. Math. A17,

1893, pp. 240 −246.

[15] Rabiner L., Gold B., Theory and application of

digital signal processing. New Jersey, Prentice-

hall, 1975.

[16] Ismagilov I. I., One approach to the ordering of

systems of discrete Walsh functions.

Radioelectronics, Vol. 1, 2006. pp. 65 −72.

[17] Cooley J. W., Tukey J. W., An algorithm for

the machine calculation of the complex Fourier

series. Mathematics Computation, v. 19, 1965,

pp. 297 −301.

[18] Walsh J. L. A closed set of normal orthogonal

functions. Amer. J. Math, v. 45, 1923, p. 5- 24.

[19] Shneider A.A., About series on Valyp

functions with monotone coefficients. Izv.

ANSSR, Ser. mat., Vol 12, 1948, pp 179 −192.

[20] Paley R., A Remarkable, Series of Orthogonal

Functions. I, II. Proc. Lond. Math. Soc., 1932, p.

241 −279.

[21] Anatoly Beletsky, Combinatorics of Gray

codes. Kyiv: KVIC, 2003.

[22] Anatoly Beletsky, Synthesis and analysis of the

system of Walsh-Cooly basis functions.

Wroclaw: XIII Int. Conference. NIKON-2000,

2000.

[23] Yen C., Walsh function and Gray code. IEEE

Trans, Vol. 1, EMC-13, 1971, pp. 68 −73.

[24] Anatoly Beletsky,Systems of Discrete

Walsh-Like Sequential Functions. WSEAS

Int. J. of Applied Math. Computational

Science and Systems Engineering, Vol. 4,

2022, pp. 60 −73.

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

International Journal of Computational and Applied Mathematics & Computer Science

DOI: 10.37394/232028.2024.4.8

Anatoly Beletsky, Mikolaj Karpinski,

Arsen Kovalchuk, Dmytro Poltoratskyi

E-ISSN: 2769-2477

Volume 4, 2024