CMPE12, Spring 2012, Section 01: Lab3: The LC-3 ALU with Memory

Lab Objective

In this lab, you will design and build a multi-page schematic for the operation of an 4-bit arithmetic logic unit (ALU) capable of performing addition (ADD), negation (NOT), and bitwise AND. You will then build a memory with four lines capable of storing four bits per line.

A partner is highly recommended!!

You may build either part 1 or part 2 first; but whichever you decide, make sure you thoroughly test your design before proceeding and adding functionality. You will have three lab sessions to compelete the work, which means you have some extra time. That means this lab is more challenging than the average lab and may require time outside your lab section. Please plan accordingly.

Part 1: The ALU

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.

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 4-bit ALU. A 8-bit or 16-bit ALU would be really messy to implement in MML, which is why our design will be only on 4 bits.

Part 2: Memory

From class you learned that combinational logic is just a function of current inputs and that sequential logic was a function not only of current input, but some past sequence of inputs. To store that past sequence information we need some storage devices.

In this part of lab you will build a memory with four 4-bit registers. You will add functionality to both read a four-bit number from a register, and write an 4-bit number into a particular register. You will allow a global reset that will reset all registers. So, let's get started.

  • What is a binary number? ---> Answer
    Binary uses the weighted number system, which means that each digit (0 or 1) has a "weight," like in base ten. The weights of the binary digits, from right to left, are in powers of two (in base ten, they are in powers of ten).
  • How do you convert from decimal to binary? ---> Answer
    There is a fun divide-by-two algorithm. You take your base-10 number and divide by two, each time remembering the remainder, until you get a quotient of 0. Reading the remainders backwards gives the binary number.
  • How do you convert from binary to hexadecimal and back? ---> Answer

Hexadecimal is base-16. The digits of hexadecimal are as follows. 0 1 2 3 4 5 6 7 8 9 a b c d e f, where a=10, b=11, c=12, d=13, e=14, and f=15 in base 10.

It is a good idea to memorize the hex to decimal conversions.

The hexadecimal prefix is "0x". We will be using it liberally throughout the quarter to indicate our use of hexadecimal numbers.

Because 24=16, you can group a binary number's digits into groups of four. Each group of four is a hexadecimal digit. E.g., 00001010 grouped into fours is 0000 1010; each group is a hex digit. In this example, the hexadecimal equivalent of 0000 1010 is 0x0a.

It is a good idea to memorize the binary to hex conversions.

  • How do you know that a 2's complement a binary number is negative? ---> Answer
    Because it starts with a 1. Two's complement binary numbers are negative if and only if the first bit is a one.
  • What is an asynchronous RESET signal?
  • What is a register file?
  • Signal sender and signal receivertools
  • Organizing the design into multiple pages
  • Bitwise ANDon 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

thealu.lgi and a lab report that includes discussion of all parts of the lab assignment.

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

In the finished schematic, your memory should interact with the ALU. That is, the user should be able to store ALU results into memory, and use memory contents as one of the inputs into the ALU. This is called an accumulator architecture, and we will cover this in class in the future.

Requirements for the ALU

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

  • Have two 4-bit inputs using two keypads
  • Have one 4-bit output using a 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 ANDof the two operands
  • Be capable of performing a bitwise NOTof 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 ADDhad 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")

Requirements for the memory

  • You can read from each register individually by selecting "Read," selecting the register, and pressing the clock button. The result is displayed on the 7-segment display.
  • You can write to each register individually by selecting "Write," selecting the register, entering a number on the keypad, and pressing the clock button.
  • You can clear all latches asynchonously (at the same time, and regardless of the clock) using the clear button.
  • The state of the registers changes only when the clock or reset buttons are pressed.
  • The read-output display only changes when a read occurs.

Requirements for the ALU-memory system

  • One of the ALU operands is always memory, specified as above (selecting the Read opcode and the corresponding memory address).
  • The second ALU operand is always an 4-bit value specified on the keypads.
  • The result of the ALU is latched and displayed. To store the ALU result into memory, the ADD ALU opcode must be selected, zero (00) must be entered on the keypads, and the memory control signals must be specified as above (Writeopcode and the corresponding memory address).
  • To read a value from memory without modifying it, select ADD on the ALU with 00, and the corresponding read signals.

Organizing the design

You can (and will) create each part of the lab separately, and test each part thorougly before joining them.

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

  1. Inputs and outputs
  2. ALU: Source registers implementation
  3. ALU: Opcode resolution -- decode based on instruction opcode
  4. ALU: Logic for the two bitwise functions AND and NOT
  5. ALU: Logic for the ADDinstruction (could be spaced on two or more pages)
  6. ALU: Destination register multiplexion
  7. ALU: Destination register implementation
  8. Memory page 1: ?
  9. Memory page 2: ?
  10. Memory page 3: ?
  11. Memory page 4: ?
  12. Memory page 5: ?

Procedure for Part 1: The ALU

Figure 1 shows an example design of the I/O layer for the ALU only. Yours may be different. What follows is a discussion of my example design decisions.

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.

Crude diagram of an ALUFigure 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!

clk, reset, CinFigure 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 notshown 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.

 

i/oFigure 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.

  1. Two 4-bit inputs
  2. One 4-bit output
  3. Two keypads for 4-bit input
  4. Three 7-segment displays (2 for input, 1 for output)
  5. A bunch of switches for opcode (could use a keypad, I guess, but switches are so much more geeky)
  6. A bunch of lights too
  7. The "is zero" LED
  8. One button for clock
  9. One button for reset
  10. 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.

control logic exampleFigure 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
  • Cinis the carry-in to the adder
  • Coutis the carry-out from the adder
  • IR[15..12]is a 4-bit subset of the instruction register (from the LC-3 instruction opcode)
  • Clkis 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.

ABc_inc_outsum
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.

4-bit adderFigure 6:A 4-bit full adder

Extra credit for Part 1: The ALU

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

Include 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 (8 points) or two (4 points) clock cycles.

Notes for Part 1: The ALU

  • 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.
  • Materials:Feel free to use other materials than those listed here. It may make your design more understandable or fun!
  • Example: If you like, you may refer to my interface design, shown in Figure 7.

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

Part 2: The Memory

Next, you will build a memory device called a register file. You will have four registers in the memory, and each register will store four bits.

You will only access one of the four registers at a time (thus reads and writes are always 4 bits in size). If you are reading, the result should be stored in a set of 4 flip-flops; the output should be connected to a display readout. Note that the display should only change when a read is done, not when a write is done.

Materials

You may need at least the following components. This is a partial list; yours may be different.

  • Clock (button) to clock the registers
  • Reset (button) to asynchonously reset all registers
  • Keypad for user input
  • Write enable signal (switch) to differentiate between reads and writes
  • Address select signals (switches) to differentiate between registers (if you like, this may be two signals -- one for reads, one for writes)
  • Decoder for register selection
  • Four 1-bit flip-flops (memory bank 0)
  • Four 1-bit flip-flops (memory bank 1)
  • Four 1-bit flip-flops (memory bank 2)
  • Four 1-bit flip-flops (memory bank 3)
  • Multiplexer for output selection
  • 7-segment display

Procedure

  1. Open a new schematic named lab2-registerfile.lgi.
  2. Consider now what your design will look like. Organize your design into multiple pages (like layers). Draw it out on paper. Your lab tutor may not help you if you haven't brainstormed on paper first!
    • The first page of your design should contain all of your I/O (input/output) -- everything that interacts with the user (you).
    • Another one or more pages should have address decode logic, register file, and remaining logic. You may reference examples\Devices\signal.lgi for an example of using the signal sender and signal receiver tools.
  3. Add a clock button. The registers and displays are all clocked, or synchronized.
  4. Add a global reset button. Resetting the system should reset all registers and displays to 0.
  5. Add the keypad and a 7-segment display to the keypad so you always know what was just entered.
  6. Add the address select switches (to select the 0, 1, 2, or 3 register bank). This is what we call the address decode logic.
  7. Add the decoder. You need a 2-to-4 decoder which will assert one of the four lines based on the two-bit input. Warning: the decoder's asserted outputs are inverted. Figure 8 shows the input of 2 base 10 de-asserting the 2nd line.
  8. Add read/write switch (to select the operation). This is the control logic.
  9. Add the 7-segment display for read results.
  10. Add the four register banks as four sets of four D-latches. Figure 9 shows how to add a latch, and Figure 10 shows how to modify the latch to make it a D-latch with preset and clear signals (clear is built in, and will be your reset).
  11. Add all the intermediate logic to make your lab work. This includes both control and data logic, including but not limited to the following.
    • Decode logic to select the register bank
    • Logic to select read/writing
    • Logic to carry clock signal
    • Logic to carry reset signal
    • Data lines to carry data to and from I/O to the registers

A decoder's outputs are invertedFigure 8: A decoder's outputs are inverted adding a latchFigure 9: Adding a latch A d-latch with extra nodesFigure 10:Making a D-latch with preset and clear signals

You can see what my example interface looks like. Refer to Figure 11.

My first page of the memoryFigure 11:Fire's memory implementation (first page only -- the input and output)

Grading Template

This is a suggested grading rubric. 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

Inputs and outputs

  • (2 pts) Have two 4-bit inputs, and display both inputs on 7-segment displays
  • (2 pts) Have one flip-flopped ("DR") 4-bit output of the register file, displayed on a 7-segment display
  • (2 pts) Have ("IR") LC-3 opcode bits (see textbook)
  • (1 pts) Have a global asynchronous reset button (labeled "Reset") to reset all registers and displays
  • (1 pts) Have a clock button (labeled "CLK") which acts as a control signal for all sequential logic
  • (1 pts) Display the operation in progress with LEDs or other output device
  • (1 pts) Display with an LED if the result of an ADDhad a carry-out
  • (1 pts) Display with three LED if the output of the ALU is zero (labeled "Z"), positive (labeled "P"), or negative ("N")

Control logic and ALU operation

  • (3 pts) Be capable of performing a bitwise AND of the two operands
  • (3 pts) Be capable of performing a bitwise NOT of the first operand
  • (3 pts) Be capable of performing an ADD of the two operands using a ripple-carry full adder

Extra credit (only one of the following)

  • (8 pts) Implement subtraction instruction in one clock cycle
  • (4 pts) Implement subtraction instruction in two clock cycles

20 (+8 or +4) points total

Register file requirements

  • (3 pts) Address decoding network is correct
  • (4 pts) Four registers with 4 bits each: implementation is correct, with D flip-flops
  • (2 pts) Ability to read from each register bank using read signal and clock
  • (2 pts) Ability to write to each register bank using write signal and clock
  • (2 pts) Read changes value on data output 7-segment display
  • (2 pts) Write does not change value on output 7-segment display

15 points total

Combination requirements

  • (3 pts) Reset signal works as intended
  • (3 pts) Design is organized on multiple pages
  • (9 pts) Ability to store ALU result into memory

15 points total

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

50 (+8 or +4) Total points

Lab write-up requirements

In the lab write-up, we will be looking for the following things. The lab report is worth 50 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 SUBinstruction (subtract) included in the LC-3 instruction set?
  • How would you modify your particular design to implement an ORinstruction?
  • What is the purpose of the N, Z, and P LEDs?
  • What is a carry-out?
  • What is the clock signal used for?
  • What is an asynchronous RESET signal?
  • What is a register file?
  • How did you tell the register banks which operation to perform, and to which bank?
  • What's so great about having the output of the ALU go directly into the register file?

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

50 Total points

Attachments