[SOLVED] CS Combinatorial Circuits

Combinatorial Circuits
1

COMP273 McGill
2
Overview a How to build an adder
a Commoncombinationalcircuits Decoders and encoders
Multiplexors
Read-only memory
Programmable logic array Arithmetic logic unit

The Big Picture Again

COMP273 McGill
Combinational Circuits
a Combinational/Combinatorial circuit: a circuit that implements a Boolean function

Circuits for Binary Arithmetic

COMP273 McGill
Half Adder a Outputs: sum and carry out
a Inputs:twobits
A B Sum Carry
0000 0110 1010 1101
Sum = AB + AB Carry = AB

COMP273 McGill
C A B Sum Carry
00000 00110 01010 01101 10010 10101 11001 11111
Full Adder
a Inputs: two bits (A, B) + carry from the previous bit (C) a Outputs:sumandcarry

Common Circuits

Decoders
a A decoder has n-bit input and 2n outputs
a Only one output active for each input combination
COMP273 McGill 13

COMP273 McGill
14
a 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 = SA + SB
15
a TheSelector.Useoften
2 signals A, and B, and a selector S
S 2 2
C
If S = 0, output = A
Otherwise, output = B
I22 I22 I22 I22 I22 I22 I22 I22 I22 I22 I22 I22 I22 I22 I22 I22 I22 I22 I22 I22 I22 I22 I22 I22
I2 I2 I2 I2 I2 I2 I2 I2
Multiplexor

COMP273 McGill
16
Multiplexor a Can have any number of inputs
Given n signals, need o}POv selector inputs
a 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
a Eightdifferentsignals(A-H)
a 3-8 Decoder for selecting the inputs
17

Arrays of Logic Elements
a Manyoperationsneedtobedone on an entire word (32 bits)
a For instance, a multiplexor that selects one of two words:
COMP273 McGill 18

COMP273 McGill
Read-only Memory (ROM)
a Inputs encode the memory address
a Outputs are the contents at each address
a Consider a circuit as a hardwired memory

COMP273 McGill
Programmable Logic Array (PLA) Canonical form: only two levels of gates
a The AND gates array is a product term consisting of any number of inputs or inverted inputs
a 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

a Adder
a Commoncircuits
Decoder and Encoder
Multiplexor
Read-only Memory (ROM)
Programmable Logic Array (PLA) Arithmetic Logic Unit (ALU)
Review
a Textbook: Appendix B.8 of 5th and 6th edition
COMP273 McGill 24