Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Walsh matrix

From Wikipedia, the free encyclopedia
Orthogonal matrix
Hadamard matrix of order 16 multiplied with a vector
Naturally ordered Hadamard matrix permuted into sequency-ordered Walsh matrix. The number of sign changes per row in the naturally ordered matrix is (0, 15, 7, 8, 3, 12, 4, 11, 1, 14, 6, 9, 2, 13, 5, 10), in the sequency-ordered matrix the number of sign changes is consecutive.
LDU decomposition of a Hadamard matrix. The ones in thetriangular matrices formSierpinski triangles. The entries of thediagonal matrix are values fromGould's sequence, with the minus signs distributed like the ones inThue–Morse sequence.

Inmathematics, aWalsh matrix is a specificsquare matrix of dimensions 2n, wheren is some particularnatural number. The entries of thematrix are either +1 or −1 and its rows as well as columns areorthogonal. The Walsh matrix was proposed byJoseph L. Walsh in 1923.[1] Each row of a Walsh matrix corresponds to aWalsh function.

The Walsh matrices are a special case ofHadamard 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 therecursive formula below and isnaturally ordered, whereas a Walsh matrix issequency-ordered.[1] Confusingly, different sources refer to either matrix as the Walsh matrix.

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

Formula

[edit]

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

H(21)=[111−1],H(22)=[11111−11−111−1−11−1−11],{\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(2k)=[H(2k−1)H(2k−1)H(2k−1)−H(2k−1)]=H(2)⊗H(2k−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 theKronecker product.

Permutation

[edit]

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 dimension22{\displaystyle 2^{2}}

H(4)=[11111−11−111−1−11−1−11]{\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)=[111111−1−11−1−111−11−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

[edit]

Sequency ordering

[edit]

The sequency ordering of the rows of the Walsh matrix can be derived from the ordering of the Hadamard matrix by first applying thebit-reversal permutation and then theGray-codepermutation:[2]

W(8)=[111111111111−1−1−1−111−1−1−1−11111−1−111−1−11−1−111−1−111−1−11−111−11−11−1−11−111−11−11−11−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

[edit]
W(8)=[111111111111−1−1−1−111−1−111−1−111−1−1−1−1111−11−11−11−11−11−1−11−111−1−111−1−111−1−11−111−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

[edit]
H(8)=[111111111−11−11−11−111−1−111−1−11−1−111−1−111111−1−1−1−11−11−1−11−1111−1−1−1−1111−1−11−111−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

[edit]
Wikimedia Commons has media related toWalsh matrix.

References

[edit]
  1. ^abKanjilal, P. P. (1995).Adaptive Prediction and Predictive Control. Stevenage: IET. p. 210.ISBN 0-86341-193-2.
  2. ^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.
Matrix classes
Explicitly constrained entries
Constant
Conditions oneigenvalues or eigenvectors
Satisfying conditions onproducts orinverses
With specific applications
Used instatistics
Used ingraph theory
Used in science and engineering
Related terms
Retrieved from "https://en.wikipedia.org/w/index.php?title=Walsh_matrix&oldid=1316534116"
Category:
Hidden categories:
[8]ページ先頭
©2009-2026 Movatter.jp