Error Detection and Correction Video Lecture | Electrical Engineering Optional Notes for UPSC

okay another important consideration for
IO interfacing is error detection and
correction because most of the high
devices are connected over the serial
device and if the data is transmitted at
a high rate in that case it is quite
likely that the data which will be read
by the CPU will be erroneous so instead
of giving the error erroneous data it
will be better that if you can detect if
there is any error in the data that has
been read from the device and if
possible to collect the data so there
are different error detection and
correction mechanisms and particularly
error detection mechanism and one of the
mechanism that you already know is the
priority parity bit so by making use of
the parity bit you can determine whether
the data has been read is correct or
there is some error in the data but the
difficulty using parity bit you know
that you can simply detect the error but
you cannot correct it so another kind of
coding technique which can be used for
detection as well as correcting the
error bit is what is called an hamming
code do you know what is Hamming code
the hamming code is something like this
whenever you have a data stream what you
do is into the data stream you introduce
additional bits which are nothing but
writing bits but in this case the parity
bits are generated in slightly different
way than how it is generated in case of
parity code so in case of Hamming code
it is something like this that every bit
position in the bit stream where the
position is
of the form 2 to the power I for some
integer
I will contain a parity bit so I can
take an example like this first this bit
position a bit position 1 is of the form
2 to the PI because 2 triples we don't
gives you 1 that means the first bit
location will be a parity bit it will
not contain a data bit so first bit
location I will put as a parity bit P 1
come to the second bit location to which
is again 2 to the power of 1 so that
will also contain a parity bit that I
will call as P 2 third location it is
not of the form 2 to the God so that
will contain a data bit and let me put
it as D 3 now the subscript indicates
the bit position fourth location which
is 2 to the power 2 again will contain a
parity bit I will put this as P 4 fifth
location which is not 2 to the power I
will contain a data bit that is d5 sixth
location again it is not off to the form
to the power I will contain a data bit
so it is d 6
similarly seventh bit location will
contend d7 because it is not to avoid
8-bit location again to deliver 3 that
will again contain a quite a bit okay so
this way this way it will continue now
d3 d5 d6 d7 they are coming from the bit
streams or data bits tips I have to
generate p1 p2 p4 so let me take this
small example I have to generate p1 p2
and p4 now how do i generate p1 while
generating p1 I consider the binary
representation of the bit locations ok
so in this case the binary
representation of d3 is 0 0 1 1
something like this
okay so when I consider p1 you consider
that p1 is 2 to the power 0 okay so for
generating this p2 to the port 0 at
parity bit
what is the 0f bit in the binary
representation of the location of the
data if that is equal to 1 then all
those data bits will take part along
with the parity bit in generation of the
fertility ok say for example here this
binary representation of d3 is if I put
it in the form of 2 bit 4-bit binary
number 0 0 1 1 this is the zeroth bit in
the binary representation of d3 and 0 if
it is equal to 1 so it's for the
generation of P 2 to the power 0 I'll
consider all those data bits where the
binary representation of the position of
the data bit in the binary
representation of the position of the
data bit the 0 HB 8 is equal to 1 okay
see when I represent the position of any
data base in the form of a binary number
that will contain n number of positional
bits I put this as let me call this as J
0 J 1 J 2 J 3 and so on when I'm coding
this p1 I am generating P 1 P 1 is not
nothing but P of 2 to the power 0 okay
so I will consider all those data bits
for generation of p1 where for which is
a J 0 equal to 1
so what are the beats for which j0 equal
to 1/4 D 3 J 0 equal to 1 4 D 5 J 0
equal to 1 for d70 31 so these bits d3
d5 and d7 along with P 1 will take part
in generation of P 1 ok so let me put it
this way d3 d5 and d7 all these bits
take part in generation of P 1 right
when I generate P 2 P 2 is P 2 to the
power 1 yeah
P 1 also will take part even for
generation say what I need is suppose I
decide that my parity will be odd parity
then odd parity will include P 1 D 3 D 5
D 7 ok whichever way you generate but
when I talk about parity parity in
prospective it
in putting the parity bit what parity
will maintain right now even on the
receiver side I'll listen about this
entire bit stream P 1 P 2 D 3 d 4 D 5 D
67 any of the bits can be an error even
P 1 can be in error so if I don't
consider P 1 in generation of the parity
bit on the receiver side I cannot detect
whether P 1 is in error if you consider
only D 3 D 5 D 7 and without considering
P 1 because at the receiver end I don't
know that whether P 1 is in error or D 3
is in error error or D 5 is in error or
D 7 is in either even P 1 can also be
never okay this one we are talking about
what is the big position of B 3 that is
the third position position p1 XOR with
d3 XOR with d5 XOR with d7 similarly
when I try to generate p2 okay I'll take
all the bits by the beat position when
represented in the form of a binary
number there J 1 has to be equal to 1
because P 2 is P 2 to the power of 1
right so you find that in all these bits
what are the bits for which J 1 equal to
1 for D 3 D 3 J 1 equal to 1 D 5 no D 6
again J 1 equal to 1 D 7 J 1 equal to 1
okay so I will consider these bits D 3 I
will consider these six and I will
consider defect okay then when I
generate P 4 that is P 2 to the power 2
so I will consider all those data bits
for which J 2 is equal to 1 right
so what are those what are those bits
for which J 2 is equal to 1
it is for that allure generating so that
has to come into picture then d5 d6 and
d7
okay so I will call this as say X 0 I'll
call this as check 1
I'll call this as check ok so if I want
what parity in that case when I generate
t1 my requirement should be p1 XOR with
d3 XOR with d5 XOR with d7 that should
be equal to 1 if I want even parity then
p1 XOR with d3 XOR with d5 XOR with d7
should be equal to 0 right similarly
when I generate p2 and if I want to add
parity of course if I want out parity
for p1 I should have out parity for p2
also ok so if I want P to and I decide
for odd parity then P 2 XOR with d3 XOR
with d6 XOR with d7 that should be equal
to 1 ok similarly for p4 it is p4 XOR
with d5 XOR with d6 XOR with d7 that
should be equal to 1 ok so this equation
will tell me that what is P 1 what is P
2 and what is P 4 there is no initial
I have equation p1 XOR with d3 XOR with
d5 XOR with d6 XOR with d7 and not d6 p1
XOR with d3 XOR with d5 and XOR with d7
that should be equal to 1 now you find
that all these bits d3 d5 and d7 they
are known only unknown is p1 I don't
have any other unknown term so this way
I can generate p1 p2 and p4
now when I transmit it on the receiver
side you performs the mineralization and
see whether the parity is maintained or
not ok so on the receiver side if I have
a situation suppose d3 is in error okay
I don't have any other bits in error
only d3 is inherit so on the receiver
side if I perform similar operation then
you will find that these Jake bits will
indicate error where d3 appears okay now
here d3 appears in check zero d3 appears
in check one so only these two checks
will indicate error check 2 will not
indicate any error because d3 does not
participate in check - ok so there if I
put a condition that wherever I make an
error wherever at whichever check level
I get an error I said the corresponding
bit equal to 1 and whatever I don't get
any error the corresponding bit is set
equal to 0 so here since d3 is equal to
is in error
so I'll get Jake level 0 equal to 1
because this gives an error th level 1
will also be equal to 1 because that is
in error check level 0 will give me 0
now if I simply decode this it is 0 1 1
that is equal to 3
so that tells me that bit d3 is in it
and because it is a binary number a
binary bit whenever there is an error I
simply what I have to do is I simply
complement it and I get the correct data
so similarly if suppose d7 is in it if
the seven is in error then all these
check bits will give me error that means
all of them will become equal to 1 so it
is 1 1 1 which is equal to 7 so
immediately tells me that it is d7 which
is in either I can correct it only
person it yeah that is correct
okay so this can detect as well as
correct to a limited extent so it can
detect single bit error correct single
bit error but even that gives a lot of
improvement okay but the advantage over
simple parity check is that in case of
parity check we can just find out
whether the data is in error or not here
I can detect a single bit error I can
also correct this interpretation
okay however both that is the parity
check or the Hamming code this assumes
that I have one if I have one bit error
then I can correct it more than that
again I am helpless I cannot do anything
but generally in a communication system
I mean whether you want to transmit a
data from one place to another place or
you transmitted data from one device to
another device the error comes because
of disturbance and whenever you have a
disturbance it is not a single beta but
a number of successive bits will be in
error in which case these schemes does
not
the secrets affairs let me reduce by
using metric segmentation image that can
be reduced but in computer system what
has become very popular is what is
called a CRC code we RC or cyclic
redundancy check
okay so whenever we talk about cyclic
redundancy check then for every such
coding scheme there is one polynomial
which is called a generating polynomial
and depending upon the different forms
of generating polynomial I can have
different types of codes and in this
case what will be the code length for
this cyclic CRC code length that depends
upon what is the generating polynomial
that you take okay now I'll not go into
any theory of this cyclic redundancy
check now let me say that given a
generating polynomial of a cyclic
redundancy check how you can generate
the C as if it's just a very simple
scheme suppose the jet generating
polynomial of a cyclic redundancy check
is given something like this say X to
the power 16 plus X to the power 12 plus
6 to the power 5 plus 1 okay now this is
a generating polynomial which is used
for a particular kind of CSV code which
is called CC ie TTC RC now there are
different standards the different
standard uses different polynomials
now these powers of X in this generating
polynomial that tells you that where you
have to put an X or gate in a code of
length 16 bits okay so given this
polynomial this polynomial can be
implemented with the help of a set of
shift registers and a number of X
objects is it X to Y or 1500 X to V or
16
okay so here it will be something like
this suppose this is the CSD code which
is implemented by a number of shift
registers so this is b20 this is bit 1
bit 2 bit 3 & 4 at the output of this
after fifth bit I put an excellent
the output of the accelerate goes to the
next shift register okay
and here the beats will be from five to
eleven so b5 b6 b7 b8 b9 b10 and b11
from b11 again it goes to an xor gate
this XOR gate output goes to another
shift register
and here I'll have the remaining bits
be proud
thirteen
b14 and this 15
I've total 16 bits is 0 to 15
total code length is 16 bits so this is
B 0 to B 15 okay now yeah
again I doubt whether it is X to the 15
or X to the 16 I think it is x2 3/16 not
X to the or 15 because you'll find that
for X to the power 5 I am taking the
output from v4 that goes to an input of
the X of it similarly for X to the power
16 this is output of B 15 which will go
to the input of an xor gate okay and in
this case the xor gate will be placed
here output of this goes to the input of
an xor gate here I'll feed the data okay
and this output will be connected to B 0
and also to the other inputs of two
other exits
oh no sorry this these imports will not
come from here these inputs will come
from this place
okay
the final output is the content of all
these shift registers that is your CSE
code so find that the powers of X that
indicate that at which locations in this
set of shift registers I should place an
excellent similarly I can have other
polynomials for example a CRC 12 that
uses a polynomial of X to the power 12
plus X to the power 3 plus X plus 1 this
is the polynomial for CRC 12 yeah there
are some standard for gap now again in
this CRC code you'll find that distance
simply detect an error error correction
is not possibly lúcia support so in this
case whenever an error is detected
simply the transmitter has to be
informed that this chunk of data is
their onus it will transmit that chunk
of data that's all this does not have
any power of correcting their data use
the ASD
it signals a bit sequence that you want
to commit that will come to this data
input one after another in the sequence
in which they will be transmitted okay
output is the content of all the shift
registers all these bits gives you the
CSD phone so it should be like this that
after you send all the data bits the
data bits are being sent simultaneously
it is also pushed into this same set of
shift registers following this logic so
after all the data bits are transmitted
you have to transmit or in our case it
has to be stored on the device okay so
after for storing these data bits you
have to store all the bits which are
there in the shift register that gives
you the CSE code data is the actual data
that I want to transmit suppose I want
to transmit a data stream something like
this 1 0 1 1 1 0 0 so when I want to
transmit this first I will transmit 1 I
will transmit 1 simultaneously this or
one will be pushed into this set of
shift registers following this logic
then I want to transmit 0 ok so when I
have pushed this one in this sheet of
shift registers this bit combinations
are different different from what it had
it was earlier now I am transmitting 0
so i'm antinea sleezy row is also being
pushed into this then I am transmitting
1 simultaneously 1 is also pushed into
this now whenever I push a new bit in
this that is combined with the previous
state of the shift registers and the new
state is being stored so finally when
this last 0 has been transmitted this 0
was also pushed into shift register so
when this last a 0 is transmitted at
that time this shift register content
will be something
now what is that something that depends
upon how this XOR gates have been placed
and whatever is the content of this that
gives you the CRC code for this
particular bit string right so at the
receiver side I have to regenerate the
CRC code then check whether the CRC code
which is being transmitted and the
Celestra code which is being generated
there same or not if they're same I
assume that the data that have received
is correct if they're not same then I
have to assume that the data that have
received is not correct now this not
correct does not mean that only that
data is erroneous even the CRC code
itself can be erroneous because error
might have occurred in the CRC code it
might not have occurred in the data
right but when I'm regenerating CRC code
because my data is correct I will
generate the correct sphere support but
the CRC code that I am receiving that is
erroneous so again there will be a
mismatch but I don't have any way to
find out whether the error has occurred
in the data weights or thyroid has
operated in the cs6 so I assume that the
whole thing is irani erroneous so I
asked the transmitter to retransmit the
integrity even accidentally it may so
happen that even if your data bits are
wrong that's the SE code that you have
generated accidentally matches with the
CRC code that you have received but in
that case you don't have any other way
you have to accept
otherwise how can you check and actually
the CRC is used in when you store is set
of data on a disk see in every sector I
stored the data in the form of midstream
okay so initially the bitstream will be
stored followed by the CSC code so for
every sector I have the data bits
followed by I may decide that after say
50 bits I'll transmit the cr6 I may
decide after thousand pairs I will
transmit fair CRC bits that is up to the
designer depends upon what is the
content of the data for every bits team
you have an inaccessible yeah but again
this report can simply detect and
accidentally it may not detect also but
that yes
all zeroes right
so in summary let us see what all we
have done in this course yeah people are
trying for it which the exit cannot be
done cannot you cannot correctly see the
advantage of CSS it takes care it
generates the code by considering a
chunk of data Hamming code considers a
simple bit not a chunk so if s no that
is why your chunk of data which is to be
generated for which is the ASCII code
has to be generated should be much
larger than the CRC code if I go for is
the SC code of 16 bits maybe my data
length should be 1 kilo bits
again economy economy should be them as
your head unit yeah so that your data
length along with the CRC code that
should give you a complete packet there
can be 12 reports and usually 12 8 or 16
weeks so if I go for this year see my
data links should be much much larger
than that okay so maybe I should go for
say one to Dobie survey the 16-bit CSV
for one kilo bits of it something like
that otherwise it will not become one
kilobyte plastics 10 bit CSS generated
for a block of data
okay yeah so your data stream along with
GRC will form a packet so that data
packet is doing right
so in summary let us see what all we
have done in this course initially we
have started with the CPU design right
we have started with CPU design and the
specific aspect of CPU design that we
have done in an elaborate way that is
the timing and control circuit design
right and along it this timing and
control circuit we have seen that what
is Hardware control unit and what is a
micro program control
okay
after this we have seen that what is
pipelining and pipeline CPU
then when we discussed about this
pipelining pipelining concept we also
have talked about something like
collision vector that differ that
decides that how the pipeline scheduling
has to be done that means what are the
time instants when a new job can be
placed into a plan into a pipeline that
will not relate to echinacea lead to any
collision okay and we have seen that
that concept is particularly important
when I have multi function pipeline
right so after doing this we had gone to
memory hierarchy doesn't it so the next
thing that we have done is the main
memory organization
and in this we have seen the evolution
of different memory organization our
memory architectures then finally what
we had talked about is what is called a
jet segmented memory management well
your basic memory management or basic
memory organization is the paging
organization and on top of paging we
have imposed sorry the basic memory
organization is the segmented memory
organization and on top of segmentation
we have imposed a paging technique for
better memory management is of memory
man and after main memory organization I
think what we had done is cache memory
rate
and there we have seen different models
of cache memory
starting with associative memory and
direct macro memory and also what is
called set associative memory so we have
said that the associative cache memory
is more flexible but at the cost of
additional Hardware on the other extreme
we had the direct mapped cache memory
where the harder is minimum but at the
same time there is a possibility that
you will have more number of cache miss
so a compromise between these two that
is less Hardware at the same time I want
to have more number of cache hits so
that is given by what we have said about
the set associative cache memory so that
the blocks in the cache memory had
partitioned into different sets and
within a set it is associative so after
cache memory the next topic that we have
discussed is I think buffer cache which
we have said that it is an interface
between the secondary storage device
particularly the devices which are
blocked storage device so it is an
interface between the block storage
device and the main memory and the
buffer cache is maintained in the main
memory and for management of the buffer
cache or replacement of a buffer cache
contains the policy that is used is
least recently used policy okay after
that we have discussed about the file
system
and when it discussed about the file
system we have talked about what is
meant by an inode or an index node of an
file we have said that all the
information about the file is contained
in the inode including the disk blocks
which contain the file data okay then we
have discussed algorithms of inode
allocation at the same time we have also
discussed about the block allocation
right and then finally today what we
have discussed is about the input/output
subsystem and the issues related to
input/output subsystems so this forms
our entire course