Kalpana Kalpana (Editor)

Pseudo Hadamard transform

Updated on
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit
Covid-19

The pseudo-Hadamard transform is a reversible transformation of a bit string that provides cryptographic diffusion. See Hadamard transform.

The bit string must be of even length, so it can be split into two bit strings a and b of equal lengths, each of n bits. To compute the transform, a' and b', from these we use the equations:

a = a + b ( mod 2 n ) b = a + 2 b ( mod 2 n )

To reverse this, clearly:

b = b a ( mod 2 n ) a = 2 a b ( mod 2 n )

Generalization

The above equations can be expressed in matrix algebra, by considering a and b as two elements of a vector, and the transform itself as multiplication by a matrix of the form:

H 1 = [ 2 1 1 1 ]

The inverse can then be derived by inverting the matrix.

However, the matrix can be generalised to higher dimensions, allowing vectors of any power-of-two size to be transformed, using the following recursive rule:

H n = [ 2 × H n 1 H n 1 H n 1 H n 1 ]

For example:

H 2 = [ 4 2 2 1 2 2 1 1 2 1 2 1 1 1 1 1 ]

References

Pseudo-Hadamard transform Wikipedia


Similar Topics
Funny Farm (film)
Deuce McAllister
Irungbam Surkumar Singh
Topics
 
B
i
Link
H2
L