Class Notes (1,100,000)
CA (620,000)
McGill (30,000)
COMP (700)
Lecture 4

# COMP 273 Lecture Notes - Lecture 4: Combinational Logic, Logic Gate, Memory Address

Department
Computer Science (Sci)
Course Code
COMP 273
Professor
Piotr Przytycki
Lecture
4

This preview shows pages 1-2. to view the full 8 pages of the document.
COMP 273 4 - combinational logic 2 Jan. 20, 2016
Read-only memory (ROM) using combinational logic circuits
The truth tables are deﬁned by “input variables” and “output variables”, and we have been thinking
of them as evaluating logical expressions. Another way to think of a combinational circuit is as a
Read Only Memory (ROM). The inputs encode a memory address. The outputs encode the value
stored at the address. We say such a memory is read-only because the gates of the circuit are ﬁxed.
For example, suppose the memory address is speciﬁed by the two input variables A1, A0, and
the contents at each address are speciﬁed by the bits Y2Y1Y0. Here is a truth table:
A1A0Y2Y1Y0
0 0 0 1 1
0 1 0 0 1
1 0 0 0 0
1 1 1 0 0
and here is the corresponding memory. (Note that the address is not stored in the memory!)
input output
00 011
01 001
10 000
11 100
What is new about this concept? You now have to think of the input and output variables in
a diﬀerent way than you did before. Before, you thought of the input variables as having TRUE
or FALSE values, and you did not associate any particular signiﬁcance to their order. Thinking
about the circuit as a ROM is quite diﬀerent. You no longer think of each of the input variables
as TRUE or FALSE. Rather, you think of the input variables as deﬁning a binary number, namely
an address. The order of the input variables now has a signiﬁcance, since it deﬁnes an ordering on
the address space. Similarly, the output variables are a string of bits whose order may or may not
matter.
Arithmetic Circuits
Last class we discussed gates and circuits and how they could be used to compute the values
of logical expressions, formed by NOT, AND, OR and other operators. Such circuits are called
combinational logic circuits or combinational digital circuits. We will look at several more useful
examples today.
How would we implement addition using these gates? Recall the algorithm from Lecture 1 for
adding two n-bit numbers, Aand B:
Cn1Cn2. . . C2C1C0
An1An2. . . A2A1A0
+Bn1Bn2. . . B2B1B0
———————————
last updated: 20th Jan, 2016 1

Only pages 1-2 are available for preview. Some parts have been intentionally blurred.

COMP 273 4 - combinational logic 2 Jan. 20, 2016
Sn1Sn2. . . S2S1S0
The Ciare the carry bits, and Siare the sum bits. Note that C0= 0 because there is no way to
carry in. (It will be clear later why we are deﬁning this bit.)
How are we interpreting these bits? We are doing ”odometer arithmetic” here, so it doesn’t
matter whether we are thinking of the numbers as signed (twos complement) or unsigned. This does
matter when we interpret the results, but it doesn’t matter from the standpoint of the mechanisms
for computing the sum.
The rightmost bit (or least signiﬁcant bit)S0of the sum is simple to determine using logical
expressions and combinational circuits, as is the carry out bit C1.
A0B0S0C1
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
Thus,
S0=A0B0
C1=A0·B0
The circuit that implements these is called a half adder. It has two inputs and two outputs. You
should be able to draw this circuit yourself. More generally, the values of the kth sum and carry
out bits are given as follows:
CkAkBkSkCk+1
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
which we can represent using sum-of-products circuits as deﬁned by these expressions:
Sk=Ak·Bk·Ck+Ak·Bk·Ck+Ak·Bk·Ck+Ak·Bk·Ck
Ck+1 =Ak·Bk·Ck+Ak·Bk·Ck+Ak·Bk·Ck+ +Ak·Bk·Ck
The box with the ’+’ below contains the combinational circuitry for implementing the truth table
above. Note that we have used a full adder for the least signiﬁcant bit (LSB) and set C0to 0.
This circuit is called a ripple adder. To compute Sn1you need to allow the carries to ripple
through from bits 0 up to bit n1. This suggests that for large n(say 32 bits for Aand Beach),
you would have to allow a long delay. Later this lecture, we will discuss how this delay can be
avoided. For now, we turn to other useful combinational circuits.
last updated: 20th Jan, 2016 2

Unlock to view full version

Only pages 1-2 are available for preview. Some parts have been intentionally blurred.

COMP 273 4 - combinational logic 2 Jan. 20, 2016
+
+
+
+
0
S0
S1
S2
S3
A0
B0
A1
A2
A3
B1
B2
B3
C1
C2
C3
C4
etc
Encoders
An encoder is a combinational logical circuit whose outputs specify which of a set of possible inputs
or groups of inputs has occured. The term encoder is used somewhat loosely. (There is no generally
agreed upon formal deﬁnition of an encoder that I am aware of.) Let’s look at a few examples.
A common example is a set of minput wires, such that exactly one of them has the value 1.
For example, consider a keyboard with 5 buttons and suppose that the mechanics of these buttons
are such that one and only one of these buttons is pressed down. (You may have seen something
like this on a children’s toy.) Such an encoder might be constructed using the truth table:
A B C D E Y1Y2Y3
0 0 0 0 1 0 0 1
0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 1
0 1 0 0 0 1 0 0
1 0 0 0 0 1 0 1
Notice that if none of the button is pressed, or if multiple buttons is pressed (because you push
hard and break the mechanism), then the above truth table does not specify what the value of the
output variables Yiis. But this is not a problem, as long as the design is such that only one can be
pressed (1) at any time.
last updated: 20th Jan, 2016 3