Tagged: cartesian product

Cartesian product or Kronecker product?


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.)

Related articles

Let’s try that again, shall we?


This query works for the previously mentioned SQL problem:

SELECT K.BATTLE
FROM
(SELECT S.name AS SHIP, B.name AS BATTLE, C.country AS COUNTRY
FROM
Ships S, Classes C, Battles B, Outcomes O
WHERE
S.class = C.class AND O.battle = B.name AND O.ship = S.name) K CROSS JOIN
(SELECT S.name AS SHIP, B.name AS BATTLE, C.country AS COUNTRY
FROM
Ships S, Classes C, Battles B, Outcomes O
WHERE
S.class = C.class AND O.battle = B.name AND O.ship = S.name) J
WHERE K.COUNTRY = J.COUNTRY AND K.BATTLE = J.BATTLE
GROUP BY K.BATTLE
HAVING COUNT(K.BATTLE) >=9

But it’s still not perfect, because it would record a positive answer if a single ship from 9 countries took part in a battle or two ships from three countries (something that certainly took place in the Pacific).

So I cheated and looked for clues – and this works properly:

SELECT K.BATTLE
FROM
(SELECT S.name AS SHIP, B.name AS BATTLE, C.country AS COUNTRY
FROM
Ships S, Classes C, Battles B, Outcomes O
WHERE
S.class = C.class AND O.battle = B.name AND O.ship = S.name) K
GROUP BY K.BATTLE
HAVING COUNT(K.COUNTRY) >=3

Related articles

Solving a relational query: part 5


Found: the relational algebra to tackle the problem outlined in part 3.

This is based on a solution to a similar problem found in Database Management Systems, Third Edition, though, unfortunately, that book prints a solution that is not relational algebra at all, as it relies on the order in which results are returned (relational algebra is a form of set algebra and sets have no order).

\rho (TEMP1, \rho (BIDDER\_ID \rightarrow USER\_ID, \sigma _{amount > 100} (BID)) \Join USER \Join LOT)

(Rename the attributes in TEMP1 – this is the step that is broken in the book)

\rho (name \rightarrow TEMP1\_name, TEMP1)

\rho(TEMP2, TEMP1 \times ( \rho(BIDDER\_ID \rightarrow USER\_ID, BID) \Join USER \Join LOT ))

\Pi _{NAME, EMAIL} ( \sigma _{TEMP1\_LOT\_ID=LOT\_ID \wedge TEMP1\_USER\_ID=USER\_ID \wedge TEMP1\_BID\_ID \neq BID\_ID} (TEMP2))

Related articles