Conceptual Bases of Gray Transformations and
Discrete Vilenkin-Crestenson Functions Systems
ANATOLY BELETSKY
Department of Electronics,
National Aviation University,
Kyiv-03058, av. Cosmonaut Komarov, 1,
UKRAINE
Abstract: - The article is devoted to the theoretical foundations of the construction of generalized Gray codes.
These include the classical "left-side" and the proposed "right-side" Gray's codes. Left-side codes develop from
left to right and right-side codes from right to left. Left- and right-handed Gray's codes augmented with reverse
permutation operators form a subset of composite Gray's codes. Such codes have found constructive application
in solving synthesis and analysis problems of discrete systems of Vilenkin-Crestenson functions (VCF).
Particular cases of VCF systems are systems of discrete exponential functions and Walsh functions. The so-
called indicator matrices (IM), bijective connected to the VCF systems, form the basis for VCF systems
synthesis. The order of IMs is determined by the logarithmic dependence on the order of the VCF system.
Unique Walsh-Cooley function systems, the only ones in the set of Walsh function systems that provide linear
connectivity of the frequency scales of DFT processors, are developed. Examples of trees of VCF systems give.
The orders of IMs are related by logarithmic dependence with the orders of VCF systems. Using IM: (1)
estimates of the number of symmetric VCF systems in an unbounded range of changes of their parameters are
obtained, (2) structures are determined and (3) rules of the interconnection of the systems established. The
fundamental axioms and lemmas corresponding to the VCF systems formulating and directions for further
research are outlined.
Key-Words: - Generalized Gray Codes, Vilenkin-Crestenson Function Systems, VCF Indicator Matrixes
Received: March 29, 2022. Revised: January 4, 2023. Accepted: February 7, 2023. Published: March 7, 2023.
1 Introduction
Gray's transformations [1, 2] are considered a
generalization of Gray's codes in this paper. The
emergence of such codes met the requirements of
engineering practice in constructing "angle-code"
transducers, providing minimal errors [3, 4]. At the
beginning of their appearance, Gray's codes
attracted the attention of mathematicians and a wide
range of developers of different electronic
equipment. A distinctive feature of classical Gray's
codes is that in binary space when moving from one
number image to the next oldest or lower number,
there is a change of digits (1 to 0 or vice versa) only
in one digit of the number. Such codes are
Hamming unit distance codes [4]. Gray's code is not
the only one in this group, as shown in Table 1 on
the example of three-digit binary codes.
Table 1. Primary sequences of Gray codes
Primary sequences
Secondary sequences
1
2
3
4
5
6
7
8
9
10
11
12
000
000
000
000
000
000
000
000
000
000
000
000
001
100
100
001
010
010
100
001
010
010
001
100
011
110
101
101
110
011
101
101
110
011
011
110
010
010
001
100
100
001
111
111
111
111
111
111
110
011
011
110
101
101
110
011
011
110
101
101
111
111
111
111
111
111
010
010
001
100
100
001
101
101
110
011
011
110
011
110
101
101
110
011
100
001
010
010
001
100
001
100
100
001
010
010
Anatoly Beletsky
E-ISSN: 2224-2872
44
Volume 22, 2023
Let us pay attention to the properties of the code
sequences in the above tables. First, sequences 2-6
in Table 1 produce all possible permutations of the
digits of column 1. The number of such
permutations is six. Secondly, sequences 7-12 are
composed of the corresponding series of 1-6
because of column inversion if the position of the
upper zero code remains unchanged. Moreover,
thirty, the Hamming distance between the first and
last codes of each sequence in the Tables remains
equal to one. Let us name the code sequences
having the listed properties, closed Gray
arrangements.
The application of Gray codes in communication
techniques, analog-to-digital conversions, and other
areas has proved to be preferable for several
reasons, among which we note the following.
Firstly, the change of digit values from one code
combination to another is twice as rare as in a
simple code, and this property allows for higher
coding accuracy at the same speed as simple codes
[5, 6]. Also secondly, when adding two adjacent
code combinations by module 2, a number
containing only one unit is formed, regardless of the
number of bits of the source code sequence, which
allows you to build an effective system of integrity
control of the accepted combinations [7, 8].
2 Problem Formulation
In the second half of the previous century, with the
rapid development of computer facilities and, on
their basis, - digital processing of discrete signals,
the problem of the development of new discrete
Fourier transforms (DFT) bases. The main
requirement to such grounds is to provide in the
frequency domain the speed of processing of
broadband signals with the much higher rate
achieved by processors in the classical basis of
discrete exponential functions (DEF). Naturally, we
were considering using bases from the Walsh family
of systems. Such bases potentially provide a speed
of calculating Fourier coefficients an order of
magnitude faster than the speed delivered by the
basis of DEF. The reason for such a phenomenon is
that Walsh's fundamental basis excludes complex
multiplication operations accompanying the DEF
basis, the implementation of which requires
significant machine resources.
However, Walsh bases have at least two
significant disadvantages. The first one is that,
because of Walsh bases realism, pairs of Fourier
coefficients of the same amplitude but different
phase signs formed at the output of the DFT
processor in the set of spectral components of
quadrature signals (and such are the majority of
actually processed signals). A noted feature of a
spectrum of messages based on Walsh functions
leads to ambiguity of the solution when the number
of the output channel of the processor with the
maximum amplitude response is calculated with the
same phase (positive or negative).
Further, none of the known (let us call them
classical) Walsh bases, ordered by Hadamard [9],
Kachmarz [10], and Paley [11], provides linear
connectivity of frequency scales of DFT processors,
the essence of which is as follows.
Gray codes and VCF systems, including Walsh
functions, are widely represented in numerous
monographs, journal articles, conference papers, and
the Internet [12-20]. In [21, 22], a rather extensive
bibliography of applications of Gray's codes and
VCF systems in various fields of science and
technology give.
Let us name the abscissa of the rectangular
coordinate system, on which we will store
normalized frequencies of the input complex-
exponential signal, the input frequency scale of the
DFT. The axis of ordinates, designed to
accommodate the channel numbers of the processor,
in which responses with the maximum amplitude
and selected phase forms, are called the output
frequency scale of the processor.
Suppose that for a discrete complex-exponential
signal, the integer normalized frequency equals
m
.
Let
( , )kt
be the basis of the processor, where
k
— the number (order) of the basis function
coincides with the amount of the basis matrix string
and the function argument (normalized discrete-
time). If the number
k
of the output channel of the
processor in which the response with the maximum
amplitude formed coincides with
m
, as shown in
Fig. 1, it means that the basis delivers
( , )kt
linear connectivity to the frequency scales of the
DFT processor. For example, a processor with a
DEF basis provides such frequency connectivity.
Fig. 1: The ratio of frequency scales of an eight-
point DFT processor in the DEF base
Anatoly Beletsky
E-ISSN: 2224-2872
45
Volume 22, 2023
Fig. 2: The ratio of frequency scales of DFT processors in bases:
𝑎) Walsh-Hadamard (
H
); 𝑏) Walsh-Kachmazh (
W
); 𝑐) Walsh-Paley (
P
)
The graphs illustrate the interrelationship of
frequency scales of eight-point DFT processors (far
from linear) in the above-mentioned classical Walsh
bases for selecting responses with positive phases in
Fig. 2. As it follows from this figure, none of the
known Walsh bases provide linear connectivity to
the frequency scales of FFT processors, which can
lead, for example, to a decrease in the efficiency of
frequency meters built based on these Walsh bases.
The primary purpose of this study is to develop
the theoretical basis of Gray transformations and
solve the problem of synthesis of Vilenkin-
Crestenson functions in discrete systems.
3 Problem Solution
Let us note one crucial feature of the Gray codes.
Both mathematicians and developers of equipment
appeared out of sight of the possibility of
constructing the codes inverted in the direct
formation of classical Gray codes. In the known
(conventional) scheme, the creation of forwarding
and reverse codes develops from left to right. At the
same time, the number transformed upper (left) digit
remains unchanged in the case of direct and inverse
transformations.
Let's denote the bits of the number
x
represented in the position code by
1 2 1 0
, , ..., ,
nn
x x x x

and the Gray code
y
by
1 2 1 0
, , ..., ,
nn
y y y y

, where
n
— is the number of
bits in the code vectors
x
and
y
. For the binary
numbering system, the rule of direct transformation
of the vector
x
into
y
a simple one is quite simple
and looks like this:
2
11
, 0, 1, 0
n i n i n i n
y x x i n x
,
(1)
and in the reverse transformation
2
11
, 0, 1, 0
n i n i n i n
x x y i n x
,
(2)
At the same time, it is possible to construct a
transformation scheme in the opposite direction of
Gray's classical (left-side) transformation. In this
class of transformations, called right-hand, the
values of the lower bits of the numbers to be
transformed remain unchanged. The system of
equations, providing the right-side conversion of
Gray is reparations:
2
11
, 0, 1, 0
i i i
y x x i n x

,
(3)
– for direct right-side conversion and
2
11
, 0, 1, 0
i i i
x y x i n x

,
(4)
– to reverse the right-side transformation of Gray.
It is advisable to lay out the material based on
code transformations, relying on structural-logic
schemes of code formation. This approach to
explaining the essence of algorithms is convenient
because it makes the material more understandable
for engineers and significantly simplifies the task of
the formal mathematical description of the coding
procedure. For illustration in Figs. 3 and 4 (the
example of four-bit codes), the schemes
corresponding to left-side transformations (1) and
(2) result, and in Figs. 5 and 6 – for the
corresponding (3) and (4) right-side changes.
Fig. 3: Block diagram of the straight left-side Gray's
transform
Anatoly Beletsky
E-ISSN: 2224-2872
46
Volume 22, 2023
Fig. 4: Block diagram of the inverse left-side Gray's
transform
Fig. 5: Block diagram of the straight right-side
Gray's transform
Fig. 6: Block diagram of the reverse right-side
Gray's transform
The following is the principal difference between
Gray's classical (left-side) transformation and the
alternative (right-side) change. Suppose in the left-
side Gray transformation the Hamming’s distance
d
between any adjacent pairs
1
( ), 0, 1,
ii
y y i n

;
the code combinations are equal to 1 (including the
couple formed by the first and the last codes of the
closed sequence (i.e.,
01
)(1,n
dy y
), for the right-
side transformation. Table 2 shows that this equality
is observed only for
/ 2 1in
and
1in
.
Table 2. Distances of adjacent right-side
Gray Codes Hemmings
i
x
y
1
,()
ii
d y y
i
x
y
1
( , )
ii
d y y
0
000
0
000
2
4
100
100
2
1
001
011
2
5
101
111
2
2
010
110
2
6
110
010
2
3
011
101
1
7
111
001
1
The combination of left- and right-side Gray
transformations (both forward and reverse) together
with the inverse permutation operator (the
"exchange" matrix [12]) led to the possibility of
constructing combined or compound Gray codes
(CGC). The use of CGC was very successful in
determining the structure and interrelation of
Walsh's symmetric function systems [13], Vilenkin-
Crestenson discrete functions (WCF) [14-17] in
cryptography [18, 19], coding [20], and other
applications [21].
Walsh's function systems and the DEF systems
are a case of discrete Vilenkin-Crestenson systems
functions (VCF), as shown in Fig. 7 [13, 19, 20].
Fig. 7: Areas of identification of VCF systems and
their particular case
VCF systems are square complex-valued matrices
(except for Walsh systems, which are real matrices).
The function determines the order of VCF systems
n
Nm
,
where
m
— the base of the number system, and
n
— is the order of the indicator matrices of the VCF
systems.
Enter a designation
,mn
V
for a particular system
of VCF with parameters
,mn
and let it be
,mn
L
—
the number of symmetrical designs
,mn
V
. The
definition of an indicator matrix (IM) for the VCF
system will introduce below.
The number of symmetric systems
,1m
L
of DEF
coincides with the number mutually simple with
m
:
,1 ()
m
Lm
,
where
()m
is the Euler function.
The exact estimate of the number of symmetric
systems of Walsh
2,n
L
functions was first obtained
in [21] and looked like it:
2,
1
(2 (mod 2))
nn
ni
Ln

.
(5)
Anatoly Beletsky
E-ISSN: 2224-2872
47
Volume 22, 2023
Assessment
2,n
L
, calculated using formula (5) for
several values
n
, is shown in Table 3.
Table 3 − Number of Walsh symmetrical function
systems
n
1
2
3
4
5
6
7
8
N
2
4
8
1
6
32
64
128
256
2,n
L
1
4
2
8
4
4
8
13ˈ
888
888ˈ
832
112ˈ88
1ˈ664
28ˈ897ˈ7
05ˈ984
The paper [15] notes that the classical systems of
Walsh functions are interconnected by the codes
(transformations) of Gray, as shown in Fig. 8, in
which it marked: GC (RGC) — the direct (reverse)
code of Gray, BIP — binary-inverse permutation.
Fig. 8: The interrelation of numbers of essential
functions in Walsh's various classic systems
The complex significance of the VCF matrices
can avoid by using an isomorphic representation of
the phase multipliers
exp 2 /W j N

. An
isomorphism establishes by a simple
correspondence
{ } { }
k
Wk
. For example, relation
(6) illustrates the image of an eighth-order Walsh-
Paley matrix.
8
0 1 2 3 4 5 6 7
0 00000000
1 00001111
2 0 0 1 1 0 0 1 1
3 00111100
{ ( , )} . (6)
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
The transition from the complex elements of VCF
systems to their images entails replacing the bitwise
multiplication operations with bitwise addition
operations modulo
m
.
Following the structural-logic schemes presented
in Fig. 1, the composition of the system linear
modular equations four-point direct (7) and inverse
(8) left-side Gray transformations
33
2 3 2
1 2 1
0 1 0
;
;
;
;
yx
y x x
y x x
y x x



(7)
3, 3
2 3 2
1 3 2 1
0 3 2 1 0
;
;
;
,
xy
x y y
x y y y
x y y y y

(8)
whose matrix shapes look like
3 2 1 0
1 1 0 0
0 1 1 0
2 ( , , , ) 0 0 1 1
0 0 0 1
x x x x






YX
; (9)
3 2 1 0
1 1 1 1
0 1 1 1
3 ( , , , ) 0 0 1 1
0 0 0 1
y y y y






XY
, (10)
where 2 and 3 are the symbols of forward and
reverse Gray left-side transformation operators.
Indicator matrices correspond to systems of Walsh
functions of order 16.
Note that in matrix products (9) and (10), the data
vector line multiplies by the matrices on the left.
Multiplying the matrix by the vector column on the
right is accepted. That explains why this
multiplication method of matrix operations 2 and 3
can be formed by the direct transformation of single
matrix lines
Е
, the Walsh-Paley system IM (
Р
),
according to the scheme shown in Fig. 3.
The VCF indicator matrices have some
remarkable properties. Firstly, the IMs are right-side
symmetric (i.e., symmetric to the auxiliary diagonal
matrices). Call square form, symmetrical to the
main diagonal, left-side symmetric matrices.
Second, the IMs are unborn matrices. Let us clarify
the concept of nondegenerate VCF modular IM
systems. Let us denote
J
, the indicator matrix of
some system of the VCF
,mn
V
with arbitrary
parameters
m
,
n
. The non-renewal of the IM
J
system means that the determinant
J
by module
m
is mutually simple, with
m
and independent of
n
.
Finally, the number of IMs is the same as that of
VCF systems, meaning each VCF system
Anatoly Beletsky
E-ISSN: 2224-2872
48
Volume 22, 2023
corresponds to only one IM. The reverse is true: IM
unequivocally explains its only relevant VCF
system.
Let us introduce some constructive principles for
the theory of discrete systems of the VCF. The proof
can either be omitted because of the evidence or
through illustrative examples, confirming the rules'
validity. For engineering applications, such a
simplification, which does not distort the results, is
quite acceptable because it equips the application
developer with the necessary working tools,
relieving him from the need to "wander in the
mathematical labyrinths".
Based on the above properties of the IM, we
formulate (as a theorem) the definition of these
matrices.
Theorem: Indicator matrices of discrete VCF
systems
,mn
V
of the order
n
Nm
, the elements of
which are non-negative integers
,ij
, belonging to
the set
m
Z
, are square right-side symmetric
matrices
J
of the order
n
(necessary conditions),
not born in the ring of deductions on the module
(sufficient conditions).
The theorem conditions make it possible to
merely calculate the number
,mn
L
of symmetric
systems
,mn
V
on computers. The calculation results
show in Table 4.
Table 4. Estimates of the number of symmetric systems of the VCF
m
Parameter value
n
1
2
3
4
5
2
1
4
28
448
13.888
3
2
18
468
37.908
9.173.736
4
2
32
1.792
458.752
455.081.984
5
4
100
12.400
7.750.000
24.211.000.000
6
2
72
13.104
16.982.784
127.404.845.568
7
6
294
100.548
241.415.748
4.057.233.060.888
8
4
256
114.688
469.762.048
14.912.126.451.71
2
9
6
486
341.172
2.238.429.492
131.633.084.706.5
52
10
4
400
347.200
3.472.000.000
336.242.368.000.0
00
11
10
1.210
1.609.30
00
23.560.152.000
12
4
576
838.656
17.390.370.816
13
12
2.028
4.453.48
8
127.196.070.76
8
14
6
1.176
2.815.37
4
108.154.255.10
4
15
8
1.800
5.803.20
0
293.787.000.00
0
The estimates derived from the simulation are
located in columns 1-3 of Table 4 and columns 4
and 5 above the double lines. Based on the data of
Table 4, analytical estimates of number
,mn
L
were
empirically obtained, namely [1, 2]:
If
m
— is a simple number, then:
,
1
( ) (2 (mod 2)),
nn
mn i
L m n
where
()m
— Euler function.
If
m
— is the
k
degree of a simple
number
p
m
, (i.e.,
k
p
mm
), then:
( 1)/2
,,
k
p
nn
m n p
mn
L L m
.
If
m
— is the composite number is such
that
1
i
lk
i
i
mm
, in which
i
m
— a simple number,
then:
,,
1
() ki
p
n
mn mn
i
L m L
.
The aggregate of 28 third-order IMs,
corresponding to the set of Walsh's eighth-order
function systems, is shown in Table 5. Fig. 9 shows
the graph of the interconnection of Walsh systems
eighth-order containing all 28 indicator matrices [1,
2, 19, 20].
Anatoly Beletsky
E-ISSN: 2224-2872
49
Volume 22, 2023
Fig. 9: The total count of Paley's eighth-order related function system Walsh
Table 5. Indicator matrixes of Walsh eighth-order function systems
1 0 0
0 1 0
0 0 1




P
1 1 0
0 1 1
0 0 1




A
1 0 0
1 1 0
0 1 1




B
0 0 1
0 1 0
1 0 0




H
1 1 1
0 1 1
0 0 1




W
1 0 0
1 1 0
1 1 1




C
1 0 1
7 0 1 0
0 0 1




1 0 0
8 0 1 0
1 0 1




0 1 0
9 1 0 1
1 1 0




1 0 1
10 1 0 0
1 1 1




0 1 1
11 1 0 1
0 1 0




1 1 1
12 0 0 1
1 0 1




0 1 1
13 1 1 1
0 1 0




1 0 1
14 1 1 0
1 1 1




0 0 1
15 1 0 0
1 1 0




0 1 0
16 0 1 1
1 0 0




1
1 1 1
7 1 0 1
0 1 1




1 1 0
18 0 0 1
1 0 1




0 1 0
19 1 1 1
1 1 0




1 1 1
20 0 1 1
1 0 1




0 1 1
21 0 0 1
1 0 0




0 0 1
22 1 1 0
0 1 0




1 1 0
23 1 0 1
1 1 1




1 0 1
24 1 0 0
0 1 1




1 1 0
25 1 1 1
0 1 1




0 1 1
26 1 1 1
1 1 0




0 1 0
27 0 0 1
1 0 0




0 0 1
28 1 0 0
0 1 0




Table 6. Gray's elementary operators
Anatoly Beletsky
E-ISSN: 2224-2872
50
Volume 22, 2023
Designation
operator
Operation performed
0
Saving the original combination
1
Inverse transposition
2
Straight left-side transformation of Gray
3
Inverse left-side transformation of Gray
4
Straight right-side transformation of Gray
5
Inverse right-side transformation of Gray
6
Cyclic shift one digit to the right
7
Cyclic shift one digit to the left
Table 7. A subset of simple Walsh's eighth-order Gray system codes
1 0 0
0 0 1 0
0 0 1




1 1 0
2 0 1 1
0 0 1




1 0 0
4 1 1 0
0 1 1




0 1 0
6 0 0 1
1 0 0





0 0 1
1 0 1 0
1 0 0




1 1 1
3 0 1 1
0 0 1




1 0 0
5 1 1 0
1 1 1




0 0 1
7 1 0 0
0 1 0




Large Latin letters in the nodes of the graph
highlight the invariant fundamental Walsh systems,
so named because the algorithm of their synthesis
does not depend on the Walsh systems. Numbers in
the nodes of the contours indicate the numbers of
systems that do not belong to a subset of Walsh's
invariant fundamental systems. The tree nodes are
connected by directed edges, each assigned a weight
equal to a compound or simple Gray's code. A full
description of Gray's elementary operators is given
in Table 6, and Table 7 presents their IMs. Fig. 10
shows, as an example, the system
3,2
V
. The IMs
elements
1
P
and
2
P
connect by the operator
2
(multiplication by 2 modulo 3).
Fig. 10: VCF of the system
3, 2
V
The generating systems in Fig. 10 are the VCF-
matrices
1
H
and
2
H
the second Cronecker degree
of DEF matrices
1
E
and
2
E
:
1
0 0 0
0 1 2
0 2 1





E
,
2
0 0 0
0 2 1
0 1 2





E
.
Statement 1. Indicator matrices
v
J
of Paley-
linked systems of VCF
,mn
V
coincide with the Gray
code (in general - composite), using which the
transition from the VCF-Paley
()
,
r
mn
P
to the system
,mn
V
carries out.
The upper index (if any) in
()
,
r
mn
P
indicates the
thr
matrix of VCF-Paley systems. For example,
Fig. 11 shows the interconnection graph of systems
5,2
V
. The IMs elements
1
P
-
4
P
connect by the
operator
4
(multiplication by 4 modulo 5).
Anatoly Beletsky
E-ISSN: 2224-2872
51
Volume 22, 2023
Fig. 11: The graph of the interconnection of the fundamental systems of the VCF
5,2
V
Statement 2. The numbers
v
k
of the functions
system
,mn
V
are related to the numbers
p
k
of the
VCF-Paley system
,mn
P
by
vp
kk
J
. (11)
Using the ratio (11), let us show how we
calculate, for example, the Walsh system of
functions indicated in Fig. 9 with the symbol
C
.
Let us substitute the indicator matrix
C
from Table
5 to (11) and replace it with
v
k
to
c
k
,
1 2 3
1 0 0
( , , ) 1 1 0
1 1 1
p
c
c
k
k = x x x





J
,
0,1
i
x
,
By rearranging the basic functions (matrix rows)
of the Walsh-Paley system (8) according to the rule
given in Table 8, we obtain the matrix named in [22,
23] by the Walsh-Cooley system. The basis for this
name is that was first obtained this system by
rotating the unit complex circle containing the phase
multipliers of the Cooley-Tukey algorithm [24]
counterclockwise. The Walsh-Cooley matrix of the
eighth order is shown below as an example.
8
0 1 2 3 4 5 6 7
00
00000000
31
00111100
62
0 1 1 0 0 1 1 0
53
0 1 0 1 1 0 1 0 .
44
0 1 0 1 0 1 0 1
75
0 1 1 0 1 0 0 1
26
0 0 1 1 0 0 1 1
17
00001111
pc
t
kk













C
(12)
Walsh-Cooley function systems have a unique
property, which can formulate as follows. Among
all the classical symmetric Walsh function systems
used as the DFT basis, the only system that provides
linear connectivity of the frequency scales of the
DFT processor is the Walsh-Cooley function
system. In addition, we will outline the essence of
Walsh's forward and backward tasks. The
convenience of using such bases, for example, in
Spectro analyzers, is that one can make an
unambiguous decision for the normalized integer
frequency of the input signal using the number of
the DFT processor output channel with the
maximum response and negative phase.
In addition, we will outline the essence of
Walsh's so-called forward and backward tasks.
Anatoly Beletsky
E-ISSN: 2224-2872
52
Volume 22, 2023
The direct of Walsh's task is to calculate a
matrix
W
of order
2n
N
using a given indicator
matrix
w
J
.
The reverse of Walsh's task is to calculate the
indicator matrix
w
J
for a given Walsh matrix
W
.
The first is more straightforward — the reverse
Walsh problem, in which the sequence of
calculations illustrates Walsh-Cooley's system of
functions of the eighth order (12).
1) Let us present the binary system of Walsh
functions in a reduced form
()
N
W
, including
n
basic functions
( , )w k t
of the order
2i
k
,
0, 1in
. For the system (12) we have
()
8
0 1 2 3 4 5 6 7
0 0 1 1 1 1 0 0
1
0 1 1 0 0 1 1 0 .
2
0 1 0 1 0 1 0 1
4
t
C
k





(13)
Moving from a shortened form of Walsh systems
to a common structure is simple enough. The
function of the zero-order restores trivially. The
functions of order
2i
k
unambiguously defines by
a set of functions, the order of which is a power of
two. I.e., the missing functions were composed of
functions already available in the reduced matrices
of Walsh systems.
2) The number of columns of the reduced matrix
can reduce to the number of its rows if you select
those and only those matrix columns whose
numbers
t
, as well as the row numbers
k
, are the
degree of two (i.e., for
2i
t
,
0, 1in
). Because
of reducing the columns of the reduced matrix (13),
we come to the square matrix, which is called
J
the first native matrix of the Walsh functions system
1 2 4
0 1 1
1
1 1 0 .
2
1 0 0
4
t
k





J
(14)
3) The matrix (14) is left-side symmetric, while
the IMs are right-side symmetric. By inversion of
matrix rows, which achieve by multiplying it on the
left by the matrix (operator), we bring the original
matrix to the right-side symmetric inverse
permutation
1 2 4
1 1 0
1
1 0 1 1 .
2
0 0 1
4
t
k






JJ
(15)
4) The subsequent request of the matrix (15) will
receive the Walsh-Cooley function system IMs
с
J
(12).
The solution to Walsh's straightforward task
implies performing calculations in the inverse
sequence of estimates for Walsh's inverse task. That
means the fourth step performs first, then the third,
and so on.
Let us formulate some fundamental statements
that form the basis for constructing Gray's theory of
transformations.
Axiom 1. Every simple
g
and arbitrary
composite
G
binary Gray's code, given by indicator
matrices of order n, forms elements (generators) of a
multiplicative group. Among the composite codes
G
, there is at least one symmetric CGС that
generates a group of maximal order
n
L
defined by
the relation
21
n
n
L
.
Axiom 2. The right-side transposition operator
reverses quadratic matrices concerning the auxiliary
diagonal.
Axiom 3. An arbitrary right-side symmetric
matrix, multiplied from left or right by the operator
1
, becomes left-side symmetric, and vice versa.
Axiom 4. An inverse permutation matrix 1
rearranges all the rows of an arbitrary square matrix
A
in reverse order if multiplied from the left by that
matrix and rearranges the columns of matrix
A
in
reverse order if multiplied from the right by matrix
A
.
Axiom 5: Inverse permutation of columns and
rows of a square matrix
A
is equivalent to a joint
left- and right-side transposition of the matrix. From
axioms 4 and 5 follow
Corollary: Since
T
gg
and, in addition,
matrices
g
also are invariant to the right-side
transposition operation
, then
11
T
g g g

, as well as,
11gg
. (16)
Inequalities (16) mean, in particular, that the
matrices corresponding to the set of the original
g
and the conjugate
g
Gray operators are similar.
Lemma 1. The right-side CGC transposition is
equivalent to the inversion of this code, which
reduces to a rearrangement of the order of Gray's
simple codes.
Anatoly Beletsky
E-ISSN: 2224-2872
53
Volume 22, 2023
Proof. That is followed by the fact that any
simple Gray's code is symmetric about the auxiliary
diagonal and invariant to right-side transposition
and thus
1 2 2 1 2 1
g g g g g g

.
Lemma 2. A symmetric CGC corresponds to a
right-side symmetric transformation matrix.
Proof. By definition, a symmetric composite
code is a code
s
G G G
in which
G
is an
arbitrary CGC and
is a kernel, a simple or
symmetric Gray's mixed code. We have
()
s
G G G G G
s
G G G
.
Lemma 3. A composite Gray's code
T
GG
,
where
G
is a right-symmetric matrix of arbitrary
CGC, corresponds to a left-symmetric matrix.
Proof. From the fact that
TTT
A B B A
, it
follows that
TT
T T T T
G G G G G G
,
which is true if and only if
T
GG
is a left-side
symmetric matrix.
Lemma 4. The right-symmetric matrix
corresponds to a composite Gray's code
GG
,
where
G
is a left-symmetric matrix of arbitrary
CGC.
The proof of Lemma 4 is similar to the defense
of Lemma 3. Namely,

G G G G G G
, which is true if
and only if
GG
is a right-side symmetric matrix.
Let us support the proof of Lemma 4 with a
numerical example. Let
24G
be a left-symmetric
CGC. We have
24 4 2 42

G
. Hence,
composite Gray's code
2442
GG
is a
symmetric code which, according to Lemma 2,
corresponds to the right-side symmetric matrix.
Lemma 5. The generators of cyclic groups that
form a tree of Paley-linked systems of Walsh
functions are symmetric CGCs of exclusively odd
length.
Proof. As follows from Fig. 9, all graph contours
are formed either by simple Gray's codes of length 1
or by composite codes of length = 3, 5, and 7.
Suppose a symmetric CGC
gg g g

G
of length
4K
, for example, code
= 2442G
, is chosen as
the generator of the group. According to the above
Corollary, the two codes
g
can represent CGC
11g
and thus code
G
is reduced to a second-degree
CGC of odd length since
2
0
1 1 1 1 ( 1 )gg g g g gG
.
Let us next consider a CGS with parameter
6K
.
By direct computation, it is easy to see that, for
example,
2
()g g gg g g g
G
, whereas the
code
253352 535
. Lemma 5 also confirmed for
the trees of Paley-linked systems of Walsh functions
with fourth-order IM and, most likely, for orders
greater than four, so there is no objective reason
why this should not be the case.
4 Discussion
We can point out at least one direction in which it is
reasonable to develop further research. Its essence is
to create Walsh-like sequential systems. We refer to
such (0,1)-sequent functions as Walsh-like ones
where the number of zeros and ones in each half of
the determination interval is not necessarily equal,
as is the case with representations of classical Walsh
functions. The algorithm's simplicity for
synthesizing systems of sequential functions and the
high speed of spectral processing of discrete signals
provided by such bases open up broad prospects for
using Walsh-like methods in various fields of
science and technology.
5 Conclusions
The problem of developing mathematical and
algorithmic support for synthesizing discrete
systems of Vilenkin-Crestenson functions, including
systems of Walsh functions, is solved.
The scientific novelty of obtained results is as
follows. First, the GGC proposed, in addition to the
classical left-side codes, contains the so-called right-
side codes. If in classical Gray's codes, the process
of their formation develops in the direction from left
to right, then in right-side codes — from right to
left. Using GGC, the problem of construction of
VCF systems is solved enough. Second, an
isomorphic transformation proposes, employing not
only the transition from complex-valued to integers
of matrices of VCFs was possible but also the
technology of synthesis of VCF systems
substantially facilitated. Third, the so-called
indicator matrices of VCF systems introduced. The
order
n
of IMs coincides with the exponent at the
base of the number system
m
, which determines the
order N of the VCF system, i.e.,
n
Nm
. There is a
one-to-one correspondence between matrices of
VCF systems and their IMs, which allows for
replacement operations on VCF systems of large
orders by processes on IMs of small orders. And
fourth, the straight and inverse Walsh problems are
Anatoly Beletsky
E-ISSN: 2224-2872
54
Volume 22, 2023
formulated, through which the relationship between
Walsh systems and their indicator matrices are
established.
The practical significance of obtaining results is
as follows. Original Walsh-Cooley function systems
with unique properties have been developed. Bases
based on Walsh-Cooley function systems are the
only Walsh bases that provide linear coupling of
frequency scales of DFT processors. The
convenience of such bases, for example, in a
Spectro analyzer, is that it can use the output
channel number of the maximal response and
negative phase DFT processor to make a one-valued
decision for a normalized integer frequency of the
input signal.
Prospects for further research lie in the
development of Walsh-like functions in which the
number of zeros and ones in each half of the
definition interval need not be the same as with
classical Walsh systems.
References:
[1] Beletsky A. Ya. Gray code combinatory,
Kyiv: Pub. house «KVIC», 2003, 506 p.
[2] Beletsky A. Ya. Gray transformations:
monograph in two vol., Vol 1: Basic theory,
Kyiv: Pub. house «NAU», 2007. — 512 p;
Vol 2: Applied aspects, Kyiv: Pub. house
«NAU», 2007, 644 p.
[3] Gray F. Pulse code communication, Pat USA,
№ 2632058, 1953.
[4] Grechishnikov V. M., Butco A. D.
Diagnostics of optical and electrical channels
of the optoelectronic angle converter, Samara:
Pub. House ANC RAN, v. 20, # 4, 2018, p.p.
138–143.
[5] Gytis E. I. Information converters for
elementary digital computing devices,
Moscow: Pub. House «Energy», 1970, 399 p.
[6] Hamming R. Coding and Information Theory,
Prentice-Hall, 1980, ISBN 0-13-139139-9
[7] Korotayev B. B., Prokofiev A. V., Timofeev
A. N., Optoelectronic measuring transducers
of linear and angular motion, St. Petersburg:
Research Institute of ITMO, 2012, 116 p.
[8] Domrachev V. A. Digital angle converters:
construction principles, accuracy theory,
control methods, Moscow: Energoizdat, 1984,
328 p.
[9] Hadamard M. J., Buii. Sci. Math, 1923, A17,
p.p. 240-246.
[10] Walsh I. L., Amer. J. Math., 1923, 45, p.p 5-
24.
[11] Paley B. E., Proc. London Math. Soc. (2),
1932, 34, p.p. 241-279.
[12] Savage C. A. Survey of Combinatorial Gray
Codes, Wikipedia [online], Available at:
https: //people.engr.ncsu.edu/savage/available
for mailing/survey.pdf
[13] Pham D. M., Premkumar A. B., Madhukumar
A. Error Detection and Correction in
Communication Channels Using Inverse Gray
RSNS Codes, IEEE Transactions on
Communications, # 59(4), 2011, p.p. 975 –
986.
DOI: 10.1109/TCOMM.2011.022811.100092
[14] Pallam S. W., Audu G. A., Musa S. Y., Visa I.
M., Performance Analysis of Convolutional
and Gray Coding Techniques in Wireless
Communications, Int. J. of Scientific &
Engineering Research, Vol. 5, Issue 3, March-
2014 843 ISSN 2229-5518
[15] Petchmaneelumka W., Julsereewong A., A
Gray-code algorithmic analog-to-digital
converter based on operational conveyors,
Int. Conference on Control, Automation and
Systems, 27-30 Oct. 2010 Gyeonggi-do,
Korea (South)
DOI: 10.1109/ICCAS.2010.5669636
[16] Chaikla A., Arayawat S. and Riewruja V.,
OTA-based Gray-code Algorithmic ADC,
Proc. SICE-ICASE Int. Joint Conference,
2006, p.p. 5787-5791.
[17] Arayawat S., Thubthong U., Julsereewong P.,
Riewruja V., and Julsereewong A., A Voltage-
mode Gray-code Algorithmic ADC, Proc.
SICE Annual Conference, 2008, p.p. 605-608.
[18] B. Jackson, B. Stevens, G. Hurlbert, Research
problems on Gray codes and universal cycles,
Discrete Math. 309 (2009), 5341–5348,
Problem 483.
[19] Diaconis P., Holmes S., Gray codes for
randomization procedures, Wikipedia
[online], Available at:
https://statweb.stanford.edu/~cgates/PERSI/pa
pers/graycodes.pdf
[20] Alvarez G., Arroyo D., Nunez J., Application
of Gray code to the cryptanalysis of chaotic
cryptosystems, Wikipedia [online], Available
at: https://www. researchgate.net/
publication/215732242
[21] Mütze T. Combinatorial Gray Codes — an
Updated Survey, Wikipedia [online],
Available at: https://arxiv.
org/pdf/2202.01280.pdf
[22] Berger U., Schwichtenberg K., Tsuiki H.,
Miyamoto H., Logic for Gray-code
Computation, Wikipedia [online], Available
Anatoly Beletsky
E-ISSN: 2224-2872
55
Volume 22, 2023
at: https://www.mathematik.uni-
muenchen.de/~ schwicht/papers/
proof13/gray1509 28.pdf
[23] Richard E. Blahut, Theory and Practice of
Error Control Codes, Addison-Wesley
Publishing Company, 1983, 500 p. ISBN-
13: 978-0201101027
[24] Trahtman A. M., Trahtman V. A.,
Fundamentals of the theory of discrete signals
on final machines, Moscow: Sov. Radio,
1975, — 208 p.
[25] Artemiev M. Yu., Gaev G. P., Krenkel N. E.,
Skotnikov A. P., Algorithm of formation of
symmetric systems of Walsh functions, Radio
engineering and electronics, № 7, 1978, p.p.
1432-1440.
[26] Yuen C. Walsh Functions and Gray Code,
IEEE Trans., 1971, EMC-13 (3), p.p. 68 -73.
[27] Wilenkin N. Ya. About one class of complete
orthogonal systems, News of the USSR
Academy of Sciences. Ser. mat., Vol. 11, No.
4, 1947, p.p. 363-400.
[28] Crestenson H. E. A class of generalized Walsh
functions, Pacific J. Math., vol. 5, 1955, p.p.
17-31.
[29] Beletsky A. Ya. Discrete orthogonal bases of
Wilenkin-Crestenson functions, Palmarium
Academic Publishing, Germany, 2015, 232 p.
ISBN 978-3-659-60300-6
[30] Beletsky A. Ya. Generalized Gray
Transforms and Synthesis Symmetric Systems
of Walsh functions, Telecommunications and
Radio Engineering, Vol. 78, # 4, 2019, p.p.
305-326. DOI:
10.1615/TelecomRadEng.v78.i4.30
[31] Beletsky A. I. Quasi-equidistant codes, Kyiv:
Pub. House NAU-Druk, 2008, 460 p.
[32] Loginov V.P. Functions of Walsh and their
applications (review), Foreign
Radioelectronics, # 4, 1973, p.p. 73-101.
[33] Beletsky A. Ya. Synthesis and analysis of the
system of Walsh-Cooley basis functions,
NIKON-2000: XIII International Conference,
Wroclaw, 2000.
[34] Cooley J.W. and Tukey J.W. An algorithm for
the complex Fourier series machine
calculation, Math. Comp., 19, 1965, p.p. 297-
306.
Anatoly Beletsky
E-ISSN: 2224-2872
56
Volume 22, 2023
Contribution of Individual Authors to the
Creation of a Scientific Article (Ghostwriting
Policy)
The authors equally contributed in 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