Class Notes (1,100,000)

CA (620,000)

McGill (30,000)

COMP (700)

COMP 273 (40)

Piotr Przytycki (10)

Lecture 4

School

McGill UniversityDepartment

Computer Science (Sci)Course Code

COMP 273Professor

Piotr PrzytyckiLecture

4This

**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

(address) (contents of memory)

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:

Cn−1Cn−2. . . C2C1C0

An−1An−2. . . A2A1A0

+Bn−1Bn−2. . . 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

Sn−1Sn−2. . . 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=A0⊕B0

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 Sn−1you need to allow the carries to ripple

through from bits 0 up to bit n−1. 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

###### You're Reading a Preview

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

###### You're Reading a Preview

Unlock to view full version