Logic design — The what and how of a computer chip

ComputersAug 2021

Logic design is the discipline of computer chip design. These chips sit at the foundation of what a computer is and does. The mechanisms inside computer chips manage manage electrical signals.

The core building blocks of a chip are logic gates—see previous post here—and the core language used to describe them is boolean algebra.

A chip, therefore, is nothing more than a gate. And a gate, in turn, is just a simple chip. A complex chip is made of simpler chips, or gates. This is all akin of legos and in its modularity.

A chip has two parts: its' interface, and architecture.

The interface is made of inputs, an output, and a broad idea of its functionality. The architecture, in turn, is made of smaller building blocks that make the functionality possible. The interface is the what, the architecture the how.

A chip can only have one interface; but it can have many possible architectures, some more efficient than others. This internal architecture of a chip is what the discipline of logic design concerns itself with.

A reminder, we're still very much in the world of binary. Both input and output will always be a zero or a one.

Now, some practical examples.

AND(a, b, c)

Let's take a three-input AND gate.

This means, as expressed in the truth table, that this gate only outputs 1 when all three inputs are 1. This, in essence, is a slightly more complex version of the elementary AND gate.

The challenge now is: how can we build this three-input AND gate using only elementary logic gates (our building blocks). We can do this using two AND gates. Let's deconstruct the function into an expression of this architecture.

This, in turn, translates into this diagram. The outer AND is the gate on the right and the inner AND serves as input to it. The input a, b, and c are completely interchangeable.

As specified, given that our entire architecture is made of AND gates, only when all inputs are 1 will the output be 1.

This is a composite gate; a gate made of other gates. Once built, composite gates can also become the elementary gates for more complex chips.

Xor(a, b)

Another example, the Xor gate, or exclusive OR gate. This gate outputs 1 when only one of its outputs is 1. This Xor gate can be expressed using the following truth table.

he Xor gate can be expressed using the canonical representation expression: A and NOT b or B and NOT a. One for each of the two rows in the truth table above that have 1 as the output.

This can be mapped onto a full boolean expression.

And into the following diagram. The two inputs connect transversally into two different AND gates; in their normal state and in their negated state (NOT); the outcome of that is then inputed onto the final OR gate.

Xor's architecture is composite and its interface simple. Two inputs, one output, and a generic icon to express it.

This is the essence of logic design. To design an architecture of elementary gates that takes a given input and matches it to the desired output.

It's pure logic.

No items found.

Why AND and OR map to multiplication and addition

ComputersAug 2021

I just realized why the AND and OR gates map to multiplication and addition in boolean algebra. We’re essentially inputting a zero or a one into a mathematical expression.

In the case of AND, multiplication makes it so that as long as there’s a 0 in the input we’ll get a 0 in the output. This is because anything multiplied by 0 is, well, zero.

In the case of OR, addition makes it so that as long as there’s a 1 in the input, we’ll end up with a 1 in the output. This is because we have at least one 1 in the input to sum onto the result.

Ah, math is fun!

No items found.

Boolean Functions 101

ComputersAug 2021

Atop the logic gate comes the ability to represent it mathematically. A boolean function gives us that ability. It takes a binary input (either a zero or a one) and returns a binary output.

Take the simple mechanisms AND, OR and NOT. These can be represented using simple expressions. AND maps to multiplication, OR maps to addition, and NOT maps to negation.

Boolean functions are used to describe and conceptualize the binary logic inside a computer chip. Chips are built out of simpler building blocks like AND, OR and NOT.

A boolean function can either be represented as a function:

Or its equivalent truth table. This is an enumeration of all possible inputs and the outputs they map to.

This means that we can construct a truth table out of a boolean function by calculating all possible inputs. But, the reverse is also possible. We can also construct a boolean function out of a truth table.

We do this by [1] isolating all the rows that output 1; [2] constructing a literal expression that represents that particular row of the truth table; and [3] ORing them together. This long boolean function is still an accurate description of the truth table.

This is what is called the canonical representation of a boolean function.

No items found.

Logic gates, visualized.

ComputersAug 2021

The three most basic building blocks atop the electrical signal are the logic gates. At its simplest, a logic gate is a device that mediates the flow of current from the source to the ground. This device is graphically expressed where the letter (a) is positioned in the diagram below:

A gate is made of transistors that take in an input and produce an output. If the lightbulb is on, that means we have a positive output, a truth, a one. If the lightbulb is off, we have a negative, false, or zero output.

Buffer Gate

Take the simplest gate, the buffer gate. In order for the lightbulb to turn on, the input needs to tell the transistor to conduct the current to the ground. If the input is (1), the current will flow and the output will also be (1) – aka. the lightbulb will be on.

NOT Gate

The next simplest gate is the NOT gate. The NOT gate inverts whatever input it is given. If the input is (1), it allows the current to flow. Given that electricity always chooses the path of least resistance, it takes the shortest path down through the transistor. As a result, it will not go through the light bulb and the input will be (0). On the other hand, if the input is (0), the current is forced to take the longer path and therefore turn on the light bulb.

AND Gate

Moving on to the AND gate. Like the name indicates, the AND gate needs both the first AND the second input to be (1). If ant of its transistors is (0), the current will simply not flow through; producing a (0) output.

OR Gate

The OR gate only needs one of its inputs to be (1) in order for the current to flow. As long as one of the inputs is (1) the current flows through and the output is (1).

Truth Tables

These are the most simple operations in boolean logic: AND, OR, and NOT. These are commonly represented using the following graphical system and equivalent truth tables.

Finally, it's worth noting that even though AND and OR are expressed as having two inputs, they can actually have more than two inputs. That being so, their logic remains the same.

No items found.

All digital data is expressed through electrical signals 🤯

ComputersAug 2021

All data in a computer is stored through a binary electrical system – binary as in bi, two. The bit, the computer’s unit of data, is expressed through an electrical signal or the lack thereof. This signal is managed by a transistor, a tiny switch that can be activated by the electrical signals it receives. If the transistor is activated, it conducts electricity. This creates an electrical signature in the computer's memory equivalent to a 1 or a truth. Otherwise, the lack of signal is equivalent to a 0 or a false.

The basis of this binary system, as we have it today, was first introduced by Leibnitz in 1689, as part of an attempt to develop a system to convert verbal logic into the smallest form of pure mathematics. It is said Leibnitz was actually influenced by the i-Ching 🤯 and was attempting to combine his philosophical and religious beliefs with the field of mathematics. Together with George Bool’s work in logic and MIT’s Claude Shanon paper relating them to computing, this was basis for the simple and yet incredibly ingenious system behind today’s digital computer.

There have been ternary and even quinary electrical systems developed in the field of computing. But the more complex the system, the harder it is to tell the difference between different types of voltage; specially when the computer is low on battery or it’s electrical system interfered with by another device (i.e. a microwave). So the world settled on binary, the simplest and most effective system. The voltage is either there or not.

That's how we get zeros and ones: electricity.

No items found.