Hadamard transform

Hadamard transform, also referred to as Walsh - Hadamard transform, Hadamard Rademacher - Walsh transform, Walsh transform, and the Walsh - Fourier transform, a discrete transform of the region of the Fourier analysis. She is an orthogonal - symmetric self inverse and linear transformation and related in structure with the discrete Fourier transform ( DFT). The Hadamard transform maps a set of real or complex input values ​​in an image area of superimposed Walsh functions, the so-called Walsh spectrum from. The transformation is named after the mathematicians Jacques Hadamard, Joseph L. Walsh and Hans Rademacher.

The applications of the Hadamard transform are in the field of digital signal processing and data compression such as JPEG XR and H.264/MPEG-4 AVC.

Definition

Hadamard transformation is constituted by a Hadamard matrix scaled by a normalization factor, which transforms an input sequence of length by means of a matrix-vector multiplication in a starting sequence.

The Hadamard transform can be variously defined, recursively, among other things, being understood by a Hadamard transform to the identity and set becomes:

With the normalization factor.

Analogous to the discrete Fourier transform (DFT ) and the optimized fast Fourier transform (FFT), a fast Hadamard transform, which reduces the number of operations with exists.