$29
Project 2 Combinational Chips Solution
Grading
(A)Project Demo [70%]:labs, for respective sections 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 using Nand2tetris software (Hardware Simulator) with TA/PT. The same simulator you would have used to check your chips in the project. So, make sure to test and verify your codes before finally submitting on eCampus.
Rubric: See the grading sheet. Each circuit needs to pass all its test cases to get the points, else you will receive 0 on that circuit.
Code Review/Q&A [30%]: To be held with the LIVE Demo
Code review of randomly selected chips. The questions can involve drawing circuit diagram of randomly selected chips. 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 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 in your code. 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 (TA will show the students an example for this). Submit this zip file on eCampus.
Late Submission Policy: Refer to the Syllabus
Background
The centerpiece of the computer's architecture is the CPU, or Central Processing Unit, and the centerpiece of the CPU is the ALU, or Arithmetic-Logic Unit. In this project you will gradually build a set of chips, culminating in the construction of the ALU chip of the Hack computer. All the chips built in this project are standard, except for the ALU itself, which differs from one computer architecture to another.
Objective
The objective of this project is to build all the chips discussed in Chapter 2 and class, leading up to an Arithmetic Logic Unit - the Hack computer's ALU. The only building blocks that you can use are the chips described in Project 1 and the chips that you will gradually build in this project.
Chips
You may open any given chip file from P2Codes.zip
Chips Name
File Name
Description
Basic Chips:
HalfAdder
HalfAdder.hdl
Half Adder
FullAdder
FullAdder.hdl
Full Adder
4-bit adder
Add4.hdl
4-bit ripple carry adder
6-bit adder
Add6.hdl
6-bit ripple carry adder
Add16
Add16.hdl
16-bit Adder
Inc16
Inc16.hdl
16-bit incrementer
Advanced Chips:
Negation
Negation.hdl
2’s complement of the input
LeftLogicBitshift
LeftLogicBitshift.hdl
16-bits left bit shifter (See below)
ALU
ALU-nostat.hdl
Arithmetic Logic Unit (without handling of status
outputs)
ALU
ALU.hdl
Arithmetic Logic Unit (complete)
Proposed Implementation
Build the basic chips in the order listed above.
Build a 4-bit ripple carry adder and a 6-bit ripple carry adder. Apply modular construction techniques of building adders as discussed in class.
Build a 16-bit negation operator that outputs the 2’s complement of the input.
Build a barrel-shifter to perform left logical bit shift by the stated amount.
Finally, construct an ALU in two incrementally advanced stages.
For Basic Chips: Refer to class lecture material and the video below
https://www.youtube.com/watch?v=xtcJMxlEFek&index=18&list=PLrDd_kMiAuNmSb-CKWQqq9 oBFN_KNMTa
Below we share with you some additional background on the logic of a Left Logic Bit Shift and the ALU.
LEFT LOGIC BIT SHIFTER:
For an operand N,whose binary equivalent is x[8],the 8-bit representation is indexed as 7..0 from left to right.
Left Logic Shifting N by one bit, represented as N<<1, moves each bit of x one place on its corresponding left. For instance, in the example above, let out[8] be the binary representation of the resulting number after applying Left Logic Bit Shifter on the input x[8]. Then, x[6] becomes out[7], x[5] becomes out[6], and so on. The rightmost bit (LSB), i.e., out[0] in the resulting number is “always” simply filled by 0.
Mathematically, what does left logic bit shifting do to a number?
To answer this, let's take the above example where the x = 00010111 is left shifted by b=1 bit. Let us start by writing its decimal equivalent before and after shifting. Before shifting, the number is N=23. After shifting by one bit, the resulting out = 00101110,in decimal representation becomes
(1×25) + (1×23) + (1×22) +(1×21) = 32 +8 + 4 + 2 = 46
46 is nothing but 23 × 2 . This essentially means that left logic shift by 1 bit doubles the number.
Similarly, left logic shift by 2 bits, N << 2, results in N × 2 2 = N × 4 , and , left logic shift by 3 bits, N << 3, results in N × 2 3 = N × 8
Therefore, for any given operand/ decimal number N, shifting by b bits to the left results in a new number, N << b = N × 2 b
Now, with this background in mind, let's jump into the concept of a barrel shifter. Barrel shifter is simply a digital circuit that implements the left logic bit shifting. Following the input pin convention according to the select pin state (0 or 1) for MUX as shown below, the diagram of the barrel shifter is as follows.
Figure 1 – schematic of a 8-bit barrel shifter. “inp” represents the input (original bits position) and “out” represents the output (after bit shifting).
Figure 1 shows a 8-bit barrel-shifter as an example. The logic circuit allows shifting the input data word left, where the amount of shifting is selected via the control inputs termed “shift”. Several processors include barrel-shifters as part of their ALUs to provide fast shift (and rotate) operations.
The logic circuit shown in Figure 1 consists of three stages of 2-way MUX, with one multiplexer per bit of the input data inp[8]which is binary representation for N.
Given, shift input, shift(2)..shift(0) ,which is binary representation for b
When all multiplexer select inputs are inactive (low), i.e., shift=000, the input data passes straight through the cascade of the multiplexers unchanged (b=0) and the output data out(7)..out(0)= inp(7)..inp(0)
On enabling just shift(0)=1, i.e., shift=001,the first stage of multiplexers performs a shift-left by one bit, i.e. N<<1 operation (b=1), due to their interconnection to the next-lower input. A low input value, 0, is used for the least significant bit, so that the shifter output becomes out(7)..out(0) = inp(6)..inp(0) 0 and in this process dropping inp(7).
Similarly, on enabling just shift(1)=1,i.e., shift=010,the second stage of multiplexers performs a shift-left by two bits, i.e. N<<2 (b=2). Note that the corresponding multiplexer inputs are connected to their second next-lower input, and two zeros are required for the lowest two bits. out(7)..out(0)= inp(5)..inp(0) 0 0
Finally, on enabling just shift(2)=1, i.e., shift=100, the third stage of multiplexers performs a shift-left by four bits, i.e. N<<4 (b=4), with four zero bits filled into the lowest bits. out(7)..out(0)= inp(3)..inp(0) 0 0 0 0
Due to the cascade of three stages, all three shift operations (by one bit, by two bits, and by four bits) can be activated independently from each other. Hence, one can shift a number left , N<< b by enabling appropriate shift(2)..shift(0)
For example, when both shift(0) and shift(2) are activated , i.e. overall shift = 101, the barrel shifter performs shift-left by five bits (b=5), i.e. N<<5. This is realized through first stage where shift(0)=1 results in N<<1,and then the resulting shifted number, N<<1,goes through second stage of MUX unchanged as it was, since shift(1)=0. Finally, it exits the barrel shifter circuit through the third stage of MUX where shift(2)=1 results in shift-left by four more bits, i.e., (N<<1)<<4). So, overall we get the effect of N<<5.
The generalization to higher word-width (e.g. 16 bits) should be obvious
In Project 2 implementation of the barrel shifter (left-logic bit shift), you are operating on a 16-bit data with maximum left-shift allowed is by 8bitpositions i.e. N<<b, where, b={0,1,2,..,8}
In your LeftLogicBitshift.hdl,there are two inputs, x[16]and y[16], and an output,out[16].
x[16] (inp[8] used in above illustration in Figure 1) is the binary representation for number N which needs to be shifted left by bbits, N<<b.
y[16] (shift[3] used in above illustration in Figure 1) is the binary representation of b by which data needs to be shifted left, resulting in
out[16] (out[8] used in above illustration in Figure 1) is the binary representation of N<<b
For instance, x = 0000 0000 1010 0101,and y = 0000 0000 0000 0010 implies that N = 165 needs to be shifted left by b = 2 bits,which should result in 165<<2 = 165 × 2 2 = 165 × 4 = 660 . We can verify this by left-shifting x by 2 bits and observing out = 0000 0010 1001 0100.(The blue out bits represent what part of original input x is still retained and shifted left, while red bits represent the newly appended zeros). Here, the higher significant bits, x(7)x(6) are dropped as bits are shifted left, and the lowest two bits are assigned value zero, i.e., out(1)out(0)= 00.
The HACK ALU
The Hack ALU produces two kinds of outputs: a "main" 16-bit output resulting from operating on the two 16-bit inputs, and two 1-bit "status outputs" named 'zr' and 'ng'. We recommend building this functionality in two stages. In Stage 1, implement an ALU that computes and outputs the 16-bit output only, ignoring the 'zr' and 'ng' status outputs. Once you get this implementation right (that is, once your ALU.hdl code passes the ALU-nostat test), extend your code to handle the two status outputs as well. This way, any problems detected by ALU.tst can be attributed to the incremental code that you've added in Stage 2. We thank Mark Armbrust for proposing this staged implementation plan, and for supplying the test files to support it.
Watch ALU Video:
https://www.youtube.com/watch?v=PEs855FNCOw&list=PLrDd_kMiAuNmSb-CKWQqq9oBFN_K NMTaI&index=17
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.
Resources
The relevant reading for this project is Chapter 2,class notes, and Appendix A.
Specifically, all the chips must be implemented in the Hardware Description Language (HDL) specified in Appendix A.
For each chip, we supply a skeletal .hdl file with 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 .hdlfiles.
The resources that you need for this project are the supplied Hardware Simulator and the files listed above.
Tips
Use built-in chips: Your HDL programs will most likely include chip parts that you've built in Project
As a rule, though, we recommend using the built-in versions of these chips instead. The use of built-in chips ensures correct, efficient, and predictable simulation.
There is a simple way to accomplish this convention: make sure that your project directory includes only the .hdl files of the chips developed in the current project.
