CS 240 Lab 3

Data as Bits

Show all answers Hide all answers

CS 240 Lab 3

• Lab slides
• Learning Goals & Reflection

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.

Use this link to open CircuitVerse, and then download & import this circuit project. If it stalls during loading check this lab 2 footnote. The project file contains all of the circuits you’ll need for this lab in different tabs, including blank tabs for circuits you should build yourself.

Open the “8x1 Mux” tab and follow these steps:

1. From the “Decoders and Plexers” section the “Circuit Elements” panel, select a “Multiplexer” and add it to your circuit.
2. Select the multiplexer, and in the “Properties” panel, set the “Control Signal Size” to 3. The size should increase and there should now be 8 inputs instead of just 2.
3. Connect the 8 D0-D7 inputs that are already set up to the 8 inputs on the left side of the multiplexer.
4. Connect the output of the multiplexer to the Q output.
5. Connect the 0:2 wires that are split off from the “Keyboard Hexer” upwards to the select input of the multiplexer (one line in the simulator will hold all 3 wires at once).

But how can you hook up 3 wires with just one line?

In the “8x1 Mux” tab in CircuitVerse, when we insert the 8x1 multiplexer, it only has 1 connection on the bottom, but we need 3 bits to select one of 8 inputs. As it turns out, CircuitVerse has the ability to use lines in a circuit diagram to represent a bundle of wires instead of just a single wire. Instead of light or dark green to indicate high or low voltage, a bundle of wires will just show up as black. These are created automatically when connecting from or to multi-bit inputs/outputs. For example, at the bottom of the circuit template there’s a “Keyboard Hexer” and the right-side output from that is a 4-wire bundle (because a hex digit is represented using 4 bits).

The circuit actually splits up the 4 bits from the hex digit into one group of 3 plus a leftover bit that we leave disconnected. That’s called a “breakout” (or a “splitter” in CircuitVerse terminology). This diagram shows how a breakout circuit symbol would actually work in terms of wires:

 

The breakout symbol shows one wire bundle coming in and splitting up into one or more groups, with the numbers indicating which wire(s) go in which group(s). In a physical circuit, you’d have multiple insulated wires bundled together and then some of them would split off into a different bundle. We count wires that represent numbers starting from the least-significant bit of a binary number as ‘0’. So if we took the hexadecimal digit 9 (1001 in binary) and split it into “0:1”, “2”, and “3” groups, the “0:1” group would be binary 01 (the two least-significant bits), the “2” group would be a 0, and the “3” group would be a 1.

If we split 4 wires into “0:2” and “3” groups, and the 4 wires had bit pattern 1101 for the number 13 (hex digit D), what bits would the first group have in it?

🤨🤔Correct answer: 101Correct!Incorrect.Explanation: The first group takes the 3 least-significant bits, so the 1s, 2s, and 4s places. The other wire split off would be a 1.

Now that things are hooked up, you can click on the keyboard input and type in a hex digit to set the values of the select lines. Answer these questions:

1. Which hex digit should you use to set the select lines to S0 = 0, S1 = 1, and S2 = 1?

   🤨🤔Correct answer: 6Correct!Incorrect.Feedback: This would also work, since E is 1110, and the 4th bit is discarded.Feedback: We expected just ‘6’ but this is correct.Explanation: 6 is 0110 and E is 1110, so either will work since we discard the 4th bit.

2. Set the select lines to S0 = 0, S1 = 1, and S2 = 1 by entering the hex digit you just identified on the keyboard input (click to select it then type the digit on your keyboard). With this select configuration, which of the 8 data input(s) affects the output (toggle them to test)?

   🤔Example answer: Only input number 6 will affect the output.

3. Now set the select lines to S0 = 1, S1 = 0, and S2 = 0 (enter ‘1’ on the keyboard). Does the same input still affect the output? yesno🤨🤔

   Correct Answer(s):
   no
   
   Correct!Incorrect.

   Which input(s) will affect the output now?

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

4. 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 $2^n$ data inputs for $n$ select bits.

Exercise 2:

The “4x1 Mux Gates” tab in CircuitVerse has an implementation of a 4x1 multiplexer using basic gates.

Edit the circuit by removing components to create a 2x1 multiplexer. Verify that it works by manipulating your inputs and observing the output, and then describe your circuit below:

How many different input combinations should you test to thoroughly test the circuit? 🤨🤔Correct answer: 8Correct!Incorrect.Explanation: Since there are 3 inputs (2 data inputs and 1 select input) we have $2^3 = 8$ possible input combinations to test.

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.

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 (answer some of the questions below to help figure out how).

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)!

The enable line (pin 7) is called active low. In the pinout diagram, it has a bar above an E, where the bar is the same notation used for NOT in boolean logic (sometimes you’ll see a little circle on the corresponding leg of the chip for a NOT gate instead). Inputs and outputs that are active low are active when voltage is low, rather than high like most other inputs/outputs. So to enable this chip, you must connect pin 7 to ground (low voltage)

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

0
1
3
8
🤨🤔

Correct!Incorrect.

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. 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 \times 2^n$ decoder has $n$ inputs and $2^n$ outputs. Only one of the outputs is active for any given $n$-bit input combination.

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

Q0 is only true when D1D0 = 00 Q1 is only true when D1D0 = 01 Q2 is only true when D1D0 = 10 Q3 is only true when D1D0 = 11

This can be described by the following truth table:

D1	D0	Q0	Q1	Q2	Q3
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.

On the pre-lab, you should have designed a circuit that looks something like this:

 

Build the circuit for the 2x4 decoder in CircuitVerse using the “2x4 Decoder” tab (it should be blank at first).

Notes on building the decoder:

1. You’ll have to add inputs and outputs. These will show up in the “Decoder test” tab as you add them.
2. You’ll find the gates you need in the “Gates” tab of the “Circuit Elements” panel.
3. Use the “Properties” pane to add labels to each input & output so you can tell which is which. Label your inputs D1 and D0 and your outputs Q0 through Q3.

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

D0
D1
D2
D3
🤨🤔

Correct!Incorrect.

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

D0
D1
D2
D3
🤨🤔

Correct!Incorrect.

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

Open the “Decoder test” tab in CircuitVerse. This is set up to test both your decoder implementation and the solution. The big chips in the middle are custom “tester” chips that read test inputs and expected outputs from a memory bank and then light up the “Wrong” light if a particular input doesn’t match the associated output (the “Failed” light lights up when the “Wrong” light does and stays on until the chip is reset). To use them, you can:

1. Hook up as many of the T0-T3 outputs as you need to the inputs of the chip being tested.
2. Hook up as many of the R0-R3 inputs as you need to the outputs of the chip being tested.
3. Connect a “Read-Only Memory” (ROM) chip from the “Sequential Elements” section of the “Circuit Elements” panel to the Taddr and Test lines at the bottom.
4. Enter values into the ROM by clicking on individual squares in the grid and typing them in. Each 2-digit value (8 bits) is split into 4 bits of “test input” and 4 bits of “expected output.”
5. Toggle the “RST” line on and then off again to reset the tester.
6. Each time you toggle the clock, it will switch to the next test stored in the ROM. When a test fails, it will light up the wrong/failed lights (and keep the failed light on until reset). Keep toggling the “CLK” input until you’ve run all the tests you want to.

During testing, the digits on the face of the chip will show the current inputs being sent to your chip, the current result from your chip, the expected result for those inputs, and which bit(s) have errors (each digit displays only a single bit).

We’ve done steps 3-4 above already. You just need to do steps 1 and 2, and then 5 and 6.

Demonstrate correct operation of the test setup 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:

 

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:

C	B	A	Y0	Y1	Y2	Y3	Y4	Y5	Y6	Y7
0	0	0	01 Correct Answer(s): 0	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1
0	0	1	01 Correct Answer(s): 1	01 Correct Answer(s): 0	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1
0	1	0	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 0	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1
0	1	1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 0	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1
1	0	0	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 0	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1
1	0	1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 0	01 Correct Answer(s): 1	01 Correct Answer(s): 1
1	1	0	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 0	01 Correct Answer(s): 1
1	1	1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 1	01 Correct Answer(s): 0

🤨🤔Correct answer: See aboveCorrect!Incorrect.

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

Demultiplexer

A demultiplexer is the exact opposite of the multiplexer.

 

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.

S1	S0	D	Q3	Q2	Q1	Q0
0	0	0	01 Correct Answer(s): 0	01 Correct Answer(s): 0	01 Correct Answer(s): 0	01 Correct Answer(s): 0
0	0	1	01 Correct Answer(s): 0	01 Correct Answer(s): 0	01 Correct Answer(s): 0	01 Correct Answer(s): 1
0	1	0	01 Correct Answer(s): 0	01 Correct Answer(s): 0	01 Correct Answer(s): 0	01 Correct Answer(s): 0
0	1	1	01 Correct Answer(s): 0	01 Correct Answer(s): 0	01 Correct Answer(s): 1	01 Correct Answer(s): 0
1	0	0	01 Correct Answer(s): 0	01 Correct Answer(s): 0	01 Correct Answer(s): 0	01 Correct Answer(s): 0
1	0	1	01 Correct Answer(s): 0	01 Correct Answer(s): 1	01 Correct Answer(s): 0	01 Correct Answer(s): 0
1	1	0	01 Correct Answer(s): 0	01 Correct Answer(s): 0	01 Correct Answer(s): 0	01 Correct Answer(s): 0
1	1	1	01 Correct Answer(s): 1	01 Correct Answer(s): 0	01 Correct Answer(s): 0	01 Correct Answer(s): 0

🤨🤔Correct answer: See aboveCorrect!Incorrect.

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

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: 5Correct!Incorrect.

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

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

Encoder

An encoder is the exact opposite of the decoder.

 

It takes $2n$ 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 (partial) truth table for the 4x2 encoder:

D3	D2	D1	D0	Q1	Q0
0	0	0	1	01 Correct Answer(s): 0	01 Correct Answer(s): 0
0	0	1	0	01 Correct Answer(s): 0	01 Correct Answer(s): 1
0	1	0	0	01 Correct Answer(s): 1	01 Correct Answer(s): 0
1	0	0	0	01 Correct Answer(s): 1	01 Correct Answer(s): 1

🤨🤔Correct answer: See aboveCorrect!Incorrect.

Why doesn’t this truth table need 16 rows for 4 inputs?

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?

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 the “Half Adder” tab of the CircuitVerse project, build the circuit which produces Sum and CarryOut from inputs A and B. 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:

CarryOut = 01

and Sum = 01

🤨🤔Correct answer: See aboveCorrect!Incorrect..

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:

 

Exercise 10:

In the “Full adder” tab of CircuitVerse, build a full adder.

Go to the “Adder test” tab and cycle through the test cases to make sure it works (yours in on the left, solution is on the right).

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:

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:

What function do you think the chip is performing?

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

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

C4 01

S4 01

S3 01

S2 01

S1 01

🤨🤔Correct answer: See aboveCorrect!Incorrect.

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

Is this result correct? noyes

Is there carry-out? noyes

Is there overflow? noyes

🤨🤔Correct answer: See aboveCorrect!Incorrect.

Extra Exercises: 4-bit Ripple-Carry Adder

It turns out that once you have a 1-bit adder, you can do $n$-bit addition by using $n$ 1-bit adders: one for each matched pair of bits in the two $n$-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 the “4-bit Ripple-Carry” tab in circuitVerse to build a 4-bit adder out of 4 1-bit adders. All the necessary components are there already; you just need to hook up the inputs and outputs.

Perform the following tests to verify the circuit:

2 + 5 = 🤨🤔Correct answer: 7Correct!Incorrect.

A + 3 = 🤨🤔Correct answer: DCorrect!Incorrect.

A + A = 🤨🤔Correct answer: 4Correct!Incorrect. (should have carry-out; this is overflow)

6 + 5 = 🤨🤔Correct answer: BCorrect!Incorrect. (no carry-out, but this is overflow)

F + F (with carry-in on) = 🤨🤔Correct answer: FCorrect!Incorrect. (carry-out and overflow)

Extra Practice

Exercise 12:

Build a 1x4 demultiplexer and/or a 4x2 encoder in CircuitVerse (create a new tab for this purpose by clicking the ‘+’ icon in the tabs tray).

Exercise 13:

Hook up two 4-bit adders to create an 8-bit adder. Make a new tab, and use “Circuit -> Insert SubCircuit” to add two copies of your “4-bit Ripple-Carry” circuit (you can also add one and then copy/paste it).