European International Journal of Pedagogics
96
https://eipublication.com/index.php/eijp
TYPE
Original Research
PAGE NO.
96-103
DOI
3
OPEN ACCESS
SUBMITED
12 March 2025
ACCEPTED
08 April 2025
PUBLISHED
11 May 2025
VOLUME
Vol.05 Issue05 2025
COPYRIGHT
© 2025 Original content from this work may be used under the terms
of the creative commons attributes 4.0 License.
Piecewise Polynomial
Methods of Haar
Transform in Digital Signal
Processing
Ibragimov Sanjarbek Salijanovich
t.f.f.d. (PhD), Andijan State Technical Institute, Uzbekistan
Abstract:
This paper analyzes the mathematical
foundations and practical significance of piecewise
polynomial methods based on the Haar orthogonal
basis in the process of digital signal processing.
Algorithms for calculating spectral coefficients in Haar,
Schauder, and spline bases are compared, and their
structural and computational efficiency is presented
through graphs and formulas. In particular, the
advantages of fast transform algorithms adapted for
piecewise-constant, piecewise-linear, and piecewise-
quadratic bases are demonstrated, along with the
challenges encountered during their implementation
and possible solutions. It is shown that piecewise
polynomial methods of the Haar transform can be
effectively applied in signal processing systems that
require high accuracy and speed.
Keywords:
Haar transform, spectral coefficients,
Schauder basis, parabolic spline, piecewise polynomial
methods, digital signal.
Introduction:
Digital signal processing has become an
integral part of modern information technologies and
electronics. One of the pressing challenges in this field
is the identification of spectral characteristics within a
signal and their efficient processing. In systems that
require rapid processing, it is particularly important to
reduce the number of computations, optimize memory
usage, and maintain algorithmic simplicity [1,2]. From
this perspective, algorithms based on the Haar
orthogonal basis occupy a prominent position. In
particular, the piecewise polynomial variants of the
Haar transform
—
including piecewise-constant,
piecewise-linear, and piecewise-quadratic bases
—
enable the analysis of signals in a segmented manner.
METHODOLOGY
European International Journal of Pedagogics
97
https://eipublication.com/index.php/eijp
European International Journal of Pedagogics
One of the key features of Haar bases is the availability
of fast algorithms for determining spectral coefficients.
Fast algorithms enable a reduction in the number of
arithmetic operations and memory usage during digital
signal processing. As a result, the use of orthogonal
bases in digital signal processing leads to an increase in
processing speed. Fast Haar transform algorithms are
widely applied for digital signal processing tasks [1,3].
The discrete Fourier-Haar series can be expressed in the
following form:
0
(
)
(
)
n
n
i
i
n
i
f x
C har x
=
=
(1)
These discrete transformations are derived by
adjusting the
n
C
coefficients relative to the
(
)
i
n
har x
Haar basis. The spectral coefficients are calculated using
the following formulas:
1
0
0
1
( )
N
i
C
X i
N
−
=
=
,
1
0
1
( )
( )
N
n
n
i
C
X i har i
N
−
=
=
(2)
Fast algorithms are available for the efficient
computation of Haar transforms, and they are referred
to as the Fast Haar Transform (FHT) algorithms.
Fast Haar transform algorithm
In the computation of the discrete Haar transform,
2
log
N
N
algebraic addition operations are
performed. In the Fast Haar Transform (FHT), the
number of required algebraic operations is
2(
1)
N
−
[1, 3, 6, 7]. This is approximately
2
0, 5 log
N
times
fewer than the number of operations required in the
standard discrete Haar transform algorithm. Therefore,
in many practical applications, the use of the FHT
algorithm for digital signal processing leads to a
significant improvement in efficiency.
Fig. 1. Fast Haar Transform graph as proposed by Andrews
The fast algorithms for computing Haar coefficients are
well-suited to the main characteristics of digital signal
processors, as they primarily involve addition and
subtraction operations. Representing the flow of
signals and the sequence of computations in the form of
a graph is an effective method for illustrating these
processes. Figure 1 shows the graph of the FHT
algorithm proposed by Andrews [3,6,7]. In these graphs,
European International Journal of Pedagogics
98
https://eipublication.com/index.php/eijp
European International Journal of Pedagogics
the number of input values is
16
N
=
.
In the presented graph, continuous solid lines
represent addition operations, whereas dashed lines
correspond to subtraction operations. The input
signals are indicated by
( ) ( )
(
)
0 ,
1 ,
,
1
X
X
X N
−
,
and the resulting Haar spectral coefficients are
represented by
( ) ( )
(
)
0 ,
1 ,
,
1
C
C
C N
−
.
Based on the FHT graph proposed by Andrews
mentioned above, the block diagram of the algorithm
for computing the spectral coefficients is illustrated in
Figure 2.
Fig. 2. Block diagram of the fast Haar transform algorithm
The key requirements for an efficient fast spectral
transform algorithm are the minimization of the
number of operations, the simplicity of each individual
operation, and the reduction of memory consumption.
Using the sources provided in the literature [1
–
6, 8],
we compare fast transform algorithms based on the
number of addition and subtraction operations
required for the computation of spectral coefficients.
In the Walsh Fast Transform algorithm, spectral
processing of an array with
2
k
N
=
elements requires
2
k
k
addition-subtraction operations. In the Fast Haar
Transform algorithm, the number of required
operations is
2(
1)
N
−
, while in the Hartley Fast
Transform algorithm,
3
4
N
−
operations are required.
Here,
N
denotes the number of array elements, and
𝑘
represents the number of iterations.
Table 1.
Comparison table of the number of arithmetic operations required for fast transform algorithms in one-
dimensional digital signal processing.
Array size
Fast Transform (FT) algorithm name
Fast Fourier
Transform
Fast Walsh
Transform
Fast Haar
Transform
Fast Harmut
Transform
European International Journal of Pedagogics
99
https://eipublication.com/index.php/eijp
European International Journal of Pedagogics
N
kN
kN
2(N-1)
3N-4
1024
10240
10240
2046
3068
Table 1 presents a comparison of the number of
arithmetic operations required for the computation in
the fast transform algorithms of Fourier, Walsh, Haar,
and Hartley transforms. According to the data
provided in the table, when the number of input values
is 1024, the Fourier and Walsh fast transforms require
10,240 arithmetic operations, the fast Haar transform
requires 2,046 operations, and the Fast Harmut
Transform requires 3,068 operations. Thus, the fast
Haar transform algorithm performs approximately 1.5
times fewer operations than the Hartley fast transform
and about 5 times fewer operations compared to the
Fourier and Walsh fast transform algorithms.
Piecewise polynomial methods of haar transform
In this section, we analyze the feasibility of applying fast
transform algorithms, originally developed for
orthogonal piecewise-constant basis functions, to the
computation of coefficients in piecewise-linear bases.
When expressed using integral representations, the
Fourier-Haar formulas take the following form:
1
1
0
0
0
1
1
0
0
1
( )
( )
( )
( )
( )
( )
1, 2,..., ;
0,1, 2,..., 2
N
i
hpj
N
k
k
i
hpj
p
C
x r dr
x r dr
C
x r
har r dr
har i
x r dr
i
n
j
−
=
−
=
−
=
=
=
=
=
(3)
This holds true only if the transformed signals
( )
x r
belong to the
)
2
0,1
L
metric space.
In this case, the properties of the local basis functions
can be utilized, namely, among the
2
p
functions of the
same order, there is only one function
pj
h
that is
nonzero within a given dyadic-rational interval
The computation algorithm for the coefficients
presented in expression (3) does not exhibit the
characteristics of a fast transform. Nevertheless, when
it is necessary to determine spectral coefficients within
local bases, the finite difference method can be applied
directly.
For example, in the Schauder basis [6], the coefficients
are calculated based on the following transformations:
1
1
1
0
0
1
1
0
0
0
(
)
(
)
1
( )
( )
( )
2
N
N
i
k
k
i
k
k
i
k
k
N
N
k
k
k
k
k
i
k
k
k
f
C
Shd
X
C
Shd
X
C
Shd
r dr
Shd
r dr
C har x
−
−
+
=
=
−
−
=
=
=
=
−
=
−
=
(4)
1
0
( )
N
i
i
k
k
k
C
f har x
−
=
=
(5)
Here, the Schauder fast transform algorithm based on
the 'time-wise' reduction principles is presented. In
expression (5), the sum on the right-hand side is
divided into two parts: the first part includes the
i
f
differences with indices ranging from i=0 to i=n/2
−
1,
and the second part includes the
i
f
differences with
indices ranging from i=n/2 to
i=n−1
:
/2 1
1
0
/2
( )
( )
N
N
i
i
i
i
k
k
k
i
i N
C
f har x
f har x
−
−
=
=
=
+
(6)
The coefficients comprising the second half of the
resulting vector, beginning from index n/2, can be
computed during the first iteration. The sequence {
i
f
} is partitioned into n/4 groups, each consisting of
two adjacent elements,
i
f
2
and
1
2
+
i
f
, to which
the discrete Haar transform formula is subsequently
applied for each pair:
/2
2
2
1,
0,1,...,
/ 2 1
N
j
j
j
C
f
f
j
N
+
+
= −
=
−
In the second iteration, the sequence is divided into
groups consisting of 8 elements; in the fourth iteration,
European International Journal of Pedagogics
100
https://eipublication.com/index.php/eijp
European International Journal of Pedagogics
into groups of 16 elements, and so on. The
corresponding values are determined according to the
following formulas:
/ 2
1
/ 2
1
0
/ 2
p
p
p
N
N
k
i
i
i
i N
C
f
f
−
−
=
=
=
−
(7)
The coefficients
1
C
and
0
C
in the final iteration are determined using the following formula:
/ 2 1
1
1
0
/ 2
N
N
i
i
i
i N
C
f
f
−
−
=
=
=
−
1
0
0
N
i
i
C
f
−
=
=
The graph representation of the Schauder fast transform algorithm for N=16 input values is shown in Figure 3.
Fig. 3. Fast Transform Graph Based on the Schauder Basis
Thus, this algorithm enables the use of fast transform
graphs based on orthogonal piecewise-constant basis
functions for computing coefficients in piecewise-
linear bases. A limitation of this algorithm is the
difficulty that arises when dealing with small values of
the
i
f
finite differences.
The analysis of coefficient computation methods
across different bases has shown that such methods
are available only for piecewise-constant and piecewise-
linear bases. For piecewise-quadratic bases, coefficient
computation methods have not yet been developed.
In fast transform algorithms utilizing local bases, the
number of coefficients within groups of the same order
is characterized by an exponential decrease as the
number of iterations increases. This property can be
exploited in the development of specialized high-speed
computational architectures.
European International Journal of Pedagogics
101
https://eipublication.com/index.php/eijp
European International Journal of Pedagogics
We proceed to examine a convergent series constructed from piecewise-quadratic Haar functions.
1
0
( )
( )
N
k
k
k
f x
C haid x
−
=
(8)
A drawback of the given series is the absence of fast
algorithms for computing the
k
C
coefficients. This
limitation can be overcome using a parabolic spline. If
the second derivative of an interpolating parabolic
spline of the function
( )
f x
over the interval [0,1] is
taken, the result is a piecewise-constant function with
step changes at the spline nodes, which can be
expanded into a series based on the piecewise-constant
orthogonal basis functions. As an example, we consider
the expansion of the spline derivative into the Haar
series:
1
2
0
( )
( )
N
k
k
k
S x
C har x
−
=
(9)
According to the theorems concerning finite
convergence and the integration of closed systems, the
integration of both components leads to the following
outcome:
1
2
2
2
0
0
( )
2
( )
( )
(0)
x
N
p
k
k
k
S x
S u du
C hain x
S
−
=
=
=
+
1
2
2
2
2
2
0
0
( )
( )
(0)
( )
(0)
(0)
x
N
k
k
k
S x
S u du
S
C haid x
S
S
−
=
=
+
=
+
+
Consequently, at dyadic-rational interpolation nodes,
the second derivative of the parabolic spline
corresponds to the expansion of the interpolated
function into a series of coefficients with respect to the
Haar orthogonal basis functions. The first derivative of
the spline corresponds to the expansion with respect
to the
hain
basis functions, while the spline itself
corresponds to the expansion with respect to the
haid
basis functions. The coefficients are
determined from the linear component of the spline
expansion, specifically, the first derivative evaluated at
x=0 defines the linear term, whereas the constant
component is given by the value of the spline
)
(
2
x
S
at
the same point.
One of the most important properties of spline
functions is the existence of higher-order derivatives.
This feature enables the development of a hardware-
oriented algorithm for computing coefficients within
piecewise-parabolic bases, consisting of the following
steps:
1.
Input of the initial functional relationship, i.e.,
entering the set of real experimental data.
2.
The b-coefficients are calculated according to the
following formula:
(
)
1
1
1
10
8
i
i
i
i
b
f
f
f
−
+
=
−
+
−
(10)
The values approximating the spline
)
(
2
x
S
are determined according to the following formula:
2
1
1
0
0
1
1
( )
( )
( )
( )
( )
f x
S x
b
B
x
b B x
b B x
−
−
=
+
+
(11)
In this case, second-order derivatives are employed in
place of the basis function values:
( )
1
B x
=
on the
interval
[−1.5,−0.5],
( )
2
B x
= −
on [
−0.5
,0.5], and
( )
1
B x
=
on [0.5,1.5].
2
1
1
0
0
1
1
( )
( )
( )
( )
( )
f
x
S x
b
B
x
b B x
b B x
−
−
=
+
+
(12)
As a result of these calculations, an array of values
approximating the second derivative of the spline
)
(
2
i
x
S
is obtained.
European International Journal of Pedagogics
102
https://eipublication.com/index.php/eijp
European International Journal of Pedagogics
3.
Formation of the
)
(
2
i
x
S
array
4.
Fast transforms are performed on the elements of
the obtained array using a fast transform graph,
and the coefficients are determined. These
coefficients constitute the piecewise-quadratic
basis coefficients.
The spectral coefficients are determined from the
elements of the
)
(
2
i
x
S
array using the fast transform
algorithms presented above. These coefficients
correspond to the coefficients in the piecewise-
quadratic basis.
RESULTS
To assess the potential of digital signal
processing based on Haar piecewise-polynomial bases,
an investigation was carried out involving both an
analytical function and geophysical signal data derived
from experimental observations.
Table 2.
Research Results on Digital Signal Processing Using Haar Piecewise-Polynomial Methods
Type of function
N
Piecewise-
constant Haar
basis
Piecewise-linear
Haar basis
Piecewise-
quadratic Haar
basis
𝑵
𝟎
%
𝑲
𝒄
𝑵
𝟎
%
𝑲
𝒄
𝑵
𝟎
%
𝑲
𝒄
𝒀 = 𝐬𝐢𝐧𝐡(𝒙)
1024
10,94
1,12
93,75
16,00
96,48
28,44
Geophysical
signal
1024
9,38
1,11
38,28
1,62
78,13
4,57
The research results are presented in Table 2. In this table, the values are determined as follows.:
𝐾
𝑐
= 𝑁/(𝑁 − 𝑁0)
N
–
Number of array;
N0% - Percentage of zero-valued coefficients;
Кc –
Compression coefficient.
As can be seen from the table, when performing digital
processing of values obtained from analytical functions
using piecewise-polynomial bases, it was found that
the percentage of coefficients equal to zero is
approximately 11% for the piecewise-constant basis,
94% for the piecewise-linear basis, and 96% for the
piecewise-quadratic basis. Similarly, when processing
real data arrays obtained from geophysical
observations, these percentages were determined to
be 9%, 38%, and 78%, respectively, for the piecewise-
constant, piecewise-linear, and piecewise-quadratic
bases. This, in turn, demonstrates that the level of data
compression
and
computational
optimization
achievable in digital calculations is exceptionally high.
Thus, the use of piecewise-polynomial bases not only
improves accuracy but also enables more efficient
utilization of computational resources.
CONCLUSION
The research results demonstrate that piecewise-
polynomial algorithms based on the Haar
orthogonal basis provide high efficiency in digital signal
processing. Transformations using the Schauder basis
and the application of parabolic splines enable
improved accuracy in the determination of spectral
coefficients. In particular, for piecewise-quadratic
bases, spline-based algorithms not only reduce
computational complexity but also preserve higher-
order derivatives effectively.
REFERENCES
Ахмед Н., Рао К.Р.
Ортогональные преобразования
при обработке цифровых сигналов. –
М.: Связь, 1980.
–
248 с.
Гадзиковский В.И. Цифровая обработка сигналов
.
–
М.: Солон
-
Пресс, 2013. –
766 с.
Сюзев В.В. Основы теории цифровой обработки
сигналов. Учебное пособие:–М. Издательство
:
«РТСофт», 2014. –
752с.
Ильин А.А., Титов В.С., Евсюков Е.В. Быстрые
алгоритмы цифровой обработки сигналов: Учеб.
пособие. Тула : Изд
-
во ТулГУ, 2004. –
125с.
Зайнидинов Х.Н, Жураев Ж.У, Маннапова М.Г.
Интерполяция функций с помощью кусочно
-
постоянных
и
кусочно
-
линейных
вейвлетов
European International Journal of Pedagogics
103
https://eipublication.com/index.php/eijp
European International Journal of Pedagogics
Хаара.//Автоматика и программная инженерия.
2020, №1(31), г. Новосибирск, Россия,
-
С. 42
-48.
Зайнидинов Х.Н. Методы и средства цифровой
обработки сигналов в кусочно
-
полиномиальных
базисах.
//
Монография,
Академия
государственного управления при Президенте РУз.
Т: «Fan va texnologiyalar», 2014,
-
С. 192
.
Зайнидинов Х.Н., Зулунов Р.М., Ибрагимов С.С.,
Жўраев
И.А.
Бўлак
-
полиномиал
базисларда
сигналларга рақамли ишлов бериш алгоритм ва
дастури. Фарғона политехника институти илмий
-
техника журнали 2016 й. 4
-
сон. 63
-
66 б.
Takahashi D. Fast Fourier Transform Algorithms for
Parallel Computers. Springer Nature Singapore Pte Ltd.
2019
–
p.120
