Error detection and correction codes

Error Detection and Correction in Digital Circuits, Parity Bit, Block Parity , Hamming Code

1. Dr. (Mrs.) GargiKhanna
Associate Professor
Electronics & Communication Engg. Deptt..
National Institute of Technology Hamirpur
(HP)
By:-

2. oError detection and correction Codes
oParity codes
oBlock Parity Codes
oHamming codes

3. When the digital information in the binary form is
transmitted from one circuit or system to another circuit or
system an error mayoccur due to interference, noise, etc
Hence, data will be corrupted
This means the signal corresponding to 0 may change to 1
or vice-versa due to presence of noise
Need schemes devised to detect and correct the error

4. •Tomaintaindataintegritybetweentransmitterand
receiver,extrabitormorethanonebitareaddedinthe
data.
•Theseextrabitsallowthedetectionandsometimesthe
correctionoferrorinthedata.
•Thedataalongwiththeextrabit/bitsformthecode
•Codeswhichallowonlyerrordetectionarecallederror
detectingcodesandcodeswhichallowerrordetection
andcorrectionarecallederrordetectingandcorrecting
codes
3

5. Single-bit error
Only 1 bit in the data unit has changed.

6. •A paritybitisusedfor thepurposeofdetecting
errors during transmission of binary information.
•A parity bit is an extra bit included with a binary
message to make the number of 1s either odd(
ODD Parity)oreven (EVEN Parity).
•Themessageincludingtheparitybitis
transmittedandthencheckedatthereceiving
endforerrors.
•Anerrorisdetectedifthecheckedparitydoesnot
matchwiththeonetransmitted.
3

7. Even/odd parity:
is basic method for detecting if an odd number of bits
has been switched by accident.
Odd parity:
The number of 1-bit must add up to an odd number
Even parity:
The number of 1-bit must add up to an even number

8. •Thecircuitthatgeneratestheparitybitinthetransmitter
iscalledaparitygeneratorandthecircuitthatchecksthe
parityinthereceiveriscalledaparitychecker.
•Asageneralruleinthedigitalsystemwherethe
transmissionsystemisrelativelyshort,itmaybeassumed
thatprobabilityofasingle-biterrorissmallandthatofa
double-biterrorandhigherordererrorsisextremely
small.
Theparityerrordetectionsystemdetectsanyoddnumber
oferrors.
However,itcannotdetectevennumberoferrorsassuch
errorswillnotdestroytheparityofthetransmittedgroup
ofbits 8

9. ASCII code may have an extra bit appended to detect
data transmission errors
P = 0if the number of 1s in the character is even, else P
= 1(even parity)
P = 0 if the number of 1s in the character is odd, else P =
1 (odd parity)
If any single bit changes, parity will be wrong at receive
end
Even parityOdd parity
ASCII A = 10000010100000111000001
ASCII T = 101010011010100 01010100

10. Parity bit
Even parity: additional bit
added to make total number of
1’s even.
Odd parity: additional bit added
to make total number of 1’s odd.
Example of odd parity on ASCII
values.Character ASCII Code
0 10110000
1 00110001
. . . . . .
9 10111001
: 10111010
A 11000001
B 11000010
. . . . . .
Z 11011010
[ 01011011
\ 11011100


Parity bits

11. Parity bit can detect odd
number of errors but not even
number of errors.
Example: Assume odd parity,
1001110001(detected)
1001110101(not detected)
Parity bits can also be applied
to a block of data.
CS2100Number Systems and Codes 110110 1
0001 0
1011 0
1111 1
1001 1
0101 0
Column-wise
parity
Row-wise parity

12. Assume we are using even paritywith 7-bit ASCII.
The letter V in 7-bit ASCII is encoded as 01101011.
How will the letter V be transmitted?
Because there are four 1s (an even number), parity is set to
zero.
This would be transmitted as: 01101010.
If we are using anodd parity:
The letter V will be transmitted as 01101011

13. Whenseveralbinarywordsaretransmittedorreceivedin
succession,theresultingcollectionofbitscanberegardedasa
blockofdata,havingrowsandcolumns.
Example:foureightbitwordsinsuccessionforman4x8block.
Paritybitscanthenbeassignedtobothrowsandcolumns.
Thisschemeisknownasblockparity
Itmakesitpossibletocorrectanysingleerroroccurringin
adatawordandtodetectanytwoerrorsinaword.
1
3

15. Sometimes, it is not enough to do error detection. We
may want to correct the errors.
Error correction is expensive. In practice, we may use
only single-bit error correction.
Popular technique: Hamming code.
CS2100Number Systems and Codes 15

17. In the late 1940’s Richard Hamming recognized that
the further evolution of computers required greater
reliability, in particular the ability to not only detect
errors, but correct them. His search for error-
correcting codes led to the Hamming Codes and the
extended Hamming Codes.

18. 18
Hamming Code
Detects single and double-bit errors
Application
Computing
Telecommunication (i.e. networking)
Theory
Using 4 data bits, can generate 3 correction bits
giving a total of 7 bits
Can correct any single bit error

19. Hammingcode…
Data: bit-stream write data in particular sequence
receiver checks Hamming codes, corrects errors
transmit
compute, add hamming code bits to data
Corrected data

20. Hammingcodenotonlyprovidesthedetectionofabit
error,butalsoidentifieswhichbitisinerrorsothatitcan
becorrected.
Thushammingcodeiscallederrordetectingand
correctingcode.
Thecodeusesanumberofparitybits(dependentonthe
numberofinformationbits)locatedatcertainpositionina
group.
Numberofparitybits:
Thenumberofparitybitsdependsonthenumberof
informationbits
Ifthenumberofbitsisdesignatedasx,thenthenumberof
paritybitsPisdeterminedusingtherelation
2
??????
≥ ??????+ ??????+ 1
20

22. Location of the parity bits in a code:
•The parity bits are located in the positions that are
numbered corresponding to ascending powers of
two(1,2,4,8,….).
•Therefore, for 7-bit code, locations for parity bits and
information bits are as follows:
D
4, D
3,D
2,P
3, D
1,P
2,P
1
Assigning values to parity bit:
•In hamming code , each parity bit provides a check on
certain other bits in the total code, therefore we must
know the value of these others in order to assign the
parity bit value.
22

24. Bit Designation D
7D
6 D
5 P
4 D
3 P
2P
1
Bit Location 7 6 5 4 3 2 1
Binary Location
Number
111110101100011010001
Information Bits
Parity Bits
24

26. AssignmentofP
1:
Thisparitybitchecksallbitlocations,thathave1sinthe
samelocationinthebinarylocationnumbers.
AssignmentofP
2:
Thisparitybitchecksallbitlocations,thathave1sinthe
middlebit.
AssignmentofP
3:
Thisparitybitchecksallbitlocations,thathave1sinthe
left-mostbit.
26

30. AssignmentofC
1:
Thisparitybitchecksallbitlocations,thathave1sinthe
samelocationinthebinarylocationnumbers.
AssignmentofC
2:
Thisparitybitchecksallbitlocations,thathave1sinthe
middlebit.
AssignmentofC
4:
Thisparitybitchecksallbitlocations,thathave1sinthe
left-mostbit.
C
4C
2C
1
30