Digital Logic: Boolean Algebra and Gates (contd..)
n-to-2n Decoder
¡ö n inputs, 2n outputs
¡ô exactly one output is 1 for each possible input pattern
¡ö Uses:
¡ô Convert memory or register address to a control line
¡ô Convert an opcode to one of n control lines
¡ô We will get to this in the MIPS material
Two-to-Four Decoder
Three-to-Eight Decoder
How to decode for 6 output lines?
¡ö How many input lines do we need?
Time for some…
¡ö We currently use decimal system in daily life
(deci=10 digits,0-9)
¡ö We know..
1+0=1 1+1=2;1+2=3;1+3=4… 1+8=9;
¡ö What is 1+9=??
Binary Addition and Half-Adder
¡ö 0+0=0
¡ö 0+1=1
¡ö 1+0=1
¡ö 1+1=…
¡ö A half-adder can add 2 bits and produces a sum and carry signal
¡ô Sum=AxorB ¡ô Carry = AB
One-Bit Full Adder
A B Cin Cout S
000 001 010
011 100 101 110 111
Four-Bit Full Adder
Ripple-carry adder
Masking
¡ö Want to look only at certain bits of a binary word
¡ö Use a mask to remove the uninteresting bits
¡ö Example:
¡ô Two values: 01001101 and 01001001
¡ô If we want to see bit 3 from right, we AND it with 00000100 to get
¡ï 00000100 and 00000000, respectively.
Logic Minimization (CSE 100!)
0 0 1 1 1 0
ABC
000
001
010
011
100
101
110
111
Y
1
0
Start with SOP:
A¡¯BC¡¯ + A¡¯BC + AB¡¯C¡¯ + ABC¡¯
Factor A¡¯ and A out:
A¡¯(BC¡¯ + BC) + A(B¡¯C¡¯ + BC¡¯)
Factor B and C¡¯ out:
A¡¯(B(C¡¯ + C)) + A(C¡¯(B¡¯ + B))
Use identity that C¡¯+C=1 and B¡¯+B=1: A¡¯B + AC¡¯
Building functions from logic gates
¡ö Combinational Logic Circuit
¡ô Output depends only on the current inputs
¡ô Stateless (memoryless)
¡ö Sequential Logic Circuit
¡ô Output depends on the sequence of inputs
(past and present)
¡ô Stores information (state) from past inputs
Sequential Circuits and Memory