today i was discussing about signal transmission with navy friends (which was totally irrelevant from the course.) basically, i learnt more about the transmission process. well, my honors year project was about coding theory, which forms like only a small part of this process. but nevertheless, it's rather interesting and there is a whole industry working on it. yup so i'll share more about coding theory and try to illuminate it in a layman's fashion.
coding theory has another name, which i feel is a more apt description of wat it is about. the theory of error correction. to me, the theory of error correction is very similar to an aspect of the mechanics of our daily language.
consider the word 'lettter'. i think with one look, you'll notice the typo and correct the word to 'letter'.
how did you do it? a simple explanation is that the english dictionary, while containing a lot of words, do not contain all the possible permutations of the 26 letters. there's no such word as 'lettter', and from our many years of education, we know that and hence we detect the error. this is also why it is almost impossible for a monkey to type a comprehensible sentence by chance.
wat i described was an aspect called 'error detection'. how do we then correct the 'lettter' to 'letter'? in some sense, 'letter' is the 'closest' to 'lettter'. if we delete one letter (no pun intended) or add one letter or change one letter of 'lettter', the only possible word you can end up with is 'letter'. (i didnt try but i think it's true...) so, intuitively, we simply just correct 'lettter' to 'letter'.
(there's a danger here. wat i described was making only one alteration. if we allowed to make two alterations, we could end up with words like 'latter' and 'litter'. and we have another aspect to discuss about..)
yes. so in coding theory, or theory of error-correction, that's wat we do... to conjure up some dictionary, but with only the letters 1 and 0. and we measure the efficiency of this dictionary by the number of errors it can correct.
(this is very very vague. for the above example of 'lettter', we can say that we can correct up to one error, but not to two errors... and the overall efficiency is measured by the worst case scenario)
coding theory has another name, which i feel is a more apt description of wat it is about. the theory of error correction. to me, the theory of error correction is very similar to an aspect of the mechanics of our daily language.
consider the word 'lettter'. i think with one look, you'll notice the typo and correct the word to 'letter'.
how did you do it? a simple explanation is that the english dictionary, while containing a lot of words, do not contain all the possible permutations of the 26 letters. there's no such word as 'lettter', and from our many years of education, we know that and hence we detect the error. this is also why it is almost impossible for a monkey to type a comprehensible sentence by chance.
wat i described was an aspect called 'error detection'. how do we then correct the 'lettter' to 'letter'? in some sense, 'letter' is the 'closest' to 'lettter'. if we delete one letter (no pun intended) or add one letter or change one letter of 'lettter', the only possible word you can end up with is 'letter'. (i didnt try but i think it's true...) so, intuitively, we simply just correct 'lettter' to 'letter'.
(there's a danger here. wat i described was making only one alteration. if we allowed to make two alterations, we could end up with words like 'latter' and 'litter'. and we have another aspect to discuss about..)
yes. so in coding theory, or theory of error-correction, that's wat we do... to conjure up some dictionary, but with only the letters 1 and 0. and we measure the efficiency of this dictionary by the number of errors it can correct.
(this is very very vague. for the above example of 'lettter', we can say that we can correct up to one error, but not to two errors... and the overall efficiency is measured by the worst case scenario)
application of error correcting codes are quite common. NRIC, ISBN or even bank accounts used it. (well, maybe not in the way i've described. more commonly engineers use terms like parity check, or redundacy...) more advanced application will be cd technology... that's why we still can scratch ur cd a bit. and more advanced, will be communications over space.
No comments:
Post a Comment