CS 240 Lab 4

ALU & Sequential Logic

CS 240 Lab 4

• Lab slides
• Learning Goals & Reflection

In lab today, you will investigate the circuit which allows you to perform a variety of logical and arithmetic operations, the Arithmetic and Logic Unit (ALU), which is an essential part of a computer processor.

You will also investigate the behavior of several sequential logic circuits, which form the basis for the various kinds of memories needed to implement a computer.

Arithmetic Logic Unit

An Arithmetic Logic Unit (ALU) is a combinational circuit used to perform all the arithmetic and logical operations for a computer processor, and can be built using basic components that you are familiar with.

You saw a very simple ALU on the lab assignment. The circuit below also uses an additional set of 2x1 multiplexers at the inputs, controlled by new control lines “Invert A,” “Invert B, and it has a”Carry in” line.

“Invert A” allows you to invert the A input (for logical operations), and “Invert B” does the same for the B input.

“Carry in” allows you to add a carry-in bit to the adder, and when combined with “Invert B,” this lets you do subtraction, since (~B + 1) = -B, and thus A + (~B + 1) = A - B.

In the following circuit, the box with + is a 1-bit adder. The “invert B” and “Carry in” inputs have been combined into one “Negate B / Carry-in” input. Assume Operation is a 2-bit value Op1 Op0.

 

The basic operations are:

The following partial truth table shows the inputs necessary to enact each of these operations. Note the clever use of DeMoragn’s law to get NAND and NOR operations. Also note that we can use one column for both “invert B” and “Carry in” because their values can be the same in every row.

invert A	invert B/Carry in	Op1	Op0	Result
0	0	0	0	A AND B
0	0	0	1	A OR B
0	0	1	0	A + B
0	1	1	0	A – B
1	1	0	0	A NOR B
1	1	0	1	A NAND B

Exercise 1:

Predict the results for this circuit (the answers to the first combination of inputs are shown; click in the Cout and Result columns to cycle through answers):

A	B	invA	invB/Cin	Op1	Op0	Cout	Result	Check	Description
0	0	0	0	0	0	0	0		Result: 0 (0 AND 0) Cout: 0 (0 + 0 has no carry-out)
GCorrect answer: 0	1	0	0	0	1	0 1	0 1	Correct answer: See above	Example answer: Result: 1 (0 OR 1) Cout: 0 (0 + 1 has no carry-out)
GCorrect answer: 0	1	0	0	0	0	0 1	0 1	Correct answer: See above	Example answer: Result: 0 (0 AND 1) Cout: 0 (0 + 1 has no carry-out)
GCorrect answer: 1	1	0	0	1	0	0 1	0 1	Correct answer: See above	Example answer: Result: 0 (1 + 1) Cout: 1 (1 + 1 has carry-out)
GCorrect answer: 0	1	0	1	1	0	0 1	0 1	Correct answer: See above	Example answer: Result: 1 (0 + 0 w/ carry-in) Cout: 0 (0 + 0 + carry-in has no carry-out)
GCorrect answer: 1	1	0	0	0	0	0 1	0 1	Correct answer: See above	Example answer: Result: 1 (1 AND 1) Cout: 1 (1 + 1 has carry-out, even though that’s not the operation we care about)
GCorrect answer: 1	1	1	1	0	0	0 1	0 1	Correct answer: See above	Example answer: Result: 0 (0 AND 0 since A and B are inverted) Cout: 0 (0 + 0 + carry-in has no carry-out)

Download this aluparts.cct circuit and then open it in LogicWorks, or work in the Falstad window below, to build a 1-bit ALU by connecting the provided parts together.

Note: In the Falstad simulator you can hover over a component to see its name.

Verify your predicted results by setting the inputs from the table above and checking that the outputs match what you expected. Click this button to show the intended connections if you get stuck:

Exercise 2:

It is possible to make a 4-bit ALU by connecting four 1-bit ALUs together in a similar way to how you connected 4 1-bit adders to make a 4-bit adder in lab last week (for this they need separate invert-B and carry-in inputs):

Without testing it in the simulator above, predict the results for this 4-bit ALU in the table below, taking into account:

• A and B are 4-bit values represented by hex digits, and are signed two’s complement representations. Use this hex reference to help you translate between hex, binary, and decimal.
• The Result is a 4-bit value and should be written as a hex digit.
• Cout, Sign, and Overflow are single bits.
• Cout and Overflow are produced according to the addition operator, even when the circuit is performing a different operation.

The definitions for each column are:

• Result is the result for the selected operation.
• Cout is the carry-out bit from addition. This is always computed by the adder, whether or not the operation is addition.
• Sign is the sign bit of the result (the most-significant bit).
• Overflow is true if there’s overflow from the adder (assuming signed two’s-complement numbers). Overflow is always computed by the adder, whether or not the operation is addition.
• Zero should be true if and only if the result is exactly 0.

Function	Test Inputs	Result (in hex)	Cout	Sign	Overflow	Zero	Check
A + B	A=3, B=7	A	0	1	1	0
GCorrect answer: A + B	A=F, B=E	Correct answer: D	0 1	0 1	0 1	0 1	Correct answer: See above
GCorrect answer: A AND B	A=1, B=F	Correct answer: 1	0 1	0 1	0 1	0 1	Correct answer: See above
GCorrect answer: A AND B	A=7, B=8	Correct answer: 0	0 1	0 1	0 1	0 1	Correct answer: See above
GCorrect answer: A OR B	A=3, B=C	Correct answer: F	0 1	0 1	0 1	0 1	Correct answer: See above
GCorrect answer: A NOR B	A=6, B=9	Correct answer: 0	0 1	0 1	0 1	0 1	Correct answer: See above
GCorrect answer: A - B	A=3, B=4	Correct answer: F	0 1	0 1	0 1	0 1	Correct answer: See above
GCorrect answer: A - B	A=C, B=9	Correct answer: 3	0 1	0 1	0 1	0 1	Correct answer: See above
GCorrect answer: A + B	A=5, B=4	Correct answer: 9	0 1	0 1	0 1	0 1	Correct answer: See above

Exercise 3:

Given the simulated 4-bit ALU above, describe the underlying connections/logic needed to produce the Sign, Overflow, and Zero outputs (including any gates that are required).

Sign bit:

Example answer: The sign bit is wired to the most-significant bit of the 4 output lines, which is the sign bit in two’s-complement arithmetic.

Overflow bit:

Example answer: The more complex way is to do (NOT(A3 XOR B3)) AND (A3 XOR R3). This breaks down into NOT(A3 XOR B3) which is true when A3 is the same as B3, along with A3 XOR R3 which is true when A3 is different from R3. In other words: “Signs were the same going in, but we got the opposite sign coming out.” An easier way to implement this is to just XOR the carry-in and carry-out for the last 1-bit ALU. That works because if there’s carry-in, there will be carry-out unless both sign bits are 0, in which case there must be overflow since we had two zeroes going in but a carry means a 1 will go out. On the other hand, if there’s no carry-in, there can only be carry-out if both sign bits were 1’s, meaning we added two negative numbers and due to carry-out ended up with a positive number.

Zero bit:

Example answer: The Zero bit is wired to the result of a 4-input NOR gate (or several 2-input OR gates with a NOT gate at the end to emulate a 4-input NOR) that takes all 4 bits of output as its inputs. That way, the Zero bit is 1 when the value of the output is exactly 0000₂, and 0 otherwise.

Exercise 4:

Now add the gates you just described to the simulator above, so that in addition to result and carry outputs, it has 1-bit outputs for Sign, Overflow, and Zero.

Verify that your outputs work by comparing against the table above, then check your design against the example below.

SR Latch

The SR latch is the basic unit of memory in most modern computers:

S means set the output to 1, and R means reset the output to 0. The two outputs Q and Q’ should always be opposites of each other.

Qp is the previous state of the latch. If you neither set or reset the circuit, it remembers its previous state. This means it is a bistable circuit: it has two stable voltage configurations, and external input can force it to swap between them.

Exercise 5:

First, plan out how you will connect the circuit, by filling in the following table:

Purpose	Comes from	Connect to	Check row
R input	logic switch	pin 2	N/A
Q output	GCorrect answer: … pin 1 pin 2 pin 3 pin 4	pin 5 and … logic indicator pin 3 pin 4 pin 6	Correct answer: See above
S input	GCorrect answer: … pin 1 logic switch pin 4	… pin 3 pin 4 pin 6	Correct answer: See above
Q’ output	GCorrect answer: … pin 1 pin 2 pin 3 pin 4	… pin 3 pin 4 pin 5 and logic indicator	Correct answer: See above

Verify the circuit by following these steps:

1. Set S=1 and R=0. What is Q? 0
   1
   

2. Now set S=0 and R=0. What is Q? 0
   1
   

3. Now set R=1, leaving S=0. What is Q? 0
   1
   

4. Set R back to 0, leaving S=0. What is Q? 0
   1
   

   Why doesn’t Q return to 1, the value it had last time S=0 and R=0?

   Example answer: Since the most recent value was Q=0, and we’ve only turned off inputs since then, without a reason to swap to the other stable configuration, the circuit stays in the one it’s in, where Q=0.

5. Now set both S=1 and R=1. What happens to Q and Q’?

   Example answer: They’re both set to 0, since both NOR gates have an active input. This violates the design principle that they should be opposites.

6. Now set S=0 and R=0, and turn off the board, then turn it back on. What is the value of Q? Explain why the answer to that question is complicated:

   Example answer: Since the board was powered off, the remembered value gets cleared out (all wires return to neutral voltage). When you power it on, neither NOR gate has high-voltage inputs, since R=0 and S=0, and the feed-back connection isn’t high-voltage to start with. Both gates will try to activate simultaneously, since NOR logic dictates their output should be high if both inputs are off. This sends power to one input of both gates, and so they then both try to deactivate, restarting the cycle. Practically, one of them will be slightly faster to activate eventually, preventing the other gate’s signal from flipping and thus stabilizing the circuit. But we can’t easily predict which one it will be, since it might depend on factors like precise manufacturing details of the chip, temperature of the two specific gates used in the chip, humidity, etc.

Don’t disconnect your circuit! You use it in the next exercise.

Clocked SR Latch

Certain circuits require that the action of the latches in the circuit occur simultaneously, and that they can wait to receive updates until other parts of the circuit have time to settle. This can be accomplished through synchronization with a common clock input.

Exercise 6:

Modify your previous circuit so that it is a clocked SR latch:

 

You will need to connect to a 7408 AND chip, using switch PB1 or PB2 as your clock. The 7408 chip is inserted BELOW the 7402 chip you wired in the previous exercise, and uses the following pin-out:

 

Verify the correct operation of the latch as follows:

1. Without pushing the clock button, set S=0 and R=0. Then flip through all four combinations of S and R. Why didn’t the outputs change?

   Example answer: Without the clock on, the latch part just sees both inputs as 0s, since neither AND gate activates.

2. Set S=1 and R=0, then push and release the clock button. What is the value of Q? 0
   1
   

3. Now set S=0 and R=1, and push the clock button again. What is the value of Q? 0
   1
   

   Did Q change when the button was pressed in, or when it was released (test again if you need to)? When it was pressed (rising edge).
   When it was released (falling edge).
   

4. Now set S=0 and R=0, and push the button. What is the value of Q? 0
   1
   

5. Without pressing the clock, flip S on and then off again. When it’s off, press the clock. Did Q’s value change? no
   yes
   

6. Set S=1 and R=1, and push and hold the button. Observe the value of Q while holding the button, and then release it. Explain why you cannot predict the value of Q after the button is released:

   Example answer: This is the same situation as before, where with both NOR gates inactive due to active inputs from S and R, if you simultaneously turn those inputs off (such as by turning off the clock signal that’s connected to both), the system enters an unstable state. Whichever gate activates faster will stabilize it, but it’s not easy to predict which gate will win.

D Latch and Flip-Flop

The SR latch should only ever receive inputs 00, 10, and 01. 11 is problematic because it sets both Q and Q’ to 0, and because if we transition from 11 to 00, the outcome is unpredictable. The D latch makes a 11 input to the latch portion impossible, by using a single D input instead of S and R inputs, along with a clock. Here’s a circuit diagram for a D latch:

 

Note: The “CLK” input above is not an actual clock element, it’s just a logic input labeled “CLK.” We do this so that we can have manual control over when the clock shifts, instead of having to work around a constantly changing real clock.

Exercise 7:

Implement the clocked D latch circuit in LogicWorks, or in the Falstad simulator:

When you first connect the circuit, it will be in an unpredictable state. Pulse the clock once to achieve valid inputs.

Verify your circuit by following these steps:

1. Set D to 0, and CLK to 1; then set CLK back to 0. What is the value of Q? 0
   1
   
2. Set D to 1. Does Q change? no
   yes
   
3. Set CLK to 1. What is the value of Q? 0
   1
   
4. Now set CLK back to 0. Does the value of Q change? no
   yes
   

What inputs should be used to set or reset the output, and what inputs can be used to remember the previous output?

Example answer: When you turn the clock on, set D to 1 to set the output, and set D to 0 to reset the output. Turning the clock off remembers the most recent setting, even when D changes.

Explain why this circuit solves the problem of S=R=1:

Example answer: The D input is sent to each AND gate but one of the lines is inverted, so it can ONLY send the equivalent of S=1/R=0 or S=0/R=1. This isn’t useful without the clock mechanism, as it wouldn’t be able to send S=0/R=0, but when the CK input is off, the latch gets S=0/R=0 and remembers the most recent state.

Exercise 8:

A D latch will change its state each time D changes, as long as the clock remains on. However, it would be even better to have a circuit which can “observe” D only for an instant, and then remember it the rest of the time. This is called a D flip-flop, and it changes its state only at the falling edge of the clock, remembering that observed state at all other times.

Next, construct a D flip-flop with a falling-edge trigger in one of the two simulators:

Use the timing window in LogicWorks or the scopes in the Falstad simulator to observe the behavior of the circuit over time, and answer these questions:

1. Toggle the D input off, and wait until Q2 becomes 0.
2. Try to quickly toggle the D input on and then off in such a way that the Q1 input never changes. When is this possible? Example answer: When the clock input is low, toggling the D input does not affect Q1 or Q2, so if you toggle D on and then back off before the clock input turns on again, Q1 will not change.
3. Now try to quickly toggle the D input on and then off so that Q1 changes to a 1 and then back to a 0, without ever changing Q2. When is this possible? Example answer: When the clock input is high, D directly affects Q1, but Q1 does NOT affect Q2. So during the on phase of the clock, you can toggle D1 on and then back off, which will also toggle Q1 for the same duration, but Q2 will not be affected.
4. Now turn D on and keep it there. When does the Q2 output change, relative to the clock signal? Example answer: It changes on the next falling edge of the clock that occurs after the D signal becomes a 1.
5. Now turn D off again, and observe when Q2 turns off. When does it change, relative to the clock signal? Example answer: It changes on the next falling edge of the clock that occurs after the D signal becomes a 0.

This circuit remembers input, but only observes that input when the clock signal changes from high to low. This means that it can simultaneously receive input for a new state, while sending output from its old state, and flip over from the old to the new in an instant. Try the following:

1. Disconnect the input switch from the D input (you can just drag it to the side in the Falstad simulator or use the lightning tool in LogicWorks to remove the connection).
2. Take the output Q2 and connect it to a NOT gate oriented back towards the start of the circuit.
3. Connect the output of that NOT gate back to the D input of the first D latch, where you just disconnected the input switch.

Notice: if this were a D latch, by connecting the output back to the input via a NOT gate, you’d have an inconsistent circuit: as soon as you turned the clock on, the circuit would rapidly flip back and forth between on and off, and it would be difficult to predict the state it would end up in when you turned off the clock. However, this circuit is different. Describe what happens if you connect the output Q2 through a NOT gate back to the input D:

Register

You can do the following with this device:

• You can read the current contents of the register at the outputs Q15..0
• You can write a new value to all 16 bits at once by setting the value at the inputs D15..0, and then pulsing (setting to high, then back to low) the CLK input.
• You can also clear all 16 bits to 0 at any time by activating the CLR input (when not using the CLR input, keep it set to 0).

Exercise 9:

For this exercise, either download this register circuit and open it in LogicWorks, or work in the frame below where we’ve set up a similar circuit in the Falstad simulator.

The inputs to the register should all be zeroes, but notice that the outputs are not all zeroes. How is this possible?

Example answer: The register stores data, and only updates when the clock input is pulsed. So although the inputs are zeroes, the stored data matches what is shown in the hex displays.

Now pulse the clock input (CLK in LogicWorks and Ld in Falstad) to forward through the inputs, setting the outputs to zeroes. Then, manipulate the circuit so that the output shows “C5F0” from top to bottom, and describe what you did:

Example answer: First, set the inputs to “C”, “5”, “F”, and “0”, which in binary becomes 1100, 0101, 1111, and 0000. Next, turn the clock on and off again, to trigger an update of the stored value.

Stretch Exercises: Register File

A register file is a set of registers that can be read from and written to. We number the registers in the set, and use the numbers to specify which registers from the set are accessed at any particular time.

Our register file has 16 registers, numbered 0 to 15 (note that it takes 4 bits to encode the register number).

Each register stores 16 bits of data (similar to the register from the previous exercise).

Registers 0 and 1 don’t store data like the others, instead they are always set to 0 (for register 0) and 1 (for register 1).

Below is an abstraction for a register file. You can read the data from each of 2 registers and write new data to a third register simultaneously.

 

To read the contents of 2 registers at any given time, specify the number of the first register at the Read register 1 input, and the number of the second register on Read register 2.

The contents of the two registers are then available at the Read data 1 and Read data 2 outputs.

To write a new value to a specified register, set the Write register”” input to the number of the register, set the Write data** inputs to the value to be written to the register, and then pulse the Write line.

Exercise 10:

Download this regfile.cct circuit and then open it in LogicWorks (we don’t have a Falstad implementation this time).

The blue wires that split into many labeled ends are called “buses,” and the parts that split out are “breakouts.” You can use the heavy + tool to create buses, and you can right-click on a bus to create a breakout by entering the wire names you’d like to use. For example, entering “D0..15” will create a 16-wire breakout. Breakout ends with the same name only count as connected if there is a bus connecting the two breakouts.

To read the values currently stored in the registers, do the following:

1. Set the Read register 1 and Read register 2 inputs to register numbers you wish to read from (start with 0 and 1).

2. Examine the value stored at those registers at the outputs Read data 1 and Read data 2.

Write the value stored in each register from the table below. (Write values as upper-case 4-digit hex numbers, without any prefix). Remember you can read two at a time.

GCorrect answer:

• Register 0: Correct answer: 0000
• Register 1: Correct answer: 0001
• Register 2: Correct answer: C5F0
• Register 3: Correct answer: FEED

Correct answer: See above

To clear all the registers, set Write = 0 and pulse CLR (this input is controlled by a push-button, so click once to pulse). Do this now.

Next, follow these directions to write values to registers 4 and 5:

• Set Write = 1.
• For each register:
  • Set Write register to the number of the register to write to.
  • Set Write data to the data specified.
  • Pulse the CLK.
• Set Write back to 0 to disable writes.

Register	Data
4	FACE
5	ACED

After you have written these values specified, set the circuit to read registers 4 and 5. Confirm the following:

GCorrect answer:

• Value of Read Register 1: Correct answer: 4
• Value of Read Register 2: Correct answer: 5
• Value of Read Data 1: Correct answer: FACE
• Value of Read Data 2: Correct answer: ACED
• Clock pulses required to write registers 4 an 5: Correct answer: 2

Correct answer: See above

Below is LogicWorks circuit which implements a register file for a set of 4 4-bit registers. Register 0 always produces a value of 0, and register 1 always produces a value of 1 (those values are hardwired in this circuit).

This register file circuit is small enough that you can examine and understand the underlying circuitry:

 

Exercise 11:

What is the purpose of the decoder device in the circuit?

Example answer: It turns a binary number specifying which register to write into a 1-hot encoding so that the clock for the indicated register can be turned on when the CLK button is pushed while all other clocks are left off.

Explain how the multiplexers are used to produce the value of the specified registers at the Read data 1 and Read data 2 outputs:

Example answer: Four multiplexers are used for each read output, each taking one signal from each register. Each multiplexer handles the output for a particular bit (so e.g., it reads bit 0 of each of the 4 registers and writes bit 0 of the read output). The multiplexers all receive the same select inputs (from the read register 1 or read register 2 input, depending on which output they’re for). This means that all 4 bits of e.g., register 2 will be sent to the read data 1 output when 2 is selected in binary as the read register 1 input.

Extra exercises: RAM Memory

This exercise will show you how a RAM device is used to store and retrieve values from memory.

Download this instructionMemory.cct circuit and then open it in LogicWorks:

 

This circuit can be used to store data into addresses of a RAM memory, which is necessary for loading a program into the instruction memory.

Examine the circuit carefully to understand its operation: you write data values into a memory location specified by an address by using the hex keyboards on the left to specify the data and address.

The currently selected address and the value stored at that address are displayed on the hex displays on the right.

Exercise 12:

To read from memory: 1. Set Load to 0 (the Load line connects the address switches to the memory chip through the tri-state buffers, which let a signal through only when Load is set to 0. When inactive, the tri-state buffers have neither high nor low output, which LogicWorks shows as an ‘X’). 2. Select the address you want to read from on the Address in keyboards. 3. The data at that address will appear on the Data bus at the right.

Read the data at addresses 0 through 3, and confirm it below (enter just the 4 hex digits you see, from top to bottom):

GCorrect answer:

Address 00: Correct answer: 5002

Address 01: Correct answer: 5003

Address 02: Correct answer: 5003

Address 03: Correct answer: 0230

Correct answer: See above

Exercise 13:

To write to memory (load a program): 1. Set Load to 0. 2. Set the Address switches to the location in memory at which you wish to write a data value. 3. Set the Data switches to the value you wish to write to that location. 4. Set Write to 0, then back to 1 (writes the data input into the specified address in memory). 5. Repeat steps 2 - 4 for each address and its data value.

Using the write procedure, load the following data values to the specified addresses:

Addr	Data
00	5002
02	5003
04	1220
06	0230
08	2122
0A	8001

As you write the values, you will observe the address and data values on the data and address bus displays. At any time, you can observe the contents of an address by setting the address switches to the desired location (without toggling the Write switch).

When you are finished, set Load = 1 to disable the address inputs.

This will always be required when the user is finished loading the program into memory, and wishes to run the program. When RAM is used as part of a full computer, the address is supplied by the CPU during execution of the program, so the switches are not needed at that point (and would interfere with the CPU operation if still connected).

Given that the RAM has 8 address inputs, how many values can it store? Correct answer: 256

Which part(s) of this RAM would it make sense to hook up to which part(s) of an ALU in a design for a full computer (there are several good answers here)?

Example answer: The “Data in” could be hooked up to an ALU’s result to store that result in memory. Similarly, the “Data bus” outputs could be hooked up to one of the inputs of an ALU in order to use data from memory as part of an operation. Although less obvious, the address bus could serve as input and/or output as well, if we need to compute the address of some data using a formula. For example, using the address as one input and the number 1 as another input and setting the ALU to do addition, we could compute the next higher address as part of a solution for writing multiple values into sequential addresses. Finally, one could hook part of the data bus outputs into the Operation bits of the ALU, to let the data determine what operation the ALU will perform!

Extra exercises: Underlying Memory Organization

The circuit below shows how a larger memory is organized from basic latches. Examine the circuit carefully:

 

The triangular symbols are tri-state buffers, which act to either allow connection between the input and output of the gate (when enabled), or disconnect (when disabled). The enable line for the tri-state buffers is active low.

Exercise 14:

Describe the overall purpose of this circuit.

Example answer: This circuit allows you to read and write memory and also select where to do so, it’s a random access memory or RAM circuit. At all times, based on the 2 address bits, one of the four sets of tri-state buffers is active, sending the (4-bit) contents of memory at that address to the output. If you want to overwrite memory at the currently selected address, just turn the clock on and the clock inputs of the D latches for that address will be activated, allowing the 4 bits of “Data in” to replace the old data at that address (and the output will be updated immediately as well).

How is the 2x4 decoder used?

Example answer: It turns a 2-bit binary address into a 1-of-four-lines-is-on signal to send enabling signals to just one of the four memory units at once, and similarly to enable one of the four sets of tri-state buffers.

What is the purpose of the tri-state buffers?

Example answer: When not enabled, they prevent different memory outputs from sending signals onto the same wire, which could result in a short circuit. When one set of the 4 is enabled, it forwards the signals from the 4 bits of the associated register to the output lines.