Memo to self: fighting the Moon is a waste of time

Moon (Photo credit: penguinbush)

My telescope is getting its (sadly) annual run out but I need not have bothered this week – as despite clear skies the Moon is also about (full Moon is on 1 August) – and that makes even setting up the telescope difficult: you can pick out Vega as a bright star in your scope, but Deneb? Even it is being drowned in moonlight.

Maybe next week will be clear too and I can get a good run: maybe even getting to see Uranus (no sniggering at the back), which is viewable right now, though low. Or even, if luck holds, Neptune.

Tim Berners-Lee and NBC

Tim Berners-Lee at a Podcast Interview
Tim Berners-Lee at a Podcast Interview (Photo credit: Wikipedia)

Lots of Brits are today indulging in a favourite sport – bashing “thick Americans” – in this case the NBC commentators on the Olympic opening ceremony who professed to have no clue as to who the inventor and first implementor of the world wide web, Tim Berners-Lee, was when he took part:

Meredith Viera: If you haven’t heard of him, we haven’t either

Matt Lauer: Google him!

The ceremony has generated a large amount of political controversy in the UK – one, particularly nasty, Tory MP called it “leftie multicultural crap” while a newspaper columnist attacked it for presenting a multi-ethnic British family as typical of the country. The chance to laugh at clueless Americans offers a distraction from that (not that most care, the ceremony got a television audience of 26.2 million – an astonishing triumph in the multi-channel age and I have yet to read a negative comment from a ‘real’ person about it).

Berners-Lee was seen typing “this is for everyone” and maybe that is why he’s not so famous. People who market technology that plainly is not for everyone – like Steve Jobs – are truly world famous, while Berners-Lee cannot get arrested.

Americans have not been getting a great press on Olympics matters this last week – Mitt Romney’s trip turned into a fiasco as he was publicly rebuked by the Prime Minister, nominally a political ally, for questioning how well prepared the country was.

All good fun if you are not a Romney fan, and I am not: but more deeply the casual anti-Americanism must reflect a fundamental worry about national decline.

ummm, in retrospect…

Update: I had another look at this. Actually, in retrospect, the substance of the lecture notes are not wrong, but they are worded for electronic engineers rather than computer scientists or mathematicians

Normally one would present the process of creating a code word in the form:

P(x) = m(x)G(x)

Where P(x) is the code word, m(x) is the message to be coded and G(x) the generator matrix. The lecture notes present the generator matrix in a systematic form which would be the equivalent of:

P(x) = m(x)IG(x) , where I is the identity matrix.

Here’s a quandry: you are researching “Cyclic Redundancy Codes” (CRCs) – mainly for finding a clearer way to explain them, when you come across some lecture notes from an academic at one of the bigger universities in Western Europe which, initially at least, look like a model of clear exposition.

But as you read on, you realise with growing incredulity that what the lecturer describes as CRCs are not CRCs at all but general linear block codes.

Now, the principles are similar – in that the lecturer discusses generator matrices and parity check matrices, but the details are hopelessly wrong.

So, do you (a) denounce the academic in public, or (b) contact them in private or (c) post a ‘blind’ blog and wonder about what value students and taxpayers are getting for their money?


Further reflections on the Raspberry Pi

I don’t want to be like a wet blanket – I really love the Raspberry Pi and the idea you can get a bare bones but entirely functional computer for less than thirty quid and hook it up to your HD TV with a £1.50 HDMI cable.Raspberry Pi on HD TV

But, having spent the day trying to get it to do some pretty basic things – like play some video or audio – I have to say that a lot of educationalists seem to be vesting far too much hope in what is, after all, a testing board.

It’s true that you can boot the thing up quickly and easily and that it comes with Scratch (though I haven’t tested that, yet). But I suspect most kids will get frustrated very quickly with it when they find it cannot do lots of things on the internet that they take for granted.

Using it is like regressing a decade or so in the Linux experience – lots of things don’t work (I still have not got mine to play any sound via the HDMI cable) or the software is not (yet) available.

I could see how it could be a low spec web server (after all I got a Dreamcast to be one of those) or a management board for NAS, and I’d love to play around with the GPIO stuff, but I would worry that many children would be put off if things that they expect their programs to do just do not happen because of some problems with the drivers.

The idea is a very sound one, though, and I am sure that in six months time it will be worth considering, but I wouldn’t bet my ICT budget on a fleet of these things yet.

(In my own case my idea, that I could use the board as a micro alternative to a projector by having it display presentations and video on our office HD TVs is on hold for now, as the software is just not available as far as I can see.)

CRCs as matrix maths

I wrote about CRCs cyclic redundancy checks – about a year ago, following on from what I had read in Andy Tanenbaum’s Computer Networks – and because you see CRCs used everywhere.

But now, thanks to another book – Networks on Chips – here’s a slightly more fundamental examination.

CRCs are a form of Cyclic codes – codes where a rotation – eg., make the 0 bit the highest order bit, the previously highest order bit the second highest order bit and so on – produces a new codeword.

As before we can think of code words as polynomials of the power of 2 with coefficients of 0 or 1, eg.,

p(x) = c_02^0 + c_12^1 + c_22^2 + c_32^3 + ... + c_{n - 1}2^{n - 1}

(And of course any natural number can be represented in this fashion.)

Then a circular shift is similar to multiplying by 2 – though with the proviso that c_{n -1} \rightarrow c_0

We can construct a codeword in the form p(x) = m(x)g(x) + r(x) where m(x) is the message, g(x) is the (monic) generator and r(x) a remainder (of the same or lesser order as g(x) ).

But if we stipulate that g(x) is of the smallest order of a codeword then that means r(x) must be zero.

So, what does a generator matrix look like?

If we have a monic generator polynomial g(x) of degree k and a code word length of n :

G = \left( {\begin{array} {rrrrrrrr} g_0 & g_1 & g_2 & ... & g_k & 0_l & 0_m & 0_n \\ 0_a & g_0 & g_1 & g_2 & ... & g_k & 0_m & 0_n \\ ... & ... & ... & ... & ... & ... & ... & ... \\ 0_a & 0_b & 0_c & g_0 & g_1 & ... & g_j & g_k \end{array} } \right)





WordPress (Photo credit: Adriano Gasparri)

I first had a blog when they were still called “web logs” (yes, kids, that’s where it comes from) – I never thought it would take off, though I also thought it was one of those ideas (like intranets – remember them?) that were so beautifully simple that I wish I had thought of it. So, what do I know anyway?

I used to host my own (WordPress) blog and I am wondering if I should do that again. It’s not that I dislike, but it’s a pain not being able to post any Javascript or similar material. The disadvantage, of course is the cost (hosting – I used to host the blog on a machine at home but that’s just too extra as my kids would say – or did, I think this this term is already out of fashion) and the hassle of upgrades (though if I set the permissions right that should go away).

Any thoughts, any one?

Thrash reduction no longer a priority for Linux kernel devs?

Version 3.5 of the Linux kernel has been released.

freshly installed ipod linux, booting. during ...
freshly installed ipod linux, booting. during Wikipedia:Workshop Köln (Photo credit: Wikipedia)

One of the changes it includes is the removal of the “swap token” code – one of the very few ‘local’ memory management policies grafted on to the ‘global’ page replacement mechanisms in the kernel.

There are various technical reasons offered for the removal of the code – on which I am not qualified to comment – but the borrow line is that it was broken in any case, so the removal seems to make sense.

What does slightly disturb me, though, is the comment that Rik Van Riel, the key figure in kernel memory management code, makes:

The days of sub-1G memory systems with heavy use of swap are over.
If we ever need thrashing reducing code in the future, we will have to
implement something that does scale.

I think the days of sub-1G systems are far from over. In fact I suspect there are more of them, and more of them running Linux, than ever before and that trend is not going to stop.

He’s right of course about the need to find that code that works – my own efforts (in my MSc report) didn’t crack this problem, but I do think there is more that can be done.

Hamming codes

Hamming codes are a family of error correction (1 bit) and error detection (2 bits) linear codes. The minimum distance (ie Hamming distance) between codewords in a Hamming code is 3.

For each integer i \geq 2 there is a binary code of block length: vectors

n = 2^i - 1

and a message length:

k = n - i

giving a coding rate:

\frac{k}{n} = \frac{n - i}{n} = 1 - \frac{i}{n}

Hamming codes have parity checking matrices the columns of which consist of all the non-zero vectors of length i .

Hence for a (7, 4) Hamming code the parity check matrix would be:

H = \left( {\begin{array} {rrrrrrr} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{array} } \right)

Which, (if I have done this correctly!), can give us a generator matrix:

G = \left( {\begin{array} {rrrrrrr} 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \end{array} } \right)

The first three columns form an identity matrix, allowing us to use the first three bits of the received code as the original message.

(One interesting point to note is that we can run this process in reverse to compress data in a lossy form – eg we could compress 7 bits into three bits using this Hamming code, provided we were willing to tolerate the errors/losses.)

More on parity matrices

Here’s a generator matrix,

G = \left( {\begin{array} {rrrr} 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 \end{array} } \right)

A parity check matrix for this, H is one where GH^T = 0 (hence the product of H^T with a codeword is also 0, though an error word generates a non-zero output).

Two candidates for this present themselves (are there others? I can’t see them):

H^{\prime}= \left( {\begin{array} {rrrr} 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 \end{array} } \right)

H^{\prime\prime}= \left( {\begin{array} {rrrr} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{array} } \right)

Taking H^{\prime} , there are 2^k distinct messages (codewords), where k = 2, but he generator can create 2^n = 2^4 different outputs. So we have 2^k - 1 non-zero code words and 2^n - 1 possible outputs, the number of detectable errors is:

2^n - 1 - (2^k - 1) = 2^n - 2^k = 12

The most likely error is the one with the lowest Hamming weight:

\left( {\begin{array} {lrrrr} codewords & 0000 & 0101 & 1100 & 1001 \\e_1 & 0001 & 0100 & 1101 & 1000\\e_2 & 0010 & 0111 & 1110 & 1011 \\e_3 & 0011 & 0110 & 1111 & 1010 \end{array} } \right)