Cartesian product or Kronecker product?

Standard
Permutation of the natural ordered Hadamard ma...

Image via Wikipedia

I am continuing to work my way through A. K. Dewdney‘s New Turing Omnibus – some bits are very familiar and not so interesting, but there are lots of fascinating parts and it is another book I wish I’d read two years ago, before I started the MSc. (Update: you may want to read this).

Anyway, I have just been reading Dewdney’s discussion of how the Mariner probes to Mars used error correction to send back their photographs to Earth. The discussion slightly dates the book – but took me back to my childhood (which doesn’t seem that long ago!) and reading about the probes and what was then thought of as the complex problem of decoding the signals (indeed, Dewdney remarks that specialist hardware had to be used to manage the 16kbs bit stream from the probes).

The probes used 32 bits to transmit every 5 bits of real data: using a Reed-Muller code based on a Hadamard matrix.

These are matrices built in this way:

Let\ H_1\ =\ \left( {\begin{array}{rr} 1 & 1 \\ 1 & -1 \\ \end{array} } \right)

H_{n+1} = H_n \otimes H_1

And where, according to the book \otimes is the “cartesian product” of the matrices.

I struggled a bit to work out what a cartesian product of two matrices might be, especially as there seemed to be no definition of such a thing available online. I made a guess (a pretty good one) though and then looked further afield and the standard term for the product appears to “kronecker product” – shown as below (which is pretty much where I was with my guess):

H_2 = H_1 \otimes H_1 =

\left( {\begin{array}{rr} 1 & 1 \\  1 & -1 \\  \end{array} } \right) \otimes \left( {\begin{array}{rr} 1 & 1 \\  1 & -1 \\  \end{array} } \right) =

\left( {\begin{array}{rrrr} 1 & 1 & 1 & 1 \\  1 & -1 & 1 & -1 \\  1 & 1 & -1 & -1 \\  1 & -1 & -1 & 1 \\  \end{array} } \right)

And H_3 = H_2 \otimes H_1 =

\left( {\begin{array}{rrrrrrrr}    1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\    1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\    1 & 1 & -1 & -1 & 1 & 1 & -1 & -1 \\    1 & -1 & -1 & 1 & 1 & -1 & -1 & 1 \\    1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 \\    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{array} } \right)

And so on… the Mariner probe used H_5 which is a 32 x 32 matrix – meaning each possible data signal corresponded to a row (or column) in the matrix – and so that row was sent instead of the data.

The reason this matrix was chosen is because every row, or column, is an orthogonal vector with respect to every other row or column, or, if you like, for the 32 x 32 matrix, each row or column is different in 16 different places from every other row or column.

This means that signals can be wrong in up to 7 different bits and yet it is still relatively simple to pick what the correct signal was meant to be (ie vectors, or rows, have a Hamming distance of 16.)

One thought on “Cartesian product or Kronecker product?

  1. Pingback: Calculating the Kronecker product | cartesian product

Comments are closed.