Recent Forum Posts

Today is Monday, May 21, 2012

view forum

Nothing available at this time.

Lab 3: The LC-3 ALU

Due date

Due Monday, July 13 by 8:00am

Lab Objective

ALU stands for Arithmetic Logic Unit. It's the major part of hardware -- in microprocessors in general and the LC-3 in particular -- responsible for most of the computations (arithmetic and logic) you perform.

In this lab, you will design and build a multi-page schematic for the operation of an 8-bit ALU capable of performing addition (ADD), negation (NOT), and bitwise AND.

The LC-3 ALU, which you have seen in class, operates on 16-bit numbers, but the ALU you will design in this lab is only an 8-bit ALU. A 16-bit ALU would be really messy to implement in MML, which is why our design will be only on 8 bits.

Lab tutors: Go over these topics

Your lab tutor will cover the following topics in the first 40 minutes of lab.

Bitwise AND on two binary numbers
Bitwise NOT, or negation, on one binary number
How to add binary numbers, and what is a carry-out

What's required

lab3.lgi and the associated write-up

Your design should be synchronous and well-organized. You must use pages and proper logic elements (a D-flip-flop versus a bunch of NAND gates, etc).

Requirements for the ALU

The ALU you design must meet at least the following criteria. It must ...

Have two 8-bit inputs using two keypads
Have one 8-bit output using two 7-segment displays
Be capable of displaying both inputs using a 7-segment display for each input
Capture the input in D-flip-flops (labeled "SR1" and "SR2" for source register)
Have a clock button (labeled "CLK")
Have a global reset to reset all registers and displays (labeled "Reset")
Allow the user to input LC-3 opcodes using switches (see textbook), and store the opcode in an instruction register (labeled "IR")
Display the operation in progress with LEDs or other output device
Be capable of performing a bitwise AND of the two operands
Be capable of performing a bitwise NOT of the first operand
Be capable of performing an ADD of the two operands using a ripple-carry full adder
Capture the result of the operation with D-flip-flops (labeled "DR")
Display the result of the operation on a 7-segment display
Display with an LED if the result of an ADD had a carry-out
Display with an LED if the output of the ALU is zero (labeled "Z")
Display with an LED if the output of the ALU is positive (labeled "P")
Display with an LED if the output of the ALU is negative (labeled "N")
Be able to recognize a bad opcode, and display 0xBC (bad code) on the output display, and light an LED representing bad opcode. Other opcode LEDs should be turned off if the opcode is invalid.

Organizing the design

You should organize your design into multiple pages. The following organization is a suggestion; yours may be different.

Inputs and outputs, as in Lab 2
Source registers implementation
Opcode resolution -- decode based on instruction opcode, and "bad code" logic
Logic for the two bitwise functions AND and NOT
Logic for the ADD instruction (could be spaced on two or more pages)
Destination register multiplexion
Destination register implementation

Example: Designing the I/O layer

Below is an example design of the I/O layer. Yours may be different.

I will start by drawing out on paper what I think I will need to build. I start at the top layer, the page (or sheet) of my design that will contain all the user-interactive pieces.

The ALU will take two inputs and a set of commands, and will produce an output. As an example, my sketch is shown in Figure 1.

Figure 1: My ALU has two operands (in1 and in2), a set of command inputs (commands), and an output (out).

Keep in mind that I will need a clock signal and a global reset signal. Also, for the adder, I will need a carry-in signal (which we will cover later). Here is my picture, in Figure 2. I am quite the artist!

Figure 2: The ALU will need an additional clock signal (like a "go" button), a global reset, and a carry-in for the adder which I'll build later.

Next, I need to figure out what kind of inputs and outputs I will need. For example, the inputs require a keypad and a 7-segment display (for verification of input); the output will need a display as well; the control fields will need some switches and lights... well, you get the idea.

My diagram so far is shown in Figure 3. One thing that is not shown in Figure 3 is the set of condition codes, which I'm required to add.

"Z" should be the is zero? LED. It will turn on if the result from the ALU is zero (that is, each bit is equal to 0), and will be off otherwise.
"N" should be the is negative? LED. It will turn on if the result from the ALU is negative (that is, the leading bit is a 1), and will be off otherwise.
"P" should be the is positive? LED. It will turn on if the result from the ALU is positive (how do I know?), and will be off otherwise.

Figure 3: The ALU so far, with the control inputs and I/O shown.

The part I called command in the first diagram has been renamed to opcode, or operation code. This is a set of bits (a number) that will tell the ALU which action to perform. I can get the LC-3 opcodes for ADD and NOT and ADD from the book, so I'm not too worried.

Note the #? comment by the switch above opcode. This means I'm not sure how many switches I will need. How many bits do I need to perform all the operations I want? The textbook will tell me.

Materials

Now I make a list of all the materials you have accumulated so far. This list is just an example; yours may be different.

Two 8-bit inputs
One 8-bit output
Two keypads for 8-bit input
Three 7-segment displays (2 for input, 1 for output)
A bunch of switches for opcode (could use a keypad, I guess, but switches are so much more geeky)
A bunch of lights too
The "is zero" LED
One button for clock
One button for reset
One switch for carry-in

That's all I have for now, but it's good enough to design the first page. Next I will work out the logic for page 2.

Control logic

Control logic is the part of the logic that decodes the opcode, checks for the reset button, checks the clock, and so on. This is a major part of the project, and should be addressed.

Figure 4 may help you design your control logic. It was drawn by Andrea Di Blas, so it is much better-looking than my diagrams earlier.

Figure 4: An example of the overall structure of the control logic for an 8-bit ALU, where:

SR1[7..0] is the 8-bit first operand
SR2[7..0] is the 8-bit second operand
DR[7..0] is the 8-bit result; DR stands for destination register
Cin is the carry-in to the adder
Cout is the carry-out from the adder
IR[15..12] is a 4-bit subset of the instruction register (from the LC-3 instruction opcode)
Clk is the clock
Reset and Res are the asynchronous global reset

The ripple-carry full adder

There are lots of ways to make an adder. The one we will implement here is called a ripple-carry full adder. The ripple-carry part means that when we need to carry a 1, it will "ripple" down the schematic; full adder means we have a (mandatory) carry-out bit.

The adder in this ALU will add the two inputs and the carry-in, and produce a sum and a carry-out. The table below shows the truth table for adding one-bit values A and B, and a carry-in.

This is the same adder we saw in class. Figure 5 shows the truth table for this adder. You can also read about it on Wikipedia's page on full adders.

A	B	c_in	c_out	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

Figure 5: The truth table for a one-bit full adder

You can probably infer the logic equation for this device, but your tutor may show you in lab how to make a ripple-carry full adder.

Note that the table in Figure 5 shows you one bits' worth of truth values. To make a ripple-carry adder, you will hook several of these pieces together. The carry-out of one adder will be the carry-in of its neighbor. Figure 6 shows a crude diagram of a 4-bit adder.

Figure 6: A 4-bit full adder

Extra credit

In order to receive extra credit points, the entire basic design must be fully functional, and the additional functionality must be added.

(2 or 3 points) Add logic to perform a SUB instruction. That is, subtract the second operand from the first (out = in1 - in2). All three values -- both inputs and the output -- must be two's complement numbers (negative numbers must be represented). Your design may work in one (3 points) or two (2 points) clock cycles.

Notes

Check your work

Verify that your logic works for each step of the design. Bugs are easiest to fix when they are caught early! Use the probe tool to see the values at important nodes. Attach LEDs to everything you care about, if it helps you to visualize your design.

Check your work with actual numbers. Work out the solutions on paper.

Other thoughts...

Feel free to use other materials than those listed here. It may make your design more understandable or fun!

If you like, you may refer to my interface design, shown in Figure 7.

Figure 7: Fire's lab 3 implementation (first page only -- the input and output) (click to see by itself)

Grading Template

This is a suggested grading rubrik. Your tutor may or may not use this rubric to grade by, but it is a good general guideline before submitting your lab to check off these points.

ALU requirements

(15 pts) Inputs and outputs

Have two flip-flopped ("SR1" and "SR2") 8-bit inputs, and display both inputs on 7-segment displays
Have one flip-flopped ("DR") 8-bit output of the ALU, displayed on a 7-segment display
Have flip-flopped ("IR") LC-3 opcode bits (see textbook)
Have a global asynchronous reset button (labeled "Reset") to reset all registers and displays
Have a clock button (labeled "CLK") which acts as a flip-flopped signal for all sequential logic
Display the operation in progress with LEDs or other output device
Display with an LED if the result of an ADD had a carry-out
Display with an LED if the output of the ALU is zero (labeled "Z"), positive (labeled "P"), or negative ("N")
Display with an LED whether the opcode was a bad opcode (other opcode LEDs should be unlit)
Display on the ALU output device whether the opcode was a bad opcode (bad code value is "BC")

(25 pts) Control logic and ALU operation

Be capable of performing a bitwise AND of the two operands
Be capable of performing a bitwise NOT of the first operand
Be capable of performing an ADD of the two operands using a ripple-carry full adder
Be able to recognize a bad opcode, and display corresponding bad code information

Extra credit (only one of the following)

(3 pts) Implement subtraction instruction in one clock cycle
(2 pts) Implement subtraction instruction in two clock cycles

40 points total

Lab write-up requirements

In the lab write-up, we will be looking for the following things. The lab report is worth 12 points. We do not break down the point values; instead, we will assess the lab report as a whole while looking for the following content in the report.

How is sequential logic useful; i.e., why are the inputs and outputs latched?
Why isn't a SUB instruction (subtract) included in the LC-3 instruction set?
How would you modify your particular design to implement an OR instruction?
What is the purpose of the N, Z, and P LEDs?

12 points

CMPE 12 Links

Off-site Links

Other links