Tuesday, February 5, 2013

My Love Over A Noisy Channel

    I'll tell you the story first.

    There's a beautiful valley in between two mountains. An armed force called Red army have settled their camp in this valley. They have a man power of 700 soldiers. There's another armed force called White army which resides in the mountains. One part of the White army resides in one mountain having 500 soldiers while the other part of the White army resides in the other mountain also having 500 soldiers. Therefore altogether White army has 1000 man power. Let's call the two mountains as mount-1 and mount-2.

    Now here's the rules of this world. In any battle the victory is on the hand of the party who have highest man power on the battle field. The loser's whole man power in the battle field gets wiped out while the winner's soldiers don't get any casualty. Therefore the victory in a war is just a matter of having more man power in the field than the enemy in this imagined world. Additionally in this world there's no any distance communication like wireless communication, birds who bring letters, smoke messages, etc.

    OK, back to the battle field. Now the commander who is in-charge of mount-1 of the White army want to destroy the whole Red army who have occupied the valley. But he has only 500 soldiers which is not enough to face the 700 soldiers in Red army. However there's another battalion of the White army in mount-2 with 500 more soldiers. So, the obvious solution is to ask for help from the other White army battalion. If both White forces attack at the same time, according to the rules whole Red army will get wiped out and the White army wins.

    The commander in the mount-1 is really happy about his brilliant idea. Now he should pass his battle plan to the mount-2 commander since they both have to attack the Red army at the same time. Suppose the battle plan message says "Let's attack Red army on next Friday morning at 5.34am". The commander of mount-1 chose a soldier and gave him the message and ordered to go to mount-2 to give the message to that commander. There's only one way to get to mount-2 from mount-1. The poor soldier goes through the enemy lines putting his life in danger. What a brave man. If he gets captured by the Red army definitely they will kill him.

    OK, so now we have some theoretical questions. On next Friday at 5.34am can mount-1 commander launch his attack ? How does he know that the soldier he sent has successfully delivered the message ? If the message hasn't delivered, the complete White army battalion in the mount-1 is going to be wiped out by the Red army. Now suppose the message is actually delivered by that brave man to the mount-2 commander. So, on next Friday at 5.34am can mount-2 commander launch his attack ? How does he make sure that mount-1 commander will do it as mentioned in the battle plan since he still doesn't know whether mount-2 commander got the message ? This is a risky situation.

    So, mount-2 commander writes an acknowledgement massage saying that "OK, my battalion too will attack on next Friday morning at 5.34am". Now again a solder is sent from mount-2 to mount-1 in the same routine with the acknowledgement message. Okay, then next Friday at 5.34am can mount-2 commander launch his attack ? How does he know whether his acknowledgement message has reached the mount-1 commander ? If the soldier with the acknowledgement message has got killed on the enemy line, the mount-2 force might get wiped out if they attack alone in next Friday. So, now what should happen ? The mount-1 commander has to acknowledge the acknowledgement message. When will this message loop end ?

    I heard this story two times from a very impressive lecturer I've met in my undergraduate university life. He's Dr. Chamath Keppitiyagama. For the first time he mentioned the story at the 'Operating Systems' lecture back in my second year. Then again he mentioned the story in my fourth year during 'Communication Networks' lecture.

    This story about the two armies is a very good way to explain the situation of sending data over noisy communication mediums like copper cables, radio signals and even fibre optics. The data we are sending might get lost or get altered while they are travelling through such mediums. Therefore it's a huge challenge to make sure that whatever the data we're sending has arrived the destination safely.

    Coding Theory is the field in Computer Science which deals with this challenge. We use various error detecting and error correcting codes to make sure what we have received from a sender over a noisy channel is exactly what he or she has sent from that side. When the Internet data traffic goes through the complex networking infrastructures, it's absolutely necessary to detect and correct possible errors that occur. Otherwise the communication networks we're using today for our everyday purposes may not become usable at all.

    Anyway we have to face the reality. All the kinds of error detecting and correcting codes we are using today in Coding Theory can only reduce the probability of errors to some extent but they can not reduce error probability to zero. That means having all these sophisticated mechanisms, we are still exposed to the risk of data loss and data alteration during communication. This is all due to the availability of noise in our communication mediums. When we are using networked communication, errors can occur any time if noise is there.

    Due to these reasons, if you send an SMS or email to someone saying "I love you!" there's a probability for it to reach your partner's computing device as "I hate you!!". Of course the probability is very smaller. Remember the probability for a tsunami to occur in Indian ocean which can affect Sri Lanka was mathematically ignorable. But it happened.