Walsh matrix

From Wikipedia, the free encyclopedia

In mathematics, a Walsh matrix is a square matrix, with dimensions a power of 2, the entries of which are +1 or -1. The Walsh matrix can be obtained from a Hadamard matrix (which is defined by the recursive formula below) of the same dimension by rearranging the rows so that the number of sign-changes is in increasing order. This is called sequency ordering. Since a Walsh matrix can be obtained from Hadamard matrix solely by exchanging rows it retains the property that the dot product of any two distinct rows (or columns) is zero. Each row of a Walsh Matrix corresponds to a Walsh function.

The Walsh matrix (and Walsh functions) are used in computing the Walsh transform and have applications in the efficient implementation of certain signal processing operations.

[edit] Formula

The Hadamard matrices of dimension 2k for k \in N are given by the recursive formula

H(1) = \begin{bmatrix} 1 \end{bmatrix},
H(2) = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix},
H(4) = \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1\\ 1 & -1 & -1 & 1\\ \end{bmatrix},


and in general

H(2^k) = \begin{bmatrix} H(2^{k-1}) & H(2^{k-1})\\ H(2^{k-1}) & -H(2^{k-1})\end{bmatrix} = H(2)\otimes H(2^{k-1}),

for 2 \le k \in N, where \otimes denotes the Kronecker product.

[edit] Sequency Ordering

The ordering of the rows of the Walsh matrix can be derived from the ordering of the Hadamard matrix by first applying the bit-reversal permutation and then the Gray code permutation.

[edit] References

Yuen, C. 1972. Remarks on the Ordering of Walsh Functions. IEEE Transactions on Computers. C-21: 1452.

Retrieved from "http://en.wikipedia.org../../../w/a/l/Walsh_matrix.html"