Building a Modern Computer from First Principles — Chap. 1 : Boolean Logic
Lately I’ve been reading the book Building a Modern Computer from First Principles and I thought it would be good to reiterate some of the things I have learned so far. If you are interested in a broad overview of how computers work from the ground up, I highly recommend checking out this resource.
In the preface of this book, they say that many computer science students are missing the forest for the trees. What they mean is that the most fundamental ideas and techniques in computer science are now hidden under many layers of obscure interfaces and proprietary implementations. And this is very true, most of us come into this field starting to learn computer science using these high level languages and we begin to forget that hardware and software are tightly interrelated through a hidden web of abstractions, interfaces, and contract-based implementations. To truly understand how the software you are creating works, you need to understand how the hardware itself is working as well. I come from a biology background and the amount of similarities between computer science and biology is astounding. I think most of us completely overlook the intricacies of the modern computer and do not have any understanding how it works. Talking to friends who have no computer science or programming background will spout off ‘oh yeah, it’s like binary or something, zeroes and ones’. And they aren’t wrong, but there is a lot more to know, so let’s take a look!
Chapter 1 — Boolean Logic
Every single digital device that you or I use (computer, cellphone, router, tv, etc., etc…. The list goes on and on) is based on a set of chips designed to store and process information. Although these chips may come from from different companies and they may come in different sizes or forms, they are all made from the same fundamental building blocks: elementary logic gates (Consider the comparison to biology; We can think of our DNA as being the building blocks of humans, much like we can think of these logic gates as being the building blocks of computers. DNA and logic gates are the roadmap to the physical representation of what we actually see). These logic gates can be physically implemented in many different materials and fabrication technologies, but their logical behavior is consistent across all computers.
We are going to look at a family of simple chips called Boolean gates. Boolean gates are physical representations of Boolean functions. To understand those we will look at some Boolean algebra first.
Boolean algebra deals with Boolean values often referred to as (binary). These values are typically labeled true/false, on/off, 1/0, etc. A Boolean function operates on binary inputs and returns binary outputs. Since computer hardware is based on the representation and manipulation of binary values, Boolean functions play a central role in the specification, construction, and optimization of hardware architectures. The basic Boolean operators that are used are And, Or, and Not and every Boolean function, no matter how complex, can be expressed using these three Boolean operators. The Nand function (also Xor) has an interesting theoretical property, each of the operations And, Or, and Not can be constructed from it. And since every Boolean function can be constructed from And, Or, and Not operations, then every Boolean function can be constructed from Nand operations alone. The practical implications of this is that if we had at our disposal a physical device that implemented the Nand function, we could make many copies of this device and wire it in a certain way to implement in hardware any Boolean function. The hard part is coming up with the right pattern of connectivity to make this all happen.
The most simple gate logic is open/closed. It’s what we know as binary. A gate is a physical device that implements a Boolean function. Just like how complex Boolean functions can be expressed in terms of simpler functions, complex gates are composed from more elementary gates. The most basic gate is called a transistor and this is just a tiny switching device. Today most gates are implemented as transistors etched in silicon, packaged as chips. Since all logic gates have the same input and output semantics (0 and 1), they can be chained together, creating composite gates of arbitrary complexity. The construction of gate logic also called logic design is the art of interconnecting gates in order to implement more complex functionality, leading to composite gates.
If we wanted we could theoretically purchase a soldering gun, a roll of copper wire, and these elementary logic gates And, Or, and Not. We could connect the chips with copper wire and solder the wire ends to the respective input/output pins. If we followed the gate diagrams correctly we should have a functioning Xor gate. If we repeated this process we could have a bunch of Xor gates that could be used to construct a more complicated chip in the future. Although it is easy to prove correctness in simple cases like Xor, we cannot do so in many realistically complex chips. Hardware designers specify the chip structure by writing an HDL (Hardware Description Language) program, which is then subjected to rigorous testing. These tests make sure the chip is giving the desired outputs based on the inputs. In addition to the chips correctness they also design for speed of computation, energy consumption, and the overall cost of the chip design, When the simulated chip is complete this HDL program can become the blueprint from which many copies of the physical chip can be stamped in silicon. This was just the tip of the iceberg when it comes to this topic, so I suggest you look further if interested. Next time, chapter 2.