# Fast Jacket-Haar Transform with Any Size

Authors: Guibo Liu; Dazu Huang; Dayong Luo; Wang Lei; Ying Guo; Moonho Lee
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Jacket-Haar transform has been recently generalized from Haar transform and Jacket transform, but, unfortunately, it is not available in a case where the lengthN is not a power of 2. In this paper, we have proposed an arbitrary-length Jacket-Haar transform which can be conveniently constructed from the 2-point generalized Haar transforms with the fast algorithm, and thus it can be constructed with any sizes. Moreover, it can be further extended with elegant structures, which result in the fast algorithms for decomposing. We show that this approach can be practically applied for the electrocardiogram (ECG) signal processing. Simulation results show that it is more efficient than the conventional fast Fourier transform (FFT) in signal processing.


---

## Body

## 1. Introduction

Hadamard transform, Haar transform, discrete Fourier transform, and their derivatives are discrete orthogonal transforms with extensive applications in signal and image processing [1–4]. Jacket transform, motivated by the center weighted Hadamard transform [5], is a special transform with its inverse transform matrix being determined by the element or block-wise inverse of an original matrix [6]. Jacket transform has been extensively applied in many fields, such as signal and data processing [1], digital wireless communications [7], cryptography [8], and encoding designs [9]. Meanwhile, several interesting matrices, such as Hadamard matrices and DFT matrices, belong to the Jacket transform matrix family. Besides all, lots of widely used matrices, such as unitary matrices and Hermitian matrices, have tightly relations with Jacket matrices.Recently, literatures relevant to discrete orthogonal matrices and their transforms mainly have involved explorations of other categories of orthogonal transform matrices and exploitations of their applications. In the later aspect, block Jacket transforms have been tentatively applied to quantum signal processing [10], Big-Data processing [11], emerging new-generation mobile communication, and so on. In addition, new orthogonal transforms, such as complex Hadamard transform [12–14], fractional Hadamard or Jacket transforms [15], parametric transforms [16–18], hybrid transforms [7], and the generalized orthogonal transforms [14], have been gradually proposed while enriching the orthogonal transform family. Particularly, with advancement of digital systems and widespread availability in the recent few decades, there exist some urgent demands for seeking a scheme to achieve compromise between the generalization efficiencies of Hadamard or Haar transforms and their the extended transforms to adaptively meet the practical implementation requirements. Subsequent research can be seen as an attempt.Haar matrix, which is useful for localized signal analysis [19], edge detection [20], OFDM, and filter design and electrocardiogram (ECG) analysis, has been generalized for Jacket-Haar matrix [21], whose entries are 0 and ±
2
k compared with entries of the original Haar matrix being 1, -
1, and 0. Although the 2
k-point Jacket-Haar matrices are successfully proposed in [21], there is still a problem on how to construct the arbitrary-length Jacket-Haar transform as the arbitrary-length Walsh-Jacket transform has already done with high efficiency [22]. Unfortunately, until this paper, the method to solve this problem is preliminary and not comprehensive except that some original results are shown [23]. Consequently, in this paper, we focus on the systematic construction of the generalized Jacket-Haar transforms of any lengths. Compared to the existing literatures, the contributions are listed as follows. Firstly, the multilevel structure of the arbitrary-length Jacket-Haar transform matrix can be derived with the recursive algorithm. Secondly, a novel approach for designing the fast generation of the Jacket-Haar transform matrices of the arbitrary length is derived in a successive fashion. Finally, the arbitrary length Jacket-Haar transforms can be generated and decomposed for extensions with the fast algorithms with several specified applications.The remaining of this paper is organized as follows. In Section2, the elegant structure of Jacket-Haar transform is investigated, followed by the generalized form of Jacket-Haar transform of size 2. In Section 3, the (
2
M
+
1
)-point Jacket-Haar transform is extensively derived from the (
M
+
1
)-point Jacket-Haar transform. Together with the proposed algorithm for generating the (
2
M
)-point Jacket-Haar transform, an arbitrary Jacket-Haar transform can be derived in a similar fashion. After that, the fast algorithm and its applications in signal processing will be shown in Section 4. In Section 5, the fast Jacket-Haar transforms are designed on the basis of the Kronecker product of the traditional Jacket and Jacket-Haar transforms. Finally, conclusion is drawn in Section 6.


## 2. Jacket-Haar Transform

Walsh transform can be extended for the arbitrary-point Walsh-Jacket transform of an arbitrary length [22]. Similarly, it is theoretically feasible to extend the Haar transform for the design of the Haar transform of any size. In order to verify the correctness of this judgement, we show an elegant structure of the Jacket-Haar transform.Definition 1.
Jacket-Haar transform is a discrete transform and it must satisfy three constraints as follows.(1)
IfΨ
N and Γ
N denote the forward and inverse N-point Jacket-Haar transform matrices, respectively, then all entries of both matrices are equal to 0 or ±
2
p, where p is an arbitrary integer.
(2)
The number of zero crossing point of any row ofΨ
N is the same as the conventional Haar matrix. Namely, zero crossing point number of any row of Ψ
N is one except the first row, where zero crossing point does not exist.
(3)
Fast algorithm of the conventional Haar transform is preserved.According to the definition of Jacket-Haar transform, all the conventional Haar transform matrices can be seen as a special case of Jacket-Haar transform matrices since the above three constraints are all satisfied. Elements of the Haar transform matrices can only be chosen from1, -
1, or 0, and order of any Haar matrix must be a power of 2. However, Jacket-Haar transform relaxes these limits with elements equal to 0 or ±
2
p. For this reason, Jacket-Haar transform can still be efficiently implemented by bit-shifting without multiplication just like the conventional Haar transform. In addition, the Jacket-Haar transform is an extension of the Jacket transform since the constraint that Γ
N
(
m
,
n
)
=
Ψ
N
(
n
,
m
)
/
C where C is a constant is not required any longer.Before generating a Jacket-Haar transform of any size, the Jacket-Haar matrices of size2 are extensively derived, based on which the Jacket-Haar matrix of any size can be efficiently achieved.Theorem 2.
Any2-point Jacket-Haar transform matrices should conform to the following forms:(1)
Ψ
2
1
=
a
0
c
-
d
,
(2)
Ψ
2
2
=
0
b
c
-
d
,
(3)
Ψ
2
3
=
a
b
c
-
d
,where a, b, c, and d are equal to 0 or a power of 2 with a
d
=
b
c.Proof.
It is straightforward that the third constraint is always satisfied for the2-point Jacket-Haar transform. Besides, the 2-point Jacket-Haar matrix Ψ
2 can be generally denoted as follows:(4)
Ψ
2
=
a
1
b
1
c
1
-
d
1
,and its inverse is(5)
Γ
2
=
1
a
1
d
1
+
b
1
c
1
d
1
b
1
c
1
-
a
1
.According to the first constraint, there exists(6)
a
1
d
1
+
b
1
c
1
=
±
2
p
.Meanwhile owing to the second constraint, we can obtain(7)
a
1
≥
0
,
b
1
≥
0
,
c
1
d
1
>
0
.So there exist three cases as follows. Firstly, if b
1
=
0, then it is easy to get that a
1
>
0 holds. So the 2-point Jacket-Haar matrix possesses the form of (1). Secondly, if a
1
=
0, then similar to case 1, the 2-point Jacket-Haar matrix has the form of (2). Thirdly, if a
1
b
1
>
0, according to (6), we can obtain (
a
1
d
1
)
(
b
1
c
1
)
>
0. In the first case, if a
1
d
1
=
2
m and b
1
c
1
=
2
n with a
1
d
1
=
k
(
b
1
c
1
), then a
1
d
1
+
b
1
c
1
=
(
1
+
k
)
2
n. Since (6) holds, k must be equal to 1. Namely, a
1
d
1
=
b
1
c
1. In the second case, we can get the same result. So, the 2-point Jacket-Haar transform conforms to (3). This completes the proof of this theorem.


## 3. Universal Jacket-Haar Transform Matrices

General forms of the 2-point Jacket-Haar transform matrices have been derived in the previous section. In this section, two algorithms are proposed to construct Jacket-Haar transform matrices of any large sizes.Theorem 3.
If the sizeN
=
2
M
+
1 of the matrix is an odd number, then one can use generation algorithm presented below to derive the N-point Jacket-Haar transform matrix from both an (
M
+
1
)-point Jacket-Haar transform matrix and an M-point identity matrix. Let Ψ
M
+
1 be an (
M
+
1
)-point Jacket-Haar transform matrix with inverse Γ
M
+
1. The n
t
h, n
∈
{
1,2
,
…
,
M
+
1
} column of Ψ
M
+
1 and the n
t
h row of Γ
M
+
1 are described by v
n and u
n, respectively. Namely, one has(8)
Ψ
M
+
1
=
v
1
,
v
2
,
…
,
v
M
+
1
,
Γ
M
+
1
=
u
1
T
,
u
2
T
,
…
,
u
M
+
1
T
T
.Suppose Ψ
2,1
,
Ψ
2,2
,
…
,
Ψ
2
,
M are the 2-point Jacket-Haar transform matrices with the respective inverse matrices Γ
2,1
,
Γ
2,2
,
…
,
Γ
2
,
n. Let v
1
,
k and v
2
,
k denote the first and second row of Ψ
2
,
k, respectively. Meanwhile, u
1
,
k and u
2
,
k are the first and second column of Γ
2
,
k, respectively. Then one has(9)
Ψ
2
,
k
=
v
1
,
k
v
2
,
k
,
Γ
2
,
k
=
u
1
,
k
u
2
,
k
,where v
1
,
k
u
1
,
k
=
v
2
,
k
u
2
,
k
=
1 and v
1
,
k
u
2
,
k
=
v
2
,
k
u
1
,
k
=
0, ∀
k
∈
{
1
,
2
,
…
,
M
}. Let e
n denote the n
t
h column of the M-point identity matrix; that is,(10)
e
n
n
=
1
,
e
n
m
=
0
,
i
f
m
≠
n
,where n
,
m
∈
{
1
,
2
,
…
,
M
}. Then the (
2
M
+
1
)-point Jacket-Haar transform matrix can be derived as(11)
Ψ
2
M
+
1
=
v
1
⊗
v
1,1
⋯
v
M
⊗
v
1
,
M
v
M
+
1
e
1
⊗
v
2,1
⋯
e
M
⊗
v
2
,
M
0
,with the inverse (
2
M
+
1
)-point Jacket-Haar transform matrix(12)
Γ
2
M
+
1
=
u
1
T
⊗
u
1,1
T
⋯
u
M
T
⊗
u
1
,
M
T
u
M
+
1
T
e
1
⊗
u
2,1
T
⋯
e
M
⊗
u
2
,
M
T
0
T
.Proof.
The product ofΨ
2
M
+
1 and Γ
2
M
+
1 can be calculated as(13)
Ψ
2
M
+
1
Γ
2
M
+
1
=
A
11
A
12
A
21
A
22
.According to (20), we have A
11, A
12, A
21, and A
22 that can be, respectively, calculated as(14)
A
11
=
∑
k
=
1
M
v
k
⊗
v
1
,
k
u
k
⊗
u
1
,
k
+
v
M
+
1
u
M
+
1
=
I
M
+
1
,
(15)
A
12
=
∑
k
=
1
M
v
k
⊗
v
1
,
k
e
k
T
⊗
u
2
,
k
=
0
,
(16)
A
21
=
∑
k
=
1
M
e
k
⊗
v
2
,
k
u
k
⊗
u
1
,
k
=
0
,
(17)
A
22
=
∑
k
=
1
M
e
k
⊗
v
2
,
k
e
k
T
⊗
u
2
,
k
=
I
M
.Hence, we have Ψ
2
M
+
1
Γ
2
M
+
1
=
I
2
M
+
1. Furthermore, it is easy to find that the first constraint and the second constraint are both satisfied. In fact, the third constraint can be easily derived. This completes the proof of this theorem.According to Theorem3, the (
2
M
+
1
)-point Jacket-Haar transform matrix with matrix size being a power function of 2 or not can be conveniently generated.Based on the above-mentioned construction, any odd integer order Jacket-Haar transform matrix can be elegantly derived, while at the same time, another construction method will be similarly proposed to construct Jacket-Haar transform matrix with the size being even numbers.Theorem 4.
If the size of the matrixN
=
2
M is even, then one can use the generating algorithm presented below to derive the N-point Jacket-Haar transform matrix from both the M-point Jacket-Haar matrix and the M-point identity matrix. The (
2
M
)-point Jacket-Haar matrix can be calculated as(18)
Ψ
2
M
=
v
^
1
⊗
v
11
⋯
v
^
M
⊗
v
1
M
e
1
⊗
v
21
⋯
e
M
⊗
v
2
M
,and its inverse can be computed as(19)
Γ
2
M
=
u
^
1
⊗
u
11
⋯
u
^
M
⊗
u
1
M
e
1
⊗
u
21
⋯
e
M
⊗
u
2
M
,where Ψ
M is the M-point Jacket-Haar matrix and Γ
M is its inverse matrix. The n
t
h, n
∈
{
1,2
,
…
,
M
}, column of Ψ
M and the n
t
h row of Γ
M are denoted by v
^
n and u
^
n, respectively. Then one has Ψ
M
=
(
v
^
1
,
…
,
v
^
M
) and Γ
M
=
(
u
^
1
,
…
,
u
^
M
) such that Ψ
M
Γ
M
=
I
M. Similarly, let v
1
,
k and v
2
,
k denote the first and second row of Ψ
2
,
k, respectively. Let u
1
,
k and u
2
,
k denote the first and second column of Γ
2
,
k, respectively. Then, one has(20)
Ψ
2
,
k
=
v
1
,
k
v
2
,
k
,
Γ
2
,
k
=
u
1
,
k
u
2
,
k
,where v
1
,
k
u
1
,
k
=
v
2
,
k
u
2
,
k
=
1 and v
1
,
k
u
2
,
k
=
v
2
,
k
u
1
,
k
=
0, k
∈
{
1
,
2
,
…
,
M
}. Moreover, the notation e
n denotes the n
t
h column of the M-point identity matrix with the following constraints:(21)
e
n
n
=
1
,
e
n
m
=
0
,
i
f
m
≠
n
,where n
,
m
∈
{
1
,
2
,
…
,
M
}.Proof.
Since the proof is similar to that of Theorem3, it is omitted here.For the further illustration and clarity, we give an example in what follows. Suppose that a 5-point Jacket-Haar matrix is(22)
Ψ
5
=
4
8
1
2
2
8
16
2
4
-
4
8
16
-
2
-
4
0
2
-
4
0
0
0
0
0
2
-
4
0
.Meanwhile, let Ψ
2,1
=
1
1
1
-
1, Ψ
2,2
=
1
2
2
-
4, Ψ
2,3
=
1
2
-
2
4, Ψ
2,4
=
1
0
2
-
4, and Ψ
2,5
=
0
1
4
-
1, respectively. Then, we obtain a 10-point Jacket-Haar matrix(23)
Ψ
10
=
1
1
1
2
1
2
1
0
0
1
1
1
1
2
1
2
1
0
0
-
1
1
1
1
2
-
1
-
2
-
1
0
0
0
1
1
-
1
-
2
0
0
0
0
0
0
0
0
0
0
1
2
-
1
0
0
0
1
-
1
0
0
0
0
0
0
0
0
0
0
2
-
4
0
0
0
0
0
0
0
0
0
0
-
2
4
0
0
0
0
0
0
0
0
0
0
2
-
4
0
0
0
0
0
0
0
0
0
0
4
-
1with the inverse matrix given by(24)
Γ
10
=
diag
⁡
2
-
4
,
2
-
4
,
2
-
4
,
2
-
5
,
2
-
4
,
2
-
5
,
2
-
3
,
2
-
4
,
2
-
3
,
2
-
1
1
1
2
4
0
8
0
0
0
0
1
1
2
4
0
-
8
0
0
0
0
1
1
2
-
4
0
0
4
0
0
0
1
1
2
-
4
0
0
-
4
0
0
0
1
1
-
2
0
4
0
0
-
4
0
0
1
1
-
2
0
4
0
0
4
0
0
1
1
-
2
0
-
4
0
0
0
0
0
1
1
-
2
0
-
4
0
0
0
-
4
0
1
-
1
0
0
0
0
0
0
0
2
1
-
1
0
0
0
0
0
0
0
0
.In a word, based on Theorems3 and 4, we can derive the Jacket-Haar transform matrix of any sizes in the recursive and alternate way. When N
=
2
M
+
1 is odd, we can choose Theorem 3 to derive the N-point Jacket-Haar transform matrix from the (
M
+
1
)-point Jacket-Haar transform. While N
=
2
M is even, we can choose Theorem 4 to get the N-point Jacket-Haar transform matrix from the M-point Jacket-Haar transform. For example, when N
=
9, the value of M is 4 and then Theorem 3 is chosen. It means the 9-point Jacket-Haar matrix can be derived from the 5-point Jacket-Haar matrix. Next, the 5-point Jacket-Haar matrix can be gotten from the 3-point Jacket-Haar matrix with Theorem 3. In the end, the 3-point Jacket-Haar matrix can be constructed from the 2-point Jacket-Haar matrix by using Theorem 3. Therefore, the 9-point Jacket-Haar matrix can be ultimately obtained from the 2-point Jacket-Haar matrices. In Table 1 we generate the N-point Jacket-Haar matrices with size N
∈
{
3,4
,
…
,
20
}. In fact, Jacket-Haar transform matrix of any sizes ultimately originates from the 2-point Jacket-Haar transform matrices.Table 1
TheN-point Jacket-Haar transform matrices based on the M-point Jacket-Haar transform matrices listed in the first column and the N-point Jacket-Haar transform matrices in the second column using the methods in the third column.
N
M
Methods
3
2
Theorem I
4
2
Theorem II
5
3
Theorem I
6
3
Theorem II
7
4
Theorem I
8
4
Theorem II
9
5
Theorem I
10
5
Theorem II
11
6
Theorem I
12
6
Theorem II
13
7
Theorem I
14
7
Theorem II
15
8
Theorem I
16
8
Theorem II
17
9
Theorem I
18
9
Theorem II
19
10
Theorem I
20
10
Theorem IIBased on the2-point Jacket-Haar transform matrices, the Jacket-Haar transform matrices of any sizes can be conveniently and elegantly constructed alternately and recursively by applying Theorems 3 and 4. Consequently, certain available sparse Jacket-Haar transform matrices can be theoretically derived.Corollary 5.
There exists an arbitrary-length sparse Jacket-Haar transform matrix with a maximum of two nonzero elements in each of the rows. In addition, there exists an arbitrary-length Jacket-Haar transform matrix, and the transpose of its inverse matrix is also a Jacket-Haar transform matrix with the following constraints:(25)
Γ
N
n
,
m
>
0
,
i
f
Ψ
N
m
,
n
>
0
,
Γ
N
n
,
m
<
0
,
i
f
Ψ
N
m
,
n
<
0
,
Γ
N
n
,
m
=
0
,
i
f
Ψ
N
m
,
n
=
0
.Proof.
The inductive method will be used for proving this corollary. At first, it is obvious that all the 2-point Jacket-Haar transform matrices meet the prescribed request. At the next step, there exist two cases based on which theorem has adopted generating a relatively higher order adjacent Jacket-Haar transform matrix. For the first case, suppose thatΨ
M
+
1 is a sparse (
M
+
1
)-point Jacket-Haar transform matrix. For the two-point Jacket-Haar transform matrices Ψ
2,1
,
Ψ
2,2
,
…
,
Ψ
2
,
M in the form described in (1) or (2), the (
2
M
+
1
)-point Jacket-Haar transform matrix derived from (11) is a sparse matrix since each of the rows possesses a maximum of two nonzero elements. For the other case, if there exists a sparse M-point Jacket-Haar transform matrix Ψ
M with the given matrices Ψ
2,1
,
Ψ
2,2
,
…
,
Ψ
2
,
M, the 2
M-point Jacket-Haar transform matrix from (18) is also a sparse matrix. This completes the proof of one part of corollary. This kind of sparse Jacket-Haar transform matrices is interesting and available in practical applications that are provided with the priority of acceptable performances promised. For another part of the proof of this corollary, the inductive method will be similarly used. At the first step, it is easy to check that the transpose of two-point inverse matrix in the form of (5) is also a Jacket-Haar transform matrix, and that (25) is satisfied. At the next step, based on the selected theorems for the construction of a relatively adjacent Jacket-Haar matrix, there exist two cases. For the first case with an (
M
+
1
)-point Jacket-Haar transform matrix Ψ
M
+
1, the transpose of whose inverse matrix is also a Jacket-Haar transform matrix that satisfies the constraint in (25). For the 2-point Jacket-Haar transform matrices Ψ
2,1
,
Ψ
2,2
,
…
,
Ψ
2
,
M, it is obvious that Ψ
2
M
+
1 derived from (12) is a (
2
M
+
1
)-point Jacket-Haar transform matrix and the transpose of whose inverse matrix is also a Jacket-Haar transform matrix. Similarly, if Ψ
M is an M-point Jacket-Haar transform matrix, the transpose of whose inverse matrix is also a Jacket-Haar transform matrix. For the 2-point Jacket-Haar transforms Ψ
2,1
,
Ψ
2,2
,
…
,
Ψ
2
,
M in the form described in (3), it is straightforward that Ψ
2
M derived from (18) is a 2
M-point Jacket-Haar transform matrix and the transpose of whose inverse matrix is also a Jacket-Haar transform matrix. Therefore, the whole corollary holds and the proof is complete.It is interesting to note the Jacket-Haar transform referred to in the afore-derived corollary is similar to that of the Jacket transform. As we all know, ifJ
N is an N-point Jacket transform matrix, then J
N
-
1 is also an N-point Jacket transform matrix with the following constraints:(26)
J
N
-
1
n
,
m
>
0
,
if
J
N
m
,
n
>
0
;
J
N
-
1
n
,
m
<
0
,
if
J
N
m
,
n
<
0
;
J
N
-
1
n
,
m
=
0
,
if
J
N
m
,
n
=
0
.


## 4. Fast Jacket-Haar Transform

### 4.1. Fast Implementation Algorithms

Just like the conventional Haar transform, the Jacket-Haar transform of large sizes can be performed with fast algorithms. In order to give a more clear demonstration with simple comparison, fast algorithms of both conventional Haar transform and Jacket-Haar transform are presented simultaneously.In Figure1, we show the implementation structures of the conventional Haar transforms with sizes 2, 4, and 2
n, respectively. In Figure 2, the implementation structures of the 2-point, the 3-point and the 4-point Jacket-Haar transform are presented, from which the 3-point and the 4-point Jacket-Haar transforms can be decomposed into 2 and 3 butterflies, respectively. For N
>
4, we can decompose the N-point Jacket-Haar transform into combination of the 2-point Jacket-Haar transforms by using the methods described as in Figure 3. From Figures 1 to 3, it is obvious that the structures of the fast algorithms of the original Haar transform and the proposed Jacket-Haar transform are similar. For example, the whole implementation structure of a 9-point Jacket-Haar transform matrix shown as (27)
Ψ
9
=
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
-
1
1
1
1
1
-
1
-
1
-
1
-
1
0
1
1
-
1
-
1
0
0
0
0
0
0
0
0
0
1
1
-
1
-
1
0
1
-
1
0
0
0
0
0
0
0
0
0
1
-
1
0
0
0
0
0
0
0
0
0
1
-
1
0
0
0
0
0
0
0
0
0
1
-
1
0has been illustrated in Figure 4. It is shown that there exist 4 layers, with 4, 2, 1, and 1 butterflies being included in the adjacent layers from the left to the right. It needs 16 arithmetic addition operations without any multiplication.Figure 1
The implementations of the fast algorithms: (a) the 2-point Haar transform, (b) the 4-point Haar transform, and (c) the(
2
k
+
1
)-point Haar transform.
(a)
(b)
(c)Figure 2
The implementations of the fast algorithm: (a) the 2-point Jacket-Haar transform, (b) the 3-point Jacket-Haar transform, and (c) the 4-point Jacket-Haar transform.
(a)
(b)
(c)Figure 3
(a) The2
M-point Jacket-Haar transform by using the M-point Jacket-Haar transform. (b) The (
2
M
+
1
)-point Jacket-Haar transform by the (
M
+
1
)-point Jacket-Haar transform.
(a)
(b)Figure 4
The fast algorithm of the 9-point Jacket-Haar transform.Compared to the conventional Haar transform, if both categories transform matrices possess the same matrix size which is a power of2, they have the same implementation layers, numbers of butterflies, and arithmetic addition operations without any multiplication operations needed, but with different numbers of bit-shift operations. When the matrix size does not equal a power of 2, there do not exist the corresponding Haar transform matrices. For the proposed Jacket-Haar transform matrices, there are l
o
g
2
N
+
1 implementation layers and 2
(
N
-
1
) arithmetic addition operations with (
N
-
1
) butterflies included, but without any multiplication operations. The details are shown in Table 2.Table 2
Complexity analysis.
Transforms
Implementation layers
Butterflies
Complexity
Haar
n
,
N
=
2
n
(
N
-
1
)
2
(
N
-
1
)
Jacket-Haar
n, if N
=
2
n
l
o
g
2
N
+
1
,
if
N
≠
2
n
(
N
-
1
)
2
(
N
-
1
)


### 4.2. Generalized Jacket-Haar Transform

Definition 6.
For a given square matrixJ
m
=
[
J
i
j
]
m, if its inverse matrix can be simply obtained from its element-wise inverse, that is, J
m
-
1
=
1
/
C
[
1
/
J
j
i
]
m, for 1
≤
i
,
j
≤
m, where C is a nonzero constant, one calls matrix J
m a Jacket matrix; that is,(28)
J
m
=
j
1,1
j
1,2
⋯
j
1
,
m
j
2,1
j
2,2
⋯
j
2
,
m
⋮
⋮
⋱
⋮
j
m
,
1
j
m
,
1
⋯
j
m
,
m
,and its inverse matrix is(29)
J
m
-
1
=
1
C
1
j
1,1
1
j
1,2
⋯
1
j
1
,
m
1
j
2,1
1
j
2,2
⋯
1
j
2
,
m
⋮
⋮
⋱
⋮
1
j
m
,
1
1
j
m
,
1
⋯
1
j
m
,
m
T
,where T denotes the operation of matrix transpose.Definition 7.
SupposeJ
M is a Jacket matrix of order M and Ψ
N is a Jacket-Haar matrix of order N. If [
J
H
]
M
N
=
J
M
⊗
Ψ
N, one calls [
J
H
]
M
N a generalized Jacket-Haar matrix.
According to the above-mentioned definition, it is obvious that both Jacket matrix and Jacket-Haar matrix belong to generalized Jacket-Haar matrix family.Theorem 8.
Since both Jacket transform and Jacket-Haar transform can be designed with the fast algorithms, the generalized Jacket-Haar transform which is the Kronecker product of Jacket transform and Jacket-Haar transform can be composed or decomposed with the fast algorithms.Proof.
SupposeJ
M can be decomposed until J
p and J
q; then(30)
J
M
=
p
m
q
n
=
I
q
n
⊗
∏
i
=
0
m
-
1
I
p
m
-
i
⊗
J
p
⊗
I
p
i
-
1
∏
i
=
0
n
-
1
I
q
n
-
i
⊗
J
q
⊗
I
q
i
-
1
⊗
I
p
m
,where I
N is the N
×
N identity matrix. The detailed procedure can be seen in [6]. Then, by using the property of Kronecker product, [
J
H
]
M
N can be decomposed as(31)
J
H
M
N
=
J
p
m
q
n
I
p
m
q
n
⊗
I
N
Ψ
N
=
I
q
n
⊗
J
p
m
J
q
n
⊗
I
p
m
⊗
I
N
I
M
⊗
Ψ
Nwith(32)
J
p
m
=
∏
i
=
0
m
-
1
I
p
m
-
i
⊗
J
p
⊗
I
p
i
-
1
,
J
q
n
=
∏
i
=
0
n
-
1
I
q
n
-
i
⊗
J
q
⊗
I
q
i
-
1
.Due to the fact that Ψ
N can be decomposed into 2-point Jacket-Haar transforms, [
J
H
]
M
N can be decomposed or constructed with the fast algorithms. This completes the proof of this theorem.For example, ifJ
2
=
Ψ
2
=
1
1
1
-
1, we can construct the 3-point Jacket-Haar transform and 4-point Jacket transform as follows:(33)
Ψ
3
=
1
1
1
1
1
-
1
1
-
1
0
,
J
4
=
J
2
⊗
J
2
=
1
1
1
1
1
-
1
1
-
1
1
1
-
1
-
1
1
-
1
-
1
1
.Then we can construct a 12-point generalized Jacket-Haar transform(34)
1
1
1
1
1
1
1
1
1
1
1
1
1
1
-
1
1
1
-
1
1
1
-
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
-
1
-
1
1
1
-
1
-
1
-
1
1
1
1
-
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
-
1
-
1
1
1
-
1
1
1
-
1
-
1
-
1
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
1
1
1
1
-
1
-
1
-
1
1
-
1
-
1
1
1
1
-
1
1
-
1
0
-
1
1
0
-
1
1
0
1
-
1
0
.The fast algorithm is shown in Figure 5.Figure 5
The fast algorithm of the 12-point generalized Jacket-Haar transform.


## 4.1. Fast Implementation Algorithms

Just like the conventional Haar transform, the Jacket-Haar transform of large sizes can be performed with fast algorithms. In order to give a more clear demonstration with simple comparison, fast algorithms of both conventional Haar transform and Jacket-Haar transform are presented simultaneously.In Figure1, we show the implementation structures of the conventional Haar transforms with sizes 2, 4, and 2
n, respectively. In Figure 2, the implementation structures of the 2-point, the 3-point and the 4-point Jacket-Haar transform are presented, from which the 3-point and the 4-point Jacket-Haar transforms can be decomposed into 2 and 3 butterflies, respectively. For N
>
4, we can decompose the N-point Jacket-Haar transform into combination of the 2-point Jacket-Haar transforms by using the methods described as in Figure 3. From Figures 1 to 3, it is obvious that the structures of the fast algorithms of the original Haar transform and the proposed Jacket-Haar transform are similar. For example, the whole implementation structure of a 9-point Jacket-Haar transform matrix shown as (27)
Ψ
9
=
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
-
1
1
1
1
1
-
1
-
1
-
1
-
1
0
1
1
-
1
-
1
0
0
0
0
0
0
0
0
0
1
1
-
1
-
1
0
1
-
1
0
0
0
0
0
0
0
0
0
1
-
1
0
0
0
0
0
0
0
0
0
1
-
1
0
0
0
0
0
0
0
0
0
1
-
1
0has been illustrated in Figure 4. It is shown that there exist 4 layers, with 4, 2, 1, and 1 butterflies being included in the adjacent layers from the left to the right. It needs 16 arithmetic addition operations without any multiplication.Figure 1
The implementations of the fast algorithms: (a) the 2-point Haar transform, (b) the 4-point Haar transform, and (c) the(
2
k
+
1
)-point Haar transform.
(a)
(b)
(c)Figure 2
The implementations of the fast algorithm: (a) the 2-point Jacket-Haar transform, (b) the 3-point Jacket-Haar transform, and (c) the 4-point Jacket-Haar transform.
(a)
(b)
(c)Figure 3
(a) The2
M-point Jacket-Haar transform by using the M-point Jacket-Haar transform. (b) The (
2
M
+
1
)-point Jacket-Haar transform by the (
M
+
1
)-point Jacket-Haar transform.
(a)
(b)Figure 4
The fast algorithm of the 9-point Jacket-Haar transform.Compared to the conventional Haar transform, if both categories transform matrices possess the same matrix size which is a power of2, they have the same implementation layers, numbers of butterflies, and arithmetic addition operations without any multiplication operations needed, but with different numbers of bit-shift operations. When the matrix size does not equal a power of 2, there do not exist the corresponding Haar transform matrices. For the proposed Jacket-Haar transform matrices, there are l
o
g
2
N
+
1 implementation layers and 2
(
N
-
1
) arithmetic addition operations with (
N
-
1
) butterflies included, but without any multiplication operations. The details are shown in Table 2.Table 2
Complexity analysis.
Transforms
Implementation layers
Butterflies
Complexity
Haar
n
,
N
=
2
n
(
N
-
1
)
2
(
N
-
1
)
Jacket-Haar
n, if N
=
2
n
l
o
g
2
N
+
1
,
if
N
≠
2
n
(
N
-
1
)
2
(
N
-
1
)


## 4.2. Generalized Jacket-Haar Transform

Definition 6.
For a given square matrixJ
m
=
[
J
i
j
]
m, if its inverse matrix can be simply obtained from its element-wise inverse, that is, J
m
-
1
=
1
/
C
[
1
/
J
j
i
]
m, for 1
≤
i
,
j
≤
m, where C is a nonzero constant, one calls matrix J
m a Jacket matrix; that is,(28)
J
m
=
j
1,1
j
1,2
⋯
j
1
,
m
j
2,1
j
2,2
⋯
j
2
,
m
⋮
⋮
⋱
⋮
j
m
,
1
j
m
,
1
⋯
j
m
,
m
,and its inverse matrix is(29)
J
m
-
1
=
1
C
1
j
1,1
1
j
1,2
⋯
1
j
1
,
m
1
j
2,1
1
j
2,2
⋯
1
j
2
,
m
⋮
⋮
⋱
⋮
1
j
m
,
1
1
j
m
,
1
⋯
1
j
m
,
m
T
,where T denotes the operation of matrix transpose.Definition 7.
SupposeJ
M is a Jacket matrix of order M and Ψ
N is a Jacket-Haar matrix of order N. If [
J
H
]
M
N
=
J
M
⊗
Ψ
N, one calls [
J
H
]
M
N a generalized Jacket-Haar matrix.
According to the above-mentioned definition, it is obvious that both Jacket matrix and Jacket-Haar matrix belong to generalized Jacket-Haar matrix family.Theorem 8.
Since both Jacket transform and Jacket-Haar transform can be designed with the fast algorithms, the generalized Jacket-Haar transform which is the Kronecker product of Jacket transform and Jacket-Haar transform can be composed or decomposed with the fast algorithms.Proof.
SupposeJ
M can be decomposed until J
p and J
q; then(30)
J
M
=
p
m
q
n
=
I
q
n
⊗
∏
i
=
0
m
-
1
I
p
m
-
i
⊗
J
p
⊗
I
p
i
-
1
∏
i
=
0
n
-
1
I
q
n
-
i
⊗
J
q
⊗
I
q
i
-
1
⊗
I
p
m
,where I
N is the N
×
N identity matrix. The detailed procedure can be seen in [6]. Then, by using the property of Kronecker product, [
J
H
]
M
N can be decomposed as(31)
J
H
M
N
=
J
p
m
q
n
I
p
m
q
n
⊗
I
N
Ψ
N
=
I
q
n
⊗
J
p
m
J
q
n
⊗
I
p
m
⊗
I
N
I
M
⊗
Ψ
Nwith(32)
J
p
m
=
∏
i
=
0
m
-
1
I
p
m
-
i
⊗
J
p
⊗
I
p
i
-
1
,
J
q
n
=
∏
i
=
0
n
-
1
I
q
n
-
i
⊗
J
q
⊗
I
q
i
-
1
.Due to the fact that Ψ
N can be decomposed into 2-point Jacket-Haar transforms, [
J
H
]
M
N can be decomposed or constructed with the fast algorithms. This completes the proof of this theorem.For example, ifJ
2
=
Ψ
2
=
1
1
1
-
1, we can construct the 3-point Jacket-Haar transform and 4-point Jacket transform as follows:(33)
Ψ
3
=
1
1
1
1
1
-
1
1
-
1
0
,
J
4
=
J
2
⊗
J
2
=
1
1
1
1
1
-
1
1
-
1
1
1
-
1
-
1
1
-
1
-
1
1
.Then we can construct a 12-point generalized Jacket-Haar transform(34)
1
1
1
1
1
1
1
1
1
1
1
1
1
1
-
1
1
1
-
1
1
1
-
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
-
1
-
1
1
1
-
1
-
1
-
1
1
1
1
-
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
-
1
-
1
1
1
-
1
1
1
-
1
-
1
-
1
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
1
1
1
1
-
1
-
1
-
1
1
-
1
-
1
1
1
1
-
1
1
-
1
0
-
1
1
0
-
1
1
0
1
-
1
0
.The fast algorithm is shown in Figure 5.Figure 5
The fast algorithm of the 12-point generalized Jacket-Haar transform.


## 5. Applications in Signal Processing

The proposed arbitrary-point Jacket-Haar transform can also be theoretically applied in areas where the conventional Haar transforms have been gained, such as signal analysis, image processing, OFDM, and filter design. In this section, two representative Jacket-Haar transforms are applied to electrocardiogram (ECG) analysis compared to the discrete Fourier transform (DFT).There are approaches for comprehensive analysis with even and odd point transforms, respectively. The length of the ECG signal in Figure6 is 202, which is even and not a power of 2. It is not convenient to analyze this case by directly using the original Haar transform, but it can be efficiently analyzed by the proposed arbitrary-point Jacket-Haar transform. In Figure 7, we show the normalized mean square error (NMSE) of the reconstructed signal when using part of the coefficients of the 202-point generalized Haar transform(35)
N
M
S
E
=
x
s
-
x
2
x
2
y
=
W
N
x
,
x
s
=
U
N
y
s
,where x is the original signal; W
N and U
N are the forward and inverse Jacket-Haar transform matrices. The vector y
s preserves S coefficients of y and others are set to zero. In Figure 7, we also show the NMSE of the reconstructed signal when using the 202-point fast Fourier transform (FFT). The results in Figure 7 show that, with the Jacket-Haar transform, we can achieve less approximation error when using only S terms (S
<
202) to expand the ECG signal.Figure 6
A 202-length electrocardiogram (ECG) and the reconstructed signal.
(a)
Original signal and reconstructed signal with FFT
(b)
Original signal and reconstructed signal with Jacket-Haar transformFigure 7
The normalized mean square error (NMSE) when using part of the coefficients to reconstruct the ECG signal in the figure. Red line: using the 202-point Jacket-Haar transform; green line: using the FFT.As shown in Figures8 and 9, another simulation experiment is arranged. The length of the ECG in Figure 8 is 321, which is odd and not a power of 2. We show the NMSE of the reconstructed signal in Figure 9 when using part of the coefficients of the 321-point Jacket-Haar transform compared with the 321-point FFT. It is obvious that the Jacket-Haar transform is more efficient for analyzing the ECG signal than that of FFT. In the future, the proposed Jacket-Haar transform will be applied to the more practical applications with the extensive comparisons.Figure 8
A 321-length electrocardiogram (ECG) and the reconstructed signal.
(a)
Original signal and reconstructed signal with FFT
(b)
Original signal and reconstructed signal with Jacket-Haar transformFigure 9
The NMSE when using part of the coefficients to reconstruct the ECG signal in the figure. Red line: using the 321-point Jacket-Haar transform; green line: using the FFT.


## 6. Conclusion

We have investigated the fast construction of the Jacket-Haar transform of the arbitrary length, which overcomes of problem of the traditional constraint that the number of the points is the power of 2. With the proposed fast generation algorithms, the arbitrary length Jacket-Haar transform can be derived in a successive fashion. Moreover, we show the possible implementations of the fast algorithms and applications in signal processing. On the basis of the structures of the traditional Jacket transform and the Jacket-Haar transform with any size, the fast algorithms of Jacket-Haar transform are derived for the arbitrary length. Compared to the traditional FFT and its extensions, the proposed Jacket-Haar transform is more efficient in signal reconstruction. However, more properties of the Jacket-Haar transform and its practical applications may be further investigated in the future work.



---

*Source: 628642-2015-10-28.xml*