Walsh matrix

From Wikipedia, the free encyclopedia

In mathematics, a Walsh matrix is a specific square matrix, with dimensions a power of 2, the entries of which are +1 or -1, and the property that the dot product of any two distinct rows (or columns) is zero. The Walsh matrix was proposed by Joseph Leonard Walsh in 1923.[1] Each row of a Walsh matrix corresponds to a Walsh function.

The natural ordered Hadamard matrix is defined by the recursive formula below, and the sequency ordered Hadamard matrix is formed by rearranging the rows so that the number of sign-changes in a row is in increasing order.[1] Confusingly, different sources refer to either matrix as the Walsh matrix.

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 sequency 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.[2]

e.g. W(4) = \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & 1 & -1 & -1\\ 1 & -1 & -1 & 1\\ 1 & -1 & 1 & -1\\ \end{bmatrix}

where the successive rows have 0, 1, 2, and 3 sign changes.

[edit] References

  1. ^ a b Adaptive Prediction and Predictive Control, by P. P. Kanjilal, p 210, 1995, IET, ISBN 0863411932
  2. ^ Yuen, C. 1972. Remarks on the Ordering of Walsh Functions. IEEE Transactions on Computers. C-21: 1452.
Languages