Objective Implement all the logic gates presented in the chapter. The only building blocks that you can use are primitive Nand gates and the composite gates that you will gradually build on top of...

75304/s21-cs243-course-materialsreadmemd-at-main-hsu-s21-cs243s21-cs243-course-materials-msbtruoe-1gmrr5j0.pdf
2/2/2021 S21-CS243-course-materials/readme.md at main · HSU-S21-CS243/S21-CS243-course-materials
https://github.com/HSU-S21-CS243/S21-CS243-course-materials/blob/main/projects/project01/readme.md 1/3
HSU-S21-CS243 / S21-CS243-course-materials
Code Issues Pull requests Actions Projects Wiki Security
S21-CS243-course-materials / projects / project01 / readme.md
acarteas added project 1 assignment description. History
1 contributor
Learn Git and GitHub without any code!
Using the Hello World guide, you’ll start a branch, write comments, and open a pull request.
Read the guide
main
41 lines (33 sloc) 2.25 KB
CS 243 Assignment #1 - Chapter 1
Complete the project listed at the end of chapter 1 in the book.
Getting Started
Raw Blame
https://github.com/HSU-S21-CS243
https://github.com/HSU-S21-CS243/S21-CS243-course-materials
https://github.com/HSU-S21-CS243/S21-CS243-course-materials
https://github.com/HSU-S21-CS243/S21-CS243-course-materials/issues
https://github.com/HSU-S21-CS243/S21-CS243-course-materials/pulls
https://github.com/HSU-S21-CS243/S21-CS243-course-materials/actions
https://github.com/HSU-S21-CS243/S21-CS243-course-materials/projects
https://github.com/HSU-S21-CS243/S21-CS243-course-materials/wiki
https://github.com/HSU-S21-CS243/S21-CS243-course-materials/security
https://github.com/HSU-S21-CS243/S21-CS243-course-materials/pulse
https://github.com/HSU-S21-CS243/S21-CS243-course-materials
https://github.com/HSU-S21-CS243/S21-CS243-course-materials/tree/main/projects
https://github.com/HSU-S21-CS243/S21-CS243-course-materials/tree/main/projects/project01
https://github.com/acarteas
https://github.com/acarteas
https://github.com/HSU-S21-CS243/S21-CS243-course-materials/commit/baa56897441cb4487d1abc3db5afdbe86dc80392
https://github.com/HSU-S21-CS243/S21-CS243-course-materials/commits/main/projects/project01/readme.md
https://guides.github.com/activities/hello-world/
https://github.com/HSU-S21-CS243/S21-CS243-course-materials/raw/main/projects/project01/readme.md
https://github.com/HSU-S21-CS243/S21-CS243-course-materials/blame/main/projects/project01/readme.md
https://desktop.github.com/
2/2/2021 S21-CS243-course-materials/readme.md at main · HSU-S21-CS243/S21-CS243-course-materials
https://github.com/HSU-S21-CS243/S21-CS243-course-materials/blob/main/projects/project01/readme.md 2/3
Begin by creating a private repository in the course's GitHub organization. Your repository
name must be in the following format: p01-{HSU LOGIN} . Thus, my project repository
name would be p01-asc564 .
Once created, your repository should have:
a "chips" directory that contains your HDL solutions
a "diagrams" directory that contains PNG or JPEG images of each of your chips
a "results" directory that contains screenshots from the testing results obtained
through the hardware simulator
Below is an example screenshot that I am expecting for each test:
NOTICE: Failing to set up your repository correctly will result in reduced assignment credit.
Design Diary Prompt
Design diaries should be a paragraph or two. You will be graded on content (i.e. it shows
deep thought) rather than syntax (e.g. spelling) and structure. Below are some prompts
that can be used to get you thinking. Feel free to use these or to make up your own.
https://github.com/HSU-S21-CS243
https://github.com/HSU-S21-CS243/S21-CS243-course-materials/blob/main/projects/project01/example_ss.png
2/2/2021 S21-CS243-course-materials/readme.md at main · HSU-S21-CS243/S21-CS243-course-materials
https://github.com/HSU-S21-CS243/S21-CS243-course-materials/blob/main/projects/project01/readme.md 3/3
Describe a particular struggle that you overcame when working on this programming
assignment.
Conversely, describe an issue with your assignment that you were unable to resolve.
Provide advice to a future student on how he or she might succeed on this
assignment.
Describe the most fun aspect of the assignment.
Describe the most challenging aspect of the assignment.
Describe the most difficult aspect of the assignment to understand.
Provide any suggestions for improving the assignment in the future.
Your design diary will be submitted on canvas and should not be included in your
repository.
Grading
You will be graded using the following:
[65 pts] Building working chips (see included grading PDF)
[35 pts] Building efficient chips (see included grading PDF)
[20 pts] Creating logism diagrams for each of your chips
[10 pts] Writing a good design diary
Due Date
This project is due by Midnight on January 27, 2021. Your repository should contain all
chips, diagrams, and output files from the test runs provided to you by the book. On
canvas, you will submit your design diary.
75304/Solution.docx
ALU.HDL
CHIP ALU {
IN
x[16], y[16], // 16-bit inputs
zx, // zero the x input?
nx, // negate the x input?
zy, // zero the y input?
ny, // negate the y input?
f, // compute out = x + y (if 1) or x & y (if 0)
no; // negate the out output?
OUT
out[16], // 16-bit output
zr, // 1 if (out == 0), 0 otherwise
ng; // 1 if (out < 0), 0 otherwise
PARTS:
    Mux16(a=x,b=false,sel=zx,out=tempx1);//zx
        
    Not16(in=tempx1,out=notx);
    Mux16(a=tempx1,b=notx,sel=nx,out=tempx2);//nx
    Mux16(a=y,b=false,sel=zy,out=tempy1);//zy
        
    Not16(in=tempy1,out=noty);
    Mux16(a=tempy1,b=noty,sel=ny, out=tempy2);//ny
        
    And16(a=tempx2,b=tempy2,out=xAndy);//f=0
    Add16(a=tempx2,b=tempy2,out=addxy);//f=1
    Mux16(a=xAndy,b=addxy,sel=f,out=tempout1);//f
        
    Not16(in=tempout1,out=notout);
    Mux16(a=tempout1,b=notout,sel=no,out=out,out[0..7]=firsthalf, out[8..15]=secondhalf,out[15]=firstbit);//no
        
    Or8Way(in=firsthalf,out=firstor);
    Or8Way(in=secondhalf,out=secondor);
    Or(a=firstor,b=secondor,out=outor);
    Xor(a=outor, b=true, out=zr);//zr
        
    And(a=firstbit,b=true,out=ng);//ng
}
ADD16.HDL
CHIP Add16 {
IN a[16], b[16];
OUT out[16];
PARTS:
    HalfAdder(a=a[0],b=b[0],sum=out[0],carry=carry1);
    
    FullAdder(a=a[1],b=b[1],c=carry1,sum=out[1],carry=carry2);
    FullAdder(a=a[2],b=b[2],c=carry2,sum=out[2],carry=carry3);
    FullAdder(a=a[3],b=b[3],c=carry3,sum=out[3],carry=carry4);
    FullAdder(a=a[4],b=b[4],c=carry4,sum=out[4],carry=carry5);
    FullAdder(a=a[5],b=b[5],c=carry5,sum=out[5],carry=carry6);
    FullAdder(a=a[6],b=b[6],c=carry6,sum=out[6],carry=carry7);
    FullAdder(a=a[7],b=b[7],c=carry7,sum=out[7],carry=carry8);
    FullAdder(a=a[8],b=b[8],c=carry8,sum=out[8],carry=carry9);
    FullAdder(a=a[9],b=b[9],c=carry9,sum=out[9],carry=carry10);
    FullAdder(a=a[10],b=b[10],c=carry10,sum=out[10],carry=carry11);
    FullAdder(a=a[11],b=b[11],c=carry11,sum=out[11],carry=carry12);
    FullAdder(a=a[12],b=b[12],c=carry12,sum=out[12],carry=carry13);
    FullAdder(a=a[13],b=b[13],c=carry13,sum=out[13],carry=carry14);
    FullAdder(a=a[14],b=b[14],c=carry14,sum=out[14],carry=carry15);
    
    Xor(a=a[15],b=b[15],out=a15Xorb15);
    Xor(a=a15Xorb15,b=carry15,out=out[15]);
}
FULLADDER.HDL
CHIP FullAdder {
IN a, b, c; // 1-bit inputs
OUT sum, // Right bit of a + b + c
carry; // Left bit of a + b + c
PARTS:
         Xor(a=a,b=b,out=aXorb);
         Xor(a=aXorb,b=c,out=sum);
        
         Not(in=b,out=notb);
         And(a=a,b=notb,out=aAndNotb);
         And(a=aAndNotb,b=c,out=aAndNotbAndc);
        
         Not(in=c,out=notc);
         And(a=a,b=b,out=aAndb);
         And(a=aAndb,b=notc,out=aAndbAndNotc);
                
         And(a=b,b=c,out=bAndc);

         Or(a=aAndbAndNotc,b=aAndNotbAndc,out=firstOr);
         Or(a=firstOr,b=bAndc,out=carry);
    }
HALFADDER.HDL
CHIP HalfAdder {
IN a, b; // 1-bit inputs
OUT sum, // Right bit of a + b
carry; // Left bit of a + b
PARTS:
         Xor(a=a,b=b,out=sum);
         And(a=a,b=b,out=carry);
}
75304/theelementsofcomputingsystemsbuildingamoder-1booleanlogic-s30s2m1q-d10l10gg.pdf
1 Boolean Logic
Such simple things, And we make of them something so complex it defeats us, Almost.
—John Ashbery (b. 1927), American poet
Every digital device—be it a personal computer, a cellular telephone, or a network
router—is based on a set of chips designed to store and process information. Al-
though these chips come in different shapes and forms, they are all made from the
same building blocks: Elementary logic gates. The gates can be physically imple-
mented in many different materials and fabrication technologies, but their logical
behavior is consistent across all computers. In this chapter we start out with one
primitive logic gate—Nand—and build all the other logic gates from it. The result is
a rather standard set of gates, which will be later used to construct our computer’s
processing and storage chips. This will be done in chapters 2 and 3, respectively.
All the hardware chapters in the book, beginning with this one, have the same
structure. Each chapter focuses on a well-defined task, designed to construct or inte-
grate a certain family of chips. The prerequisite knowledge needed to approach this
task is provided in a brief Background section. The next section provides a complete
Specification of the chips’ abstractions, namely, the various services that they should
deliver, one way or another. Having presented the what, a subsequent Implemen-
tation section proposes guidelines and hints about how the chips can be actually
implemented. A Perspective section rounds up the chapter with concluding com-
ments about important topics that were left out from the discussion. Each chapter
ends with a technical Project section. This section gives step-by-step instructions for
actually building the chips on a personal computer, using the hardware simulator
supplied with the book.
This being the first hardware chapter in the book, the Background section is
somewhat lengthy, featuring a special section on hardware description and simulation
tools.
Nisan, Noam, and Shimon Schocken. The Elements of Computing Systems : Building a Modern Computer from First Principles, MIT Press, 2005. ProQuest Ebook Central,
http://ebookcentral.proquest.com/lib/humboldt/detail.action?docID=6243305.
Created from humboldt on 2021-02-02 21:30:33.
C
op
yr
ig
ht
©
2
00
5.
M
IT
P
re
ss
. A
ll
rig
ht
s
re
se
rv
ed
.
1.1 Background
This chapter focuses on the construction of a family of simple chips called Boolean
gates. Since Boolean gates are physical implementations of Boolean functions, we
start with a brief treatment of Boolean algebra. We then show how Boolean gates
implementing simple Boolean functions can be interconnected to deliver the func-
tionality of more complex chips. We conclude the background section with a descrip-
tion of how hardware design is actually done in practice, using software simulation
tools.
1.1.1 Boolean Algebra
Boolean algebra deals with Boolean (also called binary) values that are typically
labeled true/false, 1/0, yes/no, on/off, and so forth. We will use 1 and 0. A Boolean
function is a function that operates on binary inputs and returns binary outputs.
Since computer hardware is based on the representation and manipulation of binary
values, Boolean functions play a central role in the specification, construction, and
optimization of hardware architectures. Hence, the ability to formulate and analyze
Boolean functions is the first step toward constructing computer architectures.
Truth Table Representation The simplest way to specify a Boolean function is to
enumerate all the possible values of the function’s input variables, along with the
function’s output for each set of inputs. This is called the truth table representation of
the function, illustrated in figure 1.1.
The first three columns of figure 1.1 enumerate all the possible binary values of the
function’s variables. For each one of the 2n possible tuples v1 . . . vn (here n ¼ 3), the
last column gives the value of f ðv1 . . . vnÞ.
Boolean Expressions In addition to the truth table specification, a Boolean function
can also be specified using Boolean operations over its input variables. The basic
Boolean operators that are typically used are ‘‘And’’ (x And y is 1 exactly when both
x and y are 1) ‘‘Or’’ (x Or y is 1 exactly when either x or y or both are 1), and ‘‘Not’’
(Not x is 1 exactly when x is 0). We will use a common arithmetic-like notation for
these operations: x � y (or xy) means x And y, xþ y means x Or y, and x means
Not x.
To illustrate, the function defined in figure 1.1 is equivalently given by the Boolean
expression f ðx; y; zÞ ¼ ðxþ yÞ � z. For example, let us evaluate this expression on the
8 Chapter 1
Nisan, Noam, and Shimon Schocken. The Elements of Computing Systems : Building a Modern Computer from First Principles, MIT Press, 2005. ProQuest Ebook Central,
http://ebookcentral.proquest.com/lib/humboldt/detail.action?docID=6243305.
Created from humboldt on 2021-02-02 21:30:33.
C
op
yr
ig
ht
©
2
00
5.
M
IT
P
re
ss
. A
ll
rig
ht
s
re
se
rv
ed
.
inputs x ¼ 0, y ¼ 1, z ¼ 0 (third row in the table). Since y is 1, it follows that
xþ y ¼ 1 and thus 1 � 0 ¼ 1 � 1 ¼ 1. The complete verification of the equivalence
between the expression and the truth table is achieved by evaluating the expression
on each of the eight possible input combinations, verifying that it yields the same
value listed in the table’s right column.
Canonical Representation As it turns out, every Boolean function can be expressed
using at least one Boolean expression called the canonical representation. Starting
with the function’s truth table, we focus on all the rows in which the function has
value 1. For each such row, we construct a term created by And-ing together literals
(variables or their negations) that fix the values of all the row’s inputs. For example,
let us focus on the third row in figure 1.1, where the function’s value is 1. Since the
variable values in this row are x ¼ 0, y ¼ 1, z ¼ 0, we construct the term xyz. Fol-
lowing the same procedure, we construct the terms xyz and xyz for rows 5 and 7.
Now, if we Or-together all these terms (for all the rows where the function has value
1), we get a Boolean expression that is equivalent to the given truth table. Thus the
canonical representation of the Boolean function shown in figure 1.1 is f ðx; y; zÞ ¼
xyzþ xyzþ xyz. This construction leads to an important conclusion: Every Boolean
function, no matter how complex, can be expressed using three Boolean operators
only: And, Or, and Not.
Two-Input Boolean Functions An inspection of figure 1.1 reveals that the number of
Boolean functions that can be defined over n binary variables is 22
n
. For example,
the sixteen Boolean functions spanned by two variables are listed in figure 1.2. These
functions were constructed systematically, by enumerating all the possible 4-wise com-
binations of binary values in the four right columns. Each function has a conventional
x y z f ðx; y; zÞ
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 0
Figure 1.1 Truth table representation of a Boolean function (example).
9 Boolean Logic
Nisan, Noam, and Shimon Schocken. The Elements of Computing Systems : Building a Modern Computer from First Principles, MIT Press, 2005. ProQuest Ebook Central,
http://ebookcentral.proquest.com/lib/humboldt/detail.action?docID=6243305.
Created from humboldt on 2021-02-02 21:30:33.
C
op
yr
ig
ht
©
2
00
5.
M
IT
P
re
ss
. A
ll
rig
ht
s
re
se
rv
ed
.
name that seeks to describe its underlying operation. Here are some examples: The
name of the Nor function is shorthand for Not-Or: Take the Or of x and y, then
negate the result. The Xor function—shorthand for ‘‘exclusive or’’—returns 1 when
its two variables have opposing truth-values and 0 otherwise. Conversely, the
Equivalence function returns 1 when the two variables have identical truth-values.
The If-x-then-y function (also known as x ! y, or ‘‘x Implies y’’) returns 1 when x is
0 or when both x and y are 1. The other functions are self-explanatory.
The Nand function (as well as the Nor function) has an interesting theoretical
property: Each one of the operations And, Or, and Not can be constructed from it,
and it alone (e.g., x Or y ¼ ðx Nand xÞ Nand ðy Nand yÞ. And since every Boolean
function can be constructed from And, Or, and Not operations using the canonical
representation method, it follows that every Boolean function can be constructed
from Nand operations alone. This result has far-reaching practical implications:
Once we...