This markdown uses the high-level language of R to investigate the lowest levels of computing: logic gates. If you can make logic gates, and wire them up together in any way you please, then you can build a general-purpose computer like the one you’re probably reading this document on.
We start by creating the basic logic gates an examining their truth tables. We then show that each of these logic gates can be created from NAND (Not AND), and then put these circuits to work by doing bitwise arithmetic.
The gates we will focus on are:
- NOT
- AND
-
OR
- XOR
- NAND
- NOR
We will start out with the concept of truth. For the sake of this markdown, we will focus on the values TRUE and FALSE. These will be represented by the computer as 1 and 0, respectively. A circuit is investigated using a truth table. In a circuit that has two inputs, a and b, and one output, “out.” We can make what is called a truth table. This is a table where the columns are, in this case, a, b, and out. Then we have rows that represent all the combinations of a and b (a = 0, b = 1; a = 1, b = 1; a = 1, b = 0; a = 0, b = 0), and then the final column telling us what the output is given the values of inputs a and b.
Below is a truth table initialized with columns a, b, and out. We have not put a and b through any circuit yet, so out is currently NA.
library(tidyverse)## ── Attaching packages ─────────────────────────────────────── tidyverse 1.3.2 ──
## ✔ ggplot2 3.3.6 ✔ purrr 0.3.4
## ✔ tibble 3.1.8 ✔ dplyr 1.0.9
## ✔ tidyr 1.2.0 ✔ stringr 1.4.1
## ✔ readr 2.1.2 ✔ forcats 0.5.2
## ── Conflicts ────────────────────────────────────────── tidyverse_conflicts() ──
## ✖ dplyr::filter() masks stats::filter()
## ✖ dplyr::lag() masks stats::lag()a <- c(0, 0, 1, 1)
b <- c(0, 1, 0, 1)
truth_table <- tibble(a = a, b = b, out = NA)
truth_table## # A tibble: 4 × 3
## a b out
## <dbl> <dbl> <lgl>
## 1 0 0 NA
## 2 0 1 NA
## 3 1 0 NA
## 4 1 1 NANow we begin with the basic circuits. We start with NOT, which flips a bit from 1 to 0 or 0 to 1.
NOT <- function(a) {
return(as.numeric(!a))
}
c(1, 0)## [1] 1 0NOT(c(1, 0))## [1] 0 1Now we move to AND, which only outputs 1 if a = 1 and b = 1.
AND <- function(a, b) {
return(as.numeric(a & b))
}
truth_table$out <- AND(truth_table$a, truth_table$b)
truth_table## # A tibble: 4 × 3
## a b out
## <dbl> <dbl> <dbl>
## 1 0 0 0
## 2 0 1 0
## 3 1 0 0
## 4 1 1 1Now we go to or, which outputs 1 if a = 1 or b = 1, or both equal 1.
OR <- function(a, b) {
return(as.numeric(a | b))
}
truth_table$out <- OR(truth_table$a, truth_table$b)
truth_table## # A tibble: 4 × 3
## a b out
## <dbl> <dbl> <dbl>
## 1 0 0 0
## 2 0 1 1
## 3 1 0 1
## 4 1 1 1Now we move to exclusive or, or XOR, which only outputs 1 if a = 1 or b = 1, but not if both equal 1.
XOR <- function(a, b) {
return(as.numeric(xor(a, b)))
}
truth_table$out <- XOR(truth_table$a, truth_table$b)
truth_table## # A tibble: 4 × 3
## a b out
## <dbl> <dbl> <dbl>
## 1 0 0 0
## 2 0 1 1
## 3 1 0 1
## 4 1 1 0Now we move to NAND, or Not AND. This is literally the opposite of AND. So the output is 1 unless a = 1 and b = 1.
NAND <- function(a, b) {
return(as.numeric(!(a & b)))
}
truth_table$out <- NAND(truth_table$a, truth_table$b)
truth_table## # A tibble: 4 × 3
## a b out
## <dbl> <dbl> <dbl>
## 1 0 0 1
## 2 0 1 1
## 3 1 0 1
## 4 1 1 0Below is NOR, or Not OR. It is literally the opposite of OR. If only a = 1 or only b = 1, then the output is 0. Else the output is 1.
NOR <- function(a, b) {
return(as.numeric(!(a | b)))
}
truth_table$out <- NOR(truth_table$a, truth_table$b)
truth_table## # A tibble: 4 × 3
## a b out
## <dbl> <dbl> <dbl>
## 1 0 0 1
## 2 0 1 0
## 3 1 0 0
## 4 1 1 0A key insight in computing is that you can make any logic gate from NAND gates. I will illustrate that here. We will go through all the logic gates we created in the previous section, and re-make them with NAND. We will compare the NAND-made circuits’ truth tables with the truth tables of the original circuits.
We start with NOT.
c(1, 0)## [1] 1 0NOT(c(1, 0))## [1] 0 1NAND_NOT <- function(a) {
return(as.numeric(NAND(a, a)))
}
NAND_NOT(c(1, 0))## [1] 0 1Here is AND.
truth_table$out <- AND(truth_table$a, truth_table$b)
truth_table## # A tibble: 4 × 3
## a b out
## <dbl> <dbl> <dbl>
## 1 0 0 0
## 2 0 1 0
## 3 1 0 0
## 4 1 1 1NAND_AND <- function(a, b) {
return(as.numeric(NAND_NOT(NAND(a, b))))
}
truth_table$out <- NAND_AND(truth_table$a, truth_table$b)
truth_table## # A tibble: 4 × 3
## a b out
## <dbl> <dbl> <dbl>
## 1 0 0 0
## 2 0 1 0
## 3 1 0 0
## 4 1 1 1Next is OR.
truth_table$out <- OR(truth_table$a, truth_table$b)
truth_table## # A tibble: 4 × 3
## a b out
## <dbl> <dbl> <dbl>
## 1 0 0 0
## 2 0 1 1
## 3 1 0 1
## 4 1 1 1NAND_OR <- function(a, b) {
nand_a <- NAND(a, a)
nand_b <- NAND(b, b)
nand_out <- NAND(nand_a, nand_b)
return(nand_out)
}
truth_table$out <- NAND_OR(truth_table$a, truth_table$b)
truth_table## # A tibble: 4 × 3
## a b out
## <dbl> <dbl> <dbl>
## 1 0 0 0
## 2 0 1 1
## 3 1 0 1
## 4 1 1 1And then XOR.
truth_table$out <- XOR(truth_table$a, truth_table$b)
truth_table## # A tibble: 4 × 3
## a b out
## <dbl> <dbl> <dbl>
## 1 0 0 0
## 2 0 1 1
## 3 1 0 1
## 4 1 1 0NAND_XOR <- function(a, b) {
nand_1 <- NAND(a, b)
nand_2a <- NAND(a, nand_1)
nand_2b <- NAND(b, nand_1)
nand_out <- NAND(nand_2a, nand_2b)
return(nand_out)
}
truth_table$out <- NAND_XOR(truth_table$a, truth_table$b)
truth_table## # A tibble: 4 × 3
## a b out
## <dbl> <dbl> <dbl>
## 1 0 0 0
## 2 0 1 1
## 3 1 0 1
## 4 1 1 0And now NOR.
truth_table$out <- NOR(truth_table$a, truth_table$b)
truth_table## # A tibble: 4 × 3
## a b out
## <dbl> <dbl> <dbl>
## 1 0 0 1
## 2 0 1 0
## 3 1 0 0
## 4 1 1 0NAND_NOR <- function(a, b) {
nand_a <- NAND(a, a)
nand_b <- NAND(b, b)
nand_c <- NAND(nand_a, nand_b)
nand_out <- NAND(nand_c, nand_c)
return(nand_out)
}
truth_table$out <- NAND_NOR(truth_table$a, truth_table$b)
truth_table## # A tibble: 4 × 3
## a b out
## <dbl> <dbl> <dbl>
## 1 0 0 1
## 2 0 1 0
## 3 1 0 0
## 4 1 1 0A quick refresher on binary. We count in base 10, or decimal. 111 is
1*10^2 + 1*10^1 + 1*10^0. If we use base 2, we only have 0
and 1. Thus, in binary, 111 would be
1*2^2 + 1*2^1 + 1*10^0. Which is 7.
A half-adder is a basic circuit that takes in two boolean values as input, and outputs a sum and a carry. Think of it like when you would talk through addition by hand in elementary school. 9 + 1 is 0 carry the 1, is 10. But now we’re in binary. So we have 0. 0 + 1 is 1. 1 + 1 is “0 carry the 1” is 10. This allows the computer to do basic arithmetic. Oh, and we can code it up using only NAND gates.
Note that these wiring diagrams can get pretty complicated, so we’re going to utilize the fact that we’ve already made all the basic gates from NAND in the previous section, and we’ll bring them in here. This is called going up a level of abstraction, and it is another fundamental concept in computer science.
half_add_table <- tibble(a = truth_table$a, b = truth_table$b)
half_add_table## # A tibble: 4 × 2
## a b
## <dbl> <dbl>
## 1 0 0
## 2 0 1
## 3 1 0
## 4 1 1Half_adder <- function(a, b) {
carry <- NAND_AND(a, b)
sum_out <- NAND_XOR(a, b)
result <- tibble(carry = carry, sum = sum_out)
return(result)
}
half_add_table <- bind_cols(half_add_table, Half_adder(half_add_table$a, half_add_table$b))
half_add_table## # A tibble: 4 × 4
## a b carry sum
## <dbl> <dbl> <dbl> <dbl>
## 1 0 0 0 0
## 2 0 1 0 1
## 3 1 0 0 1
## 4 1 1 1 0Now we make a one-bit full-adder. The best way to think of this is adding a and b as we did in the half-adder, but then adding in the carry if there was one, thereby “completing” the operation. Again, we will utilize the abstractions we made from NAND gates already to make the wiring a bit easier.
full_add_table <- tibble(a = c(0, 0, 0, 0, 1, 1, 1, 1),
b = c(0, 0, 1, 1, 0, 0, 1, 1),
carry_in = c(0, 1, 0, 1, 0, 1, 0, 1))
Full_adder <- function(a, b, carry_in = 0) {
half_1 <- Half_adder(a, b)
half_2 <- Half_adder(half_1$sum, carry_in)
or_carry <- NAND_OR(a = half_1$carry, b = half_2$carry)
result <- tibble(carry_out = or_carry, sum = half_2$sum)
return(result)
}
full_add_result <- Full_adder(a = full_add_table$a, b = full_add_table$b, carry_in = full_add_table$carry_in)
bind_cols(full_add_table, full_add_result)## # A tibble: 8 × 5
## a b carry_in carry_out sum
## <dbl> <dbl> <dbl> <dbl> <dbl>
## 1 0 0 0 0 0
## 2 0 0 1 0 1
## 3 0 1 0 0 1
## 4 0 1 1 1 0
## 5 1 0 0 0 1
## 6 1 0 1 1 0
## 7 1 1 0 1 0
## 8 1 1 1 1 1In order to do bitwise arithmetic the way computers do, we have to string together full-adders, such that the carry from the previous operation and be moved to the next bit. We’re going to go to 4 bits in this example. We will then count up in binary from 0000 until we get to 17, which will be outputted as 0000 with a carry of 1.
Four_bit_adder <- function(b1, b2, carry_in = 0) {
a4 <- Full_adder(b1[4], b2[4], carry_in)
a3 <- Full_adder(b1[3], b2[3], a4$carry_out)
a2 <- Full_adder(b1[2], b2[2], a3$carry_out)
a1 <- Full_adder(b1[1], b2[1], a2$carry_out)
result <- list(carry = a1$carry_out, sum = c(a1$sum, a2$sum, a3$sum, a4$sum))
return(result)
}
# Now we will count upward from 1 until we max out the 4 bits. Then we will have all 0s and then a carry.
count <- c(0, 0, 0, 0)
carry <- 0
for(i in 1:17) {
print(count)
if(carry != 0) {
print(paste("carry = ", carry))
}
curr <- Four_bit_adder(c(0, 0, 0, 1), count) # Adding 1 to count
count <- curr$sum
carry <- curr$carry
}## [1] 0 0 0 0
## [1] 0 0 0 1
## [1] 0 0 1 0
## [1] 0 0 1 1
## [1] 0 1 0 0
## [1] 0 1 0 1
## [1] 0 1 1 0
## [1] 0 1 1 1
## [1] 1 0 0 0
## [1] 1 0 0 1
## [1] 1 0 1 0
## [1] 1 0 1 1
## [1] 1 1 0 0
## [1] 1 1 0 1
## [1] 1 1 1 0
## [1] 1 1 1 1
## [1] 0 0 0 0
## [1] "carry = 1"We’ve just counted upwards in binary. To keep track of more complex operations, we’re going to write a function that converts binary output into decimal so we can understand it better.
ToDecimal <- function(b) {
result <- lapply(seq(length(b)), function(i) {
return(b[i]*2**(length(b) - i))
}) %>% unlist() %>% sum()
return(result)
}
ToBinary <- function(d) {
if(d == 0) {
return(0)
}
result <- NULL
while(d > 1) {
r <- d %% 2
d <- d %/% 2
result <- c(r, result)
}
result <- c(1, result)
return(result)
}
test <- lapply(0:16, function(i) {
b <- ToBinary(i)
d <- ToDecimal(ToBinary(i))
result <- list(input = i, binary = paste(b,collapse = ""), decimal = d)
}) %>% bind_rows()
test## # A tibble: 17 × 3
## input binary decimal
## <int> <chr> <dbl>
## 1 0 0 0
## 2 1 1 1
## 3 2 10 2
## 4 3 11 3
## 5 4 100 4
## 6 5 101 5
## 7 6 110 6
## 8 7 111 7
## 9 8 1000 8
## 10 9 1001 9
## 11 10 1010 10
## 12 11 1011 11
## 13 12 1100 12
## 14 13 1101 13
## 15 14 1110 14
## 16 15 1111 15
## 17 16 10000 16Ok, now we’re going to make a 16 bit adder by stringing together 4 4-bit adders that we made previously. That will allow us to add numbers that sum up to 2^16 - 1, or 65535. You can see by the way this is set up, that we could in turn string together 4 16-bit adders to create a 64-bit adder, and so on for very large numbers. I’ll leave that as an exercise for the reader. Note that below, we have an extra function that converts a binary number to a sixteen bit representation for the adder In other words, the binary number 101 would become 0000000000000101.
ToSixteen <- function(b) {
while(length(b) < 16) {
b <- c(0, b)
}
return(b)
}
Sixteen_bit_adder <- function(b1, b2) {
# Convert to sixteen bits
b1 <- ToSixteen(b1)
b2 <- ToSixteen(b2)
a4 <- Four_bit_adder(b1[13:16], b2[13:16], 0)
a3 <- Four_bit_adder(b1[9:12], b2[9:12], a4$carry)
a2 <- Four_bit_adder(b1[5:8], b2[5:8], a3$carry)
a1 <- Four_bit_adder(b1[1:4], b2[1:4], a2$carry)
result <- list(carry = a1$carry, sum = c(a1$sum, a2$sum, a3$sum, a4$sum))
return(result)
}Now we’re going to test this by pitting it against R’s adder. To do that, we’re going to make a function that takes decimal values as input, converts them to binary, puts them into the sixteen bit adder, converts the result back to decimal, and outputs the decimal result. This makes the testing easier to read.
Add <- function(a, b) {
a_bin <- ToBinary(a)
b_bin <- ToBinary(b)
result <- Sixteen_bit_adder(a_bin, b_bin)
if(result$carry == 1) {
stop("sum is greater than this adder can handle")
}
result <- ToDecimal(result$sum)
return(result)
}Now we run some tests on random numbers. Note that we’re using R’s internal random number generator here, not one from NAND gates. At least right now.
set.seed(1)
n1 <- runif(20, 0, 32768) %/% 1
n2 <- runif(20, 0, 32767) %/% 1
sum_nand <- lapply(seq(length(n1)), function(i) Add(n1[i], n2[i])) %>% unlist()
sum_r <- lapply(seq(length(n1)), function(i) n1[i] + n2[i]) %>% unlist()
out <- tibble(n1 = n1, n2 = n2, sum_nand = sum_nand, sum_r = sum_r)
out## # A tibble: 20 × 4
## n1 n2 sum_nand sum_r
## <dbl> <dbl> <dbl> <dbl>
## 1 8700 30627 39327 39327
## 2 12193 6951 19144 19144
## 3 18771 21353 40124 40124
## 4 29760 4114 33874 33874
## 5 6608 8756 15364 15364
## 6 29438 12651 42089 42089
## 7 30955 438 31393 31393
## 8 21653 12529 34182 34182
## 9 20614 28497 49111 49111
## 10 2024 11152 13176 13176
## 11 6749 15796 22545 22545
## 12 5785 19645 25430 25430
## 13 22512 16171 38683 38683
## 14 12586 6101 18687 18687
## 15 25226 27110 52336 52336
## 16 16308 21903 38211 38211
## 17 23514 26024 49538 49538
## 18 32502 3536 36038 36038
## 19 12452 23713 36165 36165
## 20 25475 13476 38951 38951From here, there are many different directions you can go. You can use the adder to do subtraction. You can create an arithmetic logic unit that does a number of things. You can also use feedback loops to create RAM. From there, you can start thinking at the level of operating systems.
The key points from this exercise I hope you got are:
- It
doesn’t take much to get to arithmetic from simple logic gates.
-
NAND gates can make all the logic gates we covered, and in turn do
arithmetic.
- Abstraction. We started at the level of logic gates,
and moved to arithmetic. Once we made a circuit we needed, we could
re-use it to make the next thing without having to worry about which
NAND gate hooks up to which. This can almost be thought of as the first
principles of innovation.