fraction of processor time consumed =k/t when
interrupt is generated every t sec and takes k sec to process interrupt
|------------t-----------|----k-----|
If DMA steals 1 cycle every k msec then
fraction CPU slow down is 1/k
Problem A microprocessor scans output I/O device every 20ms There are two interface ports status and output.Instruction takes 12 clock cycles.If clock is 8Mhz how long does it take to scan and service device.
Solution To check the status one instruction to read the status register, One instruction to verify content of register that is if ready or not and one more instruction if ready to feed data to device
each instruction takes (12*1)/(8*10^-6)=1.5microsec
so total of 3 instruction would take 4.5microsec
Problem If character is input in keyboard character buffer each k msec what should be scan rate
Scan should be done atleast 1 every k msec
Problem Average number of commands entered through keyboard is 60 per 8hr
If keyboard is scanned every 100ms then
1)number of times CPU scanned in 8hr?
2)number of scan if interrupt driven I/o is used
3)fraction
Solution 10 scan every sec so in 8hr its 8*60*60*10 scans
In interrupt driven I/O interrupt would be generated for each command so 60 interrupts
Problem Interrupt I/o is used on system with average 8KB/s transfer rate
1)if interrupt processing takes 100microsec. what fraction of time is consumed by i/o device if it interrupts for each byte
in a second it would interrupt 8000 times per sec or 1/8000 =1 every 125microsec
if each interrupt takes 100microsec
fraction = 100/125
2) if device has 2 16byte bufer and interrupts the cpu after one buffer is full It takes 8microsec to transfer each byte then
it interrupts 8K/16B times that is 500 times every sec or 1 times every 2000microsec
100microsec for interrupt processing + 16*8microsec for transfer of each chracter
Monday, March 15, 2010
Digital Logic Part I
Boolean Logic
1) when u have sum form (a+b)
u can convert it to product of sum by multiplying by one
(a+b).1 = (a+b).(a+a') or
(a+b).(b+b')
since a+a' = 1
and a.1 =a
2)when in product form convert to sum of product by
adding 0
since xx' = 0 and a+0 = a
use duality principle to solve if not able to proceed
3)x+xy = x
4) x(x+y) =x by duality
Boolean functions
combination of any terms in n variables
table formed for boolean function has 2^n entries for n variables
A literal is primed or unprimed variable
Cannonical and standard forms
if there are two variables and each can appear in either its normal or compliement form in AND operations
each term will represent distinct region in venn diagram and are called minterms or standard product
So from n variable we can have 2^n minterms each variable has to appear and can be in either normal or complement
in OR term they are called maxterms or standard sum
like
000 ---x'y'z'------m0----------x+y+z--------M0(compliment of minterm)
numbered m0 to m^7 for three variables
writing function in term of minterm
if the value of minterm is 1 in the truth table for the function
we include that in the sum of product form for function
F = x'y'z'+z'yz..
How many boolean functions for n variables
since there are 2^n minterms and each minterm can be either present or not so
there are 2^(2^n) functions
Converting boolean function into sum of minterms
1) by algebric manipulation
If it doesnot contains any variable AND it with x+x' which is 1
example
F=A+B'C
first term missing B and C so
A(B+B')(C+C')
useful properties here
x+x' =1
x+x =x
2)from truth table
Expressing function as product of maxterms
first bring in to OR terms form using distributive property
like
xy+x'z then (xy+x')(xy+z)
if term is missing any variable use the property xx'=0
Conversion between cannonical forms
compliment of one form gives another form using the property that mj'=Mj
that is if F is sum( 1 3 4 6) then F in product(0 2 5 7)
Standard form
number of literals may vary either product of sum or sum of product
What it means to have 2^n functions
Each 2^n functions on n variable represents one of the operator
for example for two literals there are 16 possible function and
AND and OR are just 2 of them
example
equivalence conidtion that y and x should be equal
xy+x'y'
Logic Gates
Nand is 'not and' (xy)', that is false only when both true
Nor : (x+y)' , true only when both false
OR
associative (a+b)+c = a+(b+c) =a+b+c
and commutative a+b =b+a
Nand and Nor are not associative
Minimizing Boolean Expressions
In boolean map minterms are arranged not in binary sequence but sequence similar to gray code, only single bit changes in the sequence
How we reduce Karnaugh map
m5+m7 = xy'z+xyz = xz
that is two square differ in only single term so we reduced them that is any two minterms in the adjacent squares that are ORed together will cause removal f the different variable
when all the squares are included in the map it gives 1
Prime Implicants
If any term is removed from the implicant it does not implies F
or
Product term obtained by combining the maximum possible number of adjacent squares in the map
Distinguished 1 cell: mplicant that is covered by 1 prime implicant or 1's circled by only 1 prime implicant
essential prime implicant : implicant included in one or more distinguished 1 cell
prime implicants help determining the alternative representations
Minimal sum always contains essential prime implicants
http://web.cecs.pdx.edu/~mcnames/ECE171/Lectures/Lecture10.html
Product of sum simplification
1)If we combine 0's in the Karnaugh map we obtain compliment F' in sum of product
2)If we compliment it again we obtain product of sum form
1's in function F truth table represents minterm and 0's represent max terms
if we combine zero's we obtain complimented form F'
How to represent product of sum form in Karnaugh map
find the complement of function F
then represent 0's for minterms obtained from F' and remaining ones
Don't care conditions
when function is not specified for certain conditions
Nand and Nor implementation
Nand with inverted OR logic
First convert in to sum of product form
replace and with nand and or with invert or
Two level Nand
the sum of product can be converted in to two level NAND logic in direct way
to implement completely in NAND use one input NAND to invert the input
Nor implementation
requires product of sum of form
Combinational Circuit
Half adder
performs addition of two bits (doesnot adds carry the third bit)
two inputs, two outputs
S= x'y+xy' this is XOR opeartion
C=xy
Convert it into product of sum form by adding xx' and yy'
S= x'y+xx'+xy'+yy' = (x+y)(x'+y')
we can represent C in compliment form as C' = x'+y' and complement is C = (x'+y')'
if we use three level implementation we can get S' with combining zero's that is xy+x'y' and use an invert to get S = (xy+x'y')' = S(C+x'y')
Full Adder
three inputs two outputs(third is for carry)
S= x'y'z+x'yz'+xy'z'+xyz (example where no implicants can be grouped )
C= xy+xz+yz
Implement with Half adder
S+ x'(y'z+yz')+ x(yz+y'z')
Note: we derived previously xy'+x'y = (xy+x'y')'
so, S= x xor (y xor Cin)
C= xy + Cin . (xy'+x'y) = xy + Cin .(x XOR y)
or
C = xy XOR Cin.(x XOR y)
Subtractor
two input two outputs
Borrow B is 0 when x>=y
only when x
D is arithemetic operation 2B+(x-y)
D=x'y+xy' same as half adder
B=x'y
Full subtractor
Code conversions
BCD is used to represent numbers from 0 to 9
conversion of BCD to excess 3
that is 0 in BCD would be 3 in excess-3 and
9 will be 12 in excess-3
find the minimized karnaugh map from truth table
Implementation with NAND gate
Nand uses same number of gates as implemented with AND OR in general case
when last of the gate in AND-OR is AND then we need one extra NAND in corresponding NAND implementation to invert the final output or
Any invert symbol inserted that is not compensated by inserting another bubble needs an extra invert
Converting NAND to AND-OR
first convert the last NAND into invert or and then change each alternate
At last each invert OR is OR and each NAND is AND in corresponding AND-OR
Change from NOR to AND OR
we use invert AND for AND and OR invert for OR in NOR implementation so here we do reverse
we change last level to invert AND and other alternatively
Odd function and XOR
Binary Adder
we saw half adder and full adder that sums two and three bits respectively To sum binary number
We would need n full adder for n bit binary addition
Carry of full adder is feed to next full adder as its input symbol
Can be generated in either serial or parallel
Binary parallel adder
all inputs are applied at once
since there are 9 inputs 8 addend and augend and 1 carry input, it requires 2^9 truth table entries
it has 4 sum bits +1 carry outputs
4bit Adder Subtractor
A-B = A+2's compliment of B
take 1's compliment B with inverter and add 1 by carry input
we can use XOR to control the addition or subtraction with M
M XOR B = B when M=0 and
M xor B = B' when M =1
Carry propagation
Ci in full adder propagates through an AND and OR gate to give Ci+1
If there are four full adders in parallel output carry C5 would have 2*4 gate levels
For an n bit parallel adder there are 2n gate levels for carry to propagate
to reduce the carry propagation time Look Ahead carry generator
we find carry in terms of
P = A xor B
G=AB the sum
S= P xor Ci
Ci+1 = Gi +PiCi
Gi is carry generate and produces carry =1 when both A and B are 1 regardless of carry
Pi is carry propogate
C2 = G1 + P1C1
C3=G2+P2C2 = G
BCD Adder
Decoder and Encoders
Decode : Consider output to be decimal number then for n bit it can have 2^n possible outputs or
generates all possible minterms of n
output will be active on any one of the the 2^n output lines
for n to m decoder
number of outputs m <= 2^n
Problem 5 to 32 bit decoder from 2 to 4 and 3 to 8 decoders
we give the two higher bit input to first level 2*4 decoder which selects one of the 4 3x8 decoders
the reset three lower bits will be input to 3x8 decoders
Problem 1. How many 2 to 4 decoders will be required to make 4 to 16 decoder
Solution
=> cascaded decoder
=> Since decoder generates 1 on only one of the 2^n possible output lines
=> 4 x 2 to 4 decoders are required to get the final output and one 2 to 4 decoder required to decode the enable input
Similarly how many 3to8 decoders will be needed for 4to64 decoder
8 x 3to8 decoders to get the final result of 64 output and one 3to8 decoder to generate enable input for second stage decoders so intotal 9 decoders are required
Demultiplexer
Decoder with an enable input acts as multiplexer
receives input on single line and transmits it on to one of the 2^n possible output lines
selection of output line is done by n selection lines
Encoder
performs inverse operation of decoder
Consider input to be a decimal number represented as n bit and output to be its binary form
2^n input lines and n output lines
two problems
1)only single input can be active else would give incorrect result so establish priority
2)when no input is give and when input at D0 is given both gives the same output of all 0's
specify an additional condition
Priority Encoder
Multiplexer
Its oppossite of demultiplexer that is it chooses input from any one of the 2^n possible input lines and sends output to single line
selection lines are used to select particular input
2-1 Multiplexer
inputs =2 selector =1
when S=0 I0 is connected to output and
when S=1 I1 is connected to output
Equation
Z= AS'+BS that is on S=0 A is selected and on S=1 B is selected
Implementation would need two AND gates 1 OR gate and an Inverter
4-1 Multiplexer
inputs=4 selection = log(4)=2
Equation
Z= AS(0)'S(1)' + B S(0)'S(1)+CS(0)S(1)'+DS(0)S(1)' that is
A is selected on selection 00 , B is selected on selection 01 and ..
Implementation : use 2 to 4 decoder for selection line,4 AND gates and 1 OR gate
Problem Design 32-1 Mux using 8-1 Mux
1)Final level selection lines 3 and 4 of mux is used to do the selection between 4 8x1 mux and each 8x1 mux do the selection among one of the 8 input lines with 012 selection lines
total 5 8x1 mux are used to design
Implementing Boolean function with Decoder
Decoder needs to have as many input lines as number of variables
Number of inputs for OR are equal to number of minterms and if NOR is used to implement (F')' number of inputs to NOR are equal to number of max terms in the function
Problem what is minimum number of inputs required for second level gate in implementation of below function with decoder and logic gates
Sum(0 2 5 6 7)
Solution
number of min terms are 5 and max terms are 3
If we implement with min terms we would need OR with 5 inputs and
If we implement by max terms that is we get F' from decoder and then NOR it we get F we would need 3 input NOR gate
Output in max terms when implemented with two input gates we can use inverter and AND gate
example if ABC' AB'C' are only max terms we know that output of decoder in maxterms is F'
F' = (ABC' + AB'C')
F = (ABC' + AB'C')' // with NOR (or invert)
which is equal to invert AND like NOR's OR invert
that is F' = (A'+B'+C)(A'+B+C) // with NOR (invert and)
that is take each output of max term from decoder Invert it and AND it
Problem Implement F1 =sum(0 2 3 5 7) and F2=sum(0 1 3 4 5 7 ) with decoder and two input I/N/OR logic gates
Solution
We would need single 3 to 8 decoder
Since for f1 and f2 both number of max are less than number of minterms we immplement with max terms
f1 max terms are (1 4 6 ) and f2 has (2 6)
we invert all outputs and take their AND with two input AND gate
Implementing Boolean function with Mux
Since each mux gives single output we need one mux to implement each boolean function
2^n x 1 to implement n variable function
Each input line corresponding to minterm is made 1 and others as zero
Another method that can be used to implement n+1 variable function with 2^n x 1 mux
out of n+1 variables n are connected to n selection line and single is used with input line
Implement 3 variable function f= sum(2 4 7)with 4 to 1 mux
2 selection lines 4 inputs
1)determine the truth table of boolean function
2)higher order variable connected to higher order lines B to S0 and C to S1
3)If no minterm in that column place 0 at bottom
if both minterms in that column present in function place 1 below it
if only one is highlighted corresponding variable is written below it
If we chose C as the input then table would be like
Problem implement f=product(1 2 5) with suitable mux
Solution Find corresponding minterms, write truth table and then similar way find the inputs for
ROM
include both decoder and OR gates within single IC
stores permanent binary information
n inputs called address and m output called word
there are 2^n words stored in the unit each addressed by 2^n minterms of n input variables
each word is of m bits appears on m output lines
Notation to represent ROM is 2^n x m (2^n words and each m bit word) this is also total number of bits
Example 32x8 ROM has 32 words of 8 bit each
another notation is kbits ROM that is k is total number of bits in the ROM
it may be 512*4
ROM internals
combinational with AND gate connected as decoder and number of OR equal to number of output in the unit
In 32x4 ROM 5 input variables are decoded into 32 lines by means of 32 AND and 5 inverters each output of the decoder is one min term Each address selects one and only one output from decoder
Implementing Combination ckt with ROM
for n input m output combinational ckt 2^n x m ROM is required
RAM
n data input lines, n data output lines, k address lines, two control inputs
same like ROM its specified with number of words it contains and number of bits in each word or
total number of bits in the RAM
words are addresses that is there could be address for 16 bits
example 1K x 16 memory has 2^10 words of 16 bits each
Static RAM
internal flip flops stores binary information
valid as long as powered
easy to use and shorter read/write cycles
Dynamic RAM
stores binary information as electric charges applied to capacitor
capcitor discharges with time and need to be refreshed for recharging
charge on each word has to refreshed each milliseconds
reduced power consumption compared to SRAM and large storage
Memory Decoding
to select memory word based on input address
number of storage cells = number of word*bits perword, that is, for each bit
a binary cell stores single bit in its flipflop, it has three inputs and one o/p,operates without clock
1 read/write line,1 address line ,1 data output line and 1 data o/p line for each cell
Array of RAM chips
each bit increased in the address length increases the number of word by factor of 2
and to increases the bits/word data input and o/p lines need to be increased
Increasing number of words
Constructing 4K x 8 RAM from 1K x 8 RAM
data lines 8 input and 8 o/p each goes to all chips
address lines required are 12 Least 10 are applied to all 4 1Kx8 RAM and two most significant are applied to the decoder and o/p of decoder applied to selector line of RAM
Increasing number of bits
Construct 1Kx16 RAM from 1Kx8 RAM
http://www.mil.ufl.edu/3701/
http://www.utdallas.edu/~dodge/EE2310/
http://www.ece.uidaho.edu/ee/digital/donohoe/ECE240/
http://www.ics.uci.edu/~mghodrat/ics151/
Reference
http://inst.eecs.berkeley.edu/~cs150/fa08/Calendar.htm //problem
1) when u have sum form (a+b)
u can convert it to product of sum by multiplying by one
(a+b).1 = (a+b).(a+a') or
(a+b).(b+b')
since a+a' = 1
and a.1 =a
2)when in product form convert to sum of product by
adding 0
since xx' = 0 and a+0 = a
use duality principle to solve if not able to proceed
3)x+xy = x
4) x(x+y) =x by duality
Boolean functions
combination of any terms in n variables
table formed for boolean function has 2^n entries for n variables
A literal is primed or unprimed variable
Cannonical and standard forms
if there are two variables and each can appear in either its normal or compliement form in AND operations
each term will represent distinct region in venn diagram and are called minterms or standard product
So from n variable we can have 2^n minterms each variable has to appear and can be in either normal or complement
in OR term they are called maxterms or standard sum
like
000 ---x'y'z'------m0----------x+y+z--------M0(compliment of minterm)
numbered m0 to m^7 for three variables
writing function in term of minterm
if the value of minterm is 1 in the truth table for the function
we include that in the sum of product form for function
F = x'y'z'+z'yz..
How many boolean functions for n variables
since there are 2^n minterms and each minterm can be either present or not so
there are 2^(2^n) functions
Converting boolean function into sum of minterms
1) by algebric manipulation
If it doesnot contains any variable AND it with x+x' which is 1
example
F=A+B'C
first term missing B and C so
A(B+B')(C+C')
useful properties here
x+x' =1
x+x =x
2)from truth table
Expressing function as product of maxterms
first bring in to OR terms form using distributive property
like
xy+x'z then (xy+x')(xy+z)
if term is missing any variable use the property xx'=0
Conversion between cannonical forms
compliment of one form gives another form using the property that mj'=Mj
that is if F is sum( 1 3 4 6) then F in product(0 2 5 7)
Standard form
number of literals may vary either product of sum or sum of product
What it means to have 2^n functions
Each 2^n functions on n variable represents one of the operator
for example for two literals there are 16 possible function and
AND and OR are just 2 of them
example
equivalence conidtion that y and x should be equal
xy+x'y'
Logic Gates
Nand is 'not and' (xy)', that is false only when both true
Nor : (x+y)' , true only when both false
OR
associative (a+b)+c = a+(b+c) =a+b+c
and commutative a+b =b+a
Nand and Nor are not associative
Minimizing Boolean Expressions
In boolean map minterms are arranged not in binary sequence but sequence similar to gray code, only single bit changes in the sequence
How we reduce Karnaugh map
m5+m7 = xy'z+xyz = xz
that is two square differ in only single term so we reduced them that is any two minterms in the adjacent squares that are ORed together will cause removal f the different variable
when all the squares are included in the map it gives 1
Prime Implicants
If any term is removed from the implicant it does not implies F
or
Product term obtained by combining the maximum possible number of adjacent squares in the map
Distinguished 1 cell: mplicant that is covered by 1 prime implicant or 1's circled by only 1 prime implicant
essential prime implicant : implicant included in one or more distinguished 1 cell
prime implicants help determining the alternative representations
Minimal sum always contains essential prime implicants
http://web.cecs.pdx.edu/~mcnames/ECE171/Lectures/Lecture10.html
Product of sum simplification
1)If we combine 0's in the Karnaugh map we obtain compliment F' in sum of product
2)If we compliment it again we obtain product of sum form
1's in function F truth table represents minterm and 0's represent max terms
if we combine zero's we obtain complimented form F'
How to represent product of sum form in Karnaugh map
find the complement of function F
then represent 0's for minterms obtained from F' and remaining ones
Don't care conditions
when function is not specified for certain conditions
Nand and Nor implementation
Nand with inverted OR logic
First convert in to sum of product form
replace and with nand and or with invert or
Two level Nand
the sum of product can be converted in to two level NAND logic in direct way
to implement completely in NAND use one input NAND to invert the input
Nor implementation
requires product of sum of form
Combinational Circuit
Half adder
performs addition of two bits (doesnot adds carry the third bit)
two inputs, two outputs
S= x'y+xy' this is XOR opeartion
C=xy
Convert it into product of sum form by adding xx' and yy'
S= x'y+xx'+xy'+yy' = (x+y)(x'+y')
we can represent C in compliment form as C' = x'+y' and complement is C = (x'+y')'
if we use three level implementation we can get S' with combining zero's that is xy+x'y' and use an invert to get S = (xy+x'y')' = S(C+x'y')
Full Adder
three inputs two outputs(third is for carry)
C= xy+xz+yz
Implement with Half adder
S+ x'(y'z+yz')+ x(yz+y'z')
Note: we derived previously xy'+x'y = (xy+x'y')'
so, S= x xor (y xor Cin)
C= xy + Cin . (xy'+x'y) = xy + Cin .(x XOR y)
or
C = xy XOR Cin.(x XOR y)
Subtractor
two input two outputs
Borrow B is 0 when x>=y
only when x
D is arithemetic operation 2B+(x-y)
D=x'y+xy' same as half adder
B=x'y
Full subtractor
Code conversions
BCD is used to represent numbers from 0 to 9
conversion of BCD to excess 3
that is 0 in BCD would be 3 in excess-3 and
9 will be 12 in excess-3
find the minimized karnaugh map from truth table
Implementation with NAND gate
Nand uses same number of gates as implemented with AND OR in general case
when last of the gate in AND-OR is AND then we need one extra NAND in corresponding NAND implementation to invert the final output or
Any invert symbol inserted that is not compensated by inserting another bubble needs an extra invert
Converting NAND to AND-OR
first convert the last NAND into invert or and then change each alternate
At last each invert OR is OR and each NAND is AND in corresponding AND-OR
Change from NOR to AND OR
we use invert AND for AND and OR invert for OR in NOR implementation so here we do reverse
we change last level to invert AND and other alternatively
Odd function and XOR
Binary Adder
we saw half adder and full adder that sums two and three bits respectively To sum binary number
We would need n full adder for n bit binary addition
Carry of full adder is feed to next full adder as its input symbol
Can be generated in either serial or parallel
Binary parallel adder
all inputs are applied at once
since there are 9 inputs 8 addend and augend and 1 carry input, it requires 2^9 truth table entries
it has 4 sum bits +1 carry outputs
4bit Adder Subtractor
A-B = A+2's compliment of B
take 1's compliment B with inverter and add 1 by carry input
we can use XOR to control the addition or subtraction with M
M XOR B = B when M=0 and
M xor B = B' when M =1
Carry propagation
Ci in full adder propagates through an AND and OR gate to give Ci+1
If there are four full adders in parallel output carry C5 would have 2*4 gate levels
For an n bit parallel adder there are 2n gate levels for carry to propagate
to reduce the carry propagation time Look Ahead carry generator
we find carry in terms of
P = A xor B
G=AB the sum
S= P xor Ci
Ci+1 = Gi +PiCi
Gi is carry generate and produces carry =1 when both A and B are 1 regardless of carry
Pi is carry propogate
C2 = G1 + P1C1
C3=G2+P2C2 = G
BCD Adder
Decoder and Encoders
Decode : Consider output to be decimal number then for n bit it can have 2^n possible outputs or
generates all possible minterms of n
output will be active on any one of the the 2^n output lines
for n to m decoder
number of outputs m <= 2^n
Problem 5 to 32 bit decoder from 2 to 4 and 3 to 8 decoders
the reset three lower bits will be input to 3x8 decoders
Problem 1. How many 2 to 4 decoders will be required to make 4 to 16 decoder
Solution
=> cascaded decoder
=> Since decoder generates 1 on only one of the 2^n possible output lines
=> 4 x 2 to 4 decoders are required to get the final output and one 2 to 4 decoder required to decode the enable input
 |
| 4to16 decoded from 5 2to4 decoders |
8 x 3to8 decoders to get the final result of 64 output and one 3to8 decoder to generate enable input for second stage decoders so intotal 9 decoders are required
Demultiplexer
Decoder with an enable input acts as multiplexer
receives input on single line and transmits it on to one of the 2^n possible output lines
selection of output line is done by n selection lines
Encoder
performs inverse operation of decoder
Consider input to be a decimal number represented as n bit and output to be its binary form
2^n input lines and n output lines
two problems
1)only single input can be active else would give incorrect result so establish priority
2)when no input is give and when input at D0 is given both gives the same output of all 0's
specify an additional condition
Priority Encoder
Multiplexer
Its oppossite of demultiplexer that is it chooses input from any one of the 2^n possible input lines and sends output to single line
selection lines are used to select particular input
2-1 Multiplexer
inputs =2 selector =1
when S=0 I0 is connected to output and
when S=1 I1 is connected to output
Equation
Z= AS'+BS that is on S=0 A is selected and on S=1 B is selected
Implementation would need two AND gates 1 OR gate and an Inverter
4-1 Multiplexer
inputs=4 selection = log(4)=2
Equation
Z= AS(0)'S(1)' + B S(0)'S(1)+CS(0)S(1)'+DS(0)S(1)' that is
A is selected on selection 00 , B is selected on selection 01 and ..
Implementation : use 2 to 4 decoder for selection line,4 AND gates and 1 OR gate
Problem Design 32-1 Mux using 8-1 Mux
total 5 8x1 mux are used to design
Implementing Boolean function with Decoder
Decoder needs to have as many input lines as number of variables
Number of inputs for OR are equal to number of minterms and if NOR is used to implement (F')' number of inputs to NOR are equal to number of max terms in the function
Problem what is minimum number of inputs required for second level gate in implementation of below function with decoder and logic gates
Sum(0 2 5 6 7)
Solution
number of min terms are 5 and max terms are 3
If we implement with min terms we would need OR with 5 inputs and
If we implement by max terms that is we get F' from decoder and then NOR it we get F we would need 3 input NOR gate
Output in max terms when implemented with two input gates we can use inverter and AND gate
example if ABC' AB'C' are only max terms we know that output of decoder in maxterms is F'
F' = (ABC' + AB'C')
F = (ABC' + AB'C')' // with NOR (or invert)
which is equal to invert AND like NOR's OR invert
that is F' = (A'+B'+C)(A'+B+C) // with NOR (invert and)
that is take each output of max term from decoder Invert it and AND it
Problem Implement F1 =sum(0 2 3 5 7) and F2=sum(0 1 3 4 5 7 ) with decoder and two input I/N/OR logic gates
Solution
We would need single 3 to 8 decoder
Since for f1 and f2 both number of max are less than number of minterms we immplement with max terms
f1 max terms are (1 4 6 ) and f2 has (2 6)
we invert all outputs and take their AND with two input AND gate
Since each mux gives single output we need one mux to implement each boolean function
2^n x 1 to implement n variable function
Each input line corresponding to minterm is made 1 and others as zero
Another method that can be used to implement n+1 variable function with 2^n x 1 mux
out of n+1 variables n are connected to n selection line and single is used with input line
Implement 3 variable function f= sum(2 4 7)with 4 to 1 mux
2 selection lines 4 inputs
1)determine the truth table of boolean function
2)higher order variable connected to higher order lines B to S0 and C to S1
if both minterms in that column present in function place 1 below it
if only one is highlighted corresponding variable is written below it
If we chose C as the input then table would be like
Solution Find corresponding minterms, write truth table and then similar way find the inputs for
ROM
include both decoder and OR gates within single IC
stores permanent binary information
n inputs called address and m output called word
there are 2^n words stored in the unit each addressed by 2^n minterms of n input variables
each word is of m bits appears on m output lines
Notation to represent ROM is 2^n x m (2^n words and each m bit word) this is also total number of bits
Example 32x8 ROM has 32 words of 8 bit each
another notation is kbits ROM that is k is total number of bits in the ROM
it may be 512*4
ROM internals
combinational with AND gate connected as decoder and number of OR equal to number of output in the unit
In 32x4 ROM 5 input variables are decoded into 32 lines by means of 32 AND and 5 inverters each output of the decoder is one min term Each address selects one and only one output from decoder
Implementing Combination ckt with ROM
for n input m output combinational ckt 2^n x m ROM is required
RAM
n data input lines, n data output lines, k address lines, two control inputs
same like ROM its specified with number of words it contains and number of bits in each word or
total number of bits in the RAM
words are addresses that is there could be address for 16 bits
example 1K x 16 memory has 2^10 words of 16 bits each
Static RAM
internal flip flops stores binary information
valid as long as powered
easy to use and shorter read/write cycles
Dynamic RAM
stores binary information as electric charges applied to capacitor
capcitor discharges with time and need to be refreshed for recharging
charge on each word has to refreshed each milliseconds
reduced power consumption compared to SRAM and large storage
Memory Decoding
to select memory word based on input address
number of storage cells = number of word*bits perword, that is, for each bit
a binary cell stores single bit in its flipflop, it has three inputs and one o/p,operates without clock
1 read/write line,1 address line ,1 data output line and 1 data o/p line for each cell
Array of RAM chips
each bit increased in the address length increases the number of word by factor of 2
and to increases the bits/word data input and o/p lines need to be increased
Increasing number of words
Constructing 4K x 8 RAM from 1K x 8 RAM
data lines 8 input and 8 o/p each goes to all chips
address lines required are 12 Least 10 are applied to all 4 1Kx8 RAM and two most significant are applied to the decoder and o/p of decoder applied to selector line of RAM
Increasing number of bits
Construct 1Kx16 RAM from 1Kx8 RAM
http://www.mil.ufl.edu/3701/
http://www.utdallas.edu/~dodge/EE2310/
http://www.ece.uidaho.edu/ee/digital/donohoe/ECE240/
http://www.ics.uci.edu/~mghodrat/ics151/
Reference
http://inst.eecs.berkeley.edu/~cs150/fa08/Calendar.htm //problem
Recurrence Relations
| Recurrence | Algorithm | Big-Oh Solution |
|---|---|---|
| T(n) = T(n/2) + O(1) | Binary Search | O(log n) |
| T(n) = T(n-1) + O(1) | Sequential Search | O(n) |
| T(n) = 2 T(n/2) + O(1) | tree traversal | O(n) |
| T(n) = T(n-1) + O(n) | Selection Sort (other n2 sorts) | O(n2) |
| T(n) = 2 T(n/2) + O(n) | Mergesort (average case Quicksort) | O(n log n) |
Recurrence of form
1.T(n)= T(k) + T(n-k+1)+C
2.T(n) =T(k)+T(n-k+1)+O(n)
3.T(n)=2T(n/2) +O(n)
solution
1. O(n) , relation T(..) on right contributing also Th(n)
2. O(nlogn) ,O(n) contributing to the time complexity
3.same as 2,O(n) contributing to the time complexitysolver recurrence
1) Tn=3Tn/2
Tn = 3(3Tn/22) = (3i )Tn/2i =
3log2n =nlog23
2) Tn = 3Tn−1+2.
3n − 1.
3) Tn = 2T(n−1) + 2.
2n+1 − 2.
Lame’s theorem (Complexity of the Euclidean algorithm). Let a and b be positive integers with a ? b, n be the number of divisions used by the Euclidean algorithm to find gcd(a, b) and k is the number of decimal digits in b. Then n <= 5k.Note that k <= log10 b?+1. Therefore, n = O(log b) divisions are used by the Euclidean algorithm.
Couting problems with Recurrence Relations
Problem Find number of bit string s with no two consecutive 0'slets call an be number of bit strings of lenght n where we do not have 2 consecutive zeros
1) number of bitstrings ending with 0 that should have 1 with them, that is of the form
----|10 and the first part can be occupied by any valid bit string that itsself donot have consecutive zero that is an-2
2) number bit strings ending in 1, ----|1 which is an-1
so an = an-1 + an-2 where initial conditions should be specified for a0 a1 and a2
a0 = 0
a1=2 {0,1}
a2 = 3{01,10,11}
the recurrence seems to be like Fibonacci sequence where a1 corresponds to f3, a2 to f4 i.e an = Fn+2
This is also relation for subsets of n numbers which do not contain consecutive number
{1,2,3} subsets are F(5) i.e {empty,{1},{2},{3},{1,3}} 5 subsets
Problem Count all number of n digit where number of zero is even
1)any number of for 9,57 which has no zero is valid, and such numbers in form of recurrence is
n-1|9 , n-1|8 , n-1|7... that is all strings ending in some non zero digit and having first n-1 as valid string
i.e 9*an-1
2)we have not counted any number which has zero digit in it ...(we use little to much recursive thinking here)
numbers with zero digit can be formed by adding a zero to number with even number of zeros
number with even number of zeros = total numbers - number with odd zeros(which we have named an)
10^n-1 - an-1
we get final reccurence as an = 8an-1 + 10^n-1
Solving Recurrence Relations
www.cs.duke.edu/courses/cps130/.../Homeworks/Solutions/H2-solution.pdf //order of growth problem
www.cse.psu.edu/~berman/sol_565_1.pdf
1) If f(n) = Th(g(n)) { 0<=c1g(n) <= f(n) <= c2g(n) } for some n>= n0 and c1,c2,n0 >=0
then f(n) = O(g(n)) because it implies 0<= f(n) <= c2g(n)
2)For polynomials p(n) = Th(n^d)
3)o notation
if f(n) = o(g(n))
f(n) becomes insignificant relative to g(n) for large values of n
4) if
f(n) = w(g(n))
Comparing various functions time complexity
5) exponential and polynomial function
exponential functions with base greater than 1 grows faster than polynomial functions that is
n^b = o(a^n) for a > 1
lim{n->infty} ( n^b / a^n) = 0
6)exponential e^x
e = 2.71828e^x = {sum o to inty} x^i / i!
i.e e^x >= 1+ x
when x = 0 its equality
if |x| <=1
e^x <= 1+x+x^2
so e^x = 1+x+Th(x^2)
7)logarithm functions
polylogatithmic functions grow more slowly than polynomial in the similar manner like polynomial grows slowly than exponential
we use substitution to prove that
substitute log n for n and 2^a for a
a(logbc) = c(logba)
abc converts to reverse, cba
8)
Transitivity is true for all five operators like
f(n) = O(g(n)) and g(n) = O(h(n)) then
f(n) =O(h(n))
Reflexivity is also true for O,Th and Omega that is for all asymptotic tight bounds
f(n) = O((n))
Symmetry is true for Th only that is
f(n) = Th(g(n)) if and only if gn = Th(f(n))
Case when we might not be able to compare function like in case of
trignometric functions which oscillates n^(1+sin n) and n here 1+sin n oscillates between 0 and 2
Subscribe to:
Posts (Atom)