| Line 35: | Line 35: | ||
data: 0101 | data: 0101 | ||
| − | parity bit position 1, 2, 4 | + | parity bit position 1, 2, 4 _ _ 0 _ 1 0 1 |
P1: '''''?'''''_'''''0'''''_'''''1''''' 0''''' 1''''' even: P1=0 | P1: '''''?'''''_'''''0'''''_'''''1''''' 0''''' 1''''' even: P1=0 | ||
Revision as of 11:33, 26 April 2014
link titleWhat is a code, and what could "error-correcting" mean?
Explain what Hamming codes are and how they try to correct errors. And why you would want that in the first place.
- What is a code?
The most relevant definition for a code in this context, given by Merriam Webster, is the following: that it is "a system of signals or symbols for communication". Codes are, very commonly, obfuscated during communication such that only the sender and the receiver can understand their contents, but this is not a quality which belongs to all codes.
In essence, a code is just an agreed upon language which two people could use to communicate. The English language itself could be thought of as a code, especially when viewed from the context of someone who doesn't speak it. Another example is Morse code, which is used to communicate over analog radio signals. Finally, a common code that is used by computers in information exchange is ASCII/Unicode, which maps integer numbers to symbols in many languages. For instance, the number "1" in ASCII is not 1; it is 49.
- What could "error-correcting" mean?
- What are Hamming Codes?
Data that transmitted over communication channel or stored in memory appears error.
Hamming Codes were invented by Richard Hamming in 1950. In general, Hamming code is a set of error-correction codes that can be used to detect and correct bit errors that can occur when computer data is moved or stored.[1]
Hamming Codes are important invention. The simple parity codes cannot correct errors and can detect an odd number of bits error. Compared with previous simple parity codes, hamming codes can detect two-bit errors or less or correct one-bit errors without detection of uncorrected errors. [3] Hence, hamming codes are more effective.
In order to understand what is hamming codes, Parity concept has to know first. Parity is that a binary digit is used to indicate whether the number of bits with"1" in a given set of bits is even or odd and it added to original data.
Hamming codes adopt parity concept, but have more that one parity bit. Hamming code is code word of n bits with m data bits and r parity. According to formula $ (m+r+1)<=2^r $, the lower limit of r is the number of parity bits for single-bit correction.
Now, we see the exact hamming code algorithm for single-bit correction [4] 1. Parity bits are in position of powers of 2
2. all other bit positions are for the data
3. each parity bit calculates the parity for some of the bits in the code word. The position of the parity bit determines the sequence of bits that it alternately checks and skips.
4. set a parity bit to1 id the total number of "1" in the positions checks is odd. Otherwise is "0"
For example: data: 0101
parity bit position 1, 2, 4 _ _ 0 _ 1 0 1
P1: ?_0_1 0 1 even: P1=0
P2: _ ? 0 _1 0 1 odd: P2=1
P4: _ _ 0 ? 1 0 1 even P4=0
so 0100101
- How do Hamming Codes attempt to correct errors?
Because of the limited redundancy that Hamming codes has put on the data, they can only detect and correct errors when the error rate is low. In computer memory, Hamming codes are widely used when bit errors are rare. Due to mess data transmission, transferred code words would contain errors somehow. The Hamming Code is designed to detect and correct errors in 4 bit transmissions. For example, we have transferred data is 1111010 and original data is 0001011. We need to have detection first see if this is Hamming Code. We could simply just go through the code. If it is one of the 16 code words, we know the transferred correctly. If it is not, we need to compare the data received with each code word and compute the Hamming distance for each. The Hamming distance is defined as the number of times a bit in the received message differs from the bit in the code word. So compare 1111010 with 0001011. Hamming distance is for in this case since they have 4 bits position different. Using the (7,4) Hamming Code Sheet to find all Hamming distance for each one, then we are able to get the Hamming code which produces the shortest distance for 1111010 is 1011010, which is also called “nearest” code word. This code will be the code used to correct the transmission error. If there is more than one shortest distance, we do not correct the message.
- Why would we want error correction in the first place?
Error correction is very helpful and very important in the programing activities and there are several reasons why we want error correction in the first place. First, error correction will verify the validity of the data. The validity of the data directly affects the result of the whole project. For example, consider the Microsoft Word software, when we typing a wrong word, say “teh”, the software itself will detect this and correct it automatically as “the”. If we don’t have this error correction function in it, our document will contain a lot of errors such like misspelling or grammatical mistakes. In that case, we cannot verify the validity of our document since we do not know whether the readers will understand the sentences or not. Second, error correction speeds up the system and saves time. We would like to use a perfect system without any error so we can run all the programs smoothly. Error correction plays a very important role here, correcting the errors in the system will improve the speed and accuracy of the system. Let’s take computer as an example, we correct the error in the system so you can open a software or application quickly and the system will react you faster. In this case, error correction is saving our time. Last but not the least, error-correcting codes is the base of ensuring every later step. Error correction is used in some daily use equipment, such as cell phones, and CD player. Error correction will make sure every step in programming works so we can use all these equipment smoothly. From all above, we can conclude that we want error correction in the first place because we would like to verify the validity of our data, speed up our system, save time, and provide a better base for every later steps. There’s also a link here to provide more references for the importance of error correction and hamming codes. "How Error Correcting Code Work
