Logic Gates & the 1-bit ALU

Before a processor can add, compare, or decide anything, it has to make choices one bit at a time. Those choices are made by logic gates — the smallest building blocks in all of digital hardware. We'll meet the handful you need, then wire two of them together into your very first ALU.

Think you got this already? Skip to Check Yourself

A hand-drawn collection of logic gates labeled Logic Gates: AND, NAND, OR, NOR, and NOT.

1's and 0's

Quite a few people know that their phone, laptop, or even microwave run on a bunch of 1's and 0's, but what are these 1's and 0's exactly? Well… it depends!

The 0's are easy — they are 0 Volts (V) or ground in a circuit. The 1's however could be a couple different values depending on the power supply used in the circuit. Often called V_DD or V_CC, the power supply sets what voltage is read as a '1'. In some applications this '1' or 'high' voltage can be 5V, 3.3V or even 1.8V as technology advances.

We care about these 1's and 0's because they drive the fundamental building blocks of our digital circuits — gates. Gates are driven by wires, each of which carrying a 1 or 0 (most of the time). Depending on the combination of 1's and 0's the gate will send a new signal through the circuit.

A field of 1s and 0s — streams of binary code.

Meet the Gates and their Verilog

There are only a few gates you need to know. Click on each card to flip them and see the Verilog that makes them work!

A NOT gate: a single input of 0 produces an output of 1. — NOT · inverter **Flips its single input** — a 0 becomes a 1, and a 1 becomes a 0.

Verilog HDL

input  wire a;
output wire y;

assign y = ~a;   // ~ denotes bitwise NOT

input  wire a;
output wire y;

assign y = ~a;   // ~ denotes bitwise NOT

y = 0

An AND gate: inputs 1 and 1 produce an output of 1. — AND · both **Outputs 1 only when both inputs are 1** — like two switches wired in a row.

Verilog HDL

input  wire a;
input  wire b;
output wire y;

assign y = a & b;   // & denotes bitwise AND

input  wire a;
input  wire b;
output wire y;

assign y = a & b;   // & denotes bitwise AND

y = 0

An OR gate: inputs 1 and 0 produce an output of 1. — OR · either **Outputs 1 when at least one input is 1** — only 0 and 0 give a 0.

Verilog HDL

input  wire a;
input  wire b;
output wire y;

assign y = a | b;   // | denotes bitwise OR

input  wire a;
input  wire b;
output wire y;

assign y = a | b;   // | denotes bitwise OR

y = 0

An XOR gate: inputs 1 and 1 produce an output of 0. — XOR · difference **Outputs 1 only when the two inputs differ** — matching bits cancel to 0.

Verilog HDL

input  wire a;
input  wire b;
output wire y;

assign y = a ^ b;   // ^ denotes bitwise XOR

input  wire a;
input  wire b;
output wire y;

assign y = a ^ b;   // ^ denotes bitwise XOR

y = 0

A NAND gate: inputs 0 and 0 produce an output of 1. — NAND · not-and **An AND with its answer flipped** — it gives 0 only when both inputs are 1.

Verilog HDL

input  wire a;
input  wire b;
output wire y;

assign y = ~(a & b);   // AND, then NOT

input  wire a;
input  wire b;
output wire y;

assign y = ~(a & b);   // AND, then NOT

y = 0

A NOR gate: inputs 0 and 1 produce an output of 0. — NOR · not-or **An OR with its answer flipped** — it gives 1 only when both inputs are 0.

Verilog HDL

input  wire a;
input  wire b;
output wire y;

assign y = ~(a | b);   // OR, then NOT

input  wire a;
input  wire b;
output wire y;

assign y = ~(a | b);   // OR, then NOT

y = 0

The Truth Table

Since each gate only has a few input combinations, we can enumerate all of them with their corresponding outputs in a table. This table is called a truth table, and is an easy way to describe each gate's behavior.

A truth table for the two-input gates. The a and b columns list all four input combinations; the AND, OR, NAND, NOR, and XOR columns give each gate's output, with every 1 highlighted. — The truth table for each gate discussed thus far. The NOT gate is self explanatory.

The If-Else of Digital Design

Two multiplexers drawn as trapezoids. A 2-by-1 mux picks between inputs a and b with a single select bit. A 4-by-1 mux picks among a, b, c, and d with a 2-bit select. Each passes the chosen input straight through to Result. — MUX · 2×1 & 4×1 **Passes one input straight through** guided by a `sel` signal.

Verilog HDL

module mux_2x1 (
    input  wire in0,
    input  wire in1,
    input  wire sel,
    output wire out
);
    assign out = sel ? in1 : in0;   // sel picks in0 or in1
endmodule

module mux_2x1 (
    input  wire in0,
    input  wire in1,
    input  wire sel,
    output wire out
);
    assign out = sel ? in1 : in0;   // sel picks in0 or in1
endmodule

y = 0

Gates compute answers — but a processor also needs to choose between answers. That job belongs to a multiplexer, or mux: a switch that takes several inputs and a small control signal, and passes exactly one of those inputs through to its output.

A two-way mux is the simplest kind. It has two data inputs, labeled 0 and 1, and a single control wire. When the control is 0 it forwards the first input; when it's 1 it forwards the second. Nothing is computed here! The mux simply decides which existing signal gets to be the output. That single idea is what turns a pile of gates into something that can perform different operations on command.

Muxes come in bigger sizes, too. A 4×1 mux chooses among four inputs, and hence uses a 2-bit control signal to encode all four possibilities. In general, a 2ⁿ×1 mux requires an n-bit control signal. The wider the mux, the more operations our ALU will eventually be able to offer.

Your First ALU

Here it is — your first ALU. It may be tiny, but it still packs a punch! This ALU can perform both AND and OR operations depending on the value of the operation signal.

That's the whole trick, and it's worth pausing on: with a single control wire, the same hardware performs two different operations. The gates do the work; the mux, steered by operation, chooses which work counts. Scale that idea up and you have the defining feature of an ALU — one block that carries out whichever operation the processor asks for.

Here's how we'll build on this:

More operations. Widen the multiplexer, hang more circuits off of it, and above all addition, which needs a new building block called a full adder.
More bits. Real processors work on 32 or 64 bits, not one. We'll line up copies of this slice side by side and pass a carry between them so they can add large numbers together.
Status flags. A full ALU also reports about its result, which is what allows us to perform comparisons between inputs. ALUs also have overflow detection built in, so the processor can figure out how to deal with super large or super small results.

A 1-bit ALU: inputs a and b each feed both an AND gate and an OR gate. Both gate outputs feed a two-way multiplexer whose select line is labeled Operation. The mux output is labeled Result. — ALU · 1-bit **Your first ALU** — AND and OR into a mux, so one `operation` bit picks the result. We'll make it cooler, don't worry.

Verilog HDL

module alu (
    input  wire a,
    input  wire b,
    input  wire operation,
    output wire result
);
    // operation: 0 = AND, 1 = OR
    assign result = operation ? (a | b) : (a & b);
endmodule

module alu (
    input  wire a,
    input  wire b,
    input  wire operation,
    output wire result
);
    // operation: 0 = AND, 1 = OR
    assign result = operation ? (a | b) : (a & b);
endmodule

result = 0

Check Yourself

What are the values of x and y in this circuit?

A logic circuit: an AND gate (inputs 0 and 1) and a value of 1 feed an OR gate; a NOT gate (input 1) and a NOR gate (inputs 1 and 0) feed the two data inputs of a 2-to-1 multiplexer whose select comes from the OR gate; the mux output x feeds a NAND gate together with a 0, producing y.

Continue to the Ripple Carry Adder