Talk:Walsh matrix

In my opinion, the line in the article which states: "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]" is insufficiently clear, partly because it's not clear what we're reversing the bits of, and partly because it's not clear what is meant by "the Gray code permutation".

If "the Gray code permutation" means that we label each line with the integer that it is the polar form representation of the Gray code for, and then arrange in ascending order of those integers, the example given is of little help because by doing this we obtain the sequency ordered matrix as described, without doing any form of bit-reversal. Reading "A Simplified Definition of Walsh Functions" as cited in [2], this does not appear to be what is meant.

Examining [2] carefully, we see that Henderson's ordering is the natural ordering as described in the article. This being so, a lot more clarity about what it is that we're reversing the bits of during the "bit-reversal" is required. In this case, a bit reversal is involved in mapping from Paley's ordering to the natural ordering, in that column a_{1}a_{2}...a_{n} is mapped to column a_{n}a_{n-1}...a_{1} (a_{1}a_{2}...a_{n} being a bitstring represntation of the column's index.)

If I've got this right so far, it would help to expand the example by talking the reader through the transformation process. Given the natural-ordered

$H_{2}={\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\\\end{bmatrix}}$

we label the columns with the bitstrings 00, 01, 10, 11.

${\begin{matrix}00&01&10&11\\\end{matrix}}$

${\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\\\end{bmatrix}}$

We then go through the columns and replace the column indexed by i with the column indexed by the bit reversal of i. This takes us from Henderson's ordering to Paley's ordering and gives us:

${\begin{bmatrix}1&1&1&1\\1&1&-1&-1\\1&-1&1&-1\\1&-1&-1&1\end{bmatrix}}{\begin{matrix}{\mbox{(Row 00 corresponds to truth table of null linear function }}L_{00}{\mbox{)}}\\{\mbox{(Row 01 corresponds to truth table of linear function }}L_{10}{\mbox{, but due to the bit reversal we refer to this as }}L_{01}{\mbox{)}}\\{\mbox{(Row 10 corresponds to truth table of linear function }}L_{01}{\mbox{, but due to the bit reversal we refer to this as }}L_{10}{\mbox{)}}\\{\mbox{(Row 11 corresponds to truth table of linear function }}L_{11}{\mbox{)}}\\\end{matrix}}$

We reorder the rows by taking the ij of each row's corresponding L_{ij}, and putting these in Gray code order:

${\begin{bmatrix}1&1&1&1\\1&1&-1&-1\\1&-1&-1&1\\1&-1&1&-1\end{bmatrix}}{\begin{matrix}{\mathtt {(L_{00})}}\\{\mathtt {(L_{01})}}\\{\mathtt {(L_{11})}}\\{\mathtt {(L_{10})}}\\\end{matrix}}$

This achieves the correct result, but I would welcome confirmation that this is indeed what is meant by the "Gray code permutation". [2] is rather hard to understand when consulted about this, and I have achieved the correct result for several other definitions/algorithms tried.144.32.170.32 (talk) 21:42, 11 March 2011 (UTC)

Examining the above, I note that we can optimise by removing the change in column order, although as this is not implied in [2] it may not be important enough to mention if the article is amended.144.32.170.32 (talk) 21:47, 11 March 2011 (UTC)

Can we go ahead and update this page? It is not useful as is, as I couldn't figure out how to implement this without the information on the talk page. daviddoria (talk) 14:39, 28 June 2012 (UTC)

Also, I think instead of "In this case, a bit reversal is involved in mapping from Paley's ordering to the natural ordering" you meant to say "In this case, a bit reversal is involved in mapping from the natural ordering Paley's ordering"? Finally, there seems to be some good information here for verification: http://mathworld.wolfram.com/WalshFunction.html daviddoria (talk) 14:49, 28 June 2012 (UTC)

One more thing... if you want to use the Hadamard transform on images, you need 2D basis functions. Say you need a set of 8x8 Hadamard basis functions - would you need to construct a 64x64 Walsh matrix and then take each column and "wrap" it into an 8x8 "matrix/image"? Or could you just make an 8x8 Walsh matrix and do something with the outer products of all pairs of columns? If you did the later, how would you maintain sequency ordering? daviddoria (talk) 15:03, 28 June 2012 (UTC)

Damaged TIFF picture

@Lapisgaming: Are you sure the damaged TIFF somehow contains a Walsh matrix? I just see some kind of Sierpinski triangle. (diff) --Watchduck (quack) 22:43, 28 December 2021 (UTC)