Read the original article here.

---

The Building Blocks of Computation: Understanding Logic Gates

Welcome to the fundamental level of computer architecture! Before you can even think about processors, memory, or software, you must understand the absolute simplest building block: the logic gate. In the context of building a computer from scratch, logic gates are the atomic components that perform basic decisions based on simple rules. By combining many of these simple gates, we can construct incredibly complex systems capable of computation.

What is a Logic Gate?

At its core, a logic gate is a digital circuit that performs a fundamental logical operation on one or more binary inputs and produces a single binary output.

Logic Gate: An electronic circuit (or other physical device) that implements a Boolean function, performing a logical operation on one or more binary inputs to produce a single binary output.

Boolean Function: A function that operates on binary values (typically represented as 0 and 1, or False and True) and produces a binary output. Boolean algebra, developed by George Boole, provides the mathematical foundation for digital logic.

Binary: A number system using only two digits, 0 and 1. In digital electronics, these typically represent two distinct voltage levels or states (e.g., low voltage/off for 0, high voltage/on for 1).

Think of a logic gate as a tiny decision-maker. It looks at its inputs (which are either 0 or 1) and, based on its specific design, determines whether its output should be 0 or 1. The relationship between the inputs and the output is defined by a specific logical rule.

While the concept of a logic gate is an ideal mathematical one (an ideal logic gate might have instantaneous output changes and unlimited capacity to drive other gates), in the real world, they are physical devices with limitations (like small delays in processing and limited output power). Understanding these real-world characteristics is crucial when building actual circuits.

How are Logic Gates Physically Built?

The most common way to build logic gates today is using electronic components that act as switches. The primary technology involves transistors.

Transistor: A semiconductor device used to amplify or switch electronic signals and electrical power. Transistors are fundamental building blocks of electronic devices, particularly in digital circuits where they act as tiny, electrically controlled switches.

Historically, logic gates have been implemented using various technologies:

• Electromagnetic Relays: Used in early computers like the Harvard Mark I and Zuse's Z1. These are physical switches activated by an electromagnet. Relatively slow and bulky.
• Vacuum Tubes (Thermionic Valves): Faster than relays, used in early electronic computers like ENIAC. Still relatively large, consumed a lot of power, and generated significant heat.
• Diodes and Transistors: The advent of solid-state electronics revolutionized logic gates. Diodes can perform basic logic (like AND and OR), and transistors (like bipolar transistors and MOSFETs) act as efficient, small, fast, and low-power switches controlled by an electrical signal.

Today, the vast majority of logic gates are built using MOSFETs (Metal–Oxide–Semiconductor Field-Effect Transistors), specifically in CMOS (Complementary Metal–Oxide–Semiconductor) technology. CMOS is favored for its very low power consumption when idle and good speed.

Beyond electronics, logic has also been demonstrated using:

• Fluidic/Pneumatic Logic: Using the flow of fluids or air.
• Optical Logic: Using light.
• Mechanical Logic: Using gears, levers, or other physical parts (like Babbage's Analytical Engine).
• Molecular Logic: Using chemical reactions.
• Acoustic and Thermal Elements: Even sound waves or heat flow can be used to perform logic functions in theory.

For building a computer from scratch today, understanding the electronic implementation, particularly with transistors (or using pre-made transistor-based Integrated Circuits), is the most practical path.

From Simple Operations to Complex Circuits

The true power of logic gates comes from their ability to be cascaded – the output of one gate can be connected to the input(s) of one or more other gates. This mirrors how complex Boolean functions can be composed from simpler ones.

By cascading gates, we can build progressively more complex circuits that perform specific tasks:

• Multiplexers: Circuits that select one of several input signals based on a separate set of control inputs.
• Registers: Groups of logic gates (specifically, memory elements) that store a binary value.
• Arithmetic Logic Units (ALUs): Circuits that perform arithmetic (like addition, subtraction) and logical (like AND, OR, NOT) operations on binary numbers. ALUs are a core component of a CPU.
• Computer Memory: Circuits designed specifically to store large amounts of binary data.
• Microprocessors: Complex integrated circuits containing millions or billions of logic gates working together to execute instructions.

The ability to build these complex circuits from simple gates is why logic gates are considered the fundamental building blocks of all digital computers.

Certain combinations of gates are so common that they are sometimes manufactured as single, integrated "compound gates," such as AND-OR-Invert (AOI) and OR-AND-Invert (OAI) gates. These can sometimes be more efficient to build directly in silicon using MOSFETs than creating the equivalent circuit from separate AND, OR, and NOT gates.

Defining Gate Behavior: Truth Tables

The behavior of any logic gate is completely defined by its truth table. A truth table lists all possible combinations of input values and the corresponding output value for that gate.

Truth Table: A mathematical table used in Boolean algebra to compute the functional values of a logical expression on all of its functional arguments, that is, for all possible combinations of values taken by its logical variables. For a logic gate, it lists every possible set of binary inputs and the resulting binary output.

For a gate with n inputs, there will be 2ⁿ rows in its truth table, representing all possible input combinations.

Here are the truth tables for some of the most common basic logic gates (which you will encounter when building logic circuits):

Input A	Input B	AND Output	OR Output	XOR Output	NAND Output	NOR Output	XNOR Output
0	0	0	0	0	1	1	1
0	1	0	1	1	1	0	0
1	0	0	1	1	1	0	0
1	1	1	1	0	0	0	1

(Note: The NOT gate is not shown here as it typically has only one input. Its truth table is simply: Input A | NOT Output; 0 | 1; 1 | 0)

Understanding truth tables is absolutely essential. When you design a complex logic circuit, you are essentially designing a circuit whose overall behavior is described by a very large truth table (or a combination of smaller ones).

Symbolic Representation of Logic Gates

To draw logic circuits easily, standardized graphical symbols are used for each type of gate. There are two main sets of symbols:

1. Distinctive Shape Symbols: These are more traditional symbols, often called "military" symbols due to their origin in US military standards. They use unique shapes for each gate type (e.g., a pointy shape for AND, a curved shape for OR). They are useful for simple diagrams.

   Distinctive Shape Symbol: A graphical representation for logic gates using unique shapes for each gate type (AND, OR, NOT, etc.), often associated with US standards like MIL-STD-806.

2. Rectangular Shape Symbols: These symbols, defined by standards like IEC 60617-12 and ANSI/IEEE Std 91, use rectangular outlines for all gates but include symbols inside the rectangle to denote the gate's function (e.g., '&' for AND, '≥1' for OR). These are more versatile for representing complex or non-standard logic functions within a single symbol.

   Rectangular Shape Symbol: A graphical representation for logic gates using a standard rectangular outline for all gate types, with symbols inside the rectangle indicating the specific logic function, defined by international standards like IEC 60617-12.

While distinctive shapes are common in introductory materials and simple schematics, rectangular shapes are prevalent in more complex professional diagrams, especially those using higher-level integrated circuits. For building simple circuits from scratch using discrete gates or basic ICs, you will likely encounter distinctive shape symbols most often.

De Morgan's Laws and Alternative Symbols

An important concept related to logic gates and their representation is De Morgan's Laws. These laws provide equivalences between AND, OR, and NOT operations:

De Morgan's Laws: A pair of transformation rules in Boolean algebra. They state that the negation of a conjunction (AND) is the disjunction (OR) of the negations, and the negation of a disjunction (OR) is the conjunction (AND) of the negations. In terms of gates:

• NOT (A AND B) is equivalent to (NOT A) OR (NOT B)
• NOT (A OR B) is equivalent to (NOT A) AND (NOT B)

This means a NAND gate is equivalent to an OR gate with inverted inputs, and a NOR gate is equivalent to an AND gate with inverted inputs.

These equivalences lead to alternative symbols for gates like NAND and NOR. A NAND gate symbol (AND shape with an output bubble) can also be drawn as an OR shape with bubbles on both inputs. Similarly, a NOR gate symbol (OR shape with an output bubble) can be drawn as an AND shape with bubbles on both inputs.

These alternative symbols are not just different ways to draw the same thing; they are often used in circuit diagrams to improve clarity and show the intent of the logic in a specific part of the circuit.

• A bubble on an input or output line indicates an inversion or negation.
• A bubble on an input often signifies that the gate is activated or performs its function when that input is low (0 volts, logical 0). This is called active-low logic.
• A lack of a bubble on an input signifies it's activated when high (positive voltage, logical 1). This is active-high logic.

For example, a NAND gate (output is 0 only if ALL inputs are 1) can be drawn as an OR gate with inverted inputs. This second symbol is useful if the circuit is designed such that the gate is intended to produce a HIGH output whenever any of its active-low inputs are asserted (low). Using the OR-with-inverted-inputs symbol clearly shows that the OR logic on active-low signals is the focus.

In complex schematics, seeing matching bubbles at the connection points between gates indicates that the logic "flows" without an inversion at that specific point, making it easier to follow the signal's logical state (high or low). Learning to interpret these symbols and their De Morgan equivalents is part of reading real-world logic diagrams.

Universal Gates: Building Everything from One Type

A remarkable property of certain logic gates is that they are universal. This means that any other logic gate (AND, OR, NOT, XOR, etc.) and, therefore, any combinational logic circuit, can be constructed using only instances of that universal gate type.

Universal Logic Gate: A logic gate that, by itself or in conjunction with other gates of the same type, can be used to implement any Boolean function or logic circuit.

The two most common universal gates are:

1. NAND Gate: The output is LOW only if all inputs are HIGH.
2. NOR Gate: The output is HIGH only if all inputs are LOW.

This property is incredibly important from a manufacturing standpoint. If you want to build a complex digital system, you don't necessarily need to manufacture chips containing every single type of gate. You could, in principle, manufacture only NAND gates (or only NOR gates) and use them as the sole building blocks for the entire system, including the memory and processor.

For example, you can build a NOT gate using a single NAND gate by connecting its two inputs together. You can then use NAND gates (and your new NAND-based NOT gate) to build an AND gate, and so on. This demonstrates the "functional completeness" of NAND and NOR gates.

Functional Completeness: A property of a set of logic gates or Boolean functions where the set can be used to express all possible Boolean functions. NAND gates alone are functionally complete, and NOR gates alone are functionally complete.

Storing Information: Introducing Sequential Logic

So far, we've primarily discussed combinational logic, where the output of a circuit depends only on the current inputs. Change the inputs, and the output potentially changes immediately (after propagation delay).

Combinational Logic: A type of digital logic circuit whose output is a pure function of the present inputs only. It has no memory of past inputs.

However, a computer needs memory – the ability to store results, instructions, and data. This requires sequential logic, where the output depends not only on the current inputs but also on the circuit's previous state. Sequential logic circuits have memory.

Sequential Logic: A type of digital logic circuit whose output depends not only on the present inputs but also on the sequence of past inputs; in other words, it has memory or 'state'.

Logic gates can be interconnected in specific ways, often with feedback loops, to create simple memory elements. The most basic is a latch.

Latch: A type of sequential logic circuit that holds a binary state (either 0 or 1) based on inputs, and maintains that state until the inputs change. Latches are sensitive to input level changes.

A more refined memory element is the flip-flop.

Flip-Flop: A fundamental sequential logic circuit that stores a single bit of information. Unlike latches, flip-flops are typically synchronized by a clock signal and change state only on a specific edge (rising or falling) of the clock pulse. They are called bistable circuits because they have two stable states.

By arranging multiple flip-flops in parallel, you can create a register, which is a small, fast storage location used to hold multiple bits (a word of data).

Register: A small, high-speed storage location within a computer's CPU or other digital circuit, typically implemented using multiple flip-flops to hold a sequence of bits (a binary number or instruction).

Memory circuits like Static Random-Access Memory (SRAM) are built using configurations of logic gates forming latches or flip-flops. The ability to create sequential logic circuits from gates is the critical step that allows computers to store information and execute sequences of operations, not just perform instant calculations.

The Evolution of Electronic Gates and Logic Families

The shift from bulky relays and power-hungry vacuum tubes to compact, efficient semiconductor transistors was revolutionary. Electronic logic gates offer tremendous advantages:

• Speed: Millions of times faster than relays.
• Size: Billions can fit on a single chip, compared to discrete components.
• Power Consumption: Much lower, especially with technologies like CMOS.
• Reliability: Fewer moving parts (zero for solid-state) means less wear and failure.

A key difference is that mechanical/relay switches typically create a direct conductive path, allowing current flow in either direction. Semiconductor gates, particularly modern ones, act more like high-gain amplifiers or controlled switches that direct current flow and produce a distinct voltage level at the output, effectively isolating the input from the output and providing signal gain.

When building circuits with discrete components or early integrated circuits (ICs), designers often used components from specific logic families.

Logic Family: A group of digital integrated circuits (ICs) that share the same basic electronic design, resulting in compatible electrical characteristics (such as voltage levels for 0 and 1, power consumption, and speed). Examples include TTL, CMOS, etc.

Early transistor logic families included:

• RTL (Resistor-Transistor Logic): Simple, but relatively slow and high power consumption.
• DTL (Diode-Transistor Logic): Improved upon RTL, replacing input resistors with diodes.
• TTL (Transistor-Transistor Logic): Became very popular (famously the 7400 series ICs). Offered good speed and noise immunity for its time. Used bipolar transistors.

The development of MOSFETs led to new families:

• PMOS and NMOS: Early MOSFET logic types.
• CMOS (Complementary Metal–Oxide–Semiconductor): Combines p-channel and n-channel MOSFETs in a complementary way. This is the dominant technology today due to its extremely low static power consumption and ability to operate at high speeds. (The 4000 series and modern descendants of the 7400 series use CMOS).

An important aspect of using logic families, especially in early "from scratch" builds using standard ICs (like the 74HCxx series, which are CMOS versions of TTL), is that they are designed to be easily cascadable. The output of one gate provides the correct voltage levels and sufficient current to drive the inputs of other gates in the same family.

When cascading gates, two practical limitations become important:

1. Fan-out: The maximum number of inputs that a single gate's output can reliably drive. Exceeding this can lead to insufficient voltage levels or slow transitions, causing errors.

   Fan-out: The maximum number of inputs of other gates that the output of a logic gate can connect to without degrading the performance or correctness of the circuit.

2. Propagation Delay: The small, but non-zero, time delay between a change in a gate's input(s) and the corresponding change in its output.

   Propagation Delay: The time required for a signal to pass through a logic gate or circuit, measured from the time the input changes to the time the output stabilizes at its new state.

In complex circuits, especially synchronous ones controlled by a clock, total propagation delay through multiple cascaded gates determines the maximum speed at which the circuit can reliably operate. Fan-out affects signal integrity and speed as well.

While you could build gates from individual transistors, for anything beyond the simplest demonstrations, using pre-fabricated logic gates in Integrated Circuits (ICs) like those from the 7400 or 4000 series families is the standard approach for hands-on building, providing reliable, small, and fast logic functions.

Specialized Gates: Three-State Logic

Most logic gates have two output states: High (representing 1) or Low (representing 0). However, some gates have a third output state: high-impedance (Z).

Three-State Logic Gate (or Tri-State Gate): A type of logic gate that can produce a High output (active), a Low output (active), or a High-Impedance output (inactive).

High-Impedance State (Z): An output state in digital electronics where the output terminal is effectively disconnected from the rest of the circuit. It is neither actively driving the line high nor actively driving it low. It acts like a very high resistance or an open circuit.

Three-state gates are essential for designing systems where multiple devices need to share the same set of wires, like a bus. A bus is a collection of wires used to transfer data between different components (like the CPU, memory, and peripherals). If multiple devices tried to put data onto the bus wires simultaneously, their output signals would collide, potentially causing damage or incorrect data.

With three-state gates, only one device at a time is enabled to output onto the bus (its output is High or Low). All other devices connected to that bus have their outputs in the high-impedance state, effectively getting out of the way and not interfering with the signal on the bus. A separate control signal determines which device's output is active.

This is fundamentally equivalent to using a multiplexer circuit, but distributing the control and output buffers across different chips or locations is often more practical in bus-based system design.

Historical Development Highlights

The path to modern logic gates was a long one, built on centuries of theoretical and practical work:

• 1705: Gottfried Wilhelm Leibniz refines the binary number system and recognizes its connection to logic, influenced by ancient systems.
• 1837: Charles Babbage designs the Analytical Engine, a mechanical computer using gears to perform logic functions.
• 1886: Charles Sanders Peirce describes how electrical switching circuits can perform logical operations, laying theoretical groundwork for relay logic.
• Early 20th Century: Electromechanical computers are built using relays and switches.
• 1913: Henry M. Sheffer proves the functional completeness of the NAND operation (Sheffer stroke).
• 1924: Walther Bothe creates one of the first modern electronic AND gates using vacuum tubes (coincidence circuit).
• 1935-1938: Konrad Zuse builds his Z1 computer using electromechanical logic gates.
• 1930s: Akira Nakashima, Claude Shannon, and Victor Shestakov independently show that Boolean algebra can describe and simplify the design of switching circuits, establishing the theoretical foundation for digital circuit design.
• 1940s-1950s: Vacuum tube logic is prevalent in early electronic computers.
• 1948: The invention of the transistor (Bardeen and Brattain, building on earlier concepts) paves the way for much smaller, faster, and more efficient electronic gates.
• 1950s-1960s: Early transistor logic families like RTL, DTL, and TTL are developed and integrated into ICs (like the 7400 series).
• 1960s: Development of MOSFET technology (PMOS, NMOS) and the crucial invention of CMOS logic by Sah and Wanlass in 1963, leading to significant power savings and density improvements that are fundamental to modern computing.

This history shows a clear progression from abstract logical ideas to mechanical implementations, then through various electronic technologies, constantly seeking faster, smaller, and more efficient ways to perform the same basic logical operations.

Conclusion

Logic gates are not just abstract symbols; they are physical devices that implement the fundamental operations of Boolean logic using components like transistors. By understanding how these simple gates work and how they can be combined (cascaded), how their behavior is defined (truth tables), how they are represented (symbols), and how they can even store information (sequential logic), you unlock the secrets of how complex digital systems, including computers, are built from the ground up.

Whether you plan to wire together simple ICs, work with programmable logic, or just want a deep understanding of the computer age, mastering the concept of the logic gate is the essential first step in the lost art of building a computer from scratch.