http://www.coertvonk.com/family/school/digital-logic-4245

How do computers do math?

This inquiry answers the question “How do computers do math?”. After a short introduction, it dives down into solid-state chemistry from where it emerges to traverse along Ohm’s law, semi-conductors, logic gates and combinational logic. It surfaces by building a simple arithmetic logic unit.

Tools used

Basic analog and digital simulation, Yenka Technology, Crocodile Clips (free outside of school hours)
Analog and digital experiment kit, Electronics learning lab (man), RadioShack ($70)
Advanced analog simulation, OrCAD A/D, Cadence (free Lite version)
Advanced digital simulation and synthesis, ISE WebPack, Xilinx (free WebPack version), or
Advanced digital simulation and synthesis, Quartus II including ModelSim, Altera (free Web version)

Electrical circuits

An electric circuit contains a conductive path that allows free electrons to move through it. Quantities associated with electricity are:
- Current, measure the flow of electrons (fined as a moving positive charge).
  - symbol is I
  - unit is Ampere (A)
  - compares to the flow of water through a hollow pipe. The water flows from high to low pressure.
  - 1 ampere is defined as the current through two 1 meter long parallel conductors placed 1 meter apart, that produces an electromagnetic force of 0.2 × 10^–6 newton. [SI §2.1.1.4]
  - [A = C/s], where coulomb (C) is the electrical charge in approx 6.24151×10¹⁸ electrons.
- Voltage, expresses the difference in electric potential. Potential refers to the amount of force available to move electrons from one specific point in a circuit to another point.
  - symbol U (IEC) or V (IEEE)
  - unit is Volt (V)
  - compares to water pressure.
  - [V = W/A], the voltage when a 1A current dissipates 1W of power [W = J/s]
- Resistance, measures the opposition to current flow.
  - symbol R
  - unit is Ohm (Ω)
  - compares to pipe diameter, or friction in a mechanical system
  - Free electrons move through conductors with some degree of friction, or resistance to motion. Resistance can best be explained by considering electrons as being electromagnetic waves that oscillate through a crystal like structure (lattice). Irregularities in the lattice (due to impurities) and vibration (due to heat) cause interference between the waves and the periodicity of the lattice.
  - [Ω= V/A]
    :
Ohm’s law: U = I × R
- The amount of current is:
  - I∝U, proportional voltage (U) available to motivate the electrons to move, and
  - I∝1/R, inversely proportional to resistance (R) that oppose the flow of electrons.
    :
Lab work
- Apply different voltages over a resistor, and note the effect on the current by:
  - simulate using Yenka Ohm’s law.
- In a battery-resistor circuit, with U=9V and R=10kΩ, determine the current by:
  - calculating using Ohm’s law, or
  - simulating using Yenka or OrCAD/PSpice (bias analysis displaying voltages and currents), or
  - building it using electronics learning lab.
- In a battery-and-two-series-resistors circuit, with U=9V, R₁=1kΩ and R₂=10kΩ, determine current and derive the voltages over the resistors (U₁ and U₂), by
  - calculating using Ohm’s law, or
  - simulation using Yenka or OrCAD/PSpice, or
  - building it using electronics learning lab, measure voltages and current.

Electronic circuits

Definition
- In electronic circuits the flow of electrons is controlled by another electrical signal.
- Electrical signals can be used to represent physical properties such as pressure, luminance and temperature. Examples of input devices are microphones, solar cells and temperature sensors.
- Electrical signals can be easily manipulated and converted back to a physical property. Examples of output devices are loudspeakers, light bulbs and heating elements.
  :
Types of electronic circuits:
- In analog systems, a continuously variable voltage on a wire (compared to ground) has a proportional relationship to a physical property.
- In digital systems, a set of wires carries voltages that together form a binary (base-2) number. This number represents a value for a physical property. In other words, the voltage on each wire corresponds to the binary value “0″ or “1″. Together these weighted bits form a binary number.
- In microprocessor systems, a programmable device takes digital input signals, processes them according to instructions stored in its memory and outputs results. The programmable device is called a Central Processing Unit (CPU).

Digital logic

Digital systems make logical operations based on their input signals.
- The basic binary operations are AND, OR, XOR and NOT.
- The relation between inputs and the single output can be expressed using a truth table as shown in the figure on the right.
  :
Digital logic can be implemented in various ways:
- Relays, the mechanical parts make them relatively slow, and causes wear out tear.
- Vacuum tubes, as used in early computers.
- Semiconductor, as will be discussed in this text.
- Proteins, promising but still in a research phase.
  :
Lab work:
- Experiment using snap-circuits or a simulator by:
  - building an OR function using parallel switches
  - building an AND-function using series switches
  - building a NOT-function using a relay

Diodes

Model
- A diode is a semi-conductor device that
  - conducts electrical current in one direction (once a certain threshold voltage is present), and
  - blocks current in the other direction.
    :
Semi-conductor physics
- A semi-conductor is a material with properties in between conductors and insulators in the periodic table. The element silicon is a commonly used semi-conductor material. (see also Periodic table)
- Silicon has 4 electrons in the outer shell (valence shell). It forms a covalent bond with 4 neighboring atoms so that its valence shell all 8 electrons present. The strong bond holds the atoms together that makes the element stable. This orderly crystal-like structure is called a lattice. There are no free electrons and the material will not conduct electricity. (see also Covalent bonding, PN-junction)
- Conductivity can be increased by adding very small (<1 ppm) impurities. Examples of impurities are phosphorous and boron.
  - Phosphorous, with 5 electrons in valence band, leaves an extra electron that can move easily. The resulting material is called n-type because of the abundance of negative electrons.
    - When a voltage is applied 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.
  - Boron, with 3 electrons in the valence band, leaves a hole where an electron can go. The holes move only if a neighboring electron jumps into the hole to fill the empty bond, thereby creating a new hole in the neighboring location. Whenever a hole is present, there is, in effect 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 material to the negative terminal. Electrons from the external circuit enter the negative terminal of the material and fill holes in the vicinity of this terminal. At the positive terminal, electrons are removed from the covalent bonds, thus creating new holes. This process continues as the steady stream of holes (hole current) moves toward the negative terminal. (see Diodes and Transistors)
- PN-junction. When a p-type and n-type material are brought in close contact, recombination happens:
  - In the interface layer, the electrons from the n-type silicon and the holes from the p-type silicon attract and eliminate each other. Because there is a lack of free electrons and holes in this area, it is known as the depletion region.
  - The loss of an electron from the n-type material creates a positive ion in the n-type material, while the loss of a hole from the p-type material creates a negative ion in that material. These charged ions are fixed in place in the crystal lattice structure and creates an electrostatic field across the junction.
  - The diffusion of electrons and holes across the junction will continue until the magnitude of the electrostatic field is increased to the point where the electrons and holes no longer have enough energy to overcome it, and are repelled by the negative and positive ions respectively. At this point equilibrium is established and, for all practical purposes, the movement of carriers across the junction ceases. For this reason, the electrostatic field created by the positive and negative ions in the depletion region is called a barrier.
    By manipulating this non-conductive layer, p-n junctions are commonly used as diodes.
  - Forward bias occurs when the p-type block is connected to the positive terminal of a battery and the n-type is connected to the negative terminal of the battery, the holes in the p-type region and the electrons in the n-type region are pushed towards the junction. This reduces the width of the depletion zone and eventually once enough potential is applied to overcome the depletion potential, the diode starts conducting. This depletion potential (or diode turn-on voltage) is 0.65V for silicon.
  - Reversing the voltage potential, increases the depletion zone and the diode will not conduct. (see also Navy electronics, Electronics tutorials)
    :
Lab work:
- Simulate a diode and resistor in series. Notice conducting starts once turn-on voltage is met. Use either
  - OrCAD A/D, DC Sweep from -5 to 5V, and plot U_out.
  - Yenka Technology, use the “Current in Diodes” model. Hover over the wires to see the voltage potential and current.
- Simulate the physics of a diode using “Diode structure” (free web version)

Diode-resistor logic

Model
- Boolean logic gates can be constructed using diodes acting as electrically operated switches.
  :
Logic OR-gate
- If at least one of the inputs is “1″ (5 volt), the output will be “1″. Otherwise the output will be 0. In boolean algebra that is written as X = A + B
- A logic OR-gate can be constructed from two diodes and a pull-down resistor as shown in the figure on the right. The D1N148 is a common switching diode. If both inputs are “0″, then the resistor will pull the output to ground (“0″). If either input is “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″. (See also DL OR gate.)
  :
Logic AND-gate
- If both inputs are “1″ (5 Volts), the output will be 1. Otherwise the output will be “0″. In boolean algebra this is written as X = A · B
- A OR gate can be made as shown in the figure on the right. If both inputs are “0″, current will flow through the diode, making the output equal to the diode voltage drop (0.65V). A logical “0″. Otherwise the resister will pull the output to 5V, a logical “1″. (See also DL AND gate.)
  :
Combining gates
- The single gate exhibited a small voltage difference from the ideal level of 0 and 5 volt. Cascading these gates will compound this problem as shown in the following example.
- The voltage drop in the diodes and power dissipation in the resistors degrade the signal as it passes through the gates. These problems are addressed by introducing another semiconductor, the transistors.
  :
Lab work
- OR-gate
  - Simulate this circuit using OrCAD A/D. Do a bias analysis for different combinations of the input voltage (0V or 5V). Note the results in a Truth Table. Note that a “1″ output is really 4.35 volt.
  - Build the circuit using the electronics learning lab, measure output voltage different combinations of the input voltage (0 or 5 volt). Note the results in a Truth Table.
- AND-gate
  - Simulate this circuit using OrCAD A/D. Do a bias analysis for different combinations of the input voltage (0 or 5 volt). Note the results in a Truth Table. Note that a ’0′ output is really 0.65 volt.
  - Build the circuit using the Electronics learning lab, measure output voltage different combinations of the input voltage (0V or 5V). Note the results in a Truth Table.
- Combining gates
  - Build the circuit with the two OR-gates feeding an AND-gate as shown in the theory above. Calculate, simulate or try the circuit in the lab. Exercise it with all inputs “0″ (0 Volt), and all inputs “1″ (5 Volt). Note that the output will be respectively 2.1 and 2.8V. (See also DL OR-AND Gate.)

Bipolar Junction Transistor (BJT)

Model
- Current to current amplifier.
  :
Physics
- Transistors are named after their composition:
  - NPN transistor, has a very thin p-type region between n and n⁺ type material. The ⁺ indicates more heavily doped material.
  - PNP transistor, has a very thin n-type region between p⁺ and p type material.
- The operation of the two types is very similar, except that in NPN transistors the electron flow is dominant, while PNP transistors rely mostly on the flow of “holes”. NPN transistors are more popular, because electrons move faster than holes. (see also Diode Transistor handout).
- An NPN transistor works as follows:
  - The base-emitter (BE) junction acts like a diode when it is forward-biased; thus, there is a flow of hole and electron currents from base to emitter when the collector is open. Some of the electron-hole pairs in the base will recombine; the remaining charge carriers will give rise to a net flow of current from base to emitter. It is also important to observe that the base is much narrower than the emitter section of the transistor.
  - When also reverse-biasing the base-collector (BC) junction, the electrons “emitted” by the emitter with the BE junction forward-biased reach the very narrow base region, and after a few are lost to recombination in the base, most of these electrons are “collected” by the collector. This phenomenon can take place because the base region is kept particularly narrow, and many of the electrons will have gathered enough momentum from the electric field to cross the reverse-biased collector-base junction and make it into the collector. The result is that there is a net flow of current from collector to emitter (opposite in direction to the flow of electrons), in addition to the hole current from base to emitter, I_b. The resulting current I_c is substantially larger than the current I_b that reduced the with of the BE depletion zone. The mall base current (I_b) controls the much larger collector current (I_c). (See also BJT)

Bipolar Junction Transistor based logic

Resistor-transistor logic (RTL)
- The problem with diode-resistor circuits was the signal degradation what 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 under all circumstances. This enables them to be cascaded indefinitely.
- The name bipolar refers to the two charge carriers: electrons and holes in the same crystal.
- If a +5v signal (logic 1) is applied to the base of the transistor (through an appropriate resistor to limit base-emitter forward voltage and current), the transistor turns fully on and grounds the output signal. If the input is grounded (logic 0), the transistor is off and the output signal is allowed to rise to +5 volts. This implies that the transistor inverts the logic sense of the signal, but it also ensures that the output voltage will always be a valid logic level under all circumstances.
- In other words, the transistor can be used as a switch by driving it back and forth between its “fully-OFF” (cut-off) and “fully-ON” (saturation) states.
  - “off” Here the operating conditions of the transistor are zero input base current (I_B), zero output collector current (I_C) and maximum collector voltage (V_CE) which results in a large depletion layer and no current flowing through the device. Therefore the transistor is switched “Fully-OFF”.
  - “on” Here the transistor will be biased so that the maximum amount of base current is applied, resulting in maximum collector current resulting in the minimum collector emitter voltage drop which results in the depletion layer being as small as possible and maximum current flowing through the transistor. Therefore the transistor is switched “Fully-ON”. (see also Transistor as a switch)
- Logic NOT-gate
  - With +5v at the base of the transistor (the 10kΩ limits I_be), the transistor turns “on” and grounds the output signal. If the input is 0V, the transistor is “off” and the output signal is pulled up to +5 volts.
  - Simulate or build the circuit. (see also RTL inverter)
- Logic NOR-gate
  - Combine multiple NOT-gates into a single 2-input NOR. Note that the number of inputs can be increased.
  - Simulate or build the circuit. (see also RTL NOR-gate)
    :
Diode-transistor logic (DTL)
- The RTL gates have two limitations:
  - the input resister and C_be create a RC time that slows down state transitions.
  - the input resistor take up a significant footprint in an integrated circuit.
- These limitations are addressed by replacing the input resistor with diodes. The diode connected to the transistor base raises the input voltage required to turn the transistor on to about 1.3 volt. Diodes are not only smaller but also have a low internal resistance when forward biased, thus allowing fasterswitching.
- For more examples of DTL-based gates refer to NAND-gate and NOR-gate.
  :
Transistor-transistor logic (see also TTL)
- In the DTL gate, there two diodes have their P-type anodes connected together and to the pull-up resistor. These diodes can be replaced with a single NPN transistor. This reduces the footprint, because a transistor requires about the same amount of space as a single diode. This allows a NOT-gate to be build as shown in the figure on the right.

Field Effect Transistor (FET)

Model
- Voltage to current amplifier.
  :
Junction Field-effect Transistor (JFET) physics
- The idea of a field-effect transistor (Lilienfeld,1926) is conceptually simple, but difficult to manufacture (Atalla, 1960) because the manufacturing environment needs to be extremely clean.
- Field-effect transistors can be divided in two groups based on their composition:
  - N-channel, has a n-type slab, with a p⁺ type gate. The ⁺indicates more heavily doped material.
  - P-channel, has a p-type slab, with a n⁺ type gate.
- The operation of the two types is very similar. The n-type JFET works as follows:
  - A lightly doped n-type slab has free electrons and conducts electricity. A heavy doped p-type region on both sides serves as a control electrode, the gate.
  - At the PN-junction, the electrons from the n-type silicon and the holes from the p-type silicon attract and eliminate each other forming an thin insulating depletion zone. With no gate bias (V_gs), this zone is so thin that it does not obstruct current between drain and source (I_d). The thickness of the depletion zone can be increased by applying a reverse bias on the gate. This pushes the holes from the p-type region and the electrons in the n-type region towards the junction. This increases the width of the depletion zone and 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. (see also JFET)
    :
Metal Oxide Semiconductor Field-effect Transistor (MOSFET) physics
- A MOSFET is similar to a JFET, except that the gate lead does not make a direct connection to the silicon. The gate is a metallic layer atop a silicon dioxide (or High-k dielectric) insulator.
- This type of transistor can be divided into two groups, also:
  - N-channel, has a p-type slap, with two n⁺-type gates
  - P-channel, has a n-type slap, with two p⁺-type gates
- The operation of the two types is very similar. The p-channel MOSFET works as follows:
  - The gate to the slab materials resembles a capacitor. When forward biased, p-type silicon repels electrons from the p-type substrate , that are attracted by the positive gate atop the oxide. This excess of electrons near the oxide creates an inverted (excess of electrons) channel under the oxide. On this PN-junction, a depletion region forms, isolating the channel from p-type substrate.
  - To make a MOSFET transistor, this capacitor is placed between a pair of n⁺-type diffusions. A positive bias on the gate, charges the capacitor. The p-type substrate below the gate takes on a negative charge. An inversion region with an excess of electrons forms below the gate oxide. This region now connects the source and drain n-type regions, forming a continuous N-region from source to drain. (see also MOSFET)
- These MOSFET transistors form building blocks for integrated circuits. Modern day microprocessors contain around 2 trillion MOSFETs. Each individual MOSFET devices is currently about 35 nanometer, or the width of 50 atoms.

Field Effect Transistor based logic

Most integrated circuits are based on field effect transistors. Their name Complementary Metal Oxide Semiconductor (CMOS), refers to the use of complementary pairs of p-type and n-type MOSFETs that implement logic functions.
:
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 circuits without resistors. CMOS draws no current, other than leakage, when in a steady 1 or 0 state. When the gate switches states, current is drawn to charge the capacitance at the output of the gate.
:
The gate does not draw a continuous current. Though, the gate draws a surge of current to charge the gate capacitance.
- simulation of gates using MOSFETS, Yenka Technology > Digital Electronics > CMOS equivalent
- Orcad/pSpice, generic switching p-channel bss84, n-channel bss87
- http://www.opamp-electronics.com/tutorials/digital_theory_ch_003.htm

Combinational logic

Gates, gates, nothing but gates
- In combinational logic the output is a pure function of the input values. Examples are adders, muxer and demuxers.
- Various combinations of logic gates are manufactured as integrated circuits. The figure on the right shows an example of a packaging with four two-input NAND gates.
- The two main logic families are:
  - 7400 (TTL-based), and
  - 4000 (CMOS-based).
- All other types of Boolean logic gates, such as AND, OR, NOT, XOR, XNOR, can be created from a suitable network of either NAND (or alternatively NOR) gates (Peirce, 1880).
- Following sections discus example implementations of a multiplexor and various math operations.
  :
Multiplexor
- A multiplexor uses a binary value (address) to select between several inputs. The output then assumes the value of that input.
- Method:
  - The truth table for a 2-to-1 multiplexer is shown on the right.
  - The output Y can be expressed as a function of the inputs:
  - This function can be implemented with gates as shown below. The circle at the input of the top NAND-gate represents an inverter.
    
    :
Addition
- The result of adding two n-bit numbers occupies at most n+1 bits (n-bits and carry bit).
- Method: ripple-carry, or carry propagation
  - The basic building block is a 1-bit adder with inputs A and B representing the 1-bit binary numbers being added.
    - S is the bit of the resulting sum.
    - C_i and C_o are the incoming and outgoing carry bits. The carry is similar as when adding decimal numbers — if you have a carry from one column to the next, and the next column has to include that carry.
  - The relation between the inputs and outputs is shown in the truth table shown above.
  - The outputs S and C_o can be expressed as a function of the inputs:
  - The figure on the right shows an implementation with gates. This can be abstracted into a building block called a “full adder”.
  - These building blocks can then be used to build a 4-bit adder.
  - The ripple carry propagation limits the speed of the circuit, since each more significant column in the sum must wait for the carries in the less significant columns. The carry generation can be greatly improved by adding a carry-look-ahead function. also see FPGA adder)
    :
Subtraction
- Computers represent negative numbers by the two’s complement of the absolute value. Most significant bit (msb) is given a negative weight. Other bits are the same as in unsigned. The advantage is that the circuits can treat positive and negative numbers the same when doing arithmetic.
  - A number is negated by inverting its bits and adding 1 to the number.
  - This implies that positive numbers have “0″ as their most significant bit, and negative numbers have “1″ as their most-significant bit.
  - See also the lecture Arithmetic structures for implementations with 2s complement.
- Method 1: ripple-borrow
  - Start by building a 1-bit subtractor where the inputs A and B represent the 1-bit binary numbers being added. D is the bit of the resulting difference. L_i and L_o are the incoming and outgoing loan (borrow) signals. The relation between the inputs and outputs is shown in the truth table on the right.
  - The outputs D and L_o can be expressed as a function of the inputs:
    
    The result D is still an Exclusive-OR function, just as the sum was for addition. The loan function is slightly different.
  - These building blocks can then be used to build a 4-bit subtractor.
- Method 2: A + -B
  - This method changes the adder to a circuit that adds when OP=1 and subtracts when OP=0. It uses the fact that A + B = A + (-B).
  - Under twos complement, subtracting B is the same as adding the bitwise complement of B then adding 1:
    - negate B by inverting its bit (using the XOR), and
    - add 1 by setting the least significant C_in to 1.
  - The circuit shown below also includes a overflow detection for twos complement.
    
    :
Multiplication
- Multiplication shows how simple logic functions can be combined to make a much more complex function.
- Method 1: partial products
  - The result of multiplying two n-bit numbers occupies up to 2×n bits.Multiplying the 4-bit numbers A and B can be written as A₃A₂A₁A0 × B₃B₂B₁B₀. The product can then be found by adding the partial products.
  - A basic building block can be made using:
    - Forming the partial product of two binary digits is simply an AND operation.
    - Adding the partial sums can be accomplished with 1-bit full adders.
  - These building blocks can then be used to build a 4-bit multiplier as shown in the figure below. (see also “Combinational multiplier“)
- Method 2: quarter squares
  - ¼·(A + B)² - ¼·(A – B)² = ¼·(A² + 2·A·B + B²) – ¼·(A² – 2·A·B + B²) =A·B
    - hard wire a look-up table of squares
    - calculate A + B, and look up C = (A + B)²
    - calculate A – B, and look up D = (A – B)²
    - calculate C – D, and divide by 4. The result is A × B^.
  - So three additions, two table look ups and divide by 4 (right shift by 2 bits).
  - The size of the look up tables scales nicely linear with the length of the operands.
    :
Division
- 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)
- Algorithm 1: attempt subtraction
  - In calculating A / B, the divisor B is repeatedly subtracted from the digits of the dividend (A), after being multiplied either with ’1′ or with ’0′. This multiplication bit (’1′ or ’0′) is selected for each subtraction step in such a manner that the subtraction result is not negative. The division result is composed from all the successive multiplication bits while the remainder is the result of the last subtraction step.
  - This algorithm can be implemented by a series of subtractors. 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.
  - Each divider module:
    - contains a 1-bit subtractor with the usual inputs A, B and L_i and outputs D and L_o.
    - the output select (OS) signal selects between bit X and A-B. The signal is connected to the loan output (Lo) 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 signal selects between bitA and A-B.
    - The outputs can be expressed as a function of the inputs as in:
  - The complete division can therefore be implemented by a matrix of divider cells connected on rows and columns as shown in figure on the right.
  - Each row performs one multiplication-and-subtraction cycle where the multiplication bit is supplied by the NOT logic gate at the end of each row. (also see “Combinational arithmetic“)
  - The number of gates increases with the square width of the numbers being divided. This limits its use to designs where bit-width is relatively small, typically around 16 bits or below.
    :
Lab work
- Before you start:
  - Electronics learning lab uses real CMOS gates. It is fun to make something, but also requires careful handling the CMOS parts.
  - Yenka Technology is a nice entry level simulation. It is intuitive, good support for digital logic and allows hierarchical designs.
  - Xilinx ISE is a professional FPGA simulation and bitstream generation tool. It has support for test vectors and timing analysis. More on FPGAs later.
- Exercise the inputs of a NAND circuit and observe the output, using:
  - Electronics learning lab, see Digital logic projects page 34/35
  - Yenka Technology, using a latching logic input, 7408 AND gate and logic indicators.
- Create NOR function using NAND gates, using
  - Electronics learning lab, see Digital logic projects, page 40/41
  - Yenka Technology, using a latching logic input, 7400 NAND gates and logic indicators.
- Simulate a 2-bit adder, using
  - Electronics learning lab, or
  - Yenka Technology, or
  - Xilinx ISE.
- Simulate a 2-bit subtractor using Yenka Technology, using
  - Yenka Technology employing an hierarchical design or
  - Xilinx ISE.
- Simulate a 8-bit adder/subtractor, using
  - Xilinx ISE.

Synchronous sequential logic

The logic that we have seen so far can be used for simple math. Limitations of the combinational logic are:

The input values need to remain constant during the calculation.
The output can have multiple logical transitions before settling to the correct value. The figure on the right shows that even adding two numbers without carry may cause multiple transitions. (32-bit adder simulation of adding 0 to 1 implemented in Altera FPGA).
There is no indication when the output has settled to the correct value.

This chapter introduces memory elements to hold input and output values, and a clock signal that indicates when the output value has settled.

Types of logic circuits:
- Combinational (as we have seen so far)
  - The output depends on the present inputs.
  - The output can have multiple logical transitions before settling to the correct value.
- Asynchronous sequential
  - The output depends the present inputs and previous output.
  - The output can have multiple logical transitions before settling to the correct value.
- Synchronous sequential
  - The output depends on the present inputs and previous output.
  - A clock signal synchronizes state transitions:
    - inputs, are only sampled during the active part of the clock cycle
    - outputs, are “held” until the next state is computed, thereby preventing multiple logical transitions.
  - The figure on the right shows an example of an synchronous sequential circuit. In it, a D flip-flop serves as a clocked memory element. The next section will examine the various memory element.
    :
Inverter latch (asynchronous)
- Memory elements can be made using positive feedback.
- The figure on the right shows an implementation using two inverters. This circuit will maintain its state, but lacking any inputs that state cannot be changed.
- In the following SR latch these inverters are change to NOR gates, thereby introducing two inputs to this circuit.
  :
SR latch (asynchronous)
- Extension of the inverter latch, introducing two inputs:
  - Set (S), forces the next value of the output (Q_n+1 ) to ’1′.
  - Reset (R), force the next value of the output (Q_n+1 ) to ’0′.
- The state transition diagram provides a visual abstraction. It uses
  - circles, for the output states
  - arrows, for the transition conditions.
- A complete diagram takes all the inputs (R and S) into account.
- The state transition table shows the relationship between the inputs, the current value of the output (Q_n), and the nextvalue of the output (Q_n+1). The ‘×‘ represents a “don’t care” condition.
- This function can be expressed in boolean algebra as:
- Alternatively, the function can be written and build using NOR-gates:
- For more info refer to the slides from MIT lecture “FSM and synchronisation“.
  :
D latch (synchronous)
- Synchronous variant of the SR latch with inputs:
  - Data (D), the data bit being stored
    - D=1, will set the latch to ’1′.
    - D=0, will reset the latch to ’0′.
  - Enable (EN), controls the internal set and reset signals. It serves as a level triggered clock input. Level triggered means that the input is passed to the output for was long as the clock is active.
    - EN=1, the value of D is passed to output Q.
    - EN=0, the output maintains its state.
- The circuit shown on the right implements a D latch. Note that the SR latch is drawn slightly different.
  :
D flip-flop (synchronous)
- Edge triggered memory element using two D latches. The first latch uses an inverted clock signal.
  - Data (D), the data bit being stored.
  - Clock (clk), controls when the value of D is accepted and presented at the output. The ‘>‘ symbol indicates that the clock input is sampled on the rising clock edge.
    - while clk=0, the value of D is copied in the first latch.
    - once clk becomes ’1′, the value from the first latch is copied to output Q
- For this edge triggered memory element, the input signal only needs to remain stable while it is being copied to the second latch. The so-called timing window:
  - Setup time (T_su), the minimum time before the clock event by which the input must be stable.
  - Hold time (T_h), the minimum time after the clock event during which the input must remain stable.
  - Propagation delay (T_cq), the maximum time after the clock event for the output to change.
    :
Register
- A register is a memory element that expands on the D flip-flip:
  - Load input, limits when new data is loaded into the register (only if LD=1 during the active edge of the clock). In the figure on the right this is implemented using a 2:1 multiplexer.
  - Multiple data bits are stored together. An n-bit register consists of nblocks that share the LDand clk signals.
- A sequence of bits is commonly written as D(15:0) meaning bits D₁₅ .. D₀.
  :
Large memories
- Memory consists of a large number of locations that each can store a value. Each location in a memory is given a number, called an address.
  - Memory locations, are identified by a k-bit wide address.
  - Each memory location can store a n-bit wide value.
  - The figure on the right gives an example of 16-bit addresses storing 16-bit values. To save space in this figure, hexadecimal (base-16) notation is used to represent the address and value.
- Bit density is key in building large memories. Instead of D flip-flops, large memories use more efficient methods such as:
  - Static Random Access Memory (SRAM), with
    - six transistors per memory bit,
    - relies on a feedback between two gated inverters.
  - Dynamic Random Access Memory (DRAM), with
    - one transistor per memory bit,
    - relies on an electrical charge stored in the capacitor of a MOSFET gate,
    - the drawback is that the charge has to be refreshed periodically.
- A DRAM can be implemented as
  - A single bit (cell) can be implemented as shown on the right. In this the capacitor saves the state. The transistor limits access to the capacitor.
    - To read, select raised; the charge in the capacitor the appears on pin D.
    - To write, select is raised for long enough to charge or drain the capacitor to the value of D.
  - These cells can be combined for form a large memory. The cells are organized in a matrix structure, to keep the size of the address demultiplexer practical. Otherwise to implement k address lines, a demux with 2k outputs would be needed. The figure below shows a simplified structure implementation using a 4-bit address (and 1 bit wide).
  - To make a n-bit wide memory, n memory DRAM chips can be combined.
- For more info refer to slides from MIT lectures ”Sequential building blocks” and “Memory Elements” and the web site lwn.net)
  :
Clock
- In sequential circuits, a clock signal orchestrates the state transitions. This clock is generally a square wave generated by a astable multivibrator. A delayed negative feedback causing it to oscillates between ’0′ and ’1′ .
- An implementation using inverters and a RC circuit is shown on the right. The functionality can be explained as follows:
  - Suppose initially:
    - output U₃=0V (a logical ’0′), and
    - the capacitor is not charged .·. U₁=U₃
  - 0→1:
    - The capacitor charges through resistor R .·. U₁ increases towards 5V.
    - Once U₁≥2V (the ’1′ threshold) .·. U₂ becomes 0V .·. output U₃ becomes 5V (a logical ’1′)
  - 1→0:
    - The capacitor charge reverses through the resistor R .·. U₁decreases towards 0V.
    - Once U₁≤0.7V (the ’0′ threshold) .·. U₂ becomes 5V .·. output U₃ becomes 0V (a logical ’0′), and the cycle repeats itself.
      :
Lab work
- D latch, Yenka Technology, Digital Electronics, build d-latch using gates, use models for d-type flip-flip, binary counter
- Build or simulate a set-reset latch using NOR gates. (see Digital logic projects, page 27)
- Build or simulate a D-latch using NAND gates. (see Digital logic projects, page 6)

Programmable logic

Complexity – CAD – Simulation ….

Logic devices can be classified into two broad categories :
- Fixed devices, where the circuits are permanent. Their function cannot be changed. Examples are:
  - gates (NAND, NOR, XOR),
  - binary counters,
  - multiplexers, and
  - adders.
- Application-Specific Integrated Circuit (ASIC)
  - The manufacturer defines a integrated circuit containing transistors, but does not connect them together.
  - The user specifies the metal mask that connects the transistors.
  - The manufacturer uses this mask to finish the ASIC.
  - Introduced by Fairchild in 1967. Have since grown to contain over 100 million gates.
- Programmable logic devices (PLD), can be changed at any time to perform any number of functions. Prominent flavors of PLDs are:
  - Programmable array logic (PAL)
    - based on sum-of-products, with programmable “fuses”,
    - used for simple combinational logic (a few 100′s gates),
    - introduced by MMI (Birkner and Chua, 1978).
    - The figure on the right shows an example of an AND function with programmable fuses.
  - Complex programmable logic device (CPLD)
    - based on sum-of-products,
    - for medium size combinational logic (10,000′s gates).
  - Field-programmable gate array (FPGA)
    - based on blocks containing a look-up tables, full adder and d flip-flop,
    - used for complex combinational or sequential logic such as state machines (1,000,000′s gates),
    - introduced by Xilinx (Freeman, Vonderschmitt) in 1985.
- A CPLD would be sufficient to implement the combinational circuits discussed so far, however our ultimate goal is to create a modest microprocessor circuit. As we will see later, a microprocessor circuit requires a state machine for which we need a FPGA. As a result the remainder of this text will focus on a FPGAs implementation.
  :
The core of a FPGAs contains a vast array of interconnected logic cells.
- The exact logic cell architecture depends on the vendor. (refer toFPGA logic cells for typical cell architectures.)
- The main vendors are:
  - Xilinx for leading edge products, and
  - Altera for lean and efficient devices .
- In general:
- The functionality of an FPGA can be changed by downloading a different configuration.
- The circuits are often much faster as with discrete components, because the signals stay within the silicon die of the FPGA.
- The figure below shows a typical matrix organization of the logic cells that are interconnected using programmable interconnects.
  
  :
Lab environment (thanks Dylon)
- Altera, much butter tools.
- Boards
  - Xilinx, development boards are easy to find. E.g. Spartan6 ($89 at Avnet) that has a USB-to-UART chip on it so you can plug it right into your computer to download new FPGA code as well as use it as a UART.
  - Alternatively, the Xilinx Spartan3E development board is an old standby that works well.
- Simulator
  - icarus verilog (free simulator, yum install iverilog) and GTKWave (free waveform viewer, yum install gtkwave) work great. They are just as good as most of the bundled simulators that you’ll find with the tools.
  - a web copy of ModelSim bundled with Xilinx or Altera that wouldn’t be bad either.
- Cliff Cummings posted papers about verilog, and book recommendations.
- OpenCores has lots of verilog and VHDL code for most any kind of core you can imagine.
- Scripts SimShop and Tizzy for simulation and state machines! SimShop provides an easy scriptable way to set up a simulation environment, and Tizzy allows you to write state machines in .dot and will do a conversion to verilog for you.
xx
- Xilinx
  - Hierarchical schematic design entry, note Test Bench Waveform Editor is no longer included in ISE 11.
  - Verilog Test Fixture tutorial
- Advanced digital simulation and synthesis, Quartus II including ModelSim, Altera (free Web version)
  - Tutorials as part of Quartus
  - Hierarchical schematic design entry
  - Other tutorials
xx
The typical workflow:
- The desired logic is specified using traditional schematics or a hardware description language.
- The logic function is compiled into a binary file that can be downloaded into the FPGA.
- Test vectors and output verification.
- The binary file is download the FPGA.
The application-specific integrated circuit (ASIC), is similar to the FPGA, except that it is not reprogrammable. The advantage is higher speed and smaller footprint.
Hardware description language (HDL)
1. Verilog/VHDL
2. netlist
3. synthesis optimizes the functions
4. mapping to hardware
build-in components are called macros (counters, RAM, multiplexers, adders, LUT)
See “Introduction to Verilog“
In order the obtain reasonable speeds (wires are not ideal), the utilization is typically limited to about 50%.
Lab work
- FPGA tools for design entry, simulation, synthesis and uploading is available from: (see alsocomparison)
  - Altera, Quartus II Web Edition, includes timing simulation and an embedded logic analyzer (free for small and medium FPGAs)
  - Xilinx, ISE WebPack (see also Schematic tutorial and Behavior simulation tutorial). (free for medium FPGAs)
- Build an 8-bit adder

Arithmetic Logical Unit (ALU)

Arithmetic Logical Unit (ALU)
- http://ecen3233.okstate.edu/Fall%202009/labs/Lab05.pdf
- soft cores for Xilinx, http://www.1-core.com/library/digital/soft-cpu-cores/
Add Simple picture showing different functions feeding into a multiplexor where the operation is the selector.

The inquiry “How do microprocessors work?” picks up from here.

alex9ufo 聰明人求知心切

2014年11月22日星期六