Project 1

Building Boolean Logic Gates

Grading

(A) Project Demo [70%]: Logistics to be provided soon

You will be graded for correctness of the chips (hdl) you have designed and coded. You will be running live

test of all your HDL codes downloaded from your eCampus using Nand2tetris software (Hardware Simulator)

with TA/PT. So, make sure to test and verify your codes before finally submitting on eCampus.

Rubric: PriorityEncoder83.hdl is worth 10 points and the others are worth 4 points each. Each chip needs to

pass all its test cases to get full credit, else you will receive a 0 point on that chip.

(B) Code Review/Lab Quiz [30%]: To be held with the LIVE Demo

Code review/Lab Quiz of randomly selected chips. The questions can involve drawing circuit diagram of

randomly selected chips or truth table. Should not be difficult for you if you have understood the core inner

workings of your project.

Deliverables & Submission

You need to turn in only the completed HDL files for all the chips implemented. Put your full name in the

introductory comment present in each HDL code. Use relevant code comments and indentation. Also, include this

cover sheet with your signature below. Zip all the required HDL files and the signed cover sheet into a compressed file

FirstName-LastName-UIN.zip . Submit this zip file on eCampus.

Late Submission Policy: Refer to the Syllabus

Full Name: Section: UIN:

Any assignment turned in without a fully completed cover page will NOT BE GRADED.

Please list all below all sources (people, books, web pages, etc) consulted regarding this assignment:

CSCE 312 Students Other People Printed Material Web Material (URL) Other

1. 1. 1. 1. 1.

2. 2. 2. 2. 2.

3. 3. 3. 3. 3.

4. 4. 4. 4. 4.

5. 5. 5. 5. 5.

Please consult the Aggie Honor System Office for additional information regarding academic misconduct – it is your responsibility

to understand what constitutes academic misconduct and to ensure that you do not commit it.

I certify that I have listed above all the sources that I consulted regarding this assignment, and that I have not received nor given any

assistance that is contrary to the letter or the spirit of the collaboration guidelines for this assignment.

eCampus Submission Date: ___________________

Printed Name (in lieu of a signature): _________________________

Background

A typical computer architecture is based on a set of elementary logic gates like AND, OR, MUX,

etc.as well as their bitwise 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.

Objective

1. Build all the logic gates described below, yielding a basic chip-set. The only building blocks

that you can use in this project are primitive NOR gate (HDL provided) and the following

composite gates that you will gradually build on top of them.

2. After implementing all elementary logic gates, use them to implement chips for the following

logic scenarios:

● Exercise 1: A student would fail an exam if he spent the previous night studying for the

exam, or if he has not had breakfast before the exam.

● Exercise 2: You cannot get onto the ride if you are too young and too short, or too old

and have heart disease.

Hint: Convert the sentence to Boolean algebra equation and draw the truth table of each

scenario before implementation.

Here are the Chips you are required to implement in order:

Chip Name File Name Description

Not Not.hdl Not Gate

Or Or.hdl Or Gate

And And.hdl And Gate

Xor Xor.hdl Exclusive Or Gate

Mux Mux.hdl Multiplexer Gate

DMux DMux.hdl Demultiplexer Gate

Not16 Not16.hdl 16-bit Not Gate

And16 And16.hdl 16-bit And Gate

Or16 Or16.hdl 16-bit Or Gate

Mux16 Mux16.hdl 16-Bit Multiplexer

Or8Way Or8Way.hdl 8-bit input Or Gate

Mux4Way16 Mux4Way16.hdl 4-way 16-bit input Multiplexer

DMux4Way DMux4Way.hdl 4-way 16-bit input Demultiplexer

Exercise1 Exercise1.hdl Exercise 1 based circuit

Exercise2 Exercise2.hdl Exercise 2 based circuit

8 to 3 Priority Encoder PriorityEncoder83.hdl TBD in Next Week Lab

Contract

Download and uncompress the P1Codes.zip file in your local nand2tetris folder.

NOTE: You should have already deleted the default project directory already present in

nand2tetris folder, as announced in the first lab and also on Slack.

When loaded into the supplied Hardware Simulator, your chip design (completed .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 as error message in the footnote

space.

Resources

The relevant reading for this project is Chapter 1 and Appendix A of the textbook.

Specifically, all the chips described in Chapter 1

https://docs.wixstatic.com/ugd/44046b_f2c9e41f0b204a34ab78be0ae4953128.pdf

These should be implemented in the Hardware Description Language (HDL) specified in

Appendix A https://docs.wixstatic.com/ugd/44046b_2cc5aac034ae49f4bf1650a3d31df32c.pdf

Another resource that you will find handy in this and in all subsequent hardware projects is this

HDL Survival Guide written by Mark Armbrust https://www.nand2tetris.org/hdl-survival-guide

For each chip, we supply a skeletal .hdl file with a placeholder 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.

Tips

Prerequisite: If you haven’t done it yet,

1. Read Chapter 1 and Appendix A, and go through parts I-II-III of the Hardware Simulator

Tutorial ppt (see ECampus) , before starting to work on this project.

2. Built-in chips: The NOR gate is considered primitive and thus there is no need to

implement it: whenever a NOR chip-part is encountered in your HDL code, the simulator

automatically invokes the built-in tools/builtInChips/Nor.hdl implementation.

3. We recommend implementing the other gates in this project in the order in which

they appear in Chapter 1. However, note that the simulator’s environment includes a

library with built-in versions 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.

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 a builtin 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.

Tools

All the chips mentioned in Projects 1-3 and 6 can be implemented and tested using the supplied

Hardware Simulator. Here is a screenshot of testing a Xor.hdl chip implementation on the

Hardware Simulator:

Continued Next Page

Tips/FAQs:

Here are some useful tips for writing your HDL codes.

1. Input = 0

1. To input zero to a wire, use the false keyword. Unassigned ports by default are

assigned 0 (False)

2. And(a=false, b=false, out=o1); would always compute “0 AND 0”

2. Sub busing

1. Sub busing is your tool to reference a slice of the bus that are named in the IN

and OUT statements of an HDL file, or inputs and outputs of the chip-parts

used in the PARTS section. If you need a sub-bus of an internal bus, you must

create the narrower bus as an output from a chip-part. The syntax is

bus_name[i..j]. (This references the slice of bus_name from bit i to j inclusive,

i<j)

2. Example 1:

Something4 (in=in, out=my_out[0..3]); this Something4’s “out” port

carries values at bits 0 through 3 inclusive of “my_out” bus.

Example 2:

Something4 (a[0..1]=my_a, out=out); this connects the 2-bit bus

“my_a” to bits 0 through 1 inclusive of Something4’s “a” port.

Example 3:

Something4 (a[0..1]=my_a[4..5], out=out); assigns bits 4 through 5

inclusive of “my_a” bus to bits 0 through 1 inclusive of Something4’s “a” input.

This is all discussed in the HDL survival guide available at

https://phoenix.goucher.edu/~kelliher/f2015/cs220/hdlSurvivalGuide.pdf if you have further questions.

From a Truth Table to a Simplified Boolean expression for a chip

Boolean function synthesis requires us to first identify the cases in the Truth Table which have output

logic as TRUE (1). These are the different scenarios of input values which correspond to output of

boolean function to be true. By creating an expression for these TRUE output cases, it is ensured that

FALSE output cases will be automatically taken care of as the output itself is binary and hence

complement of these TRUE cases.

With that in mind, we try to express each TRUE case as “Product of Input variables” i.e. combining all the

inputs through logical AND. Why? Since, all these inputs will need to hold their respective boolean values,

simultaneously, for the function output of that case to be TRUE. Eg: Let’s take a scenario where we need

to derive expression for f(a,b)

a b f(a,b)

0 0 0

0 1 1

1 0 1

1 1 1

Step 1: f(a, b) = 1 (TRUE) when the inputs are as follows:

(i) a=0 and b=1 = NOT(a) AND b = a’.b {Always complement the input variable if it is FALSE}

(ii) a=1 and b=0 = a AND NOT(b) = a.b’

(iii) a=1 and b=1 = a AND b = a.b

These product terms, namely, a’b , ab’ , ab are called minterms. These are used when we focus just on

output cases when TRUE.

(Likewise, there are also maxterms which is alternate way of observing the truth table in terms output

logic FALSE, i.e., we focus on creating “complement” of the boolean function. Maxterm involves “sum of

input variables” for a given FALSE output case, which is later multiplied as “PRODUCT of SUMs” across

different FALSE cases). In this course, we will follow minterm notation only.

Step 2: Since, cases (i), (ii) and (iii) will not happen simultaneously as boolean inputs in digital circuits

can either be a 1 or 0 but not both (that’s quantum, folks, when any state can exhibit both dual values

0<=1 at the same time, which is being used to build a quantum computer), there is a notion of OR

across these three TRUE output cases. So, we create a “SUM of PRODUCTS” expression with the

minterms , i.e., f(a.b) = (a’b) OR (ab’) OR (ab) = a’b + ab’ + ab (AND/. has higher precedence than

OR/+)

Step 3: Simplify the boolean expression using boolean identities.

f(a.b) = a’b + ab’ + ab

= a’b + a(b’+b)

= a’b + a(1)

= a’b + a

= a + a’b {by commutative property}

= (a+a’)(a+b) {by Distributive property}

= (1)(a+b)

= a+b

= a OR b

Hence, we have successfully derived the simplified boolean function f(a, b).

How do we get mathematical form of Boolean expressions: eg: x ∨ y = x OR y = x + y ? Which

one should we learn/use ? / Using . and + seem less intuitive than logical or set notation ∧ , ∨, ¬

In terms of mathematical logic and set theory, which came earlier in literature and were in a way to

express logical human thought, it is absolutely correct to use notations such as ∧ , ∨, ¬ for logical AND

(intersection), logical OR (union), logical NOT (complement). Hence, in the slides you will find the logical

names (AND, OR, NOT) being used in all the examples and expressions. In boolean algebra, we as

computer scientists abuse this notation a little bit to make our lives easier in terms of modeling these

logics as mathematical expressions to better understand the boolean identities. On a personal level, I

found expressing AND as . (multiplication) and OR as + (addition) helps me to remember and understand

the boolean identities as some mathematical property.

To answer why OR is represented/denoted as + or AND as . = Well, if we look at the truth table of these

logics, we find that all the outputs are either non-zero or zero for any given logic (OR/AND) and are also

well preserved under mathematical operations of addition (+) or multiplication(.) over all possible values of

inputs for that logic. eg: 0 OR 0 = 0 can be thought of as 0+0 = 0, similarly,

0 OR 1 = 1 OR 0 = 1 is the same as if 0+1 = 1+0 = 1, and 1 OR 1 = 1+1 = 2 which is again non-zero,

hence, logic HIGH or Logic 1 (Recall, the expressions used in if() in C++programming, where non-zero

evaluations are treated as logic TRUE). So, I will suggest using notations that best help you to understand

and to remember the identities and simplify boolean expressions.