Graphics Reference
In-Depth Information
2. Calculate the odd part using a
N
/2
N
/2 subset matrix obtained from the odd
columns of the inverse transform matrix (
6.15
shows an example).
3. Add/subtract the odd and even parts to generate
N
-point output (
6.16
shows an
example).
Even-odd decomposition of the inverse 4-point transform is given by (
6.14
-
6.16
):
Even part:
z
0
z
1
D
d
16
d
16
d
16
d
16
x
0
x
2
(6.13)
The even part can be further simplified as:
t
0
D
d
16
x
0
t
1
D
d
16
x
2
z
0
z
1
D
t
0
C
t
1
t
0
t
1
(6.14)
Odd part:
z
2
z
3
D
d
24
x
1
x
3
d
8
(6.15)
d
8
d
24
Add/sub:
2
4
3
5
2
4
3
5
y
0
y
1
y
2
y
3
z
0
z
3
z
1
z
2
z
1
C
z
2
z
0
C
z
3
D
(6.16)
The direct 1D 4-point transform using (
6.12
) would require 16 multiplications
and 12 additions. The 2D transform will require 128 multiplications and 96
additions. Even-Odd decomposition on the other hand requires a total of six
multiplications and eight additions for 1D transform using (
6.14
-
6.16
). The 2D
transform using Even-Odd decomposition will require a total of 48 multiplications
and 64 additions which is 62.5 % savings in number of multiplications and 33.3 %
savings in number of additions when compared to direct matrix multiplication.
The 8-point 1D inverse transform is defined by the following equation:
y
D
D
8
x
(6.17)
where
x
D
[
x
0
,
x
1
, :::,
x
7
]
T
is input and
y
D
[
y
0
,
y
1
, :::,
y
7
]
T
is output, and
D
8
is
given by:
