logic

In this article, we will build logic circuits that implement math functions. It is part of a quest to answer the question “How do computers do math?”. This will section bring us the long awaited grail!\(\)

In combinational logic, the output is a function of the input values. There are a wide variety of logic gates our disposal to build these functions. Ever since the 80s, the leading logic families are the TTL-based 7400 and the CMOS-based 4000 series.

The figure below shows an example of a package with four two-input NAND gates.

Following sections discuss implementations of a multiplexer and some basic math operations.

Multiplexer (mx)

Albeit technically not a math function, we will cover the multiplexer because we will be needing it to build operations.

A multiplexer uses a binary value (address) to select between several inputs. The output then assumes the value of that input.

The table below gives the truth table for a 2-to-1 multiplexer. From this follows the boolean equation that expresses the output z as a function of the inputs. The illustration also shows the corresponding circuit, where the circle at the input of the top NAND-gate represents an inverter.

os	a	b	z
0	0	1	0
0	0	0	0
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

Animate

$$ z= \overline{os} \cdot a + os \cdot b \nonumber $$

We have now reached the the heart of the question “How do computers do Math?”. The first math operation that we will tackle using these gates is: addition.

Addition (fa)

The full adder forms the building block for all n-bit adders. This full adder adds the 1-bit values a and b to the incoming carry (c_i), and outputs a 1-bit sum (s) and a 1-bit outgoing carry (c_o). The carry is similar as when adding decimal numbers — if you have a carry from one column to the next, then that next column has to include that carry.

The truth table, shown below, gives the relation between these inputs and outputs. The Boolean equations and circuit are derived from this table.

a	b	ci	co	s
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

Animate

$$ \begin{aligned} s &= a \oplus b \oplus c_i\\ c_o &= a \cdot b + c_i \cdot (a \oplus b) \end{aligned} \nonumber $$

Now that we can add 1-bit values, we can move on to n-bit values. The basic carry-propagate adder starts by adding the least significant bit and passing the carry on to each following bit. The s outputs are combined to form the sum S.

Expanding

The circuit shown below gives an example of a 4-bit carry-propagate adder. The carry has to propagate from the lowest to the highest bit position. This so-called “ripple carry” limits the speed of the circuit.

Animate

The accompanying article “Building Math Circuits” describes Verilog HDL implementations of this along with a faster algorithms, and a demonstration setup.

Subtraction (fs)

Before we can look at subtraction, we need to be able to represent negative numbers. Referring back to the section on digital systems, the positive decimal value would be represented by the binary value 111 as shown below. $$ \require{color} 7 \equiv \color{red}{1}\color{black}{\times 2^2}\ +\ \color{red}{1}\color{black}{\times 2^1}\ +\ \color{red}{1}\color{black}{\times 2^0} = \mathrm{b}\color{red}{111} \nonumber $$

The most common digital representation for negative numbers is called “two’s complement”. It assigns the most significant bit (msb) a negative weight. The other bits have their usual binary weights. The advantage of this system is that the circuits can treat positive and negative numbers the same when doing arithmetic. The 4-bit two’s complement for decimal value -7 is 1001 is shown below. $$ \require{color} -7 \equiv \color{red}{1}\color{black}{\times (-2^3)}\ +\ \color{red}{0}\color{black}{\times 2^2}\ +\ \color{red}{0}\color{black}{\times 2^1}\ +\ \color{red}{1}\color{black}{\times 2^0} = \mathrm{b}\color{red}{1001} \nonumber $$

Inverting the bits of a binary number and adding 1 makes the number negative. This implies that positive numbers have the value 0 as their most significant bit, and negative numbers have the value 1 as their most-significant bit. $$ \require{color} \color{red}-\color{black}7 \equiv \,^{\color{red}\sim}\mathrm{b}0111\color{red}\color{red}{+\mathrm{b}1}\color{black} =\mathrm{b}1000 + \mathrm{b}0001 = \mathrm{b}1001 \nonumber $$

This implies that using 8-bits, we can encode the decimal values -128 to 127.

Similar to addition, the simplest subtraction method is borrow propagation. Again, we will start by building a 1-bit subtractor. The inputs a and b represent the 1-bit binary numbers being added. Output d, the difference. b_i and b_o are the incoming and outgoing borrow signals.

The truth table shown below gives the relation between the inputs and outputs. The outputs d and b_o can both be expressed as a function of the inputs. The result d is an exclusive-or (XOR) function, just as the sum was for addition.

a	b	li	lo	d
0	0	0	0	0
0	0	1	1	1
0	1	0	1	1
0	1	1	1	0
1	0	0	0	1
1	0	1	0	0
1	1	0	0	0
1	1	1	1	1

Animate

$$ \begin{align*} d&=a \oplus b \oplus l_i \\ l_o&=\overline{a} \cdot b + l_i \cdot (\overline{a \oplus b}) \end{align*} $$

To build a 4-bit subtractor we combine four of these building blocks.

Animate

For a faster approach or a Verilog implementation of the subtractor shown above, refer to Building Math Circuits.

Multiplication (ma)

Multiplication is another important operation in digital signal processing (e.g. fast Fourier Transfers). It is an excellent example of combining simple logic functions to make a much more complex function. The two methods that allow us to do this called “array multipliers”.

The array multiplier is a simple technique for implementing multiplication. It resembles the process how you would probably perform a multiplication yourself, aside from the fact that it sums up the partial products as it goes.

Each partial product bit position can be generated by a simple AND gate between corresponding positions of the multiplicand A and multiplier B bits. Adding the partial products forms the product.

The multiplier adder (ma) shown below, is the basic building block for the multiplier. It uses an AND gate to form the partial product of two binary digits. To calculate the partial sum and carry out signals, it reuses the 1-bit full adders described earlier. The boolean equations describe the multiplier adder (ma) as a function of its ports:

x	y	si	ci	b	co	so
0	0	0	0	0	0	0
0	0	0	1	0	0	1
0	0	1	0	0	0	1
0	0	1	1	0	1	0
0	1	0	0	0	0	0
0	1	0	1	0	0	1
0	1	1	0	0	0	1
0	1	1	1	0	1	0
1	0	0	0	0	0	0
1	0	0	1	0	0	1
1	0	1	0	0	0	1
1	0	1	1	0	1	0
1	1	0	0	1	0	1
1	1	0	1	1	1	1
1	1	1	0	1	1	0
1	1	1	1	1	1	0

Animate

$$ \begin{align*} b &= x \cdot y\\ s_o &= s_i\oplus b\oplus c_i\\ c_o &= s_i \cdot b + c_i \cdot(s_i \oplus b) \end{align*} $$

The carry propagation array multiplier works similarly to the way humans multiply. The maij building blocks connect in a grid, where ij identifies the row and column. The figure below gives an example of a 4-bit multiplier.

Animate

You might notice some redundancy in the top row, where ma0x merely function as AND gates.

This method will provide the expected result, but it will take a relatively long time to do so because of the long carry chain. A more optimized method is the carry-save array multiplier described below.

Implementations of this and faster multipliers in Verilog HDL can be found in the accompanying articles Building Math Circuits.

Division (csm)

Division is another example of combining simple logic function to make a more complex circuit. Note that the method shown below ignores the divide-by-0 condition. (See also Multipliers and dividers.)

Next we’ll introduce the most basic division method called attempt subtraction divider. In calculating x/y, it repeatedly subtracts the divisor y⋅os* from the digits of the dividend x. Initially the value of os equals logic 0, so that it subtracts the value y. If the difference is negative, the subtraction is cancelled by making os logic 1. Together, all the successive OS‘s together makes the division result, while the remainder is the difference of last subtraction step.

To implement this algorithm, we need subtractors that can cancel the subtraction. Each subtractor calculates the difference between two input numbers, but if the result is negative, the operation is canceled and replaced with a subtraction of zero.

Such a Controlled Subtract-Multiplex (CSM) contains a 1-bit subtractor a-b with the usual inputs a, b, and b_i and outputs d and b_o. The output select (os) signal selects between bit x and d=a-b. The signal is connected to the borrow output of the most significant 1-bit subtractor.

• 0, means subtraction result was positive ⇒ D’ = D.
• 1, means subtraction result was negative ⇒ D’ = X.

Inside each divider cell the os controls a multiplexer that selects between the result of the addition d and the original remainder x. The boolean expressions express the output as a function of the inputs. (Click image to animate)

os	x	y	bi	bo	d
0	0	0	0	0	0
0	0	0	1	1	1
0	0	1	0	1	1
0	0	1	1	1	0
0	1	0	0	0	1
0	1	0	1	0	0
0	1	1	0	0	0
0	1	1	1	1	1
1	0	0	0	0	0
1	0	0	1	1	0
1	0	1	0	1	0
1	0	1	1	1	0
1	1	0	0	0	1
1	1	0	1	0	1
1	1	1	0	0	1
1	1	1	1	1	1

Animate

$$ \begin{align*} d^\prime &=x \oplus y \oplus b_i\\ d&=os \cdot x + \overline{os} \cdot d^\prime\\ b_o&=\overline{x} \cdot y + b_i \cdot (\overline{x \oplus y}) \end{align*} $$

The circuit shown below implements a complete 8:4-bit divider matrix using CSM modules. Each row performs one “attempt subtraction” cycle. Note that the most significant bit is used to drive the os inputs. (For details see “Combinational arithmetic“.)

Animate

For a faster approach or a Verilog implementation of above divider, refer to Building Math Circuits.

Square root

The square root operation is an interesting algorithm to implement in hardware. Its implementation is another example of combining simple logic functions, reusing previous designs.

Samavi and Sutikno improved the classical non-restoring digit recurrence square root algorithm. This example uses their algorithm but without the optimizations. The algorithm of this Simplified-Samovi Square root is:

1. Add the next bit from the input number to the right of the current remainder. This becomes the new current remainder (A)
2. Take the square root obtained so far, append 01 to it and subtracts this, properly shifted, from the current remainder. (The 0 in 01 corresponds to multiplying by 2; the 1 is a new guess bit.)
3. If the result is
   • Positive, then the new root bit is 1, and the result becomes the new remainder.
   • Negative, then the current remainder (A) will become the new remainder (as if the subtraction never happened).

The circuit shown below implements a complete 8-bit square root circuit. Each row performs one “attempt subtraction” cycle. Like in the division circuit, the most significant bit is used to drive the os inputs.

Animate

For a Verilog implementation of above square root algorithm, refer to Building Math Circuits.

I hope the this answered the question “How do computers do math?“. The easy answer would be “because the physics make it”, just like a ball rolling down a hill. I hope you enjoyed our much longer journey into this exciting field!

This article describes the physics of Metal Oxide Silicon Field-effect Transistors (MOSFET). It uses these MSOFETs to build logic gates. This is part in a quest to answer the question “How do computers do math?”.\(\)

At first glance, the construction of the MOSFET might appear similar to the JET. However, there are some important differences: (1) a thin layer of silicon dioxide (SiO₂) isolates the gate, and (2) they have no obvious conductive channel.

The illustration below shows symbols for, and examples of, MOSFETs.

Semiconductor physics

In the n-channel MOSFET, a p-type substrate connects to the source and drain pins via more heavily doped n⁺ type regions, as shown below. A very thin layer of silicon dioxide insulates the metal gate terminal from the substrate. A bias over the drain-source terminals causes the depletion layer around the drain to widen. The depletion areas prevent a drain current.

Applying a gate potential \(U_{gs}\) makes the gate positive with respect to the source and substrate, as shown below. The positive charge on the gate repels holes from the p-layer underneath, forming a depletion area. This charge also attracts free electrons from the n⁺ source and drain that form a thin layer under the gate terminal bridging the source and drain areas. This layer is called an inversion channel because it behaves like a n-type material. The inversion channel is of the same type as the source and drain, and thus it provides a channel through which current can pass.

Any further increase of the gate voltage attracts more electrons into the inversion channel, reducing its resistance and increaing the current between the source and drain. Removing the gate source voltage stops the current leading and the area beneath the gate to revert to p-type. This method of operation is called enhanced mode, because the gate potential “enhances” the conducting channel. There are also devices where a gate potential “depletes” the conducting channel.

Due to the physics of MOSFET, these transistors draw very little power because the gate current is extremely low; they’re as small as 7 nanometers, the width of 10 silicon atoms; and can switch on/off in the order of GHz. This makes them an ideal building block modern day computers that use integrated circuits with trillions of MOSFETs on one piece of silicon.

MOSFET based logic

A voltage input to the gate controls the flow of current from source to drain. Being voltage-controlled rather than current-controlled, it allows for resistor-less circuits. CMOS draws no current other than leakage when in a steady 1 or 0 state. When the gate switches states, it draws current to charge the capacitance at the gate.

To implement logic functions, a complementary pair of MOSFETs can connect an output to either V_cc or ground. The name Complementary Metal Oxide Semiconductor (CMOS) refers to the use of complementary pairs of p-type and n-type MOSFETs. Note that the CMOS voltage levels are 0 volt and 3.3 volts.

NOT gate in CMOS

The circuit shown below gives the most basic implementation of a CMOS gate, where the FETs are used invert a logical input signal.

When a 3.3 volts signal (logic 1) is applied at input \(A\), the n-channel MOSFET is conducting, and the p-channel MOSFET is not, and the output \(X\) is a logic 0. On the other hand, if the input is grounded (logic 0) the situation is reversed, and the output \(X\) is a logic 1. A simulation confirms that the output values stay well within the CMOS range.

By extending this NOT gate, we can build NOR and NAND gates.

NOR gate in CMOS

Putting two n-channel MOSFETs in parallel and two p-channel MOSFETs in series, we can create a two-input NOR gate as shown in the circuit below. A simulation confirms that these output values stay perfectly within CMOS range.

Simulation results

\(U_A\)	\(U_B\)	\(U_X\)
0.00 V	0.00 V	3.30 V
0.00 V	3.30 V	0.00 V
3.30 V	0.00 V	0.00 V
3.30 V	3.30 V	0.00 V

NAND gate in CMOS

By putting two n-channel MOSFETs in series and two p-channel MOSFETs in parallel, we can build a two-input NAND gate as shown in the circuit below. Once more, simulation confirms that the output values are at CMOS values.

Simulation results

\(U_A\)	\(U_B\)	\(U_X\)
0.00 V	0.00 V	3.30 V
0.00 V	3.30 V	3.30 V
3.30 V	0.00 V	3.30 V
3.30 V	3.30 V	0.00 V

This post describes the semiconductor physics of the Field Effect Transistors (FET). It uses the FET to build logic gates. This is part of a quest to answer the question “How do computers do math?”. Here we introduce an improved transistor type. \(\)

The Field Effect Transistor (FET) can be used as a voltage-controlled resistor.

Lilienfeld and Heil discovered the principle of field-effect as early as 1926-1927 [patent], but it took until well after the invention of the bipolar junction transistor before it became practical to make them (Atalla, 1960). Even though FETs are conceptually simple, they are difficult to manufacture because they require an extremely clean manufacturing environment.

The illustration below shows the symbols for the JFETs.

Semiconductor physics

In the n-channel device, the channel is in between two connected p-type regions, as shown in the illustration below. More heavily doped n⁺ type regions connect the source and drain pins to the n-type channel. This n⁺ type silicon prevents an unwanted pn-junction between the regular n-type silicon with its four valence electrons and the e.g. aluminum terminal with its three valence electrons.

When we place a modest voltage \(U_{ds}\) over the drain and source, the ions at the depletion layers give the channel a positive charge compared to the gate. The depletion layer is thicker towards the drain end of the channel, as the voltage on the drain is more positive than that on the source due to voltage gradient that exists along the channel. The current flows and the silicon channel acts similarty to a conductor.

To use this JFET as a switch, we can increase the thickness of the depletion zone by applying a reverse bias on the gate, as shown below. This pushes the holes from the p-type region and the electrons in the n-type region away from the junction, increasing the width of the depletion zone. Eventually, once enough potential is applied, the transistor will pinch off the channel current (\(I_d\)). This pinch off voltage is typically a negative few volts.

To use this JFET as an amplifier, we can increase \(U_{ds}\) while \(U_{gs}=0\). At first, the drain current \(I_d\) will increase, but meanwhile the depletion layer is also growing and narrowing the n-channel. At the so called “pinch-off” value \(U_{p}\), the conducting channel is so narrow that it cancels out the effect of the higher \(U_{ds}\). The \(I_d\) doesn’t increase much further, and the JFET is said to be in saturation mode. At this point, a small \(U_{gs}\) can be used to control the current through the source−drain channel from its maximum value to zero. [learn-electronics]

JFET based logic

JFETs have very nice properties, but when used in circuits they still require bulky resistors. As we see in the next section, MOSFETs do not require such resistors.

This post describes the physics of Bipolar Junction Transistors (BJT), and uses these to build logic gates. This is part of a quest to answer “How do computers do math?”.

If you are pressed for time, overwhelmed by the semiconductor physics, or simply to curious to find the answer to the inquiry, you may skip forward to Math operations using combinational logic. However, if you are somebody who likes to know it all, I encourage you to work through this chapter. \(\)

Bardeen, Brattain and Shockley invented the transistor in 1947. They greatly reduce energy consumption, weight and footprint compared to the existing vacuum tubes. This enabled groundbreaking new developments such as landing a man on the moon. The illustration below shows the symbols for bipolar junction transistors (BJT, along with some examples of them.

In this context, the term “bipolar” refers to the two charge carriers: electrons and holes in the same crystal. The model of the Bipolar Junction Transistor is a “voltage controlled current device”, even though for small signals we typically model it as a current amplifier. We will explain this by exploring the BJT semiconductor physics of a NPN-junction.

Semiconductor physics

Joining three layers of semiconductor material creates a transistor. There are two types of bipolar junction transistors. The PNP transistor has a very thin n-type layer between p⁺ and p-type material. In this the ⁺ sign indicates more heavily doped material. The other type of transistor, the NPN transistor, has a very thin p-type layer between n and n⁺ type materials as shown in the image below.

The physics of both types of transistor are very similar, except that the electron flow is dominant in NPN transistors, while PNP transistors rely mostly on the flow of “holes”. NPN transistors are more popular, because electrons move faster than “holes”. In this discussion, we will focus on the NPN transistor.

When a NPN transistor has no bias (voltage), the base-emitter and base-collector junctions behave like diode junctions as shown in the image below. That means we can apply what we learned in the previous chapter. At both junctions, the electrons from the n-type material and the holes from the p-type attract and recombine leaving positive and negative ions behind. This continues until the electrons and holes no longer have enough energy to overcome the electrostatic field created by the ions, about 0.65 volts. The resulting depletion area acts as an insulator.

When we apply a forward bias on the base-emitter junction, as shown below on the left, it pulls the holes in the p-type region to the electrons on the - terminal of the battery, and the electrons in the n-region to the + terminal. With both the electrons and holes pulled towards the junction, the depletion layer becomes very thin. Once enough voltage is applied, the base-emitter junction starts conducting and electrons and holes flow freely. The result is a small flow of holes from the base to the emitter, and electrons from the opposite direction. Together these flows are called the base current \((I_b)\).

When we also apply a strong reverse bias on the collector-base junction, the free electrons and holes pull away from the junction and the depletion layer widens as shown in the bottom-right image. The magic lays in the extremely thin depletion layer between the base and emitter and the strong charge on the collector.

Once the electrons “emitted” by the emitter reach the very narrow base region, the strong electric field from the collector attracts them. The electrons will cross the reverse biased collector-base junction to be “collected” by the collector. The result is a net flow of electrons from the collector to the emitter, or in other words: an electrical current from the collector to the emitter (\(I_c\)). This current is substantially larger than the current (\(I_b\)) that reduced the width of the base-emitter depletion zone. In other words, the small base current (\(I_b\)) controls the much larger collector current (\(I_c\)).

Note that even though the base-emitter threshold voltage is 0.65 volts, the collector-emitter drop will be much lower, in the order of a few millivolts. This is because the electric field over the collector-base junction is opposite to that of the base-emitter junction.

Transistor based logic

The problem with diode-resistor circuits was the signal degradation which kept them from being cascaded. RTL replaces the diode switch with a transistor switch. The transistor ensures that the output voltage will always be a valid logic level, so they can be cascaded indefinitely.

Resistor-transistor logic (RTL)

Transistors can be used to amplify signals, but in this context we are only interested in using them as on/off switches. This implies that we apply no base-emitter bias, or apply enough bias to make the collector-emitter conduct.

NOT Gate in RTL

The circuit shown below gives the most basic implementation of a BJT gate, where the transistor is used to invert a logical input signal.

When a 5 volts signal (logic 1) is applied at input \(A\), the base-emitter junction is forward biased, resulting in maximum collector current and a minimum collector-emitter voltage drop. The transistor is switched “on”, and the output \(X\) is a logic 0. On the other hand, if the input is grounded (logic 0), the base current (\(I_b\)) is zero, and there will be no collector-emitter current. With the transistor switched “off”, the resistor pulls the output signal up to 5 volts, a logic 1.

A simulation confirms that the output values stay well within the TTL range. The circuit is at rest when the inputs is logic 0 (0 V). In this case, the resistor pulls the output up to 5 volts. An input value of logic 1 turns the transistor “on” so that current flows through the resistor and into the connector-emitter.

This implies that the transistor inverts the input signal, while ensuring that the output voltage is a valid TTL level. By extending this NOT gate, we can build other logic gates.

NOR Gate in RTL

Putting two NOT gates in parallel, creates a two-input NOR gate as shown in the circuit below. A simulation confirms that the output values stay within the TTL range. The circuit is at rest when both inputs are logic 0 (0 volts). In this case, the resistor pulls the output up to 5 volts. When either input is logic 1, the corresponding transistor turns “on” so that current flows through the resistor and connector-emitter.

Voltages

\(U_A\)	\(U_B\)	\(U_X\)
0.00 V	0.00 V	5.00 V
0.00 V	5.00 V	0.06 V
5.00 V	0.00 V	0.06 V
5.00 V	5.00 V	0.04 V

NAND Gate in RTL

Putting two NOT gates in series creates a two-input NAND gate as shown in the circuit below. The simulation confirms that the output values stay within TTL range. The circuit is at rest when at least one input inputs is logic 0 (0 V). In this case, the resistor pulls the output up to 5 volts. When both inputs are logic 1, the corresponding transistors turn “on” so that current flows through resistor and connector-emitter, driving the output to logic 0.

voltages

\(U_A\)	\(U_B\)	\(U_X\)
0.00 V	0.00 V	5.00 V
0.00 V	5.00 V	5.00 V
5.00 V	0.00 V	5.00 V
5.00 V	5.00 V	0.12 V

Limitations of RTL

The RTL gates have two limitations: (1) the input resister and \(C_{be}\) create a RC time that slows down state transitions, and (2) the input resistor take up a significant footprint in an integrated circuit. We will address the first limitation by replacing the input resistor with diodes. The next page tackles the second limitation.

Diode-transistor logic (DTL)

The switching speed of the NOT gate can be improved by replacing the input resistor with two diodes and a resistor as shown in the circuit below. Diodes are not only smaller but also have a low internal resistance when forward biased, thus allowing faster switching. The diode connected to the transistor base raises the input voltage required to turn the transistor “on” to about 1.3 volts.

voltages

\(U_A\)	\(U_X\)
0.00 V	5.00 V
5.00 V	0.04 V

The simulation results are noted in the table on the right. Similar to the resistor-transistor logic, by adding input diodes, we can build an NAND gate, and by placing the inverter in parallel we can make a NOR gate.

Transistor-transistor logic (TTL)

In the DTL gate, there are two diodes have their P-type anodes connected together and to the pull-up resistor. A single NPN transistor can replace these two diodes while taking up about the same amount of space. The figure below shows a NOT gate build using TTL logic. The simulation results are noted in the table on the right.

voltages

\(U_A\)	\(U_X\)
0.00 V	5.00 V
5.00 V	0.02 V

This post gives an introduction to digital logic, dives into the semiconductor physics and finishes with an implementation in diode-resistor logic. It forms part of the quest to answer How do computers do math?.\(\)

Logic gates

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.

OR gate

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\).

\(A\)	\(B\)	\(A+B\)
0	0	0
0	1	1
1	0	1
1	1	1

AND gate

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

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

XOR gate

The eXclusive OR gate (XOR) is represented by the symbol \(\oplus\).

\(A\)	\(B\)	\(A \oplus B\)
0	0	0
0	1	1
1	0	1
1	1	0

NOT gate

The inverter gate (NOT) represented by a bar above as in \(\overline{A}\).

\(A\)	\(\overline A\)
0	1
1	0

NOR and NAND gate

At times, an OR gate is combined with an inverter to form Not-OR, or NOR for short. The table below shows this gate and its truth tables.

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

Other times, an AND gate is combined with an inverter to form to form Not-AND, or NAND for short.

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

Semiconductor physics

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 built a vacuum tube based system to simulate the hydrogen bomb. Currently, digital systems are built using the semiconductors we will discuss here.

Have you ever wondered about the jagged 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 creating the zigzag line share some properties of both conductors and insulators. These elements are called semiconductors or metalloids.

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

Pure silicon

Silicon is a a common semiconductor material. It has four electrons in the outer shell (valence shell). This causes it to form covalent bond with four neighboring atoms so that in its valence shell all eight electrons are present (as shown in the illustration below). These bonds hold the atoms together, making the element stable.

The bonds help form an orderly crystaline structure called a lattice. Because there are no free electrons, the material will not conduct electricity. The illustration above shows a simplified view of the lattice. The conductivity of the lattrice can be increased by adding very a small number (<1 ppm) of impurities. Examples of such impurities are phosphorous and boron.

N-type silicon

Adding a tiny amount of phosphorous, which has five electrons in valence band, leaves an extra electron that can move easily. Four out of the five phosehorus’ valence electrons bond with their neighboring silicon atoms. This leaves one free electron that becomes mobile.

The resulting material is called an n-type because of the abundance of negatively charged electrons.

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

P-type silicon

Boron has only three electrons in its valence band. Add a tiny amount of it to silicon only allows for the formation of 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 called 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-type 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 from the covalent bonds, 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 in a process called recombination. Because of the 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, creating an electrostatic field across the junction.

This continues until the electric field from the negatively charged ions in the p-type material gets 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, an equilibrium is established. 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 measures 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 the 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.

The symbol and some samples of diodes are shown 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 - terminal. With both charge carriers pulled away from the junction, the depletion layer widensm 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 volts for silicon diodes.

With the two opposite flow of electrons and holes, some will eventually recombine. An electron will fall from a higher energy level to a the lower energy level of the hole. This leads to energy beging 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.

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}\).

Using an AC signal generator and diode-resistor circuit, an xy-plot on an oscilloscope can visualize this. 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 these, the diodes act as electrically operated switches. The following examples assume TTL levels, where an input value of 0 to 0.8 volts is recognized as a logic 0, and 2 to 5 volts is recognized as 1.

OR Gate in DRL

If at least one of the inputs is a logic 1 (5 V), 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\).

A logic OR-gate can be built 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 volts 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 V). In this case, the resistor pulls the output down to 0 volts. When either input level is high, current flows through the diode and the resistor. The diode is in forward bias with a voltage drop of about 0.65 volts. Consequently, the output will be 5 – 0.65 volts, which is recognized as logic 1.

AND Gate in DRL

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

A OR gate can be made as shown in the schematic above. If both inputs are logic 0, current will flow through the diode, making the output equal to the diode voltage drop (0.65 V), a logic 0. Otherwise, the resister will pull the output to 5 volts, 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 V). In this case, the resistor pulls the output up to 5 volts. 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 volts. Consequently, the output will be 0.65 volts above the input value of 0 volts, 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 volts. The circuit below cascades 2 OR gates with one AND gate to build the Boolean expression \(X=(A+B)\cdot(C+D)\).

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}\):

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.

In electronic circuits, an electric signal controls the flow of current. We introduces analog, digital and microprocessor systems. This is part 2 in a quest to answer the question “How do computers do math?”. In this chapter we introduce the different types of electronic circuits.\(\)

In electronic circuits, another electric signal controls the flow of electrons. This electrical input signal typically represents physical properties such as sound, vision or temperature. Converting these physical properties to electrical signals, allows them to be easily manipulated and transported.

We distinguish three types of electronic systems: analog, digital and microprocessor systems.

Analog systems

In analog systems, a continuously variable voltage on a wire has a proportional relationship to a physical property as illustrated on the right. The word “analog” comes from the Greek word ανάλογος (analogos) meaning “proportional”. For example, a voltage of -1 to 1 volt may represent a sound pressure of -15 to 0 dB_a.

In an old fashion telephone, a battery provides the energy. The carbon powder in the microphone controls the current, as the vibrations from the voice causes the resistance to fluctuate. Copper wires transport the analog signal. Eventually, on the other end, a loudspeaker recreates the sound.

Analog systems consist of components such as batteries, resistors, capacitors, diodes and transistors. They first became viable with the introduction of the vacuum tube (Fleming, 1904; de Forest, 1907) and later the semiconductor diode (Ohl, 1939) and transistor (Bardeen, Brattain and Shockley, 1947).

If you interested in the history, consider watching the PBS documentary Transistorized! (the original video vanished, but it can still be found on YouTube) or the Silicon Valley American Experience.

The thermal behavior of the components and the transmission of the analog signal introduce noise. Reducing noise and thereby improving accuracy is complicated and expensive in analog systems. The inherent inaccuracy was acceptable for telephony, but not for precision tools such as calculators. As we will see next, digital systems can offer this precision.

Digital systems

In digital systems, there are only two voltages. One voltage corresponds to a logic 1, and the other to logic 0. These systems are binary after the Latin word bīnārius that stands for “consisting of twos”. Digital systems consist of circuits build using digital gates. Internally the gates use analog components, but the input and output are digital, so only logic 1 and logic 0.

Digital systems became viable with the introduction of the transistor. Later with the invention of integrated circuits, digital systems became commonplace (Kilby and Noyce, 1959).

By combining a set of \(n\) wires and assigning them weighted values, we can transmit \(2^n\) binary values. In the above example with four wires, a mass from 0 to 100 kg may be represented by a 4-bit binary signal from 0000 to 1111. That implies that 16 different values can be transmitted, decimal 0 to 15.\(\)

All voltages within a range represent the same digital value. As shown in the figure above, TTL-based logic recognizes an input value of 0 … 0.8 volt as logic 0, while 2 … 5 volt is recognized as logic 1. This implies that small changes in analog signal levels (noise) will be ignored allowing transmission over long distances without noise degradation.

The number of bits used limits the precision of digital systems. Digital systems can be very precise, but have to be custom designed for each task. During World War II, the Nazis and allied forces, used electro-mechanical systems and later vacuum tube based calculators to calculate artillery-firing tables. These systems were fast, but it took great effort to re-purpose the machines. Microprocessor systems add flexibility to digital systems.

Microprocessor systems

Since 1945, the von Neumann architecture forms the foundation for modern day computers. It allows the same device to perform a wide variety of functions. One moment it can be a scientific calculator, another a magazine reader of be used to call your cousin.

A programmable device takes digital input signals, processes them according to instructions stored in its memory and outputs results. The programmable device is a Central Processing Unit (CPU).

Build using digital gates, microprocessors came to life with the invention of integrated circuits and spread rapidly once the whole CPU fit on one piece of silicon (Intel and Texas Instruments, 1971). This architecture is described in more detail in our follow-up inquiry “How do Microprocessors Work?.

Before we can answer the question “How do computers do math?“, we need to get our toes wet with a short introduction to electrical circuits. What are the electrical properties and what does Ohm’s law have to do with it?\(\)

Turbulence in thunderclouds builds up static electricity because of the friction between water droplets. Your physics teacher might run a van der Graaff generator causing her hair to stand up, or you can simply rub a balloon over your sweater (demo). Objects that rub against each other create static charge. This charge caused by an excess or lack of electrons. The electrons can be easily transferred by rubbing objects, because they only have a loose bond with their atomic nucleus (protons and neutrons).

Static electricity may suddenly discharge, such as when a bolt of lightning flashes through the sky. Other times, objects with opposite charges attract like when a balloon clings to a sweater. In between these two extremes are experiments with a modest flow of electrons, such as the van der Graaff generator discharging through a fluorescent light tube.

Electrical charge is expressed in Coulomb and corresponds to a charge of \(-6.24151\times 10^{18}\) electrons. Electric current is the movement of charge (electrons). Your light bulb, computer and phone all harness the movement of electrons.

Current

Electric current flows when there is a closed loop, a circuit, around which electrons flow. For example, in a flashlight, once you close the switch the current flows from the battery through the bulb, wires, switch and back through the battery. The current through the thin wire of the light bulb causes it to heat and light up. When you open the switch, it breaks the current and the light turns off.

The illustration above visualizes an electron traversing a wire from atom to atom. In real life, the scale if very different. The atoms are so small that they are invisible to the naked eye. To get an idea of the scale, imagine a current of about 1,000,000,000,000,000,000 electrons per second to power a light bulb.

Current is the movement of charge, with a unit of 1 Ampere corresponding to moving a charge of one Coulomb a second.

The unit name for current “ampere” is in remembrance of André-Marie Ampère, a French physicist and mathematician and early pioneer of electromagnetism. He introduced the symbol \(I\) from the French term “intensité de courant”. Electrical current is the flow of positive charge opposite to the movement of electrons. This is an historic artifact because he discovered current 60 years before the discovery of the electron.

Analogy

Let us take a step back and compare the electrical current to a water system as shown below. When you open the valve in the pipe, water starts flowing down the pipe, similar to closing the switch in flashlight.

The amount of water flow depends on the pipe diameter and the height difference of the water. Similarly, in the flashlight the current depends on the voltage of the battery and the resistance of the light bulb.

Voltage

In the water model above, the voltage compares to the difference in water level. Voltage is the difference in charge between two points. For example, in the flashlight that is between the \(+\) and \(-\) terminals of the batteries. Instead of charge, people also use the term electric potential, the amount of force available to move electrons from one specific point in a circuit to another point.

The unit “volt” honors of the Italian physicist Alessandro Volta, who discovered the first chemical battery. The symbol for voltage depends on your location. Europe uses symbol \(U\) and the US uses the symbol \(V\). In either case, the unit Volt (\(V\)) is defined as the electric potential over a wire when an electric current of 1 Ampere dissipates 1 Joule of energy.

Resistance

The third electric property is resistance, a material’s tendency to resist the flow of charge (current). Free electrons move through a conductor with some degree of friction or resistance to motion.

A thin carbon wire has a high resistance, and a thick copper wire has a low resistance. In the water analogy, it compares with the narrowness of the water pipe. The narrower the pipe, the smaller the flow of water.

The symbol for resistance is \(R\). Resistance is measured in the unit Ohm (\(\Omega\)) after the German physicist Georg Ohm.

Ohm’s law

Ohm’s law describes the relationship between voltage, current and resistance. The amount of current is proportional with the voltage that motivates the electrons to move, and inversely proportional to the resistance that oppose the flow of electrons. Georg Ohm formulated this relationship as:

The illustration below shows the circuit and the popular Ohm’s law triangle. Here \(U\) represents the voltage [Volt], \(I\) the current [A] and \(R\) the resistance in Ohms [Ω].

Using Ohm’s law, we can determine the voltage, current or resistance if the other two properties are known. For example, if we have a circuit with the potential of 12 Volt, a resistance of 120 Ω, then the current follows as $$ \frac{12\ \mathrm{V}}{120\ \Omega}=0.1\ \mathrm{A} \nonumber $$

Another example is a 9 volt battery powering a light emitting diode in series with a resistor. If we want a current of 10 mA, and at that current, the LED has a potential drop of 2.2 volts then we can calculate the required current limiting resistor value as $$ \def\e#1{\times 10^{#1}} \def\num#1{\numx#1}\def\numx#1e#2{{#1}\mathrm{e}{#2}} R=\frac{U_{bat}-U_{led}}{I}=\frac{9 – 2.2}{10\e{-3}}=680\ \Omega\nonumber $$