Patrick Hayden's Lecture at the Bruce County Museum


Science  This weeks lecture:  "From Tornados to Black Holes"


This column does not have a single author, but is submitted by a number of experts that contribute regularly to our news source.  Some are in Canada, some in the UK and one is in the far east


Dr. Hayden's lecture at the Museum was wide ranging and concerned the theory of information which is at the heart of some big questions in physics.  He is an expert in this area.

One big question concerns the information loss in Black Holes.  The general theory of relativity says large black holes do destroy information and some new quantum mechanical theories say no they don't.  This is still a question, but some experts agree with the latter (even Stephen Hawking)

Information in the broader sense is not just what's stored in a library, but includes all matter and energy and their organization.

Near the end of the lecture he talked about information recovery from data that had been partially erased.  Ironically in this very area of the DVD talk on large screen, the picture started to break and become garbled -- information loss for real.  The Museum Staff deftly shifted to a PC which handled the DVD perfectly and the lecture continued.

Many were mystified by how information could be recovered from a message that was partially erased. 

Let's use a simple example that is different from Dr. Hayden's.  Suppose we were sending a  message over a 'noisy' Internet Mail system that was subject to a 50% error rate.  Suppose further that a girl Alice was sending a yes or no message to Tom as Tom had asked her to marry him.  Beforehand they had agreed that she would send

Yes = 0, No = 1.

Knowing that the erasure rate was 50% on average, Alice and Tom agreed use double redundancy

Yes = 00, No = 11

Sadly, we might get a garbled or good message with possible outcomes

00 No
10 Inconclusive
01 Inconclusive
11 Yes
1 Too short retransmit
0 Too short retransmit
xxx ... Too long a packet retransmit
Nothing Oh well, she left town

Dr. Hayden simplified the problem over what we have shown by examining a message with 4 possible outcomes and a padding without the complications that we've introduced. (like too long or nothing)

(next column)

07/10/2009 06:02 PM

Hayden discussed a slightly different problem where Alice is trying to send a message to Tom that consists of one of the words Waterloo, Montreal, Vancouver or Toronto

You'll note quickly that you could have encoded this transmission with 00, 01, 10 and 11 because there are only four possibilities, but Alice thought that since we have a predicted 50% ERASURE rate, then putting in seven bits might help Tom to reconstruct a partially erased message.  Let's see what would happen if we lost 3/7th of our data to erasure?

Hayden did not combine packet size with error rate clearly, but you can guess that to get better recovery would be costly in terms size of the message without other 'magic'.  But, if the erasure rate is below 3 out of 7, then his example is ok.  This example does NOT include garbled messages

Let's suppose Alice and Tom agreed on the following transmissions

Waterloo 0101101
Montreal 1001011
Vancouver 0110110
Toronto 1011010

Example of a message received by Tom with 3 out of 7 erasure rate.

Waterloo 0xxx101
Montreal 1xxx011
Vancouver 0xxx110
Toronto 1xxx010

Notice that Tom gets unique non-erased codes 0101, 1011, 0110 and 1010, so he knows what Alice has sent and he can reconstruct the message.  The neat thing about this is that you can try any combination of erasures of 3, 2 or 1 and you are magically able to reconstruct the message. For example

Waterloo 0x01x0x
Montreal 1x01x1x
Vancouver 0x10x1x
Toronto 1x11x1x

yields 0010, 1011, 0101, 1111 which still tells you what city Alice transmitted.

Some in the audience had trouble with this 'magic' because Dr. Hayden did not discuss other erasure rates, nor shorter messages than anticipated etc.  Since he was discussing it in terms of recovering information from a Black Hole it kind of came out of the blue, since it's clear that messages too long or too short or a different erasure/change rate would mess up the idea.

In real data transmission, which he lightly touched upon earlier, check sums and packet sizes are controlled and redundancy checks are used also (e.g. CRC redundancy)  It was an interesting lecture, but a bit spotty.  In defense of the young genius, it is a hard subject to cover in under two hours

For more on Erasure Codes Click Here

For more on CRC checking Click Here

For Check sums Click Here

View the Lecture in full Click Here

for world news, books, sports, movies ...