From Gates to Arithmetic: The Nand2Tetris Progression

The Nand2Tetris course, affectionately known as "How to Build a Computer From Scratch," is a rigorous exploration of computer architecture. Part two of this journey focuses on translating abstract logic into functional hardware components. Following the construction of basic logic gates, the next logical step is to assemble these gates into more complex circuits that perform arithmetic and logical operations. This phase of the project is critical for understanding how processors execute instructions, moving from Boolean algebra to the foundational elements of an Arithmetic Logic Unit (ALU).

Constructing the HalfAdder and FullAdder

The process begins with the most elementary building blocks of addition: the HalfAdder and the FullAdder. The HalfAdder is designed to add two single bits, producing a sum bit and a carry-out bit. Analyzing its truth table, the sum output can be directly mapped to an XOR gate, while the carry-out output corresponds to an AND gate. This initial step is straightforward, reinforcing the direct correlation between logical operations and hardware implementation.

Building upon the HalfAdder, the FullAdder introduces the capability to add three bits: two input bits and a carry-in bit from a previous stage. This is essential for multi-bit addition. The realization here is that a FullAdder can be constructed by combining two HalfAdders and an OR gate. One HalfAdder sums the two input bits, and its carry output is OR-ed with the carry output of a second HalfAdder, which sums the first sum output with the carry-in bit. This compositional approach—building complex chips from simpler, already-built components—is a cornerstone of efficient hardware design. Instead of redesigning each circuit from first principles, developers leverage existing modules, mirroring software engineering practices.

Diagram illustrating the inputs, outputs, and internal logic of a FullAdder circuit.

Scaling to 16-bit Addition: Add16 and Inc16

With the fundamental adder circuits in place, the next challenge is to perform addition on wider data paths, specifically 16-bit words, which are standard for many early computer architectures. The Add16 chip is designed for this purpose. The initial thought process might involve confusion about how to sum all 16 bits simultaneously. However, the solution lies in a ripple-carry adder architecture. A 16-bit adder is created by chaining sixteen 1-bit adders (effectively, FullAdders) together. The carry-out from each bit position is fed as the carry-in to the next higher bit position. This creates a sequential addition process, where the carry propagates from the least significant bit (LSB) to the most significant bit (MSB).

While this ripple-carry method is conceptually simple and effective for demonstrating the principle, it's not the most performant due to the propagation delay of the carry signal. Nevertheless, for the Nand2Tetris curriculum, it serves as a vital lesson in modular design and bit-wise operations. The Inc16 chip, which increments a 16-bit value by one, can also be implemented using adder logic, specifically by adding the value 1 to the input. This is often achieved by setting the LSB's carry-in to 1 and all other carry-ins to 0, effectively performing `value + 1`.

The Arithmetic Logic Unit (ALU) at its Core

The culmination of this stage is the construction of the ALU. The ALU is the heart of any central processing unit (CPU), responsible for performing arithmetic and logical operations. A typical ALU needs to support a range of functions, including addition, subtraction, logical AND, logical OR, and potentially others like NOT, XOR, and shifts. For the Nand2Tetris ALU, the specification typically includes operations such as AND, OR, NOT, ADD, SUB, and variations like XOR, NAND, and conditional operations based on flags.

Designing the ALU involves integrating previously built components and creating new logic to handle the selection of operations. The ALU receives two 16-bit data inputs (x and y) and a control signal (often called `zx`, `zy`, `nx`, `ny`, `f`, `no`). These control bits dictate the operation to be performed. For instance:

  • `zx` (Zero x): If set, input x is replaced by 0.
  • `zy` (Zero y): If set, input y is replaced by 0.
  • `nx` (Not x): If set, input x is bitwise NOTted.
  • `ny` (Not y): If set, input y is bitwise NOTted.
  • `f` (Function): If set to 1, perform arithmetic operation (ADD, SUB); if 0, perform logical operation (AND, OR, etc.).
  • `no` (Not output): If set, the final output is bitwise NOTted.

Each of these control signals enables specific transformations on the input data before they are fed into the core arithmetic or logic units. For arithmetic operations like ADD and SUB, the Adder (Add16) chip is utilized. Subtraction is typically implemented using two's complement arithmetic: `x - y` is equivalent to `x + (-y)`. The negation of `y` (`-y`) is achieved by bitwise NOTting `y` and then adding 1. The `no` control bit allows for the negation of the final result if required.

For logical operations, gates like AND, OR, and XOR are directly implemented. The ALU design must carefully route the transformed inputs (`nx`, `ny` applied) through the appropriate functional units based on the `f` control bit, and then apply the `no` transformation to the final result. The complexity lies in orchestrating these control signals to select the correct output for each instruction the ALU is designed to handle. The output of the ALU also typically includes condition codes or flags, such as zero (zr) and negative (ng), which indicate properties of the result (e.g., if the result is zero or negative). These flags are crucial for conditional branching in the CPU's control unit.

The Significance of this Stage

Completing the ALU is a major milestone in the Nand2Tetris journey. It represents the integration of numerous smaller components into a functional unit capable of performing the core computational tasks of a processor. This stage solidifies the understanding of how abstract instructions are physically realized in hardware through a hierarchy of increasingly complex circuits. The ability to design and verify these fundamental chips provides a robust foundation for building the more complex components of a computer system, such as the CPU's control unit, memory, and input/output devices. The discipline of analyzing truth tables, composing circuits, and meticulously managing control signals becomes second nature. This practical experience is invaluable for anyone aspiring to work in hardware design, embedded systems, or even low-level software optimization.