The most common types of error-correcting codes used in RAM are based on the codes devised by R. W. Hamming. In the Hamming code, k parity bits are added to an n- bit data word, forming a new word of n + k bits. The bit positions are numbered in sequence from 1 to n + k. Those positions numbered with powers of two are reserved for the parity bits. The remaining bits are the data bits. The code can be used with words of any length. A hamming code table is made. If a received code exactly matches one of the codes in the table, no errors have occurred. If a received code differs from one of the codes in the table by one bit (Hamming distance 1), then a single bit error is assumed to have occurred, and it can be corrected. If a received code differs from one of the codes in the table by two bits (Hamming distance 2), then a double bit error is assumed to have occurred. This can be reported, but it can’t necessarily be corrected, since the received code may differ in exactly two bits from several of the codes in the table. The basic Hamming code can detect and correct an error in only a single bit. Some multiple-bit errors are detected, but they may be corrected erroneously, as if they were single-bit errors.
In telecommunication, Hamming codes are a family of linear error-correcting codes that generalize the Hamming(7,4)-code, and were invented by Richard Hamming in 1950. Hamming codes can detect up to two-bit errors or correct one-bit errors without detection of uncorrected errors. By contrast, the simple parity code cannot correct errors, and can detect only an odd number of bits in error. Hamming codes are perfect codes, that is, they achieve the highest possible rate for codes with their block length and minimum distance of three.
Due to the limited redundancy that Hamming codes add to the data, they can only detect and correct errors when the error rate is low. This is the case in computer memory (ECC memory), where bit errors are extremely rare and Hamming codes are widely used. In this context, an extended Hamming code having one extra parity bit is often used. Extended Hamming codes achieve a Hamming distance of four, which allows the decoder to distinguish between when at most one one-bit error occurs and when any two-bit errors occur. In this sense, extended Hamming codes are single-error correcting and double-error detecting, abbreviated as SECDED.
Hamming Codes fall under the category of linear Block codes of Forward Error Correcting FEC) codes. To understand how it can be constructed, consider the simplest (7,4) hamming code. The notation (7,4) indicates that the codewords are of length 7 bits. Out of these 7 bits, 4 bits are the original message and remaining 3 bits are added for detecting and correcting errors. These remaining 3 bits are called redundant bits.
The structure can be indicated as follows:
Consider transmitting 4 data bits and these data bits are represented by letter D. We are going to find the 3 redundant bits (represented by letter P) using Hamming code algorithm and form the 7-bit Hamming code. The codewords made in this way is called (7,4) Hamming code which is a very basic code.
Let the codeword bits be represented by D7, D6, D5, P4, D3, P2, P1. Here D7, D6, D5 and D3 are the message bits and P4, P2, P1 are the parity or redundant bits. The parity bits are calculated using the following equations. Here + sign indicates modulo-2 addition or XOR operation.
The following table illustrates how to calculate parity bits for the above coding scheme.
Let us attempt to find the Hamming code for the message bits 1101. The message 1101 will be sent as 1100110 using Hamming coding algorithm as follows. Here the data bits and the parity bits in the codeword are mixed in position and so it is a non-systematic code.
SOURCE CODE :
print ‘msg with parity’,h
print>>sys.stderr,’sending %s’ %h sent=s.sendto(h,saddress)
#print>>sys.stderr,’waiting to receive’
#print>>sys.stderr,’received %s’ %data
print>>sys.stderr,”starting up on %s port %s” %(host,port)
print>>sys.stderr,’\n waiting to receive the msg’
print ‘received msg’,m
c= int(not (int(h)-int(‘0’)))
print ‘msg with changed bit’,h
print ‘position of error’,pos+1
print ‘corrected data’,h1
# print>>sys.stderr,’sent %s bytes back to %s’ %(sent,address)
msg with parity 1100110
starting up on localhost port 10000
waiting to receive the msg
received msg 1100110
msg with changed bit 1110110
position of error 3
corrected data 1100110