We then add 10000 to our remaining code words writing the result underneath the code word: 00000 Weight 1 means there is only one 1 etc.) We could choose 10000, 01000, 00100, 00010, 00001 because none of these are our code words, and all have weight 1. Next we choose another binary five digit string which has the smallest number of 1s possible from all our choices. We start by writing the code words in the first row (starting with 00000): 00000 We can decode linear codes by arranging all the permutations of received messages into a standard array. A binary code which has this property is an example of a linear code. In this case the sum of two code words is also a code word. However, to make sure the resulting strings only have 0s and 1s as their entries, we use the rule that 0+0=0, 0+1=1+0=1 and 1+1=0. add the first digit of one to the first digit of the other, the second of one to the second of the other, and so on. To add two strings, simply add corresponding digits, i.e. Linear codesīinary strings of symbols come with a notion of addition. The branch of mathematics called coding theory is concerned with creating optimal codes for data transmission – and in our current digital age has become hugely important. This trade off between speed and accuracy will depend on what the data is to be used for. You want a code that can be transmitted quickly (a short length), that has a large number of different code words (to allow for more information to be conveyed) but that also has the capability to minimise errors in interpretation. This highlights the key considerations in designing codes. However when faced with crocodiles you are probably going to accept a loss of speed for greater accuracy. The downside of this code is that it will take longer to transmit than the other codes. This new code can correct any single error, or detect two errors. If there was one error in the transmission of 00000, say to give 01000, you would still decode as 00000 because this is the closest code word to the message received. Code 3Įven better still is a code that can actually correct an error, such as follows: Unfortunately you are not in a position to ask your friend to repeat their message. However in this case you would not know which the original code word was – 010 is 1 digit away from 000, 110 and 011 – so if we assume one error then it could be any of these three. In this case if there was a single error in transmission, say 000 turned into 010, then you would immediately know that there was a problem, as 010 is not a code word. A better code is an error detecting code. What is it about this code that makes it so dangerous for you? Well, it's very susceptible to errors – if there is any error in transmission you will receive completely the wrong information, turning (say) West rather than North. In other words you have around a 34% chance of encountering either a crocodile or land mine. (See the picture.) The probability of this is only. In order for you to arrive at the treasure you need to receive two messages correctly: North, West. Therefore, you have a probability of, translating to a 19% chance, of interpreting 00 as a direction other than North. The probability that your friend sends 00 and you also receive 00 is therefore. The probability that your friend sends a 0 and you receive a 0 is. Is this a good code to choose? Well, your transmission system is not especially reliable – around 10% of the time you will mistake a short puff of smoke for a long one (a 0 for 1) or vice versa. The code you agree on is as follows: Code 1 This amounts to a binary code made up of only two symbols. We will write 0 for a short puff and 1 for a long one. Your friend will use only two types of signal: a short puff of smoke and a longer one. Be careful however, one false step and disaster awaits: there are crocodiles and land mines everywhere! They will send you smoke signals to tell you the correct way. Luckily your friend sitting safely on your boat has the map. You find yourself lost on a dangerous island in search of a buried treasure. To guide you to the treasure your friend needs to tell you take one step North and one step West.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |