//Error Correction Using Hamming Code

Error Correction Using Hamming Code

ABSTRACT :


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.

ABOUT :

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:

4messagebits+3redundantbits⇒7bitHammingcode.

ALGORITHM :


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 :

  1.  Serverside :

    import socket
    import sys
    s=socket.socket(socket.AF_INET,socket.SOCK_DGRAM)
    saddress=(‘localhost’,10000)
    m=raw_input(‘enter message’)
    n1=[m[0],m[1],m[2]] c1=n1.count(‘1’)
    p4=c1%2
    n1=[m[0],m[1],m[3]] c1=n1.count(‘1’)
    p2=c1%2
    n1=[m[0],m[2],m[3]] c1=n1.count(‘1’)
    p1=c1%2
    h=”.join(m[0:3]+str(p4)+str(m[3])+str(p2)+str(p1))
    print ‘msg with parity’,h
    try:
    print>>sys.stderr,’sending %s’ %h   sent=s.sendto(h,saddress)
    #print>>sys.stderr,’waiting to receive’
    #data,server=s.recvfrom(4096)
    #print>>sys.stderr,’received %s’ %data
    finally:
    print>>sys.stderr,’closing socket’
    s.close()

  2. client side

    import socket
    import sys
    s=socket.socket(socket.AF_INET,socket.SOCK_DGRAM)
    host=’localhost’
    port=10000
    print>>sys.stderr,”starting up on %s port %s” %(host,port)
    s.bind((host,port))
    print>>sys.stderr,’\n waiting to receive the msg’
    m,address=s.recvfrom(4096)
    print ‘received msg’,m
    n1=[m[0],m[1],m[2]] c1=n1.count(‘1’)
    19
    p4=c1%2
    n1=[m[0],m[1],m[4]] c1=n1.count(‘1’)
    p2=c1%2
    n1=[m[0],m[2],m[4]] c1=n1.count(‘1’)
    p1=c1%2
    #h=”.join(m[0:3]+str(p4)+str(m[3])+str(p2)+str(p1))
    h=m
    c= int(not (int(h[2])-int(‘0’)))
    h=”.join(m[0:2]+str(c)+str(p4)+str(m[4])+str(p2)+str(p1))
    print ‘msg with changed bit’,h
    h=list(h)
    m1=[h[3],h[2],h[1],h[0]] c=m1.count(‘1’)
    p4=c%2
    m1=[h[5],h[4],h[1],h[0]] c=m1.count(‘1’)
    p2=c%2
    m1=[h[6],h[4],h[2],h[0]] c=m1.count(‘1’)
    20
    p1=c%2
    pos=7-(p4*4+p2*2+p1)
    print ‘position of error’,pos+1
    if h[pos]==’1′:
    h[pos]=’0′
    else:
    h[pos]=’1′
    h1=”.join(h)
    print ‘corrected data’,h1
    #if h:
    # sent=s.sendto(h1,address)
    # print>>sys.stderr,’sent %s bytes back to %s’ %(sent,address)


OUTPUT :

  1. Server:

    enter message1101
    msg with parity 1100110
    sending 1100110
    closing socket

  2.  Client:

    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