Patrick Hayden's Lecture at the Bruce County Museum
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
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)
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
Example of a message received by Tom with 3 out of 7 erasure rate.
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
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 ...|