Hello! In our last lesson, you built a 4-bit ripple-carry adder, which was a major step in creating a circuit that performs mathematics. You now have the "Arithmetic" component for your computer's CPU.
Today, we will build its counterpart: the "Logic" component. This lesson focuses on constructing a logic unit capable of performing bitwise operations like AND, OR, and NOT on multi-bit numbers. Unlike the adder, where a carry signal had to ripple from one bit to the next, you'll see that logical operations are much simpler to implement in parallel. This unit is the second critical piece of the Arithmetic Logic Unit (ALU) you'll complete in the next lesson.
Bitwise Operations: A Different Kind of Calculation
In the previous lesson, the result of adding A_i and B_i depended on the carry from bit i-1. This is not the case for logical operations.
Since you're familiar with C, you've likely used bitwise operators like & (AND), | (OR), and ~ (NOT). In hardware, these operations are performed in an "embarrassingly parallel" fashion. This means the operation on each pair of bits is completely independent of all the others.
For example, to compute 1011 & 0101, we perform four independent AND operations:
- bit 0:
1 & 1 = 1 - bit 1:
1 & 0 = 0 - bit 2:
0 & 1 = 0 - bit 3:
1 & 0 = 0
The result is 0001. Notice that the calculation for bit 2 has no effect on the calculation for bit 3. This lack of dependency makes the hardware design remarkably straightforward.
Constructing Multi-Bit Logic Gates
If a 1-bit AND operation is done with one AND gate, how do you perform a 16-bit AND? You simply use 16 AND gates side-by-side. The first AND gate takes A[0] and B[0], the second takes A[1] and B[1], and so on, up to the 16th gate taking A[15] and B[15]. The same principle applies to OR, XOR, and NOT.
The following resource shows this concept implemented in a Hardware Description Language (HDL). While you don't need to learn HDL syntax, notice the simple, repetitive structure of the code for building 16-bit versions of NOT, AND, and OR gates.
This GitHub repository contains solutions for the Nand2Tetris course, which involves building a computer from the ground up. The HDL files provide a clear, textual representation of the hardware circuits.
On the page, scroll down until you find the HDL code snippets. First, look at the code under Not16. You can see it's just 16 individual NOT gates (implemented here with NANDs), one for each bit of the 16-bit input. Next, examine the code for And16. Again, it's a simple list of 16 And gates, each operating on a corresponding pair of bits from the two 16-bit inputs. Finally, look at the code for Or16, which follows the exact same parallel pattern.
This demonstrates the core principle: a multi-bit logic gate is just an array of single-bit gates operating in parallel.
A Configurable Logic Unit: The "Bit-Slice" Design
We don't want to build a separate circuit for every single operation. Ideally, we want one versatile unit that can perform AND, OR, NOT, etc., based on a command. This is achieved by combining our parallel logic blocks with a multiplexer (MUX), a component you designed in a previous lesson.
The strategy is as follows:
- Perform all possible logical operations on the inputs simultaneously and in parallel.
- Feed all the results into a large multiplexer.
- Use the multiplexer's select lines to choose which one of the results to pass to the final output.
This design is often done using a "bit-slice" approach. We first design a circuit that can perform all the desired operations for a single bit, and then we stack N of these slices together to create an N-bit unit.
The image below shows a 1-bit slice for a configurable logic unit.
In this diagram, the select lines S0, S1, and S2 act as an opcode (operation code). If you set the select lines to 001, the MUX might select the output of the AND gate. If you set them to 010, it might select the output of the OR gate, and so on.
To create a 16-bit logic unit, you would arrange 16 of these "bit-slices" side-by-side. The multi-bit inputs A and B would be wired such that A[0] and B[0] go to the first slice, A[1] and B[1] go to the second, and so on. Crucially, the opcode lines (S0, S1, S2) would be shared across all 16 slices, ensuring they all perform the same operation at the same time.
The following video explains this concept clearly, showing the design of a 1-bit ALU and discussing how bitwise operations are handled across multiple bits.
Video 34: Basic ALU Design, CS/ECE 3810 Computer Organization
This video from a University of Utah course on Computer Organization explains the design of a basic ALU, starting with a 1-bit slice.
First, watch the segment that introduces the 1-bit ALU design. Pay attention to how an and-gate, or-gate, and adder all compute their results in parallel, with a MUX selecting the final output. Next, watch the explanation of bitwise operations. The key takeaway here is that for logical operations like AND and OR, "there's really no carry out or exchange of information between these different ALU blocks."
Practical Walkthrough: Building an 8-bit ALU in a Simulator
The best way to solidify this concept is to see it in action. The following video tutorial walks through the entire process in the LogiSim circuit simulator. It demonstrates exactly the "bit-slice" architecture we've been discussing: building a 1-bit unit and then combining 8 of them to create an 8-bit ALU.
CSE 230 - LogiSim ALU Tutorial
This LogiSim tutorial by Ryan Meuth shows the step-by-step construction of an ALU. We'll focus on the parts relevant to creating a multi-bit logic unit from single-bit slices.
First, watch the section on building the 1-bit ALU. You'll see the instructor place AND, OR, XOR, and other components, wire them to common inputs, and use a MUX to select the operation. This is a practical implementation of the block diagram you saw earlier. Next, watch how these 1-bit units are used to build an 8-bit ALU. The instructor places eight of the 1-bit ALU components he just designed. Pay close attention to how a single 3-bit op (operation) input is wired to all eight slices, ensuring they all perform the same function. This is the bit-slice design in practice.
Conclusion
You have now designed the logic unit, the second major component of a CPU's core. You've seen how to perform bitwise operations on multi-bit numbers and, more importantly, how to create a single, configurable unit that can be instructed to perform any of a set of logical operations.
Key takeaways from this lesson:
- Bitwise logical operations like AND, OR, and NOT are "embarrassingly parallel," as the calculation for each bit is independent.
- An N-bit logic gate is built from N single-bit gates, with no connections between them.
- A configurable logic unit uses multiplexers to select which operation's output to use, controlled by "opcode" select lines.
- Complex multi-bit units are often built using a bit-slice architecture: design a 1-bit version of the unit, then replicate it N times, sharing the control signals across all slices.
In the previous lesson, you built an adder. In this lesson, you built a logic unit. In the next lesson, you will combine these two powerful components, using the same multiplexer-based selection technique, to create a complete Arithmetic Logic Unit (ALU)—the computational heart of your computer.