Error Detection and Correction Using Hamming Code

PROJECT REPORT
ON
ERROR DETECTION AND

CORRECTION USING HAMMING
CODE
CONTENTS
1. Company Profile
2. Introduction
3. Requirements
 Hardware requirements
 Software requirements
 Operating system
 Language
4. Modular Diagram
5. Coding
6. Snapshots
7. Scope and Objectives
8. Conclusion
9. Proposed enhancements
10. Bibliography
OPEN SOURCE SOFTWARE VERSUS CLOSED
SOURCE SYSTEM
Open source software is currently one of the most debated phenomena in the
software industry, both theoretically and empirically. At the most basic level,
the term open source software simply means software for which the source code
is open and available. The source code is the program in which a software is
originally written. A software is said ”open” when its source code can be read
(seen) and written (modified) by everybody. Availability implies that anybody
can acquire the code either free of charge or for a nominal fee (usually media
and shipping charges or online connection charges).
In recent years, the growth and development of the open source movement
has been boosted by the Internet: today, making a source code available can
be as simple as posting it on the World Wide Web or in an online newsgroup.
Furthermore, making the software open is also extremely simple, i.e. place no
restrictions on how the software is actually used or by whom.
Typically, open source software has been extremely successful in those segments
of the market where the potential purchasers are ”sophisticated users”,i.e. system and
server administrators or more generally those that are experienced
in handling computers and that, for this reason, are well aware of all
various packages available. Just to take a relevant example, the open source
software Apache is currently the most popular software for web servers; its
market share is about 60% of the total, more than two times larger than
Microsoft, its ”closed source” commercial rival. Two other examples of well established
open source softwares are Sendmail, the dominant messaging service
program for routing and handling email by email servers and Linux, an operating
system which is probably the best-known example of the emerging open
source software movement, which has a current market share of about 30%.
Open source software has recently attracted a great amount of attention.

Many researchers have focused on explaining where contributors find their motivationsto
develop new software or to improve the existing one, provided that
open source software and its further developments are usually made available
at zero price. Any software improvement is a costly activity, and supplying it
for free does not reflect these costs; other benefits related to career concerns
and/or ego gratification must be taken into account when analysing motivations
for open source software developers. Lerner and Tirole (2002) and
Lakhani and von Hippel (2000) go in this direction. A different explanation
has been offered by Raymond (1999) which stresses on the idea that open
source is a form of gift economy based on altruistic motives.
Our analysis is essentially static: it does not contemplate neither R&D

activity from software producers nor firms’ entry and compatibility strategies,
which have both dynamic nature.7 In particular, one of the reasons that has
been put forward to justify government intervention in favor of the open source
movement is that open source developers have more incentives to innovate
than those working for a commercial producer. This is a very interesting
and controversial issue: both Smith (2002) and Schmidt and Schnitzer (2002)
contrast this argument and argue that it is the marketplace rather than the
policy arena to provide the right incentives to ensure continuous innovation.
Bessen (2002) argues in favor of open source; he contends that open source
addresses market failures associated with incomplete contracts and asymmetric
information: the government should remove the impediments it has imposed
to developers through software patents, which tilt the market in favor of proprietary
developers.
As it is clear from this concise discussion, the issue of government intervention

in the software market is still very much debated. The vast majority
of the literature does not provide a sufficiently developed analytical framework
able to analyse the complex intricacies of the various issues at stake; our
contribution is a first, although simple, effort to try to fill this gap.
INTRODUCTION
Error
 An error is a deviation from a correct value caused by a malfunction in a
system or a functional unit. An example would be the occurrence
of a wrong a bit caused by an equipment malfunction.
 An error is an unauthorized change in the content that is being sent.
 The error can completely change the meaning of the data sent.
 Error occurs because of transmission impairments — signal gets

Attenuated, overwhelmed by noise.
Types of Error
Whenever an electromagnetic signal flows from one point to another, it is subjected to

unpredictable interference from heat, magnetism and other forms of electricity. This
interference can change the shape or timing of the signal. The error can be:
 Single-Bit Error
 Burst Error
Single-Bit Error
The term single bit error means that only one bit of a given data unit (such as a byte,
character, data unit, or packet) is changed from 1to 0 or from 0 to 1.
0 changed to 1
0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0
Received Sent
Single- bit error are the least likely type of error in serial data transmission. For a single-
bit error to occur the noise must have duration of only 1 microsecond, which is very
rare; noise normally lasts much longer than this.
However, a single –bit error can happen if we are sending data using parallel
transmission. For example, if eight wires are used to send all of the eight bits of a byte
at the same time and one of the wires is noisy, one bit can be corrupted in each byte.
Burst Error
The term burst error means that two or more bits un the data unit have changed from 1 to 0
or from 0 to 1.
A burst error doesn’t necessarily mean that the errors occur in consecutive bits. The length
of the burst is measured from the first corrupted bit to the last corrupted bit. Some itsin
between may not have been corrupted.
Length of
burst error
(5 bits)
Sent
0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1
Bits corrupted by burst error
0 1 0 1 1 1 0 1 0 1 0 0 0 0 1 1
Received
Burst error is most likely to happen in a serial transmission. The duration of noise is
normally longer than the duration of a bit, which means that when noise affects data, it
affects a set of bits. The number of bits affected depends on the data rate and duration of
noise. For example, if we are sending data at 1 Kbps, a noise of 1/100 seconds can affect
10 bits; if we are sending data at 1 Mbps, the same noise can affect 10,000 bits.
Error Detection
 Error detection is the ability to detect the presence of errors caused by noise
or other impairments during transmission from the transmitter to the
receiver.
Error detection schemes

In telecommunication, a redundancy check is extra data added to a message for the
purposes of error detection.
Several schemes exist to achieve error detection, and are generally quite simple. All error
detection codes (which include all error-detection-and-correction codes) transmit more bits
than were in the original data. Most codes are "systematic": the transmitter sends a fixed
number of original data bits, followed by fixed number of check bits (usually referred to as
redundancy in the literature) which are derived from the data bits by some deterministic
algorithm. The receiver applies the same algorithm to the received data bits and compares
its output to the received check bits; if the values do not match, an error has occurred at
some point during the transmission. In a system that uses a "non-systematic" code, such
as some raptor codes, data bits are transformed into at least as many code bits, and the
transmitter sends only the code bits.
Repetition schemes
Variations on this theme exist. Given a stream of data that is to be sent, the data is broken
up into blocks of bits, and in sending, each block is sent some predetermined number of
times. For example, if we want to send "1011", we may repeat this block three times each.
Suppose we send "1011 1011 1011", and this is received as "1010 1011 1011". As one
group is not the same as the other two, we can determine that an error has occurred. This
scheme is not very efficient, and can be susceptible to problems if the error occurs in
exactly the same place for each group (e.g. "1010 1010 1010" in the example above will be
detected as correct in this scheme).
The scheme however is extremely simple, and is in fact used in some transmissions of
numbers stations.
Parity schemes
A parity bit is an error detection mechanism that can only detect an odd number of errors.
The stream of data is broken up into blocks of bits, and the number of 1 bits is counted.
Then, a "parity bit" is set (or cleared) if the number of one bits is odd (or even). (This
scheme is called even parity; odd parity can also be used.) If the tested blocks overlap,
then the parity bits can be used to isolate the error, and even correct it if the error affects a
single bit: this is the principle behind the Hamming code.
There is a limitation to parity schemes. A parity bit is only guaranteed to detect an odd
number of bit errors (one, three, five, and so on). If an even number of bits (two, four, six
and so on) is flipped, the parity bit appears to be correct, even though the data is corrupt.
Checksum
A checksum of a message is an arithmetic sum of message code words of a certain word

length, for example byte values, and their carry value. The sum is negated by means of
ones-complement, and stored or transferred as an extra code word extending the
message.
On the receiver side, a new checksum may be calculated, from the extended message. If
the new checksum is not 0, error is detected.
Checksum schemes include parity bits, check digits, and longitudinal redundancy check.
Cyclic redundancy checks
More complex error detection (and correction) methods make use of the properties of finite
fields and polynomials over such fields.
The cyclic redundancy check considers a block of data as the coefficients to a polynomial
and then divides by a fixed, predetermined polynomial. The coefficients of the result of the
division are taken as the redundant data bits, the CRC.
On reception, one can recomputed the CRC from the payload bits and compare this with
the CRC that was received. A mismatch indicates that an error occurred.
Hamming distance based checks
If we want to detect d bit errors in an n bit word we can map every n bit word into a bigger
n+d+1 bit word so that the minimum Hamming distance between each valid mapping is
d+1. This way, if one receives a n+d+1 word that doesn't match any word in the mapping
(with a Hamming distance x <= d+1 from any word in the mapping) it can successfully
detect it as an errored word. Even more, d or fewer errors will never transform a valid word
into another, because the Hamming distance between each valid word is at least d+1, and
such errors only lead to invalid words that are detected correctly. Given a stream of m*n
bits, we can detect x <= d bit errors successfully using the above method on every n bit
word. In fact, we can detect a maximum of m*d errors if every n word is transmitted with
maximum d errors.
Hash function
Any hash function can be used as a redundancy check.

Horizontal and vertical redundancy check
Other types of redundancy check include horizontal redundancy check and vertical
redundancy check.
Polarity schemes
One less commonly used form of error correction and detection is transmitting a polarity
reversed bitstream simultaneously with the bitstream it is meant to correct. This scheme is
very weak at detecting bit errors, and marginally useful for byte or word error detection and
correction. However, at the physical layer in the OSI model, this scheme can aid in error
correction and detection.
Polarity symbol reversal is (probably) the simplest form of Turbo code, but technically not a
Turbo code at all.
 Turbo codes DO NOT work at the bit level.
 Turbo codes typically work at the character or symbol level depending on

their placement in the OSI model.
 Character here refers to Baudot, ASCII-7, the 8-bit byte or the 16-bit word.
Original transmitted symbol 1011
 transmit 1011 on carrier wave 1 (CW1)
 transmit 0100 on carrier wave 2 (CW2)
Receiver end
 Do bits polarities of (CW1) <> (CW2)?
 if CW1 == CW2, signal bit error (triggers more complex ECC)
This polarity reversal scheme works fairly well at low data rates (below 300 baud) with very
redundant data like telemetry data.
Error Correction
 Error correction is the additional ability to reconstruct the original, error-free
data
Error Correcting Codes
 Error correcting codes enable data to be sent through a noisy communication

channel without corruption.
 To accomplish this, the sender appends redundant information to the message.
 So that even if some of the original data is corrupted during transmission, the
receiver can still recover the original message intact.
Various methods
 Parity
 Repetition
 Hamming Code
Hamming Code
In telecommunication a Hamming code is a linear error-correcting code named after its
inventor, Richard Hamming. Since 1946 Richard Hamming (1915 - 1998) works on a
model of Calculator to Perforated card of low reliability. If, during the week, of the engineers
could correct the errors, the been unemployed periods as the end of the week see the
machines stopping invariably on bugs. Frustration hamming conduit to invent the first truly
effective correct code.
This period corresponds to the birth of the Information theory. Claude Shannon (1916,
2001) formalizes this theory as a branch of mathematics. Hamming develops the premises
of the theory of the codes and described its solution like an example.
In 1960, two mathematicians R.C. Bump, D.K. Ray-Chaudhuri show that ideals of the ring
of the polynomials on the finished bodies of characteristic two are particularly adapted. The
theory is generalized by mathematician A. Hocquenghem and gives rise to the family of
codes BCH. The Hamming codes the binary ones seem codes BCH immediately.
Hamming codes can detect and correct single-bit errors. In other words, the Hamming
distance between the transmitted and received code-words must be zero or one for reliable
communication. Alternatively, it can detect (but not correct) up to two simultaneous bit
errors.
In contrast, the simple parity code cannot correct errors, nor can it be used to detect more
than one error (such as where two bits are transposed).
 Hamming Code work by formula:-
2^k>=n+k+1
Where n = no. of bits entered

K= parity bits
Hamming Code Example

Consider the 7-bit data word "0110101". To demonstrate how Hamming codes are
calculated and used to detect an error, see the tables below. They use d to signify data bits
and p to signify parity bits.
Firstly the data bits are inserted into their appropriate positions and the parity bits
calculated in each case using even parity. The diagram to the right shows which of the four
parity bits cover which data bits.
p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7
Data word (without parity): 0 1 1 0 1 0 1
p1 1 0 1 0 1 1
p2 0 0 1 0 0 1
p3 0 1 1 0
p4 0 1 0 1
Data word (with parity): 1 0 0 0 1 1 0 0 1 0 1
Calculation of Hamming code parity bits
Graphical depiction of the 7 data bits and 4 parity bits and which parity bits apply to
which data bits
Bit position of the data and parity bits
The new data word (with parity bits) is now "10001100101". We now assume the
final bit gets corrupted and turned from 1 to 0. Our new data word is
"10001100100"; and this time when we analyze how the Hamming codes were created we
flag each parity bit as 1 when the even parity check fails.
p1 p2 d1 p3 d2 D3 d4 p4 d5 d6 d7 Parity check Parity bit

Received data word: 1 0 0 0 1 1 0 0 1 0 0
p1 1 0 1 0 1 0 Fail 1
p2 0 0 1 0 0 0 Fail 1
p3 0 1 1 0 Pass 0
p4 0 1 0 0 Fail 1
Checking of parity bits (switched bit highlighted)
Mapping in the example data value. The parity of the red, yellow, green,
and blue circles are even
The final step is to evaluate the value of the parity bits (remembering the bit with lowest
index is the least significant bit, i.e., it goes furthest to the right). The integer value of the
parity bits is 11, signifying that the 11th bit in the data word (including parity bits) is wrong
and needs to be flipped.
p4 P3 p2 p1
Binary 1 0 1 1
Decimal 8 2 1 Σ = 11
A bit error on bit 11 causes bad parity in the red, yellow, and green circles
Flipping the 11th bit changes 10001100100 back into 10001100101. Removing the
Hamming codes gives the original data word of 0110101.
REQUIREMENTS
Hardware Requirements
 256 MB RAM
 40 GB HDD
 ps/2 MOUSE
 KEYBOARD
 PENTIUM 4 PROCESSOR OR HIGHER VERSION
Software Requirements
 Operating System: Linux (It requires K development environment (KDE) )
 Requires stand alone programs i.e. No networking
 Language used: C++

Operating System – LINUX
Linux is the name usually given to any Unix-like computer operating system that uses the
Linux kernel. Linux is one of the most prominent examples of free software and open
source development: typically all underlying source code can be freely modified, used, and
redistributed by anyone.
The name "Linux" comes from the Linux kernel started in 1991 by Linus Torvalds. The
system's utilities and libraries usually come from the GNU operating system, announced in
1983 by Richard Stallman. The GNU contribution is the basis for the alternative name
GNU/Linux.
Predominantly known for its use in servers, Linux is supported by corporations such as
Dell, Hewlett-Packard, IBM, Novrell, Oracle Corporation, Red Hat, and Sun Microsystems.
It is used as an operating system for a wide variety of computer hardware, including
desktop computers, supercomputers, and embedded devices such as E-book readers,
DVRs, video game systems (PlayStation 2, PlayStation 3 and XBox), mobile phones and
routers.
User interface
Linux can be controlled by one or more of a text-based command line interface (CLI),
graphical user interface (GUI) (usually the default for desktop), or through controls on the
device itself (common on embedded machines).
On desktop machines, GNOME, KDE and Xfce are the most popular user interfaces,
though a variety of other user interfaces exist. Most popular user interfaces run on top of
the X Window System (X), which provides network transparency, enabling a graphical
application running on one machine to be displayed and controlled from another.
Other GUIs include X window managers such as FVWM, Enlightenment, Fluxbox and
Window Maker. The window manager provides a means to control the placement and
appearance of individual application windows, and interacts with the X window system.
A Linux system usually provides a command line interface of some sort through a shell,
which is the traditional way of interacting with a Unix system. A Linux distribution
specialized for servers may use the CLI as its only interface. A “headless system” run
without even a monitor can be controlled by the command line via a protocol such as SSH
or telnet.
Most low-level Linux components, including the GNU Userland, use the CLI exclusively.
The CLI is particularly suited for automation of repetitive or delayed tasks, and provides
very simple inter-process communication. A graphical terminal emulator program is often
used to access the CLI from a Linux desktop.
Programming on Linux
Most Linux distributions support dozens of programming languages. The most common
collection of utilities for building both Linux applications and operating system programs is
found within the GNU tool chain, which includes the GNU Compiler Collection (GCC) and
the GNU build system. Amongst others, GCC provides compilers for Ada, C, C++, Java,
and FORTRAN. The Linux kernel itself is written to be compiled with GCC. Proprietary
compilers for Linux include the Intel C++ Compiler and IBM XL C/C++ Compiler.
Most distributions also include support for Perl, Ruby, Python and other dynamic
languages. Examples of languages that are less common, but still well-supported, are C#
via the Mono project, and Scheme. A number of Java Virtual Machines and development
kits run on Linux, including the original Sun Microsystems JVM (HotSpot), and IBM's J2SE
RE, as well as many open-source projects like Kaffe. The two main frameworks for
developing graphical applications are those of GNOME and KDE. These projects are based
on the GTK+ and Qt widget toolkits, respectively, which can also be used independently of
the larger framework. Both support a wide variety of languages. There are a number of
integrated development environments available including Anjuta, Code::Blocks, Eclipse,
KDevelop, Lazarus, MonoDevelopr, Net Beans, and Omnis Studio while the long-
established editors Vim and Emacs remain popular.
C++ in LINUX
Object-Oriented programming is a hot topic in the computer industry these days, and most
experts agree that C++ is the predominant object-oriented programming language. Many
programmers are familiar with the C programming language and would like to move to C++,
but feel they lack the necessary tools and resources, particularly if the training has to be
done on their own time.
It should therefore come as welcome news to learn that Linux makes an ideal platform for
learning C++. This article covers some of the C++ programming tools available under Linux
and refers the reader to additional resources, many of them freely available on the Internet.
Tools
Listed here are a number of useful C++ programming tools. If you use one of the standard
Linux distributions you probably have most of these already, otherwise you can get them
from a major archive site. To save time and disk space, I suggest obtaining the Linux
binaries rather than building them from source.
The standard Linux C++ compiler is GNU g++ from the Free Software Foundation. It
follows the evolving ANSI C++ standard and supports most features found in AT&T's cfront
3.0 compiler, including templates. It does not yet support exceptions.
Unlike cfront, which is a preprocessor, g++ generates native code. As the compiler is
evolving quickly, I recommend getting the latest version. (At the time of writing most Linux
distributions included version 2.5.8; version 2.6.0 had just been released.)
Gdb is the GNU symbolic debugger; you have probably used it already for debugging C
programs under Linux. It supports most C++ data types and language constructs, and
transparently handles C++ “name demangling”. Gdb runs well inside Emacs, or you can
use the xxgdb graphical user interface under X. The documentation for gdb, in info format,
describes the features specific to C++ debugging.
The programmer's editor of choice, Emacs, has a C++ mode that assists in editing. It works
well in conjunction with gdb and g++, allowing you to compile and debug from within the
editor.
Class Libraries
If you want to run any meaningful programs, such as examples from a textbook or code of
your own, you will want some class libraries. A number of C++ class libraries are available
under Linux.
The GNU libg++ library provides the standard C++ iostream class. It also includes a
number of additional useful classes, from complex numbers to general-purpose stack,
queue, and set objects. Since the source is freely available, you can read it to understand
how the libraries were implemented. Libg++ is well documented in the included info pages.
Compilers
At this time, I'm testing two Linux-based C and C++ compilers: GNU's Compiler Collection
(GCC), and Intel's C++ product. GCC is, of course, released under the GNU Public
License, and I own a commercial license for the Intel compiler. I realize that other
commercial compilers exist, but do not own them and, as such, can not test them. If other
compiler vendors wish to be included in these ongoing comparisons, I'd be more than
happy to talk to them.
Gnu’s Compiler Collection
GCC (which includes C, C++, Objective-C, Fortran, and Ada compilers) is arguably the
most important tool for the creation of free software; without a free-as-in-speech and -as-in-
beer compiler, it is unlikely that Linux (and perhaps BSD and OS X) would exist. I have an
abiding interest in the quality of GCC. In all fairness, I do some peripheral work on GCC as
time permits, so I am not an entirely unbiased observer.
Intel's C++ Compiler
Intel produces C, C++, and Fortran 95 compilers for Windows and Linux. Under Linux, the
Intel compilers are available with a non-commercial license, meaning that anyone can
download and use the full compiler for non-profit work. The Intel non-commercial license is
not the same thing as the GNU General Public License (GPL); the Intel compilers are not
"free-as-in-speech" software -- however, they are excellent tools that can be used for
working on free software and non-commercial projects.
Intel's command-line options vary from GCC's, so it won't operate a a drop-in replacement
for the GNU compiler. You can compile the Linux kernel with ICC if you so desire, but I'm
more comfortable sticking with GCC for building Linux-based systems, since that is their
"native" environment
By supporting GCC's extensions to C and C++, the Intel compiler is clearly trying to attract
users to their development tools -- and thus to Intel processors. Intel also offers features
that GCC does not, including OpenMP for simplified parallel programming. If you check
forums dedicated to scientific work, video encoding, or source-based Linux distributions,
you'll likely find people using and talking about Intel's compiler.
To mount an USB Pen Drive/Hard Disk
Attach your USB pendrive to Linux computer.

#dmesg
{Check the last lines. It will show the device name used by pendrive for example
/dev/sda1 or /dev/sdb1)
#mkdir /pendrive
#mount /dev/sdb1 /pendrive
To unmount & remove an USB Pen Drive/Hard Disk from Linux System
#unmount /pendrive
# eject /dev/sdb1 à {Pendrive will stop blinking. Now remove it}
MODULAR DIAGRAM
Modular description
Input Module
 The sender is given the liberty to enter anything from the alphanumeric character
set using a standard keyboard.
 Input from the keyboard is manipulated as ASCII values ranging from 0-255.
Processing Module
 Conversion Module
 Conversion of characters to ASCII code
 Conversion of ASCII codes to Binary numbers
 Input Specifications
Inputs taken from user are elements from Alphanumeric Character

Set
 Output Specifications
Outputs given to Parity Module are message bits in the form of

binary data.
 Parity Introduction module
 Calculation of number & location of parities.
 Calculation of values of parities.
 Formation of information stream.
Inputs taken from Conversion Module are message bits in the form
of binary data.
Outputs given to Transmission Module are the Information bits with

inserted parities.
Transmission Module
 Introduction of errors in the information bit stream.
 Transmission of the corrupted stream to the receiver.
Error Detection Module
 Detection of error positions.
 Reporting the various error position(s) detected.
 Detection Method
 The corrupted error bit(s) are detected by re-computing the

parities.
 The positions detected are passed to next module.
Input taken from Transmission Module is the corrupted information

bit stream.
Output given to Error Correction Module:
 The corrupted information bit stream

 The corrupted bit position(s)
 Error Correction Module
 Correction of Burst errors introduced in the information bit

stream during transmission.
Re-conversion Module
 Conversion of the binary numbers into ASCII codes.
 Conversion of ASCII codes to Characters.
Input taken from Separation Module is the message bit stream.
Output given by the Module is a combination of Alphanumeric

Characters.
Output Module
 The receiver gets a combination of alphanumeric characters which is same as the

input given by the sender.
CODING
#include <iostream.h>
#include <math.h>
main()
{
int alp,k;
do{
cout<<"\n ****************************************************************";
cout<<"\n \n";
cout<<"\n WELCOME TO ERROR DETECTION AND CORRECTION";
cout<<"\n";
cout<<"\n THE PROGRAM USES SINGLE BIT CORRECTION METHOD OF
HAMMING CODES";
cout<<"\n \n";
cout<<"\n ****************************************************************";
cout<<"\n \n \n 1.ALPHABET \n \n 2.NUMERIC \n \n 3.EXIT \n \n ENTER THE
CHOICE::";
cin>> alp;
if(alp==1)
{
int num,err_bito,err_bitn;
int bit[]={0,0,0,0,0,0,0,0,0,0,0,0};
int bits[]={0,0,0,0,0,0,0,0,0,0,0,0};
cout << "\n \n \n THIS IS CHARACTER ERROR DETECTION AND
CORRECTION PROGRAM";
char one_char;
int aq;
cout << "\n \n \n \n Enter any a CHARACTER of upper or lower case: ";
cin >> one_char;
cout << "\n \n The character entered was : " << one_char << '\n';
aq=(int) one_char;
cout << "\n \n Its ASCII value is : " << aq << '\n';
num=aq;
bit[1]=num%2;
int a;
a=num-num%2;
int b=a/2;
bit[2]=b%2;
a=b-b%2;
b=a/2;
bit[3]=b%2;
a=b-b%2;
b=a/2;
bit[4]=b%2;
a=b-b%2;
b=a/2;
bit[5]=b%2;
a=b-b%2;
b=a/2;
bit[6]=b%2;
a=b-b%2;
b=a/2;
bit[7]=b%2;
a=b-b%2;
b=a/2;
bit[8]=b%2;
a=b-b%2;
b=a/2;
bit[9]=b%2;
a=b-b%2;
b=a/2;
bit[10]=b%2;
a=b-b%2;
b=a/2;
bit[11]=b%2;
a=b-b%2;
b=a/2;
cout << "\n \n The equivalent binary data is:";
for( k=11;k>0;k--)
cout << bit[k];
cout << endl;
int r1,r2,r3,r4,r1o,r2o,r3o,r4o,r1n,r2n,r3n,r4n;
r1=r2=r3=r4=r1o=r2o=r3o=r4o=r1n=r2n=r3n=r4n=0;
if(bit[1]==1)
{
r1++;
r2++;
}
if(bit[2]==1)
{
r1++;
r3++;
}
if(bit[3]==1)
{
r2++;
r3++;
}
if(bit[4]==1)
{
r1++;
r2++;
r3++;
}
if(bit[5]==1)
{
r1++;
r4++;
}
if(bit[6]==1)
{
r2++;
r4++;
}
if(bit[7]==1)
{
r1++;
r2++;
r4++;
}
if(bit[8]==1)
{
r3++;
r4++;
}
if(bit[9]==1)
{
r1++;
r3++;
r4++;
}
if(bit[10]==1)
{
r2++;
r3++;
r4++;
}
if(bit[11]==1)
{
r1++;
r2++;
r3++;
r4++;
}
r1o=r1%2;
r2o=r2%2;
r3o=r3%2;
r4o=r4%2;
cout<<"\n \n The REDUNDENT BITS are: ";
cout << r1o << r2o << r3o << r4o << endl;
r1=r2=r3=r4=0;
int tx_data[]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
int rx_data[]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
cout <<"\n \n Data with REDUNDANT BITS are:";
tx_data[15]=bit[11];
cout << tx_data[15];
cout <<tx_data[14];
tx_data[13]=bit[9];
tx_data[12]=bit[8];
tx_data[11]=bit[7];
tx_data[10]=bit[6];
tx_data[9]=bit[5];
cout << tx_data[9];
tx_data[8]=r4o;
cout <<"("<<tx_data[8]<<")";
tx_data[7]=bit[4];
cout << tx_data[7];
tx_data[6]=bit[3];
cout << tx_data[6];
tx_data[5]=bit[2];
cout << tx_data[5];
tx_data[4]=r3o;
cout <<"("<< tx_data[4]<<")";
tx_data[3]=bit[1];
cout << tx_data[3];
tx_data[2]=r2o;
cout <<"("<< tx_data[2]<<")";
tx_data[1]=r1o;
cout <<"("<< tx_data[1]<<")";
cout<<endl;
cout << "\n \n The TRANSMITTED DATA is: ";
for(k=15;k>0;k--)
cout << tx_data[k];
cout << endl;
err_bito=((8*r4o)+(4*r3o)+(2*r2o)+(1*r1o)); // ERROR BIT GENERATED
for(k=15;k>0;k--)
rx_data[k]=tx_data[k];
if(rx_data[err_bito]==1)
rx_data[err_bito]=0;
else
cout << "\n \n The Received DATA WITH ERROR is:";
for(k=15;k>0;k--)
cout << rx_data[k];
cout << endl;
if(rx_data[3]==1)
{
r1++;
r2++;
}
if(rx_data[5]==1)
{
r1++;
r3++;
}
if(rx_data[6]==1)
{
r2++;
r3++;
}
if(rx_data[7]==1)
{
r1++;
r2++;
r3++;
}
if(rx_data[9]==1)
{
r1++;
r4++;
}
if(rx_data[10]==1)
{
r2++;
r4++;
}
if(rx_data[11]==1)
{
r1++;
r2++;
r4++;
}
if(rx_data[12]==1)
{
r3++;
r4++;
}
if(rx_data[13]==1)
{
r1++;
r3++;
r4++;
}
if(rx_data[14]==1)
{
r2++;
r3++;
r4++;
}
if(rx_data[15]==1)
{
r1++;
r2++;
r3++;
r4++;
}
r1n=r1%2;
r2n=r2%2;
r3n=r3%2;
r4n=r4%2;
r1=r2=r3=r4=0;
if(r1o==r1n)
{
if(r2o==r2n)
{
if(r3o==r3n)
{
if(r4o==r4n)
cout << "\n \n No Error" << endl;
else
cout << "\n \n Not Possible" << endl;
}
else
{
if(r4o==r4n)
else
{
err_bitn=12;
cout << "\n \n Error in bit 12" << endl;
}
}
}
else
{
if(r3o==r3n)
{
if(r4o==r4n)
else
{
err_bitn=10;
}
}
else
{
if(r4o==r4n)
{
err_bitn=6;
}
else
{
err_bitn=14;
}
}
}
}
else
{
if(r2o==r2n)
{
if(r3o==r3n)
{
if(r4o==r4n)
else
{
err_bitn=9;
}
}
else
{
if(r4o==r4n)
{
err_bitn=5;
}
else
{
err_bitn=13;
}
}
}
else
{
if(r3o==r3n)
{
if(r4o==r4n)
{
err_bitn=3;
}
else
{
err_bitn=11;
}
}
else
{
if(r4o==r4n)
{
err_bitn=7;
}
else
{
err_bitn=15;
}
}
}
}
if(rx_data[err_bitn]==1)
rx_data[err_bitn]=0;
else
cout << "\n \n The CORRECTED DATA is: ";
for(k=15;k>0;k--)
cout << rx_data[k];
cout << endl;
bits[11]=rx_data[15];
bits[5]=rx_data[9];
bits[4]=rx_data[7];
bits[3]=rx_data[6];
bits[2]=rx_data[5];
bits[1]=rx_data[3];
cout << "\n \n The Received data withot redundant bit is: ";
for(k=11;k>0;k--)
cout << bits[k];
cout << endl;
double x=2;
double number=0;
for(k=11;k>0;k--)
{
double z=0;
z=pow(x, k-1);
double temp=0;
temp=bit[k]*z;
number=number+temp;
}
cout << "\n \n The ALPHABET entered was: " << one_char << endl;
}
else
{
if(alp==2)
{
int num,numb,err_bito,err_bitn;
int bit[]={0,0,0,0,0,0,0,0,0,0,0,0};
int bits[]={0,0,0,0,0,0,0,0,0,0,0,0};
cout << "\n \n THIS NUMERIC ERROR DETECTION AND CORRECTION
PROGRAM" << endl;
cout<<"\n \n
*******************************************************************************";
cout<<"\n -:CAUTION:- ";
cout<<"\n \n SINCE THE PROGRAM HAS BEEN DESIGNED FOR 11BIT
ARRAY,THE PROGRAM WILL NOT ACCEPT ANY VALUES GREATER THAN OR
EQUAL 2048";
cout<<"\n \n
*******************************************************************************";
cout << "\n \n \n Enter any decimal number: ";
cin >> numb;
if(numb<2048)
num=numb;
else
{
cout << "\n" << endl;
cout << "If u carry on u will get erroneous results" <<endl;
}
bit[1]=num%2;
int a;
a=num-num%2;
int b=a/2;
bit[2]=b%2;
a=b-b%2;
b=a/2;
bit[3]=b%2;
a=b-b%2;
b=a/2;
bit[4]=b%2;
a=b-b%2;
b=a/2;
bit[5]=b%2;
a=b-b%2;
b=a/2;
bit[6]=b%2;
a=b-b%2;
b=a/2;
bit[7]=b%2;
a=b-b%2;
b=a/2;
bit[8]=b%2;
a=b-b%2;
b=a/2;
bit[9]=b%2;
a=b-b%2;
b=a/2;
bit[10]=b%2;
a=b-b%2;
b=a/2;
bit[11]=b%2;
a=b-b%2;
b=a/2;
cout << "\n \n The equivalent binary data is:";
for( k=11;k>0;k--)
cout << bit[k];
cout << endl;
int r1,r2,r3,r4,r1o,r2o,r3o,r4o,r1n,r2n,r3n,r4n;
r1=r2=r3=r4=r1o=r2o=r3o=r4o=r1n=r2n=r3n=r4n=0;
if(bit[1]==1)
{
r1++;
r2++;
}
if(bit[2]==1)
{
r1++;
r3++;
}
if(bit[3]==1)
{
r2++;
r3++;
}
if(bit[4]==1)
{
r1++;
r2++;
r3++;
}
if(bit[5]==1)
{
r1++;
r4++;
}
if(bit[6]==1)
{
r2++;
r4++;
}
if(bit[7]==1)
{
r1++;
r2++;
r4++;
}
if(bit[8]==1)
{
r3++;
r4++;
}
if(bit[9]==1)
{
r1++;
r3++;
r4++;
}
if(bit[10]==1)
{
r2++;
r3++;
r4++;
}
if(bit[11]==1)
{
r1++;
r2++;
r3++;
r4++;
}
r1o=r1%2;
r2o=r2%2;
r3o=r3%2;
r4o=r4%2;
cout<<"\n \n The REDUNDENT BITS are: ";
cout << r1o << r2o << r3o << r4o << endl;
r1=r2=r3=r4=0;
int tx_data[]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
int rx_data[]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
cout<<"\n \n Data with REDUNDANTS BITS are:";
cout<< tx_data[15];
cout<< tx_data[14];
tx_data[13]=bit[9];
cout<< tx_data[12];
tx_data[12]=bit[8];
cout<< tx_data[12];
tx_data[11]=bit[7];
cout<< tx_data[11];
tx_data[10]=bit[6];
cout<< tx_data[10];
tx_data[9]=bit[5];
cout<< tx_data[9];
tx_data[8]=r4o;
cout<<"("<< tx_data[8]<<")";
tx_data[7]=bit[4];
cout<< tx_data[7];
tx_data[6]=bit[3];
cout<< tx_data[6];
tx_data[5]=bit[2];
cout<< tx_data[5];
tx_data[4]=r3o;
cout<<"("<< tx_data[4]<<")";
tx_data[3]=bit[1];
cout<< tx_data[3];
tx_data[2]=r2o;
cout<<"("<< tx_data[2]<<")";
tx_data[1]=r1o;
cout<<"("<< tx_data[1]<<")";
cout<<endl;
cout << "\n \n The TRANSMITTED DATA is: ";
for(k=15;k>0;k--)
cout << tx_data[k];
cout << endl;
err_bito=((8*r4o)+(4*r3o)+(2*r2o)+(1*r1o)); // ERROR BIT GENERATED
for(k=15;k>0;k--)
rx_data[k]=tx_data[k];
if(rx_data[err_bito]==1)
else
cout << "\n \n The Received DATA WITH ERROR is:";
for(k=15;k>0;k--)
cout << rx_data[k];
cout << endl;
if(rx_data[3]==1)
{
r1++;
r2++;
}
if(rx_data[5]==1)
{
r1++;
r3++;
}
if(rx_data[6]==1)
{
r2++;
r3++;
}
if(rx_data[7]==1)
{
r1++;
r2++;
r3++;
}
if(rx_data[9]==1)
{
r1++;
r4++;
}
if(rx_data[10]==1)
{
r2++;
r4++;
}
if(rx_data[11]==1)
{
r1++;
r2++;
r4++;
}
if(rx_data[12]==1)
{
r3++;
r4++;
}
if(rx_data[13]==1)
{
r1++;
r3++;
r4++;
}
if(rx_data[14]==1)
{
r2++;
r3++;
r4++;
}
if(rx_data[15]==1)
{
r1++;
r2++;
r3++;
r4++;
}
r1n=r1%2;
r2n=r2%2;
r3n=r3%2;
r4n=r4%2;
r1=r2=r3=r4=0;
if(r1o==r1n)
{
if(r2o==r2n)
{
if(r3o==r3n)
{
if(r4o==r4n)
cout << "\n \n No Error" << endl;
else
}
else
{
if(r4o==r4n)
else
{
err_bitn=12;
}
}
}
else
{
if(r3o==r3n)
{
if(r4o==r4n)
else
{
err_bitn=10;
}
}
else
{
if(r4o==r4n)
{
err_bitn=6;
}
else
{
err_bitn=14;
}
}
}
}
else
{
if(r2o==r2n)
{
if(r3o==r3n)
{
if(r4o==r4n)
else
{
err_bitn=9;
}
}
else
{
if(r4o==r4n)
{
err_bitn=5;
}
else
{
err_bitn=13;
}
}
}
else
{
if(r3o==r3n)
{
if(r4o==r4n)
{
err_bitn=3;
}
else
{
err_bitn=11;
}
}
else
{
if(r4o==r4n)
{
err_bitn=7;
}
else
{
err_bitn=15;
}
}
}
}
if(rx_data[err_bitn]==1)
else
cout << "\n \n The CORRECTED DATA is: ";
for(k=15;k>0;k--)
cout << rx_data[k];
cout << endl;
bits[5]=rx_data[9];
bits[4]=rx_data[7];
bits[3]=rx_data[6];
bits[2]=rx_data[5];
bits[1]=rx_data[3];
cout << "\n \n The Recieved data without redundant bit is: ";
for(k=11;k>0;k--)
cout << bits[k];
cout << endl;
double x=2;
double number=0;
for(k=11;k>0;k--)
{
double z=0;
z=pow(x, k-1);
double temp=0;
temp=bit[k]*z;
number=number+temp;
}
cout << "\n \n The decimal number entered was:" << number << endl;
}
else
{
cout<<"You are quiting from the program";
}
}
}while(alp!=3);
return(0);
}
INTERFACE SCREENSHOTS
Main Interface
Case 1- Character data
Data Insertion
Detecting and Receiving Character Data
Interface Between Case1 And Case2
Case 2- Numeric data
Numeric Data Insertion
Output For Numeric Error Detection & Correction
Case 3: Exit
SCOPE & OBJECTIVES
 Detection & Correction of Burst Errors introduced by noisy channels
 Data can be sent through a noisy environment without corruption.
 It can be used in various communication systems such as mobile

communication, etc.
 Efficient transmission of data (bandwidth efficiency)
 Error Detection Code
 Add redundant check bits to detect bit error in the transmission codes
 Error Correction Codes
 More powerful – not only detecting errors, but also capable of correcting
errors as well
CONCLUSION
 Successful implementation of the Hamming Code Algorithm in the Linux

Environment using the K Develop.
 The application works perfectly for any binary stream of data.
 The errors (single bit errors) are efficiently detected as well as corrected (if any),
that may occur during the transmission of data.
 Using the Hamming algorithm, we can not only detect single bit errors in this
code word, but also correct them
 Fast & simple encoding/decoding algorithms

PROPOSED ENHANCEMENTS
 Implementation of an Encryption-Decryption Algorithm for encryption of files

before sending and their decryption after receiving.
 Implementation of a Compression Algorithm for compression of the files before

sending.
BIBLIOGRAPHY
 BOOKS:
 Modern Digital Electronics, 3rd edition

By: R.P.Jain
 Data Communication and Networking, 2nd edition

By: Behrouz A.Forouzan
 The Complete Reference Linux, 5th edition

By: Richard L.Petersen
 Object Oriented Programming With C++, 2nd edition

By: E Balagurusamy
 ONLINE REFERENCE:
 www.linuxjournal.com
 www.coyotegulch.com
 www.cse.iitk.ac.in
 www.kde.org
 www.wikipedia.org
 www.computing.dcu.ie
 www.thanglong.ece.jhu.edu
 www.speedylook.com/

Error Detection and Correction Using Hamming Code

Uploaded by

Copyright:

Available Formats

Error Detection and Correction Using Hamming Code

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Error Detection and Correction Using Hamming Code

Uploaded by

Copyright:

Available Formats

PROJECT REPORT

ERROR DETECTION AND

7. Scope and Objectives

Open source software has recently attracted a great amount of attention.

Our analysis is essentially static: it does not contemplate neither R&D

As it is clear from this concise discussion, the issue of government intervention

 An error is an unauthorized change in the content that is being sent.

 Error occurs because of transmission impairments — signal gets

Whenever an electromagnetic signal flows from one point to another, it is subjected to

Bits corrupted by burst error

Error detection schemes

A checksum of a message is an arithmetic sum of message code words of a certain word

Cyclic redundancy checks

Hamming distance based checks

Any hash function can be used as a redundancy check.

 Turbo codes DO NOT work at the bit level.

 Turbo codes typically work at the character or symbol level depending on

Original transmitted symbol 1011

 transmit 1011 on carrier wave 1 (CW1)

 transmit 0100 on carrier wave 2 (CW2)

 Do bits polarities of (CW1) <> (CW2)?

 if CW1 == CW2, signal bit error (triggers more complex ECC)

Error Correcting Codes

 Error correcting codes enable data to be sent through a noisy communication

 To accomplish this, the sender appends redundant information to the message.

 Hamming Code work by formula:-

Where n = no. of bits entered

Hamming Code Example

Bit position of the data and parity bits

p1 p2 d1 p3 d2 D3 d4 p4 d5 d6 d7 Parity check Parity bit

 PENTIUM 4 PROCESSOR OR HIGHER VERSION

 Operating System: Linux (It requires K development environment (KDE) )

 Requires stand alone programs i.e. No networking

 Language used: C++

Intel's C++ Compiler

To mount an USB Pen Drive/Hard Disk

Attach your USB pendrive to Linux computer.

 Conversion of characters to ASCII code

 Conversion of ASCII codes to Binary numbers

Inputs taken from user are elements from Alphanumeric Character

Outputs given to Parity Module are message bits in the form of

 Parity Introduction module

 Calculation of number & location of parities.

 Calculation of values of parities.

 Formation of information stream.

Outputs given to Transmission Module are the Information bits with

 Introduction of errors in the information bit stream.

 Transmission of the corrupted stream to the receiver.

Error Detection Module

 Detection of error positions.

 Reporting the various error position(s) detected.

 The corrupted error bit(s) are detected by re-computing the

 The positions detected are passed to next module.

Input taken from Transmission Module is the corrupted information

Output given to Error Correction Module:

 The corrupted information bit stream

 Correction of Burst errors introduced in the information bit

 Conversion of the binary numbers into ASCII codes.