# Implementing an Arithmetic and Logic Unit

In this coursework, you will implement an 8-bit variant of the Arithmeitc and Logic Unit (ALU) used in the nand2tetris Hack CPU. You will be guided to build the ALU in three stages, starting with the simpler components and building these blocks together to build the final ALU. The details of each component will be released in a staggered fashion over the next few weeks so that you have time to complete them all. This coursework is worth 25% of your final G51CSA mark.

Each of the components are to be developed using the Hardware Design Language (HDL) of the nand2tetris Hardware Simulator. Therefore, it is strongly recommended that you read Appendix A and Project 1 of that before you start the coursework if you have not already done so to gain some experience with the Hardware Simulator. You may also find it helpful to read the chapter on ‘Boolean Arithmetic’ for more information about the ALU. In addition, we will supply test scripts that you can use within the simulator to test your circuits.

Each component will be marked in the G51CSA and G51PRG computing labs by the Preceptors. You will need to show the Preceptors your finished component and run it against the supplied test script. Full Assessment details and a release schedule for the next set of components can be found below

#### Introduction

The ALU is found at the heart of all CPUs and is responsible for performing all the mathematical and logic operations in a CPU. As was described in the lecture, one of the aims is to produce an ALU with as much functionality as needed using the least logic.

A C implementation of the ALU logic can be download here, you might want to use this in conjuction with the lecture slides to experiment with how an ALU works.

Our ALU is represented pictorially below and consists of two 8-bit inputs, `X` and `Y` and one 8-bit output. It also has six control inputs, which are described in both lecture seven, and the ‘Boolean Arithmetic’ chapter of nand2tetris.

The inputs and output are multibit, and so we represent in the HDL as buses. A bus is just a collection of logic signals that we keep together (in this case they reach represent a numeric value in binary). We can define them in the HDL by suffixing the pin name with square brackets, thus: `a[8]`. This denotes that `a` is a bus 8 bits wide, numbered `0–7`. Each individual bit can be accessed by placing the number of the required bit in the square brackets. So `a[3]` would access the fourth bit (remember, numbering starts from zero!). Again, reread Appendix A of nand2tetris for more details on the HDL syntax.

#### Component Set One

As described, the ALU can either add the two inputs together, or boolean and the two inputs together. In addition, both inputs and the output can also be inverted (each bit of the bus is passed through a NOT gate). For this component set, you will create 8-bit versions of these operations that we will combine in later stages to produce the final ALU. In addition, you will also create an 8-bit `MUX`er that can be used to switch between one of two inputs based on a control signal.

For this set of components, you will be implementing four circuts:

• `Not8`

This has one input bus, `in` and one output bus, `out`. Each bit of the output should be inverse (i.e. not) of the corresponding input bit.

• `And8`

This has two input buses, `a` and `b` and one output bus, `out`. Each bit of the output should be the result of anding together the corresponding input bits in `a` and `b`.

• `Add8`

This has two input buses, `a` and `b` and one output bus, `out`. Each bit of the output should be the result of adding together the corresponding input bits in `a` and `b` while making sure that any carry is propagted to the next bit.

Note: You can assume that `FullAdder` is defined on the system already and takes three inputs, `a`, `b` and `c` and produces two outputs `sum` and `carry`. Also, you can use the keywords `true` and `false` to force a value to one or zero respectively, should you need to.

• `Mux8`

This has two input buses, `a` and `b` and one output bus, `out`. Also present is a `sel` input, which is used to select whether input `a` or `b` is passed to `out`. If `sel` is false, input `a` should be selected, otherwise input `b` should be selected.

Note: You can assume that `Mux` is defined on the system already and takes three inputs, `a`, `b` and `sel`, and produces an output `out`.

You can download the skeleton `.hdl` files, and test scripts in this ZIP file. You may assume that the logic gates listed in the Appendix are pre-defined and available for you to use in your circuits.

#### Component Set Two

You are going to develop two additional components in this section, both can be built using the components created during the previous section along with the logic gates listed in the Appendix. As described in the lecture and the nand2tetris chapter on ‘Binary Arithmentic’, our modified Hack ALU allows for both inputs to be either zeored (all bits set to zero) and/or negated (each bit inverted, or run through a not gate) based on the value of a control signal.

The first component you are to create is called `ZeroOrIn`, and has one input bus, `in`, and one output bus, `out`. It also has an input, `z` which is used to say whether the output (`out`) matches the input (`in`) when `z` is `0`, or whether the output is forced to have all bits set to zero (when `z` is 1).

The second component you are to create is similar and called `NegateOrIn`. Again, it has one input bus, `in`, and one output bus, `out`. It also has an input, `z` which is used to say whether the output (`out`) matches the input (`in`) when `z` is `0`, or whether the output is logical inversion (i.e. all bits of the bus have been inverted, or notted) when `z` is 1.

Again, you can download skeleton `.hdl` files as starting points, along with test scripts in this ZIP file. Although, this week, you are required to specify the `IN`puts and `OUT`puts for `CHIP`s in the HDL yourselves, but remember the names must match those given above otherwise they will not be compatible with the test scripts.

#### Component Set Three

There's only one component to implement in this section, the modified Hack ALU itself. You can find the skeleton `.HDL` file and the test scritps in this ZIP file.

The ALU can be constructed purely by using the components you have created in the previous sessions, although you may need to have more than one instance of some of them. Therefore, you should make sure all the `.hdl` files, test scripts and `.cmp` files are all in the same folder on your computer. It helps when constructing this component to mentally follow the signals through the chip from the input buses to the output bus and remember that you cannot change the value of the input signals (as the example C implementation I gave you does). Instead, as with component set two you must produce a new set of signals and select between that new signal and the original. You might find it helpful to draw a diagram on paper showing the connections between the different component while you are developing you solution.

This description refers only to the `x` input, the `y` input bus requires an equivalent path through the chip (apart from the control signals used to control it, which will use the `zy` and `ny` signals instead). The first thing that should happen is that the input on the `x` bus, should be switched to zero if the `zx` control input is `1`. This new signal should then be switched to a negated (bitwise “not”) version if the `nx` signal is `1`.

Having formed an equivalent circuit, for the signal on the `y` bus, you now need to select between the and-ed or add-ed versions of the two input buses based on the control signal `f`, the function code (1 for add, 0 for and). Finally, the selected result should be negated if `no` is 1 before the signal is fed to the output bus, `out`.

#### Assessment

Each component will be marked in the G51CSA and G51PRG computing labs by the Preceptors. You will need to show the Preceptors your finished component and run it against the supplied test script. The Preceptors will then award it a mark based on how it performs against the test script and how well-implemented it is. Each component will be marked on a three point scale — checking whether it works and if it is well implemented. The marks will be awarded thusly:

• A — Component works without issue and is well implemented.
• C — It works but the logic is over-complicated, or it fails some of the tests in the test scripts.
• E — Completely fails to pass test scripts and logic is unrecognisable as a solution.

However, since you will be provided with the test scripts for each component there should be no reason why your circuit fails (since you can test it yourself beforehand). Therefore, YOU WILL ONLY GET ONE DEMONSTRATION ATTEMPT to a preceptor, so remember to check your code first!

The deadline for this coursework is 14th November at 5pm, by which point you will need to have shown all your components to a Preceptor for marking as well as submitting them via Moodle (details to follow). Marking will start, in the labs, the week commencing 27th October. We strongly advise you to get the components marked as soon as you have finished them and not to leave them all to the last minute.

This page will be updated on the dates specified above with details of the next set of components. The (provisional) release schedule for each component set is:

• 21st October – First set of components
• 28th October – Second set of components
• 4th November – Final components

#### Appendix

You may assume that the following logic gates are pre-defined and available for you to use in your components:

• `Not`

Not gate: `out` = not `in`

```CHIP Not
{
IN  in;
OUT out;
…
}
```
• `And`

And gate: `out` = `a` and `b`

```CHIP And
{
IN  a, b;
OUT out;
…
}
```
• `Or`

Or gate: `out` = `a` or `b`

```CHIP Or
{
IN  a, b;
OUT out;
…
}
```
• `Mux`

Multiplexor. If `sel == 1` then `out = b` else `out = a`.

```CHIP Or
{
IN  a, b, sel;
OUT out;
…
}
```
• `FullAdder`

Full adder. Computes `sum`, the least significant bit of `a + b + c`, and `carry`, the most significant bit of `a + b + c`. */

```CHIP FullAdder
{
IN  a, b, c;
OUT sum,     // LSB of a + b + c
carry;   // MSB of a + b + c
…
}
```