Abstract

Translate

This paper proposes fast algorithms for odd-time and odd-frequency discrete Hartley transforms (DHTs) with normalization if the size of the input sequence ranges from 2 to 8. Fast algorithms for small-sized inputs can be included as modules in fast algorithms for discrete transforms of large-length input sequences. The existing fast odd-time DHT and odd-frequency DHT algorithms are primarily radix-type algorithms, specifically, radix-2 and prime factor algorithms. However, the algorithms in the literature do not normalize the initial transform. This means that after applying such algorithms, additional N multiplications are required. In this paper, the structural approach is exploited supposing that the starting point to design the fast algorithms is a matrix vector product expression. The factorization of the matrices of DHT coefficients is produced to reduce computational complexity taking into account the repetition and arranging of the matrix entries. The strict mathematical background proves the correctness of the obtained algorithmic solutions. Also, the MATLAB R2023b environment was applied for testing of the performance of the proposed algorithms. The obtained factorizations of the odd-time DHT and odd-frequency DHT matrices allow us to reduce the number of multiplications by 69%, while the amount of additions is decreased by about of 5% for odd-time DHTs and 8% for odd-frequency DHTs if the length of input data is in the range from 2 to 8. A comparison is provided with the direct calculation of the matrix vector product. Additionally, the computational complexity for each obtained solution is compared with the computational complexity of the existing fast algorithms for odd-time DHTs and odd-frequency DHTs. In addition, data flow graphs have been created for the proposed odd-time DHT and odd-frequency DHT algorithms. The modular space–time structure of the resulting data flow graphs is suitable for VLSI implementation.

Full text

Turn on search term navigation

Translate

1. Introduction

The DHT is widely applied in digital signal and image processing to obtain the frequency representation of data [1,2,3]. This transform is used in image compression [4], smart grid applications [5], wireless communication [6], audio watermarking [7], digital image watermarking [8,9,10], signal processing [11], and other applications. This transform can successfully supplement the discrete cosine transform (DCT) in different applications due to additional exploiting of the sine transform [1,2,3]. The latter allows for the processing of the signal details at high noise levels with better performance. For example, in [12], the DHT is applied in three-dimensional (3D) medical image compression. X-ray angiogram (XA) and magnetic resonance (MR) data with varied resolutions and with different numbers of frames/slices were processed. Each XA or MR data point was represented by a 3D array which was divided into blocks of size 8 × 8 × 8, and then a 3D DHT and a 3D zigzag scheme were employed. For comparison, the 3D DCT was applied with the corresponding zigzag pattern [13]. In the full 3D DHT-based codec implementation, only the first L zig-zag coefficients are preserved, encoded by entropy coding [14], and then transmitted and/or stored. However, to study the effect of the 3D DHT block, the bitrate in bit per voxel (bpv) must be calculated before entropy coding. As a result, both transforms have shown better performance at compressing XA data than MR data. Compared with the DCT on the XA data [15], approximate versions of the exact 3D DHT and the one proposed in [12] present better performance than the 3D DCT in terms of peak noise–signal ratio for the low bitrate ranging from 1 bpv to 6 bpv.

To increase robustness against various noise disturbances, similar advantages of the DHT are employed in image and audio watermarking [8,9,10]. Additionally, a significant reduction in the multiplicative complexity allows us to increase the computing efficiency and save resources [12].

To date, different DHT types have been exploited, specifically a generalized DHT [16,17], sliding DHT [18], two-dimensional DHT [19,20], 3D DHT [12], etc. However, the traditional DHT is still the most developed and researched transform compared with other types of DHT transforms [21,22,23,24]. In our paper, the odd-time DHT and odd-frequency DHT are considered. The odd-frequency DHT allows for data processing of frequencies that are centred in the range of those employed by the traditional DHT.

Direct computation of the different types of DHTs requires a huge number of arithmetic operations. Specifically, direct computation of the odd-time DHT or odd-frequency DHT of an N-point sequence requires $N^{2}$ multiplications which are especially time- and resource-consuming. To achieve a reduction in computational complexity, fast DHT algorithms have been designed [23,24,25]. But in articles devoted to the efficient implementation of the odd-time DHT and odd-frequency DHT, large-length inputs are considered [17,25,26,27,28,29,30,31]. It should be noted that more complex fast algorithms can be designed with modules containing odd-time DHT and odd-frequency DHT algorithms for short-length sequences [17]. In particular, in [21], a $2^{m - n}$ -point odd-frequency DHT is used to develop a split algorithm for a $2^{m}$ -point traditional DHT with reduced arithmetic complexity, where n is changed in the range from 1 to m. Once constructed, odd-time DHT and odd-frequency DHT algorithms for small-size inputs can be successfully exploited in different applications. As such, the development of fast odd-time DHT and odd-frequency DHT algorithms for short-length input sequences is a topical issue, and the appropriate approach for solving the determined parts of a general problem should be selected.

1.1. Related Papers

Most of the fast odd-time DHT and odd-frequency DHT algorithms are designed based on the divide-and-conquer strategy [17], which means obtaining a solution of a large problem via a set of solutions of smaller tasks. Bearing in mind this strategy, radix-type algorithms were developed including radix-2 and prime factor algorithms.

Thus, the radix-2 fast odd-time DHT and odd-frequency DHT algorithms were proposed in [17,26,27,28,29]. In [26,27] the proposed fast algorithms decompose the N-point odd-time DHT into two adjacent N/2-point odd-time DHTs. Such fast odd-time DHT algorithms save from 16% to 24% of the arithmetic operations in comparison with Hu’s algorithm if N varies from 16 to 64 [26].

In [17] the N-point odd-frequency DHT is decomposed into the N/2-point odd-frequency DHT and the N/2-point odd-time odd-frequency DHT. For odd-time DHT similar algorithms are also proposed. As a result, the computational complexity of the N-point odd-time DHT and odd-frequency DHT is reduced. In [28] the odd-frequency DHT of length N = $2^{m}$ was represented by several 16-point odd-frequency DHTs. Then the 16-point odd-frequency DHT is calculated by first-order moments. As a consequence, a needed number of additions and multiplications is lower than in other existing algorithms.

In [29,30] radix-2 fast algorithms are developed for the VLSI implementation of odd-time DHT and odd-frequency DHT of length N = $2^{m}$ . The algorithms differ by parallelism as well as regular and simple computational structure with low arithmetic cost.

Developed in [26,27,28,29] the fast odd-time DHT and odd-frequency DHT algorithms apply the decimation-in-frequency approach. However, for real-time applications the fast algorithms based on the decimation-in-time approach are preferable. Presented in [31] the radix-2 fast odd-time DHT algorithm with decimation-in-time substantially saves the arithmetic operations relative to Hu’s algorithm. Also, in [31] a regular signal flow graph is constructed which can be used for odd-time DHT with different lengths of inputs.

In [32] a split-radix algorithm with decimation-in-time splits N-point odd-time DHT into N/2-point odd-time DHT for even indexed samples and two odd-time DHTs of length N/4 for odd-indexed samples. Thus the number of multiplications and additions was reduced up to 29% and 10% respectively in comparison with the radix-2 odd-time DHT algorithm [31].

Mentioned radix-2 odd-time DHT and odd-frequency DHT algorithms are cost-effective but when the input sequence length is not a power of two the computational overhead frequently arises. Thus the prime factor algorithms are introduced in [17] for sequence lengths N = p × q, where p and q are relatively prime. The first prime factor algorithm decomposes the N-point odd-time DHT into p q-point odd-time DHT and q p-point odd-time DCTs. A similar decomposition also takes place for odd-frequency DHT by replacing odd-time transforms with odd-frequency transforms. However, in this case, irregularity in the index mapping occurs. To implement the in-place computation, which is easily attained by the radix-2 algorithms, the second prime factor algorithm was developed [17]. The N-point odd-time DHT is decomposed into N/q q-point odd-frequency DCTs and q N/q-point odd-time DHTs. The N-point odd-frequency DHT computation is decomposed into q N/q-point odd-frequency DHTs and N/q q-point odd-time DCTs.

Along with the algorithms synthesized based on the divide-and-conquer strategy, the algebraic signal processing is taken into account to develop the fast odd-time DHT and odd-frequency DHT algorithms. Thus, in [33] the polynomial transforms, linear congruencies, and index permutations are applied to design the fast odd-time DHT and odd-frequency DHT algorithms. In [11] fast general-radix algorithms for a wide class of orthogonal trigonometric transforms are provided. This transform class includes the odd-time DHT and odd-frequency DHTs and related algorithms are obtained by manipulating the polynomial algebras instead of manipulating the transform expression.

The short review of existing fast odd-time DHT and odd-frequency DHT algorithms has allowed defining their drawbacks and formulation of unsolved parts of the general problem of reducing computational complexity.

1.2. The Main Contributions of the Paper

After review, we note that the existing fast odd-time DHT and odd-frequency DHT algorithms are developed using polynomial algebras or radix-type approach. However, several papers devoted to fast algorithms for orthogonal trigonometric transforms exploit a structural approach that compares the transform coefficient matrix with matrix patterns [34,35,36,37,38,39]. As an option, these matrix patterns are introduced in [34] based on Winograd’s approach to the fast algorithm development. The advantage of the structural approach is the factorization of the transform matrix on sparse, scaled orthogonal, rotational, or rotational-reflection matrices [38,39]. Moreover, based on the structural approach we can obtain the data flow graphs of odd-time DHT and odd-frequency DHT algorithms with only one multiplication along the critical path [34,35,36,37]. If there is more than one multiplication in the critical path of the algorithm, then this will create additional problems for the implementation of computations.

In [37] based on the structural approach efficient algorithms for small-sized odd-time DHT were developed that do not consider the normalizing coefficients. Many authors do this, naively thinking that the result can be multiplied by the normalizing constants at subsequent stages of data processing and combined with other calculations. However, this trick cannot always be implemented, and then the normalization still has to be introduced leading to the need to perform N additional multiplications. This means that to obtain true quantitative estimates of the computational complexity of the proposed solutions, it is necessary to include N additional multiplications for each N-point algorithm, otherwise such estimates will be incorrect. To avoid such shortcomings, it is necessary to consider the normalizing constants in the original transform matrix at the very beginning.

The article [34] describes a general approach to constructing reduced complexity algorithms for calculating matrix-vector products in those cases where the matrices have certain structures. In the paper, we apply this approach to specific transforms, namely, odd-time DHT and odd-frequency DHT. Taking into account the normalization of these transforms is influenced by the number of arithmetic operations, and in some cases on the matrix structure. As a result, the mentioned approach can also allow us to obtain new interesting solutions if normalization is kept in mind.

Therefore, in this article, we consider the case of factorization of the original transformation matrices, the entries of which are already initially multiplied by the corresponding normalizing constants. This paper aims to reduce the computational complexity of the odd-time DHT and odd-frequency DHT with normalization via developing fast algorithms. We base on the structural approach supposing that input sequence length N is changed from 2 to 8.

The article is organized as follows. The considered problem is introduced and the research subject is formulated in Section 1. Brief mathematical background is provided and the used notations are defined in Section 2. Section 3 is devoted to odd-time DHT and odd-frequency DHT matrix factorizations for different N from 2 to 8 and following obtaining of the fast odd-time DHT and odd-frequency DHT algorithms via the data flow graphs. In Section 4 and Section 5 the computational complexity of the proposed fast odd-time DHT and odd-frequency DHT algorithms is evaluated. In Section 6 the conclusions are provided.

2. Preliminary Background

The traditional DHT is expressed as follows [17]:

(1) $y_{k} = \sum_{n = 0}^{N - 1} x_{n} cas \frac{2 π nk}{N}, k = 0, 1, \dots, N - 1,$

where casθ = sinθ + cosθ =

\sqrt{2}

cos(θ

-

π/4);

y_{k}

is the output data sequence after the traditional DHT;

x_{n}

is the sequence of input data; N is the number of signal samples.

The direct generalized DHT can be described by the following expression [17]:

(2) $y_{k} = \sum_{n = 0}^{N - 1} x_{n} cas \frac{(n + n_{0}) (k + k_{0}) 2 π}{N}, k = 0, 1, \dots, N - 1,$

where

y_{k}

is the output sequence after the direct generalized DHT;

n_{0}

is a time shift;

k_{0}

is a frequency shift.

Using the expression (2) we have the traditional DHT if $n_{0} = 0, k_{0} = 0,$ the odd-time DHT if $n_{0} = 1 / 2, k_{0} = 0,$ the odd-frequency DHT if $n_{0} = 0, k_{0} = 1 / 2,$ the odd-time odd-frequency DHT if $n_{0} = 1 / 2, k_{0} = 1 / 2 .$ When for the odd-time DHT with normalization the expression (2) is represented as follows [17]:

(3) $y_{k} = \frac{1}{\sqrt{N}} \sum_{n = 0}^{N - 1} x_{n} cas \frac{π (2 n + 1) k}{N}, k = 0, 1, \dots, N - 1,$

where

y_{k}

is the output sequence after the odd-time DHT.

For the odd-frequency DHT with normalization we derive the expression (2) as follows [17]:

(4) $y_{k} = \frac{1}{\sqrt{N}} \sum_{n = 0}^{N - 1} x_{n} cas \frac{π (2 k + 1) n}{N},$

where

y_{k}

is the odd-frequency DHT outputs,

k = 0, 1, \dots, N - 1

The odd-time DHT and odd-frequency DHT can be obtained as a matrix-vector product:

(5) $Y_{N \times 1} = C_{N} X_{N \times 1},$

where

C_{N} = [\begin{matrix} \begin{matrix} c_{0, 0} & c_{0, 1} \end{matrix} & \dots & c_{0, N - 1} \\ \begin{matrix} c_{1, 0} & c_{1, 1} \end{matrix} & \dots & c_{1, N - 1} \\ ⋮ & ⋱ & ⋮ \\ \begin{matrix} c_{N - 1, 0} & c_{N - 1, 1} \end{matrix} & \dots & c_{N - 1, N - 1} \end{matrix}]

c_{k n} = \frac{1}{\sqrt{N}} cas \frac{π (2 n + 1) k}{N}

for odd-time DHT, and

c_{k n} = \frac{1}{\sqrt{N}} cas \frac{π (2 k + 1) n}{N}

for odd-frequency DHT, n, k = 0, …, N − 1;

Y_{N \times 1} = {[y_{0}, y_{1}, \dots, y_{N - 1}]}^{T}

X_{N \times 1} = {[x_{0}, x_{1}, \dots, x_{N - 1}]}^{T}

Because the generalized DHT with normalization is orthonormal then the matrices of inverse transforms are transposed to the direct ones. That is, for odd-time DHT the inverse is odd-frequency DHT and vice versa. For traditional DHT the inverse transform is the same [40].

In the article the following notations and abbreviations are used [34]:

⊕ is the direct sum of two matrices;
$I_{N}$ is an order N identity matrix;
⊗ is a Kronecker product of two matrices;
$H_{2}$ is a 2 × 2 Hadamard matrix;
$s_{m}^{(N)}$ is a multiplier;
$P_{N}$ is a permutation matrix;
$W_{M \times N}$ is a block-diagonal matrix of size M × N;
$W_{N}$ , $D_{N}$ are block-diagonal and diagonal matrices of size N × N, respectively;
an empty cell in a matrix means that it contains zero;
DHT is a discrete Hartley transform;
VLSI is very large-scale integration;
DCT is a discrete cosine transform;
XA is a X-ray angiogram;
MR is magnetic resonance;
3D is a three-dimensional data.

3. Reduced Complexity Algorithms for Short-Length Odd-Time DHT and Odd-Frequency DHT

3.1. Algorithms for 2-Point Odd-Time DHT and Odd-Frequency DHT

To develop the algorithm for two-point odd-time DHT with normalization we consider the expression:

(6) $Y_{2 \times 1} = C_{2} X_{2 \times 1},$

where

C_{2} = [\begin{matrix} a_{2} & a_{2} \\ a_{2} & - a_{2} \end{matrix}]

a_{2} = \frac{1}{\sqrt{2}} cas 0 = \frac{1}{\sqrt{2}} \approx

0.7071,

b_{3} = \frac{1}{\sqrt{3}} cas \frac{π}{3} \approx

0.7887,

c_{3} = \frac{1}{\sqrt{3}} cas \frac{2 π}{3} \approx

0.2113,

Y_{2 \times 1} = {[y_{0}, y_{1}]}^{T}

X_{2 \times 1} = {[x_{0}, x_{1}]}^{T}

. The expression (6) for two-point odd-frequency DHT with normalization is the same because

C_{2} = C_{2}^{T}

Then the factorization of the odd-time and odd-frequency DHT matrix for N = 2 can be presented as follows:

(7) $Y_{2 \times 1} = D_{2} H_{2} X_{2 \times 1},$

where

D_{2} = diag (s_{0}^{(2)}, s_{1}^{(2)}), s_{0}^{(2)} = s_{1}^{(2)} = a_{2}

We have shown a data flow graph of the algorithm for the 2-point odd-time DHT and odd-frequency DHT in Figure 1. As can be seen, we have 2 additions as well as when using the direct method. The number of multiplication is also 2 against 4 multiplications for the direct matrix-vector product.

3.2. Algorithms for 3-Point Odd-Time DHT and Odd-Frequency DHT

The expression for 3-point odd-time DHT with normalization is as follows:

(8) $Y_{3 \times 1} = C_{3} X_{3 \times 1},$

where

Y_{3 \times 1} = {[y_{0}, y_{1}, y_{2}]}^{T}

X_{3 \times 1} = {[x_{0}, x_{1}, x_{2}]}^{T}

C_{3} = [\begin{matrix} a_{3} & a_{3} & a_{3} \\ b_{3} & - a_{3} & - c_{3} \\ c_{3} & a_{3} & - b_{3} \end{matrix}]

with

a_{3} = \frac{1}{\sqrt{3}} cas 0 = \frac{1}{\sqrt{3}} \approx

0.5774,

b_{3} = \frac{1}{\sqrt{3}} cas \frac{π}{3} \approx

0.7887,

c_{3} = \frac{1}{\sqrt{3}} cas \frac{2 π}{3} \approx

0.2113. For odd-frequency DHT with normalization we use

C_{3}^{T}

instead of

C_{3}

in Equation (8).

To factorize the $C_{3}$ matrix we swap the first and second rows. Then we alter the sign of the third row and third column of the resulted matrix $C_{3}^{(a)}$ and decompose it into two components:

(9) $C_{3}^{(a)} = C_{3}^{(b)} + C_{3}^{(c)},$

where

C_{3}^{(b)} = [\begin{matrix} - a_{3} \\ a_{3} & a_{3} & - a_{3} \\ {- a}_{3} \end{matrix}]

C_{3}^{(b)} = [\begin{matrix} b_{3} & c_{3} \\ {- c}_{3} & - b_{3} \end{matrix}]

In the second column and second row of the matrix $C_{3}^{(b)}$ we obtained identical entries that differ only in sign. Therefore, the number of operations can be reduced without additional transforms. Next, we eliminate the second row and second column containing only zero entries in matrix $C_{3}^{(c)}$ , and matrix $C_{2}^{(a)} = [\begin{matrix} b_{3} & c_{3} \\ - c_{3} & - b_{3} \end{matrix}]$ was obtained.

We derive the factorization for the 3-point odd-time DHT based on the decomposition of matrix $C_{2}^{(a)}$ [34,37]:

(10) $Y_{3 \times 1} = P_{3} W_{3 \times 4} W_{4} D_{4} W_{4 \times 3} W_{3} X_{3 \times 1},$

where

D_{4} = diag (s_{0}^{(3)}, s_{1}^{(3)}, s_{2}^{(3)}, s_{3}^{(3)})

s_{0}^{(3)} = (b_{3} + c_{3}) / 2

s_{1}^{(3)} = (b_{3} - c_{3}) / 2

s_{2}^{(3)} = s_{3}^{(3)} = - a_{3}

$W_{4} = ({\bar{I}}_{2} H_{2}) \oplus I_{2},$

$P_{3} = [\begin{matrix} 1 \\ 1 \\ - 1 \end{matrix}], W_{3 \times 4} = [\begin{matrix} 1 & 1 \\ - 1 & - 1 \\ 1 & 1 \end{matrix}], W_{3} = [\begin{matrix} 1 & - 1 \\ 1 \\ 1 & 1 \end{matrix}], W_{4 \times 3} = [\begin{matrix} 1 \\ 1 \\ 1 \\ 1 \end{matrix}] .$

Based on Equation (10) the factorization for the 3-point odd-frequency DHT is obtained as:

(11) $Y_{3 \times 1} = W_{3}^{T} W_{4 \times 3}^{T} D_{4} W_{4}^{T} W_{3 \times 4}^{T} P_{3}^{T} X_{3 \times 1} .$

A data flow graph of the 3-point odd-time DHT algorithm is shown in Figure 2. Then the amount of multiplications can be reduced from 9 to 3 because $s_{0}^{(3)} = 0.5$ . However, the number of additions enlarges from 6 to 7.

A data flow graph of the 3-point odd-frequency DHT algorithm is shown in Figure 3. The number of arithmetic operations remains the same as for 3-point odd-time DHT.

3.3. Algorithms for 4-Point Odd-Time DHT and Odd-Frequency DHT

The four-point odd-time DHT with normalization is defined as follows:

(12) $Y_{4 \times 1} = C_{4} X_{4 \times 1},$

where

Y_{4 \times 1} = {[y_{0}, y_{1}, y_{2}, y_{3}]}^{T}

X_{4 \times 1} = {[x_{0}, x_{1}, x_{2}, x_{3}]}^{T}

C_{4} = [\begin{matrix} a_{4} & a_{4} & a_{4} & a_{4} \\ b_{4} & 0 & - b_{4} & 0 \\ a_{4} & - a_{4} & a_{4} & - a_{4} \\ 0 & b_{4} & 0 & - b_{4} \end{matrix}]

with

a_{4} = \frac{1}{2} cas 0 =

0.5,

b_{4} = \frac{1}{2} cas \frac{π}{4} \approx

0.7071. For odd-frequency DHT with normalization we use

C_{4}^{T}

instead of

C_{4}

in Equation (12).

We permutate the rows of $C_{4}$ according to $π_{4} = (\begin{matrix} 1 & 2 \\ 1 & 3 \end{matrix} \begin{matrix} 3 & 4 \\ 2 & 4 \end{matrix})$ . The permutation matrix is $P_{4} = [\begin{matrix} 1 \\ 1 \\ 1 \\ 1 \end{matrix}]$ . The obtained matrix $C_{4}^{(a)} = [\begin{matrix} a_{4} & a_{4} & a_{4} & a_{4} \\ a_{4} & - a_{4} & a_{4} & - a_{4} \\ b_{4} & 0 & - b_{4} & 0 \\ 0 & b_{4} & 0 & - b_{4} \end{matrix}]$ matches the pattern $[\begin{matrix} A_{2} & A_{2} \\ B_{2} & - B_{2} \end{matrix}]$ where $A_{2} = [\begin{matrix} a_{4} & a_{4} \\ a_{4} & - a_{4} \end{matrix}]$ and $B_{2} = [\begin{matrix} b_{4} \\ b_{4} \end{matrix}]$ .

Applying the matrix templates from [34,37], we derive the expressions

(13) $C_{4}^{(a)} = (A_{2} \oplus B_{2}) (H_{2} \otimes I_{2}), A_{2} = (a_{4} \oplus a_{4}) H_{2}, B_{2} = (b_{4} \oplus b_{4}) I_{2} .$

Therefore the factorization of the 4-point odd-time DHT matrix is as follows:

(14) $Y_{4 \times 1} = P_{4} D_{4} W_{4}^{(0)} W_{4}^{(1)} X_{4 \times 1},$

where

W_{4}^{(0)} = H_{2} \oplus I_{2}

D_{4} = diag (s_{0}^{(4)}, s_{1}^{(4)}, s_{2}^{(4)}, s_{3}^{(4)})

s_{0}^{(4)} = s_{1}^{(4)} = a_{4}, s_{2}^{(4)} = s_{3}^{(4)} = b_{4},

W_{4}^{(1)} = H_{2} \otimes I_{2}

The data flow graph of the 4-point odd-time DHT algorithm is presented in Figure 4. As one can see, the number of multiplications is reduced from 4 to 2 because $s_{0}^{(4)} = s_{1}^{(4)} = a_{4} = 0.5$ , the number of additions is decreased from 8 to 6 compared to direct matrix-vector product.

Taking into consideration the Equation (14), the factorization for the four-point odd-frequency DHT matrix is expressed as

(15) $Y_{4 \times 1} = {(W_{4}^{(1)})}^{T} {(W_{4}^{(0)})}^{T} D_{4} P_{4}^{T} X_{4 \times 1}$

The algorithm of the 4-point odd-frequency DHT with normalization is provided as a data flow graph in Figure 5. The number of arithmetic operations is the same as for odd-time DHT.

3.4. Algorithms for 5-Point Odd-Time DHT and Odd-Frequency DHT

To develop the algorithm for five-point odd-time DHT with normalization we use the following expression

(16) $Y_{5 \times 1} = C_{5} X_{5 \times 1},$

where

Y_{5 \times 1} = {[y_{0}, y_{1}, y_{2}, y_{3}, y_{4}]}^{T}

X_{5 \times 1} = {[x_{0}, x_{1}, x_{2}, x_{3}, x_{4}]}^{T}

a_{5}

\frac{1}{\sqrt{5}} \approx

0.4472,

b_{5}

\frac{1}{\sqrt{5}} cas \frac{π}{5} \approx

0.6247,

c_{5}

\frac{1}{\sqrt{5}} cas \frac{3 π}{5} \approx

0.2871,

d_{5}

\frac{1}{\sqrt{5}} cas \frac{2 π}{5} \approx

0.5635,

e_{5}

- \frac{1}{\sqrt{5}} cas \frac{4 π}{5} \approx

0.0989,

$C_{5} = [\begin{matrix} a_{5} & a_{5} & a_{5} & a_{5} & a_{5} \\ b_{5} & c_{5} & - a_{5} & - d_{5} & e_{5} \\ d_{5} & - b_{5} & a_{5} & - e_{5} & - c_{5} \\ c_{5} & e_{5} & - a_{5} & b_{5} & - d_{5} \\ - e_{5} & d_{5} & a_{5} & - c_{5} & - b_{5} \end{matrix}] .$

For odd-frequency DHT with normalization in Equation (16) we use $C_{5}^{T}$ instead of $C_{5}$ .

We alter the order of rows and columns of $C_{5}$ applying the permutations

$π_{5} = (\begin{matrix} 1 & 2 \\ 2 & 3 \end{matrix} \begin{matrix} 3 & 4 & 5 \\ 1 & 5 & 4 \end{matrix}), π_{6} = (\begin{matrix} 1 & 2 \\ 1 & 2 \end{matrix} \begin{matrix} 3 & 4 & 5 \\ 3 & 5 & 4 \end{matrix}) .$

The corresponding permutation matrices are as follows

$P_{5}^{(1)} = [\begin{matrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{matrix}], P_{5}^{(0)} = [\begin{matrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{matrix}] .$

Then we decompose the resulting matrix $C_{5}^{(a)}$ into two submatrices:

(17) $C_{5}^{(a)} = C_{5}^{(b)} + C_{5}^{(c)},$

where

C_{5}^{(b)} = [\begin{matrix} a_{5} \\ - a_{5} \\ a_{5} & a_{5} & a_{5} & a_{5} & a_{5} \\ - a_{5} \\ a_{5} \end{matrix}]

and

C_{5}^{(c)} = [\begin{matrix} b_{5} & c_{5} & e_{5} & - d_{5} \\ d_{5} & - b_{5} & - c_{5} & - e_{5} \\ - e_{5} & d_{5} & - b_{5} & - c_{5} \\ c_{5} & e_{5} & - d_{5} & b_{5} \end{matrix}]

In the third column and third row of the matrix $C_{5}^{(b)}$ it is obtained identical entries that differ only in sign. Therefore, the number of operations can be reduced without additional transforms [36]. We eliminate in matrix $C_{5}^{(c)}$ the row and column with only zero entries. The resulted matrix

$C_{4}^{(d)} = [\begin{matrix} b_{5} & c_{5} & e_{5} & - d_{5} \\ d_{5} & - b_{5} & - c_{5} & - e_{5} \\ - e_{5} & d_{5} & - b_{5} & - c_{5} \\ c_{5} & e_{5} & - d_{5} & b_{5} \end{matrix}]$

matches the matrix template

[\begin{matrix} A_{2}^{(a)} & B_{2}^{(a)} \\ - B_{2}^{(a)} & - A_{2}^{(a)} \end{matrix}]

where

A_{2}^{(a)} = [\begin{matrix} b_{5} & c_{5} \\ d_{5} & - b_{5} \end{matrix}]

B_{2}^{(a)} = [\begin{matrix} e_{5} & - d_{5} \\ - c_{5} & - e_{5} \end{matrix}]

The factorization of template $[\begin{matrix} A_{2}^{(a)} & B_{2}^{(a)} \\ - B_{2}^{(a)} & - A_{2}^{(a)} \end{matrix}]$ is known from [34], and we represent the matrix $C_{4}^{(d)}$ as

(18) $C_{4}^{(d)} = ({\bar{I}}_{2} \otimes I_{2}) (H_{2} \otimes I_{2}) 1 / 2 [(A_{2}^{(a)} + B_{2}^{(a)}) \oplus (A_{2}^{(a)} - B_{2}^{(a)})] (H_{2} \otimes I_{2}),$

where

{\bar{I}}_{2} = [\begin{matrix} 1 & 0 \\ 0 & - 1 \end{matrix}]

. The resulting matrices

A_{2}^{(a)} + B_{2}^{(a)} = [\begin{matrix} b_{5} + e_{5} & c_{5} - d_{5} \\ d_{5} - c_{5} & - b_{5} - e_{5} \end{matrix}]

and

A_{2}^{(a)} - B_{2}^{(a)} = [\begin{matrix} b_{5} - e_{5} & c_{5} + d_{5} \\ d_{5} + c_{5} & - b_{5} + e_{5} \end{matrix}]

match the templates

[\begin{matrix} g & h \\ - h & - g \end{matrix}]

and

[\begin{matrix} p & q \\ q & - p \end{matrix}]

, respectively. Therefore, we obtain the following factorizations from [34]:

(19) $A_{2}^{(a)} + B_{2}^{(a)} = {\bar{I}}_{2} H_{2} \times diag ((g + h) / 2, (g - h) / 2) H_{2}, A_{2}^{(a)} - B_{2}^{(a)} = T_{2 \times 3}^{(4)} \times diag (p - q, - p - q, q) T_{3 \times 2}^{(3)},$

where

T_{2 \times 3}^{(4)} = [\begin{matrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{matrix}]

T_{3 \times 2}^{(3)} = [\begin{matrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{matrix}],

= b_{5} + e_{5},

= c_{5} - d_{5},

= b_{5} - e_{5},

= c_{5} + d_{5} .

Let us add matrices from decomposition (19) to the left of the diagonal matrix into the matrix $W_{6 \times 7} = ({\bar{I}}_{2} H_{2}) \oplus I_{2} \oplus T_{2 \times 3}^{(4)}$ , and to the left of the diagonal matrix into the matrix $W_{7 \times 6} = H_{2} \oplus I_{2} \oplus T_{3 \times 2}^{(3)}$ . Combining the expressions (17), (18), and (19) the matrix factorization for the five-point odd-time DHT with normalization is represented as

(20) $Y_{5 \times 1} = P_{5}^{(1)} W_{5 \times 6} W_{6}^{(1)} W_{6 \times 7} D_{7} W_{7 \times 6} W_{6}^{(0)} W_{6 \times 5} P_{5}^{(0)} X_{5 \times 1}$

where

$D_{7} = diag (s_{0}^{(5)}, s_{1}^{(5)}, s_{2}^{(5)}, s_{3}^{(5)}, s_{4}^{(5)}, s_{5}^{(5)}, s_{6}^{(5)}), s_{0}^{(5)} = (b_{5} + e_{5} + c_{5} - d_{5}) / 4; s_{1}^{(5)} = (b_{5} + e_{5} - c_{5} + d_{5}) / 4; s_{2}^{(5)} = a_{5}; s_{3}^{(5)} = a_{5}; s_{4}^{(5)} = (b_{5} - e_{5} - c_{5} - d_{5}) / 2; s_{5}^{(5)} = (- b_{5} + e_{5} - c_{5} - d_{5}) / 2; s_{6}^{(5)} = (c_{5} + d_{5}) / 2; W_{6}^{(1)} = [\begin{matrix} 1 & 1 \\ 1 & 1 \\ 1 \\ 1 \\ - 1 & 1 \\ - 1 & 1 \end{matrix}], W_{6}^{(0)} = [\begin{matrix} 1 & 1 \\ 1 & 1 \\ 1 \\ 1 \\ 1 & - 1 \\ 1 & - 1 \end{matrix}], W_{6 \times 5} = [\begin{matrix} 1 \\ 1 \\ 1 \\ 1 & 1 & 1 & 1 \\ 1 \\ 1 \end{matrix}], W_{5 \times 6} = [\begin{matrix} 1 & - 1 \\ 1 & 1 \\ 1 & 1 \\ 1 & 1 \\ - 1 & 1 \end{matrix}] .$

We have added the matrix $I_{2}$ into the crossing of third and fourth columns and rows of the matrices $W_{7 \times 6}, W_{6 \times 7}$ , $W_{6}^{(1)}$ and $W_{6}^{(0)}$ . This allows the factorizing the matrix $C_{5}^{(b)}$ using $W_{6 \times 5}$ and $W_{5 \times 6}$ .

Next, we present the algorithm of the five-point odd-time DHT with normalization via the data flow graph in Figure 6. As one can see, the number of multiplications is reduced from 25 to 6 because $s_{1}^{(5)} = 0.25$ ; the number of additions is enlarged from 20 to 23.

Based on Equation (20), the matrix factorization for the five-point odd-frequency DHT with normalization is represented as

(21) $Y_{5 \times 1} = {(P_{5}^{(0)})}^{T} W_{6 \times 5}^{T} {(W_{6}^{(0)})}^{T} W_{7 \times 6}^{T} D_{7} W_{6 \times 7}^{T} {(W_{6}^{(1)})}^{T} W_{5 \times 6}^{T} {(P_{5}^{(1)})}^{T} X_{5 \times 1}$

Figure 7 shows a data flow graph of the algorithm for the five-point odd-frequency DHT with normalization. The number of arithmetic operations is the same as for 5-point odd-time DHT with normalization.

3.5. Algorithms for 6-Point Odd-Time DHT and Odd-Frequency DHT

Let us propose an algorithm for six-point odd-time DHT with normalization which is expressed as follows:

(22) $Y_{6 \times 1} = C_{6} X_{6 \times 1},$

where

Y_{6 \times 1} = {[y_{0}, y_{1}, y_{2}, y_{3}, y_{4}, y_{5}]}^{T}

X_{6 \times 1} = {[x_{0}, x_{1}, x_{2}, x_{3}, x_{4}, x_{5}]}^{T}

$C_{6} = [\begin{matrix} a_{6} & a_{6} & a_{6} & a_{6} & a_{6} & a_{6} \\ b_{6} & a_{6} & - c_{6} & - b_{6} & - a_{6} & c_{6} \\ b_{6} & - a_{6} & - c_{6} & b_{6} & - a_{6} & - c_{6} \\ a_{6} & - a_{6} & a_{6} & - a_{6} & a_{6} & {- a}_{6} \\ c_{6} & a_{6} & - b_{6} & c_{6} & a_{6} & - b_{6} \\ - c_{6} & a_{6} & b_{6} & c_{6} & - a_{6} & - b_{6} \end{matrix}]$

with

a_{6} = \frac{1}{\sqrt{6}} \approx 0.4082,

b_{6}

\frac{1}{\sqrt{6}} cas \frac{π}{6} \approx

0.5577,

c_{6}

\frac{1}{\sqrt{6}} cas \frac{2 π}{3} \approx

0.1494. For odd-frequency DHT with normalization in Equation (22) we use

C_{6}^{T}

instead of

C_{6}

Note that $c_{6}$ = $b_{6} - a_{6}$ , thus we decompose $C_{6} = a_{6} C_{6}^{(a)} + C_{6}^{(b)}$ , where

$C_{6}^{(a)} = [\begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & - 1 & - 1 \\ 0 & - 1 & 1 & 0 & - 1 & 1 \\ 1 & - 1 & 1 & - 1 & 1 & - 1 \\ - 1 & 1 & 0 & - 1 & 1 & 0 \\ 1 & 1 & 0 & - 1 & - 1 & 0 \end{matrix}], C_{6}^{(b)} = [\begin{matrix} b_{6} & - b_{6} & - b_{6} & b_{6} \\ b_{6} & - b_{6} & b_{6} & - b_{6} \\ b_{6} & - b_{6} & b_{6} & - b_{6} \\ - b_{6} & b_{6} & b_{6} & - b_{6} \end{matrix}] .$

Further the matrix $C_{6}^{(a)}$ is added to factorization immediately as a submatrix of the matrix $W_{8 \times 10}$ : $W_{8 \times 10} = C_{6}^{(a)} \oplus B_{2 \times 4}$ , $B_{2 \times 4} = [\begin{matrix} - 1 & 1 & 1 & - 1 \\ 1 & - 1 & 1 & - 1 \end{matrix}]$ . The matrix $B_{2 \times 4}$ is determined by the structure of the matrix $C_{6}^{(b)}$ for which the second and sixth rows, the third and fifth rows are the same except on the sign. The matrices $W_{10 \times 6}$ and $W_{6 \times 8}$ will denote the order of the columns and the rows of the matrices $C_{6}^{(a)}$ and $B_{2 \times 4}$ in resulted factorization. The identity submatrix $I_{6}$ of $W_{10 \times 6}$ and $W_{6 \times 8}$ related to $C_{6}^{(a)}$ , and the rest submatrices of $W_{10 \times 6}$ and $W_{6 \times 8}$ related to $B_{2 \times 4}$ :

$W_{10 \times 6} = [\begin{matrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{matrix}], W_{6 \times 8} = [\begin{matrix} 1 \\ 1 & - 1 \\ 1 & 1 \\ 1 \\ 1 & 1 \\ 1 & 1 \end{matrix}]$

Let us introduce $s_{0}^{(6)} = s_{1}^{(6)} = s_{2}^{(6)} = s_{3}^{(6)} = s_{4}^{(6)} = s_{5}^{(6)} = a_{6}$ to multiply the each row of matrix $C_{6}^{(a)}$ , and $s_{6}^{(6)} = s_{7}^{(6)} = b_{6}$ to multiply the each row of $B_{2 \times 4}$ . Then the factorization of the matrix of the 6-point odd-time DHT with normalization can be expressed as [37]

(23) $Y_{6 \times 1} = W_{6 \times 8} D_{8} W_{8 \times 10} W_{10 \times 6} X_{6 \times 1},$

where

D_{8} = diag (s_{0}^{(6)}, s_{1}^{(6)}, s_{2}^{(6)}, s_{3}^{(6)}, s_{4}^{(6)}, s_{5}^{(6)}, s_{6}^{(6)}, s_{7}^{(6)})

Figure 8 shows the data flow graph of the algorithm of the 6-point odd-time DHT with normalization. The amount of multiplications and additions can be lessened from 36 to 8 and from 30 to 28, respectively.

Based on Equation (23), the matrix factorization for the 6-point odd-frequency DHT with normalization is expressed as

(24) $Y_{6 \times 1} = W_{10 \times 6}^{T} W_{8 \times 10}^{T} D_{8} W_{6 \times 8}^{T} X_{6 \times 1},$

Figure 9 shows the data flow graph of the algorithm implementing the 6-point odd-frequency DHT with normalization. As one can see, the amount of multiplications may be lessened from 36 to 8. Also we decreased the amount of additions from 30 to 24.

3.6. Algorithms for 7-Point Odd-Time DHT and Odd-Frequency DHT

Now we will design the algorithm for 7-point odd-time DHT with normalization using the expression

(25) $Y_{7 \times 1} = C_{7} X_{7 \times 1},$

where

Y_{7 \times 1} = {[y_{0}, y_{1}, y_{2}, y_{3}, y_{4}, y_{5}, y_{6}]}^{T}

X_{7 \times 1} = {[x_{0}, x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}]}^{T}

a_{7}

\frac{1}{\sqrt{7}} \approx

0.3780,

b_{7}

\frac{1}{\sqrt{7}} cas \frac{π}{7} \approx

0.5045,

c_{7}

\frac{1}{\sqrt{7}} cas \frac{3 π}{7} \approx

0.4526,

d_{7}

\frac{1}{\sqrt{7}} cas \frac{5 π}{7} \approx

0.0598,

e_{7}

\frac{1}{\sqrt{7}} cas \frac{2 π}{7} \approx

0.5312,

g_{7}

- \frac{1}{\sqrt{7}} cas \frac{6 π}{7} \approx

0.1765,

f_{7}

\frac{1}{\sqrt{7}} cas \frac{4 π}{7} \approx

0.2844,

$C_{7} = [\begin{matrix} a_{7} & a_{7} & a_{7} & a_{7} & a_{7} & a_{7} & a_{7} \\ b_{7} & c_{7} & d_{7} & - a_{7} & - e_{7} & - f_{7} & g_{7} \\ e_{7} & - g_{7} & - c_{7} & a_{7} & f_{7} & - b_{7} & - d_{7} \\ c_{7} & - e_{7} & b_{7} & - a_{7} & g_{7} & d_{7} & - f_{7} \\ f_{7} & - d_{7} & - g_{7} & a_{7} & - b_{7} & e_{7} & - c_{7} \\ d_{7} & b_{7} & - f_{7} & - a_{7} & c_{7} & g_{7} & - e_{7} \\ - g_{7} & f_{7} & e_{7} & a_{7} & - d_{7} & - c_{7} & - b_{7} \end{matrix}] .$

For odd-frequency DHT with normalization in Equation (25) the $C_{7}^{T}$ matrix must be used instead of $C_{7}$ .

Let us define the permutations $π_{7}$ and $π_{8}$ :

$π_{7} = (\begin{matrix} 1 & 2 \\ 2 & 3 \end{matrix} \begin{matrix} 3 & 4 & 5 & 6 & 7 \\ 4 & 1 & 7 & 6 & 5 \end{matrix}), π_{8} = (\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 2 & 3 & 4 & 7 & 6 & 5 \end{matrix}) .$

After permutation of the rows of $C_{7}$ with $π_{7}$ and permutation the columns of $C_{7}$ with $π_{8}$ , we alter the sign of the fifth, sixth, and seventh columns. The corresponding permutation matrices are introduced as

$P_{7}^{(1)} = [\begin{matrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{matrix}], P_{7}^{(0)} = [\begin{matrix} 1 \\ 1 \\ 1 \\ 1 \\ - 1 \\ - 1 \\ - 1 \end{matrix}] .$

The obtained matrix $C_{7}^{(a)}$ was decomposed into two components:

(26) $C_{7}^{(a)} = C_{7}^{(b)} + C_{7}^{(c)},$

where

$C_{7}^{(b)} = [\begin{matrix} - a_{7} \\ a_{7} \\ - a_{7} \\ a_{7} & a_{7} & a_{7} & a_{7} & - a_{7} & - a_{7} & - a_{7} \\ a_{7} \\ - a_{7} \\ a_{7} \end{matrix}], C_{7}^{(c)} = [\begin{matrix} b_{7} & c_{7} & d_{7} & - g_{7} & f_{7} & e_{7} \\ e_{7} & - g_{7} & - c_{7} & d_{7} & b_{7} & - f_{7} \\ c_{7} & - e_{7} & b_{7} & f_{7} & - d_{7} & - g_{7} \\ - g_{7} & f_{7} & e_{7} & b_{7} & c_{7} & d_{7} \\ d_{7} & b_{7} & - f_{7} & e_{7} & - g_{7} & - c_{7} \\ f_{7} & - d_{7} & - g_{7} & c_{7} & - e_{7} & b_{7} \end{matrix}] .$

We can reduce the number of operations by taking into account the similar entries in the fourth column and fourth row of the matrix $C_{7}^{(b)}$ [36], which differ only in sign. Next, in matrix $C_{7}^{(c)}$ we eliminate the rows and columns with only zero entries. The obtained matrix

$C_{6}^{(d)} = [\begin{matrix} b_{7} & c_{7} & d_{7} & - g_{7} & f_{7} & e_{7} \\ e_{7} & - g_{7} & - c_{7} & d_{7} & b_{7} & - f_{7} \\ c_{7} & - e_{7} & b_{7} & f_{7} & - d_{7} & - g_{7} \\ - g_{7} & f_{7} & e_{7} & b_{7} & c_{7} & d_{7} \\ d_{7} & b_{7} & - f_{7} & e_{7} & - g_{7} & - c_{7} \\ f_{7} & - d_{7} & - g_{7} & c_{7} & - e_{7} & b_{7} \end{matrix}]$

acquires the structure

[\begin{matrix} A_{3} & B_{3} \\ B_{3} & A_{3} \end{matrix}]

and can be decomposed as [34]:

(27) $C_{6}^{(d)} = (H_{2} \otimes I_{3}) 1 / 2 [(A_{3} + B_{3}) \oplus (A_{3} - B_{3})] (H_{2} \otimes I_{3}) .$

Now we will decompose the matrices

$A_{3} + B_{3} = [\begin{matrix} b_{7} {- g}_{7} & c_{7} + f_{7} & e_{7} + d_{7} \\ e_{7} + d_{7} & b_{7} {- g}_{7} & - (c_{7} + f_{7}) \\ c_{7} + f_{7} & - (e_{7} + d_{7}) & b_{7} {- g}_{7} \end{matrix}], A_{3} - B_{3} = [\begin{matrix} b_{7} {+ g}_{7} & c_{7} - f_{7} & d_{7} - e_{7} \\ e_{7} - d_{7} & - (b_{7} {+ g}_{7}) & - (c_{7} - f_{7}) \\ c_{7} - f_{7} & d_{7} - e_{7} & b_{7} {+ g}_{7} \end{matrix}],$

representing them as a circular convolution matrix

H_{3} = [\begin{matrix} h_{0} & h_{2} & h_{1} \\ h_{1} & h_{0} & h_{2} \\ h_{2} & h_{1} & h_{0} \end{matrix}]

[35,36]:

(28) $H_{3} = T_{3}^{(1)} T_{3 \times 4} \times diag (s_{0}, s_{1}, s_{2}, s_{3}) {\times T}_{4 \times 3} T_{3}^{(0)},$

where

s_{0} = {(h}_{0} + h_{1} + h_{2}) / 3, s_{1} = h_{0} - h_{2}, s_{2} = h_{1} - h_{2}, s_{3} = {(h}_{0} + h_{1} - 2 h_{2}) / 3

;

T_{3}^{(1)} = [\begin{matrix} 1 & 1 \\ 1 & - 1 & - 1 \\ 1 & 1 \end{matrix}]

$T_{3 \times 4} = [\begin{matrix} 1 \\ 1 & - 1 \\ 1 & - 1 \end{matrix}], T_{4 \times 3} = [\begin{matrix} 1 \\ 1 \\ 1 \\ 1 & 1 \end{matrix}], T_{3}^{(0)} = [\begin{matrix} 1 & 1 & 1 \\ 1 & - 1 \\ 1 & - 1 \end{matrix}] .$

We need to modify the matrices $(A_{3} + B_{3})$ , $(A_{3} - B_{3})$ to make them consistent with the expression of the circular convolution for N = 3. For that, in the matrix $(A_{3} + B_{3})$ the sign of entries in the first column and first row was altered by multiplying left and right on $P_{3}^{(1)} = [\begin{matrix} - 1 \\ 1 \\ 1 \end{matrix}]$ . In the $(A_{3} - B_{3})$ matrix the sign of the second-row entries was changed by multiplying left on $P_{3}^{(0)} = [\begin{matrix} 1 \\ - 1 \\ 1 \end{matrix}]$ . As a result, we obtain the matrices:

$(A_{3} + B_{3})^{(0)} = [\begin{matrix} b_{7} {- g}_{7} & - (c_{7} + f_{7}) & - (e_{7} + d_{7}) \\ - (e_{7} + d_{7}) & b_{7} {- g}_{7} & - (c_{7} + f_{7}) \\ - (c_{7} + f_{7}) & - (e_{7} + d_{7}) & b_{7} {- g}_{7} \end{matrix}], (A_{3} - B_{3})^{(0)} = [\begin{matrix} b_{7} {+ g}_{7} & c_{7} - f_{7} & d_{7} - e_{7} \\ d_{7} - e_{7} & b_{7} {+ g}_{7} & c_{7} - f_{7} \\ c_{7} - f_{7} & d_{7} - e_{7} & b_{7} {+ g}_{7} \end{matrix}] .$

Let us apply the expression (28) to $(A_{3} + B_{3})^{(0)}$ , $(A_{3} - B_{3})^{(0)} .$ For the matrix $(A_{3} + B_{3})^{(0)}$ the elements of circular convolution are $h_{0} = b_{7} {- g}_{7}, h_{1} = - e_{7} - d_{7}, h_{2} = - c_{7} - f_{7}$ . For the matrix $(A_{3} - B_{3})^{(0)}$ we have $h_{0} = b_{7} {+ g}_{7}, h_{1} = - e_{7} + d_{7}, h_{2} = c_{7} - f_{7}$ . Further we form the matrices $W_{10 \times 8} = T_{4 \times 3} \oplus I_{2} \oplus T_{4 \times 3}$ , $W_{8 \times 10} = T_{3 \times 4} \oplus I_{2} \oplus T_{3 \times 4}$ to factorize the circular convolutions. The matrices $T_{3}^{(1)}$ and $T_{3}^{(0)}$ were multiplied on $P_{3}^{(1)}$ and $P_{3}^{(0)}$ . And we obtained $W_{a} = T_{3}^{(0)} P_{3}^{(1)} = [\begin{matrix} - 1 & 1 & 1 \\ - 1 & - 1 \\ 1 & - 1 \end{matrix}]$ , $W_{c} = P_{3}^{(1)} T_{3}^{(1)} = [\begin{matrix} - 1 & - 1 \\ 1 & - 1 & - 1 \\ 1 & 1 \end{matrix}]$ , $W_{d} {= P}_{3}^{(0)} T_{3}^{(1)} = [\begin{matrix} 1 & 1 \\ - 1 & 1 & 1 \\ 1 & 1 \end{matrix}]$

We have added the matrix $I_{2}$ into direct sum in the matrices $W_{10 \times 8}, W_{8 \times 10}$ , $W_{8}^{(0)}$ and $W_{8}^{(1)}$ . This allows the factorizing the matrix $C_{7}^{(b)}$ using $W_{7 \times 8}$ and $W_{8 \times 7}$ .

In sum, we derive the factorization of the matrix of the seven-point odd-time DHT with normalization:

(29) $Y_{7 \times 1} = P_{7}^{(1)} W_{7 \times 8} W_{8} W_{8}^{(1)} W_{8 \times 10} D_{10} W_{10 \times 8} W_{8}^{(0)} W_{8} W_{8 \times 7} P_{7}^{(0)} X_{7 \times 1},$

where

D_{10} = diag (s_{0}^{(7)}, s_{1}^{(7)}, s_{2}^{(7)}, s_{3}^{(7)}, s_{4}^{(7)}, s_{5}^{(7)}, s_{6}^{(7)}, s_{7}^{(7)}, s_{8}^{(7)}, s_{9}^{(7)})

$W_{8}^{(0)} = W_{a} \oplus I_{2} \oplus T_{3}^{(0)}, W_{8}^{(1)} = W_{c} \oplus I_{2} \oplus W_{d}, s_{0}^{(7)} = (b_{7} {- g}_{7} - e_{7} - d_{7} - c_{7} - f_{7}) / 6; s_{1}^{(7)} = (b_{7} {- g}_{7} {+ c}_{7} + f_{7}) / 2; s_{2}^{(7)} = (- e_{7} - d_{7} + c_{7} + f_{7}) / 2; s_{3}^{(7)} = (b_{7} {- g}_{7} - d_{7} - e_{7} + 2 c_{7} + {2 f}_{7}) / 6; s_{4}^{(7)} = a_{7}; s_{5}^{(7)} = a_{7}; s_{6}^{(7)} = (b_{7} {+ g}_{7} - e_{7} + d_{7} + c_{7} - f_{7}) / 6; s_{7}^{(7)} = (b_{7} {+ g}_{7} {- c}_{7} + f_{7}) / 2; s_{8}^{(7)} = (- e_{7} + d_{7} - c_{7} + f_{7}) / 2; s_{9}^{(7)} = (b_{7} {+ g}_{7} - e_{7} + d_{7} - 2 c_{7} + {2 f}_{7}) / 6; W_{7 \times 8} = [\begin{matrix} 1 & - 1 \\ 1 & 1 \\ 1 & - 1 \\ 1 & 1 \\ 1 & 1 \\ - 1 & 1 \\ 1 & 1 \end{matrix}], W_{8 \times 7} = [\begin{matrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 & 1 & 1 & - 1 & - 1 & - 1 \\ 1 \\ 1 \\ 1 \end{matrix}], W_{8} = [\begin{matrix} 1 & 1 \\ 1 & 1 \\ 1 & 1 \\ 1 \\ 1 \\ 1 & - 1 \\ 1 & - 1 \\ 1 & - 1 \end{matrix}] .$

To calculate the 7-point odd-time DHT with normalization the fast algorithm is developed and presented in Figure 10 by data flow graph. As a consequence we can reduce the amount of multiplications from 49 to 10, but the amount of additions increased from 42 to 46.

Based on Equation (29), the matrix factorization for the 7-point odd-frequency DHT with normalization is obtained as

(30) $Y_{7 \times 1} = {(P_{7}^{(0)})}^{T} W_{8 \times 7}^{T} W_{8}^{T} {(W_{8}^{(0)})}^{T} W_{10 \times 8}^{T} D_{10} W_{8 \times 10}^{T} {(W_{8}^{(1)})}^{T} W_{8}^{T} W_{7 \times 8}^{T} {(P_{7}^{(1)})}^{T} X_{7 \times 1},$

To compute the 7-point odd-frequency DHT with normalization we propose the fast algorithm shown in Figure 11 by data flow graph. The number of arithmetic operations is the same as for 7-point odd-time DHT with normalization.

3.7. Algorithms for 8-Point Odd-Time DHT and Odd-Frequency DHT

Let us develop the algorithm for eight-point odd-time DHT with normalization which is expressed as follows:

(31) $Y_{8 \times 1} = C_{8} X_{8 \times 1},$

where

Y_{8 \times 1} = {[y_{0}, y_{1}, y_{2}, y_{3}, y_{4}, y_{5}, y_{6}, y_{7}]}^{T}

X_{8 \times 1} = {[x_{0}, x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}, x_{7}]}^{T}

$C_{8} = [\begin{matrix} a_{8} & a_{8} & a_{8} & a_{8} & a_{8} & a_{8} & a_{8} & a_{8} \\ b_{8} & b_{8} & c_{8} & - c_{8} & - b_{8} & - b_{8} & - c_{8} & c_{8} \\ d_{8} & 0 & - d_{8} & 0 & d_{8} & 0 & - d_{8} & 0 \\ b_{8} & - b_{8} & c_{8} & c_{8} & - b_{8} & b_{8} & - c_{8} & - c_{8} \\ a_{8} & - a_{8} & a_{8} & - a_{8} & a_{8} & - a_{8} & a_{8} & - a_{8} \\ c_{8} & c_{8} & - b_{8} & b_{8} & - c_{8} & - c_{8} & b_{8} & - b_{8} \\ 0 & d_{8} & 0 & - d_{8} & 0 & d_{8} & 0 & - d_{8} \\ - c_{8} & c_{8} & b_{8} & b_{8} & c_{8} & - c_{8} & - b_{8} & - b_{8} \end{matrix}]$

with

a_{8}

\frac{1}{\sqrt{8}} \approx

0.3536;

b_{8}

\frac{1}{\sqrt{8}} cas \frac{π}{8} \approx

0.4619;

c_{8}

\frac{1}{\sqrt{8}} cas \frac{5 π}{8} \approx

0.1913;

d_{8}

\frac{1}{\sqrt{8}} cas \frac{π}{4} =

0.5. For odd-frequency DHT with normalization in (31) the

C_{8}^{T}

matrix must be used instead of

C_{8}

Let us define the permutation $π_{8} = (\begin{matrix} 1 & 2 \\ 1 & 5 \end{matrix} \begin{matrix} 3 & 4 & 5 & 6 & 7 & 8 \\ 3 & 7 & 4 & 2 & 6 & 8 \end{matrix})$ to change the order of rows of $C_{8}$ . The permutation matrix $P_{8}$ and the resulted matrix $C_{8}^{(a)}$ can be expressed as

$P_{8} = [\begin{matrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{matrix}], C_{8}^{(a)} = [\begin{matrix} a_{8} & a_{8} & a_{8} & a_{8} & a_{8} & a_{8} & a_{8} & a_{8} \\ a_{8} & - a_{8} & a_{8} & - a_{8} & a_{8} & - a_{8} & a_{8} & - a_{8} \\ d_{8} & 0 & - d_{8} & 0 & d_{8} & 0 & - d_{8} & 0 \\ 0 & d_{8} & 0 & - d_{8} & 0 & d_{8} & 0 & - d_{8} \\ b_{8} & - b_{8} & c_{8} & c_{8} & - b_{8} & b_{8} & - c_{8} & - c_{8} \\ b_{8} & b_{8} & c_{8} & - c_{8} & - b_{8} & - b_{8} & - c_{8} & c_{8} \\ c_{8} & c_{8} & - b_{8} & b_{8} & - c_{8} & - c_{8} & b_{8} & - b_{8} \\ - c_{8} & c_{8} & b_{8} & b_{8} & c_{8} & - c_{8} & - b_{8} & - b_{8} \end{matrix}] .$

The resulted matrix $C_{8}^{(a)}$ acquires the structure:

$[\begin{matrix} A_{4} & A_{4} \\ B_{4} & - B_{4} \end{matrix}] with A_{4} = [\begin{matrix} a_{8} & a_{8} & a_{8} & a_{8} \\ a_{8} & - a_{8} & a_{8} & - a_{8} \\ d_{8} & 0 & - d_{8} & 0 \\ 0 & d_{8} & 0 & {- d}_{8} \end{matrix}] and B_{4} = [\begin{matrix} b_{8} & - b_{8} & c_{8} & c_{8} \\ b_{8} & b_{8} & c_{8} & - c_{8} \\ c_{8} & c_{8} & - b_{8} & b_{8} \\ - c_{8} & c_{8} & b_{8} & b_{8} \end{matrix}] .$

Then using the template from [34] we obtain $C_{8}^{(a)} = (A_{4} \oplus B_{4}) (H_{2} \otimes I_{4})$ . The matrix $A_{4}$ has the following structure:

$[\begin{matrix} A_{2}^{(b)} & A_{2}^{(b)} \\ B_{2}^{(b)} & - B_{2}^{(b)} \end{matrix}] with A_{2}^{(b)} = diag (a_{8}, a_{8}) H_{2} and B_{2}^{(b)} = d_{8} I_{2} .$

Using the decomposition of the extracted submatrices [34], the matrix $A_{4}$ is represented as

(32) $A_{4} = diag (a_{8}, a_{8}, d_{8}, d_{8}) (H_{2} \oplus I_{2}) (H_{2} \otimes I_{2}) .$

The entries of the diagonal matrix we denoted as $s_{0}^{(8)} = a_{8},$ $s_{1}^{(8)} = a_{8},$ $s_{2}^{(8)} = d_{8},$ $s_{3}^{(8)} = d_{8} .$

Next we swap the first and second column of the $B_{4}$ matrix with permutation matrix $P_{2} \oplus I_{2}, P_{2} = [\begin{matrix} 1 \\ 1 \end{matrix}]$ . The resulted matrix $B_{4}^{(a)} = [\begin{matrix} - b_{8} & b_{8} & c_{8} & c_{8} \\ b_{8} & b_{8} & c_{8} & - c_{8} \\ c_{8} & c_{8} & - b_{8} & b_{8} \\ c_{8} & - c_{8} & b_{8} & b_{8} \end{matrix}]$ is similar to the template $[\begin{matrix} A_{2}^{(c)} & B_{2}^{(c)} \\ B_{2}^{(c)} & A_{2}^{(c)} \end{matrix}]$ and can be decomposed as

(33) $B_{4}^{(a)} = (H_{2} \otimes I_{2}) 1 / 2 [(A_{2}^{(c)} + B_{2}^{(c)}) \oplus (A_{2}^{(c)} - B_{2}^{(c)})] (H_{2} \otimes I_{2}),$

where

1 / 2 (A_{2}^{(c)} + B_{2}^{(c)}) = 1 / 2 [\begin{matrix} - b_{8} + c_{8} & b_{8} + c_{8} \\ b_{8} + c_{8} & b_{8} - c_{8} \end{matrix}]

matches the pattern

1 / 2 [\begin{matrix} e & f \\ f & - e \end{matrix}]

e = - b_{8} + c_{8}

f = b_{8} + c_{8}

. It is represented as

(34) $1 / 2 (A_{2}^{(c)} + B_{2}^{(c)}) = T_{2 \times 3}^{(4)} \times diag (e - f, - e - f, f) T_{3 \times 2}^{(3)},$

where

T_{2 \times 3}^{(4)}

T_{3 \times 2}^{(3)}

are defined as in Equation (19). The entries of diagonal matrix we denoted as

s_{4}^{(8)} = - b_{8}, s_{5}^{(8)} = - c_{8}, s_{6}^{(8)} = (b_{8} + c_{8}) / 2 .

The matrix

1 / 2 (A_{2}^{(c)} - B_{2}^{(c)})

is similarly decomposed with diagonal matrix entries

s_{7}^{(8)} = - b_{8}, s_{8}^{(8)} = c_{8}, s_{9}^{(8)} = (b_{8} - c_{8}) / 2 .

Let us add matrices from decomposition (34) to the left of the diagonal matrix into the matrix $W_{8 \times 10} = I_{4} \oplus T_{2 \times 3}^{(4)} \oplus T_{2 \times 3}^{(4)}$ , and to the right of the diagonal matrix into the matrix $W_{10 \times 8} = I_{4} \oplus T_{3 \times 2}^{(3)} \oplus T_{3 \times 2}^{(3)}$ . Also we added matrices from decompositions (32), (33) to the left of the diagonal matrices into the matrix $W_{8}^{(a)} = I_{4} \oplus (H_{2} \otimes I_{2})$ , and to the right of the diagonal matrices into $W_{8}^{(b)} = H_{2} {\oplus I}_{2} \oplus P_{2} \oplus I_{2}, W_{8}^{(c)} = (H_{2} \otimes I_{2}) \oplus I_{4}, W_{8}^{(d)} = H_{2} \otimes I_{4}$ .

In sum, the 8-point odd-time DHT with normalization is factorized as

(35) $Y_{8 \times 1} = P_{8} W_{8}^{(a)} W_{8 \times 10} D_{10} W_{10 \times 8} W_{8}^{(a)} W_{8}^{(b)} W_{8}^{(c)} W_{8}^{(d)} X_{8 \times 1},$

where

D_{10} = diag (s_{0}^{(8)}, s_{1}^{(8)}, s_{2}^{(8)}, s_{3}^{(8)} {, s}_{4}^{(8)}, s_{5}^{(8)}, s_{6}^{(8)} {, s}_{7}^{(8)}, s_{8}^{(8)}, s_{9}^{(8)})

To compute the 8-point odd-time DHT with normalization the data flow graph of the fast algorithm is designed and presented in Figure 12. As a consequence we can reduce the amount of multiplications from 48 to 8, because $s_{2}^{(8)} = s_{3}^{(8)} = 0.5$ , and the amount of additions from 48 to 28.

Based on Equation (35), the matrix factorization for the 8-point odd-frequency DHT with normalization is given as

(36) $Y_{8 \times 1} = {(W_{8}^{(d)})}^{T} {(W_{8}^{(c)})}^{T} {(W_{8}^{(b)})}^{T} {(W_{8}^{(a)})}^{T} W_{10 \times 8}^{T} D_{10} W_{8 \times 10}^{T} {(W_{8}^{(a)})}^{T} P_{8}^{T} X_{8 \times 1},$

Figure 13 shows the data flow graph of the algorithm implementing the 8-point odd-frequency DHT with normalization. The amount of arithmetic operations is the same as for 8-point odd-time DHT with normalization.

4. Results

We confirmed the correctness of the odd-time DHT and odd-frequency DHT matrix factorizations obtained in Section 3 by experiment. Using the MATLAB R2023b software it was evaluated the coincidence of the results of the multiplication of factorized matrices by Formulas (7), (10), (14), (20), (23), (29), and (35) with the original odd-time DHT matrices. Also, it was evaluated the similarity of the results of the computing of the matrices of the odd-frequency DHT with the expressions (11), (15), (21), (24), (30), (36) using the MATLAB R2023b environment. The last formulas define the factorizations of the odd-frequency DHT matrices. The obtained coincidence of the factorized matrices with the initial odd-time DHT and odd-frequency DHT matrices for each N indicates the correctness of the developed algorithms.

Next, we evaluated the number of arithmetic operations for the calculation of the odd-time DHT and odd-frequency DHT with normalization via matrix-vector product and for the proposed algorithms. In general, the multiplications on data flow graphs are corresponded to the graph vertices, denoted by circles with factors. The amount of additions was evaluated by the amount of entering of two graph edges in one vertex. One must notice that these operations for zero elements of odd-time DHT and odd-frequency DHT matrices were not counted. In the matrices $C_{4}$ and $C_{8}$ we have four and eight zeros, respectively. Also if an element of the odd-time DHT or odd-frequency DHT matrix can be expressed as a power of two then the multiplication by this element can be implemented by a shift and has not counted as a multiplication. The proposed algorithms use the same number of multiplications to both the odd-time DHT and the odd-frequency DHT with normalization. Applying these algorithms we can reduce the number of multiplications required for odd-time or odd-frequency DHTs by nearly 69%, and the amount of additions by nearly of 5% for odd-time DHT and 8% for odd-frequency DHT if the length of input data is in the range from 2 to 8.

Table 1 shows the obtained results. In parentheses, we indicate the difference in the amount of operations in percent. The plus means that the amount of operations has increased relative to the matrix-vector product, and the minus means it has lessened. In Table 2 and Table 3 the number of multiplication and additions is presented for the existing odd-time DHT and odd-frequency DHT algorithms.

5. Discussion of Computational Complexity

Let us compare the number of multiplication and additions for the existing algorithms and for the proposed algorithms of odd-time DHT and odd-frequency DHT with normalization. As for the odd-time DHT, if N = 4 then the proposed algorithm is no different from algorithms known from the literature by the multiplication number. However if the existing algorithms do not include the normalization they require the additional four multiplications. If N = 8 then the amount of multiplications may be lessened with the proposed solution versus Hamood’s algorithms [31,32] by 33%. Relative to the prime factor algorithm [17], the amount of multiplications for N = 8 is the same, and less than for the radix-2 algorithm [27] by 20%. However, the considered existing algorithms of odd-time DHT do not include normalization for N = 8 which requires 8 additional multiplications. The amount of additions for N = 8 has increased by 17% relative to Hamood’s algorithms [31,32] and is the same as for algorithms in [17,27].

As for the odd-frequency DHT, if N = 4 then the obtained algorithm is no different from algorithms known from the literature by the amount of multiplications. However the absence of normalization requires the additional four multiplications. Besides, for N = 4, the proposed algorithm reduces the number of additions significantly (by 40–45%). If N = 8 then the number of multiplications may be significantly lessened with the proposed solution relative to the radix-2 algorithm [28,29] but exceeds by 33% the number of multiplications for the algorithm of the prime factor (N = $2^{m}$ ) without normalization [17,41,42]. The normalization will require 8 additional multiplications.

Due to the evaluation that has been done in [34], we can estimate the reduction of computational complexity of the proposed algorithms by Big O notation. The list represents the number of arithmetic operations that the algorithm performs to obtain the odd-time or odd-frequency DHT of size N. We can use the estimation of template complexity for even N directly. For odd N we have decomposed the initial transform matrix as the sum of two matrices. Therefore we have to add two multiplications and 2(N − 1) additions to the Big O notation of the template complexity. The obtained estimations are summarised in Table 4. Analysing the resulting Big O estimates it should be noted the following. The number of multiplications is reduced two times, in general, although the number of additions is increased by 2(N − 1) if the proposed algorithms are compared to the direct matrix-vector product.

6. Conclusions

In the paper, the fast algorithms for odd-time DHT and odd-frequency DHT with normalization are proposed for input signals of short length. The obtained algorithms for short-length input signals can subsequently be used as readymade modules of algorithms for long-length sequences.

Including the normalization in the fast algorithms for odd-time DHT and odd-frequency DHT allows us to use them directly in applications that involve recovering the processed signals or images, specifically, in image compression, signal and image denoising, image encryption, etc. Normalization ensures the orthonormality of transform and, as a result, the inverse transform matrix is obtained by a transposing of the direct transform matrix. The last property enables the construction of fast algorithms for inverse transform based on the fast algorithms for direct transform easily.

The fast algorithms for odd-time DHT and odd-frequency DHT were developed in the article based on the structural properties of the matrices of the transform coefficients. Optimization of the parameters of the odd-time DHT and odd-frequency DHT is not performed. We have applied the partition of the initial matrix into the submatrices with previous rearranging of the matrix rows and/or columns. The partitioning of the original matrix and rearranging its structure aims to find the factorization which possibly reduces further the computational complexity. Based on the obtained factorizations, we have constructed the fast algorithms presented by the data flow graphs. The critical path of each designed data flow graph has only one multiplication. This is a significant advantage of the proposed solutions. If the critical path of the data flow graph has more than one multiplication, additional difficulties arise with the presentation and further processing of the result of each successive multiplication.

The comparison of the computational complexity of the direct matrix-vector products with the computational complexity of the proposed algorithms has shown a reducing in the number of multiplications by 69% for the input sequence lengths from 2 to 8. At the same time, the amount of additions is lowered by nearly 5% for odd-time DHT and by 8% for odd-frequency DHT for the same range of the input sequence lengths.

The comparison of the designed fast algorithms for odd-time DHT and odd-frequency DHT with the existing algorithms shows that bearing in mind the structure of transform matrices enabled the increase in the fast algorithms’ efficiency against the efficiency of radix-type algorithms. This result enables easier operation in real time because the amount of needed signal processor resources is significantly reduced. Reducing the number of multiplications significantly contributes to the resource- and time-saving of signal processing and enables easier operation in real-time.

Author Contributions

Conceptualization, A.C.; methodology, A.C. and M.P.; software, M.P.; validation, A.C., M.P. and J.S.; formal analysis, A.C., M.P. and J.S.; investigation, M.P. and J.S.; writing—original draft preparation, M.P. and A.C.; writing—review and editing, A.C., M.P. and J.S.; supervision, A.C. All authors have read and agreed to the published version of the manuscript.

Data Availability Statement

Data are contained within the article.

Conflicts of Interest

The authors declare no conflicts of interest. The funders had no role in the design of the study; in the collection, analyses, or interpretation of data; in the writing of the manuscript; or in the decision to publish the results.

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Figures and Tables

Figure 1. The data flow graph of the proposed algorithm for computation of two-point odd-time DHT and odd-frequency DHT.

Figure 2. The data flow graph of the algorithm for the 3-point odd-time DHT.

Figure 3. The data flow graph of the algorithm for the 3-point odd-frequency DHT.

Figure 4. The data flow graph of the algorithm for implementation of 4-point odd-time DHT.

Figure 5. The data flow graph of the algorithm for implementation of 4-point odd-frequency DHT.

Figure 6. The data flow graph of the algorithm for the 5-point odd-time DHT.

Figure 7. The data flow graph of the algorithm for the 5-point odd-frequency DHT.

Figure 8. The data flow graph of the algorithm for the computation of the 6-point odd-time DHT.

Figure 9. The data flow graph of the algorithm for the computation of the 6-point odd-frequency DHT.

Figure 10. The data flow graph implementing the 7-point odd-time DHT.

Figure 11. The data flow graph implementing the 7-point odd-frequency DHT.

Figure 12. The data flow graph for the computing of the 8-point odd-time DHT.

Figure 13. The data flow graph of the algorithm for the 8-point odd-time DHT.

Table 1

The computational complexity of the matrix-vector product and the proposed fast algorithms for odd-time and odd-frequency DHTs.

N	Matrix-Vector Product		Proposed Odd-Time DHT Algorithms		Proposed Odd-Frequency DHT Algorithms
	Adds.	Mults.	Adds.	Mults.	Adds.
2	2	4	2 (0%)	2 (−50%)	2 (0%)
3	6	9	7 (+16%)	3 (−67%)	6 (0%)
4	8	4	6 (−25%)	2 (−50%)	6 (−25%)
5	20	25	23 (+15%)	6 (−76%)	23 (+15%)
6	30	36	28 (−7%)	8 (−78%)	24 (−20%)
7	42	49	46 (+10%)	10 (−80%)	46 (+10%)
8	48	48	28 (−42%)	8 (−83%)	28 (−42%)

Table 2

The number of operations for the existing odd-time DHT algorithms.

Algorithm	Year of Publication, Reference	N = 4		N = 8
Algorithm	Year of Publication, Reference	Mults.	Adds.	Mults.	Adds.
Prime factor	2003, [17]	2 (0%)	10 (−40%)	8 (0%)	28 (0%)
Radix-2	2011, [27]	–	–	10 (−20%)	28 (0%)
Radix-2 with decimation-in-time	2016, [31]	2 (0%)	6 (0%)	12 (−33%)	24 (+17%)
Split-radix	2020, [32]	2 (0%)	6 (0%)	12 (−33%)	24 (+17%)
Proposed	–	2	6	8	28

Table 3

The number of operations of the existing odd-frequency DHT algorithms.

Algorithm	Year of Publication, Reference	N = 4		N = 8
Algorithm	Year of Publication, Reference	Mults.	Adds.	Mults.	Adds.
Radix-2	2011, [28,29]	8 (−75%)	11 (−45%)	16 (−50%)	37 (−24%)
Prime factor, Wang	1992, [41]	2 (0%)	10 (−40%)	8 (0%)	28 (0%)
Prime factor, Hu, Chang, Ersoy	1992, [42]	2 (0%)	10 (−40%)	8 (0%)	28 (0%)
Prime factor, Bi, Zeng	2003, [17]	2 (0%)	10 (−40%)	6 (+33%)	26 (+8%)
Proposed	–	2	6	8	28

Table 4

The computational complexity of the proposed algorithms and the direct matrix-vector product in the Big O notation.

N	Proposed Algorithms		Matrix-Vector Product
	Adds.	Mults.	Adds.	Mults.
2, 4, 8	$N^{2} / 2$	$N^{2} / 2$	$N (N - 1)$	$N^{2}$
3, 5, 7	$(N + 2) (N - 1)$	${(N - 1)}^{2} / 2 + 2$
6	$(N + 2) (N - 1)$	$N + 2$

References

1. Jones, K. The regularized fast Hartley transform. Low-Complexity Parallel Computation of the FHT in One and Multiple Dimensions; 2nd ed. Springer: New York, NY, USA, 2021.

2. Patra, N.; Nayak, S.S. Discrete Hartley transform and its applications—A review. J. Integr. Sci. Technol.; 2022; 10, pp. 173-179.

3. Moraga, C. Generalized discrete Hartley transforms. Proceedings of the 39th International Symposium on Multiple-Valued Logic; Naha, Japan, 21–23 May 2009.

4. Vimal Kumar, C.; Raghavendra, D.; Eshwarappa, M.N. Design and implementation of VLSI DHT algorithm for image compression. Int. J. Eng. Trends Technol.; 2015; 23, pp. 218-223. [DOI: https://dx.doi.org/10.14445/22315381/IJETT-V23P241]

5. de Oliveira Nascimento, F.A. Hartley transform signal compression and fast power quality measurements for smart grid application. IEEE Trans. Power Deliv.; 2023; 99, pp. 1-11. [DOI: https://dx.doi.org/10.1109/TPWRD.2023.3302188]

6. Anoh, K.; Tanriover, C.; Ribeiro, M.V.; Adebisi, B.; See, C.H. On the fast DHT precoding of OFDM signals over frequency-selective fading channels for wireless applications. Electronics; 2022; 11, 3099. [DOI: https://dx.doi.org/10.3390/electronics11193099]

7. Budiman, G.; Suksmono, A.B.; Danudirdjo, D.; Pawellang, S. QIM-based audio watermarking with combined techniques of SWT-DST-QR-CPT using SS-based synchronization. Proceedings of the 6th International Conference on Information and Communication Technology (ICoICT); Bandung, Indonesia, 3–4 May 2018.

8. Lipinski, P.; Puchala, D. Digital image watermarking using fast parametric transforms. Bull. Pol. Acad. Sci. Tech. Sci.; 2019; 67, pp. 463-477. [DOI: https://dx.doi.org/10.24425/bpasts.2019.129646]

9. Kasban, H. A spiral-based image watermarking scheme using Karhunen–Loeve and discrete Hartley transforms. Multidimens. Syst. Signal Process.; 2017; 28, pp. 573-595. [DOI: https://dx.doi.org/10.1007/s11045-015-0361-4]

10. Zhang, X.; Su, Q. A spatial domain-based colour image blind watermarking scheme integrating multilevel discrete Hartley transform. Int. J. Intell. Syst.; 2021; 36, pp. 4321-4345. [DOI: https://dx.doi.org/10.1002/int.22461]

11. Voronenko, Y.; Puschel, M. Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms for Real DFTs. IEEE Trans. Signal Process.; 2009; 57, pp. 205-222. [DOI: https://dx.doi.org/10.1109/TSP.2008.2006152]

12. Coutinho, V.A.; Cintra, R.J.; Bayer, F.M. Low-complexity three-dimensional discrete Hartley transform approximations for medical image compression. Comput. Biol. Med.; 2021; 139, 105018. [DOI: https://dx.doi.org/10.1016/j.compbiomed.2021.105018]

13. Bozinovic, N.; Konrad, J. Scan order and quantization for 3D-DCT coding. Proc. SPIE Vis. Commun. Image Process.; 2003; 5150, 1205.

14. Rao, K.R.; Yip, P. The Transform and Data Compression Handbook; 1st ed. CRC Press LLC: Boca Raton, FL, USA, 2001.

15. Rao, K.R.; Yip, P. Discrete Cosine Transform: Algorithms, Advantages, Applications; 2nd ed. Academic Press: Cambridge, UK, 2014.

16. Prots’ko, I. Algorithm of efficient computation of generalised discrete Hartley transform based on cyclic convolutions. IET Signal Process.; 2014; 8, pp. 301-308. [DOI: https://dx.doi.org/10.1049/iet-spr.2013.0204]

17. Bi, G.; Zeng, Y. Transforms and Fast Algorithms for Signal Analysis and Representations; 1st ed. Birkhäuser: Boston, FL, USA, 2004.

18. Kober, V. Fast recursive computation of sliding DHT with arbitrary step. Sensors; 2020; 20, 5556. [DOI: https://dx.doi.org/10.3390/s20195556]

19. Jiang, L.; Shu, H.; Wu, J.; Wang, L.; Senhadji, L. A novel split-radix fast algorithm for 2-D discrete Hartley transform. IEEE Trans. Circuits Syst. I Regul. Pap.; 2010; 57, pp. 911-924. [DOI: https://dx.doi.org/10.1109/TCSI.2009.2028639]

20. Wu, J.; Shu, H.; Senhadji, L.; Luo, L.M. Radix-3x3 algorithm for the 2-D discrete Hartley transform. IEEE Trans. Circuits Syst. Part 2 Analog Digit. Signal Process.; 2008; 55, pp. 566-570.

21. Grigoryan, A.M. Novel algorithm for computing the 1-D discrete Hartley transform. IEEE Signal Process. Lett.; 2004; 11, pp. 156-159. [DOI: https://dx.doi.org/10.1109/LSP.2003.819876]

22. Hamood, M. New efficient algorithm for the discrete Hartley transform. IOP Conf. Ser. Mater. Sci. Eng.; 2020; 978, 012013. [DOI: https://dx.doi.org/10.1088/1757-899X/978/1/012013]

23. Chiper, D.F. A novel VLSI DHT algorithm for a highly modular and parallel architecture. IEEE Trans. Circuits Syst. II Express Briefs; 2013; 60, pp. 282-286. [DOI: https://dx.doi.org/10.1109/TCSII.2013.2251974]

24. Pyrgas, L.; Kitsos, P.; Skodras, A.N. An FPGA design for the two-band fast discrete Hartley transform. Proceedings of the IEEE International Symposium on Signal Processing and Information Technology (ISSPIT); Limassol, Cyprus, 12–14 December 2016.

25. Yang, X.; Megson, G.M.; Xing, Y.; Evans, D.J. A novel radix-3/9 algorithm for type-III generalized discrete Hartley transform. J. Circuits Syst. Comput.; 2006; 15, pp. 301-312. [DOI: https://dx.doi.org/10.1142/S0218126606003064]

26. Shu, H.; Wang, Y.; Senhadji, L.; Luo, L. Direct computation of type-II discrete Hartley transform. IEEE Signal Process. Lett.; 2007; 14, pp. 329-332. [DOI: https://dx.doi.org/10.1109/LSP.2006.888362]

27. Chiper, D.F. Fast radix-2 algorithm for the discrete Hartley transform of type II. IEEE Signal Process. Lett.; 2011; 18, pp. 687-689. [DOI: https://dx.doi.org/10.1109/LSP.2011.2170166]

28. Hua, X.; Liu, J. A novel fast algorithm for discrete Hartley transform of type-III base on the split-radix and first-order moments. Proceedings of the SPIE Eighth International Symposium on Multispectral Image Processing and Pattern Recognition; Wuhan, China, 26–27 October 2013.

29. Chiper, D.F. Radix-2 fast algorithm for computing discrete Hartley transform of type III. IEEE Trans. Circuits Syst. II Express Briefs; 2012; 59, pp. 297-301. [DOI: https://dx.doi.org/10.1109/TCSII.2012.2190863]

30. Chiper, D.F. An improved algorithm for the VLSI implementation of type II generalized DHT that allows an efficient incorporation of obfuscation technique. Proceedings of the 45th International Conference on Telecommunications and Signal Processing (TSP); Prague, Czech Republic, 13–15 July 2022.

31. Hamood, M.T. Fast algorithm for computing the discrete Hartley transform of type-II. Indones. J. Electr. Eng. Inform.; 2016; 4, pp. 120-125. [DOI: https://dx.doi.org/10.11591/ijeei.v4i2.220]

32. Hamood, M.T. Direct split-radix algorithm for fast computation of type-II discrete Hartley transform. Telecommun. Comput. Electron. Control; 2020; 18, pp. 3067-3072. [DOI: https://dx.doi.org/10.12928/telkomnika.v18i6.16100]

33. Huang, Y.-M.; Wu, J.-L. Polynomial transform based algorithms for computing two-dimensional generalized DFT, generalized DHT, and skew circular convolution. Signal Process.; 2000; 80, pp. 2255-2260. [DOI: https://dx.doi.org/10.1016/S0165-1684(00)00110-9]

34. Cariow, A. Strategies for the synthesis of fast algorithms for the computation of the matrix-vector product. J. Signal Process. Theory Appl.; 2014; 3, pp. 1-19. [DOI: https://dx.doi.org/10.7726/jspta.2014.1001]

35. Cariow, A.; Papliński, J. Algorithmic structures for realizing short-length circular convolutions with reduced complexity. Electronics; 2021; 10, 2800. [DOI: https://dx.doi.org/10.3390/electronics10222800]

36. Polyakova, M.; Witenberg, A.; Cariow, A. The design of fast type-V discrete cosine transform algorithms for short-length input sequences. Electronics; 2024; 13, 4165. [DOI: https://dx.doi.org/10.3390/electronics13214165]

37. Polyakova, M.; Cariow, A. Fast Type-II Hartley Transform Algorithms for Short-Length Input Sequences. Appl. Sci.; 2024; 14, 10719. [DOI: https://dx.doi.org/10.3390/app142210719]

38. Perera, S.M. Signal flow graph approach to efficient and forward stable DST algorithms. Linear Algebra Its Appl.; 2018; 542, pp. 360-390. [DOI: https://dx.doi.org/10.1016/j.laa.2017.05.050]

39. Perera, S.M.; Lingsch, L. Sparse matrix-based low-complexity, recursive, radix-2 algorithms for discrete sine transforms. IEEE Access; 2021; 9, pp. 141181-141198. [DOI: https://dx.doi.org/10.1109/ACCESS.2021.3120051]

40. Paraskevas, I.; Barbarosou, M.; Chilton, E. Hartley transform and the use of the whitened Hartley spectrum as a tool for phase spectral processing. J. Eng.; 2015; 2015, pp. 95-101. [DOI: https://dx.doi.org/10.1049/joe.2014.0350]

41. Wang, Z. A prime factor fast W transform algorithm. IEEE Trans. Signal Process.; 1992; 40, pp. 2361-2368. [DOI: https://dx.doi.org/10.1109/78.157241] [PubMed: https://www.ncbi.nlm.nih.gov/pubmed/18425179]

42. Hu, N.C.; Chang, H.I.; Ersoy, O.K. Generalized discrete Hartley transforms. IEEE Trans. Signal Process.; 1992; 40, pp. 2931-2940.

© 2025 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.

Fast Algorithms for Short-Length Odd-Time and Odd-Frequency Discrete Hartley Transforms

Content area

Abstract

Full text

1. Introduction

1.1. Related Papers

1.2. The Main Contributions of the Paper

2. Preliminary Background

3. Reduced Complexity Algorithms for Short-Length Odd-Time DHT and Odd-Frequency DHT

3.1. Algorithms for 2-Point Odd-Time DHT and Odd-Frequency DHT

3.2. Algorithms for 3-Point Odd-Time DHT and Odd-Frequency DHT

3.3. Algorithms for 4-Point Odd-Time DHT and Odd-Frequency DHT

3.4. Algorithms for 5-Point Odd-Time DHT and Odd-Frequency DHT

3.5. Algorithms for 6-Point Odd-Time DHT and Odd-Frequency DHT

3.6. Algorithms for 7-Point Odd-Time DHT and Odd-Frequency DHT

3.7. Algorithms for 8-Point Odd-Time DHT and Odd-Frequency DHT

4. Results

5. Discussion of Computational Complexity

6. Conclusions