How do computers do math?

This the fourth part of the quest to answer How do computers do math? Here we will start with an introduction to digital logic, dive into the semiconductor physics and finish with an implementation in diode-resistor logic.\(\)

Diodes

Digital systems use gates to make logical operations based on their input signals. These gates take one or more binary inputs and produce one binary output.

The OR gate is one of the simplest gates. The symbol and truth table for the OR gate are shown in the illustration below. The output is 1 when either input A or B are 1, otherwise it is 0. The OR gate is represented by Boolean algebra operator \(+\). Note that in Boolean algebra \(1+1=1\).


(c) Copyright 2016, Coert Vonk
OR gate

\(A\) \(B\) \(A+B\)
0 0 0
0 1 1
1 0 1
1 1 1
(c) Copyright 2016, Coert Vonk
AND gate

\(A\) \(B\) \(A\cdot B\)
0 0 0
0 1 0
1 0 0
1 1 1

The AND gate, is represented by the Boolean algebra operator ‘\(\cdot\)’. Its output is 1 when both inputs are 1, otherwise it is 0.

Other gates include eXclusive OR (XOR) and the inverter (NOT) represented by respectively \(\oplus\) and a bar as in \(\overline{A}\). Sometimes a gate is combined with an inverter to form NOR or NAND. The table below gives an overview of these gates and their truth tables.

(c) Copyright 2016, Coert Vonk
XOR gate

\(A\) \(B\) \(A \oplus B\)
0 0 0
0 1 1
1 0 1
1 1 0
(c) Copyright 2016, Coert Vonk
NOT gate

\(A\) \(\overline A\)
0 1
1 0
(c) Copyright 2016, Coert Vonk
NOR gate

\(A\) \(B\) \(\overline{A+B}\)
0 0 1
0 1 0
1 0 0
1 1 0
(c) Copyright 2016, Coert Vonk
NAND gate

\(A\) \(B\) \(\overline{A\cdot B}\)
0 0 1
0 1 1
1 0 1
1 1 0

History

There are many different ways to implemented digital logic. Nazi Germany (1941) used a system with electro-mechanical relays to calculate artillery-firing tables. Two years later the US army build a vacuum tube based system to simulate the hydrogen bomb. Currently, digital systems are build using the semiconductors that we will discuss here.

Semiconductor physics

Did you ever wonder about the zigzag line on the right of the periodic table? It separates the metals (conductors) on the left from the non-metals (insulators) on the right. The elements on the zigzag line itself share some properties of both conductors and insulators. These elements are the semiconductors or metalloids.


http://www.ptable.com/
Periodic table Illustration , source: ptable.com

Using these semiconductors, we can build the gates that we need for digital systems. For this discussion, we will focus on the element silicon for building gates.

Pure silicon

The element silicon is a commonly used semiconductor material. Silicon has four electrons in the outer shell (valence shell). It forms a covalent bond with four neighboring atoms so that in its valence shell all eight electrons are present as shown in the illustration below. The strong bond holds the atoms together making the element stable.


(c) Copyright 2016, Coert Vonk
Covalent bonds between Silicon atoms

The bond helps form an orderly crystal-like structure called a lattice.
Because there are no free electrons, the material will not conduct electricity. The illustration below shows a simplified view of the lattice. The conductivity can be increased by adding very small (<1 ppm) impurities. Examples of impurities are phosphorous and boron.

N-type silicon

Adding a tiny amount of Phosphorous, with five electrons in valence band, leaves an extra electron that can move easily. Four out of the five valence electrons bond with its neighboring silicon atoms leaving one free electron to become mobile. The resulting material is an n-type because of the abundance of negative electrons.

When you apply a voltage over the material, electrons will move through the crystal just as current would flow in a copper wire. The positive potential of a battery will attract the free electrons in the crystal. These electrons will leave the crystal and flow into the positive terminal of the battery. As electrons leaves the lattice, electrons from the negative terminal of the battery will enter the lattice, thus completing the circuit.

P-type silicon

Adding a tiny amount of Boron to Silicon, with only three electrons in the valence band, can only form three covalent bonds. This leaves a hole where an electron can go. The hole can move if a neighboring electron fills the hole, thereby creating a new hole in the neighboring location. You can imagine a hole has missing a negatively charged electron. In other words, the hole has a positive charge. The resulting material is a p-type semiconductor.

Conduction in the p-type material is by positive holes, instead of negative electrons. A hole moves from the positive terminal of the P material to the negative terminal. Electrons from the external circuit enter the negative terminal of the material and fill holes near this terminal. The positive terminal removes electrons are from the covalent bonds, thus creating new holes. This process continues as the steady stream of holes (hole current) moves toward the negative terminal.

PN-junction

The magic starts when you create a PN-junction by bringing a p-type and n-type material in close contact. In the interface layer, the electrons from the n-type material and the holes from the p-type attract and eliminate each other (recombination). Because there is a lack of free electrons and holes in this area, we call it the depletion region.

The loss of an electron from the n-type material leaves a positive ion, while the loss of a hole from the p-type material leaves a negative ion. The crystal lattice structure keeps these charged ions in place thereby creating an electrostatic field across the junction.

This continues until the electric field from the negatively charged ions in the p-type material get so strong that it repels the free electrons from the n-type material. In other words, the recombination of electrons and holes across the junction continues until the electrostatic field reaches the point where the electrons and holes no longer have enough energy to overcome it. At this point equilibrium is established and for all practical purposes, the movement of carriers across the junction ceases.

This so called depletion layer, has no free electrons or holes, and consequently does not conduct electricity. At the depletion layer, the ions in the n- and p-type materials cause a respectively positive and negative charge. This potential difference is typically 0.65 volts for silicon. In effect, the n-type material has become positive compared to the p-type. If there were a free electron at junction barrier, it will now require extra energy to cross the depletion region.

PN-junction diode

This pn-junction makes a diode that conducts electrical current in one direction, and blocks current in the other direction. We will explain this by applying a bias voltage over the diode visualized with a battery. The energy from the battery will affect the depletion zone shown in white. First, we show the symbol and some samples of diodes below.

Reverse bias occurs when we apply a negative voltage, as shown below on the left. The free electrons in the n-region are pulled to the + terminal of the battery and the holes in the p-type region are pulled to the -. With both charge carriers pulled away from the junction, the depletion layer widens and the diode will conduct electricity even less.

When we reverse the battery, the diode is in forward bias, as shown above on the right. The free electrons in the n-region are attracted to the + terminal, and the holes in the p-type region are attracted to the electrons on the - terminal. With both the electrons and holes pulled towards the junction, the depletion layer gets very thin. Once enough voltage is applied, the diode starts conducting and electrons and holes flow freely with minimum resistance. This threshold voltage \(U_{th}\) is about 0.65 volt for silicon diodes.

With the two opposite flow of electrons and holes, some will recombine. The electron will fall from a higher energy level to a the lower energy level of the hole. The energy is released in the form of a photon. According to quantum theory, the energy of a photon is the product of frequency \(f\) of electromagnetic radiation and the Planck constant \(\hbar\). The frequency is the quotient of the speed of light \(c\) and the wavelength \(\lambda\). In silicon or germanium diodes, the wavelength corresponds to infrared radiation (heat). For Light Emitting Diodes (LEDs), the p- and n-type materials are chosen so that the energy is released as visible light.

$$\left.\begin{align}
E_g&=\hbar\ f\nonumber\\
f&=\frac{c}{\lambda}\nonumber
\end{align}\right\}
\ \Rightarrow\
\lambda=\frac{\hbar\ c}{E_g}$$

When we plot the current as a function of the bias voltage, we get the characteristic graph shown above. From the graph, we see that the diode has a very small leak current in reverse bias, and starts conducting once the forward bias surpasses the threshold voltage \(U_{th}\).

Diode with current limiting resistor

Using an AC signal generator and diode-resistor circuit, an x-y plot on an oscilloscope can visualize the characteristic graph. The voltage over the resistor is representative of the current through the diode.

Diode-resistor logic (DRL)

By combining diodes with resistors, we can create logic gates. In this, the diodes act as electrically operated switches. The following examples assume TTL levels, where an input value of 0 to 0.8 volt is recognized as a logic 0, and 2 to 5 volt is recognized as 1.

TTL voltage levels

OR Gate in DRL

If at least one of the inputs is a logic 1 (5 volt), the output will be a logic 1. Otherwise, the output will be a logic 0. In Boolean algebra that is written as \(X=A+B\).

OR gate in DLR

A logic OR-gate can be build using two diodes and a pull-down resistor as shown above. The 1N4148 is a common switching diode. If both inputs are logic 0, then the resistor will pull the output to ground (logic 0). If either input is a logic 1, the resistor limits the current through the diode. In that case, the output will be 5 volt minus the diode voltage drop; this is considered a logical 1.

In the simulation, click on an input on the left to toggle its state. The circuit is at rest when both inputs are Low (0 Volt). In this case, the resistor pulls the output down to 0 Volt. When either input is high, current flows through the diode and the resistor. The diode is in forward bias with a voltage drop of about 0.65 Volt. Consequently, the output will be 5 – 0.65 Volt, what is recognized as logic 1.

AND Gate in DRL

If both inputs are “1” (5 volt), the output will be 1. Otherwise, the output will be “0”. In Boolean algebra this is written as X = A · B.


(c) Copyright 2016, Coert Vonk
AND gate in DRL

A OR gate can be made as shown in the figure on the right. If both inputs are logic 0, current will flow through the diode, making the output equal to the diode voltage drop (0.65 volt), a logic 0. Otherwise, the resister will pull the output to 5 volt, a logical 1.

In the simulation, click on an input on the left to toggle its state. The circuit is at rest when both inputs are logic 1 (5 volt). In this case, the resistor pulls the output up to 5 volt. When either or both inputs are logic 0, current flows through the resistor and diode. The diode is in forward bias with a voltage drop of about 0.65 volt. Consequently, the output will be 0.65 volt above the input value of 0 volt, what is recognized as logic 0.

Combining gates in DRL

As we have seen, the output voltage levels of the single gates were a little off from the ideal levels of 0 and 5 volt. The circuit below cascades 2 OR gates with one AND gate to build the Boolean expression \(X=(A+B)\cdot(C+D)\).


(c) Copyright 2016, Coert Vonk
Double OR to AND gates in DRL

Simulating this circuit reveals a problem when the output should be 0. The circuit in effect acts as a voltage divider, where the current from the pull-up resistor splits over the two diodes and flows to ground over both pull-down resistors. Output voltage \(U_x\) follows from the current through the pull-up resistor \(I_{u}\):

$$\newcommand{\parallelsum}{\mathbin{\!/\mkern-5mu/\!}}
\left.
\begin{align}
I_{u} &= \frac{5 – 0.65}{10\mathrm k + 10\mathrm k \parallelsum 10\mathrm k} = \frac{4.35}{15\mathrm k} \nonumber\\
U_X&=5 – I_{u}\cdot 10\mathrm{k}\nonumber
\end{align}\right\}
\Rightarrow U_X = 5 – \frac{4.35}{15\cancel{\mathrm{k}}}\times10\cancel{\mathrm{k}}=2.1\ \mathrm V$$

Simulation confirms that combining the gates causes a problem where the output should be a logical 0 as shown below on the left. We can improve this specific circuit by increasing the pull-up resistor to \(470\ \mathrm{k\Omega}\). I will spare you the math, and simply hover over the \(X\) wire in the simulation to reveal the output voltage values . Now, all these levels are within the correct TTL range as shown below on the right.

Simulated results before
\(U_A\) \(U_B\) \(U_C\) \(U_D\) \(U_X\)
0 V 0 V 0 V 0 V 2.10 V
0 V 5 V 0 V 0 V 2.83 V
5 V 0 V 5 V 0 V 4.88 V
5 V 5 V 5 V 5 V 4.90 V
Simulated results after
\(U_A\) \(U_B\) \(U_C\) \(U_D\) \(U_X\)
0 V 0 V 0 V 0 V 0.60 V
0 V 5 V 0 V 0 V 0.67 V
5 V 0 V 5 V 0 V 4.79 V
5 V 5 V 5 V 5 V 4.81 V

The following chapter will introduce the transistor and how it can be used to build improved logic gates.When using resistor-diode logic, the voltage drop in the diodes and power dissipation in the resistors degrade the signal as it passes through the gates. As we will see on the next page, these problems solved by introducing another semiconductor: the transistors.

Embedded software developer
Passionately curious and stubbornly persistent. Enjoys to inspire and consult with others to exchange the poetry of logical ideas.

2 Replies to “How do computers do math?”

  1. Coert, I have tried to make a square root in excel but it would be work. The multiply and divide work in excel and the CSM works. I can not send you a picture of my work in this system. Can you help me?
    Ronald lokker from the Netherlands

  2. Thanks. I think the sqrt schematic might use the q* instead of the q to build the new subtrahend.
    [in parallel to email conversation]

Leave a Reply

Your email address will not be published. Required fields are marked *

 

This site uses Akismet to reduce spam. Learn how your comment data is processed.