Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Walsh matrix
Orthogonal matrix with several useful properties

In mathematics, a Walsh matrix is a specific square matrix of dimensions 2n, where n is some particular natural number. The entries of the matrix are either +1 or −1 and its rows as well as columns are orthogonal. The Walsh matrix was proposed by Joseph L. Walsh in 1923. Each row of a Walsh matrix corresponds to a Walsh function.

The Walsh matrices are a special case of Hadamard matrices where the rows are rearranged so that the number of sign changes in a row is in increasing order. In short, a Hadamard matrix is defined by the recursive formula below and is naturally ordered, whereas a Walsh matrix is sequency-ordered. 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.

Related Image Collections Add Image
Profiles
1 Image
We don't have any YouTube videos related to Walsh matrix yet.
We don't have any PDF documents related to Walsh matrix yet.
We don't have any Books related to Walsh matrix yet.
We don't have any archived web articles related to Walsh matrix yet.

Formula

The Hadamard matrices of dimension 2 k {\displaystyle 2^{k}} for k ∈ N {\displaystyle k\in \mathbb {N} } are given by the recursive formula (the lowest order of Hadamard matrix is 2):

H ( 2 1 ) = [ 1 1 1 − 1 ] , H ( 2 2 ) = [ 1 1 1 1 1 − 1 1 − 1 1 1 − 1 − 1 1 − 1 − 1 1 ] , {\displaystyle {\begin{aligned}H\left(2^{1}\right)&={\begin{bmatrix}1&1\\1&-1\end{bmatrix}},\\H\left(2^{2}\right)&={\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\\\end{bmatrix}},\end{aligned}}}

and in general

H ( 2 k ) = [ H ( 2 k − 1 ) H ( 2 k − 1 ) H ( 2 k − 1 ) − H ( 2 k − 1 ) ] = H ( 2 ) ⊗ H ( 2 k − 1 ) , {\displaystyle H\left(2^{k}\right)={\begin{bmatrix}H\left(2^{k-1}\right)&H\left(2^{k-1}\right)\\H\left(2^{k-1}\right)&-H\left(2^{k-1}\right)\end{bmatrix}}=H(2)\otimes H\left(2^{k-1}\right),}

for 2 ≤ k ∈ N, where ⊗ denotes the Kronecker product.

Permutation

We can obtain a Walsh matrix from a Hadamard matrix. For that, we first generate the Hadamard matrix for a given dimension. Then, we count the number of sign changes of each row. Finally, we re-order the rows of the matrix according to the number of sign changes in ascending order.

For example, let us assume that we have a Hadamard matrix of dimension 2 2 {\displaystyle 2^{2}}

H ( 4 ) = [ 1 1 1 1 1 − 1 1 − 1 1 1 − 1 − 1 1 − 1 − 1 1 ] {\displaystyle H(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, 3, 1, and 2 sign changes (we count the number of times we switch from a positive 1 to a negative 1, and vice versa). If we rearrange the rows in sequency ordering, we obtain:

W ( 4 ) = [ 1 1 1 1 1 1 − 1 − 1 1 − 1 − 1 1 1 − 1 1 − 1 ] , {\displaystyle 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.

Alternative forms of the Walsh matrix

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:3

W ( 8 ) = [ 1 1 1 1 1 1 1 1 1 1 1 1 − 1 − 1 − 1 − 1 1 1 − 1 − 1 − 1 − 1 1 1 1 1 − 1 − 1 1 1 − 1 − 1 1 − 1 − 1 1 1 − 1 − 1 1 1 − 1 − 1 1 − 1 1 1 − 1 1 − 1 1 − 1 − 1 1 − 1 1 1 − 1 1 − 1 1 − 1 1 − 1 ] , {\displaystyle W(8)={\begin{bmatrix}1&1&1&1&1&1&1&1\\1&1&1&1&-1&-1&-1&-1\\1&1&-1&-1&-1&-1&1&1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&-1&-1&1&-1&1&1&-1\\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, 3, 4, 5, 6, and 7 sign changes.

Dyadic ordering

W ( 8 ) = [ 1 1 1 1 1 1 1 1 1 1 1 1 − 1 − 1 − 1 − 1 1 1 − 1 − 1 1 1 − 1 − 1 1 1 − 1 − 1 − 1 − 1 1 1 1 − 1 1 − 1 1 − 1 1 − 1 1 − 1 1 − 1 − 1 1 − 1 1 1 − 1 − 1 1 1 − 1 − 1 1 1 − 1 − 1 1 − 1 1 1 − 1 ] , {\displaystyle W(8)={\begin{bmatrix}1&1&1&1&1&1&1&1\\1&1&1&1&-1&-1&-1&-1\\1&1&-1&-1&1&1&-1&-1\\1&1&-1&-1&-1&-1&1&1\\1&-1&1&-1&1&-1&1&-1\\1&-1&1&-1&-1&1&-1&1\\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, 3, 2, 7, 6, 4, and 5 sign changes.

Natural ordering

H ( 8 ) = [ 1 1 1 1 1 1 1 1 1 − 1 1 − 1 1 − 1 1 − 1 1 1 − 1 − 1 1 1 − 1 − 1 1 − 1 − 1 1 1 − 1 − 1 1 1 1 1 1 − 1 − 1 − 1 − 1 1 − 1 1 − 1 − 1 1 − 1 1 1 1 − 1 − 1 − 1 − 1 1 1 1 − 1 − 1 1 − 1 1 1 − 1 ] , {\displaystyle H(8)={\begin{bmatrix}1&1&1&1&1&1&1&1\\1&-1&1&-1&1&-1&1&-1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&1&1&1&-1&-1&-1&-1\\1&-1&1&-1&-1&1&-1&1\\1&1&-1&-1&-1&-1&1&1\\1&-1&-1&1&-1&1&1&-1\\\end{bmatrix}},}

where the successive rows have 0, 7, 3, 4, 1, 6, 2, and 5 sign changes (Hadamard matrix).

See also

Wikimedia Commons has media related to Walsh matrix.

References

  1. Kanjilal, P. P. (1995). Adaptive Prediction and Predictive Control. Stevenage: IET. p. 210. ISBN 0-86341-193-2. 0-86341-193-2 ↩

  2. Kanjilal, P. P. (1995). Adaptive Prediction and Predictive Control. Stevenage: IET. p. 210. ISBN 0-86341-193-2. 0-86341-193-2 ↩

  3. Yuen, C.-K. (1972). "Remarks on the Ordering of Walsh Functions". IEEE Transactions on Computers. 21 (12): 1452. doi:10.1109/T-C.1972.223524. /wiki/Doi_(identifier) ↩