Project 1: Boolean Logic and Study Skills Inventory

Due on Thursday, January 13 at 11:59pm PST

Learning Objectives

  • Practice the principles of Boolean logic and learn about fundamental logic gates that form the basis of all modern computers.
  • Spend time thinking about what you want to get out of this course.

Part I: Study Skills Inventory (2 points)

Complete the Study Skills Inventory online at https://forms.gle/A7nnoGk87hW4evAy8.

The Study Skills Inventory is meant to help you reflect on your current academic behaviors, strategies, and practices. Answer the questions honestly. We are not going to be judging or grading you based on your answers. The goal is to help you identify areas where you feel are strengths and areas of improvements in your study skill practices. You will be asked to submit this same Study Skill Inventory at the end of the course. To access the Study Skills Inventory, you will need to be signed in to your CSE Net ID Credentials.

You do NOT have to submit anything in your repository for Part I of the project, simply submit the linked Google Form. Contact the course staff if you have trouble accessing the form.

Part II: Boolean Logic (15 points)

Background

A typical computer architecture is based on a set of elementary logic gates like And, Or, Mux, etc., as well as their bit-wise versions And16, Or16, Mux16, etc. (assuming a 16-bit machine). This project engages you in the construction of a typical set of basic logic gates. These gates form the elementary building blocks from which more complex chips will be later constructed.

Pulling From Your GitLab Repository

In your GitLab repository, you will see a new folder, /projects/1/. Since the updated code currently only exists in your server (sometimes called the remote or origin) repository, you'll need to pull the code from the server to your local repository. To do this, navigate to your local repository, (e.g., cse390b-22wi-ericfan), and run git pull, which pulls your code from your GitLab repository. If successful, you'll see the /projects/1/ directory in your local repository.

Overview

BEFORE starting the work for Part II: Boolean Logic (but after reading through the spec), estimate how long you believe it will take you to complete it. You will need to include this for your reflection in Part III.

In this project, you will build the following logic gates, yielding a basic chip-set. The only building blocks you can use in this project are the primitive Nand gate and any logic gates that you've already implemented, so you will gradually build on top of them. For that reason, we highly recommend that you go in the order given below (Not should only be built from Nand gate(s), And should be built from Not and Nand gates, etc.).

Chip NameDescriptionTest ScriptExpected Output
Nand(Primitive) Nand Gate
NotNot gateNot.tstNot.cmp
AndAnd gateAnd.tstAnd.cmp
OrOr gateOr.tstOr.cmp
XorXor gateXor.tstXor.cmp
MuxMultiplexorMux.tstMux.cmp
DMuxDemultiplexorDMux.tstDMux.cmp
Not1616-bit Not gateNot16.tstNot16.cmp
Mux1616-bit MultiplexorMux16.tstMux16.cmp
Or8WayOr gate between 8 inputsOr8Way.tstOr8Way.cmp
Mux4Way1616-bit, 4-way MultiplexorMux4Way16.tstMux4Way16.cmp

Contract

When loaded into the supplied Hardware Simulator, your chip design (modified .hdl program), tested on the supplied .tst script, should produce the outputs listed in the supplied .cmp file. If that is not the case, the simulator will let you know. This contract must be satisfied for each chip listed above, except for the Nand chip, which is considered primitive, and thus there is no need to implement it.

Resources

The relevant reading for this project is Chapter 1 and Appendix A. Specifically, all the chips described in Chapter 1 should be implemented in the Hardware Description Language (HDL) specified in Appendix A. Another resource that you will find handy in this and in all subsequent hardware projects is this HDL Survival Guide, written by Mark Armbrust.

For each chip, we supply a skeletal .hdl file with a place holder for a missing implementation part. In addition, for each chip we supply a .tst script that instructs the hardware simulator how to test it, and a .cmp ("compare file") containing the correct output that this test should generate. Your job is to complete and test the supplied skeletal .hdl files.

You will find the supplied Hardware Simulator and all the necessary project files in the tools/ directory and in the projects/1 directory of your repository, respectively.

Tips

Make sure you've followed the setup instructions in Project 0!

Built-in chips: The Nand gate is considered primitive and thus there is no need to implement it: whenever a Nand chip-part is encountered in your HDL code, the simulator automatically invokes the built-in tools/builtInChips/Nand.hdl implementation. We recommend implementing all the other gates in this project in the order in which they appear in the above table. However, note that the supplied hardware simulator features built-in implementations of all these chips. Therefore, you can use any one of these chips before implementing it: the simulator will automatically invoke their built-in versions (all you have to do is rename or move the un-implemented file so the simulator does not try to use it).

For example, consider the supplied skeletal Mux.hdl program. Suppose that for one reason or another you did not complete the implementation of Mux, but you still want to use Mux chips as internal parts in other chip designs. You can easily do so, thanks to the following convention. If the simulator fails to find a Mux.hdl file in the current directory, it automatically invokes the built-in Mux implementation, which is part of the supplied simulator's environment. This built-in Mux implementation has the same interface and functionality as those of the Mux chip described in the book. Thus, if you want the simulator to ignore one or more of your chip implementations, simply rename the corresponding chipName.hdl file, or remove it from the directory. When you are ready to develop this chip in HDL, put the file chipName.hdl back in the directory, and proceed to edit it with your HDL code.

Don't forget to peruse Chapter 1 of the online textbook before you start implementing chips. It breaks down each one's interface in depth, and often describes strategies for implementation.

You'll also want to refer to Appendix A periodically to learn about the HDL. In particular, we recommend you read section A.5.3 "Buses" before getting to the 16-bit chips, where you'll need to use wires that consist of multiple bits (called "buses"). When you see a wire declared as in[16], think of that as a "bundle" of 16 wires -- each of which can be individually referenced with in[0], in[1], ... in[15]. When you draw these out, feel free to represent them as a single wire for convenience.

When you test your code by running the hardware simulator as shown in lecture by loading the corresponding .tst script and pressing Run, it may indicate a "comparison error". When that happens, we recommend going to your file explorer and searching for: (1) a corresponding .cmp file that shows the inputs being tested and EXPECTED outputs of your chip, and (2) a corresponding .out file that shows the ACTUAL outputs of your chip when tested. Given that information, a good next step is tracing through your design with those inputs to see why it produced the value it did.

Additional Chips

The following additional chips (described in Chapter 1) can be used in future projects, but you are not required to implement them (instead, you can rely on the built-in versions). The intention is to give you extra tools to make future projects easier without requiring you to spend time implementing (and all of these chips bear heavy similarity to the ones you implement in this assignment so there is little to be gained by implementing them.)

Tools

All the chips mentioned in projects 1-5 can be implemented and tested using the supplied Hardware Simulator. Instructions for opening the Hardware Simulator are:

Nand2Tetris offers some more specifics about the Hardware Simulator (including a tutorial) on the "Software" page of their website (skip the Download section as you already have the software downloaded in your repo under the tools/ directory). Here is a screen shot of testing a Xor.hdl chip implementation on the Hardware Simulator:

Examples

The following are complete reference implementations of two chips in the assignment. Feel free to copy and paste them into the code you submit on Gitlab. These are provided to help you get familiar with the HDL syntax and let you experiment with the tools before working on the rest of the assignment. Note that you will either need a working And.hdl, Or.hdl, and Not.hdl, or you will need to rename those files so the simulator uses built-in versions (as demoed in class).

Xor.hdl

An Xor gate returns 1 when one, and only one, of its inputs is 1 -- if neither or both are 1, the gate returns 0. You can learn more in Chapter 1.

CHIP Xor {
  IN a, b;
  OUT out;

  PARTS:
  // Put your code here:
  Not (in=a, out=nota);
  Not (in=b, out=notb);
  And (a=a, b=notb, out=x);
  And (a=nota, b=b, out=y);
  Or (a=x, b=y, out=out);
}

Mux.hdl

A Multiplexor ("Mux") has two "data" inputs and one "selector" input. If the selector input is 0, the chip returns whatever it gets from the first data input, and if the selector is 1, the chip returns whatever it gets from the second data input. This is a fundamental tool allowing the computer to "choose" which of two possible values it should use. You can learn more in Chapter 1. 

CHIP Mux {
  IN a, b, sel;
  OUT out;

  PARTS:
  // Put your code here:
  Not (in=sel, out=notsel);
  And (a=a, b=notsel, out=anda);
  And (a=b, b=sel, out=andb);
  Or (a=anda, b=andb, out=out);
}

Part III: Social Computing Reflection (5 points)

You're now in the midst of developing a (virtual) computer! There are many social aspects and issues related to hardware design, development, and production and your first social reflection is aimed at exploring some of these. First, read through the general reflection details and requirements which will give you an idea of what's required for the reflection. Then find an article/blog/paper to complete the requirements with that is loosely related to the prompts below. The prompts don't have to be strictly adhered to, they are just there to give you an idea of possible topics you could explore for this reflection.

There is a document called p1_social_computing_reflection.docx located in the projects/1 directory where you can complete the reflection. Edit the document and submit by pushing to GitLab.

Part IV: Project 1 Reflection (3 points)

Upon completing the Boolean Logic assignment (Part II), take time to reflect on what that experience was like for you and address the following questions:

  1. What was the most frustrating or difficult part of the Boolean Logic assignment?
  2. What tools, questions, strategies did you utilize to persist through the assignment?

Record your answers in the document called p1_project_reflection located in the projects/1 directory. Edit the document, and after completing your changes, make sure the completed version has the same name in the same location. Commit and push the changes as you did in Project 0.

Submitting

To submit your project, make sure you commit and push your changes, then tag them as project-1 and push that tag as well:

Then, verify that the tag and all your code is uploaded correctly by checking on gitlab.cs.washington.edu.

Project Skills and Passing Requirements

Below are the skills you need to demonstrate in order to pass this project, along with concrete tasks we expect you to complete to demonstrate each skill. Remember that in order to receive a passing grade for the class, you must receive a passing grade on each project. Only completing the bare minimum to pass a project will result in a low grade. See the syllabus for more details and let us know if you have any questions.