▲ ☰ ▼

CS 240 Lab 3

Data as Bits

CS 240 Lab 3

Arithmetic Circuits

All the circuits you will work with today in lab are combinational circuits. Like basic gates, the output of combinational circuits depends only on the current inputs to the circuit. Combinational circuits are made with basic gates, but produce more complex functions.

Certain functions are very useful for a variety of tasks that help us design important components of a computer, so we examine them here. These include the multiplexer, decoder, demultiplexer, encoder, and the adder (the basic arithmetic circuit for addition).

Multiplexer

Exercise 1:

Although you may not have realized it, in the first problem on the lab assignment, you designed a simple 2x1 multiplexer (MUX), which you have also learned about in lecture.

A multiplexer can be thought of as a steering circuit, which steers a single input from a set of inputs through to the output, based on the select line.

A diagram showing a mutiplexer as multiple wires that come in, one of which is connected to the output wire, with the select inputs controlling which connection is made. This isn’t actually how it’s implemented using transistors, but it’s a good analogy. 

A schematic diagram showing conceptually how an 8x1 mux works.

The symbol for a multiplexer: a trapezoid with the narrow end facing right, which is where the output (Q) comes out. The inputs (D0 and D1) come into the wide end on the left and the select input (S) comes into either the top or the bottom (the bottom in this image). 

The logic diagram symbol for a 2x1 mux.

An 8x1 MUX (shown on the right) has 8 input lines D7 - D0, 3 select lines S2 – S0, and 1 output line Q (the device labeled DEV1 below is a LogicWorks 8x1 MUX).

Important: The EN input is an “enable” line – you must activate it for the device to work correctly. However, notice the small circle representing NOT attached to the EN input: this means that you should connect it to ground to activate it, rather than connecting it to +5V. These kinds of inverted connections are also called active low, since they’re active when the voltage is low, rather than when it’s high.

A thin tall rectangle labeled DEV1 with 12 inputs along the left edge and a singe output Q on the right. From top to bottom, the inputs are labeled EN, S2, S1, S0, D7, D6, D5, D4, D3, D2, and D1. The EN input has a circle attached to it on the outside of the rectangle. 

Use the Falstad window below, or create a new circuit in LogicWorks. Follow these steps:

LogicWorks

  1. Add an 8x1 mux (search for “Mux-8”).
  2. Connect the enable line to ground.
  3. Add a “Hex Keyboard w/o STB” and connect the three bottom pins to the S0, S1, and S2 inputs. Leave the top pin disconnected.
  4. Connect 8 binary switches as inputs D7-D0.
  5. Connect a binary probe to the output Q.

Falstad

Add an 8x1 mux (“Draw -> Digital Chips -> Multiplexer”) to the circuit. Edit the mux to increase the select lines from 2 to 3. It should fit in between the provided inputs (on the left) and output (on the right).

Click on the hex keyboard in LogicWorks, or set the S0-S2 bits directly in Falstad to change the select lines. Answer these questions:

  1. Set the select lines to S0 = 0, S1 = 1, and S2 = 1 (pick 6 on the keyboard in LogicWorks). With this select configuration, which of the 8 data input(s) affects the output (toggle them to test)?

    Example answer: Only input number 6 (D6 in LogicWorks or I6 in Falstad) will affect the output.

  2. Now set the select lines to S0 = 1, S1 = 0, and S2 = 0 (or pick 1 on the keyboard in LogicWorks). Does the same input still affect the output? yes
     no

    Which input(s) will affect the output now?

    Example answer: Now only input number 1 affects the output.

  3. What is the relationship between the data inputs, the select inputs, and the output of a multiplexer?

    Example answer: The select bits are interpreted as a binary number. This specifies which of the data inputs should be forwarded through to the output. The other data inputs are ignored. That’s why there are always 2n2^n data inputs for nn select bits.

Exercise 2:

Here’s a simulated version of a 4x1 mux (note how to select among 4 data inputs, 2 select inputs are needed):

Edit the circuit above by removing components to create a 2x1 mux, or if you prefer, build a 2x1 mux in LogicWorks. Verify that it works by manipulating your inputs and observing the output, and then describe your circuit below:

Example answer:

A 2x1 multiplexer circuit diagram, showing how it’s implemented (see description below) 

Inputs D0 and D1 each connect to a separate AND gate. The other inputs of those and gates connect to the S selector input, but with a NOT gate on the way for the AND gate connected to input D0. This means that switching S back and forth switches which AND gate gets activated by the S input, but only one of them does at a time. Both AND gates connect to an OR gate whose output is the circuit output.

How many different input combinations should you test to thoroughly test the circuit? Correct answer: 8

Exercise 3:

A multiplexer can be used to implement any boolean function by hard-wiring the data inputs to fixed high or low values. The select lines become the inputs to the boolean function, and based on the desired truth table, you set the appropriate data input to either 0 or 1.

This following truth table for a function Q indicates whether or not a 3-bit value S2 S1 S0 is a power of two:

S2 S1 S0 Q
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 0

Here is a pin-out for a 74151 8x1 multiplexer:

Pinout for the 74151. The notch is on the left, with pin 1 below it and pins numbered counterclockwise around the chip. There are 8 pins on each side. In order, the pins are labeled: D3, D2, D1, D0, Y, Y-bar, E-bar, GND (pin 8), S₂, S₁, S₀, D7, D6, D5, D4, and Vcc (pin 16). 

On your protoboard, there is a 74151 chip (8 x 1 MUX) inserted in the top-right area. Connect it to produce the function Q.

Output is measured at Y (pin 5). It is not necessary to use or connect pin 6.

Don’t forget the power(pin 16), ground (pin 8), and enable line (pin 7, connect to ground)!

When everything is plugged in, how many logic switches should be connected?

0
 1
 3
 8

Which inputs should those switches connect to? Example answer: They need to connect to the S0, S1, and S2 inputs, which are pins 11, 10, and 9.

Where should the data inputs D0-D7 be connected? Example answer: Each data input should connect to either the +5V or ground rail via a wire. For this circuit, D1, D2, and D4 should connect to +5V and the rest should connect to ground.

Confused? Click here for hints.

The key to this exercise is to figure out what “hard-wiring the data inputs” means. The data inputs are D0-D7 (or in Falstad, I0-I7). Rather than connect these to switches, like you did in the previous exercise in the simulator, you’re going to connect each one directly to either +5V or ground, to establish a permanent high or low voltage signal for that input.

The goal given that info is to figure out: which data inputs should I connect to +5V and which should I connect to ground, in order to make the chip behave according to the specified truth table?

You will connect S0/S1/S2 to three of the logic switches, because those inputs are what you’ll be manipulating.

Demonstrate to the instructor that your circuit detects inputs on the select lines which represent a power of 2.

Decoder

Exercise 4:

A n×2nn \times 2^n decoder has nn inputs and 2n2^n outputs. Only one of the outputs is active for any given nn-bit input combination.

In the second problem on the pre-lab assignment, you designed a simple 2x4 decoder. Assuming 2 inputs A0 and A1 and 4 outputs D0 - D3, and:

D0 is only true when A1A0 = 00 D1 is only true when A1A0 = 01 D2 is only true when A1A0 = 10 D3 is only true when A1A0 = 11

This can be described by the following truth table:

A1 A0 D0 D1 D2 D3
0 0 1 0 0 0
0 1 0 1 0 0
1 0 0 0 1 0
1 1 0 0 0 1

Such a device is said to decode the binary number which is specified by the inputs, activating the output which corresponds to the decimal value of the binary input.

You should have designed a circuit that looks something like this:

A circuit diagram with inputs D1 and D0 at the top. It has 4 AND gates feeding into outputs Q0 through Q1 on the right. Wires distribute normal and inverted versions of D0 and D1 to the AND gates as follows: Q0 is NOT-D1 and NOT-D0, Q1 is NOT-D1 and D0, Q2 is D1 and NOT-D0, and Q3 is D1 and D0. In the diagram, D0 is off and D1 is on, activating the Q2 output and leaving the rest inactive. 

Build the circuit for the 2x4 decoder in LogicWorks or the Falstad simulator (blank window below) using basic gates.

When you set both inputs to 1, which of the outputs is/are active?

D0
 D1
 D2
 D3

When you set both inputs to 0, which of the outputs is/are active?

D0
 D1
 D2
 D3

Why doesn’t a decoder ever have more than one of its outputs active?

Example answer: The purpose of a decoder is to use 2n2^n outputs to indicate the binary value represented by a bit pattern on its nn inputs. Since any possible input pattern corresponds to a unique number, only the output line for that number will be active. Having two output lines active doesn’t make sense, because it implies that two distinct bit patterns are active at once, which is impossible.

Demonstrate correct operation to the instructor.

Exercise 5:

The 74138 is a 3x8 decoder chip. You will find one inserted in the bottom-right corner of your protoboard. Below is a pin-out for the 74138:

Pinout for the 74138, showing pin 1 on the bottom-left with 16 pins numbered counterclockwise around the chip. They are labeled: A₀, A₁, A₂, inverse E₁, inverse E₂, E₃, inverse O₇, GND (pin 8), inverse O₆, inverse O₅, inverse O₄, inverse O₃, inverse O₂, inverse O₁, inverse O₀, and Vcc (pin 16). The diagram is titled 74LS138. As hinted, the output labels for pins 4, 5, 7, and 9-15 all have bars over them to indicate they’re inverted (active low). 

Make the following connections to the device:

  1. Connect VCC pin to voltage and GND pin to ground on the board.
  2. Connect the select lines A₀ A₁ A₂ on the chip to 3 Logic Switches on the board.
  3. Connect each of the 8 outputs (O) on the chip to Logic Indicators on the board.
  4. Connect the enable lines E₁ and E₂ to ground on the board.
  5. Connect the enable line E₃ to voltage on the board.

Now complete this truth table based on your observations of the decoder:

GCorrect answer:

C B A Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7
0 0 0 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
0 0 1 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
0 1 0 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
0 1 1 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
1 0 0 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
1 0 1 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
1 1 0 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
1 1 1 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1

Correct answer: See above

The outputs for this device are active low. Describe what that means in your own words:

Example answer: It means that instead of high-voltage meaning ‘active’ while low voltage means ‘inactive,’ the opposite is true: low-voltage means ‘active’ and high-voltage means ‘inactive.’

Demultiplexer

A demultiplexer is the exact opposite of the multiplexer.

The symbol for a 1x4 demux: input D comes in on the left which is the short end of a trapezoid. Select inputs S0 and S1 come in from the bottom, and outputs Q0 through Q3 go out from the right (the wide end of the trapezoid). 

The demultiplexer takes one single input data line and then switches it to only one of the individual output lines at a time based on selector inputs, leaving the rest of the output lines low.

Exercise 6:

Complete the truth table for the 1x4 demultiplexer with select lines S1 and S0 and input D.

GCorrect answer:

S1 S0 D Q3 Q2 Q1 Q0
0 0 0 0
 1
 0
 1
 0
 1
 0
 1
0 0 1 0
 1
 0
 1
 0
 1
 0
 1
0 1 0 0
 1
 0
 1
 0
 1
 0
 1
0 1 1 0
 1
 0
 1
 0
 1
 0
 1
1 0 0 0
 1
 0
 1
 0
 1
 0
 1
1 0 1 0
 1
 0
 1
 0
 1
 0
 1
1 1 0 0
 1
 0
 1
 0
 1
 0
 1
1 1 1 0
 1
 0
 1
 0
 1
 0
 1

Correct answer: See above

Why are there some rows in the table where all of the data outputs are zeroes?

Example answer: Because if the input is 0, it doesn’t matter where it gets directed to, that line will be a 0 and the others will be zeroes by default.

Complete the Boolean algebra function for each output:

Q3 = Example answer: S1S0D

Q2 = Example answer: S1S0’D

Q1 = Example answer: S1’S0D

Q0 = Example answer: S1’S0’D

Exercise 7:

We can use the 74138 chip as a demultiplexer by hooking up our data input to the enable pin, so that when the ‘data’ is a 1 we get an output on the corresponding output line, and when the ‘data’ is a 0, we get no active outputs at all (because the chip is inactive).

Disconnect the E₃ enable line from voltage, and connect it instead to a push-button on the board.

If we set the select lines A₀, A₁, and A₂ to 1, 0, and 1 respectively, what number does that represent in decimal? Correct answer: 5

When the select lines are set that way, what will happen when we push the button?

Example answer: The 6th LED (index 5 counting from 0) should blink off as long as the button is pressed, and turn on again (so that they’re all on) when the button is released.

What configuration of select lines + the button state would cause the 4th LED (index 3 counting from 0) to turn off?

Example answer: Setting A₀ and A₁ to 1 and A₂ to 0, and then pushing the button should turn off the 4th LED.

Encoder

An encoder is the exact opposite of the decoder.

A schematic of a 4x2 encoder, which is just a rectangle with four inputs D0-D3 on the left and two outputs Q0 and Q1 on the right. 

It takes 2n2n inputs (it is assumed that only 1 of the inputs can be active at a time). The input number of the input that’s active specifies a decimal number, which gets translated to binary on the output lines.

Exercise 8:

Complete the truth table for the 4x2 encoder:

GCorrect answer:

D3 D2 D1 D0 Q1 Q0
0 0 0 1 0
 1
 0
 1
0 0 1 0 0
 1
 0
 1
0 1 0 0 0
 1
 0
 1
1 0 0 0 0
 1
 0
 1

Correct answer: See above

Complete the Boolean algebra function for each output:

Q1 = Example answer: D3 + D2

Q0 = Example answer: D1 + D3

Why doesn’t D0 appear in either equation above?

Example answer: Because when D0 is the input that’s on, the correct output is 00, and so neither output variable is true. Boolean algebra formulas express what’s necessary to make something true, and they are false under any other condition.

Stretch Material: Addition

In the pre-lab assignment for today, you saw that you can represent the sum of two single bit numbers A and B with the following truth table:

A B CarryOut Sum
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

This points to the following logical formulae:

CarryOut = A AND B

Sum = A XOR B

Exercise 9:

Using LogicWorks or the Falstad simulator, build the circuit which produces Sum and CarryOut from inputs A and B (this circuit is known as a half adder). You should use exactly one AND gate and one XOR gate.

Check your circuit against the truth table above. In particular, if you set both A and B inputs to 1, then:

GCorrect answer: CarryOut = 0
 1

and Sum = 0
 1
 Correct answer: See above.

The following is the truth table for a full adder (which incorporates a carry-in bit to the sum of A and B):

CarryIn A B CarryOut Sum
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1

The circuit for the full adder is:

A circuit diagram for a full adder. The sum output of one half-adder is connected to another set of XOR and AND gates that form a second half-adder, for which the other input is the carry-in bit. The output of that half-adder is the Sum output for the whole system. The carry-out outputs from each half-adder are wired into an OR gate, and the output of that get is the CarryOut output for the entire system. 

Exercise 10:

Revise your circuit from the previous exercise to build a full adder.

Demonstrate its operation to the instructor.

Stretch Material: IC 7483

Note: You can disconnect the wires you have currently set up before working on this part.

You will find an IC 7483 inserted in the middle section of your protoboard. Here is a logic diagram of the chip (as usual, actual pins are numbered counterclockwise around the chip from 1 at the top left), along with a diagram showing the ordering for the input connections:

Logic diagram for a 7483. It shows 9 inputs along the left-hand side: B4 at pin 16, A4 at pin 1, B3 at pin 4, A3 at pin 3, B2 at pin 7, A2 at pin 8, B1 at pin 11, A1 at pin 10, and C0 at pin 13. Vcc (pin 5) is on top and GNC (pin 12) is at the bottom. The 5 outputs along the right-hand side are: C4 on pin 14, S4 on pin 15, S3 on pin 2, S2 on pin 6, and S1 on pin 9. 

Logic diagram (NOT a pinout) for the 7483.

A drawing on a whiteboard showing how to connect the input pins of the 7483 to the logic switches on the board. Lines curve around and across each other in many places to show the following connections: First, pin 5 to Vcc, pin 12 to ground, and pin 13 to PB1. Next: pin 1 to switch 5 (labeled A4), pin 3 to switch 6 (A3), pin 4 to switch 2 (B3), pin 7 to switch 3 (B2), pin 8 to switch 7 (A2), pin 10 to switch 8 (A1), pin 11 to switch 4 (B1), and pin 16 to switch 1 (B4). 

How to connect the inputs (output connections not shown). Ordering and grouping of A and B inputs is important.

Exercise 11:

Wire up the chip, following these guidelines:

  • Use logic switches on the board for the A and B inputs, and the PB1 switch for C0.
  • It is best to group the A switches next to one another (don’t alternate with the B switches), and arrange the input switches so the most significant bit is on the left (see diagram on the right).
  • Connect all 5 outputs to logic indicators, in order with S1 on the right, S2 to its left, etc. Leave a gap between S4 and C4 for clarity.
  • Don’t forget to connect Vcc and GND.

REMEMBER: the actual chip layout has pin 1 on the upper left, with 8 pins on each side of the chip numbered counterclockwise around it.

Now that it’s working, perform the following tests:

Set the A4 A3 A2 A1 and B4 B3 B2 B1 inputs to the numbers shown below, and record the outputs for each setting:

A inputs 0001

B inputs 0001

C0 off (i.e., 0)

GCorrect answer:

C4 0
 1

S4 0
 1

S3 0
 1

S2 0
 1

S1 0
 1

Correct answer: See above

A inputs 0010

B inputs 0011

C0 off (i.e., 0)

GCorrect answer:

C4 0
 1

S4 0
 1

S3 0
 1

S2 0
 1

S1 0
 1

Correct answer: See above

A inputs 0010

B inputs 0011

C0 pressed (i.e., 1)

GCorrect answer:

C4 0
 1

S4 0
 1

S3 0
 1

S2 0
 1

S1 0
 1

Correct answer: See above

What function do you think the chip is performing?

Example answer: 4-bit addition, with carry-in and carry-out.

What is the purpose of C4? Is it correct for the calculations above?

Example answer: C4 is the carry-out bit. It’s off in all results above, as it should be.

Next, set A to 1010 and B to 1111 leaving C0 off, and record the result:

GCorrect answer:

C4 0
 1

S4 0
 1

S3 0
 1

S2 0
 1

S1 0
 1

Correct answer: See above

Click to select answers for these questions, assuming a 4-bit two’s-complement (i.e., signed) representation:

GCorrect answer:

Is this result correct? no
 yes

Is there carry-out? no
 yes

Is there overflow? no
 yes

Correct answer: See above

Extra Exercises: 4-bit Ripple-Carry Adder

It turns out that once you have a 1-bit adder, you can do nn-bit addition by using nn 1-bit adders: one for each matched pair of bits in the two nn-bit numbers being added. The CarryOut for each pair of bits becomes the CarryIn for the next most significant pair of bits in the numbers. This is known as a ripple-carry adder.

Exercise 11:

Use either LogicWorks or the Falstad simulator to build a 4-bit adder out of 1-bit adders:

LogicWorks

  1. Download this 4bit-adder circuit template and then open it in LogicWorks. It contains four 1-bit adders (the adder device is an abstraction for the 1-bit full adder you experimented with earlier).
  2. Add hex keyboards for the A and B inputs. Connect the individual bits from each keyboard to one of the 1-bit adders.
  3. Add a “Hex Display” and connect the four outputs to it.
  4. Add a binary switch for the carry-in and a binary probe for the carry-out.
  5. Connect the carry-out / carry-in lines between each of the adders.

Falstad

  1. Start from the circuit below, which includes 4 1-bit adders, 8 logic inputs, and hex displays for both the two inputs and the output.
  2. You do NOT need to connect anything to the bottom displays, they will display the inputs automatically once everything is hooked up.
  3. Connect the 8 inputs to the 8 input lines of the 4 adders. Make sure to connect A0/B0 to the bottom adder and move upwards from there.
  4. Add a 9th input for the carry-in.
  5. Add a logic output for the carry-out.
  6. Connect together the carry-out / carry-in lines between the adders.
  7. Connect the S outputs to the I0-I3 inputs to the display at the top right.

Perform the following tests to verify the circuit:

2 + 5 = Correct answer: 7

A + 3 = Correct answer: D

A + A = Correct answer: 4 (should have carry-out; this is overflow)

6 + 5 = Correct answer: B (no carry-out, but this is overflow)

F + F (with carry-in on) = Correct answer: F (carry-out and overflow)

Extra Practice

Exercise 12:

Build a 1x4 demultiplexer and/or a 4x2 encoder in LogicWorks or the Falstad simulator (blank window below):

Exercise 13:

Hook up two 4-bit adders to create an 8-bit adder. Note: In Falstad, you can right-click an adder to select how many bits you want.