SI202: Week 1



SM242 Week 2 (Notes based on Epp Chapter 1)

I. Logic (continued)

20. Logic Gates Consider the circuit below which has 2 switches in series:

S1 S2

Light

When will the light turn on?

We can represent the light's operation using a table:

S1 S2 Light

open open off

open shut off

shut open off

shut shut on

Change the words open and off to F and the words shut and on to T and the table becomes

S1 S2 Light This is the truth table for the [pic] logical connective.

F F F We can say that the circuit above corresponds

F T F to S1 [pic] S2.

T F F

T T T

Now consider the circuit that has 2 switches in parallel.

S1

S2 Light

When will the light turn on?

We can represent the light's operation using a table

S1 S2 Light

open open off

open shut on

shut open on

shut shut on

Changing the words open and off to F and the words shut and on to T and the table becomes

S1 S2 Light

F F F

F T T This is the truth table for the [pic] logical connective.

T F T We can say that the circuit above corresponds to S1 [pic] S2.

T T T

Notes:

• Usually, when designing circuits, the symbol 0 is used to denote F and the symbol 1 is used to denote T.

• A compound expression as we are using it here (in the context of logic circuits) is called a Boolean expression. We will develop a more formal definition of a Boolean expression later in the course.

To a Computer Scientist, the computer’s hardware is comprised of digital logic circuits. Digital logic circuits are built from just a handful of primitive elements, called logic gates, combined in various ways.

In a digital logic circuit, only two values may be present. The values may be [pic] and + 5 volts. Or the values may be 0.5 and 3.5 volts. Or the values may be… you get the picture. To allow consideration of all of these possibilities, we will say that digital logic circuits allow the presence of two logical values: 0 and 1.

So, signals in a digital logic circuit take on the values of 0 or 1. Logic gates are devices which compute functions of these binary signals.

In this course we will consider three logic gates that are used to construct digital logic circuits:

A. Not gate (inverter) Has one input and one output. If the input, P, is 1, the output is 0. If the input is 0, the output is 1.

[pic]

Inverter or NOT gate

P ~P

0 1 Corresponds to the ~ connective

1 0

B. And gate – has two inputs and one output. If both inputs, say P and Q, are both 1 then the output is 1. Otherwise, the output is 0.

AND gate

P Q [pic]

0 0 0

0 1 0 Corresponds to the [pic] connective

1 0 0

1 1 1

C) Or gate – has two inputs and one output. If either or both inputs, say P and Q, are 1, the output is 1. Otherwise, the output is 0.

[pic]

OR gate

P Q [pic]

0 0 0

0 1 1 Corresponds to the [pic] connective.

1 0 1

1 1 1

21. Combinational circuits

A. A combinational circuit is a digital logic circuit whose output is determined only by the current values of the inputs (with no dependence on past input values). A combinational circuit is built up by combining our three basic logic gates with the following provisos:

• The output of a gate may not eventually feed back to that same gate.

• The output lines from 2 different gates cannot be combined.

The following are not combinational circuits:

[pic] [pic]

B. Example. The air conditioning plant on a ship is controlled by a logic circuit. The air conditioner will turn on (logical “1”) if the temperature is above 80(F (logical “1”). If the motor is overheating (logical “1”), however, a signal is sent to turn the air conditioner off. Sketch (within the box) the logic circuit to accomplish this design.

temp > 80(F

air conditioner

motor overheating

Answer:

C. Our study of combinational circuits will involve five (very much related!) tasks

• (Task 1) Given a digital logic circuit, write the corresponding Boolean expression.

• (Task 2) Given a Boolean expression, draw a digital logic circuit that represents this expression.

• (Task 3) Given a digital logic circuit, construct the corresponding truth table.

• (Task 4) Given a truth table, construct a digital logic circuit that implements this truth table.

• (Task 5) Given a digital logic circuit, design a simpler digital logic circuit that performs the equivalent function.

TASK 1: Given a digital logic circuit, write the corresponding Boolean expression.

The Boolean expression corresponding to a digital logic circuit can be determined by evaluating the effect of the logic gates on the input expressions.

Example: Determine the Boolean expression corresponding to the digital logic circuit shown.

[pic]

Example. Write the Boolean expression for the logic circuit shown below.

[pic]

Evaluating the effect of the logic gates on the input expressions, we see:

TASK 2: Given an expression, draw a digital logic circuit that represents this expression.

The basic approach is to write the expression on the right side of the page. Draw the circuit from right to left, by working from the outermost part of the expression.

Example: Construct a digital logic circuit that will implement the Boolean expression (p [pic] ~ q) [pic]~ p

At the highest level, we are

[pic]

Now, let’s continue to deconstruct this by looking at the top term,

[pic]

Finally,

[pic]

Example: Draw a digital logic circuit that represents the Boolean expression x [pic] (y [pic] ~ (x [pic] ~ z))

TASK 3: Given a digital logic circuit, construct the corresponding truth table.

There are many convenient ways to do this. We can determine the corresponding Boolean expression (TASK 1) and construct a truth table as we did in Week 1. Or, alternatively, we can trace through the circuit for each possible combination of input values.

Example: Construct the truth table corresponding to the circuit shown.

[pic]

Substitute p = 0 and q = 0 and r = 0 and trace through the circuit gate by gate. Repeat this for the other combinations of input values. The resulting truth table is

p q output

Example. Construct the truth table for the circuit shown below.

[pic]

p q output

Have you seen this truth table before?

[pic]

Example. Write the Boolean expression for the logic circuit shown below, and then construct the truth table for it.

[pic]

Evaluating the effect of the logic gates on the input expressions, we see that the output is:

How many rows will be in this truth table?

The truth table is

p q r

Aside an aside (and not related to the example above), note that for AND gates and OR gates, we will allow more than two inputs. For a multi-input AND gate, the output is one if ALL of the inputs are 1. For a multi-input OR gate, the output is 1 is ANY one of the inputs is a 1 (or if more than one input is a 1). The example below shows what we mean.

Example. Design a digital logic circuit to implement the Boolean expression [pic] if:

(a) You only have 2-input gates available.

(b) You have gates with any number of inputs allowed.

TASK 4: Given a truth table, construct a digital logic circuit that implements this truth table.

Suppose the input expressions are [pic].

a. Identify the rows of the truth table that have an output of 1.

b. For each such row, form the Boolean expression.

[pic]

where[pic] if [pic] in this row, and [pic] if [pic]in this row.

c. After step b., we will have one Boolean expression corresponding to each row that had an output of 1. Take the disjunction of all these Boolean expressions. The resulting expression has the truth table under evaluation. (As an aside, an expression such as this, which is a disjunction of several terms, where each of these terms is a conjunction of irreducible expressions, is said to be disjunctive normal form.)

d. Form the digital logic circuit from this Boolean expression using the technique discussed in TASK 2 above.

Example: Construct a logic circuit for the truth table shown.

p q output

0 0 0

0 1 1

1 0 0

1 1 1

Solution:

p q output

0 0 0

0 1 1

1 0 0

1 1 1

Example: Construct a logic circuit for the truth table shown.

A B C Output

[pic]

TASK 5: Given a digital logic circuit, design a simpler digital logic circuit that performs the equivalent function.

a. Find the Boolean expression that corresponds to this logic circuit (TASK 1 above).

b. Use the Table on page 14 of the text to find a simpler logically equivalent Boolean expression.

c. Given this simpler Boolean expression, draw the digital logic circuit that represents this expression (TASK 2 above). This simpler circuit will perform precisely the same way as the original (more complex) circuit.

Example. Suppose we find that a logic circuit has the Boolean expression

[pic]

Can this circuit be simplified?

[pic]

Note: In IC220 (Computer Architecture and Organization) you will learn an important additional technique (the Karnaugh Map) to accomplish TASK 5 above.

22. Examples

Question 1 You have been tasked with designing the sprinkler system for the Commanding Officer’s stateroom. The CO’s stateroom has three smoke alarms. Since the CO will be very angry if his stateroom is drenched by a false or spurious alarm, you decide that the sprinkler system will not be activated by any single smoke alarm. The sprinkler system will activate if any two of the smoke alarms activate (or if all three activate).

a. Write a truth table that describes how the sprinkler operation will depend on the status of the three smoke alarms. (Clearly state what you intend by logical 1 and logical 0.)

b. Based on your truth table, design the digital logical circuit.

Let logical 1 mean the alarm/sprinkler is on.

Question 2 Let’s pretend that there are four midshipman who are very good friends (remember, this is just pretending). Their names are:

MIDN Miller

MIDN Porter

MIDN Lees

MIDN Wolz

Although they are all good friends, MIDN Lees and MIDN Wolz are youngsters, so they “kinda-sorta” get, shall we say, “outvoted” when it comes to some decision-making.

Our four midshipmen always eat dinner together. In fact, they always eat dinner together in one of two locations: King Hall or California Pizza Kitchen (CPK). Each day, at 1645, they take a vote to decide where all four will eat. The voting works as follows:

• If there is a clear majority, the majority wins.

• If there is a tie vote, they all eat in King Hall with one exception: If MIDN Miller and MIDN Porter agree on CPK, they pull rank and their choice (CPK) wins out.

Design a digital logic circuit that will allow our four midshipmen to cast their votes electronically. Based on the votes, the logic circuit will decide (based on the rules above) where our midshipmen will be eating dinner that day. (To make our task of grading easier, please use the following convention: Let 1 denote a vote for CPK and 0 denote a vote for King Hall.)

Let 1 = CPK, 0 = King Hall

23. Number Representations

A. Decimal Integers and Decimal Notation

The decimal number system has 10 digits (0,1,2,3…9). Since it is based on 10 distinct symbols, we say the base is 10. In decimal notation, we write a number as a string of digits. To interpret a decimal number, we multiply each digit by the power of 10 associated with that digit’s position.

Example: Consider the decimal number: 6349.

This number is:

6 3 4 9

The Binary Number System

The binary number system has two digits (0 and 1). The base is two. Just as with decimal notation, we write a number as a string of digits, but now each digit is 0 or 1. To interpret a binary number, we multiply each digit by the power of 2 associated with that digit’s position.

Example: Consider the binary number 1011.

This number is:

1 0 1 1 =

Converting a binary number to a decimal number

To convert a binary number to a decimal number, write the binary number as a sum of powers of 2.

Example: Express the binary number 1011 as a decimal number.

Note: We must be careful that the base is understood. When we say “11” above, we mean the number 11 in base 10, not the number 11 in base 2. If the base is not clear from context, it can be made explicit by including the base as a subscript as in: [pic]

Example: Express the binary number 110110 as a decimal number.

Converting a decimal integer to a binary number

1. Method 1. Express the decimal number as a sum of powers of 2. To do this:

i. find the highest power of two less than or equal to the decimal number. The binary representation will have a one in this position.

ii. Now subtract this power of two from the original decimal number.

iii. If this new decimal number is zero, we’re done. Otherwise return to step i. above.

Example: Convert the decimal number 78 to binary.

Think to yourself: Self, what is the largest power of 2 that is less than or equal to 78.

[pic] is a power of 2 that is less than 78, but is it the largest?

So, the binary representation of 78 will have a one in the [pic] position:

_____ _____ _____ _____ _____ _____ _____

[pic] [pic] [pic] [pic] [pic] [pic] [pic]

Now, subtracting 64 from our number 78 gives [pic]. Thus, 14 is now the number we are working with.

What is the largest power of 2 that is less than or equal to 14?

_____ _____ _____ _____ _____ _____ _____

[pic] [pic] [pic] [pic] [pic] [pic] [pic]

Now, subtracting 8 from our number 14 gives [pic]. Thus, 6 is now the number we are working with. What is the largest power of 2 that is less than or equal to 6?

Answer:

_____ _____ _____ _____ _____ _____ _____

[pic] [pic] [pic] [pic] [pic] [pic] [pic]

Now, subtracting 4 from our number 6 gives [pic]. Thus, 2 is now the number we are working with.

What is the largest power of 2 that is less than or equal to 2?

_____ _____ _____ _____ _____ _____ _____

[pic] [pic] [pic] [pic] [pic] [pic] [pic]

Now, subtracting 2 from our number 2 gives 0, so we are done. Filling in the zeros, we have our answer: The decimal number 78 in binary is

_____ _____ _____ _____ _____ _____ _____

[pic] [pic] [pic] [pic] [pic] [pic] [pic]

Example: Convert the decimal number 201 to binary.

At the risk of insulting your intelligence, we ask that you “memorize” the binary representations of the decimal digits 1 through 16.

2. Method 2. Repeated division by 2

i. Divide the number by 2 to obtain a quotient and remainder. (The remainder will be 0 or 1)

ii. If the quotient is zero, we’re done (proceed to step iii). Otherwise, go back to step 1., treating our quotient as the number under examination.

iii. The sequence of remainders forms the binary representation of the number.

Example: Convert the decimal number 53 to binary.

Example: Convert the decimal number 201 to binary.

Using the algorithm, your answer should match the representation shown on the prior page.

Binary Arithmetic

1. Example Translate the decimal first grade problem 1 + 1 = 2 to binary notation.

We see that when we add two binary ones together, we have a carry into the next column. This idea of “carrying over to the next column” when adding binary numbers together is analogous to carrying over when adding decimal numbers: if the result of the addition is a number too big to be represented as a single digit in the number system, we carry a one over to the next column.

2. Example Translate the second grade decimal problem 1 + 1 + 1 = 3 to binary notation.

We see that when we add three binary ones together, we have a carry into the next column.

3. Example. Perform the addition of the two binary numbers:

1 0 1 1 0 1 1 1 1 1

+ 1 0 1 1 + 1 0 1

------------- --------

Negative Binary Numbers

3. Two’s complement. To find the two’s complement of a binary number, change each 1 to a zero and each zero to a one (i.e., invert all the bits), then add one to this.

2. Example: What is the two’s complement of the binary number 10010010 ?

1. Negative binary numbers using two’s complement notation. To find the representation of a negative decimal number:

• First find the binary representation of the number without the negative sign

• Then take the two’s complement. The result is the representation of the negative number.

2. Example: Express the decimal integer –13 as an eight bit binary number.

3. Example: Express the decimal integer (53 as an eight bit binary number.

4. Why is the two’s complement notation a good representation for negative numbers?

A binary number, added to its two’s complement, results in zero. This is “how its ‘sposed to be: a number added to its negative should give zero.

Example: 53: 0 0 1 1 0 1 0 1

-53: 1 1 0 0 1 0 1 1

7. Note that given the binary representation of a negative number in two’s complement notation, we can use the “inverting all the bits and adding one” idea to find the corresponding decimal equivalent.

Example. What is the decimal equivalent of this 32-bit two’s complement number?

1111 1111 1111 1111 1111 1111 1111 1100

Storage of integers (C++)

Positive integers are stored in four bytes by converting the integer to a binary number. The right most 31 bits are used. The left most bit is set to zero (indicating a positive number).

Negative integers are stored in four bytes by converting the integer to a binary number in two’s complement notation. The right most 31 bits are used. The left most bit will be a one.

Can you explain the output of the C++ program shown below?

#include

using namespace std;

int main( )

{

int number = 2147483646;

cout ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download