Combinatorial Circuits
1
COMP273 McGill
2
Overview á How to build an adder
á Commoncombinationalcircuits ± Decoders and encoders
± Multiplexors
± Read-only memory
± Programmable logic array ± Arithmetic logic unit
The Big Picture Again
COMP273 McGill
Combinational Circuits
á Combinational/Combinatorial circuit: a circuit that implements a Boolean function
Circuits for Binary Arithmetic
COMP273 McGill
Half Adder á Outputs: sum and carry out
á Inputs:twobits
A B Sum Carry
0000 0110 1010 1101
Sum = A’B + AB’ Carry = AB
COMP273 McGill
C A B Sum Carry
00000 00110 01010 01101 10010 10101 11001 11111
Full Adder
á Inputs: two bits (A, B) + carry from the previous bit (C) á Outputs:sumandcarry
Common Circuits
Decoders
á A decoder has n-bit input and 2n outputs
á Only one output active for each input combination
COMP273 McGill 13
COMP273 McGill
14
á Opposite of a decoder
± Output only specified if one input is 1
Encoders
Assume only one button can be pressed at any time
COMP273 McGill
C = S’A + SB
15
á TheSelector.Useoften
± 2 signals A, and B, and a selector S
S 2 2
C
± If S = 0, output = A
± Otherwise, output = B
Ï22 Ï22 Ï22 Ï22 Ï22 Ì22 Ï22 Ì22 Ï22 Ï22 Ì22 Ì22 Ì22 Ï22 Ï22 Ì22 Ï22 Ì22 Ì22 Ì22 Ï22 Ì22 Ì22 Ì22
Ï2 Ï2 Ì2 Ì2 Ï2 Ì2 Ï2 Ì2
Multiplexor
COMP273 McGill
16
Multiplexor á Can have any number of inputs
± Given n signals, need øo}PÓv¿ selector inputs
á Three step recipe for building a multiplexor ± A decoder that generates n signals
± An array of n AND gates to combine the signals ± A single n input OR gate to compute the result
COMP273 McGill
Multiplexor
á Eightdifferentsignals(A-H)
á 3-8 Decoder for selecting the inputs
17
Arrays of Logic Elements
á Manyoperationsneedtobedone on an entire word (32 bits)
á For instance, a multiplexor that selects one of two words:
COMP273 McGill 18
COMP273 McGill
Read-only Memory (ROM)
á Inputs encode the memory address
á Outputs are the contents at each address
á Consider a circuit as a “hardwired” memory
COMP273 McGill
Programmable Logic Array (PLA) Canonical form: only two levels of gates
á The AND gates array is a product term consisting of any number of inputs or inverted inputs
á The OR gates array is a sum term consisting of any number of these product terms.
COMP273 McGill
D = A+ B + C
Programmable Logic Array (PLA)
A ~ | | [ = ~ | | [ = ~ | | [ &A||
A dot in the AND plane indicates that the input, or its inverse, occurs in the product term.
A dot in the OR plane indicates that the corresponding product term appears in the corresponding output.
Instruction
Ainvert Binvert
CarryIn Operation
COMP273 McGill
22
Arithmetic Logic Unit (ALU)
1-Bit ALU
ADD 0 0 0 2 SUB 0 1 1 2 AND 0 0 x 0 OR 0 0 x 1 NOR 1 1 x 0 SLT 0 1 1 3
COMP273 McGill
23
Arithmetic Logic Unit (ALU)
32-Bit ALU
á Adder
á Commoncircuits
± Decoder and Encoder
± Multiplexor
± Read-only Memory (ROM)
± Programmable Logic Array (PLA) ± Arithmetic Logic Unit (ALU)
Review
á Textbook: Appendix B.8 of 5th and 6th edition
COMP273 McGill 24