Cryptography Reference
In-Depth Information
where
I
k
is the unit matrix of order
k
.
Developing recursively, we obtain:
n
I
2
i−
1
⊗
I
N/
2
i
H
N
=
H
2
⊗
i
=1
The fast Hadamard transform is in fact the use of this factorization to calculate
R
.
Example 8.6
Let us calculate the Hadamard transform of vector
R
=[0
.
2; 0
.
5;
−
0
.
7; 1
.
3; 0
.
1;
−
1
.
1; 0
.
8;
−
0
.
3]
We have
R
=
RH
8
with
⎡
⎤
11111111
1
⎣
⎦
−
11
−
11
−
11
−
1
11
−
1
−
11 1
−
1
−
1
1
−
1
−
11 1
−
1
−
11
H
8
=
1111
−
1
−
1
−
1
−
1
1
−
11
−
1
−
11
−
11
11
−
1
−
1
−
1
−
11 1
1
−
1
−
11
−
11 1
−
1
The direct calculation gives:
R
=[0
.
8; 0
.
0;
−
1
.
4; 1
.
8; 1
.
8;
−
4
.
6; 1
.
6; 1
.
6]
Now, according to the above,
H
8
=
G
1
G
2
G
3
where
G
i
=
I
i
⊗
H
2
⊗
I
8
/
2
i
,
we have:
⎡
⎣
⎤
⎦
10001000
01000100
00100010
00010001
1000
⎡
⎣
⎤
⎦
1000
0100
0010
0001
11
1
G
1
=[1]
⊗
⊗
=
1000
0100 0
−
−
1
10 0
0010 0 0
−
10
0001 0 0 0
−
−
1
